时间和全局状态.ppt

第3章 时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结简介简介n如何计时？n如何同步时钟？n没有物理时钟能否确定事件的顺序？简介简介n时间的重要性时间的重要性n需要精确度量审计电子商务n某些算法依赖于时钟同步数据一致性维护、maken计算全局状态事件排序n时间的复杂性时间的复杂性n节点具有独立的物理时钟n精确同步物理时钟非常困难n全局状态的捕获全局状态的捕获n依赖于逻辑时钟n逻辑时钟与物理时钟无必然联系第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结时钟、事件和进程状态时钟、事件和进程状态n假设假设n每个进程在单处理器上执行n处理器之间不共享内存n进程之间通过消息进行通信n进程状态进程状态n所有变量的值n相关的本地操作系统环境中的对象的值n事件事件n定义：一个通信动作或进程状态转换动作n进程历史：时钟、事件和进程状态时钟、事件和进程状态n计算机时钟计算机时钟n晶体具有固定震荡频率n硬件时钟：n软件时钟：n时钟漂移时钟漂移n频率不同n时钟频率随温度变化而有所差别n时钟偏移不可避免时钟偏移不可避免时钟、事件和进程状态时钟、事件和进程状态n时间分类时间分类n天文学时间天文学时间 -太阳日：两次连续的太阳中天之间的时间间隔 -太阳秒：1/86400个太阳日n国际原子时间国际原子时间(TAI)-基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期n通用协调时间通用协调时间(UTC)-基于原子时间 -采用润秒，与天文时间保持一致第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结同步物理时钟同步物理时钟n外部同步外部同步n采用权威的外部时间源n时钟Ci在范围D内是准确的n内部同步内部同步n无外部权威时间源,系统内时钟同步n时钟Ci在范围D内是准确的n关系关系 若P在范围D内外部同步,则P在范围2D内内部同步同步物理时钟同步物理时钟n时钟正确性时钟正确性n基于漂移率n基于单调性n基于混合条件 单调性+漂移率有界+同步点跳跃前进n时钟故障时钟故障n崩溃故障:时钟完全停止滴答n随机故障:其它故障，如“千年虫”问题同步物理时钟同步物理时钟n同步系统中的同步同步系统中的同步n假设条件 -已知时钟漂移率范围 -存在最大的消息传输延迟 -进程每一步的执行时间已知n方法 若一个进程将时间t发送至另一个进程，且消息传输时间的不确定性为u=maxmin，则接收进程：t+min，则时钟偏移至多为u t+max，则时钟偏移可能为u t+(max+min)/2，则时钟偏移至多为u/2同步物理时钟同步物理时钟nCristian方法方法n应用条件应用条件-存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短n协议协议-进程p根据消息mr，mt计算消息往返时间Tround -根据服务器在mt中放置的时间t设置时钟为：t+Tround/2mtp时间服务器Smr同步物理时钟同步物理时钟n精度分析精度分析若消息的最小传输时间为min，则精度为：(Tround/2 min)tt+Tround-mint+Tround/2t+mint+Tround同步物理时钟同步物理时钟nBerkeley算法算法n主机主机周期轮询周期轮询从属机时间从属机时间n主机通过消息往返时间估算从属机的时间主机通过消息往返时间估算从属机的时间与Cristian方法类似n主机计算主机计算容错平均值容错平均值n主机发送每个从属机的主机发送每个从属机的调整量调整量同步物理时钟同步物理时钟n网络时间协议网络时间协议(NTP)n设计目标设计目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全性强 防止恶意或偶然的干扰同步物理时钟同步物理时钟n协议结构协议结构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置123233 同步子网结构示例同步物理时钟同步物理时钟n同步模式同步模式 -组播 适用于高速LAN 准确度较低，但效率高 -过程调用 与Cristian算法类似 准确度较低 -对称模式 保留时序信息 准确度最高同步物理时钟同步物理时钟n消息交换消息交换若消息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)/2TiTi-1Ti-2Ti-3服务器 B服务器 A时间mm时间di=t+t=Ti-2 Ti-3+Ti Ti-1o=oi+(t-t)/2同步物理时钟同步物理时钟nNTP采用过滤离中趋势算法，保留采用过滤离中趋势算法，保留8个最近的个最近的，用以估算偏移用以估算偏移onNTP采用对等方选择算法，可改变用于同步的对等方采用对等方选择算法，可改变用于同步的对等方 -优先选择层次较低的对等方 -优先选择过滤离中趋势数值较低的对等方第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时间的引入逻辑时间的引入n分布式系统中的物理时钟无法完美同步分布式系统中的物理时钟无法完美同步 -消息传输延时的不确定性n事件排序是众多分布式算法的基石事件排序是众多分布式算法的基石 -互斥算法 -死锁检测算法n缺乏全局时钟缺乏全局时钟 -后发生的事件有可能赋予较早的时间标记逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时钟逻辑时钟n众多应用只要求所有节点具有众多应用只要求所有节点具有相同时间相同时间，该时间，该时间不一不一定与实际时间相同定与实际时间相同nLamport(1978)指出：不进行交互的两个进程之间不需指出：不进行交互的两个进程之间不需要时钟同步要时钟同步对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。n所有的进程需要在时间的所有的进程需要在时间的发生顺序发生顺序上上达成一致达成一致 如make程序逻辑时间和逻辑时钟逻辑时间和逻辑时钟n事件排序事件排序n“系统系统i中的事件中的事件a发生在系统发生在系统j中的事件中的事件b之前之前”是不是不准确的准确的 -事件发生和观察之间存在时延 -不同系统中的时钟存在偏差n时间戳时间戳(Lamport 1978)-用于分布式系统中的事件排序 -与物理时钟无关 -实用高效，应用广泛逻辑时间和逻辑时钟逻辑时间和逻辑时钟n两个基本事实两个基本事实 -同一进程中的两个事件存在关系“i”-任一消息的发送事件发生在该消息的接收事件之前n“发生在先发生在先(happens-before)”关系定义关系定义 -若存在进程pi满足eie，则ee -对于任一消息m，存在send(m)recv(m)-若事件满足ee 和ee，则een并发关系定义并发关系定义 XY 与 YX均不成立，则称事件X、Y是并发的，表示为X|Y逻辑时间和逻辑时钟逻辑时间和逻辑时钟n事件排序示例事件排序示例 -bc，cd和d f成立 -bf与ef均成立 -事件b和e无法比较，即b|ep1p2p3abcdefm1m2物理物理时间时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟时钟n机制机制 -进程维护一个单调递增的软件计数器，充当逻辑时钟 -用逻辑时钟为事件添加时间戳 -按事件的时间戳大小为时间排序n逻辑时钟修改规则逻辑时钟修改规则 -进程pi发出事件前，逻辑时钟Li:=Li+1 -进程pi发送消息m时，在m中添加时间戳t=Li -进程pj在接收(m,t)时，更新Li:=max(Lj,t)+1，给s事件recv(m)添加时间戳后发送给应用程序abcdefm1m2213451p1p2p3物理时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟示例时钟示例(一一)ab L(a)L(b)L(e)L(b)b e逻辑时间和逻辑时钟逻辑时间和逻辑时钟 (a)三个不同速率的时钟三个不同速率的时钟 (b)Lamport算法校正时钟算法校正时钟n Lamport时钟示例时钟示例(二二)逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟练习时钟练习假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。逻辑时钟 0逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟练习时钟练习答案答案逻辑时钟：0144328657579逻辑时间和逻辑时钟逻辑时间和逻辑时钟n不同不同进程产生的消息可能具有进程产生的消息可能具有相同数值相同数值的的Lamport时间戳时间戳物理物理时间时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟n基于基于Lamport时间戳的事件排序时间戳的事件排序-总结总结n算法不依赖于事件发生的真实时间算法不依赖于事件发生的真实时间n与真实物理时间中事件的发生顺序可能不一致与真实物理时间中事件的发生顺序可能不一致基于基于Lamport时间戳的排序中，在时刻时间戳的排序中，在时刻(2,1)发生的事件发生比在时发生的事件发生比在时刻刻（2，2）发生的事件要早，然而在真实物理时间中可能恰好相反。发生的事件要早，然而在真实物理时间中可能恰好相反。逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟不具备性质：若时钟不具备性质：若L(A)L(B)则则ABn没有捕获事件的因果关系没有捕获事件的因果关系节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。araarr我们无法准确确定我们无法准确确定r的先后关系：的先后关系：C(a)C(r)a ra 是节点是节点A发布的文章发布的文章r 是节点是节点B对文章对文章a的评论的评论 全序逻辑时钟全序逻辑时钟n引入进程标示符创建事件的全序关系引入进程标示符创建事件的全序关系n若若e、e分别为进程分别为进程pi、pj中发生的事件，则其全局中发生的事件，则其全局逻辑时间戳分别为逻辑时间戳分别为(Ti,i)、(Tj,j)。nee TiTj|Ti=Tj&ijn系统中各个事件系统中各个事件Lamport时间戳均不相同时间戳均不相同向量时钟向量时钟n克服Lamport时钟的缺点：若L(e)L(e)不能推出则ee。n每个进程维护它自己的向量时钟VinVC1:初始情况下，Vij=0,i,j=1,2,.N.nVC2:在pi给事件加时间戳之前，设置Vii=Vii+1。nVC3:pi在它发送的每个消息中包括tVi。nVC4：当pi接收到消息中的时间戳t时，设置Vij=max(Vij,tj),j=1,2,.,N。向量时钟向量时钟 Host 1Host 2Host 3Host 40,0,0,0Vector logical clockMessage(vector timestamp)Physical Time0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量时钟向量时钟向量时钟向量时钟n V1=V2,iff V1i=V2i,i=1,nn V1 V2,iff V1i V2i,i=1,nn V1 V2,iff V1 V2&j(1 j n&V1j V2j)n V1 is concurrent with V2iff not(V1 V2 OR V2 V1)第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结全局状态全局状态n观察全局状态的必要性观察全局状态的必要性n分布式无用单元的收集分布式无用单元的收集 -基于对象的引用计数 -必须考虑信道和进程的状态n分布式死锁检测分布式死锁检测 观察系统中的“等待”关系图中是否存在循环p1消息无用对象对象引用p2等待等待p1p2n分布式终止检测分布式终止检测 与进程的状态有关“主动”或“被动”n分布式调试分布式调试 需要收集同一时刻系统中分布式变量的数值全局状态全局状态激活被动的p1p2被动的全局状态全局状态n全局状态和一致割集全局状态和一致割集n观察进程集的状态观察进程集的状态全局状态非常困难全局状态非常困难根源：缺乏全局时间n进程的历史进程的历史hi=n进程历史的有限前缀进程历史的有限前缀hi k=n全局历史全局历史单个进程历史的并集单个进程历史的并集H=h1 h2 hN全局状态全局状态n进程状态进程状态 sik:进程pi在第k个事件发生之前的状态n全局状态全局状态单个进程状态的集合单个进程状态的集合S=(s1,s2,sN)n割集割集系统全局历史的子集系统全局历史的子集C=n割集的一致性割集的一致性割集C是一致的:对于所有事件eC,f e f C全局状态全局状态n割集示例割集示例m1m2p1p2物理时间物理时间e10一致的割集不一致的割集e11e12e13e20e21e22全局状态全局状态n一致的全局状态一致的全局状态对应于一致割集的状态对应于一致割集的状态S0 S1 S2 全局状态全局状态n走向走向(run)-全局历史中所有事件的全序 -与每个本地历史顺序一致 -不是所有的走向都经历一致的全局状态不是所有的走向都经历一致的全局状态全局状态全局状态n线性化走向线性化走向 -所有的线性化走向只经历一致的全局状态所有的线性化走向只经历一致的全局状态 -若存在一个经过S和S的线性化走向，则状态S是从S可达全局状态全局状态nChandy和和Lamport的的“快照快照”算法算法n目的目的捕获一致的全局状态n假设假设 -进程和通道均不会出现故障 -单向通道，提供FIFO顺序的消息传递 -进程之间存在全连通关系 -任一进程可在任一时间开始全局拍照 -拍照时，进程可继续执行，并发送和接收消息全局状态全局状态n算法基本思想算法基本思想 -接入通道+外出通道 -进程状态+通道状态 -标记消息 标记接收规则：强制进程在记录下自己的状态之后但在它们发送其他消息前发送一个标记。标记发送规则：强制没有记录状态的进程去记录状态全局状态全局状态n算法伪码算法伪码(一一)进程pi的标记接收规则 pi接收通道c上的标记消息：if(pi还没有记录它的状态)pi记录它的进程状态；将c的状态记成空集；开始记录从其他接入通道上到达的消息 else pi把c的状态记录到从保留它的状态以来它 在c上接收到的消息集合中 end if全局状态全局状态n算法伪码算法伪码(二二)进程pi的标记发送规则 在pi记录了它的状态之后，对每个外出通道c:(在pi从c上发送任何其他消息前)pi在c上发送一个消息标记全局状态全局状态n算法示例算法示例 -两个进程p1、p2进行交易，每件10$-初始状态 进程p2已经收到5件商品的定单，它将马上分发给p1 p1p2c2c1帐户窗口部件$1000(none)帐户窗口部件$502000全局状态全局状态最后状最后状态态：P1:;p2:;c1:;c2:p1(空)1.全局状态 S0p1p1p1c2c1(空)2.全局状态 S13.全局状态 S24.全局状态 S3p2p2p2p2c2c2c2c1c1c1(定单10，$100)，M(空)(空)(定单10，$100)，M(五个窗口部件)M=标记信息)(定单10，$100)全局状态全局状态n算法终止算法终止 -假设：一个进程已经收到了一个标记信息，在有限的时间内记录了它的状态，并在有限的时间里通过每个外出通道发送了标记信息-若存在一条从进程pi到进程pj的信道和进程的路径，那么pi记录它的状态之后的有限时间内pj将记录它的状态-进程和通道图是强连接的，因此在一些进程记录它的状态之后的有限时间内，所有进程将记录它们的状态和节入通道的状态。全局状态全局状态n算法一致性算法一致性 ei、ej分别为进程pi、pj中的事件，且ei ej则我们有:若ej C ei C，其中C为一个割集。即如果ej在pj记录它的状态之前发生，那么ei必须在pi记录它的状态之前发生.证明思路如下：-i=j时，显然成立 -ij时，反证法全局状态全局状态n全局状态谓词、稳定性、安全性和活性全局状态谓词、稳定性、安全性和活性n全局状态谓词全局状态谓词 从系统P的进程全局状态集映射到True,False的函数n稳定的谓词稳定的谓词 一旦系统进入谓词为True的状态，它将在所有可从该状态可达的状态中一直保持True。如系统死锁、系统终止等状态相关的谓词。n安全性安全性 一个断言，即对所有可从S0到达的所有状态。如a是可以成为死锁的性质，则对于所有可从S0到达的所有状态S，a的值为False。n活性活性 对于任一从状态S0开始的线性化走向L，对可从S0到达的状态SL，谓词为True。第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结分布式调试分布式调试n目的目的对系统实际执行中的暂态作出判断n例子例子n安全条件检查 xi为进程pi的变量(i=1,2,)，安全条件为|xi-xj|n控制系统所有阀门在某些时间是否全部处于开启状态分布式调试分布式调试n方法方法n监控器进程收集进程状态信息n全局状态谓词的判断 -可能的：存在一个一致的全局状态S，H的一个线性化走向经历了这个全局状态S，而且该S使得(s)为True。-明确的：对于H的所有线性化走向L，存在L经历的一个一致的全局状态S，而且该S使得(s)为True。分布式调试分布式调试n观察一致的全局状态观察一致的全局状态n进程的状态信息附有向量时钟值n全局状态的一致性判断CGS条件 设S=(s1,s2,sN)是从监控器进程接收到的状态信息中得出的全局状态，V(si)是从pi接收到的状态si的向量时间戳，则S是一致的全局状态当且仅当：V(si)i=V(sj)i(i,j=1,2,N)即若一个进程的状态依赖于另一个进程的状态，则全局状态也包含了它所依赖的状态。分布式调试分布式调试n全局状态示例m1m2p1p2物理时间 Cut C1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100 x1=105x2=100 x2=95x2=90 x1=90Cut C2Sij=在进程发生事件i以及在进程发生事件j之后的全局状态S00S10S20S21S30S31S32S22S23S33S43层次 01234567分布式调试分布式调试n一致全局状态网格分布式调试分布式调试n判定可能的判定可能的 从初始状态考试，遍历可达状态的网格。L:=0;States:=(s01,s02,s0N);while(对所有可能的SStates，(s)=False)L:=L+1;Reachable:=S:H中从一些SStates可到达的状态level(S)=L;States:=Reachable;end while输出“可能的”;?层次 012345FFFFTFF=(s)=False);T=(s)=True)分布式调试分布式调试n值判定示例 在第层的状态为True明确的在第层的状态为False可能的分布式调试分布式调试n异步系统异步系统开销很大，需要作O(k)次比较。n同步系统同步系统物理时钟：|Ci(t)Cj(t)|D，即在范围D内同步。n同步系统中的算法改进同步系统中的算法改进n消息中同时携带物理时间戳和向量时间戳n测试条件 V(si)i V(si)i，且si和sj能在同一时间发生第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结小结小结n时钟偏移和时钟漂移时钟偏移和时钟漂移n物理时钟同步物理时钟同步nCristian方法nBerkeley方法n网络时间协议n逻辑时间逻辑时间n发生在先关系nLamport时间戳n向量时钟小结小结n全局状态全局状态n一致割集，一致全局状态n“快照”算法n分布式调试分布式调试n状态收集n判定可能的和明确的作业1.11.42.11.143.Databases-R-Us runs a 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.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?作业4.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.