Leaderless Replication

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

Leaderless Replication

在過去 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

figure_5-10

我們可以看到 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 ,這樣的好處是讀取會變快,但壞處是只要有一個節點壞掉寫入就會失敗,如果寫入或讀取時不滿足 wr 個節點,則會回覆錯誤。

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 的寫入。
figure_5-12

如果我們只是簡單覆蓋資料過去,最後在取得 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 relationshipconcurrency (並發性):

  • 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 只有一份) 來說明演算法怎麼工作吧,請先看下圖:

figure_5-13

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

  1. Client 1 新增了 milk (牛奶) 到購物車裡,這是該 key 的第一次新增,所以資料庫儲存後也指派成 version 1,然後在回覆剛剛新增的資料給 Client 端。
  2. Client 2 新增了 eggs (蛋) 到購物車裡,Client 2 並不知道 Client 1 已經並行且成功的新增了 milk (牛奶) 到購物車裡,資料庫對 Client 2 的寫入指派成 version 2,然後將 eggs 和 milks 分開來存,最後在回覆這 2 個值給 Client 2。
  3. 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 。
  4. 同時,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。
  5. 最後,Client 1 想新增 bacon (培根),一樣合併 version 3 中的資料成為 [milk. flour, eggs, bacon],並告知資料庫要覆寫 version 3 (注意 verison 2 的 eggs 已被上一步覆寫了),一樣因為有並行的 [eggs, milk, harm] 資料存在,所以資料庫也是持續保留這 2 個值。

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

figure_5-14

這裡要留意的是寫入時務必要搭配 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 差不多。

tshine73
tshine73
文章: 50

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *