Multi-Master-Paxos: 3

本文連結：

https：//

blog。openacid。com/algo/

mmp3/

Background

200行程式碼實現paxos-kv 中介紹了一款非常簡潔的分散式kv儲存實現， 它是基於 classic-paxos 實現分散式一致性。 在 paxos的直觀解釋 中我們提到， 每次寫入， 也就是每個 paxos 例項需要2輪 RPC 完成， 效率低。

一個常見的最佳化就是

mutli-paxos

（或raft）， 用一次 RPC 對多個例項執行 phase-1； 再對每個例項分別執行 phase-2， 這樣均攤開銷是一次 RPC 完成一次寫入。 它透過 phase-1 在叢集中確定了一個唯一可寫的 leader。 這種設計在跨機房（或跨雲）部署的環境中的缺陷是： 異地機房的寫入就需要2個 RTT 才能完成：

client → leader → followers → leader → client

也就是說它無法做到

異地多活

， 在3節點的場景裡， 有

2/3

的寫入效率降低到2 個 RTT。

本文從另一角度出發來解決異地多活的問題, 3機房部署的3副本叢集中:

任一節點都可寫,

任一筆寫入都可以嚴格在1個 RTT 內完成.

這就是今天要介紹的 200行程式碼實現paxos-kv 的改進版： mmp-3： multi-master-paxos 3副本實現。

同樣 show me the code 的原則不能變： 本文實現的3節點多活程式碼在：

異地多活是目前分散式領域越來越被重視的一個問題， 機房正在變成單機， 單機房多機分散式在現在大規模部署的業務中已經滿足不了業務的可用性需求了。

幾乎所有線上環境部署的分散式儲存， 都需要跨機房（或者跨雲）的部署。 而大家也積極在解決這些問題：

或者用佇列等最終一致性的手段來完成跨機房的複製， 這樣會產生資料不一致， 2條互相沖突的資料可能同時被寫入； 業務層需要參與解決這類衝突。

或者將資料做拆分， 將在A地寫入多的分配到A機房為 leader 的 sharding ， 將B地寫入較多的資料分配到B機房為 leader 的 sharding 。

或者一個機房為主： 部署2個副本， 另一個機房部署1個副本來形成3副本的叢集， 這樣實際上A機房故障會導致全域性不可讀寫， B機房只能提供額外的資料冗餘， 無法提供更多的資料可用性。

paxos 在叢集較小時可以透過定製 paxos 來完成1個 RTT 的寫入， 如果使用 majority-quorum， 最多支援5個副本的多活。

在 epaxos 定義的多活設計， 簡單介紹了3節點的設計， 但並沒有給出實現的細節， 其中各種衝突的處理以及修復的流程並沒有明確的定義。

同時 epaxos 的 apply 演算法存在不可解決的 livelock 問題： 透過 SCC 來確定 instance 順序無法保證在有限時間內結束。

另外 epaxos 的設計中缺少一個 rnd 記錄（ paxos 中的

last-seen-ballot

或 vbal）， 導致其一致性實現是錯誤的。

以及 instance 之間的依賴關係會在修復過程中產生不一致的問題。

epaxos 需要另外一個seq來確定 instance 之間的順序， 在 mmp3 的設計中， seq 是不必要的， 只需依賴關係就可以確定確定的 apply 順序。

Multi master paxos - 3

我們從 classic-paxos 出發來分析問題。

xp的tips： 要實現一個穩定的分散式系統， 最好用 raft， 因為開箱就用。 要學習分散式系統， 最好從 paxos 開始。 raft 看似簡單的設計 隱藏了一些隱晦的條件， 其正確性的證明要比 paxos 複雜。

我們需要達到2個目的：

1個 RTT 完成一次commit。

3個節點同時無衝突寫。

1 RTT 的 classic- paxos

如果 classic-paxos 不需要2個 RTT， 我們就不需要

multi-paxos

或 raft 這些東西來最佳化延遲了。

在3節點的系統中， 這是可以實現的。

首先做一些基礎的設定： 一個 replica 在系統中是一個replica（或叫作server或node）， 它同時是 proposer 和 acceptor。 一個 replica 接受到一個寫入請求時， 它就用本地的 proposer 來完成提交。

回顧

classic paxos

200行程式碼實現paxos-kv 介紹的 classic-paxos 寫入流程如下， replica-0 上的 proposer P0， 順次完成 phase-1， phase-2 和 commit：

思考以上過程。。。

最佳化 classic paxos 為 1個 RTT

因為 proposer 本身只是一個

資料結構

， 在 paxos 中， 它不需要跟 acceptor 有什麼繫結關係， 所以， 我們可以

讓 proposer 執行在任何一個 replica 上

： 把 proposer 發到另一個 replica 上執行， 這樣訊息的傳輸就可以轉變成 proposer 的傳輸。

要達到 paxos 要求的 2/3的

多數派

， 也只需要將 proposer 發到另外一個 replica， 因為這個 proposer 永遠只有1個例項， 所以不會出現不一致（proposer 或者在R0上工作或者在在R1上工作）。

如果要將 proposer 發到 2個 replica 就會複雜一些， 例如5節點中 quorum=3， 2個不同的 proposer 可能會嘗試使用不同的值。

透過傳送 proposer 的方式， paxos 可以被最佳化成如下的1 RTT實現： P0 在 R1 上順次執行 phase-1 和 phase-2， 然後再被送會R0：

在傳輸 proposer 的過程中， 區別於原始 paxos 的是： 往返兩個過程都要包括 proposer 的完整資訊：

R0 到 R1 的過程中， 要帶上使用者要提交的值， 以便在 R1 上 Prepare 成功後直接執行 Accept；

R1 到 R0 的過程中， 要帶上 R1 的 Prepare 和 Accept 的執行結果。

這樣一輪 RPC 後， R0 和 R1 就可以形成多數派， 然後 R0 可以直接 commit。

注意， 這個模型中， 除了 proposer 的位置變化了， 跟 classisc-paxos 沒有任何區別！ 也就是說， 任何 paxos 能完成的事情它都可以完成。

現在我們完成了第一個任務。 如果以此模型來重寫 200行程式碼實現paxos-kv， 可以在3副本系統上實現1 RTT提交， 但多寫入點依然會有衝突， 例如 R0 和 R1 同時發起同一個paxos instance的寫入， R0 在收到傳送回來的 P0 後， 可能就會發現本地的 instance 已經被 P1 以更高的 ballot 覆蓋了， 要重新提升P0 的ballot再重試。

這就是我們要解決的第二個問題： 避免不同 replica 的寫入衝突。

Multi

column log

2個 replica 同時寫一個 instance 產生活鎖， 導致無法保證1個 RTT 完成寫入。 要避免衝突， 我們就需要讓每個 replica 不能產生互相沖突的 instance，

所以給每個 replica 分配 instance 的空間要分開

。

在 mmp3 的實現中， 有3個replica 就需要有3列 instance ， 每個 replica 只寫其中一列。

例如：

R0 維護一個 proposer P0， 不斷的執行 paxos 在每個 replica 上 column

A

的 instance，

R1 維護 proposer P1， 只寫每個 replica 上的 column

B

列的 instance。

這種結構有點類似於 3 個標準的 raft 組， 每組都部署在3個replica上， 第i組的raft的leader就是R［i］

這樣， 因為沒有 instance 衝突， 所以不論任何一個 replica 上收到的寫請求， 都只需 1個 RTT 完成 instance 的提交。

但是！

這3列的 instance 目前還是

無關

的， 要想將 instance 應用到 state machine， 所有 replica 上的 instance 都必須以相同的順序 apply。 （不像 raft 裡的 instance 是簡單的單調遞增的， 只要保證 instance 一致， apply 的順序就一致）。

因此在 mmp3 中， 除了 instance 內容一致外， 還需要額外增加每列 instance 之間的約束， 來保證 apply 順序一致。 3個 column 中的 instance 之間是一種（較弱但一致的）

拓撲

順序， 因此在 mmp3 中， paxos 要確定的值（Value）包括2個：

使用者要提交的資料： 一條操作 state machine 的日誌： instance。Val，

還需要確定這個 instance 與其他 instance 的關係**。

使用 paxos 確定 instance 之間的關係

這個

關係

我們描述為： 一個 instance

X

看到了哪些其他 instance： 用

X。Deps

來表示， 用它來確定 instance 之間的 apply 的順序：

例如在單機系統中， 併發寫入3條資料a， b， c， 可以這樣確定 a， b， c 的順序：

如果 a 寫入時沒有看到 b ,那麼 a 就在 b 之前執行

。 所以可見性就表示了 instance 之間的順序。

當然這個思路在分散式系統中要複雜一些， 因為多個 replica 之間沒有單機中的鎖的保護， 多個 replica 上同一個 instance 看到的其他 instance 也可能不一樣。

最終 mmp3 中的 instance 資料結構相比 classic-paxos， 多了一個

Deps

欄位：

instance。Deps： 看到了哪些其他的 instance。

message Ins {

InsId InsId

Cmd Val

repeated int64 Deps // <——

BallotNum VBal // <——

bool Committed

}

Deps

的實現包括以下步驟的變化：

Proposer 選擇 Deps 的值

在上面 1-RTT 的 classic-paxos 基礎上：

在初始化 instance X 的時候（也就是建立

X

後， 在本地replica執行prepare的時候）， 將當前 replica 上所有知道其存在的 instance 集合初始化為

X。Deps

（包括 replica 上能看到的所有 instance， 以及這些 instance 看到的 instance， 雖然間接看到的 instance 可能不存在於當前 replica），

執行 accept 的時候， 最終

X。Deps

的值為2次 prepare 獲得的

Deps

的

並集

作為 accept 的值。

例如 instance

a4

， 在建立它的 replica 上和被複制到的另一個 replica 上分別看到

b2， c2

和

b1， c3

， 對應得到的2個

a4。Deps

分別是：

［4， 2， 2］

和

［4， 1， 3］

：

那麼

a4

將用來執行 accpet 的

Deps

值就是

［4， 2， 3］

：

classic-paxos 中要求 prepare 階段看到的已存在的值要使用， 而 mmp3 中將所有 prepare 階段看到的

Deps

的值做了並集， 實際上並沒有破壞 paxos 的約束， 只不過 classic-paxos 假設它的

值

是任意的， 不一定可取並集， mmp3 中可以把 prepare 過程中看到的

Deps

的值認為是

VBal

為 0 的一個值，

讀者可以自行驗證， 它不會破壞 classic-paxos 要求的任何約束。

因為

X。Deps

的值的確定也透過 paxos， 所以可以保證每個 replica 上的每個 instance 最終提交的

Deps

都是一致的。

這時再透過一個確定的演算法使用每個 instance

Deps

的值來決定 apply 的順序， 就可以保證多個 replica 上的 state machine 最終狀態一致。

以上兩點滿足了 apply 演算法的第一個要求：

Consistency

。 此外， apply 的順序還需提供另外一個保證

Linearizability

， 即： 如果 propose A 發生在 commit B 之後， 那麼 A 應該在 B 之後apply。

這是一個直覺上的要求： 如果一個命令

set x=1

發給儲存系統並返回OK（committed）， 那麼這之後發給儲存的

get x

命令， 應該一定能看到

x=1

的值。

實際上xp認為在分散式系統全域性範圍內使用絕對時間的先後並不是一個理性的選擇。 不過它更容易被業務使用。

接下來我們設計一個演算法來滿足

Linearizability

的要求：

Apply 演算法： 有環

有向圖

中節點的定序

Interfering instance

mmp3 中設定： 任意2個 instance 都是 interfering 的， 即， 交換2個 instance 的 apply 順序會導致結果不同（雖然可能是可以互換順序的）。

epaxos 中認為 set x=1 和 set y=2 這2個 instance 可以互換順序， 因為x的值跟y的值無關， 但 set x=y 和 set y=2 這2個 instance 不能互換順序 apply， 因為順序的變化會產生不同的x的結果。 也是因為 epaxos 需要透過減少 interfering 的數量來實現1個 RTT， 所以才有了這個設計。

在3 replica 的系統中，

mmp3 有無衝突都只需要1個 RTT

， 所以我們可以無需擔心 interfering 的 instance 的衝突帶來的另一個RTT開銷。 只需假設任意2個 instance 都是 interfering 的， 這樣反倒能簡化問題。

Lemma-0： instance 之間的依賴關係

定義 A 依賴 B， 即

A → B

為：

A。Deps ∋ B

。

因為 mmp3 假定任意2個instance都是interfering的， 並且2個 instance 提交的 quorum 必然有交集， 所以任意2個 instance 之間至少有一個依賴關係， 即， A， B之間的關係只可能是：

A → B

B → A

A ↔ B

依賴關係構成一個可能帶環的有向圖， 例如按照以下時間順序執行：

R0 propose a1， a1。Deps = ［1， 0， 0］，

R1 propose b1， b1。Deps = ［0， 1， 0］，

R0 send a1 to R1， a1。Deps = ［1， 1， 0］

R1 send b1 to R0， b1。Deps = ［1， 1， 0］

R0 commit a1

R1 commit b1

這樣 a1 ∈ b1。Deps 且 b1 ∈ a1。Deps

依賴關係很直觀， 這個依賴關係的圖中， 我們將試圖尋找一個有限大小的集合來實現一個有效的 apply 演算法。

Lemma-1： 用Deps確定Linearizability

首先我們有一個小結論：

如果 A 在 B commit 之後被 propose, 那麼一定有 A.Deps ⊃ B.Deps

。

因為 B 如果 commit 了， 那麼

B。Deps

， 也就是 B 看到的所有其他 instance 的 id 集合， 就已經複製到了某個 quorum。 那麼 A 在執行 paxos 的時候，一定會看到 B commit 的

B。Deps

的值。

又因為

A。Deps

是2個在 prepare 階段看到的

Deps

的值的並集， 因此

A。Deps

一定包含全部

B。Deps

的instance。

於是實現 apply 演算法的思路就是：

如果 A。Deps ⊃ B。Deps， 先 apply B， 即可以保證Linearizability。

其他情況下， 選擇何種順序都不會破壞 Linearizability， 所以 mmp3 中使用 instance 的 （columnIndex， index） 的大小排序來確定 apply 順序。

epaxos 提供了一種簡單粗暴的方法來在有環圖中確定 apply 順序： 從圖中一個節點出發： 找到

最大連通子圖

（Strongly-Connected-Component or SCC）（沒有出向邊的一個節點也是一個SCC）， 然後按照節點， 也就是 instance 的某個屬性（例如epaxos中使用（seq， instanceId）） 來排序一個SCC中的節點， 再按順序 apply。

epaxos 的 SCC 演算法有個問題， 就是一個 SCC 可能無限增大， 例如 A commit 之前有另一個interfering 的 instance B 被 propose， 然後 B commit 之前又出現interfering 的 instance C。。。，

那麼 epaxos 的做法就無法保證在有限時間內找出 SCC。

epaxos 建議中斷一小段時間的新 instance 的 propose 來斷開 SCC， 這也是不容易實現的， 因為必須在n-1個 replica 同時中斷才有效。 只要有2個 replica 在持續的寫入新 instance， 那麼就有可能造成無限大的 SCC。

Lemma-2： 不需要 SCC

第2個小結論：

如果 A, B不屬於同一個 SCC, 即, A ∈ SCC₁ B ∉ SCC₁, 那麼

：

A → B ⇒ A.Deps ⊃ B.Deps

。

B → A ⇒ B.Deps ⊃ A.Deps

。

因為根據 Lemma-0， 任意2個 instance 至少有一個依賴關係， 如果X ∈ B。Deps 且 X ∉ A。Deps， 那麼必然有 X → A， 導致 A → B → X → A 成為一個SCC。

因此，

不論A, B是否在一個 SCC 中, 保證 Linearizability 的條件都可以用 Deps 來確定, 所以我們的演算法不必尋找 SCC , 只需遍歷依賴關係

。

減小遍歷數量： 只需考慮最老的 instance

以上 apply 演算法還可以進一步最佳化為最多隻考慮3個 instnace 的方式：

假設 a1， a2 是 column-A 上相鄰的2個 instance， 那麼一定有

a1 ∈ a2。Deps

。 根據 apply 演算法設計，

a1。Deps ⊃ a2。Deps

一定不成立， a2 一定不會在 a1 之前 apply：

如果 a1 不依賴 a2， a1 一定先apply，

如果 a1 依賴 a2， 但 a1 的

（a3。columnIndex， a3。index）

較小， 所以 a1 也一定會在 a2 之前apply。

因此只需考慮每個 column 上最老的一個未 apply 的 instance 就可以找出下一個 apply 的 instance。 在 mmp3 中， 最多有3個（但演算法本身不限於3）。

Lemma-3： Deps 集合數量來決定 Linearizability

定義一個依賴數量：

|X.Deps| 為 X 依賴的, 未 apply 的 instance 的所在 column 的數量

。

例如： a3。Deps = ［3， 2， 2］：

如果完成 apply 的 instance 是 ［2， 1， 1］， 即 a1， a2， b1， c1， 那麼此時a3在3個 column 上都依賴一個未 apply 的 instance：

|a3。Deps|=3

。

之後如果c2 被 apply 了， 那麼

|a3。Deps| = 2

。

這裡可以清楚的看到一個結論：

A。Deps ⊃ B。Deps ⇒ |A。Deps| > |B。Deps|

。

最終 apply 演算法為：

找到一個 column 上下一個已 commit, 未 apply 的 instance X, 遍歷X.Deps, 得到未遍歷過的 column 上的最老的未 apply 的 instance, 遍歷結束後, 選擇(|X.Deps|, X.columnIndex) 最小的一個apply 到 state machine

。

下次再 apply 時， 重新構造這個圖， 找到第二個要執行的 instance。

必須重新遍歷， 因為之前排序第2的 instance， 在新加入一個 instance 之後可能還是第2。

這樣， 每個 replica 上， committed 的 instance 的 Deps 值都一樣， 最老的3個 instance 構成的

依賴圖

也都一樣， 於是找出第1個 apply 的 instance 也一樣， 重複這個步驟， 找出的第2個 apply 的 instance 也一樣。。。 最終每個 replica 上的 state machine 達到一致的狀態， 保證了

Consistency

。

Apply 執行的例子

例如以下 20 個 instance 的 Deps 關係是一個有向圖， 最終生成的 apply 順序是一個單向路徑：

RPC的超時重試

paxos 假設工作在一個網路不可靠的環境中， 在標準的實現中， 如果某個請求超時， 理論上應該進行重試。 mmp3 的執行環境假設與 classic-paxos 一樣， 也需要對超時重試。 這裡跟 classic-paxos 有一點差別， 就是

重試時必須提升自己的 BallotNum

， 重新在本地執行 prepare， 再用新的 BallotNum 重發RPC。

這是因為 prepare 過程中， 在每個 replica 上得到的

Deps

的值可能不同。

例如R0 propose 的 instance X， 在 R1 和 R2 上的 prepare 後， 可能會分別得到不同的

X。Deps

的值（2個replica包含的instance不同）。 使用同一個 BallotNum 無法區分哪一個才是最新的值。

重試提升BallotNu

m， 才能保證最後被確定的值能被識別出來。

一個修復程序（例如R0宕機後， R1或R2都可以重新執行 paxos 進行修復）， 在R1 和 R2上看到2個不同 BallotNum 的 X， 那麼說明較小 BallotNum 的

X

沒有成功返回應答給 R0， R0 放棄了它， 並進行了重試。 這時只需考慮較大 BallotNum 的 instance ， 它是唯一可能被 R0 commit 的。

以下是重試過程：

recovery

上面提到的重試機制為正確的recovery做好了準備： 當 R0 發起一輪 paxos 後並宕機了， R1 或 R2 都可以透過超時檢查來發現這個問題並修復未 commit 的 instance 。 要修復的內容依舊是2個： instance 要執行的命令 Val ， 以及 instance 看到哪些其他的 instance： Deps。

因為這2個值都是透過 classic-paxos 來確立的， 修復過程也很簡單， 提升 BallotNum 再執行一次 paxos 就可以了。 相當於將 R0 的leadership 搶走賦予給了另一個 replica。

程式碼和測試

git repo mmp3 是一份本文介紹的 multi-master 的三副本實現（mmp3 分支）， 其中主要的 server 端 instance 提交的邏輯實現在

mmp。go

， apply 演算法實現在

apply_*

中。

程式碼中除了基本的單元測試， 最主要的是：

Test_set_get

對一個三副本叢集進行隨機讀寫壓測， 這個測試中模擬傳送和接受的網路錯誤（各20%機率）， 在這種情況下， 檢查：

全部寫請求都提交

3個 replica 的 instance 一致

3個 replica 上 apply 順序一致， 以及最終 state machine 中的狀態一致。

Limitation

mmp3 設計上只支援3節點系統， 其次這個實現中不包含成員變更實現。

總結

mmp3 是一個完全對等的設計實現的multi-master consensus。 之前在試圖基於 epaxos 實現一個 multi-master 的儲存， 中間卻發現幾處不易修復的問題（開始還有幾個容易修復的問題）， 於是打算自己設計一套。

期待與對這個方向感興趣各路神仙交流蛋逼~

Reference：

200行程式碼實現基於paxos的kv儲存 ：

https：//

zhuanlan。zhihu。com/p/27

5710507

classic paxos ：

http：//

lamport。azurewebsites。net

/pubs/pubs。html#paxos-simple

可靠分散式系統-paxos的直觀解釋 ：

https：//

zhuanlan。zhihu。com/p/14

5044486

multi-master-paxos-3 ：

https：//

github。com/openacid/pax

oskv/tree/mmp3

多數派讀寫的少數派實現 ：

https：//

zhuanlan。zhihu。com/p/26

7559303

本文連結：

https：//

blog。openacid。com/algo/

mmp3/