一种自适应失效检测算法的研究与应用

段文佳，刘晓洁

一种自适应失效检测算法的研究与应用

段文佳，刘晓洁

(四川大学计算机学院，成都 610065)

失效检测技术是保证容灾备份系统高可用性的关键技术之一，但经典的自适应失效检测算法失效检测时间较长、误判率较高。为此，提出一种基于指数分布的自适应失效检测算法λ-FD，采用Push与Pull 2种心跳模式结合的方法实现算法的重查策略。实验结果表明，λ-FD在阈值取0.68时性能较优，失效检测时间为1 339.5 ms，误判率为0.055 7%，远低于同等失效检测时间下经典算法Φ-FD的15.19%和Chen-FD的24.92%。λ-FD在相同失效检测时间下误判率普遍低于经典的自适应失效检测算法，相同误判率时耗费的失效检测时间较短，有效提高失效检测的性能，更符合广域网中灾备系统的应用需求。

自适应；失效检测；指数分布；容灾备份；心跳；阈值

1 概述

失效检测作为容错领域的基本研究内容，也是实现容灾系统高可用性的重要保障技术[1]。评判失效检测算法性能的主要指标有失效检测时间和误判率[2]，失效检测时间是指算法检测到并判定一次失效所需耗费的时间，误判率是指算法判断错误的概率[3]。由于网络环境的多变性和不可预测性，要想同时保证快速的检测和小的误判率是很困难的。为了满足这种需求，出现了自适应失效检测器，通过自动调节心跳发送周期和超时值来适应不断变化的网络状况。

文献[4]提出了一种简单的自适应失效检测机制，通过统计到达的心跳消息的延迟，不断获得一个最大的延迟值作为超时的上限值来实现自适应失效检测，其检测时间受网络时延波动影响较大。其后又出现了Chen-FD算法，算法根据历史心跳消息来预测下一个心跳消息的到达时间[5]，并用一个固定修正值调整超时时间，这种算法的优点是提供了一个较好的估计值来预测下一个心跳的到达时间。但是，固定的值不利于描述反映实时多变的广域网环境，并且如果追求高准确性的话，可能会导致检测时间变长。失效检测器(Failure detector, Bertier-FD)是在Chen-FD的基础上进行了改进[6]，根据往返时间的计算方法来计算修正值，使能够随着网络状况动态调整，从而在一定程度上提高了失效检测器的检测准确性，但是它不能很好地减少丢包所带来的误判。后来出现的Φ-FD算法[7-8]，假设心跳到达间隔服从正态分布，利用正态分布函数计算出时间之前心跳到达的概率，作为时刻的怀疑级别，然后与设定的阈值比较来判定进程是否失效。该算法实现了一个通用的失效检测器，在一定程度上削弱了突发网络状况的不良影响。然而，正态分布并不是对心跳间隔分布的理想近似[9-10]，从而导致该算法的可靠度下降。

本文对现有的自适应失效检测算法进行了研究和分析，提出一种基于指数分布的带重查策略自适应失效检测算法λ-FD。算法使用符合大多数网络特征的指数分布[11-12]作为心跳到达间隔的分布假设，有效降低了平均失效检测时间；采用Push与Pull方式结合实现的重查策略有效降低了误判率。本文将该策略应用于广域网环境中容灾系统实现双机热备时的主机失效检测中，在保证检测准确性和完整性的前提下减少网络时延突变和高丢包率对主机失效检测的影响，降低误判率。

2 失效检测算法λ-FD

2.1 失效检测算法λ-FD描述

在实际网络环境中，影响心跳信息到达时间的主要因素是网络时延和网络丢包。同时，网络状况实时多变，时延和丢包随机发生。为了更好地描述随机的心跳信息到达时间间隔，设计了一个基于指数分布描述带重查策略的随时间变化输出怀疑度的自适应失效检测算法。

本文用阈值表示用户对失效检测的准确性期望，∈(0, 1)，当对失效检测的准确性要求较高时，取较大的值；当对失效检测的速度要求较高时，取较小的值。算法在等待心跳消息时会计算出当前时刻的失效怀疑度。当超过阈值时就怀疑主机失效，触发重查，二次怀疑失效后判定失效。进行失效检测的主机和备机不需要建立永久链接，因此，可以使用UDP连接实现通信。假设主机和备机的时间是同步的。算法模型如图1所示。

图1 λ-FD算法模型

因为讨论的是失效检测算法对主机的监测，所以假设备机一直正确运行。检测过程如下：

(1)主机以固定周期Δ向备机上的失效检测器发送心跳消息M(∈(1,)，取正整数，以下均相同)，发送形式为服从UDP协议的数据包。消息内容应当包含编号，且编号是递增的。

(2)心跳M到达备机的时刻记录为T，当前时刻记为。阈值对应的超时检测时间记为_。心跳M到达时间间隔则记为´，满足´=T－T－1。是´的平均值。失效检测器维护一个滑动窗口，大小为，每当有新的消息到达时就更新值。失效怀疑度满足：

(3)初始化：设置T0=0，Flag=Active，=0。

(4)等待心跳消息M+1，如果当前Flag==Active，算法输入－T，经式(1)计算后输出当前时刻怀疑度，若≥，跳转第(5)步，否则继续运行直到心跳到达，记录其到达时间，更新，并等待下一次心跳，转回第(4)步；如果当前Flag=Suspense，等待2×，若无心跳到达跳转第(5)步，否则有心跳到达则记录其到达时间，更新，重置Flag= Active，转回第(4)步。

(5)若当前Flag==Active，则标记Flag为Suspense，由备机向主机发送一条要求立即反馈的消息，跳转到第(4)步；若当前Flag==Suspense，算法终止，由备机启动切换接管程序，算法最终判定主机失效，由备机接管继续工作。

2.2 基于λ-FD算法的双机热备系统

灾备系统中的双机热备就是对于灾备服务，提供2台灾备服务器共同执行同一任务，以冗余提高系统可靠性[13]。当一台灾备服务器出现故障时，另一台可以发现故障并接管故障服务器，代替其继续提供服务，以此实现无人工值守干预情况下，能保证系统自动持续的提供服务。双机热备中常见的失效检测模型是采用基于Active/Standby方式的服务器热备，2台服务器通过软件保持数据实时同步。在同一时间内只有一台服务器(主机)保持Active状态，另一台备份服务器(备机)处于监控准备状态。双机之间心跳消息的发送采用Pull模式。这个模型由于失效检测器本身采用简单的二元状态，不够灵活，从而导致误判率较高，同时网络延迟和丢包对系统影响明显，不能很好地适用于广域网。

本文对这种基于Active/Standby方式的失效检测器进行了改进，模型示意图如图2所示。改进后的模型是基于Active/Suspense/Standby方式，心跳消息发送模式采用push与pull相结合，添加了重查策略。由主机向备机发送消息，当主机第一次由λ-FD判断其怀疑失效后，并不马上让备机接管，而是将主机标记为Suspense状态，并由备机向主机发送复查消息，要求主机在收到此消息后立刻发送一个心跳至备机，若在Suspense状态下经λ-FD算法检测第二次怀疑主机失效，则立即由备机接管。期间在Suspense状态下备机收到主机任意反馈消息都会重置主机为Active状态。

图2 改进后的双机热备模型

3 对比实验

实验对λ-FD算法的误判率和平均错误检测时间进行测试，并分析验证算法对不同服务质量需求具有广泛适用性。然后再从这两方面与经典的自适应失效检测算法进行对比，证明λ-FD算法在相同检测时间下误判率更低。

3.1 实验环境与实验数据

算法在模拟环境中测试。使用2台处于同一局域网的机器作为主机与备机，主备机相互通信时在本地产生一定的延迟来模拟互联网中的网络延迟，延迟数据采集自广域网，对百度网站进行Ping响应测试，历时8 h，共采集约 6万条数据，最小响应时间56 ms，最大响应时间3 463 ms，平均值99 ms，丢包率0.034%。从数据本身特点来看，满足容灾系统模型中网络信息延迟与丢包的特点。在每个小时获取的记录数据中各随机取2 000条记录，共16 000条作为心跳信息依次的延迟时间，并取发送周期Δ=1 s，滑动窗口=1 000，对算法进行测试。心跳记录分布如图3所示。

图3 心跳信息的时延数据分布

3.2 实验结果

阈值大小对λ-FD算法的误判率、平均失效检测时间的影响如图4、图5所示。

图4 阈值对误判率的影响

图5 阈值对失效检测时间的影响

λ-FD算法与经典算法Φ-FD、Chen-FD的对比结果如图6所示。

图6 λ-FD算法与经典算法的对比

3.3 实验分析

从图4和图5中可以看出，阈值取值越大，误判率越低，且检测时间越来越长。实验结果与理论分析相符，证明该算法能根据不同的QoS灵活设置阈值，具有广泛的适用性。阈值取值0.4左右时，随着阈值增大，误判率发生显著下降变化，这是由于此时心跳间隔均值约等于2×，即重查策略的等待时间。对于很多突发的延迟或者丢包，此时触发重检的信息恰好能规定等待时间内到达，随着阈值增大，也增大，重查的成功率也会增大，误判率下降。阈值在0.65附近时，误判率会明显趋于平稳并缓慢下降。此时阈值对应的检测时间约等于心跳间隔均值。随着阈值的增大，超时上限进一步增大，大部分数据不会被怀疑失效和触发重查，误判率会下降。实验数据分析表明，阈值取值0.68附近时，误判率较低且失效检测时间仍然处于比较低的水平，算法性能接近最优，此时λ-FD的误判率为0.055 7%，失效检测时间约为1 339.5 ms。

图6实验结果对比说明，在相同的错误检测时间下，λ-FD算法比经典算法Φ-FD和Chen-FD(NFD-E)普遍具有更低的误判率，而误判率相同时λ-FD算法耗费较少的错误检测时间完成检测。在λ-FD算法性能最优时对比优势最明显，失效检测时间同为1 339 ms时Φ-FD的误判率为15.19%，Chen-FD的误判率为24.92%，均高于λ-FD算法的误判率0.055 7%；而Φ-FD和Chen-FD算法达到0.05%这一数级误判率时，对应的失效检测时间分别是1 750 ms和2 000 ms，均高于λ-FD算法的1 339 ms。实验充分证明了λ-FD算法建立在Active/Suspense/Standby三态转换模型上的重查机制有效降低了误判率。基于指数分布计算怀疑度使得平均错误检测时间得以维持在较低水平，克服了经典算法检测不够灵活、误判率较高的缺点，优化了灾备系统的可用性。

4 结束语

本文提出了一种能适应广域网环境高时延，丢包频繁特点的自适应失效检测算法λ-FD，并应用于广域网环境下的容灾备份系统中。实验结果证明，和经典自适应失效检测算法相比，λ-FD算法在相同失效检测时间内具有更低的误判率，并且能在较少的时间代价下，使得误判率更进一步地快速下降，并最终维持在更低的水平。下一步的主要研究内容为使用动态阈值进一步提高自适应性。

[1] Chandra T D, Toueg S. Unreliable Failure Detectors for Reliable Distributed Systems[J]. Journal of the ACM, 1996, 43(2): 225-267.

[2] 董 剑, 左德承, 刘宏伟, 等. 一种基于QoS的自适应网格失效检测器[J]. 软件学报, 2006, 17(11): 2362-2372.

[3] 陈宁江, 魏 峻, 杨 波, 等. Web应用服务器的适应性失效检测[J]. 软件学报, 2005, 16(11): 1929-1938.

[4] Fetzer C, Raynal M, Tronel F. An Adaptive Failure Detection Protocol[C]//Proc. of the 8th Pacific Rim International Symposium on Dependable Computer. Washington D. C., USA: IEEE Press, 2001: 146-153.

[5] Chen Wei, Toueg S, Aguilera M K. On the Quality of Service of Failure Detectors[J]. IEEE Transactions on Computers, 2002, 51(5): 561-580.

[6] Bertier M, Marin O, Sens P. Implementation and Performance Evaluation of an Adaptable Failure Detector[C]//Proc. of the 15th International Conference on Dependable Systems and Networks. Bethesda, USA: IEEE Press, 2002: 354-363.

[7] Hayashibara N, Defago X, Yared R, et al. The Φ Accrual Failure Detector[C]//Proc. of the 23rd International Sympo- sium on Reliable Distributed Systems. Washington D. C., USA: IEEE Computer Society, 2004: 66-78.

[8] Hayashibara N, Takizawa M. Performance Evaluation of the Φ Accrual Failure Detector[C]//Proc. of the 26th International Conference on Distributed Computing Systems Workshops. [S. l.]: IEEE Press, 2006: 46.

[9] Bhole Y, Popescu A. Measurement and Analysis of HTTP Traffic[J]. Journal of Network and Systems Management, 2005, 13(4): 357-370.

[10] Golmie N, Rebala O. Bluetooth Adaptive Techniques to Mitigate Interference[C]//Proc. of the Global Telecommunications Conference. Piscataway, USA: IEEE Press, 2003: 405-409.

[11] Teng W, Chang C, Chen M. Integrating Web Caching and Web Prefetching in Client-side Proxies[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(5): 444-454.

[12] 张世武, 吴月华, 杨 杰, 等. 基于信息寻觅智能体的网络用户浏览模式研究[J]. 计算机研究与发展, 2004, 41(11): 1966-1973.

[13] 毛秀清, 陈性元, 杨英杰, 等. 面向容灾的自适应故障检测框架研究[J]. 计算机工程, 2012, 38(7): 4-6

编辑 顾逸斐

Study and Application of an Adaptive Failure Detection Algorithm

DUAN Wen-jia, LIU Xiao-jie

(School of Computer, Sichuan University, Chengdu 610065, China)

Failure detection is one of the crucial techniques to promise the disaster recovery system’s serviceability, and classical adaptive failure detection algorithm has the shortage of long failure detection time and high error rate. For this problem, this paper studies an adaptive failure detection algorithm λ-FD, based on exponential distribution. Simultaneously, λ-FD combines Pull heartbeat and Push heartbeat to achieve re-check. Experimental results show that λ-FD has the optimal performance when it sets the threshold to 0.68, the failure detection time to 1 339.5 ms and the error rate to 0.055 7%, and the latter is much lower than the error rate of Φ-FD, 15.19%, and the error rate of Chen-FD, 24.92%. So the error rate of λ-FD is generally lower than the classical algorithms which have the same failure detection time, and λ-FD takes the shortest failure detection time if its error rate is the same with classical algorithm, λ-FD can better adapt to the disaster recovery system in the Wide Area Network(WAN).

adaptive; failure detection; exponential distribution; disaster recovery; heartbeat; threshold

1000-3428(2014)03-0303-03

A

TP301.6

国家自然科学基金资助项目(61173159)；教育部重大项目培育基金资助项目(708075)。

段文佳(1988－)，男，硕士研究生，主研方向：数据存储，容灾抗毁；刘晓洁，副教授。

2013-03-20

2013-04-21 E-mail：lxtxdwj@163.com

10.3969/j.issn.1000-3428.2014.03.064