iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 26
1
AI & Data

資料工程師修煉之路系列 第 26

[Day 26] Replication (4-3) - Leaderless Replication - Detecting Concurrent Writes & 結論

延續 (Day 25)

Detecting Concurrent Writes

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

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

figure_5-12

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

Last write wins (discarding concurrent writes)

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

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

另外如果遺失資料是不被同意的,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 上。

    figure_5-9

  • 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 必須做合併的工作,寫入衝突在 Day 23 時有介紹過,依不同場景能選擇不同方法,最簡單的方法就是上面介紹過的 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 差不多。

總結

終於到總結啦!

Replication 這章首先在講做分散式資料的原因:Scalability, Fault tolerance/high availability (容錯 / 高可用性), Latency

最後在講做 replication 的方式:

Single-leader replication (Day 21, Day 22)

Multi-leader replication (Day 23)

Leaderless replication (Day 24 ~ Day 26)

明天,就會進入了 partition 環節,如何把大的資料集切成小的。


上一篇
[Day 25] Replication (4-2) - Leaderless Replication - Sloppy Quorums and Hinted Handoff
下一篇
[Day 27] Partitioning (1) - Partitioning of key-value data
系列文
資料工程師修煉之路30

尚未有邦友留言

立即登入留言