分布式系统-时间和全局状态

时间和全局状态时间和全局状态简介时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结简介如何计时？如何同步时钟？没有物理时钟能否确定事件的顺序？简介时间的重要性需要精确度量——审计电子商务某些算法依赖于时钟同步——数据一致性维护、make计算全局状态——事件排序时间的复杂性节点具有独立的物理时钟精确同步物理时钟非常困难全局状态的捕获依赖于逻辑时钟逻辑时钟与物理时钟无必然联系第3章时间和全局状态简介时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结时钟、事件和进程状态假设每个进程在单处理器上执行处理器之间不共享内存进程之间通过消息进行通信进程状态所有变量的值相关的本地操作系统环境中的对象的值事件定义：一个通信动作或进程状态转换动作进程历史：,...,,)(210iiiieeephistory时钟、事件和进程状态计算机时钟晶体具有固定震荡频率硬件时钟：软件时钟：时钟漂移频率不同时钟频率随温度变化而有所差别时钟偏移不可避免)(thi)()(thtCiiNetwork时钟、事件和进程状态时间分类天文学时间-太阳日：两次连续的太阳中天之间的时间间隔-太阳秒：1/86400个太阳日国际原子时间(TAI)-基于铯原子跳跃周期-秒：9192631770次跳跃周期通用协调时间(UTC)-基于原子时间-采用润秒，与天文时间保持一致第3章时间和全局状态简介时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结同步物理时钟外部同步采用权威的外部时间源时钟Ci在范围D内是准确的内部同步无外部权威时间源,系统内时钟同步时钟Ci在范围D内是准确的关系若P在范围D内外部同步,则P在范围2D内内部同步NiDtCtSi,...,2,1,|)()(|NjiDtCtCji,...,2,1,,|)()(|同步物理时钟时钟正确性基于漂移率基于单调性基于混合条件单调性+漂移率有界+同步点跳跃前进时钟故障崩溃故障:时钟完全停止滴答随机故障:其它故障，如“千年虫”问题)')(1()()'()')(1(tttHtHtt)()'('tCtCtt同步物理时钟同步系统中的同步假设条件-已知时钟漂移率范围-存在最大的消息传输延迟-进程每一步的执行时间已知方法若一个进程将时间t发送至另一个进程，且消息传输时间的不确定性为u=max－min，则接收进程：t+min，则时钟偏移至多为ut+max，则时钟偏移可能为ut+(max+min)/2，则时钟偏移至多为u/2同步物理时钟Cristian方法应用条件-存在时间服务器，可与外部时间源同步-消息往返时间与系统所要求的精度相比足够短协议-进程p根据消息mr，mt计算消息往返时间Tround-根据服务器在mt中放置的时间t设置时钟为：t+Tround/2mtp时间服务器Smr同步物理时钟精度分析若消息的最小传输时间为min，则精度为：(Tround/2–min)tt+Tround-mint+Tround/2t+mint+Tround同步物理时钟Berkeley算法主机周期轮询从属机时间主机通过消息往返时间估算从属机的时间与Cristian方法类似主机计算容错平均值主机发送每个从属机的调整量同步物理时钟网络时间协议(NTP)设计目标-可外部同步使得跨Internet的用户能精确地与UTC同步-高可靠性可处理连接丢失，采用冗余服务器、路径等-扩展性好大量用户可经常同步，以抵消漂移率的影响-安全性强防止恶意或偶然的干扰同步物理时钟协议结构-层次结构-主服务器直接与外部UTC同步-同步子网可重新配置123233同步子网结构示例同步物理时钟同步模式-组播适用于高速LAN准确度较低，但效率高-过程调用与Cristian算法类似准确度较低-对称模式保留时序信息准确度最高同步物理时钟消息交换若消息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同步物理时钟NTP采用过滤离中趋势算法，保留8个最近的oi,di，用以估算偏移oNTP采用对等方选择算法，可改变用于同步的对等方-优先选择层次较低的对等方-优先选择过滤离中趋势数值较低的对等方第3章时间和全局状态简介时钟、事件和进程状态物理时钟同步逻辑时间和逻辑时钟全局状态分布式调试小结逻辑时间和逻辑时钟逻辑时间的引入分布式系统中的物理时钟无法完美同步-消息传输延时的不确定性事件排序是众多分布式算法的基石-互斥算法-死锁检测算法缺乏全局时钟-后发生的事件有可能赋予较早的时间标记逻辑时间和逻辑时钟逻辑时钟众多应用只要求所有节点具有相同时间，该时间不一定与实际时间相同Lamport(1978)指出：不进行交互的两个进程之间不需要时钟同步对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。所有的进程需要在时间的发生顺序上达成一致如make程序逻辑时间和逻辑时钟事件排序“系统i中的事件a发生在系统j中的事件b之前”是不准确的-事件发生和观察之间存在时延-不同系统中的时钟存在偏差时间戳(Lamport1978)-用于分布式系统中的事件排序-与物理时钟无关-实用高效，应用广泛逻辑时间和逻辑时钟两个基本事实-同一进程中的两个事件存在关系“i”-任一消息的发送事件发生在该消息的接收事件之前“发生在先(happens-before)”关系定义-若存在进程pi满足eie’，则ee’-对于任一消息m，存在send(m)recv(m)-若事件满足ee’和e’e’’，则ee’’并发关系定义XY与YX均不成立，则称事件X、Y是并发的，表示为X||Y逻辑时间和逻辑时钟事件排序示例-bc，cd和df成立-bf与ef均成立-事件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时钟示例(一)abL(a)L(b)L(e)L(b)be逻辑时间和逻辑时钟(a)三个不同速率的时钟(b)Lamport算法校正时钟Lamport时钟示例(二)逻辑时间和逻辑时钟Lamport时钟练习假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。逻辑时钟0逻辑时间和逻辑时钟Lamport时钟练习答案逻辑时钟：0144328657579逻辑时间和逻辑时钟不同进程产生的消息可能具有相同数值的Lamport时间戳物理时间逻辑时间和逻辑时钟基于Lamport时间戳的事件排序---总结算法不依赖于事件发生的真实时间与真实物理时间中事件的发生顺序可能不一致基于Lamport时间戳的排序中，在时刻(2,1)发生的事件发生比在时刻（2，2）发生的事件要早，然而在真实物理时间中可能恰好相反。逻辑时间和逻辑时钟Lamport时钟不具备性质：若L(A)L(B)则AB没有捕获事件的因果关系节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。araarr我们无法准确确定r的先后关系：C(a)C(r)ara是节点A发布的文章r是节点B对文章a的评论全序逻辑时钟引入进程标示符创建事件的全序关系若e、e’分别为进程pi、pj中发生的事件，则其全局逻辑时间戳分别为(Ti,i)、(Tj,j)。ee’TiTj||Ti=Tj&&ij系统中各个事件Lamport时间戳均不相同向量时钟克服Lamport时钟的缺点：若L(e)L(e’)不能推出则ee’。每个进程维护它自己的向量时钟ViVC1:初始情况下，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。向量时钟abcdefm1m2(2,0,0)(1,0,0)(2,1,0)(2,2,0)(2,2,2)(0,0,1)p1p2p3PhysicaltimeHost1Host2Host3Host40,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向量时钟向量时钟V1=V2,iffV1[i]=V2[i],i=1,…,nV1V2,iffV1[i]V2[i],i=1,…,nV1V2,iffV1V2&j(1jn&V1[j]V2[j])V1isconcurrentwithV2iffnot(V1V2ORV2V1)第3章时间和全局状态简介时钟、事件和进程状态同步物理时钟逻辑时间和逻辑时钟全局状态分布式调试小结全局状态观察全局状态的必要性分布式无用单元的收集-基于对象的引用计数-必须考虑信道和进程的状态分布式死锁检测观察系统中的“等待”关系图中是否存在循环p1消息无用对象对象引用p2等待等待p1p2分布式终止检测与进程的状态有关——“主动”或“被动”分布式调试需要收集同一时刻系统中分布式变量的数值全局状态激活被动的p1p2被动的全局状态全局状态和一致割集观察进程集的状态——全局状态非常困难根源：缺乏全局时间进程的历史hi=ei0,ei1,ei2…进程历史的有限前缀hik=ei0,ei1,…,eik全局历史——单个进程历史的并集H=h1h2…hN全局状态进程状态sik:进程pi在第k个事件发生之前的状态全局状态——单个进程状态的集合S=(s1,s2,…sN)割集——系统全局历史的子集C=h1c1,h2c2…h3c3割集的一致性割集C是一致的:对于所有事件eC,fefC全局状态割集示例m1m2p1p2物理时间e10一致的割集不一致的割集e11e12e13e20e21e22全局状态一致的全局状态——对应于一致割集的状态S0S1S2…走向(run)-全局历史中所有事件的全序-与每个本地历史顺序一致-不是所有的走向都经历一致的全局状态线性化走向-所有的线性化走向只经历一致的全局状态-若存在一个经过S和S’的线性化走向，则状态S’是从S可达全局状态Chandy和Lamport的“快照”算法目的捕获一致的全局状态假设-进程和通道均不会出现故障-单向通道，提供FIFO顺序的消息传递-进程之间存在全连通关系-任一进程可在任一时间开始全局拍照-拍照时，进程可继续执行，并发送和接收消息