《分布式系统_11_协调和协定》由会员分享，可在线阅读，更多相关《分布式系统_11_协调和协定（47页珍藏版）》请在金锄头文库上搜索。
1、分布式系统概念与设计,张兆心,1,第七章 协调和协定,简介分布式互斥选举组播通信共识问题,2,7.1 简介,分布式系统的一个基本目的：供一组进程来协调他们的动作或对一个或多个值达成协议避免固定的主从关系的原因：经常需要系统即使在故障出现时也能保持正确的工作，因此需要避免单结点例如固定的主控器的故障,3,共享资源访问方式故障的处理故障和故障的检测同步系统：可靠的故障检测异步系统：不可靠的故障检测,4,故障检测完整性：有失效的进程就能被检测出来正确性：正常的进程不会被认为失效强完整性、弱完整性强准确性、弱准确性、最终强准确性、最终弱准确性不可靠的故障检测消息的延迟消息的丢失,5,7.2 分布式互斥
2、,分布式互斥共享资源的协调基于消息的传递互斥算法临界区要求ME1(安全性)：最多一个进程进入临界区ME2(活性)：进入和离开临界区的请求最终成功ME3(顺序)：先请求，先进入性能评价消耗的带宽：进入和退出临界区的消息数目延迟：每次进入和退出导致的客户延迟吞吐量：系统吞吐量,6,中央服务器法服务器专门授理访问临界区的请求，令牌为进入临界区每个进程需向该服务器发出请求允许进入，服务器授予令牌，应答令牌被占用，放入缓冲区等待退出临界区，进程发送消息，则令牌释放，取出等待队列中的进程，授予令牌，应答,7,中央服务器法满足ME1？满足 ME2？满足ME3？满足ME1，满足 ME2不能满足ME3性能带宽：
3、3个消息（请求、授权、离开）；延迟：请求进入2N个消息间隔，退出：1个消息间隔吞吐量：2个消息的间隔,8,基于环的算法地位对等，不需要单独的服务器令牌令牌连续的单向传输只有获得令牌才有权进入临界区获得令牌-占用令牌-进入临界区-退出临界区-释放令牌,9,基于环的算法满足ME1，满足 ME2，不满足ME3性能带宽：1 N个消息进入临界区 0 N-1个消息退出临界区1个消息延迟：1 N个消息的间隔吞吐量：1 N个消息的间隔,10,使用组播和逻辑时钟的算法(Ricart and Agrawala)引入逻辑时钟，确定动作的先后关系状态变量：RELEASED, WANTED, HELD进程Pi初始化：s
4、tate:= RELEASED;Task1：state:=WANTED; T:=时间戳； send (Ti,Pi) to all process; Wait until (receive N-1 answer); state:=HELD;,11,使用组播和逻辑时钟的算法(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:= RELEASED; a
5、nswer 队列中的所有请求；,12,算法讨论满足ME1,满足 ME2, 满足ME3性能带宽：进入临界区2（N-1）个消息， N-1个用于组播， N-1个用于应答退出0-(N-1)个消息延迟：请求进入 2 N个消息间隔吞吐率：1个消息的间隔,13,Maekawa 算法选举的方法获得部分支持就可以进入临界区定义: 进程集合 P1,P2PiPN 对任意进程的选举集合 Vi 是进程集合的真子集 有：Pi Vi ; Vi Vj ; | Vi |=| Vj|=K;,14,进程Pi初始化: state :=RELEASED; voted:=FALSE; Task1: state:=WANTED; send
6、 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,Task3: state :=RELEASED; send released message to Vi-Pi;Task4: Pj（ji）receive the released message from Pi ; if (请求队列非空)
7、删除队列头部的Pk; answer Pk; voted:=TRUE; else voted:= FALSE;,16,讨论ME1? YesME2? Yes?（p1，p2，p3）都申请ME3? No改进加入逻辑时钟ME2， ME3 yes性能带宽：进入2(K-1)个消息，退出K-1个消息延迟：请求进入 2 N个消息间隔，与Ricart and Agrawala 相同吞吐率：2个消息间隔,17,容错？消息的丢失？不能容忍进程崩溃？中央服务器法可以容忍一个既不申请，也不持有令牌的进程崩溃，基于环的算法不能容忍任一个进程崩溃Maekawa算法，如不在一个投票集中，可以容忍Ricart and Agraw
8、ala 算法不能容忍任一个进程崩溃,18,7.3 选举,选举对象：扮演特定角色的唯一进程目的：找到一个大家认可的替代者属性：定义变量electedE1(安全性)： elected为未决，或为P，E2(活性)：所有进程都参加且最终elected不为空，或崩溃性能：带宽使用：发送消息的总数算法的回转时间：从启动算法到中止算法，串行消息的传输次数,19,基于环的选举算法(Chang and Roberts)逻辑环排列的进程顺时针发送过程 ：选举出一个协调者1、最初，所有进程都是选举中的非参加者，所有进程都有一个标示2、开始一次选举，自己标为参加者，将自己的标示放到消息中发到下一个进程,20,基于环的
9、选举算法(Chang and Roberts)3、当一个进程收到一个选举消息。1）如果消息内的标示比自己的标示大，则转发消息到下一个邻居，标自己为参加者。2）标示比自己的小且自己不是参加者，则选举消息替换成自己的标示，发送，标自己为参加者；3）标示比自己的小且自己是参加者，则不转发消息4、如果收到的标示是接收者自己的，则自己被选举成为协调者。向邻居发送当选消息，并标记为非参加者5、任一个进程收到当选消息，置变量elected，并标记为非参加者，转发当选消息,21,讨论E1（安全性）：满足所有的标识都比较一个进程当选必须收回自己的标识任意两个进程，标识较大的不会传递标识较小的进程标识，不可能两者
10、都收到自己的标识E2（活性）：满足遍历环，所有人都参加,22,性能当只有一个进程启动选举最坏的情况，3N-1个消息逆时针邻居具有最大标识，到达该邻居需要N-1个消息回路N个消息当选发送N个消息最好的情况，2N个消息算法的限制假设消息传输是可靠的假设无进程崩溃,23,霸道算法假设消息传输是可靠的，且有上界假设可能会发生进程崩溃同步（环：异步）可以和所有进程通信且知道标识较高的进程（环：邻居）消息的类型选举消息：选举某进程为协调者的消息回答消息：回复选举的结果协调者消息：“新协调者”宣布当选,24,25,过程：任一个进程开始选举1、知道自己是最大标示的进程，直接认为自己是协调者进程，并发送协调者消
11、息2、具有较低标示的进程开始一次选举，发选举消息给比自己标示大的进程，等待应答消息若无应答消息，则认定自己是协调者有消息应答，则等待接受协调者消息无协调者消息，则再进行一次选举3、若收到一个选举消息，回送应答。若自己没开始选举，则自己开始一次选举4、若收到协调者消息，则认定新的协调者,讨论E1 （安全性）：满足没有进程被替换E2（活性）：满足根据可靠消息传递的假设性能最好的情况N-2个消息标识最大的进程发现协调者错误，发送N-2个协调者消息最坏情况O(N2)个消息标识最小的进程发现协调者错误，然后N-1个进程开始选举，每个进程都发送消息到较大标识的进程,26,7.4 组播通信,特点一个进程只调
12、用一个组播操作来发送一个消息到组中的每个进程不是多次发送同一个消息到不同进程效率：程序员方便，硬件的支持传递保证：无法保证系统模型组标识：G封闭组：只有G内的成员可以发送消息给G开放组：组G外的成员也可以发送消息给G,27,静态组与动态组静态组：组内成员不可变更的组，组成员按照某种方式事先定义，以后无论发生什么情况都不可变更动态组：允许组成员动态地加入退出。一个进程可以提出请求，加入（Join）一个组，从而成为这个组的成员，也可以要求离开或由于失效而退出（Leave）这个组,28,静态组与动态组动态组提供面向视图（View-Oriented）的组成员服务（Group Membership Se
13、rvice）视图（View）是组中当前活跃的成员（进程）列表，每个视图都有一个唯一的标志，组成员服务跟踪组的成员关系随时间的变化。当组成员列表发生变化，组成员服务负责通知组的各个成员，组成员就会安装（Install）新的视图,29,消息通信服务根据消息传输是否可靠，消息通信服务可分为不可靠多播（Unreliable Multicast）和可靠多播（Reliable Muticast）不可靠多播类似UDP提供的数据报服务，不保证消息安全到达所有接收方。可靠多播保证消息被所有接收方安全收到（Receive），但并不保证被接收方安全接收（Deliver）区分接收（Deliver）和收到（Receiv
14、e）。一个进程收到消息后可以先不接收它（送交上层应用），即接收是应用层行为，而收到在通信层行为,30,消息通信服务按照消息的顺序特性，消息通信服务可分为无序、先入先出顺序（FIFO Order）、因果序（Causal Order）、全序（Total Order）等。,31,基本组播原语 B-multicast(g,m)：对每个属于组g的进程p, send(p,m)，可靠的一对一 send操作进程p执行 receive(m)时：进程执行 B-deliver(m) 可靠组播完整性（安全性）：任何传递的消息与发送的消息相同，且不会被重复传递有效性（活性）：任何消息都会被传送到目的地协定：如果一个正确
15、的进程收到消息，则组中所有正确成员都终将收到该消息,32,用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 P,B-Multicast(g,m) ； end if R-deliver (m);end if,
