分布式系统中的通信.ppt

《分布式系统中的通信.ppt》由会员分享，可在线阅读，更多相关《分布式系统中的通信.ppt（65页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章第三章 分布式系统中的通信分布式系统中的通信1 1 概述概述1.1.系统中各部分通信的基本方式系统中各部分通信的基本方式 利用共享存储区利用共享存储区 消息传送消息传送2.2.分布式系统中通信考虑的关键问题分布式系统中通信考虑的关键问题 发送策略发送策略 固定策略固定策略 虚拟线路策略虚拟线路策略 动态发送策略动态发送策略 固定策略简单，但不顾及网络负载；虚拟策略对此有所改进，亦能保固定策略简单，但不顾及网络负载；虚拟策略对此有所改进，亦能保证消息发送与到达次序一致，但不能最大限度利用带宽；动态策略可充证消息发送与到达次序一致，但不能最大限度利用带宽；动态策略可充分利用带宽，但不能严格保

2、证消息发送与到达次序一致。分利用带宽，但不能严格保证消息发送与到达次序一致。第三章第三章 分布式系统中的通信分布式系统中的通信 连接策略连接策略 线路转换：永久物理链路，固定独占使用线路转换：永久物理链路，固定独占使用 消息转换：物理链路动态分配，临时共享使用消息转换：物理链路动态分配，临时共享使用 信包转换：物理链路与信包捆绑，消息拆分传输信包转换：物理链路与信包捆绑，消息拆分传输 冲突解决策略冲突解决策略 冲突检测冲突检测 令牌传递令牌传递 消息槽消息槽 保密保密 单密钥技术单密钥技术 公公密钥技术公公密钥技术 第三章第三章 分布式系统中的通信分布式系统中的通信2 2 分布式系统中的同步机

3、制分布式系统中的同步机制 条件限定条件限定 有关信息分散在不同计算机上有关信息分散在不同计算机上 只能根据本地得到的信息进行决策只能根据本地得到的信息进行决策 应能回避单点故障或错误应能回避单点故障或错误 系统中不存在公共时钟或全局时钟装置系统中不存在公共时钟或全局时钟装置1.1.时钟同步时钟同步 逻辑时钟逻辑时钟:一个单调增长的计数器一个单调增长的计数器 记号：顺序记号：顺序 a ba b；并发并发 abab；进程进程p p的逻辑时钟记为的逻辑时钟记为Cp 事件事件a a在进程在进程P P中的时间邮戳为中的时间邮戳为Cp(a)，事件事件x在任何在任何进程中的时间邮戳记为进程中的时间邮戳记为C

4、(x)，a b a b 则则C(a)C(b)C(a)ba-b可以保证可以保证C(a)C(b)C(a)C(b)，但反之不然。但反之不然。上图中事件上图中事件e e和和f f分别是进程分别是进程3 3中的事件，虽然可以看出存在中的事件，虽然可以看出存在C(f)C(e)C(f)C(e)，但但efef。使用逻辑时钟只能对事件作部分排序！使用逻辑时钟只能对事件作部分排序！可以通过对发生的事件加上进程标识符且对进程标识符进可以通过对发生的事件加上进程标识符且对进程标识符进行排序，来实现对事件的完全排序。行排序，来实现对事件的完全排序。进程进程P P上的事件上的事件a a时间邮时间邮戳为戳为T Ta a，进

5、程进程Q Q上的事件上的事件b b时间邮戳为时间邮戳为T Tb b，定义：定义：a a、b b的全局时间邮戳分别为的全局时间邮戳分别为 (T(Ta a，p)p)，(T(Tb b，q)q)，(T(Ta a，p)(Tp)(Tb b，q)q)当且仅当当且仅当T Ta a T Tb b 或者或者T Ta a=T=Tb b但同时有但同时有p qp T Tj j则则将令牌交给将令牌交给P Pj j，否则删除该请求继续查否则删除该请求继续查看，直至队列为空。若队列已空令牌仍在手中，等到看，直至队列为空。若队列已空令牌仍在手中，等到m mj j T Tj j的的请求出现时，再转移令牌。无令牌进程接到请求将其插

6、入请请求出现时，再转移令牌。无令牌进程接到请求将其插入请求队列即可。求队列即可。实际上，临界区实际上，临界区C C已经扩大为（已经扩大为（C C，T T）了。了。第三章第三章 分布式系统中的通信分布式系统中的通信3.协调者选择问题协调者选择问题 分布式系统中常常会有分布式系统中常常会有“协调者协调者”，如何选择。，如何选择。Bully算法算法 系统中有系统中有n个进程个进程P1，P2，Pn，假定进程号最大者为假定进程号最大者为协调进程。某一进程在规定时间内无法与协调者联系，可以协调进程。某一进程在规定时间内无法与协调者联系，可以发起竞选。发起竞选。Pi发起竞选，广播附有本进程号的竞选消息。发起

7、竞选，广播附有本进程号的竞选消息。Pi接到消息，若自己号小则沉默，否则发回拒绝消息，接到消息，若自己号小则沉默，否则发回拒绝消息，自己发起竞选。自己发起竞选。竞选者在规定时间内未接到拒绝消息，自动当选。广竞选者在规定时间内未接到拒绝消息，自动当选。广播当选消息，运行协调程序，成为协调进程。否则竞选失败，播当选消息，运行协调程序，成为协调进程。否则竞选失败，准备接受他人当选消息。若规定时间内未接到当选消息，可准备接受他人当选消息。若规定时间内未接到当选消息，可再度发起竞选。再度发起竞选。第三章第三章 分布式系统中的通信分布式系统中的通信 环形算法环形算法 结点组成逻辑环。结点组成逻辑环。进程进程

8、Pi发起竞选，创建一活跃表，填入本进程号，发发起竞选，创建一活跃表，填入本进程号，发送给左邻，若左邻规定时间内未应答，则故障，跳过其向下送给左邻，若左邻规定时间内未应答，则故障，跳过其向下一个发送，直至非故障者。一个发送，直至非故障者。进程进程Pj接到右邻的竞选消息接到右邻的竞选消息 若为第一次接到，将本进程号加入表中向左邻发送若为第一次接到，将本进程号加入表中向左邻发送 若为第二次接到，又若本进程号最大，则向左邻发若为第二次接到，又若本进程号最大，则向左邻发布自己当选消息，否则继续传送活跃表布自己当选消息，否则继续传送活跃表 进程接到当选消息必须立即向左邻转发，直至当选者进程接到当选消息必须

9、立即向左邻转发，直至当选者从右邻获得自己当选消息为止。从右邻获得自己当选消息为止。第三章第三章 分布式系统中的通信分布式系统中的通信4.原子事务原子事务 事务模型事务模型 事务原语事务原语 begin-transaction 事务开始事务开始 end-transaction 事务结束事务结束 abort-transaction 退出事务，恢复事务开始状态退出事务，恢复事务开始状态 等。等。事务的特性事务的特性 顺序性顺序性 原子性原子性 永久性永久性 嵌套事务：父子事务提交的时机与分布式环境嵌套事务：父子事务提交的时机与分布式环境第三章第三章 分布式系统中的通信分布式系统中的通信 分布式系统中

10、事务的实现分布式系统中事务的实现 副本问题副本问题 一致性一致性 读写分开问题读写分开问题 修改日志修改日志 两阶段提交两阶段提交 第一阶段：发送消息，检查提交准备工作并回送检查第一阶段：发送消息，检查提交准备工作并回送检查结果结果 第二阶段：发送消息，要求提交或第二阶段：发送消息，要求提交或abort 事务发起者即为协调者事务发起者即为协调者第三章第三章 分布式系统中的通信分布式系统中的通信 协调者需要：协调者需要：知道事务涉及的所有结点知道事务涉及的所有结点 让所有参与者知道谁是协调者让所有参与者知道谁是协调者 做法做法 Client向每个服务器发送事务函数向每个服务器发送事务函数 Add

11、server（事务名，协调者名）事务名，协调者名）每个参与者（非协调者）向协调者发送报到消息每个参与者（非协调者）向协调者发送报到消息 NewserverNewserver（事务名，本结点名）事务名，本结点名）协调者生成一张参与者表，在收到参与者消息后将协调者生成一张参与者表，在收到参与者消息后将每个参与者列入表中每个参与者列入表中 第三章第三章 分布式系统中的通信分布式系统中的通信 事务并发控制事务并发控制 锁机制锁机制 可能引起死锁可能引起死锁 空间数据上锁的粒度问题空间数据上锁的粒度问题 乐观机制乐观机制 冲突处理：为每个数据结构记录读、写时间，在提冲突处理：为每个数据结构记录读、写时间

12、，在提交时刻检查，若已被其他事务修改，本事务中止，否则提交时刻检查，若已被其他事务修改，本事务中止，否则提交。在重负载时，失败率急剧上升。交。在重负载时，失败率急剧上升。时间邮戳时间邮戳 约定：每个数据只有一个版本约定：每个数据只有一个版本第三章第三章 分布式系统中的通信分布式系统中的通信 方法方法1 1：设置两类时间邮戳：事务开始邮戳，数据访问邮戳设置两类时间邮戳：事务开始邮戳，数据访问邮戳 事务提交前检查：若事务戳晚于所涉及数据上其它的数事务提交前检查：若事务戳晚于所涉及数据上其它的数据辍，表示该事务开始后所有数据未被其他事务访问，可据辍，表示该事务开始后所有数据未被其他事务访问，可以提交

13、，否则中止提交过程，失败！以提交，否则中止提交过程，失败！方法方法2 2：时间戳分为两类四种：读（尝试读时间戳分为两类四种：读（尝试读TTr r，结束读结束读T Tr r）、）、写（尝试写写（尝试写TTW W，结束写结束写T TW W），），读写进行时用盖读写进行时用盖“尝试尝试”，提交时盖，提交时盖“结束）。结束）。不要求严格保证互斥，只需保证不同事务的先后次序即不要求严格保证互斥，只需保证不同事务的先后次序即可。可。不会引起死锁，但实现复杂。不会引起死锁，但实现复杂。第三章第三章 分布式系统中的通信分布式系统中的通信例例两个事务两个事务a，b（其中其中a先开始）的情形。先开始）的情形。A.

14、无冲突，可继续进行，其中无冲突，可继续进行，其中x，y代表任意的事务代表任意的事务B.有冲突，需中止有冲突，需中止C.对对A而言，等待而言，等待B的提交的提交Tr(x)Tw(y)Tw(a)Tr(a)Tr(x)Tw(y)Tr(a)Tr(b)Tw(a)Tr(b)Tw(a)Tw(b)Tr(a)Tw(b)Tr(a)Tw(b)Tw(b)Tr(a)第三章第三章 分布式系统中的通信分布式系统中的通信3 3 Client/ServerClient/Server模型模型 应用系统的逻辑层次：应用系统的逻辑层次：表表 示示 逻逻 辑辑应应 用用 逻逻 辑辑数数 据据 操操 纵纵 逻逻 辑辑数数 据据 库库 逻逻

15、辑辑第三章第三章 分布式系统中的通信分布式系统中的通信 应用系统的工作方式与结构：应用系统的工作方式与结构：Host-Based Device-Shared Client-Server Peer-to-Peer 从分布式系统角度来看，从分布式系统角度来看，client与与server的关系就是一组的关系就是一组协同进程关系，而且是一种主从关系协同进程。形成一对多协同进程关系，而且是一种主从关系协同进程。形成一对多的关系。的关系。第三章第三章 分布式系统中的通信分布式系统中的通信1.寻址问题：三种寻址方式寻址问题：三种寻址方式Client核心核心server核心核心121：请求：请求 2：服务应

16、答：服务应答Client核心核心server核心核心34121：广播：广播 2：应答：应答 3：请求：请求 4：服务应答：服务应答Client核心核心server核心核心Name server核心核心12341：查找：查找 2：NS应答应答 3：请求：请求 4：服务应答：服务应答第三章第三章 分布式系统中的通信分布式系统中的通信 评论：第一种：绑定，不透明；第二种：开销大；第三种：评论：第一种：绑定，不透明；第二种：开销大；第三种：集中式。集中式。2.消息传送原语消息传送原语 执行方式执行方式 阻塞方式，同步通信阻塞方式，同步通信 非阻塞方式，异步通信非阻塞方式，异步通信 实现方式实现方式 缓

17、冲方式，设置邮箱，消息在邮箱暂存。问题：邮箱缓冲方式，设置邮箱，消息在邮箱暂存。问题：邮箱满如何处置满如何处置 非缓冲方式，不设邮箱，消息直接送入接收者指定的非缓冲方式，不设邮箱，消息直接送入接收者指定的存储区，问题：存储区，问题：receive必须早于必须早于send，第三章第三章 分布式系统中的通信分布式系统中的通信3.可靠性问题可靠性问题 两次确认方法两次确认方法Client核心核心server核心核心13241.服务请求服务请求 2.请求确认请求确认 3.服务应答服务应答 4.应答确认应答确认2.确认在核心之间进行确认在核心之间进行一次确认方法一次确认方法 省略请求确认，以服务应答隐含

18、代替省略请求确认，以服务应答隐含代替第三章第三章 分布式系统中的通信分布式系统中的通信Client-server通信协议通信协议消息代码消息代码 消息类型消息类型 发送者发送者 接收者接收者 说说 明明REQ 服务请求服务请求 client server client请求服务请求服务REP 服务结果应答服务结果应答 server client server回送结果回送结果ACK 接收消息确认接收消息确认 任意任意 任意任意 消息已经收到消息已经收到AYA 询问：还活着吗询问：还活着吗 client server 了解是否故障了解是否故障IAA 回答：还活着回答：还活着 server clien

19、t 回答：无故障回答：无故障TA 再试一次再试一次 server client server邮箱已满邮箱已满AU 地址不详地址不详 server client 无进程用此地址无进程用此地址消息代码消息代码 消息类型消息类型 发送者发送者 接收者接收者 说说 明明REQ 服务请求服务请求 client server client请求服务请求服务REP 服务结果应答服务结果应答 server client server回送结果回送结果ACK 接收消息确认接收消息确认 任意任意 任意任意 消息已经收到消息已经收到AYA 询问：还活着吗询问：还活着吗 client server 了解是否故障了解是否故

20、障IAA 回答：还活着回答：还活着 server client 回答：无故障回答：无故障TA 再试一次再试一次 server client server邮箱已满邮箱已满AU 地址不详地址不详 server client 无进程用此地址无进程用此地址第三章第三章 分布式系统中的通信分布式系统中的通信4.组通信组通信 组有动态性，单个结点可以是多个组的成员组有动态性，单个结点可以是多个组的成员 组通信分类组通信分类 原子组播原子组播 所有组员要么全部收到，要么都不收到所有组员要么全部收到，要么都不收到 实现：设置定时器，发送者在定时结束时发出停止传递消息实现：设置定时器，发送者在定时结束时发出停止

21、传递消息 接收者若未收到停止传递消息则转播（组播）接收者若未收到停止传递消息则转播（组播）可靠组播可靠组播 任意组员有应答即可任意组员有应答即可 不可靠组播不可靠组播 播出去即可播出去即可第三章第三章 分布式系统中的通信分布式系统中的通信 定序问题定序问题 网络传播时间上具有不确定性，定序不当将破坏数据一网络传播时间上具有不确定性，定序不当将破坏数据一致性。两个冗余的数据库服务器：致性。两个冗余的数据库服务器：server 1server 2client1client11234Client1首先组播：首先组播：A改为改为5，B改为改为4；client4组播：组播：A改为改为10，B改为改为A+

22、B；正确结果：两库均为：正确结果：两库均为：A=10，B=14 若通信次序如图，若通信次序如图，server1中中A=10，B=14；server2中中A=5，B=4库中库中A、B初值任意初值任意第三章第三章 分布式系统中的通信分布式系统中的通信 全局定序全局定序ABCAST 类似两阶段提交，发送者对消息附加类似两阶段提交，发送者对消息附加“序列邮戳序列邮戳”并并组播；接收者返回一个自己的序列邮戳（大于它任何收到或组播；接收者返回一个自己的序列邮戳（大于它任何收到或发送的邮戳值）；发送者收到所有回执后，选其中最大者附发送的邮戳值）；发送者收到所有回执后，选其中最大者附加在提交消息中组播，服务器

23、的提交工作按邮戳次序进行。加在提交消息中组播，服务器的提交工作按邮戳次序进行。因果定序因果定序CBCAST 每个组员都维护一个其个数与组员相等的向量，分别每个组员都维护一个其个数与组员相等的向量，分别每个分量与一个组员对应，初值均为零。每个组员组播消息每个分量与一个组员对应，初值均为零。每个组员组播消息时，将代表自己的分量加时，将代表自己的分量加1后发出消息，接收者接收来自成后发出消息，接收者接收来自成员员j的消息并处理必须符合条件：的消息并处理必须符合条件：Vj=Lj+1且且ViLi（ij），），否否则延迟接收与处理。则延迟接收与处理。第三章第三章 分布式系统中的通信分布式系统中的通信ABC

24、(0,0,0)(0,0,0)(0,0,0)M1(1,0,0)M2(1,0,0)(1,1,0)消息消息2虽到达，但必须推迟提交虽到达，但必须推迟提交消息消息1到达并提交到达并提交消息消息2 2推迟后提交推迟后提交第三章第三章 分布式系统中的通信分布式系统中的通信468210368215358215378215268215378315成员号成员号012345组播组播接收接收延迟延迟接收接收延迟延迟接收接收第三章第三章 分布式系统中的通信分布式系统中的通信 组播的设计组播的设计 原则原则 效率：充分利用网络层提供的组播寻址功能效率：充分利用网络层提供的组播寻址功能 可靠性：防止消息没有送到或只有部分

25、送到后故障可靠性：防止消息没有送到或只有部分送到后故障 可监控：能判断成员故障，能必要时重发可监控：能判断成员故障，能必要时重发 设计问题讨论设计问题讨论 封闭式与开放式小组：前者适合并行处理，后者适封闭式与开放式小组：前者适合并行处理，后者适合冗余服务器情形合冗余服务器情形 对等式与层次式结构：前者可靠但开销大，后者有对等式与层次式结构：前者可靠但开销大，后者有集中式缺点集中式缺点第三章第三章 分布式系统中的通信分布式系统中的通信 组的管理问题：设立组管理器，有集中式弊病但简单；组的管理问题：设立组管理器，有集中式弊病但简单；组管理分散则复杂，开销大组管理分散则复杂，开销大 组寻址问题：对网

26、络支持的要求；利用组寻址问题：对网络支持的要求；利用IP表利用点对点表利用点对点通信实现；断言寻址法通信实现；断言寻址法-消息中包含断言，消息周游时，消息中包含断言，消息周游时，接点自行判断应否接收消息接点自行判断应否接收消息 组重叠问题组重叠问题 全局时间定序只能在组内进行，要扩大到整个系统极全局时间定序只能在组内进行，要扩大到整个系统极其复杂。其复杂。根据应用逻辑，具体对待。根据应用逻辑，具体对待。第三章第三章 分布式系统中的通信分布式系统中的通信5.远程过程调用远程过程调用RPC 本地过程调用本地过程调用c=proc(fd,buf,k)前后数据栈的变化前后数据栈的变化调用前调用前调用中调

27、用中调用后调用后主程序的局主程序的局部变量部变量主程序的局主程序的局部变量部变量KBufFd返回地址返回地址过程过程proc的的局部变量局部变量主程序的局主程序的局部变量部变量spspsp第三章第三章 分布式系统中的通信分布式系统中的通信 RPC的实现的实现 分同步、异步两种分同步、异步两种Client应用程序应用程序stubstubServer程序程序网网 络络参数打包参数打包结果打包结果打包结果解包结果解包参数解包参数解包第三章第三章 分布式系统中的通信分布式系统中的通信实现步骤：实现步骤：client应用程序正常调用应用程序正常调用client stub client stub构造消息，

28、通过构造消息，通过trap进入核心进入核心 核心将消息发送到核心将消息发送到server的核心的核心 server核心将消息交给核心将消息交给server stub server stub将消息解包，用相应参数调用服务例程将消息解包，用相应参数调用服务例程 服务例程进行计算，将结果返回服务例程进行计算，将结果返回server stub server stub 构造消息，通过构造消息，通过trap进入核心进入核心 核心将消息发送到核心将消息发送到client的核心的核心 client核心接收消息并将它交给相应核心接收消息并将它交给相应stub stub解包，将调用结果返回应用程序解包，将调用结果

29、返回应用程序第三章第三章 分布式系统中的通信分布式系统中的通信 RPC的参数传递的参数传递 数据格式问题数据格式问题 统一规范格式，简单但不灵活，效率也不高统一规范格式，简单但不灵活，效率也不高 增加一个参数，或在消息中指明格式，由接收者做增加一个参数，或在消息中指明格式，由接收者做相应处理，效率较高，但每个机器需配置完全的格式转换相应处理，效率较高，但每个机器需配置完全的格式转换程序程序 指针类参数问题指针类参数问题 全部禁用，不利于用户使用全部禁用，不利于用户使用 复制复制/重新存储方法，重新存储方法，client以实体代替指针，以实体代替指针，server生成缓冲区存放实体，计算后将缓冲

30、区打包发回生成缓冲区存放实体，计算后将缓冲区打包发回 复杂数据类型问题复杂数据类型问题 在在GISGIS中，指针指向图，此时需制订专门的通信协议，详细中，指针指向图，此时需制订专门的通信协议，详细描述数据规格，并配置相应程序读取描述数据规格，并配置相应程序读取 第三章第三章 分布式系统中的通信分布式系统中的通信 client-server的连接的连接 解决解决client stub与与server地址的绑定问题地址的绑定问题 静态连接静态连接 在在client配置时，将地址登入配置时，将地址登入stub。简单，不灵活简单，不灵活 动态连接动态连接 设立地址连接服务器设立地址连接服务器 连接服务

31、器维护所有服务的接口与地址，连接服务器维护所有服务的接口与地址，server启动时，将自己的地址与服务接口发给连接服务器，关闭时启动时，将自己的地址与服务接口发给连接服务器，关闭时要求撤销注册；要求撤销注册；client首次使用某个首次使用某个RPC时，向连接服务器时，向连接服务器发消息请求得到它的接口与发消息请求得到它的接口与server地址地址。灵活，但开销大，具有集中式的一切弊病灵活，但开销大，具有集中式的一切弊病第三章第三章 分布式系统中的通信分布式系统中的通信 例外处理例外处理 找不到服务器找不到服务器 多次发送消息都未受到应答，作为例外事件来处理，多次发送消息都未受到应答，作为例外

32、事件来处理，用户编写例外时间处理程序。用户编写例外时间处理程序。收不到应答消息收不到应答消息 消息丢失消息丢失 按找不到服务器处理。按找不到服务器处理。某些特殊请求应在请求消息中注明最多执行一次，某些特殊请求应在请求消息中注明最多执行一次，这样服务器再次收到这个请求不再执行，只将结果重发。这样服务器再次收到这个请求不再执行，只将结果重发。服务器故障服务器故障第三章第三章 分布式系统中的通信分布式系统中的通信 故障时刻：故障时刻：早就故障；早就故障；接到请求，处理开始前故障；接到请求，处理开始前故障；处理过程中故障；处理过程中故障；处理结束，发出应答消息前故障；处理结束，发出应答消息前故障；应对

33、策略应对策略 RPC至少处理一次，可以多次，以最后一次为准至少处理一次，可以多次，以最后一次为准 至多处理一次，可以不处理至多处理一次，可以不处理 不做承诺，可以是不做承诺，可以是0-n次次 恰好恰好1次。次。第三章第三章 分布式系统中的通信分布式系统中的通信 Client故障故障 考虑发出请求后，收到应答前故障，使服务器无法结考虑发出请求后，收到应答前故障，使服务器无法结束事务。束事务。处理策略处理策略 清除法。清除法。Client为每次为每次RPC做日志，恢复时显式清除做日志，恢复时显式清除RPC。但在但在RPC嵌套时，可能无法实现。嵌套时，可能无法实现。再生法。将时间划分为顺序编号的时段

34、，再生法。将时间划分为顺序编号的时段，client恢复恢复时，广播新时段开始，有关机器接到广播后清除所有老时时，广播新时段开始，有关机器接到广播后清除所有老时段的运算。段的运算。温和再生法。只清除无主的温和再生法。只清除无主的RPC。过期法。为每个过期法。为每个RPC规定标准时限，若在标准时限内规定标准时限，若在标准时限内不能结束，必须先申请延长，否则自动清除。不能结束，必须先申请延长，否则自动清除。第三章第三章 分布式系统中的通信分布式系统中的通信 通信设计问题通信设计问题 协议问题协议问题 面向连接的协议面向连接的协议 Client与与Server固定捆绑，简单，可靠，无需处理固定捆绑，简

35、单，可靠，无需处理确认，适用于广域网；但性能较低，由于额外的软件开销，确认，适用于广域网；但性能较低，由于额外的软件开销，对局域网而言，本来就很可靠，必要性不大。对局域网而言，本来就很可靠，必要性不大。面向非连接的协议面向非连接的协议 虽需要处理确认等以保证可靠性，但效率高，在局虽需要处理确认等以保证可靠性，但效率高，在局域网上适用。域网上适用。第三章第三章 分布式系统中的通信分布式系统中的通信 信包大小问题信包大小问题 与使用的协议有关，原则上长信包的效率较高，例如与使用的协议有关，原则上长信包的效率较高，例如以太网以太网1536B，SUN更大，更大，8K。信包确认问题信包确认问题 停停-等

36、协议，上一个信包确认后才发下一个，发现丢等协议，上一个信包确认后才发下一个，发现丢失及时补发失及时补发 爆发协议，信包全部一次发完，然后总体确认。发现爆发协议，信包全部一次发完，然后总体确认。发现丢失时，局域网上往往采用全部重发，广域网上则采用有丢失时，局域网上往往采用全部重发，广域网上则采用有选择重发选择重发 超限处理问题，使用爆发协议时，超长消息容易引起超限处理问题，使用爆发协议时，超长消息容易引起截断性丢失问题，通常根据芯片缓冲区大小，将消息分成截断性丢失问题，通常根据芯片缓冲区大小，将消息分成数段中间设置停顿。数段中间设置停顿。第三章第三章 分布式系统中的通信分布式系统中的通信4 4

37、异步通信问题异步通信问题1.1.通信时的进程关系模型通信时的进程关系模型 同步模型同步模型 发送进程在收到消息已被接受的确认前，不认为此次发送进程在收到消息已被接受的确认前，不认为此次通信已经完成，进程必须等待，不再进行其他工作。通信已经完成，进程必须等待，不再进行其他工作。异步模型异步模型 发送进程将消息放入发送信箱以后即认为此次通信已发送进程将消息放入发送信箱以后即认为此次通信已经完成，进程转而进行别的工作。经完成，进程转而进行别的工作。问题：在异步情况，进程问题：在异步情况，进程P P向进程向进程Q Q先后发出两条消息先后发出两条消息m m1 1、m m2 2，由于传输原因，由于传输原因

38、，m m2 2先于先于m m1 1到达并接收，谓之超越。到达并接收，谓之超越。第三章第三章 分布式系统中的通信分布式系统中的通信2.解决思路解决思路 无限制，显然问题很多无限制，显然问题很多 FIFO，太严格，有时无必要。无关联的消息允许无序，太严格，有时无必要。无关联的消息允许无序，即使是有关联的消息也并非完全不能超越。即使是有关联的消息也并非完全不能超越。实现问题：如何确定当前消息是第一个消息，若认为实现问题：如何确定当前消息是第一个消息，若认为可能有超越，等待多长时间才可确定无超越。可能有超越，等待多长时间才可确定无超越。F通道，将消息分为通道，将消息分为4类：类：t：两端堵塞，前后不许

39、超越两端堵塞，前后不许超越 o：任意，允许超越和被超越任意，允许超越和被超越 b：向后堵塞，不许被超越向后堵塞，不许被超越 f：向前堵塞，不许超越别人向前堵塞，不许超越别人第三章第三章 分布式系统中的通信分布式系统中的通信 层次通道，将消息分为若干层次，每一层次遵循同一层次通道，将消息分为若干层次，每一层次遵循同一种通道规则。不同层次通道的消息，高层次通道的消息可种通道规则。不同层次通道的消息，高层次通道的消息可以超越低层次通道的消息。以超越低层次通道的消息。3.PCAP（process-Channel-Agent-Process）模模型型 在发送进程在发送进程P和接收进程和接收进程Q之间引入

40、之间引入Agent C pq PCpqQ P P的发送序列为的发送序列为q q1 1，Q Q的接收序列为的接收序列为q q2 2，两者元素相同，次序可能不同。两者元素相同，次序可能不同。Q Q可向可向C Cpqpq发送要求（例如发送序列的一个子集），发送要求（例如发送序列的一个子集），C Cpqpq按按要求将消息以接要求将消息以接收序列的次序送给收序列的次序送给Q Q。第三章第三章 分布式系统中的通信分布式系统中的通信 通道语法规则通道语法规则 消息序列消息序列 通道语法通道语法G 发送序列发送序列send 接收序列接收序列recv send recv，表示表示send经符合经符合G的若干次超

41、越后的若干次超越后形成接收序列形成接收序列recv 可传送集可传送集D=m|，表示表示m可以可以加到序列加到序列Si的首部的首部*G*G第三章第三章 分布式系统中的通信分布式系统中的通信 例例 F F通道规则通道规则G GF F R1：o型消息可以相互超越型消息可以相互超越 R2：o型消息可以超越前面的型消息可以超越前面的f型消息型消息 R3：b 型消息可以超越前面型消息可以超越前面的的o型消息型消息 R4：b型消息可以超越前面的型消息可以超越前面的f型消息型消息 这样，令层次通道规则这样，令层次通道规则Gh为层次间语法规则为层次间语法规则Rh和和各层通各层通道的语法规则道的语法规则Gi的并集

42、：的并集：Gh=RhGiRh：iff iff(mi.levelm.level（实际上，实际上，L表示了那些在它前面的元素层次都较表示了那些在它前面的元素层次都较低的元素集合）低的元素集合）D=Di，Di=m|(m.level=I)且且ExtractSame(m,Sm)Smm这里这里ExtractSame(m,Sm)表示在表示在Sm中中取出与取出与m层次相同的消层次相同的消息后形成的消息序列。息后形成的消息序列。i0i0*Gi第三章第三章 分布式系统中的通信分布式系统中的通信 这样，这样，m=v且且m Dh就变成了就变成了m=v且且m(LD)引入记号，用以判断引入记号，用以判断m是否可以在是否可

43、以在Sm中超越（即中超越（即m L）：）：NonLowerAhead(m,Sm)=true iff (Sm=SmS)(m S：m.levelm.level)；这样再引入这样再引入 LevelDeliverable(m,Sm)=true iff ExtractSame(m,Sm)Smm （即（即m在同一通道中可传送）在同一通道中可传送）*Gi第三章第三章 分布式系统中的通信分布式系统中的通信 改进后的改进后的Cpq算法算法 收到来自收到来自P的消息的消息m，则则 ）Sm=mSm；）若若 NonLowerAhead(m,Sm)=true 则则 L=Lm；）若若LevelDeliverable(m,

44、Sm)=true 则则 D=Dm；收到来自收到来自Q的要求的要求v，则，则Sv=vSv；若若SveLD e 则则 ）x=first(Sv)）若若 mm(LD)则则 将将m移至移至Sm的首部，的首部，Sm=after(m,Sm)；L=m NonLowerAhead(m,Sm)；第三章第三章 分布式系统中的通信分布式系统中的通信 D=m|LevelDeliverable(m,Sm)；send（m,Q）；）；Sv=after（m,Sv）；）；转转 否则转否则转 转转 显然，目前显然，目前PCAP的算法只是定性描述，只有在确定了各的算法只是定性描述，只有在确定了各子通道的类型，子通道的类型，Level

45、Deliverable(m,Sm)才是确定的和可才是确定的和可计算的。计算的。第三章第三章 分布式系统中的通信分布式系统中的通信5 5 RPC的结构模型的结构模型1.1.一对多模型一对多模型 在这种情况，系统中存在多个在这种情况，系统中存在多个Server，对一个对一个client，其，其RPC发往何处并不明确。发往何处并不明确。分散式分散式 RPC以广播方式发出，每个以广播方式发出，每个server收到后自行判断。收到后自行判断。或抛弃（或抛弃（server无此服务），或执行无此服务），或执行RPC。优点：逻辑简单，优点：逻辑简单，client处理方便。处理方便。缺点：网络开销大，计算开销大

46、（缺点：网络开销大，计算开销大（server需要判断，甚需要判断，甚至重复计算）至重复计算）第三章第三章 分布式系统中的通信分布式系统中的通信 改进型：改进型：client上配置全局服务目录，由上配置全局服务目录，由client自行选取自行选取提供服务的提供服务的server，定向发送定向发送RPC。适用于专业系统。适用于专业系统。集中式集中式 配置服务目录配置服务目录agent。改进型：改进型：ClientagentRPC执行结果执行结果Server 1Server nagentServer 1Server nClient服务地址服务地址询问地址询问地址WEB Service第三章第三章 分

47、布式系统中的通信分布式系统中的通信 优点：减少了网络负载优点：减少了网络负载 缺点：缺点：agent的负担过大，将成为系统的瓶颈，一旦故障，的负担过大，将成为系统的瓶颈，一旦故障，系统陷于崩溃。系统陷于崩溃。改进型（改进型（WEB Service）虽然部分减轻了虽然部分减轻了agent的的负载，但是增加了网络的开销。集中式的弊病依然存在。负载，但是增加了网络的开销。集中式的弊病依然存在。第三章第三章 分布式系统中的通信分布式系统中的通信2.多对多模型多对多模型 在这种情形，一个在这种情形，一个client可以同时发出多个可以同时发出多个RPC，指向多指向多个个server。m-to-m（age

48、nt-id，n，service1，arg1,，argt1，servicen，arg1，argtn）实现模型实现模型m-to-mAgent leader服务结果服务结果返回结果返回结果队列队列管理管理Agent线程线程（服务队列）服务队列）输向输向server的服务请求的服务请求第三章第三章 分布式系统中的通信分布式系统中的通信工作示意工作示意clientagentserverm-to-m接收接收m-to-m请求，分配线程，将请求，分配线程，将分服务要求插入线程，进行线程分服务要求插入线程，进行线程调度。调度。各线程分别向各线程分别向server发送服务请发送服务请求求接收服务请求，执行服务接收

49、服务请求，执行服务例程。发送服务结果。例程。发送服务结果。接收服务结果，根据服务存根接收服务结果，根据服务存根分类存放，收齐所有结过后向分类存放，收齐所有结过后向client发送。发送。发送服务请求发送服务请求回送服务结果回送服务结果接收结果接收结果向向agent发送发送RPC请请求求第三章第三章 分布式系统中的通信分布式系统中的通信 讨论：讨论：如果只有一个如果只有一个agent，将引起超载将引起超载 若有多个若有多个agent副本，之间如何协调以避免重复副本，之间如何协调以避免重复 agentagent公布负载情况，供用户选择？公布负载情况，供用户选择？用户规定用户规定agentagent次序，超载次序，超载agentagent自动转移负载？自动转移负载？划分划分agent的功能范围，划分原则的功能范围，划分原则 静态划分，增加用户负担，不方便静态划分，增加用户负担，不方便 动态划分，管理困难动态划分，管理困难 划分原则的确定划分原则的确定