續 Day 15

依賴線性一致性的場景

鎖和 leader 選舉

若系統是 single-leader，一個選 leader 的方式是使用鎖，所有節點都嘗試去取得鎖，成功的節點成為 leader，這個過程就很適合使用 線性一致性 (Linearizability) 的概念來建立機制；協調服務像 Apache Zookeepr 就常拿來幹選 leader 的事，它多使用了共識算法來實作線性化操作。

限制和唯一保證 (Constraints and uniqueness guarantees)

唯一限制常被用在資料庫中，如果你想要在資料寫入時限制些東西（像 2 個 user 同時建一樣 email 的帳號），你就需要 線性一致性。

實現線性化系統 (Implementing Linearizable Systems)

線性一致性意味者 資料只有一份，且它所有的操作皆是原子操作；一般來說，讓系統允許容錯的方法就是使用 數據複製 (replication)，但資料若只有一份，該怎麼容錯呢？現在我們回頭看一下 2020 Day 21~Day 26 談過分散式系統的 replication 方法，看它們能否支持線性化 (linearizable)。

Single-leader replication (潛在線性化)

使用 single-leader replication 的資料庫 ，leader 有主要給寫入使用的資料副本，其他 followers 節點則是使用該資料的備份，如果你從 leader 讀取資料，或者 follower 節點是使用同步化的方式讀取資料，則 single-leader 可以做到潛在線性化（但不是所有的 single-leader 資料庫都能線性化，要看它怎麼設計）。

再者就是 single-leader 可能會發生 Day 12 講過的情況，或者 follower 是使用異步化的方式更新節點資料的話，它就違反線性一致性了。

Consensus algorithm (線性化)

Day 20 開始會講到 共識算法 (Consensus algorithm)，現在只要知道該系統很像 single-leader ，但它避免了 split brain 和壞掉的副本，所以它能安全的實作線性一致性系統。

Multi-leader replication (無線性化)

multi-leader replication 就代表它們會並發的在多個節點寫入資料，然後 異步化 (asynchronous) 的同步資料，所以就沒有線性化了。

Leaderless replication (可能沒有線性化)

無 leader 的系統，人們常誤會它有很強的一致性，但實質不然；若你解資料衝突策略是用 最後寫的是老大 (Last write wins) ，它通常會依靠日歷鐘來比較時間，所以若時鐘不準 (Day 11) ，它就無法保證事件順序，所以 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 之後讀取資料，卻讀到舊資料，就不符合線性一致性了。

線性一致性告一段落啦，明後天開始談 排序保證 (Ordering Guarantee)。