DDIA：分布式系统最重要的事情——“顺序”和“因果”

木鸟杂记

发布于 2023-11-27 18:31:13

5240

DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 在这里[1]。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

我们之前提到，一个线性化的寄存器对外表现得像：

数据只有一个副本
（施加于数据上的）操作原子的完成

该定义暗含着：所有操作会形成一个确定的执行顺序。在图 9-4 中，我们就根据读到的结果来推测出了一个服务器端所有操作的看起来的执行顺序。

顺序（ordering）是本书中不断强调的一个主题，这也确实说明顺序是一个非常重要的基础概念。我们回忆一下本书所提到顺序的相关上下文：

在第五章[2]，我们在单主模型中提到，主副本最重要的作用就是确定复制日志（replication log）中的写入顺序（order of writes），然后所有从副本都要遵从该顺序。如果不存在唯一的主节点作为权威来协调该顺序，则在并发的多个写入可能会产生冲突。（参见处理写入冲突[3]）
在第七章[4]，我们讨论了可串行化（serializability），即保证所有并发的事务像以某种顺序一样串行执行（some sequential order）。可以通过物理上真的串行执行来实现，也可以通过并发执行但解决冲突（加锁互斥或者抛弃执行）来实现。
在第八章[5]，我们讨论了在分布式系统中使用时钟（参见依赖同步时钟)，这也是一个试图对无序的真实世界引入某种顺序，以解决诸如哪个写入更靠后之类的问题。

顺序性（ordering）、线性一致性（linearizability）和共识协议（consensus）三个概念间有很深的联系。相比本书其他部分，尽管这几个概念更偏理论和抽象，但理解他们却有助于来厘清系统的功能边界——哪些可以做，哪些做不了。在接下来的几小节中，我们会对此进行详细探讨。

顺序和因果（Ordering and Causality）

顺序在本书中反复被提及的原因有很多，其中一个是：它可以维持因果性。关于因果关系的重要性，本书也举过很多例子：

在一致前缀读中我们提到一个先看到答案、后看到问题的例子。这种现象看起来很奇怪，是因为它违反了我们关于因果顺序的直觉：问题应该先于答案出现。因为只有看到了问题，才可能针对其给出答案（假设这不是超自然现象，并且不能预言将来）。对于这种情况，我们说在问题和答案之间存在着因果依赖（causal dependency）。
在第五章图 5-9 中有类似的情况，在有三个主的情况下，由于网络延迟，一些本应该先到的写入操作却居于后面。从某个副本的角度观察，就感觉像在更新一个不存在的数据。因果在此处意味着，某一行数据只有先被创建才能够被更新。
在并发写入检测一节我们知道，对于两个操作 A 和 B，有三种可能性：A 发生于 B 之前，B 发生于 A 之前，A 和 B 是并发的。这种发生于之前（happened before）是因果性的另一种表现：如果 A 发生在 B 之前，则 B 有可能知道 A，进而基于 A 构建，或者说依赖于 A。如果 A 和 B 是并发的，则他们之间没有因果联系，也即，我们可以断定他们互不知道。
在事务的快照隔离级别下（参见快照隔离和重复读），所有的读取都会发生在某个一致性的快照上。这里的一致性是什么意思呢？是因果一致性（consistent with causality）。如果一个快照包含某个问题答案，它一定包含该问题本身。假设我们以上帝视角，在某个时间点（意味着瞬时观察完）观察整个数据库可以让得到的快照满足因果一致性：所有在该时间点之前操作结果都可见，在该时间点之后的操作结果都不可见。读偏序（Read skew，即图 7-6 中提到的不可重复读），即意味读到了违反因果关系的状态。
之前提到的事务间的写偏序的例子（参见写偏序和幻读）本质上也是因果依赖：在图 7-8 中，系统允许 Alice 请假，是因为事务看到的 Bob 的状态是仍然再岗；当然，对于 Bob 也同样。在这个例子中，一个医生是否允许在值班时请假，依赖于当时是否仍有其他医生值班。在可串行的快照隔离级别（SSI，参见可串行的快照隔离) 下，我们通过追踪事务间的因果依赖（即读写数据集依赖）来检测写偏序。
在 Alice 和 Bob 看足球比赛的例子中，Bob 在 Alice 表示结果已经出来之后，仍然没有看到网页结果，便是违反了因果关系：Alice 的说法基于比赛结果已经出来的事实，因此 Bob 在听到 Alice 的陈述之后，应该当能看到比赛结果。图片尺寸调整的例子也是类似。

因果将顺序施加于事件（event）：

先有因，后有果
先有消息发送，然后该消息被收到
先有问题，后有答案

这和现实生活一样，一件事的发生会引起另一件的事的出现：一个节点读取数据之后，依据读取内容，（依赖于读取）写入了一些数据；另一个节点读取这些写入，进而写入了另外一些数据，循环往复。操作（operation）发生的依赖链条定义了系统中事件的因果——也即，谁居先，谁处后。

如果一个系统遵循因果约束，则我们称其为因果一致的（_causally consistent_）。比如，快照隔离就可以提供因果一致性：当从数据库读取数据的时候，如果你能读到某个时间点的数据，就一定能读到其之前的数据（当然，要在该数据还没有被删除的情况下）。

因果序非全序

全序（total order）意味着系统内任意两个元素可比大小。如，自然数是全序：任举两个自然数，比如 5 和 13，我们可以确定 13 是比 5 大的。但与此相对，数学中的集合就不是全序的，比如我们无从比较 {a, b} 和 {b, c} 的大小关系，因为他们互不为对方子集。对于这种情况，我们称其不可比（incomparable）。反之，集合是偏序（partially ordered）：在某些情况下，我们可以说一个集合比另一个集合大（两个集合间有包含关系）；但在另外一些情况下，两个集合间没有可比关系。

全序和偏序的区别还反应在不同强度数据库一致性模型（database consistency models）上：

线性一致性（Linearizability）：让我们回忆下对于可线性化的理解，可线性化对外表现的像所有操作都发生于单副本上，并且会原子性的完成。这就意味着，对于任意两个操作，我们总是可以确定其发生的先后关系，也即在可线性化系统中，所有的操作顺序满足全序关系。如之前图 9-4 中给的例子。
因果一致性（Causality）。如果我们无从判定两个操作的先后关系，则称之为并发的（concurrent，参见发生于之前和并发关系）。从另一个角度说，如果两个事件因果相关，则其一定有序。也即，因果性定义了一种偏序（partial order）关系，而非全序关系：有些操作存在因果，因此可比；而另外一些操作则是并发的，即不可比。

根据上述解释，在线性一致性的数据存储服务中，是不存在并发操作的：因为必然存在一个时间线能将所有操作进行排序。同一时刻可能会有多个请求到来，但是线性化的存储服务可以保证：所有请求都会在单个副本上、一个单向向前的时间线上的某个时间点被原子地处理，而没有任何并发。

并发（concurrency）意味着时间线的分叉与合并。但在重新合并之时，来自两个时间分支的操作就有可能出现不可比的情况。在第五章的图 5-14（参见确定 Happens-Before 关系）中我们见过类似的现象，所有的事件不在一条时间线上，而是有相当复杂的图形依赖。图中的每个箭头，本质上定义了一种因果依赖，也即偏序关系。

理解全序和偏序、线性一致性和因果一致性的一个关键模型是有向图。在该图中，点代表事件，有向边代表因果关系，并且从因事件指向果事件，很自然的，因果性满足传递性。如果该图中有一条单一的路径能串起所有点，且不存在环，则该系统是线性一致的。可以看出，因果关系是一种局部特性（也即偏序关系），定义在两个点之间（如果两个点之间存在着一条单向途径，则这两点有因果关系）；而线性关系是一种全局特性（也即全序关系），定义在整个图上。

如果你熟悉一些分布式的版本管理工具，如 Git，你就会发现相似的特性。在 Git 中，版本间的依赖就类似于一个因果依赖图。大部分时候，所有人的提交（commit）是前后相继的，组成一个直线；但有时，如果团队中的几个人同时（并发的）为一个项目工作，版本历史就会产生分叉，并且在提交的时候重又合并。

在 Spark 的多个 RDD 之间，也有类似的感觉。如果所有算子都是单输入算子，则执行图会是一条线，即全序没有并发；如果有的算子有多个输入，则不同输入之间可以并发，此时为偏序关系。

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

那么因果顺序和线性一致性的关系是什么？答曰：线性一致性是因果一致性的充分（implies）条件。所有提供线性一致性的系统都能够能够保证因果性。尤其对于有多个通信通道的系统来说，我们不需要做任何额外努力（比如在多个组件间传递时间戳，以建立因果关系），线性一致性就能够保证系统中发生的所有事件满足因果性。

用我们之前的图模型来说，就是不存在环。即，因果一致性（有向无环图） ⇒ 线性一致性（在有向无环图的基础上，存在一条能串起所有点的单向路径）。

线性一致性能能够保证因果关系，该特点让系统易于使用，从而对应用层很有吸引力。但任何事情都是有代价的，如我们在之前线性一致性的代价一节中所讨论的：提供线性一致性非常伤性能和可用性，在网络有显著延迟时（如全球部署的系统），该副作用尤其明显。因此，很多系统会舍弃线性一致性以换取更好的性能，但当然，代价是更难用了。

好消息是存在折中路线。线性一致性并非保持因果关系的唯一途径，还有很多其他办法。也即，一个系统可以不必承担线性一致性所带来的性能损耗，而仍然是因果一致的（consistent）。当然，在这种情况下，CAP 定理是不适用的。事实上，因果一致性是系统在保证有网络延迟而不降低性能、在有网络故障而仍然可用的情况下，能够提供的最强一致性模型。

在大多数情况下，我们以为我们需要线性一致模型，其实我们真实需要因果一致模型，而后者允许我们实现性能更好的系统。基于这个观察，研究人员在探寻新型数据库的设计，让系统既可以提供因果关系保证，也可以提供（堪比最终一致性系统的）高性能和高可用性。

这些研究都比较新，还存在很多挑战，也没有进行落地。但无疑，是分布式系统在将来一个很有前景发展方向。

真实系统中，在所有的事件集中，只有部分事件是有因果依赖的，这些事件需要在执行时保证因果顺序执行；而其他的大部分事件是没有因果依赖的，因此可以乱序、按需执行以保证性能。但这件事情的难点在于，因果关系是应用层定义的。而我们在系统层，就很难识别。可能需要提供某种接口，可以让应用层显示指定因果，但一来不确定这种接口是否能做的足够宽泛；二来，这种因果追踪的额外代价是非常大的。

捕获因果依赖

我们不会事无巨细的去探究非线性化系统如何保持因果关系的每个细节，仅就其中的一些关键点进行探讨。

为了保证因果一致性，我们首先需要知道哪些操作存在着因果关系。如之前所说，因果关系是偏序关系，有些操作是并发的，但如果确定某个操作发生在另外一个之前，则在所有的副本上都要以同样的顺序处理这两个操作。因此，当某个副本处理一个操作时，它必须确保所有其前驱（happens before）操作都已经完成；如果有任何前驱操作还未出现，则之后的操作必须等待直到其被处理。

为了确定因果依赖，我们需要某种手段来描述系统中节点的“知识”（knowledge）。如果某个节点在收到 Y 的写入请求时已经看到了值 X，则 X 和 Y 间可能会存在着因果关系。就如在调查公司的欺诈案时，CEO 常被问到，“你在做出 Y 决定时知道 X 吗”？

确定哪些操作先于哪些些操作发生的方法类似于我们在“并发写入检测”一节讨论的技术。那一节针对无主模型讨论了如何检测针对单个 Key 的并发写入，以防止更新丢失问题。因果一致性所需更多：需要在整个数据库范围内追踪所有 Key 间操作的因果依赖，而非仅仅单个 Key 上。版本向量（version vectors）常用于此道。

为了解决确定因果顺序，数据库需要知道应用读取数据的版本信息。这也是为什么在图 5-13 中（参见确定 Happens-Before 关系），我们在写入数据时需要知道先前读取操作中数据库返回的版本号。在 SSI 的冲突检测（参见可串行的快照隔离）中也有类似的思想：当一个事务提交时，数据库需要检查其读取集合中的数据版本是否仍然是最新的。为此，数据库需要跟踪一个事务读取了哪些数据的哪些版本。

序列号定序

理论上来说，因果关系很重要；但在实践中，追踪所有的因果依赖非常不切实际。在很多应用场景，客户端会先读取大量数据，才会进行写入。并且我们也无从得知，之后的写入和先前有没有关系，和哪些有关系。显式的追踪所有读集合所带来的开销会非常大。

不过，我们有一种更简单的手段：使用序列号（sequence numbers）或者时间戳（timestamps）来给事件定序。我们不非得用物理时间戳（如日历时钟，time-of-day clock，参见日历时钟），而可以使用逻辑时钟（logic clock），即使用某种算法来产生一系列的数值以关联操作。最简单的，可以用一个计数器来递增地为每个操作安排一个序列号。

此种序列号和时间戳通常都非常紧凑，只占几个字节，但却能提供一种全序关系。通过给每个操作关联一个序列号，就能比较任何两个操作的先后关系。

进一步，我们可以保证我们产生序列号的方式满足因果关系：如果操作 A 发生在 B 之前，则 A 获取到的序列号比 B 小。并发的（无法比较谁先谁后）操作获取到的序列号顺序不确定。序列号本质上是一种全序，通过这种方式可以追踪因果关系，但也施加了一个比因果关系更为严格的全序。

联想我们之前用以理解的有向图，相当于在满足原来有向边（因果关系）的基础上，增加了一些有向边，串出了一条能串起所有点（操作）的路径。

在使用单主模型的多副本系统中，主节点上操作日志的追加顺序确定了一个对所有操作的全序，且满足操作发生的因果关系。主节点可以为每条日志按顺序关联一个全局递增的序列号，如果从节点上也按都按此序列号顺序应用操作日志到状态机，则每个副本总能保持一致的状态（但有可能稍落后于主节点）。

非因果序生成器

如果系统中没有唯一的单主节点（比如你用的是多主模型或无主模型，又或者你的系统存在多个分区），则如何为每个操作产生一个序列号就变得不那么简单直观了。常用的方式有以下几种：

每个节点独立地生成不相交的序列集。如，你的系统中有两个节点，一个节点只产生奇数序号，另一个节点只产生偶数序号。更通用一些，我们可以在生成的序号中保留一些位来编码对节点的标识，从而让不同的节点永远不会产生相同的序号。
可以为每个操作关联一个日历时钟（或者说物理时钟）。这些时间戳不是有序的（因为回拨？），但如果有足够的精读，就可以让任意两个操作关联的时间戳不同，依次也可以达到全序的目的。此种方法有时候会被用在解决冲突使用后者胜的策略（但会有风险）。
每次可以批量产生一组序列号。比如，在请求序列号时，节点 A 可以一次性声明占用 1 ~ 1000 的序列号，节点 B 会一次占用 1001~2000 的序列号。则本地的操作可以从拿到的这批序列号中直接分配，仅在快耗尽时再去请求一批。这种方法常被用在 TSO（timestamp oracle，单点授时）的优化中。

这三种方案都要比使用单点计数器生成序列号要性能好、扩展性更强，且能为系统中的每个操作产生全局唯一的、近似递增的序列号。但他们都存在着同样的问题：产生的序列号不是因果一致的。

由于这些序列号生成方法都不能够很好地捕捉跨节点的操作因果关系，因此都存在因果问题：

不同节点上处理操作的速率很难完全同步。因此，如果一个节点使用奇数序号，另一个节点时用偶数序号，则两个序号消耗的速率也会不一致。此时，当你有两个奇偶性不同的序号时，就难以通过比较大小来确定操作发生的先后顺序。
物理时间戳会由于多机时钟偏差，而不满足因果一致。例如，在图 8-3 中（参见时间戳以定序），就出现了发生在之后的操作被分配了一个较小的时间戳。
对于批量分配方式，有可能发生较早的操作被分配了 1001-2000 的序列号，而较晚的操作被分配了 1-1000 的序列号。如此一来，序列号的分配不满足因果一致。

Lamport 时间戳

虽然上面的几种方式产生的序列号不满足因果一致性，但却有一种相对简洁的方式可以做到—— Lamport 时间戳。它是由 Lesilie Lamport 在 1978 年提出的，是分布式领域被引用最多的论文之一。

下图展示了 Lamport 时间戳的使用方法。在该系统中，每个节点有一个唯一的 id 和一个记录处理过多少个操作的计数器，Lamport 时间戳是上述两者组成的二元组：(counter, node ID) 。不同的节点可能会有相同的 counter 值，但通过引入 node ID，可以使所有时间戳都是全局唯一的。

Untitled

Lamport 时间戳不依赖于物理时钟，但可以提供全序保证，对于任意两个 Lamport 时间戳：

具有较大 counter 的时间戳较大
counter 相同，具有较大 node ID 的时间戳较大

但到此为止，以上表述和之前提到的奇偶时间戳没有本质区别。让 Lamport 时间戳能够满足因果一致性的核心点在于：每个节点和客户端都会让 counter 追踪当前所看到（包括本机的和通信的）的最大值。当节点看到请求或者回复中携带的 counter 值比自己大，就会立即用其值设置本地 counter。

如上图，客户端 A 在收到节点 2 的 counter = 5 的回复后，会使用该值向节点 1 发送请求。节点 1 本来的 counter 值是 1，在收到该请求后，会立即前移为 5。尔后，下一个请求操作到来会将其增加为 6。

系统中所有的事件（event），和交互方（client，server）都要被纳入 Lamport Clock 体系内，才能追踪系统内的所有因果关系。

只要最大的 counter 值通过每个操作被传播，就能保证 Lamport 时间戳满足因果一致。因为每次因果依赖的交互都会推高时间戳。

有时候我们会将 Lamport 时间戳和之前提到的版本向量（version vector，参见并发写入检测）混淆。虽然看起来相似，但其根本目的却是不同：

版本向量能够用于检测操作的并发和因果依赖
Lamport 时间戳只是用于确定全序

对于 2，虽然 Lamport 时间戳能够追踪因果关系，即具有因果关系中的 happens-before 关系。但是反过来，并不能通过两个 Lamport 时间戳的大小来判断其是有因果关系、还是并发的。但相对于版本向量，Lamport 时间戳占用空间小，更为紧凑。

时间戳定序还不够

尽管 Lamport 时间戳能够给出一种能够追踪因果关系的全序时间戳生成算法，但并不足以解决分布式系统中所面临的的很多基本问题。

举个例子，考虑一个系统，在该系统中，以用户名唯一确定一个账户。如果两个用户并发的用同一个用户名创建账户，则一个成功，另一个失败（参见领导者和锁）。

第一感觉，对所有事件进行全序定序（如使用 Lamport 时间戳）能够解决该问题：如果系统收到两个具有相同用户名的账户创建请求，让具有较小时间戳的那个请求成功，让另一个失败。由于所有时间戳满足全序关系，这两个请求的时间戳总是可以比的。

该方法能够确定赢家基于一个隐藏假设：当你拿到系统中所有的账户创建操作后，你才可以比较他们的时间戳。然而，在收到某个账户创建请求时，系统中单个节点并不能立即独自的判断该请求成功还是失败。此时此刻，该节点并不知道其他节点是否收到了具有同样用户名的账户创建请求，以及其请求的时间戳是大还是小。

如果其他节点收到同名账户的创建请求，并且获得了较小的时间戳，本节点的创建请求就得失败。为了避免这一点，它需要不断和其他节点沟通，以知晓他们在做啥。但如果沟通时，其他节点宕机或者网络出现问题，则可能会导致系统陷入停顿而不能提供服务。这显然不符合我们对一个高可用系统的期望。

上述问题的核心在于，只有在收集到系统中所有操作之后，才能真正确定所有操作的全序。如果其他节点正在进行某些操作，但你并不知晓，也就自然不能确定最终的事件的全序：毕竟这些未知节点的操作可能被插入到不同位置。举个例子，本节点的事件顺序为 n1e1, n1e2, n1e3，另外一个节点有两个事件，顺序为 n2e1, n2e2，将两个序列进行合并时，会有多种可能的结果。这有点类似于多个并发事务中的读写序列定序。

小结一下，在分布式系统中，为了实现类似于针对用户名的唯一性约束，仅为所有时间进行全局定序是不够的，你还需要知道该定序何时完成。对于某个创建账户的操作，如果我们能够确定在最终的全序里，不会有其他操作插到该操作之前，我们便可以安全的让该操作成功。

确定全局定序何时收敛，将会在接下来的小节 —— 全序广播（_total order broadcast_）中讨论。

全序广播

如果你的系统只跑在单核 CPU 上，那确定该系统中所有操作的全局顺序是相当简单直接的——即其在 CPU 上的执行顺序。然而，在一个分布式系统中，让所有节点就所有操作的某个确定的全局序列达成一致是相当棘手的。在上一小节，我们讨论了使用时间戳或者序列号进行定序的问题，但发现相比单主模型这种方法容错能力很弱鸡（在使用时间戳定序的系统中，如果你想实现唯一性约束，就不能容忍任何故障）。

如前所述，单主模型通过在所有节点中选出一个主，尔后在该节点上利用某个 CPU 对所有操作进行定序，从而确定一个唯一的全局序列。但使用单主模型的系统会面临两个问题：

当系统负载超过单机可以处理的尺度，如何进行扩容。
当主节点宕机时如何进行故障转移（failover）。

在分布式系统的语境下，该问题也被称为全序广播（total order broadcast）或者原子广播（atomic broadcast）。

顺序保证的范围。 多分区的数据库，对于每个分区使用单主模型，能够维持每个分区的操作全局有序，但并不能提供跨分区的一致性保证（比如一致性快照，外键约束）。当然，跨分区的全序保证也是可以提供的，只不过需要进行额外的协调。

全序广播是一种多个节点间交换消息的协议。它要求系统满足两个安全性质：

可靠交付。如果一个节点收到了消息，则系统内所有的相关节点都要收到该消息。
全序交付。每个节点接收到消息的顺序一致。

一个正确的全序广播算法需要保证上述两条性质在任何情况下都能够满足，包括网络故障和节点宕机。但当然，如果网络出现故障时，消息肯定不能送达所有节点；但算法可以进行重试，直到网络最终恢复（当然，恢复后也要保证所有消息送达的顺序一致）。

使用全序广播

像 Zookeeper 和 etcd 等共识服务都实现了全序广播算法。从这些共识服务我们能感觉到，全序广播和共识协议具有很强的关联性，我们会在本章稍后一探究竟。

在做数据库备份时其实我们真正需要的是全序广播：如果我们让“消息”具象为数据库中的写入，且每个副本以相同的顺序处理相同的输入集，则每个副本必然会保持一致（除却暂时的临时同步延迟外）。该准则也被称为：状态机复制（state machine replication），在第 11 章的时候我们将继续该主题。

类似的，全序广播也可以用于实现可串行化的事务：如之前物理上串行提到的，消息在此具象为作为存储过程执行的一个确定性的事务，如果所有节点按同样的顺序处理这些消息，则数据中的所有分区和副本最终都会在数据上保持一致。

需要注意到，全序广播的一个重要性质是：当收到消息时，其顺序已经确定。这是因为，节点不能将后收到的消息，插入之前的已经收到的消息序列。这让全序广播要强于时间戳排序（timestamp order）。

还可以从另外一个角度来理解全序广播——用来写日志（比如复制日志、事务日志或者写前日志）：投递消息就像追加日志。由于所有节点都会按照同样的顺序发送消息，则所有节点在读取日志的时候也会得到同样的消息序列。

全序广播也可以用来实现提供防护令牌功能（fencing token，参见防护令牌，即关联了 id 的锁）的锁服务。每个上锁请求可以作为消息追加到日志中，依据其追加到日志中的顺序，所有请求可以被自然地编号。由于这个序列号是单调递增的，便可以充当防护令牌。在 Zookeeper 中，这个序列号便是 zxid。

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

如图 9-4，在线性一致系统中，所有操作存在着一个全局序列。这是否意味着全序广播就是线性一致性？不尽然，但他们间有很深的联系。

全序广播是异步的：系统保证以同样的顺序交付消息，但并不保证消息的交付时刻（即，有的消息接收者间可能存在着滞后）。与之相对，线性一致性是一种新鲜度保证：读取一定能看到最新成功的写。

不过，你可以基于全序广播来构建线性一致的存储系统。如，可以用于保证用户名的唯一性约束。

对于该问题，可以这样实现。对每一个可能的用户名，我们使用一个支持 CAS 操作的线性寄存器，初始值为 null（表示该用户名没有被占用）。当用户想使用某个用户名创建账户时，使用 CAS 操作，在寄存器旧值为 null 时，将其值设置为该用户 account-id。由于寄存器的原子性，最后只有一个用户会成功。

使用全序广播系统作为日志追加服务，便可以实现这样一个支持可线性化 CAS 操作的“寄存器”：

向服务中追加一个带有某用户名的消息条目，表明你想使用该用户名。
（由于全序广播是异步的）不断读取日志，直到能够读到刚才你追加的消息条目。
检查所有想要使用该用户名的消息，这时你可能会得到多条消息，如果你当初写下的消息在第一条，则你是成功的。此时，你可以“确认”（持久化，比如追加日志，比如写入数据库）占有该用户名的信息，然后给客户端返回成功。如果第一条消息不是你的，则终止请求。

这里其实隐藏了一些细节，即我们会将追加消息请求发送给全序广播系统，全序广播系统会真正将消息按之前提到的两条保证的方式（可靠送达和全序送达）同步到每个节点。因此，对于每个节点来说，会首先发起消息追加请求，然后之后某个时刻，可以等到真正同步回来的消息。如果觉得绕，可以带入 Raft 的复制日志来类比。

由于所有日志条目都会以同样的顺序送达每个节点，若有并发写入，则所有节点都能依靠日志顺序就谁“先来后到”达成一致。当有同名冲突时，可以选择第一条作为赢家，并舍弃其后的冲突请求。可以使用类似的方式，基于日志来实现涉及到多对象的事务的可串行化。

尽管该方式能够提供线性化的写入，却不能保证线性化的读取。如果你从一个异步同步日志的节点读取日志，就有可能读到陈旧的数据（更精确一点说，上述过程能够提供顺序一致性，sequential consistency，有时也被称为时间线一致性，_timeline consistency_，比线性一致性稍弱）。在此基础上，如果想让读取也变得可线性化，有几种做法：

让读取也走日志，即通过追加消息的方式将读取顺序化，然后当读取请求所在节点收到这条读取日志时才去真正的去读。则消息在日志中的位置定义了整个时间序列中读取真正发生的时间点。（etcd 中的法定读取就是用的类似的做法）
如果日志服务允许查询最新日志的位置，则可以在请求到来时，获取当时最新位置，然后不断查询日志看是否已经跟到最新位置。如果跟到了，就进行读取。（这是 Zookeeper 中 sync() 操作的背后的原理）
可以将读取路由到写入发生的那个节点，或者与写入严格同步的节点，以保证能够读到最新的内容。（这种技术用于链式复制，_chain replication_ 中）

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

上节展示了如何使用全序广播来实现 CAS 操作的线性化存储。我们也可以反过来，设有一个线性一致的存储系统，看如何基于其实现全序广播。

最简单的方法，假设我们有一个整数寄存器，并提供 increment-and-get 原子操作，当然提供 CAS 原子操作也是可以的，只是稍微没那么直观。

算法相当简单：对于每一个发给全序广播系统的消息，使用整数寄存器 increment-and-get 操作关联一个序列号；然后将消息发送给所有节点（重试任何丢失的消息）。每个节点接收到消息后利用序列号顺序对外交付消息。这种机制很像 TCP，但并不是描述通信双方，而是一个分布式系统。

如何判断消息是否丢失？ACK 或者是否遇到异常。

注意到，和 Lamport 时间戳不同，从线性化的寄存器中获取的数字是连续的，非跳跃的。如此一来，当某节点交付了消息 4 后，收到了消息 6，但不能立即交付，而需要等待消息 5 的到来。但在 Lamport 时间戳系统中则非如此——这（是否连续）也是全序广播和时间戳顺序的核心不同。

实现一个支持 increment-and-get 原子操作的线性化整数寄存器有多难？如果所有组件都不会出错，则很简单：你可以直接用单台机器上的一个变量。但如果连接到该节点的网络会出问题怎么办？这台机器机器宕机后，宕机前变量的值又该怎么恢复？理论上说，只要你对线性序列生成器思考的足够完备，就会不可避免的得到一个共识算法（consensus algorithm）。

这并不是巧合：可以证明，一个线性的 CAS 寄存器和全序广播都等价于共识协议（equivalent to consensus）。也即，如果你解决了其中任意一个问题，就可以通过某种手段将其转化为另一个问题的解决方案。这真是一个惊人的性质！

终于，说到了共识，这是本章余下将要全力探讨的问题。