时间和全局状态

第3章时间和全局状态第3章时间和全局状态简介

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

-太阳日：两次连续的太阳中天之间的时间间隔

-太阳秒：1/86400个太阳日国际原子时间(TAI)-基于铯原子跳跃周期

-秒：9192631770次跳跃周期通用协调时间(UTC)-基于原子时间

-采用润秒，与天文时间保持一致第3章时间和全局状态简介

时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结时钟、事件和进程状态假设每个进程在单处理器上执行处理器之间不共享内存进程之间通过消息进行通信进程状态所有变量的值相关的本地操作系统环境中的对象的值事件定义：一个通信动作或进程状态转换动作进程历史：时钟、事件和进程状态计算机时钟晶体具有固定震荡频率硬件时钟：软件时钟：时钟漂移频率不同时钟频率随温度变化而有所差别时钟偏移不可避免Infact,theeffectofclockskewisthemainreasonwhyclockoffsetskeepdriftingaway.Novelclockphaseoffset……IEEETransactionsonCommnunications,Vol55,No.4,2007.4第3章时间和全局状态简介

时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结同步物理时钟外部同步采用权威的外部时间源时钟Ci在范围D内是准确的内部同步无外部权威时间源,系统内时钟同步时钟Ci在范围D内是准确的关系

若P在范围D内外部同步,则P在范围2D内内部同步同步物理时时钟Cristian方法(适用于只有有一台机器器有WWV接收器)应用条件-存在时间服服务器，可可与外部时时间源同步步-消息往返时时间与系统统所要求的的精度相比比足够短协议-进程p根据消息mr，mt计算消息往往返时间Tround-根据服务器器在mt中放置的时时间t设置时钟为为：t+Tround/2mtp时间服务器Smr同步物理时时钟Berkeley算法（没有有WWV接收器）主机周期轮询从属机时间间主机通过消消息往返时时间估算从从属机的时时间与Cristian方法类似主机计算容错平均值值主机发送每每个从属机机的调整量同步物理时时钟网络时间协协议(NTP)设计目标-可外部同步步使得跨Internet的用户能精精确地与UTC同步-高可靠性可处理连接接丢失，采采用冗余服服务器、路路径等-扩展性好大量用户可可经常同步步，以抵消消漂移率的的影响-安全性强防止恶意或或偶然的干干扰同步物理时时钟协议结构-层次结构-主服务器直直接与外部部UTC同步-同步子网可可重新配置置123233

同步子网结构示例第3章时间和和全局状态态简介时钟、事件件和进程状状态物理时钟同同步逻辑时间和和逻辑时钟钟全局状态分布式调试试小结逻辑时间和和逻辑时钟钟逻辑时间的的引入分布式系统统中的物理理时钟无法法完美同步步-消息传输延延时的不确确定性事件排序是是众多分布布式算法的的基石-互斥算法-死锁检测算算法缺乏全局时时钟-后发生的事事件有可能能赋予较早早的时间标标记逻辑时间和和逻辑时钟钟逻辑时钟众多应用只只要求所有有节点具有有相同时间，该时间不一定与实实际时间相相同Lamport(1978)指出：不进进行交互的的两个进程程之间不需需要时钟同同步对于不需要要交互的两两个进程而而言，即使使没有时钟钟同步，也也无法察觉觉，更不会会产生问题题。所有的进程程需要在时时间的发生顺序上达成一致如make程序逻辑时间和和逻辑时钟钟事件排序“系统i中的事件a发生在系统统j中的事件b之前”是不不准确的-事件发生和和观察之间间存在时延延-不同系统中中的时钟存存在偏差时间戳(Lamport1978)-用于分布式式系统中的的事件排序序-与物理时钟钟无关-实用高效，，应用广泛泛逻辑时间和和逻辑时钟钟两个基本事事实-同一进程中中的两个事事件存在关关系“i”-任一消息的的发送事件件发生在该该消息的接接收事件之之前“发生在先先(happens-before)””关系定义-若存在进程程pi满足eie’，则ee’-对于任一消消息m，存在send(m)recv(m)-若事件满足足ee’和e’e’’，则ee’’并发关系定定义XY与YX均不成立，，则称事件件X、Y是并发的，，表示为X||Y逻辑时间和和逻辑时钟钟事件排序示示例-bc，cd和df成立-bf与ef均成立-事件b和e无法比较，，即b||ep1p2p3abcdefm1m2物理时间逻辑时间和和逻辑时钟钟Lamport时钟机制-进程维护一一个单调递递增的软件件计数器，，充当逻辑辑时钟-用逻辑时钟钟为事件添添加时间戳戳-按事件的时时间戳大小小为时间排排序逻辑时钟修修改规则-进程pi发出事件前前，逻辑时时钟Li:=Li+1-进程pi发送消息m时，在m中添加时间间戳t=Li-进程pj在接收(m,t)时，更新Li:=max(Lj,t)+1，给s事件件recv(m)添加时间戳戳后发送给给应用程序序abcdefm1m2213451p1p2p3物理时间逻辑时间和和逻辑时钟钟Lamport时钟示例(一)abL(a)<L(b)L(e)<L(b)be逻辑时间和和逻辑时钟钟(a)三个不同速速率的时钟钟(b)Lamport算法校正时时钟Lamport时钟示例(二)逻辑时间和和逻辑时钟钟Lamport时钟练习假设系统中中只存在消消息发送和和接收事件件，如下图图所示，请请给出事件件a-g的逻辑时钟钟。逻辑时钟0逻辑时间和和逻辑时钟钟Lamport时钟练习答案逻辑时钟：：0144328657579逻辑时间间和逻辑辑时钟不同进程产生生的消息息可能具具有相同数值值的Lamport时间戳物理时间逻辑时间间和逻辑辑时钟基于Lamport时间戳的的事件排排序---总结算法不依依赖于事事件发生生的真实实时间与真实物物理时间间中事件件的发生生顺序可可能不一一致基于Lamport时间戳的的排序中中，在时时刻(2,1)发生的事事件发生生比在时时刻（2，2）发生的事事件要早早，然而而在真实实物理时时间中可可能恰好好相反。。逻辑时间间和逻辑辑时钟Lamport时钟不具具备性质质：若L(A)<L(B)则AB没有捕获获事件的的因果关关系节点B发布一篇篇文章并并传送给给节点A和C。节点A就此发表表评论并并传送给给节点B和C。araarr我们无法法准确确确定r的先后关关系：C(a)<C(r)ara是节点A发布的文文章r是节点B对文章a的评论全序逻辑辑时钟引入进程程标示符符创建事事件的全全序关系系若e、e’分别为进进程pi、pj中发生的的事件，，则其全全局逻辑辑时间戳戳分别为为(Ti,i)、(Tj,j)。ee’Ti<Tj||Ti=Tj&&i<j系统中各各个事件件Lamport时间戳均均不相同同向量时钟钟克服Lamport时钟的缺缺点：若L(e)<L(e’)不能推出出则ee’。每个进程程维护它它自己的的向量时时钟ViVC1:初始情况况下，Vi[j]=0,i,j=1,2,...N.VC2:在pi给事件加加时间戳戳之前，，设置Vi[i]=Vi[i]+1。VC3:pi在它发送送的每个个消息中中包括t＝Vi。VC4：当pi接收到消消息中的的时间戳戳t时，设置置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。向量时钟钟Host1Host2Host3Host40,0,0,0VectorlogicalclockMessage(vectortimestamp)PhysicalTime0,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向量时钟钟第3章时间间和全局局状态简介时钟、事事件和进进程状态态同步物理理时钟逻辑时间间和逻辑辑时钟全局状态态分布式调调试小结全局状态态观察全局局状态的的必要性性分布式无无用单元元的收集集-基于对象象的引用用计数-必须考虑虑信道和和进程的的状态分布式死死锁检测测观察系统统中的““等待””关系图图中是否否存在循循环p1消息无用对象对象引用p2等待等待p1p2分布式终终止检测测与进程的的状态有有关——“主动”或“被动”分布式调调试需要收集集同一时时刻系统统中分布布式变量量的数值值全局状态态激活被动的p1p2被动的全局状态态全局状态态和一致致割集观察进程程集的状状态——全局状态态非常困困难根源：缺缺乏全局局时间进程的历历史hi=<ei0,ei1,ei2…>进程历史史的有限限前缀hik=<ei0,ei1,…,eik>全局历史史——单个进程程历史的的并集H=h1h2…hN全局状态进程状态sik:进程pi在第k个事件发生之之前的状态全局状态——单个进程状态态的集合S=(s1,s2,…sN)割集——系统全局历史史的子集C=<h1c1,h2c2…h3c3>割集的一致性性割集C是一致的:对于所有事件件eC,fefC全局状态割集示例m1m2p1p2物理时间e10一致的割集不一致的割集e11e12e13e20e21e22全局状态一致的全局状状态——对应于一致割割集的状态S0S1S2…走向(run)-全局历史中所所有事件的全全序-与每个本地历历史顺序一致致-不是所有的走走向都经历一一致的全局状状态线性化走向-所有的线性化化走向只经历历一致的全局局状态-若存在一个经经过S和S’的线性化走向向，则状态S’是从S可达全局状态Chandy和Lamport的“快照”算算法目的捕获一致的全全局状态假设-进程和通道均均不会出现故故障-单向通道，提提供FIFO顺序的消息传传递-进程之间存在在全连通关系系-任一进程可在在任一时间开开始全局拍照照-拍照时，进程程可继续执行行，并发送和和接收消息全局状态算法基本思想想-接入通道+外出通道-进程状态+通道状态-标记消息标记接收规则则：强制进程在在记录下自己己的状态之后后但在它们发发送其他消息息前发送一个个标记。标记发送规则则：强制没有记记录状态的进进程去记录状状态全局状态算法伪码(一)进程pi的标记接收规规则pi接收通道c上的标记消息息：if(pi还没有记录它它的状态)pi记录它的进程程状态；将c的状态记成空空集；开始记录从其其他接入通道道上到达的消消息elsepi把c的状态记录到到从保留它的的状态以来它它在c上接收到的消消息集合中endif全局状态算法伪码(二)进程pi的标记发送规规则在pi记录了它的状状态之后，对对每个外出通通道c:(在pi从c上发送任何其其他消息前)pi在c上发送一个消消息标记全局状态算法示例-两个进程p1、p2进行交易，每每件10$-初始状态进程p2已经收到5件商品的定单单，它将马上上分发给p1p1p2c2c1帐户窗口部件$1000(none)帐户窗口部件$502000全局状态最后状态：P1:<$1000,0>;p2:<$50,1995>;c1:<(fivewidgets)>;c2:<>p1(空)<$1000,0>1.全局状态S0p1p1p1c2c1(空)2.全局状态S1<$900,0><$900,0><$900,5><$50,1995><$50,1995><$50,2000><$50,2000>3.全局状态S24.全局状态S3p2p2p2p2c2c2c2c1c1c1(定单10，$100)，M(空)(空)(定单10，$100)，M(五个窗口部件)M=标记信息)(定单10，$100)全局局状状态态算法法终终止止-假设设：：一一个个进进程程已已经经收收到到了了一一个个标标记记信信息息，，在在有有限限的的时时间间内内记记录录了了它它的的状状态态，，并并在在有有限限的的时时间间里里通通过过每每个个外外出出通通道道发发送送了了标标记记信信息息．．-若存存在在一一条条从从进进程程pi到进进程程pj的信信道道和和进进程程的的路路径径，，那那么么pi记录录它它的的状状态态之之后后的的有有限限时时间间内内pj将记记录录它它的的状状态态．．-进程程和和通通道道图图是是强强连连接接的的，，因因此此在在一一些些进进程程记记录录它它的的状状态态之之后后的的有有限限时时间间内内，，所所有有进进程程将将记记录录它它们们的的状状态态和和节节入入通通道道的的状状态态。。全局局状状态态算法法一一致致性性ei、ej分别别为为进进程程pi、pj中的的事事件件，，且且eiej则我我们们有有:若ejCeiC，其其中中C为一一个个割割集集。。即即如如果果ej在pj记录录它它的的状状态态之之前前发发生生，，那那么么ei必须须在在pi记录录它它的的状状态态之之前前发发生生.证明明思思路路如如下下：：-i=j时，，显显然然成成立立-i≠≠j时，，反反证证法法第3章时时间间和和全全局局状状态态简介介时钟钟、、事事件件和和进进程程状状态态物理理时时钟钟同同步步逻辑辑时时间间和和逻逻辑辑时时钟钟全局局状状态态分布布式式调调试试小结结分布布式式调调试试目的的对系系统统实实际际执执行行中中的的暂暂态态作作出出判判断断例子子安全全条条件件检检查查xi为进进程程pi的变变量量(i=1,2,…)，安安全全条条件件为为|xi-xj|≤≤控制制系系统统所有有阀阀门门在在某某些些时时间间是是否否全全部部处处于于开开启启状状态态分布布式式调调试试方法法监控控器器进进程程收集集进进程程状状态态信信息息全局局状状态态谓谓词词的的判判断断-可能能的的：存在在一一个个一一致致的的全全局局状状态态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)即若若一一个个进进程程的的状状态态依依赖赖于于另另一一个个进进程程的的状状态态，，则则全全局局状状态态也也包包含含了了它它所所以以来来的的状状态态。。分布布式式调调试试全局局状状态态示示例例m1m2p1p2物理时间

CutC1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100x1=105x2=100x2=95x2=90x1=90CutC2Sij=在进程１发生事件i以及在进程２发生事件j之后的全局状态S00S10S20S21S30S31S32S22S23S33S43层次01234567分布布式式调调试试一致致全全局局状状态态网网格格分布布式式调调试试判定定可可能能的的从初初始始状状态态考考试试，，遍遍历历可可达达状状态态的的网网格格。。L:=0;States:={(s01,s02,……,s0N)};while(对所所有有可可能能的的S∈∈States，(s)=False)L:=L+1;Reachable:={S’’:H中从一一些S∈States可到达达的状状态∧∧level(S’)=L};States:=Reachable;endwhile输出““可能能的”;

?

–层次012345FFFFTFF=((s)=False);T=((s)=True)分布式式调试试值判定定示例例在第５５层的的状态态为True＝》明确的的在第第５层层的状状态为为False＝》可能的的分布式式调试试异步系系统开销很很大，，需要要作O(kＮ)次比较较。同步系系统物理时时钟：：|Ci(t)－Cj(t)|<D，即在在范围围D内同步步。同步系系统中中的算算法改改进消息中中同时时携带带物理理时间间戳和和向量量时间间戳测试条条件V(si)[i]≧≧V(si)[i]，且si和sj能在同同一时时间发发生第3章时时间和和全局局状态态简介时钟、、事件件和进进程状状态物理时时钟同同步逻辑时时间和和逻辑辑时钟钟全局状状态分布式式调试试小结小结时钟偏偏移和和时钟钟漂移移物理时时钟同同步Cristian方法Berkeley方法网络时时间协协议逻辑时时间发生在在先关关系Lamport时间戳戳向量时时钟小结全局状状态一致割割集，，一致致全局局状态态“快照照”算算法分布式式调试试状态收收集判定可可能的的和明确的的作业11.411.14Databases-R-UsrunsaclusterofthreeserversA,B,andC,whichcommunicatewithoneanother.Youaretoldthatthecurrentclockskewsbetweenserverpairsareasfollows:A-B:3ms;B-C:1ms;C-A:-4ms.Further,youaretoldthatcorrectnessinthedatabaserequiresthatnotwoserverclocksbemorethan30msapart.Ifeachoftheservershasanabsoluteclockdriftof2msperminute,howmanyminimum(i.e.,worst-case)minutescantheclustergowithoutrunningasynchronizationalgorithmamongitsservers?作业a,b,andcareeventsandnotwoeventsbelongtothesameprocess.Proveordisprove(givecounter-example)thefollowing:(a)aisconcurrentwithbandbisbeforecimpliesthataisbeforec.(b)aisconcurrentwithbandbisconcurrentwithcimpliesthataisconcurrentwithc.9、静夜四无邻邻，荒居旧业业贫。。1月-231月-23Sunday,January1,202310、雨中中黄叶叶树，，灯下下白头头人。。。13:01:1513:01:1513:011/1/20231:01:15PM11、以我独独沈久，，愧君相相见频。。。1月-2313:01:1513:01Jan-2301-Jan-2312、故人江海别别，几度隔山山川。。13:01:1513:01:1513:01Sunday,January1,202313、乍乍见见翻翻疑疑梦梦，，相相悲悲各各问问年年。。。。1月月-231月月-2313:01:1513:01:15January1,202314、他乡乡生白白发，，旧国国见青青山。。。01一一月月20231:01:15下下午13:01:151月-2315、比不了了得就不不比，得得不到的的就不要要。。。一月231:01下午午1月-2313:01January1,202316、行动出成成果，工作作出财富。。。2023/1/113:01:1513:01:1601January202317、做前，能够够环视四周；；做时，你只只能或者最好好沿着以脚为为起点的射线线向前。。1:01:16下午1:01下下午13:01:161月-239、没有有失败败，只只有暂暂时停停止成成功！！。1月-231月-23Sunday,January1,202310、很多事事情努力力了未必必有结果果，但是是不努力力却什么么改变也也没有。。。13:01:1613:01:1613:011/1/20231:01:16PM11、成功就是是日复一日日那一点点点小小努力力的积累。。。1月-2313:01:1613:01Jan-2301-Jan-2312、世间成事事，不求其其绝对圆满满，留一份份不足，可可得无限完完美。。13:01:1613:01:1613:01Sunday,January1,202313、不知知香积积寺，