《分布式系统中的计算模型》由会员分享，可在线阅读，更多相关《分布式系统中的计算模型（38页珍藏版）》请在金锄头文库上搜索。
1、,1,第4章 分布式系统中的计算模型,2006.12.15,2,概述,分布式系统计算模型的复杂性 系统由并发执行部件构成 系统中无全局时钟 必须捕捉系统部件可能的失效 对策 因果关系（Causality） 一致状态（Consistent states） 全局状态,3,4.1 基本知识,协议（Protocol） 协议中的控制语句 1.Send（destination, action; parameters） destination：处理器抽象。实用中是通信实体的地址： 机器名，机器的端口号(即1个socket地址) action： 控制msg，希望接收者采取的动作 parameters：参数集合
2、 假定： msg发送是无阻塞、可靠的（语义类似于TCP套接字）； 有时假定较弱的msg传递层（等价于UDP）。,4,4.1 基本知识,2.接收msg 接收msg可推广至接收事件，引起事件的原因是： 外部msg、超时设定、内部中断 事件在处理前，一般是在缓冲区（如事件队列）中，若一处理器想处理事件，它必须执行一个声明处理这些事件的线程。 例如，一个处理器通过执行下述代码等待事件A1, A2,., An waiting for A1, A2,., An ：/声明 A1（Source; parameters） Code to handle A1 . A1（Source; parameters） Co
3、de to handle An 当p执行send(q, A1; parameters)且q执行上述代码时，q将最终处理由p发送的msg,5,4.1 基本知识,3.超时 当怀疑远程处理器失效时，可通过超时检测来判定： 当T秒后仍未收到P的类型为event的msg时，执行指定的动作 waiting until P sends (event; parameters), timeout=T on timeout timeout action 仅当收到一个响应msg时才采取动作，超时不做任何动作 waiting until P sends (event; parameters), timeout=T o
4、n timeout； if no timeout occurred Successful response actions ,6,4.1 基本知识,3.超时 处理器等待响应T秒 若处理器在等待开始后T秒内没响应，则等待结束，协议继续 waiting up to T seconds for (event; parameters) msgs Event: ,7,4.2 因果关系,分布式系统为何缺乏全局的系统状态？ 1.非即时通信 A和B同时向对方喊话 他们都认为是自己先喊话 C听到两人是同时喊话 结论：系统的全局状态依赖于观察点 原因： 传播延迟 网络资源的竞争 丢失msg重发,d1 = d2,8
5、,4.2 因果关系,2.相对性影响 假设张三和李四决定使用同步时钟来观察全局状态： 他们约定下午5点在某餐馆会面，张三准时到达，但李四在一个接近光速的日光系统中游览。 张三在等待李四1小时后离开餐馆，而李四在自己的表到达5点时准时达到餐馆，但他认为张三未达到。 因为大多数计算机的实际时钟均存在漂移，故相对速度不同，时钟同步仍然是一个问题。 结论：使用时间来同步不是一个可靠机制。,9,4.2 因果关系,3.中断 假设张三和李四在同一起跑线上赛跑，信号为小旗，前两个问题可以忽略，但是 即使可忽略其他影响，也不可能指望不同的机器会同时做出某些反应。因为现代计算机是一个很复杂的系统：CPU竞争、中断、
6、页错误等，执行时间无法预料。 结论：不可能在同一时刻观察一个分布式系统的全局状态 必须找到某种可以依赖的性质： 时间回溯 因果相关,10,4.2 因果关系,假设分布式系统构成： PP1, P2, Pn：处理器集合 E：全体事件的集合 EpE, Ep表示发生在p上的所有事件 次序 e1e2： 事件e1发生e2在之前（亦记：e1e2） e1I e2：事件e1发生e2在之前，I为信息源 定序 有些E中事件很容易定序： 发生在同一节点p上的事件满足全序： 若e1,e2 Ep，则 e1pe2 或 e2pe1 成立 e1发送消息m,e2接收m，则e1me2,11,4.2 因果关系,Happens-befo
7、re关系（H） 该关系是节点次序和消息传递次序的传递闭包： 规则1：若e1pe2，则e1He2 规则2：若e1me2，则e1He2 规则3：若e1He2，且e2He3，则e1He3 e1He3表示存在1个事件因果链，使e1发生e3在之前 Note: H是一种偏序关系，即 存在e和e，二者之间无这种关系 并发事件：若两事件不能由H定序,12,4.2 因果关系,举例 1)因事件e1,e4和e7均发生在P1上，故：e1P1e4P1e7 2)因e1发送1个msg到e3，故：e1me3，类似地e5me8 3)应用规则1和2得： e1He4He7，e1He3，e5He8 4)由H的传递闭包性质得：e1He
8、8 5)e1和e6是并发的：e1和e6之间无 路径,13,4.2 因果关系,HDAG 有时将Happens-before关系描述为一个有向无环图 顶点集VH是事件集E：eVH 当且仅当 eE 边集EH：若(e1，e2)EH 当且仅当e1Pe2或e1me2,14,4.2.1 Lamport时间戳,系统有序性的重要性 若分布式系统中存在全局时钟，则系统中的事件均可安排为全序。例如，可以更公平地分配系统资源。 全序对事件的影响和由H关系确定的偏序对事件的影响是一致的 如何通过H关系确定的偏序关系来建立一个“一致”的全序关系？ 在H的DAG上拓扑排序 On the fly：Lamport提出了动态即席
9、地建立全序算法,15,4.2.1 Lamport时间戳,Lamport算法的思想 每个事件e有一个附加的时戳：e.TS 每个节点有一个局部时戳：my_TS 节点执行一个事件时，将自己的时戳赋给该事件； 节点发送msg时，将自己的时戳赋给所有发送的msg。,16,4.2.1 Lamport时间戳,Lamport算法的实现 Initially：my_TS=0; On event e： if ( e是接收消息m ) then my_TS = max ( m.TS, my_TS ); /取msg时戳和节点时戳的较大者作为新时戳 my_TS+; e.TSmy_TS; /给事件e打时戳 if ( e是发送
10、消息m ) then m.TSmy_TS; /给消息m打时戳,17,4.2.1 Lamport时间戳,Lamport算法赋值的时戳是因果相关的 若e1He2，则 e1.TS e2.TS 若e1Pe2或e1me2，则的e2时戳大于e1的时戳 在因果事件链上，每一事件的时戳大于其前驱事件的时戳 问题：系统中所有事件已为全序？ 不同的事件可能有相同的时戳（并发事件） Lamport算法改进 因为并发事件的时戳可以任意指定先后 故可用节点地址作为时戳的低位,18,4.2.1 Lamport时间戳,改进的Lamport时戳 事件标号：时戳.id 事件e8为4.3: my_TS=max(m.TS,my_T
11、S) =max(3,1)=3 按字典序得全序： 1.1,1.2,1.3,2.1,2.2,3.1,3.2,4.3 算法特点：分布、容错、系统开销小,19,4.2.2 向量时间戳,Lamport时戳缺点 若e1He2，则 e1.TS e2.TS；反之不然。 例如：1.32.1，但是e6e4不成立 原因：并发事件之间的次序是任意的 不能通过事件的时戳判定两事件之间是否是因果相关 判定事件间因果关系的重要性 例子：违反因果关系检测 在一个分布式对象系统中，为了负载平衡，对象是可移动的，对象在处理器之间迁移是为了获得所需的调用的进程或资源。如下图：,20,4.2.2 向量时戳,1)P1持有对象O，决定迁
12、移到P2 为获取资源，P1将O装配在消息 M1中发送给P2 2)P1收到P3访问O的请求 P1将O的新地址P2放在消息M2 中通知P3 3)P3在M3中请求访问P2的O 当M3达到P2时，O不可用，故 回答一个出错消息。 问题：当debug该系统时，会发 现O已在P2上，故不知错在哪？,21,4.2.2 向量时间戳,错误原因：违反因果序 P3请求O是发生在从P1迁移到P2之后，但该请求被处理是在迁移达到P2之前。形式地， 设：s(m)是发送m的事件 r(m)是接收m的事件 若s(m1)H s(m2)，则称消息m1因果关系上先于m2，记做m1C m2 若m1 C m2，但 r(m2) P r(m
13、1)，则违反“因果关系”： 即，若m1先于m2发送，但在同一节点P上m2在m1之前被接收 例如，在上例中有： M1CM3，但 r(M3) P2 r(M1),22,4.2.2 向量时间戳,违反因果序检测 定义：若时戳VT具有比较函数V满足： e1H e2 iff e1.VTV e2.VT 则我们能够检测出是否违反因果关系 VT性质 1）因H 是偏序，故V 也是偏序； 2）因为必须知道在因果关系上每一节点中哪些事件是在事 件e之前，故e.VT中必须包含系统中每一个其它节点的 状态。 这两个性质导致了向量时戳VT的引入,23,4.2.2 向量时戳,向量时戳VT VT是一个整数数组： e.VTi=k表
14、示在节点i（或 Pi）上，因果关系上e之前有k 个事件（可能包括e自己）。 e.VT=(3,6,4,2)表示因果序： 在P1上，有3个事件须在e之前 在P2上，有6个事件须在e之前 在P3上，有4个事件须在e之前 在P4上，有2个事件须在e之前,24,4.2.2 向量时间戳,向量时戳的意义 在因果关系上，e1.VT V e2.VT表示e2发生在 e1及e1前所有的 事件之后。更精确的说，向量时钟的次序为： e1.VTV e2.VT iff e1.VTi e2.VTi,i=1,2,M e1.VTV e2.VT iff e1.VT VTe2.VT且e1.VTe2.VT 向量时戳算法 my_VT：每
15、个节点有局部的向量时戳 e.VT：每个事件有向量时戳 m.VT：每个msg有向量时戳 节点执行一个事件时，将自己的时戳赋给该事件； 节点发送msg时，将自己的时戳赋给所有发送的msg。,25,4.2.2 向量时间戳,算法实现 Initially：my_VT=0,0; On event e： if ( e是消息m的接收者 ) then for i=1 to M do /向量时戳的每个分量只增不减 my_VT i = max( m.VTi, my_VTi ); my_VT self +; /设变量self是本节点的名字 e.VTmy_VT; /给事件e打时戳 if ( e是消息m的发送者 ) th
16、en m.VTmy_VT; /给消息m打时戳,26,4.2.2 向量时间戳,算法性质 1）若eH e，则e.VTVT e.VT 算法确保对于每个事件满足： 若eP e或em e ，则e.VTVT e.VT 2）若eH e，则e.VTVT e.VT pf：若e和e 因果相关，则有eH e，即e.VTVT e.VT 若e和e 是并发的，则在H-DAG上，从e到e和从e 到e均无有向路径，即得： e.VTVT e.VT 且 e.VT VT e.VT,27,4.2.2 向量时戳,向量时戳比较 e1.VT=(5,4,1,3) e2.VT=(3,6,4,2) e3.VT=(0,0,1,3) 1）e1和e2是并发的 e1.VT1e2.VT1 e1.VT2e2.VT2 e1到e2及e2到e1均无路径 2
