线性一致(2)

为使系统线性一致，需新增一个重要约束，如图-3：

在一个线性一致系统中，在 x 值从 0 自动翻转到 1 时（在写操作开始和结束之间）必定有一时间点。因此，若某客户端读取返回新值 1，即使写未提交，所有后续读也必须全部返回新值。

图-3中的箭头表示该时序依赖关系。客户端 A 先读到新值 1 ，A读取返回后，B 开始读。由于 B 读严格在A 读后发生，因此即使 C 写仍在进行中，也必须返回 1（与图-1的 Alice 和 Bob 的情况相同：在 Alice 读取新值后，Bob 也希望读新值）。

进一步细化该时序图，图-4显示一个更复杂案例：

图-4中，除读写外，还引入第三种类型的操作：

• cas(x, v_{old}, v_{new})⇒r 表示客户端请求操CAS操作。若寄存器 x 的当前值等于 v_{old} ，则应该原子地设置为 v_{new} 。如果 x≠v_{old} ，则操作应该保持寄存器不变并返回一个错误。 r 是数据库的响应（正确或错误）。

图-4每个操作都有竖线，表示可能的执行时间点。这些标记按序连接，结果必是有效的寄存器读写序列（即每次读取都必须返回最近一次写设置的值）。

线性一致要求是，若操作标记的连线总按时间（从左到右）向前移动，而不能向后移动。该要求确保我们之前讨论的就近性保证：一旦新值被写入或读取，所有后续读都会看到最新值，直到被再次覆盖。

图-4：

• B先发送读取 x 请求，然后D发送请求将 x 置为 0，紧接着A发请求将 x 置 1。而最终返回给B的值为 1（由A所写）。这是可以的：这意味着数据库首先处理 D 的写入，然后是 A 的写入，最后是 B 的读取。虽然这不是请求发送的顺序，但这是一个可以接受的顺序，因为这三个请求是并发的。也许 B 读网络延迟更大，导致在两次写后才到DB，因此这是个合法的可接受的处理顺序。

• A从DB收到响应前，B即读到1 ，表示写1 已成功。这是肯能的：但不代表着执行写前执行了读，只意味着可能从DB到A的响应在网络中略有延迟。

• 此模型不假定事务间的隔离：即另一个并发客户端可能随时更新值。如C首先读到 1 ，然后读到 2 ，因为两次读之间的值由 B 更改。可使用CAS检查值是否被其它客户端更改，如B、C的CAS成功，但D的CAS失败（因为DB处理时，x 值已不再是0 ）。

• B最后一次读取（阴影方框）不满足线性一致性。该操作与C的CAS写并发（它将 x 从 2 更新为 4 ）。无其他请求时，B可以读到 2 。但B读开始前，A已读新值 4 ，因此不允许B读比A更旧的值。这与图-1的 Alice 和 Bob case相同。

这就是线性一致性背后的直觉。 正式的定义【6】更准确地描述了它。 通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，以测试一个系统的行为是否线性一致性是可能的（尽管在计算上是昂贵的）【11】。