Abstract

一些分布式的p2p的應(yīng)用在整個過程中需要知道進程組成員的弱一致性信息。SWIM是一個通用的軟件模型，他能夠為大規(guī)模的進程組提供服務(wù)。由于傳統(tǒng)心跳協(xié)議的不可伸縮性促使了SWIM的出現(xiàn)，因為傳統(tǒng)心跳協(xié)議要么增加了網(wǎng)絡(luò)負載，隨著成員的規(guī)模程2次方增加，要么增加響應(yīng)時長或者誤檢測出進程奔潰的頻率。本文報導(dǎo)了在大型商用PC集群上的SWIM子系統(tǒng)的設(shè)計，實現(xiàn)和性能。

　　不像傳統(tǒng)的心跳協(xié)議，SWIM將成員協(xié)議的故障檢測和成員更新信息傳遞功能分離開來。進程之間的監(jiān)控是通過一個有效的p2p的周期隨機探測協(xié)議。每個進程失敗被檢測到的預(yù)期時間和每個成員的預(yù)期消息負載都和成員的規(guī)模無關(guān)。成員變化信息，比如進程加入，退出和故障都是通過ping消息和確認消息捎帶進行傳遞。這是一個非常健壯和快速傳染風(fēng)格（也是傳染的后者流言蜚語類型）的傳遞。

　　SWIM系統(tǒng)中的故障檢測錯誤率是通過修改協(xié)議允許組成員在宣布它失敗之前質(zhì)疑進程（這允許系統(tǒng)發(fā)現(xiàn)和糾正錯誤的故障檢測）來降低的。最后，協(xié)議保證一個檢測故障的確定的時間邊界。

　　從SWIM原型的實驗結(jié)果已經(jīng)給出。我們討論一個WAN規(guī)模的可擴展性設(shè)計。

1、Introduction

　　一些大規(guī)模的點對點分布式進程組運行在因特網(wǎng)上，依賴于一個分布式的成員維護子系統(tǒng)。現(xiàn)有的中間件系統(tǒng)使用包含可靠多播和傳染風(fēng)格的信息傳播的成員協(xié)議。這些協(xié)議依次使用在一些應(yīng)用中，比如分布式數(shù)據(jù)庫，它需要協(xié)調(diào)最近斷開的更新，發(fā)布訂閱系統(tǒng)和大規(guī)模點對點系統(tǒng)。其他出現(xiàn)的應(yīng)用比如大規(guī)模協(xié)同游戲和其他協(xié)作的分布式應(yīng)用的性能嚴重的依賴于使用的成員維護協(xié)議的可靠性和可升縮性。

　　簡單的說，一個成員管理協(xié)議提供每個進程（“成員”）一個本地維護的組內(nèi)非故障進程的列表。協(xié)議保證成員列表會隨著新成員的加入，或者退出（自愿或者通過故障）而被更新。應(yīng)用直接通過地址空間或者回調(diào)接口或者API使用成員列表。應(yīng)用可以自由的按需使用列表的內(nèi)容，比如基于gossip的傳播協(xié)議會使用這個列表來周期性的挑選目標節(jié)點來傳播消息。

　　通過幾個性能指標來衡量成員子系統(tǒng)的可靠性和可伸縮性。成員變化發(fā)生后必須在組內(nèi)快速的傳播。底層網(wǎng)絡(luò)的異步和不可靠性會導(dǎo)致消息的丟失，導(dǎo)致進程故障的錯誤檢測，因為一個進程丟失消息和一個進程故障時很難區(qū)分的。這個誤報率必須很低。最后，協(xié)議必須是p2p的（不能依賴一個中心服務(wù)），并且在網(wǎng)絡(luò)和進程間有很低的消息和計算負載。

　　一個超過幾十個進程規(guī)模的組上的成員協(xié)議是很難的，因為它會影響應(yīng)用的性能。就像在另一篇文章中所述的，在這些組上的性能很差的主要癥狀是要么增加進程故障檢測的誤報率，要么增加故障檢測的時間。不可伸縮的傳統(tǒng)成員維護協(xié)議的另一個癥狀是成2次方的消息負載增長。應(yīng)用嚴重依賴成員子系統(tǒng)的例子是虛擬同步多播協(xié)議。傳統(tǒng)的實現(xiàn)在超過幾十個成員規(guī)模上會遭受很嚴重的性能下降和分區(qū)。

　　本文介紹了在SWIM項目中工作成果，實現(xiàn)了一個成員子系統(tǒng)，該系統(tǒng)提供穩(wěn)定的故障檢測時間，穩(wěn)定的誤報率和每個成員的低消息負載，這使得分布式應(yīng)用可以很好的使用它來進行擴展。我們專注于一個組成員的弱變量，在同一時刻，組內(nèi)不同成員的成員列表不要求是一致的。通過增強成員子系統(tǒng)可以實現(xiàn)更強的保證，比如可以通過一個有序的周期性檢查成員列表進程來提供幾戶同步的成員列表。然而，與弱一致性不一樣，強一致性規(guī)范有基本的伸縮限制。

　　傳統(tǒng)的分布式成員算法是通過心跳來實現(xiàn)的。每個進程周期性的發(fā)送遞增的心跳計數(shù)到外部網(wǎng)絡(luò)。如果一定時間收不到進程的心跳就會認為它已經(jīng)故障了。然而實際的心跳受到服務(wù)擴展性的限制。發(fā)送所有的心跳到一個中心節(jié)點會導(dǎo)致熱點情況。像所有成員發(fā)送心跳（通過網(wǎng)絡(luò)多播或者gossiping）導(dǎo)致網(wǎng)絡(luò)和組的消息負載隨著組規(guī)模程2次方增長。如果心跳沿著一個邏輯環(huán)發(fā)送，當(dāng)有多個故障時會導(dǎo)致不可預(yù)測的故障檢測時間。不幸的是，隨著組規(guī)模的增長，出現(xiàn)多個故障的可能性也在增長。

　　關(guān)于基于心跳的成員維護機制的固有的不可擴展的原因在文檔[12]中有進一步討論。本文提出了一種替代心跳，基于成員間隨機探測的分布式隨機故障檢測協(xié)議。數(shù)學(xué)分析表名隨著組規(guī)模的上升，協(xié)議的屬性，（期望的）故障檢測時間，誤報率和每個成員的消息負載，都獨立于組的規(guī)模。相對于基于all-to-all的心跳協(xié)議，每個成員的故障探測時間或者網(wǎng)絡(luò)帶寬使用（或者誤報率）基于線性變量（組規(guī)模），這是一個提升。

　　文檔[12]的工作成果表名通用類型的all-to-all心跳協(xié)議的可擴展性源于隱式的融合成員探測規(guī)范的兩個主要功能：1）成員更新傳播：傳播由于成員加入，離開或者故障引起的成員變更；2）故障檢測：檢測現(xiàn)有成員是否故障。通過設(shè)計一個有效的非多播的故障檢測器可以消除多播心跳的開銷，并且只有成員變更發(fā)生時才使用傳播組件。成員傳播組件可以通過硬件多播或者傳染模式實現(xiàn)。

　　雖然[12]提出了一個故障檢測協(xié)議和理論分析，我們的工作著眼于將成員傳播組件建成一個工作成員的子系統(tǒng)。此外，最終的協(xié)議通過減少誤報率和在單個進程的故障檢測時間給予更強的確定性保證的機制進行增強。

　　SWIM系統(tǒng)提供一個成員基礎(chǔ)：

每個組成語有一個常量的消息負載
集群中非故障進程檢測到一個進程故障在一個（期望的）常量時間內(nèi)。
一個非故障進程檢測到另一個進程故障的本地時間有一個明確的邊界（組大小的函數(shù)）
以傳染模式（[2,8]中的gossip-style或者epidemic-style）傳播成員更新信息，包括故障信息。傳遞延遲隨著成員數(shù)增長緩慢（對數(shù)）
通過在“聲明”一個進程故障之前進行“懷疑”的機制來降低誤報率

　　雖然1和2是[12]中故障檢測協(xié)議的屬性，但是3-5是本文的后續(xù)工作。運行在PC集群上的SWIM實現(xiàn)原型的實驗結(jié)果進行了討論。SWIM協(xié)議也可以擴展到工作在廣域網(wǎng)（WAN）或者虛擬專用網(wǎng)絡(luò)（VPN），我們在Section 6進行了簡單的介紹。

　　本文后續(xù)組織如下：section 2簡要介紹了這個領(lǐng)域的前人研究和來自[12]的可升縮的故障檢測協(xié)議的基礎(chǔ)。Section 3描述了基本的SWIM協(xié)議，Section 4改進協(xié)議。Section 5展現(xiàn)了實現(xiàn)原型的實驗結(jié)果。Section 6進行總結(jié)。

2. Previous Work

　　在傳統(tǒng)的分布式all-to-all心跳故障檢測算法中，每個組成員定期發(fā)送一個“心跳”消息（有一個遞增計數(shù)器）到所有的其他組成員。非故障成員Mj連續(xù)幾個心跳周期沒有收到成員M_i心跳時,會認為M_i已經(jīng)發(fā)生故障。

　　分布式的心跳機制保證一個故障成員總是會被任何非故障成員檢測到（它故障之后一個時間段），因為一個已經(jīng)奔潰的成員會停止發(fā)送心跳消息。然而，這些協(xié)議的準確性和可擴展性保證各有差異，這依賴于實際使用的傳遞心跳的機制。

　　在最簡單的實現(xiàn)中，每個心跳都廣播給組中所有其他成員。這會導(dǎo)致每秒θ(n^2/T)的消息負載（盡管使用了IP廣播），T是分布式應(yīng)用要求的故障檢測時間。Renesse在[16]中提出了一種通過健壯的gossip-style協(xié)議來傳播心跳的方式。在這個協(xié)議中，每個t_gossip時間單元，每個成員進行傳播給一些隨機的目標，θ(n)-最近從其他成員處接收到心跳計數(shù)器的數(shù)量。雖然gossiping減少了誤報率，但是通常需要一個新的心跳計數(shù)，期望上θ[log(n)?t_gossip]時間單元到達任意其他組成員。為了滿足應(yīng)用指定的檢測時間，協(xié)議每秒產(chǎn)生θ((n^2?log(n))/?t_gossip)字節(jié)的網(wǎng)絡(luò)負載。使用批量消息來解決這個問題受到UDP包大小的限制，例如50個成員的5B心跳（IP地址和數(shù)量）已經(jīng)產(chǎn)生250B，然而SWIM產(chǎn)生的包最多只有135B，無論組多大。

　　將心跳通知到所有的組成員會導(dǎo)致成2次方增長的網(wǎng)絡(luò)負載。這可以問題通過將故障檢測操作從成員更新傳播中分離開來而避免。

　　已經(jīng)有一些層次的成員系統(tǒng)被提出，比如Congress[1]。這屬于一類更廣泛的方案，該方案中每個進程只心跳到一個子進程組。這類協(xié)議需要仔細的配置和維護成員信息流動的軌跡，并且協(xié)議的準確性依賴于圖的魯棒性。相比之下，SWIM的設(shè)計避免了虛擬圖的開銷。

　　SWIM對于上面描述的不伸縮性問題的解決方案基于（a）設(shè)計一個分開的故障檢測與成員更新信息傳遞組件，和（b)使用非心跳的策略來進行故障檢測。

　　在轉(zhuǎn)移到描述SWIM協(xié)議細節(jié)之前，我們首先奠定理解分布式故障檢測器協(xié)議的關(guān)鍵的效率和可升縮性特征的基礎(chǔ)。通過[6,7,12,16]的研究已經(jīng)可以辨別分布式故障檢測器協(xié)議的基本屬性（從理論和實際的角度），和同時不可能滿足他們的結(jié)果。結(jié)果的權(quán)衡通常是根據(jù)分布式應(yīng)用需要的安全性和可用性來決定的。這些屬性是[12]：

Strong Completeness：任何成員的奔潰故障會被所有非故障成員檢測到[6];
故障檢測的速度：一個成員故障到它被一些非故障成員檢測到的時長
準確性：故障檢測的誤報率
網(wǎng)絡(luò)消息負載：每秒由協(xié)議產(chǎn)生的字節(jié)數(shù)

　　[6]證明了在一個異步網(wǎng)絡(luò)上建立一個準確（沒有錯誤的檢測）且Strong Completeness的故障檢測器是不可能的。然而，由于典型的分布式應(yīng)用依賴于一直持有（為了維護動態(tài)組的時間信息）的Strong Completeness，包括基于心跳方案的大多數(shù)故障檢測器保證這個屬性，同時試圖保持較低的誤報率。SWIM采用相同的方式。

　　在[12]中，一個簡單的計算表明了在滿足指定每個成員的故障檢測率（記為PM(t)），和n個成員組大小的檢測時間T的情況下最小的網(wǎng)絡(luò)負載（每秒字節(jié)數(shù)）。計算出來的負載時n?(log(PM(T)))/(log(p_ml))，p_ml是底層網(wǎng)絡(luò)的包丟失概率。

　　雖然這個計算結(jié)果是在理想的情況下，即每個消息的獨立的消息丟失概率（p_ml），計算出來的，它可以作為一個很好的比較不同故障檢測協(xié)議的基線。例如，Section2中討論的all-to-all的心跳協(xié)議有一個與組規(guī)程呈線性變化的次最優(yōu)因子。

3. The Basic SWIM Approach

　　如前所述，SWIM有兩個組件：

一個故障檢測器組件：用來檢測成員故障
一個傳播組件：用來傳遞最近有成員加入，離開或者故障的消息

　　我們現(xiàn)在描述基本的SWIM協(xié)議。基本協(xié)議使用基于[12]的故障檢測協(xié)議的隨機探測方式（Section 3.1）并且通過網(wǎng)絡(luò)廣播傳播成員更新信息（Section 3.2）。SWIM協(xié)議通過提煉這個最初設(shè)計開發(fā)成功（Section 4）。

3.1. SWIM Failure Detector

　　SWIM故障檢測算法[12]使用兩個參數(shù)：協(xié)議周期T’（時間單元）和整數(shù)k—故障檢測子集的大小。協(xié)議不要求成員之間同步時鐘，并且協(xié)議的屬性保證T’是否是組成員的平均協(xié)議周期。

　　圖1說明了協(xié)議在任意一個成員M_i上的工作過程。在每個協(xié)議周期的T’時間單元（M_i的本地時鐘）內(nèi)，從M_i的成員列表中隨機選中一個M_j，并且發(fā)送一個ping消息給它。M_i然后等待賴在M_j的ACK。如果在指定的超時時間（通過消息的往返時間決定，通常選擇小于協(xié)議周期）內(nèi)沒有收到ACK，M_i間接探測M_j。M_i隨機選擇擇k個成員并且都發(fā)送ping-req（M_j）消息。每一個成員（非故障的）收到這個消息后，ping M_j，并且轉(zhuǎn)發(fā)M_j的ACK（如果收到）給M_i。在協(xié)議周期結(jié)束的時候，M_i檢查是否收到任何ack，不論是直接來自M_j還是間接通過那k個成員。如果沒有收到，它聲明M_j，已經(jīng)故障，并且通過傳播組件處理這個更新。

　　在圖1的示例中，只要這k個成員中的一個在完成這個周期時認為M_j是存活的，則M_i在這個協(xié)議周期會認為M_j是故障的。

　　用于啟動間接探測的預(yù)先指定的超時時間基于分布式網(wǎng)絡(luò)的往返時間進行估計，例如平均值或者99%的用時。注意協(xié)議周期T’必須至少是往返時間估計的三倍。在我們的實驗中，使用往返時間的評價值來設(shè)置超時時間，并且我們的協(xié)議周期遠遠大于這個值。

　　協(xié)議的每個消息都包含啟動者M_i上的唯一的協(xié)議周期序列號。注意ping，ping-req，ack消息的大小有一個常亮的邊界值，并且獨立于組大小。

　　上述協(xié)議的第二部分使用一個間接的子成員探測小組來重新ping和ack。使用這種方法而不是直接發(fā)送k個ping消息給M_j，或者直接返回ping-req的ack給M_i，避免受M_i和M_j之間的網(wǎng)絡(luò)堵塞的影響。堵塞可能導(dǎo)致丟失原始的ping消息或者它的ack。

　　這個故障檢測協(xié)議在[12]中已經(jīng)分析過。這里我們簡單的總結(jié)下分析結(jié)果：

如果每個成員有一個大小為n的成員列表，并且其中有q_f是非故障的，則一個協(xié)議周期中任意一個成員被選為ping目標的概率為，它下降的很快（隨著n—>∞）到

因此，任意故障的成員和它被組內(nèi)其他進程檢測到的預(yù)期時間最多是。根據(jù)應(yīng)用指定的期望檢測時間，這給出了一個協(xié)議周期長度的估算值。

如果是及時傳遞一個包的概率，所有傳送的包都是獨立的，在一個協(xié)議周期內(nèi)任何一個非故障成員會被錯誤的檢測為故障的概率為

根據(jù)應(yīng)用要求的誤報率，這給出了一個k的配置值。

這個故障檢測器滿足Strong Completeness：一個故障成員在每個非故障成員上最終會被選為一個ping目標，并且從它的成員列表中刪除。

由協(xié)議引入的每個成員的消息負載是一個常量，它不隨組大小變化，并且所有成員都是對稱的。這個負載可以通過k的估算值計算出來。

這些屬性（除了漸進值）都不依賴于組大小n

3.2. Dissemination Component and Dynamic Mem- bership

　　在檢測到一個組成員故障后，進程只是簡單的廣播M_j失敗的消息到剩下的組成員中。一個成員接收到這個消息后將M_j從它的本地成員列表中刪除。

　　新加入成員或者主動離開成員的信息以相似的方式廣播。然而，對于一個加入的進程，他必須知道至少一個組內(nèi)的聯(lián)系成員。這可以通過一些方式實現(xiàn)：如果組關(guān)聯(lián)到一個眾所周知的服務(wù)器或者IP多播地址，所有的加入可以直接連接相關(guān)地址。在缺乏這樣的基礎(chǔ)設(shè)施的情況下，加入消息可以廣播出去，組成員接收到之后可以決定（通過拋硬幣）是否響應(yīng)。另外，為了避免多個成員響應(yīng)，可以在組內(nèi)維護一個靜態(tài)的協(xié)調(diào)器來處理加入請求。實際上，存在多個協(xié)調(diào)器并不影響協(xié)議的正確性，只會導(dǎo)致多個加入請求響應(yīng)。通過傳播組件，隨著時間的推移可以發(fā)現(xiàn)和解決多個協(xié)調(diào)器。在當(dāng)前的SWIM版本中，我們選擇維護一個協(xié)調(diào)器，盡管沒有理由排除任何其他的策略。

4. A More Robust and Efficient SWIM

　　Section 3描述了基本的SWIM協(xié)議，它使用網(wǎng)絡(luò)多播來傳遞成員更新信息（成員加入，離開和故障）。然而，網(wǎng)絡(luò)多播原語比如IP多播等，只是最大努力——消息丟失可能導(dǎo)致任何成員的任意的和相關(guān)未接收成員關(guān)系變化。在Section 4.1中我們描述了一個通過故障檢測協(xié)議發(fā)送的ping和ack消息附帶成員更新信息的傳遞組件。這完全消除了由于傳遞組件（通過）導(dǎo)致的額外的數(shù)據(jù)包生成。SWIM只生成ping，ping-req和ack數(shù)據(jù)包，從而為每個成員提供一個常量的消息負載。這種方式導(dǎo)致一個傳染風(fēng)格的信息傳遞，使得數(shù)據(jù)包丟失的魯棒性提供和低延遲。

　　基本的SWIM協(xié)議其計算的準確性受慢進程（例如，由于緩沖區(qū)溢出丟失大量數(shù)據(jù)包）聲明一些非故障進程已經(jīng)故障的影響。這也有可能是進程受到短時間的波動，比如一個高負載的機器。這導(dǎo)致進程沒有機會準時的響應(yīng)接收到的ping消息，而被錯誤的聲明為故障。Section 4.2提出了一種猜疑機制，一個進程沒有響應(yīng)ping消息，就像Section 3描述的那樣，不會被立即聲明為“故障”。相反，進程聲明它是“可疑的”，并且這個信息使用傳播組件擴散到組內(nèi)。在一個預(yù)設(shè)的超時時間（在Section 5中討論如何設(shè)值）之后，被猜疑的進程被聲明為“故障”并且這個消息傳播到組內(nèi)。然而，如果在這個超時過期之前，被猜疑的進程響應(yīng)了一個ping請求，關(guān)于它還“或者”的消息被傳播的組內(nèi)。這個進程將會在不同成員的成員列表中重新被激活，而無需離開或者重新加入組。這個預(yù)先指定的超時時間通過增加故障檢測時間而降低誤報率。

　　基本的SWIM故障檢測協(xié)議保證最終任意一個故障進程M_i會被每個非故障組成員M_i檢測到。然而，它沒有保證任意一個故障成員M_i和它被另一個任意的成員M_j(基于M_j的本地協(xié)議數(shù))檢測到的時長。Section 4.3描述了一個修改的SWIM故障檢測協(xié)議，它保證時間有界的完整屬性；故障發(fā)生和它被M_j檢測到之間的時長不會超過兩倍的組大小（協(xié)議周期數(shù)量）。

4.1. Infection-Style Dissemination Component

　　基本的SWIM協(xié)議傳遞成員更新消息通過使用原始的多播。在大多數(shù)網(wǎng)絡(luò)和操作系統(tǒng)中，硬件多播和IP多播都是可用的，但是都基本不會開啟，例如由于管理的原因。為了傳播成員更新消息到所有的組成員，基本的SWIM協(xié)議不得不使用昂貴的廣播或者低效的點對點消息機制。更進一步，多播是不可靠的，成員變換只能盡最大努力傳遞給組成員。

　　相反，增強的SWIM協(xié)議完全消除了使用額外的原始多播。它通過在故障檢測協(xié)議生成的ping，ping-req和ack消息上攜帶信息來傳遞。我們稱為傳染式的傳播機制，信息傳播類似于社會中八卦的傳播，或者在普通人群中傳播[8]。注意傳播機制的實現(xiàn)并不生成任何額外的數(shù)據(jù)包（例如多播）——所有“消息”都通過搭載在故障檢測組件的數(shù)據(jù)包上傳播。

　　Bailey[2]給出了包含一個初始感染成員的大小為n的均勻混合的組的傳染速度的確定分析。在每個單位時間內(nèi)接觸率為β的情況下，（期望的）感染成員數(shù)x(初始為1)和時間t的關(guān)系可以得到：

　　在我們的傳染式的傳播組件中，通過ping和ack消息傳遞成員更新信息的速度也能以一種相似的方式分析。協(xié)議的周期當(dāng)做一個時間單位，接觸率β是任何一對感染與未感染成員聯(lián)系的概率，并且等于

。這告訴我們。

　　這樣一個傳染進程以指數(shù)級在組內(nèi)快速傳播。在輪協(xié)議周期后，這里λ是一個參數(shù)，期望的受傳染的成員是。在協(xié)議周期后通過傳染風(fēng)格攜帶傳遞的成員更新信息會到達個組成員。簡化一下，隨著n增長（—>∞），x的估值為。將λ設(shè)為一個很小的常量足以滿足可靠的傳播——即使在很小的組大小下也是真的，就像我們在Section5中的實驗所示。

　　文獻包含了一些其它傳入風(fēng)格[4,8,13]的分析，關(guān)于他們的可靠性概率有著基本相似的結(jié)論。這些分析也表名傳染風(fēng)格的傳播可以彈性從處理故障和網(wǎng)絡(luò)消息丟失，就像流行病的傳染。我們的實現(xiàn)結(jié)果也展示了這些特性。

　　實現(xiàn)上是順序的。SWIM協(xié)議層在每個組成員M_i上維護一個最近的成員更新的緩存，以及每個緩存元素的一個本地計數(shù)。該本地計數(shù)表名該元素到目前為止被M_i上攜帶的次數(shù)，并用來選擇下次攜帶哪個元素。每個元素最多可以被攜帶次。如果緩存區(qū)的大小大于在單個ping消息（或者ack）上能夠攜帶的元素最大數(shù)量，選擇被傳遞次數(shù)更少的元素。由于協(xié)議的周期時固定的，并且成員變化的速率可能暫時高過傳播速率，這是必要的。在這種情況下，更”年輕“的緩存元素可以保證所有成員變化傳染至少幾個成員——當(dāng)成員變化速度停頓時，這些變化會通過剩下的組成員傳播。

　　我們對這個協(xié)議的實現(xiàn)維護兩個組成員列表——一個列表是那些沒有被聲明為故障的組成員，另一個是最近已經(jīng)故障的成員。目前，從這兩個列表中選取相同數(shù)量的緩存元素來進行攜帶，但是該方案可以推廣到適應(yīng)進程加入，離開和故障率的相對變化。

4.2. Suspicion Mechanism: Reducing the Fre- quency of False Positives

　　在到目前為止描述的SWIM故障檢測協(xié)議中，如果一個非故障成員M_j（錯誤的）被另一個成員M_i錯誤的檢測為已經(jīng)發(fā)生故障，無論是由于網(wǎng)絡(luò)包丟失或者因為M_j睡眠了一段時間，還是因為M_i是一個慢進程,M_j會在組內(nèi)聲明為已經(jīng)故障。換句話說，一個完全健康的進程M_j遭受了非常重的懲罰，在被錯誤的檢測為故障后強制退出組。這導(dǎo)致一個很高的誤報率。

　　我們通過修改SWIM，無論何時基本的SWIM故障檢測協(xié)議檢測到一個故障都運行一個子協(xié)議降低了這種影響，該子協(xié)議稱為猜疑子協(xié)議。

　　猜疑子協(xié)議工作流程如下。考慮成員M_i在當(dāng)前協(xié)議周期選擇成員M_j作為ping目標，并且運行基本的SWIM故障檢測周期。如果M_i沒有接收到確認消息，不論是直接或者間接的探測子集，它并不聲明M_j是故障的。相反，M_i在本地成員列表中標記M_j為可疑的。另外，一個{Suspect M_j：M_iSuspect M_j}消息通過傳播組件在組內(nèi)傳遞開來。任何組成員M_l收到該消息也標記M_j為可疑的。可以的成員待在成員列表中并且在SWIM故障檢測協(xié)議選擇ping目標時被當(dāng)做一個非故障成員。

　　如果一個成員M_l在基本的SWIM協(xié)議過程中成功的ping一個可疑的成員M_j,它取消成員列表中之前M_j的可以標記，并且通過傳播組件（在我們的系統(tǒng)中使用傳染風(fēng)格）傳遞{Alive M_j：M_lkonws M_j}消息。這樣一個Alive的消息取消接受M_j可疑的成員的列表中的可疑標記。注意，如果成員M_j收到猜疑它自己的信息，他可以傳遞一個Alive的消息來聲明它沒有故障。

　　超過指定的超時時間后，成員列表中被猜疑的記錄過期。如果M_j在成員M_h上是可疑的，并且在收到Alive消息之前已經(jīng)超時，M_h聲明M_j已經(jīng)故障，并且將其從本地成員列表中刪除,并開始通過傳播組件傳遞{Confirm M_j：M_hdeclares M_j as faulty}消息。這個消息會覆蓋之前的Suspect或者Alive消息，并且從所有接受這的成員列表中刪除M_j。

　　這個機制降低（并未消除）了故障檢測的誤報率。注意原始協(xié)議的Strong Completeness屬性繼續(xù)保持。處理猜疑一個故障進程M_j的失敗可能會延長故障檢測時間，但是最終被檢測到是可以保證的。

　　從上面的討論中，Alive消息覆蓋了Suspect消息，Confirm消息覆蓋了Suspect和Alive消息，在這種影響下，本地成員列表對可以元素M_j保持一致。然而，一個成員在他的生命周期中可能被猜疑和解除猜疑多次。這些多版本的Suspect和Alive消息（都關(guān)聯(lián)同一個成員M_j）需要通過唯一的標識符區(qū)分。這個標識符通過使用成員列表中每個元素的虛擬的incarnation number屬性來提供。Incarnation number是全局的。一個成員M_i的incarnation number當(dāng)它加入時初始化為0，它只可以被M_i增加，當(dāng)它收到它被猜疑的信息時，M_i生成一個擁有它標識符和一個自增incarnation number的Alive消息，并且通過傳播組件傳遞到組內(nèi)。

　　因此，Suspect，Alive和Confirm消息包含成員的incarnation number和它的標識符。這些消息的優(yōu)先次序和他們對成員列表的影響被指定如下：

{Alive M_l， inc=i} overrides

　　　　—{Suspect M_l， inc=j},i>j

　　　　—{Alive M_l， inc=j},i>j

{SuspectM_l， inc=i} overrides

　　　　—{SuspectM_l， inc=j},i>j

　　　　—{Alive M_l， inc=j},i≥j

{Confirm M_l， inc=i} overrides

　　　　—{SuspectM_l， inc=j},any j

　　　　—{Alive M_l， inc=j},any j

　　很容易看到這些消息的優(yōu)先次序和覆蓋維護故障檢測組件所需要的正確屬性。熟悉adhoc路由協(xié)議例如AODV的讀者會注意到使用序列號和我們的incarnation number機制之間的相似性。

　　傳播組件的偏好規(guī)則和傳染風(fēng)格也包含了一個進程被多個進程懷疑。偏好規(guī)則不依賴于猜疑的來源，并且如果有多了個來源，傳染模式傳遞一個消息（Suspect，Alive或者Confirm）非常迅速，且每個進程的開銷與來自一個傳染源的開銷完全一樣。

4.3. Round-Robin Probe Target Selection: Provid- ing Time-Bounded Strong Completeness

　　在Section 3中描述的基本的SWIM故障檢測協(xié)議在一個平均常量的協(xié)議周期內(nèi)檢測到故障。及時每個進程故障被保障最終會被每個非故障進程檢測到（eventual Strong Completeness），一個病態(tài)的ping目標的選擇會導(dǎo)致組內(nèi)任何地方第一次檢測到該異常時有很大的延遲。極端情況下，這個延遲可能是無界的，由于故障的進程用于不會被其他非故障進程選為ping目標。

　　這可以通過如下修改協(xié)議來解決。故障檢測協(xié)議在成員M_i上通過維護一個當(dāng)前成員列表的已知元素的列表（直觀的，一個數(shù)組），并且不是隨機的從這個列表中選取ping目標，而是輪訓(xùn)方式。相反，一個新成員加入時，隨機的選擇一個位置，并插入列表中。當(dāng)完成整個列表的遍歷時，M_i上以一種隨機重排的方式重新安排成員列表。

　　考慮M_i上如上修改的SWIM協(xié)議的執(zhí)行。一旦另一個成員M_j包含在M_i的成員列表中,在每次遍歷M_i的成員列表時都會被選作ping目標。如果成員列表的大小不超過n_i，成功的選擇相同目標最多需要（2·n_i-1）個協(xié)議周期。它限制了任何故障進程成員M_i的故障檢測時間的最壞情況，因此它滿足Time Bounded Completeness 屬性。

　　原始協(xié)議的平均故障檢測時間通過這個優(yōu)化保留下來，因為在不同成員上的隨機的成員列表導(dǎo)致每個成員一個相似的分布式ping目標選項。

5. Performance Evaluation of a Prototype

總結(jié)

以上是生活随笔為你收集整理的SWIM:一种可扩展的弱一致性的传染风格的进程组成员协议的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。