分布式系统教学课件DOSCH6Syncv15

1、第6章 分布式同步控制 第1页，共82页。2主要内容6.1 物理时钟同步6.2 逻辑时钟同步6.3 互斥控制6.4 选举算法6.5 *分布式事务管理6.6 *分布式死锁处理6.7 小结6.8 习题第2页，共82页。36.1物理时钟同步分布式协同处理基于时间的同步分布式算法的特点相关信息散布在多个场地上应避免因单点失败造成整个系统的失败不存在公共时钟或精确的全局时间第3页，共82页。4时钟同步问题例：makefile误差时间#脚本命令output.o ： cc C output.c第4页，共82页。5遥远的星系遥远的星系在n天后的日中天，地球旋转不到360物理时钟与现实时钟日中天（transit

2、 of the sun）：太阳升到一天的最高点太阳日：连续的两次日中天的时间太阳年：地球围绕太阳旋转360（一周）。太阳秒：solar-day/24*3600=solar-day/86400平均太阳秒：n solar-days/n*86400如，格林威治时间第0个日中天第n个日中天第5页，共82页。6现实时钟TAI秒：国际原子时间铯133原子钟：9,192,631,770次跃迁/1秒巴黎BIH统计50个实验室原子钟后的平均值UTC秒：世界时间在TAI秒中加入闰秒（TAI秒长度恒定，但比太阳秒短）时间服务：美国WWV电台(NIST)、GEOS卫星1020UTC- 在TAI中引入闰秒，以与太阳秒同

3、步第6页，共82页。7例：时间的应用-GPS全球定位系统GPS卫星使用4个原子时钟周期地广播定位消息即，接收器接收di = c(tnow ti)d =di+ci d = i 时钟误差(1)(2)(3)第7页，共82页。8例：GPS全球定位系统求解方程组（扩展到3维，需4颗卫星）可求出（xr,yr,zr）,以及r误差因素卫星的位置卫星、接收器的时钟精度；信号传播速度第8页，共82页。9时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步设进程P的机器时钟值Cp(t),t 为UTC时间最大偏移率（）精确时钟： dC/dt =1快时钟： dC/dt 1慢时钟： dC/dt 1第9页，共82页。1

4、0时钟同步算法时钟校正设两个时钟都存在误差率，允许两者之间误差；由于最大可能误差2t ，则t /2需每隔/(2)校准时间，进行校正校准原则：单调递增假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。第10页，共82页。11网络时间协议Christian算法时间服务器，可接受WWV的UTC时间每隔/(2)，客户机向服务器询问时间服务器返回CUTC客户机校正自己时间=CUTC+传播时间传播时间=(T1-T0-I)/2T0:请求时间，T1:到达时间I:中断处理时间假定双向路径相同优化处理设定传播阈值,超出阈值，认定无效第11页，共8

5、2页。12网络时间协议时间服务请求过程参数假定双向路径相同T1:A请求时间， T2:B接收时间T3:B发送时间， T4:A接收时间传输延时 = dTreqdTres时间偏差T1=T2 - dTreq + T4=T3+dTres+ 平均延时=(dTreq+dTres)/2 =T4-T3-dTres=T4 -T3 - =时间服务器客户第12页，共82页。13Berkeley 算法 主动式方法时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间第13页，共82页。14平均值算法 非集中式方法划分固定时间间隔R;在每个间隔，所有机器广播自己的时钟时间启动本地计时器收集在S时间间隔中到达的其他

6、机器广播的时间执行平均时间计算算法，得到新的时间值第14页，共82页。15多重外部时间源法消除传播延迟造成的误差例：OSF DCE方法接受所有时间源的当前UTC区间去掉与其他区间不相交的区间将相交部分的中点作为校准时间时间第15页，共82页。16无线网络中的时钟同步参考广播同步协议（RBS）普通的网络延时关键路径RBS的网络延时关键路径第16页，共82页。17无线网络中的时钟同步参考广播同步协议（RBS）一个节点广播一个消息m后，其他节点p记录接收时间Tp,m第17页，共82页。18同步时钟的应用最多一次消息递交每个消息携带一个连接ID和一个时间戳ts服务器的登记表T中，记录每个连接C最近的时

7、间戳t对到达的消息m，如果ts(m)t, 则拒绝m登记表的维护例：服务器中设置全局变量G G = CurrentTime MaxLifetime MaxClockSkew所有G的时间戳从表T中清除对于具有新的ID的到达消息m,如果ts(m)G则拒绝m,否则，接受m按照T，定期地将G写入磁盘。当系统重启后，G=G+T第18页，共82页。19同步时钟的应用基于时钟的缓存一致性当客户读取一个副本到缓存时，设置一个租期（lease）在租期过期之前，客户可更新副本，重续租期如果已经过期，缓存中的副本失效优化策略： 改进的一致性协议当客户修改文件时，只需将所有没有到期的缓存副本设为无效如果某个客户崩溃，则

8、等待，直到该客户的租期过期第19页，共82页。206.2 逻辑时钟同步计时器：石英晶体+计数器时钟偏差（clock skew）物理时钟：真实时间逻辑时钟：相对时间“之前”关系: 事件a在b之前出现，则aba为发送消息m，b为接收m，则ab具有传递性：ab, bc,则ac并发事件（concurrent）两个事件相互对立。既不ab，不 b a第20页，共82页。21Lamport算法C(a)表示事件a的时钟值。性质：if ab;则C(a)C(b)a,b C(a) C(b)C是递增的校正算法ab，if C(b)C(a), 则C(b) = C(a) +1第21页，共82页。22Lamport算法时间慢

9、快慢快三个进程，各有自己的局部时钟，它们速率不同通过Lamport算法，校正时钟第22页，共82页。23Lamport算法Pi在执行一个事件之前，Pi执行CiCi+1Pi在发送消息m给Pj时，时间戳ts(m) CiPj接受到消息m后，CjmaxCj，ts(m)第23页，共82页。24举例：全序多播（1） 问题：两个进程分别对同一个复制数据库进行更新时，造成不一致状态 原因：全局次序不一致。u1u2; u2u1第24页，共82页。25举例：全序多播（2）解决方案：全序多播发送进程多播发送消息m时，给m带上当前时间戳ts当接收进程收到消息m后，存放其局部队列q，并按时间戳排序接收进程向所有进程多播

10、发送应答当消息m被所有进程应答，且排在队列q队首后，方可处理（递交给接收进程，从队列中删除）定理：各个进程的局部队列的值最终都相同第25页，共82页。26举例：全序多播（3）举例q1q2u1u2(1)u1u2u1u2(2）u1u2a11u1u2a22(3)q1q2u1u2a11a22u1u2a11a22(4)u1u2a11a22a12u1u2a11a22a21(5)q1q2u1u2a11a22a12a21u1u2a11a22a12a21(6)a11, a22本地消息a12,a21远地消息第26页，共82页。27向量时钟因果性(causality):如果事件a，b存在因果关系。a为因，b为果，则

11、C(a)C(b)Vector Clock如果VC(a)VC(b)，则a与b为因果关系进程Pi上的向量时钟VCi的基本性质VCii=n, 在Pi中发生了n个事件VCij=k，Pi已知在Pj中发生了k个事件第27页，共82页。28向量时钟(2)向量修改规则Pi在执行一个事件之前，Pi执行VCiiVCii+1当进程Pi发送消息m时,ts(m)=VCi当进程Pj收到m后,置VCjk=maxVCjk,ts(m)kPi的消息m在进程Pk正确递交的条件:ts(m)i = VCki+1tsmjVCkj for all ij第28页，共82页。29有序的消息递交例：A发一个帖子M1,B回一个帖子M2第29页，共

12、82页。30强制因果有序通信第30页，共82页。31强制因果有序通信012345433323675767888888222223111111555555进程0的向量 进程1-5的向量发送消息接收拒绝第31页，共82页。32全局状态（1）*局部状态：进程正在处理的变量值、对象状态等例：分布库系统中的数据库记录全局状态：由每个进程的局部状态和正在传递的消息组成一致性状态：符合逻辑关系-时钟次序例：P Q,如有Q的接收状态，必有P的发送状态m第32页，共82页。33全局状态（2）*分布式快照（snapshot）反映分布式系统的一致性全局状态割集：全局部状态的图形表示(a) 一致性割集 (b) 不一致

13、性割集第33页，共82页。34全局状态（3）*分布式割集的实现通信通道结构：单向的点对点通信输入通道：接收消息输出通道：发出消息标记(Marker)：指示收集状态进程第34页，共82页。35全局状态（4）*算法：发起者进程P向所有输出通道发送marker消息进程 Q第一次收到marker，记录其局部状态，并传递marker（图1）进程 Q记录所有的到来消息（图2）进程Q 再次收到marker后，完成对该输入通道的状态记录（图3）进程Q记录完所有进入通道的状态后，向发起者返回局部状态和通道状态第35页，共82页。36全局状态（5）*举例：终止检测检查一个分布式计算是否结束前趋者：发送marker

14、的进程后继者：接收marker的进程基本算法(递归算法)发起者进程P向所有后继者发送marker请求快照当进程Q完成快照后，向其前趋者返回DONE消息当P收到所有后继者返回DONE消息后，结束第36页，共82页。37全局状态（6）修正算法：不允许有正在传送中的消息，即所有通道必须为空。如果满足以下条件，返回DONE消息给前趋者进程Q的所有后继者都返回DONE消息进程Q在记录局部状态和收到marker之间不再从任何输入通道收到消息否则，返回CONTINUE消息给前趋者发起者进程P接到CONTINUE消息后，继续发起另一个snapshot。第37页，共82页。386.3 互斥算法基本概念当一个进程

15、使用某个共享资源，其他进程不允许对这个资源操作临界区：对共享资源进行操作的程序段基本方法：信号量、管程问题：死锁饥饿第38页，共82页。39集中式算法协调者：确定那个进程可进入临界区通信量：3个消息：请求-许可-释放缺点：单点失败CCC第39页，共82页。40分布式算法（Ricart-Agrawala算法）在一个进程P打算进入临界区R之前，向所有其他进程广播消息 当一个进程P收到消息后，做如下决定：若P不在临界区R中，也不想进入R，它就向P发送OK；若P已经在临界区R中，则不回答，并将P放入请求队列；若P也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果

16、P时间戳小，则向P发送OK;否则，不回答，并将P放入请求队列；当P收到所有的OK消息后，进入R。否则，等待。当P退出R时，如果存在等待队列，则取出一个请求者，向其发送OK消息。第40页，共82页。41分布式算法举例举例： 共有0，1，2三个进程。进程0，2申请进入临界区020022第41页，共82页。42分布式算法评价缺点：n点失败n点瓶颈2（n-1)个消息改进方案：超时重发组通信（进程少且不改变组成员时）简单多数同意（1/2）第42页，共82页。43令牌环算法构造一个逻辑环，得到令牌才可进入临界区问题：令牌丢失检测第43页，共82页。44三种互斥算法的比较算法每次进出需要的消息进入前的延迟（

17、按消息次数）存在问题集中式32协调者崩溃分布式2（n-1）2（n-1）任何一个进程崩溃令牌环1到0到n-1丢失令牌，进程崩溃第44页，共82页。456.4 选举算法作用：在分布式进程之间做出统一的的决定例如：确定协调者前提：每个进程具有唯一的号码，如IP地址每个进程知道其它进程的号码选举标准：确定具有最大号码的进程第45页，共82页。46霸道（Bully）算法将进程进行排序P向高的进程发E消息如果没有响应，P选举获胜如果有进程Q响应,则P结束，Q接管选举并继续下去。456564656第46页，共82页。47环算法所有进程按逻辑或物理次序排序，形成一个环当一个进程P发现协调者C失效后，向后续进程

18、发送E消息每个进程继续向后传递E消息，直到返回PP再将新确定的协调者C传给所有进程52第47页，共82页。48无线网络系统的选举算法例：选举一个协调者，它具有最大的能力1、发起者，提出选举第48页，共82页。49无线网络系统的选举算法2、向邻居节点扩展，形成一个生成树（spanning tree）第49页，共82页。50无线网络系统的选举算法3、沿生成树向父节点返回i，cmax，cmax为最大值4、发起者，向其余节点发布协调者第50页，共82页。51大型系统的选举大型系统中需要选举多个节点如p2p系统中的超级节点对如何选择超级节点（superpeer）的要求:普通节点对超级节点的访问延迟要小超

19、级节点应均匀地分布在覆盖网络中相对于覆盖网络中的节点数量，应有一定数量的预先定义好的超级节点每个超级节点所服务的普通节点个数不能超过规定的数量例：一个小型chord系统m=8(长度), k=3(预留)P AND 11100000作为超级节点的键值N个节点中平均有2k个超级节点第51页，共82页。52大型系统的选举M维空间中的超级节点选举首先，在N个随机选择的节点中，放置N个令牌每个节点不允许拥有一个以上的令牌每个令牌具有排斥力，推动另一个令牌移动通过互相排斥，最终达到在空间中的均匀分布例：使用排斥力在二维空间中移动令牌第52页，共82页。536.5 分布式事务管理*事务原子性： 组成原子事务的

20、一组操作要么全部执行，要么一个也不执行，并且事务失败后能返回到最初状态例1： 老式磁带系统（备份）例2：汇款（提款存款）第53页，共82页。54事务的性质 原子性（Atomic）：对外部世界来说，事务的发生是不可分割的；一致性（Consistent）：事务不会破坏系统的不变式；隔离性（Isolated）：并发的事务之间不会互相干扰；可串行性（Serializable）:多个事务并发执行的结果，与它们顺序地执行效果相同。持久性（Durable）：一旦一个事务提交，它的更新结果不会因故障而丢失。第54页，共82页。55事务模型稳定存储器（Stable Storage）：通过一对双工磁盘实现第55页

21、，共82页。56事务原语（1）BEGIN_TRA NSACTION：标记一个事务的开始；（2）END_TRANSACTION：结束事务并设法提交；（3）ABORT_TRANSACTION：取消事务并恢复旧值；（4） READ：从一个文件（或其他类型的对象，如数据库）读取数据；（5） WRITE：将数据写入一个文件（或其他类型的对象，如数据库）第56页，共82页。57事务举例BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi reserve NairobiMalindi END TRANSACTION BEGIN TRANSACTION rese

22、rve WPJFK reserve JFKNairobi NairobiMalindi fullABORT TRASACTION 当第三个航班的机票预定失败后事务中止预定三个航班机票：中转站是JFK、Nairobi第57页，共82页。58分布式事务嵌套式事务(nested)：由子事务树组成分布式事务：由分布式数据操作组成第58页，共82页。59事务的实现（1） 私有工作空间与影子更新方法当进程启动事务T时，分配一个私有工作空间W，在提交或中止T前所有的读写操作都是在W中进行03影子块第59页，共82页。60事务的实现（1）日志方法：就地更新（in-place）日志纪录事务标识，文件标识，块号，

23、前像，后像例：第60页，共82页。61先写日志协议（WAL）回滚（Rollback）:反做（undo）废弃事务的更新结果只有当日志成功地写入稳存之后，才可以修改文件。如果事务执行成功并被提交，则它的提交记录将被写入日志。如果事务异常中止，则用日志来备份初始状态。从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。在系统崩溃后,日志也可用来进行的恢复。第61页，共82页。62两阶段提交协议（2PC）准备阶段：取得一致决定执行阶段：执行命令（提交或废弃）第62页，共82页。63并发控制(Concurrency Control)正确性标准：可串行性（serializable）B

24、EGIN_TRANSACTION x = 0; x = x + 1;END_TRANSACTION 事务1可能的调度策略BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION事务2BEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION事务3调度1x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3合法调度2x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;合法调度3x = 0; x = 0; x

25、= x + 1; x = 0; x = x + 2; x = x + 3;非法第63页，共82页。64并发控制事务管理系统的结构第64页，共82页。65并发控制分布式事务管理系统的结构第65页，共82页。66基于锁的方法封锁加锁：获得资源上的封锁解锁：释放已拥有的锁封锁的类型和相容性读锁(R)写锁(W)锁的粒度细粒度：如字段粗粒度：如文件RWRW第66页，共82页。67两阶段封锁协议(2PL)两阶段封锁协议(2PL)1. 加锁阶段2. 开锁阶段第67页，共82页。68两阶段封锁协议(2PL)严格的2PL与2PC结合避免级联废弃（cascaded abort)死锁：等待图（WFG）超时检测（ti

26、meout)第68页，共82页。69时间戳法(Timestamp)每个事务的操作带有该事务的时间印ts(T)每个文件带有对它操作的最后一个提交事务的读时间戳tsr(x)、写时间戳tsw(x)算法：如果当前事务T的时间戳文件的时间戳，则执行；否则 ，废弃T;第69页，共82页。70时间戳法举例设有三个事务T1, T2 , T3 , ts(T1)ts(T2)ts(T3)；T1, T3已调度执行，T2请求调度写操作读操作第70页，共82页。71乐观法(Optimistic CC)算法读阶段：将文件读入私有工作区确认阶段：提交前，检查是否有冲突有，则废弃事务，重启。无，则提交事务写阶段：如可以提交，则

27、将修改内容从私有工作区，写入文件。第71页，共82页。72三种方法比较算法并发度死锁性能2PL低有中时间印法较高无较高乐观法高无高（废弃度低时）第72页，共82页。736.6 分布式系统的死锁处理*死锁解决策略鸵鸟法：留给用户考虑检测法：发现死锁，进行处理预防法：在设计上使死锁不可能发生避免法：在运行中，防止出现死锁银行家算法Dijkstra,1965P, free第73页，共82页。74集中式检测方法进程-资源等待图节点：进程P、资源R有向边:(1)PR请求关系; (2) R P拥有关系;死锁检测协调者负责检测死锁资源图的维护策略：当资源图中，有一条边加入/删除时，通知协调者每个进程周期性地向协调者发送图的更新消息协调者在需要时，向参入者请求第74页，共82页。75假死锁问题：B释放R,请求T。若请求T消息先到达协调者解决方案一：协调者确认