分布式系统中的计算模型

1、1第第4章章分布式系统中的计算模型分布式系统中的计算模型2006.12.152概述概述n分布式系统计算模型的复杂性分布式系统计算模型的复杂性v系统由并发执行部件构成系统由并发执行部件构成v系统中无全局时钟系统中无全局时钟v必须捕捉系统部件可能的失效必须捕捉系统部件可能的失效n对策对策v因果关系（因果关系（Causality）v一致状态（一致状态（Consistent states）v全局状态全局状态34.1 基本知识基本知识n 协议（协议（Protocol）n 协议中的控制语句协议中的控制语句 1.Send（destination, action; parameters） destinatio

2、n：处理器抽象。实用中是通信实体的地址：处理器抽象。实用中是通信实体的地址： 机器名，机器的端口号机器名，机器的端口号(即即1个个socket地址地址) action： 控制控制msg，希望接收者采取的动作，希望接收者采取的动作 parameters：参数集合参数集合 假定：假定： msg发送是无阻塞、可靠的（语义类似于发送是无阻塞、可靠的（语义类似于TCP套接字）；套接字）； 有时假定较弱的有时假定较弱的msg传递层（等价于传递层（等价于UDP）。）。TCP与与UDP的区别：的区别：基于连接与无连接基于连接与无连接对系统资源的要求（对系统资源的要求（TCP较多，较多，UDP少）少） UDP程

3、序结构较简单程序结构较简单流模式与数据报模式流模式与数据报模式 TCP保证数据正确性，保证数据正确性，UDP可能丢包可能丢包 TCP保证数据顺序，保证数据顺序，UDP不保证不保证44.1 基本知识基本知识2.接收接收msg 接收接收msg可推广至接收事件，引起事件的原因是：可推广至接收事件，引起事件的原因是： 外部外部msg、超时设定、内部中断、超时设定、内部中断 事件在处理前，一般是在缓冲区事件在处理前，一般是在缓冲区(如事件队列如事件队列)中，若一处理中，若一处理器想处理事件，它必须执行一个声明处理这些事件的线程。器想处理事件，它必须执行一个声明处理这些事件的线程。 例如，一个节点通过执行

4、下述代码等待事件例如，一个节点通过执行下述代码等待事件A1, A2,., An waiting for A1, A2,., An ：/声明声明 A1（Source; parameters） Code to handle A1 . An（Source; parameters） Code to handle An 当当p执行执行send(q, A1; parameters)且且q执行上述代码时，执行上述代码时，q将将最终处理由最终处理由p发送的发送的msg54.1 基本知识基本知识3.超时超时 当怀疑远程处理器失效时，可通过超时检测来判定：当怀疑远程处理器失效时，可通过超时检测来判定：当当T秒后仍

5、未收到秒后仍未收到P的类型为的类型为event的的msg时，执行指定的动作时，执行指定的动作 waiting until P sends (event; parameters), timeout=T on timeout timeout action仅当收到一个响应仅当收到一个响应msg时才采取动作，超时不做任何动作时才采取动作，超时不做任何动作 waiting until P sends (event; parameters), timeout=T on timeout； if no timeout occurred Successful response actions 64.1 基本知识

6、基本知识3.超时超时处理器等待响应处理器等待响应T T秒秒 若处理器在等待开始后若处理器在等待开始后T T秒内没响应，则等待结束，协议继续秒内没响应，则等待结束，协议继续 waiting up to T seconds for (event; parameters) msgs Event: 74.2 因果关系因果关系 分布式系统为何缺乏全局的系统状态？分布式系统为何缺乏全局的系统状态？ 1.非即时通信非即时通信 A A和和B B同时向对方喊话同时向对方喊话 他们都认为是自己先喊话他们都认为是自己先喊话 C C听到两人是同时喊话听到两人是同时喊话 结论：结论：系统的全局状态依赖于观察点系统的全局

7、状态依赖于观察点 原因：原因： 传播延迟传播延迟 网络资源的竞争网络资源的竞争 丢失丢失msg重发重发 ACBd1 = d284.2 因果关系因果关系2.相对性影响相对性影响 假设张三和李四决定使用同步时钟来观察全局状态：假设张三和李四决定使用同步时钟来观察全局状态： 他们约定下午他们约定下午5 5点在某餐馆会面，张三准时到达，但李四点在某餐馆会面，张三准时到达，但李四在一个接近在一个接近光速的日光系统光速的日光系统中游览。中游览。 张三在等待李四张三在等待李四1 1小时后离开餐馆，而李四在自己的表到小时后离开餐馆，而李四在自己的表到达达5 5点时准时达到餐馆，但他认为张三未达到。点时准时达到

8、餐馆，但他认为张三未达到。 因为大多数计算机的实际时钟均存在漂移，故相对速度不因为大多数计算机的实际时钟均存在漂移，故相对速度不同，时钟同步仍然是一个问题。同，时钟同步仍然是一个问题。 结论：结论：使用时间来同步不是一个可靠机制。使用时间来同步不是一个可靠机制。94.2 因果关系因果关系3.中断中断 假设张三和李四在同一起跑线上赛跑，信号为小旗，前两假设张三和李四在同一起跑线上赛跑，信号为小旗，前两个问题可以忽略，但是个问题可以忽略，但是 即使可忽略其他影响，也不可能指望不同的机器会同时做即使可忽略其他影响，也不可能指望不同的机器会同时做出某些反应。因为现代计算机是一个很复杂的系统：出某些反应

9、。因为现代计算机是一个很复杂的系统：CPUCPU竞争、中断、页错误等，执行时间无法预料。竞争、中断、页错误等，执行时间无法预料。结论：结论：不可能在同一时刻观察一个分布式系统的全局状态不可能在同一时刻观察一个分布式系统的全局状态 必须找到某种可以依赖的性质：必须找到某种可以依赖的性质：时间回溯时间回溯因果相关因果相关104.2 因果关系因果关系n 假设分布式系统构成：假设分布式系统构成： P PPP1 1, P, P2 2,., P,., Pn n ：处理器集合：处理器集合 E E：全体事件的集合：全体事件的集合 E Ep pE E, , E Ep p表示发生在表示发生在p p上的所有事件上的

10、所有事件n 次序次序 e e1 1ee2 2： 事件事件e e1 1发生发生e e2 2在之前（亦记：在之前（亦记：e e1 1ee2 2） e e1 1 I e e2 2：事件：事件e e1 1发生发生e e2 2在之前，在之前，I为信息源为信息源n 定序定序 有些有些E E中事件很容易定序：中事件很容易定序：v 发生在同一节点发生在同一节点p p上的事件满足全序：上的事件满足全序： 若若e e1 1,e,e2 2 E Ep p，则，则 e e1 1 pe e2 2 或或 e e2 2 pe e1 1 成立成立ve e1 1发送消息发送消息m,em,e2 2接收接收m m，则，则e e1 1

11、 me e2 2114.2 因果关系因果关系n Happens-before关系（关系（ H） 该关系是节点次序和消息传递次序的传递闭包该关系是节点次序和消息传递次序的传递闭包：v规则规则1 1：若若e e1 1 pe e2 2，则，则e e1 1 He e2 2v规则规则2 2：若若e e1 1 me e2 2，则，则e e1 1 He e2 2v规则规则3 3：若若e e1 1 He e2 2，且，且e e2 2 He e3 3，则，则e e1 1 He e3 3 e e1 1 He e3 3表示存在表示存在1 1个事件因果链，使个事件因果链，使e e1 1发生发生e e3 3在之前在之前

12、 Note: Note: H是一种偏序关系，即是一种偏序关系，即 存在存在e e和和ee，二者之间无这种关系，二者之间无这种关系v并发事件：并发事件：若两事件不能由若两事件不能由 H定序定序 在集合在集合 X 上的二元关系上的二元关系 R 的传递闭包是包含的传递闭包是包含 R 的的 X 上的最小的传递关系。上的最小的传递关系。 124.2 因果关系因果关系nHappens-before关系（关系（ H）v规则规则1 1表述的是同一处理器上两个事件之间的因果关系；表述的是同一处理器上两个事件之间的因果关系；v规则规则2 2表述了不同处理器上两个事件之间的因果关系表述了不同处理器上两个事件之间的因

13、果关系v规则规则3 3阐述了传递律阐述了传递律Note: Happens-Before关系完整表述了执行中的因果关系。关系完整表述了执行中的因果关系。如果一个执行中的事件按照其相对顺序重新进行排如果一个执行中的事件按照其相对顺序重新进行排序，而不改变他们的序，而不改变他们的happens-before关系的话，那关系的话，那么其结果仍是一个执行，并且对处理器而言，该执么其结果仍是一个执行，并且对处理器而言，该执行与原执行并无区别。行与原执行并无区别。134.2 因果关系因果关系n 举例举例1)1)因事件因事件e1,e4e1,e4和和e7e7均发生在均发生在P1P1上，故：上，故：e e1 1

14、P1e e4 4 P1e e7 72)2)因因e1e1发送发送1 1个个msgmsg到到e3e3，故：，故：e e1 1 me e3 3，类似地，类似地e e5 5 me e8 83)3)应用规则应用规则1 1和和2 2得：得： e e1 1 He e4 4 He e7 7，e e1 1 He e3 3，e e5 5 He e8 84)4)由由 H的传递闭包性质得：的传递闭包性质得： e e1 1 He e8 85)e15)e1和和e6e6是并发的：是并发的：e1e1和和e6e6之间无之间无 路径路径 P1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5

15、 5e e8 8e e6 6time144.2 因果关系因果关系n HDAG 有时将有时将Happens-before关系描述为一个有向无环图关系描述为一个有向无环图v顶点集顶点集V VH H是事件集是事件集E E：eVeVH H 当且仅当当且仅当 eeE E v边集边集E EH H：若：若(e(e1 1，e e2 2)E)EH H 当且仅当当且仅当e e1 1 Pe e2 2或或e e1 1 me e2 2 P1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5 5e e8 8e e6 6timee e1 1e e2 2e e4 4e e3 3e e7

16、7e e5 5e e8 8e e6 6154.2.1 Lamport时间戳时间戳n 系统有序性的重要性系统有序性的重要性 若分布式系统中存在全局时钟，则系统中的事件均可若分布式系统中存在全局时钟，则系统中的事件均可安排为全序。例如，可以更公平地分配系统资源。安排为全序。例如，可以更公平地分配系统资源。n 全序对事件的影响和由全序对事件的影响和由H关系确定的偏序对事件的影关系确定的偏序对事件的影响是一致的响是一致的n 如何通过如何通过H关系确定的偏序关系来建立一个关系确定的偏序关系来建立一个“一致一致”的全序关系？的全序关系？v在在 H的的DAGDAG上拓扑排序上拓扑排序 vOn the fly

17、：Lamport提出了动态即时地建立全序提出了动态即时地建立全序算法算法 164.2.1 Lamport时间戳时间戳n Lamport算法的算法的思想思想 每个每个事件事件e有一个附加的时戳：有一个附加的时戳：e.TS 每个每个节点节点有一个局部时戳：有一个局部时戳：my_TS 每个每个msg有一个附加时间戳：有一个附加时间戳：m.TS 节点节点执行执行一个事件时，将自己的时戳赋给该一个事件时，将自己的时戳赋给该事件事件； 节点发送节点发送msg时，将自己的时戳赋给所有时，将自己的时戳赋给所有发送发送的的msg。 174.2.1 Lamport时间戳时间戳n Lamport算法的算法的实现实现

18、 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是发送消息是发送消息m ) then m.TSmy_TS; /给消息给消息m打时戳打时戳184.2.1 Lamport时间戳时间戳nLamport算法赋值的时戳是因果相关的算法赋值的时戳是因果相关的 若若e e1 1 He e2 2，则，则 e e1 1.TS e.TS

19、 e2 2.TS.TS 若若e e1 1 Pe e2 2或或e e1 1 me e2 2，则的，则的e e2 2时戳大于时戳大于e e1 1的时戳的时戳 在因果事件链上，每一事件的时戳大于其前驱事在因果事件链上，每一事件的时戳大于其前驱事件的时戳件的时戳n问题：系统中所有事件已为全序？问题：系统中所有事件已为全序？ 不同的事件可能有相同的时戳（并发事件）不同的事件可能有相同的时戳（并发事件）nLamport算法改进算法改进 因为并发事件的时戳可以任意指定先后因为并发事件的时戳可以任意指定先后 故可用节点地址作为时戳的低位故可用节点地址作为时戳的低位194.2.1 Lamport时间戳时间戳n

20、改进的改进的Lamport时戳时戳 事件标号：时戳事件标号：时戳.id.id 事件事件e8e8为为4.3:4.3: my_TS=max(m.TS,my_TS my_TS=max(m.TS,my_TS) ) =max(3,1)=3 =max(3,1)=3 按字典序得全序：按字典序得全序： 1.1, 1.2, 1.3, 2.1, 2.2, 3.1, 3.2, 4.31.1, 1.2, 1.3, 2.1, 2.2, 3.1, 3.2, 4.3n 算法特点：分布、容错、系统开销小算法特点：分布、容错、系统开销小n Lamport算法的迷人之处在于：任何进程在发送消息前，先将自己的本地算法的迷人之处在于

21、：任何进程在发送消息前，先将自己的本地计数器累加计数器累加1；接收进程总是计算自己的本地计数器和接受到计数器中较大；接收进程总是计算自己的本地计数器和接受到计数器中较大值加上值加上1的结果的结果timeP1P1P2P2P3P3e e1 1e e2 2e e4 4e e3 3e e7 7e e5 5e e8 8e e6 61 1. .2 22 2. .2 23 3. .2 23 3. .1 12 2. .1 11 1. .1 14 4. .3 31 1. .3 3204.2.2 向量时间戳向量时间戳nLamport时戳缺点时戳缺点 若若e e1 1 He e2 2，则，则 e e1 1.TS e

22、.TS e2 2.TS.TS；反之不然。；反之不然。 例如：例如：1.32.11.32.1，但是，但是e e6 6ee4 4不成立不成立 原因：并发事件之间的次序是任意的原因：并发事件之间的次序是任意的 不能通过事件的不能通过事件的时戳判定时戳判定两事件之间是否是两事件之间是否是因果相关因果相关n判定事件间因果关系的重要性判定事件间因果关系的重要性 例子：违反因果关系检测例子：违反因果关系检测 在一个分布式对象系统中，为了负载平衡，对象是可在一个分布式对象系统中，为了负载平衡，对象是可移动的，对象在处理器之间迁移是为了获得所需的调移动的，对象在处理器之间迁移是为了获得所需的调用的进程或资源。如

23、下图：用的进程或资源。如下图： 214.2.2 向量时戳向量时戳1)P1持有对象持有对象O，决定迁移到，决定迁移到P2 为获取资源，为获取资源，P1P1将将O装配在消息装配在消息 M1中发送给中发送给P22)P1收到收到P3访问访问O的请求的请求 P1将将O的新地址的新地址P2放在消息放在消息M2 中通知中通知P33)P3在在M3中请求访问中请求访问P2的的O 当当M3 3达到达到P2P2时，时，O不可用，故不可用，故 回答一个出错消息。回答一个出错消息。n 问题：当问题：当debug该系统时，会发该系统时，会发 现现O已在已在P2上，故不知错在哪？上，故不知错在哪？P1P1P2P2P3P3M

24、1On P2On P2Where Where is is O? ?迁移迁移O到到P2P2I dont knowM2Where Where is is O? ?M3Error!Error!224.2.2 向量时间戳向量时间戳n 错误原因：违反因果序错误原因：违反因果序 P3请求请求O是发生在从是发生在从P1迁移到迁移到P2之后，但该请求被处理是在迁之后，但该请求被处理是在迁移达到移达到P2之前。形式地，之前。形式地， 设：设：s(m)是发送是发送m的事件的事件 r(m)是接收是接收m的事件的事件 若若s(m1)s(m1)H s(m2)s(m2)，则称消息，则称消息m1m1因果关系上先于因果关系上

25、先于m2m2，记做，记做m1m1C m2m2 若若m1 m1 C m2m2，但，但 r(m2) r(m2) P r(m1)r(m1)，则，则违反违反“因果关系因果关系”： 即，若即，若m1m1先于先于m2m2发送，但在发送，但在同一节点同一节点P P上上m2m2在在m1m1之前被接收之前被接收 例如，在上例中有：例如，在上例中有： M1CM3，但，但 r(M3) P2 r(M1)234.2.2 向量时间戳向量时间戳n 违反因果序检测违反因果序检测v定义：定义：若时戳若时戳VT具有比较函数具有比较函数 V满足：满足： e1e1H e2 e2 iff e1.VTe1.VTV e2.VTe2.VT

26、则我们能够检测出是否违反因果关系则我们能够检测出是否违反因果关系vVTVT性质性质 1 1）因）因 H 是偏序，故是偏序，故 V 也是偏序；也是偏序； 2 2）因为必须知道在因果关系上每一节点中哪些事件是在事）因为必须知道在因果关系上每一节点中哪些事件是在事 件件e e之前，故之前，故e.VTe.VT中必须包含系统中每一个其它节点的中必须包含系统中每一个其它节点的 状态。状态。 这两个性质导致了这两个性质导致了向量时戳向量时戳VTVT的引入的引入244.2.2 向量时戳向量时戳n 向量时戳向量时戳VT VT是一个整数数组：是一个整数数组： e.VTi=k表示在节点表示在节点i（或（或 Pi）上

27、，因果关系上）上，因果关系上e之前有之前有k 个事件（可能包括个事件（可能包括e自己）。自己）。 e.VT=(3,6,4,2)表示因果序：表示因果序： 在在P1上，有上，有3个事件须在个事件须在e之前之前 在在P2上，有上，有6个事件须在个事件须在e之前之前 在在P3上，有上，有4个事件须在个事件须在e之前之前 在在P4上，有上，有2个事件须在个事件须在e之前之前P1P1P2P2P3P31 1P4P43 32 25 54 43 31 12 21 15 54 41 16 64 42 23 31 13 32 2e e254.2.2 向量时间戳向量时间戳n 向量时戳的意义向量时戳的意义在因果关系上，

28、在因果关系上，e1.VT e1.VT V e2.VTe2.VT表示表示e2e2发生在发生在 e1e1及及e1e1前所有的前所有的事件之后。事件之后。更精确的说，向量时钟的次序为：更精确的说，向量时钟的次序为： e1.VTe1.VTV e2.VTe2.VT iff e1.VTie1.VTi e2.VTie2.VTi,i=1,2,i=1,2,M,M e1.VT e1.VTV e2.VTe2.VT iff e1.VTe1.VT VTe2.VTe2.VT且且e1.VTe2.VTe1.VTe2.VT n 向量时戳算法向量时戳算法 my_VT：每个节点有局部的向量时戳每个节点有局部的向量时戳 e.VT：每

29、个事件有向量时戳每个事件有向量时戳 m.VT：每个每个msg有向量时戳有向量时戳 节点节点执行执行一个事件时，将自己的时戳赋给该一个事件时，将自己的时戳赋给该事件事件； 节点节点发送发送msg时，将自己的时戳赋给所有时，将自己的时戳赋给所有发送发送的的msg。注意注意V, VT以及以及V之间的区别之间的区别：V代表因果序，代表因果序，而而VT代表时戳比较代表时戳比较264.2.2 向量时间戳向量时间戳n 算法算法实现实现 Initially：my_VT=0,0; On event e： if ( e是消息是消息m的接收者的接收者 ) then for i=1 to M do /向量时戳的每个分

30、量只增不减向量时戳的每个分量只增不减 my_VT i = max( m.VTi, my_VTi ); my_VT self +; /设变量设变量self是本节点的名字是本节点的名字 e.VTmy_VT; /给事件给事件e打时戳打时戳 if ( e是消息是消息m的发送者的发送者 ) then m.VTmy_VT; /给消息给消息m打时戳打时戳274.2.2 向量时间戳向量时间戳n 算法性质算法性质 1）若）若e eH e e，则，则e.VTe.VTVT e e.VT.VT 算法确保对于每个事件满足：算法确保对于每个事件满足： 若若e eP e e或或e em e e ，则，则e.VTe.VTVT

31、 e e.VT.VT 2）若）若e eH e e，则，则e.VTe.VTVT e e.VT.VT pf：若若e e和和e e 因果相关，则有因果相关，则有e eH e e，即，即e e.VT.VTe2.VT1 e1.VT2e2.VT2 e1e1到到e2e2及及e2e2到到e1e1均无路径均无路径 2 2）e3e3在因果序上先于在因果序上先于e1e1 即：即：e3.VTe3.VTV e1.VTe1.VT e1 e1的前驱事件见方框的前驱事件见方框P1P1P2P2P3P310001000P4P43300330023002300541354134400440013001300120012000100

32、010035003500140014000010001036423642014201420120012001320132001100110013001300120012e2e2e3e3e1e1294.2.2 向量时戳向量时戳n 因果序检测因果序检测 1)1)消息时戳间比较消息时戳间比较 在在P2P2上，先到达的上，先到达的M3的时戳为的时戳为 （3,0,3），后到达的），后到达的M1的时戳的时戳 为（为（1,0,0）。但是：）。但是： (1,0,0)V (3,0,3) M1在因果序上先于在因果序上先于M3 故故M1后于后于M3到达违反因果序到达违反因果序 2)2)消息时戳和局部时戳比较消息时戳

33、和局部时戳比较 当当时戳为时戳为(1,0,0) 的的M1到达到达P2 时，时，P2的时戳是的时戳是(3,2,3)。但：。但： (1,0,0)V (3,2,3) M1在因果序上应先于在因果序上应先于(3,2,3)对应的事件对应的事件P1P1P2P2P3P3M1On P2On P2Where Where is is O? ?迁移迁移O到到P2P2I dont knowM2Where Where is is O? ?M3Error!Error!100100201201301301001001302302303303313313323323333333324324304.2.3 因果通信因果通信n 如

34、何保证通信不违反因果如何保证通信不违反因果关系？关系？ 处理器不能选择处理器不能选择msgmsg达到达到的次序，但能的次序，但能抑制抑制过早达过早达到的到的msgmsg来修正传递（指来修正传递（指提交给应用）次序。提交给应用）次序。 n FIFO通信（如通信（如TCP） 由由msg传递协议栈里的一传递协议栈里的一层负责确保层负责确保FIFO通信通信ApplicationFIFO orderingDeliver in FIFO orderMsg passinga s s i g n timestamps314.2.3 因果通信因果通信nFIFO通信通信 源处理器给每个发送的源处理器给每个发送的m

35、sg顺序编号，目的处理器知道自顺序编号，目的处理器知道自己所收到的己所收到的msg应该有何顺序的编号，若目的处理器收到应该有何顺序的编号，若目的处理器收到一个编号为一个编号为x的的msg但未收到较小编号的但未收到较小编号的msg时，则延迟传时，则延迟传递直至能够顺序传递为止。递直至能够顺序传递为止。n因果通信因果通信 因果通信与因果通信与FIFO通信类似通信类似 源：附上时戳源：附上时戳 目的地：延迟错序目的地：延迟错序msgMsg 达到次序达到次序X2deliverx2X5bufferx5X1deliverx1X4bufferx4X3deliverx3x4x5324.2.3 因果通信因果通信n 因果通信实现思想因果通信