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) 類型的資料庫該如何實作線性一致性。