可靠分佈式系統 - Paxos 的直觀解釋

paxos 是什麼？

• 在分佈式系統中保證多副本數據強一致的算法。

paxos 有啥用？

• 沒有 paxos 的一堆機器, 叫做分佈式；

• 有 paxos 協同的一堆機器, 叫分佈式系統。

Google Chubby 的作者 Mike Burrows 說過：

這個世界上只有一種一致性算法，那就是 Paxos …

其他一致性算法, 都可以看做 paxos 在實現中的變體和擴展。

另外一個經常被提及的分佈式算法是【raft】，raft 的貢獻在於把一致性算法落地。因爲【Leslie Lamport】的理論很抽象，要想把他的理論應用到現實中，還需要工程師完全掌握他的理論再添加工程必要的環節才能跑起來。

經常有人問起 raft 和 paxos 的區別，或在實現中應該選擇哪個，在不瞭解 paxos 之前可能會有這種疑問。對於這個問題, 就像是被問及四則運算和算盤有什麼區別，小店老闆應該使用四則運算還是用算盤結賬一樣。

記得 Leslie Lamport 2015 年時來了一次北京，那時會場上有人也問了老爺子 paxos 和 raft 有啥區別。

老爺子當時給出的回答是：沒聽過 raft…

raft 的核心可以認爲是 multi paxos 的一個應用，對於要掌握一致性算法的核心內容，從 paxos 入手，更容易去掉無關干擾，直達問題本質。所以我們選擇 paxos 作爲了解一致性算法的入口，聊開了聊透了。

網絡上 raft 比 paxos 流行，因爲 raft 的描述更直白一些，實際上 raft 比 paxos 更復雜。raft 詳細的解釋了 “HOW”，缺少 “WHY” 的解釋。paxos 從根本上解釋清楚了 “WHY”，但一直缺少一份通俗易懂的教程，以至於沒有被更廣泛的接受。所以就有了本文，一篇 paxos 入門教程，從基本的分佈式中的複製的問題出發，通過逐步解決和完善這幾個問題，最後推導出 paxos 的算法。

本文分爲 2 個部分:

• 前 1 部分是分佈式一致性問題的討論和解決方案的逐步完善，用人話得出 paxos 算法的過程。如果只希望理解 paxos 而不打算花太多時間深入細節， 只閱讀這 1 部分就可以啦。

• 第 2 部分是 paxos 算法和協議的嚴格描述。這部分可以作爲 paxos 原 paper 的實現部分的概括。如果你打算實現自己的 paxos 或類似協議。需要仔細瞭解協議細節，希望這部分內容可以幫你節省閱讀原 paper 的時間。

圖片是 xp 之前做過的 paxos 分享使用的 slides，在此基礎上加入了更多口頭解釋的內容。

分佈式系統要解決的問題

slide-01

paxos 的工作，就是把一堆運行的機器協同起來，讓多個機器成爲一個整體系統。在這個系統中，每個機器都必須讓系統中的狀態達成一致，例如三副本集羣如果一個機器上上傳了一張圖片，那麼另外 2 臺機器上也必須複製這張圖片過來。整個系統才處於一個一致的狀態。

slide-02
我是無需解釋的目錄頁。

slide-03
分佈式系統的一致性問題最終都歸結爲分佈式存儲的一致性。像 aws 的對象存儲可靠性要求是 9 ~ 13 個 9。而這麼高的可靠性都是建立在可靠性沒那麼高的硬件上的。

slide-04
幾乎所有的分佈式存儲（甚至單機系統），參考【EC 第一篇：原理】，【EC 第二篇：實現】，【EC 第三篇：極限】 都必須用某種冗餘的方式在廉價硬件的基礎上搭建高可靠的存儲。而冗餘的基礎就是多副本策略，一份數據存多份。多副本保證了可靠性，而副本之間的一致，就需要 paxos 這類分佈式一致性算法來保證。

slide-05
在早些年各種各樣的複製策略都被提出來來解決各種場景下的需要。除了複製的份數之外，各種各樣的算法實際上都是在嘗試解決一致的問題。從下一頁開始簡單回顧下各種複製策略，看看他們的優缺點以及 paxos 如何解決副本之間一致性的問題。

不太完美的複製策略

不太完美的複製策略

slide-06
無需解釋的目錄頁 

slide-07
主從異步複製是最簡單的策略之一，它很容易實現，但存在一個問題：客戶端收到一個數據已經安全（OK）的信息，跟數據真正安全（數據複製到全部的機器上）在時間上有一個空隙，這段時間負責接收客戶端請求的那個機器（master）如果被閃電擊中或被隕石砸到或被打掃衛生的大姐踢斷了電源，那數據就可能會丟失。因此它不是一個可靠的複製策略（使用主從異步複製要求你必須相信宇宙中不存在閃電隕石和掃地大姐）。

slide-08
跟主從異步複製相比，主從同步複製提供了完整的可靠性：直到數據真的安全的複製到全部的機器上之後，master 才告知客戶端數據已經安全。

但主從同步複製有個致命的缺點就是整個系統中有任何一個機器宕機，寫入就進行不下去了。相當於系統的可用性隨着副本數量指數降低。

slide-09
然鵝，在同步和異步之間，做一個折中，看起來是一個不錯的方案。這就是半同步複製。它要求 master 在應答客戶端之前必須把數據複製到足夠多的機器上，但不需要是全部。這樣副本數夠多可以提供比較高的可靠性；1 臺機器宕機也不會讓整個系統停止寫入。

但是它還是不完美，例如數據 a 複製到 slave-1，但沒有到達 slave-2；數據 b 複製達到了 slave-2 但沒有到達 slave-1，這時如果 master 掛掉了需要從某個 slave 恢復出數據，任何一個 slave 都不能提供完整的數據。所以在整個系統中，數據存在某種不一致。

slide-10
爲了解決半同步複製中數據不一致的問題，可以將這個複製策略再做一改進：多數派讀寫：每條數據必須寫入到半數以上的機器上。每次讀取數據都必須檢查半數以上的機器上是否有這條數據。

在這種策略下，數據可靠性足夠，宕機容忍足夠，任一機器故障也能讀到全部數據。

slide-11
然鵝多數派讀寫的策略也有個但是，就是對於一條數據的更新時，會產生不一致的狀態。例如：

• node-1，node-2 都寫入了 a=x

• 下一次更新時 node-2，node-3 寫入了 a=y

這時，一個要進行讀取 a 的客戶端如果聯繫到了 node- 1 和 node-2，它將看到 2 條不同的數據。

爲了不產生歧義，多數派讀寫還必須給每筆寫入增加一個全局遞增的時間戳。更大時間戳的記錄如果被看見，就應該忽略小時間戳的記錄。這樣在讀取過程中，客戶端就會看到 a=x₁，a=y₂ 這 2 條數據，通過比較時間戳 1 和 2 發現 y 是更新的數據，所以忽略 a=x₁ 這樣保證多次更新一條數據不產生歧義。

slide-12
是的，但是又來了。這種帶時間戳的多數派讀寫依然有問題。就是在客戶端沒有完成一次完整的多數派寫的時候：例如，上面的例子中寫入 a=x₁ 寫入了 node-1 和 node-2，a=y₂ 時只有 node-3 寫成功了，然後客戶端進程就掛掉了，留下系統中的狀態如下：

node-1: a=x₁
node-2: a=x₁
node-3: a=y₂

這時另一個讀取的客戶端來了：

• 如果它聯繫到 node-1 和 node-2，那它得到的結果是 a=x₁

• 如果它聯繫到 node-2 和 node-3，那它得到的結果是 a=y₂

整個系統對外部提供的信息仍然是不一致的

slide-13
現在我們已經非常接近最終奧義了，paxos 可以認爲是多數派讀寫的進一步升級，paxos 中通過 2 次原本並不嚴謹的多數派讀寫，實現了嚴謹的強一致 consensus 算法。

從多數派讀寫到 paxos 的推導

從多數派讀寫到 paxos 的推導

slide-14
首先爲了清晰的呈現出分佈式系統中的核心問題：一致性問題, 我們先設定一個假象的存儲系統，在這個系統上，我們來逐步實現一個強一致的存儲，就得到了 paxos 對一致性問題的解決方法。

slide-15
在實現中，set 命令直接實現爲一個多數派寫，這一步非常簡單。而 inc 操作邏輯上也很簡單，讀取一個變量的值 i₁，給它加上一個數字得到 i₂，再通過多數派把 i₂ 寫回到系統中。

slide-16
冰雪如你一定已經看到了這種實現方式中的問題：如果有 2 個併發的客戶端進程同時做這個 inc 的操作，在多數派讀寫的實現中，必然會產生一個 Y 客戶端覆蓋 X 客戶端的問題，從而產生了數據更新點的丟失。

而 paxos 就是爲了解決這類問題提出的，它需要讓 Y 能檢測到這種併發衝突，進而採取措施避免更新丟失。

slide-17
提取一下上面提到的問題：讓 Y 去更新的時候不能直接更新 i₂ 而是應該能檢測到 i₂ 的存在，進而將自己的結果保存在下一個版本 i₃ 中，再寫回系統中。

而這個問題可以轉化成：i 的每個版本只能被寫入一次，不允許修改。如果系統設計能滿足這個要求，那麼 X 和 Y 的 inc 操作就都可以正確被執行了。

slide-18
於是我們的問題就轉化成一個更簡單，更基礎的問題：如何確定一個值（例如 iⱼ）已經被寫入了。

直觀來看，解決方法也很簡單，在 X 或 Y 寫之前先做一次多數派讀，以便確認是否有其他客戶端進程已經在寫了，如果有，則放棄。

slide-19
但是！ 這裏還有個併發問題，X 和 Y 可能同時做這個寫前讀取的操作，並且同時得出一個結論：還沒有其他進程在寫入，我可以寫。這樣還是會造成更新丟失的問題。

slide-20
爲了解決上面的問題，存儲節點還需要增加一個功能，就是它必須記住誰最後一個做過寫前讀取的操作。並且只允許最後一個完成寫前讀取的進程可以進行後續寫入，同時拒絕之前做過寫前讀取的進程寫入的權限。

可以看到，如果每個節點都記得誰讀過，那麼當 Y 最後完成了寫前讀取的操作後，整個系統就可以阻止過期的 X 的寫入。

這個方法之所以能工作也是因爲多數派寫中，一個系統最多隻能允許一個多數派寫成功。paxos 也是通過 2 次多數派讀寫來實現的強一致。

slide-21
以上就是 paxos 算法的全部核心思想了，是不是很簡單？剩下的就是如何實現的簡單問題了：如何標識一個客戶端如 X 和 Y，如何確認誰是最後一個完成寫前讀寫的進程，等等。

slide-22
【Leslie Lamport】就這麼把這麼簡單的一個算法寫了個 paper 就獲得了圖領獎！騷年，改變世界就這麼容易！

paxos 算法描述

paxos 算法描述

接下來的篇幅中我們將用計算機的語言準確的描述整個 paxos 運行的過程。

slide-23
首先明確要解決的問題：

slide-24
我們要介紹的 paxos 實際上是最樸實的 classic paxos，在這之後我們順提下幾個老爺子對 paxos 的優化，multi paxso 和 fast paxos，它們都是針對 paxos 的理論層面的優化。

slide-25
paxos 算法中解決了如何在不可靠硬件基礎上構建一個可靠的分佈式系統的方法。但 paxos 核心算法中只解決網絡延遲 / 亂序的問題，它不試圖解決存儲不可靠和消息錯誤的問題，因爲這兩類問題本質上跟分佈式關係不大，屬於數據校驗層面的事情。

有興趣可以參考【Byzantine Paxos】的介紹。

slide-26
本文儘量按照【Classic Paxos】的術語來描述。

老爺子後面的一篇 【Fast Paxos】實現了 fast-paxos，同時包含了 classic-paxos，但使用了一些不同的術語表示。

• Proposer 可以理解爲客戶端。

• Acceptor 可以理解爲存儲節點。

• Quorum 在 99% 的場景裏都是指多數派，也就是半數以上的 Acceptor。

• Round 用來標識一次 paxos 算法實例，每個 round 是 2 次多數派讀寫：算法描述裏分別用 phase-1 和 phase-2 標識。同時爲了簡單和明確，算法中也規定了每個 Proposer 都必須生成全局單調遞增的 round，這樣 round 既能用來區分先後也能用來區分不同的 Proposer（客戶端）。

slide-27
在存儲端（Acceptor）也有幾個概念：

• last_rnd 是 Acceptor 記住的最後一次進行寫前讀取的 Proposer（客戶端）是誰，以此來決定誰可以在後面真正把一個值寫到存儲中。

• v 是最後被寫入的值。

• vrnd 跟 v 是一對，它記錄了在哪個 Round 中 v 被寫入了。

v 和 vrnd 是用於恢復一次未完成的 paxos 用的。一次未完成的 paxos 算法運行可能留下一些沒有達到多數派的值的寫（就像原生的多數派寫的髒讀的問題）， paxos 中通過 vrnd 來決定哪些值是最後寫入的，並決定恢復哪個未完成的 paxos 運行。後面我們會通過幾個例子來描述 vrnd 的作用。

slide-28
首先是 paxos 的 phase-1，它相當於之前提到的寫前讀取過程。它用來在存儲節點（Acceptor）上記錄一個標識：我後面要寫入；並從 Acceptor 上讀出是否有之前未完成的 paxos 運行。如果有則嘗試恢復它；如果沒有則繼續做自己想做的事情.

我們用類似 yaml 的格式來描述 phase-1 的請求 / 應答的格式：

request:
    rnd: int

response:
    last_rnd: int
    v: "xxx",
    vrnd: int

phase-1 成功後，acceptor 應該記錄 X 的 rnd=1，並返回自己之前保存的 v 和 vrnd。

slide-29
Proposer X 收到多數（quorum）個應答，就認爲是可以繼續運行的。如果沒有聯繫到多於半數的 acceptor，整個系統就 hang 住了，這也是 paxos 聲稱的只能運行少於半數的節點失效。

這時 Proposer 面臨 2 種情況：

• 所有應答中都沒有任何非空的 v，這表示系統之前是乾淨的，沒有任何值已經被其他 paxos 客戶端完成了寫入（因爲一個多數派讀一定會看到一個多數派寫的結果），這時 Proposer X 繼續將它要寫的值在 phase-2 中真正寫入到多於半數的 Acceptor 中。

• 如果收到了某個應答包含被寫入的 v 和 vrnd，這時，Proposer X 必須假設有其他客戶端（Proposer）正在運行，雖然 X 不知道對方是否已經成功結束， 但任何已經寫入的值都不能被修改！所以 X 必須保持原有的值。於是 X 將看到的最大 vrnd 對應的 v 作爲 X 的 phase-2 將要寫入的值。

  這時實際上可以認爲 X 執行了一次（不知是否已經中斷的）其他客戶端（Proposer）的修復。

slide-30
在第 2 階段 phase-2，Proposer X 將它選定的值寫入到 Acceptor ，這個值可能是它自己要寫入的值，或者是它從某個 Acceptor 上讀到的 v（修復）。

同樣用類似 yaml 的方式描述請求應答：

request:
    v: "xxx",
    rnd: int

reponse:
    ok: bool

slide-31
當然這時（在 X 收到 phase-1 應答，到發送 phase-2 請求的這段時間），可能已經有其他 Proposer 又完成了一個 rnd 更大的 phase-1，所以這時 X 不一定能成功運行完 phase-2。

Acceptor 通過比較 phase-2 請求中的 rnd，和自己本地記錄的 rnd，來確定 X 是否還有權寫入。如果請求中的 rnd 和 Acceptor 本地記錄的 rnd 一樣，那麼這次寫入就是被允許的, Acceptor 將 v 寫入本地，並將 phase-2 請求中的 rnd 記錄到本地的 vrnd 中。

用例子看 paxos 運行

用例子看 paxos 運行

好了 paxos 的算法描述也介紹完了。這些抽象的算法描述，其中的規則覆蓋了實際所有可能遇到的情況的處理方式。一次不太容易看清楚它們的作用，所以我們接下來通過幾個例子來看看 paxos 如何處理各種不同狀態並最終使整個系統的狀態達成一致。

slide-32
沒衝突的例子不解釋了 

slide-33
X 和 Y 同時運行 paxos，Y 迫使 X 中斷的例子：

• X 成功完成了寫前讀取（phase-1），將 rnd=1 寫入到左邊 2 個 Acceptor。

• Y 用更大的 rnd=2，覆蓋了 X 的 rnd，將 rnd=2 寫入到右邊 2 個 Acceptor。

• X 以爲自己還能運行 phase-2，但已經不行了，X 只能對最左邊的 Acceptor 成功運行 phase-2，而中間的 Acceptor 拒絕了 X 的 phase-2。

• Y 對右邊 2 個 Acceptor 成功運行了 phase-2，完成寫入 v=y，vrnd=2。

slide-34
繼續上面的例子，看 X 如何處理被搶走寫入權的情況：

這時 X 的 phase-2 沒成功，它需要重新來一遍，用更大的 rnd=3。

• X 成功在左邊 2 個 Acceptor 上運行 phase-1 之後，X 發現了 2 個被寫入的值：v=x，vrnd=1 和 v=y，vrnd=2；這時 X 就不能再寫入自己想要寫入的值了。它這次 paxos 運行必須不能修改已存在的值，這次 X 的 paxos 的運行唯一能做的就是，修復（可能）已經中斷的其他 proposer 的運行。

• 這裏 v=y，vrnd=2 是可能在 phase-2 達到多數派的值。v=x，vrnd=1 不可能是，因爲其他 proposer 也必須遵守算法約定，如果 v=x，vrnd=1 在某個 phase-2 達到多數派了，Y 一定能在 phase-1 中看到它，從而不會寫入 v=y, vrnd=2。

因此這是 X 選擇 v=y，並使用 rnd=3 繼續運行，最終把 v=y，vrnd=3 寫入到所有 Acceptor 中。

slide-35
Paxos 還有一個不太重要的角色 Learner，是爲了讓系統完整加入的，但並不是整個算法執行的關鍵角色，只有在最後在被通知一下。

Paxos 優化

**

Paxos 優化

**

slide-36
第一個優化 multi-paxos：

paxos 誕生之初爲人詬病的一個方面就是每寫入一個值就需要 2 輪 rpc：phase-1 和 phase-2。因此一個尋常的優化就是用一次 rpc 爲多個 paxos 實例運行 phase-1。

例如，Proposer X 可以一次性爲 i₁~i₁₀ 這 10 個值， 運行 phase-1，例如爲這 10 個 paxos 實例選擇 rnd 爲 1001，1002…1010，這樣就可以節省下 9 次 rpc，而所有的寫入平均下來只需要 1 個 rpc 就可以完成了。

這麼看起來就有點像 raft 了：

• 再加上 commit 概念（commit 可以理解爲: 值 v 送達到多數派這件事情是否送達到多數派了）

• 和組成員變更（將 quorum 的定義從 “多於半數” 擴展到 “任意 2 個 quourm 必須有交集”）

slide-37
第二個優化 fast-paxos：

fast-paxos 通過增加 quorum 的數量來達到一次 rpc 就能達成一致的目的。如果 fast-paxos 沒能在一次 rpc 達成一致，則要退化到 classic paxos。

slide-38
fast-paxos 爲了能在退化成 classic paxos 時不會選擇不同的值, 就必須擴大 quorum 的值。也就是說 fast-round 時，quorum 的大小跟 classic paxos 的大小不一樣。同樣我們先來看看爲什麼 fast-quorum 不能跟 classic-quorum 一樣，這樣的配置會引起 classic 階段回覆時選擇錯誤的值 y₀：

slide-39
要解決這個問題，最粗暴的方法是把 fast-quorum 設置爲 n，也就是全部的 acceptor 都寫入成功才認爲 fast-round 成功（實際上是退化到了主從同步複製）。這樣，如果 X 和 Y 兩個 proposer 併發寫入，誰也不會成功，因此 X 和 Y 都退化到 classic paxos 進行修復，選任何值去修復都沒問題。因爲之前沒有 Proposer 認爲自己成功寫入了。.

如果再把問題深入下，可以得出，如果 classic paxos 的 quorum 是 n/2+1，那麼 fast-round 的 quorum 應該是大於 ¾n，¾ 的由來可以簡單理解爲：在最差情況下，達到 fast-quorum 的 acceptor 在 classic-quorum 中必須大於半數，纔不會導致修復進程選擇一個跟 fast-round 不同的值。.

slide-40
下面是一個 fast-round 中 X 成功，Y 失敗的衝突的例子：

X 已經成功寫入到 4（fast-quorum>¾n）個 acceptor，Y 只寫入 1 個，這時 Y 進入 classic-round 進行修復，可以看到，不論 Y 選擇哪 3（classic quorum）個 acceptor，都可以看到至少 2 個 x₀，因此 Y 總會選擇跟 X 一樣的值，保證了寫入的值就不會被修改的條件。

slide-41
再來看一個 X 和 Y 都沒有達到 fast-quorum 的衝突：

這時 X 和 Y 都不會認爲自己的 fast-round 成功了，因此修復過程選擇任何值都是可以的。最終選擇哪個值，就回歸到 X 和 Y 兩個 classic-paxos 進程的競爭問題了。最終會選擇 x₀ 或 y₀ 中的一個。

其他

slide-42
一個很容易驗證的優化，各種情況下都能得到一致的結果。

參考鏈接

• [raft]：https://raft.github.io/

• [Leslie Lamport]：http://www.lamport.org/

• [Byzantine Paxos]：https://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos

• [Classic Paxos]：http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple

• [Fast Paxos]：http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos

• [EC 第一篇：原理]：https://blog.openacid.com/storage/ec-1

• [EC 第二篇：實現]：https://blog.openacid.com/storage/ec-2

• [EC 第三篇：極限]：https://blog.openacid.com/storage/ec-3

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