類Paxos共識(shí)算法研究進(jìn)展

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

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

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

副本復(fù)制技術(shù)是提供可靠性的基礎(chǔ)技術(shù)之一，為數(shù)據(jù)或者服務(wù)提供冗余.副本狀態(tài)機(jī)能夠在有效隱藏服務(wù)器宕機(jī)問(wèn)題的情況下，保證整個(gè)系統(tǒng)的強(qiáng)一致性,是分布式容錯(cuò)系統(tǒng)的一個(gè)基本結(jié)構(gòu).圖1是副本狀態(tài)機(jī)的基本原理，圖1中展示了上下2個(gè)副本狀態(tài)機(jī)的狀態(tài)變化過(guò)程，實(shí)際中可能用到更多的副本狀態(tài)機(jī)來(lái)保證更高的可靠性.2個(gè)狀態(tài)機(jī)的初始狀態(tài)都為S0，此后每1個(gè)狀態(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ī)工作原理

越來(lái)越多的系統(tǒng)使用副本狀態(tài)機(jī)作為核心協(xié)同服務(wù)，例如Google公司的Spanner[1]、Oracle公司的MySQL[2]等數(shù)據(jù)庫(kù)系統(tǒng)，以及Ceph[3]等分布式文件系統(tǒng).為了能夠發(fā)揮副本狀態(tài)機(jī)技術(shù)的優(yōu)勢(shì)，也陸續(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ù)器上)共同決策一系列操作的順序.于是核心問(wèn)題就是在多機(jī)情況下，如何讓各個(gè)副本進(jìn)程就某個(gè)操作達(dá)成一致，這就涉及到分布式共識(shí)算法(distributed consensus algorithm).Paxos就是一個(gè)著名的分布式共識(shí)算法.從Lamport[9-10]提出Paxos算法開始，此后基于Paxos變形的分布式共識(shí)算法越來(lái)越多.近些年來(lái)，網(wǎng)絡(luò)方面RDMA、軟件定義網(wǎng)絡(luò)(sofware defined networking， SDN)等技術(shù)發(fā)展迅猛，也有部分研究人員結(jié)合網(wǎng)絡(luò)技術(shù)的發(fā)展和變化以及具體硬件重新設(shè)計(jì)共識(shí)算法提升分布式系統(tǒng)的性能.

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

1 分布式共識(shí)

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

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

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

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

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

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

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

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

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

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

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

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

Fig. 2 The main procedure of Paxos圖2 Paxos算法主要過(guò)程

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

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

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

階段2. 接受提議階段.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.1.1 Multi-Paxos算法

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

3.1.1.2 VR算法

領(lǐng)導(dǎo)者進(jìn)程接收客戶端請(qǐng)求，將請(qǐng)求添加到本地日志末端，然后向其他追隨者進(jìn)程發(fā)送這個(gè)請(qǐng)求，編號(hào)為n.追隨者進(jìn)程在接收這一請(qǐng)求之后會(huì)作一個(gè)檢查，查看本地的日志中是否包含所有編號(hào)小于n的日志項(xiàng)，若不包含，則等到全部包含為止.滿足上述條件以后，追隨者進(jìn)程會(huì)給領(lǐng)導(dǎo)者進(jìn)程一個(gè)回復(fù).領(lǐng)導(dǎo)者進(jìn)程在收到F個(gè)追隨者進(jìn)程的回復(fù)以后，在本地提交并且執(zhí)行這個(gè)請(qǐng)求，將執(zhí)行結(jié)果回復(fù)給客戶端.其他追隨者進(jìn)程想要獲知這個(gè)請(qǐng)求是否需要提交并且執(zhí)行則需要客戶端發(fā)起下一個(gè)請(qǐng)求，領(lǐng)導(dǎo)者在下一個(gè)請(qǐng)求中攜帶提交通知一起發(fā)送給追隨者進(jìn)程.若沒(méi)有，則領(lǐng)導(dǎo)者一段時(shí)間以后自己廣播Commit消息，通知追隨者進(jìn)程提交相對(duì)應(yīng)的請(qǐng)求.這個(gè)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)程接收到客戶端請(qǐng)求后，本地形成1個(gè)事務(wù)，并給事務(wù)分配1個(gè)遞增的事務(wù)編號(hào) (1個(gè)64 b的整數(shù)，前32 b表示事務(wù)所在的任期，后32 b表示任期內(nèi)的事務(wù)編號(hào)).然后，領(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個(gè)以上副本進(jìn)程的確認(rèn)消息后，向所有的副本進(jìn)程廣播Commit消息.副本進(jìn)程收到Commit消息時(shí)，提交該事務(wù).

3.1.1.4 Raft算法

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

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

2) 如果當(dāng)前日志項(xiàng)屬于之前領(lǐng)導(dǎo)者的任期，那么這個(gè)日志項(xiàng)是否被提交的依據(jù)是它的下一條日志項(xiàng)是否已經(jīng)提交，也就是下一個(gè)日志項(xiàng)的提交會(huì)順便將之前所有的日志項(xià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)者需要知道追隨者跟它保持一致的日志位置，然后從這個(gè)位置后的第1個(gè)位置開始執(zhí)行復(fù)制操作.

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

3.1.1.5 小結(jié)

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

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

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

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

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

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

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

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

3.1.2.1 Multi-Paxos算法

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

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

3.1.2.2 VR算法

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

3.1.2.3 ZAB算法

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

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

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

為了提高數(shù)據(jù)同步效率，領(lǐng)導(dǎo)者為每個(gè)支持它的副本進(jìn)程維護(hù)一個(gè)FIFO隊(duì)列，將新的事務(wù)日志中未提交的事務(wù)放入隊(duì)列，同時(shí)向隊(duì)列中加入Commit消息.而通信模塊則負(fù)責(zé)將各個(gè)隊(duì)列里的消息順序發(fā)送給對(duì)應(yīng)的副本進(jìn)程，同步過(guò)程即是恢復(fù)過(guò)程.至此完成視圖切換，然后開始接收客戶端的請(qǐng)求，提供服務(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)者、候選者和追隨者，分別對(duì)應(yīng)了副本進(jìn)程在不同時(shí)期的狀態(tài).同時(shí)，Raft算法用一種心跳機(jī)制(heartbeat)來(lái)觸發(fā)選舉過(guò)程，如圖9所示.當(dāng)系統(tǒng)啟動(dòng)時(shí)，所有的副本進(jìn)程都會(huì)被初始化為追隨者，領(lǐng)導(dǎo)者會(huì)向所有追隨者發(fā)送心跳信息來(lái)確保領(lǐng)導(dǎo)者和其他追隨者連接正常.如果有追隨者在1個(gè)周期內(nèi)沒(méi)有收到心跳信息，它就會(huì)認(rèn)為當(dāng)前系統(tǒng)中沒(méi)有領(lǐng)導(dǎo)者，然后把自己的狀態(tài)轉(zhuǎn)換成候選者狀態(tài)，并增加當(dāng)前任期編號(hào)，發(fā)起1輪投票.如果1個(gè)候選者在1個(gè)任期內(nèi)收獲了半數(shù)以上的副本進(jìn)程給它投票，那它就會(huì)將自己的狀態(tài)轉(zhuǎn)化為領(lǐng)導(dǎo)者.投票請(qǐng)求中的內(nèi)容包含3個(gè)重要信息：候選者新的任期、候選者本地最新日志項(xiàng)的任期以及日志編號(hào).判斷是否投票的條件，首先投票請(qǐng)求中的新任期比副本進(jìn)程本地任期要大，這一條件不滿足則不投票；其次，對(duì)比投票請(qǐng)求中的日志任期和副本進(jìn)程本地最后一個(gè)日志項(xiàng)的任期，投票請(qǐng)求的日志任期較小，則副本進(jìn)程不投票，相同則比較日志項(xiàng)編號(hào)，投票請(qǐng)求中的日志項(xiàng)編號(hào)較小則不投票.總結(jié)一下就是，投票請(qǐng)求內(nèi)容比副本進(jìn)程本地狀態(tài)更超前，則副本進(jìn)程認(rèn)可這個(gè)投票，否則就不投票.

3.1.2.5 小結(jié)

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

總體上，選取新的領(lǐng)導(dǎo)者是因?yàn)榕f的領(lǐng)導(dǎo)者失效，出于安全性考慮，同一任期最好只有1個(gè)領(lǐng)導(dǎo)者，因?yàn)槎鄠€(gè)領(lǐng)導(dǎo)者可能造成日志序列不一致.因此，4種算法在選舉階段的目標(biāo)也是相對(duì)明確的，即在1個(gè)任期內(nèi)選出1個(gè)領(lǐng)導(dǎo)者，選舉操作本身成功與否都不能影響系統(tǒng)安全性.對(duì)于領(lǐng)導(dǎo)者選舉部分來(lái)說(shuō)，有4個(gè)關(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)程之間會(huì)維護(hù)獨(dú)立的雙向心跳消息，所謂雙向指的是領(lǐng)導(dǎo)者到追隨者、追隨者到領(lǐng)導(dǎo)者.ZAB算法選舉觸發(fā)是2個(gè)方面的，可以來(lái)自于領(lǐng)導(dǎo)者自身或者追隨者進(jìn)程.VR算法和Raft算法則主要是領(lǐng)導(dǎo)者向追隨者發(fā)送心跳消息，追隨者在一段時(shí)間沒(méi)有收到心跳消息以后會(huì)觸發(fā)選舉操作.心跳消息也不一定是單獨(dú)設(shè)置的.在VR算法中，心跳消息可以是普通請(qǐng)求消息或者提交通知.對(duì)于Raft算法來(lái)說(shuō)，心跳消息是正常的日志項(xiàng)或者空的日志項(xiàng).

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

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

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

3.1.3 成員更新

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

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

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

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

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

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

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

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

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

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

3.2.1 Mencius算法

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

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

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

3.2.2 EPaxos算法

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

Fig. 12 The main procedure of EPaxos圖12 EPaxos算法主要過(guò)程

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

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

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

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

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

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

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

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

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

3.3 2類算法對(duì)比

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

Table 3 Contradistinction of Two Kinds of Distributed Consensus Algorithms表3 2類分布式共識(shí)算法的對(duì)比

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

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

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

在Multi-Paxos算法中，客戶端將請(qǐng)求先提交給領(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ā)送給接受者，在沒(méi)有沖突的情況下通信1輪直接提交，在有沖突的情況下，交由領(lǐng)導(dǎo)者協(xié)調(diào)處理，領(lǐng)導(dǎo)者協(xié)調(diào)完畢后在下1輪通信中完成提交.Fast Paxos算法因?yàn)椴蝗菀妆焕斫庖约皩?shí)現(xiàn)過(guò)程比較復(fù)雜，很少被使用.這些改進(jìn)實(shí)質(zhì)上可以看作是對(duì)于Paxos算法思想的一種延伸.

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

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

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

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

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

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

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

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

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

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

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

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

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

6 討 論

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

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

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

3) 特定硬件，因?yàn)槎鄼C(jī)共識(shí)問(wèn)題的重要性，設(shè)計(jì)特定硬件以高效解決共識(shí)問(wèn)題也是一個(gè)值得關(guān)注的方向.

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

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

7 結(jié) 論

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