（计算机软件与理论专业论文）基于失效检测器的异步系统共识协议研究.pdf

基于失效检测器的异步系统共识协议研究 摘要 设计和实施具有容错功能的分布式应用是一项复杂的任务。分布式应用对一 致性的普遍要求使共识问题和原子广播问题成为研究的关键所在，因为它们可以 用来解决许多在实践中出现的问题，例如选举领导者或者需要对复制的数据达成 一致时都涉及到共识问题，原子广播可以保证进程传递消息的一致性和次序性。 比较不同的系统模型，尽管异步系统比同步系统具有更强的实用性，但f l p 理论 证明在异步系统中，如果允许出现崩溃进程，那么上述两种问题不具有确定解， 这使共识问题成为具体设计中的一道障碍。针对共识问题人们做了大量的研究， 归纳起来异步系统下共识问题的解决途径大致有两秘，一种是基于随机数字指示 器的方法，另外一种是基于失效检测器的方法。本文的研究内容就是基于失效检 测器的共识协议。 本文首先详细描述了失效检测器的定义和分类，然后对失效检测器的设计方 法和性能检测标准做了介绍。分析了几种典型的基于失效检测器的共识协议，包 括四阶段的c t 协议、p a x o s 协议和两阶段的1 r 协议、p r 协议。在n e k o 实验平台 上完成了对失效检测器和协议的具体设计。原子广播可以利用共识协议来实现， 本文测试了在几种不同的故障负载下利用各种协议设计的原子广播在相同吞吐量 下的延时数据，结合实验结果对协议进行了评估。 本文对基于失效检测器的共识协议进行了改进，根据局域网内消息传递的自 发性原则，提出了把参与共识的进程分为提议进程和参与进程两组，并在协议的 第一阶段提议进程消息广播的方法。经实验证明，改进后的共识协议能够在提议 进程提出值相同的条件下，进程只经过一次通信就完成共识，提高了共识的效率。 本文描述了失效检测器和共识协议的自适应性研究方向，提出了由领导进程 动态组织组内进程成员的方法，根据系统进程之间的消息往返延时，让当前运行 速度较快的进程在共识协议的执行过程中处于主导位置，这种方法可以在系统部 分进程运行缓慢或者发生崩溃的情况发生时不影响到系统效率。 关键字：软件容错；异步系统；失效检测器；共识协议 u a b s t r a c t t h ed e s i g na n di m p l e m e n to ff a u l t t o l e r a n td i s t r i b u t e da p p l i c a t i o n si sw i d e l y v i e w e da sac o m p l e xe n d e a v o r r e q u i r i n gc o n s i s t e n c yo fd i s t r i b u t e da p p “c a t i o n s m a k ec o n s e n s u sa n da t o m i cb r o a d c a s t b e c o m ek e yp r o b l e m si nr e s e a r c h i np r a c t i c e ， c o n s e n s u sc a nb eu s e dt oe l e c tal e a d e ro ra g r e eo nt h ev a l u eo far e p l i c a t ed a t a a t o m i cb r o a d c a s ta l l o w sp r o c e s s e st oa g r e eo nt h es e to fm e s s a g e st h e yd e l i v e ra n d t h eo r d e ro fb r o a d c a s tm e s s a g e s c o n s i d e r i n gd i f f e r e n ts y s t e mm o d e l s ，a l t h o u 曲t h e a s y n c h r o n o u sm o d e li sm o r ea t t r a c t i v et h a ns y n c l l r o n o u sm o d e l ，f l pm e o r yp m v e s t h a tc o n s e n s u sa n da t o m i cb r o a d c a s tc a n n o tb e s o l v e dd e t e r m i n i s t i c a l l yi n a n a s y n c h r o n o u ss y s t e mi nw h i c hp r o c e s s e sm a yc r a s h c o n s e n s u si s c o n s i d e r e da sa b u i l d i n gb l o c kf o rd i s t r i b u t e ds y s t e m s m a n yr e s e a r c h e sh a v ed o n et oc i r c u m v e n tt h i s i m p o s s i b i l i t y t h e r ea r et 、v om a i na p p r o a c h e s ，t h ef i r s to n e u s e sr a n d o mo r a c l e sa n d t h es e c o n da p p r o a c hi sb a s e do ne q u i p p i n gt l cp u r e l ya s y n c h r o n o u ss y s t e mw i t h u n r e l i a b l ef a i l u r ed e t e c t i o no r a c l e s t h i sp a p e rm a i n l ys t u d i e st h es e c o n da p p m a c h f i r s t l yi t i n t r o d u c e sd e f i n i t i o na n dc l a s s i n c a t i o no ft h ef a i l u r cd e t e c t o r sa i l d d e s c r i b e st h em e t h o dt oi m p l e m e n taf a i l u r ed e t e c t o lt h e na n a l y z e st h eq u a l i t yo f s e r v i c eo ft h ef a i l l l r ed e t e c t o r ，t h i sp a p e ra n a l y z e ss e v e r a lk i n d so ft y p i c a lc o n s e n s u s p r o t o c 0 1b a s e do nt h ef h i l u r ed e t e c t o lt h ep r o t o c o l si n c l u d i n gc tp r o t o c o l ，p a x o s p r o t o c o l ，m rp r o t o c o la n dp rp r o t o c 0 1 w eu s et h en e k of r 锄e w o r kt od e s i g nm e f a i l u r ed e t e c t o ra i l dt h ep r o t o c 0 1 t h ea t o m i cb r o a d c a s tc a nb ea c h i e v e db yc o n s e n s u s ， s ot 1 1 ep e r f o r m a n c em e t r i co fc o n s e n s u si sm el a t e n c yo fa t o m i cb r o a d c a s tw i t ht h e s a n l et h r o u g h p u t w em e a s u r ei tw i t hs e v e r a ld i 玎e r c n tf a u l t l o a d s i ns u c c e s s i o n ，t h i sp a p e ri n l p r o v e st h ec o n s e n s u sp r o t o c o lb a s e do nt h ef a i l u r e d e t e c t o r st h r o u 曲t h ep r o p e n yo fs p o n t a n e o u st o t a lo r d e ri nl o c a l a r e an e t w o r k s ，t h e p r o c e s si sd i v i d e di n t ot w op a r t s ：t h ep a n i c i p a n ta n dt h ep r o p o s e r a n dt h ep r o p o s e r s b r o a d c a s tm e s s a g e si nt h e 矗r s tp h a s e t h r o u g he x p e r i m e n t s ，m ei m p m v e dc o n s e n s u s p r o t o c o lc a nr c a c had e c i s i o nw i t ho n ec o m m u n i c a t i o ns t e pi ft h ep r o p o s e r sh a v et h e s a l l l ev a l u e b yt h i sw a y ，i tc a ne n h a n c et h ee m c i e n c yo fc o n s e n s u sp r o t o c 0 1 a tl a s t ，t h i sp a p e ri m r o d u c e st h ea d a p t i v ef h i l u r ed e t e c t o ra n dc o n s e n s u sp r o t o c 0 1 b r i n g sf o r w a r dt h em e t h o do fa d j u s t i n gt h em e m b e r s h i pi nt h eg r o u pb yt h ei e a d e r p r o c e s sb a s e do nt h er o u n d - t r i pd e l a ym a t r i x m a k et h o s e “f a s t ”p r o c e s s e sp l a yak e y r 0 1 ed u r i n gt h ee x e c u t i o no ft h ec o n s e n s u sp r o t o c o l s t h i sm e t h o dc a i ld e a lw i t ht h e c r a s ho rr u n n i n gs l o w l yo fp r o c e s s e si nt h es y s t e m i i i 基于失效检测器的异步系统共识协议研究 k e yw o r d s ： s o f t w a r ef a u l t t o l e r a n t ； a s y n c h r o n o u ss y s t e m ； f a i l u r ed e t e c t o r ； c o n s e n s u sp r o t o c o l s i v 硕t 学位论文 插图索引 图3 1 失效检测器设计的p u s h 方法 图3 2 失效检测器设计的p u l l 方法 图3 3 基于询问回答式的失效检测器设计方法一 图3 4 失效检测器的检测时间( 进程q 检测进程p ) 图3 5 失效检测器错误重现时间( 进程q 检测进程p ) 图4 1 基于轮转协调者的c t 协议一 图4 2p a x o s 协议 图4 _ 3p a x o s 协议良好运行的一个例子( 进程p l 为l e a d e r 进程) 图4 4 消息传递模型 图5 1 消息传递的自发性 图5 2 改进后协议运行的一个具体实例 图5 3p r 协议和改进后协议的执行时间对比 图5 4m r 协议和改进后协议的执行时间对比( 五= 1 ) 图5 5m r 协议和改进后协议的执行时间对比( 五= o 1 ) 图6 1 基于失效检测器的共识协议模型化视图 图6 2 基于失效检测器的自适应性共识协议模型化视图 图6 3 领导进程动态调整组内成员 v i i 1 3 1 4 1 4 1 5 1 5 2 1 2 2 2 3 2 8 3 3 3 7 一3 8 3 9 4 0 4 2 4 3 4 6 附表索引 表3 1 四种类型的失效检测器 表3 2 通信量开销最小的设计方法 表3 3 失效检测器不同的设计方法对比 表4 1m r 协议的伪代码 表4 2 共识协议统一框架的伪代码 表4 3 在正常稳定状态下三种协议的延时对比 表4 4 非协调者进程发生崩溃时三种协议延时对比 表4 5 协调者进程发生崩溃三种协议延时对比 表4 6 多个进程同时发生崩溃时三种协议延时数据对比 表5 1p r 和pr 协议执行时间对比实验一 表5 2p r 和p r 协议执行时间对比实验二 表5 3m r 和m r 执行时间对比实验一 表5 4m r 和m r 执行时间对比实验二 表5 5m r 和m r 执行时间对比实验三 表5 6m r 和m r 执行时间对比实验四 v l i i 1 2 1 6 1 8 2 4 2 6 2 9 3 0 如”勰弛”如加柏 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：王 冈j 日期：嘶6 月二上日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 王刚日期：j 凸幽萨f 5 月土日 日期：a 。乒r 月v 乙月d 岫d 1 1概述 第1 章绪论 随着分布式计算的发展，分布式系统的可靠性变得越来越重要。可靠性的重 要内容是故障的检测和处理。分布式系统跨越不同站点主机上的操作系统平台， 由分布在不同结点主机上的软件交互协同工作完成任务。设计具有容错功能的分 布式应用是非常复杂的一项任务。 基于消息传递的分布式系统如果在硬件或软件故障情况下，仍能满足性能要 求和服务质量要求，则认为该系统具有容错特性。系统冗余是实现容错的基本策 略，冗余可分为基于空间的冗余和基于时间的冗余。在消息传递系统中进行容错 时，一项重要的措施就是使用检查点回卷恢复技术，另外一种是使用复制技术。 检查点回卷恢复技术【l 】指的是定期将一个正在执行程序的状态存储在存储 器内，以便在故障后系统可以从该状态恢复。每个被保存的程序状态称为检查点。 从以前保存的状态重新开始的过程，称为回卷恢复。在基于消息传递的系统中， 从故障中进行回卷恢复的技术可以分为两个主要的类别：基于检查点的回卷恢复 方法和基于消息日志的回卷恢复方法。基于检查点的回卷恢复又分为协同检查点 方法和通信诱导检查点方法；基于消息日志的回卷恢复分为悲观的消息日志方法 和乐观的消息日志方法。协同检查点方法在做检查点时，所有进程需要同步，所 做的检查点是全局一致可恢复的。而通信诱导检查点方法中，进程做检查点时则 不需要同步，各个进程可以独立地做检查点。在出现故障时，需要收集各个进程 记录的依赖关系，以便计算出全局一致性恢复线，然后各个进程回卷到全局一致 恢复线状态。悲观消息日志就是消息的记录与消息的处理是同步进行的，保证消 息在处理之前己经被记录到固定存储器中，而乐观消息日志消息的处理和消息的 记录是异步进行的。 在复制方法中，一个进程可能同时拥有几个副本，所有副本同时执行相同的 计算，这样的话，在一个副本出现错误的情况下，不会对其他组件的执行带来影 响。当错误发生时，计算可以继续执行，除非发生错误的副本超过了规定的范围。 相关的复制协议也较多，按照参与复制的进程的主动性区分，大致有主动复制 ( a c t i v er c p l i c 砒i o n ) 【2 1 、被动复制( p a s s i v er e p l i c a t i o n ) 【3 】以及在此基础上的半主动复 制( s e m i 吨c t i v er e p l i c a t i o n ) 和半被动复制( s e m i p a s s i v er e p l i c a t i o n ) 4 1 几种，主动复 制技术给予所有的复制品赋予了相同的地位，没有中心控制点。所有的复制品以 基于失效检测器的异步系统共识协议研究 相同的次序执行同一个操作，同时处理客户的请求并将结果反馈给客户。主动复 制协议正因为没有中心控制点，那么就必须保证所有的副本进行的是同样的操作， 要求参与主动复制的所有进程处理客户的请求次序必须是相同的，保证发送给所 有目的地的消息要按照统一的次序传递给上层应用程序，在这一点上往往需要调 用组通信原语原子广播( a t o m i cb m a d c a s t ) 【5 l ；被动复制只有一个主副本执行操作， 负责处理客户的请求，并随之更新其他所有副本的内容。被动复制不需要所有的 副本同时参与运行，要求的处理能力小于主动复制，但是一旦被动复制的主副本 发生崩溃，重新选举一个新的主副本往往带来很大的时间开销。 一致性问题是分布式系统的基础问题【6 l ，有很多种不同类型的一致性问题， 不过它们都有一个特征：参与进程需要达成一个共同的决定。主动复制中需要调 用的组通讯原语原子广播和本文所研究的共识问题就是对于实现具有容错能力的 分布式系统的一个最基本的抽象。事实上原子广播和共识问题是等价的【7 1 ，也就 是说，能够解决其中一种问题的方法同样可以用来解决另外一种问题，而这两种 问题在异步系统并且允许进程出现崩溃的条件下的不可解性8 1 ，使得它们成为设 计具有容错功能的分布式系统的一个障碍，因此也成为了分布式容错研究的一个 热点。下面详细介绍原子广播问题和共识问题，并证明它们的等价性。 原子广播：原子广播也被称为全序广播( 9 。原子广播能确保将消息发送到一 组站点，且保证各站点传递消息的一致性及次序性。为了实现传递消息的次序， 一个站点所接收的消息，不能立即传递给应用程序，而必须被延时直到它们可以 按照相同次序被传递。这里需要指出的是接收消息( r e c e i v i n g ) 和传递消息 ( d e l i v e r y ) 的意义是不同的。接收消息是指组通信层从网络底层接收到数据包，而 消息传递( m e s s a g ed e l i v e r y ) ，指的是向上层应用进程传递信息。 原子广播可分为两个原语，a b r o a d c a s t 原语和a d e l i v e r 原语。原子广播是 一种特殊的可靠广播，它除了具有可靠广播所有的属性以外，还需要满足： 全序性( t 0 t a lo r d e r ) ：如果两个正确进程p 和q 都传递消息m 和m ，那么p 传递m 在传递m 。之前，当且仅当进程q 传递m 在传递m 之前。 共识闯题：共识问题是另一个常见的分布式容错计算的基础问题。例如在一 个数据复制系统中，对相同的复制数据要求进行相同次序的操作；在一个传感器 复制系统中，对传感器的值达成一致；在同步系统中，对时钟进行同步；在消息 广播系统中，以相同的次序传输消息；在数据库系统中，对一个事务进行提交或 中止操作等等，复制容错中的半被动复制是基于s 类失效检测器和懒惰共识 ( 1 a z yc o n s e n s u s ) 协议来进行选举主副本和更新其余副本内容的。共识问题是对一 致性问题的本质归纳，在消息传递系统中，任何复制容错系统都会涉及到共识问 题。 2 共识问题抽象来说，就是要求一系列进程对某个抽象值( v a l u e ) 达成一个共识。 过程可以用两个原语来表示，p r o p o s e 原语和d e c i d e 原语。p r o p o s e 时每个进程提 出一个抽象值v ，d e c i d e 时所有正确进程必须最终决定某个值。解决共识问题必 须满足以下条件： 【1 】终止性：所有正确进程最终都要决定某个值； 【2 】有效性：假如某个进程决定了某个值，那么这个值必须是在p r o p o s e 原语 中由某个进程所提出的。 【3 】一致性：所有正确进程最终决定的必须是同个值。 原子广播和共识问题的等价性： 文献( 7 】中证明了异步系统下原子广播和共识问题是等价的。 1 原子广播可以用共识问题的方法解决：当某个进程执行a - b r o a d c a s t 原语 时，发送消息给所有进程，当其它进程收到消息后，把这条消息进行缓存， 一直等到这条消息的次序最终被决定。而决定消息的过程是由进程间的一 系列的共识( 分别标为1 ，2 n ) 来完成的。具体过程如下：消息m s 甑是在 第k 次共识时被决定的，消息m s g k + l 是在第k + 1 次共识时被决定的，每 次共识完成后就可以传递条消息，只要缓存区域内还有消息没有被传 递，就不断地进行共识。借助共识的一致性，原子广播的属性可以得到满 足。 2 共识问题可以用原子广播的方法解决：需要进行共识时，每个进程执行 p r o p o s e 原语提出一个值v 的同时，利用原子广播把这个值传给其它进程， 决定( d e c i d e ) 时选择第一个被传递的消息，由于原子广播的全序性，能够 确保每个正确进程都会传递相同的第一个消息。共识问题的其他属性也可 以很容易的被满足。 由上面的证明可以看出，在允许出现崩溃进程的异步式分布系统中，原子广 播问题和共识问题是等价的，其中一个问题的解决方法都可以用来解决另外一个 问题。 1 2 共识问题的研究现状 共识协议的解决途径大致有两种，相同的是都需要借助一些指示器( o r a c 】e ) 。 其中一种是借助随机化的方法，另外一种是基于失效检测器的途径 ，也有的文 献结合了这两种途径以求得到更好的效果【1 0 川】，以下将对这两种途径做一个简单 的描述。 3 基于失效检测器的异步系统共识协议研究 1 2 1 基于r o r a c l e s 的共识协议 这种途径实际上减弱了共识问题的要求【l 。”l ，利用r o r a c l e 模块设计概率共 识协议( p r o b a b i l i s t i cc o n s e n s u sp r o t o c o l s ) ，也就是努力使得共识协议能够得到最终 确定解的概率为1 。每个进程连接一个r o m c l e 模块，当进程询问本地r - o r a c l e 模块时会有一个返回值，返回值的取值范围为f 1 ，n ，返回值服从统一分布， 每个值x ( 1 x 1 ，进程集合为n = f p l ，p 。j ，进 程在运行过程中可能发生崩溃性错误( c r hf a i l u r e s ) ，进程发生崩溃以后不会自动 恢复。由于共识协议纵容性的要求，发生崩溃性错误的进程数目f 不能超过进程 总数n 的一半( ， 兰) 。 2 为方便后面的研究分析，首先要对分布式系统模型有所了解。在这里将首先 详细介绍一下系统的模型。分布式系统有两种基本的类型，同步模型和异步模型， 但针对异步系统下共识问题的不可解性，研究者提出了一种介于同步模型和异步 模型之间的系统模型半同步模型【】”。分布式系统模型有两个最重要的变量： 消息的传输延时和进程的相对执行速度。为方便后面的研究分析，首先定义这两 个变量：表示消息的传输延时：表示进程相对执行速度。 1 同步模型：在同步系统模型中，和的上界都是已知的，并且假设进程 具有同步的时钟。在这样的系统中，使用超时机制可以实现可靠的失效检测，因 此，分布式系统中一些重要的问题，例如：一致性问题，选举问题都可以得到解 决。但是，因为同步模型对和的限制较大，所以满足这种特性的分布式系统 很少，特别是对于大规模的分布式系统，都很难满足这样的特性。 很少，特别是对于大规模的分布式系统，都很难满足这样的特性。 7 2 异步模型：在异步系统中，消息的传输延时和进程的相对执行速度都 没有上限，进程之间的时钟不同步。正因为这种系统模型对条件的要求比较小， 而目前的分布式系统因为网络状况和应用负载的多变性使得异步式分布式系统的 应用最为广泛。 3 半同步模型；由f l p 理论我们已经知道在完全异步的系统模型中，只要允 许进程发生错误，那么共识问题具有不可解性。但是在实际的应用当中，系统既 不是完全异步的，也不是完全同步的。在大多数时间内，系统处在一个稳定时期 当中，延时和进程运行速度都是有限的，系统只是在短时间内，延时和进程运行 速度都不稳定，此时系统处在一个异步的环境中。因此这种模型被称为半同步模 型。d w o r k 等考虑了以下三种半同步模型f ”j 1 m 1 ：在系统的运行中，消息传输延时和进程相对速度毋都存在上限，但 是其大小未知。 2 1 2 ：消息传输延时和进程相对速度都存在上限且大小可知，但是上限 只在一个未知的系统稳定时间g s t ( g l o b a ls t a b i l i z a t i o nt i m e ) 后存 在，其中g s t 是有上限的。与m 2 模型相符合的系统，在g s t 时刻之前为 异步系统，在g s t 时刻以后为同步系统。 3 m 3 ：消息传输延时和进程相对速度存在有未知上限，此上限只有经过 一段系统稳定时间后( g l o b a ls t a b i l i z a t i o nt i e ) 才存在，系统稳定 时间( g s t ) 有上限，但上限不可知。与m 3 模型相符合的系统，在g s t 时刻 之前为异步系统，在g s t 时刻以后和m 1 模型相同。另外，符合m l 模型或 者符合m 2 模型的系统都符合m 3 模型。 2 3 进程的失效类型和失效模式 失效类型：典型的分布式系统由多个进程组成，这些进程通过它们之间的通 道进行通信。在分布式系统中，因为故障的发生，进程的失效是不可避免的，根 据消息传递的分布式系统进程可能发生的故障来分类，大致有以下两种类型： c r a s hf a i l u r e s 类型，当这种错误发生后，进程停止运行，不再做出发送、 传输、接受消息等任何行为，这种类型的错误比如在出现进程崩溃故障、 系统掉电故障等情况下存在。 b y z a i l t i n ef a i l u r e s 类型，这种失效会导致进程处于一种完全随机的状态， 进程出错后仍继续运行，但执行的结果不正确，会给其他进程给出错误 的响应这种失效一般是由逻辑错误或者是恶意攻击所导致的。 另外，在这里指出，我们把一个从来没有发生过上述错误的进程称为一个正 确的进程( c o r r e c tp r o c e s s ) 。本文研究的错误类型为c r a s h 蹦l u r e s 类型错误。 8 硕士学位论文 失效模式说明：为了方便下一章对失效检测器精确性和完整性两种属性的介 绍，在这里首先介绍在失效检测器设计当中存在的一些符号和表达式：f 代表虚 构的系统时钟值，取值范围为自然数。失效模式表示为f ，f ( t ) 代表经过t 时刻以 后系统中发生崩溃的进程队列，进程发生崩溃后不再恢复，因此f ( t ) f ( t + 1 ) 。 崩溃进程集合表示为c r a s h ( f ) = uf 。，f ( t ) ，正确进程集合表示为c o r r e c t ( f ) = n 一盯船舷d ( f ) 。h 代表失效检测器的历史纪录，h ( p ，t ) 代表在t 时刻p 进程本地失 效检测器的怀疑队列，q h ( p ，t ) 代表的意义为，在t 时刻，p 进程本地失效检测 器认为进程q 发生崩溃。同一时刻两个不同进程p 和q 的失效检测器结果可能不 相同，即存在有h ( p ，t ) h ( q ，t ) 。 2 4 可靠广播概念 进程之间通过可靠的通信通道进行消息传递来彼此通信。信道是可靠的，不 存在对消息的生成、变更、丢失和复制。在消息的传输中可以调用可靠广播【l “， 可靠广播r e l i a b i eb 加a d c a s t 的定义如下： 简单来说可靠广播确保满足三点要求： 所有正确进程传递相同的消息集。 所有正确进程广播的消息最终都会被传递。 在传递的消息中不存在有伪造的消息。 可靠广播分为两个原语r - b r o a d c a s t ( m ) 和r d e l i v e r ( m ) ，当进程执行 r 出r o a d c a s t ( m ) 原语时，我们称它广播了一条消息m ，当进程执行r d e l i v e r ( m ) 原 语时，我们称它传递了消息m 。每条消息m 都是唯一的，可靠广播有以下三条属 性： 有效性( v a l i d i t y ) ：如果某个进程广播( r b m a d c a s t ) 消息m ，最终它会传 递( r d e l i v e r ) 消息m 。 一致性( a g r e e m e n t ) ：如果某个正确进程传递( r d e l i v e r ) 消息m ，那么所有 正确进程最终都会传递( r d e l i v e r ) 消息m 。 统一性( u n i f o mi m e g r i t y ) ： 对于任何一条消息m 来说，如果有某个进程 执行了r d e l i v e r ( m ) ，那么在这之前必然存在有进程p i 执行过 r b r o a d c a s t ( m ) 。其中进程p i 是消息m 的发送者。 2 5基于失效检测器的共识协议纵容性 基于失效检测器的共识协议，每个进程都要异步地执行一定的轮次，每一轮 中各个进程之间相互通信交换信息。协议必须满足两点属性，即安全性( s a f e t y ) 和 9 基于失效检测器的异步系统共识协议研究 活跃性( l i v e n e s s ) 。这两条属性确保了执行共识的进程最终能够终止运行，并且正 确进程所得出的结果是一致的。失效检测器的属性确保活跃性，保证进程不会因 为长时| 、日j 等待一个崩溃进程信息而处于阻塞状态。安全性意味着当某个进程p ，在 某一轮中得到一个共识结果以后，此后所有其它正确进程所得到的共识结果都会 是同一个值，因此协议要求当进程做决定时，必须得到大于进程总数一半数目进 程的认可。这也是前文所提到的协议一个非常重要的属性，即纵容性的含义。所 有的共识协议都必须具有“纵容性”，因为失效检测器给出的结果并不能保证是 正确的，共识协议必须确保在检测器的结果不正确时，不违背安全性的原则。即 只有当失效检测器的条件满足时，共识协议才可能给出结果，能够确保给出的结 果一定是j 下确的。当失效检测器的条件没有满足时，共识协议不会给出任何结果。 2 6 本章小结 本章详细介绍了异步共识问题所涉及到的一些基本概念，对进程集合、系统 模型、网络环境和进程有可能出现的错误分类进行了描述，在本章的最后对基于 失效检测器的共识协议的基本原理做了简单的阐述，本文将在第四章详细介绍共 识协议。 1 0 硕七学位论文 3 1引言 第3 章失效检测器研究 通过f l p 理论可以得知，在异步系统并且允许进程出现崩溃的情况下，共识 等一致性问题得不到确定解，关键原因在于异步系统下无法准确的判断一个长时 间没有响应的进程究竟是发生崩溃，还是只是运行的比较缓慢。正是由于这种不 确定性使得问题难以解决，在这里就需要求助于指示器( o r a c l e ) 【1 7 】。失效检测器的 功能就是提供这样的一种指示，负责周期性的检测其它进程的状态，并将结果返 回给上层的协议【l “1 9 】。在这一章里，我们将详细介绍失效检测器的定义和分类， 然后对失效检测器的具体设计和评估方法进行描述，介绍失效检测器的o o s 标 准，在本章的最后是在本文的实验中所引入的失效检测器的设计方法，这种方法 具有较小的通信量开销，减轻失效检测器设计本身带来的消息负载。 3 2失效检测器的定义和分类 3 2 1 失效检测器定义 失效检测器也称为故障检测器，由于在异步系统模型下，无法对进程的具体 状态做出准确的判断，因此检测故障的任务由不可靠失效检测器来完成。之所以 称之为不可靠的失效检测器是它可以出错，比如可能怀疑一个正确的进程p 发生 崩溃，在此后发现错误的怀疑了p 进程后，再将p 进程从怀疑队列中清除。因此， 每个模块都可能重复的增加或删除队列中的怀疑对象，在某个特定时刻，两个不 同的失效检测器模块可能有不同的怀疑进程队列。 3 2 2 失效检测器分类 c h a l l d r a 和t o u e g 在文献【7 】中根据完整性和精确性两种属性将失效检测器 分类。其中完整性是对失效检测器掌握崩溃进程的全面性做出限制，而精确性则 限制了其可能出现错误的范围。完整性分为两种，精确性分为四种，因此将失效 检测器分为八类。其中的四类是研究的重点。如表3 1 所示。 完整性属性的描述如下： 1 强完整性( s t r o n gc o m p l e t e n e s s ) ：最终每个崩溃的进程都被所有正确进 程永久地怀疑。 基于失效检测器的异步系统共识协议研究 v f ，v h j d ( f ) ，了f r ，b c ，u 咖e d ( ，) ，v g c o r m c f ( f ) ，v f f ：p 日( g ，f ) ( 3 1 ) 2 弱完整性( w e a kc o m p l e t e n e s s ) ：最终每个崩溃的进程都会被某些( 至少 一个) 正确进程所怀疑。 v f ，v h d ( f ) 弓f f ，v p c r 椰矗e d ( f ) ，弓g c d r r e c f ( f ) ，v f f ：p 日( g ，f ) ( 3 2 ) 显而易见的是，仅仅有完整性是远远不够的。因为只要某个失效检测器简单 地永久地怀疑所有进程就可以满足完整性的要求，但这肯定是没有任何用处的。 因此除了完整性以外，失效检测器还有精确性属性，限定它可能发生的错误的范 围。精确性属性的描述如下： 1 最终强精确性( e v e n t u a ls t r o n ga c c u r a c y ) ：存在一个时刻t ，当过了这 个时刻以后，任何正确进程都不会被所有其他正确进程所怀疑。 v f ，v 日d ( ，) ，m f ，v f ，y p ，g r 陀c f ( f ) ：p 萑( g ，f ) ( 3 3 ) 2最终弱精确性( e v e n t u a lw e a ka c c r u r a c y ) ： 存在一个时刻，当过了这 个时刻以后，至少存在有一个正确的进程不被其他所有正确进程怀疑。 v f ，v d ( f ) ，j r f ，动c 口r w 甜( f ) ，v f f ，v g c o 玎p 甜( f ) ：p 叠日( q ，r ) ( 3 4 ) c h a n d r a 和t o u e g 在文献【7 】中证明w 类失效检测器是解决异步共识问题的 最低限度，同时他们也指出了任何w 类失效检测器可以借助于某种算法成为s 类失效检测器。因此w 类和s 类失效检测器在解决问题的能力上是相等的，假 如一个问题可以用s 类失效检测器解决，那么它也可以用w 类失效检测器解 决，反之依然，因此s 类失效检测器同样也是解决关识问题的最低限度。有很 多种共识协议就是基于s 类失效检测器的。 表3 1 四种类型的失效检测器 完整性 a c c u r y ( 精确性) c o m p l e t e n e s s e v e n t u a ls t r o n ga c c u 阮c ye v e n t u a lw e a ka c c u r a c y s t r o n gc o m p l e t e n e s s e v e n t u a lp e r f 爸c t p e v e n t u a ls t r o n g s w e a kc o m p l e t e n e s s q e v e n t u a lw e a k w s 类失效检测器满足： 1 强完整性( s t r o n gc o m p l e t e n e s s ) ：最终每个崩溃进程都被所有正确进程 怀疑。 2 最终弱精确性( e v e n t u a lw e a ka c c u r a c y ) ：存在一个时刻，当过了这个 时刻以后，至少存在有一个正确的进程不被所有正确进程怀疑。 q 类失效检测器： q 类失效检测器是另外一种比较典型的失效检测器。q 类失效检测器被询问 时，所返回的结果是当前唯一一个被认为是正确的进程，即领导( 1 e a d e r ) 进程， 同理，q 类失效检测器也是不可靠的，在很长一段时间内，可以同时存在几个领 导进程，但最终所有正确进程应该选择同一个领导进程。即满足条件： 1 2 最终决定权( e v e n t u a ll e a d e r s h i p ) ：存在一个正确进程p 和一个时刻t ， 在时刻t 后，任何正确进程询问失效检测器的返回值都是进程p 。 尽管q 类失效检测器的输出是一个单个的进程，和s 类失效检测器的输出 为一系列进程不相同，但实际上，他们的性麓是一样的，可以通过某种协议将两 种类型的检测器进行互换【2 0 1 ，因此，这两种类型的检测器解决问题能力是相等的。 3 3失效检测器设计方法概述 任何设计失效检测器的协议都要求进程检测其他进程是否发生崩溃，然后采 取相应的措施。失效检测器的设计方法有很多种f 2 1 也】，归纳起来大致有两种，一 种是根据心跳消息检测的方式另外一种则是询问回答的方式。 3 3 1 根据心跳消息的设计方式 这种方式采用的是常见的心跳检测法，检测进程在其检测时间t 内如果没有 收到来自被检测进程的消息，则认为进程发生崩溃。根据心跳发送的类型分有 p u s h 模型和p u l l 模型。基于p u s h 的失效检测方法又称为“推”方法，如图3 1 ： 被检测进程q 周期性的发送j - a i l l a l i v e 消息，以显示其没有发生崩溃。假如在t 时间内，p 没有收到q 的消息，那么p 认为进程q 发生崩溃。 譬兰害兰聿兰妥二。 k 下下 i、 、 、 每每害奇： 图3 1 失效检测器设计的p u s h 方法 基于p u n 的失效检测方法又称为“拉”方法，过程如图3 2 所示：检测进程 周期性地向被检测进程发出询问，被检测者在收到这样的询问消息后，就会向检 测者报告自己的状况以显示没有发生崩溃，同理如果在一定时间t 内进程p 没有 收到来自被检测进程q 的晌应，则认为其崩溃。 这种基于心跳机制的失效检测器设计方法有一个比较难以解决的问题，就是 检测时间t 的设置，如果时间t 设置的过短，进程发生崩溃时检测时间( d e t e c t t i m e ) 会较短，但同时发生错误怀疑( w o n gs u s p i c i o n s ) 的几率会升高；而如果 时间t 设置的过长，错误怀疑的发生率会降低，但同时付出的代价是检测时间的 1 3 基于失效检测器的异步系统共识协议研究 延长。而分布式下各进程都处于网络环境中，网络的状况是在不断变化的，消息 的传输延时随着网络环境的变化而变化，从而心跳消息到达的时间间隔是一个变 化值，甚至有可能因为网络数据的丢包造成心跳消息的丢失。因此如何让失效检 测器具有自适应性，以达到减少失效检测发生错误怀疑的概率方面，是一个设计 研究的热点，关于失效检