iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
AI & Data

資料工程師修煉之路 Part II系列 第 15

Consistency and Consensus (2-1) - Linearizability

Linearizability

線性一致性 (Linearizability) 的概念就是原來有多份副本的資料庫變成只有一份,這樣就不會有往不同副本讀取資料卻得到不同結果的情況,且它所有的操作皆是原子操作。

在線性一致性系統中,當一個使用者完成寫入,其他所有使用者必須都讀到最近的寫入,換句話說,線性一致性也等於是 最近保證 (recency quarantee)

什麼東西使系統線性化?(What Make a System Linearizable?)

雖然線性一致性概念很簡單,但實際上做起來要考量一些東西,為了更了解線性化,來看幾個例子吧!

下圖 9-2 展示了 3 個 Client 往線性化資料庫並發讀取跟寫入 key 為 x 的情境,每一條 bar 代表了 request 的開始與結束,在分散式系統文獻中,x 稱為 register,實務上 x 可以是 key-value 資料、RDB 的 row 或者 文件資料庫 (document database) 的 文件 (document)。

現在我們能確定的是:

  • Client A 的第 1 次和第 3 次讀取是符合邏輯,因為是在 Client C 寫入前後發生。
  • 而 Client A 第 2 次讀取和 Client B 的讀取因為是與 Client C 的寫入並發發生,因為它們不曉得 Client C 的寫入到底何時影響資料,所以它可能會回傳 0 或 1。

但是在 線性一致性 (Linearizability) 系統中,為了滿足 當一個使用者完成寫入,其他所有使用者必須都讀到最近的寫入,我們必須讓系統線性化,幫它加了個額外的時間依賴關係,如下圖 9-3 的箭頭:

因為 Client B 的第 2 次讀取是在 Client A 的第 2 次讀取之後,所以 Client B 務必會讀到新的值,儘管 Client C 的寫入操作還沒完成(Client C bar 很長是因為網路延遲或其他鬼故事原因 Day 8 ~ Day13, 所以對資料庫來說它是完成寫入了)。

我們可以進一步細看這個時序圖,視覺化所有原子操作的時間點,如下圖 9-4,除了讀取跟寫入,這裡我們多增加了一個操作: cas (Day 5 - Compare-and-set):

  • $cas(X, V_{old}, V_{new}) => r$

    原子性的 比較並交換 (Compare-and-set) 作業,當 $X$ 的值等於 $V_{old}$ 時,將 $X$ 的值設為 $V_{new}$ ,若等於則回傳 Error,$r$ 等於回傳的訊息,Ok 或 Error。

每一個圖 9-4 的操作都能看到直線,直線的時間點可想成是資料庫已經執行完該作業的時間點,直線將所有操作從左到右有序的串連起來,代表時間軸是一直前進的;register 一旦被寫入新值,所有後續的讀取必定是前一次的寫入(最近保證)。

這裡可以看到幾個有趣的點:

  • Client B 先執行 read 操作,然後 Client D 寫 0,再來才是 Client A 寫 1, 並發操作的結果還是看資料庫處理的順序,所以 Client B 最後讀的到值是 1 (老樣子 Client B 可能網路延遲所以才會等這麼久)。
  • Client B 讀到 1 時,Client A 的操作都還沒收到資料庫的回覆訊息呢。
  • Client D 的 cas 操作 Error,因為 x 的值並發的被 Client A 和 C 改掉。
  • Client B 最後的讀取不符合線性化,Client B 讀取到的值不得比 Client A 還舊。

好啦,以上是對線性一致性概念直觀圖示化展示,正式的定義其實更加精準,有興趣的就自己看 Linearizability: A Correctness Condition for Concurrent Objects 吧!


明天會繼續看各種 數據複製 (replication) 類型的資料庫該如何實作線性一致性。


上一篇
Consistency and Consensus (1) - Consistency Guarantees
下一篇
Consistency and Consensus (2-2) - Implementing Linearizable
系列文
資料工程師修煉之路 Part II30

尚未有邦友留言

立即登入留言