Consistency and Consensus (2-2) - Implementing Linearizable

续 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)。