段文佳，劉曉潔

一種自適應(yīng)失效檢測算法的研究與應(yīng)用

段文佳，劉曉潔

(四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

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

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

1 概述

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

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

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

2 失效檢測算法λ-FD

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

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

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

圖1 λ-FD算法模型

因?yàn)橛懻摰氖鞘z測算法對主機(jī)的監(jiān)測，所以假設(shè)備機(jī)一直正確運(yùn)行。檢測過程如下：

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

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

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

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

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

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

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

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

圖2 改進(jìn)后的雙機(jī)熱備模型

3 對比實(shí)驗(yàn)

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

圖4 閾值對誤判率的影響

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

λ-FD算法與經(jīng)典算法Φ-FD、Chen-FD的對比結(jié)果如圖6所示。

圖6 λ-FD算法與經(jīng)典算法的對比

3.3 實(shí)驗(yàn)分析

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

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

4 結(jié)束語

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

[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的自適應(yīng)網(wǎng)格失效檢測器[J]. 軟件學(xué)報, 2006, 17(11): 2362-2372.

[3] 陳寧江, 魏 峻, 楊 波, 等. Web應(yīng)用服務(wù)器的適應(yīng)性失效檢測[J]. 軟件學(xué)報, 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] 張世武, 吳月華, 楊 杰, 等. 基于信息尋覓智能體的網(wǎng)絡(luò)用戶瀏覽模式研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(11): 1966-1973.

[13] 毛秀清, 陳性元, 楊英杰, 等. 面向容災(zāi)的自適應(yīng)故障檢測框架研究[J]. 計(jì)算機(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

國家自然科學(xué)基金資助項(xiàng)目(61173159)；教育部重大項(xiàng)目培育基金資助項(xiàng)目(708075)。

段文佳(1988－)，男，碩士研究生，主研方向：數(shù)據(jù)存儲，容災(zāi)抗毀；劉曉潔，副教授。

2013-03-20

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

10.3969/j.issn.1000-3428.2014.03.064