一種基于失效檢測器的快速異步系統共識算法
2007-01-01 00:00:00王剛張大方楊金民
計算機應用研究 2007年1期
摘要：異步系統下的共識問題是容錯方向中的關鍵問題。首先分析了幾種基于失效檢測器的共識算法，然后考慮減少響應時間，對現有算法提出改進。改進后的算法滿足異步系統下共識問題的兩階段最低限度，并且在特定條件下可以在第一階段快速作出響應。經實驗證明，改進后的算法具有更快的響應時間和較少的通信量。
關鍵詞：異步系統； 容錯； 共識問題； 失效檢測器
中圖法分類號：TP302.8文獻標識碼：A
文章編號：1001－3695(2007)01－0097－03
一致性問題是分布式計算中的常見問題。例如，在一個復制數據系統中，對復制數據進行相同順序的操作；在復制傳感器系統中，對傳感器的值達成一致；在一個廣播系統中以相同的順序傳遞一個消息等。共識問題就是對一致性問題的本質歸納。在消息傳遞系統中，任何復制容錯系統都會涉及到共識問題，因此共識問題是容錯研究中的一個關鍵問題。共識問題抽象地來說，就是要求一系列進程對某個值(Value)達成一個共識。過程分為兩個原語，即Propose原語和Decide原語。Propose時每個進程提出一個值v，Decide時所有正確進程必須最終決定某個值。解決共識問題必須滿足以下條件：
（1）終止性，即所有正確進程最終都要決定某個值。
（2）有效性，假如某個進程決定了某個值，那么這個值必須是在Propose原語中由某個進程所提出的。
（3）一致性，即所有進程最終決定的必須是同一個值。
本文主要考慮異步系統下的共識問題，一個分布式系統如果是異步的，那么在消息延遲、時鐘漂移和執行一步所消耗的時間上都沒有上限。共識問題看似簡單，但M. J. Fischer 等人[1]證明共識問題在異步系統模型中，只要出現一個崩潰進程，那么共識問題就不能得到解決。原因主要在于進程無法準確得知一個很久沒有響應的進程究竟是崩潰了，還是只是運行得比較緩慢。圍繞這個問題，研究者大概提出兩種主要途徑：①簡化問題的定義，如借助Random Oracles的方法；②允許各個分布式進程有一段足夠的同步時間得到正確的結果，其中最主要的就是借助失效檢測器。失效檢測器的概念最早是由Chandra和Toueg[2]提出的，在文中給出了基于失效檢測器解決異步模型下共識問題的算法，基于失效檢測器的共識算法模型可以用圖1來表示。共識算法周期性地詢問失效檢測器，失效檢測器在被詢問時返回當前所懷疑的錯誤進程，共識算法根據返回的結果來完成下一步運算。所有的共識算法均具有縱容性，即只有當失效檢測器的條件滿足時，共識算法才可能給出結果，并且給出的結果一定是正確的；當失效檢測器的條件沒有滿足時，共識算法不會給出任何結果。
減少共識問題時間開銷的途徑有兩種：①采用提高失效檢測器的準確度和靈敏度的方法，這方面已經有很多研究；②從提高共識算法的效率方面考慮。近幾年來，有關基于失效檢測器的共識算法研究已經有很多，如文獻[4，6，8]，從最早的四階段CT算法到兩階段的PR，MR算法，研究者提出了很多種基于失效檢測器的共識算法。本文分析了幾種典型的基于失效檢測器的共識算法，并在其基礎上作出改進，改進后的算法在穩定狀態下兩階段可以完成共識，并且在特定的條件下，第一階段就可以快速給出結果，從而降低時間開銷。
1系統模型和定義
系統由一系列有限的n個進程組成，n>1，進程集合為∏={P1，…，Pn}，進程可能發生崩潰性錯誤（在這里我們不涉及到拜占庭性錯誤），進程發生崩潰以后不會自動恢復。一個進程在發生崩潰性錯誤以前，我們把它稱為一個正確的進程。發生崩潰性錯誤的進程數目f不能超過進程總數n的一半(f
不可靠失效檢測器的概念最早是由Chandra 和 Toueg[2]提出的，每個進程都連接一個本地的失效檢測器，負責對其他進程進行監控，在被詢問時給出當前所懷疑發生崩潰的進程的集合。不可靠就是允許出現錯誤的懷疑，如果發現將一個正確的進程錯誤地劃入到懷疑對象中，就將其從懷疑對象中移除。文中根據完整性和精確性兩種屬性將失效檢測器分類。其中◇S類失效檢測器被證明是在異步系統下完成共識算法的最低限度。
◇S類失效檢測器應滿足：
（1）強完整性(Strong Completeness)，即最終每個崩潰進程都被所有正確進程懷疑。
（2）最終弱精確性(Eventual Weak Accuracy)，即存在一個時刻，當過了這個時刻以后，至少存在一個正確的進程不被其他所有正確進程懷疑。
Ω類失效檢測器是另外一種典型的失效檢測器。Ω類失效檢測器被詢問時，所返回的結果是當前唯一一個被認為正確的進程，即Leader進程。在很長一段時間內，可以同時存在幾個Leader進程，但最終所有正確進程應該選擇同一個Leader進程，即滿足條件：
最終決定權（Eventual Leadership），存在一個正確進程P和一個時間t，在時間t后，任何正確進程詢問失效檢測器的返回值均為進程P。
2算法分析
2．1四階段CT共識算法
CT算法是由Chandra和Toueg[2]提出的，CT算法是一種輪轉協調者算法，如圖2所示。
每個進程都有一個確定的編號，分別為p1，…，pn。為了完成一次共識，所有進程都要執行一定的輪數(Round)，每輪分為四個階段。執行過程中各個進程不一定都處在同一輪，每一輪中都會有唯一的一個協調者。協調者是輪轉的，第一輪，p1成為協調者；第二輪，p2成為協調者；以此類推，pi進程在第kn+i輪時成為協調者。當一個進程成為協調者時，它試圖讓所有進程對某個值達成共識，如果本輪協調者被大多數進程所認可，共識算法結束，問題解決；否則就進入下一輪，由下一個協調者來完成同樣的工作。CT算法基于◇S類失效檢測器，要求崩潰進程數目不能超過進程總數的一半。
使用CT算法，在正常運行情況下（沒有出現崩潰進程，并且失效檢測器給出的結果是正確的）完成一次共識，每個進程需要經歷如圖2所示的四個階段。每次在共識算法開始時，算法都會默認進程P1為協調者，這在進程P1沒有崩潰時不會對算法有任何影響，一旦進程P1發生崩潰，勢必會延長共識算法完成的時間，而且決定權在協調者，如果協調者進程運行速度變慢，那么整個系統的時間開銷就會增加。
2．2兩階段共識算法
CT算法之后，研究者提出了幾種每輪兩階段的共識算法，如Fast Consensus[7]、MR算法[4]，這些算法在某些情況下可以經兩階段完成一次共識，但都有一定的限制條件。P. Dutta 和R. Guerraoui[6]提出了一種新的基于Ω類失效檢測器的算法，這種算法在穩定狀態下，進程一輪經歷兩個階段就可以完成一次共識，并且滿足Zero Degrading ，即在穩定狀態下，完成一次共識需要的階段數相同，系統穩定后，崩潰進程不會增加共識算法的時間開銷。具體算法描述如下：
當一個進程Propose時，它同時開始運行兩個任務。
任務1所有進程都要執行一定的輪數，每輪分為兩個階段，在這兩個階段各個進程彼此交換一些信息，進程Pi保存的信息有當前失效檢測器認為的正確進程leaderi、估值estimatei（初始值為Pi提出值）、本輪號碼ri、中間值newestimatei（初始值為⊥）。
第一階段：進程Pi發送leaderi和estimatei給其他所有進程，并且等待進程leaderi和
n+12-1
個進程的消息。此時，
(1)如果在收到進程leaderi的消息之前認為進程leaderi崩潰，或收到來自進程Pj的消息，有leaderj≠leaderi那么newestimatei=⊥。
(2)如果收到進程leaderi的消息，而且所有收到的其他進程消息都認為leaderi是正確進程，那么newestimatei的值為進程leaderi所提出的值v。
第二階段：進程Pi再次發送newestimatei給所有其他進程，并且等待
n+12
個進程的消息。此時，
（1）如果收到的所有進程消息的newestimate都為⊥，則進入下一輪。
（2）如果收到的進程消息有部分newestimate不為空，則把此值賦給estimatei，進入下一輪。
（3）如果收到所有進程消息的newestimate都為值v，則decide值為v，并且發送decide消息給其他所有進程，完成一次共識。
任務2在接收到任何進程的decide消息后，決定相同的值v，并且向其他進程發送decide消息，完成一次共識。
這種算法在穩定狀態下，進程經歷兩階段就可以完成一次共識。因為在CT算法中決定權只在于協調者，當協調者運行比較緩慢或者崩潰時會對整體運行速度產生影響，而這種算法中每個進程都可以自主地決定值，因此在完成相同工作量的情況下與CT算法相比，降低了時間開銷。
2．3快速共識算法
PR算法各個進程在每個階段都需要向其他所有進程發送消息，這樣通信量要大于其他算法。我們考慮利用算法的特性，使得算法能夠在某種特定條件下在第一階段就完成共識。首先分析文獻[3]中Ω類失效檢測器的實現方法，它采用的是Push模式，如圖3所示。被檢測進程q周期性地發送Iamalive消息，以顯示其沒有發生崩潰。假如在時間T內，p沒有收到q的消息，那么p認為進程q發生崩潰。初始時所有進程相信進程P1為唯一正確的進程（P1為Leader），進程P1開始發送Iamalive消息給P2，P3，…，Pn。通常，一個進程Pi，只有當trustedi=i，進程Pi才會周期性地給后繼進程Pi+1，…，Pn進程發送Iamalive消息。假如trustedi≠i，那么進程Pi所做的只是等待來自于進程Ptrustedi的消息。在等待過程中如果在時間T內沒有收到消息，則進程Pi認為進程Ptrustedi崩潰，進而相信進程Ptrustedi+1為當前的Leader進程。在運行過程中如果Pi收到了來自Pj的消息，并且j 圖3失效檢測器模型 目前已經有文章證明兩階段是異步系統模型下完成共識問題的最低限度，但在一些特定條件下，共識問題可以在第一階段完成。我們在對PR算法進行分析后，不難看出在第二階段只有Leader進程所提出的值才可以成為最終的決定值，如果采用基于上述算法的Ω類失效檢測器，編號為Pi的進程不可能認為編號大于i的進程為當前的Leader，因此編號大于 n+12 的進程在PR算法中無法得到大于進程總數一半的進程的認同，也就無法成為Leader，所提出的值不可能成為最終的決定值。這樣就可以將所有進程分為兩部分：①提議者(Proposer)進程，即編號不大于 n+12 的進程，它們所提出的值有可能會成為最終的決定值；②參與者(Participant)進程，它們只是參與整個共識算法的運行，而不能成為最終決定值的提議者。如果在第一階段中有一個提議者進程在等待 n+12 個進程消息過程中，收到了其他所有提議者進程的消息，并且它們提出的值相同時，這個進程就可以決定這個值，從而在第一階段完成共識。這種情況也是常見的，如在由一個三臺備份機組成的主動復制容錯系統中，要求對處理一個消息的前后次序進行共識，在這種情況下，消息到達三臺備份機的次序在大多數情況下是相同的。同時考慮到崩潰情況的發生概率比較低，因此我們考慮一種快速達成共識的方法。在PR算法的第一階段中加入對消息來源的判斷，假如某個提議者進程收到所有提議者進程的消息，并且提出值相同，那么這個進程就可以決定這個值，完成共識。下面是對算法的證明。有效性通過算法描述不難證明，下面證明終止性和一致性。 （1）終止性。因為系統要求崩潰進程數目不能超過進程總數的一半，所以提議者進程中至少有一個進程Pi是正確的，那么根據部分同步模型的定義，在經過系統穩定時間以后，Pi就成為其他所有正確進程的Leader，并且最終得到大部分進程的認可，從而完成共識，達到終止性的要求。 （2）一致性。假如在算法的執行過程中，某個進程在第一階段決定了值v，這個進程必然是提議者進程，而且這時提議進程值均為v，那么在此后的運行過程中，如果有進程決定某個值v′，那么v′必然等于值v，從而滿足一致性的要求，其余證明等同于PR算法的證明。 3試驗和算法評估 在本節中，我們通過模擬實驗來顯示在執行相同工作量時PR算法和改進后算法的性能對比。實驗操作系統為Linux，實驗平臺為NEKO[5]。在大多數時間下，進程均處于正常運行中，所以我們主要給出在沒有出現崩潰進程的情況下的模擬試驗結果。分別考慮了進程總數n=3和n=5兩種情況下兩種算法的數據對比，實驗的結果是通過NEKO時間觀察器來收集的。所有的進程同時開始運行，完成一次共識所需要的時間為最快完成共識的進程所消耗的時間。測試的Consensus的類型為Binary Consensus，因此確保各個進程提出的值有可能相同。改進算法所得出的時間值為平均值，兩次共識之間有一定的時間間隔。表1和表2分別是PR算法和改進后算法在進程總數n=3和n=5的執行時間。圖4為其執行時間對比圖。 表1進程總數n=3時兩種算法執行時間 表2進程總數n=5時兩種算法執行時間 圖4PR算法和改進后算法的執行時間對比 4結束語 異步系統模型下的共識問題是容錯方面的關鍵問題，基于失效檢測器的共識算法是解決共識問題的重要途徑。從最早的四階段CT算法到兩階段的MR算法和PR算法等，研究者提出了很多種方案。本文在PR算法的基礎上，結合一種Ω類失效檢測器的設計方法對算法提出改進，改進后的算法在特定情況下，可以在第一階段完成共識。經實驗證明，該算法具有更短的響應時間和較少的通信量。 參考文獻： ［1］M J Fischer， N A Lynch， M D Paterson. Impossibility of Distributed Consensus with One Faulty Process[J]. Journal of ACM，1985，32(2):374382. ［2］T Chandra， S Toueg. Unreliable Failure Detectors for Reliable Distributed Systems[J]. Journal of ACM，1996，43(2):225267. ［3］M Larrea， A Fernandez， S Arevalo. Optimal Implementation of the Weakest Failure Detector for Solving Consensus[C].The 19th IEEE Symposium on Reliable Distributed Systems(SRDS)，2000.334. ［4］A Mostefaoui， M Raynal. Leaderbased Consensus[J].Parallel Processing Letters， 2001，11(1)：95107. ［5］P Urb’an， X D’efago， A Schiper. NEKO： A Single Environment to Simulate and Prototype Distributed Algorithms[C].Beppu City: Proceedings of the 15th International Conference on Information Networking (ICOIN)，IEEE Computer Society，2001.503511. ［6］P Dutta， R Guerraoui. Fast Indulgent Consensus with Zero Degradation[C]. Proceedings of the 4th European Dependable Computing Conference (EDCC)， 2002.191208. ［7］M Hurfin， M Raynal. A Simple and Fast Asynchronous Consensus Protocol Based on a Weak Failure Detector[J]. Distributed Computing， 1999，12(4)：209223. ［8］R Guerraoui， et al. Information Structure of Indulgent Consensus[J].IEEE Transactions on Computers，20-04，53(4)：453466. 作者簡介： 王剛(1980)，男，河南洛陽人，碩士研究生，主要研究方向為容錯計算； 張大方(1959)，男，教授，博導，博士，主要研究方向為軟件容錯、網絡測試、軟件測試、可信系統與網絡； 楊金民(1967)，男，湖南寧鄉人，博士，主要研究方向為容錯計算、軟件容錯。 注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
