類Paxos共識算法研究進展

王 江 章明星 武永衛(wèi) 陳 康 鄭緯民

(清華大學計算機科學與技術(shù)系 北京 100084) (北京信息科學與技術(shù)國家研究中心 北京 100084) (清華大學深圳研究生院 廣東深圳 518055)

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，單機服務(wù)早已無法滿足業(yè)務(wù)需求，越來越多的應(yīng)用需要分布式系統(tǒng)的支持.由于數(shù)據(jù)量的快速增長，集群機器數(shù)目越來越大，因為服務(wù)器宕機等問題使得各類業(yè)務(wù)組件失效的可能性也越來越高.如何保證服務(wù)的可靠性和高可用性變得越來越重要.

副本復制技術(shù)是提供可靠性的基礎(chǔ)技術(shù)之一，為數(shù)據(jù)或者服務(wù)提供冗余.副本狀態(tài)機能夠在有效隱藏服務(wù)器宕機問題的情況下，保證整個系統(tǒng)的強一致性,是分布式容錯系統(tǒng)的一個基本結(jié)構(gòu).圖1是副本狀態(tài)機的基本原理，圖1中展示了上下2個副本狀態(tài)機的狀態(tài)變化過程，實際中可能用到更多的副本狀態(tài)機來保證更高的可靠性.2個狀態(tài)機的初始狀態(tài)都為S0，此后每1個狀態(tài)變化都是一樣的，且狀態(tài)變化是具有確定性的.“確定性”的含義是只要輸入相同，由輸入引起的狀態(tài)變化是確定且唯一的.根據(jù)數(shù)學歸納法，在保證了初始狀態(tài)一樣、狀態(tài)切換順序一致的情況下，所有狀態(tài)機到達的最終狀態(tài)也是一樣的.

Fig. 1 The principle of replicated state machine圖1 副本狀態(tài)機工作原理

越來越多的系統(tǒng)使用副本狀態(tài)機作為核心協(xié)同服務(wù)，例如Google公司的Spanner[1]、Oracle公司的MySQL[2]等數(shù)據(jù)庫系統(tǒng)，以及Ceph[3]等分布式文件系統(tǒng).為了能夠發(fā)揮副本狀態(tài)機技術(shù)的優(yōu)勢，也陸續(xù)有機構(gòu)將該技術(shù)實現(xiàn)成為一種獨立的可靠性服務(wù)，如Google公司的chubby[4]、Yahoo!公司的ZooKeeper[5-6]、騰訊公司的phxpaxos[7]以及CoreOS公司的etcd[8]等.

維護副本之間的強一致性就是讓一組副本進程(通常分布在不同服務(wù)器上)共同決策一系列操作的順序.于是核心問題就是在多機情況下，如何讓各個副本進程就某個操作達成一致，這就涉及到分布式共識算法(distributed consensus algorithm).Paxos就是一個著名的分布式共識算法.從Lamport[9-10]提出Paxos算法開始，此后基于Paxos變形的分布式共識算法越來越多.近些年來，網(wǎng)絡(luò)方面RDMA、軟件定義網(wǎng)絡(luò)(sofware defined networking， SDN)等技術(shù)發(fā)展迅猛，也有部分研究人員結(jié)合網(wǎng)絡(luò)技術(shù)的發(fā)展和變化以及具體硬件重新設(shè)計共識算法提升分布式系統(tǒng)的性能.

本文主要從Paxos算法演進歷程的角度出發(fā)，介紹在Paxos演進過程中4個關(guān)鍵的變種算法，并對這些算法作一些對比分析以及適用場景說明.同時也簡要介紹了最近幾年類Paxos算法在實現(xiàn)和使用上的一些新的優(yōu)化思路.希望籍此能夠幫助推進相關(guān)算法的進一步改進和使用，并為分布式容錯場景下共識算法的選擇提供參考.

1 分布式共識

分布式共識算法試圖讓一組分布式的進程達成共識，共同決定1個值.總體來說，一個正確的分布式共識算法需要滿足4個基本條件：

1) 可終結(jié)性(termination).每個正常工作的進程最終都會決定1個值.

2) 合法性(validity).如果1個進程決定1個值,那么這個值一定是某個進程提出的，這避免了一些只決定無意義值的算法.

3) 完整性(integrity).決定出來的值不能被修改，結(jié)論不能推翻.

4) 一致性(agreement).所有正常的進程都只能同意同一個值.

以上4個條件，常常被歸結(jié)為2個方面：活性(liveness)和安全性(safety).活性主要包含可終結(jié)性；安全性方面主要包含合法性、完整性以及一致性.

解決分布式共識問題最基本的解決思路就是投票.一組相互獨立的進程之間進行投票操作，一旦投票的結(jié)果被大多數(shù)進程(quorum)所認可，就可以被認為是完成了共識過程.當然，這其中會涉及到網(wǎng)絡(luò)的消息延遲、消息重復，以及節(jié)點的宕機、掉線等情況.雖然基本的思路很簡單，但是給出一個切實可行的算法非常不容易.其中一個非常著名的算法就是由Lamport[9-10]提出的Paxos算法.

2 Paxos算法

Paxos算法中定義了3種角色：提議者(Proposer)、接受者(Acceptor)以及學習者(Learner).3種角色的作用如表1所示：

Table 1 The Function of the Roles in Paxos表1 Paxos算法中的角色及其作用

Paxos 算法基于一系列的假設(shè)，其中2個關(guān)于通信方面的假設(shè)：

1) 異步通信環(huán)境，即多個進程中的操作指令可以以任意速度執(zhí)行，多個進程之間的通信時間或長或短，通信消息在傳遞過程中可能會發(fā)生丟失、順序錯亂以及多次重復發(fā)送，也允許進程執(zhí)行失敗退出，退出后也可能會再次啟動并運行；

2) 非拜占庭模型，即每個參與共識的進程都忠實地遵守算法約束，不參與破壞，不篡改消息.

在實際分布式系統(tǒng)中，異步通信普遍存在，同時用于做共識的節(jié)點往往都運行在數(shù)據(jù)中心中，能夠保證大多數(shù)情況下節(jié)點不被劫持，且節(jié)點之間通信正常，因此這2點假設(shè)具有比較好的普適性.后來出現(xiàn)的很多共識算法的設(shè)計也都是基于這2點假設(shè)的，本文將基于這2個假設(shè)的分布式共識算法統(tǒng)稱為類Paxos算法.

一般來說，假設(shè)分布式系統(tǒng)中有2F+1個副本進程，這些算法通常容忍其中F個副本進程故障，即失效.也就是說只要其中有F+1個副本進程正常工作，系統(tǒng)就能夠正常提供服務(wù).

Paxos算法關(guān)鍵的地方在于提議者不能隨便提出自己的提議.原因很簡單，如果系統(tǒng)中所有的接受者已經(jīng)達成了一致的意見，那么提議者就不能提出有可能破壞一致意見的提議.這么做的原因當然是為了滿足分布式共識算法的上述4點性質(zhì).這樣，Paxos算法分為2個階段:1)提議者去了解一下當前接受者群體的一些情況；2)提出合適的提議.這樣的2個階段如圖2所示，分別被稱為準備提議階段和接受提議階段.

Fig. 2 The main procedure of Paxos圖2 Paxos算法主要過程

階段1. 準備提議階段.

階段1.1. 提議者準備提案編號n，向系統(tǒng)中大多數(shù)(超過半數(shù)以上)接受者發(fā)送這個編號n，消息被稱作是Prepare消息.

階段1.2. 接受者接收到帶有提案編號為n的Prepare 消息.根據(jù)接受者之前是否接受過比n編號更大的Prepare消息，接受者有2種狀態(tài)：1)接受過；2)沒有接受過.針對第1種狀態(tài)，接受者直接忽略編號為n的消息即可.在第2種狀態(tài)下，根據(jù)是否接受過階段2.2的Accept消息，又分為2種情況：1)沒有接受過；2)接受過.接受者的任務(wù)是將自己的最新狀態(tài)反饋給提議者，這個最新狀態(tài)包括自己接受過的最大提案編號以及提案內(nèi)容.沒有接受過則反饋空集即可.

階段2. 接受提議階段.

階段2.1. 提議者收到半數(shù)以上的接受者反饋的情況之后，會向所有接受者發(fā)送Accept消息，這個Accept消息中包含提案編號和提案內(nèi)容.提案編號在之前就確定了，關(guān)于提案內(nèi)容有2個來源.首先，可能有一部分接受者反饋了它們之前接受過的提案，提議者會從中選擇一個提案編號最大的提案內(nèi)容作為Accept消息中的提案內(nèi)容.其次，如果接受者反饋的提案的內(nèi)容都為空，那么提議者可以任意選擇一個值作為Accept消息的提案內(nèi)容.

Fig. 3 Livelock in Paxos圖3 Paxos算法中的活鎖

階段2.2. 如果接受者接收到了提案編號為n的Accept消息，且在此之前接受者沒有響應(yīng)過具有比編號n更大的消息，那么接受者接受這個Accept消息，即接受這個提案.

對于學習者而言，它們的工作比較簡單，就是調(diào)查接受者，看看是不是有大多數(shù)的接受者接受了相同的提案(包括提案編號以及提案的值).若有，則算法結(jié)束;若沒有，投票需要繼續(xù).算法中角色的分配是靈活的，在實際系統(tǒng)中，一個副本進程可以同時扮演多個角色.

3 類Paxos算法發(fā)展以及分類

第2節(jié)介紹了基礎(chǔ)Paxos算法原理，系統(tǒng)經(jīng)歷2個階段可以確定一個操作或值.這一整個過程可被稱為一個實例(instance).一個實例是不夠的，多個實例可以用來維護副本狀態(tài)機的一致，即可以形成副本狀態(tài)機所必須的日志序列.在執(zhí)行一個實例時，可能會出現(xiàn)如圖3所示的活鎖情況，圖3中ServerA和ServerE反復交替執(zhí)行2個階段形成活鎖，Paxos算法并不能保證這種情況不會出現(xiàn).從原則上來看，活性的條件并不能保證，不能保證算法一定得出一個最終的共識結(jié)果.為了能夠讓算法盡量得出共識結(jié)果，類Paxos算法還需要一個重要的假設(shè)，即在一段時間內(nèi)大部分的參與者以及它們之間的網(wǎng)絡(luò)連接是良好的.實際系統(tǒng)的情況也符合這樣的假設(shè).這一段時間就被用來完成共識過程.

有了上述假設(shè)之后，在實際實現(xiàn)過程中，通常需要在系統(tǒng)中選取一個唯一的領(lǐng)導者來盡量避免活鎖情況的出現(xiàn).選完領(lǐng)導者以后的一段時間內(nèi)，所有操作指令的先后順序都由領(lǐng)導者決定.當然這個領(lǐng)導者是可變化的，即當領(lǐng)導者進程發(fā)生故障后，系統(tǒng)通過選舉算法產(chǎn)生新的領(lǐng)導者，再繼續(xù)提供服務(wù).從Lamport[9-10]提出Paxos算法以來，有許多類Paxos共識算法研究陸續(xù)出現(xiàn)，以適應(yīng)不同的工程實踐環(huán)境.其中，就有一類采用了類似上文選取穩(wěn)定領(lǐng)導者的思路，本文將這一類算法稱作為強領(lǐng)導者(leader-based)共識算法.

當然，隨著研究的深入，也有研究人員發(fā)現(xiàn)了一些新的思路：不通過選舉產(chǎn)生領(lǐng)導者，每個副本進程都作為一個弱化的領(lǐng)導者，負責一部分請求的提交工作.通過其他約束來滿足安全性和活性條件，使得多個進程之間達成共識.本文將這一類算法稱作為弱領(lǐng)導者(leaderless)共識算法.

3.1 強領(lǐng)導者共識算法

在第3節(jié)引言中也提到，強領(lǐng)導者共識算法的主要思路是引入一個穩(wěn)定的領(lǐng)導者，在一段時間內(nèi)，所有的值都由這個領(lǐng)導者來決定.在這個過程中，需要考慮3個問題：

1) 正常情況下的日志復制；

2) 領(lǐng)導者失效以后選取新的領(lǐng)導者，系統(tǒng)開始時沒有領(lǐng)導者屬于這種情況的一種特例；

3) 成員更新問題，即系統(tǒng)內(nèi)的成員發(fā)生變化，如何做配置切換.

在實際實現(xiàn)過程中，為了解決這3個問題，同時保證安全性條件，且盡量滿足活性條件，研究人員提出了各種強領(lǐng)導者共識算法.在類Paxos算法發(fā)展歷程中，先后出現(xiàn)了4種比較典型的強領(lǐng)導者共識算法：

1) Multi-Paxos[10-11]是將Paxos算法應(yīng)用到工程實踐中，通過對Paxos算法中所缺失的對于實際情況的補充來構(gòu)造完成的算法；

2) VR (viewstamped replication)是Liskov等人[12-13]為了替換2階段提交協(xié)議而設(shè)計的復制算法，主要用于數(shù)據(jù)庫系統(tǒng)和分布式文件系統(tǒng)；

3) ZAB[6](ZooKeeper’s atomic broadcast)是雅虎公司為了實現(xiàn)分布式協(xié)同服務(wù)而設(shè)計的一種可以支持崩潰恢復的原子廣播算法；

4) Raft是Ongaro等人[14]為了讓技術(shù)人員更好地理解、學習以及實現(xiàn)副本狀態(tài)機而設(shè)計的分布式共識算法，展現(xiàn)了副本狀態(tài)機實現(xiàn)過程中的各個細節(jié).

根據(jù)實際實現(xiàn)過程中需要考慮的問題，可以將強領(lǐng)導者共識算法分為3個部分：正常情況下的復制、領(lǐng)導者失效情況下的領(lǐng)導者選取以及成員更新.實際上4種算法描述基本都是圍繞著這3個部分進行的.從強領(lǐng)導者共識算法的3個部分闡述4種算法在3個部分中采取的不同方法，以及不同方法在解決共識問題中對于安全性和活性所做的考慮.4種算法的描述中使用了一些類似的概念，但是表述不同，列舉在表2中.在4種算法中，副本進程在不同時期會擁有不同狀態(tài)，狀態(tài)大致分為3種：正常情況下的領(lǐng)導者、正常情況下的追隨者以及在領(lǐng)導者失效過程中重新選舉的中間態(tài).

Table 2 The Confrontation of Some Concepts in Leader-Based Distributed Consensus Algorithms表2 強領(lǐng)導者共識算法相關(guān)概念對比

3.1.1 正常情況下的復制

正常情況下，強領(lǐng)導者共識算法中都存在一個領(lǐng)導者進程，其主要的任務(wù)是接收來自客戶端的請求，將其轉(zhuǎn)換成為副本狀態(tài)機中的一個日志項.通過復制階段的算法約束讓其他副本進程接受這個日志項，而又不違反安全性條件.4種算法在這個階段中的差別比較小，下面將對4種算法在這一階段的表現(xiàn)形式作簡要描述.

3.1.1.1 Multi-Paxos算法

領(lǐng)導者進程接收客戶端請求后，在本地形成提案，并執(zhí)行基礎(chǔ)Paxos算法的第2個階段將提案發(fā)送給其他副本進程，如圖4所示.

3.1.1.2 VR算法

領(lǐng)導者進程接收客戶端請求，將請求添加到本地日志末端，然后向其他追隨者進程發(fā)送這個請求，編號為n.追隨者進程在接收這一請求之后會作一個檢查，查看本地的日志中是否包含所有編號小于n的日志項，若不包含，則等到全部包含為止.滿足上述條件以后，追隨者進程會給領(lǐng)導者進程一個回復.領(lǐng)導者進程在收到F個追隨者進程的回復以后，在本地提交并且執(zhí)行這個請求，將執(zhí)行結(jié)果回復給客戶端.其他追隨者進程想要獲知這個請求是否需要提交并且執(zhí)行則需要客戶端發(fā)起下一個請求，領(lǐng)導者在下一個請求中攜帶提交通知一起發(fā)送給追隨者進程.若沒有，則領(lǐng)導者一段時間以后自己廣播Commit消息，通知追隨者進程提交相對應(yīng)的請求.這個Commit消息本身也起到判斷領(lǐng)導者進程和追隨者進程之間的網(wǎng)絡(luò)連接是否正常的心跳作用，如圖5所示.

Fig. 4 Normal case in Multi-Paxos圖4 Multi-Paxos 正常復制階段

Fig. 5 Normal case in VR圖5 VR算法正常復制階段

3.1.1.3 ZAB算法

領(lǐng)導者進程接收到客戶端請求后，本地形成1個事務(wù)，并給事務(wù)分配1個遞增的事務(wù)編號 (1個64 b的整數(shù)，前32 b表示事務(wù)所在的任期，后32 b表示任期內(nèi)的事務(wù)編號).然后，領(lǐng)導者進程向其他副本進程發(fā)送事務(wù)提案.其他副本進程接收到事務(wù)提案以后，將事務(wù)寫到本地磁盤，然后向領(lǐng)導者進程發(fā)送確認消息.領(lǐng)導者進程收到F個以上副本進程的確認消息后，向所有的副本進程廣播Commit消息.副本進程收到Commit消息時，提交該事務(wù).

3.1.1.4 Raft算法

領(lǐng)導者進程接收客戶端請求，將請求記錄成日志項的形式，并把日志項發(fā)送給其他追隨者進程，如圖6所示.領(lǐng)導者將T3日志項發(fā)送給其他2個追隨者完成復制過程.日志提交有2個限制條件：

1) 如果當前日志項屬于領(lǐng)導者當前任期，那么當這個日志項發(fā)送給過半數(shù)以上的副本進程并得到正確回應(yīng)以后，日志項即可標記為已提交；

2) 如果當前日志項屬于之前領(lǐng)導者的任期，那么這個日志項是否被提交的依據(jù)是它的下一條日志項是否已經(jīng)提交，也就是下一個日志項的提交會順便將之前所有的日志項標記為已經(jīng)提交.

Fig. 6 Normal case in Raft圖6 Raft算法正常復制

為了追隨者進程和領(lǐng)導者進程維護的操作日志保持一致，在新的領(lǐng)導者產(chǎn)生后，領(lǐng)導者需要知道追隨者跟它保持一致的日志位置，然后從這個位置后的第1個位置開始執(zhí)行復制操作.

追隨者獲知日志項是否提交的方式跟VR算法類似，也是領(lǐng)導者通過下一個日志項來廣播提交通知，追隨者進程獲得通知以后更新本地日志項的狀態(tài).在沒有請求到達的時候，Raft算法會定期地廣播空的日志項作為心跳消息.

3.1.1.5 小結(jié)

從3個方面比較4個算法的不同點：日志項提交的判斷、日志項是否連續(xù)以及追隨者進程獲知日志項提交的方式.

1) 日志項提交條件.4種算法對于1個日志項是否提交具有1個基本原則，即過半進程回復確認以后，即表示這個日志項可以提交；Raft算法則對于不屬于當前任期的日志項，有特殊判斷.

Fig. 8 View change in VR圖8 VR算法的視圖切換

2) 日志項是否連續(xù).Multi-Paxos算法的日志序列是允許有空洞的，如圖7所示.對于FollowerA來說沒有接收到日志項x=3,不影響其接受x=4.其他3種算法則要求日志連續(xù)，VR算法在算法描述中強調(diào)了這一特征， ZAB算法和Raft算法則隱含了這個特征.

Fig. 7 The empty instance of Multi-Paxos圖7 Multi-Paxos算法中的日志空洞

3) 獲知日志項需要提交的方式.Multi-Paxos和ZAB算法都有獨立的廣播提交通知的階段.VR和Raft算法則將提交通知隱含在下一個請求中，這個請求可以是來自客戶端的請求或者領(lǐng)導者的心跳信息.心跳消息在VR算法中表現(xiàn)為Commit消息，在Raft算法中表現(xiàn)為空日志項.

3.1.2 領(lǐng)導者選取

強領(lǐng)導者共識算法的一個重點就是在領(lǐng)導者失效的時候選出新的領(lǐng)導者并且需要保證在選舉過程中系統(tǒng)狀態(tài)的正確性.這里需要解決2個問題： 第1問題是正確選舉產(chǎn)生新的領(lǐng)導者；第2問題是選舉產(chǎn)生新的領(lǐng)導者以后，如何保證新的領(lǐng)導者以1個正確的狀態(tài)開始新的任期，對于原來已經(jīng)提交的內(nèi)容不再推翻.為了避免舊領(lǐng)導者的影響，因此有了任期這個概念，新的領(lǐng)導者任期編號大于舊領(lǐng)導者任期編號.

3.1.2.1 Multi-Paxos算法

在Multi-Paxos算法中，選舉算法是相對比較靈活的.文獻[11]中提到，在選舉階段，副本進程會產(chǎn)生一個任期編號，這個編號大于它之前見到的所有任期編號.然后，這個副本進程向所有副本進程發(fā)送這個任期編號.如果半數(shù)以上的副本進程都回復表示沒有見過比這個任期編號更大的編號，那么該副本進程就作為新的領(lǐng)導者，這個回復消息被稱為Promise消息，即發(fā)送了Promise消息的副本進程將不再回應(yīng)來自舊任期的領(lǐng)導者的消息.與此同時，這個Promise消息中，也包含了副本進程最近見過的任期，以及這個任期內(nèi)接受的最后一個日志項.至于選舉的觸發(fā)操作可以通過簡單的超時機制實現(xiàn).

領(lǐng)導者進程從收到的Promise消息中選擇一個離自己任期最近的日志項，將這個日志項作為恢復的結(jié)束點.然后領(lǐng)導者進程只需要1個讀階段就能夠?qū)⒆约旱臓顟B(tài)和其他副本進程恢復到一致.而讀階段可以簡單理解為在日志空洞位置執(zhí)行基礎(chǔ)Paxos算法的第1個階段去發(fā)現(xiàn)其他進程在對應(yīng)位置上的值就可以，然后把這些位置上的值重新提交即可.

3.1.2.2 VR算法

當系統(tǒng)中的追隨者進程一段時間沒有收到領(lǐng)導者進程的普通請求消息或者Commit消息時，追隨者進程就會進入領(lǐng)導者選舉，選舉主要分為3個過程.首先追隨者進程將狀態(tài)轉(zhuǎn)換為視圖切換狀態(tài)，即表示不再接受來自其他進程的請求.VR算法為領(lǐng)導者選取階段定義了3種消息，如圖8所示.3種消息也對應(yīng)了3個過程.START-VIEW-CHANGE的主要作用是告知其他追隨者自己進入新的任期，同時在此過程中選出一個最高的任期作為新的任期，擁有最高任期且得到多數(shù)派認可的副本進程出任領(lǐng)導者.這個過程類似于Paxos算法的第1個階段.DO-VIEW-CHANGE作為第2個過程其主要作用是，非領(lǐng)導者進程向領(lǐng)導者進程發(fā)送自己的本地日志.領(lǐng)導者收集完過半進程的日志序列后，確認自己進入領(lǐng)導者狀態(tài)，從收集的日志序列中選出一個最新日志作為新任期的初始狀態(tài).第3個過程START-VIEW的作用則是，新的領(lǐng)導者向所有副本進程宣布其領(lǐng)導者身份，并告知它們進入新的任期，將本地狀態(tài)切換為新的狀態(tài)，開始進入追隨者狀態(tài)正常工作，完成視圖切換過程.VR算法的選舉橫跨了第1，2個過程.對于新任期正確狀態(tài)的確定則主要體現(xiàn)在第2，3個過程.

3.1.2.3 ZAB算法

在ZAB算法中，每個進程有3種狀態(tài)，即選舉狀態(tài)、追隨狀態(tài)以及領(lǐng)導狀態(tài).正常情況下，副本進程會向領(lǐng)導者進程發(fā)送心跳信息，當領(lǐng)導者進程一段時間沒有收到多數(shù)副本進程的心跳消息時，它就進入選舉狀態(tài).同時如果副本進程發(fā)現(xiàn)領(lǐng)導者進程失效或者讓出了領(lǐng)導者的位置，它也會將自己的狀態(tài)切換為選舉狀態(tài).在ZooKeeper中選舉算法有多種，最經(jīng)典的選舉算法是Fast leader election算法，思路就是每個副本進程都會維護一個投票箱，用以保存投票請求并且統(tǒng)計選票.進入選舉階段以后，系統(tǒng)經(jīng)歷2個過程.

1) 候選者進程向其他副本進程發(fā)送請求投票消息，請求投票消息內(nèi)容主要包含2個信息：①副本進程編號；②副本進程本地最后一個事務(wù)的編號.此后的過程就是每個副本進程在接收到投票消息以后，如果它認可這個投票，它會統(tǒng)計這個投票，同時向外廣播這個投票.對于判斷是否認可的條件主要依賴于投票內(nèi)容和副本進程本地狀態(tài)的對比.直到有過半進程都接受了某一個投票內(nèi)容，則第1個過程結(jié)束，產(chǎn)生了新的準領(lǐng)導者.

2) 準領(lǐng)導者將會向其他副本進程發(fā)送新任期通知，其他副本進程收到新任期通知以后會將本地狀態(tài)更新，并且會向新的準領(lǐng)導者發(fā)送確認消息，確認消息中就包含本地最新的事務(wù)日志.準領(lǐng)導者收到過半副本進程的回復以后，會從回復消息中選擇一個最新的事務(wù)日志作為新任期初始化的事務(wù)集合，此時領(lǐng)導者也就確認了自己的領(lǐng)導者身份.

為了提高數(shù)據(jù)同步效率，領(lǐng)導者為每個支持它的副本進程維護一個FIFO隊列，將新的事務(wù)日志中未提交的事務(wù)放入隊列，同時向隊列中加入Commit消息.而通信模塊則負責將各個隊列里的消息順序發(fā)送給對應(yīng)的副本進程，同步過程即是恢復過程.至此完成視圖切換，然后開始接收客戶端的請求，提供服務(wù).

3.1.2.4 Raft算法

Fig. 9 Leader election in Raft圖9 Raft算法選取領(lǐng)導者

Raft算法為副本進程定義了3種不同角色：領(lǐng)導者、候選者和追隨者，分別對應(yīng)了副本進程在不同時期的狀態(tài).同時，Raft算法用一種心跳機制(heartbeat)來觸發(fā)選舉過程，如圖9所示.當系統(tǒng)啟動時，所有的副本進程都會被初始化為追隨者，領(lǐng)導者會向所有追隨者發(fā)送心跳信息來確保領(lǐng)導者和其他追隨者連接正常.如果有追隨者在1個周期內(nèi)沒有收到心跳信息，它就會認為當前系統(tǒng)中沒有領(lǐng)導者，然后把自己的狀態(tài)轉(zhuǎn)換成候選者狀態(tài)，并增加當前任期編號，發(fā)起1輪投票.如果1個候選者在1個任期內(nèi)收獲了半數(shù)以上的副本進程給它投票，那它就會將自己的狀態(tài)轉(zhuǎn)化為領(lǐng)導者.投票請求中的內(nèi)容包含3個重要信息：候選者新的任期、候選者本地最新日志項的任期以及日志編號.判斷是否投票的條件，首先投票請求中的新任期比副本進程本地任期要大，這一條件不滿足則不投票；其次，對比投票請求中的日志任期和副本進程本地最后一個日志項的任期，投票請求的日志任期較小，則副本進程不投票，相同則比較日志項編號，投票請求中的日志項編號較小則不投票.總結(jié)一下就是，投票請求內(nèi)容比副本進程本地狀態(tài)更超前，則副本進程認可這個投票，否則就不投票.

3.1.2.5 小結(jié)

新領(lǐng)導者開啟新的任期以后，就開始正常的日志復制工作，復制過程初始階段不可避免地涉及到對于舊任期日志的處理，在3.1節(jié)的日志復制階段有相關(guān)說明.

總體上，選取新的領(lǐng)導者是因為舊的領(lǐng)導者失效，出于安全性考慮，同一任期最好只有1個領(lǐng)導者，因為多個領(lǐng)導者可能造成日志序列不一致.因此，4種算法在選舉階段的目標也是相對明確的，即在1個任期內(nèi)選出1個領(lǐng)導者，選舉操作本身成功與否都不能影響系統(tǒng)安全性.對于領(lǐng)導者選舉部分來說，有4個關(guān)鍵方面：1)選舉觸發(fā)條件;2)副本進程當選領(lǐng)導者的條件;3)確定任期內(nèi)領(lǐng)導者的唯一性;4)新任期系統(tǒng)狀態(tài)的確定.

1) 選舉觸發(fā)條件.Multi-Paxos算法和ZAB算法中副本進程和領(lǐng)導者進程之間會維護獨立的雙向心跳消息，所謂雙向指的是領(lǐng)導者到追隨者、追隨者到領(lǐng)導者.ZAB算法選舉觸發(fā)是2個方面的，可以來自于領(lǐng)導者自身或者追隨者進程.VR算法和Raft算法則主要是領(lǐng)導者向追隨者發(fā)送心跳消息，追隨者在一段時間沒有收到心跳消息以后會觸發(fā)選舉操作.心跳消息也不一定是單獨設(shè)置的.在VR算法中，心跳消息可以是普通請求消息或者提交通知.對于Raft算法來說，心跳消息是正常的日志項或者空的日志項.

2) 副本進程當選領(lǐng)導者的條件.4種算法判斷領(lǐng)導者當選的條件是一致的，即該領(lǐng)導者進程得到了過半副本進程的認可.VR和ZAB算法對于領(lǐng)導者當選的判斷可以是由候選者本身統(tǒng)計，其他副本進程也有統(tǒng)計.Multi-Paxos和Raft算法主要是候選者向別人征集投票，自己統(tǒng)計.

3) 確定任期內(nèi)領(lǐng)導者的唯一性.4種算法本質(zhì)上都限制在某一個任期內(nèi)只投1次票.在這種情況下，要么形成分票的局面，即沒有1個候選者獲得過半進程認可;要么就選出1個領(lǐng)導者，而這個領(lǐng)導者，在這個任期內(nèi)是唯一的.對于分票情況，4種算法都是通過超時，然后增加任期編號，重新選舉.為了選舉能夠盡快成功，ZAB和VR算法通過不停廣播選票信息，使得盡可能多的副本進程參與選舉.Raft算法則通過隨機化超時時間來降低再次分票的可能性.

4) 新任期系統(tǒng)狀態(tài)的確定.Multi-Paxos算法新任領(lǐng)導者在確定日志恢復結(jié)束點之后，領(lǐng)導者進程會將自己的狀態(tài)同步到日志恢復結(jié)束點的狀態(tài)，然后開始正常工作；VR和ZAB算法則是向其他副本進程征集，在半數(shù)以上副本進程的日志序列中，選一個最新的日志作為新任期初始狀態(tài)，實現(xiàn)上有些小的差別；Raft算法則是在選舉的時候就要求候選者符合一定條件，其他副本進程才會給它投票，選出來的領(lǐng)導者本身就有比較全面的狀態(tài).

3.1.3 成員更新

成員更新也是分布式系統(tǒng)中經(jīng)常會遇到的問題，涉及到系統(tǒng)規(guī)模的縮小和擴大.一個最簡單的思路是把當前系統(tǒng)停掉，停止期間不接收客戶端請求，然后更換配置再重啟系統(tǒng)，等系統(tǒng)恢復正常以后，開始對外提供服務(wù).然而，這樣不僅僅會影響系統(tǒng)的可用性，同時如果手工操作失誤很有可能造成無法恢復的局面.舊版本ZooKeeper就是這樣做的，ZAB算法中也不包含成員更新部分.成員更新頻率不高，在實際場景中也不如前面4個問題關(guān)鍵，因此很多算法都沒有考慮這個問題.

在文獻[9-10]中，提及了成員變更的方法，這一方法對于Multi-Paxos來說同樣適用，具體的思路是將成員變更操作看作是狀態(tài)機的一部分，可以通過操作指令去修改.當新配置出現(xiàn)時，將其形成一個提案通過Multi-Paxos算法去提交.提交條件還按照舊的配置，當新的配置提交并執(zhí)行時，系統(tǒng)切換到新的配置上來.

Raft算法提出了共同共識(joint consensus)的概念，指的是在集群進行配置調(diào)整的時候，讓系統(tǒng)先進入一個過渡狀態(tài)，這個過渡狀態(tài)稱為共同共識，一旦共同共識被提交，系統(tǒng)就可以切換成新的配置.共同共識的狀態(tài)可以理解為新舊配置結(jié)合的一種狀態(tài)，同時也是一種特殊的日志項.領(lǐng)導者會廣播這個日志項，讓日志項提交.

實際上，以上提到的成員變更方法，基本都是將集群的配置更新作為狀態(tài)機的一部分，這也是類Paxos共識算法都可以通用的思路.而為了系統(tǒng)具有更好的可用性，往往都會讓新加入的成員與老成員的狀態(tài)基本達到一致時再執(zhí)行配置更新.

3.1.4 強領(lǐng)導者共識算法總結(jié)

在上述的4種強領(lǐng)導者共識算法中很容易看到，在解決共識問題過程中，解決的思路有著緊密的聯(lián)系.4種算法都有類似于領(lǐng)導者進程這樣的角色，整體上由其負責多個副本進程之間達成共識的工作.4種算法中，領(lǐng)導者進程都需要等待超過半數(shù)以上的副本進程正確的回應(yīng)后才能夠就一個提案達成共識.當然不同算法，對于提案提交條件有不同限制.Multi-Paxos 被當作是基礎(chǔ)Paxos算法的一種具體實現(xiàn)形式，在文獻[10]中只是簡單提了一下，而實際上沒有系統(tǒng)而完整的描述.VR算法、ZAB算法以及Raft算法是對Multi-Paxos算法作出了更加嚴格的限制以及更加規(guī)范的、階段化的描述.同時，4種算法也有著不太一樣的設(shè)計原則.

對于舊領(lǐng)導者尚未提交的日志項，Raft算法是比較消極的，只有舊領(lǐng)導任期內(nèi)的日志項被過半復制或者日志項已經(jīng)提交，才能夠保證該日志項不被覆蓋.Multi-Paxos，VR，ZAB算法則相對比較激進，即便是舊領(lǐng)導者未過半復制的日志項，只要是新的領(lǐng)導者能夠獲知這個日志項的存在，也會將這個日志項重新提交，然而處理的方式可能會存在細微的不同.對于只在舊領(lǐng)導者本地存在的日志項，當這個舊領(lǐng)導者重新回到系統(tǒng)中的時候：Raft算法的處理方式是新的領(lǐng)導者會把自己本地的日志發(fā)送給回歸的舊領(lǐng)導者進程，覆蓋掉只在舊領(lǐng)導者本地存在的舊的日志項；Multi-Paxos算法和VR算法則采用恢復機制嘗試將舊的日志項覆蓋；ZAB 算法特別地設(shè)計了TRUNC指令用以刪除只在舊領(lǐng)導者本地存在的日志項，然后添加新的日志項.

隨著強領(lǐng)導者共識算法在工業(yè)界的盛行，如Chubby 使用Multi-Paxos算法,ZooKeeper使用ZAB算法以及etcd 使用Raft算法，強領(lǐng)導者共識算法在解決共識問題上更能被工程人員接受.因為后續(xù)出現(xiàn)的如Raft 算法，提供了完整的副本狀態(tài)機實現(xiàn)的描述，使得副本狀態(tài)機的實現(xiàn)以及共識算法的理解變得相對容易.

3.2 弱領(lǐng)導者共識算法

強領(lǐng)導者共識算法會有單個領(lǐng)導者在處理請求上的性能瓶頸問題.尤其在廣域網(wǎng)的情況下，客戶端和領(lǐng)導者節(jié)點可能不在同一個區(qū)域，跨域請求的延時會相對較高.因此，也有研究人員想基于基礎(chǔ)Paxos算法設(shè)計弱領(lǐng)導者共識算法.

3.2.1 Mencius算法

Mencius[15]算法就是為了解決單領(lǐng)導者共識算法存在的瓶頸問題而設(shè)計.在Mencius算法中，所有副本進程組成一個閉環(huán)，提前給這些副本進程分配好用以提出題案的空位編號，如圖10所示.通過這種方式，所有副本進程都輪流提出自己的提案.這樣做能夠提高系統(tǒng)吞吐率，尤其是在整個系統(tǒng)性能限制在CPU資源上的時候.因為日志空位上的指令提案由哪個副本進程負責提出是預(yù)先商定好的，通過這種形式也就省去了基礎(chǔ)Paxos算法中的準備提議階段，負責對應(yīng)空位的副本進程直接執(zhí)行接受提議階段即可.如果該副本進程暫時沒有提案可以提出，則在對應(yīng)空位填入空操作.這種做法給整個系統(tǒng)帶來更均衡的通信模式，進而能夠更好地利用閑置的網(wǎng)絡(luò)帶寬.當一個副本進程X失效或者處理速度很慢時，其余副本進程可以通過運行基礎(chǔ)Paxos算法中的準備提議階段，接管原本分配給X的空位，在接受提議階段只能提交空操作.判斷一個副本進程是否需要被接管可以簡單通過超時機制來實現(xiàn).

Fig. 10 The log of Mencius圖10 Mencius算法的日志

在正常情況下，系統(tǒng)中所有副本進程請求負載比較均衡，系統(tǒng)性能跟有固定領(lǐng)導者的Multi-Paxos算法是比較類似的，但是Mencius算法有效解決了單領(lǐng)導者性能瓶頸以及請求跨地域情況下網(wǎng)絡(luò)延時較高等問題.然而，當系統(tǒng)中有部分副本進程比較空閑，以及有部分副本進程很慢時，就會產(chǎn)生很多無效的空操作，進而使整個系統(tǒng)性能下降.為了解決這一問題，Mencius算法也提出了一些如租約機制等優(yōu)化手段，但是依然避免不了系統(tǒng)性能受限于最慢的副本進程.同時如果有副本進程失效，因為系統(tǒng)需要花費時間去檢測失效的副本進程，還需要有其他副本進程接管它負責的空位，這樣的開銷甚至比強領(lǐng)導者共識算法切換領(lǐng)導者更大.所以從可用性上來講，它有可能比強領(lǐng)導者共識算法表現(xiàn)得更差.為了避免以上Mencius算法的缺陷，卡內(nèi)基梅隆大學的研究人員提出了基于所有副本進程身份均等的EPaxos[16](egalitarian Paxos)算法.

3.2.2 EPaxos算法

EPaxos算法給出的設(shè)計思路是允許所有的副本進程從客戶端接收請求，并讓副本進程擁有只需要1個通信輪次就可以提交提案的權(quán)利.在這種情況下，系統(tǒng)就可以有效實現(xiàn)負載均攤，此外，還可以允許客戶端盡量選擇離自己較近的副本進程提交請求，從而解決跨地域請求延時較長的問題.基礎(chǔ)Paxos算法能夠?qū)崿F(xiàn)副本進程最少在2個通信輪次的情況下提交提案，達到同樣效果，也就是基礎(chǔ)Paxos算法的2個階段.EPaxos算法能夠?qū)崿F(xiàn)在1個通信輪次內(nèi)提交提案，讓其他副本進程接受，原因也就在于算法假設(shè)：沒有關(guān)聯(lián)的2個操作指令(即提案內(nèi)容)在所有副本進程上提交以及執(zhí)行的順序是無關(guān)緊要的.舉例來講，有2個副本進程A和B，A提出1個提案將x變?yōu)閤+1，B提出1個提案將y變?yōu)閥-1.2個提案所改變的對象是不相同的，那么它們的順序先后并不是很重要.基礎(chǔ)Paxos算法里有1個實例的概念，1個實例就是運行1輪Paxos算法，在對應(yīng)的1維日志項的空位里填上狀態(tài)機操作指令，這樣就形成了1個一致性操作序列.在EPaxos算法中，為了使得不同副本進程在提出提案過程中不會與其他副本進程在日志項排序上存在競爭，EPaxos算法將日志設(shè)計成了1個2維矩陣的形式.日志項編號為R.id，其中R表示的是副本進程的編號，id表示的是在副本進程R內(nèi)連續(xù)遞增的正整數(shù).每個副本進程都會維護這樣1個矩陣，用以記錄整個系統(tǒng)的狀態(tài)，如圖11所示.

Fig. 12 The main procedure of EPaxos圖12 EPaxos算法主要過程

Fig. 11 The log of EPaxos圖11 EPaxos算法的日志

在實際生產(chǎn)環(huán)境中，對于狀態(tài)機而言，操作指令之間完全不存在沖突的概率是比較低的.在操作指令存在沖突的情況下如何處理操作之間的順序也就成為了EPaxos算法設(shè)計過程中最主要解決的問題.

簡單來說，EPaxos算法主要貢獻在于無沖突操作指令可以在經(jīng)歷1個階段以后就可以提交并且執(zhí)行.在存在操作指令沖突的情況下，退化為2個階段的基礎(chǔ)Paxos算法.因此，EPaxos算法適用于沖突較少，甚至是沒有沖突的應(yīng)用場景.

3.2.3 弱領(lǐng)導者共識算法總結(jié)

弱領(lǐng)導者共識算法在設(shè)計的過程中需要考慮2個關(guān)鍵問題：

1) 沒有單個穩(wěn)定的領(lǐng)導者，怎樣使得請求在盡量少的通信輪次后被提交；

2) 當副本進程失效時，如何恢復.

針對問題1，弱領(lǐng)導者算法的解決思路是將領(lǐng)導者的責任均攤到每個副本進程上去.Mencius算法是將日志空位進行預(yù)分配，不選領(lǐng)導者而是每個副本進程輪流作為領(lǐng)導者主持日志項的提交.EPaxos算法則是組織了一種新的日志形式，將日志組織成為2維矩陣.每個副本進程都負責提交自己提出的日志項，作為自己提出的日志項的領(lǐng)導者，同時也維護其他副本進程提出的日志項的狀態(tài).

對于問題2，無論是Mencius算法還是EPaxos算法都需要通過其他副本進程接管的形式對于失效進程的日志項進行恢復.比較不同的是，EPaxos算法的性能不會像Mencius算法一樣受限于集群中較慢的節(jié)點，因為算法只要能夠從最快的多數(shù)派中拿到回復就可以對1個日志項進行提交.Mencius算法因為副本進程輪流當領(lǐng)導者角色的緣故，無法避免慢節(jié)點的影響.然而，EPaxos算法由于同時有多個領(lǐng)導者存在，通過將日志設(shè)計為2維矩陣的形式避免了不同領(lǐng)導者對于同一個日志項空位的競爭.但是為了多個進程間能夠拿到1個一致性順序，不得不做一些額外的設(shè)計.帶來的開銷也是多方面的，例如需要1個額外的階段來讓各個副本進程接受同一個操作指令以及依賴集合.恢復階段的設(shè)計也比較復雜，場景局限也很顯然.

3.3 2類算法對比

強領(lǐng)導者和弱領(lǐng)導者可以看作是Paxos算法2種不同的實現(xiàn)方向，從本質(zhì)上都是Paxos算法在實際使用中的一種擴展形式.在不同的適用場景中，工程人員會有不同方面的考慮.2類算法對比如表3所示：

Table 3 Contradistinction of Two Kinds of Distributed Consensus Algorithms表3 2類分布式共識算法的對比

4 類Paxos共識算法進一步改進

4.1 算法設(shè)計上的改進

Paxos算法的作者Lamport在后續(xù)研究中，給出了一些新的改進思路.Paxos算法中假設(shè)總副本進程數(shù)為2F+1,容忍F個副本進程失效，達成共識過程中只需要F+1個副本進程參與.Cheap Paxos[17]算法為了節(jié)約資源，在算法設(shè)計過程中只使用了F+1個副本進程，另外F個副本進程在正常情況下處于閑置狀態(tài).當正常工作的F+1個副本進程出現(xiàn)進程失效的情況時，閑置的副本進程就會出來替換失效的進程.當然，這一過程不可避免地會造成額外的恢復開銷.這一優(yōu)化雖然對性能沒有太大的提升，但是提出了一個更節(jié)約資源的思路.Shi等人[18]在他們的研究中設(shè)計了ThriftyPaxos算法，旨在構(gòu)建低成本高可用的副本狀態(tài)機.在ThriftyPaxos算法中，副本進程在處理請求的過程中，后臺同時進行恢復操作.這樣的設(shè)計改善了Cheap Paxos算法恢復慢、可用性差等缺陷.

在Multi-Paxos算法中，客戶端將請求先提交給領(lǐng)導者，然后再由領(lǐng)導者轉(zhuǎn)發(fā)給其他的接受者.Fast Paxos[19]算法則認為：從本質(zhì)上，領(lǐng)導者只應(yīng)該起到協(xié)調(diào)的作用，客戶端本身更清楚提案的內(nèi)容.Fast Paxos算法提出客戶端應(yīng)該直接將提案發(fā)送給接受者，在沒有沖突的情況下通信1輪直接提交，在有沖突的情況下，交由領(lǐng)導者協(xié)調(diào)處理，領(lǐng)導者協(xié)調(diào)完畢后在下1輪通信中完成提交.Fast Paxos算法因為不容易被理解以及實現(xiàn)過程比較復雜，很少被使用.這些改進實質(zhì)上可以看作是對于Paxos算法思想的一種延伸.

4.2 結(jié)合硬件特性的優(yōu)化

當前，越來越多的研究人員開始關(guān)注共識算法結(jié)合網(wǎng)絡(luò)環(huán)境和特定硬件的研究.隨著RDMA網(wǎng)絡(luò)技術(shù)的發(fā)展，類Paxos共識算法在設(shè)計和實現(xiàn)過程中出現(xiàn)了新的變化.Poke等人[20]基于RDMA原語設(shè)計了新的共識算法DARE.DARE算法跟Raft類似分為3個階段：領(lǐng)導者選取、日志復制和集群成員更新.主要貢獻在于引入了RDMA單邊操作：Read和Write.因為旁路服務(wù)端的單邊通信模式跟以往的雙邊通信模式有所區(qū)別，所以DARE重新設(shè)計了Raft共識算法.有效利用了RDMA單邊操作低延時的特性，使得副本狀態(tài)機的性能有了大幅度提升.

Wang等人[21]基于RDMA 原語實現(xiàn)了Multi-Paxos算法APUS.與DARE的不同之處在于APUS主要為通用服務(wù)器程序設(shè)計，而DARE主要是用于維護小型簡單的鍵值存儲.其次由于DARE中領(lǐng)導者進程負擔所有的過程，完全旁路其他副本進程，因此當客戶端連接數(shù)增多時，DARE會有嚴重的性能下降.APUS比DARE擁有更好的可擴展性，它采用了selective signaling[22]技術(shù)，領(lǐng)導者進程不必一直輪詢完成事件隊列(completion queue)獲取網(wǎng)卡的操作完成信號.此外，DARE中為了實現(xiàn)超低的請求延時，把所有數(shù)據(jù)都存在內(nèi)存中.APUS把日志數(shù)據(jù)都持久化到SSD硬盤中去，是一個通用型可持久化的系統(tǒng).

另一方面，分布式共識算法的實現(xiàn)跟網(wǎng)絡(luò)狀態(tài)和性能密不可分，對網(wǎng)絡(luò)性能和穩(wěn)定性有著比較高的要求.研究人員發(fā)現(xiàn)在網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中，有很多時間花費在操作系統(tǒng)網(wǎng)絡(luò)協(xié)議棧上，因此部分研究人員漸漸開始關(guān)注類Paxos共識算法在網(wǎng)絡(luò)設(shè)備中實現(xiàn)的研究.Speculative Paxos[23]使用可預(yù)測的網(wǎng)絡(luò)行為來改善Paxos算法的性能.它有效將IP多播、固定長度的網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及作為消息序列器的單個頂端交換機等技術(shù)組合在一起，消除了數(shù)據(jù)中心網(wǎng)絡(luò)中的重排現(xiàn)象.這個方法引入了MOM(mostly-ordered multicast)原語，可以最大程度上保證：所有接收者接收到的來自不同發(fā)送者的消息擁有一致性的順序，這使得數(shù)據(jù)中心中的網(wǎng)絡(luò)行為處于可預(yù)測狀態(tài)，客戶端的請求能夠在盡可能少的通信開銷內(nèi)被提交并執(zhí)行.

NetPaxos[24]主要提供了在SDN網(wǎng)絡(luò)交換機中，利用網(wǎng)絡(luò)中的消息順序?qū)崿F(xiàn)整個Paxos算法全部邏輯的詳細設(shè)計.同時，也表明了在不更改OpenFlow[25]API接口的情況下，僅僅依賴網(wǎng)絡(luò)交換機設(shè)備特性實現(xiàn)樂觀控制協(xié)議的可行性.它與Speculative Paxos最大的不同之處在于交換機設(shè)備本身會作為共識算法中的角色，共識算法邏輯運行在交換機中.Speculative Paxos只是利用網(wǎng)絡(luò)設(shè)備特性去優(yōu)化Paxos算法，共識算法相關(guān)邏輯還需要運行在服務(wù)器上.

與Speculative Paxos類似，NOPaxos[26](network ordered Paxos)也是將共識問題分為2個部分：1)網(wǎng)絡(luò);2)共識算法.Paxos算法的基本假設(shè)是網(wǎng)絡(luò)消息可以是亂序的、不可靠的.NOPaxos的思路是設(shè)計一個OUM (ordered unreliable multicast)原語,在網(wǎng)絡(luò)層面上提供有序不可靠的傳輸，這樣的原語在數(shù)據(jù)中心網(wǎng)絡(luò)中帶來的開銷近乎為零.有了這個原語，NOPaxos就可以利用消息傳遞過程中的有序性來減少協(xié)同過程中所需要的通信操作.在應(yīng)用層面只需要考慮網(wǎng)絡(luò)丟包情況即可.解決了亂序問題以后，達成共識就變得相對簡單，開銷也變得更小.當然和Speculative Paxos一樣，NOPaxos也依賴于數(shù)據(jù)中心固定網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及可靠性網(wǎng)絡(luò)等特性，因此不具備很好的通用性.NOPaxos和Speculative Paxos的不同之處在于，OUM保證了消息的有序性，而MOM只是最大程度上保證消息的有序性.NOPaxos只需要簡單的多數(shù)派(即過半)，但是Speculative Paxos需要更大的多數(shù)派，也就意味著性能方面延時會比NOPaxos高.比較遺憾的是OUM需要更多網(wǎng)絡(luò)技術(shù)方面的支持，需要網(wǎng)絡(luò)設(shè)備提供可編程的數(shù)據(jù)層.MOM可以只需要設(shè)備支持OpenFlow協(xié)議即可.

除了修改交換機之外，István等人[27]認為共識算法在解決共識問題過程中所帶來的協(xié)同通信的開銷往往是讓人無法接受的，因此在實際使用過程中不得不做一些取舍，比如容忍部分數(shù)據(jù)丟失和數(shù)據(jù)不一致，以降低協(xié)同過程帶來的開銷.因此，為了更高效地解決共識問題，他們把共識算法做到硬件中，用硬件的獨特優(yōu)勢來實現(xiàn)高性能共識算法.為了驗證這一想法的可行性，他們在FPGA中實現(xiàn)了ZAB算法，比原有ZooKeeper系統(tǒng)擁有更好更穩(wěn)定的性能.同時因為不跟特定交換機設(shè)備相關(guān)，他們設(shè)計的硬件中間件可以適應(yīng)不同的網(wǎng)絡(luò)，具有良好的可移植性.

5 類Paxos共識算法的應(yīng)用現(xiàn)狀

在應(yīng)用方面，Paxos算法用以解決數(shù)據(jù)一致性與可靠性被工業(yè)界普遍接受與認可.使用Paxos算法的鍵值存儲、數(shù)據(jù)庫、分布式文件系統(tǒng)以及分布式消息隊列等系統(tǒng)越來越多.工程實踐角度，Chandra等人[11]就如何使用Paxos 算法實現(xiàn)分布式共識系統(tǒng)給出了詳細的工程細節(jié).

1) 鍵值存儲系統(tǒng)方面.開源的ZooKeeper，etcd在業(yè)界已經(jīng)被廣泛使用多年.ZooKeeper作為一種分布式協(xié)同服務(wù)解決了很多分布式情況下如分布式鎖等問題，成為了分布式系統(tǒng)架構(gòu)中不可缺少的一個組成部分.

2) 數(shù)據(jù)庫系統(tǒng)方面.MySQL提出了基于Mencius算法的狀態(tài)機復制MGR(MySQL group replication)技術(shù)代替了原有系統(tǒng)的主備架構(gòu).MGR支持多節(jié)點寫入的同時保證數(shù)據(jù)一致性以及高可用性，還避免了主備系統(tǒng)的腦裂問題.架構(gòu)上，數(shù)據(jù)庫的并發(fā)控制和共識算法屬于不同的層次.分層的方法帶來的問題是引入2次協(xié)同操作：1)用于并發(fā)控制中確保事務(wù)的一致性;2)用于數(shù)據(jù)存儲副本之間達成共識一致.由于數(shù)據(jù)庫的并發(fā)控制協(xié)議與共識算法存在著相似性，MDCC[28]，TAPIR[29]，Janus[30]等協(xié)議嘗試將分布式共識算法和并發(fā)控制協(xié)議融合到一起實現(xiàn)分布式數(shù)據(jù)庫的容錯.這樣的方式解決了數(shù)據(jù)庫事務(wù)和數(shù)據(jù)副本的一致性問題，將協(xié)同次數(shù)減少為1次.

3) 文件系統(tǒng)方面.Ceph分布式文件系統(tǒng)采用Paxos算法用以維護集群元信息并負責元信息的更新.元信息包括記錄數(shù)據(jù)分布的OSDMap、記錄集群監(jiān)控狀態(tài)的MonitorMap以及集群中其他的必要信息.由于系統(tǒng)可擴展性以及集群配置管理等問題，GlusterFS也決定在下一版本中采用etcd系統(tǒng)存儲集群配置信息.

4) 分布式消息隊列方面.Kafka作為分布式消息系統(tǒng)對比傳統(tǒng)的消息系統(tǒng)性能和可靠性有大幅提升.Kafka領(lǐng)導者選舉過程使用了ZooKeeper，同時底層的數(shù)據(jù)復制也用到共識相關(guān)技術(shù).騰訊云基于Raft算法實現(xiàn)了一個高可靠、強一致性的分布式消息隊列CMQ，主要服務(wù)于訂單、交易類業(yè)務(wù)場景，在特定情況下保證消息的嚴格有序.

6 討 論

在未來的類Paxos算法的研究和應(yīng)用中，主要可以從3個方面著手.

1) 對RDMA網(wǎng)絡(luò)的使用.RDMA網(wǎng)絡(luò)擁有著高吞吐、低延時的特性，利用這一特性，可以有效提高算法在實用系統(tǒng)中的性能.盡管算法在協(xié)同通信的輪次上沒有變化，但是因為網(wǎng)絡(luò)本身的特性，通信開銷變小了.如何利用好RDMA特性，需要針對具體算法進行設(shè)計.

2) 對可編程網(wǎng)絡(luò)的使用.對于類Paxos共識算法的實現(xiàn)來說，網(wǎng)絡(luò)環(huán)境的重要性毋庸置疑.網(wǎng)絡(luò)中，數(shù)據(jù)包的可控制程度也決定了算法設(shè)計以及實現(xiàn)過程所需要考慮情況的多少.可編程網(wǎng)絡(luò)使得網(wǎng)絡(luò)行為變得可控，給類Paxos共識算法的設(shè)計實現(xiàn)提供了便利條件.同時也給系統(tǒng)設(shè)計人員提出2個要求：①對于網(wǎng)絡(luò)環(huán)境和設(shè)備特性的了解;②需要根據(jù)可編程網(wǎng)絡(luò)自身的特性，對類Paxos共識算法進行重新設(shè)計.

3) 特定硬件，因為多機共識問題的重要性，設(shè)計特定硬件以高效解決共識問題也是一個值得關(guān)注的方向.

同時，豐富多樣的應(yīng)用場景也對類Paxos算法提出了新的要求.因為應(yīng)用場景的不同，對于可靠性、可用性的要求有高有低.在設(shè)計算法過程中，針對具體應(yīng)用場景進行優(yōu)化，也將使得類Paxos共識算法更好地發(fā)揮作用.關(guān)于強領(lǐng)導者和弱領(lǐng)導者算法的選取則依賴于在不同場景下的取舍.比如在一個數(shù)據(jù)中心內(nèi)部，或者說在同一機柜上的幾臺機器之間做副本狀態(tài)機.在這種情況下網(wǎng)絡(luò)環(huán)境相對穩(wěn)定，也不存在請求跨域的問題.如果單個領(lǐng)導者不會成為應(yīng)用的瓶頸，可以考慮采用強領(lǐng)導者共識算法.當然在跨數(shù)據(jù)中心之間做副本狀態(tài)機，弱領(lǐng)導者共識算法就顯得比較有優(yōu)勢.因此，類Paxos算法設(shè)計和實現(xiàn)也漸漸地與應(yīng)用場景結(jié)合更加緊密.

綜上，類Paxos共識算法有兩大熱點方向：1)類Paxos算法在不同網(wǎng)絡(luò)環(huán)境、網(wǎng)絡(luò)設(shè)備以及不同硬件條件下的實現(xiàn);2)針對具體應(yīng)用場景如數(shù)據(jù)庫系統(tǒng)等，設(shè)計新的類Paxos算法解決分布式可靠性和一致性等問題.

7 結(jié) 論

分布式共識算法是構(gòu)建分布式服務(wù)中一個必不可少的組成部分.本文從分布式類Paxos共識算法歷史發(fā)展的角度，闡述了在解決共識問題上，類Paxos共識算法在演進過程中的變化.同時，也詳細介紹了在演進過程中4種關(guān)鍵的算法，并且對算法演進過程、分類以及適用場景、優(yōu)缺點等進行了歸納和分析.在本文的后半部分，還簡要介紹了類Paxos共識算法在研究與應(yīng)用方面的現(xiàn)狀.隨著集群規(guī)模以及業(yè)務(wù)需求的發(fā)展，相信在不久的將來使用分布式共識算法的應(yīng)用越來越廣泛，也期待隨著網(wǎng)絡(luò)技術(shù)、硬件技術(shù)的發(fā)展，類Paxos共識算法的設(shè)計、實現(xiàn)以及應(yīng)用會有越來越多新的突破.