条分缕析分布式：因果一致性和相对论时空

在上一篇文章《 条分缕析分布式：浅析强弱一致性 》中，我们重点讨论了顺序一致性、线性一致性和最终一致性这几个概念。本文我们将继续深入，详细探讨另一种一致性模型——因果一致性，并在这个过程中逐步逼近分布式系统最深层的事件排序的本质。沿着这个方向，如果我们走得稍微再远一点，就会触达我们所生活的这个宇宙的时空本质，以及因果律的本质（这才是真正有意思的地方，希望你能一口气读到最后）。

回到现实，《Designing Data-Intensive Applications》[1]一书的作者在他的书中提到，基于因果一致性构建分布式数据库系统，是未来一个非常有前景的研究方向。而且，估计很少有人注意到，我们经常使用的ZooKeeper，其实就在session维度上提供了因果一致性的保证[2]。理解「因果一致性」的概念，有助于我们对于分布式系统的认识更进一层。

结合 上一篇文章 的讨论，我们再把一致性模型的来历简单梳理一下。

早期的分布式系统设计者，为了让使用系统的开发者能够以比较简单的方式来使用系统，希望分布式系统能提供单一系统视图 (SSI， single-system image )[3]，即系统“表现得就好像只有一个单一的副本”。线性一致性和顺序一致性就是沿着这个思路设计的。满足线性一致性或顺序一致性的系统，对读写操作的排序呈现全局唯一的一种次序。

然而，系统为了维持这种全局排序的一致性是有成本的，必然需要在副本节点之间做很多通信和协调工作。这降低了系统的可用性（ availability ）和性能。于是，在一致性、可用性、系统性能之间进行权衡的结果，就是降低系统提供的一致性保障，转向了最终一致性[4]。

不过最终一致性提供的一致性保障是如此之弱，它放弃了所有的 safety 属性（具体讨论见 上一篇文章 ）。这给系统的使用带来了额外的困难。面向最终一致性系统进行编程，需要随时关注数据不一致的情况。加州大学伯克利分校在2013年发表了一篇非常不错的文章[3]，对于如何在最终一致性系统上构建应用，进行了非常深入的研究。文章指出了两种思路：

• 针对可能出现的数据不一致情况实施补偿措施 ( compensation )。这需要在分布式系统之上的应用层面进行额外的处理，是非常容易出错且费时费力的。

• 基于CALM定理和CRDTs，完全消除补偿操作。但这样做其实限制了应用编程能够使用的操作类型，也就限制了系统能力。

以上两种思路都涉及到了大量细节，我们不打算在这里深入讨论，有兴趣的读者可以仔细去阅读论文[3]。

总之，为了提高系统可用性和系统性能，人们放弃了强一致性，采取了几乎最弱的一类一致性模型（最终一致性），但也同时牺牲了系统的能力或系统使用的便利性。那么，到底有没有必要一定采取这么「弱」的一致性模型呢？有没有可能在最终一致性的基础上增加一点 safety 属性，提供稍强一点的一致性，但同时也不至于对系统可用性和性能产生明显的损害呢？

基于最新的研究，这是有可能的。这个问题的答案就是本文接下来要讨论的因果一致性 ( causal consistency )。

德克萨斯大学奥斯汀分校在2011年的一项研究表明[5]：

• 不存在比因果一致性更强的一致性模型，能够在网络分区的情况下仍然可用。

• 在一个永远保持可用且单程收敛 ( always-available, one-way convergent ) 的系统里，因果一致性是可以被实现出来的。

因果律是这个世界最基础的规律，物理法则决定了我们总是先看到事物的「因」，后看到事物的「果」。对于一个分布式系统来说，在数字世界中保持这种因果关系，当然也是一个最基本的要求。

为了能比较通俗地理解因果一致性，我们这里引用一个假想的实例（来自论文[6]）。假设Billy是一个小男孩，Sally是他的妈妈。下面的故事发生在一个类似Facebook的社交网站上：

1. 有一天，Billy失踪了。Sally找不到他的儿子，很着急，于是在社交网站上发布了一条状态：“我儿子Billy丢了！”

2. 过了一会，Sally突然接到了儿子的电话。Billy告诉妈妈，他跑到朋友家玩去了。Sally长出一口气，又重新修改了刚才发布的状态：“谢天谢地，虚惊一场！Billy原来是跑出去玩了。”

3. Sally的一个朋友，叫James，看到了她发的最新的状态，在社交网站上回复了她：“太好了，总算松了一口气！”

假如这家社交网站的数据库系统没能保证因果一致性，那么我们就可能看到比较奇怪的事件次序。假设Sally的另外一个朋友，叫Henry，也在浏览这个社交网站。可能由于系统延迟，数据还未收敛到一致的状态，Henry可能会看到Sally发的第一条状态和James的回复，但却看不到Sally发的第二条状态。于是，在Henry看来：

1. Sally说：“我儿子Billy丢了！”

2. James回复：“太好了，总算松了一口气！”

Henry可能会错误地认为，James满心希望Sally的儿子丢了（James肯定是恨透了Sally）！

之所以发生这样的问题，就是因为因果倒置了。考虑两个事件：事件A，Sally发布第二条状态（称自己的儿子找到了）；事件B，James回复Sally表示安慰。显然，事件B是由事件A引发的，也就是说，事件A是事件B的「因」，事件B是事件A的「果」。但在Henry看来，却只看到了事件B，没有看到事件A，这违反了因果规律。（当然，这个例子隐藏了很多具体实现细节，你可能会产生一些疑问，但不妨碍我们讨论事件的因果关系）

这里需要注意，如果分布式系统是满足线性一致性或者顺序一致性的，那么是不会发生这样的问题的。因为线性一致性和顺序一致性是能够保持因果关系的（下一章节我们还会继续讨论这个问题）。而只是满足最终一致性的系统，是没法总是保持因果关系的。但是，如果一个系统满足因果一致性，那么我们可以放心地认为，事件的因果关系是能够得到保证的。

现在，让我们来尝试对因果一致性进行定义。我们先采取一种不那么严格，但比较直观的说法（下个章节再进行精确定义）。因果一致性遵守下面三条规则：

1. 单进程写操作有序。

2. “writes follow reads”规则。

3. 因果关系可传递。

我们来分别解释一下：

1. 单进程写操作有序，指的是一个进程的多个写操作（可能是针对不同的数据对象的），在所有进程看来都是遵循同样的执行顺序。对应到前面的例子中，Sally的所有朋友都会看到，Sally是先发了一条状态“我儿子Billy丢了！”，然后又发了第二条状态“谢天谢地，虚惊一场！Billy原来是跑出去玩了。”这条规则保证了没有人是先看到第二条状态然后才看到第一条状态的。对于这个次序的保证也是因果性的一种体现。

2. “writes follow reads”指的是，假设第一个进程先读取到了数据对象 x=5 ，后写入了另一个数据对象 y=10 ，然后第二个进程读到了 y=10 ，那么接下来如果这个进程读取数据对象 x 的值，那么不能读到一个比 x=5 更旧的值。这条规则在不同进程的不同数据对象之间建立了因果关联。对应到前面的例子中，James看到了Sally发的最新状态：“谢天谢地，虚惊一场！Billy原来是跑出去玩了。”（相当于读到了 x=5 ），然后回复说：“太好了，总算松了一口气！”（相当于写入了 y=10 ），再然后Henry看到了James的回复内容（相当于第二个进程读到了 y=10 ），这时候站在Henry的视角上看Sally发布的状态，他不能比James看到的数据版本更旧。前面的例子中出现的问题就在于，Henry比James看到了更旧的一个数据版本：“我儿子Billy丢了！”，致使因果关系混乱了。

3. 因果关系是具有传递性的。如果操作A和操作B在因果关系上满足先后次序，而且操作B和操作C在因果关系上也满足先后次序，那么A和C在因果关系上必然是满足先后次序的。

在前一章节我们讨论了因果一致性的直观解释，但我们还需要一个精确的定义。这样对于一个具体的包含读写操作的并发执行过程来说，我们才能知道如何判定它是否满足因果一致性。

我们采用 上一篇文章 的表示方法，还是先通过一个例子来看一个并发执行过程，如下图：

图中线段上面的符号表示具体的读写操作：

• A --> w _i ( x )，表示一个写操作：第 i 个进程向数据对象 x 写入了值 A 。

• r _i ( x ) --> A ，表示一个读操作：第 i 个进程从数据对象 x 中读到了值 A 。

这个图表达了3个进程（ P ₁ 、 P ₂ 和 P ₃ ）对于数据存储的读写执行过程。它是否满足因果一致性呢？

跟线性一致性和顺序一致性的定义一样，因果一致性也是表达了系统对于读写操作的某种排序规则。为此我们首先需要定义清楚一个关键概念—— 因果顺序 (causality order)，它表明了两个不同操作之间的排序是怎样规定的。

因果顺序 的定义：如果两个操作 o ₁ 和 o ₂ 满足下面三个条件之一，那么它们就是满足因果顺序的，记为 o ₁ → o ₂ ：

• (1) o ₁ 和 o ₂ 属于同一个进程，且 o ₁ 在 o ₂ 前面执行。

• (2) o ₁ 是个写操作， o ₂ 是个读操作，且 o ₂ 读到的值是由 o ₁ 写入的。

• (3) 存在一个操作 o '满足 o ₁ → o '→ o ₂ 。

结合上图的例子，我们解释一下这三个条件：

• (1) 同一个进程内部先后执行的两个操作，不管他们是读操作还是写操作，都是满足因果顺序的。比如上图中 P ₁ 进程的 A --> w ₁ ( x ) 和 B --> w ₁ ( x ) 两个操作就是满足因果顺序的； P ₂ 进程的 r ₂ ( x ) --> B 和 C --> w ₂ ( y ) 也是满足因果顺序的。这一条件表明，因果顺序遵从了进程的执行顺序。

• (2) 如果一个读操作读到的值是由另一个写操作写入的（肯定是针对同一个数据对象），那么不管它们是不是属于同一个进程，这个写操作和读操作就是满足因果关系的。比如上图中的 B --> w ₁ ( x ) 和 r ₂ ( x ) --> B 就是满足因果顺序的； C --> w ₂ ( y ) 和 r ₃ ( y ) --> C 也是满足因果顺序的。这个条件反映了读写操作之间的因果依赖关系。

• (3) 这个条件表明因果顺序“→”满足传递关系 ( transitive relation )。

从因果顺序的定义中，我们还能得到两个重要的结论：

• 因果顺序是一种 偏序关系 。所谓偏序关系，就是说只有一部分操作是可以按照因果顺序进行比较的，而有一些操作之间是不能比较的。比如上图中的 A --> w ₁ ( x ) 和 D --> w ₃ ( x ) 这两个操作之间的关系，就不符合因果顺序三个条件中的任何一个。 r ₂ ( x ) --> B 和 D --> w ₃ ( x ) 之间也同样如此，它们之间不存在因果顺序。这具有很深刻的物理学和哲学内涵，因为现实世界的事件之间的因果关系就是偏序的（先不展开讨论）。分布式系统里对于读写操作之间的这种因果顺序的定义，正是对现实世界中这种现象的一种刻画。

• 因果顺序不能有循环依赖。假如操作 o ₁ → o ₂ → o '→...→ o ₁ ，由传递关系就应该有： o ₁ → o ₁ 。这表示一个操作是它自己的「因」，这是荒谬的。换句话说，如果把因果顺序用一个图来表示，那么它应该是一个有向无环图 ( directed acyclic graph )。

现在基于 因果顺序 的定义，我们可以给出 因果一致性 的定义了。

因果一致性 定义[7]：在一个并发执行过程中，站在其中任意一个进程 P _i 的视角上，考虑这个进程的所有读、写操作和所有其它进程的所有写操作（注意不包含读操作），得到一个操作序列。如果站在任意一个进程的视角上得到的这个操作序列都能够重排成一个线性有序的序列，并且该序列满足以下两个条件，那么这个并发执行过程就是满足因果一致性的：

• 条件I ：重排后的序列中每一个读操作返回的值，必须等于前面对同一个数据对象的最近一次写操作所写入的值。

• 条件II ：重排后的序列遵从前面定义的因果顺序“→”。

对比 上一篇文章 中的顺序一致性定义，因果一致性的定义有两个不同：

1. 顺序一致性是对所有进程的所有读写操作进行统一的重排，而因果一致性是站在每个进程的视角各自进行局部重排。这表示顺序一致性要求系统的所有进程都对操作排序达成一致的看法，而因果一致性允许每个进程对操作的排序有不同的看法。

2. 因果一致性与顺序一致性的 条件II 不同。顺序一致性的 条件II 只是要求遵从进程的执行顺序，而因果一致性则有更强的要求——遵从 因果顺序 （而进程的执行顺序只是因果顺序的一部分）。

以前面图示的并发执行过程为例，我们先以 P ₁ 的视角，需要考虑把 P ₁ 的所有读写操作和 P ₂ 、 P ₃ 的所有写操作进行重排，可以得到如下的有序序列：

1. D --> w ₃ ( x )

2. A --> w ₁ ( x )

3. B --> w ₁ ( x )

4. C --> w ₂ ( y )

再以 P ₂ 的视角，需要考虑把 P ₂ 的所有读写操作和 P ₁ 、 P ₃ 的所有写操作进行重排，可以得到如下的有序序列：

1. D --> w ₃ ( x )

2. A --> w ₁ ( x )

3. B --> w ₁ ( x )

4. r ₂ ( x ) --> B

5. C --> w ₂ ( y )

最后以 P ₃ 的视角，需要考虑把 P ₃ 的所有读写操作和 P ₁ 、 P ₃ 的所有写操作进行重排，可以得到如下的有序序列：

1. D --> w ₃ ( x )

2. A --> w ₁ ( x )

3. B --> w ₁ ( x )

4. C --> w ₂ ( y )

5. r ₃ ( y ) --> C

6. r ₃ ( x ) --> B

我们可以依次检查三个重排序列，会发现因果一致性的 条件I 和 条件II 都是满足的（留给读者自己去检查，有疑问可以在评论区回复），所以前面图中的并发执行过程是满足因果一致性的。