Paxos 算法是一種用於在分佈式系統中實現一致性的算法。算法的核心是多數派原則（Quorum），在一個分佈式系統中，只要有一組超過半數的接受者接受了某個提案，那麼這個提案的值就被認爲是達成一致的值。它能夠讓分佈式系統中的多個節點，在可能出現網絡故障、節點故障以及消息延遲、丟失或重複等複雜情況下，就某個值達成一致。

一、角色構成

• 提議者（Proposer）：主要職責是提出提案（Proposal）。提案是包含一個編號和一個值的組合，編號用於區分不同的提案，並且保證提案的順序。提議者需要與接受者進行通信，嘗試讓自己的提案被接受。
• 接受者（Acceptor）：接受者的主要職責是接收提議者的請求並決定是否接受提案，維護一些狀態信息，如已經響應過的最大提案編號。當收到提議者發送的準備請求時，接受者會比較請求中的提案編號和自己已經響應過的所有提案編號。只有當收到的提案編號大於已響應過的所有提案編號時，它纔會表示願意接受這個編號對應的提案。同時，接受者還會返回自己已經接受過的編號最大的提案（如果有的話）。
• 學習者（Learner）：學習者主要是獲取已經達成一致的提案值。不參與投票和決策的過程，學習者是數據備份節點，被動的接受數據（決策結果）。

二、算法核心流程（Basic Paxos）

階段一：準備階段（僅需攜帶提案 ID）

1. 生成一個提案 ID ，如下圖提案 ID 爲 K, 確保提案 ID 的唯一和遞增.

2. Proposer 向全體 Acceptor 發送 Prepare(K) 請求。

3. Acceptor 收到 Prepare 請求後，會有以下三種可能的迴應：

• Case1: 若 Acceptor 尚未承諾過任何提案（即 MaxN==null），則記錄當前最大提案編號 MaxN 爲 K，並回復 "ok"。
• Case2: 若提案編號 K 小於 Acceptor 記錄的最大提案編號 MaxN，則不予迴應或回覆錯誤提示。
• Case3: 若提案編號 K 大於 Acceptor 記錄的最大提案編號 MaxN，更新 MaxN 爲 K 並回復 "ok"；若 Acceptor 之前已接受過提案，則還需附帶已接受的提案編號 AcceptN 和對應的值 AcceptV。

5. 若 Proposer 收到超過半數 Acceptor 的 "ok" 回覆，則進入下一階段；否則，重新進入準備階段。

階段二：批准階段

1. Proposer 向所有在準備階段回覆 "ok" 的 Acceptor 發送 Accept 請求，請求中包含提案編號 K 以及從準備階段獲取的最大 AcceptN 所對應的 AcceptV（若之前無已接受的 value，則 Proposer 可自由決定 value）。

2. Acceptor 收到 Accept 請求後，會有以下兩種可能的迴應：

• case1: 若提案編號 K 小於 Acceptor 記錄的最大提案編號 MaxN，則不予迴應或回覆錯誤提示。
• case2：若提案編號 K 大於等於 Acceptor 記錄的最大提案編號 MaxN，則批准該請求，回覆 "ok"，並更新記錄 AcceptN=K，AcceptV=value（若之前已有 AcceptN 和 AcceptV，則會被覆蓋）。

4. 若 Proposer 收到超過半數 Acceptor 的 "ok" 回覆，則選舉過程結束，將結果通知給 Learner；否則，重新進入準備階段。

三、算法執行實例演示（Basic Paxos）

準備階段

不妨假設客戶端 1 選定的提案編號爲 1，客戶端 2 選定的提案編號爲 5。同時假定節點 A 和節點 B 率先接收到來自客戶端 1 的準備請求，而節點 C 則首先接收到來自客戶端 2 的準備請求。在 Paxos 算法的流程中，客戶端扮演提議者的角色，會向系統內所有的接受者發送準備請求，此請求的關鍵構成要素即爲提案編號。值得注意的是，在這一準備階段，請求內容僅涵蓋提案編號，而無需明確指定提議所對應的具體值，其目的在於通過提案編號來協調各節點之間的狀態，爲後續的一致性達成奠定基礎

接下來，節點 A，B 接收到客戶端 1 提案編號爲 1 準備請求，節點 C 接收到客戶端 2 提案編號爲 5 的準備請求。

集羣中各個節點在接收到第一個準備請求的處理：

• 節點 A, B：由於之前沒有通過任何提案，所以節點 A，B 將返回 “尚無提案” 的準備響應，並承諾以後不再響應提案編號小於等於 1 的準備請求，不會通過編號小於 1 的提案

• 節點 C：由於之前沒有通過任何提案，所以節點 C 將返回 “尚無提案” 的準備響應，並承諾以後不再響應提案編號小於等於 5 的準備請求，不會通過編號小於 5 的提案

接下來，當節點 A，B 接收到提案編號爲 5 的準備請求，節點 C 接收到提案編號爲 1 的準備請求

• 節點 A, B：由於提案編號 5 大於之前響應的準備請求的提案編號 1，且節點 A, B 都沒有通過任何提案，故均返回 “尚無提案” 的響應，並承諾以後不再響應提案編號小於等於 5 的準備請求，不會通過編號小於 5 的提案

• 節點 C：由於節點 C 接收到提案編號 1 小於節點 C 之前響應的準備請求的提案編號 5 ，所以丟棄該準備請求，不作響應

批准階段

Basic Paxos 算法第二階段爲批准階段。當客戶端 1，2 在收到大多數節點的準備響應之後會開始發送接受請求。

• 客戶端 1：客戶端 1 接收到大多數的接受者（節點 A, B）的準備響應後，根據響應中的提案編號最大的提案的值，設置接受請求的值。由於節點 A, B 均返回 “尚無提案”，即提案值爲空，故客戶端 1 把自己的提議值"leehao.me"作爲提案的值，發送接受請求[1, "leehao.me"]

• 客戶端 2：客戶端 2 接收到大多數接受者的準備響應後，根據響應中的提案編號最大的提案的值，設置接受請求的值。由於節點 A, B, C 均返回 “尚無提案”，即提案值爲空，故客戶端 2 把自己的提議值"www.leehao.me"作爲提案的值，發送接受請求[5, "www.leehao.me"]

當節點 A, B, C 接收到客戶端 1, 2 的接受請求時，對接受請求進行處理：

• 節點 A, B, C 接收到接受請求[1, "leehao.me"]，由於提案編號 1 小於三個節點承諾可以通過的最小提案編號 5，所以提案[1, "leehao.me"]被拒絕

• 節點 A, B, C 接收到接受請求[5, "www.leehao.me"]，由於提案編號 5 不小於三個節點承諾可以通過的最小提案編號 5 ，所以通過提案[5, "www.leehao.me"]，即三個節點達成共識，接受X的值爲"www.leehao.me"

如果集羣中還有學習者，當接受者通過一個提案，就通知學習者，當學習者發現大多數接受者都通過了某個提案，那麼學習者也通過該提案，接受提案的值。

接受者存在已通過提案的情況

上面例子中，準備階段和接受階段均不存在接受者已經通過提案的情況。這裏繼續使用上面的例子，不過假設節點 A, B 已通過提案[5, "www.leehao.me"]，節點 C 未通過任何提案。增加一個新的提議者客戶端 3，客戶端 3 的提案爲[9，"leehao"]。接下來，客戶端 3 執行準備階段和接受階段。客戶端 3 向節點 A, B, C 發送提案編號爲 9 的準備請求：

節點 A, B 接收到客戶端 3 的準備請求，由於節點 A, B 已通過提案[5, "www.leehao.me"]，故在準備響應中，包含此提案信息。節點 C 接收到客戶端 3 的準備請求，由於節點 C 未通過任何提案，故節點 C 將返回 “尚無提案” 的準備響應。

客戶端 3 接收到節點 A, B, C 的準備響應後，向節點 A, B, C 發送接受請求。這裏需要特點指出，客戶端 3 會根據響應中的提案編號最大的提案的值，設置接受請求的值。由於在準備響應中，已包含提案[5, "www.leehao.me"]，故客戶端 3 將接受請求的提案編號設置爲 9，提案值設置爲"www.leehao.me"即接受請求的提案爲[9, "www.leehao.me"]

節點 A, B, C 接收到客戶端 3 的接受請求，由於提案編號 9 不小於三個節點承諾可以通過的最小提案編號，故均通過提案[9,www.leehao.me]。

到這裏，我們總結下 Basic Paxos 特點：

• 採用準備和接受兩個階段達成共識。準備階段，提議者向接受者發送僅含提案編號的請求，接受者依規則決定響應與否及返回信息；接受階段，提議者根據反饋確定提案值再次請求，接受者判斷是否接受，以此逐步達成共識。

• 具備容錯性，在少於一半節點故障時，依靠多數派決策機制，集羣仍能正常工作，保障服務不間斷與數據一致。

• 提案編號大小代表優先級。對於提案編號，接受者提供三個承諾：

• 如果準備請求的提案編號，小於等於接受者已經響應的準備請求的提案編號，那麼接受者承諾不響應這個準備請求

• 如果接受請求中的提案編號，小於接受者已經響應的準備請求的提案編號，那麼接受者承諾不通過這個提案

• 如果按受者已通過提案，那些接受者承諾會在準備請求的響應中，包含已經通過的最大編號的提案信息

四、Paxos 算法的活鎖問題 

Basic Paxos 只能就單個提案值進行共識，不適合處理多個值的連續共識。在算法的運行流程中，可能會出現一種極端狀況：當存在兩個提案者（proposer）連續不斷地提出一系列編號嚴格遞增的議案時，系統可能會陷入一個無法終止的循環之中，導致無法順利進入並完成第二階段，也就是無法成功選定一個最終的提案。如下圖：

五、Multi-Paxos

Multi-Paxos 是對 Basic Paxos 的擴展，用於處理一系列值的連續共識。它的核心思想是將多個 Paxos 實例合併爲一個連續的過程，從而減少消息傳遞的次數和提高效率。在 Multi-Paxos 中，系統會選舉出一個領導者（Leader），負責協調整個過程。領導者會向其他節點（Acceptors）發送提議，並收集多數派的響應。一旦領導者收集到足夠的響應，它就會向所有節點廣播決定，從而完成一個值的提交。Multi-Paxos 通過引入領導者節點和優化共識流程，解決了 Basic Paxos 存在的問題

六、Multi-Paxos 算法工程實踐與應用

1、谷歌的分佈式鎖服務 Chubby

Chubby 通過 Multi-Paxos 算法來確保分佈式鎖服務的一致性和可用性，使得多個客戶端可以安全地訪問和修改共享資源。工作原理：Chubby 中的每個節點都運行着 Multi-Paxos 算法的一個實例，這些實例共同維護着鎖的狀態。當一個客戶端想要獲取鎖時，它會向 Chubby 發送一個請求。Chubby 的領導者節點會接收到這個請求，並嘗試通過 Multi-Paxos 算法來達成共識，以決定是否授予該客戶端鎖。一旦達成共識，領導者節點會向所有節點廣播決定，並更新鎖的狀態。客戶端在收到成功的響應後，即可獲得鎖並開始操作共享資源。

2、Google Spanner 與 Multi-Paxos 算法

Google Spanner 是一個全球分佈的、可擴展的、同步複製的數據庫系統。它旨在提供強一致性，同時支持水平擴展和高可用性。爲了實現這一目標，Spanner 採用了 Multi-Paxos 算法來管理分佈式數據的副本。在 Spanner 中，Multi-Paxos 算法被用於在多個副本之間複製數據。每個副本節點都運行着 Multi-Paxos 算法的一個實例，這些實例共同維護着數據的一致性。當一個寫操作發生時，領導者節點會接收到這個操作，並通過 Multi-Paxos 算法來達成共識，以決定是否在多個副本上執行該操作。一旦達成共識，領導者節點會向所有副本節點廣播寫操作，並更新數據狀態。讀操作則可以直接從任何一個副本節點上獲取數據，因爲 Multi-Paxos 算法保證了所有副本節點上的數據都是一致的。

最後

除了 Multi - Paxos 還有一些其它經典的一致性協議算法，如 raft 、zab。 Raft 是一種相對於 Paxos 算法更易理解和實現的分佈式一致性算法，在許多分佈式存儲系統和集羣管理工具中得到廣泛應用。例如在 etcd 中，Raft 算法用於維護文件系統元數據的一致性，確保不同節點對文件系統的目錄結構、文件屬性等信息的認知相同。Zab（Zookeeper Atomic Broadcast）是 ZooKeeper 實現分佈式數據一致性的核心算法。適用於需要分佈式協調服務的場景，如分佈式鎖、服務發現、配置管理等。

七、參考文獻

• https://leehao.me / 圖解 - Paxos - 算法 /

• http://www.scs.stanford.edu/20sp-cs244b/sched/readings/paxos_made_simple.pdf

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