分布式系统一致性

说到『一致性』这个词，你首先想到了什么？

图1：CAP 定理趣图

是 ACID 中的 consistency? 还是 Raft 或者 Paxos 中的 consensus? 是 MESI cache 一致性协议中的 coherence? 亦或是 CAP Theory 中的 consistency?

不管你想到了其中的几个，你都不得不承认这些 consistency，coherence，consensus（实际应该是共识）『一致性』为每一个想要了解数据库、体系结构以及分布式系统的 newbie 造成了巨大的困扰。说到这里，你可能以为我们想通过这篇文章来深入地剖析上诉『一致性』的内在区别。其实不然，开门见山的说，此文及其后续的文章都聚焦于与 CAP Theory 中的 consistency 相关的、并行系统中不同的『一致性保证』。我们希望在讨论这个 consistency 的过程中，能顺便理解上述这些『一致性』定义所产生的背景和意义，从而更加精确地理解一些分布式系统设计中的考量。

分布式系统模型

准确地说，『一致性』的定义是基于并行系统的，而本文中所关注的分布式系统只是并行系统中的一部分。『分布式系统』应该如何定义，不同的人有不同的理解。Leslie Lamport 在 PODC 83 上面指出，广义上的『分布式系统』是一个相对的概念，同样的实体从不同的角度来看，可以既是非分布式（nondistributed）的，也可是分布式的；Andrew Tanenbaum 在他的书 Distributed Systems: Principles and Paradigms 中总结分布式系统为一个表现如单个计算机的由多个处理节点组成的系统；而 foldoc 上面的解释却认为，分布式系统与 network 有明显的区别，其对用户具有更高的透明度。

图2：典型的分布式系统

尽管这些理解和定义都从某个角度刻画了分布式系统的特征，但为了方便阐述与分布式系统相关理论，我们仍然需要为其建立一个简单而明确的模型：

分布式系统可以抽象为一个由多个完成相同目的的实体组成的集合，集合中的每个实体都具有 autonomous, programmable, asynchronous 以及 failure-prone 的特点；不同实体之间可以依赖底层通讯介质互相通讯.

这个定义将分布式系统归结成为两种不同的模型，即同步分布式模型(Synchronous Distributed System)和异步分布式模型(Asynchronous Distributed System)。同步分布式模型中的消息传递和节点的计算操作耗时均有限(bounded)，典型的如多处理器系统；而异步分布式模型中，节点可能无限执行某一步操作，或者由于传输媒介不可靠而产生无限的消息传输延迟，典型的如 Internet，数据中心，WAN 等。

一致性模型

正是由于分布式系统中多个实体或者多个备份的特点，才产生了一致性的概念。从字面意义上来说，『一致性』关注的是分布式系统中不同实体之间数据或者状态的一致程度；而从实际的角度来看，『一致性』其实反映了系统对 client 提供的服务所表现出的特征。因此，本文以及后文将从 client 的角度出发，来分析分布式系统中不同的一致性保证。

一般而言，分布式系统中的一致性按照从强到若可以分为四种：

1. Linearizability (Strong consistency or Atomic consistency)
2. Sequential consistency
3. Causal consistency
4. Eventual consistency

这篇文章主要讨论前两者，因果一致性涉及到逻辑时间的概念，而最终一致性与 CAP 定理紧密相连，我们将在以后的文章中再来讨论。

线性一致性 (Linearizability)

线性一致性又被称为强一致性或者原子一致性。Maurice P. Herlihy 与 Jeannette M. Wing 在 1987 年的论文[2]中形式化的给出了 Linearizability 的概念。这里我们不打算将论文中的定义重复一遍（实际上这篇论文的形式化并不难理解），而是从 client 的抽象角度来探索 Linearizability 究竟提供了什么样的一致性保证。有一点需要说明的是，原始论文中线性一致性是基于 single-object (e.g. queue, register) 以及 single-operation (e.g. read, write, enqueue, dequeue) 的模型来定义的。因此，如果我们要在任意的分布式系统中严谨地讨论 Linearizability，就需要将系统以某种方式归约到这个模型中。

以典型的分布式数据库为例，我们可以将整个分布式数据库作为单个的 object 来看待，如果该数据库支持线性一致性，那么 client 对于该数据库的单个读写操作就需要满足 Linearizability 相应的要求。考虑如下图的线程 P1 读写某个分布式数据库（横向表示时间）：

图3：线程读写

我们期望得到的结果是什么？显然，我们希望 read 操作读取到的 x 值是 write 操作最近写入的那个值 2。因此，Linearizability 实际上刻画了我们对于分布式系统的非常自然的期望：

• 每一个读操作都将返回『最近的写操作』（基于单一的实际时间）的值
• 对任何 client 的表现均一致

注意上面『基于单一的实际时间』这几个字，这表明读写的先后顺序是由一个统一的实际时间（例如某个钟）来决定的，而不由逻辑时间所决定。在此要求下，系统的表现就像按照某个实际的时间顺序来处理所有 client 的读写请求。这个描述看起来不是很好理解，我们通过例子来详细说明。假定 $Inv(X)$ 表示 $X$ 操作的起始， $Res(X)$ 表示 $X$ 操作的结束，横轴表示统一的时间，如下示例图显示了进程 P1 和 P2 的操作时序图：

图4：Linearizability 示例1

上图中，P1 和 P2 进程均先调用 W 操作写入，再调用 R 操作读取。从单个进程的角度来看，进程自身的读写操作在时间顺序下必定互不重叠；而从整体上看，P1 和 P2 的读写操作在时间上也与彼此互不重叠。因此在上图中，『最近的写操作』应该如何定义一目了然：离 P1 的读操作最近的写操作是 P2 调用 w 写；而离 P2 的读操作最近的写操作仍然是其自身的 w 写。

然而在真实的系统中，不同进程之间的并发读写操作必然会出现时间上的重叠，如下图所示：

图5：Linearizability 示例2

P2 进程的写操作与 P1 进程的读写操作均产生了重叠，针对这种情况下的读操作我们应该如何来定义『最近的写操作』？为了定义『最近』这个概念，我们需要承认一点，任何读操作或者写操作必然在 $Inv(X)$ 和 $Res(X)$ 之间的某一点生效，写操作生效点之后的读操作必定会读到该写操作的值。在此基础上，Linearizability 描述了系统应具备如下两点要求：

1. 对于所有的 client 而言，其表现得如同采用了某种顺序来串行地执行所有进程的读写操作；
2. 在这种顺序下，所有的读操作均能返回最近的写操作的值；

因此，我们可以为上图中的 P1 和 P2 找到一个合理的执行顺序：P1 先写 x，然后 P2 再写 x，之后 P1 在 P2 写操作生效点之后读出 x 值为 3，最后 P2 读出 x 的值也为3。这个顺序显然满足上述两点要求，也就满足 Linearizability。

再来看如下图中的场景，如果 P2 进程读出来的值也就是图中的 “?” 的值为 0，仔细想想当前的系统是否满足 Linearizability 的两条要求？

图6：Linearizability 示例3

答案显然是不满足的，因为你不可能找到一种序列来顺序的执行 P1，P2 以及 P3 的读写操作，使其得到上图中的结果。更直观点说，既然 P3 的读操作返回了 x 的值为 3，说明了 P3 的读操作是在 P1 的写操作生效点之后执行；而 P2 的第二个读操作在时序上在 P3 的读操作之后（no overlapping），因此 P2 的读操作返回 0 值必然不能满足 Linearizability 的要求。

不知道例子说到这儿，对于 Linearizability 你有没有一个感性的理解。如果有的话，赶紧趁热看一下 Herlihy 的论文就能彻底理解了。论文中也证明了 Linearizability 同时满足 Local(composable) 和 non-blocking 的特性，这部分也自行去看证明吧。抽象总结起来，Linearizability 要求系统表现的如同一个单一的副本，按照实际的时间顺序来串行的执行线程的读写操作，这也就是『线性』这个定义的由来。然而，满足线性一致性的系统不仅难于实现，更难于提供较高的性能。

最后说两点很多人都会错误表述的概念：

1. 关于线性性(Linearizability) 跟可序列化(Serialization) 的关系。这两者看起来似乎相同，然而却是完全不同的两个概念。可序列化(Serialization) 的定义来自于数据库领域，是针对事务的概念，描述对一组事务的执行效果等同于某种串行的执行，没有 ordering 的概念；而 Linearizability 来自于并行计算领域，描述了针对某种数据结构的操作所表现出的顺序特征。详细内容可以看 这里；
2. 关于使用 2PC 来保证线性一致性的说法。2PC 和 3PC 是分布式事务领域的概念，是用来实现分布式事务，而事务的存在主要是保证数据库本身的内部一致性。Linearizability 在前文强调过，是针对 single-object 以及 single-operation 的模型而定义。所以这种说法在描述上并不准确。关于如何实现 Linearizability，可以采用 Active Replication 或 Chain-replication 的系统模型。

顺序一致性 (Sequential consistency)

在 Herlihy & Wing 提出线性一致性之前，Lamport 早在 1979 年就提出了顺序一致性（Sequential consistency）的概念[3]：

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 上述的定义是基于 shared-memory multi-processor system 的。我们可以将这种系统理解成一个同步分布式模型，从而扩展该定义到分布式系统领域。

这个定义实际上对系统提出了两条访问共享对象时的约束：

1. 从单个处理器（线程或者进程）的角度上看，其指令的执行顺序以编程中的顺序为准；
2. 从所有处理器（线程或者进程）的角度上看，指令的执行保持一个单一的顺序；

约束 1 保证了单个进程的所有指令是按照程序中的顺序来执行；而约束 2 保证了所有的内存操作都是原子的或者说实时地。从编程者的角度，顺序一致性提供了如下图中的抽象。我们可以将共享内存看成一个服务台，而将多个进程看成是接受服务的排队队列：每个进程的内部的读写指令都是按照编程的顺序先来先『服务』，同时服务台在多个队列之间不断切换。

图7：编程者角度的线性一致性

我们仍然用一个例子来更加清楚地展示顺序一致性的概念。下图中横轴表示程序中的顺序（注意不再是时间序），观察如下的两种执行结果是否满足顺序一致性要求：

通过简单分析就可以发现，这两种情况我们都可以找到一个满足上述两个约束的执行顺序，即：P1 x.write(2) -> P1 x.write(3) -> P2 x.write(5) -> P1 x.read(5)，这表明其执行结果满足顺序一致性。

继续观察下述的执行结果，你能否找到一种执行顺序使其满足顺序一致性呢？

答案是：不能。不管你怎么安排这四个进程的读写操作，要使其既满足各自的编程顺序，又得到相应的执行结果是不可能的。不信你可以把这四个进程对应到上面图 7 中的实例，看看你有没有办法能够找到符合要求的顺序。如果系统的执行得到上图中的结果，我们可以充分的肯定该系统不满足线性一致性。

可以看到，相比于 linearizability，Sequential consistency 放松了一致性的要求。首先，其并不要求操作的执行顺序严格按照真实的时间序；其次，其对不同线程之间的读写操作执行先后没有任何要求，只需保证执行是原子性即可。最后说一点，CPU 体系结构中 Sequential consistency 的概念与我们前文中所介绍的 Hardware Memory Reordering 息息相关，这一部分的以后再找时间另说。

两者的比较

简单地总结一下两者如下表：

除了表中的这些明显的区别以外，论文[4] 对 linearizability 与 Sequential consistency 的性能做出了分析。这一部分内容暂时我还没有细看，先只能留个白了，待后续有时间好好读下论文再回来补上。

参考文献

[1] Time, Clocks, and the Ordering of Events in a Distributed System
[2] Linearizability: A Correctness Condition for Concurrent Objects
[3] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
[4] Sequential consistency vs linearizability

• Previous
  Lock-free 编程：A Case Study（下）
• Next
  C++ 模板特性之 SFINAE