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) 类型的资料库该如何实作线性一致性。