Leaderless Replication

本文為 Design Data Intensive Applications 的書摘 + 個人心得。

在過去 relational 資料庫主宰過的那個時代中，Leaderless replication (無 leader 副本) 的概念已有但乏人問津，直到 Amazon 在內部的 Dynamo 系統中使用，之後就是許多的 open source 都以此 replication 模型為基準，如 Riak, Cassandra, Voldemort，這種 replication 風格的資料庫也稱 Dynamo-style 。

Writing to the Database When a Node Is Down

想像一下你在 3 個節點做 replica，然後有一台掛掉，在 leader-base replication 架構下，如果你想繼續處理寫入，你必須執行 failover，但在 leaderless replication 架構下，failover 不存在，下圖說明了 leaderless 如何在有節點掛掉時還能處理寫入需求：

failover 的說明請參考 Leaders and Followers。

我們可以看到 User 1234 是同時送 3 個寫入需求到 3 個 replica 節點上，其中 2 個 replica 回覆 OK，1 個 replica 掛點，然後我們因為收到 2 個 OK 所以認為寫入成功了，現在想像一下當 Replica 3 恢復了，另一個 User 2345 讀取資料，因為 Replica 3 的資料不是最新，所以會讀到舊的資料，我們稱這種遺失的資料為 stale (outdated) – 腐敗資料。

如何不讓 stale 資料來影響查詢結果呢？我們得讓 client 並行的發數個 reqeust 到不同節點上，然後我們可以透過 Version 號來判斷哪個 Replica 的資料是最新的。

Read repair and anti-entropy

讀取資料沒問題了，那我們如何讓上圖的 Replica 3 catch up 遺失的資料呢？有 2 個在 Dynamo-style 中常用的機制：

catch up 的說明請看 Leaders and Followers。

Read repair

當 client 從多個 replica 讀取資料後，我們可以檢查哪些資料是腐敗的，如前一小節的圖 5-10，檢查到 stale 資料後就將最新資料寫回該 Replica 節點上，這個方法適合大量讀取的場景。

anti-entropy process

反熵進程 (聽起來很高大上的 process)，這是一種附加的做法，在某些資料庫會在背景執行此程式來尋找遺失的資料，然後把資料從某個 replica 複製到另一個上，不像 leader-base replication 所用的 log ，anti-entropy process 不理會資料順序，也就是說資料在複製時可能會發生嚴重的延遲。

熵為一物理概念，來描述系統的混亂程度，當一個系統越混亂，熵越高，反之亦然，

Quorums for reading and writing

想像一下圖 5-10 的例子，若寫入時只有一台 replica 回覆 OK 時該怎麼辦？

在 3 台 replica 下我們能夠獲得寫入資料成功的最低保證是 2 個 replica，也就是說最多能容許一個 replica 能變成腐敗狀態，所以若我們在讀取時最少讀 2 個 replica，至少一定會有一個 replica 的資料是最新的，所以也能容許某一個 replica 掛掉。

一般來說，若 replica 是 n 台，每一次寫入必須確認有 w 個節點成功，然後查詢時必須最少查 r 個節點，以我們的例子就是 n=3, w=2, r=2；只要符合 w + r > n 就行，這些必須遵守的讀取和寫入數量稱為 quorum，w 和 r 可以想成為了讓寫入跟讀取有效的最小數量。

最常見的做法是通常會讓 n 設定為奇數 (3 或 5)，然後讓 w = r = (n + 1) / 2 (四捨五入)。

我們來看看在符合 w + r > n 的條件下，能讓系統容許多少不可用的節點：

若 w < n，當一個節點不可用時，系統還能持續處理寫入。
若 r < n，當一個節點不可用時，系統還能持續處理讀取。
若 n = 3, w = 2, r = 2 ，我們可以容許一個節點掛掉。
若 n = 5, w = 3, r = 3 ，我們可以容許二個節點掛掉，如下圖：

這些設定也能依場景做調整，例如我們有一個寫入很少但讀取非常大量的場景，我們可以將資料庫設定為 w=n , r=1 ，這樣的好處是讀取會變快，但壞處是只要有一個節點壞掉寫入就會失敗，如果寫入或讀取時不滿足 w 或 r 個節點，則會回覆錯誤。

Sloppy Quorums and Hinted Handoff

資料庫若有適當的 quorums，它能夠允許獨立的節點掛掉而不用完成 failover，它也能允許某些節點變慢，因為只要等待到符合 quorums 的量就好了。

然而，quorums 並不能保證 uesr 始終能連線到所有的 n (節點)，網路一不穩就會造成 user 從大量的資料庫叢集中被斷掉某些連線，此時你只剩下小於 w 和 r 的節點可連線，所以你往後不可能達到 quorums 的量。

這個時候工程師們就有些權衡點可以煩惱了：

當能連線的節點數不足 w 和 r 的量時，我們應該全部 return error 嗎？
或者，就同意讓 client 寫入到某些能被連接的節點，不用寫到所有活著的 n 之中。

後者被稱為 sloppy quorums ，寫入和讀取一樣需要接收到 w 和 r 的量，但在這些節點中，可能不全都是在 n 裡面的節點。

書中用一個例子來說明，想像你被鎖在你家外面，你能敲你鄰居的門，然後坐在他的沙發上看電視。

一旦網路問題解決，剛剛那個被暫存資料的節點就會送資料給所有 n 裡面的節點，這個動作稱為 hinted handoff。

回到那個例子，你找到你家的鑰匙了，你的鄰居就會很有禮貌的請你從他的沙發上滾開然後叫你回家。

最後，sloppy quorums 不是一般我們認為的那種 quorums，它只是一種系統能更加耐用的保證，資料最終還是會被存到某個地方的 w 個節點上，另外它沒有保證 r 在 hinted handoff 完成後能馬上看到資料。

sloppy quorums 通常在 Dynamo-style 資料庫中都是 optional (非必須)，如 Cassandra 和 Voldemort 皆是。

Detecting Concurrent Writes

Dynamo-style 資料庫允許多個 client 同時寫同一個 key 的資料，意味者資料的衝突勢必會發生，雖然可以提升成 Read repair 和 hinted handoff 的問題 (也就是當節點掛掉問題來處理)，但這衝突追根究底是資料在到達多個節點時的順序不同，一個簡單的例子來說如下圖：

Node 1 接收了 A 的寫入，但沒接收到 B 的寫入需求 (可能是網路問題)。
Node 2 先接收了 A 的寫入，然後是 B 的寫入。
Node 3 先接收了 B 的寫入，然後是 A 的寫入。

如果我們只是簡單覆蓋資料過去，最後在取得 X 的資料時，每個節點的資料會不一致，為了資料在每個 replica 的 eventual consistency (Leaders and Followers)，你不能指望資料庫像個黑盒子般的解決衝突，現在我們就來看看這其中有什麼黑科技吧！

Last write wins (discarding concurrent writes)

最後寫的是老大！Last write wins (LWW) 這個方法就是只保留最近的資料，然後覆寫和捨棄舊的資料；這裡最有趣的問題是什麼是最近 ? 你可以選一個最大的 timestamp，你也可以選一個最大的資料版本號，LWW 也是 Cassandra 唯一支援的解衝突演算法。

LWW 是以資料庫的耐用性為成本，如果我們有多個並行寫入到同一個 key，儘管符合 w 的 quorums 量，但最終只會有一筆資料存活下來，其他的資料會被安靜的被幹掉。

另外如果遺失資料是不被同意的，LWW 是個很爛的解衝突方法，這時唯一的方法就只能確保每筆資料只會寫入一次，然後另資料成為不可變，Cassandra 就使用 UUID 做它的唯一 key。

The “happens-before” relationship and concurrency

首先要了解一下什麼是 happens-before relationship 和 concurrency (並發性)：

happens-before relationship 以下圖為例子來說明，Client B 更新資料時是依賴於 Client A 所新增的值 (value = value + 1)，換句話說 B 的操作一定比 A 之後，也可說 B 是 因果依賴 (causally dependent) 在 A 上。

concurrency 如最上面貼過的圖 5-12，Client A 和 B 的操作可視為 concurrent (並發)，因為它們倆並不知道另一個 Client 是否有針對同一個 key 做操作，也就沒有誰依賴誰的關係了。

一個操作是否在另一個操作之後 是判斷是否為並發的關鍵，所以說 2 個操作 A 和 B 只會有 3 個關係：A 在 B 之前發生、B 在 A 之前發生、或者 A 和 B 為 concurrent (並行)，所以我們會需要一個演算法來幫助我們若是 happend-before 關係我們需要覆寫舊的值，若是並行則需要解決衝突。

Capturing the happens-before relationship

我們就用一個簡單化的購物車例子 (replica 只有一份) 來說明演算法怎麼工作吧，請先看下圖：

圖 5-13 示範了 2 個 client 同時操作購物車時之間的資料依賴關係，一開始的購物車是空的，各步驟的解釋如下：

Client 1 新增了 milk (牛奶) 到購物車裡，這是該 key 的第一次新增，所以資料庫儲存後也指派成 version 1，然後在回覆剛剛新增的資料給 Client 端。
Client 2 新增了 eggs (蛋) 到購物車裡，Client 2 並不知道 Client 1 已經並行且成功的新增了 milk (牛奶) 到購物車裡，資料庫對 Client 2 的寫入指派成 version 2，然後將 eggs 和 milks 分開來存，最後在回覆這 2 個值給 Client 2。
Client 1 不知 Client 2 新增 eggs 成功，他這時想新增 flour (麵粉) 至購物車裡，所以 Client 1 認為此時購物車應該是 [milk, flour] ，所以就隨著先前取得的 version 1 一起傳給資料庫，跟它說我想覆寫 version 1 的資料成為 [milk, flour]，但是這裡已經有個並行寫入的 [eggs] ，因此資料庫就對 [milk, flour] 指派了個 version 3 的編號，並覆寫了 version 1 的 [milk]，同時保留 version 2 的值 [eggs]，然後把留下來的所有值回傳給 Client 1 。
同時，Client 2 想新增 ham (火腿) 至購物車中，Client 2 此時並不知道 Client 1 已新增成功 flour，Client 2 先前已從資料庫接收到 2 個值 [milk] 和 [eggs]，所以 client 端可以合併他們並加入想要新增的 ham (火腿) 成為新的值 [milk, eggs, ham]，Client 2 一樣隨著前一個接收到的 version 2 編號一起將新值傳給資料庫，資料庫一樣知道 version 2 的 [eggs] 要被覆寫成新的值，但此時有並行的 version 3 [milk, flour] 存在，所以就保留 version 3，並將 [milk, eggs, ham] 指派成 version 4。
最後，Client 1 想新增 bacon (培根)，一樣合併 version 3 中的資料成為 [milk. flour, eggs, bacon]，並告知資料庫要覆寫 version 3 (注意 verison 2 的 eggs 已被上一步覆寫了)，一樣因為有並行的 [eggs, milk, harm] 資料存在，所以資料庫也是持續保留這 2 個值。

圖 5-13 的資料流可以視覺化成下圖，自從另一個 Client 在做並行操作後，每一個 client 都沒有維持在最新資料，但舊的 version 資料最終還是會被覆寫成新的，且沒有資料會遺失。

這裡要留意的是寫入時務必要搭配 version 編號，否則不會覆寫任何資料。

Merging concurrently written values

這個演算法雖然可以不讓資料被捨棄，相對的它會造成 Client 額外的工作，Client 必須做合併的工作，寫入衝突在 Multi-Leader Replication 時有介紹過，依不同場景能選擇不同方法，最簡單的方法就是上面介紹過的 LWW；圖 5-13 的購物車例子是使用 union (聯集) 方法。

合併的工作是很複雜且容易錯誤的，需要努力為其設計資料結構執行，有興趣的可以找書看 “Automatic Conflict Resolution” on page 174 講 Riak 怎麼為其設計一個資料型態來做合併。

Version vectors

圖 5-13 介紹的例子是針對單一 replica，那本章的重點 leaderless replication 呢？

這時我們就需要每個 replica 中的每個 key 都會有自己的 version 編號，這個 version 的集合稱為 version vetor ，這個 version vector 會讓資料庫區分哪些是覆寫，哪些是並行來的資料，然後其他的處理概念跟單一 replica 差不多。

Leaderless Replication