分布式系統(tǒng)原理

Quorum 機制

Quorum 機制是一種簡單有效的副本管理機制。本節(jié)首先討論一種最簡單的副本控制規(guī)則write-all-read-one，在此基礎(chǔ)上，放松約束，討論 quorum 機制。

1. 約定

為了簡化討論，本節(jié)先做這樣的約定：更新操作（write）是一系列順序的過程，通過其他機制確定更新操作的順序（例如 primary-secondary 架構(gòu)中由 primary 決定順序），每個更新操作記為 w i ，i 為更新操作單調(diào)遞增的序號，每個 w i 執(zhí)行成功后副本數(shù)據(jù)都發(fā)生變化，稱為不同的數(shù)據(jù)版本，記作 v i 。假設(shè)每個副本都保存了歷史上所有版本的數(shù)據(jù)。

2. Write-all-read-one

Write-all-read-one（簡稱 WARO）是一種最簡單的副本控制規(guī)則，顧名思義即在更新時寫所有的副本，只有在所有的副本上更新成功，才認(rèn)為更新成功，從而保證所有的副本一致，這樣在讀取數(shù)據(jù)時可以讀任一副本上的數(shù)據(jù)。

• 假設(shè)有一種 magic 的機制，當(dāng)某次更新操作 w i 一旦在所有 N 個副本上都成功，此時全局都能知道這個信息，此后讀取操作將指定讀取數(shù)據(jù)版本為 v i 的數(shù)據(jù)，稱在所有 N 個副本上都成功的更新操作為“成功提交的更新操作”，稱對應(yīng)的數(shù)據(jù)為“成功提交的數(shù)據(jù)”。在 WARO 中，如果某次更新操作 w i 在某個副本上失敗，此時該副本的最新的數(shù)據(jù)只有 v i-1 ，由于不滿足在所有 N 個副本上都成功，則 w i 不是一個“成功提交的更新操作”，此時，雖然其他 N-1 個副本上最新的數(shù)據(jù)是 v i ，但 v i 不是一個“成功提交的數(shù)據(jù)”，最新的成功提交的數(shù)據(jù)只是 v i-1 。

• 分析一下 WARO 的可用性。由于更新操作需要在所有的 N 個副本上都成功，更新操作才能成功，所以一旦有一個副本異常，更新操作失敗，更新服務(wù)不可用。對于更新服務(wù)，雖然有 N 個副本，但系統(tǒng)無法容忍任何一個副本異常。另一方面，N 個副本中只要有一個副本正常，系統(tǒng)就可以提供讀服務(wù)。對于讀服務(wù)而言，當(dāng)有 N 個副本時，系統(tǒng)可以容忍 N-1 個副本異常。

• 從上述分析可以發(fā)現(xiàn) WARO 讀服務(wù)的可用性較高，但更新服務(wù)的可用性不高，甚至雖然使用了副本，但更新服務(wù)的可用性等效于沒有副本。

• WARO 犧牲了更新服務(wù)的可用性，最大程度的增強讀服務(wù)的可用性。

3. Quorum 定義

在 Quorum 機制下，當(dāng)某次更新操作 w i 一旦在所有 N 個副本中的 W 個副本上都成功，則就稱該更新操作為“成功提交的更新操作”，稱對應(yīng)的數(shù)據(jù)為“成功提交的數(shù)據(jù)”。令 R>N-W，由于更新操作 w i 僅在 W 個副本上成功，所以在讀取數(shù)據(jù)時，最多需要讀取 R 個副本則一定能讀到 w i 更新后的數(shù)據(jù) v i 。如果某次更新 w i 在 W 個副本上成功，由于 W+R>N，任意 R 個副本組成的集合一定與成功的 W 個副本組成的集合有交集，所以讀取 R 個副本一定能讀到 w i 更新后的數(shù)據(jù) v i 。

例 2.4.1，某系統(tǒng)有 5 個副本，W=3，R=3，最初 5 個副本的數(shù)據(jù)一致，都是 v 1 ， 某次更新操作w 2 在前 3 副本上成功，副本情況變成（v 2 v 2 v 2 v 1 v 1 ）。此時，任意 3 個副本組成的集合中一定包括v 2 。

在上述定義中，令 W=N，R=1，就得到 WARO，即 WARO 是 Quorum 機制的一種特例。

與分析 WARO 相似，分析 Quorum 機制的可用性。限制 Quorum 參數(shù)為 W+R=N+1。由于更新操作需要在 W 個副本上都成功，更新操作才能成功，所以一旦 N-W+1 個副本異常，更新操作始終無法在 W 個副本上成功，更新服務(wù)不可用。另一方面，一旦 N-R+1 個副本異常，則無法保證一定可以讀到與 W 個副本有交集的副本集合，則讀服務(wù)的一致性下降。

Quorum 機制的三個系統(tǒng)參數(shù) N、W、R 控制了系統(tǒng)的可用性，也是系統(tǒng)對用戶的服務(wù)承諾：數(shù)據(jù)最多有 N 個副本，但數(shù)據(jù)更新成功 W 個副本即返回用戶成功。

4. 讀取最新成功提交的數(shù)據(jù)

上節(jié)中，假設(shè)有某種 magic 的機制使得讀取者知道當(dāng)前已提交的數(shù)據(jù)版本號。本節(jié)取消這種假設(shè)，分析在 Quorum 機制下，如何始終讀取成功提交的數(shù)據(jù)，以及如何確定最新的已提交的數(shù)據(jù)。

Quorum 機制只需成功更新 N 個副本中的 W 個，在讀取 R 個副本時，一定可以讀到最新的成功提交的數(shù)據(jù)。但由于有不成功的更新情況存在，僅僅讀取 R 個副本卻不一定能確定哪個版本的數(shù)據(jù)是最新的已提交的數(shù)據(jù)。
例 2.4.3，在 N=5，W=3，R=3 的系統(tǒng)中，某時刻副本最大版本號為 （ v 2 v 2 v 2 v 1 v 1 ）。注意，這里繼續(xù)假設(shè)有 v 2 的副本也有 v 1 ，上述列出的只是最大版本號。此時，最新的成功提交的副本應(yīng)該是 v 2 ，因為從全局看 v 2 已經(jīng)成功更新了 3 個副本。讀取任何 3 個副本，一定能讀到 v 2 。 但僅讀 3 個副本時，有可能讀到 （ v 2 v 1 v 1 ），如圖 2-11（a）。此時，由于 v 2 蘊含 v 1 ， 可知 v 1 是一個成功提交的版本 ， 但卻不能判定 v 2 一定是一個成功提交的版本 。 這是因為，圖 2-11（b）,假設(shè)副本最大版本號為 （ v 2 v 1 v 1 v 1 v 1 ），當(dāng)讀取 3 個副本時也可能讀到 （ v 2 v 1 v 1 ）,此時 v 2 是一個未成功提交的版本。所以在本例中，僅僅讀到 （ v 2 v 1 v 1 ）時，可以肯定的是最新的成功提交的數(shù)據(jù)要么是 v 1 要么是 v 2 ，卻沒辦法確定究竟是哪一個 。

對于一個強一致性系統(tǒng)，應(yīng)該始終讀取返回最新的成功提交的數(shù)據(jù)，在 quorum 機制下，要達(dá)到這一目的需要對讀取條件做進一步加強。

1. 限制提交的更新操作必須嚴(yán)格遞增，即只有在前一個更新操作成功提交后才可以提交后一個更新操作，從而成功提交的數(shù)據(jù)版本號必須是連續(xù)增加的。 2. 讀取 R 個副本，對于 R 個副本中版本號最高的數(shù)據(jù)， 2.1 若已存在 W 個，則該數(shù)據(jù)為最新的成功提交的數(shù)據(jù) 2.2 若存在個數(shù)據(jù)少于 W 個，假設(shè)為 X 個，則繼續(xù)讀取其他副本，直若成功讀取到 W 個該版本的副本，則該數(shù)據(jù)為最新的成功提交的數(shù)據(jù)；如果在所有副本中該數(shù)據(jù)的個數(shù)肯定不滿足 W 個，則 R 中版本號第二大的為最新的成功提交的副本。

例 2.4.4：依舊接例 2.4.3，在讀取到 （ v 2 v 1 v 1 ）時，繼續(xù)讀取剩余的副本，若讀到剩余兩個副本為（v 2 v 2 ）則 v 2 是最新的已提交的副本；若讀到剩余的兩個副本為（v 2 v 1 ）或（v 1 v 1 ）則 v 1 是最新成功提交的版本；若讀取后續(xù)兩個副本有任一超時或失敗，則無法判斷哪個版本是最新的成功提交的版本。

可以看出，在單純使用 Quorum 機制時，若要確定最新的成功提交的版本，最多需要讀取 R+（W-R-1）=N 個副本，當(dāng)出現(xiàn)任一副本異常時，讀最新的成功提交的版本這一功能都有可能不可用。實際工程中，應(yīng)該盡量通過其他技術(shù)手段，回避通過 Quorum 機制讀取最新的成功提交的版本。例如，當(dāng) quorum 機制與 primary-secondary 控制協(xié)議結(jié)合使用時，可以通過讀取 primary 的方式讀取到最新的已提交的數(shù)據(jù)。

5. 基于 Quorum 機制選擇 primary

本節(jié)介紹一種介于 quorum 機制選擇 primary 的技術(shù)。回憶 2.2.2 節(jié)，基本 primary-secondary 協(xié)議中，primary 負(fù)責(zé)進行更新操作的同步工作。現(xiàn)在基本 primary-secondary 協(xié)議中引入 quorum 機制，即 primary 成功更新 W 個副本(含 primary 本身)后向用戶返回成功。

在 primary-secondary 協(xié)議中，當(dāng) primary 異常時，需要選擇出一個新的 primary，之后 secondary 副本與 primary 同步數(shù)據(jù)。通常情況下，選擇新的 primary 的工作是由某一中心節(jié)點完成的，在引入 quorum 機制后，常用的 primary 選擇方式與讀取數(shù)據(jù)的方式類似，即中心節(jié)點讀取 R 個副本，選擇 R 個副本中版本號最高的副本作為新的 primary。新 primary 與至少 W 個副本完成數(shù)據(jù)同步后作為新 的 primary 提供讀寫服務(wù)。首先，R 個副本中版本號最高的副本一定蘊含了最新的成功提交的數(shù)據(jù)。 再者，雖然不能確定最高版本號的數(shù)是一個成功提交的數(shù)據(jù)，但新的 primary 在隨后與 secondary 同步數(shù)據(jù)，使得該版本的副本個數(shù)達(dá)到 W，從而使得該版本的數(shù)據(jù)成為成功提交的數(shù)據(jù)。

例 2.4.5：在 N=5，W=3，R=3 的系統(tǒng)中，某時刻副本最大版本號為 （ v 2 v 2 v 1 v 1 v 1 ），此時 v 1 是系統(tǒng)的最新的成功提交的數(shù)據(jù) ， v 2 是一個處于中間狀態(tài)的未成功提交的數(shù)據(jù)。假設(shè)此刻原 primary副本異常，中心節(jié)點進行 primary 切換工作。這類“中間態(tài)”數(shù)據(jù)究竟作為“臟數(shù)據(jù)”被刪除，還是作為新的數(shù)據(jù)被同步后成為生效的數(shù)據(jù)，完全取決于這個數(shù)據(jù)能否參與新 primary 的選舉。下面分別分析這兩種情況。

• 第一、如圖 2-12，若中心節(jié)點與其中 3 個副本通信成功，讀取到的版本號為（v 1 v 1 v 1 ），則任選一個副本作為primary，新primary以v 1 作為最新的成功提交的版本并與其他副本同步，當(dāng)與第1、第 2 個副本同步數(shù)據(jù)時，由于第 1、第 2 個副本版本號大于 primary，屬于臟數(shù)據(jù)，可以按照 2.2.2.4節(jié)中介紹的處理臟數(shù)據(jù)的方式解決。實踐中，新 primary 也有可能與后兩個副本完成同步后就提供數(shù)據(jù)服務(wù)，隨后自身版本號也更新到 v 2 ， 如果系統(tǒng)不能保證之后的 v 2 與之前的 v 2 完全一樣，則新primary 在與第 1、2 個副本同步數(shù)據(jù)時不但要比較數(shù)據(jù)版本號還需要比較更新操作的具體內(nèi)容是否一樣。

第二、若中心節(jié)點與其他 3 個副本通信成功，讀取到的版本號為（v 2 v 1 v 1 ），則選取版本號為v2 的副本作為新的 primary，之后，一旦新 primary 與其他 2 個副本完成數(shù)據(jù)同步，則符合 v 2 的副本個數(shù)達(dá)到 W 個，成為最新的成功提交的副本，新 primary 可以提供正常的讀寫服務(wù)。

6. 工程投影

• GFS 中的 Quorum。GFS 使用 WARO 機制讀寫副本。GFS 系統(tǒng)不保證異常狀態(tài)時副本的一致性，GFS 系統(tǒng)需要上層應(yīng)用通過 Checksum 等機制自行判斷數(shù)據(jù)是否合法。

• Dynamo 中的 Quorum。Dynamo/Cassandra 是一種去中心化的分布式存儲系統(tǒng)。Dynamo 使用 Quorum 機制來管理副本。用戶可以配置 N、R、W 的參數(shù)，并保證滿足 R+W>N 的 quorum 要求。Dynamo 提出了一種 clock vector 的方法，該方法的思路就是記錄數(shù)據(jù)的版本變化，以類似 MVCC（2.7 ）的方式幫助用戶解決數(shù)據(jù)沖突。所謂 clock vector即記錄了數(shù)據(jù)變化的路徑的向量，為每個更新操作維護分配一個向量元素，記錄數(shù)據(jù)的版本號及主導(dǎo)該次更新的副本名字。

• Zookeeper 中的 Quorum。Zookeeper 使用的 paxos 協(xié)議本身就是利用了 Quorum機制，在 2.8 中有詳細(xì)分析，這里不贅述。當(dāng)利用 paxos 協(xié)議外選出 primary 后，Zookeeper 的更新流量由 primary 節(jié)點控制，每次更新操作，primary 節(jié)點只需更新超過半數(shù)（含自身）的節(jié)點后就返回用戶成功。每次更新操作都會遞增各個節(jié)點的版本號（xzid）。當(dāng) primary 節(jié)點異常，利用 paxos 協(xié)議選舉新的 primary 時，每個節(jié)點都會以自己的版本號發(fā)起 paxos 提議，從而保證了選出的新 primary 是某個超過半數(shù)副本集合中版本號最大的副本。

• Mola*/Armor*中的 Quorum。Mola*和 Armor*系統(tǒng)中所有的副本管理都是基于 Quorum，即數(shù)據(jù)在多數(shù)副本上更新成功則認(rèn)為成功。

• Big Pipe*中的 Quorum。Big Pipe*中的副本管理也是采用了 WARO 機制。

參考：《分布式系統(tǒng)原理介紹》 - 劉杰

總結(jié)

以上是生活随笔為你收集整理的分布式系统原理 之4 Quorum 机制的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。