分布式系统中的通信

第三章分布式系统中的通信§1概述1.系统中各部分通信的基本方式利用共享存储区消息传送2.分布式系统中通信考虑的关键问题●发送策略固定策略虚拟线路策略动态发送策略固定策略简单，但不顾及网络负载；虚拟策略对此有所改进，亦能保证消息发送与到达次序一致，但不能最大限度利用带宽；动态策略可充分利用带宽，但不能严格保证消息发送与到达次序一致。第三章分布式系统中的通信●连接策略线路转换：永久物理链路，固定独占使用消息转换：物理链路动态分配，临时共享使用信包转换：物理链路与信包捆绑，消息拆分传输●冲突解决策略冲突检测令牌传递消息槽●保密单密钥技术公公密钥技术第三章分布式系统中的通信§2分布式系统中的同步机制条件限定有关信息分散在不同计算机上只能根据本地得到的信息进行决策应能回避单点故障或错误系统中不存在公共时钟或全局时钟装置1.时钟同步●逻辑时钟:一个单调增长的计数器记号：顺序ab；并发a‖b；进程p的逻辑时钟记为Cp事件a在进程P中的时间邮戳为Cp(a)，事件x在任何进程中的时间邮戳记为C(x)，ab则C(a)C(b)第三章分布式系统中的通信★Lamport时钟校正方法通过在本地物理时间上加上一个偏移量来实现进程本地逻辑时钟，进程按以下方式更新其逻辑时钟并在进程件传递逻辑时钟的值：■Cp在进程P上的每一事件之前增值并加盖邮戳：Cp=Cp+1；■当进程P发送消息m时，在m上携带逻辑时钟值t=Cp■当进程Q接收消息(m，t)时，计算Cq=max(Cq，t)+1第三章分布式系统中的通信[例]三个备有自己不同频率物理时钟的进程相互发送消息000618122430364248546081624324048566472809182736455463728190ABCD000612182430364248657181624324048566472809182736455463728190ABCD未同步前各自的时钟同步后的时钟时钟同步事件f事件e第三章分布式系统中的通信注意：使用逻辑时钟，a-b可以保证C(a)C(b)，但反之不然。上图中事件e和f分别是进程3中的事件，虽然可以看出存在C(f)﹥C(e)，但e‖f。使用逻辑时钟只能对事件作部分排序！可以通过对发生的事件加上进程标识符且对进程标识符进行排序，来实现对事件的完全排序。进程P上的事件a时间邮戳为Ta，进程Q上的事件b时间邮戳为Tb，定义：a、b的全局时间邮戳分别为(Ta，p)，(Tb，q)，(Ta，p)(Tb，q)当且仅当TaTb或者Ta=Tb但同时有pq。进程P中的事件a先于进程Q中的事件b发生，用a﹦﹦＞b表示。这里﹦﹦＞表示全序关系。第三章分布式系统中的通信●物理时钟通常，使用协同宇宙时间UTC（UniversalCoordinatedTime）来代替国际原子时间TAI（InternationalAtomicTime），精度可达0.5毫秒。时间服务器S配备接收卫星授时装置并根据请求提供标准时间。进程P在消息mr中请求时间，并在消息mt中接收时间t，原则上它应该将自身的时钟置为t+Ttrans，其中Ttrans为从S到P的消息传送时间。Ttrans是不确定的，容易受到网络传输竞争的变化。实际上，Ttrans=min+x，min是理想情况下的网络传输时间，而x随网络环境的变化而变化。第三章分布式系统中的通信★Cristian算法如果进程P的时钟刷新率很低，那么发送mr所需时间、时钟服务器处理请求的时间和接收mt所需时间的来回时间Tround可以以合理的精度地用进程P的本机时钟计算出来。如果从S接收的标准时间为t，近似地可以认为实际时间为t+0.5Tround。近似精度为±[(Tround/2)–min]。★Berkeley算法时间服务器周期性地向所有节点发送UTC并询问当地的时间，接收者返回各自本地时间与服务器时间的偏差信息，根据接收到的偏差信息、当时的服务器本机时间，计算出传输来回的平均时间，扣除后再计算出每台机器的时间偏差，向它们分别发送，供它们修正自己的本机时间。第三章分布式系统中的通信★平均算法将时间划分为定长的时间区间，大家约定一个起始时间T0，第i个区间为[T0+iR，T0+(I+1)R]，这里R为系统参数。每个时间间隔开始时，每台计算机广播自己的本机时间。由于本机时间各不相同，这些广播并不精确地发生在同一时刻。每台机器也会收到其它机器的广播，仿照Berkeley算法，取一个可信时间间隔，在该区间内收到的广播为有效广播，计算平均值（或去掉一个最大值、一个最小值后平均），用估计传输时间做修正后，作为自己的本机时间。显然，这样得到的系统标准时间与UTC无关，仅仅为了系统内部同步使用。第三章分布式系统中的通信★网络时间协议（NTP）NTP定义了时间服务的体系结构和在各种互连网络上分布时间信息的协议，被Internet用作时钟同步的标准。服务器组成层次结构，形成同步子网。主服务器位于树根，与标准时间资源（如UTC接收机）相连，上级服务器对下级服务器进行同步控制。一般来说，由于每一层同步都会出现误差，较低层次的服务器比较高层次的服务器时间更不准确。在服务器不可达或出现故障时，可以重构同步子网。同步控制的方式大致有三种。第三章分布式系统中的通信■组播方式：主要用于高速网。某个或某几个服务器定期向局域网上的服务器广播时间，服务器收到时间后，对广播延迟做小的修正后进行同步，修改本地时钟。■过程调用方式：与Cristian算法类似。■对称方式：最适用于用于层次同步方式，精度最高。主、从服务器之间成对交换，每个消息都附加时间邮戳。服务器ATi+1Ti+2服务器BTTi+3第三章分布式系统中的通信在服务器A、B之间传送两个消息m和m’。令由B到A的延迟时间为t，由A到B的延迟时间为t’，服务器A对B的本机时钟的偏差为δ。那么，Ti+1=Ti+t+δ；(t≥0)Ti+3=Ti+2+t’-δ；(t’≥0)记a=Ti+1-Ti，b=Ti+3–Ti+2；两个消息的总延迟时间为：d=t+t’=a-b令每一对消息的计算误差为Q=(a+b)/2，那么：δ=Q+(t’–t)/2，由于t，t’≥0，于是Q–d/2≤δ≤Q+d/2第三章分布式系统中的通信●同步时钟的使用消息传送实现Cache的一致性2互斥问题临界区规则：有空让进，无空等待，有限等待+定序进入简单的实现方法：设立“仲裁者”，集中式弊端约定：进程与结点等价进程间发送消息遵从“管道”规则每个消息将在有限时间内正确到达系统全互连第三章分布式系统中的通信●Lamport算法①进程Pi要求进入临界区k，向每个进程发送消息Request（Ti,k,i），公告进入要求，并将其置于自己请求消息队列的队尾。其中Ti是该进程的时间邮戳②进程Pj收到消息后，按全序方式排序并插入自己的队列中，返回带有自己邮戳的ok消息③以下条件成立时，进程Pi可以进入临界区k：Pi自己的Request（Ti,k,i）消息位于自己请求队列的队首Pi收到所有进程发回的时间邮戳晚于Ti的ok消息④退出时，Pi删去自己队列的相应消息，并公告退出消息⑤进程Pj收到退出消息后，删去自己队列的相应消息第三章分布式系统中的通信Ricart和Agrawala对此算法做了改进，使需要发送的消息从3（n+1）减少为2（n+1）②进程Pj收到消息后，按全序方式排序并插入自己的队列中：若自己不在且不想进入临界区，发送ok消息若自己在临界区，不做回答若自己正想进入临界区，比较到达消息与自己请求消息的邮戳，若到达邮戳早，发ok，否则不发问题：一旦出现故障结点，ok消息永不到达，无法进入。第三章分布式系统中的通信●令牌传递方法令牌是一类点对点的、代表“许可权”的特殊消息。★循环式令牌传递所有结点组成一个逻辑环■单向方案---被动式只有一个令牌。令牌沿一个方向流动，需要进入临界区者留住令牌，退出时再交出，否则立即转交下一个节点。■双向方案---主动式请求消息与令牌反向流动。自己有令牌，不在也不想进入，接到请求后传递令牌；自己在临界区，退出时转交；自己也发出了请求消息，接到请求后记下，等自己有了令牌并退出临界区时再转交；自己没有令牌，也不想进入临界区，接到请求后立即相同方向邻居传递。第三章分布式系统中的通信★广播式令牌传递针对非环状结构网。对每个临界区，设令牌向量T=（T1，T2,…Tn），其中n为进程数。每个进程对每个临界区设立请求队列。进程Pi希望mi次进入临界区时，广播Request(Pi,mi)后等待令牌。收到后将Ti改为mi并进入临界区，退出时，查看请求队列，若空则继续执行，若有请求则取出队首元素Rquest(Pj,mj)，若mjTj则将令牌交给Pj，否则删除该请求继续查看，直至队列为空。若队列已空令牌仍在手中，等到mjTj的请求出现时，再转移令牌。无令牌进程接到请求将其插入请求队列即可。实际上，临界区C已经扩大为（C，T）了。第三章分布式系统中的通信3.协调者选择问题分布式系统中常常会有“协调者”，如何选择。●Bully算法系统中有n个进程P1，P2，…Pn，假定进程号最大者为协调进程。某一进程在规定时间内无法与协调者联系，可以发起竞选。★Pi发起竞选，广播附有本进程号的竞选消息。★Pi接到消息，若自己号小则沉默，否则发回拒绝消息，自己发起竞选。★竞选者在规定时间内未接到拒绝消息，自动当选。广播当选消息，运行协调程序，成为协调进程。否则竞选失败，准备接受他人当选消息。若规定时间内未接到当选消息，可再度发起竞选。第三章分布式系统中的通信●环形算法结点组成逻辑环。★进程Pi发起竞选，创建一活跃表，填入本进程号，发送给左邻，若左邻规定时间内未应答，则故障，跳过其向下一个发送，直至非故障者。★进程Pj接到右邻的竞选消息■若为第一次接到，将本进程号加入表中向左邻发送■若为第二次接到，又若本进程号最大，则向左邻发布自己当选消息，否则继续传送活跃表★进程接到当选消息必须立即向左邻转发，直至当选者从右邻获得自己当选消息为止。第三章分布式系统中的通信4.原子事务●事务模型★事务原语begin-transaction事务开始end-transaction事务结束abort-transaction退出事务，恢复事务开始状态等。★事务的特性顺序性原子性永久性★嵌套事务：父子事务提交的时机与分布式环境第三章分布式系统中的通信●分布式系统中事务的实现★副本问题一致性读写分开问题★修改日志★两阶段提交■第一阶段：发送消息，检查提交准备工作并回送检查结果■第二阶段：发送消息，要求提交或abort■事务发起者即为协调者第三章分布式系统中的通信★协调者需要：知道事务涉及的所有结点让所有参与者知道谁是协调者■做法Client向每个服务器发送事务函数Addserver（事务名，协调者名）每个参与者（非协调者）向协调者发送报到消息Newserver（事务名，本结点名）协调者生成一张参与者表，在收到参与者消息后将每个参与者列入表中第三章分布式系统中的通信★事务并发控制■锁机制可能引起死锁空间数据上锁的粒度问题■乐观机制冲突处理：为每个数据结构记录读、写时间，在提交时刻检查，若已被其他事务修改，本事务中止，否则提交。在重负载时，失败率急剧上升。■时间邮戳约定：每个数据只有一个版本第三章分布式系统中的通信方法1：设置两类时间邮戳：事务开始邮戳，数据访问邮戳事务提交前检查：若事务戳晚于所涉及数据上其它的数据辍，表示该事务开始后所有数据未被其他事务访问，可以提交，否则中止提交过程，失败！方法2：时间戳分为两类四种：读（尝试读T’r，结束读Tr）、写（尝试写T’W，结束写TW），读写进行时用盖“尝试”，提交时盖“结束）。不要求严格保证互斥，只需保证不同事务的先后次序即可。不会引起死锁，但实现复杂。第三章分布式系统中的通信[例]两个事务a，b（其中a先开始）的情形。A.无冲突，可继续进行，其中x，y代表任意的事务B.有冲突，需中止C.对A而言，等待B的提交Tr(x)Tw(y)T’w(a)T’r(a)Tr(x)Tw(y)T’r(a)T’r(b)T