本文為 Design Data Intensive Applications 的書摘 + 個人心得。
線性一致性 (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 很長可能是網路延遲或其他鬼故事發生的關係， 所以對資料庫來說它是完成寫入了）。
我們可以進一步細看這個時序圖，視覺化所有原子操作的時間點，如下圖 9-4，除了讀取跟寫入，這裡我們多增加了一個操作： CAS (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 吧！
依賴線性一致性的場景
鎖和 leader 選舉
若系統是 single-leader，一個選 leader 的方式是使用鎖，所有節點都嘗試去取得鎖，成功的節點成為 leader，這個過程就很適合使用 線性一致性 (Linearizability) 的概念來建立機制；協調服務像 Apache Zookeepr 就常拿來幹選 leader 的事，它多使用了共識算法來實作線性化操作。
限制和唯一保證 (Constraints and uniqueness guarantees)
唯一限制常被用在資料庫中，如果你想要在資料寫入時限制些東西（像 2 個 user 同時建一樣 email 的帳號），你就需要 線性一致性。
實現線性化系統 (Implementing Linearizable Systems)
線性一致性意味者 資料只有一份，且它所有的操作皆是原子操作；一般來說，讓系統允許容錯的方法就是使用 數據複製 (replication)，但資料若只有一份，該怎麼容錯呢？現在我們回頭看一下 之前 談過的分散式系統 replication 方法，看它們能否支持線性化 (linearizable)。
Single-leader replication (潛在線性化)
使用 single-leader replication 的資料庫 ，leader 有主要給寫入使用的資料副本，其他 followers 節點則是使用該資料的備份，如果你從 leader 讀取資料，或者 follower 節點是使用同步化的方式讀取資料，則 single-leader 可以做到潛在線性化（但不是所有的 single-leader 資料庫都能線性化，要看它怎麼設計）。
再者就是 single-leader 可能會發生 Trouble with Distributed Systems – Truth and Lies 講過的情況，或者 follower 是使用異步化的方式更新節點資料的話，它就違反線性一致性了。
Consensus algorithm (線性化)
之後開始會講到 共識算法 (Consensus algorithm)，現在只要知道該系統很像 single-leader ，但它避免了 split brain 和壞掉的副本，所以它能安全的實作線性一致性系統。
Multi-leader replication (無線性化)
multi-leader replication 就代表它們會並發的在多個節點寫入資料，然後 異步化 (asynchronous) 的同步資料，所以就沒有線性化了。
Leaderless replication (可能沒有線性化)
無 leader 的系統，人們常誤會它有很強的一致性，但實質不然；若你解資料衝突策略是用 最後寫的是老大 (Last write wins) ，它通常會依靠日歷鐘來比較時間，所以若時鐘不準，它就無法保證事件順序，所以 leaderless replication 就沒有線性化了； 又或者發生 Sloppy Quorums and Hinted Handoff 也會破壞線性一致性。
那如果我用很強的 quorum (法定人數) 呢？如下圖 9-6：
x 初始是 0，然後 Writer 寫 x=1 到 3 個副本上 (n=3, w=3)，寫入時發生鬼故事之一的網路延遲；同時間，Reader A 往 2 個副本讀取資料 (r=2)，A 看到了新值 1 ，而 Reader B 也是往 2 個副本讀取資料，但它只看到舊值 0 。
quorum 條件符合 (w + r > n) ，但 B 在 A 之後讀取資料，卻讀到舊資料，就不符合線性一致性了。
