聊聊 分佈式一致性算法協議 Paxos

大家好，我是不才陳某~

Google 的粗粒度鎖服務 Chubby 的設計開發者 Burrows 曾經說過：所有一致性協議本質上要麼是 Paxos 要麼是其變體。

網上有很多講解 Paxos 算法的文章，但是質量層次不齊。今天筆者帶大家深入聊一下 Paxos

Paxos 是什麼？

Paxos 算法是基於消息傳遞且具有高度容錯特性的一致性算法，是目前公認的解決分佈式一致性問題最有效的算法之一。

Paxos 算法是 Lamport 宗師提出的一種基於消息傳遞的分佈式一致性算法，使其獲得 2013 年圖靈獎。

自 Paxos 問世以來就持續壟斷了分佈式一致性算法，Paxos 這個名詞幾乎等同於分佈式一致性。

Google 的很多大型分佈式系統都採用了 Paxos 算法來解決分佈式一致性問題，如 Chubby、Megastore 以及 Spanner 等。開源的 ZooKeeper，以及 MySQL 5.7 推出的用來取代傳統的主從複製的 MySQL Group Replication 等紛紛採用 Paxos 算法解決分佈式一致性問題。

但是它也有兩個明顯的缺點：

  1. 難以理解

  2. 在工程是實現上比較複雜。

問題產生的背景

在常見的分佈式系統中，總會發生諸如機器宕機或網絡異常（包括消息的延遲、丟失、重複、亂序，還有網絡分區）等情況。Paxos 算法需要解決的問題就是如何在一個可能發生上述異常的分佈式系統中，快速且正確地在集羣內部對某個數據的值達成一致，並且保證不論發生以上任何異常，都不會破壞整個系統的一致性。

“

這裏某個數據的值並不只是狹義上的某個數，它可以是一條日誌，也可以是一條命令（command）。根據應用場景不同，某個數據的值有不同的含義。

”

相關概念

在 Paxos 算法中，有三種角色：

需要注意的是，在具體的算法實現過程中，並不是一個進程只能擔任其中一種角色，它有可能會同時充當多個。比如一個進程既是 Proposer 又是 Acceptor 還是 Learner。

還有一個很重要的概念叫提案（Proposal）。最終要達成一致的 value 就在提案裏。

這個提案包括什麼呢？是僅僅包括一個信息數值嗎？到底是如何咱們繼續向下閱讀，目前咱們先認爲僅僅是一個普普通通的 value。

初次認識

Paxos 算法過程和我國的立法過程是極其相似的（法律案的提出、法律案的審議、法律案的表決、法律的公佈四個階段），所謂的提案就是新頒佈法律。

Proposer (提案者) 可以提出（propose）提案；Accoptor 可以接受（accept）提案；如果某個提案被選定（chosen），那麼該提案裏的 value 就被選定了。

回到剛剛說的『對某個數據的值達成一致』，指的是 Proposer、Acceptor、Learner 都認爲同一個 value 被選定（chosen）。那麼，Proposer、Acceptor、Learner 分別在什麼情況下才能認爲某個 value 被選定呢？

問題描述

假設有一組可以提出（propose）value 的進程集合（提案者團隊），一個一致性算法需要保證提出的這麼多 value 中，僅僅只有一個相同的 value 被選定（chosen）。也就是說要麼沒有 value 被提出，只要提出了 value 並且被選定，那麼大家最終學習到的 value 必須是一致的。對於一致性算法，安全性（safaty）要求如下：

“

Paxos 的目標：保證最終有一個 value 會被選定，當 value 被選定後，進程最終也能獲取到被選定的 value。

”

俗話說的好，哪裏有需求，哪裏就會出現糟糕的問題。如果假設不同角色之間可以通過發送消息來進行通信，那麼：

以上都是可能會遇到的問題，要怎麼解決？？？

推導過程

最簡單的方案——只有一個 Acceptor

假設只有一個 Acceptor（可以有多個 Proposer），只要 Acceptor 接受它收到的第一個提案，則該提案被選定，該提案裏的 value 就是被選定的 value。這樣就保證只有一個 value 會被選定。

但是，如果這個唯一的 Acceptor 宕機了，那麼整個系統就無法工作了！

因此，一個 Acceptor 是不可行的，必須要有多個 Acceptor！

多個 Acceptor

當有多個 Acceptor 的時候，如何保證在多個 Proposer 和多個 Acceptor 的情況下選定一個 value 呢？

大家可以自己先進行思考。

首先，我們的最終目標是無論有多少 Proposer 提出提案，有且僅有一個 value 被選定。

那麼，我們可以先定義一個約束：

“

P1：一個 Acceptor 必須接受它收到的第一個提案。

”

但是，這樣又會出現其它的問題：如果每個 Proposer 所提出的提案 value 是不同的，並且將提案發送給不同的 Acceptor。根據 P1 約束，每個 Acceptor 都接受它收到的第一個提案，就會出現不同 value 被選定的情況，出現了不一致。

剛剛是因爲『一個提案只要被一個 Acceptor 接受，則該提案的 value 就被選定了』才導致了出現上面不一致的問題。因此，我們需要加一個規定：

“

規定：一個提案被選定需要被半數以上的 Acceptor 接受

”

一個提案被半數以上接受，說明『一個 Acceptor 必須能夠接受不止一個提案！』，不然可能導致最終沒有 value 被選定。比如上圖的情況。v1、v2、v3 都沒有被選定，因爲它們都只被一個 Acceptor 的接受，並沒有被超過半數以上的 Acceptor 接受。

最開始將【提案 = value】已經無法滿足現在的需求，因爲當一個 Proposer 發送多個提案到一個 Acceptor 的時候，需要使用一個編號來區分被提出的順序。現在【提案 = 提案編號 + value】。

雖然允許多個提案被選定，但必須保證所有被選定的提案都具有相同的 value 值。否則又會出現不一致。

“

P2：如果某個 value 爲 v 的提案被選定了，那麼每個編號更高的被選定提案的 value 必須也是 v。

”

一個提案只有被 Acceptor 接受纔可能被選定，因此我們可以把 P2 約束改寫成對 Acceptor 接受的提案的約束 P2a。

“

P2a：如果某個 value 爲 v 的提案被選定了，那麼每個編號更高的被 Acceptor 接受的提案的 value 必須也是 v。

”

只要滿足了 P2a，就能滿足 P2。

但是，考慮如下的情況：以立法過程爲背景，假設總的有 5 個人大代表（Acceptor）。

人民法院（Proposer2）提出 [M1,V1] 的提案，人大代表 2-5 號（半數以上）均接受了該提案，於是對於人大代表 2-5 號和人民法院來講，它們都認爲 V1 提案是被選定的。此時，人大代表 1 在辦完其它事務之後也參與到其中（之前人大代表 1 沒有收到過任何提案），此時最高人民檢察院（另一個提案者 Proposer1）向人大代表 1 發送了 [M2,V2] 的提案（V2≠V1 且 M2>M1），對於人大代表 1 來講，這是它收到的第一個提案。根據 P1（一個 Acceptor 必須接受它收到的第一個提案。）, 人大代表 1 必須接受該提案！同時人大代表 1 認爲 V2 被選定。這就出現了兩個問題：

  1. 人大代表 1 認爲 V2 被選定，人大代表 2-5 和人民法院認爲 V1 被選定。出現了不一致。

  2. V1 被選定了，但是編號更高的被人大代表 1 接受的提案 [M2,V2] 的 value 爲 V2，且 V2≠V1。這就跟 P2a（如果某個 value 爲 v 的提案被選定了，那麼每個編號更高的被 Acceptor 接受的提案的 value 必須也是 v）矛盾了。

所以，我們要對 P2a 約束進行加強！

P2a 是對 Acceptor 接受的提案約束，但其實提案是 Proposer 提出來的，所有我們可以對 Proposer 提出的提案進行約束。得到 P2b：

“

P2b：如果某個 value 爲 v 的提案被選定了，那麼之後任何 Proposer 提出的編號更高的提案的 value 必須也是 v。

”

那麼，如何確保在某個 value 爲 v 的提案被選定後，Proposer 提出的編號更高的提案的 value 都是 v 呢？

只要滿足 P2c 即可：

“

P2c：對於任意的 N 和 V，如果提案 [N, V] 被提出，那麼存在一個半數以上的 Acceptor 組成的集合 S，滿足以下兩個條件中的任意一個：

  • S 中每個 Acceptor 都沒有接受過編號小於 N 的提案。

  • S 中 Acceptor 接受過的最大編號的提案的 value 爲 V。

”

Proposer 生成提案

爲了滿足 P2b，這裏有個比較重要的思想：Proposer 生成提案之前，應該先去『學習』已經被選定或者可能被選定的 value，然後以該 value 作爲自己提出的提案的 value。如果沒有 value 被選定，Proposer 纔可以自己決定 value 的值。這樣才能達成一致。這個學習的階段是通過一個『Prepare 請求』實現的。

於是我們得到了如下的提案生成算法：

  1. Proposer 選擇一個新的提案編號 N，然後向某個 Acceptor 集合（半數以上）發送請求，要求該集合中的每個 Acceptor 做出如下響應（response）。

    (a) 向 Proposer 承諾保證不再接受任何編號小於 N 的提案。

    (b) 如果 Acceptor 已經接受過提案，那麼就向 Proposer 響應已經接受過的編號小於 N 的最大編號的提案。

    我們將該請求稱爲編號爲 N 的 Prepare 請求。

  2. 如果 Proposer 收到了半數以上的 Acceptor 的響應，那麼它就可以生成編號爲 N，Value 爲 V 的提案 [N,V]。這裏的 V 是所有的響應中編號最大的提案的 Value。如果所有的響應中都沒有提案，那 麼此時 V 就可以由 Proposer 自己選擇 (一般爲當前提案)。

    生成提案後，Proposer 將該提案發送給半數以上的 Acceptor 集合，並期望這些 Acceptor 能接受該提案。我們稱該請求爲 Accept 請求。（注意：此時接受 Accept 請求的 Acceptor 集合不一定是之前響應 Prepare 請求的 Acceptor 集合）

Acceptor 接受提案

Acceptor 可以忽略任何請求（包括 Prepare 請求和 Accept 請求）而不用擔心破壞算法的安全性。因此，我們這裏要討論的是什麼時候 Acceptor 可以響應一個請求。

我們對 Acceptor 接受提案給出如下約束：

“

P1a：一個 Acceptor 只要尚未響應過任何編號大於 N 的 Prepare 請求，那麼他就可以接受這個編號爲 N 的提案。

”

如果 Acceptor 收到一個編號爲 N 的 Prepare 請求，在此之前它已經響應過編號大於 N 的 Prepare 請求。根據 P1a，該 Acceptor 不可能接受編號爲 N 的提案。因此，該 Acceptor 可以忽略編號爲 N 的 Prepare 請求。當然，也可以回覆一個 error，讓 Proposer 儘早知道自己的提案不會被接受。

因此，一個 Acceptor 只需記住：1. 已接受的編號最大的提案 2. 已響應的請求的最大編號。

Paxos 算法描述

經過上面的推導，我們總結下 Paxos 算法的流程。

Paxos 算法分爲兩個階段。具體如下：

  1. 階段一：

  2. Proposer 選擇一個提案編號 N，然後向半數以上的 Acceptor 發送編號爲 N 的 Prepare 請求。

  3. 如果一個 Acceptor 收到一個編號爲 N 的 Prepare 請求，且 N 大於該 Acceptor 已經響應過的所有 Prepare 請求的編號，那麼它就會將它已經接受過的編號最大的提案（如果有的話） 作爲響應反饋給 Proposer，同時該 Acceptor 承諾不再接受任何編號小於 N 的提案。

  4. 階段二：

  5. 如果 Proposer 收到半數以上 Acceptor 對其發出的編號爲 N 的 Prepare 請求的響應，那麼它就會發送一個針對 [N,V] 提案的 Accept 請求給半數以上的 Acceptor（和之前的 Acceptor 不一定相同）。注意：V 就是收到的響應中編號最大的提案的 value，如果響應中不包含任何提案，那麼 V 就由 Proposer 自己決定。

  6. 如果 Acceptor 收到一個針對編號爲 N 的提案的 Accept 請求，只要該 Acceptor 沒有對編號大於 N 的 Prepare 請求做出過響應，它就接受該提案。

Learner 學習被選定的 value

Learner 學習（獲取）被選定的 value 有如下三種方案：

方案一

Acceptor 接受到一個提案，就將該提案發送給所有 Learners.

方案二

Acceptor 接受一個提案，就將提案發送給主 Learner, 主 Learner 再通知其它 Learner

方案三

Acceptor 接受一個提案，就將提案發送給 Learner 團,Learner 團再通知其它 Learner

如何保證 Paxos 算法的活性

通過選取主 Proposer，就可以保證 Paxos 算法的活性。通過選取主 Proposer，並規定只有主 Proposer 才能提出議案。這樣一來只要主 Proposer 和過半的 Acceptor 能夠正常進行網絡通信，那麼但凡主 Proposer 提出一個編號更高的提案，該提案終將會被批准，這樣通過選擇一個主 Proposer，整套 Paxos 算法就能夠保持活性。至此，我們得到一個既能保證安全性，又能保證活性的分佈式一致性算法——Paxos 算法。

總結

到此，我們針對 Paxos 算法是什麼、它的特性以及算法的具體推導過程做了詳細的闡述。Paxos 算法是現在很多一致性算法的變體，非常值得我們學習

碼猿技術專欄 前螞蟻 P8，純粹的技術人，專注於 Java 後端技術分享，只寫外面看不到的乾貨，你想要的都在這裏……

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

猜你喜歡