Chapter 5 Replication :無主複製

本章到前面所討論的複製方法:

1. 單主複製(Single Leader replication)
2. 多主複製(Multi Leader replication) 概念都是: 客戶端向一個主庫(Leader)發送寫請求，而資料庫系統負責寫入複製到其他副本。 主庫(Leader)決定寫入的順序，而從庫(Follower)按相同順序應用主庫(Leader)的寫入。

接下來會討論的複製方法: 3. 無主複製(Leaderless replication): 放棄主庫(Leader)的概念，並允許任何副本(Replica)直接接受來自用戶端的寫入。

舉例: 亞馬遜將其用於其內部的Dynamo系統, Riak，Cassandra和Voldemort是由Dynamo啟發的無領導複製模型的開源數據存儲, 這類數據庫被稱為Dynamo風格

無領導者的實現中又分為兩種:

1. 用戶端直接將寫入發送到到幾個節點(Replica)中
2. 一個協調者（coordinator）節點代表用戶端進行寫入。 但與主庫資料庫不同，協調者不執行特定的寫入順序。

當節點故障時寫入資料庫

情境: 假設你有一個帶有三個節點的資料庫，而其中一個節點(Replica)目前不可用，或許正在重新啟動以安裝系統更新

1. 有主複製:如果要繼續處理寫入，則可能需要執行故障切換, 參考前面的:Leader failure: Failover
2. 無主複製:不存在故障切换

用戶端（用戶1234）並行發送寫入到所有三個節點，並且兩個可用節點(Replica)接受寫入，但是不可用節點(Replica)錯過了它。 假設三個副本中的兩個承認寫入是足夠的：在使用者1234已經收到兩個確定的回應之后，我們認為寫入成功。 客戶簡單地忽略了其中一個副本錯過了寫入的事實

發生問題: 讀取到過時的值 當不可用的節點重新連線，客戶端開始讀取它。節點關閉時發生的任何寫入都從該節點丟失。 因此，如果您從該節點讀取數據，則可能會將陳舊（過時）值視為回應。

解決方法: 檢測併發寫入 當一個用戶端從資料庫中讀取數據時，它不僅僅發送它的請求到一個節點(Replica)：讀請求也被並行地發送到多個節點(Replica)。客戶可能會從不同的節點(Replica)獲得不同的回應。 即來自一個節點的最新值和來自另一個節點的陳舊值。版本號用於確定哪個值更新(檢測併發寫入)

檢測併發寫入(Detect concurrent writes)

Dynamo風格的資料庫允許多個客戶端同時寫入相同的Key,在讀修復或帶提示的接力期間也可能會產生衝突 由於可變的 '網路延遲' 和 '部分故障'，事件可能在不同的節點以不同的順序到達。

例如，圖5-12顯示了兩個客戶機A和B同時寫入三節點數據儲存區中的鍵X：

• 節點 1 接收來自 A 的寫入，但由於暫時中斷，從不接收來自 B 的寫入。
• 節點 2 首先接收來自 A 的寫入，然後接收來自 B 的寫入。
• 節點 3 首先接收來自 B 的寫入，然後從 A 寫入。

發生問題: 節點永久地不一致 如果每個節點只要接收到來自用戶端的寫入請求就簡單地覆蓋了某個鍵的值，那麼節點就會永久地不一致，如圖5-12中的最終獲取請求所示：節點2認為 X 的最終值是 B，而其他節點認為值是 A

解決方法:

最後寫入勝利（丟棄併發寫入,Discard concurrent writes） - 時間戳

實現最終融合的一種方法是聲明每個副本只需要存儲最"最近"的值，並允許“更舊”的值被覆蓋和拋棄。

那麼如何實現 "最近" 呢? 例如，可以為每個寫入附加一個時間戳，挑選最"最近"的最大時間戳，並丟棄具有較早時間戳的任何寫入。這種衝突解決演算法被稱為最後寫入勝利（LWW， last write wins），是Cassandra唯一支持的衝突解決方法，也是Riak中的一個可選特徵。

缺點: 付出'持久性'代價 並可能丟失值: LWW實現了最終收斂的目標，但以持久性為代價：如果同一個Key有多個併發寫入，即使它們都被報告為用戶端成功（因為它們被寫入 w 個副本），但只有一個寫入將存活，而其他寫入將被靜默丟棄。 因此，LWW甚至可能會刪除不是併發的寫入, 將在第八章討論到。

與LWW一起使用資料庫的唯一安全方法是確保一個鍵只寫入一次，然後視為不可變，從而避免對同一個金鑰進行併發更新(Concurrent updates)。 例如，Cassandra推薦使用的方法是使用UUID作為鍵，從而為每個寫操作提供一個唯一的鍵。

happens-before 和併發

我們如何判斷兩個操作是否是併發的？

定義併發性，確切的時間並不重要：如果兩個操作都意識不到對方的存在，就稱這兩個操作併發(Concurrent),但現實中是很難判斷兩個事件是否同時發生的, 詳細會在第八章說明。

例子： 圖5-9中，兩個寫入不是併發的：A的插入發生在B的增量之前，因為B遞增的值是A插入的值。 換句話說，B的操作建立在A的操作上，所以B的操作必須有後來發生。 我們也可以說B是因果依賴（causally dependent）於A

圖5-12中，的兩個寫入是併發的：當每個客戶端啟動操作時，它不知道另一個用戶端也正在執行操作同樣的Key。 因此，操作之間不存在因果關係

擷取 happens-before 先後關係 -版本號

下面簡單演示一個只有一個副本的數據庫, 之後便可以概括具有多個副本的無領導數據庫

圖5-13，顯示了兩個用戶端同時向同一購物車添加項目

圖5-14 這個例子中，客戶端永遠不會完全掌握伺服器上的數據，因為總是有另一個操作同時進行。 但是，舊版本的值最終會被覆蓋，並且不會丟失任何寫入。

伺服器可以通過查看版本號來確定兩個操作是否是併發的,該演算法的工作原理如下：

• 伺服器為每個鍵保留一個版本號，每次寫入鍵時都增加版本號，並將新版本號與寫入的值一起存儲。
• 當用戶端讀取鍵時，伺服器將返回所有未覆蓋的值以及最新的版本號。 用戶端在寫入前必須讀取。
• 用戶端寫入鍵時，必須包含之前讀取的版本號，並且必須將之前讀取的所有值合併在一起。 （來自寫入請求的回應可以像讀取一樣，返回所有當前值，這使得我們可以像購物車示例那樣連接多個寫入。 ）
• 當伺服器接收到具有特定版本號的寫入時，它可以覆蓋該版本號或更低版本的所有值（因為它知道它們已經被合併到新的值中），但是它必須保持所有值更高版本號（因為這些值與傳入的寫入同時發生）。

當一個寫入包含前一次讀取的版本號時，它會告訴我們寫入的是哪一種狀態。 如果在不包含版本號的情況下進行寫操作，則與所有其他寫操作併發，因此它不會覆蓋任何內容 —— 只會在隨後的讀取中作為其中一個值返回。

合併同時寫入的值(Merge values that are written at the same time) - 墓碑（tombstone）

這種演算法:

優點:確保沒有數據被無聲地丟棄 缺點: 用戶端需要做一些額外的工作：如果多個操作併發發生，則客戶端必須通過合併併發寫入的值來擦屁股。 Riak稱這些併發值兄弟（siblings）。

合併兄弟值（siblings），本質上是與多領導者複製中的衝突解決相同的問題（參閱"處理寫入衝突"），簡單的解決方法就是：最後寫入勝利（LWW， last write wins），但也可能丟失值。

發生問題: 如果他們從手推車中"刪除"東西，而不是僅僅添加東西，那麼把合併兄弟(siblings)可能不會產生正確的結果：如果你合併了兩個兄弟手推車，並且只在其中一個兄弟值裡刪掉了它，那麼被刪除的專案會重新出現在合併兄弟集(siblings)中

解決方法: 系統必須留下一個具有合適版本號的標記，以指示合併兄弟(siblings)時該項目已被刪除。 這種刪除標記被稱為墓碑（tombstone）

但在代碼中合併兄弟(siblings)是複雜且容易出錯的，所以有一些數據結構被設計出來用於自動執行這種合併。例如，Riak的數據類型支援使用稱為CRDT的數據結構家族可以以合理的方式自動合併兄弟，包括保留刪除。

版本向量

圖5-13中的示例只使用一個副本。 當有多個副本但沒有領導者時，演算法如何修改？

當多個副本併發接受寫入時，

1. 每個鍵使用版本號之外
2. 每個副本中使用版本號。 每個副本在處理寫入時增加自己的版本號，並且跟蹤從其他副本中看到的版本號。 這個資訊指出了要覆蓋哪些值，以及保留哪些值作為兄弟(siblings)。

所有副本的版本號集合稱為版本向量（version vector）。 這個想法的可能是在Riak 2.0中使用的分散版本向量（dotted version vector）

當讀取值時，版本向量會從資料庫副本發送到客戶端，並且隨後寫入值時需要將其發送回資料庫。 （Riak將版本向量編碼為一個字元串，它稱為因果上下文（causal context））。 版本向量允許資料庫區分覆蓋寫入和併發寫入。

比較表:

Method	Pros	Cons	特徵
最終寫入勝利LWW		付出'持久性'代價,當發生操作併發(Concurrent)時,可能丟失值	時間戳
擷取'happens-before'先後關係	舊版本的值最終會被覆蓋，並且不會丟失任何寫入		版本號
合併同時寫入的值	確保沒有數據被無聲地丟棄	多個操作併發發生, 客戶端必須通過合併併發寫入的值來擦屁	版本號+墓碑

讀修復和反熵(Read repair and Anti-entropy process)

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

1. Read repair: 當用戶端並行讀取多個節點時，它可以檢測到任何陳舊的回應。

在圖5-10中，使用者2345獲得了來自Replica 3的版本6值和來自Replica1和2的版本7值。 客戶端發現Replica3具有陳舊值，並將新值寫回Replica。

適用於: 頻繁閱讀的值

2. Anti-entropy process: 不斷查找副本之間的數據差異，並將任何缺少的數據從一個副本複製到另一個副本。

與基於領導者的複製中的複製日誌不同，此反熵過程不會以任何特定的順序複製寫入，並且在複製數據之前可能會有顯著的延遲。

並不是所有的系統都實現了這兩個; 例如，Voldemort目前沒有反熵過程。 如果沒有反熵過程，某些副本中很少讀取的值可能會丟失，從而'降低了持久性'，因為只有在應用程式讀取值時才執行讀修復。

讀寫的法定人數

在圖5-10的示例中，n 代表副本數，w 代表寫入成功需要的節點數，r 代表讀取需要查詢的節點數。 （在我們的例子中，$n = 3，w = 2，r = 2$）。 只要$w + r>n$，我們期望在讀取時獲得最新的值，因為r個讀取中至少有一個節點是最新的。

遵循這些r值，w值的讀寫稱為法定人數（quorum） 的讀和寫。你可以認為，r和w是有效讀寫所需的最低票數。有時候這種法定人數被稱為嚴格的法定人數，相對「鬆散的法定人數」而言(參閱"鬆散法定人數與帶提示的接力")

在Dynamo風格的資料庫中，參數n，w和r通常是可配置的。 常見的選擇是使n為奇數（通常為3或5）並設置 $w = r =（n + 1）/ 2$（向上取整）。 但是可以根據需要更改數字。 例如，設置$w = n$和$r = 1$ 優點:寫入很少且讀取次數較多的工作負載，讀取速度更快， 缺點:具有只有一個失敗節點導致所有資料庫寫入失敗

仲裁條件$w + r> n$允許系統容忍不可用的節點，如下所示：

• 如果$w <n$，如果節點不可用，我們仍然可以處理寫入。
• 如果$r <n$，如果節點不可用，我們仍然可以處理讀取。
• 對於$n = 3，w = 2，r = 2$，我們可以容忍一個不可用的節點。
• 對於$n = 5，w = 3，r = 3$，我們可以容忍兩個不可用的節點。 這個案例如圖5-11所示。
• 通常，讀取和寫入操作始終並行發送到所有n個副本。 w和r決定我們等待多少個節點需要報告成功。如果少於所需的w或r節點可用，則寫入或讀取將返回錯誤。

仲裁一致性的侷限性

即使在$w + r> n$的情況下，也可能存在返回陳舊值的邊緣情況。 這取決於實現，但可能的情況包括：

• 如果使用鬆散的法定人數（見“鬆散法定人數與帶提示的接力”），w個寫入和r個讀取落在完全不同的節點上，因此r節點和w之間不再保證有重疊節點。
• 如果兩個寫入同時發生，不清楚哪一個先發生。 在這種情況下，唯一安全的解決方案是合併併發寫入。 如果根據時間戳（最後寫入勝利）挑選出勝者，則由於時鐘偏差，寫入可能會丟失。
• 如果寫操作與讀操作同時發生，寫操作可能僅反映在某些副本上。 在這種情況下，不確定讀取是返回舊值還是新值。
• 如果寫操作在某些副本上成功，而在其他節點上失敗，在小於w個副本上寫入成功。 所以整體判定寫入失敗，但整體寫入失敗並沒有在寫入成功的副本上回滾。 這意味著如果一個寫入雖然報告失敗，後續的讀取仍然可能會讀取這次失敗寫入的值。
• 如果攜帶新值的節點失敗，需要讀取其他帶有舊值的副本。 並且其數據從帶有舊值的副本中恢復，則存儲新值的副本數可能會低於w，從而打破法定人數條件。
• 即使一切工作正常，有時也會不幸地出現關於時序（timing）的邊緣情況。

監控陳舊度

在無領導者複製的系統中，沒有固定的寫入順序，這使得監控變得更加困難。 而且，如果資料庫只使用讀修復（沒有反熵過程），那麼對於一個值可能會有多大的限制是沒有限制的 - 如果一個值很少被讀取，那麼由一個陳舊副本返回的值可能是古老的。

關於衡量無主複製資料庫中的複製陳舊度的研究，並根據參數n，w和r來預測陳舊讀取的預期百分比，將過時測量值包含在數據庫的標準度量標準中是一件好事。 最終的一致性是故意模糊的保證，但是對於可操作性來 說，能夠量化"最終"是很重要的。

鬆散法定人數與帶提示的接力

松散的法定人数(sloppy quorum): 寫和讀仍然需要w和r成功的回應，但是那些可能包括不在指定的n個"主"節點中的值

優點:對寫入可用性的提高 缺點:即使當$w + r> n$時，也不能確定讀取某個鍵的最新值，因為最新的值可能已經臨時寫入了n之外的某些節點

在所有常見的Dynamo實現中，鬆散法定人數是可選的。 在Riak中，它們預設是啟用的 在Cassandra和Voldemort中它們預設是關閉的

維運多個數據中心

在無主複製亦適用多個數據中心操作, 因為它旨在容忍衝突的併發寫入，網路中斷和延遲尖峰

小結

複製可以用於幾個目的：

1. 高可用性:

• 即使在一台機器（或多台機器，或整個數據中心）停機的情況下也能保持系統正常運行斷開連接的操作
• 允許應用程式在網路中斷時繼續工作

2. 延遲:

• 將數據放置在距離使用者較近的地方，以便用戶能夠更快地與其交互

3.可擴展性:

• 能夠處理比單個機器更高的讀取量可以通過對副本進行讀取來處理

儘管是一個簡單的目標,但複製卻是一個非常棘手的問題。 它需要仔細考慮併發和所有可能出錯的事情，並處理這些故障的後果。

我們討論了複製的三種主要方法：

1. 單主複製: 用戶端將所有寫入操作發送到單個節點（Leader），該節點將數據更改事件流發送到其他副本（Follower）。 讀取可以在任何副本上執行，但從Follower讀取可能是陳舊的。

2. 多主複製: 客戶端發送每個寫入到幾個Leader節點之一，其中任何一個都可以接受寫入。 領導者將數據更改事件流發送給彼此以及任何副本（Follower）。

3. 無主複製: 客戶端發送每個寫入到幾個節點，並從多個節點並行讀取，以檢測和糾正具有陳舊數據的節點。

我們研究了一些可能由複製滯後引起的奇怪效應，我們討論了一些有助於決定應用程式在復制滯後時的行為的一致性模型：

• 寫後讀: 用戶提交資料後可能會立即查看。然而，如果使用異步複製，新資料可能尚未同步到副本中，導致用戶看不到剛剛提交的資料，造成用戶不滿。

• 單調讀: 使用非同步從庫讀取資料時，可能出現的時光倒流現象。 當使用者從不同從節點進行多次讀取時，可能會看到不一致的結果。

• 一致前綴讀: 用戶應該將數據視為具有因果意義的狀態：例如，按照正確的順序查看問題及其答覆。

複製策略優缺點比較: