iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 24
2
AI & Data

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

[Day 24] Replication (4-1) - Leaderless Replication

Leaderless Replication

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

Writing to the Database When a Node Is Down

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

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 意思請看 Day 21

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 個節點,以我們的例子就是 https://chart.googleapis.com/chart?cht=tx&chl=n%3D3%2C%20w%3D2%2C%20%20r%3D2 ;只要符合 https://chart.googleapis.com/chart?cht=tx&chl=w%20%2B%20r%20%3E%20n 就行,這些必須遵守的讀取和寫入數量稱為 quorum,w 和 r 可以想成為了讓寫入跟讀取 有效 的最小數量。

最常見的做法是通常會讓 n 設定為奇數 (3 或 5),然後讓 https://chart.googleapis.com/chart?cht=tx&chl=w%20%3D%20r%20%3D%20(n%20%2B%201)%20%2F%202 (四捨五入)。

我們來看看在符合 https://chart.googleapis.com/chart?cht=tx&chl=w%20%2B%20r%20%3E%20n 的條件下,能讓系統容許多少不可用的節點:

  • w < n,當一個節點不可用時,系統還能持續處理寫入。

  • r < n,當一個節點不可用時,系統還能持續處理讀取。

  • n = 3, w = 2, r = 2 ,我們可以容許一個節點掛掉。

  • n = 5, w = 3, r = 3 ,我們可以容許二個節點掛掉,如下圖:

    figure_5-11

這些設定也能依場景做調整,例如我們有一個寫入很少但讀取非常大量的場景,我們可以將資料庫設定為 https://chart.googleapis.com/chart?cht=tx&chl=w%20%3D%20n%20%2C%20r%20%3D%201 ,這樣的好處是讀取會變快,但壞處是只要有一個節點壞掉寫入就會失敗,如果寫入或讀取時不滿足 w 或 r 個節點,則會回覆錯誤。


Leaderless Replication 的後半段明日待續啦!


上一篇
[Day 23] Replication (3) - Multi-Leader Replication
下一篇
[Day 25] Replication (4-2) - Leaderless Replication - Sloppy Quorums and Hinted Handoff
系列文
資料工程師修煉之路30

尚未有邦友留言

立即登入留言