时间和全局状态.ppt

《时间和全局状态.ppt》由会员分享，可在线阅读，更多相关《时间和全局状态.ppt（71页珍藏版）》请在三一文库上搜索。

1、第3章 时间和全局状态,第3章 时间和全局状态,简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,简介,如何计时？ 如何同步时钟？ 没有物理时钟能否确定事件的顺序？,简介,时间的重要性 需要精确度量审计电子商务 某些算法依赖于时钟同步数据一致性维护、make 计算全局状态事件排序 时间的复杂性 节点具有独立的物理时钟 精确同步物理时钟非常困难 全局状态的捕获 依赖于逻辑时钟 逻辑时钟与物理时钟无必然联系,第3章 时间和全局状态,简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,时钟、事件和进程状态,假设 每个进程在

2、单处理器上执行 处理器之间不共享内存 进程之间通过消息进行通信 进程状态 所有变量的值 相关的本地操作系统环境中的对象的值 事件 定义：一个通信动作或进程状态转换动作 进程历史：,时钟、事件和进程状态,计算机时钟 晶体具有固定震荡频率 硬件时钟： 软件时钟： 时钟漂移 频率不同 时钟频率随温度变化而有所差别 时钟偏移不可避免,时钟、事件和进程状态,时间分类 天文学时间 -太阳日：两次连续的太阳中天之间的时间间隔 -太阳秒：1/86400个太阳日 国际原子时间(TAI) -基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期 通用协调时间(UTC) -基于原子时间 -采用润秒，与天文时

3、间保持一致,第3章 时间和全局状态,简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,同步物理时钟,外部同步 采用权威的外部时间源 时钟Ci在范围D内是准确的 内部同步 无外部权威时间源,系统内时钟同步 时钟Ci在范围D内是准确的 关系 若P在范围D内外部同步,则P在范围2D内内部同步,同步物理时钟,时钟正确性 基于漂移率 基于单调性 基于混合条件 单调性+漂移率有界+同步点跳跃前进 时钟故障 崩溃故障: 时钟完全停止滴答 随机故障: 其它故障，如“千年虫”问题,同步物理时钟,同步系统中的同步 假设条件 -已知时钟漂移率范围 -存在最大的消息传输延迟 -

4、进程每一步的执行时间已知 方法 若一个进程将时间t发送至另一个进程，且消息传输时间的不确定性为u=maxmin，则 接收进程：t+min，则时钟偏移至多为u t+max，则时钟偏移可能为u t+(max+min)/2，则时钟偏移至多为u/2,同步物理时钟,Cristian方法 应用条件 -存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短 协议 -进程p根据消息mr，mt计算消息往返时间Tround -根据服务器在mt中放置的时间t设置时钟为：t+Tround/2,同步物理时钟,精度分析 若消息的最小传输时间为min，则精度为： (Tround/2 min),同步物

5、理时钟,Berkeley算法 主机周期轮询从属机时间 主机通过消息往返时间估算从属机的时间 与Cristian方法类似 主机计算容错平均值 主机发送每个从属机的调整量,同步物理时钟,网络时间协议(NTP) 设计目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全性强 防止恶意或偶然的干扰,同步物理时钟,协议结构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置,同步物理时钟,同步模式 -组播 适用于高速LAN 准确度较低，但效率高 -过程调用 与Cri

6、stian算法类似 准确度较低 -对称模式 保留时序信息 准确度最高,同步物理时钟,消息交换 若消息m、m的实际传输时间分别为t、t；o为B时钟相对于A时钟的真正偏移， o为偏移估计，则 Ti-2 = Ti-3 + t + o , Ti = Ti-1 + t o 定义 oi=(Ti-2 Ti-3 + Ti-1 Ti)/2,di=t+t=Ti-2 Ti-3+Ti Ti-1 o=oi+(t-t)/2,同步物理时钟,NTP采用过滤离中趋势算法，保留8个最近的，用以估算偏移o NTP采用对等方选择算法，可改变用于同步的对等方 -优先选择层次较低的对等方 -优先选择过滤离中趋势数值较低的对等方,第3章

7、时间和全局状态,简介 时钟、事件和进程状态 物理时钟同步 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,逻辑时间和逻辑时钟,逻辑时间的引入 分布式系统中的物理时钟无法完美同步 -消息传输延时的不确定性 事件排序是众多分布式算法的基石 -互斥算法 -死锁检测算法 缺乏全局时钟 -后发生的事件有可能赋予较早的时间标记,逻辑时间和逻辑时钟,逻辑时钟 众多应用只要求所有节点具有相同时间，该时间不一定与实际时间相同 Lamport(1978)指出：不进行交互的两个进程之间不需要时钟同步 对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。 所有的进程需要在时间的发生顺序上达成一

8、致 如make程序,逻辑时间和逻辑时钟,事件排序 “系统i中的事件a发生在系统j中的事件b之前”是不准确的 -事件发生和观察之间存在时延 -不同系统中的时钟存在偏差 时间戳(Lamport 1978) -用于分布式系统中的事件排序 -与物理时钟无关 -实用高效，应用广泛,逻辑时间和逻辑时钟,两个基本事实 -同一进程中的两个事件存在关系“i” -任一消息的发送事件发生在该消息的接收事件之前 “发生在先(happens-before)” 关系定义 -若存在进程pi满足eie，则ee -对于任一消息m，存在send(m) recv(m) -若事件满足ee 和ee ，则ee 并发关系定义 XY 与 Y

9、X均不成立，则称事件X、Y是并发的，表示为X |Y,逻辑时间和逻辑时钟,事件排序示例 - bc，cd和d f成立 - bf与ef均成立 -事件b和e无法比较，即b|e,逻辑时间和逻辑时钟,Lamport时钟 机制 -进程维护一个单调递增的软件计数器，充当逻辑时钟 -用逻辑时钟为事件添加时间戳 -按事件的时间戳大小为时间排序 逻辑时钟修改规则 -进程pi发出事件前，逻辑时钟Li:=Li+1 -进程pi发送消息m时，在m中添加时间戳t=Li -进程pj在接收(m,t)时，更新Li:=max(Lj,t)+1，给s事 件recv(m)添加时间戳后发送给应用程序,逻辑时间和逻辑时钟,Lamport时钟示

10、例(一) ab L(a)L(b) L(e)L(b) b e,逻辑时间和逻辑时钟,(a) 三个不同速率的时钟 (b) Lamport算法校正时钟,Lamport时钟示例(二),逻辑时间和逻辑时钟,Lamport时钟练习 假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。,逻辑时钟 0,逻辑时间和逻辑时钟,Lamport时钟练习答案,逻辑时钟：0,逻辑时间和逻辑时钟,不同进程产生的消息可能具有相同数值的Lamport时间戳,物理 时间,逻辑时间和逻辑时钟,基于Lamport时间戳的事件排序-总结 算法不依赖于事件发生的真实时间 与真实物理时间中事件的发生顺序可能不一致,基

11、于Lamport时间戳的排序中，在时刻(2,1)发生的事件发生比在时刻（2，2）发生的事件要早，然而在真实物理时间中可能恰好相反。,逻辑时间和逻辑时钟,Lamport时钟不具备性质：若L(A) L(B)则AB 没有捕获事件的因果关系 节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。,我们无法准确确定r的先后关系： C(a) C(r) a r,a 是节点A发布的文章 r 是节点B对文章a的评论,全序逻辑时钟,引入进程标示符创建事件的全序关系 若e、e分别为进程pi、pj中发生的事件，则其全局逻辑时间戳分别为(Ti,i)、(Tj,j)。 ee TiTj | Ti=Tj

12、& ij 系统中各个事件Lamport时间戳均不相同,向量时钟,克服Lamport时钟的缺点：若L(e) L(e)不能推出则ee。 每个进程维护它自己的向量时钟Vi VC1:初始情况下，Vij=0,i,j=1,2,.N. VC2:在pi给事件加时间戳之前，设置Vii= Vii+1。 VC3:pi在它发送的每个消息中包括tVi。 VC4：当pi接收到消息中的时间戳t时，设置Vij=max(Vij,tj),j=1,2,.,N。,向量时钟,Host 1,Host 2,Host 3,Host 4,0,0,0,0,Vector logical clock,Message,(vector timestam

13、p),Physical Time,0,0,0,0,0,0,0,0,0,0,0,0,n,m,p,q,向量时钟,向量时钟,V1 = V2, iff V1i = V2i, i = 1, , n V1 V2, iff V1i V2i, i = 1, , n V1 V2, iff V1 V2 & j (1 j n & V1j V2j) V1 is concurrent with V2 iff not (V1 V2 OR V2 V1),第3章 时间和全局状态,简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,全局状态,观察全局状态的必要性 分布式无用单元的收集 -基

14、于对象的引用计数 -必须考虑信道和进程的状态 分布式死锁检测 观察系统中的“等待”关系图中是否存在循环,分布式终止检测 与进程的状态有关“主动”或“被动” 分布式调试 需要收集同一时刻系统中分布式变量的数值,全局状态,激活,被动的,p1,p2,被动的,全局状态,全局状态和一致割集 观察进程集的状态全局状态非常困难 根源：缺乏全局时间 进程的历史 hi = 进程历史的有限前缀 hi k= 全局历史单个进程历史的并集 H = h1 h2 hN,全局状态,进程状态 sik : 进程pi在第k个事件发生之前的状态 全局状态单个进程状态的集合 S = (s1, s2, sN) 割集系统全局历史的子集 C

15、 = 割集的一致性 割集C是一致的: 对于所有事件eC, f e f C,全局状态,割集示例,全局状态,一致的全局状态对应于一致割集的状态 S0 S1 S2 ,全局状态,走向(run) -全局历史中所有事件的全序 -与每个本地历史顺序一致 -不是所有的走向都经历一致的全局状态,全局状态,线性化走向 -所有的线性化走向只经历一致的全局状态 -若存在一个经过S和S的线性化走向，则状态S是从S可达,全局状态,Chandy和Lamport的“快照”算法 目的 捕获一致的全局状态 假设 - 进程和通道均不会出现故障 - 单向通道，提供FIFO顺序的消息传递 - 进程之间存在全连通关系 - 任一进程可在任

16、一时间开始全局拍照 - 拍照时，进程可继续执行，并发送和接收消息,全局状态,算法基本思想 - 接入通道+外出通道 - 进程状态+通道状态 - 标记消息 标记接收规则：强制进程在记录下自己的状态之后但在它们发送其他消息前发送一个标记。 标记发送规则：强制没有记录状态的进程去记录状态,全局状态,算法伪码(一) 进程pi的标记接收规则 pi接收通道c上的标记消息： if (pi还没有记录它的状态) pi记录它的进程状态； 将c的状态记成空集； 开始记录从其他接入通道上到达的消息 else pi把c的状态记录到从保留它的状态以来它 在c上接收到的消息集合中 end if,全局状态,算法伪码(二) 进程

17、pi的标记发送规则 在pi记录了它的状态之后，对每个外出通道c: (在pi从c上发送任何其他消息前) pi在c上发送一个消息标记,全局状态,算法示例 - 两个进程p1、p2进行交易，每件10$ - 初始状态 进程p2已经收到5件商品的定单，它将马上分发给p1,全局状态,最后状态： P1:; p2:; c1:; c2:,全局状态,算法终止 - 假设：一个进程已经收到了一个标记信息，在有限的时间内记录了它的状态，并在有限的时间里通过每个外出通道发送了标记信息 - 若存在一条从进程pi到进程pj的信道和进程的路径，那么pi记录它的状态之后的有限时间内pj将记录它的状态 - 进程和通道图是强连接的，因

18、此在一些进程记录它的状态之后的有限时间内，所有进程将记录它们的状态和节入通道的状态。,全局状态,算法一致性 ei、ej分别为进程pi、pj中的事件，且ei ej则我们有: 若ej C ei C，其中C为一个割集。即如果ej在pj记录它的状态之前发生，那么ei必须在pi记录它的状态之前发生. 证明思路如下： - i=j时，显然成立 - ij时，反证法,全局状态,全局状态谓词、稳定性、安全性和活性 全局状态谓词 从系统P的进程全局状态集映射到True,False的函数 稳定的谓词 一旦系统进入谓词为True的状态，它将在所有可从该状态可达的状态中一直保持True。如系统死锁、系统终止等状态相关的谓

19、词。 安全性 一个断言，即对所有可从S0到达的所有状态。如a是可以成为死锁的性质，则对于所有可从S0到达的所有状态S，a的值为False。 活性 对于任一从状态S0开始的线性化走向L，对可从S0到达的状态SL，谓词为True。,第3章 时间和全局状态,简介 时钟、事件和进程状态 物理时钟同步 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,分布式调试,目的 对系统实际执行中的暂态作出判断 例子 安全条件检查 xi为进程pi的变量(i=1,2,)，安全条件为|xi-xj| 控制系统 所有阀门在某些时间是否全部处于开启状态,分布式调试,方法 监控器进程 收集进程状态信息 全局状态谓词的判断 -可能

20、的：存在一个一致的全局状态S，H的一个线性化走向经历了这个全局状态S，而且该S使得(s) 为True。 -明确的：对于H的所有线性化走向L，存在L经历的一个一致的全局状态S，而且该S使得(s) 为True。,分布式调试,观察一致的全局状态 进程的状态信息附有向量时钟值 全局状态的一致性判断CGS条件 设S=(s1,s2,sN)是从监控器进程接收到的状态信息中得出的全局状态，V(si)是从pi接收到的状态si的向量时间戳，则S是一致的全局状态当且仅当： V(si)i=V(sj)i (i,j = 1,2, N) 即若一个进程的状态依赖于另一个进程的状态，则全局状态也包含了它所依赖的状态。,分布式调

21、试,全局状态示例,分布式调试,一致全局状态网格,分布式调试,判定可能的 从初始状态考试，遍历可达状态的网格。 L:=0; States:=(s01, s02, , s0N); while (对所有可能的SStates，(s)=False) L:=L+1; Reachable:=S: H中从一些SStates可到达的状态level(S)=L; States:=Reachable; end while 输出“可能的”;,分布式调试,值判定示例,在第层的状态为True明确的 在第层的状态为False可能的,分布式调试,异步系统 开销很大，需要作O(k)次比较。 同步系统 物理时钟：|Ci(t) Cj

22、(t) |D，即在范围D内同步。 同步系统中的算法改进 消息中同时携带物理时间戳和向量时间戳 测试条件 V(si)i V(si)i ，且si和sj能在同一时间发生,第3章 时间和全局状态,简介 时钟、事件和进程状态 物理时钟同步 逻辑时间和逻辑时钟 全局状态 分布式调试 小结,小结,时钟偏移和时钟漂移 物理时钟同步 Cristian方法 Berkeley方法 网络时间协议 逻辑时间 发生在先关系 Lamport时间戳 向量时钟,小结,全局状态 一致割集，一致全局状态 “快照”算法 分布式调试 状态收集 判定可能的和明确的,作业,11.4 11.14 Databases-R-Us runs a

23、cluster of three servers A, B, and C, which communicate with one another. You are told that the current clock skews between server pairs are as follows: A-B: 3 ms; B-C: 1 ms; C-A: -4 ms. Further, you are told that correctness in the database requires that no two server clocks be more than 30ms apart

24、. If each of the servers has an absolute clock drift of 2 ms per minute, how many minimum (i.e., worst-case) minutes can the cluster go without running a synchronization algorithm among its servers?,作业,a, b, and c are events and no two events belong to the same process. Prove or disprove (give counter-example) the following: (a)a is concurrent with b and b is before c implies that a is before c. (b)a is concurrent with b and b is concurrent with c implies that a is concurrent with c.,