段文佳，劉曉潔

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

段文佳，劉曉潔

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

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

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

1 概述

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

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

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

2 失效檢測(cè)算法λ-FD

2.1 失效檢測(cè)算法λ-FD描述

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

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

圖1 λ-FD算法模型

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

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

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

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

(4)等待心跳消息M+1，如果當(dāng)前Flag==Active，算法輸入－T，經(jīng)式(1)計(jì)算后輸出當(dāng)前時(shí)刻懷疑度，若≥，跳轉(zhuǎn)第(5)步，否則繼續(xù)運(yùn)行直到心跳到達(dá)，記錄其到達(dá)時(shí)間，更新，并等待下一次心跳，轉(zhuǎn)回第(4)步；如果當(dāng)前Flag=Suspense，等待2×，若無(wú)心跳到達(dá)跳轉(zhuǎn)第(5)步，否則有心跳到達(dá)則記錄其到達(dá)時(shí)間，更新，重置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ī)啟動(dòng)切換接管程序，算法最終判定主機(jī)失效，由備機(jī)接管繼續(xù)工作。

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

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

本文對(duì)這種基于Active/Standby方式的失效檢測(cè)器進(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ā)送一個(gè)心跳至備機(jī)，若在Suspense狀態(tài)下經(jīng)λ-FD算法檢測(cè)第二次懷疑主機(jī)失效，則立即由備機(jī)接管。期間在Suspense狀態(tài)下備機(jī)收到主機(jī)任意反饋消息都會(huì)重置主機(jī)為Active狀態(tài)。

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

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

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

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

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

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

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

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

圖4 閾值對(duì)誤判率的影響

圖5 閾值對(duì)失效檢測(cè)時(shí)間的影響

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

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

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

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

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

4 結(jié)束語(yǔ)

本文提出了一種能適應(yīng)廣域網(wǎng)環(huán)境高時(shí)延，丟包頻繁特點(diǎn)的自適應(yīng)失效檢測(cè)算法λ-FD，并應(yīng)用于廣域網(wǎng)環(huán)境下的容災(zāi)備份系統(tǒng)中。實(shí)驗(yàn)結(jié)果證明，和經(jīng)典自適應(yīng)失效檢測(cè)算法相比，λ-FD算法在相同失效檢測(cè)時(shí)間內(nèi)具有更低的誤判率，并且能在較少的時(shí)間代價(jià)下，使得誤判率更進(jìn)一步地快速下降，并最終維持在更低的水平。下一步的主要研究?jī)?nèi)容為使用動(dòng)態(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)格失效檢測(cè)器[J]. 軟件學(xué)報(bào), 2006, 17(11): 2362-2372.

[3] 陳寧江, 魏 峻, 楊 波, 等. Web應(yīng)用服務(wù)器的適應(yīng)性失效檢測(cè)[J]. 軟件學(xué)報(bào), 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)故障檢測(cè)框架研究[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

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

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

2013-03-20

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

10.3969/j.issn.1000-3428.2014.03.064