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

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

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

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

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

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

維護(hù)副本之間的強(qiáng)一致性就是讓一組副本進(jìn)程(通常分布在不同服務(wù)器上)共同決策一系列操作的順序.于是核心問題就是在多機(jī)情況下，如何讓各個副本進(jìn)程就某個操作達(dá)成一致，這就涉及到分布式共識算法(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算法演進(jìn)歷程的角度出發(fā)，介紹在Paxos演進(jìn)過程中4個關(guān)鍵的變種算法，并對這些算法作一些對比分析以及適用場景說明.同時也簡要介紹了最近幾年類Paxos算法在實(shí)現(xiàn)和使用上的一些新的優(yōu)化思路.希望籍此能夠幫助推進(jìn)相關(guān)算法的進(jìn)一步改進(jìn)和使用，并為分布式容錯場景下共識算法的選擇提供參考.

1 分布式共識

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

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

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

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

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

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

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

2 Paxos算法

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

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

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

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

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

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

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

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

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

階段1. 準(zhǔn)備提議階段.

階段1.1. 提議者準(zhǔn)備提案編號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消息，即接受這個提案.

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

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

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

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

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

3.1 強(qiáng)領(lǐng)導(dǎo)者共識算法

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

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

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

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

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

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

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

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

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

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

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

3.1.1 正常情況下的復(fù)制

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

3.1.1.1 Multi-Paxos算法

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

3.1.1.2 VR算法

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

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

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

3.1.1.3 ZAB算法

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

3.1.1.4 Raft算法

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

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

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

Fig. 6 Normal case in Raft圖6 Raft算法正常復(fù)制

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

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

3.1.1.5 小結(jié)

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

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

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

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

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

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

3.1.2 領(lǐng)導(dǎo)者選取

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

3.1.2.1 Multi-Paxos算法

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

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

3.1.2.2 VR算法

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

3.1.2.3 ZAB算法

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

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

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

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

3.1.2.4 Raft算法

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

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

3.1.2.5 小結(jié)

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

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

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

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

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

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

3.1.3 成員更新

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

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

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

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

3.1.4 強(qiáng)領(lǐng)導(dǎo)者共識算法總結(jié)

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

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

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

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

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

3.2.1 Mencius算法

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

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

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

3.2.2 EPaxos算法

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

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

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

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

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

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

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

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

2) 當(dāng)副本進(jìn)程失效時，如何恢復(fù).

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

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

3.3 2類算法對比

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

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

4 類Paxos共識算法進(jìn)一步改進(jìn)

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

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

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

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

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

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

另一方面，分布式共識算法的實(shí)現(xiàn)跟網(wǎng)絡(luò)狀態(tài)和性能密不可分，對網(wǎng)絡(luò)性能和穩(wěn)定性有著比較高的要求.研究人員發(fā)現(xiàn)在網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中，有很多時間花費(fèi)在操作系統(tǒng)網(wǎng)絡(luò)協(xié)議棧上，因此部分研究人員漸漸開始關(guān)注類Paxos共識算法在網(wǎng)絡(luò)設(shè)備中實(shí)現(xiàn)的研究.Speculative Paxos[23]使用可預(yù)測的網(wǎng)絡(luò)行為來改善Paxos算法的性能.它有效將IP多播、固定長度的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及作為消息序列器的單個頂端交換機(jī)等技術(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ò)交換機(jī)中，利用網(wǎng)絡(luò)中的消息順序?qū)崿F(xiàn)整個Paxos算法全部邏輯的詳細(xì)設(shè)計.同時，也表明了在不更改OpenFlow[25]API接口的情況下，僅僅依賴網(wǎng)絡(luò)交換機(jī)設(shè)備特性實(shí)現(xiàn)樂觀控制協(xié)議的可行性.它與Speculative Paxos最大的不同之處在于交換機(jī)設(shè)備本身會作為共識算法中的角色，共識算法邏輯運(yùn)行在交換機(jī)中.Speculative Paxos只是利用網(wǎng)絡(luò)設(shè)備特性去優(yōu)化Paxos算法，共識算法相關(guān)邏輯還需要運(yù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ò)丟包情況即可.解決了亂序問題以后，達(dá)成共識就變得相對簡單，開銷也變得更小.當(dāng)然和Speculative Paxos一樣，NOPaxos也依賴于數(shù)據(jù)中心固定網(wǎng)絡(luò)拓?fù)浣Y(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é)議即可.

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

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

在應(yīng)用方面，Paxos算法用以解決數(shù)據(jù)一致性與可靠性被工業(yè)界普遍接受與認(rèn)可.使用Paxos算法的鍵值存儲、數(shù)據(jù)庫、分布式文件系統(tǒng)以及分布式消息隊列等系統(tǒng)越來越多.工程實(shí)踐角度，Chandra等人[11]就如何使用Paxos 算法實(shí)現(xiàn)分布式共識系統(tǒng)給出了詳細(xì)的工程細(xì)節(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)機(jī)復(fù)制MGR(MySQL group replication)技術(shù)代替了原有系統(tǒng)的主備架構(gòu).MGR支持多節(jié)點(diǎn)寫入的同時保證數(shù)據(jù)一致性以及高可用性，還避免了主備系統(tǒng)的腦裂問題.架構(gòu)上，數(shù)據(jù)庫的并發(fā)控制和共識算法屬于不同的層次.分層的方法帶來的問題是引入2次協(xié)同操作：1)用于并發(fā)控制中確保事務(wù)的一致性;2)用于數(shù)據(jù)存儲副本之間達(dá)成共識一致.由于數(shù)據(jù)庫的并發(fā)控制協(xié)議與共識算法存在著相似性，MDCC[28]，TAPIR[29]，Janus[30]等協(xié)議嘗試將分布式共識算法和并發(fā)控制協(xié)議融合到一起實(shí)現(xiàn)分布式數(shù)據(jù)庫的容錯.這樣的方式解決了數(shù)據(jù)庫事務(wù)和數(shù)據(jù)副本的一致性問題，將協(xié)同次數(shù)減少為1次.

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

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

6 討 論

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

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

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

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

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

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

7 結(jié) 論

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