Read-Write Quorum System 及在 Raft 中的實踐

引言

在 Paxos、Raft 這類一致性算法的描述裏，經常會看到 Majority、Quorum 這兩個詞，在以前我以爲都是表達 “半數以上” 的含義，最近才發現兩者有不小的區別。本文介紹這兩者的區別，以及在 Raft 中實踐中的問題。有了 Quorum 的視角，能更好得理解一致性算法。

Read-Write Quorum System

首先來在數學上給出 Read-Write Quorum System 的定義。

一個 Read-Write Quorum System（讀寫法定系統）是兩個集合組成的元組，即 Q=（R,W），其中：

• 集合 R 被稱爲 Read Quorum（讀法定集合），即可以認爲讀操作都是讀的集合 R 中的元素；

• 集合 W 被稱爲 Write Quorum（寫法定集合），即可以認爲寫操作都是寫入到集合 W 中的元素。

• $r∈R, w∈W,r∩w≠0 $，即任從讀集合中取一個成員 r，以及任從寫集合中取一個成員 w，這兩個集合一定有交集。

都知道在分佈式系統中，一個寫入操作要達成一致，讀寫操作一定要有一定的冗餘度，即：

• 寫入多份數據成功才能認爲寫入成功，

• 從多個節點讀到同一份數據才認爲讀取成功。

在 Majority 系統中，這個冗餘度就是系統內半數以上節點。因爲根據抽屜原理 [1]，當寫入到至少半數以上節點時，讀操作與寫操作一定有重合的節點。

但是在一個 Read-Write Quorum System 中，這個條件變的更寬泛了，在這類系統中，只需要滿足以下條件即可認爲讀寫成功：

$r∈R, w∈W,r∩w≠0 $

用直觀的大白話來說：在 Read-Write Quorum System 中，只要讀、寫集合中的任意元素有重合即可。

我們來詳細看看 Majority 和 Read-Write Quorum System 這兩個系統的區別在哪裏。

首先，Majority 系統並沒有區分讀、寫兩類不同的集合，因爲在它的視角里，讀和寫操作都要到半數以上節點才能達到一致。但是在 Read-Write Quorum System 系統裏，是嚴格區分了讀、寫集合的，儘管可能在很多時候，這兩類集合是一樣的。

再次，有了前面嚴格區分的讀、寫集合之後，以這個視角來看分佈式系統中，一個數據達成一致的大前提是 “讀、寫操作一定有重合的節點”，這樣就能保證：寫入一個數據到寫集合中，最終會被讀集合讀到。在 Majority 系統裏，讀、寫集合都必須是半數以上節點的要求當然能夠滿足這個條件，但是這個條件太強了。如果只考慮讀、寫集合有重合這個條件，是可以適當放寬而且還不影響系統的一致性的。

從以上的討論，可以得到下面的結論：

• 分佈式系統中，只要讀、寫集合有重合，就能保證數據的一致性了。

• Majority 系統是對上述條件的一個強實現，但是存在比這個實現更弱一些的實現，同樣能保證數據的一致性。

• 以 Read-Write Quorum System 的定義和視角來看，Majority 系統相當於在這兩方面強化了 Read-Write Quorum System 系統的要求：

• 讀、寫集合完全一樣，

• 且都是半數以上節點集合的 Read-Write Quorum System。

即可以認爲 Majority 系統，只是 Read-Write Quorum System 的一個子集。

講了這麼多，來看一個非 Majoiry 的 Read-Write Quorum System，下面的集合 {a,b,c,d,e,f} 組成的網格（grid）被劃分成了橫豎兩個讀、寫集合：

在上圖中，定義了一個 Read-Write Quorum System，Q={{abc}∪{def},{ab}∪{bc}∪{ac}}，其中：

• 讀集合爲 {abc}∪{def}，即橫着的兩個集合 {abc} 和 {def} 組成了讀集合。

• 寫集合爲 {ab}∪{bc}∪{ac}，即豎着的三個集合 {ab}、{bc}、{ac} 組成了寫集合。

顯然這個劃分是能夠滿足前面的條件：$r∈R, w∈W,r∩w≠0 $ 的，因爲任選一個讀集合中的集合如 {abc}，寫集合中任選的一個集合如 {bc}，這兩個集合中的元素都會有重合。

假設是這樣構成的一個分佈式系統，那麼寫操作只需要寫入寫集合中的任意一個集合即可認爲成功，可以看到一個寫集合最小可以只有兩個節點構成，這個數量是小於 Majority 的。

有了對 Read-Write Quorum System 系統及與 Majority 的區分和聯繫，以這個視角來看看 raft 的成員變更算法。

Read-Write Quorum 視角下的 Raft 成員變更算法

實際這幾個問題，在之前的博客重讀 Raft 論文中的集羣成員變更算法（二）：實踐篇 - codedump 的網絡日誌 [2] 中都有提及，不過這一次因爲有了新的視角，再拿出來看看。

單步成員變更的問題

假設一種場景，機房中的某個節點 a 由於各種原因需要下線，替換成同一機房中的另一個節點 d，即 a、d 節點在同機房，而 b 和 c 在另外兩個機房。

這意味着節點集合要從 {a,b,c} 變爲 {b,c,d}，根據 Raft 的單步成員變更算法，要經歷如下兩次單步變更：

• 加入節點 d，即從 {a,b,c} 變成 {a,b,c,d}。

• 刪除節點 a，即從 {a,b,c,d} 變成 {b,c,d}。

假設當集羣變爲 {a,b,c,d} 之後，如果 a、d 所在的機房與另外兩個機房發生了網絡隔離，那麼此時就選不出一個新的 leader，寫入數據也不能達成一致了。箇中原因，是因爲在這種情況下，以 Majority 的視角看來，無論讀、寫都沒法滿足 “半數以上” 這個條件了。

如果換成前面的 Read-Write Quorum 視角，將系統重新定義一個新的讀和寫 quorum 集合，如下：

• 讀 quorum 集合：仍然保持之前的 Majority 集合，即認爲要讀到半數以上節點才能認爲是讀成功。

• 寫 quorum 集合：在之前的 Majority 集合之外，再加入由 {b,c} 兩個節點組成的集合。

即對於這個新的 Read-Write Quorum System 而言，以最開始的數學定義來看：

Q(R,W) = Q(M(Q), M(Q) ∪ {b,c})。

其中 M(Q) 爲取集合 Q 的半數以上的節點集合，以 {a,b,c，d} 組成的集合來說，M(Q)={{a,b,c},{a,c,d},{b,c,d},{a,b,c,d}}

顯然，這裏的讀 quorum 集合和寫 quorum 集合，是可以滿足之前的條件的，即：$r∈R, w∈W,r∩w≠0 $ ，這是因爲 $M(Q)∩{b,c}≠0 $ 。

對於這個改造後的系統，可以認爲：

• 讀操作，仍然需要讀到集羣中至少半數以上的節點才能算讀成功。

• 寫操作，只要寫入 {b,c}（由於 {b,c} 已經包含在半數以上節點中，這裏就不單獨強調寫半數以上節點這個條件了）就可以認爲寫成功了。

這樣改造之後，即便系統出現了前面的機房隔離問題，也沒有問題。

Read-Write Quorum 視角下的 joint consensus 算法

與單步成員變更不同的是，joint consensus 算法允許一次提交多個節點的變化，在之前對 joint consensus 算法的描述中（見：重讀 Raft 論文中的集羣成員變更算法（一）：理論篇 - codedump 的網絡日誌 [3]），這個算法分爲兩階段提交（假設舊的節點集合爲 $C_Old$，而新的節點集合爲 $C_New$）：

• 首先提交一個 $C_Old ∪ C_New$ 的配置。
• 如果上述配置提交成功，再提交一個 $C_New$ 的配置。

在上面的例子中，$C_Old = {a,b,c}$，而 $C_New = {b,c,d}$。

從 Read-Write Quorum 的視角下來看看爲什麼 joint consensus 算法可以很好的工作，而不用像單步成員變更算法那樣擔心網絡隔離導致的問題。來計算一下集合 ${a,b,c} ∪ {b,c,d}$ 的 Majority 值：

M(abc) x M(bcd) = {
    ab ∪ bc,
    ab ∪ cd,
    ab ∪ bd,
    bc ∪ bc,
    bc ∪ cd,
    bc ∪ bd,
    ac ∪ bc,
    ac ∪ cd,
    ac ∪ bd,
} = {
    abc,
    abcd,
    abd,
    acd,
    bc,
    bcd,
} = {M(a,b,c,d),{b,c}}

（引用自 TiDB 在 Raft 成員變更上踩的坑 - OpenACID Blog[4]）

可以看到，計算出來的 Majority 集合剛好就是前面提到的 M(a,b,c,d)∪ {b,c}。

換言之，從數學角度來看，以上證明了 joint consensus 算法即便在網絡隔離的條件下，以 Majority 的條件來要求這個算法，也是能很好的工作的。這也就是爲什麼這個算法會比單步變更算法更爲健壯的數學依據。

quorum 改造的啓示

從以上的分析來看，從 Read-Write Quorum 視角來看，寫 Quorum 集合從 Majority 視角下的 W(Q)=M(Q)={{a,b,c},{a,c,d},{b,c,d},{a,b,c,d}}，擴展爲 W(Q)=M(Q)∪{b,c} 來提升系統的可用性。

未來，是不是可以針對 Raft 的寫操作，都能這樣改造寫 Quorum 集合，這會是一個有意思的方向，我還沒有對這個方向思考的更多，先把問題放在這裏：）

在論文 Read-Write Quorum Systems Made Practical [5] 中，作者給出了一個 Python 庫 quoracle:[6]，專門用於評估、計算不同的讀、寫集合下系統的可用性等指標。

參考資料

• TiDB 在 Raft 成員變更上踩的坑 - OpenACID Blog[7]
• 後分布式時代: 多數派讀寫的’少數派’實現 - OpenACID Blog[8]
• Read-Write Quorum Systems Made Practical [9]

引用鏈接

[1]抽屜原理: https://baike.baidu.com/item/%E6%8A%BD%E5%B1%89%E5%8E%9F%E7%90%86/233776

[2]重讀 Raft 論文中的集羣成員變更算法（二）：實踐篇 - codedump 的網絡日誌: https://www.codedump.info/post/20220507-weekly-14/

[3]重讀 Raft 論文中的集羣成員變更算法（一）：理論篇 - codedump 的網絡日誌: https://www.codedump.info/post/20220417-weekly-13/#%E4%B8%80%E6%AC%A1%E5%8F%98%E6%9B%B4%E5%A4%9A%E4%B8%AA%E8%8A%82%E7%82%B9

[4]TiDB 在 Raft 成員變更上踩的坑 - OpenACID Blog: https://blog.openacid.com/distributed/raft-bug/

[5]Read-Write Quorum Systems Made Practical : https://mwhittaker.github.io/publications/quoracle.pdf

[6]quoracle:: https://github.com/mwhittaker/quoracle

[7]TiDB 在 Raft 成員變更上踩的坑 - OpenACID Blog: https://blog.openacid.com/distributed/raft-bug/

[8]後分布式時代: 多數派讀寫的’少數派’實現 - OpenACID Blog: https://blog.openacid.com/algo/quorum/

[9]Read-Write Quorum Systems Made Practical : https://mwhittaker.github.io/publications/quoracle.pdf

關於 Databend

Databend 是一款開源、彈性、低成本，基於對象存儲也可以做實時分析的新式數倉。期待您的關注，一起探索雲原生數倉解決方案，打造新一代開源 Data Cloud。

Databend 文檔：https://databend.rs/
Twitter：https://twitter.com/Datafuse_Labs
Slack：https://datafusecloud.slack.com/
Wechat：Databend
GitHub ：https://github.com/datafuselabs/databend

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

引言