[1901] 第03講：如何透徹理解 Paxo 算法？

本課時我們主要講解“如何透徹理解 Paxos 算法”？

Paxos 算法在分佈式領域具有非常重要的地位，開源分佈式鎖組件 Google Chubby 的作者 Mike Burrows 說過，這個世界上只有一種一致性算法，那就是 Paxos 算法，其他的算法都是殘次品。

Paxos 算法雖然重要，但是也因算法複雜而著名，不過 Paxos 算法是學習分佈式系統必需的一個知識點，這一課時我們就知難而上，一起來學習下 Paxos 算法。

Quorum 機制#

在學習 Paxos 算法之前，我們先來看分佈式系統中的 Quorum 選舉算法。在各種一致性算法中都可以看到Quorum 機制的身影，主要數學思想來源於抽屜原理，用一句話解釋那就是，在 N 個副本中，一次更新成功的如果有 W 個，那麼我在讀取數據時是要從大於 N－W 個副本中讀取，這樣就能至少讀到一個更新的數據了。

和 Quorum 機制對應的是 WARO，也就是Write All Read one，是一種簡單的副本控制協議，當 Client 請求向某副本寫數據時（更新數據），只有當所有的副本都更新成功之後，這次寫操作才算成功，否則視為失敗。

WARO 優先保證讀服務，因為所有的副本更新成功，才能視為更新成功，從而保證了

所有的副本一致，這樣的話，只需要讀任何一個副本上的數據即可。寫服務的可用性較低，因為只要有一個副本更新失敗，此次寫操作就視為失敗了。假設有 N 個副本，N－1 個都宕機了，剩下的那個副本仍能提供讀服務；但是只要有一個副本宕機了，寫服務就不會成功。

WARO 犧牲了更新服務的可用性，最大程度地增強了讀服務的可用性，而 Quorum 就是在更新服務和讀服務之間進行的一個折衷。

Quorum 定義#

Quorum 的定義如下：假設有 N 個副本，更新操作 wi 在 W 個副本中更新成功之後，才認為此次更新操作 wi 成功，把這次成功提交的更新操作對應的數據叫做：“成功提交的數據”。對於讀操作而言，至少需要讀 R 個副本才能讀到此次更新的數據，其中，W+R>N ，即 W 和 R 有重疊，一般，W+R=N+1。

N = 存儲數據副本的數量

W = 更新成功所需的副本

R = 一次數據對象讀取要訪問的副本的數量

Quorum就是限定了一次需要讀取至少N+1-w的副本數據,聽起來有些抽象，舉個例子，我們維護了10個副本，一次成功更新了三個，那麼至少需要讀取八個副本的數據，可以保證我們讀到了最新的數據。

Quorum 的應用#

Quorum 機制無法保證強一致性，也就是無法實現任何時刻任何用戶或節點都可以讀到最近一次成功提交的副本數據。

Quorum 機制的使用需要配合一個獲取最新成功提交的版本號的 metadata 服務，這樣可以確定最新已經成功提交的版本號，然後從已經讀到的數據中就可以確認最新寫入的數據。

Quorum 是分佈式系統中常用的一種機制，用來保證數據冗餘和最終一致性的投票算法，在 Paxos、Raft 和 ZooKeeper 的 Zab 等算法中，都可以看到 Quorum 機制的應用。

Paxos 節點的角色和交互#

了解了 Quorum 機制，我們接下來學習 Paxos 算法，首先看一下 Paxos 算法中的節點角色和交互。

Paxos 的節點角色#

在 Paxos 協議中，有三類節點角色，分別是 Proposer、Acceptor 和 Learner，另外還有一個 Client，作為產生議題者。

上述三類角色只是邏輯上的劃分，在工作實踐中，一個節點可以同時充當這三類角色。

Proposer 提案者#

Proposer 可以有多個，在流程開始時，Proposer 提出議案，也就是value，所謂 value，在工程中可以是任何操作，比如“修改某個變量的值為某個新值”，Paxos 協議中統一將這些操作抽象為 value。

不同的 Proposer 可以提出不同的甚至矛盾的 value，比如某個 Proposer 提議“將變量 X 設置為 1”，另一個 Proposer 提議“將變量 X 設置為 2”，但對同一輪 Paxos 過程，最多只有一個 value 被批准。

Acceptor 批准者#

在集群中，Acceptor 有 N 個，Acceptor 之間完全對等獨立，Proposer 提出的 value 必須獲得超過半數（N/2+1）的 Acceptor 批准後才能通過。

Learner 學習者#

Learner 不參與選舉，而是學習被批准的 value，在Paxos中，Learner主要參與相關的狀態機同步流程。

這裡Leaner的流程就參考了Quorum 議會機制，某個 value 需要獲得 W=N/2 + 1 的 Acceptor 批准，Learner 需要至少讀取 N/2+1 個 Accpetor，最多讀取 N 個 Acceptor 的結果後，才能學習到一個通過的 value。

Client 產生議題者#

Client 角色，作為產生議題者，實際不參與選舉過程，比如發起修改請求的來源等。

Proposer 與 Acceptor 之間的交互#

Paxos 中， Proposer 和 Acceptor 是算法核心角色，Paxos 描述的就是在一個由多個 Proposer 和多個 Acceptor 構成的系統中，如何讓多個 Acceptor 針對 Proposer 提出的多種提案達成一致的過程，而 Learner 只是“學習”最終被批准的提案。

Proposer 與 Acceptor 之間的交互主要有 4 類消息通信，如下圖：

這 4 類消息對應於 Paxos 算法的兩個階段 4 個過程，下面在分析選舉過程時會講到。

Paxos 選舉過程#

選舉過程可以分為兩個部分，準備階段和選舉階段，可以查看下面的時序圖：

Phase 1 準備階段#

Proposer 生成全局唯一且遞增的 ProposalID，向 Paxos 集群的所有機器發送 Prepare 請求，這裡不攜帶 value，只攜帶 N 即 ProposalID。

Acceptor 收到 Prepare 請求後，判斷收到的 ProposalID 是否比之前已響應的所有提案的 N 大，如果是，則：

在本地持久化 N，可記為 Max_N；
回覆請求，並帶上已經 Accept 的提案中 N 最大的 value，如果此時還沒有已經 Accept 的提案，則返回 value 為空；
做出承諾，不會 Accept 任何小於 Max_N 的提案。

如果否，則不回覆或者回覆 Error。

Phase 2 選舉階段#

為了方便描述，我們把 Phase 2 選舉階段繼續拆分為 P2a、P2b 和 P2c。

P2a：Proposer 發送 Accept#

經過一段時間後，Proposer 收集到一些 Prepare 回覆，有下列幾種情況：

若回覆數量 > 一半的 Acceptor 數量，且所有回覆的 value 都為空時，則 Porposer 發出 accept 請求，並帶上自己指定的 value。
若回覆數量 > 一半的 Acceptor 數量，且有的回覆 value 不為空時，則 Porposer 發出 accept 請求，並帶上回覆中 ProposalID 最大的 value，作為自己的提案內容。
若回覆數量 <= 一半的 Acceptor 數量時，則嘗試更新生成更大的 ProposalID，再轉到準備階段執行。

P2b：Acceptor 應答 Accept#

Accpetor 收到 Accpet 請求後，判斷：

若收到的 N >= Max_N（一般情況下是等於），則回覆提交成功，並持久化 N 和 value；
若收到的 N < Max_N，則不回覆或者回覆提交失敗。

P2c: Proposer 統計投票#

經過一段時間後，Proposer 會收集到一些 Accept 回覆提交成功的情況，比如：

當回覆數量 > 一半的 Acceptor 數量時，則表示提交 value 成功，此時可以發一個廣播給所有的 Proposer、Learner，通知它們已 commit 的 value；
當回覆數量 <= 一半的 Acceptor 數量時，則嘗試更新生成更大的 ProposalID，轉到準備階段執行。
當收到一條提交失敗的回覆時，則嘗試更新生成更大的 ProposalID，也會轉到準備階段執行。

Paxos 常見的問題#

關於Paxos協議，有幾個常見的問題，簡單介紹下。

1.如果半數以內的 Acceptor 失效，如何正常運行？

在Paxos流程中，如果出現半數以內的 Acceptor 失效，可以分為兩種情況：

第一種，如果半數以內的 Acceptor 失效時還沒確定最終的 value，此時所有的 Proposer 會重新競爭提案，最終有一個提案會成功提交。

第二種，如果半數以內的 Acceptor 失效時已確定最終的 value，此時所有的 Proposer 提交前必須以最終的 value 提交，也就是Value實際已經生效，此值可以被獲取，並不再修改。

2. Acceptor需要接受更大的N，也就是ProposalID有什麼意義？

這種機制可以防止其中一個Proposer崩潰宕機產生阻塞問題，允許其他Proposer用更大ProposalID來搶佔臨時的訪問權。

3. 如何產生唯一的編號，也就是 ProposalID？

在《Paxos made simple》論文中提到，唯一編號是讓所有的 Proposer 都從不相交的數據集合中進行選擇，需要保證在不同Proposer之間不重複，比如系統有 5 個 Proposer，則可為每一個 Proposer 分配一個標識 j(0~4)，那麼每一個 Proposer 每次提出決議的編號可以為 5*i + j，i 可以用來表示提出議案的次數。

總結#

這一課時分享了 Paxos 協議相關的知識點，Paxos 是經典的分佈式協議，理解了它們以後，學習其他分佈式協議會簡單很多。

Paxos算法更重要的是理解過程，並不是要把各個流程都背下來，除了文中介紹的，相關的分支判斷和選擇場景還有很多，如果希望了解Paxos算法相關的推導和證明，我在最後附上了 Paxos 相關的幾篇論文地址，感興趣的同學可以去學習下：

《Java 工程師高薪訓練營》

實戰訓練+面試模擬+大廠內推，想要提升技術能力，進大廠拿高薪，點擊鏈接，提升自己！

精選評論#

* 鑫：#

若回覆數量 > 一半的 Acceptor 數量，且有的回覆 value 不為空時，則 Porposer 發出 accept 請求，並帶上回覆中 ProposalID 最大的 value，作為自己的提案內容。

這個不太明白，作為自己的提案內容是什麼意思啊

講師回覆：

在投票後發現有其他的節點唯一 ID 超過自己，放棄本地操作，選擇其他節點的提案

** 露：#

老師，有一個疑問就是，一個 Porposer 生成了一次 ProposalID 就不會生成更大的 ProposalID 了呢？如果是這樣的話豈不是最後一個 Proposer 無論如何生成的 ProposalID 始終是最大的，這樣也不能防止這個 Porposer 崩潰宕機，產生阻塞呀？

講師回覆：

Porposer 生成的 ProposalID 是基於本地記錄信息生成的，是一個單點的最大值

** 文：#

如果半數以上的 Acceptor 失效，這個時候會發生什麼狀況，怎麼處理

講師回覆：

算法就不工作了，具體要看各家的工程實現吧

**9904：#

不錯，值得收藏

* 星：#

受教了，選舉問題！這就是個基礎的算法，每一家的產品都是在這個基礎上進行了一定的定制和細節優化

桑：#

在準備階段 Acceptor 收到 Prepare 請求，回覆時是回覆所有的 Proposer，還是誰請求了，回覆誰呢？

講師回覆：

回覆提案提出者

桑：#

老師您好，文中說多個 Proposer 的提案可能不同，還說如果提案沒有被半數以上的接受，那麼 Proposer 會生成更大的 ProposalID，這樣怎麼確認哪些 Proposer 的值是需要被保存的值呢？會不會一個不正確的值通過生成更大的 ProposalID 導致自己會選呢？

講師回覆：

paxos 應該是不存在惡意節點的，可以對比下拜占庭問題