第 10 章 一致性与共识

古谚有云："出海时勿带两台计时器；要么带一台，要么带三台。"

—— Frederick P. Brooks Jr.，《人月神话：软件工程随笔》（1995）

正如第 9 章所讨论的，分布式系统中可能出错的事情很多。要让服务在面对种种麻烦时仍能正确运行，就得想办法容忍故障。

最有力的容错工具之一就是复制。然而正如第 6 章所见，把数据复制到多个副本上也增加了不一致的风险：读请求可能落到尚未追上的副本上，返回过期结果；如果多个副本都能接受写入，又得处理不同副本并发写入产生的冲突。从宏观上看，处理这类问题有两种针锋相对的哲学：

最终一致性

在这种哲学下，系统采用复制这一事实对应用是可见的，应用开发者要自行处理可能出现的不一致与冲突。多主复制（见第 215 页"多主复制"）和无主复制（见第 229 页"无主复制"）常采用此思路。

强一致性

这种哲学认为应用不该为内部复制细节操心，系统应表现得像运行在单个节点上一样。其优点是对应用开发者更简单；缺点是更强的一致性会带来性能成本，而且某些最终一致系统能容忍的故障，会让强一致系统直接中断服务。

哪种做法更好，一如既往，取决于你的应用。如果应用允许用户离线修改数据（如第 220 页"同步引擎与本地优先软件"所述），最终一致性就不可避免；但最终一致性对应用而言往往很难处理。如果副本部署在通信快速可靠的数据中心内，强一致性的代价通常值得。

本章我们将深入探讨强一致这一路径，重点关注三个方面：

• 一个挑战是"强一致"本身相当含糊，因此我们将给出一个更精确的目标定义：线性一致性（linearizability）。
• 我们将讨论生成 ID 与时间戳的问题。这听起来似乎与一致性无关，但实际上联系紧密。
• 我们将探讨分布式系统如何在保持容错的前提下实现线性一致——答案是共识算法。

一路上我们会看到，分布式系统所能做到的事情存在根本性的限制。

本章涉及的主题以难以正确实现著称。在没有故障时表现得宜的系统很容易写出来，可一旦遇上设计者未曾设想过的不幸故障组合或消息时序，它们就会彻底崩溃。围绕这些边界情况已积累了大量理论，帮助我们构建鲁棒的容错系统。

本章只能浅尝辄止。我们将停留在直观层面，避开算法细节、形式化模型与证明。若你想认真做共识系统或类似基础设施的工作，必须深入理论才有希望让系统真正鲁棒；本章的参考文献提供了入门指引。

线性一致性

如果你希望让一个采用复制的数据库尽可能简单易用，就应该让它表现得像一个一致的单节点数据库。这样用户既不必担心复制延迟、冲突或其他不一致，你也能在不必为多副本伤脑筋的同时享受容错的好处。

这正是线性一致性 [1]（也叫原子一致性 [2]、强一致性、即时一致性或外部一致性 [3]）背后的思想。线性一致性的精确定义相当微妙，本节余下篇幅会来探讨。其基本思想是让系统看上去好像只有一份数据副本，对它的所有操作都是原子的。有了这一保证，即便现实中存在多个副本，应用也无须为它们操心。

在线性一致系统中，只要某客户端成功完成一次写入，所有从数据库读取的客户端都必须能看到刚写入的值。维持单一副本的假象，意味着读到的总是最新值，不会来自陈旧缓存或落后副本。换言之，线性一致性是一种新近性保证。为帮助理解，我们先看一个非线性一致系统的例子。

图 10-1 展示了一个非线性一致体育网站 [4] 的例子。Aaliyah 与 Bryce 坐在同一房间里，二人都在手机上查他们最爱球队比赛的最终结果。比分刚一公布，Aaliyah 就刷新页面看到了赢家，兴奋地告诉 Bryce。Bryce 不可置信地点了刷新，但他的请求落到一个落后的数据库副本上，所以他的手机显示比赛仍在进行。

图 10-1. 这个系统不是线性一致的，让球迷困惑 如果 Aaliyah 与 Bryce 是同时点击刷新的，得到不同结果倒并不太奇怪——他们并不知道服务器何时分别处理了各自的请求。然而 Bryce 是在听见 Aaliyah 喊出最终比分之后才点的刷新（即发起查询），因此他理应期望自己查到的结果不会比 Aaliyah 看到的更旧。事实上他得到了过期结果，这就违反了线性一致性。

是什么让系统线性一致

为更好理解线性一致性，再看几个例子。图 10-2 展示了三个客户端在一个线性一致数据库上并发地读写同一对象 x。在分布式系统理论里，x 被称为一个寄存器（register）——实际上它可以是键值存储中的一个键、关系型数据库中的一行，或文档数据库中的一份文档。

图 10-2. 当读请求与写请求并发时，可能返回旧值或新值 为简化起见，图 10-2 只展示客户端视角下的请求，不展示数据库内部细节。每条线段是某个客户端发出的一次请求，线段起点是请求发出的时刻，终点是客户端收到响应的时刻。由于网络延迟可变，客户端并不准确知道数据库何时处理了请求；它只知道这次处理一定发生在自己发请求之后、收到响应之前。

本例中，寄存器有两类操作：

• Read(x) ⇒ v 表示客户端请求读寄存器 x 的值，数据库返回值 v。
• Write(x, v) ⇒ r 表示客户端请求把寄存器 x 设为值 v，数据库返回响应 r（OK 或 Error）。

在图 10-2 中，x 的初始值为 0，客户端 C 发起一次写请求把它设为 1。在这期间，客户端 A 和 B 反复轮询数据库读取最新值。它们的读请求可能得到哪些响应？

我们一一分析：

• 客户端 A 的第一次读完成发生在写开始之前，因此必然返回旧值 0。
• 客户端 A 的最后一次读开始于写完成之后，因此若数据库是线性一致的，它必然返回新值 1，因为该读必然在写之后被处理。
• 任何在时间上与写操作重叠的读，可能返回 0 也可能返回 1，因为我们不知道在该读被处理时写是否已生效。这些操作与写并发。

然而这还不足以完整刻画线性一致性。如果与写并发的读可以返回旧值或新值，那么读者可能在写期间看到值在新旧之间反复跳变。这并非我们对一个模拟"单份数据副本"的系统所期待的行为。

要使系统成为线性一致的，还需加上另一项约束，如图 10-3 所示。

图 10-3. 一旦某次读返回了新值，所有后续读（无论同一客户端还是其他客户端）也必须返回新值 在线性一致系统中，我们设想必有某个时间点（介于写操作开始与结束之间）x 的值原子地从 0 翻到 1。因此一旦某客户端的读返回新值 1，所有后续读必定也返回新值，即便写操作还未正式完成。

这种时序依赖在图 10-3 中以箭头标示。客户端 A 是首个读到新值 1 的。就在 A 的读返回之后，B 开始读取。由于 B 的读严格发生在 A 之后，因此即使 C 的写仍在进行，B 也必须返回 1。（这与图 10-1 中 Aaliyah 与 Bryce 的情形相同：Aaliyah 读到新值后，Bryce 也应当读到新值。）

我们可以进一步细化这一时序图，让每个操作在某一时点原子地生效 [5]，如图 10-4 所示。这个例子中，除 read 与 write 之外又加了第三类操作：

CAS(x, v_old, v_new) ⇒ r 表示客户端请求一次原子 CAS 操作（见第 302 页"条件写入（compare-and-set）"）。若寄存器 x 当前值等于 v_old，应原子地置为 v_new；若 x 的值不等于 v_old，则保持不变并返回错误。r 是数据库的响应（OK 或 Error）。

图 10-4 中每个操作都用一根竖线标记（位于该操作对应线段内部），表示我们认为它被执行的那一时刻。这些标记按顺序串成一个序列，结果必须是合法的对寄存器的读写序列（每次读必须返回最近一次写所设置的值）。

线性一致性的要求是：连接这些操作标记的连线在时间上始终向前（从左向右），不得倒退。这一要求确保了前述新近性保证：一旦某个新值被写入或被读出，之后的所有读都会看到该值，直到它再次被覆盖。

图 10-4. 可视化读与写"看起来生效"的那些时点——B 的最后一次读不是线性一致的 图 10-4 中有几处有趣的细节值得指出：

• 首先，客户端 B 发出读 x 的请求，然后客户端 D 发出把 x 设为 0 的请求，再然后客户端 A 发出把 x 设为 1 的请求。然而 B 的读返回了 1（A 写入的值）。这没问题：意思是数据库先处理了 D 的写、再处理了 A 的写、最后处理了 B 的读。虽然这不是请求被发送的顺序，但仍是一种可接受的顺序，因为这三次请求是并发的。或许 B 的读请求在网络中被略微延迟，所以它在两次写之后才到达数据库。
• 客户端 B 的读返回 1，发生在客户端 A 收到数据库回复"写入值 1 成功"之前。这也没问题：只能说明数据库给 A 的 OK 响应在网络中被略微延迟了。
• 该模型不假定任何事务隔离：另一个客户端可能随时改变某个值。例如 C 先读到 1 后又读到 2，因为这期间 B 把值改成了 2。原子 CAS 操作可用来检查该值未被其他客户端并发修改：B 与 C 的 CAS 请求成功，但 D 的 CAS 失败（数据库处理它时，x 已不是 0 了）。
• 客户端 B 最后一次读（用阴影线段标出）不是线性一致的。这次操作与 C 的 CAS 写并发，后者把 x 从 2 更新为 4。在没有其他请求的情况下，B 的读返回 2 本来是允许的。然而客户端 A 在 B 的读开始之前已经读到了新值 4，因此不允许 B 比 A 读到更旧的值。这又是图 10-1 中 Aaliyah 与 Bryce 的情形。

这就是线性一致性背后的直觉；其形式化定义 [1] 描述得更精确。原则上可以测试一个系统的行为是否线性一致：记录所有请求与响应的时序，检查它们能否被排成一个合法的顺序序列（不过这在计算上代价高昂）。

正如事务除可串行化外还有种种较弱的隔离级别（见第 288 页"弱隔离级别"），副本系统除线性一致性之外也有种种较弱的一致性模型 [8]。第 209 页"复制延迟下的问题"中提及的写后读一致性、单调读和一致前缀读保证就是几个例子。线性一致性包含所有这些保证，是常用一致性模型中最强的。

线性一致性 vs 可串行化

线性一致性容易与可串行化（见第 308 页"可串行化"）相混，因为字面上都像在说"可被排成某种顺序"。然而它们是相当不同的两类保证，必须区分清楚：

可串行化

可串行化是事务的一种隔离级别，事务可以读写多个对象（行、文档、记录）。它保证事务在效果上等价于按某种串行顺序执行——即先把一个事务的所有操作做完，再做下一个事务的，依此类推，彼此不交错。允许该串行顺序与事务实际执行顺序不同 [9]。

线性一致性

线性一致性是对寄存器（一个单独对象）读写的保证。它不会把多个操作组合成事务，因此不能防止涉及多对象的写偏斜等问题（见第 303 页"写偏斜与幻影"）。但它是一种新近性保证：要求若一个操作在另一个操作开始前完成，则后者必须看到至少与前者一样新的状态。可串行化没有这个要求——例如可串行化允许过期读 [10]。

顺序一致性[8] 又是另一种概念，本书不予讨论。

一个数据库可同时提供可串行化与线性一致性；这一组合被称为严格可串行化或强单副本可串行化（strong-1SR）[11, 12]。单节点数据库通常是线性一致的；而对采用乐观方法（如 SSI，见第 317 页"可串行化快照隔离"）的分布式数据库，情形则复杂得多。例如 CockroachDB 提供可串行化以及对读的若干新近性保证，但并非严格可串行化 [13]，因为严格可串行化要求事务之间进行昂贵的协调 [14]。Spanner 与 FoundationDB 则提供严格可串行化 [15, 16]。

也可以把较弱的隔离级别与线性一致性、或较弱的一致性模型与可串行化结合起来；事实上一致性模型与隔离级别在很大程度上可以彼此独立选取 [17, 18]。

依赖线性一致性

线性一致性在哪些场合有用？体育比赛最终比分晚几秒看到这个例子或许显得无关紧要——结果哪怕过期几秒，也很难造成什么真正的伤害。然而在另一些领域，线性一致性却是系统正确工作的关键要求。

加锁与主节点选举

使用单主复制的系统必须确保确实只有一个主节点，而不是多个（脑裂）。选主的一种方法是使用租约：每个启动的节点都尝试获取这一租约，拿到的那个就是主节点 [19]。无论实现细节如何，这一机制都必须是线性一致的——绝不能让两个节点同时持有这一租约。

Apache ZooKeeper [20]、etcd 之类的协调服务常被用来实现分布式租约与选主。它们借助共识算法以容错方式实现线性一致操作（本章后面会讨论这些算法）。正确实现租约与选主有很多微妙之处（如第 373 页"分布式锁与租约"中的屏障问题），Apache Curator 之类的库会在 ZooKeeper 之上提供更高层的"配方"以帮助实现。但归根结底，线性一致的存储服务才是此类协调任务的根本基础。

严格来说，ZooKeeper 提供的是线性一致的写，读则可能过期——因为不保证读由当前主节点服务 [20]。etcd 自第 3 版起默认提供线性一致读。

某些分布式数据库在更细粒度上使用分布式锁，例如 Oracle Real Application Clusters（RAC）[21]。RAC 对每个磁盘页面加一把锁，多个节点共享同一套磁盘存储。由于这些线性一致锁处于事务执行的关键路径上，RAC 部署通常专门配有一条集群互联网络供数据库节点间通信。

约束与唯一性保证

数据库中常见唯一性约束——例如用户名或邮箱地址必须唯一标识某个用户，文件存储服务中不能有两个同路径同名的文件。如果你想在数据写入的同时强制这一约束（这样两人并发尝试创建同名用户或文件时，其中一方会收到错误），就需要线性一致性。

这与加锁相似：当用户在你的服务上注册时，可视作对所选用户名加了一把锁；它也很像一次原子 CAS——若用户名尚未被占用，则将其设置为该用户的 ID。

类似问题在另一些场景中也会出现：要确保银行账户余额永远不为负、不能卖出超过库存数量的商品、两人不能并发预订同一航班或剧院的同一座位等。这些约束都要求所有节点对单一最新值（账户余额、库存量、座位占用情况）达成一致。

实际应用中有时可以宽松对待这种约束——例如某航班超售时，可以把客户改签至另一班并赔偿不便。这种情形下未必需要线性一致性（我们将在第 571 页"时效性与完整性"中讨论这种宽松解读的约束）。

不过，关系数据库中那种硬性唯一性约束的确要求线性一致。其他类型的约束（如外键或属性约束）则不需要线性一致性也能实现 [22]。

跨通道时序依赖

图 10-1 还有一个重要细节值得注意：如果 Aaliyah 没有喊出比分，Bryce 就不会知道自己的查询结果是过期的。他大概几秒后再刷新一次，最终也能看到最终比分。线性一致性的违反之所以被察觉，是因为系统中存在一条额外的通信通道（Aaliyah 的声音传到 Bryce 耳里）。

类似情况也会出现在计算机系统中。比如，假设你的网站允许用户上传视频，并由一个后台进程将视频转码成可在慢速网络上播放的低质量版本。该系统的架构与数据流如图 10-5 所示。视频转码器需要被显式指示去执行转码任务，这条指令通过消息队列从 Web 服务器发给转码器（见第 12 章）。Web 服务器不会把整个视频塞进队列，因为多数消息代理是为小消息设计的，而视频体积可能高达数兆字节。因此先把视频写入文件存储服务，写入完成后再把转码指令放进队列。

图 10-5. Web 服务器与视频转码器同时通过文件存储和消息队列通信，由此打开了竞态条件之门 若文件存储服务是线性一致的，这套系统应能正常工作；若不是，就有竞态风险：消息队列（图 10-5 步骤 3 与 4）可能比存储服务内部的复制更快。此时转码器去取原视频（步骤 5），可能读到旧版本，甚至什么都读不到。一旦它处理了过期版本，文件存储中的原视频与转码视频就会永久彼此不一致。

问题之所以出现，是因为 Web 服务器与转码器之间存在两条通信通道：文件存储与消息队列。失去了线性一致性的新近性保证，这两条通道之间就可能发生竞态。这与图 10-1 如出一辙——那里同样是两条通道之间的竞态：数据库复制与 Aaliyah 嘴到 Bryce 耳的实地音频通道。

如果手机 App 在服务器上出现新数据时通过推送通知告知用户、用户收到通知后再去拉取数据，类似竞态也会发生：若拉取请求落到落后副本上，就可能出现推送通知到得很快、但后续拉取却看不到通知所述数据的情况。

线性一致性不是规避这种竞态的唯一办法，但它最好理解。如果你能控制那条额外通道（如消息队列那种情形，而非 Aaliyah/Bryce 那种情形），可以借鉴第 210 页"读己之写"中讨论过的替代方案，代价是增加额外复杂度。

实现线性一致系统

看过几个线性一致性派得上用场的例子之后，再来思考如何构建一个具备线性一致语义的系统。

线性一致性本质上意味着"表现得像只有一份数据副本，对它的所有操作都是原子的"，因此最简单的答案就是真的只用一份。但那样做无法容错：一旦持有该副本的节点故障，数据要么丢失，要么至少在节点恢复前不可访问。

我们重新审视第 6 章中的几种复制方法，看哪些能做到线性一致：

单主复制（潜在线性一致）

在采用单主复制的系统中，主节点持有用于写入的主副本，从节点在其他机器上维护备份副本。只要所有读写都发到主节点，它们就可能是线性一致的。但这要建立在你确实知道主节点是谁这一前提上。正如第 373 页"分布式锁与租约"中讨论的，某节点完全可能错以为自己是主节点而其实不是——这种"幻觉中的主节点"若继续提供服务，很可能违反线性一致性 [23]。配合异步复制，故障转移甚至可能丢失已提交的写入，既违反持久性也违反线性一致性。

按分片划分单主数据库（每个分片有独立主节点）不影响线性一致性，因为它本就是一种单对象保证。跨分片事务则是另一回事（见第 323 页"分布式事务"）。

共识算法（很可能线性一致）

有些共识算法本质上就是带自动选主与故障转移的单主复制。它们经过精心设计以防止脑裂，可以安全地实现线性一致存储。例如 ZooKeeper 使用 Zab 共识算法 [24]，etcd 使用 Raft [25]。不过仅仅在系统里用上共识，并不保证它的所有操作都是线性一致的：如果它允许在某节点上直接读、而不检查该节点是否仍是主节点，那读到的就可能是过期值——刚选出新主时尤为如此，旧主返回的还是旧值。

多主复制（不线性一致）

使用多主复制的系统通常不是线性一致的，因为它们在多个节点上并发处理写入再异步复制到其他节点；因此可能出现需要解决的写冲突（见第 222 页"处理冲突写入"）。

无主复制（很可能不线性一致）

对采用无主复制（Dynamo 风格；见第 229 页"无主复制"）的系统，有人有时声称只要做 quorum 读写（w + r > n）就能获得"强一致性"。但视具体算法以及你对强一致性的定义而定，这一说法并不完全正确。

基于墙钟时间的 LWW 冲突解决方法（如 Cassandra 与 ScyllaDB 中所用）几乎肯定是非线性一致的，因为受时钟漂移影响（见第 362 页"依赖同步时钟"），时钟时间戳无法保证与真实事件顺序一致。即便用了 quorum，仍可能出现非线性一致行为，下面这一节会演示。

直觉上，似乎在 Dynamo 风格模型中读写 quorum 就该是线性一致的。然而在网络延迟可变的情况下，仍可能出现竞态，如图 10-6 所示。

图 10-6 中 x 初值为 0，写客户端通过把写发往全部三副本（n=3, w=3）来更新 x 到 1。同时客户端 A 从两副本的 quorum（r=2）读，看到一个副本上是新值 1，另一副本上是旧值 0。同时与该写并发，客户端 B 从另一组两副本的 quorum 读，得到的两份都是 0。

虽然 quorum 条件 (w + r > n) 满足，但这一执行并非线性一致：B 的请求开始于 A 的请求完成之后，但 B 返回了旧值，而 A 返回了新值。（这又是图 10-1 中 Aaliyah 与 Bryce 的情景。）

图 10-6. 使用 quorum 仍出现非线性一致执行 让 Dynamo 风格的 quorum 变为线性一致是可能的，代价是性能下降。读取客户端必须在把结果返回应用之前同步完成读修复（见第 231 页"补回错过的写"）[26]；写入之前，写客户端也必须先读取一组 quorum 节点，拿到此前所有写中的最大时间戳，再保证本次写的时间戳更大 [27, 28]。然而 Riak 因性能开销不做同步读修复。Cassandra 虽然在 quorum 读时会等待读修复完成 [29]，但它因为使用墙钟时间戳而仍丢失了线性一致性。

而且只有线性一致的读和写操作能这样实现，线性一致的 CAS 操作不行——它需要共识算法 [30]。综上，最稳妥的假定是：采用 Dynamo 风格复制的无主系统不提供线性一致性，即便配以 quorum 读写也不例外。

线性一致性的代价

既然有些复制方式能提供线性一致性、有些不能，深入比较一下线性一致性的利弊就很有意思。

第 6 章中我们已讨论过不同复制方式的若干用途；例如多主复制常常很适合多区域部署（见第 216 页"地理分布的运营"）。这样的部署示例见图 10-7。

设想两个区域之间发生网络中断会怎样。假设各区域内的网络运转正常，客户端能访问到本区域的服务，但区域之间无法互通。这就是所谓的网络分区。

图 10-7. 网络中断迫使在线性一致性与可用性之间二选一 在多主数据库里，每个区域都能继续正常运行。由于一个区域的写是异步复制到另一区域的，网络中断期间写入只是先在本地排队，等连通恢复后再交换。

而采用单主复制时，主节点必须位于其中某个区域。任何写、任何线性一致读都必须发到主节点；因此对连到从节点所在区域的客户端来说，读写请求必须同步跨网络发到主节点所在区域。

若区域间网络中断，单主架构下连到从节点区域的客户端就联系不上主节点，既无法写入数据库，也无法进行线性一致读。它们仍可以读从节点，但读到的可能是过期值（非线性一致）。一旦应用要求线性一致读写，网络中断便会让那些联系不上主节点的区域中的应用陷入不可用。

如果客户端能直接连到主节点所在区域，则不会受影响，应用在那里照常工作。但只能连到从节点区域的客户端就会经历一次中断，直到网络链路恢复。

CAP 定理

这一问题并非单主与多主复制的副作用。任何线性一致的数据库都会面临，无论其实现方式如何；问题也不限于多区域部署——只要网络不可靠，即便在单一区域内也可能发生。其中的权衡如下：

• 如果你的应用要求线性一致性，而某些副本因网络问题与其他副本失联，那么这些副本会暂时不能处理请求：它们要么等到网络问题修复，要么返回错误（无论怎样它们都变得不可用）。这种选择有时被称为 CP（网络分区下保持一致）。
• 如果你的应用不要求线性一致性，可以让每个副本独立处理请求，即便它与其他副本失联（如多主复制）。这种情况下，应用面对网络问题仍能保持可用，但其行为不是线性一致的。这种选择被称为 AP（网络分区下保持可用）。

由此可见，不要求线性一致性的应用对网络问题更宽容。这一洞见以 CAP 定理 [31, 32, 33, 34] 而广为流传，由 Eric Brewer 于 2000 年命名，尽管这一权衡早自 1970 年代起就为分布式数据库设计者所知 [35, 36, 37]。

CAP 最初是作为一条经验法则提出的，没有精确定义，意在引发关于数据库取舍的讨论。当时许多分布式数据库聚焦于在共享存储的机器集群上提供线性一致语义 [21]，CAP 鼓励数据库工程师去探索更广阔的设计空间——分布式无共享系统，因为后者更适合实现大规模 Web 服务 [38]。CAP 在这一文化转变中功不可没——它帮助引发了 NoSQL 运动，催生出 2000 年代中期一波新数据库技术。

CAP 定理形式化定义之后 [32] 适用范围其实非常窄：只考虑一种一致性模型（即线性一致性）和一种故障（网络分区）；据 Google 的数据，分区不到 8% 故障原因 [39]。它对网络延迟、节点失效或其他权衡几乎只字未提。因此尽管 CAP 在历史上影响深远，对今天的系统设计实用价值有限 [4, 45]。

已有一些将 CAP 推广的尝试。例如 PACELC 原则指出，系统设计者还可能在网络运行良好时为降低延迟而弱化一致性 [40, 46, 47]：网络分区（P）期间需在可用性（A）与一致性（C）间选择；不存在分区（E）时则在低延迟（L）与一致性（C）间选择。然而这一定义继承了 CAP 的诸多问题，例如对一致性与可用性的反直觉定义。

分布式系统中还有不少更有趣的不可能性结果 [41]；CAP 如今已被更精确的结果取代 [42, 43]，今天基本只剩下历史意义。

那个无益的 CAP 定理

CAP 有时被表述为一致性、可用性、分区容忍性：三选二。可惜这种说法颇具误导性 [34]：网络分区本是一种故障，并非你"选不选"的事——它会不会发生，不取决于你的意愿。能保证不出网络分区的唯一办法就是没有网络——也就是只用一个副本——但那样高可用也就无从谈起。

网络正常时，系统可以同时提供一致性（线性一致性）与可用性；一旦网络出故障，就必须二选一。因此 CAP 更恰当的表述应是要么分区时一致、要么分区时可用 [44]。网络越可靠，需要做出这种选择的次数就越少，但终究无法避免。

CP/AP 这种分类还有几处缺陷 [4]：一致性被形式化为线性一致性（定理对更弱的一致性模型并未涉及）；而可用性的形式化 [32] 也与该词的通常含义不同 [45]——许多高可用（容错）系统其实并不满足 CAP 对可用性的特殊定义。此外一些系统设计者（出于正当理由）既不提供线性一致性、也不提供 CAP 所设想的可用性形式，因此那些系统既非 CP 也非 AP [46, 47]。

总之 CAP 周围充斥着误解与混淆，对我们理解系统并无多少帮助，最好不要在它上面过多纠缠。

线性一致性与网络延迟

尽管线性一致性是一项有用的保证，令人意外的是，实践中真正线性一致的系统其实很少。例如，即便现代多核 CPU 上的 RAM 也不是线性一致的 [48]：一个线程在某 CPU 核上向某内存地址写入，另一线程在不同的 CPU 核上稍后读同一地址，并不能保证一定读到第一个线程写入的值（除非使用了内存屏障或 fence [49]）。

原因在于每个 CPU 核都有各自的内存缓存与存储缓冲：读默认走缓存，对缓存的修改异步写回主内存。访问缓存比访问主内存快得多 [50]，这对现代 CPU 取得良好性能至关重要；但这也意味着数据存在多份（一份在主内存，可能还有几份在各级缓存里），它们彼此异步更新——线性一致性也就丢了。

为什么要做这种权衡？用 CAP 定理去解释多核内存一致性模型并无意义：在一台计算机内部，我们通常假定通信可靠，并不指望某个 CPU 核与机器其他部分断开仍能继续工作。这里放弃线性一致性的原因是性能，而不是容错 [46]。

许多选择不提供线性一致保证的分布式数据库也是如此：它们这样做主要是为了提升性能，而非为了容错 [40]。线性一致系统的延迟往往更高——并不只是网络故障时如此，平时也是。

那么是否存在更高效的线性一致存储实现？看来答案是没有。Attiya 与 Welch [51] 证明：若要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。在网络延迟高度可变的网络中（绝大多数计算机网络皆是；见第 352 页"超时与无界延迟"），线性一致读写的响应时间不可避免地会很高。更快的线性一致算法不存在，但较弱的一致性模型可以快得多——因此这一权衡对延迟敏感系统极为重要。第 13 章我们会讨论一些在不牺牲正确性的前提下避开线性一致性的做法。

ID 生成器与逻辑时钟

许多应用在创建数据库记录时需要给它们分配一个唯一 ID，以作为引用记录的主键。单节点数据库里常用自增整数：它紧凑，只需 64 位（甚至 32 位——如果你能确定记录数不会超过 40 亿；但这其实有点冒险）即可存下。

自增 ID 的另一好处是：ID 的顺序就告诉你记录的创建顺序。例如图 10-8 展示了一个聊天应用，按发布顺序给消息分配自增 ID。按 ID 递增顺序显示消息，聊天线索就一目了然：Aaliyah 提的问题分配到 ID 1，Bryce 的回答 ID 更大——也就是 3。

图 10-8. 聊天应用中给消息分配自增整数 ID 的 ID 生成器 这种单节点 ID 生成器又是一类线性一致系统：每次取 ID 的请求都是一次原子操作——把计数器加一并返回旧值（即一次 fetch-and-add）；线性一致性保证了若 Aaliyah 的发帖在 Bryce 的发帖之前完成，则 Bryce 消息的 ID 必然大于 Aaliyah 的。图 10-8 中 Aaliyah 与 Caleb 的消息是并发的，因此线性一致性不规定它们 ID 的相对顺序，只要保证唯一即可。

内存中的单节点 ID 生成器很容易实现：用 CPU 提供的原子加指令，多个线程便可安全地对同一计数器加一；稍加工作就能把计数器持久化，让节点崩溃重启后不会重置计数（否则会产生重复 ID）。真正的问题在于：

• 单节点 ID 生成器无法容错——该节点本身就是单点故障。
• 在另一个区域创建记录时会很慢——可能需要一趟绕到地球另一端取 ID。
• 写吞吐高时，那个单节点可能成为瓶颈。

为此可以考虑几种替代方案：

分片 ID 分配

可以让多个节点同时分配 ID——例如一个只发偶数、另一个只发奇数。一般可在 ID 中保留若干位用作分片号。这种 ID 仍紧凑，但失去了顺序性：看到带 ID 16 和 17 的两条聊天消息，你并不知道 16 是不是真的先发，因为它们由不同节点分配，节点之间可能彼此领先。

预分配 ID 块

由单节点 ID 生成器一次分一整块 ID，而非单个 ID。比如节点 A 领走 1 至 1000 这一段，节点 B 领走 1001 至 2000；之后各节点独立从自己的块里发 ID，本地号将用尽时再请求新块。这种方案同样不能保证正确顺序：可能一条消息拿到 1001 至 2000 区间的 ID，而稍后一条消息却从另一节点拿到 1 至 1000 区间的 ID。

随机 UUID

可以使用通用唯一标识符（UUID），又叫全局唯一标识符（GUID）。它最大的优势是任何节点都可以本地生成而无需通信，但占用空间更大（128 位）。UUID 有多个版本；最简单的是版本 4，本质上就是一段长到几乎不可能两节点选到同一值的随机数。可惜这种 ID 的顺序也是随机的——比较两个 ID，说不出哪个更新。

唯一化的墙钟时间戳

如果节点时钟通过 NTP 保持大致正确，可以把这一时钟的时间戳放到 ID 的高位，低位再填一些额外信息以保证唯一（即便时间戳本身重复）——例如分片号加分片内自增计数，或一段长随机值。这种做法见于 UUID v7 [52]、X 的 Snowflake [53]、ULID [54]、Hazelcast 的 Flake ID 生成器、MongoDB 的 ObjectID 等众多方案 [52]。这类生成器在应用代码或数据库内部均可实现 [55]。

上述方案生成的 ID 都唯一（至少冲突概率小到可以忽略），但其顺序保证远弱于单节点自增方案。

如第 362 页"为事件排序的时间戳"中所讨论，墙钟时间戳最多只能给出近似排序。若较早的写从一只稍快的钟拿到时间戳、较晚的写从一只稍慢的钟拿到时间戳，时间戳的顺序就可能与事件实际发生顺序不一致。如果时钟因使用非单调时钟而出现跳变，单节点生成的时间戳也可能给出错误的顺序。因此基于墙钟时间的 ID 生成器一般不会是线性一致的。

借助高精度时钟同步（用原子钟或 GPS 接收器）可以减少这种乱序，但若能不依赖特殊硬件就生成既唯一又顺序正确的 ID 自然更好。下面就来看一种刚好能做到这点的时钟。

逻辑时钟

第 358 页"不可靠的时钟"中讨论过墙钟与单调时钟。两者都是物理时钟：用硬件设备测量时间流逝（秒、毫秒、微秒等）。

分布式系统中还常用另一类时钟，称为逻辑时钟。与物理时钟不同，逻辑时钟是一种算法，对已发生的事件计数。因此逻辑时钟的时间戳无法告诉你现在几点，但可以用来比较两个时间戳，判断哪个更早、哪个更晚。

逻辑时钟的一般要求如下：

• 时间戳紧凑（几个字节大小）且唯一。
• 任意两个时间戳均可比较，能判定哪个更早（即全序）。
• 时间戳的顺序与因果一致：若操作 A 在操作 B 之前发生，则 A 的时间戳小于 B 的时间戳。（先前已在第 238 页"happens-before 关系与并发性"中讨论过因果。）

单节点 ID 生成器满足这些要求，但前面讨论过的几种分布式 ID 生成方案则不满足因果排序要求。

Lamport 时间戳

幸运的是，有一种简单方法可生成与因果一致的逻辑时间戳，并能作为分布式 ID 生成器使用——这就是 Lamport 时钟，由 Leslie Lamport 于 1978 年提出 [56]，如今是分布式系统领域被引用最多的论文之一。

虽然 Lamport 时钟提供全序，但它不提供线性一致性——它没法保证某个值是最新的，只是给事件分配 ID，使得若事件 A 在事件 B 之前发生，A 的 ID 就小于 B 的 ID。

图 10-9 展示了 Lamport 时钟在图 10-8 聊天例子中如何工作。每个节点都有一个唯一标识符——图 10-9 中是 Aaliyah、Bryce、Caleb 这样的名字，实际中可以是随机 UUID 或类似的东西。每个节点还维护一个已处理操作数的计数。Lamport 时间戳就是一个 (计数, 节点 ID) 二元组——两节点的计数值有时会相同，但把节点 ID 也纳入时间戳就保证了每个时间戳的唯一性。

图 10-9. Lamport 时间戳给出与因果一致的全序 每当一个节点生成时间戳时，就把自己的计数器加一，再使用新值。每当节点收到另一节点发来的时间戳时，若该时间戳中的计数值大于本地计数，就把本地计数升到该值。

图 10-9 中 Aaliyah 发出自己的消息时尚未看到 Caleb 的，反之亦然；两人都从初始计数 0 开始，因此都把本地计数加一，并将新计数 1 附在自己的消息上。Bryce 收到这两条消息后把本地计数升到 1；最后他给 Aaliyah 回复时再把计数加一，将新值 2 附在消息上。

比较两个 Lamport 时间戳时，先比较计数——例如 (2, "Bryce") 大于 (1, "Aaliyah")，也大于 (1, "Caleb")；若计数相同，再按字典序比较节点 ID。本例中时间戳顺序为 (1, "Aaliyah") < (1, "Caleb") < (2, "Bryce")。

混合逻辑时钟

Lamport 时间戳擅长刻画事件发生的顺序，但也存在限制：

• 它与物理时间没有直接关系，因此无法用来查找诸如"某一天发布的所有消息"，必须另外存物理时间。
• 若两节点从不通信，一节点上计数器的递增就永远不会反映到另一节点上。结果是不同节点上大约同一时间产生的事件，计数值可能相差悬殊。

混合逻辑时钟则同时具备墙钟时钟的优点与 Lamport 时钟的排序保证 [57]。它像物理时钟一样以秒或微秒计数；又像 Lamport 时钟那样，当某节点看到另一节点发来的时间戳大于本地时钟值时，就把本地值前移到对方时间戳。这样一来，若某个节点时钟走得快，其他节点在与之通信时也会把自己的钟跟着前移。

每次混合逻辑时钟生成时间戳时也会递增，因此即便底层物理时钟向后跳（如 NTP 调整），混合逻辑时钟仍单调前进。这使混合逻辑时钟可能略微领先底层物理时钟，算法的细节会确保这一差距尽量小。

因此，混合逻辑时钟的时间戳几乎可以当作普通墙钟时间戳来用，同时还有一个额外性质：其顺序与 happens-before 关系一致。它不依赖任何特殊硬件，只要求时钟大致同步即可。CockroachDB 等系统就采用了混合逻辑时钟。

Lamport / 混合逻辑时钟 与 向量时钟

第 295 页"多版本并发控制"中讨论过快照隔离的常见实现方式：每个事务获得一个事务 ID，可以看到 ID 比它小的事务所做的写入，而比它大的事务的写入对它隐藏。Lamport 时钟与混合逻辑时钟很适合生成这种事务 ID，因为它们能保证快照与因果一致 [58]。

当多个时间戳并发生成时，这些算法只是任意把它们排个序——也就是说，给定两个时间戳，你通常无法判断它们是并发生成的，还是其中一个先于另一个。（图 10-9 中倒能看出 Aaliyah 与 Caleb 的消息必为并发，因为它们的计数相同；可一旦计数不同就分不清是否并发了。）

如果你想判断记录是否为并发创建，就需要另一种算法，如向量时钟。向量时钟为每个节点维护一个计数，每次写入都把所有节点的计数值附在写上。如果某节点上写 A 的计数比 B 高、而另一节点上写 B 的计数又比 A 高，则 A 与 B 必为并发（见第 237 页"检测并发写"）。缺点是向量时钟的时间戳比前述其他几种时间戳占用空间大得多——系统中每个节点都对应一个整数。

线性一致 ID 生成器

尽管 Lamport 时钟与混合逻辑时钟提供了有用的排序保证，这种排序仍弱于前面讨论过的线性一致单节点 ID 生成器。回想线性一致性的要求：若请求 A 在请求 B 开始前完成，B 必须有更大的 ID，即便 A 与 B 从未通信过。而 Lamport 时钟只能保证某节点生成的时间戳大于自己见过的任何时间戳；对没见过的时间戳就没有这种保证。

图 10-10 展示了非线性一致 ID 生成器可能引发的问题。设想用户 A 想在社交媒体上私下给朋友分享一张令人尴尬的照片：A 的账号最初是公开的，他先用笔记本把账号设置改为私有，然后用手机上传照片。既然 A 是按此顺序操作的，他理应期望照片上传受到新的、更严格的账号权限的约束。但如图所示，结果未必如此。

图 10-10. 用户 A 先把账号设为私有再分享照片。若 ID 生成器不是线性一致的，未授权观众也可能看到这张照片。 账号权限与照片分别存放在两个不同的数据库（或同一数据库的不同分片）中，假定它们用 Lamport 时钟或混合逻辑时钟给每次写分配时间戳。由于照片数据库并未从账号数据库读取数据，照片数据库本地的计数器可能稍稍落后，导致照片上传分配到的时间戳比账号设置更新的时间戳要小。

此时假设某位观众（并非 A 的好友）正在浏览 A 的资料页，他的读基于 MVCC 的快照隔离实现。便可能出现：观众读取所用的时间戳大于照片上传时间戳，却小于账号设置更新时间戳——结果系统判定读取时账号仍是公开状态，从而把那张本不该让他看到的尴尬照片展示给了他。

你大概能想到几种修复办法：照片数据库或许应该在写入前先去读取用户的账号状态，可这种检查很容易被遗漏；如果 A 的所有操作都在同一台设备上完成，App 也可以在本地跟踪该用户写入的最新时间戳——但本例中 A 同时用了笔记本和手机，这就不太容易。最简单的办法是采用一个线性一致的 ID 生成器，由它确保照片上传的 ID 一定大于账号权限更新的 ID。

实现一个线性一致的 ID 生成器

确保 ID 分配线性一致最简单的办法是真的只用一个节点。该节点只需做三件事：被请求时原子地把计数器加一并返回旧值；把计数值持久化（让节点崩溃重启后不会产生重复 ID）；为容错把它复制出去（用单主复制）。实践中的确有人这么做——例如 TiDB/TiKV 把它称为时间戳预言机（timestamp oracle），灵感来自 Google 的 Percolator [59]。

作为一种优化，你可以免去每次请求都做磁盘写与复制：让 ID 生成器写一条描述一批 ID 的记录；记录持久化并复制完成后，节点便按顺序发出这一批 ID；当本批将要用完前，再持久化并复制下一批的记录。这样即便节点崩溃重启或故障转移到从节点，最多只会跳过一些 ID，但不会重复或乱序。

ID 生成器不容易分片：多个分片各自独立分配 ID 时，就再也无法保证 ID 的顺序是线性一致的。也不容易跨区域分布；因此在地理上分布的数据库中，所有取 ID 的请求都得到某一区域的节点。所幸 ID 生成器的工作非常简单，单节点能处理相当高的请求吞吐。

如果不想用单节点 ID 生成器，可以仿照 Google 的 Spanner（见第 365 页"全局快照的同步时钟"）：它依赖一种特殊的物理时钟，不仅返回单一时间戳，还返回一段表示时钟读数不确定度的区间；Spanner 在返回结果前会等待这一不确定区间过去。

假定不确定区间是正确的（即真实的当前物理时间总落在该区间内），这一过程同样保证：若一个请求在另一个开始前完成，则后一个请求会得到更大的时间戳。这种做法无需任何通信就实现了线性一致的 ID 分配；不同区域间的请求也能被正确排序，且无需等待跨区域往返。代价是需要硬件与软件支持，让时钟紧密同步并能算出所需的不确定区间。

用逻辑时钟强制约束

第 409 页"约束与唯一性保证"中我们看到，线性一致的 CAS 操作可在分布式系统中实现锁、唯一性约束等构造。这就引出一个问题：逻辑时钟或线性一致的 ID 生成器是否也足以实现这些？

答案是：还不够。当多个节点同时试图获取同一把锁或注册同一个用户名时，可以用逻辑时钟给每个请求分配时间戳，并把时间戳最低的那个判为胜者。若时钟是线性一致的，你便知道任何未来请求都会拿到更大的时间戳，因此可以确信不会出现某个未来请求得到比胜者更低的时间戳。

可惜问题还有一部分没解：节点怎么确认自己的时间戳就是最低的？要确认这一点，它必须从每个可能生成时间戳的其他节点都收到回应 [56]。一旦其中某个节点故障，或因网络问题不可达，整个系统就停摆，因为我们无法确认那个节点的时间戳是否更低。这显然不是我们想要的容错系统。

要以容错方式实现锁、租约及类似构造，我们需要比逻辑时钟或 ID 生成器更强的工具——共识。

共识

本章见过的若干例子都是只有单节点时容易办、加上容错就难得多的事情：

• 数据库可以是线性一致的，只要你只用一个主节点并把所有读写都放在该主节点上做。但若主节点故障，怎样在避免脑裂的前提下完成故障转移？怎样确保某个节点不会自以为是主、却其实在临时暂停期间已被投票罢免？
• 单节点上的线性一致 ID 生成器只是一个带原子 fetch-and-add 指令的计数器——但它若崩溃了怎么办？
• 原子 CAS 操作在多个进程争抢锁或租约时很有用，能决定谁拿到，或用来确保具有给定名称的文件或用户的唯一性。在单节点上，CAS 可以简单到只是一条 CPU 指令，但怎么把它做成容错的？

事实上，这些都是同一个根本性分布式系统问题的不同侧面：共识。共识的标准提法是：让多个节点对一个值达成一致。它是分布式计算最重要、最根本的问题之一，也以"难以正确实现"而臭名昭著 [60, 61]，许多系统都曾在此栽跟头。如今我们已讨论过复制（第 6 章）、事务（第 8 章）、系统模型（第 9 章）与线性一致性（本章），终于可以正式着手攻克共识问题了。

最知名的共识算法包括 Viewstamped Replication [62, 63]、Paxos [60, 64, 65, 66]、Raft [25, 67, 68] 与 Zab [20, 24, 69]。它们颇有相似之处，但并不相同 [70, 71]。这些算法都工作在非拜占庭系统模型下：网络通信可能任意延迟或丢失，节点也可能崩溃、重启或失联，但算法假定节点会忠实遵循协议、不会蓄意作恶。

也有共识算法能容忍若干拜占庭节点——即不忠实遵循协议的节点，比如向不同节点发送相互矛盾的消息。一种常见假设是拜占庭故障节点少于全体的三分之一 [28, 72]。这类算法被用于区块链等 [73]。然而正如第 377 页"拜占庭故障"中所述，拜占庭容错算法超出本书范围。

共识的不可能性

你或许听说过 FLP 结果 [74]——以作者 Fischer、Lynch、Paterson 命名——它证明：在节点可能崩溃的前提下，没有任何算法能始终达成共识。可分布式系统中节点崩溃是必须假定会发生的，那可靠的共识不就成了不可能？而我们这里却在讨论实现共识的算法，怎么回事？

首先，FLP 并未断言共识永远不可达；它只是说不能保证共识算法总会终止。其次，FLP 是在异步系统模型（见第 380 页"系统模型与现实"）下、假定算法是确定性的前提下证明的——这意味着算法既不能用时钟也不能用超时。一旦允许算法借助超时去怀疑某节点已崩溃（哪怕偶尔猜错），共识就变得可解 [75]；甚至只允许算法使用随机数也已足够 [76]。

因此，FLP 关于共识不可能性的结果虽具重大理论意义，分布式系统在实践中通常仍能达成共识。

共识的多张面孔

共识可以有多种表述方式。例如：

• 单值共识与原子 CAS 操作非常相似，可用于实现锁、租约和唯一性约束。
• 构建只追加日志也需要共识，这一问题通常形式化为全序广播。有了这种日志，便可实现状态机复制、基于主节点的复制、事件溯源以及其他有用模式。
• 原子 fetch-and-add（即原子加）操作同样等价于共识。
• 多数据库或多分片事务的原子提交要求所有参与者就"提交还是中止"达成一致。

事实上，上述问题彼此等价：解决其中任一问题的算法都可以转化为求解其他问题的算法。这是一个深刻而出人意料的洞见，也是我们能把这些表面差异颇大的事物统统归入"共识"这一标签下的原因。下面我们逐一审视，看看为何如此。

单值共识

让多个节点就某个单一值达成一致很有用。例如：

• 当采用单主复制的数据库初次启动、或现有主节点故障时，可能有多个节点同时尝试成为主节点；多个节点也可能并发争抢一把锁或租约。共识能让它们决定谁胜出。
• 当几个人同时尝试预订飞机上的最后一个座位、剧院里的同一座位，或注册相同用户名时，若谁先到并不显然，共识算法可以决定谁该成功。

更一般地，一个或多个节点可提议值，共识算法在那些值之中决定一个。在上面的例子中，每个节点可以提议自己的 ID，算法决定哪个节点 ID 应当成为新主节点、租约持有者，或机票/座位的购买者。在这种形式化下，共识算法必须满足以下性质 [28]：

一致同意（Uniform agreement）

没有两个节点决定不同的值。

完整性（Integrity）

某节点决定一个值后，不能改主意决定另一个值。

有效性（Validity）

若节点决定值 v，则 v 是某节点提议过的。

终止性（Termination）

每个不崩溃的节点最终都会决定一个值。

如果你想决定多个值，可以为每个值各跑一次共识算法实例。例如剧院里每个可订座位单独跑一次共识，每个座位都会有一个决定（一个买家）。

一致同意与完整性两条性质定义了共识的核心思想：所有人决定同一个结果，且决定之后不能反悔。有效性则排除了平凡解——比方说一个无论提议什么都决定为 null 的算法，它满足一致同意与完整性，却不满足有效性。

如果不在乎容错，前三条性质很容易满足。可以硬编码一个节点作"独裁者"，让它做所有决定。然而那个节点一旦故障，系统就再也做不出任何决定——这正是没有故障转移的单主复制。一切难处都源自对容错的需求。

终止性形式化了"容错"这一概念。它本质上是说：共识算法不能干等着不动——它必须有所进展；即便有些节点故障，其他节点仍必须做出决定。（终止性是一条活性性质，其余三条是安全性性质——见第 382 页"区分安全与活性"。）

如果某个崩溃节点可能恢复，你可以等它回来。然而共识算法必须确保：即便某个崩溃节点彻底消失、再也回不来，它也能做出决定。（与其想象软件崩溃，不如想象一场地震引发山体滑坡摧毁了承载该节点的数据中心，节点被埋在 9 米厚的泥浆之下，再也不会上线。）

当然，如果所有节点都崩溃、一个不剩，那没有任何算法能做出决定。算法能容忍的故障数始终是有限的。事实上可以证明：任何共识算法都至少需要多数节点正常运行才能保证终止 [75]。这个"多数"可以稳妥地用作一个 quorum（见第 231 页"用 quorum 进行读写"）。

因此终止性受制于"不可达节点少于一半"这一假设。不过多数共识算法保证安全性——一致同意、完整性和有效性——始终成立，即使多数节点故障或发生严重网络问题 [77]。这意味着大规模故障会让系统暂停处理请求，但不会让共识系统因做出不一致决策而被破坏。

CAS 即共识

CAS 操作的语义是：检查某对象当前值是否等于一个期望值；若相等，则原子地把对象更新为新值；若不等，对象保持不变，操作返回错误。

如果你已有一个容错的线性一致 CAS 操作，解决共识就很简单：先把对象初始化为 null，然后让每个想提议某值的节点对该对象执行一次 CAS——期望值为 null，新值即它想提议的值（假定非空）。最终对象被设成的那个值，就是被决定的值。

反过来，若你有共识的解决方案，也可以实现 CAS。当一个或多个节点想用相同期望值执行 CAS 时，它们通过共识协议各自提议自己 CAS 调用的新值，然后把对象设为共识决定的那个值。提议值未被选中的 CAS 调用一律返回错误。使用不同期望值的多次 CAS 调用则各自跑一次共识协议。

这表明 CAS 与共识等价 [30, 75]。两者在单节点上都简单，但做成容错都难。作为 CAS 在分布式场景中的一个例子，第 202 页"由对象存储支撑的数据库"中我们看到对象存储的条件写操作——只有当该名对象自客户端上次读取以来未被其他客户端创建或修改时，写入才被允许。

共享日志即共识

我们见过若干种日志的例子，比如复制日志、事务日志、预写日志。日志保存一连串日志条目，任何读取者看到的条目顺序都相同。有时日志只允许一个写者追加新条目；而共享日志则允许多个节点请求追加条目。一个例子就是单主复制：任何客户端都可以让主节点做一次写，主节点将其追加到复制日志，所有从节点按与主节点相同的顺序应用这些写入。

更正式地说，共享日志支持两个操作：请求把某值加入日志，以及读日志中的条目。它必须满足以下性质：

最终追加

若一个节点请求把某值加入日志，且该节点未崩溃，那么该节点最终必须能在某个日志条目中读到该值。

可靠投递

没有日志条目丢失——如果某节点读到一条日志条目，则任何不崩溃的节点最终也必须读到该条目。

只追加

节点读到一条日志条目后，该条目就不可变；新条目只能加在它之后，不能插在它之前。如果节点重读日志，看到的条目内容与顺序都与最初一致（即便经历了崩溃重启）。

一致约定

若两个节点都读到了日志条目 e，那么在读到 e 之前它们必定以相同顺序读到了完全相同的日志条目序列。

有效性

若某节点读到一条包含某值的日志条目，则此前必有节点请求过把该值加入日志。

共享日志可以借助全序广播协议（又称原子广播或全序多播）实现 [28, 78, 79]。要把某个值加入日志，我们用该协议把它"广播"出去；当协议"投递"该值时，它就成为可读日志条目的一部分。

有了共享日志的实现，解决共识就很容易：每个想提议某值的节点请求把它加入日志，最先出现在第一条日志条目中的那个值就是被决定的值。由于所有节点都以相同顺序读日志条目，它们必然就"最先投递的是哪个值"达成一致 [30]。

反过来，如果你已有共识的解决方案，也可以实现共享日志。细节稍复杂，基本思路如下 [75]：

1. 日志的每个未来条目都对应一个槽位；为每个槽位单独运行一次共识实例，决定该槽位应放什么值。
2. 节点想把某值加入日志时，向某个尚未被决定的槽位提议该值。
3. 当共识算法对某个槽位作出决定，且其前所有槽位都已决定时，该决定值就被追加到日志末尾；紧随其后已决定的连续槽位也依次把它们的决定值追加上来。
4. 若某节点提议的值未被该槽位选中，它便对后面的槽位重新提议。

这表明共识等价于全序广播与共享日志。没有故障转移的单主复制无法满足活性要求，因为主节点崩溃后就不再投递消息。一如既往，难点在于如何安全且自动地完成故障转移。

Fetch-and-add 即共识

第 423 页"线性一致 ID 生成器"中讨论过的线性一致 ID 生成器，接近共识但还差一点。这种 ID 生成器可以用 fetch-and-add 操作实现：原子地把计数器加一并返回旧值。

如果你有 CAS 操作，实现 fetch-and-add 不难：先读取计数器值，然后做一次 CAS——期望值就是读到的值，新值为它加一。若 CAS 失败，再读取再重试，直到成功为止。这比原生 fetch-and-add 在有竞争时效率低些，但功能上等价。既然你能用共识实现 CAS，也就能用共识实现 fetch-and-add。

反过来，如果你已有一个容错的 fetch-and-add，能用它解决共识吗？设想把计数器初始化为 0，每个想提议值的节点都调用一次 fetch-and-add 把计数器加一。由于 fetch-and-add 是原子的，恰好有一个节点会读到初始值 0，其他节点读到的都是已被加过至少一次的值。

现在我们规定：读到 0 的节点是胜者，它的值就是被决定的值。这对读到 0 的节点没问题，但其他节点有麻烦——它们知道自己不是胜者，却不知道谁是胜者。胜者可以再向其他节点发消息告诉它们自己赢了，但要是胜者在消息发出之前就崩溃了怎么办？那时其他节点就只能干等，无法决定任何值，共识也就无法终止；它们也不能退而决定读到 0 的节点提议的值。

不过有一个例外：若我们确知至多只有两个节点会提议值，节点便可以先互相通报各自打算提议的值，再各自执行一次 fetch-and-add——读到 0 的节点决定自己的值，读到 1 的节点决定另一节点的值。这就解决了两节点间的共识问题，因此 fetch-and-add 的共识数为 2 [30]。相比之下，CAS 与共享日志能解决任意数量节点提议值时的共识问题，故其共识数为 ∞（无穷大）。

原子提交即共识

第 323 页"分布式事务"中我们看到了原子提交问题，即让参与分布式事务的多个数据库或分片要么都提交、要么都中止。我们也看到了两阶段提交算法，它依赖一个本身是单点故障的协调器。

共识与原子提交是什么关系？乍看二者很像——都要求节点就某种约定达成一致。但有一个关键区别：共识里决定任何被提议过的值都行，而原子提交里只要任一参与者投了中止，算法就必须中止。更精确地说，原子提交要求以下性质 [80]：

一致同意

不可能一个节点提交而另一个中止。

完整性

节点提交后不能反悔去中止，反之亦然。

有效性

若一个节点提交，则所有节点之前必投了提交。若任一节点投了中止，则所有节点必中止。

非平凡性

若所有节点都投提交、且未发生通信超时，则所有节点必须提交。

终止性

每个不崩溃的节点最终要么提交、要么中止。

有效性保证只有所有节点都同意时事务才会提交；非平凡性则禁止算法总是简单中止（但允许在节点间通信超时时中止）。其余三条性质本质上与共识一致。

若你已有共识的解决方案，可以用多种方式解决原子提交 [80, 81]。一种做法是这样：要提交事务时，每个节点把自己的"提交"或"中止"投票发给所有其他节点；从所有其他节点都收到"提交"票的节点通过共识算法提议"提交"；收到"中止"票或经历超时的节点则通过共识算法提议"中止"。共识算法做出决定后，每个节点据此提交或中止。

在这一算法中，只有所有节点都投"提交"时才会提议"提交"；任何一节点投了"中止"，共识里所有提议都将是"中止"。也可能出现一些节点提议"中止"、另一些提议"提交"的情形——例如所有节点都投了提交，却有些通信超时；这种情况下，节点们最终是提交还是中止都无所谓，只要大家做相同的事即可。

反过来，如果你已有一个容错的原子提交协议，也能用它解决共识。每个想提议值的节点在一组 quorum 节点上启动一次事务，并在每个节点上做一次单节点 CAS——若该寄存器尚未被其他事务设过，就将其设为本次提议值；CAS 成功则该节点投提交，否则投中止。若原子提交协议提交了该事务，其值就成为共识的决定；若中止，提议节点便用新事务重试。

这表明原子提交与共识同样彼此等价。

实践中的共识

我们已看到单值共识、CAS、共享日志与原子提交彼此等价：解决其中之一的方案可以转换为另一个的方案。这是一个有价值的理论洞见，却没回答一个实际问题：在共识的诸多形式化中，哪一种在实践中最常用？

答案是：多数共识系统提供共享日志（一种等价于全序广播的抽象）。Raft、Viewstamped Replication 与 Zab 开箱即用就提供共享日志；Paxos 提供单值共识，但实际中多数用 Paxos 的系统采用的是其扩展 Multi-Paxos，后者同样提供共享日志。

使用共享日志

共享日志非常适合用于数据库复制。若每条日志条目代表对数据库的一次写，每个副本以确定性逻辑按相同顺序处理同样的写，那么所有副本最终会处于一致状态。这一思想叫状态机复制 [82]，正是事件溯源的原理（见第 101 页"事件溯源与 CQRS"）。共享日志对流处理也很有用，详见第 12 章。

类似地，共享日志可用于实现可串行化事务。如第 309 页"实际串行执行"所述，若每条日志条目代表一个以存储过程形式执行的确定性事务，且各节点按相同顺序执行这些事务，事务即可达成可串行化 [83, 84]。

具有强一致性模型的分片数据库通常每个分片维护一份独立日志：这有利于可扩展性，但也限制了它跨分片所能提供的一致性保证（如一致快照、外键引用）。跨分片的可串行化事务并非不可能，但需要额外协调 [85]。

共享日志的强大之处还在于：它能轻松适配为其他形式的共识：

• 已经看到如何用它实现单值共识与 CAS：只需选定日志中最先出现的那个值。
• 若想要单值共识的多个实例——比如剧院里许多人各自抢订一个座位——把座位号写入日志条目，对每个座位号取首次出现的那条日志条目即可。
• 若想要原子 fetch-and-add，则把要加到计数器上的数写入日志条目，计数器当前值即所有已写入日志条目数值之和。基于日志条目的简单计数器还可用来生成屏障令牌（见第 374 页"隔离僵尸与延迟请求"）——例如 ZooKeeper 中这一序号叫 zxid [20]。

从单主复制到共识

前面已经看到：如果只有一个"独裁"节点做决定，单值共识就很容易；同样，如果只有一个主节点被允许追加日志条目，共享日志也很容易。问题在于：那个节点故障时如何容错？

传统上采用单主复制的数据库并不解决这一问题：它们把主节点故障转移交给管理员手动处理。可惜这意味着相当长的停机时间，毕竟人反应再快也有限，且不满足共识的终止性。在共识里，我们要求算法能自动选出新主。（并非所有共识算法都有主节点，但常用的几种都有 [86, 87]。）

这并不容易。前面讨论过脑裂问题，也已确立所有节点必须就"谁是主"达成一致——否则两个节点可能各自以为是主，做出不一致的决定。看起来我们需要共识来选主，又需要主来求解共识。这一死结如何打破？

事实上，共识算法并不要求任何时刻只能有一个主节点。它们给出的是更弱的保证：定义一个纪元号（Paxos 里叫 ballot number、Viewstamped Replication 里叫 view number、Raft 里叫 term number），并保证在每个纪元内主节点唯一。

当某节点因在一段超时内未收到当前主的消息而认为主已死时，它可以发起一次选举来选新主，并赋予该选举一个比此前所有纪元号都更大的新纪元号。如果两个不同纪元的两个主发生冲突（也许之前的主其实并未死去），则纪元号更高的主胜出。

主节点在追加共享日志的下一条目之前，必须先确认不存在纪元号更高的主可能追加不同的条目。这可以通过收集 quorum 个节点的投票来完成——通常（但并非总是）是多数节点 [88]：节点只有在不知道存在任何更高纪元的主时才会投赞成。

于是有两轮投票：一次选主，第二次对主提议要追加到日志的下一条目投票。这两次投票的 quorum 必须重叠：若某提议被通过，至少有一个为它投票的节点也必定参与了最近一次成功的选主 [88]。如果一个提议的投票通过且没有发现更高纪元号，则当前主可以断定尚未有更高纪元号的主被选出，于是可以安全地把该提议条目追加到日志 [28, 89]。

这两轮投票表面上像 2PC（见第 324 页"两阶段提交"），但是非常不同的协议。共识算法里任何节点都可以发起选举，且只需 quorum 个节点响应；而 2PC 中只有协调者能请求投票，且每个参与者都必须投赞成才能提交。

共识的微妙之处

这一基本结构对 Raft、Multi-Paxos、Viewstamped Replication 和 Zab 都是共通的：先一次 quorum 投票选主，然后主每要追加一条日志条目都再做一次 quorum 投票 [70, 71]。每条新日志条目都会同步复制到一组 quorum 节点上，再向请求方确认；这样即便当前主故障，该日志条目也不会丢失。

不过，魔鬼藏在细节里——这也是上述算法各显神通之处。例如旧主故障、新主被选出后，算法需要确保新主尊重旧主在故障前已追加的所有日志条目。Raft 只允许日志至少与多数从节点的日志一样新的节点成为新主 [71]；Paxos 则允许任何节点成为新主，但要求它在开始追加自己的新条目之前，先把日志补齐到与其他节点同等水平。

选主时的一致性 vs 可用性

如果你希望共识算法严格保证第 429 页"共享日志即共识"中所列性质，那么新主在处理任何写或线性一致读之前，必须先把所有已确认的日志条目同步到本地。否则一个数据陈旧的节点成为新主时，可能会在旧主已经写过的日志槽位上写入新值，违反共享日志的"只追加"性质。

在某些情况下，你也许会选择弱化共识性质以更快从主节点故障中恢复，或仅仅是为了能恢复。例如 Kafka 提供非干净选主（unclean leader election）选项，允许任何副本成为新主——哪怕它并非最新。在使用异步复制的数据库中，主故障时也无法保证任何从节点是最新的。

一旦放弃"新主必须最新"这一要求，性能与可用性也许有所改善，但你已踩上薄冰：共识理论不再适用。只要没有故障，一切看似正常运行；可第 9 章讨论过的种种问题随时可能造成数据丢失或损坏。

另一处微妙之处在于：算法如何处理旧主在故障前已经提议、但尚未完成投票的那些条目。这方面的细节讨论可在本章参考文献中找到 [25, 71, 89]。

对采用共识算法做复制的数据库而言，仅把写转为日志条目并复制到 quorum 还不够。要想保证线性一致读，读也得像写那样经过一次 quorum 投票，以确认那个自认是主的节点确实仍是最新的。etcd 的线性一致读就是这样实现的。

按其标准形式，多数共识算法假定节点集合是固定的——节点可以下线再上线，但参与投票的节点集合在集群创建时就已确定。实践中往往需要在系统配置中加入新节点或移除旧节点。为支持这一点，共识算法被扩展了重新配置（reconfiguration）能力。在向系统加入新区域、或从一处迁移到另一处（先加新节点、再移除旧节点）时，这一能力尤其有用。

共识的优缺点

共识算法虽然复杂而精微，却是分布式系统中的一项重大突破。共识本质上就是"做对了的单主复制"——主节点故障时自动进行故障转移，确保已提交的数据不丢失、不出脑裂，即便面对第 9 章中讨论的所有问题也是如此。

任何提供自动故障转移、却未基于经过验证的共识算法的系统，很可能并不安全 [90]。采用经过验证的共识算法并不能保证整个系统正确——别处仍可能潜伏 bug——但这是个不错的起点。

尽管如此，共识也并非随处可用，因为这些好处是有代价的。共识系统始终需要严格多数才能运行——三节点容忍一节点故障，五节点容忍两节点故障。每个操作都要与一个 quorum 通信，因此无法靠增加节点来提升吞吐（事实上节点越多，算法越慢）。一旦发生网络分区把若干节点与其余节点切断，只有多数那一侧还能进展，其他节点都会被阻塞。

共识系统通常依赖超时检测节点失败。在网络延迟高度可变的环境中——尤其是跨多个地理区域分布的系统——把这些超时调好并不容易。超时过大，故障恢复就慢；过小，又会触发大量不必要的选主，反倒拖垮性能，系统可能把时间都花在选主上而无暇干正事。

有时共识算法对网络问题尤其敏感。例如已有研究表明 Raft 在某些边角情形下表现欠佳 [91, 92]：若整个网络运转正常、只有某一条特定链路始终不可靠，Raft 可能陷入主节点在两节点间反复切换、或当前主不断被迫退位的状况，致使系统实际上无法进展。原始 Raft 算法后来通过引入预投票阶段来缓解这一点 [67]。Paxos 同样依赖主节点，可能产生类似的性能问题。Egalitarian Paxos（EPaxos）及其变种采用无主协议，对表现欠佳的节点或网络连接更为鲁棒 [86]。

协调服务

共识算法在任何想提供线性一致操作的分布式数据库中都用得上，许多现代分布式数据库就用它做复制。但有一类系统是共识尤其突出的使用者：协调服务——如 ZooKeeper、etcd 与 Consul。这些系统表面上看像普通的键值存储，但它们并不像多数数据库那样为高写吞吐或通用数据存储而设计。

相反，它们的目的是协调另一个分布式系统中的节点。例如 Kubernetes 依赖 etcd，Spark 与 Flink 在高可用模式下依赖后台运行的 ZooKeeper。协调服务被设计为持有可全部装入内存的少量数据（仍会写磁盘以保证持久化），通过容错共识算法在多节点间复制。

协调服务的设计灵感来自 Google 的 Chubby 锁服务 [19, 60]。它们在共识算法之外还结合了若干特性，使它们在构建分布式系统时特别有用：

锁与租约

我们已经看到共识系统如何实现一个原子且容错的 CAS 操作；协调服务正是依赖这种能力来实现锁与租约。多节点同时尝试获取同一租约时，只会有一个成功。

屏障支持

如第 373 页"分布式锁与租约"中所讨论的，资源被租约保护时，需要屏障（fencing）以防止客户端在进程暂停或大网络延迟下相互干扰。共识系统可以通过给每条日志条目分配单调递增的 ID 来生成屏障令牌（如 ZooKeeper 中的 zxid、cversion，etcd 中的 revision 号）。

故障检测

客户端与协调服务之间维持一条长效会话，周期性交换心跳来检查对方是否存活。即使连接临时中断或服务器故障，客户端持有的任何租约仍保持有效。但若超过租约超时仍无心跳，协调服务就判定客户端已死并释放租约（ZooKeeper 把这种节点称为临时节点）。

变更通知

客户端可以请求协调服务在某些键发生变化时通知自己。借此，一个客户端就能知道另一客户端何时加入了集群（根据它写入协调服务的值），或另一客户端何时发生了故障（其会话超时、临时节点消失）等。这些通知让客户端免于为获知变化而频繁轮询。

故障检测与变更通知本身并不需要共识，但与那些确实需要共识的原子操作及屏障支持配合起来，对分布式协调非常有用。

用协调服务管理配置

应用与基础设施常常具有配置参数，如超时、线程池大小等。协调服务有时被用来以键值对的形式存放这类配置数据：进程启动时加载最新设置，并订阅变更通知；配置变化时，进程可以立刻使用新设置，也可以自我重启来加载新值。

配置管理本身并不需要协调服务的共识能力，但既然你已经在跑这套服务，顺手用它并借助其通知机制是很方便的。或者进程也可以周期性地从文件或 URL 拉取配置更新，这样就不必专设协调服务。

把工作分配给节点

如果你有某进程或服务的多个实例，需要从中选出一个作主节点（leader 或 primary），那么协调服务就很有用。当主节点故障时，其余节点中应有一个接手。单主数据库需要这种机制，作业调度器及类似有状态系统也是如此。

另一种用例是：你有一个分片资源（数据库、消息流、文件存储、分布式 actor 系统等），需要决定哪个分片分给哪个节点。新节点加入集群时，得把一部分分片从既有节点迁到新节点以重新平衡负载；某节点被移除或故障时，其他节点也要接管它的工作。

这类任务都可以借助协调服务里的原子操作、临时节点和变更通知来巧妙完成。如果做得对，应用便能在故障发生时无须人工干预、自动恢复。这并不容易，但有 Apache Curator 这类库在 ZooKeeper 客户端 API 之上提供更高层工具——总比从零实现共识算法要强得多，后者极易出 bug。

专门的协调服务还有一个优势：它可以运行在固定数量节点上（通常 3 或 5），与依赖它进行协调的整个分布式系统的节点数无关。例如一个有数千个分片的存储系统，若在数千个节点上跑共识算法效率会极差；最好把共识"外包"给少数运行协调服务的节点。

协调服务管理的数据通常变化相当慢，例如"IP 10.1.1.23 上的节点是分片 7 的主节点"这类信息，分配往往以分钟或小时为单位变化。协调服务并非为每秒变化数千次的数据而设计——对这类用例最好用常规数据库，或者像 Apache BookKeeper [93, 94] 这样的工具可以用来复制服务那部分快变的内部状态。

服务发现

ZooKeeper、etcd 和 Consul 也常被用于服务发现——即查询联系某个服务所需的 IP 地址（见第 184 页"负载均衡器、服务发现与服务网格"）。在云环境中，虚拟机来去频繁，你往往事先并不知道服务的 IP 地址。相反，你可以让服务在启动时把自己的网络端点注册到一个服务注册表，其他服务由此找到它们。

把协调服务用作服务发现往往很方便：其故障检测与变更通知特性让客户端能轻松追踪服务实例的来去。若你已在使用协调服务做租约、加锁或选主，那么顺势用它做服务发现就很合理，毕竟它已经掌握哪个节点应当接收对你服务的请求。

然而把共识用于服务发现往往是过度。这一用例通常不要求线性一致性；更要紧的是服务发现要高可用且快速——少了它，一切都得停摆。因此通常更可取的做法是缓存服务发现信息：无法连接缓存的客户端可绕过缓存、用最新值重试，并在必要时更新缓存；缓存也可借助 TTL 周期性刷新。例如基于 DNS 的服务发现就靠多层缓存来兼顾性能与可用性。

为支持这一用例，ZooKeeper 提供了观察者（observers）。这些副本接收日志并维护 ZooKeeper 中数据的一份拷贝，但不参与共识算法的投票过程。从观察者读出的数据并非线性一致（可能过期），但即便网络中断它们仍可用，还能通过缓存提升系统所能支撑的读吞吐。

总结

本章我们考察了容错系统中的强一致性主题：它是什么、又如何实现。我们深入研究了线性一致性——一种流行的强一致性形式化，确保被复制的数据看起来好像只有一份、所有操作都对它原子地进行。当你需要某些数据在读取时是最新的，或需要解决某种竞态（比如多个节点并发做同一件事，如创建同名文件）时，线性一致性就很有用。

线性一致性因为容易理解而极具吸引力——它让数据库在并发下表现得像单线程程序里的一个变量。但它也有代价：慢，尤其是在网络延迟较大的环境中。许多复制算法表面上看似提供强一致性，其实并不保证线性一致性。

接着我们把线性一致性概念应用到 ID 生成器上。单节点自增计数器是线性一致的，却不容错。许多分布式 ID 生成方案不保证 ID 顺序与事件实际发生顺序一致；Lamport 时钟、混合逻辑时钟这类逻辑时钟提供与因果一致的排序，但仍不保证线性一致性。

这一切把我们引向了共识算法——它让我们能实现容错的、线性一致的复制。线性一致性意味着系统必须表现得像只有一份数据副本，所有操作都按一个良好定义的顺序、一次一个地作用其上。共识让一组节点就单一的操作序列达成一致，即便消息延迟、某些节点故障也是如此；这一序列使得分布式系统的行为看起来像只有一个节点在按序处理操作，尽管实际上是一群节点在协同工作。

经典的共识形式化涉及决定一个单一值，要求所有节点对决定的内容达成一致且不再改变。事实上一大类问题都可归约为共识，并彼此等价（只要有了其中一个问题的解，就能转化为其他所有问题的解）。这些等价问题包括：

线性一致 CAS 操作

寄存器需要根据其当前值是否等于操作所给的参数，原子地决定要不要设置其值。

锁与租约

多个客户端并发争抢锁或租约时，由锁决定谁成功获取。

唯一性约束

多个事务并发尝试创建带相同键的冲突记录时，约束必须决定允许哪一个、让哪一个失败并报约束违反。

共享日志

多个节点并发想往日志追加条目时，由日志决定追加顺序。共享日志通过全序广播协议实现。

原子事务提交

参与分布式事务的数据库节点必须就该事务是提交还是中止做出相同的决定。

线性一致的 fetch-and-add 操作

可用于实现 ID 生成器。多个节点可以并发调用该操作，由它决定对计数器加一的顺序。它其实只解决了两节点之间的共识，而上面其他几种都对任意数量节点成立。

如果你只有一个节点、或愿意把决策权交给一个节点，所有这些问题都很直截了当。单主数据库正是如此：所有决策权都集中在主节点，这也是这类数据库能提供线性一致操作、唯一性约束、复制日志等能力的原因。

然而一旦那个唯一的主节点故障、或网络中断使主节点不可达，这种系统就无法继续进展，直到有人手动做故障转移。Raft、Paxos 等被广泛采用的共识算法，本质上就是带内置自动选主与当前主故障转移功能的单主复制。

共识算法经过精心设计，确保故障转移过程中不丢失任何已提交写、系统不会进入多节点同时接受写的脑裂状态。这要求每次写、每次线性一致读都得到一个 quorum 节点（通常是多数）的确认。代价可能很高，跨地理区域时尤甚——但若想要共识所提供的强一致性与容错，就避不开。

ZooKeeper、etcd 等协调服务也建立在共识算法之上。它们提供锁、租约、故障检测和变更通知等特性，对管理分布式应用的状态非常有用。如果你发现自己想做的事可归约为共识，又希望它容错，建议使用协调服务。它不能保证你做对，但多半有帮助。

共识算法虽然复杂而精微，却由 1980 年代以来积累的丰厚理论支撑。正是这套理论让我们能构建出在容忍第 9 章中所讨论一切故障的同时仍能保证数据不被破坏的系统。这是一项了不起的成就，本章末的参考文献收录了这一工作中的部分代表性成果。

参考文献

[1] Maurice P. Herlihy and Jeannette M. Wing. "Linearizability: A Correctness Condition for Concurrent Objects." ACM Transactions on Programming Languages and Systems, volume 12, issue 3, pages 463–492, July 1990. doi:10.1145/78969.78972

[2] Leslie Lamport. "On interprocess communication." Distributed Computing, volume 1, issue 2, pages 77–101, June 1986. doi:10.1007/BF01786228

[3] David K. Gifford. "Information Storage in a Decentralized Computer System." Xerox Palo Alto Research Centers, CSL-81-8, March 1981. 归档于 perma.cc/K5ZP-2EJV

[4] Martin Kleppmann. "Please Stop Calling Databases CP or AP." martin.kleppmann.com, May 2015. 归档于 perma.cc/MJG7-79U6

[5] Hagit Attiya and Jennifer L. Welch. "Sequential Consistency Versus Linearizability." ACM Transactions on Computer Systems, volume 12, issue 2, pages 91–122, May 1994. doi:10.1145/176575.176576

[6] Mike Burrows. "The Chubby Lock Service for Loosely-Coupled Distributed Systems." 见 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.

[7] Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini. "Zab: High-Performance Broadcast for Primary-Backup Systems." 见 41st IEEE International Conference on Dependable Systems and Networks (DSN), June 2011. doi:10.1109/DSN.2011.5958223

[8] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming, 2nd edition. Springer, 2011. ISBN: 978-3-642-15259-7

[9] Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil. "A Critique of ANSI SQL Isolation Levels." 见 ACM International Conference on Management of Data (SIGMOD), May 1995. doi:10.1145/223784.223785

[10] Mike Burrows. "Re: [Cassandra] [DISCUSS] Improvements to LWT." Apache mailing list, May 2020.

[11] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects, 1987.

[12] Phillip B. Gibbons. "Strict serializability." Encyclopedia of Database Systems, 2009. doi:10.1007/978-0-387-39940-9_366

[13] CockroachDB. "What Is CockroachDB's Consistency Model?" cockroachlabs.com. 归档于 perma.cc/J3CR-4PXH

[14] Daniel Abadi. "Correctness Anomalies Under Serializable Isolation." dbmsmusings.blogspot.com, June 2019. 归档于 perma.cc/Q9NP-FH7V

[15] James C. Corbett 等. "Spanner: Google's Globally-Distributed Database." 见 10th USENIX Symposium on Operating System Design and Implementation (OSDI), October 2012.

[16] Apple, Inc. "FoundationDB Documentation." apple.github.io. 归档于 perma.cc/W7CK-VTMD

[17] Atul Adya. "Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions." Ph.D. thesis, MIT, March 1999.

[18] Peter Bailis. "Linearizability versus Serializability." bailis.org, September 2014. 归档于 perma.cc/UQ2A-GRDS

[19] Mike Burrows. "The Chubby Lock Service for Loosely-Coupled Distributed Systems." 见 OSDI 2006.

[20] Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. "ZooKeeper: Wait-Free Coordination for Internet-Scale Systems." 见 USENIX Annual Technical Conference (ATC), June 2010.

[21] Wei Hu 等. "Oracle Real Application Clusters." Oracle 白皮书, January 2025.

[22] Tushar Deepak Chandra, Robert Griesemer, and Joshua Redstone. "Paxos Made Live—An Engineering Perspective." 见 26th ACM Symposium on Principles of Distributed Computing (PODC), June 2007. doi:10.1145/1281100.1281103

[23] Martin Kleppmann. "How to Do Distributed Locking." martin.kleppmann.com, February 2016. 归档于 perma.cc/Y24W-YQ5L

[24] Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini. "Zab: High-Performance Broadcast for Primary-Backup Systems." 见 DSN 2011.

[25] Diego Ongaro and John Ousterhout. "In Search of an Understandable Consensus Algorithm (Extended Version)." 见 USENIX Annual Technical Conference (ATC), June 2014.

[26] Peter Bailis 等. "Quantifying Eventual Consistency with PBS." Communications of the ACM, volume 57, issue 8, pages 93–102, August 2014. doi:10.1145/2632792

[27] Salvatore Sanfilippo. "WAIT: synchronous replication for Redis." antirez.com, December 2013. 归档于 perma.cc/9EHK-WLP4

[28] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming, 2nd edition. Springer, 2011.

[29] Apache Cassandra. "Read Repair." cassandra.apache.org. 归档于 perma.cc/E55C-JNJU

[30] Maurice Herlihy. "Wait-Free Synchronization." ACM Transactions on Programming Languages and Systems, volume 13, issue 1, pages 124–149, January 1991. doi:10.1145/114005.102808

[31] Armando Fox and Eric A. Brewer. "Harvest, Yield, and Scalable Tolerant Systems." 见 7th Workshop on Hot Topics in Operating Systems (HotOS), March 1999. doi:10.1109/HOTOS.1999.798396

[32] Seth Gilbert and Nancy Lynch. "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services." ACM SIGACT News, volume 33, issue 2, pages 51–59, June 2002. doi:10.1145/564585.564601

[33] Seth Gilbert and Nancy Lynch. "Perspectives on the CAP Theorem." Computer, volume 45, issue 2, pages 30–36, February 2012. doi:10.1109/MC.2011.389

[34] Eric A. Brewer. "CAP Twelve Years Later: How the 'Rules' Have Changed." IEEE Computer, volume 45, issue 2, pages 23–29, February 2012. doi:10.1109/MC.2012.37

[35] Susan B. Davidson, Hector Garcia-Molina, and Dale Skeen. "Consistency in Partitioned Networks." ACM Computing Surveys, volume 17, issue 3, pages 341–370, September 1985. doi:10.1145/5505.5508

[36] Paul R. Johnson and Robert H. Thomas. "RFC 677: The Maintenance of Duplicate Databases." Network Working Group, January 1975.

[37] Bruce G. Lindsay 等. "Notes on Distributed Databases." IBM Research Report RJ2571(33471), July 1979.

[38] Eric A. Brewer. "NoSQL: Past, Present, Future." 见 QCon San Francisco, November 2012.

[39] Peter Bailis and Kyle Kingsbury. "The Network is Reliable." ACM Queue, volume 12, issue 7, July 2014. doi:10.1145/2639988.2639988

[40] Daniel J. Abadi. "Consistency Tradeoffs in Modern Distributed Database System Design." IEEE Computer, volume 45, issue 2, pages 37–42, February 2012. doi:10.1109/MC.2012.33

[41] Hagit Attiya, Faith Ellen, and Adam Morrison. "Limitations of Highly-Available Eventually-Consistent Data Stores." 见 ACM Symposium on Principles of Distributed Computing (PODC), July 2015. doi:10.1145/2767386.2767419

[42] Peter Sewell 等. "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors." Communications of the ACM, volume 53, issue 7, pages 89–97, July 2010. doi:10.1145/1785414.1785443

[43] Martin Kleppmann. "A Critique of the CAP Theorem." arXiv:1509.05393, September 2015.

[44] Henry Robinson. "CAP Confusion: Problems with 'Partition Tolerance'." blog.cloudera.com, April 2010. 归档于 perma.cc/2MFG-V9XL

[45] Adrian Cockcroft. "Errors in Database Paper Equating Multi-Region Consistency to Single-Region." adrianco.medium.com, July 2021. 归档于 perma.cc/X8L6-D9QT

[46] Daniel Abadi. "Problems with CAP, and Yahoo's little known NoSQL system." DBMS Musings, April 2010. 归档于 perma.cc/3LM8-LDCK

[47] Daniel J. Abadi. "PACELC: An Extension to CAP." DBMS Musings, October 2010.

[48] Hans-J. Boehm. "An Almost Non-Blocking Stack." 见 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), March 2004. doi:10.1145/1007912.1007923

[49] Paul E. McKenney. "Memory Barriers: a Hardware View for Software Hackers." June 2010. 归档于 perma.cc/DR3D-4DWG

[50] Ulrich Drepper. "What Every Programmer Should Know About Memory." people.redhat.com, November 2007. 归档于 perma.cc/CSY7-ESSG

[51] Hagit Attiya and Jennifer L. Welch. "Sequential Consistency Versus Linearizability." ACM Transactions on Computer Systems, volume 12, issue 2, pages 91–122, May 1994. doi:10.1145/176575.176576

[52] IETF. "RFC 9562: Universally Unique IDentifiers (UUIDs)." May 2024.

[53] Twitter Engineering. "Announcing Snowflake." blog.twitter.com, June 2010. 归档于 perma.cc/8XGD-FYK3

[54] Alizain Feerasta. "ULID: Universally Unique Lexicographically Sortable Identifier." github.com. 归档于 perma.cc/H38J-K3MK

[55] Brandur Leach. "Identity in PostgreSQL with UUIDs." brandur.org, October 2022. 归档于 perma.cc/L7EF-A2DT

[56] Leslie Lamport. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM, volume 21, issue 7, pages 558–565, July 1978. doi:10.1145/359545.359563

[57] Sandeep S. Kulkarni 等. "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases." 见 International Conference on Principles of Distributed Systems (OPODIS), December 2014.

[58] Murat Demirbas. "Hybrid Logical Clocks." muratbuffalo.blogspot.com, July 2014. 归档于 perma.cc/2ZUJ-9P6C

[59] Daniel Peng and Frank Dabek. "Large-scale Incremental Processing Using Distributed Transactions and Notifications." 见 9th USENIX Symposium on Operating System Design and Implementation (OSDI), October 2010.

[60] Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. "Paxos Made Live—An Engineering Perspective." 见 PODC 2007.

[61] Henry Robinson. "Consensus Protocols: Two-Phase Commit." the-paper-trail.org, November 2008. 归档于 perma.cc/3DPB-FU8R

[62] Brian M. Oki and Barbara H. Liskov. "Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems." 见 7th ACM Symposium on Principles of Distributed Computing (PODC), August 1988. doi:10.1145/62546.62549

[63] Barbara H. Liskov and James Cowling. "Viewstamped Replication Revisited." MIT-CSAIL-TR-2012-021, July 2012.

[64] Leslie Lamport. "The Part-Time Parliament." ACM Transactions on Computer Systems, volume 16, issue 2, pages 133–169, May 1998. doi:10.1145/279227.279229

[65] Leslie Lamport. "Paxos Made Simple." ACM SIGACT News, volume 32, issue 4, pages 51–58, December 2001.

[66] Robbert van Renesse and Deniz Altinbuken. "Paxos Made Moderately Complex." ACM Computing Surveys, volume 47, issue 3, article 42, February 2015. doi:10.1145/2673577

[67] Heidi Howard 等. "Raft does not Guarantee Liveness in the face of Network Faults." decentralizedthoughts.github.io, March 2020.

[68] Diego Ongaro. "Consensus: Bridging Theory and Practice." Ph.D. thesis, Stanford University, August 2014.

[69] Apache ZooKeeper. "ZooKeeper Internals." zookeeper.apache.org. 归档于 perma.cc/Y6KE-4PJG

[70] Heidi Howard. "Distributed Consensus Revised." Ph.D. thesis, University of Cambridge, April 2019.

[71] Robbert van Renesse, Nicolas Schiper, and Fred B. Schneider. "Vive La Différence: Paxos vs. Viewstamped Replication vs. Zab." IEEE Transactions on Dependable and Secure Computing, volume 12, issue 4, pages 472–484, July 2015. doi:10.1109/TDSC.2014.2355848

[72] Miguel Castro and Barbara H. Liskov. "Practical Byzantine Fault Tolerance and Proactive Recovery." ACM Transactions on Computer Systems, volume 20, issue 4, pages 398–461, November 2002. doi:10.1145/571637.571640

[73] Yonatan Sompolinsky and Aviv Zohar. "Secure High-Rate Transaction Processing in Bitcoin." 见 Financial Cryptography and Data Security, January 2015. doi:10.1007/978-3-662-47854-7_32

[74] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. "Impossibility of Distributed Consensus with One Faulty Process." Journal of the ACM, volume 32, issue 2, pages 374–382, April 1985. doi:10.1145/3149.214121

[75] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. "Consensus in the Presence of Partial Synchrony." Journal of the ACM, volume 35, issue 2, pages 288–323, April 1988. doi:10.1145/42282.42283

[76] Michael Ben-Or. "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols." 见 2nd ACM Symposium on Principles of Distributed Computing (PODC), August 1983. doi:10.1145/800221.806707

[77] Kyle Kingsbury. "Call Me Maybe: Elasticsearch 1.5.0." aphyr.com, April 2015. 归档于 perma.cc/YD9G-58A2

[78] Xavier Défago, André Schiper, and Péter Urbán. "Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey." ACM Computing Surveys, volume 36, issue 4, pages 372–421, December 2004. doi:10.1145/1041680.1041682

[79] Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edition. John Wiley & Sons, 2004. ISBN: 978-0-471-45324-6

[80] Christian Cachin 等. Introduction to Reliable and Secure Distributed Programming, 2nd edition.

[81] Rachid Guerraoui. "Revisiting the Relationship Between Non-Blocking Atomic Commitment and Consensus." 见 9th International Workshop on Distributed Algorithms (WDAG), September 1995. doi:10.1007/BFb0022140

[82] Fred B. Schneider. "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial." ACM Computing Surveys, volume 22, issue 4, pages 299–319, December 1990. doi:10.1145/98163.98167

[83] Mark Slee, Aditya Agarwal, and Marc Kwiatkowski. "Thrift: Scalable Cross-Language Services Implementation." Facebook, April 2007.

[84] Mahesh Balakrishnan 等. "CORFU: A Shared Log Design for Flash Clusters." 见 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI), April 2012.

[85] Daniel Peng and Frank Dabek. "Large-scale Incremental Processing Using Distributed Transactions and Notifications." 见 OSDI 2010.

[86] Iulian Moraru, David G. Andersen, and Michael Kaminsky. "There Is More Consensus in Egalitarian Parliaments." 见 24th ACM Symposium on Operating Systems Principles (SOSP), November 2013. doi:10.1145/2517349.2517350

[87] Fred B. Schneider. "Replication Management Using the State-Machine Approach." Distributed Systems, 2nd edition, ACM Press, 1993. doi:10.1145/302430.302438

[88] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. "Flexible Paxos: Quorum Intersection Revisited." 见 20th International Conference on Principles of Distributed Systems (OPODIS), December 2016. doi:10.4230/LIPIcs.OPODIS.2016.25

[89] Diego Ongaro and John Ousterhout. "In Search of an Understandable Consensus Algorithm (Extended Version)." May 2014.

[90] Kyle Kingsbury. "Call Me Maybe: RabbitMQ." aphyr.com, June 2014. 归档于 perma.cc/YV5L-2VWB

[91] Heidi Howard and Richard Mortier. "Paxos vs Raft: Have we reached consensus on distributed consensus?" 见 7th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC), April 2020. doi:10.1145/3380787.3393681

[92] Jay Kreps. "Why local state is a fundamental primitive in stream processing." oreilly.com, July 2014.

[93] Apache BookKeeper. bookkeeper.apache.org.

[94] Flavio Junqueira, Ivan Kelly, and Benjamin Reed. "Durability with BookKeeper." ACM SIGOPS Operating Systems Review, volume 47, issue 1, pages 9–15, January 2013. doi:10.1145/2433140.2433144