分布式系统中的通信.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 分布式系统中的通信,1,概述,1.,系统中各部分通信的基本方式,利用共享存储区,消息传送,2.,分布式系统中通信考虑的关键问题,发送策略,固定策略,虚拟线路策略,动态发送策略,固定策略简单，但不顾及网络负载；虚拟策略对此有所改进，亦能保证消息发送与到达次序一致，但不能最大限度利用带宽；动态策略可充分利用带宽，但不能严格保证消息发送与到达次序一致。,第三章 分布式系统中的通信,连接策略,线路转换：永久物理链路，固定独占使用,消息转换：物理链路动态分配，临时共享使用,信包转换：物理链路与信包捆绑，消息拆分传输,冲突解决策略,冲突检测,令牌传递,消息槽,保密,单密钥技术,公公密钥技术,第三章 分布式系统中的通信,2,分布式系统中的同步机制,条件限定,有关信息分散在不同计算机上,只能根据本地得到的信息进行决策,应能回避单点故障或错误,系统中不存在公共时钟或全局时钟装置,1.,时钟同步,逻辑时钟,:,一个单调增长的计数器,记号：顺序,a b,；,并发,ab,；,进程,p,的逻辑时钟记为,C,p,事件,a,在进程,P,中的时间邮戳为,C,p,(a),，,事件,x,在任何进程中的时间邮戳记为,C(x),，,a b,则,C(a)b,可以保证,C(a)C(b),，,但反之不然。上图中事件,e,和,f,分别是进程,3,中的事件，虽然可以看出存在,C(f)C(e),，,但,ef,。,使用逻辑时钟只能对事件作部分排序！,可以通过对发生的事件加上进程标识符且对进程标识符进行排序，来实现对事件的完全排序。,进程,P,上的事件,a,时间邮戳为,T,a,，,进程,Q,上的事件,b,时间邮戳为,T,b,，,定义：,a,、,b,的全局时间邮戳分别为,(T,a,，,p),，,(T,b,，,q),，,(T,a,，,p)(T,b,，,q),当且仅当,T,a,T,b,或者,T,a,=T,b,但同时有,p,T,j,则,将令牌交给,P,j,，,否则删除该请求继续查看，直至队列为空。若队列已空令牌仍在手中，等到,m,j,T,j,的请求出现时，再转移令牌。无令牌进程接到请求将其插入请求队列即可。,实际上，临界区,C,已经扩大为（,C,，,T,）,了。,第三章 分布式系统中的通信,3.,协调者选择问题,分布式系统中常常会有“协调者”，如何选择。,Bully,算法,系统中有,n,个进程,P,1,，,P,2,，,P,n,，,假定进程号最大者为协调进程。某一进程在规定时间内无法与协调者联系，可以发起竞选。,P,i,发起竞选，广播附有本进程号的竞选消息。,P,i,接到消息，若自己号小则沉默，否则发回拒绝消息，自己发起竞选。,竞选者在规定时间内未接到拒绝消息，自动当选。广播当选消息，运行协调程序，成为协调进程。否则竞选失败，准备接受他人当选消息。若规定时间内未接到当选消息，可再度发起竞选。,第三章 分布式系统中的通信,环形算法,结点组成逻辑环。,进程,P,i,发起竞选，创建一活跃表，填入本进程号，发送给左邻，若左邻规定时间内未应答，则故障，跳过其向下一个发送，直至非故障者。,进程,P,j,接到右邻的竞选消息,若为第一次接到，将本进程号加入表中向左邻发送,若为第二次接到，又若本进程号最大，则向左邻发布自己当选消息，否则继续传送活跃表,进程接到当选消息必须立即向左邻转发，直至当选者从右邻获得自己当选消息为止。,第三章 分布式系统中的通信,4.,原子事务,事务模型,事务原语,begin-transaction,事务开始,end-transaction,事务结束,abort-transaction,退出事务，恢复事务开始状态,等。,事务的特性,顺序性,原子性,永久性,嵌套事务：父子事务提交的时机与分布式环境,第三章 分布式系统中的通信,分布式系统中事务的实现,副本问题,一致性,读写分开问题,修改日志,两阶段提交,第一阶段：发送消息，检查提交准备工作并回送检查结果,第二阶段：发送消息，要求提交或,abort,事务发起者即为协调者,第三章 分布式系统中的通信,协调者需要：,知道事务涉及的所有结点,让所有参与者知道谁是协调者,做法,Client,向每个服务器发送事务函数,Addserver,（,事务名，协调者名）,每个参与者（非协调者）向协调者发送报到消息,Newserver,（,事务名，本结点名）,协调者生成一张参与者表，在收到参与者消息后将每个参与者列入表中,第三章 分布式系统中的通信,事务并发控制,锁机制,可能引起死锁,空间数据上锁的粒度问题,乐观机制,冲突处理：为每个数据结构记录读、写时间，在提交时刻检查，若已被其他事务修改，本事务中止，否则提交。在重负载时，失败率急剧上升。,时间邮戳,约定：每个数据只有一个版本,第三章 分布式系统中的通信,方法,1,：,设置两类时间邮戳：事务开始邮戳，数据访问邮戳,事务提交前检查：若事务戳晚于所涉及数据上其它的数据辍，表示该事务开始后所有数据未被其他事务访问，可以提交，否则中止提交过程，失败！,方法,2,：,时间戳分为两类四种：读（尝试读,T,r,，,结束读,T,r,）、,写（尝试写,T,W,，,结束写,T,W,），,读写进行时用盖“尝试”，提交时盖“结束）。,不要求严格保证互斥，只需保证不同事务的先后次序即可。,不会引起死锁，但实现复杂。,第三章 分布式系统中的通信,例,两个事务,a,，,b,（,其中,a,先开始）的情形。,无冲突，可继续进行，其中,x,，,y,代表任意的事务,B.,有冲突，需中止,C.,对,A,而言，等待,B,的提交,T,r,(x),T,w,(y),T,w(a),T,r(a),T,r,(x),T,w,(y),T,r(a),T,r(b),T,w(a),T,r,(b),T,w(a),T,w,(b),T,r(a),T,w,(b),T,r(a),T,w(b),T,w,(b),T,r(a),第三章 分布式系统中的通信,3,Client/Server,模型,应用系统的逻辑层次：,表 示 逻 辑,应 用 逻 辑,数 据 操 纵 逻 辑,数 据 库 逻 辑,第三章 分布式系统中的通信,应用系统的工作方式与结构：,Host-Based,Device-Shared,Client-Server,Peer-to-Peer,从分布式系统角度来看，,client,与,server,的关系就是一组协同进程关系，而且是一种主从关系协同进程。形成一对多的关系。,第三章 分布式系统中的通信,1.,寻址问题：三种寻址方式,Client,核心,server,核心,1,2,1：请求 2：服务应答,Client,核心,server,核心,3,4,1,2,1：广播 2：应答 3：请求 4：服务应答,Client,核心,server,核心,Name server,核心,1,2,3,4,1：查找,2：,NS,应答 3：请求 4：服务应答,第三章 分布式系统中的通信,评论：第一种：绑定，不透明；第二种：开销大；第三种：集中式。,2.,消息传送原语,执行方式,阻塞方式，同步通信,非阻塞方式，异步通信,实现方式,缓冲方式，设置邮箱，消息在邮箱暂存。问题：邮箱满如何处置,非缓冲方式，不设邮箱，消息直接送入接收者指定的存储区，问题：,receive,必须早于,send,，,第三章 分布式系统中的通信,3.,可靠性问题,两次确认方法,Client,核心,server,核心,1,3,2,4,服务请求 2.请求确认 3.服务应答 4.应答确认,确认在核心之间进行,一次确认方法,省略请求确认，以服务应答隐含代替,第三章 分布式系统中的通信,Client-server,通信协议,消息代码 消息类型 发送者 接收者 说 明,REQ,服务请求,client server client,请求服务,REP,服务结果应答,server client server,回送结果,ACK,接收消息确认 任意 任意 消息已经收到,AYA,询问：还活着吗,client server,了解是否故障,IAA,回答：还活着,server client,回答：无故障,TA,再试一次,server client server,邮箱已满,AU,地址不详,server client,无进程用此地址,消息代码 消息类型 发送者 接收者 说 明,REQ,服务请求,client server client,请求服务,REP,服务结果应答,server client server,回送结果,ACK,接收消息确认 任意 任意 消息已经收到,AYA,询问：还活着吗,client server,了解是否故障,IAA,回答：还活着,server client,回答：无故障,TA,再试一次,server client server,邮箱已满,AU,地址不详,server client,无进程用此地址,第三章 分布式系统中的通信,4.,组通信,组有动态性，单个结点可以是多个组的成员,组通信分类,原子组播,所有组员要么全部收到，要么都不收到,实现：设置定时器，发送者在定时结束时发出停止传递消息,接收者若未收到停止传递消息则转播（组播）,可靠组播,任意组员有应答即可,不可靠组播,播出去即可,第三章 分布式系统中的通信,定序问题,网络传播时间上具有不确定性，定序不当将破坏数据一致性。两个冗余的数据库服务器：,server 1,server 2,client1,client1,1,2,3,4,Client1,首先组播：,A,改为5，,B,改为,4；,client4,组播：,A,改为10，,B,改为,A+B；,正确结果：两库均为：,A=10，B=14,若通信次序如图，,server1,中,A=10，B=14；server2,中,A=5，B=4,库中,A、B,初值任意,第三章 分布式系统中的通信,全局定序,ABCAST,类似两阶段提交，发送者对消息附加“序列邮戳”并组播；接收者返回一个自己的序列邮戳（大于它任何收到或发送的邮戳值）；发送者收到所有回执后，选其中最大者附加在提交消息中组播，服务器的提交工作按邮戳次序进行。,因果定序,CBCAST,每个组员都维护一个其个数与组员相等的向量，分别每个分量与一个组员对应，初值均为零。每个组员组播消息时，将代表自己的分量加,1,后发出消息，接收者接收来自成员,j,的消息并处理必须符合条件：,V,j,=,L,j,+1,且,V,i,L,i,（,ij,），,否则延迟接收与处理。,第三章 分布式系统中的通信,A,B,C,(,0,0,0),(,0,0,0),(,0,0,0),M,1,(,1,0,0),M,2,(,1,0,0),(,1,1,0),消息2虽到达，但必须推迟提交,消息1到达并提交,消息2推迟后提交,第三章 分布式系统中的通信,4,6,8,2,1,0,3,6,8,2,1,5,3,5,8,2,1,5,3,7,8,2,1,5,2,6,8,2,1,5,3,7,8,3,1,5,成员号,0,1,2,3,4,5,组播,接收,延迟,接收,延迟,接收,第三章 分布式系统中的通信,组播的设计,原则,效率：充分利用网络层提供的组播寻址功能,可靠性：防止消息没有送到或只有部分送到后故障,可监控：能判断成员故障，能必要时重发,设计问题讨论,封闭式与开放式小组：前者适合并行处理，后者适合冗余服务器情形,对等式与层次式结构：前者可靠但开销大，后者有集中式缺点,第三章 分布式系统中的通信,组的管理问题：设立组管理器，有集中式弊病但简单；组管理分散则复杂，开销大,组寻址问题：对网络支持的要求；利用,IP,表利用点对点通信实现；断言寻址法,-,消息中包含断言，消息周游时，接点自行判断应否接收消息,组重叠问题,全局时间定序只能在组内进行，要扩大到整个系统极其复杂。,根据应用逻辑，具体对待。,第三章 分布式系统中的通信,5.,远程过程调用,RPC,本地过程调用,c=proc(,fd,buf,k),前后数据栈的变化,调用前,调用中,调用后,主程序的局部变量,主程序的局部变量,K,Buf,Fd,返回地址,过程,proc,的局部变量,主程序的局部变量,sp,sp,sp,第三章 分布式系统中的通信,RPC,的实现,分同步、异步两种,Client,应用程序,stub,stub,Server,程序,网 络,参数打包,结果打包,结果解包,参数解包,第三章 分布式系统中的通信,实现步骤：,client,应用程序正常调用,client stub,client stub,构造消息，通过,trap,进入核心,核心将消息发送到,server,的核心,server,核心将消息交给,server stub,server stub,将消息解包，用相应参数调用服务例程,服务例程进行计算，将结果返回,server stub,server stub,构造消息，通过,trap,进入核心,核心将消息发送到,client,的核心,client,核心接收消息并将它交给相应,stub,stub,解包，将调用结果返回应用程序,第三章 分布式系统中的通信,RPC,的参数传递,数据格式问题,统一规范格式，简单但不灵活，效率也不高,增加一个参数，或在消息中指明格式，由接收者做相应处理，效率较高，但每个机器需配置完全的格式转换程序,指针类参数问题,全部禁用，不利于用户使用,复制,/,重新存储方法，,client,以实体代替指针，,server,生成缓冲区存放实体，计算后将缓冲区打包发回,复杂数据类型问题,在,GIS,中，指针指向图，此时需制订专门的通信协议，详细描述数据规格，并配置相应程序读取,第三章 分布式系统中的通信,client-server,的连接,解决,client stub,与,server,地址的绑定问题,静态连接,在,client,配置时，将地址登入,stub,。,简单，不灵活,动态连接,设立地址连接服务器,连接服务器维护所有服务的接口与地址，,server,启动时，将自己的地址与服务接口发给连接服务器，关闭时要求撤销注册；,client,首次使用某个,RPC,时，向连接服务器发消息请求得到它的接口与,server,地址,。,灵活，但开销大，具有集中式的一切弊病,第三章 分布式系统中的通信,例外处理,找不到服务器,多次发送消息都未受到应答，作为例外事件来处理，用户编写例外时间处理程序。,收不到应答消息,消息丢失,按找不到服务器处理。,某些特殊请求应在请求消息中注明最多执行一次，这样服务器再次收到这个请求不再执行，只将结果重发。,服务器故障,第三章 分布式系统中的通信,故障时刻：,早就故障；,接到请求，处理开始前故障；,处理过程中故障；,处理结束，发出应答消息前故障；,应对策略,RPC,至少处理一次，可以多次，以最后一次为准,至多处理一次，可以不处理,不做承诺，可以是,0-,n,次,恰好,1,次。,第三章 分布式系统中的通信,Client,故障,考虑发出请求后，收到应答前故障，使服务器无法结束事务。,处理策略,清除法。,Client,为每次,RPC,做日志，恢复时显式清除,RPC,。,但在,RPC,嵌套时，可能无法实现。,再生法。将时间划分为顺序编号的时段，,client,恢复时，广播新时段开始，有关机器接到广播后清除所有老时段的运算。,温和再生法。只清除无主的,RPC,。,过期法。为每个,RPC,规定标准时限，若在标准时限内不能结束，必须先申请延长，否则自动清除。,第三章 分布式系统中的通信,通信设计问题,协议问题,面向连接的协议,Client,与,Server,固定捆绑，简单，可靠，无需处理确认，适用于广域网；但性能较低，由于额外的软件开销，对局域网而言，本来就很可靠，必要性不大。,面向非连接的协议,虽需要处理确认等以保证可靠性，但效率高，在局域网上适用。,第三章 分布式系统中的通信,信包大小问题,与使用的协议有关，原则上长信包的效率较高，例如以太网,1536,B,，,SUN,更大，,8,K,。,信包确认问题,停,-,等协议，上一个信包确认后才发下一个，发现丢失及时补发,爆发协议，信包全部一次发完，然后总体确认。发现丢失时，局域网上往往采用全部重发，广域网上则采用有选择重发,超限处理问题，使用爆发协议时，超长消息容易引起截断性丢失问题，通常根据芯片缓冲区大小，将消息分成数段中间设置停顿。,第三章 分布式系统中的通信,4,异步通信问题,1.,通信时的进程关系模型,同步模型,发送进程在收到消息已被接受的确认前，不认为此次通信已经完成，进程必须等待，不再进行其他工作。,异步模型,发送进程将消息放入发送信箱以后即认为此次通信已经完成，进程转而进行别的工作。,问题：在异步情况，进程,P,向进程,Q,先后发出两条消息,m,1,、,m,2,，,由于传输原因，,m,2,先于,m,1,到达并接收，谓之超越。,第三章 分布式系统中的通信,2.,解决思路,无限制，显然问题很多,FIFO,，,太严格，有时无必要。无关联的消息允许无序，即使是有关联的消息也并非完全不能超越。,实现问题：如何确定当前消息是第一个消息，若认为可能有超越，等待多长时间才可确定无超越。,F,通道，将消息分为,4,类：,t,：,两端堵塞，前后不许超越,o,：,任意，允许超越和被超越,b,：,向后堵塞，不许被超越,f,：,向前堵塞，不许超越别人,第三章 分布式系统中的通信,层次通道，将消息分为若干层次，每一层次遵循同一种通道规则。不同层次通道的消息，高层次通道的消息可以超越低层次通道的消息。,3.,PCAP,（,process-Channel-Agent-Process,）,模型,在发送进程,P,和接收进程,Q,之间引入,Agent C,pq,P,C,pq,Q,P,的发送序列为,q,1,，Q,的接收序列为,q,2,，,两者元素相同，次序可能不同。,Q,可向,C,pq,发送要求（例如发送序列的一个子集），,C,pq,按,要求将消息以接收序列的次序送给,Q。,第三章 分布式系统中的通信,通道语法规则,消息序列,通道语法,G,发送序列,send,接收序列,recv,send,recv,，,表示,send,经符合,G,的若干次超越后形成接收序列,recv,可传送集,D=,m|,，,表示,m,可以加到序列,S,i,的首部,*,G,*,G,第三章 分布式系统中的通信,例,F,通道规则,G,F,R,1,：,o,型消息可以相互超越,R,2,：,o,型消息可以超越前面的,f,型消息,R,3,：,b,型消息可以超越前面,的,o,型消息,R,4,：,b,型消息可以超越前面的,f,型消息,这样，令层次通道规则,G,h,为层次间语法规则,R,h,和,各层通道的语法规则,G,i,的并集：,G,h,=,R,h,G,i,R,h,：,iff,(m,i,.levelm.level,（,实际上，,L,表示了那些在它前面的元素层次都较低的元素集合）,D=,D,i,，,D,i,=m,|(m.level=I),且,ExtractSame,(m,S,m,),S,m,m,这里,ExtractSame,(m,S,m,),表示在,S,m,中,取出与,m,层次相同的消息后形成的消息序列。,i,0,i,0,*,G,i,第三章 分布式系统中的通信,这样，,m=v,且,m,D,h,就变成了,m=v,且,m,(LD),引入记号，用以判断,m,是否可以在,S,m,中超越（即,mL,）：,NonLowerAhead,(m,S,m,)=true,iff,(,S,m,=S,mS,),(mS,：,m.levelm.level),；,这样再引入,LevelDeliverable,(m,S,m,)=true,iff,ExtractSame,(m,S,m,)S,m,m,（即,m,在同一通道中可传送）,*,G,i,第三章 分布式系统中的通信,改进后的,C,pq,算法,收到来自,P,的消息,m,，,则,）,S,m,=,mS,m,；,）,若,NonLowerAhead,(m,S,m,)=true,则,L=L,m,；,）,若,LevelDeliverable,(m,S,m,)=true,则,D=Dm,；,收到来自,Q,的要求,v,，则,S,v,=,vS,v,；,若,S,v,e,LD e,则,）,x=first(,S,v,),）,若,m,m(LD),则,将,m,移至,S,m,的首部，,S,m,=after(m,S,m,),；,L=m,NonLowerAhead,(m,S,m,),；,第三章 分布式系统中的通信,D=m,|,LevelDeliverable,(m,S,m,),；,send,（,m,Q,）；,S,v,=after,（,m,S,v,）；,转,否则转,转,显然，目前,PCAP,的算法只是定性描述，只有在确定了各子通道的类型，,LevelDeliverable,(m,S,m,),才是确定的和可计算的。,第三章 分布式系统中的通信,5,RPC,的结构模型,一对多模型,在这种情况，系统中存在多个,Server,，,对一个,client,，其,RPC,发往何处并不明确。,分散式,RPC,以广播方式发出，每个,server,收到后自行判断。或抛弃（,server,无此服务），或执行,RPC,。,优点：逻辑简单，,client,处理方便。,缺点：网络开销大，计算开销大（,server,需要判断，甚至重复计算）,第三章 分布式系统中的通信,改进型：,client,上配置全局服务目录，由,client,自行选取提供服务的,server,，,定向发送,RPC,。,适用于专业系统。,集中式,配置服务目录,agent,。,改进型：,Client,agent,RPC,执行结果,Server 1,Server n,agent,Server 1,Server n,Client,服务地址,询问地址,WEB Service,第三章 分布式系统中的通信,优点：减少了网络负载,缺点：,agent,的负担过大，将成为系统的瓶颈，一旦故障，系统陷于崩溃。,改进型（,WEB Service,）,虽然部分减轻了,agent,的,负载，但是增加了网络的开销。集中式的弊病依然存在。,第三章 分布式系统中的通信,2.,多对多模型,在这种情形，一个,client,可以同时发出多个,RPC,，,指向多个,server,。,m-to-m,（,agent-id,，,n,，,service,1,，,arg,1,，,arg,t1,，,service,n,，,arg,1,，,，,arg,tn,）,实现模型,m-to-m,Agent leader,服务结果,返回结果,队列管理,Agent,线程,（,服务队列）,输向,server,的服务请求,第三章 分布式系统中的通信,工作示意,client,agent,server,m-to-m,接收,m-to-m,请求，分配线程，将分服务要求插入线程，进行线程调度。,各线程分别向,server,发送服务请求,接收服务请求，执行服务例程。发送服务结果。,接收服务结果，根据服务存根分类存放，收齐所有结过后向,client,发送。,发送服务请求,回送服务结果,接收结果,向,agent,发送,RPC,请求,第三章 分布式系统中的通信,讨论：,如果只有一个,agent,，,将引起超载,若有多个,agent,副本，之间如何协调以避免重复,agent,公布负载情况，供用户选择？,用户规定,agent,次序，超载,agent,自动转移负载？,划分,agent,的功能范围，划分原则,静态划分，增加用户负担，不方便,动态划分，管理困难,划分原则的确定,