摘要：只需超過半數的節點達成一致。總結是分布式一致性問題中的重要共識算法。

在一個分布式系統中，由于節點故障、網絡延遲等各種原因，根據CAP理論，我們只能保證一致性（Consistency）、可用性（Availability）、分區容錯性（Partition Tolerance）中的兩個。

對于一致性要求高的系統，比如銀行取款機，就會選擇犧牲可用性，故障時拒絕服務。MongoDB、Redis、MapReduce使用這種方案。

對于靜態網站、實時性較弱的查詢類數據庫，會犧牲一致性，允許一段時間內不一致。簡單分布式協議Gossip，數據庫CouchDB、Cassandra使用這種方案。

圖1

如圖1所示，一致性問題，可以根據是否存在惡意節點分類兩類。無惡意節點，是指節點會丟失、重發、不響應消息，但不會篡改消息。而惡意節點可能會篡改消息。有惡意節點的問題稱為拜占庭將軍問題，不在今天的討論范圍。Paxos很好地解決了無惡意節點的分布式一致性問題。

1990年，Leslie Lamport在論文《The Part-Time Parliament》中提出Paxos算法。由于論文使用故事的方式，沒有使用數學證明，起初并沒有得到重視。直到1998年該論文才被正式接受。后來2001年Lamport又重新組織了論文，發表了《Paxos Made Simple》。作為分布式系統領域的早期貢獻者，Lamport獲得了2013年圖靈獎。

Paxos算法廣泛應用在分布式系統中，Google Chubby的作者Mike Burrows說：“這個世界上只有一種一致性算法，那就是 Paxos（There is only one consensus protocol, and that"s Paxos）”。

后來的Raft算法、是對Paxos的簡化和改進，變得更加容易理解和實現。

Paxos本來是虛構故事中的一個小島，議會通過表決來達成共識。但是議員可能離開，信使可能走丟，或者重復傳遞消息。對應到分布式系統的節點故障和網絡故障。

圖2

如圖2所示，假設議員要提議中午吃什么。如果有一個或者多個人同時提議，但一次只能通過一個提議，這就是Basic Paxos，是Paxos中最基礎的協議。

顯然Basic Paxos是不夠高效的，如果將Basic Paxos并行起來，同時提出多個提議，比如中午吃什么、吃完去哪里嗨皮、誰請客等提議，議員也可以同時通過多個提議。這就是Multi-Paxos協議。

Paxos算法存在3種角色：Proposer、Acceptor、Learner，在實現中一個節點可以擔任多個角色。

圖3

Proposer負責提出提案

Acceptor負責對提案進行投票

Learner獲取投票結果，并幫忙傳播

Learner不參與投票過程，為了簡化描述，我們直接忽略掉這個角色。

運行過程分為兩個階段，Prepare階段和Accept階段。

Proposer需要發出兩次請求，Prepare請求和Accept請求。Acceptor根據其收集的信息，接受或者拒絕提案。

Prepare階段

Proposer選擇一個提案編號n，發送Prepare(n)請求給超過半數（或更多）的Acceptor。

Acceptor收到消息后，如果n比它之前見過的編號大，就回復這個消息，而且以后不會接受小于n的提案。另外，如果之前已經接受了小于n的提案，回復那個提案編號和內容給Proposer。

Accept階段

當Proposer收到超過半數的回復時，就可以發送Accept(n, value)請求了。 n就是自己的提案編號，value是Acceptor回復的最大提案編號對應的value，如果Acceptor沒有回復任何提案，value就是Proposer自己的提案內容。

Acceptor收到消息后，如果n大于等于之前見過的最大編號，就記錄這個提案編號和內容，回復請求表示接受。

當Proposer收到超過半數的回復時，說明自己的提案已經被接受。否則回到第一步重新發起提案。

完整算法如圖4所示：

圖4

Acceptor需要持久化存儲minProposal、acceptedProposal、acceptedValue這3個值。

Basic Paxos共識過程一共有三種可能的情況。下面分別進行介紹。

如圖5所示。X、Y代表客戶端，S1到S5是服務端，既代表Proposer又代表Acceptor。為了防止重復，Proposer提出的編號由兩部分組成：

序列號.Server ID

例如S1提出的提案編號，就是1.1、2.1、3.1……

圖5 以上圖片來自Paxos lecture (Raft user study)第13頁

這個過程表示，S1收到客戶端的提案X，于是S1作為Proposer，給S1-S3發送Prepare(3.1)請求，由于Acceptor S1-S3沒有接受過任何提案，所以接受該提案。然后Proposer S1-S3發送Accept(3.1, X)請求，提案X成功被接受。

在提案X被接受后，S5收到客戶端的提案Y，S5給S3-S5發送Prepare(4.5)請求。對S3來說，4.5比3.1大，且已經接受了X，它會回復這個提案 (3.1, X)。S5收到S3-S5的回復后，使用X替換自己的Y，于是發送Accept(4.5, X)請求。S3-S5接受提案。最終所有Acceptor達成一致，都擁有相同的值X。

這種情況的結果是：新Proposer會使用已接受的提案

圖6 以上圖片來自Paxos lecture (Raft user study)第14頁

如圖6所示，S3接受了提案(3.1, X)，但S1-S2還沒有收到請求。此時S3-S5收到Prepare(4.5)，S3會回復已經接受的提案(3.1, X)，S5將提案值Y替換成X，發送Accept(4.5, X)給S3-S5，對S3來說，編號4.5大于3.1，所以會接受這個提案。

然后S1-S2接受Accept(3.1, X)，最終所有Acceptor達成一致。

這種情況的結果是：新Proposer會使用已提交的值，兩個提案都能成功

圖7 以上圖片來自Paxos lecture (Raft user study)第15頁

如圖7所示，S1接受了提案(3.1, X)，S3先收到Prepare(4.5)，后收到Accept(3.1, X)，由于3.1小于4.5，會直接拒絕這個提案。所以提案X無法收到超過半數的回復，這個提案就被阻止了。提案Y可以順利通過。

這種情況的結果是：新Proposer使用自己的提案，舊提案被阻止

活鎖發生的幾率很小，但是會嚴重影響性能。就是兩個或者多個Proposer在Prepare階段發生互相搶占的情形。

圖8 以上圖片來自Paxos lecture (Raft user study)第16頁

解決方案是Proposer失敗之后給一個隨機的等待時間，這樣就減少同時請求的可能。

上一小節提到的活鎖，也可以使用Multi-Paxos來解決。它會從Proposer中選出一個Leader，只由Leader提交Proposal，還可以省去Prepare階段，減少了性能損失。當然，直接把Basic Paxos的多個Proposer的機制搬過來也是可以的，只是性能不夠高。

將Basic Paxos并行之后，就可以同時處理多個提案了，因此要能存儲不同的提案，也要保證提案的順序。

Acceptor的結構如圖9所示，每個方塊代表一個Entry，用于存儲提案值。用遞增的Index來區分Entry。

圖9

Multi-Paxos需要解決幾個問題，我們逐個來看。

一個最簡單的選舉方法，就是Server ID最大的當Leader。

每個Server間隔T時間向其他Server發送心跳包，如果一個Server在2T時間內沒有收到來自更高ID的心跳，那么它就成為Leader。

其他Proposer，必須拒絕客戶端的請求，或將請求轉發給Leader。

當然，還可以使用其他更復雜的選舉方法，這里不再詳述。

Prepare的作用是阻止舊的提案，以及檢查是否有已接受的提案值。

當只有一個Leader發送提案的時候，Prepare是不會產生沖突的，可以省略Prepare階段，這樣就可以減少一半RPC請求。

Prepare請求的邏輯修改為：

Acceptor記錄一個全局的最大提案編號

回復最大提案編號，如果當前entry以及之后的所有entry都沒有接受任何提案，回復noMoreAccepted

當Leader收到超過半數的noMoreAccepted回復，之后就不需要Prepare階段了，只需要發送Accept請求。直到Accept被拒絕，就重新需要Prepare階段。

目前為止信息是不完整的。

Basic Paxos只需超過半數的節點達成一致。但是在Multi-Paxos中，這種方式可能會使一些節點無法得到完整的entry信息。我們希望每個節點都擁有全部的信息。

只有Proposer知道一個提案是否被接受了（根據收到的回復），而Acceptor無法得知此信息。

第1個問題的解決方案很簡單，就是Proposer給全部節點發送Accept請求。

第2個問題稍微復雜一些。首先，我們可以增加一個Success RPC，讓Proposer顯式地告訴Acceptor，哪個提案已經被接受了，這個是完全可行的，只不過還可以優化一下，減少請求次數。

我們在Accept請求中，增加一個firstUnchosenIndex參數，表示Proposer的第一個未接受的Index，這個參數隱含的意思是，對該Proposer來說，小于Index的提案都已經被接受了。因此Acceptor可以利用這個信息，把小于Index的提案標記為已接受。另外要注意的是，只能標記該Proposer的提案，因為如果發生Leader切換，不同的Proposer擁有的信息可能不同，不區分Proposer直接標記的話可能會不一致。

圖10

如圖10所示，Proposer正在準備提交Index=2的Accept請求，0和1是已接受的提案，因此firstUnchosenIndex=2。當Acceptor收到請求后，比較Index，就可以將Dumplings提案標記為已接受。

由于之前提到的Leader切換的情況，仍然需要顯式請求才能獲得完整信息。在Acceptor回復Accept消息時，帶上自己的firstUnchosenIndex。如果比Proposer的小，那么就需要發送Success(index, value)，Acceptor將收到的index標記為已接受，再回復新的firstUnchosenIndex，如此往復直到兩者的index相等。

Paxos是分布式一致性問題中的重要共識算法。這篇文章分別介紹了最基礎的Basic Paxos，和能夠并行的Multi-Paxos。

在Basic Paxos中，介紹了3種基本角色Proposer、Acceptor、Learner，以及提案時可能發生的3種基本情況。在Multi-Paxos中，介紹了3個需要解決的問題：Leader選舉、Prepare省略、完整信息流。

在下一篇文章中，我們將實現一個簡單的demo來驗證這個算法，實現過程將會涉及到更多的細節。

分布式一致性與共識算法

Paxos 算法與 Raft 算法

Paxos

Paxos Made Simple

Paxos lecture (Raft user study)

YouTube | Paxos lecture (Raft user study)

本作品采用CC BY 4.0許可協議，轉載時請注明鏈接。