Question

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

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

• 在 第 5 章 中我们看到，领导者在单主复制中的主要目的就是，在复制日志中确定 写入顺序（order of write） ——也就是从库应用这些写入的顺序。如果不存在一个领导者，则并发操作可能导致冲突（参阅 处理写入冲突 ）。
• 在 第 7 章 中讨论的 可序列化 ，是关于事务表现的像按 某种序列顺序（some sequential order） 执行的保证。它可以通过字面意义上地 序列顺序（serial order） 执行事务来实现，或者通过允许并行执行，同时防止序列化冲突来实现（通过锁或中止事务）。
• 在 第 8 章 讨论过的在分布式系统中使用时间戳和时钟（参阅 依赖于同步时钟 ）是另一种将顺序引入无序世界的尝试，例如，确定两个写入操作哪一个更晚发生。

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

顺序与因果

顺序 反复出现有几个原因，其中一个原因是，它有助于保持 因果关系（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） 的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

因果顺序不是全序的

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

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

^{译注 i}. 设 R 为非空集合 A 上的关系，如果 R 是自反的、反对称的和可传递的，则称 R 为 A 上的偏序关系。简称偏序，通常记作≦。一个集合 A 与 A 上的偏序关系 R 一起叫作偏序集，记作$(A,R)$或$(A, ≦)$。全序、偏序、关系、集合，这些概念的精确定义可以参考任意一本离散数学教材。 ↩

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

线性一致性

​ 在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。这个全序 图 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 的冲突检测中会出现类似的想法，如 可序列化的快照隔离（SSI） 中所述：当事务要提交时，数据库将检查它所读取的数据版本是否仍然是最新的。为此，数据库跟踪哪些数据被哪些事务所读取。

序列号顺序

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

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

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

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

^vii. 与因果关系不一致的全序很容易创建，但没啥用。例如你可以为每个操作生成随机的 UUID，并按照字典序比较 UUID，以定义操作的全序。这是一个有效的全序，但是随机的 UUID 并不能告诉你哪个操作先发生，或者操作是否为并发的。 ↩

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

非因果序列号生成器

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

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

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

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

• 每个节点每秒可以处理不同数量的操作。因此，如果一个节点产生偶数序列号而另一个产生奇数序列号，则偶数计数器可能落后于奇数计数器，反之亦然。如果你有一个奇数编号的操作和一个偶数编号的操作，你无法准确地说出哪一个操作在因果上先发生。
• 来自物理时钟的时间戳会受到时钟偏移的影响，这可能会使其与因果不一致。例如 图 8-3 展示了一个例子，其中因果上晚发生的操作，却被分配了一个更早的时间戳。^vii

  ^viii. 可以使物理时钟时间戳与因果关系保持一致：在 用于全局快照的同步时钟 中，我们讨论了 Google 的 Spanner，它可以估计预期的时钟偏差，并在提交写入之前等待不确定性间隔。 这中方法确保了实际上靠后的事务会有更大的时间戳。 但是大多数时钟不能提供这种所需的不确定性度量。 ↩

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

兰伯特时间戳

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

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

图 9-8 Lamport 时间戳提供了与因果关系一致的总排序。

​ 兰伯特时间戳与物理时间时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则 计数器 值大者是更大的时间戳。如果计数器值相同，则节点 ID 越大的，时间戳越大。

​ 迄今，这个描述与上节所述的奇偶计数器基本类似。使兰伯特时间戳因果一致的关键思想如下所示：每个节点和每个客户端跟踪迄今为止所见到的最大 计数器 值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

​ 这如 图 9-8 所示，其中客户端 A 从节点 2 接收计数器值 5 ，然后将最大值 5 发送到节点 1 。此时，节点 1 的计数器仅为 1 ，但是它立即前移至 5 ，所以下一个操作的计数器的值为 6 。

​ 只要每一个操作都携带着最大计数器值，这个方案确保兰伯特时间戳的排序与因果一致，因为每个因果依赖都会导致时间戳增长。

​ 兰伯特时间戳有时会与我们在 检测并发写入 中看到的版本向量相混淆。虽然两者有一些相似之处，但它们有着不同的目的：版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序。从兰伯特时间戳的全序中，你无法分辨两个操作是并发的还是因果依赖的。 兰伯特时间戳优于版本向量的地方是，它更加紧凑。

光有时间戳排序还不够

​ 虽然兰伯特时间戳定义了一个与因果一致的全序，但它还不足以解决分布式系统中的许多常见问题。

​ 例如，考虑一个需要确保用户名能唯一标识用户帐户的系统。如果两个用户同时尝试使用相同的用户名创建帐户，则其中一个应该成功，另一个应该失败。 （我们之前在 领导者与锁定 中提到过这个问题。）

​ 乍看之下，似乎操作的全序关系足以解决这一问题（例如使用兰伯特时间戳）：如果创建了两个具有相同用户名的帐户，选择时间戳较小的那个作为胜者（第一个抓到用户名的人），并让带有更大时间戳者失败。由于时间戳上有全序关系，所以这个比较总是可行的。

​ 这种方法适用于事后确定胜利者：一旦你收集了系统中的所有用户名创建操作，就可以比较它们的时间戳。然而当某个节点需要实时处理用户创建用户名的请求时，这样的方法就无法满足了。节点需要 马上（right now） 决定这个请求是成功还是失败。在那个时刻，节点并不知道是否存其他节点正在并发执行创建同样用户名的操作，罔论其它节点可能分配给那个操作的时间戳。

​ 为了确保没有其他节点正在使用相同的用户名和较小的时间戳并发创建同名账户，你必须检查其它每个节点，看看它在做什么【56】。如果其中一个节点由于网络问题出现故障或不可达，则整个系统可能被拖至停机。这不是我们需要的那种容错系统。

​ 这里的问题是，只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

​ 总之：为了实诸如如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定。如果你有一个创建用户名的操作，并且确定在全序中，没有任何其他节点可以在你的操作之前插入对同一用户名的声称，那么你就可以安全地宣告操作执行成功。

​ 如何知道你的全序关系已经尘埃落定，这个想法将在 全序广播 一节中详细说明。

全序广播

​ 如果你的程序只运行在单个 CPU 核上，那么定义一个操作全序是很容易的：可以简单地就是 CPU 执行这些操作的顺序。但是在分布式系统中，让所有节点对同一个全局操作顺序达成一致可能相当棘手。在上一节中，我们讨论了按时间戳或序列号进行排序，但发现它还不如单主复制给力（如果你使用时间戳排序来实现唯一性约束，而且不能容忍任何错误）。

​ 如前所述，单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个 CPU 核上对所有操作进行排序。接下来的挑战是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（ 处理节点宕机 ），如何处理故障转移。在分布式系统文献中，这个问题被称为 全序广播（total order broadcast） 或 原子广播（atomic broadcast）^ix 【25,57,58】。

^ix. 原子广播 是一个传统的术语，非常混乱，而且与 原子 一词的其他用法不一致：它与 ACID 事务中的原子性没有任何关系，只是与原子操作（在多线程编程的意义上 ）或原子寄存器（线性一致存储）有间接的联系。全序广播是另一个同义词。 ↩

顺序保证的范围

每个分区各有一个主库的分区数据库，通常只在每个分区内维持顺序，这意味着它们不能提供跨分区的一致性保证（例如，一致性快照，外键引用）。 跨所有分区的全序是可能的，但需要额外的协调【59】。

全序广播通常被描述为在节点间交换消息的协议。 非正式地讲，它要满足两个安全属性：

可靠交付（reliable delivery）

​ 没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

全序交付（totally ordered delivery）

​ 消息以相同的顺序传递给每个节点。

正确的全序广播算法必须始终保证可靠性和有序性，即使节点或网络出现故障。当然在网络中断的时候，消息是传不出去的，但是算法可以不断重试，以便在网络最终修复时，消息能及时通过并送达（当然它们必须仍然按照正确的顺序传递）。

使用全序广播

​ 像 ZooKeeper 和 etcd 这样的共识服务实际上实现了全序广播。这一事实暗示了全序广播与共识之间有着紧密联系，我们将在本章稍后进行探讨。

​ 全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟）。这个原理被称为 状态机复制（state machine replication） 【60】，我们将在 第 11 章 中重新回到这个概念。

​ 与之类似，可以使用全序广播来实现可序列化的事务：如 真的串行执行 中所述，如果每个消息都表示一个确定性事务，以存储过程的形式来执行，且每个节点都以相同的顺序处理这些消息，那么数据库的分区和副本就可以相互保持一致【61】。

​ 全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将（先前）消息插入顺序中的较早位置。这个事实使得全序广播比时间戳命令更强。

​ 考量全序广播的另一种方式是，这是一种创建日志的方式（如在复制日志，事务日志或预写式日志中）：传递消息就像附加写入日志。由于所有节点必须以相同的顺序传递相同的消息，因此所有节点都可以读取日志，并看到相同的消息序列。

​ 全序广播对于实现提供防护令牌的锁服务也很有用（参见 防护令牌 ）。每个获取锁的请求都作为一条消息追加到日志末尾，并且所有的消息都按它们在日志中出现的顺序依次编号。序列号可以当成防护令牌用，因为它是单调递增的。在 ZooKeeper 中，这个序列号被称为 zxid 【15】。

使用全序广播实现线性一致的存储

​ 如 图 9-4 所示，在线性一致的系统中，存在操作的全序。这是否意味着线性一致与全序广播一样？不尽然，但两者之间有者密切的联系^x 。

^x. 从形式上讲，线性一致读写寄存器是一个 更容易 的问题。 全序广播等价于共识【67】，而共识问题在异步的崩溃-停止模型【68】中没有确定性的解决方案，而线性一致的读写寄存器 可以 在这种模型中实现【23,24,25】。 然而，支持诸如 比较并设置（CAS, compare-and-set） ，或 自增并返回（increment-and-get） 的原子操作使它等价于共识问题【28】。 因此，共识问题与线性一致寄存器问题密切相关。 ↩

​ 全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息 何时 被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

​ 但如果有了全序广播，你就可以在此基础上构建线性一致的存储。例如，你可以确保用户名能唯一标识用户帐户。

​ 设想对于每一个可能的用户名，你都可以有一个带有 CAS 原子操作的线性一致寄存器。每个寄存器最初的值为空值（表示不使用用户名）。当用户想要创建一个用户名时，对该用户名的寄存器执行 CAS 操作，在先前寄存器值为空的条件，将其值设置为用户的账号 ID。如果多个用户试图同时获取相同的用户名，则只有一个 CAS 操作会成功，因为其他用户会看到非空的值（由于线性一致性）。

你可以通过将全序广播当成仅追加日志【62,63】的方式来实现这种线性一致的 CAS 操作：

1. 在日志中追加一条消息，试探性地指明你要声明的用户名。
2. 读日志，并等待你所附加的信息被回送。^xi
3. 检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就你自己的消息，那么你就成功了：你可以提交声称的用户名（也许是通过向日志追加另一条消息）并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作。

^xi. 如果你不等待，而是在消息入队之后立即确认写入，则会得到类似于多核 x86 处理器内存的一致性模型【43】。 该模型既不是线性一致的也不是顺序一致的。 ↩

​ 由于日志项是以相同顺序送达至所有节点，因此如果有多个并发写入，则所有节点会对最先到达者达成一致。选择冲突写入中的第一个作为胜利者，并中止后来者，以此确定所有节点对某个写入是提交还是中止达成一致。类似的方法可以在一个日志的基础上实现可序列化的多对象事务【62】。

​ 尽管这一过程保证写入是线性一致的，但它并不保证读取也是线性一致的 —— 如果你从与日志异步更新的存储中读取数据，结果可能是陈旧的。 （精确地说，这里描述的过程提供了 顺序一致性（sequential consistency） 【47,64】，有时也称为 时间线一致性（timeline consistency） 【65,66】，比线性一致性稍微弱一些的保证）。为了使读取也线性一致，有几个选项：

• 你可以通过追加一条消息，当消息回送时读取日志，执行实际的读取。消息在日志中的位置因此定义了读取发生的时间点。 （etcd 的法定人数读取有些类似这种情况【16】。）
• 如果日志允许以线性一致的方式获取最新日志消息的位置，则可以查询该位置，等待直到该位置前的所有消息都传达到你，然后执行读取。 （这是 Zookeeper sync() 操作背后的思想【15】）。
• 你可以从同步更新的副本中进行读取，因此可以确保结果是最新的。 （这种技术用于链式复制【63】；参阅 复制研究 。）

使用线性一致性存储实现全序广播

​ 上一节介绍了如何从全序广播构建一个线性一致的 CAS 操作。我们也可以把它反过来，假设我们有线性一致的存储，接下来会展示如何在此基础上构建全序广播。

​ 最简单的方法是假设你有一个线性一致的寄存器来存储一个整数，并且有一个原子 自增并返回 操作【28】。或者原子 CAS 操作也可以完成这项工作。

​ 该算法很简单：每个要通过全序广播发送的消息首先对线性一致寄存器执行 自增并返回 操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收件人将按序列号连续发送消息。

​ 请注意，与兰伯特时间戳不同，通过自增线性一致性寄存器获得的数字形式上是一个没有间隙的序列。因此，如果一个节点已经发送了消息 4 并且接收到序列号为 6 的传入消息，则它知道它在传递消息 6 之前必须等待消息 5 。兰伯特时间戳则与之不同 —— 事实上，这是全序广播和时间戳排序间的关键区别。

​ 实现一个带有原子性 自增并返回 操作的线性一致寄存器有多困难？像往常一样，如果事情从来不出差错，那很容易：你可以简单地把它保存在单个节点内的变量中。问题在于处理当该节点的网络连接中断时的情况，并在该节点失效时能恢复这个值【59】。一般来说，如果你对线性一致性的序列号生成器进行深入过足够深入的思考，你不可避免地会得出一个共识算法。

​ 这并非巧合：可以证明，线性一致的 CAS（或自增并返回）寄存器与全序广播都都等价于 共识 问题【28,67】。也就是说，如果你能解决其中的一个问题，你可以把它转化成为其他问题的解决方案。这是相当深刻和令人惊讶的洞察！

现在是时候正面处理共识问题了，我们将在本章的其余部分进行讨论。