老规矩，枯燥乏味的论文，需要精神支持，先给兄弟们上图，缓解疲劳。

这个问题不仅仅是单主复制和多主复制的后果：任何线性一致的数据库都有这个问题，不管它是如何实现的。这个问题也不仅仅局限于多数据中心部署，而可能发生在任何不可靠的网络上，即使在同一个数据中心内也是如此。问题面临的权衡如下：5

• 如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误。（无论哪种方式，服务都 不可用）。

• 如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求（例如多主复制）。在这种情况下，应用可以在网络问题解决前保持可用，但其行为不是线性一致的。

因此，不需要线性一致性的应用对网络问题有更强的容错能力。这种见解通常被称为 CAP 定理【29,30,31,32】，由 Eric Brewer 于 2000 年命名，尽管 70 年代的分布式数据库设计者早就知道了这种权衡【33,34,35,36】。

CAP 最初是作为一个经验法则提出的，没有准确的定义，目的是开始讨论数据库的权衡。那时候许多分布式数据库侧重于在共享存储的集群上提供线性一致性的语义【18】，CAP 定理鼓励数据库工程师向分布式无共享系统的设计领域深入探索，这类架构更适合实现大规模的网络服务【37】。对于这种文化上的转变，CAP 值得赞扬 —— 它见证了自 00 年代中期以来新数据库的技术爆炸（即 NoSQL）。

顺序保证

之前说过，线性一致寄存器的行为就好像只有单个数据副本一样，且每个操作似乎都是在某个时间点以原子性的方式生效的。这个定义意味着操作是按照某种良好定义的顺序执行的。我们将操作以看上去被执行的顺序连接起来，以此说明了 图 9-4 中的顺序。

顺序（ordering） 这一主题在本书中反复出现，这表明它可能是一个重要的基础性概念。让我们简要回顾一下其它曾经出现过 顺序 的上下文：

• 在 第五章 中我们看到，领导者在单主复制中的主要目的就是，在复制日志中确定 写入顺序（order of write）—— 也就是从库应用这些写入的顺序。如果不存在一个领导者，则并发操作可能导致冲突（请参阅 “处理写入冲突”）。

• 在 第七章 中讨论的 可串行化，是关于事务表现的像按 某种先后顺序（some sequential order） 执行的保证。它可以字面意义上地以 串行顺序（serial order） 执行事务来实现，或者允许并行执行，但同时防止序列化冲突来实现（通过锁或中止事务）。

• 在 第八章 讨论过的在分布式系统中使用时间戳和时钟（请参阅 “依赖同步时钟”）是另一种将顺序引入无序世界的尝试，例如，确定两个写入操作哪一个更晚发生。

事实证明，顺序、线性一致性和共识之间有着深刻的联系。尽管这个概念比本书其他部分更加理论化和抽象，但对于明确系统的能力范围（可以做什么和不可以做什么）而言是非常有帮助的。我们将在接下来的几节中探讨这个话题。

顺序与因果关系

顺序 反复出现有几个原因，其中一个原因是，它有助于保持 因果关系（causality）。在本书中我们已经看到了几个例子，其中因果关系是很重要的：

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

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

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

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

• 事务之间 写偏差（write skew） 的例子（请参阅 “写入偏差与幻读”）也说明了因果依赖：在 图 7-8 中，爱丽丝被允许离班，因为事务认为鲍勃仍在值班，反之亦然。在这种情况下，离班的动作因果依赖于对当前值班情况的观察。可串行化快照隔离 通过跟踪事务之间的因果依赖来检测写偏差。

• 在爱丽丝和鲍勃看球的例子中（图 9-1），在听到爱丽丝惊呼比赛结果后，鲍勃从服务器得到陈旧结果的事实违背了因果关系：爱丽丝的惊呼因果依赖于得分宣告，所以鲍勃应该也能在听到爱丽斯惊呼后查询到比分。相同的模式在 “跨信道的时序依赖” 一节中，以 “图像大小调整服务” 的伪装再次出现。

因果关系对事件施加了一种 顺序：因在果之前；消息发送在消息收取之前。而且就像现实生活中一样，一件事会导致另一件事：某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。

如果一个系统服从因果关系所规定的顺序，我们说它是 因果一致（causally consistent） 的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

因果顺序不是全序的

全序（total order） 允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。例如，自然数集是全序的：给定两个自然数，比如说 5 和 13，那么你可以告诉我，13 大于 5。

然而数学集合并不完全是全序的：{a, b} 比 {b, c} 更大吗？好吧，你没法真正比较它们，因为二者都不是对方的子集。我们说它们是 无法比较（incomparable） 的，因此数学集合是 偏序的（partially ordered） ：在某些情况下，可以说一个集合大于另一个（如果一个集合包含另一个集合的所有元素），但在其他情况下它们是无法比较的 7。

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

• 线性一致性

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

• 因果性

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

因此，根据这个定义，在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。可能有几个请求在等待处理，但是数据存储确保了每个请求都是在唯一时间线上的某个时间点自动处理的，不存在任何并发。

并发意味着时间线会分岔然后合并 —— 在这种情况下，不同分支上的操作是无法比较的（即并发操作）。在 第五章 中我们看到了这种现象：例如，图 5-14 并不是一条直线的全序关系，而是一堆不同的操作并发进行。图中的箭头指明了因果依赖 —— 操作的偏序。

如果你熟悉像 Git 这样的分布式版本控制系统，那么其版本历史与因果关系图极其相似。通常，一个 提交（Commit） 发生在另一个提交之后，在一条直线上。但是有时你会遇到分支（当多个人同时在一个项目上工作时），合并（Merge） 会在这些并发创建的提交相融合时创建。

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

那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性 隐含着（implies） 因果关系：任何线性一致的系统都能正确保持因果性【7】。特别是，如果系统中有多个通信通道（如 图 9-5 中的消息队列和文件存储服务），线性一致性可以自动保证因果性，系统无需任何特殊操作（如在不同组件间传递时间戳）。

线性一致性确保因果性的事实使线性一致系统变得简单易懂，更有吸引力。然而，正如 “线性一致性的代价” 中所讨论的，使系统线性一致可能会损害其性能和可用性，尤其是在系统具有严重的网络延迟的情况下（例如，如果系统在地理上散布）。出于这个原因，一些分布式数据系统已经放弃了线性一致性，从而获得更好的性能，但它们用起来也更为困难。

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

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

这方面的研究相当新鲜，其中很多尚未应用到生产系统，仍然有不少挑战需要克服【52,53】。但对于未来的系统而言，这是一个有前景的方向。

捕获因果关系

我们不会在这里讨论非线性一致的系统如何保证因果性的细节，而只是简要地探讨一些关键的思想。

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

为了确定因果依赖，我们需要一些方法来描述系统中节点的 “知识”。如果节点在发出写入 Y 的请求时已经看到了 X 的值，则 X 和 Y 可能存在因果关系。这个分析使用了那些在欺诈指控刑事调查中常见的问题：CEO 在做出决定 Y 时是否 知道 X ？

用于确定 哪些操作发生在其他操作之前 的技术，与我们在 “检测并发写入” 中所讨论的内容类似。那一节讨论了无领导者数据存储中的因果性：为了防止丢失更新，我们需要检测到对同一个键的并发写入。因果一致性则更进一步：它需要跟踪整个数据库中的因果依赖，而不仅仅是一个键。可以推广版本向量以解决此类问题【54】。

为了确定因果顺序，数据库需要知道应用读取了哪个版本的数据。这就是为什么在 图 5-13 中，来自先前操作的版本号在写入时被传回到数据库的原因。在 SSI 的冲突检测中会出现类似的想法，如 “可串行化快照隔离” 中所述：当事务要提交时，数据库将检查它所读取的数据版本是否仍然是最新的。为此，数据库跟踪哪些数据被哪些事务所读取。

序列号顺序

虽然因果是一个重要的理论概念，但实际上跟踪所有的因果关系是不切实际的。在许多应用中，客户端在写入内容之前会先读取大量数据，我们无法弄清写入因果依赖于先前全部的读取内容，还是仅包括其中一部分。显式跟踪所有已读数据意味着巨大的额外开销。

但还有一个更好的方法：我们可以使用 序列号（sequence number） 或 时间戳（timestamp） 来排序事件。时间戳不一定来自日历时钟（或物理时钟，它们存在许多问题，如 “不可靠的时钟” 中所述）。它可以来自一个 逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

这样的序列号或时间戳是紧凑的（只有几个字节大小），它提供了一个全序关系：也就是说每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大（即哪些操作后发生）。

特别是，我们可以使用 与因果一致（consistent with causality） 的全序来生成序列号 8：我们保证，如果操作 A 因果地发生在操作 B 前，那么在这个全序中 A 在 B 前（ A 具有比 B 更小的序列号）。并行操作之间可以任意排序。这样一个全序关系捕获了所有关于因果的信息，但也施加了一个比因果性要求更为严格的顺序。

在单主复制的数据库中（请参阅 “领导者与追随者”），复制日志定义了与因果一致的写操作。主库可以简单地为每个操作自增一个计数器，从而为复制日志中的每个操作分配一个单调递增的序列号。如果一个从库按照它们在复制日志中出现的顺序来应用写操作，那么从库的状态始终是因果一致的（即使它落后于领导者）。

非因果序列号生成器

如果主库不存在（可能因为使用了多主数据库或无主数据库，或者因为使用了分区的数据库），如何为操作生成序列号就没有那么明显了。在实践中有各种各样的方法：

• 每个节点都可以生成自己独立的一组序列号。例如有两个节点，一个节点只能生成奇数，而另一个节点只能生成偶数。通常，可以在序列号的二进制表示中预留一些位，用于唯一的节点标识符，这样可以确保两个不同的节点永远不会生成相同的序列号。可以将日历时钟（物理时钟）的时间戳附加到每个操作上【55】。这种时间戳并不连续，但是如果它具有足够高的分辨率，那也许足以提供一个操作的全序关系。这一事实应用于 最后写入胜利 * 的冲突解决方法中（请参阅 “有序事件的时间戳”）。

• 可以预先分配序列号区块。例如，节点 A 可能要求从序列号 1 到 1,000 区块的所有权，而节点 B 可能要求序列号 1,001 到 2,000 区块的所有权。然后每个节点可以独立分配所属区块中的序列号，并在序列号告急时请求分配一个新的区块。

这三个选项都比单一主库的自增计数器表现要好，并且更具可伸缩性。它们为每个操作生成一个唯一的，近似自增的序列号。然而它们都有同一个问题：生成的序列号与因果不一致。

因为这些序列号生成器不能正确地捕获跨节点的操作顺序，所以会出现因果关系的问题：

• 每个节点每秒可以处理不同数量的操作。因此，如果一个节点产生偶数序列号而另一个产生奇数序列号，则偶数计数器可能落后于奇数计数器，反之亦然。如果你有一个奇数编号的操作和一个偶数编号的操作，你无法准确地说出哪一个操作在因果上先发生。

• 来自物理时钟的时间戳会受到时钟偏移的影响，这可能会使其与因果不一致。例如 图 8-3 展示了一个例子，其中因果上晚发生的操作，却被分配了一个更早的时间戳。8

• 在分配区块的情况下，某个操作可能会被赋予一个范围在 1,001 到 2,000 内的序列号，然而一个因果上更晚的操作可能被赋予一个范围在 1 到 1,000 之间的数字。这里序列号与因果关系也是不一致的。

兰伯特时间戳

尽管刚才描述的三个序列号生成器与因果不一致，但实际上有一个简单的方法来产生与因果关系一致的序列号。它被称为兰伯特时间戳，莱斯利・兰伯特（Leslie Lamport）于 1978 年提出【56】，现在是分布式系统领域中被引用最多的论文之一。

图 9-8 说明了兰伯特时间戳的应用。每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。兰伯特时间戳就是两者的简单组合：（计数器，节点 ID）$(counter, node ID)$。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点 ID，每个时间戳都是唯一的。