1、1基于三次检测模式的故障检测算法研究摘要：本文在传统故障算法的基础上，提出了一种基于三次检测模式的故障检测算法。利用平滑历史检测点逼近检测时间；根据历史误判情况分析，动态调整二次检测时间；通过在定时器超时后向被检测点发送咨询消息的方式减少由于网络丢包等情况使得心跳消息不可达而造成的误判。通过三次检测模式，提高了异构分布式网络环境下失效检测算法的自适应性。通过对比实验，验证了在分布式系统实现检测应用中，利用三次检测模式的故障检测算法能有效提高检测算法的准确性和自适应性。关键词：异构分布式系统；故障检测；自适应性；三次检测模式1 引言随着计算机和网络技术的飞速发展，分布式系统已经渗入到许多领域。其
2、中一些关键领域，如作战指挥控制、航空航天等，对分布式系统的可靠性提出了更高的要求，容错技术是提高系统可靠性的一种有效手段。容错技术涉及到故障检测以及故障恢复等技术，而故障检测是提高系统可靠性的基础。为了更好地权衡故障检测算法的性能，Chandra 和Toueg 提出了故障检测器的两个基本属性：完整性（Completeness）和精确性（Accuracy） 1。其中，完整性刻画了故障检测器怀疑一个出现故障的处理器的能力，而精确性则体现了故障检测器不会去怀疑一个工作正常的处理器的能力。完整性和精确性是衡量失效检测算法优劣的关2键指标。目前针对故障检测算法的研究大都是基于超时机制的。检测点与被检测点
3、之间周期性地发送测试消息，并启动超时定时器作为下一个周期的检测点。根据定时器超时前是否收到检测消息判定被检测点是否发生故障。因此超时时限的设定是影响给故障检测算法的关键因素。传统故障检测算法并没有考虑异构分布式环境的多变性，超时时限的设定过于简单。为了提高故障检测算法的自适应性，本文提出了一种利用三次检测模式的故障检测算法。2 故障检测算法故障检测算法是分布式系统容错技术的基础，Metze2等人在 1967年率先提出了基于图理论模型的故障检测分析方法，以后的故障检测器的分析大都在此模型基础上进行的。2.1 故障检测机制目前的故障检测算法大都是基于超时机制的。超时机制的实现方式有两种。一种是基于
4、请求应答模式的；一种是基于心跳模式的。图21 给出了基于请求应答模式的简单示意图。其中，节点 p 需要了解q 的状态，节点 p 每个 T 时间向节点 q 送请求，并启动定时器 T，如果节点 p 在 T 时间内没有收到节点 q 的应答信息，则节点 p 就认定节点 q 出现故障。该模式是通过检测节点向被检测节点发送状态咨询测试消息的方式完成状态检测的。图 22 给出了基于心跳模式超时机制的简单示意图。其中，节点 p 为监控节点，节点 q 为被监控节点。被监控节点 p 周3期性地向监控节点 q 发送自己的心跳消息，监控节点 p 如果在时间间隔T 内没有收到节点 q 的心跳消息，则判定节点 q 出现故
5、障。该模式是通过被检测节点周期性地向检测节点发送自己的状态信息来通告自己仍然存活。2.2 传统故障检测算法假定系统中存在两个节点进程 p 和 q，进程 p 负责监控进程 q 的状态。考虑采用请求应答模式，传统故障检测算法的基本思想是：进程 p 以固定的时间间隔周期性地向进程 q 发送咨询信息，询问进程 q 的状态，同时启动超时定时器。进程 q 收到咨询信息后会向进程 p 发送应答信息，告之自己仍然存活。进程 p 根据在定时器超时之前能否收到进程 q 的应答消息来判定进程 q 是否存活。如果判定未存活，则停止发送咨询信息，并怀疑进程 q。由于异构分布式网络环境的多变性，很可能会造成两个节点进程之
6、间网络延迟或丢包等现象。因此，利用传统故障检测算法实现故障检测存在以下缺陷：1）固定超时时限。根据分布式系统节点之间消息传递时延的差异，分布式系统可以分为：同步系统、异步系统和部分同步系统。同步系统中节点之间传递消息的时延存在一个固定的上限，因此在同步模型中把超时时限设定为固定的上限可以有效地检测节点是否失效。异构系统中节点之间的通信是不同步的，因此不存在一个真正有效的固定时限。而Chandra 和 Toueg 已经证明了在绝对异步的系统中设计一个可靠的故障检测器是不可能的。部分同步系统中节点之间消息传递的延时存在上限但4是不固定且是未知的，在该模型下，采用固定超时时限的方式也是不合理的。由于
7、绝对同步的系统式理想化的，因此传统故障检测算法采用的固定超时时限的方式仅有理论研究的意义并没有实际应用的价值。2）自适应性差。在异构分布式环境下，节点之间通信延迟和丢包现象时有发生。传统故障检测算法由于采用了固定超时时限的方式，因此在这些情况下会直接判定节点发生故障，进而发生误判。3 基于三次检测模式的故障检测算法3.1 算法模式的提出传统故障检测算法具有自适应性差的缺点。故障检测算法的自适应能力主要指故障检测算法能够根据异构分布式网络环境的多变性动态调整检测策略，使得在节点之间传递消息时即便出现了网络延迟或丢包现象也能提供检测算法性能上的保障。算法的性能主要取决于超时时限的选择上。理论情况下
8、，每个检测周期故障检测器的超时时限都刚好等于检测消息到达的时间，那么该故障检测器将没有检测延时，唯一的影响就是后续故障恢复的延时了。相对的，如果超时时限设置的过大，那么故障检测延时将会很高，同样对故障的恢复也会造成很大的影响；而如果超时时限设置的过小，就会频繁发生误判以及超时时限的不断调整影响整个故障检测器的可靠性。但是考虑到可能存在的网络延时以及丢包现象，要想精确获取每一次心跳消息的到达时间是不可能的，现在大部分的研究都是采用连续逼近的方法尽可能得逼近心跳消息到达的时刻。但是现有的连续逼近的方法非常简单并不能很好地适应真实的环境，比如一次偶然的丢包就可能造成系统发生误判。为了增加故障检测器的
9、自5适应能力，本文采用了三次检测模式。4 实验本文基于三次检测模型提出了一种故障检测算法，实验主要测试了相对数量和速度的错误判断。我们规定一次检测模型为 1D 算法，两次检测模型为 2D 算法，三次检测模型为 3D 算法。实验分析了 100 次循环中的检测算法测试结果。表 41 列出了三种不同算法的错误数和错误率。根据实验的结果分析和比较，三次检测模型的检测算法具有更高的精度和更好的自适应性。5 结论本文在传统故障检测算法基础上，提出了一种基于三次检测模式的故障检测算法。针对传统故障检测算法自适应能力差的缺点，本文给出了一种三次检测模型，该模型综合考虑了分布式异构系统网络环境多变的特点，通过采
10、用三次检测模式，算法可以有效地减少由于网络环境恶劣而造成网络延迟或丢包现象。通过仿真实验可以看出该算法在系统网络状况不佳的情况下可以有效地减少误判，与传统故障检测算法相比，在自适应性方面有很大的提高。参考文献1 Chandra TD， Toueg S. Unreliable Failure Detectors for Reliable Distributed SystemsJ. Journal of the ACM（JACM） ， 1996， 43 （2）： 225267.2 Preparata，P.F，Metze，et al.On the Connection 6Assignment Problem of Diagnosable SystemsJ.IEEE Transactions on Electronic Computers，1967，16 （6）： 848854.3 Allman M，Paxson V. On Estimating EndtoEnd Network Path PropertiesJ. Preceedings of ACM Sigcomm，Cambridge， Aug，1999，29 （4）作者简介：刘宗桃， 男，1979 年 8 月，籍贯：甘肃榆中，民族：汉，学历：硕士，学位：研究生，职称：讲师。
