Casual Consistency | 因果一致性

如果 A 进程在更新之后向 B 进程通知更新的完成，那么 B 的访问操作将会返回更新的值。如果没有因果关系的 C 进程将会遵循最终一致性的规则。因果一致性(Casual Consistency)在一致性的要求上，又比顺序一致性降低了：它仅要求有因果关系的操作顺序得到保证，非因果关系的操作顺序则无所谓。

因果相关的要求是这样的：

• 本地顺序：本进程中，事件执行的顺序即为本地因果顺序。
• 异地顺序：如果读操作返回的是写操作的值，那么该写操作在顺序上一定在读操作之前。
• 闭包传递：和时钟向量里面定义的一样，如果 a->b，b->c，那么肯定也有 a->c。

• 图 a 满足顺序一致性，因此也满足因果一致性，因为从这个系统中的四个进程的角度看，它们都有相同的顺序也有相同的因果关系。

• 图 b 满足因果一致性但是不满足顺序一致性，这是因为从进程 P3、P4 看来，进程 P1、P2 上的操作因果有序，因为 P1、P2 上的写操作不存在因果关系，所以它们可以任意执行。不满足一致性的原因，同上面一样是可以推导出冲突的情况来。

顺序和因果

顺序反复出现有几个原因，其中一个原因是，它有助于保持因果关系（causality）。

• 一个对话的观察者首先看到问题的答案，然后才看到被回答的问题。这是令人困惑的，因为它违背了我们对因（cause）与果（effect）的直觉：如果一个问题被回答，显然问题本身得先在那里，因为给出答案的人必须看到这个问题（假如他们并没有预见未来的超能力）。我们认为在问题和答案之间存在因果依赖（causal dependency）。

• 三位领导者之间的复制，并注意到由于网络延迟，一些写入可能会“压倒”其他写入。从其中一个副本的角度来看，好像有一个对尚不存在的记录的更新操作。这里的因果意味着，一条记录必须先被创建，然后才能被更新。

• 在并发写入中，如果有两个操作 A 和 B，则存在三种可能性：A 发生在 B 之前，或 B 发生在 A 之前，或者 A 和 B 并发。这种此前发生（happened before）关系是因果关系的另一种表述：如果 A 在 B 前发生，那么意味着 B 可能已经知道了 A，或者建立在 A 的基础上，或者依赖于 A。如果 A 和 B 是并发的，那么它们之间并没有因果联系；换句话说，我们确信 A 和 B 不知道彼此。

• 在事务快照隔离的上下文中，我们说事务是从一致性快照中读取的。但此语境中“一致”到底又是什么意思？这意味着与因果关系保持一致（consistent with causality）：如果快照包含答案，它也必须包含被回答的问题。在某个时间点观察整个数据库，与因果关系保持一致意味着：因果上在该时间点之前发生的所有操作，其影响都是可见的，但因果上在该时间点之后发生的操作，其影响对观察者不可见。读偏差（read skew）意味着读取的数据处于违反因果关系的状态。

• 事务之间写偏差（write skew）的例子也说明了因果依赖：爱丽丝被允许离班，因为事务认为鲍勃仍在值班，反之亦然。在这种情况下，离班的动作因果依赖于对当前值班情况的观察。可序列化的快照隔离通过跟踪事务之间的因果依赖来检测写偏差。

• 在爱丽丝和鲍勃看球的例子中，在听到爱丽丝惊呼比赛结果后，鲍勃从服务器得到陈旧结果的事实违背了因果关系：爱丽丝的惊呼因果依赖于得分宣告，所以鲍勃应该也能在听到爱丽斯惊呼后查询到比分。

因果关系对事件施加了一种顺序：因在果之前；消息发送在消息收取之前。而且就像现实生活中一样，一件事会导致另一件事：某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。如果一个系统服从因果关系所规定的顺序，我们说它是因果一致（causally）的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

因果顺序不是全序的

全序（total order）允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。例如，自然数集是全序的：给定两个自然数，比如说 5 和 13，那么你可以告诉我，13 大于 5。然而数学集合并不完全是全序的：{a, b} 比 {b, c} 更大吗？好吧，你没法真正比较它们，因为二者都不是对方的子集。我们说它们是无法比较（incomparable）的，因此数学集合是偏序（partially order）的：在某些情况下，可以说一个集合大于另一个（如果一个集合包含另一个集合的所有元素），但在其他情况下它们是无法比较的。

全序和偏序之间的差异反映在不同的数据库一致性模型中：

• 线性一致性：在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。

• 因果性：如果两个操作都没有在彼此之前发生，那么这两个操作是并发的。换句话说，如果两个事件是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

因此，根据这个定义，在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。可能有几个请求在等待处理，但是数据存储确保了每个请求都是在唯一时间线上的某个时间点自动处理的，不存在任何并发。并发意味着时间线会分岔然后合并，在这种情况下，不同分支上的操作是无法比较的（即并发操作）。如果你熟悉像 Git 这样的分布式版本控制系统，那么其版本历史与因果关系图极其相似。通常，一个提交（Commit）发生在另一个提交之后，在一条直线上。但是有时你会遇到分支（当多个人同时在一个项目上工作时），合并（Merge）会在这些并发创建的提交相融合时创建。

线性一致性强于因果一致性

线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性。特别是，如果系统中有多个通信通道，线性一致性可以自动保证因果性，系统无需任何特殊操作（如在不同组件间传递时间戳）。线性一致性确保因果性的事实使线性一致系统变得简单易懂，更有吸引力。不过使系统线性一致可能会损害其性能和可用性，尤其是在系统具有严重的网络延迟的情况下（例如，如果系统在地理上散布）。出于这个原因，一些分布式数据系统已经放弃了线性一致性，从而获得更好的性能，但它们用起来也更为困难。

好消息是存在折衷的可能性。线性一致性并不是保持因果性的唯一途径，还有其他方法。一个系统可以是因果一致的，而无需承担线性一致带来的性能折损（尤其对于 CAP 定理不适用的情况）。实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型。而且在网络故障时仍能保持可用。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似。

捕获因果关系

为了维持因果性，你需要知道哪个操作发生在哪个其他操作之前（happened before）。这是一个偏序：并发操作可以以任意顺序进行，但如果一个操作发生在另一个操作之前，那它们必须在所有副本上以那个顺序被处理。因此，当一个副本处理一个操作时，它必须确保所有因果前驱的操作（之前发生的所有操作）已经被处理；如果前面的某个操作丢失了，后面的操作必须等待，直到前面的操作被处理完毕。

为了确定因果依赖，我们需要一些方法来描述系统中节点的“知识”。如果节点在发出写入 Y 的请求时已经看到了 X 的值，则 X 和 Y 可能存在因果关系。这个分析使用了那些在欺诈指控刑事调查中常见的问题：CEO 在做出决定 Y 时是否知道 X ？因果一致性需要跟踪整个数据库中的因果依赖，而不仅仅是一个键，可以推广版本向量以解决此类问题。为了确定因果顺序，数据库需要知道应用读取了哪个版本的数据。在 SSI 的冲突检测中会出现类似的想法，如可序列化的快照隔离（SSI）中所述：当事务要提交时，数据库将检查它所读取的数据版本是否仍然是最新的。为此，数据库跟踪哪些数据被哪些事务所读取。

案例分析

在 InfoQ 分享的腾讯朋友圈的设计中，他们在设计数据一致性的时候，使用了因果一致性这个模型。用于保证对同一条朋友圈的回复的一致性，比如这样的情况：

1. A 发了朋友圈内容为梅里雪山的图片。
2. B 针对内容 a 回复了评论：“这里是哪里？”
3. C 针对 B 的评论进行了回复：”这里是梅里雪山“。

那么，这条朋友圈的显示中，显然 C 针对 B 的评论，应该在 B 的评论之后，这是一个因果关系，而其他没有因果关系的数据，可以允许不一致。微信的做法是：

1. 每个数据中心，都自己生成唯一的、递增的数据 ID，确保能排重。在下图的示例中，有三个数据中心，数据中心 1 生成的数据 ID 模 1 为 0，数据中心 1 生成的数据 ID 模 2 为 0，数据中心 1 生成的数据 ID 模 3 为 0，这样保证了三个数据中心的数据 ID 不会重复全局唯一。

2. 每条评论都比本地看到所有全局 ID 大，这样来确保因果关系，这部分的原理前面提到的向量时钟一样。

有了这个模型和原理，就很好处理前面针对评论的评论的顺序问题了。

1. 假设 B 在数据中心 1 上，上面的 ID 都满足模 1 为 0，那么当 B 看到 A 的朋友圈时，发表了评论，此时给这个评论分配的 ID 是 1，因此 B 的时钟向量数据是[1]。

2. 假设 C 在数据中心 2 上，上面的 ID 都满足模 2 为 0，当 C 看到了 B 的评论时，针对这个评论做了评论，此时需要给这个评论分配的 ID 肯定要满足模 2 为 0 以及大于 1，评论完毕之后 C 上面的时钟向量是[1,2]。

3. 假设 A 在数据中心 3 上，上面的 ID 都满足模 3 为 0，当 A 看到 B、C 给自己的评论时，很容易按照 ID 进行排序和合并–即使 A 在收到 C 的数据[1,2]之后再收到 B 的数据[1]，也能顺利的完成合并。