分佈式共識算法之 Paxos 詳解

分佈式一致性：共識算法

對於一個分佈式系統來說，保障集羣中所有節點的數據完全相同（即一致性）是很重要的，隨着多節點的引入，這影響的是整個分佈式系統對外服務的表象一致性。也就是說，一個分佈式系統想要做到完全的一致性，需要對外表現爲順序一致性，即各個節點上的操作順序都一致。

而在現實運行情況下，節點可能故障，可能增加，甚至可能被篡改，這就給分佈式一致性帶來了挑戰。在這種情況的干擾下，分佈式系統需要通過某些機制，來就一些事情達成一致的看法，也就是共識。

但要注意的是，共識算法並不能一次性解決所有分佈式的不一致問題。不同的算法能解決不同異常情況下的問題，所以共識算法也有分類：

拜占庭將軍問題：Lamport 曾經提出過在分佈式網絡下的一種節點作惡場景。描述的是拜占庭需要通過信使來在守衛邊境的多個將軍間傳遞消息，以達成一致的決定。如果此時出現叛徒，故意發送不同的消息來干擾共識的達成，應該如何讓忠誠的將軍們保持行動一致。映射到分佈式系統中就是多個節點就消息達成共識時如果出現錯誤節點傳遞了錯誤的消息該怎麼辦。

對於拜占庭容錯，往往都需要通過其他方面的激勵或懲罰，來讓 “誠實” 表達的節點利益最大化，本文描述的 Paxos 算法不解決拜占庭的問題，只解決崩潰容錯算法條件下達成分佈式共識的問題。

Paxos

背景

有一種說法，說所有共識算法都是 Paxos。這種說法的來源，一方面是由於 Paxos 的第一次提出非常的早，另一方面則是因爲，Paxos 解決的其實是在分佈式環境下，所有服務達成一次某個值的共識的過程，而這一過程，可以說每種共識算法都繞不開。

最早在 1990 年，Paxos 的作者 Leslie Lamport 就提交了關於 Paxos 的論文《The Part-Time Parliament》，但直到 2001 年 Lamport 第三次發表簡化版的相關論文，且 2006 年 Google 使用 Paxos 的理念實現了分佈式系統，該算法才被大衆所理解和追捧。

1990 年的論文中，Lamport 描述了一個名爲 Paxos 的希臘城邦（算法得名於此），這個城邦是按照民主的議會制度來進行選舉的，所有的居民進行提議和投票來選出決議。但是居民們不想花時間一直在選舉上，大家都不定時地來提議、瞭解提議、投票、看進展等等，而 Paxos 算法的目標就是通過少數服從多數的方式來達成最終的一致意見。但是審稿人覺得這個背景太複雜了，要求刪去，Lamport 不樂意就沒繼續投稿了（真大師）。八年後的 1998 年，Lamport 再次整理算法進行投稿，但是大家還是不太理解，因此也沒有引出多少水花。又過了三年，2001 年，Lamport 再次進行了簡化，發表了《Paxos Made Simple》，去掉了希臘城邦的背景，裏面甚至沒有一個公式。但依然直到 2006 年被 Google 實現後纔開始吸引大家的眼球，而作者 Lamport 也才獲得了 2013 年圖靈獎。

算法過程

少數服從多數

首先要認識到，這是一個分佈式系統下的共識算法，要解決的問題，簡化一點，就是一堆機器，每一臺都可能會收到客戶端的一條消息，那需要將自己收到的消息，告訴其他的機器，讓所有分佈式系統中的機器，達到最終的一致，這就是達到共識。

Paxos 採取了一個我們非常熟悉的達成共識的方法：少數服從多數。只要有超過一半的機器認可某一個消息，那麼最終就所有機器都接受這條消息並將它作爲本次的結論。而競選失敗的少數派消息，就會被拒絕，並由第一個從客戶端處接收到該消息的機器，向客戶端發送失敗結果，由客戶端進行重試，去嘗試在下一輪競選中勝出。

少數服從多數，說來簡單，如果是一羣人的話，大家碰個頭一起舉手表決就好了。但是放到一個分佈式系統中就變複雜了。機器之間怎麼傳遞提議，怎麼表決，怎麼統計多數，網絡傳輸需要時間，在表決過程中，其他機器收到了新的消息怎麼辦，都需要一整套機制來解決。

下面就來逐步講解 Paxos 的過程，但在講解過程之前，先說 Paxos 中最常見的兩種角色：

除了以上兩種角色，實際上 Paxos 還會提到 Learner，即學習者這個角色，該角色是在達成決議時，對結論的學習者，也即是從其他節點 “學習” 最終提案內容，比較簡單。需要注意，這些角色只是在不同時間下，邏輯上的劃分，實際上任何一臺機器都可以充當這三個角色之一。

一個簡單的提案

先描述最簡單的情況，假設現在有四臺機器，其中一臺收到了來自客戶端的寫操作請求，需要同步給其他機器。

此時這臺收到請求的機器，我們稱它爲 Proposer，因爲它將要開始將收到的請求，作爲一個提案，提給其他的機器。這裏爲了方便，我們假設這個請求是要將一個地址設置爲 “深圳”，那麼如下圖所示：

此時，其他的 Acceptor 都閒着呢，也沒其他人找，所以當它們收到 Proposer 的提案時，就直接投票了，說可以可以，我是空的，贊成提案（同意提議）：

到這裏，就還是一個簡單的同步的故事，但需要注意的是，這裏 Proposer 實際上是經歷了兩步的。

在這個簡單的提案過程中，Proposer 其實也經歷了兩個階段：

  1. Prepare 階段：Proposer 告訴所有其他機器，我這裏有一個提案（操作），想要你們投投票支持一下，想聽聽大家的意見。Acceptor 看自己是 NULL，也就是目前還沒有接受過其他的提案，就說我肯定支持。

  2. Accept 階段：Proposer 收到其他機器的回覆，說他們都是空的，也就是都可以支持接受 Proposer 的提案（操作），於是正式通知大家這個提案被集體通過了，可以生效了，操作就會被同步到所有機器正式生效。

兩個提案併發進行

現在考慮一個更復雜的場景，因爲我們處於一個分佈式的場景，每臺機器都可能會收到請求，那如果有兩臺機器同時收到了兩個客戶端的不同請求，該怎麼處理呢？大家聽誰的呢？最後的共識以誰的爲準呢？如下圖

在這種情況下，由於網絡傳輸的時間問題，兩個 Proposer 的提案到達各個機器，是會存在先後順序的。假設 Proposer 1 的提案先達到了 Acceptor 1 和 Acceptor  2，而 Proposer 2 的提案先達到了 Acceptor 3，其達到 Acceptor 1 和 Acceptor 2 時，由於機器已經投票給 Proposer 1 了，所以 Proposer 2 的提案遭到拒絕，Proposer 1 達到 Acceptor 3 的時候同樣被拒。

Acceptor 們迷了，Proposer 們也迷了，到底應該接受誰？此時，還是遵循自由民主的法則——少數服從多數。

Proposer 1 發現超過半數的 Acceptor 都接受了自己，所以放心大膽地發起要求，讓所有 Acceptor 都按照自己的值來操作。而 Proposer 2 發現只有不到半數的 Acceptor 支持自己，而有超過半數是支持 Proposer 1 的值的，因此只能拒絕 Client 2，並將自己也改爲 Proposer 1 的操作：

到此爲止，看起來沒有問題，但是，這是因爲恰好 Acceptor 的數量是單數，可以選出 “大多數”，但是因爲同時成爲 Proposer 的機器數量是不確定的，因此是無法保證 Acceptor 的數量一定是單數的，如下面這種情況就無法選出“大多數” 了：

這時，兩個 Proposer 有可能總是先搶到一個 Acceptor 的支持，然後在另一個 Acceptor 處折戟沉沙，算法就一直循環死鎖下去了。爲了解決這種情況，Paxos 給提案加了一個編號。

給提案加上編號

之前我們 Proposer 的提案都是隻有操作內容的，現在我們給他加一個編號，即：

假設 Proposer 1 接到 Clint 1 的消息稍微早一點，那麼它的編號就是 1，Proposer 2 的編號就是 2，那麼他們的提案實際就是：

此時，Paxos 加上一條規則：

所以，回到上面的困境

  1. 當 Proposer 1 想要向 Acceptor 2 尋求支持時，Acceptor 2 一看你的編號（1）比我已經支持的編號（2）要小，拒絕拒絕。此時 Proposer 1 由於沒有得到過半數的支持，會重新尋求支持。

  2. 而當 Proposer 2 想要向 Acceptor 1 尋求支持時，Acceptor 1 一看你的編號（2）比我已經支持的編號（1）要大，好的你是老大我聽你的。此時 Proposer 2 已經得到了超過半數的支持，可以進入正式生效的 Accept 階段了。

這裏需要補充一下，Proposer 1 這裏支持提案失敗，他是怎麼讓自己也接受 Proposer 2 的提案的呢？

所以這裏的後續會發生的事情是：

  1. Proposer 2 發現得到了過半數的支持，開始向所有 Acceptor 發送 Accept 請求。

  2. 所有 Acceptor 接收到 Accept 請求後，按照之前 Prepare 時收到的信息與承諾，去生效 Proposer 2 的提案內容（即 Set Addr = “北京” 的操作）。

  3. Proposer 1 之前已經收到了所有 Acceptor 的回覆，發現沒有得到過半數的支持，直接回復 Client 1 請求失敗，並變成一個 Acceptor（或者說 Learner），接受 Proposer 2 的 Accept 請求。

這裏再想多一點，考慮另一種場景：假設 Proposer 2 的 Accept 請求先達到了 Acceptor 2，然後 Proposer 1 向 Acceptor 2 發送的 Prepare 請求才到達 Acceptor 2，會發生什麼呢？

最直觀的處理是， Acceptor 2 直接拒絕，然後 Proposer 1 走上面的流程，但 Paxos 爲了效率，又增加了另一條規則：

此時會發生的事情就變成了：

  1. 此時 Acceptor 2 除了會拒絕它的請求，還會告訴 Proposer 1，說我已經通過並生效了另一個編號爲 2 的提案，內容是 Set Addr = “北京”。

  2. 然後 Proposer 1 查看回復時，發現已經有 Acceptor 生效提案了，於是就修改自己的提案，也改爲 Set Addr = “北京”，並告知 Client 1 你的請求失敗了。

  3. 接着 Proposer 1 開始充當 Proposer 2 的小幫手，幫他一起傳播 Proposer 2 的提案，加快達成共識的過程。

PS：這裏需要注意，編號是需要保證全局唯一的，而且是全局遞增的，否則在比較編號大小的時候就會出現問題，怎麼保證編號唯一且遞增有很多方法，比如都向一個統一的編號生成器請求新編號；又比如每個機器的編號用機器 ID 拼接一個數字，該數字按一個比總機器數更大的數字間隔遞增。

一些異常情況

上面的規則是不是就能保證整個算法解決所有問題了呢？恐怕不是，這裏再看看一些異常情況。

異常情況一：假設現在有三個 Proposer 同時收到客戶端的請求，那麼他們會生成全局唯一的不同編號，帶着各自接收到的請求提案，去尋求 Acceptor 的支持。但假設他們都分別爭取到了一個 Acceptor 的支持，此時由於 Prepare 階段只會接受編號更大的提案，所以正常情況下只有 Proposer 3 的提案會得到所有 Acceptor 的支持。但假設這時候 Proposer 3 機器掛了，無法進行下一步的 Accept 了，怎麼辦呢？那麼所有 Acceptor 就會陷入持續的等待，而其他的 Proposer 也會一直重試然後一直失敗。

爲了解決這個問題，Paxos 決定，允許 Proposer 在提案遭到過半數的拒絕時，更新自己的提案編號，用新的更大的提案編號，去發起新的 Prepare 請求。

那麼此時 Proposer 1 和 Proposer 2 就會更新自己的編號，從【1】與【2】，改爲比如【4】和【5】，重新嘗試提案。這時即使 Proposer 3 機器掛了，沒有完成 Accept，Acceptor 也會由於接收到了編號更大的提案，從而覆蓋掉 Proposer 3 的提案，進入新的投票支持階段。

異常情況二：雖然更新編號是解決了上面的問題，但卻又引入了活鎖的問題。由於可以更新編號，那麼有概率出現這種情況，即每個 Proposer 都在被拒絕時，增大自己的編號，然後每個 Proposer 在新的編號下又爭取到了小於半數的 Acceptor，都無法進入 Accept，又重新加大編號發起提案，一直這樣往復循環，就成了活鎖（和死鎖的區別是，他們的狀態一直在變化，嘗試解鎖，但還是被鎖住了）。

要解決活鎖的問題，有幾種常見的方法：

異常情況三：由於在提案時，Proposer 都是根據是否得到超過半數的 Acceptor 的支持，來作爲是否進入 Accept 階段的依據，那如果在算法進行中新增或下線了機器呢？如果此時一些 Proposer 知道機器數變了，一些 Proposer 不知道，那麼大家對半數的判斷就會不一致，導致算法出錯。

因此在實際運行中，機器節點數的變動，也需要作爲一條要達成共識的請求提案，通過 Paxos 算法本身，傳達到所有機器節點上。

爲了使 Paxos 運行得更穩定，不需要時刻擔心是否有節點數變化，可以固定一個週期，要求只有在達到固定週期時才允許變更節點數，比如只有在經過十次客戶端請求的提案與接受後，才處理一次機器節點數變化的提案。

那如果這個間隔設置地相對過久，導致現在想要修改節點數時，一直要苦等提案數，怎麼辦呢？畢竟有時候機器壞了是等不了的。那麼可以支持主動填充空的提案數，來讓節點變更的提案儘早生效。

Paxos 協議的兩階段

抽象和完善一下這個過程，就是：

  1. Prepare 準備階段：在該階段，Proposer 會嘗試告訴所有的其他機器，我現在有一個提案（操作），請告訴我你們是否支持（是否能接受）。其他機器會看看自己是否已經支持其他提案了（是否接受過其他操作請求），並回復給 Proposer（如果曾經接受過其他值，就告訴 Proposer 接受過什麼值 / 操作）。

  2. Acceptor 如果已經支持了編號 N 的提案，那麼不會再支持編號小於 N 的提案，但可以支持編號更大的提案；

  3. Acceptor 如果生效了編號爲 N 的提案，那麼不會再接受編號小於 N 的提案，且會在回覆時告知當前已生效的提案編號與內容。

  4. Accept 提交階段：在該階段，Proposer 根據上一階段接收到的回覆，來決定行爲：

  5. 如果上一階段超過半數的機器回覆說接受提案，那麼 Proposer 就正式通知所有機器去生效這個操作；

  6. 如果上一階段超過半數的機器回覆說他們已經先接受了其他編號更大的提案，那麼 Proposer 會更新一個更大的編號去重試（隨機延時）；

  7. 如果上一階段的機器回覆說他們已經生效了其他編號的提案，那麼 Proposer 就也只能接受這個其他人的提案，並告知所有機器直接接受這個新的提案；

  8. 如果上一階段都沒收到半數的機器回覆，那麼提案取消。

  9. PS：接受其他提案，以及提案取消的情況下，Proposer 就要直接告訴客戶端該次請求失敗了，等待客戶端重試即可。

這裏可以看到，超過半數以上的機器是個很重要的決定結果走向的條件。

至此，已經描述完了針對一次達成共識的過程，這被稱爲 Basic-Paxos。

那如果有多個值需要達成共識呢？

Multi-Paxos

如果有多個值要不斷地去針對一次次請求達成共識，使用 Basic-Paxos 也是可以的，無非就是一遍遍地執行算法取得共識並生效嘛，但在分佈式系統下，容易由於多次的通信協程造成響應過慢的問題，何況還有活鎖問題存在。因此 Lamport 給出的解法是：

  1. 先選擇一個 Leader 來擔當 Proposer 的角色，取消多 Proposer，只有一個 Leader 來提交提案，這樣就沒有了競爭（也沒有了活鎖）。同時，由於無需協商判斷，有了 Leader 後就可以取消 Prepare 階段，兩階段變一階段，提高效率。

  2. 對於每一次要確定的值 / 操作，使用唯一的一個標識來區分，保證其單調遞增即可。

對於選擇 Leader 的過程，簡單的做法很多，複雜的也只需要進行一次 Basic-Paxos 即可。選出 Leader 後，直到 Leader 掛掉或者到期，都可以保持由它來進行簡化的 Paxos 協議。

如果有多個機器節點都由於某些問題自認爲自己是 Leader，從而都提交了提案，也沒關係，可以令其退化成 Basic-Paxos，也可以在發現後再次選擇 Leader 即可。

其他共識算法

這裏也順便對比一下另外兩種常見的共識算法：ZAB 和 Raft。

ZAB

ZAB 全稱是 Zookeeper Atomic Broadcast，也就是 Zookeeper 的原子廣播，顧名思義是用於 Zookeeper 的。

ZAB 理解起來很簡單，在協議中有兩種角色：

既然有 Leader 節點，就必然有 Leader 的選舉過程，ZAB 的選舉，會先看各個節點所記錄的消息的時間戳（數據 ID），時間戳（數據 ID）越大，節點上的數據越新，就會優先被投票，如果數據 ID 比較不出來，就再看事先定義的節點的優先級（節點 ID）。當大家根據上述優先級投票，超過半數去支持一個節點時，該節點就成爲 Leader 節點了。

通過心跳算法可以共同檢查 Leader 節點的健康度，如果出現問題（比如機器下線、網絡分區、延遲過高等），就會考慮重新選舉。

可以看出，這種選舉方式相對 Paxos 是比較方便高效的，而且選出 Leader 節點後，就可以直接通過 Leader 節點接受消息進行廣播，而不需要進行兩階段提交。

其實 ZAB 就很像選出了 Leader 的 Multi-Paxos，兩者的差異主要在選 Leader 的流程上。

Raft

Raft 的應用比 Paxos 要多，有人認爲 Raft 是 Multi-Paxos 的改進，因爲 Raft 的作者也曾研究過 Paxos。既然 Paxos 是前輩，爲什麼應用的反而要少呢？這是因爲 Basic-Paxos 相對比較耗時，而 Multi-Paxos，作者並沒有給出具體的實現細節，這雖然給了開發者發揮的空間，但同樣可能會在實現的過程中由於開發者不同的實現方式帶來不同的問題，對於一個分佈式共識算法，誰也不知道潛在的問題會不會就影響到一致性了。而 Raft 算法給出了大量實現細節，簡單說就是，實現起來更不容易出錯。

Raft 協議同樣是需要選舉出 Leader 的，從這裏也能看到，共識算法大都會走向選舉出一個 Leader 的方向，來提升效率和穩定性。不同之處可能只在於選舉的方式，以及消息同步的方式。

Raft 的選舉，會在上一任 Leader 失去聯繫時發起，每個 Follower 便有機會成爲 Candidate，參與選舉。之所以說有機會，是因爲每個 Follower 都會先等一會，看是否有其他候選人過來拉票，避免人人都跑去湊熱鬧參與選舉浪費通信，這個等待的時間是在一個範圍內隨機的。

候選者參與選舉時會產生一個 term 概念，每個候選者會先投自己一票，然後帶着自己的 term 和自己的日誌信息（代表着數據的新舊）去拉票，其他的 Follower 先看候選者的 term 是否大於等於當前自己的 term，再看其日誌信息是否比自己新，如果都滿足就會投票。候選者收到超過半數的投票的話，就會成爲新的 Leader 了。

在這個過程中投票的 Follower 也會更新自己的 term 爲自己投票的候選者的 term，這樣就可以拒絕低於它的 term 的候選者了。而候選者如果被拒絕，也會回去更新自己的 term 以獲得支持。

選出 Leader 後，Leader 會把自己的日誌發給大家做同步，以保持大家和自己的日誌是一樣的，然後就進行後續的接收客戶端請求的環節。

可以看到 Raft 和 Multi-Paxos 也都要選舉出一個 Leader 節點來，不同之處在於，Raft 選舉的 Leader 節點上的日誌信息是最新最全的，這一方面可以不丟失日誌信息的順序，另一方面也可以讓選舉過程簡化（日誌信息的順序總是好比較的），而 Multi-Paxos 選 Leader 的過程偏隨機，就是看誰先拉攏更多節點的支持並快速落定，這一方面會使其日誌不連續，另一方面也會使得其實現變得複雜和相對不可控。

但實際上不連續也不完全是缺點，它也可以提高寫入的併發性能，所以雖然 Raft 實現相對更簡單，但微信的 PaxosStore 還是選擇了 Paxos，甚至它都沒有選擇 Multi-Paxos，而是 Basic-Paxos，就是爲了進一步避免單點依賴和切換 Leader 時的拒絕服務，來提高可用性。

可以看到，共識算法基本都需要解決兩個基本問題：

  1. 如何提出一個需要達成共識的提案（選舉 Leader、隨機投票...）

  2. 如何讓多個節點對提案達成共識（廣播、複製、投票...）

在這兩個問題的處理方案上選擇不同，就會導致性能、可用性等指標的不同，所以其實，兵器各有利弊，還是要看使用場景和使用的人。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/w8vm1c5b6G7OG1qaRMYPkw

猜你喜歡