现实生活中，对于一个系统的组成会经常发生网络分区、消息丢失、发送延迟、消息重复、消息乱序等等，造成这一问题的原因有很多，包括光纤、交换机、网卡、主机硬件、操作系统、磁盘、虚拟化层、程序等等，都可能会出现各种各样的问题。

此时就需要有一个比较直观的正确性模型，包括如何定义、描述。

简介 #

数据库、分布式中存在多种一致性的定义，例如 ACID 中的 Consistency、RAFT/Paxos 中的 Consensus (共识)、CAP Theory 中的 Consistency 以及 MESI Cache 中的 Coherence 。这些概念在使用时很容易混淆，这里先介绍分布式系统中的相关概念。

分布式系统中与一致性相关的主要有，线性一致性 Linearizability、顺序一致性 Sequential Consistency、因果一致性 Causality Consistency、最终一致性 Eventual Consistency 四类。

现实 #

当对某个全局资源进行操作时，本机上可能会消耗十几到几百个时钟周期，到分布式系统上会更加明显，那么每个操作可能会在期间的任意时间点发生，这也就是说，所有的操作会有两个特性：

• 每个操作包括了请求 (Invocation) 和响应 (Response) 两个事件，而且请求一定早于响应。
• 每个操作的实际生效时间在请求和响应之间的任意时间。

Linearizability #

也被称为强一致性或者原子一致性，最早在 1978 年的 Linearizability: A Correctness Condition for Concurrent Objects 论文中给出了形式化的定义。

简单来说，严格保证时间顺序一致，当某个操作完成后，后续其它操作应该读取到该操作的结果，注意，对操作中间态没有限制。

意味着不会读取到发起请求前的老数据，读取到的是发起请求到结束请求之间的数据，这也是最严格的方式，成本也最高。

如下是一个简单示例。

虽然在 Clint B 看来，成功将 x 修改为了 2，而且读取到了 2，但是实际上已经有其它客户端将 x 修改为了 4，所以不满足线性一致性的要求，此时读取到的应该是 4 。

另外，这里只是定义了逻辑上的时间，而实际实现时的时间和事件顺序又另当别论。

Sequential Consistency #

在提出线性一致性之前，Lamport 早在 1979 年就提出了顺序一致性的概念：

A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

另外，Lamport 上述的定义是基于单机的，如上所述，可以扩展推广到分布式系统领域。这个定义实际上对系统提出了两条访问共享对象时的约束：

1. 从单个线程 (或进程) 的角度上看，其指令的执行顺序以程序中的顺序为准；
2. 从所有线程 (或进程) 的角度上看，指令的执行保持一个单一的顺序。

其中，约束 1 保证了单进程的所有指令是按照程序中的顺序执行，也就是符合我们编码最初的预期，这里针对的是执行顺序，而非结果；约束 2 保证了所有的内存操作都是原子的或者说实时生效的，其执行顺序不必严格遵循时间顺序。

对于顺序一致性来说，上述两种方式都是合法的，只要满足客户端看到的顺序一致性即可，不要求严格的全局时钟顺序，但是线性一致性则要求只能出现其中的一种结果。

前者的顺序为
A W(x, 1) => B W(x, 2) => C R(x, 1) -> D R(x, 1) => C R(x, 2) => D R(x, 2)
后者的顺序为
B W(x, 2) => A W(x, 1) => C R(x, 2) => D R(x, 2) => C R(x, 1) => D R(x, 1)

最常见的如订阅系统、Twitter消息等，实际使用时，常见的数据库主备复制都是满足的。

其它 #

Linearizability VS. Serializability #

这两个概念是分布式、数据库中常见而且容易混淆的概念，简单来说，其区别可以概括为。

Linearizability: single-operation, single-object, real-time order.

Serializability: multi-operation, multi-object, arbitrary total order.

在 Linearizability 的定义里有顺序化 (Sequential)，而在 Serializability 的定义里有串行化 (Serial)，所以会导致这两个概念非常容易混淆，而实际上，这两个概念分别源自分布式系统和数据库，随着分布式数据库发展导致这两个概念比较容易混淆。

更多可以参考 Linearizability VS. Serializability 中的内容。

Linearizability #

用来保证的是针对单个对象的多个操作行为，而且是在严格时序上的操作顺序。

简单来说，写对于应用来说是立即生效的，也就是说，当写入完成后，所有后续 (严格时序) 的读操作，获得的都是最新值；当读获取到一个值后，后面的操作将读取到该值或者最新的值。

对应了 CAP 理论中的 C 。

Serializability #

保证的是针对多个对象的一组操作 (一般是事务)，确保这组操作等价于某个顺序执行过程。

注意，上述的顺序没有明确说是何种顺序，不必是严格的时间序，只需要某个可以确定存在的执行顺序即可，有点类似 SC 。

这是事务 (ACID) 的隔离 (Isolation) 级别，事务是有可能会读写多个对象的，该特性用于保证不同事务在执行时的效果跟串行化 (前一个事务结束了后一个事务才开始，没有重叠) 执行是一样。

注意，该特性不保证多个事务彼此之间的顺序，它只是一个保证数据库正确性条件。

Strict Serializability #

也就是将 Linearizability 和 Serializability 结合起来，例如在事务 T1 中写入 X 的值，然后事务 T2 再读取 X 的值，那么对于 SS 来说，需要严格保证 T1 先于 T2 执行。

对于只提供了 Serializability 能力的数据库来说，是允许 T2 先于 T1 执行的。

实际上，如果数据库使用的锁来保证 (锁粒度较大)，那么就是 SS ；如果采用了 MVCC 实现，那么可能就只是 Serializability 。

总结 #

两者的实现都必须要有一个中间协调者才可以。真实场景是，默认数据库不会使用 Serializability ，多核的系统也不会使用 Linearizability ，如果要使用，那么会有非常高的成本，所以使用较多的是 Read Commit 以及 SC 。

参考 #

• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs Lamport 关于顺序一致性最早描述。
• jepsen.io 用于验证分布式数据库一致性的工具，包含了很多基本概念的介绍。