分佈式系統理論之 Quorum 機制

一 Quorum 機制介紹

在分佈式系統中有個 CAP 理論，對於 P（分區容忍性）而言，是實際存在 從而無法避免的。因爲，分佈系統中的處理不是在本機，而是網絡中的許多機器相互通信，故網絡分區、網絡通信故障問題無法避免。因此，只能儘量地在 C 和 A 之間尋求平衡。對於數據存儲而言，爲了提高可用性（Availability），採用了副本備份，比如對於 HDFS，默認每塊數據存三份。某數據塊所在的機器宕機了，就去該數據塊副本所在的機器上讀取（從這可以看出，數據分佈方式是按 “數據塊” 爲單位分佈的）

但是，問題來了，當需要修改數據時，就需要更新所有的副本數據，這樣才能保證數據的一致性（Consistency）。因此，就需要在 C(Consistency) 和 A(Availability) 之間權衡。

而 Quorum 機制，就是這樣的一種權衡機制，一種將 “讀寫轉化” 的模型。在介紹 Quorum 之前，先看一個極端的情況：WARO 機制

 WARO(Write All Read one) 是一種簡單的副本控制協議，當 Client 請求向某副本寫數據時 (更新數據)，只有當所有的副本都更新成功之後，這次寫操作纔算成功，否則視爲失敗。

從這裏可以看出兩點：①寫操作很脆弱，因爲只要有一個副本更新失敗，此次寫操作就視爲失敗了。②讀操作很簡單，因爲，所有的副本更新成功，才視爲更新成功，從而保證所有的副本一致。這樣，只需要讀任何一個副本上的數據即可。假設有 N 個副本，N-1 個都宕機了，剩下的那個副本仍能提供讀服務；但是隻要有一個副本宕機了，寫服務就不會成功。

 WARO 犧牲了更新服務的可用性，最大程度地增強了讀服務的可用性。而 Quorum 就是更新服務和讀服務之間進行一個折衷。

Quorum 機制是 “抽屜原理” 的一個應用。定義如下：假設有 N 個副本，更新操作 wi 在 W 個副本中更新成功之後，才認爲此次更新操作 wi 成功。稱成功提交的更新操作對應的數據爲：“成功提交的數據”。對於讀操作而言，至少需要讀 R 個副本才能讀到此次更新的數據。**其中，W+R>N ，即 W 和 R 有重疊。**一般，W+R=N+1

假設系統中有 5 個副本，W=3，R=3。初始時數據爲 (V1，V1，V1，V1，V1）-- 成功提交的版本號爲 1

當某次更新操作在 3 個副本上成功後，就認爲此次更新操作成功。數據變成：(V2，V2，V2，V1，V1）-- 成功提交後，版本號變成 2

因此，最多隻需要讀 3 個副本，一定能夠讀到 V2(此次更新成功的數據)。而在後臺，可對剩餘的 V1 同步到 V2，而不需要讓 Client 知道。

二、Quorum 機制分析

①Quorum 機制無法保證強一致性

所謂強一致性就是：任何時刻任何用戶或節點都可以讀到最近一次成功提交的副本數據。強一致性是程度最高的一致性要求，也是實踐中最難以實現的一致性。

 因爲，僅僅通過 Quorum 機制無法確定最新已經成功提交的版本號。

比如，上面的 V2 成功提交後（已經寫入 W=3 份），儘管讀取 3 個副本時一定能讀到 V2，如果剛好讀到的是 (V2，V2，V2），則此次讀取的數據是最新成功提交的數據，因爲 W=3，而此時剛好讀到了 3 份 V2。如果讀到的是（V2，V1，V1），則無法確定是一個成功提交的版本，還需要繼續再讀，直到讀到 V2 的達到 3 份爲止，這時才能確定 V2 就是已經成功提交的最新的數據。

1）如何讀取最新的數據？--- 在已經知道最近成功提交的數據版本號的前提下，最多讀 R 個副本就可以讀到最新的數據了。

2）如何確定 最高版本號 的數據是一個成功提交的數據？--- 繼續讀其他的副本，直到讀到的 最高版本號副本 出現了 W 次。

②基於 Quorum 機制選擇 primary

中心節點 (服務器) 讀取 R 個副本，選擇 R 個副本中版本號最高的副本作爲新的 primary。

新選出的 primary 不能立即提供服務，還需要與至少與 W 個副本_完成同步_後，才能提供服務 --- 爲了保證 Quorum 機制的規則：W+R>N

至於如何處理同步過程中衝突的數據，則需要視情況而定。

 比如，(V2，V2，V1，V1，V1），R=3，如果讀取的 3 個副本是：(V1，V1，V1) 則高版本的 V2 需要丟棄。

如果讀取的 3 個副本是（V2，V1，V1），則低版本的 V1 需要同步到 V2

三、Quorum 機制應用實例

HDFS 高可用性實現

 HDFS 的運行依賴於 NameNode，如果 NameNode 掛了，那麼整個 HDFS 就用不了了，因此就存在單點故障 (single point of failure)；其次，如果需要升級或者維護停止 NameNode，整個 HDFS 也用不了。爲了解決這個問題，採用了 QJM 機制(Quorum Journal Manager) 實現 HDFS 的 HA（High Availability）。注意，一開始採用的 “共享存儲” 機制，關於共享存儲機制的不足，可參考：（還提到了 QJM 的優點）

In a typical HA cluster, two separate machines are configured as NameNodes.
At any point in time, exactly one of the NameNodes is in an Active state, and the other is in a Standby state. 
The Active NameNode is responsible for all client operations in the cluster, while the Standby is simply acting as a slave, 
maintaining enough state to provide a fast failover if necessary.

爲了實現 HA，需要兩臺 NameNode 機器，一臺是 Active NameNode，負責 Client 請求。另一臺是 StandBy NameNode，負責與 Active NameNode 同步數據，從而快速 failover。

那麼，這裏就有個問題，StandBy NameNode 是如何同步 Active NameNode 上的數據的呢？主要同步是哪些數據呢？

數據同步就用到了 Quorum 機制。同步的數據 主要是 EditLog。

In order for the Standby node to keep its state synchronized with the Active node, 
both nodes communicate with a group of separate daemons called “JournalNodes” (JNs).

數據同步用到了一個第三方” 集羣 “：Journal Nodes。Active NameNode 和 StandBy NameNode 都與 JournalNodes 通信，從而實現同步。

''''''''''''''''''''''''''''''''''

每次 NameNode 寫 EditLog 的時候，除了向本地磁盤寫入 EditLog 之外，也會並行地向 JournalNode 集羣之中的每一個 JournalNode 發送寫請求，只要大多數 (majority) 的 JournalNode 節點返回成功就認爲向 JournalNode 集羣寫入 EditLog 成功。如果有 2N+1 臺 JournalNode，那麼根據大多數的原則，最多可以容忍有 N 臺 JournalNode 節點掛掉。

這就是：Quorum 機制。每次寫入 JournalNode 的機器數目達到大多數 (W) 時，就認爲本次寫操作成功了。

'''''''''''''''''''''''''''''''''

這樣，每次對 Active NameNode 中的元數據進行修改時，都會將該修改寫入 JournalNode 集羣的大多數機器中，才認爲此次修改成功。

當 Active NameNode 宕機時，StandBy NameNode 向 JournalNode 同步 EditLog，從而保證了 HA。

Active NameNode 向 JournalNode 集羣提交 EditLog 是同步的
但 Standby NameNode 採用的是定時從 JournalNode 集羣上同步 EditLog 的方式，那麼 Standby NameNode 內存中文件系統鏡像有很大的可能是落後於 Active NameNode 的，
所以 Standby NameNode 在轉換爲 Active NameNode 的時候需要把落後的 EditLog 補上來。

具體的同步過程可參考：Hadoop NameNode 高可用 (High Availability) 實現解析

In order to provide a fast failover, it is also necessary that the Standby node have up-to-date information
regarding the location of blocks in the cluster. In order to achieve this, the DataNodes are configured with the location of both NameNodes, 
and send block location information and heartbeats to both.

此外，爲了實現快速 failover，StandBy NameNode 需要實時地與各個 DataNode 通信以獲得每個數據塊的地址信息。爲咐要這樣？

因爲：每個數據塊的地址信息不屬於 “元信息”，並沒有保存在 FsImage、CheckPoint...，這是因爲地址信息變化比較大。比如說，一臺 DataNode 下線了，其上面的數據塊地址信息就全無效了，而且爲了達到指定的數據塊 “複製因子”，還需要在其他機器上覆制該數據塊。

而快速 failover，是指 Active NameNode 宕機後，StandBy NameNode 立即就能提供服務。因此，DataNode 也需要實時向 StandBy NameNode 發送 block report

另外，還有手動 failover 和 自動 failover，自動 failover 需要 Zookeeper 的支持，具體可參考官網：HDFS High Availability Using the Quorum Journal Manager

如何避免 “Split Brain”(腦裂) 問題？

Split Brain 是指在同一時刻有兩個認爲自己處於 Active 狀態的 NameNode。

when a NameNode sends any message (or remote procedure call) to a JournalNode, it includes its epoch number as part of the request. 
Whenever the JournalNode receives such a message, it compares the epoch number against a locally stored value called the promised epoch. 
If the request is coming from a newer epoch, then it records that new epoch as its promised epoch.
 If instead the request is coming from an older epoch, then it rejects the request. This simple policy avoids split-brain

簡單地理解如下：每個 NameNode 與 JournalNodes 通信時，需要帶一個 epoch numbers(epoch numbers 是唯一的且只增不減)。而每個 JournalNode 都有一個本地的 promised epoch。擁有值大的 epoch numbers 的 NameNode 會使得 JournalNode 提升自己的 promised epoch，從而佔大多數，而 epoch numbers 較小的那個 NameNode 就成了少數派 (Paxos 協議思想)。

從而 epoch number 值大的 NameNode 纔是真正的 Active NameNode，擁有寫 JournalNode 的權限。注意：（任何時刻只允許一個 NameNode 擁有寫 JournalNode 權限）

when using the Quorum Journal Manager, only one NameNode will ever be allowed to write to the JournalNodes,
so there is no potential for corrupting the file system metadata from a split-brain scenario.

具體實現可參考：（還提到了 QJM 的優點）

四、參考資料

維基百科 Quorum

https://issues.apache.org/jira/secure/attachment/12547598/qjournal-design.pdf

Hadoop2.6.0 學習筆記（九）SPOF 解決方案 Quorum 機制

HDFS HA 與 QJM[官網整理]

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