分布式系统协调和协定

1、分布式系统协调和协定第1页，共47页，2022年，5月20日，10点12分，星期一第七章 协调和协定简介分布式互斥选举组播通信共识问题2第2页，共47页，2022年，5月20日，10点12分，星期一7.1 简介分布式系统的一个基本目的：供一组进程来协调他们的动作或对一个或多个值达成协议避免固定的主从关系的原因：经常需要系统即使在故障出现时也能保持正确的工作，因此需要避免单结点例如固定的主控器的故障3第3页，共47页，2022年，5月20日，10点12分，星期一共享资源访问方式故障的处理故障和故障的检测同步系统：可靠的故障检测异步系统：不可靠的故障检测4第4页，共47页，2022年，5月20日，

2、10点12分，星期一故障检测完整性：有失效的进程就能被检测出来正确性：正常的进程不会被认为失效强完整性、弱完整性强准确性、弱准确性、最终强准确性、最终弱准确性不可靠的故障检测消息的延迟消息的丢失5第5页，共47页，2022年，5月20日，10点12分，星期一7.2 分布式互斥分布式互斥共享资源的协调基于消息的传递互斥算法临界区要求ME1(安全性)：最多一个进程进入临界区ME2(活性)：进入和离开临界区的请求最终成功ME3(顺序)：先请求，先进入性能评价消耗的带宽：进入和退出临界区的消息数目延迟：每次进入和退出导致的客户延迟吞吐量：系统吞吐量6第6页，共47页，2022年，5月20日，10点12

3、分，星期一中央服务器法服务器专门授理访问临界区的请求，令牌为进入临界区每个进程需向该服务器发出请求允许进入，服务器授予令牌，应答令牌被占用，放入缓冲区等待退出临界区，进程发送消息，则令牌释放，取出等待队列中的进程，授予令牌，应答7第7页，共47页，2022年，5月20日，10点12分，星期一中央服务器法满足ME1？满足 ME2？满足ME3？满足ME1，满足 ME2不能满足ME3性能带宽：3个消息（请求、授权、离开）；延迟：请求进入2N个消息间隔，退出：1个消息间隔吞吐量：2个消息的间隔8第8页，共47页，2022年，5月20日，10点12分，星期一基于环的算法地位对等，不需要单独的服务器令牌令

4、牌连续的单向传输只有获得令牌才有权进入临界区获得令牌-占用令牌-进入临界区-退出临界区-释放令牌9第9页，共47页，2022年，5月20日，10点12分，星期一基于环的算法满足ME1，满足 ME2，不满足ME3性能带宽：1 N个消息进入临界区 0 N-1个消息退出临界区1个消息延迟：1 N个消息的间隔吞吐量：1 N个消息的间隔10第10页，共47页，2022年，5月20日，10点12分，星期一使用组播和逻辑时钟的算法(Ricart and Agrawala)引入逻辑时钟，确定动作的先后关系状态变量：RELEASED, WANTED, HELD进程Pi初始化：state:= RELEASED;T

5、ask1：state:=WANTED; T:=时间戳； send (Ti,Pi) to all process; Wait until (receive N-1 answer); state:=HELD; 11第11页，共47页，2022年，5月20日，10点12分，星期一使用组播和逻辑时钟的算法(Ricart and Agrawala)Task2：receive a massage (Ti,Pi);if (state:=HELD or (state:=WANTED) and (Tj,Pj)(Ti,Pi) 将(TiPi)放入请求队列; else answer (Pi);Task3： state

6、:= RELEASED; answer 队列中的所有请求；12第12页，共47页，2022年，5月20日，10点12分，星期一算法讨论满足ME1,满足 ME2, 满足ME3性能带宽：进入临界区2（N-1）个消息， N-1个用于组播， N-1个用于应答退出0-(N-1)个消息延迟：请求进入 2 N个消息间隔吞吐率：1个消息的间隔13第13页，共47页，2022年，5月20日，10点12分，星期一Maekawa 算法选举的方法获得部分支持就可以进入临界区定义: 进程集合 P1,P2PiPN 对任意进程的选举集合 Vi 是进程集合的真子集 有：Pi Vi ; Vi Vj ; | Vi |=| Vj|

7、=K;14第14页，共47页，2022年，5月20日，10点12分，星期一进程Pi初始化: state :=RELEASED; voted:=FALSE; Task1: state:=WANTED; send request to Vi-Pi wait until (the number of answer = (K-1) state:=HELD Task2: receive the request from Pi ; if(state=HELD or voted=true) 将Pi放入请求队列 else answer Pi ； voted:=true; 15第15页，共47页，2022年，5

8、月20日，10点12分，星期一Task3: state :=RELEASED; send released message to Vi-Pi;Task4: Pj（ji）receive the released message from Pi ; if (请求队列非空) 删除队列头部的Pk; answer Pk; voted:=TRUE; else voted:= FALSE;16第16页，共47页，2022年，5月20日，10点12分，星期一讨论ME1? YesME2? Yes?（p1，p2，p3）都申请ME3? No改进加入逻辑时钟ME2， ME3 yes性能带宽：进入2(K-1)个消息，退

9、出K-1个消息延迟：请求进入 2 N个消息间隔，与Ricart and Agrawala 相同吞吐率：2个消息间隔17第17页，共47页，2022年，5月20日，10点12分，星期一容错？消息的丢失？不能容忍进程崩溃？中央服务器法可以容忍一个既不申请，也不持有令牌的进程崩溃，基于环的算法不能容忍任一个进程崩溃Maekawa算法，如不在一个投票集中，可以容忍Ricart and Agrawala 算法不能容忍任一个进程崩溃18第18页，共47页，2022年，5月20日，10点12分，星期一7.3 选举选举对象：扮演特定角色的唯一进程目的：找到一个大家认可的替代者属性：定义变量electedE1(

10、安全性)： elected为未决，或为P，E2(活性)：所有进程都参加且最终elected不为空，或崩溃性能：带宽使用：发送消息的总数算法的回转时间：从启动算法到中止算法，串行消息的传输次数19第19页，共47页，2022年，5月20日，10点12分，星期一基于环的选举算法(Chang and Roberts)逻辑环排列的进程顺时针发送过程 ：选举出一个协调者1、最初，所有进程都是选举中的非参加者，所有进程都有一个标示2、开始一次选举，自己标为参加者，将自己的标示放到消息中发到下一个进程20第20页，共47页，2022年，5月20日，10点12分，星期一基于环的选举算法(Chang and R

11、oberts)3、当一个进程收到一个选举消息。1）如果消息内的标示比自己的标示大，则转发消息到下一个邻居，标自己为参加者。2）标示比自己的小且自己不是参加者，则选举消息替换成自己的标示，发送，标自己为参加者；3）标示比自己的小且自己是参加者，则不转发消息4、如果收到的标示是接收者自己的，则自己被选举成为协调者。向邻居发送当选消息，并标记为非参加者5、任一个进程收到当选消息，置变量elected，并标记为非参加者，转发当选消息21第21页，共47页，2022年，5月20日，10点12分，星期一讨论E1（安全性）：满足所有的标识都比较一个进程当选必须收回自己的标识任意两个进程，标识较大的不会传递标

12、识较小的进程标识，不可能两者都收到自己的标识E2（活性）：满足遍历环，所有人都参加22第22页，共47页，2022年，5月20日，10点12分，星期一性能当只有一个进程启动选举最坏的情况，3N-1个消息逆时针邻居具有最大标识，到达该邻居需要N-1个消息回路N个消息当选发送N个消息最好的情况，2N个消息算法的限制假设消息传输是可靠的假设无进程崩溃23第23页，共47页，2022年，5月20日，10点12分，星期一霸道算法假设消息传输是可靠的，且有上界假设可能会发生进程崩溃同步（环：异步）可以和所有进程通信且知道标识较高的进程（环：邻居）消息的类型选举消息：选举某进程为协调者的消息回答消息：回复选

13、举的结果协调者消息：“新协调者”宣布当选24第24页，共47页，2022年，5月20日，10点12分，星期一25过程：任一个进程开始选举1、知道自己是最大标示的进程，直接认为自己是协调者进程，并发送协调者消息2、具有较低标示的进程开始一次选举，发选举消息给比自己标示大的进程，等待应答消息若无应答消息，则认定自己是协调者有消息应答，则等待接受协调者消息无协调者消息，则再进行一次选举3、若收到一个选举消息，回送应答。若自己没开始选举，则自己开始一次选举4、若收到协调者消息，则认定新的协调者第25页，共47页，2022年，5月20日，10点12分，星期一讨论E1 （安全性）：满足没有进程被替换E2（

14、活性）：满足根据可靠消息传递的假设性能最好的情况N-2个消息标识最大的进程发现协调者错误，发送N-2个协调者消息最坏情况O(N2)个消息标识最小的进程发现协调者错误，然后N-1个进程开始选举，每个进程都发送消息到较大标识的进程26第26页，共47页，2022年，5月20日，10点12分，星期一7.4 组播通信特点一个进程只调用一个组播操作来发送一个消息到组中的每个进程不是多次发送同一个消息到不同进程效率：程序员方便，硬件的支持传递保证：无法保证系统模型组标识：G封闭组：只有G内的成员可以发送消息给G开放组：组G外的成员也可以发送消息给G27第27页，共47页，2022年，5月20日，10点12

15、分，星期一静态组与动态组静态组：组内成员不可变更的组，组成员按照某种方式事先定义，以后无论发生什么情况都不可变更动态组：允许组成员动态地加入退出。一个进程可以提出请求，加入（Join）一个组，从而成为这个组的成员，也可以要求离开或由于失效而退出（Leave）这个组28第28页，共47页，2022年，5月20日，10点12分，星期一静态组与动态组动态组提供面向视图（View-Oriented）的组成员服务（Group Membership Service）视图（View）是组中当前活跃的成员（进程）列表，每个视图都有一个唯一的标志，组成员服务跟踪组的成员关系随时间的变化。当组成员列表发生变化，组

16、成员服务负责通知组的各个成员，组成员就会安装（Install）新的视图29第29页，共47页，2022年，5月20日，10点12分，星期一消息通信服务根据消息传输是否可靠，消息通信服务可分为不可靠多播（Unreliable Multicast）和可靠多播（Reliable Muticast）不可靠多播类似UDP提供的数据报服务，不保证消息安全到达所有接收方。可靠多播保证消息被所有接收方安全收到（Receive），但并不保证被接收方安全接收（Deliver）区分接收（Deliver）和收到（Receive）。一个进程收到消息后可以先不接收它（送交上层应用），即接收是应用层行为，而收到在通信层行为

17、30第30页，共47页，2022年，5月20日，10点12分，星期一消息通信服务按照消息的顺序特性，消息通信服务可分为无序、先入先出顺序（FIFO Order）、因果序（Causal Order）、全序（Total Order）等。31第31页，共47页，2022年，5月20日，10点12分，星期一基本组播原语 B-multicast(g,m)：对每个属于组g的进程p, send(p,m)，可靠的一对一 send操作进程p执行 receive(m)时：进程执行 B-deliver(m) 可靠组播完整性（安全性）：任何传递的消息与发送的消息相同，且不会被重复传递有效性（活性）：任何消息都会被传送

18、到目的地协定：如果一个正确的进程收到消息，则组中所有正确成员都终将收到该消息32第32页，共47页，2022年，5月20日，10点12分，星期一用B-multicast实现可靠组播算法每个消息被发给每个进程|g|次满足有效性，可靠的通信保证完整性， B-deliver(m) 保证协定33过程：进程P, 组g初始化：Received:=;发送, 进程P R-Multicast (m)： 进程P,B-Multicast(g,m)；接受：进程Q B-deliver(m) 时,其中g=group（m）if m Received;thenReceived:= Receivedm;if (PQ) then

19、 P,B-Multicast(g,m) ； end if R-deliver (m);end if第33页，共47页，2022年，5月20日，10点12分，星期一基于IP组播实现可靠组播每个进程有一个唯一的消息顺序数Sp每个进程记载一组消息顺序数（Sp,Sq）进程P,R-Multicast (m)时， Sp =Sp+1，所有send上携带Sgp，并分别携带确认进程V接收m，如S= Rgp +1， 则R-deliver(m) ，并且接收后Rgp +1；进程V接收m，如S Rgp ，则丢掉此消息进程V接收m，如S Rgp +1，则表明漏掉了进程P的某些个消息，保留m到队列，发送重发的确认34第34

20、页，共47页，2022年，5月20日，10点12分，星期一有序组播FIFO排序：一个进程的Multicast(g,m)在Multicast(g,m)前面，则每个正确传递m的进程将在m前传递m因果排序：如果Multicast(g,m) - Multicast(g,m) ,则每个正确传递m的进程将在m前传递m全排序：如果一个正确传递m的进程在m前传递m，那么其他正确传递m的进程将在m前传递m35第35页，共47页，2022年，5月20日，10点12分，星期一性质因果排序隐含FIFO排序全排序不一定是因果排序或FIFO排序全排序消息在不同进程中是顺序一样的前提下允许消息随机排序有序组播不一定隐含可靠

21、组播正确进程p传递消息m然后传递m，q传递m，不一定传递m36第36页，共47页，2022年，5月20日，10点12分，星期一实现FIFO排序两个顺序数变量SPg ,进程p发送到g的消息计数Rqg, 进程p传递进程q并发往组g的最近的消息顺序数过程Multicast消息附带SPg ；检查收到的进程q的消息序数与Rqg+1的关系，等于则接受，否则，放入等待队列37第37页，共47页，2022年，5月20日，10点12分，星期一全排序组播维持一个组特定的顺序数S协调者进程sequence(g)来管理标识进程P Multicast(g,m)的消息中带有本进程的顺序数Rp，同时也被发给sequence

22、(g)进程sequence(g)，收到该消息，S=S+1， Multicast(g,);进程Q 收到消息m，放入等待队列，直到收到,消息，判断S的值是否顺序，然后从等待队列中取出消息m38第38页，共47页，2022年，5月20日，10点12分，星期一7.5 共识问题 (Consensus)共识一个协定一个或多个进程提议了一个值应当是什么后，所有进程对这个值达成协定系统模型一组通过消息传递进行通信的进程通信是可靠的可能出现故障：拜占庭故障和崩溃故障39第39页，共47页，2022年，5月20日，10点12分，星期一共识的定义每个进程处于未决状态，并提议集合D中的一个值vi。进程间相互通信，交换值。最后，每个进程设定一个约定变量di的值共识算法的要求是在每次运行中满足以下条件：终止性：每个正确的进程最终设定它的决定变量协定性：所有正确进程的决定变量都相同完整性：如果正确的进程都提议相同的值，那么在决定状态的任何正确进程已选择了该值40第40页，共47页，2022年，5月20日，10点12分，星期一同步的，不出故障的系统的共识问题解决每个进程采用可靠的组播，发出自己的协议值每个进程收到协议值，采用设定的函数选取决定变量终止性由可靠组播的有效性和协定性保证协定性由可靠组播的完整性和设定的函数保证41第41页，共47页，2022年，