（计算机应用技术专业论文）基于消息延迟预测的自适应失效检测模型研究.pdf

本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 一：依矗森嗍咖如侈日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州 大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、 缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学 位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑 州大学。保密论文在解密后应遵守此规定。 学位敝懈百褰矗象 嗍弘解岁月日 摘要 摘要 失效检测是实现分布式系统高可用性的一个关键技术，被广泛应用于网络 通讯协议、分布式算法、组通讯协议、组成员管理协议、计算机集群管理、网 格计算等各种分布式应用系统中，并经常被用来解决分布式系统中的一些基本 问题，如一致性问题、原子多播问题等。 在实际的网络环境中，系统规模比较大，网络状况比较复杂，传统的通过 设置固定超时值失效检测方法不能满足系统的q o s 需求。白适应失效检测是通 过对消息延迟的历史记录进行计算、分析之后得到一个预测的理论超时值，作 为判断下一个消息是否失效的重要依据，这个超时值是随着实际消息延迟的变 化而变化的，因此具有较强的适应能力。 本文提出了一种基于消息延迟预测的二次检测模型，并在此模型的基础上 提出了一种p a - a f d 自适应失效检测算法，该算法使用z i p f 定律对得到的超时 值进行加权计算，然后作为判断信息是否失效的依据。 本文证明了p a - a f d 算法满足的失效检测级别，实验结果及分析表明该算法 在保证检测准确性和完整性的同时缓解了网络延迟对失效检测的影响。 关键词：高可用性失效检测q o s 分布式系统 白适应 f a i l u r ed e t e c t i o ni sak e yt e c h n o l o g yt or e a l i z eh i g ha v a i l a b i l i t yi nd i s t r i b u t e d s y s t e m s i th a sb e e nw i d e l yu s e di nm a n yd i s t r i b u t e da p p l i c a t i o ns y s t e m s ，s u c ha s n e t w o r kc o m m u n i c a t i o np r o t o c o l s ，d i s t r i b u t e d a l g o r i t h m s ，g r o u p c o m m u n i c a t i o n p r o t o c o l s ，g r o u pm e m b e r s h i pm a n a g e m e n tp r o t o c o l ，c o m p u t e rd u s t e rm a n a g e m e n t a n dg r i dc o m p u t i n ga n di ti sa l w a y su s e dt os o l v ec o h e r e n c ea n da t o m i cm u l t i c a s t i s s u e s ，e t c w h i c ha r ef u n d a m e n t a li s s u e si nd i s t r i b u t e ds y s t e m s i nt h ea c t u a ln e t w o r ke n v i r o n m e n t ，t h es y s t e m sa r er e l a t i v e l yl a r g ea n dt h e n e t w o r ks i t u a t i o ni sc o m p l e x ，s ot h et r a d i t i o n a lf a i l u r ed e t e c t i o nm e t h o dw h i c hi s r e a l i z e d b ys e t t i n gaf i x e dt i m e o u tv a l u ec a nn o tm e e tt h eq o so ft h es y s t e m r e q u i r e m e n t s i n t h ea d a p t i v ef a i l u r ed e t e c t i o na l g o r i t h m s ，p r e d i c t e dt h e o r e t i c a l t i m e - o u tv a l u e sa r eo b t a i n e db yc a l c u l a t i n ga n da n a l y s i n gt h eh i s t o r i c a lr e c o r d so f m e s s a g ed e l a y t h et i m e - o u tv a l u e s ，w h i c ha r eu s e dt oj u d g et h a tw h e t h e rt h en e x t m e s s a g ei sf a i l e do rn o t ，c a nc h a n g ew i t ht h ea c t u a lm e s s a g ed e l a y s ot h ea d a p t i v e f a i l u r ed e t e c t i o na l g o r i t h m sh a v es t r o n ga d a p t a b i l i t y ad o u b l ed e t e c t i o nm o d e lb a s e do nm e s s a g ed e l a yp r e d i c t i o ni sp r o p o s e di nt h i s a r t i c l ea n dap a - a f da d a p t i v ef a i l u r ed e t e c t i o na l g o r i t h mi sp r o p o s e do nt h eb a s eo f t h i sm o d e l t h ep a - a f da l g o r i t h mu s e st h ez i p f sl a wt ow e i g h t - c a l c u l a t et h e t i m e - o u tv a l u ea n dt h e nj u d g e st h a tw h e t h e ram e s s a g ei sf a i l e do rn o t t h ef a i l u r ed e t e c t i o nl e v e lw h i c ht h ep a - a f da l g o r i t h ms a t i s f i e si sp r o v e di n t h i sa r t i c l e e x p e r i m e n t a lr e s u l t sa n da n a l y s i s e ss h o wt h a tp a - a f da l g o r i t h mh a s d e t e c t i o na c c u r a c ya n dd e t e c t i o nc o m p l e t e n e s sa n dc a ne a s et h ei m p a c to fn e t w o r k d e l a yo nf a i l u r ed e t e c t i o n k e yw o r d s ：h i g ha v a i l a b i l i t y ；f a i l u r ed e t e c t i o n ；q o s ；d i s t r i b u t e ds y s t e m ；a d a p t i v e i i 目录 目录 摘要i a b s t r a c t i i 目录i i i 图的目录v 工 表的目录v i i 1 绪论1 1 1 研究背景1 1 2 提高系统可用性的关键技术3 1 2 1 提高系统硬件可用性的关键技术3 1 2 2 提高系统软件可用性的关键技术4 1 3 失效检测技术现状7 1 3 1 可扩展失效检测技术8 1 3 2自适应失效检测技术1 0 1 4 本文的主要研究内容与组织结构1 1 2 失效检测技术的理论基础1 4 2 1 分布式系统模型分析1 4 2 1 i同步系统1 4 2 1 2 异步系统1 5 2 1 3 半同步系统1 5 2 2 故障类型1 6 2 2 1 按照故障持续的时间划分1 7 2 2 2 按照节点出现故障后的行为划分1 7 2 2 3 按照故障的外在表现划分1 7 2 3 失效检测器的定义1 8 2 4 失效检测级别定义1 9 2 4 1 失效检测器的属性1 9 2 4 2 失效检测级别及分类2 0 tt t 目录 2 4 3 失效检测器的分类2 1 2 5 本章小结2 2 3 失效检测算法分析2 3 3 1 失效检测技术2 3 3 1 ip u s h 模式失效检测技术2 3 3 1 2p u l l 模式失效检测技术2 4 3 2 失效检测算法分析一2 5 3 2 1 传统的失效检测算法2 5 3 2 2自适应失效检测算法及分析2 5 3 3 失效检测的性能评价分析2 8 3 3 i 检测准确性和检测速度之间的矛盾2 8 3 3 2 配置参数对失效检测性能的影响2 9 3 3 3 失效检测的性能评价目的2 9 3 3 4 基于应用的失效检测性能评价。3 0 3 4 本章小结3 1 4 基于消息延迟预测的二次检测模型3 2 4 1 基于消息延迟预测的二次检测模型3 2 4 2 基于二次检测模型的p - a f d 算法及其实现3 4 4 2 1 算法描述3 5 4 2 2 算法失效级别证明3 8 4 3 实验及性能分析3 9 4 3 1p 取值对失效检测性能的影响3 9 4 3 2 历史窗口大小对失效检测性能的影响4 0 4 3 3 性能分析4 2 4 4 本章小结4 3 5 总结与展望4 5 5 1 结论4 5 5 2 进一步的工作4 5 参考文献4 6 i v 目录 个人简历、在学期间发表的学术论文5 0 个人简历5 0 在学期间发表的学术论文5 0 致谢5 1 图的目录 图的目录 图i 1计算机系统的运行、维护周期2 图1 2层次结构的失效检测器9 图2 1失效检测状态转换图1 9 图2 2四类失效检测器检测级别的顺序2 2 图3 1p u s h 模式失效检测执行过程2 3 图3 2p u l l 模式失效检测执行过程2 4 图4 1二次检测模型失效检测执行过程3 4 图4 2p 对检测时间的影响4 0 图4 3 窗口大小对检测时间的影响一4 1 图4 4与b e r t i e r 算法的性能对比4 3 v i 表的目录 表的目录 表2 1失效检测器的八种类型2 1 表4 1p a 对平均检测时间和错误率的影响4 0 表4 2窗口大小对平均检测时间和错误率的影响4 1 表4 3 与c h e n 失效检测算法比较4 2 表4 4 与b e r t i e r 失效检测算法比较4 3 v i i 1 绪论 1 绪论 随着网络应用的发展，分布式系统在人们的社会生活中起着越来越重要的 作用，系统的高可用性作为一个研究热点也越来越被人们所关注。在现实生活 中，大多数分布式系统都属于异步系统，由于分布式系统的不确定性、可能的 结点故障和通信延迟等因素的存在，要想在异步系统上实现可靠的分布式应用， 离不开失效检测技术。本章介绍了分布式系统的常用关键技术，分析了分布式 系统中失效检测器的研究现状和相关解决方案，并在此基础上给出了论文的研 究课题和全文的内容组织结构。 1 1研究背景 在i n t e r n e t 应用日益普及与流行的当今社会，分布式计算技术已经渗入到商 业、电信、金融等应用领域【1 1 ，另外，随着政府、企业以及公司业务规模的不断 扩大，单位所使用的网络环境也逐渐从早期的局域网扩展到广域网。系统规模 的不断扩大，导致外在的危险因素对系统正常运行的影响越来越大，而系统中 软件或者硬件部分发生不可预计的故障的可能性也不断增大。一般情况下，对 于一个系统来说，平均每天有几个节点发生故障是正常的1 2 】，它们或者是需要更 换系统的硬件设备，或者是仅仅需要重启一下应用进程或操作系统即可恢复系 统的正常工作。但是，对于每天都要面临上百万甚至上千万级用户访问量的服 务商来说，这些故障是不可容忍的，因为，对于他们来说，数据的丢失或者服 务的频繁中断将直接导致巨大的经济损失，甚至会造成法律上的纠纷。这也从 另一个角度说明了，用户对服务的可用性提出了越来越苛刻的要求，他们希望 能够得到7 * 2 4 小时的不间断服务，所以，系统的高可用性越来越成为人们研究 的重点。 在高可用性理论中i3 1 ，一般采用可靠性( r e l i a b i l i t y ) 、可用性( a v a i l a b i l i t y ) 和可维护性( s e r v i c e a b i l i t y ) 这三个术语来定义系统的完善性和健壮性，通常被 简记为r a s 。下面先给出这三个术语的定义： 可靠性( r e l i a b i l i t y ) 是指一个系统在不中断的情况下，可以连续多长时间 地正常工作。它是大规模存储系统中的关键问题之一1 4 j ，通常使用m t f ( m e a n 1 绪论 t i m et of a i l u r e ) 来衡量，m t r f 表示两次故障之间的平均时间，即系统运行的 平均故障时间。 可用性( a v a i l a b i l i t y ) 是指对于用户来说，系统可以正常使用的时间对于总 时间的百分比。它强调的是，系统在故障出现之后多长时间才能恢复并能重新 提供服务。 可维护性( s e r v i c e a b i l i t y ) 反映了对系统的服务，如软件和硬件的维护、修 理以及升级的难易程度。它一般是通过m i t r ( m e a nt i m et or e p a i r ) 来衡量的， m t i r 表示从系统停止服务到系统可以正常运行的平均时间。 图1 1 反映了一个计算机系统的运行周期。一般情况下，一个计算机系统先 是正常运行一段时间，然后，突然发生了故障，需要进行系统的修理或者升级， 系统进入维护阶段。经过一段时间之后，当系统维护好了，就重新回到正常的 工作状态。这个过程是周而复始的。 o k f a i l ( f a u l to c c u r s ) o k l n o r m a lo p e r a t i o n i b e i n gr e p a i r e d i 卜m t t f ( m e a nt i m et of a i l ) 卟m i t r ( m e a n t i m et or e p a i r ) 叫 ii l 图1 1计算机系统的运行、维护周期 通过m t i f 和m t i r ，可以将计算机系统的可用性定义为： a v a i l a b i l i t y ：坚竺或a v a i l a b i l i t y ：丝塑 m t t f + m i t rm u t + m d t 其中，m u t 为系统能够正常提供服务的时间，m d t 为系统不能正常提供服务的 时间。 由可用性的定义公式不难看出，系统的可靠性和可维护性共同决定了系统 的可用性，所以，要想提高系统的可用性，有两种途径： ( 1 ) 提高系统的可维护性，即缩短系统的m t i r 。系统的m t t r 依赖于系 统发生故障的组件：如果是应用程序本身发生了故障，那么，只要简单地重新 启动应用程序就可以将系统恢复了；但是，如果是由于系统的硬件故障而导致 应用出了问题，那么，系统的恢复工作就可能会涉及到：把系统的故障通知给 服务提供商一等待服务商的技术人员一确认系统发生故障的组件一更换系统发 生故障的组件一重新启动操作系统一重新恢复文件系统一重新恢复数据库系统 一重新启动系统的网络设备( 包括软件) 一重新启动应用程序。 2 l 绪论 ( 2 ) 提高系统的可靠性，即增大系统的m t r f 。这就需要提高组成系统的 每个组件的可靠性。这些组件主要包括：服务器上面安装的操作系统、服务器 的硬件以及应用程序本身，另外，还有其他的一些组件，例如，文件系统、数 据库系统、网络设备、数据存储设备、数据中心的基础设施等。 1 2 提高系统可用性的关键技术 一个完整的计算机系统往往由大量复杂的软件和硬件组成，这样复杂的系 统难免会产生故障。在一些系统中，部分组件的故障，无论是软件部分的故障 还是硬件部分的故障，都有可能会导致整个系统的崩溃，因此，很有必要提高 系统的可用性。一般情况下，系统的故障可以分为硬件故障和软件故障【5 1 ，所以， 提高系统的可用性，可以从两个方面来考虑，即：提高系统的硬件可用性和提 高系统的软件可用性。 1 2 1 提高系统硬件可用性的关键技术 研究发现，硬件系统通过最小化故障修复时间以及最大化系统组件的可用 性，可以获得9 9 到9 9 9 的系统可用性。在分布式系统中，要想取得较高的系 统可用性，一般需要采用冗余配置技术。冗余的主要目的是屏蔽系统中节点的 暂时失效，从而能够让系统在没有永久失效时保证系统的目标可用性【6 1 。常用的 冗余技术有【7 j ： ( 1 ) 软件冗余：通过提供软件模块的额外版本、不同的软件实现方法等 方式来提高系统的可用性； ( 2 ) 信息冗余：通过备份信息的方式来达到容错的目的，以提高系统的可 用性，例如检查点( c h e c k p o i n t ) 技术、日志机制等，从而使系统在部分组件出现 故障的时候使系统仍然能够正常运行； ( 3 ) 物理冗余：通过增加多余的处理器、存贮器等重要物理资源的方式实 现容错，以提高系统的可用性； ( 4 ) 时间冗余：通过重复执行某个操作达到容错目的，例如重新执行操作、 超时重发机制等。 根据冗余在不同级别的实施，又可以将冗余划分为三种类型： ( 1 ) 双机热备：该冗余模式是系统级的冗余，即对系统中的所有节点进行 3 1 绪论 冗余备份，这时，可以将系统中的节点分为主用节点和备份节点两部分，一般 情况下，系统的正常运行是靠主用节点来完成的，当主用节点由于其中某个部 件出现故障而导致该节点不能正常使用时，则立即启用备份的节点，以保证系 统继续正常工作。 ( 2 ) 部件冗余：该冗余模式是元件级的冗余，即对系统的重要部件、使用 频率较高的部件以及容易出现故障的部件进行冗余备份，当正在使用的某一个 部件出现故障时，马上启用冗余的部件来承担任务，以保证系统继续正常运行。 总的来说，部件冗余和双机热备都属于热备模式的冗余方法，二者的区别 在于：部件冗余是对系统的重要部件、容易出现故障的部件和使用频率较高的 部件进行冗余备份；而双机热备则是对所使用的整个系统节点进行冗余备份的。 一般情况下，作为热备模式的冗余方法，都是由系统的主用组件提供服务的， 这个时候，系统的备份组件不提供服务。一旦系统的主用组件发生故障，那么， 备份的组件能够马上接替工作。不过，从节约成本的角度出发，一个更经济的 做法是使用一个备份组件来对多个主用组件进行备份，因为备用组件一般情况 下都是空闲的，所以，它们能够很快接替主用组件的服务。但是，在这样的配 置当中，主用组件和备份组件往往在逻辑上是不对等的，主用组件的优先级别 往往要高于备份组件的优先级别，因此，这种热备模式的冗余方法有时候也被 称为“级联”。 ( 3 ) 集群：这也是一种系统级的冗余，它的实现原理为，将n 个节点连接 在一起，作为一个系统，这样的话，一个节点可以有多个备份节点，也可以使 多个节点之间相互备份，当某个节点发生故障时，通过将该故障节点上面的数 据、应用和用户交换到另外一个节点或者几个节点上面来提高系统的可用性。 通过上面对各种系统冗余方法的简单介绍，可以看出，对系统硬件进行不 同类型的冗余将会为系统提供不同级别的可用度，但同时系统的开销也是不一 样的。所以，在实际的应用当中，应该根据不同的性价比来选择不同的冗余方 式或者几种冗余方式的组合。 1 2 2 提高系统软件可用性的关键技术 提高系统的软件可用性也是提高系统可用性的一个常用方法，通常情况下， 提高系统的软件可用性可以从如下几个方面进行考虑： ( 1 ) 容错技术 4 1 绪论 在高可用性方案中，容错技术是提高系统可用性的一种成本最高的方法。 因为，在这种技术中，需要有n 个组件来为一个组件做备份，这样的话，就使 成本增加了n 倍。然而，从应用的角度来说，使用容错技术时，即使组件有n 1 次的故障，也不会影响系统的正常运行。容错技术在目前的飞机飞行控制系统 中有着广泛的应用。 ( 2 ) 数据备份技术 在实行数据备份时，会涉及到多种数据备份技术，不同的数据备份技术在 具体的实现方法上面的侧重点也是不一样的。下面从不同的方向将各种备份技 术进行分类比较。 从备份量上进行分类，数据备份技术主要包括：差异备份、增量备份和完 整备份。 差异备份 所谓差异备份，就是每次备份的数据是相对于上一次完整备份之后新增加 的和修改过的数据。差异备份不需要经常对系统进行完整备份，从而缩短了系 统的备份时间，当系统出现故障时，它也可以很方便的对系统进行恢复。这种 备份方式适用于进行了完整备份之后的后续备份。 增量备份 所谓增量备份，是指每次备份的数据只是相对于上一次备份之后增加的和 修改过的数据。在这种备份方式中，没有重复的备份数据，既节省了数据的存 储空间，又缩短了系统的备份时间。但是，当系统出现故障时，这种备份方式 在进行数据恢复时就比较麻烦。通常情况下，这种备份方式也适用于进行了完 整备份之后的后续备份。 完整备份 所谓完整备份，就是需要对整个服务器系统进行备份，包括应用程序生成 的所有数据以及服务器的操作系统。完整备份是对数据库进行的最完整、最全 面的备份，当发生数据丢失的故障时，可以对所有的数据进行恢复。然而，完 整备份的数据量非常大，需要花费很长的备份时间，并且备份的数据中有大部 分的内容都是重复的，这必然会增加用户的成本。一般情况下，完整备份方式 只是在备份的最开始时使用。 按照延迟时间来分类，数据备份技术可以分为：异步备份、同步备份、半 同步备份和定期备份。 5 i 绪论 异步备份 所谓异步备份，就是在上层发出多个写请求时，系统在数据写入主存储系 统之后就可以继续往下执行，而数据的同步工作则由主从存储系统在后台进行。 由此看来，在实际的远程容灾系统中，更适合使用异步备份方式。 同步备份 所谓同步备份，就是在应用程序每次发出写请求时，都需要在将数据同时 完全写入主存储系统和从存储系统后，才能继续执行。通常情况下，这种备份 模式适用于网络延迟较小的远程容灾系统，不过，一般都局限在几十公里之内。 半同步备份 所谓半同步备份，就是在应用程序每次发出写请求时，只须在将数据写入 主存储系统之后就可以继续执行，之后再由主存储系统与从存储系统之间进行 写数据同步，不过，主存储系统只能在主从存储系统完成写数据同步之后才能 响应主机的下一个写请求。 定期备份 所谓定期备份，就是在数据备份的过程中，先将数据保存下来，然后再进 行批量备份。这种备份方式可以使系统及网络管理员在网络有额外负荷时控制 数据的备份。但是，这种备份方式不能保证数据的写入顺序，所以，在备份的 过程中，已传输到目的系统的数据跟源数据不一致，一旦源系统故障，则目的 系统中的数据也不能使用。另外，定期备份的数据有可能早已过期，所以，在 系统出现故障时，不能对系统进行恢复。一般情况下，定期备份被用于数据挖 掘、数据转存以及其他的一些关键场合。 ( 3 ) 失效检测技术 失效检测也是实现分布式系统高可用性的一个关键技术，它是指检测者利 用一定的失效检测模式及失效检测算法对被检测对象进行检测，从而判断被检 测对象在某时刻是否失效的过程【8 】。如果主用系统出现故障，那么，备用系统能 够及时检测到；同样，当备用系统出现故障时，主用系统也应该能够及时检测 到。由于设备的故障将直接影响到系统的正常运行，因此，能否及时检i i ! i i 设 备故障是当前研究的重点问题之一1 9 j 。 按照发起检测行为的不同，一般情况下，可以将失效检测分为外部检测和 内部检测两类。其中，外部检测是指该系统的检测工作由系统外部的失效检测 器来执行；而内部检测则是指将失效检测机制置于系统的内部，在系统的内部 6 1 绪论 执行检测工作，并向外部报告检测的结果。失效检测技术是分布式计算领域中 的一个关键技术，失效检测的效率、结果以及成功率等对系统的可靠性具有重 要的影响。另外，失效检测也是分布式容错系统的基本组成部分，被广泛应用 于各种分布式应用中，例如网络通讯协议、分布式算法、组通讯协议、组成员 管理协议、计算机集群管理【1 0 1 1 1 1 、网格计算【1 2 】等，并经常被用来解决分布式系 统中诸如一致性问题、原子多播问题i ”】等基本问题。失效检测一般采用心跳技 术来实现，按照实现的方式不同，心跳技术又可以分为p u s h 和p u l l 两种1 1 4 j i l 川， 其中，p u s h 模式又被称为“推”模式，是比较常见的失效检测方法，而p u l l 模 式又被称为“拉”模式。 1 3 失效检测技术现状 如前所述，失效检测是实现分布式系统高可用性的一个关键技术，它已经 被广泛应用于网络通讯协议、分布式算法、组通讯协议、组成员管理协议、计 算机集群管理、网格计算等各种分布式应用中【1 6 】，并经常被用来解决分布式系 统中的一些基本问题，例如一致性问题、原子多播问题等。目前，关于失效检 测的研究主要集中在失效检测模型、失效检测算法以及失效检测级别这几个方 面【1 7 】。 c h a n d r a 和t o u e g 最先对失效检测方法进行了系统研究，并在1 9 9 6 年发表了文 献【1 8 】，对失效检测器的理论基础进行了系统论述，同时，根据不同的失效检测 器所满足的完整性和准确性的不同，定义了八类失效检测器，并且给出了他们 之间的转化关系。稍后，他们又证明了w 类型的失效检测器是解决一致性问题 的最弱失效检测器【1 9 】。此后，在理论研究领域里面，人们不断提出一些更加实 用的、新的失效检测器。例如：结合q 失效检测器的属性，在s 类型失效检测 器的基础上，m i k e l 2 0 l 提出了一种被称为最终一致性( e v e n t u a l l yc o n s i s t e n t ) 的 失效检测器c 。同s 类型的失效检测器相比，基于c 类失效检测器实现的一 致性算法具有更短的时间开销。然而，各类失效检测器的完整性要求却很难在 异步环境下得到满足。因此，为了便于实现，人们开始研究对属性进行相应限 制的失效检测器。g u e r r a o u i 署 i s c h i p e r 提出了一种基于有限准确性( l i m i t e d - s c o p e a c c u r a c y ) 的失效检测器，y a n g l 2 1 】等人将这一思想用于解决k 集一致性( k s e t a g r e e m e n t ) 问题。在此基础上，m o s t e f a o u i 矛i i a n c e n n m e 2 2 】【2 3 】总结了正确性受到 7 1 绪论 限制的失效检测器的特点，提出了p k 和p k 失效检测器( 其中，k 为没有被错误 怀疑的正确节点的最少数目) ，并且给出了p k 和p k 失效检测器与具备完整正确 性的p 和p 失效检测器之间转化的算法。在总结了前述的理论研究成果的基础 上，r a y n a l 提出了受限( r e s t r i c t e d ) 失效检测器的概念，定义了两类受限的失效 检测器r ( 1 【，k ，) 和r ( k ，k ，) ( 其中，k 和k ，分别表示正确节点集合中，满足相应的 完整性和正确性要求的节点个数) ，并且，也证明了在同时满足m a x ( k ，k ，) f ( f 为系统允许发生失效的最大节点数目) 和k + k n 的情况下，r ( k ，k ) 和r ( k ，k ) 失效检测器分别等价于s 和s 失效检测器，同时，也给出了相应的失效检测算 法。这些研究工作提高了失效检测器的实用价值，降低了失效检测器的实现代 价，使失效检测器的理论模型逐步走向完善。 然而，在实际的应用当中，随着分布式系统规模的不断扩大，系统对失效 检测机制的设计有了更高的要求，因此，在为实际的分布式应用系统设计失效 检测机制时，仅仅实现满足某种模型的失效检测器模块是远远不够的。在一般 的局域网系统中，由于网络状况相对稳定，系统的节点数目相对来说也比较少， 所以，一般情况下都是基于简单的心跳检测机制，使用a 1 1 t o a 1 1 的失效检测方法 【2 4 】来实现失效检测，也就是说，每一个节点的失效检测模块也同时检测其他的 任何节点，以便获得对整个系统的全局检测消息。但是，随着分布式系统规模 的不断扩大，系统中的节点数目逐渐增多，系统的网络状况也越来越复杂，通 信网络的故障将会对系统的正常运行产生严重的影响【2 5 1 ，这就对失效检测器的 实现提出了可扩展性和自适应性的要求。因此，失效检测器的可扩展性和自适 应性已经成为目前分布式系统失效检测技术的研究重点。 1 3 1 可扩展失效检测技术 对于一个节点数目为n 的系统来说，在使用传统的a 1 1 t o a l l 的失效检测方法 时，将会对系统产生o ( n 2 ) 的检测负载，面对不断扩大的分布式系统规模，这样 的负载量是无法满足系统的q o s 需求的。目前，为了解决失效检测器的可扩展性 问题，人们已经提出了很多方法，其中，最常见的方法是基于g o s s i p 的失效检测 方法和基于层次的失效检测方法。 ( 1 ) 基于层次的失效检测方法 基于层次的失效检测方法是在将节点进行分组的基础上，将其组织成某种 层次结构( 如树结构、森林结构等) ，来降低系统检测消息的复杂度，从而达到 8 1 绪论 图1 2 层次结构的失效检测器 失效检测模块 被检测节点 图1 2 给出了一种层次结构的失效检测器，节点成员被分成若干个组，每个 组都位于不同的层中，并且，在每个组中都包含一个( 或者多个) l e a d e r 节点， 位于该l e a d e r 节点之上的失效检测模块负责对组内其他节点成员进行检测，然 后，每个l e a d e r 节点再将其本地的检测消息连同其后代l e a d e r 节点所上传的检测 信息传递给它上一层中的直接父节点，最终，整个系统中的所有失效检测信息 将被集中在最高层的一个( 树) 或者多个( 森林) 根节点上，而根节点再将这 些失效检测信息广播到系统中所有的l e a d e r 节点上面，这样的话，系统中的各个 节点要想得到整个系统中所有节点的失效信息，只需要查询本组内的l e a d e r 节点 就可以了。很显然，与传统的失效检测方法相比，基于层次的失效检测方法可 以有效降低系统检测消息的复杂度，因而具有很好的扩展性。另外，基于层次 的失效检测方法中所使用的层次结构还可以有效地利用系统的实际拓扑结构。 ( 2 ) 基于g o s s i p 的失效检测方法 g o s s i p l 2 6 】1 2 7 】是一种借鉴了蠕虫病毒在大规模分布式系统中高效传播方式的 基于概率的多播协议1 2 8 】。其实现原理为：在每一轮消息交换的过程中，一个节 9 1绪论 点随机选择另外的某些节点来进行信息交换，经过多轮信息交换之后，即可确 保系统中的所有节点与系统中的其他任何一个节点进行了信息交换。这种失效 检测方法可以有效降低系统中的消息复杂度，并且其实现过程完全脱离了系统 的物理拓扑结构。 r e n e s s e 最早将g o s s i p 技术引入到失效检测领域中，他在文献【2 9 】中提出了最 初的两类基于g o s s i p 技术的失效检测器：基本g o s s i p 失效检测器和多层g o s s i p 失 效检测器。 在基本g o s s i p 失效检测器中，各个节点都拥有一个列表，该列表包含所有节 点成员信息并且为每个节点成员保持一个心跳计数( h e a r t b e a tc o u n t e r ) ，每个节 点周期性地增加表中本节点的心跳计数，然后将成员列表包含在心跳消息中， 发送给随机从成员列表中选择的一个节点成员；某一个节点在接收到消息时， 就会将它曾经保存的列表与消息中包含的列表合并，并且在合并时将所有节点 成员的心跳计数保存为最大值，以更新列表。失效检测系统根据实际应用的需 要设置更新心跳计数的时间间隔l ，如果列表中的某个成员的心跳计数被其中 任何一个节点发现在之后还没有更新的话，那么，该节点成员将被从成员列 表中删除。 多层g o s s i p 失效检测器是在大规模分布式应用系统需求的情况下，对基本 g o s s i p 失效检测器的一个变体。另外，多层g o s s i p 失效检测器还借鉴了层次式失 效检测器的思想，按照i n t e m e t 中域( d o m a i n ) 和子网( s u b n e t w o r k ) 的概念， 结合节点成员的口信息将失效检测系统进行了划分。这样的话，除了少数g o s s i p 消息可以跨越子网的界限外，大多数的g o s s i p 消息都被限制在子网范围内，能在 域之间传送的消息更少。 很显然，基：于二g o s s i p 的失效检测器具有很好的可扩展性，因为该类失效检测 器可以有效控制系统产生的检测消息的数量，一个域内的失效检测负载仅仅与 其拥有的子网数有关。另外，每个节点成员之间的关系是对等的，任何一个节 点都不可能成为系统的可靠性瓶颈。然而，f l 抒g o s s i p 失效检测器消息传输机制 的局限性，需要一段相当长的时间才能够将一个指定的失效节点检测完毕( 至 少o ( 1 0 9n ) t f a i l ) ，也就是说，对于g o s s i p 失效检测器而言，要保证一定的失效检 测准确率，就需要付出较长的检测延迟。 1 3 2 自适应失效检测技术 1 0 1 绪论 从实际应用系统的开发角度来讲，应用系统的q o s 需求是失效检测器的一个 重要的设计依据。人们往往通过使用尽可能少的检测消息来获得实际应用系统 所需要的q o s ，从而尽可能地降低系统的检测开销。传统的基于心跳消息实现的 失效检测器，一般都是通过心跳消息的发送周期t i 和心跳消息的超时值a t o 来决 定其检测行为的。然而，在实际的网络环境中，分布式系统的规模越来越大， 网络链路的结构越来越复杂，从而导致消息延迟的变化也比较大，在这种情况 下，传统的基于固定的发送周期t i 和心跳消息超时值a l o 实现的失效检测器将不 能再提供稳定的q o s 。因此，能够自适应于网络变化的自适应失效检测器被提出。 早期提出的自适应失效检测算法一般都是通过对历史心跳消息的到达时间 进行记录、统计、分析，计算出一个预测值，然后根据该预测值对下一个心跳 消息的超时值a t o 进行调整，在失效检测延迟和失效检测准确性之间进行权衡。 f e t z e r 3 0 l 最早提出了一种简单的自适应失效检测算法，他是在对历史心跳消息延 迟进行统计、分析的基础上，不断获得一个最大的延迟值作为超时值a t o 的上限， 从而在半同步模型下实现了一个o p 类失效检测器。s o t o m a l 3 l j 在c o r b a 中实现 了一个基于m e a n 方法的自适应失效检测协议( m 巳埘方法也是一种常用的失效 检测技术，它是利用心跳间隔的平均值作为失效检测的基础) ，同时又通过使用 心跳消息到达间隔的比率作为调节因子来对预测值进行进一步的调整。在对线 性序列、m e a n 和l a s t 等常用预测方法研究的基础上，f a l a i 3 2 j 等人又给出了各 种方法之间的性能比较，结果表明，将l a s t 方法和线性序列结合起来的失效检 测效果非常好，并且检测复杂度也比较低。然而，这些失效检测方法还不能准 确描述其检测结果所能满足的q o s ，而只是定性地对系统的q o s 需求进行描述。 c h e n 3 3 】等人提出了基于q o s 的失效检测度量体系，并在概率网络模型假设的前 提下，提出了一系列自适应失效检测算法，实现了q o s 对失效检测器参数调整的 定量控制；b e r t i e r l 3 4 】等人对c h e n 等人的自适应失效检测算法进行了改进，通过 使用j a c o b o s o n 关于往返时间( r t r ：r o u n d t r i pt i m e ) 的预测算法来计算修正值 a ，使修正值a 能够随着网络状况动态调整，从而在一定程度上提高了失效检测 器的检测准确度；h a y a s h i b a r a l 3 5 】等人提出的9 检测器，在一定程度上达到了一 个驴检测器可以为多个不同应用提供检测服务的目的。 1 4 本文的主要研究内容与组织结构 1 绪论 如何提高失效检测器的性能是分布式应用系统研究的一个重要内容。失效 检测的完整性和失效检测的准确性决定了失效检测器的性能。目前，主要是通 过采用心跳策略对节点对象进行检测的方法来解决该问题。然而，随着分布式 应用系统规模的不断扩大，网络结构变得越来越复杂，传统的失效检测方法就 不能满足当前分布式应用系统的q o s 需求。在对现有自适应失效检测算法研究、 分析的基础上，本文提出了一种基于消息延迟预测的自适应失效检测算法，该 算法通过对消息延迟的历史记录进行分析、计算之后得到一个超时值，这个超 时值随着实际消息延迟的变化而变化，具有较强的自适应性。另外，本文提出 的算法，可以通过设置参数的大小来满足不同应用的q o s 需求，并在保证检测 准确性和检测完整性的前提下缓解了网络延迟对失效检测的影响。 论文的主要工作及成果如下： 本文在对现有自适应失效检测算法研究、分析的基础上，提出了一种基于 消息延迟预测的自适应失效检测模型，论证了该失效检测模型所满足的失效检 测级别，针对该失效检测模型进行了模拟实验，对实验结果进行了性能分析， 并在模拟实验中将本文提出的自适应失效检测算法与经典的自适应失效检测算 法进行了性能比较。 论文各章节的组织结构如下： 第1 章，绪论。在对分布式应用系统的发展背景进行阐述的基础上，对提高 分布式应用系统可用性的关键技术进行了介绍，并对失效检测技术的研究现状 和研究重点进行了重点介绍，最后，介绍了本文的主要研究内容，并给出了论 文各章节的组织结构。 第2 章，失效检测技术的理论基础。首先对分布式应用系统的模型及故障模 型进行了分类描述，然后给出了失效检测器的定义，对失效检测级别进行了分 类介绍，并结合失效检测级别对失效检测器进行了分类。 第3 章，失效检测算法分析。首先对现有的失效检测技术进行了描述，并对 其进行了对比分析；然后对当前常用的失效检测算法进行了分类讨论，在总结 传统失效检测算法不足的基础上，引出了自适应失效检测算法，并对当前流行 的自适应失效检测算法进行了介绍；最后