引言

在 Paxos、Raft 這類一致性算法的描述里，經(jīng)常會看到 Majority、Quorum 這兩個詞，在以前我以為都是表達(dá)“半數(shù)以上”的含義，最近才發(fā)現(xiàn)兩者有不小的區(qū)別。本文介紹這兩者的區(qū)別，以及在 Raft 中實踐中的問題。有了 Quorum 的視角，能更好得理解一致性算法。

Read-Write Quorum System

?首先來在數(shù)學(xué)上給出 Read-Write Quorum System 的定義。

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

??集合 R 被稱為 Read Quorum（讀法定集合），即可以認(rèn)為讀操作都是讀的集合 R 中的元素；

??集合 W 被稱為 Write Quorum（寫法定集合），即可以認(rèn)為寫操作都是寫入到集合 W 中的元素。

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

都知道在分布式系統(tǒng)中，一個寫入操作要達(dá)成一致，讀寫操作一定要有一定的冗余度，即：

??寫入多份數(shù)據(jù)成功才能認(rèn)為寫入成功，

??從多個節(jié)點讀到同一份數(shù)據(jù)才認(rèn)為讀取成功。

在 Majority 系統(tǒng)中，這個冗余度就是系統(tǒng)內(nèi)半數(shù)以上節(jié)點。因為根據(jù)抽屜原理（https://baike.baidu.com/item/%E6%8A%BD%E5%B1%89%E5%8E%9F%E7%90%86/233776），當(dāng)寫入到至少半數(shù)以上節(jié)點時，讀操作與寫操作一定有重合的節(jié)點。

但是在一個 Read-Write Quorum System 中，這個條件變的更寬泛了，在這類系統(tǒng)中，只需要滿足以下條件即可認(rèn)為讀寫成功：

r∈R,w∈W,r∩w=0

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

我們來詳細(xì)看看 Majority 和 Read-Write Quorum System 這兩個系統(tǒng)的區(qū)別在哪里。

首先，Majority 系統(tǒng)并沒有區(qū)分讀、寫兩類不同的集合，因為在它的視角里，讀和寫操作都要到半數(shù)以上節(jié)點才能達(dá)到一致。但是在 Read-Write Quorum System 系統(tǒng)里，是嚴(yán)格區(qū)分了讀、寫集合的，盡管可能在很多時候，這兩類集合是一樣的。

再次，有了前面嚴(yán)格區(qū)分的讀、寫集合之后，以這個視角來看分布式系統(tǒng)中，一個數(shù)據(jù)達(dá)成一致的大前提是“讀、寫操作一定有重合的節(jié)點”，這樣就能保證：寫入一個數(shù)據(jù)到寫集合中，最終會被讀集合讀到。在 Majority 系統(tǒng)里，讀、寫集合都必須是半數(shù)以上節(jié)點的要求當(dāng)然能夠滿足這個條件，但是這個條件太強(qiáng)了。如果只考慮讀、寫集合有重合這個條件，是可以適當(dāng)放寬而且還不影響系統(tǒng)的一致性的。

從以上的討論，可以得到下面的結(jié)論：

??分布式系統(tǒng)中，只要讀、寫集合有重合，就能保證數(shù)據(jù)的一致性了。

? Majority 系統(tǒng)是對上述條件的一個強(qiáng)實現(xiàn)，但是存在比這個實現(xiàn)更弱一些的實現(xiàn)，同樣能保證數(shù)據(jù)的一致性。

??以 Read-Write Quorum System 的定義和視角來看，Majority 系統(tǒng)相當(dāng)于在這兩方面強(qiáng)化了 Read-Write Quorum System 系統(tǒng)的要求:

1.讀、寫集合完全一樣，

2.且都是半數(shù)以上節(jié)點集合的 Read-Write Quorum System。

即可以認(rèn)為 Majority 系統(tǒng)，只是 Read-Write Quorum System 的一個子集。

講了這么多，來看一個非 Majoiry 的 Read-Write Quorum System，下面的集合 {a,b,c,d,e,f} 組成的網(wǎng)格（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}，這兩個集合中的元素都會有重合。

假設(shè)是這樣構(gòu)成的一個分布式系統(tǒng)，那么寫操作只需要寫入寫集合中的任意一個集合即可認(rèn)為成功，可以看到一個寫集合最小可以只有兩個節(jié)點構(gòu)成，這個數(shù)量是小于 Majority 的。

有了對 Read-Write Quorum System 系統(tǒng)及與 Majority 的區(qū)分和聯(lián)系，以這個視角來看看raft的成員變更算法。

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

實際這幾個問題，在之前的博客重讀 Raft 論文中的集群成員變更算法（二）：實踐篇 - codedump 的網(wǎng)絡(luò)日志[2]（https://www.codedump.info/post/20220507-weekly-14/）中都有提及，不過這一次因為有了新的視角，再拿出來看看。

單步成員變更的問題

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

這意味著節(jié)點集合要從 {a,b,c} 變?yōu)?{b,c,d}，根據(jù) Raft 的單步成員變更算法，要經(jīng)歷如下兩次單步變更：

??加入節(jié)點 d，即從 {a,b,c} 變成 {a,b,c,d}。

??刪除節(jié)點 a，即從 {a,b,c,d} 變成 {b,c,d}。

假設(shè)當(dāng)集群變?yōu)?{a,b,c,d} 之后，如果 a、d 所在的機(jī)房與另外兩個機(jī)房發(fā)生了網(wǎng)絡(luò)隔離，那么此時就選不出一個新的 leader，寫入數(shù)據(jù)也不能達(dá)成一致了。個中原因，是因為在這種情況下，以 Majority 的視角看來，無論讀、寫都沒法滿足“半數(shù)以上”這個條件了。

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

??讀 quorum 集合：仍然保持之前的 Majority 集合，即認(rèn)為要讀到半數(shù)以上節(jié)點才能認(rèn)為是讀成功。

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

即對于這個新的 Read-Write Quorum System 而言，以最開始的數(shù)學(xué)定義來看：

顯然，這里的讀 quorum 集合和寫 quorum 集合，是可以滿足之前的條件的，即：r∈R,w∈W,r∩w=0?，這是因為?M(Q)∩b,c=0?。

對于這個改造后的系統(tǒng)，可以認(rèn)為：

??讀操作，仍然需要讀到集群中至少半數(shù)以上的節(jié)點才能算讀成功。

??寫操作，只要寫入{b,c}（由于 {b,c} 已經(jīng)包含在半數(shù)以上節(jié)點中，這里就不單獨強(qiáng)調(diào)寫半數(shù)以上節(jié)點這個條件了）就可以認(rèn)為寫成功了。

這樣改造之后，即便系統(tǒng)出現(xiàn)了前面的機(jī)房隔離問題，也沒有問題。

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

與單步成員變更不同的是，joint consensus 算法允許一次提交多個節(jié)點的變化，在之前對 joint consensus 算法的描述中（見：重讀Raft論文中的集群成員變更算法（一）：理論篇 - codedump的網(wǎng)絡(luò)日志（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）），這個算法分為兩階段提交（假設(shè)舊的節(jié)點集合為?COld，而新的節(jié)點集合為?CNew）：

??首先提交一個?COld∪CNew?的配置。

??如果上述配置提交成功，再提交一個?CNew?的配置。

在上面的例子中，COld=a,b,c，而?CNew=b,c,d。

從 Read-Write Quorum 的視角下來看看為什么 joint consensus 算法可以很好的工作，而不用像單步成員變更算法那樣擔(dān)心網(wǎng)絡(luò)隔離導(dǎo)致的問題。來計算一下集合?a,b,c∪b,c,d的 Majority 值：

（引用自?TiDB 在 Raft 成員變更上踩的坑 - OpenACID Blog（https://blog.openacid.com/distributed/raft-bug））

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

換言之，從數(shù)學(xué)角度來看，以上證明了 joint consensus 算法即便在網(wǎng)絡(luò)隔離的條件下，以 Majority 的條件來要求這個算法，也是能很好的工作的。這也就是為什么這個算法會比單步變更算法更為健壯的數(shù)學(xué)依據(jù)。

quorum 改造的啟示

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

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

在論文?Read-Write Quorum Systems Made Practical（https://mwhittaker.github.io/publications/quoracle.pdf）中，作者給出了一個 Python 庫?quoracle（https://github.com/mwhittaker/quoracle），專門用于評估、計算不同的讀、寫集合下系統(tǒng)的可用性等指標(biāo)。

參考資料

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

??后分布式時代: 多數(shù)派讀寫的“少數(shù)派”實現(xiàn) - OpenACID Blog：https://blog.openacid.com/algo/quorum

??Read-Write Quorum Systems Made Practical：https://mwhittaker.github.io/publications/quoracle.pdf

關(guān)于?Databend

Databend 是一款開源、彈性、低成本，基于對象存儲也可以做實時分析的新式數(shù)倉。期待您的關(guān)注，一起探索云原生數(shù)倉解決方案，打造新一代開源 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