Quorum NWR：通過仲裁實現數據一致性

楔子

數據同步相關的協議有 Paxos, Raft, ZAB 等等（我們以後會聊），但這些協議都有一個相同之處，就是要求集羣當中要有一個領導者。客戶端只向領導者發送寫請求，領導者再將數據同步給追隨者。領導者決定寫入的順序，而追隨者則按相同順序來同步領導者的寫入。

但也有一些數據存儲系統採用了不同的方法，其放棄了領導者的概念，並允許任何副本都能接受來自客戶端的寫入。最早的一些系統是無領導者的（leaderless），但是在關係數據庫主導的時代，這個想法幾乎已被忘卻。

不過在亞馬遜將其用於內部的 Dynamo 系統之後，它再一次成爲數據存儲的一種時尚架構。Riak, Cassandra 和 Voldemort 都是由 Dynamo 啓發的無領導複製模型的開源數據存儲，所以這類數據庫也被稱爲 Dynamo 風格。

但是問題來了，在無領導者的實現中，客戶端將寫入發送到任何一個節點都可以，那麼該節點的數據要如何同步給其它節點呢？以及客戶端在讀取的時候讀取到舊數據該怎麼辦呢？

此時就需要 Quorum NWR 算法，客戶端寫數據不止寫入一個節點，而是寫入多個節點；同理當客戶端讀取的時候，也會讀取多個節點。關於這背後的原理，我們來慢慢講解。

仲裁讀

假設你有一個帶有三個副本的分佈式系統，而其中一個副本目前不可用，如果是基於領導者的複製，那麼可能要執行故障切換。但在無領導者配置中，故障切換不存在。

比如下圖顯示的那樣：客戶端（用戶 satori）將寫入並行發送到所有的副本中，並且兩個可用副本接受寫入，但是不可用副本錯過了它。所以現在的結果就是，三個副本中有兩個寫入成功（返回了響應），而此時客戶端整體寫入成功，因此客戶簡單地忽略了其中一個副本錯過了寫入的事實。

然後客戶端開始讀取，顯然 Replica 3 返回的是之前的舊數據，因爲在寫入新數據的時候它下線了。所以爲了解決這個問題，客戶端在讀數據的時候不僅僅只讀一個副本，正如寫請求會並行地寫入多個副本，讀請求也會從多個副本讀取。這樣就會獲取多個響應，然後通過版本號選擇最新的值。

比如當前從 Replica 3 中讀取到的雖然是舊值，但 1 和 2 返回的是新值，基於版本號可以選擇出最新的那一個。

所以原理還是不難理解的，就是每次寫的時候，會寫入多個副本；讀的時候，也會讀多個副本，基於版本號選擇最新的那一個。這樣也能保證客戶端看到的是新數據，從而實現數據一致性。

但這就產生了一個問題，客戶端每次寫的時候到底要寫多少個副本，讀的時候又要讀多少個副本呢？我們一直說多個副本，顯然這是很模糊的，因爲說不清楚究竟多少才叫多。

讀取的法定人數

還是上面那張圖，三個副本有兩個寫入成功，我們就認爲客戶端寫入成功了。但如果只有一個副本寫入成功了呢？

首先當成功寫入兩個時，這意味着至多有一個副本可能是陳舊的，因此在讀取的時候至少要讀取兩個副本，纔可以確保至少有一個是最新的。但如果只成功寫入一個，那麼在讀取的時候就要讀三個副本。

注：這裏我們一個節點上只有一個副本

更一般地說，如果有 n 個節點，寫入的時候至少成功寫入 w 個節點才能被認爲是成功，並且讀取的時候至少讀取 r 個節點。那麼只要 w + r > n，我們在讀取時就能獲得最新的值，因爲 r 個讀取中至少有一個節點是最新的。

比如 3 個節點，成功寫入了 2 個，那麼讀的時候至少要讀 2 個，才能拿到最新的值；如果只成功寫入了 1 個，那麼就至少要讀 3 個，才能拿到最新的值。同理 5 個節點，成功寫入 2 個，還剩下 3 個沒寫，那麼讀的時候至少要讀 4 個，才能保證拿到最新的值。

這些 r 值和 w 值就被稱爲讀寫的法定人數（quorum），你可以認爲，r 和 w 是有效讀寫所需的最低票數。而在大部分使用 Quorum 的系統中，r, w, n 都是可配置的，通過使 r + w > n 便可實現強一致性。

比如你開發了一個有 5 個節點的分佈式系統，一開始的要求是實現最終一致性，用戶寫完數據之後不一定會立刻看到變化，經過一段時間的數據同步之後，這個變化纔會看到。但最新需求變了，讓你支持強一致性，用戶一旦寫完數據，就要立刻看到變化。

此時便可以通過 Quorum 自定義一致性，既然要求強一致性，那麼只要保證 r + w 大於 n 即可。這裏 n 是 5，那麼就讓 r 和 w 都爲 3。

因爲 𝑤 + 𝑟 > 𝑛，讀取 r 個副本，至少有一個副本必然包含了最近的成功寫入。但是問題來了，剩餘的兩個節點的數據該怎麼辦呢？雖然目前可以實現強一致性，但節點之間的數據還是不一致的。

在 Dynamo 風格的數據存儲中經常使用兩種機制：

1）讀修復（Read repair）

當客戶端並行讀取多個節點時，它可以檢測到所有陳舊的響應。如果發現某個節點的值是舊值，那麼會將新值寫回。因此這種方法適用於頻繁讀取的值。

2）反熵過程（Anti-entropy process）

關於反熵我們在介紹 gossip 的時候已經說過了，數據存儲系統的後臺進程會不斷查找副本之間的數據差異（隨機挑選兩個副本），並將缺少的數據從一個副本複製到另一個副本。與基於領導者的複製不同，反熵不會以任何特定的順序複製寫入（但我們在設計的時候可以適當調整），並且在複製數據之前可能會有顯著的延遲。

r 和 w 應該怎麼設置

如果你有 n 個副本，並且使得 𝑤+𝑟 > 𝑛，那麼讀取的節點中至少有一個具有最新值的節點，因爲寫的節點集合和讀的節點集合一定會有重疊。但當滿足 𝑤+𝑟 > 𝑛 時，有很多種組合，那麼 r 和 w 到底應該怎麼設置呢？

r 和 w 的設置方式，取決於我們想要優化哪一方面的性能。如果 w = n，那麼每次寫數據時所有節點都要寫，然後讀的時候只要讀一個就行，顯然這是爲了優化讀性能；如果 r = n，那麼每次讀數據時要讀所有的節點，然後寫的時候只需要寫一個就行，顯然這是爲了優化寫性能；如果 r 和 w 接近，等於 (n + 1) / 2，那麼容錯能力比較好，能容忍 (n - 1) / 2 個點發生故障。

如果讀寫頻率相差不大的話，那麼建議將 r 和 w 設置爲第三種，總之只要保證讀寫使用的節點做交集之後至少包含一個節點即可。因此法定人數的配置是很自由的，這使得分佈式算法的設計有一定的靈活性。

所以 Quorum NWR 是非常實用的一個算法，能有效彌補 AP 型系統缺乏強一致性的痛點，給業務提供了按需選擇一致性級別的靈活度。

當然啦，我們這裏是讓 r + w > n，爲了實現強一致性。但也可以讓 r + w <= n，實現最終一致性，在這種情況下，由於法定條件不滿足，讀取的時候可能會讀不到包含最新值的節點。然後經過一段時間的同步，纔會讀到新數據。

另外 r+w <= n 這種配置允許更低的延遲和更高的可用性，比如網絡中斷，並且許多副本變得無法訪問，可以繼續處理讀取和寫入的機會更大（因爲 w 和 r 更小）。只有當可達副本的數量低於 w 或 r 時，系統才分別變得不可用於寫入或讀取。

本文參考自分佈式神書《DDIA》

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