分布式系統(tǒng)之Quorum機制

春和秋榮 2019-10-13

展開全文

在《分布式系統(tǒng)之中心副本控制協(xié)議（Primary-secondary協(xié)議）》中略微提及到了Quorum，但沒有進行詳細的闡述，這篇文章將帶你走進Quorum.

1. Quorum介紹

首先，先認識發(fā)音和基本含義，英[?kw?:r?m]，美[?kw?r?m, ?kwor-]，n. 法定人數(shù).
在介紹Quorum之前，先對一些概念進行定義：系統(tǒng)中的更新操作定義為 $w_{i}$ ， $i$ 為更新操作單調(diào)遞增序號。每個 $w_{i}$ 執(zhí)行成功后副本數(shù)據(jù)的版本記為 $v_{i}$ . 假設每個副本保存了歷史上所有版本的數(shù)據(jù)。

1.1 Write all read one(WARO)

WARO的意思是：在更新時寫所有副本，只有在所有副本中更新成功才算成功，保證了所有副本中數(shù)據(jù)的一致性，讀取時可以讀任意副本數(shù)據(jù)。

很顯然，這種機制在工程實踐中并沒有那么好的可用性，為什么呢？

更新操作需要在N個節(jié)點上都更新成功才算真正成功，只要存在一個節(jié)點異常，則更新服務不可用。更新操作無法容忍任一節(jié)點的異常。
但是WARO讀服務卻有著較高的容錯能力，可以容忍N-1個副本異常。讀服務有較高的可用性。

WARO機制同時需要原服務器記錄數(shù)據(jù)版本信息，從而達到數(shù)據(jù)的強一致性。WARO犧牲了更新服務的可用性，最大程度地增強了讀服務的可用性。

1.2 Quorum機制

對WARO條件進行松弛，對讀寫服務可用性做折中。

Quorum機制：當更新操作 $w_{i}$ 在N個節(jié)點中的W個節(jié)點上更新成功，稱之為“成功提交的更新操作”。由于更新操作 $w_{i}$ 在W個節(jié)點上更新成功，所以在讀數(shù)據(jù)時，令 $R > N - W$ ，最多讀取R個節(jié)點副本一定能讀到更新操作 $w_{i}$ 更新后的數(shù)據(jù) $v_{i}$ 。

說白了，在更新操作 $w_{i}$ 成功提交后，R+W>N，那么讀取的R個節(jié)點一定會與更新成功的W個節(jié)點有交集。此時你是否想到了鴿巢原理。

當W=N,R=1時，就可以得到WARO機制，所以WARO是Quorum的特例。

那WARO的可用性如何呢？

限制Quorum參數(shù)W+R=N+1.
更新操作在W個節(jié)點上更新成功，當N-W+1個節(jié)點異常時，更新操作不可用。
當N-R+1個節(jié)點異常，無法保證讀取內(nèi)容與W個副本有交集，讀服務一致性降低。

注意：僅僅依賴Quorum機制無法保證強一致性。因為僅有Quorum機制時無法確定最新已成功提交的數(shù)據(jù)。那如何能夠讀到最新提交數(shù)據(jù)呢？

1.3 增強Quorum機制（讀取最新成功提交數(shù)據(jù)）

為了能夠保證系統(tǒng)的強一致性，系統(tǒng)應該返回最新成功提交數(shù)據(jù)，需要對Quorum機制進行條件增強。

1. 更新操作嚴格遞增（數(shù)據(jù)版本號嚴格遞增），只有前一個更新操作成功提交才可以允許后一個更新操作提交
2. 讀取R個節(jié)點，取得最高版本號數(shù)據(jù)
    2.1. 在讀取的R個節(jié)點中，存在W個節(jié)點有最高版本數(shù)據(jù)，則該數(shù)據(jù)為最新成功提交的數(shù)據(jù)
    2.2. 若存在小于W個節(jié)點有最高版本數(shù)據(jù)，則繼續(xù)讀取剩余節(jié)點，直至讀到W個節(jié)點存在最高版本數(shù)據(jù)為止；
         如果所有節(jié)點讀取完畢不滿足W個，則版本號第二大的數(shù)據(jù)為最新成功提交的數(shù)據(jù)（此時可能處于更新提交的中間態(tài)）

從上述增強Quorum機制可得，若需確定最新成功提交的數(shù)據(jù)，最多需要讀取N個節(jié)點。

當出現(xiàn)任一節(jié)點異常時，可能無法讀到最新成功提交的數(shù)據(jù)。

例如：共有5個節(jié)點，W=3，R=3，已讀取3個節(jié)點數(shù)據(jù)版本為（ $v_{2}, v_{1}, v_{1}$ ）。
1. 若剩余2個節(jié)點讀到（ $v_{2} ， v_{2}$ ），則 $v_{2}$ 為最新成功提交的數(shù)據(jù)版本；
2. 若剩余2個讀到( $v_{2} ， v_{1}$ )或（ $v_{1} ， v_{1}$ ），則 $v_{1}$ 為最新成功提交的數(shù)據(jù)版本；
3. 若剩余2個節(jié)點中，讀取到1個節(jié)點數(shù)據(jù)版本為（ $v_{2}$ ），另一個節(jié)點異常，則無法判斷哪個版本是最新成功提交的數(shù)據(jù)。

在工程實踐中，節(jié)點異常是經(jīng)常會出現(xiàn)的情況，需要盡量回避通過Quorum機制來讀取最新成功提交數(shù)據(jù)。

2. 基于Quorum機制選擇primary

當Quorum機制與Primary-Secondary協(xié)議結合時，可以通過讀取primary的方式讀取最新成功提交的數(shù)據(jù)。

在primary-secondary協(xié)議中，primary負責進行更新同步操作。在primary-secondary協(xié)議中引入Quorum機制，primary成功更新W個節(jié)點（含本身）后向用戶返回成功。

讀取數(shù)據(jù)時按照一致性要求不同可有不同的做法：

達到強一致性，直接讀取primary中的數(shù)據(jù)，也可通過增強Quorum機制進行讀取最新成功提交數(shù)據(jù)

達到會話一致性，根據(jù)已讀版本號在副本上進行選擇性讀?。ㄟx擇版本號 > 已讀版本號）

達到弱一致性，選擇任意版本讀取

當primary節(jié)點異常時，需要選擇一個新的節(jié)點作為primary，然后secondary與primary進行同步。選擇新的primary是由一個中心節(jié)點完成的，此時引入Quorum機制，新primary的選擇方式類似于讀取數(shù)據(jù)的方式，中心節(jié)點讀取R個節(jié)點副本，選擇R個節(jié)點副本中版本號最高的作為新的primary（R個節(jié)點副本中一定存在最新成功提交的數(shù)據(jù)）。新primary與至少W個副本完成數(shù)據(jù)同步后作為新的primary提供讀寫服務。

需要進一步說明的是，讀取R個節(jié)點副本能夠獲取到當前最新的數(shù)據(jù)，但并不一定是一個成功提交的數(shù)據(jù)。這時候會出現(xiàn)兩種情況（假設系統(tǒng)版本情況為（ $v_{2}, v_{2}, v_{1}, v_{1}, v_{1}$ ），W=3，R=3）：
1. R個節(jié)點全部讀到成功提交的數(shù)據(jù)（ $v_{1}, v_{1}, v_{1}$ ），此時產(chǎn)生的 $v_{2}$ 為臟數(shù)據(jù)，可以有多種處理方式解決臟數(shù)據(jù)，如簡單粗暴的刪除。
2. R個節(jié)點讀到的最新數(shù)據(jù)不是成功提交的數(shù)據(jù)（ $v_{2}, v_{1}, v_{1}$ ）,此時新primary副本的最新數(shù)據(jù)為 $v_{2}$ ，雖然 $v_{2}$ 不是一個成功提交的數(shù)據(jù)，但是在隨后primary與secondary的數(shù)據(jù)同步后，使 $v_{2}$ 版本數(shù)據(jù)達到W個，便能夠使得該版本數(shù)據(jù)成為一個最新成功提交的數(shù)據(jù)。