劉家希，吳智博，董 劍，溫東新

（哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱150001）

0 引 言

分布式系統(tǒng)（Distributed System）是一個硬件或者軟件分布在不同的網(wǎng)絡計算機上，彼此之間僅僅通過消息傳遞進行通信和協(xié)調的系統(tǒng)［1］。目前，分布式系統(tǒng)可以說是無所不在，無論商業(yè)、學界、政府部門或者是家庭之中均能看到其身影。這些分布式系統(tǒng)提供共享資源、共享數(shù)據(jù)的技術手段，在這個信息化的時代是極其重要的［2］。然而，隨著分布式系統(tǒng)規(guī)模的不斷增長以及復雜性的不斷增加，由于各種原因造成的軟硬件失效已然不可避免，這就在相當程度上決定了分布式系統(tǒng)可用性的好壞。容錯技術是分布式系統(tǒng)中保證高可用性的有效方法［3］，可以使系統(tǒng)在有部分硬件或者軟件發(fā)生失效的情況下，仍可作為整體能夠正常運行并完成其設計功能。而失效檢測器是容錯技術實現(xiàn)的前提，通過周期性地探測系統(tǒng)中節(jié)點的狀態(tài)，可以為系統(tǒng)容錯提供良好的信息支持。因此，失效檢測器的性能直接影響分布式系統(tǒng)的正常運行。

目前，失效檢測器的研究主要集中在失效檢測器理論模型與失效檢測算法的實現(xiàn)兩個方面?？偟貋碚f，在失效檢測器理論模型方面，Chandra等人［4］首次提出了失效檢測器的理論，并且根據(jù)完整性與準確性定義了8種類型的失效檢測器，同時指出了解決分布式一致性問題最弱的失效檢測器模型。在此基礎上，陸續(xù)有學者針對不同的分布式系統(tǒng)模型提出不同能力的失效檢測器模型。而在失效檢測器的實現(xiàn)方面，針對失效檢測所面臨的檢測準確性、速度以及負載的矛盾，自適應失效檢測器和基于結果共享機制的失效檢測器也屢獲提出，并相繼問世。這些失效檢測器以不同的側重點解決了實際分布式系統(tǒng)中對失效檢測服務的需求設計問題。

本文以失效檢測器的實現(xiàn)為重點分析對象，并將從如下方面展開論述：首先，提出失效檢測器定義、實現(xiàn)以及服務質量評價指標。其次，研究了不同種類的失效檢測器。最后，對分布式系統(tǒng)中失效檢測器做出總結與展望。

1 失效檢測器模型

1.1 失效檢測器定義

Chandra等人［4］最早提出了失效檢測器的理論。在該理論中，分布式系統(tǒng)中每個節(jié)點都有一個本地的失效檢測器，用于檢測系統(tǒng)中的部分節(jié)點并且維護一張懷疑節(jié)點發(fā)生失效的列表。失效檢測器可能會錯誤地將正常運行的節(jié)點加入到懷疑列表中，但當發(fā)現(xiàn)錯誤懷疑時，又可以把該節(jié)點從懷疑列表中直接刪除，這個過程可以重復進行。任意2個節(jié)點的失效檢測器對相同的節(jié)點可能有不同的檢測結果。

失效檢測器形式化的定義可表述為：在一個由n個節(jié)點組成的分布式系統(tǒng)Π中，F(xiàn)被稱為失效模式，F(xiàn)：T→2Π。其中，T是全局時鐘到自然計數(shù)的一個映射。 對于Π中的節(jié)點p，則用crash（F）＝Ut∈TF（t）定義發(fā)生失效的節(jié)點集合，correct（F）＝Π-F（t） 定義被判斷為正確的節(jié)點集合。

一個失效檢測器（Failure Detector，F(xiàn)D）可視作為一組失效檢測模塊的集合，分布在系統(tǒng)的每一個節(jié)點上，而失效檢測器的輸出就是被懷疑發(fā)生失效的節(jié)點的集合，可以用H來表示，Π×T→2Π，H（p，t）則表示節(jié)點p在t時刻所認為發(fā)生失效的節(jié)點集合。

1.2 失效檢測器的實現(xiàn)

當前失效檢測方法的實現(xiàn)大多數(shù)都是基于心跳機制的。通過判斷被檢測節(jié)點發(fā)出的消息能否在規(guī)定時間內到達，從而判定被檢測節(jié)點是否發(fā)生失效。按照實現(xiàn)方式的不同，可以分為 PUSH模型［5］和PULL模型［1］，其它的失效檢測方法都是建立在這2種失效檢測方法之上。現(xiàn)對這2種方法將給出如下闡釋與分析。

（1）在基于PUSH模型的失效檢測方法中，被檢測節(jié)點是主動的參與者，檢測方法的基礎工作方式如圖1所示。由圖1看到，被檢測節(jié)點p周期性地發(fā)送“I am alive”消息到失效檢測器，這種消息也稱為心跳消息。失效檢測器會設置一個超時值Δt，如果失效檢測器在超時值Δt前沒有收到被檢測節(jié)點發(fā)送的消息，則懷疑被檢測節(jié)點發(fā)生失效。由于PUSH模型在系統(tǒng)內是單方向的消息傳輸，使其可獲得較高傳輸效率。同時如果被檢測節(jié)點有多個檢測者，可以使用硬件的多播機制來實現(xiàn)。但是，PUSH模型需要被檢測節(jié)點維護本地時鐘以便周期性地發(fā)送消息。

圖1 PUSH模型Fig.1 PUSH model

（2）在基于PULL模型的失效檢測方法中，被檢測節(jié)點是被動的參與者，檢測方法的基礎工作方式如圖2所示。失效檢測器周期性地發(fā)送“Are you alive”查詢消息到被檢測節(jié)點，并且設置一個超時值Δt。 如果被檢測節(jié)點在超時值Δt前回復應答消息“Yes”，則失效檢測器判定其處于正常狀態(tài)；否則，失效檢測器懷疑其發(fā)生失效。由于被檢測節(jié)點在PULL模型中是被動參與者，所以失效檢測器更容易實現(xiàn)。而且，這些被檢測節(jié)點只需要在有詢問消息時做出反應，不需要為了定期發(fā)送消息而維護當?shù)貢r鐘，可以在異步計算環(huán)境下運行。但是，采用PULL模型的失效檢測方法所需檢測消息是PUSH模型的2倍。

圖2 PULL模型Fig.2 PULL model

1.3 失效檢測器的服務質量

許多實際應用對失效檢測器所提供的節(jié)點懷疑信息有諸多限制，而且也無法接受過慢的或者輸出錯誤太多的失效檢測服務。針對這個問題，Chen等人［6］在失效檢測器理論模型的基礎上，提出了一套失效檢測器服務質量（Quality of Service，QoS）的評價指標體系，可以對失效檢測器性能進行定量評價。這套指標體系主要描述失效檢測器發(fā)現(xiàn)真實失效的速度以及避免錯誤懷疑的概率兩個方面。

為了理解Chen所創(chuàng)建的定量評價指標體系，需要明晰一些QoS關鍵指標含義。其中，T表示失效檢測器認為被檢測節(jié)點處于正常狀態(tài)，S表示失效檢測器認為被檢測節(jié)點處于失效狀態(tài)。T-transition表示失效檢測器的輸出結果由S變成T，S-transition表示失效檢測器的輸出結果由T變成S。詳情表述見如下。

（1）檢測時間TD：從節(jié)點發(fā)生失效的時刻到該節(jié)點被失效檢測器永久懷疑所持續(xù)的時間。也可以說，TD表示節(jié)點發(fā)生失效的時刻到最后一個S-transition發(fā)生的時刻（以后不會再發(fā)生transition）之間持續(xù)的時間，如圖3所示。

（2）錯誤間隔時間TMR：失效檢測器連續(xù)2次發(fā)生錯誤懷疑的間隔時間。也就是說，TMR表示從一個S-transition到下一個S-transition所經(jīng)歷的時間，如圖3所示。

圖3 QoS指標Fig.3 QoS metrics

（3）錯誤持續(xù)時間TM：失效檢測器改正一次錯誤懷疑所經(jīng)歷的時間。也就是說，TM表示從一個S-transition到下一個T-transition所經(jīng)歷的時間，如圖3所示。

2 失效檢測器的分類

失效檢測器不僅需要保證基本的失效檢測能力，也需要能夠保證失效檢測能力在可接受的服務質量范圍內。隨著大規(guī)模分布式系統(tǒng)的發(fā)展，就需要檢測大量的節(jié)點，較高概率的消息丟失、不斷變換的系統(tǒng)拓撲以及消息延遲的不可預測性等問題不斷涌現(xiàn)。這些情況對于研究開發(fā)高效的失效檢測器提出了巨大的挑戰(zhàn)，加劇了失效檢測有效性（失效檢測準確性和失效檢測速度）和失效檢測所需負載的矛盾。而自適應失效檢測與結果共享機制是當前解決這一問題的主要途徑。因而圍繞這2個方面，針對當前大規(guī)模分布式系統(tǒng)失效檢測技術的研究可做綜合分析與詳述如下。

2.1 自適應于網(wǎng)絡環(huán)境的失效檢測器

在早期的自適應失效檢測器的研究中，通過調整心跳消息發(fā)送間隔η和超時值Δt來適應網(wǎng)絡環(huán)境的變化，從而在一定檢測速度的約束下，盡力提高檢測準確性。例如，Sotoma等人［7］提出了一種基于MEAN超時值預測方法的自適應失效檢測器，并且在CORBA系統(tǒng)中實現(xiàn)了這種自適應失效檢測器。這種失效檢測器使用心跳傳輸時間的平均值作為超時值Δt的預測值，可以周期性地調整超時值Δt，從而達到了自適應失效檢測設計效果。Fetzer等人［8］提出了另一種基于MAX超時值預測方法的自適應失效檢測協(xié)議，通過利用歷史心跳消息的傳輸時間最大值作為超時值Δt的預測值，可以有效地改善失效檢測準確性。Falai等人［9］對這些超時值預測方法進行了總結與歸納，選取出5種超時值預測方法：LAST、MEAN、 WINMEAN（N）、LPF（β） 以及 ARIMA（p，d，q），分別為其配以不同的安全邊界（SMCI和SMJAC），并通過實驗的方法對其性能進行評價。實驗結果表明，ARIMA（p，d，q）方法具有較高的預測準確性，而具有較低算法復雜性的LAST方法結合SMJAC安全邊界則獲得了最快的檢測時間以及較好的檢測準確性。

上述這些方法對QoS的研究都停留在定性的階段，并不能夠精確地描述失效檢測器所能滿足的QoS，而且用戶也不能對失效檢測器提出定量的QoS需求。針對這一情況，Chen等人［6］提出了一整套失效檢測器的QoS評價指標體系。這套QoS指標體系主要是對失效檢測器的檢測速度以及準確性的衡量，實現(xiàn)了對失效檢測器的檢測能力的定量的評價。同時，基于以上QoS指標，Chen等人提出的自適應失效檢測器NFD-E可以根據(jù)用戶或者應用給定的QoS需求，自動地調整檢測參數(shù)，從而以最小的檢測負載獲得定量的QoS指標。針對NFD-E檢測器檢測速度的問題，Bertier等人［10］提出了一種基于動態(tài)安全邊界的失效檢測器。這種失效檢測器利用Jacobson的往返時間（round-trip time，RTT）來對安全邊界進行估計，使其可以隨網(wǎng)絡環(huán)境的變化進行動態(tài)改變，此方法明顯地降低了Δt值，提高了檢測速度。但是，這種改進后的NFD-E檢測器在檢測速度提高的同時帶來了更多的錯誤檢測。針對NFD-E檢測器檢測準確性的問題，Tomsic等人［11］提出了一種基于雙窗口的失效檢測器2W-FD。這種失效檢測器使用2個不同尺寸的滑動窗口存儲歷史心跳消息，分別計算超時值，從結果中選取較大的值作為最終的超時值，這種方法可以捕獲更多的心跳消息，從而提高檢測準確性。實驗結果表明，在不穩(wěn)定的網(wǎng)絡環(huán)境下，2W-FD檢測器能夠獲得更高的檢測準確性。

在大規(guī)模分布式系統(tǒng)中，尤其是部署大量不同類型分布式應用的系統(tǒng)，失效檢測器僅提供單一的QoS已經(jīng)不能滿足應用的需求。Défago等人［12］提出的新的失效檢測器模型—Accrual檢測器，可以同時滿足大規(guī)模分布式系統(tǒng)中多個應用不同的QoS需求。該次研究將傳統(tǒng)失效檢測器模型中的監(jiān)測權與解釋權相分離。Accrual檢測器只負責對節(jié)點進行監(jiān)測，與此同時還將輸出一個代表被檢測節(jié)點懷疑程度的連續(xù)值（也稱為懷疑值，slqp（t）），而不再直接輸出相信或者懷疑的二值性檢測結果。不同的應用根據(jù)自身QoS需求對此懷疑值做出解釋，從而決定被檢測節(jié)點的狀態(tài)。

φ檢測器［13］是Accrual檢測器的首款設計，如圖4所示。通過設置滑動窗口存儲來自被檢測節(jié)點的心跳消息，然后假設這些心跳消息的到達時間間隔符合正態(tài)分布，從而根據(jù)累積分布函數(shù)F（t）計算懷疑值φ。應用程序可以在任意時刻tnow發(fā)起查詢，會收到檢測器返回一個φ值，最終通過φ值與應用程序設定的閾值的比較結果確定被檢測節(jié)點狀態(tài)。φ檢測器的實現(xiàn)滿足了應用程序對失效檢測服務的多樣化需求。

圖4 φ檢測器Fig.4 φ failure detector

Xiong等人［14］指出指數(shù)分布更加適合于描述心跳消息到達時間間隔，從而利用指數(shù)分布計算懷疑值。Lakshman等人［15］將這種基于指數(shù)分布的Accrual檢測器應用于著名的社交網(wǎng)站Facebook的P2P存儲系統(tǒng)Cassandra中，獲得了良好的失效檢測性能。

同時，也陸續(xù)推出了一些基于其它方法處理心跳消息的 Accrual檢測器的研發(fā)實例。Satzger等人［16］提出了一種低開銷的Accrual檢測器的設計，利用直方統(tǒng)計圖計算懷疑值，通過直接分析檢測消息延遲的歷史記錄，計算延遲小于當前檢測時間的消息所占的比例，以此為基礎計算懷疑值。He等人［17］提出的Accrual檢測器則引入了指數(shù)移動平均算法，利用心跳消息到達時間間隔與間隔預測值計算懷疑值。

2.2 檢測結果共享機制

在節(jié)點檢測層面，自適應失效檢測可以解決檢測有效性與檢測負載之間的關系問題。然而從整個系統(tǒng)層面來看，如果每個節(jié)點都單獨進行失效檢測，那么在一個規(guī)模為n的系統(tǒng)中，至多需要產(chǎn)生n2個檢測關系。這對于大規(guī)模的分布式系統(tǒng)而言，無疑會造成巨大的檢測開銷。因此，節(jié)點之間通過共享檢測結果的方法降低檢測開銷，以期改善檢測性能獲得了廣泛的研究。在眾多方法中，基于層次式的檢測方法和基于Gossip式的檢測方法已成為學界矚目焦點。對此內容詳情可做研究評述如下。

（1）層次式方法。將系統(tǒng)中節(jié)點組織成樹或森林的層次結構，然后依托這些特殊的結構建立失效檢測關系，以達到降低系統(tǒng)檢測負載，提高可擴展性的目的。一種典型的層次式結構即如圖5所示。

Felber等人［18］提出了一種層次式的失效檢測服務。在系統(tǒng)中，節(jié)點根據(jù)IP地址被劃分到不同的子網(wǎng)中，每一個子網(wǎng)中的節(jié)點為一個分組，分組中選擇一個主節(jié)點部署失效檢測模塊，負責對分組中其它節(jié)點進行檢測。不同的分組之間可以通過主節(jié)點進行檢測結果交換。這種方法易于管理，并且可以迅捷實現(xiàn)失效檢測。但是，該方法卻高度依賴系統(tǒng)拓撲結構，并不適合拓撲頻繁改變的系統(tǒng)。

圖5 層次式失效檢測Fig.5 Hierarchical failure detector

Stelling等人［19］根據(jù)網(wǎng)格的架構特點，利用Globus toolkit工具包研發(fā)了一個類兩層結構的檢測協(xié)議。每臺主機上安裝一個本地檢測模塊，負責檢測主機上運行的所有進程，不同主機上的檢測模塊會互相交換信息以獲得檢測結果的全面共享。這一協(xié)議適用于節(jié)點計算能力較強的系統(tǒng)，而且從節(jié)點層面看，這不是一種真正意義上的雙層檢測結構。而Bertier等人［20］提出了一種真正意義上的雙層架構的檢測協(xié)議。系統(tǒng)中所有節(jié)點被分配到不同分組中，每一個分組選擇一個主節(jié)點部署失效檢測器，負責檢測組內的節(jié)點狀態(tài)，而所有的主節(jié)點通過互相交換檢測結果可形成全局檢測信息。這種檢測架構在整體設計上相對容易且效率較高，但是與多層結構相比，其對檢測負載的改進沒有多層結構明顯。

（2）Gossip［21］。 本身是一種概率多播協(xié)議［22］，可采用類似蠕蟲病毒（rumor）的快速傳播方式，通過多輪的消息交換以較低的代價實現(xiàn)消息的高效廣播。Renesse等人［23］將Gossip這種協(xié)議引入到失效檢測領域中，提出了2種基于Gossip式的失效檢測器：基本Gossip檢測器以及多層Gossip檢測器。對于基本Gossip檢測器而言，每輪檢測中節(jié)點隨機選擇鄰居節(jié)點進行檢測并交換檢測結果，通過數(shù)輪的交換可以獲得系統(tǒng)中其它節(jié)點的狀態(tài)。在這種檢測器中，其檢測負載與系統(tǒng)的規(guī)模以及拓撲結構無關，而其檢測時間受算法隨機性的影響，隨著系統(tǒng)規(guī)模的增大，檢測時間會呈現(xiàn)線性增長。針對這種情況，多層Gossip檢測器也隨即得以提出。借鑒層次式的檢測思想，根據(jù)節(jié)點IP信息將系統(tǒng)中節(jié)點劃分到不同的子網(wǎng)，大多數(shù)的Gossip消息在子網(wǎng)內傳播，只有少數(shù)的消息可以跨越子網(wǎng)傳播，實現(xiàn)全局的檢測需求。在這種檢測器中，其檢測負載只和系統(tǒng)子網(wǎng)的數(shù)量相關，而與具體節(jié)點數(shù)量無關，擁有良好的可擴展性。然而，針對某一確定節(jié)點的檢測時間至少需要O（logn）Tfail。其中，Tfail是對某一節(jié)點所允許的失效檢測延遲。

雖然基于Gossip式檢測方法在降低檢測負載以及提高可擴展性方面具有優(yōu)勢，但是其所需檢測時間仍然較長。為此，大量的研究集中在對檢測時間的改進上。例如，Gupta等人［24］利用“再檢測”機制實現(xiàn)的組成員協(xié)議SWIM。在SWIM協(xié)議中，節(jié)點q隨機選擇一個節(jié)點p進行檢測，如果在規(guī)定時間內沒有收到回復消息，那么節(jié)點q會隨機選取k個節(jié)點再對節(jié)點p進行檢測，最后根據(jù)這k個節(jié)點返回的檢測結果對節(jié)點p的狀態(tài)做出判斷，以上設計過程如圖6所示。這種方法可以有效地提高檢測準確性，并且通過調整檢測周期與協(xié)議參數(shù)改進檢測時間。Snyder等人［25］將SWIM協(xié)議應用到大規(guī)模HPC存儲系統(tǒng)，通過選取適當?shù)膮f(xié)議參數(shù)以及檢測周期，可以獲得良好的檢測性能。Horita等人［26］提出了類似方法，同樣需要另外k個節(jié)點進行輔助檢測，只是這種輔助檢測是靜態(tài)配置的，不需要動態(tài)發(fā)起過程，在提高檢測準確性的同時進一步改善了檢測時間。Ward等人［27］針對大規(guī)模云計算系統(tǒng)提出了一種多層的gossip協(xié)議。根據(jù)云計算系統(tǒng)架構，可將系統(tǒng)分為3層：云、分組以及虛擬機，在每個檢測周期內，虛擬機選擇同分組內其它虛擬機進行消息交換，其中一定比例的虛擬機會跨越分組、以及跨越云進行消息交換。這種方法可以利用實際系統(tǒng)不同層次所具有的不同通信延遲，實現(xiàn)快速的失效檢測。

圖6 SWIM失效檢測器檢測過程Fig.6 Process of failure detector in SWIM

3 結束語

失效檢測器已經(jīng)是構建高可用分布式系統(tǒng)的基礎組件之一。失效檢測器通過周期性地探測系統(tǒng)中節(jié)點的狀態(tài)，不僅能夠解決分布式系統(tǒng)中一些基礎問題（例如，一致性問題，原子廣播等），還能夠為路由選擇、負載均衡以及任務調度等發(fā)揮有益的支持作用。因此，失效檢測器所提供的服務對分布式系統(tǒng)的性能有著重要的影響。自適應失效檢測和檢測結果共享機制是分布式系統(tǒng)中失效檢測實現(xiàn)的主要方法，未來將深入研究如何降低檢測負載，提高檢測準確性以及檢測時間。