一種自適應失效檢測算法的研究與應用

段文佳，劉曉潔

一種自適應失效檢測算法的研究與應用

段文佳，劉曉潔

(四川大學計算機學院，成都 610065)

失效檢測技術是保證容災備份系統(tǒng)高可用性的關鍵技術之一，但經典的自適應失效檢測算法失效檢測時間較長、誤判率較高。為此，提出一種基于指數(shù)分布的自適應失效檢測算法λ-FD，采用Push與Pull 2種心跳模式結合的方法實現(xiàn)算法的重查策略。實驗結果表明，λ-FD在閾值取0.68時性能較優(yōu)，失效檢測時間為1 339.5 ms，誤判率為0.055 7%，遠低于同等失效檢測時間下經典算法Φ-FD的15.19%和Chen-FD的24.92%。λ-FD在相同失效檢測時間下誤判率普遍低于經典的自適應失效檢測算法，相同誤判率時耗費的失效檢測時間較短，有效提高失效檢測的性能，更符合廣域網中災備系統(tǒng)的應用需求。

自適應；失效檢測；指數(shù)分布；容災備份；心跳；閾值

1 概述

失效檢測作為容錯領域的基本研究內容，也是實現(xiàn)容災系統(tǒng)高可用性的重要保障技術[1]。評判失效檢測算法性能的主要指標有失效檢測時間和誤判率[2]，失效檢測時間是指算法檢測到并判定一次失效所需耗費的時間，誤判率是指算法判斷錯誤的概率[3]。由于網絡環(huán)境的多變性和不可預測性，要想同時保證快速的檢測和小的誤判率是很困難的。為了滿足這種需求，出現(xiàn)了自適應失效檢測器，通過自動調節(jié)心跳發(fā)送周期和超時值來適應不斷變化的網絡狀況。

文獻[4]提出了一種簡單的自適應失效檢測機制，通過統(tǒng)計到達的心跳消息的延遲，不斷獲得一個最大的延遲值作為超時的上限值來實現(xiàn)自適應失效檢測，其檢測時間受網絡時延波動影響較大。其后又出現(xiàn)了Chen-FD算法，算法根據(jù)歷史心跳消息來預測下一個心跳消息的到達時間[5]，并用一個固定修正值調整超時時間，這種算法的優(yōu)點是提供了一個較好的估計值來預測下一個心跳的到達時間。但是，固定的值不利于描述反映實時多變的廣域網環(huán)境，并且如果追求高準確性的話，可能會導致檢測時間變長。失效檢測器(Failure detector, Bertier-FD)是在Chen-FD的基礎上進行了改進[6]，根據(jù)往返時間的計算方法來計算修正值，使能夠隨著網絡狀況動態(tài)調整，從而在一定程度上提高了失效檢測器的檢測準確性，但是它不能很好地減少丟包所帶來的誤判。后來出現(xiàn)的Φ-FD算法[7-8]，假設心跳到達間隔服從正態(tài)分布，利用正態(tài)分布函數(shù)計算出時間之前心跳到達的概率，作為時刻的懷疑級別，然后與設定的閾值比較來判定進程是否失效。該算法實現(xiàn)了一個通用的失效檢測器，在一定程度上削弱了突發(fā)網絡狀況的不良影響。然而，正態(tài)分布并不是對心跳間隔分布的理想近似[9-10]，從而導致該算法的可靠度下降。

本文對現(xiàn)有的自適應失效檢測算法進行了研究和分析，提出一種基于指數(shù)分布的帶重查策略自適應失效檢測算法λ-FD。算法使用符合大多數(shù)網絡特征的指數(shù)分布[11-12]作為心跳到達間隔的分布假設，有效降低了平均失效檢測時間；采用Push與Pull方式結合實現(xiàn)的重查策略有效降低了誤判率。本文將該策略應用于廣域網環(huán)境中容災系統(tǒng)實現(xiàn)雙機熱備時的主機失效檢測中，在保證檢測準確性和完整性的前提下減少網絡時延突變和高丟包率對主機失效檢測的影響，降低誤判率。

2 失效檢測算法λ-FD

2.1 失效檢測算法λ-FD描述

在實際網絡環(huán)境中，影響心跳信息到達時間的主要因素是網絡時延和網絡丟包。同時，網絡狀況實時多變，時延和丟包隨機發(fā)生。為了更好地描述隨機的心跳信息到達時間間隔，設計了一個基于指數(shù)分布描述帶重查策略的隨時間變化輸出懷疑度的自適應失效檢測算法。

本文用閾值表示用戶對失效檢測的準確性期望，∈(0, 1)，當對失效檢測的準確性要求較高時，取較大的值；當對失效檢測的速度要求較高時，取較小的值。算法在等待心跳消息時會計算出當前時刻的失效懷疑度。當超過閾值時就懷疑主機失效，觸發(fā)重查，二次懷疑失效后判定失效。進行失效檢測的主機和備機不需要建立永久鏈接，因此，可以使用UDP連接實現(xiàn)通信。假設主機和備機的時間是同步的。算法模型如圖1所示。

圖1 λ-FD算法模型

因為討論的是失效檢測算法對主機的監(jiān)測，所以假設備機一直正確運行。檢測過程如下：

(1)主機以固定周期Δ向備機上的失效檢測器發(fā)送心跳消息M(∈(1,)，取正整數(shù)，以下均相同)，發(fā)送形式為服從UDP協(xié)議的數(shù)據(jù)包。消息內容應當包含編號，且編號是遞增的。

(2)心跳M到達備機的時刻記錄為T，當前時刻記為。閾值對應的超時檢測時間記為_。心跳M到達時間間隔則記為′，滿足′=T－T－1。是′的平均值。失效檢測器維護一個滑動窗口，大小為，每當有新的消息到達時就更新值。失效懷疑度滿足：

(3)初始化：設置T0=0，F(xiàn)lag=Active，=0。

(4)等待心跳消息M+1，如果當前Flag==Active，算法輸入－T，經式(1)計算后輸出當前時刻懷疑度，若≥，跳轉第(5)步，否則繼續(xù)運行直到心跳到達，記錄其到達時間，更新，并等待下一次心跳，轉回第(4)步；如果當前Flag=Suspense，等待2×，若無心跳到達跳轉第(5)步，否則有心跳到達則記錄其到達時間，更新，重置Flag= Active，轉回第(4)步。

(5)若當前Flag==Active，則標記Flag為Suspense，由備機向主機發(fā)送一條要求立即反饋的消息，跳轉到第(4)步；若當前Flag==Suspense，算法終止，由備機啟動切換接管程序，算法最終判定主機失效，由備機接管繼續(xù)工作。

2.2 基于λ-FD算法的雙機熱備系統(tǒng)

災備系統(tǒng)中的雙機熱備就是對于災備服務，提供2臺災備服務器共同執(zhí)行同一任務，以冗余提高系統(tǒng)可靠性[13]。當一臺災備服務器出現(xiàn)故障時，另一臺可以發(fā)現(xiàn)故障并接管故障服務器，代替其繼續(xù)提供服務，以此實現(xiàn)無人工值守干預情況下，能保證系統(tǒng)自動持續(xù)的提供服務。雙機熱備中常見的失效檢測模型是采用基于Active/Standby方式的服務器熱備，2臺服務器通過軟件保持數(shù)據(jù)實時同步。在同一時間內只有一臺服務器(主機)保持Active狀態(tài)，另一臺備份服務器(備機)處于監(jiān)控準備狀態(tài)。雙機之間心跳消息的發(fā)送采用Pull模式。這個模型由于失效檢測器本身采用簡單的二元狀態(tài)，不夠靈活，從而導致誤判率較高，同時網絡延遲和丟包對系統(tǒng)影響明顯，不能很好地適用于廣域網。

本文對這種基于Active/Standby方式的失效檢測器進行了改進，模型示意圖如圖2所示。改進后的模型是基于Active/Suspense/Standby方式，心跳消息發(fā)送模式采用push與pull相結合，添加了重查策略。由主機向備機發(fā)送消息，當主機第一次由λ-FD判斷其懷疑失效后，并不馬上讓備機接管，而是將主機標記為Suspense狀態(tài)，并由備機向主機發(fā)送復查消息，要求主機在收到此消息后立刻發(fā)送一個心跳至備機，若在Suspense狀態(tài)下經λ-FD算法檢測第二次懷疑主機失效，則立即由備機接管。期間在Suspense狀態(tài)下備機收到主機任意反饋消息都會重置主機為Active狀態(tài)。

圖2 改進后的雙機熱備模型

3 對比實驗

實驗對λ-FD算法的誤判率和平均錯誤檢測時間進行測試，并分析驗證算法對不同服務質量需求具有廣泛適用性。然后再從這兩方面與經典的自適應失效檢測算法進行對比，證明λ-FD算法在相同檢測時間下誤判率更低。

3.1 實驗環(huán)境與實驗數(shù)據(jù)

算法在模擬環(huán)境中測試。使用2臺處于同一局域網的機器作為主機與備機，主備機相互通信時在本地產生一定的延遲來模擬互聯(lián)網中的網絡延遲，延遲數(shù)據(jù)采集自廣域網，對百度網站進行Ping響應測試，歷時8 h，共采集約 6萬條數(shù)據(jù)，最小響應時間56 ms，最大響應時間3 463 ms，平均值99 ms，丟包率0.034%。從數(shù)據(jù)本身特點來看，滿足容災系統(tǒng)模型中網絡信息延遲與丟包的特點。在每個小時獲取的記錄數(shù)據(jù)中各隨機取2 000條記錄，共16 000條作為心跳信息依次的延遲時間，并取發(fā)送周期Δ=1 s，滑動窗口=1 000，對算法進行測試。心跳記錄分布如圖3所示。

圖3 心跳信息的時延數(shù)據(jù)分布

3.2 實驗結果

閾值大小對λ-FD算法的誤判率、平均失效檢測時間的影響如圖4、圖5所示。

圖4 閾值對誤判率的影響

圖5 閾值對失效檢測時間的影響

λ-FD算法與經典算法Φ-FD、Chen-FD的對比結果如圖6所示。

圖6 λ-FD算法與經典算法的對比

3.3 實驗分析

從圖4和圖5中可以看出，閾值取值越大，誤判率越低，且檢測時間越來越長。實驗結果與理論分析相符，證明該算法能根據(jù)不同的QoS靈活設置閾值，具有廣泛的適用性。閾值取值0.4左右時，隨著閾值增大，誤判率發(fā)生顯著下降變化，這是由于此時心跳間隔均值約等于2×，即重查策略的等待時間。對于很多突發(fā)的延遲或者丟包，此時觸發(fā)重檢的信息恰好能規(guī)定等待時間內到達，隨著閾值增大，也增大，重查的成功率也會增大，誤判率下降。閾值在0.65附近時，誤判率會明顯趨于平穩(wěn)并緩慢下降。此時閾值對應的檢測時間約等于心跳間隔均值。隨著閾值的增大，超時上限進一步增大，大部分數(shù)據(jù)不會被懷疑失效和觸發(fā)重查，誤判率會下降。實驗數(shù)據(jù)分析表明，閾值取值0.68附近時，誤判率較低且失效檢測時間仍然處于比較低的水平，算法性能接近最優(yōu)，此時λ-FD的誤判率為0.055 7%，失效檢測時間約為1 339.5 ms。

圖6實驗結果對比說明，在相同的錯誤檢測時間下，λ-FD算法比經典算法Φ-FD和Chen-FD(NFD-E)普遍具有更低的誤判率，而誤判率相同時λ-FD算法耗費較少的錯誤檢測時間完成檢測。在λ-FD算法性能最優(yōu)時對比優(yōu)勢最明顯，失效檢測時間同為1 339 ms時Φ-FD的誤判率為15.19%，Chen-FD的誤判率為24.92%，均高于λ-FD算法的誤判率0.055 7%；而Φ-FD和Chen-FD算法達到0.05%這一數(shù)級誤判率時，對應的失效檢測時間分別是1 750 ms和2 000 ms，均高于λ-FD算法的1 339 ms。實驗充分證明了λ-FD算法建立在Active/Suspense/Standby三態(tài)轉換模型上的重查機制有效降低了誤判率?；谥笖?shù)分布計算懷疑度使得平均錯誤檢測時間得以維持在較低水平，克服了經典算法檢測不夠靈活、誤判率較高的缺點，優(yōu)化了災備系統(tǒng)的可用性。

4 結束語

本文提出了一種能適應廣域網環(huán)境高時延，丟包頻繁特點的自適應失效檢測算法λ-FD，并應用于廣域網環(huán)境下的容災備份系統(tǒng)中。實驗結果證明，和經典自適應失效檢測算法相比，λ-FD算法在相同失效檢測時間內具有更低的誤判率，并且能在較少的時間代價下，使得誤判率更進一步地快速下降，并最終維持在更低的水平。下一步的主要研究內容為使用動態(tài)閾值進一步提高自適應性。

[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]. 計算機研究與發(fā)展, 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－)，男，碩士研究生，主研方向：數(shù)據(jù)存儲，容災抗毀；劉曉潔，副教授。

2013-03-20

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

10.3969/j.issn.1000-3428.2014.03.064