一致性和共识
本章的线性一致性是在铺垫了多副本、网络问题、时钟问题后的一个综合探讨。首先探讨了线性一致的内涵：让系统表现得好像只有一个数据副本。然后讨论如何实现线性一致性，以及背后所做出的的取舍考量。其间花了一些笔墨探讨 CAP，可以看出作者很不喜欢 CAP 的模糊性。
由于分布式系统可能存在各种问题，本章我们将会讨论一些用于构建具有容错性分布式系统的算法和协议。
构建一个容错系统最好的方法是：找到一些基本抽象，可以对上提供某些承诺，应用层可以依赖这些承诺来构建系统，而不必关心底层细节。之前介绍的事务就是一种抽象机制并对外提供一些承诺，从而简化应用层。
本章将继续讨论一些可以减轻应用层负担的分布式系统中的基本抽象。例如，分布式系统最重要的抽象之一就是共识：让所有的节点在某件事情上达成一致。
为什么共识协议如此重要呢？他和真实系统的连接点在于哪里？答曰，操作日志。而大部分数据系统都可以抽象为一系列数据操作的依次施加，即状态机模型。而共识协议可以让多机对某个确定的操作序列达成共识，进而对系统的任意状态达成共识。
在讨论共识之前，我们需要探索下分布式系统中我们可以提供的保证和抽象有哪些，并了解系统能力的边界，即哪些可行，哪些不可行。
分布式系统领域针对这些主题的研究已经持续了数十载，因此积累了很多材料，但我们只能进行简要介绍其皮毛。由于篇幅所限，我们不会详细探究其严谨的模型描述和详细证明，相反，我们只会给一些其背后的直觉（informal intuitions）。如果你感兴趣，章节末尾的参考文献应该可以提供一些足够深入的细节。
# 1. 一致性保证
在“数据复制”一章中，我们知道了，在相同时刻，由于时间差的问题，多副本之间可能存在不一致性。无论我们使用什么数据副本模型（单主、多主和无主），这种数据的不一致性都有可能会发生。大部分多副本数据库会提供最终一致性的保证，即所有的副本最终会收敛到相同的值。但最终一致性是一个很弱的保证，对应用开发者很不友好。因为它表现出和单线程程序中的变量不一样的行为：赋值之后仍可能读到旧值。
在使用只提供弱保证的数据库时，我们需要时刻记得其限制，而不能偶尔自己增加额外假设，否则，会产生非常致命且难以察觉的 BUG。
本章将探究更强的一致性模型，更强的保证可以让上层应用的逻辑更简单，但也会牺牲性能或可用性。因此需要我们去进行取舍。
本章涉及到很多主题，乍看起来很宽泛，但其内里是互相勾连的：
- 首先，我们从常用的最强的一致性模型：线性一致性（linearizability）开始，探究其优缺点。
- 接着，我们会考察分布式系统中时间的顺序问题，尤其是关于因果关系（causality）和全序问题（total ordering）。
- 最后，在第三部分，我们会探索如何原子性的提交一个分布式事务，最终导出共识问题的解决方法。
# 2. 线性一致性
线性一致性（linearizability）的基本思想：让一个数据系统看起来好像只有一个数据副本，且所有的操作都是原子的。这样就可以表现出只让时间线推进，而不让时间线倒流。有了这个保证，应用程序就不需要关系系统内部的多个副本了。换句话说，线性一致性是一种数据新鲜度的保证。
线性一致性还有很多其他称谓：原子一致性（atomic consistency）、强一致性（strong consistency）、即时一致性（immediate consistency），或者外部一致性（external consistency）。
# 2.1 非线性一致性的例子
我们看一个非线性一致性系统的例子：
上图显示了一个非线性一致性的体育网站。Alice 和 Bob 在一间屋子里，分别通过手机来查看 2014 年国际足联世界杯的总决赛的结果。在最终比分出来后，Alice 刷新了网页，并且看到了发布的赢家信息，并且将该结果告诉了 Bob。Bob 有点难以置信，重新刷了一下网页，但是他的请求被打到了一个滞后的数据库副本上，该副本显示比赛仍在进行。
如果 Alice 和 Bob 同时（也就是并发）刷新网页，可能还不会对出现不同结果有太多惊讶，毕竟他们也不知道谁的查询请求先到（因为并发）。但，上述例子中，Bob 是在 Alice 告知他结果后刷新的网页，因此他才会期待至少能看到和 Alice 一样新的结果。该例子中 Bob 的请求返回了一个过期的结果，这便是违反了线性一致性。
# 2.2 如何让系统满足线性一致性？
线性一致性背后的思想很简单：让系统表现得好像只有一个数据副本。为了理解这个概念，先看更多的例子。
下图显示了三个客户端并发访问提供线性一致性的数据库的同一个键。在分布式系统论文中，x 被称为“寄存器”（register）。在实践中，x 可以是一个键值存储中的键值对、关系型数据中的一行或者文档数据中的一个文档。
上图只显示了客户端角度数据读写视图：
- Client C 有一个 write 操作，与 write 前后没有交集的 read 返回的结果是确定的
- 当 read 与 write 存在交集时，读取的结果就是不确定的
由于当 read 与 write 存在交集时，查询结果可能在新值与旧值之间来回跳变，这不符合线性一致性的要求，因此需要增加约束：一旦某个读操作返回了新值，之后的所有的读操作都必须返回新值：
- 如上图，Client A 的第二次 read 返回新值 1 后，Client B 的第二次 read 也必须返回新值 1。
在多副本数据库中，如果要解决线性一致性，就要满足一旦某个客户端读取到新值，则其之后的读请求一定能读到该新值，而不是还可能看到旧值。这很难，由于上一章讲的时钟问题，我们甚至很难对多个客户端定义“先后”。此外，这种线性一致性的特性类似于薛定谔的猫，本来可能有多个状态，但一旦有个一个客户端进行了一次观察，就迅速的坍缩到了一个状态，其他后来者，也只能看到这一个状态。从另外一个角度理解，是读取请求塑造（seal）了并发请求的多状态边界。
我们将这个时序图提炼一下，将所有请求生效时间都压缩到一个点，一次请求的操作在这个时间点才执行并瞬间完成：
cas(x, v-old, v-new) ⇒ r表示一个 CAS 请求，只有当寄存器 x 的值为 v-old 时，才会被更新为 v-new。r 是返回值，指示是否更新成功。
如果将所有生效时间点连成一条线，线性一致性要求所有操作标记组成序列是永远向前的，即满足数据新鲜度要求：一旦我们写入或者读取到某值，所有稍后的读请求都能看到该值，直到有人再次将其改写。
这就是线性一致性背后的一些直觉。
除此之外，上面这个图有几个有意思的点：
- Client B 的最后一次 read 读到了旧值，因此不满足线性一致性
- 这个模型对事务隔离性没做任何要求，因为按照快照隔离的要求，若 client C 的前两次 read 是一个事务的话，那应该读取到同样的结果，也就是可重复读。
线性一致性 vs 可串行化
线性一致性和可串行化容易发生混淆。
- 线性一致性：这个概念时由于多副本而引出的，是读写寄存器（单个对象）的最新值保证；
- 可串行化：这个概念是由于一个事务有多个操作并可以假设像独占系统一样来引出的，它是事务的一个隔离属性，其中每个事务也往往涉及到读写多个对象。
需要注意的是，在可串行化中，如果某种串行顺序和实际执行顺序不一致也没事，只要是串行执行就行。举个例子，如果 A、B、C 三个事务并发执行，真实顺序是 A、B、C，但如果对应用层表现为 CAB 的执行顺序（可能由于多机时间戳不同步），也可以叫可串行化，但 CAB 的执行顺序在某个对象上可能不满足线性一致性。
一个数据库可以同时提供可串行化和线性一致性保证，我们称之为严格可串行化（strict serializability）或者单副本可串行化（strong one-copy serializability）。使用两阶段锁或者真正串行化执行实现的可串行化，通常都是线性一致的。但实际上这个级别的数据库通常性能会不太好，所以实际上我们还是选择放松要求。
然而，基于快照隔离的串行化通常不是线性一致的。为了避免读写互相阻塞，所有的读取都会基于某个一致性的快照，则该快照之后的写入不会反映到读请求上，因此，快照读不满足线性一致性。
# 2.3 依赖线性一致性的例子
下面讲了一些需要线性一致性的例子。
# 2.3.1 加锁和主节点选举
主从复制的额系统需要确保只有一个主节点，否则就会脑裂。选举主节点的常见方法是使用锁：每个节点在启动时都试图去获取锁，最终只有一个节点会成功并且变为主节点。
不论使用什么方式实现锁，都必须满足线性一致性：所有节点必须就某节点拥有锁达成一致，否则这样的锁服务是不能用的。
提供协调者服务的系统，如 Apache Zookeeper 和 ectd 等通常用来实现分布式锁和主节点选取，他们通常使用共识算法来实现线性一致性操作，并且能够进行容错。
# 2.3.2 约束和唯一性保证
唯一性约束在数据库中很常见：
- userId 要求具有唯一性
- 文件的绝对路径要求在一个文件系统中具有唯一性
如果你想要在数据写入时维持这些约束，你需要线性一致性。
这个情形和锁的语义非常类似：当一个用户注册时，可以认为他获得了一个和所注册的用户名关联的“锁”。这个操作很像原子的 CAS（compare-and-set）：如果该用户名没有被使用，就将其分配给该用户。
类似的约束还有：
- 保证银行账户余额不出现负值
- 航班座位不能超卖
这些约束都要求所有节点在单个最新值（账户余额、股票水位、座位预定）上达成一致。
当然，在真实场景下，有时这些约束课可以被适当放宽（比如，如果机票座位被超订了，可以将其中一个用户移到其他航班，并给与适当补偿）。在这种情况下，可能不需要严格的线性一致性。
# 2.3.3 多渠道的时序依赖
在图 9-1 中我们可以注意到一个细节：如果 Alice 没有说出决赛结果，Bob 就不会知道他看到的是过时的结果。如果 Bob 没有从 Alice 那里事先知道结果，他可能就会过几秒再刷新一次页面，最终会看到最终分数。也就是说，因为存在一个额外的通信渠道，导致我们注意到了系统不满足线性一致性。
这说明，一个 Web client 如果观测到系统不满足线性一致性，通常就是有多个通信渠道来获取信息。如果没有线性一致性的保证，那么多个通信渠道的信息就会发生不一致。如果你可以控制所有的通信渠道，就可以使用类似“读你所写”的技术来解决这种竞态条件。
一个示例
比如下面这个例子：我们有一个可以让用户上传照片的网站，有个后台进程会将照片进行压缩以支持快速加载，架构图如下：
图片调整服务（image resizer）需要显式的指定任务，任务指令是通过消息队列由 web 服务器发给图片调整服务。但由于消息队列是针对短小消息（1kb 以下）而设计的，而图片通常有数 M，因此不能直接将图片发送到消息队列。而是，首先将图片写入文件存储服务（File Storage Service），然后将包含该文件路径的调整请求发送到消息队列中。
如果文件存储服务是线性一致的，则这个系统能正常运作。但如果他不是，则可能会存在竞态条件：消息队列可能会比文件存储服务内部多副本同步要快。在这种情况下，当图片调整服务去文件存储服务中捞照片时，就会发现一个旧照片、或者照片不存在。如果调整服务看到的是旧照片，却以为是新的，然后把它调整了并且存回了存储服务，就会出现永久的不一致。
出现这种情况是因为在 web 服务器和图片调整服务中间存在两条不同的通信渠道（communication channels）：存储系统和消息队列。如果没有线性一致性提供的新鲜度保证，两条通信渠道就有可能发生竞态条件（race condition）。
# 2.4 实现了线性一致的系统
我们已经看了一些依赖线性一致性的例子，接下来让我们思考下如何实现一个提供线性一致语义的系统。
线性一致性的本质是在说：系统表现得像只有一个数据副本，且所有施加于其上的操作都会原子性（瞬间）的完成。那么，我们最简单的实现方式就是真的只用一个数据副本。但其问题在于，不能容错：一旦该副本挂了，轻则长时间（重启之前）不可用、重则数据丢失。
最常用的让系统进行容错的方式就是多副本。让我们回顾下几种多副本模型，然后逐一考察下其是否能够做成可线性化的：
- 单主模型（主从复制模型）：部分支持线性一致。当数据读取是从主节点或者同步更新的从节点上读取时，就可以满足线性一致性。
- 共识算法：线性一致。有一些共识算法，看起来与单主模型类似。但这些共识协议有一些阻止脑裂和过期副本的手段。由于这些额外细节，共识算法可以实现安全的线性一致性存储。Zookeeper 和 etcd 就是用的这种手段。
- 多主模型：不可线性一致。因为它可以同时在多个节点上处理写入，并且异步同步写入数据。
- 无主模型：可能不能线性一致。这完全取决于 quorum 的配置，以及如何定义强一致性，它可能并不保证线性一致。即使对于严格的法定策略，非线性一致的现象也可能出现。
# 2.4.1 线性一致和 quorum
从直觉出发，在 Dynamo 风格的系统重使用严格的 Quorum 读写应该会满足线性一致性。但在具有不确定延迟的网络中，仍然可能会出现竞态条件。如下图所示：
在图 9-6 中，x 的初始值是 0。然后一个客户端想将 x 更新为 1，然后将该写请求发送到所有三个副本（n=3, w=3）。与此同时，客户端 A 使用 r = 2 的配置进行 Quorum 读，并且看到了新值 1。稍后，客户端 B 也是用 r = 2 的配置在另外两个节点进行 Quorum 读，但却读到了旧值 0。
Quorum 的配置是严格满足 w+r>n 的，然而这个读写序列却不是线性一致的：B 的读取请求开始于 A 的读请求结束之后，却读到了比 A 旧的值。
当然，有趣的是，我们可以通过牺牲部分性能来让 Dynamo 风格的 Quorum 读写变成线性一致的：
- 每个读请求必须进行同步的读取修复。
- 发送任意写请求之前要先读取最新值。
但由于性能原因 Riak 并没有采用同步的读取修复；Cassandra 倒是会同步读取修复，但在多个请求并发写入同一个 key 时，由于采用了后者胜的策略（考虑时钟，会导致接受顺序不是真正事件发生顺序），仍然不能保持线性一致性。此外，这种方式只能实现线性一致的读写操作，而不能实现线性一致的 CAS 操作。只有共识协议才能实现线性一致的 CAS。
总结来说，最好认为基于无主模型的 Dynamo 风格的系统不提供线性一致性保证。
# 2.5 线性一致性的代价
线性一致性的代价，如下图：
对于上图的系统，当两个数据中心之间发生网络中断时，
- 如果要提供线性一致性，则两个数据中心都不可用；
- 如果不提供线性一致性，那两个数据中心都是可用的，
因此，网络中断迫使在可线性化和可用性之间做出选择。
# 2.5.1 CAP 理论
上面的问题不只是在主从复制和多主复制上才有的问题，无论如何实现，任何想要提供线性一致性的系统都会面临上述取舍问题。该问题也不止局限于跨数据中心部署，即使是在一个数据中心之内，任何通过不可靠网络连接的系统都会有该问题。其背后的取舍考量如下：
- 如果应用层要求系统提供线性一致性，此时如果某些数据副本由于网络问题和系统其他部分断开了连接，则这些数据副本就不再能够正常地处理请求：要么等待网络恢复、要么进行报错。但这都意味着系统不可用。
- 如果应用不要求系统的线性一致，则即使多副本间遇到连接问题，每个副本可以独立的进行写入。从而，即使出现了网络故障，系统仍然能够保持可用，但其行为不是线性一致的。
总而言之，如果系统不提供线性一致性，就可以对网络故障更加鲁棒。这种思路通常被称为 CAP 定理。
CAP 最初被提出只是一个为了激发数据库取舍讨论的模糊的取舍参考，而非被精确定义的定理，Martin 还专门写过一篇文章 (opens new window)来探讨这件事。在当时，很多分布式数据库还在着眼于基于共享存储的一组机器上提供线性一致性语义。CAP 的提出，鼓励工程师们在 share-nothing 等更广阔的设计领域进行架构探索，以找出更加适合大规模可扩展 web 服务架构。 在新世纪的最初十年里，CAP 的提出见证并推动了当时数据库设计思潮从强一致系统转向弱一致系统（也被称为 NoSQL 架构）。
CAP 定理的形式化定义适用范围很窄：仅包含一种一致性模型（即线性一致性）和一种故障类型（网络分区，或者说节点存活，但互不连通）。它没有进一步说明任何关于网络延迟、宕机节点、以及其他的一些取舍考量。因此，尽管 CAP 在历史上很有影响力，但他在设计系统时缺乏实际有效指导力，所以它现在更多是代表历史上曾经的一个关注热点而已。
CAP 理论
CAP 有时候被表述为，在做系统设计时，一致性（consistency）、可用性（Availability）、分区容错性（Partition tolerance），只能三选二。然而，这种说法极具误导性，因为网络分区是一种故障类型，而不是一种可以取舍的选项：不管你喜欢还是不喜欢，只要是分布式系统，它都在那。
在网络正常连通时，系统可以同时提供一致性（线性一致性）和完全的可用性。当网络故障发生时，你必须在线性一致性和完全可用性之间二选一。因此，对于 CAP 更好的一个表述可能是：当网络出现分区时，一致性和可用性只能二选其一。一个可靠的网络，可以减少其上的系统该选择的次数，但无论如何，分布式系统中，该选择是无法避免的。
在有关 CAP 的讨论，有几种关于可用性的大相径庭的定义，且将 CAP 升格为定理并给出证明中的提到的形式化的可用性并非通常意义中所说的可用性。很多所谓“高可用”的系统通常并不符合 CAP 定理中关于可用性的独特（idiosyncratic）定义。总而言之，CAP 有很多容易误解和模糊不清的概念，并不能帮助我们更好的理解系统，因此最好不用 CAP 来描述一个系统。
# 2.5.2 线性一致性和网络延迟
尽管线性一致性是一个非常有用的保证，但令人惊讶的是在工程实践中，很少有系统支持真正的线性一致。
甚而，即使在现代多核 CPU 体系下的 RAM 也不是线性一致的：如果一个核上的某个线程往某个内存地址中写了一个值，稍后另外核的一个线程读取该地址，并不一定能读到刚才的值。这是因为每个 CPU 都有自己的缓存（memory cache）和缓冲区（store buffer）。一般缓存通常说的是读取，而缓冲区通常针对写入。线程的内存访问会首先落到缓存里，所有对于缓存的更新会异步同步到主存中。缓存访问的速度要（ns 级别）比内存访问（百ns 级别）快几个数量级，由于可以用来弥合寄存器和主存的访问鸿沟，因此是现代 CPU 架构高性能的基石。但一份数据存了多个副本（比如主存中一个，一些 CPU 缓存中各有一个），且是异步更新的，导致线性一致性被破坏。
为什么会做此取舍？此处牺牲线性一致性的真正原因在于——性能，而不是容错。当然，在单机多线程编程中，可以使用一些手段（比如锁）来强制同步相应变量到主存，从而允许用户在关心一致性超过性能的地方，自行进行取舍。
很多分布式系统选择不提供线性一致性的原因也在于此：是为了提升系统性能而非进行容错。在任何时候，提供线性一致性都会严重拖慢系统。而非在网络故障发生时，才需要对线性一致性进行牺牲。
也就说，尽管 CAP 说了一致性和可用性只能二选一，但我们选择放松一致性的真正原因确实性能而非可用性。
我们能找到一种更高效的实现来让存储服务提供线性一致吗？遗憾的是，暂时没有。Attiya 和 Welch 证明了，如果你想要保证线性一致，读写请求的响应时间是正比于网络延迟的。提供线性一致性保证可能没有更快的算法，但是我们稍微放松一致性，就可以设计出一个更快的系统。这种取舍在对延迟敏感的系统非常重要。
# 3. 顺序保证
线性一致性的定义暗含着：所有的操作会形成一个确定的执行顺序。顺序是本书不断强调的一个主题，它是一个很重要的基础概念。先回忆一下本书提到的有关顺序的上下文：
- 数据复制 一章中，提到主从复制中就需要由主副本来确定复制日志的写入顺序，然后所有从副本都要遵从这个顺序。
- 事务 一章中，“可串行化”就是保证所有并发的事务像以某种顺序一样串行执行。
- 分布式系统的挑战 中的时钟也是试图对无序的真实世界引入某种顺序，以解决诸如哪个写入更靠后之类的问题。
顺序性（ordering）、线性一致性（linearizability）和共识协议（consensus）三个概念间有很深的联系，尽管这几个概念比较偏理论和抽象，但理解他们有助于来厘清系统的功能边界——哪些可以做，哪些做不了。
# 3.1 顺序和因果（Ordering and Causality）
# 3.1.1 什么是因果一致性？
顺序可以维持因果性。下面给出了一些体现“因果关系”重要性的例子：
- 在一致性前缀读中，我们提到：问题和答案之间存在因果依赖（casual dependency）。我们应该先看到问题，才能看到答案。
- 在数据复制的多主模型中，由于网络延迟可能出现对一个对象的写入操作居于更新操作后面的问题。这里因果意味着一个对象必须先被创建，然后才能去更新。
- 在检测并发写时，判断”A发生在B之前“就是一种因果关系，这说明 B 依赖于 A
- 事务从一致性快照中读取，这里的“一致性”就意味着因果关系一直，它对此后发生的事件不可见
- 事务之间写倾斜的例子，图7-8中，Alice 申请调班成功是因为事务以为 Bob 仍在值班。
- 违反线性一致性，导致 A 看到新值而后 B 看到旧值也是违背了因果关系。
因果将顺序施加于事件，也就是谁应该先发生，谁应该后发生：
- 先有因，后有果
- 先有消息发送，然后该消息被收到
- 先有问题，后有答案
如果一个系统遵循因果约束，则我们称其为因果一致的（causally consistent）。比如，快照隔离就可以提供因果一致性：当从数据库读取数据的时候，如果你能读到某个时间点的数据，就一定能读到其之前的数据（当然，要在该数据还没有被删除的情况下）。
# 3.1.2 因果序非全序
- 全序（total order）意味着任意两个元素之间都可以进行比较大小。比如整数的比大小。
- 偏序（partially order）意味着一个元素可以和一部分元素进行比较大小，但和另一部分是不可比的。比如数学集合的包含关系。
全序和偏序的差异也体现在数据库的一致性模型中：
- 线性一致性：由于它对外表现像所有操作都发生于单副本上，并且会原子性的完成。这意味着，任意两个操作，总是可以确定他们发生的先后关系。所有操作是全序的。
- 因果一致性：如果我们无从判定两个操作的先后关系，则称之为并发的。如果两个事件因果相关，则其一定有序。因此，因果性定义了一种偏序关系，而非全序的。
根据上述解释，在线性一致性的数据存储服务中，是不存在并发操作的：因为必然存在一个时间线能将所有操作进行排序。
理解全序和偏序、线性一致性和因果一致性的一个关键模型是有向图。在该图中，点代表事件，有向边代表因果关系，并且从因事件指向果事件，很自然的，因果性满足传递性。如果该图中有一条单一的路径能串起所有点，且不存在环，则该系统是线性一致的。可以看出，因果关系是一种局部特性（也即偏序关系），定义在两个点之间（如果两个点之间存在着一条单向途径，则这两点有因果关系）；而线性关系是一种全局特性（也即全序关系），定义在整个图上。
# 3.1.3 线性一致性强于因果一致性
任何线性一致性的系统都将正确地保证因果一致性。
线性一致性能够保证因果一致性，这一结论使得线性化系统更加简单易懂且富有吸引力，但这会显著降低性能和可用性，尤其是网络延迟严重的情况下。
好消息是存在折中路线。一个系统可以不必承担线性一致性所带来的性能损耗，而仍然是因果一致的。这种情况下，CAP 理论是不适用的。事实上，因果一致性是系统在保证有网络延迟而不降低性能、在有网络故障而仍然可用的情况下，能够提供的最强一致性模型。
在大多数情况下，我们以为我们需要线性一致模型，其实我们真实需要因果一致模型，而后者允许我们实现性能更好的系统。基于这个观察，研究人员在探寻新型数据库的设计，让系统既可以提供因果关系保证，也可以提供（堪比最终一致性系统的）高性能和高可用性。这些研究都比较新，还存在很多挑战，也没有进行落地。但无疑，是分布式系统在将来一个很有前景发展方向。
实践
真实系统中，在所有的事件集中，只有部分事件是有因果依赖的，这些事件需要在执行时保证因果顺序执行；而其他的大部分事件是没有因果依赖的，因此可以乱序、按需执行以保证性能。但这件事情的难点在于，因果关系是应用层定义的。而我们在系统层，就很难识别。可能需要提供某种接口，可以让应用层显示指定因果，但一来不确定这种接口是否能做的足够宽泛；二来，这种因果追踪的额外代价是非常大的。
# 3.1.4 捕获因果依赖
我们不会事无巨细的去探究非线性化系统如何保持因果关系的每个细节，仅就其中的一些关键点进行探讨。
为了保证因果一致性，我们需要知道哪些操作存在着因果关系。为了确定因果依赖，我们需要某种手段来描述系统中节点的“知识”（knowledge）。如果某个节点在收到 Y 的写入请求时已经看到了值 X，则 X 和 Y 间可能会存在着因果关系。就如在调查公司的欺诈案时，CEO 常被问到，“你在做出 Y 决定时知道 X 吗”？
确定哪些操作先于哪些些操作发生的方法类似于我们在“并发写入检测”一节讨论的技术。那一节针对无主模型讨论了如何检测针对单个 Key 的并发写入，以防止更新丢失问题。因果一致性所需更多：需要在整个数据库范围内追踪所有 Key 间操作的因果依赖，而非仅仅单个 Key 上。版本向量（version vectors）常用于此道。
为了解决确定因果顺序，数据库需要知道应用读取数据的版本信息。为此，数据库需要跟踪一个事务读取了哪些数据的哪些版本。
# 3.2 序列号定序
虽然因果关系很重要，但在实践中，追踪所有的因果依赖非常不切实际。面对大量的读写，我们也无从得知之后的写入和先前有没有关系，和哪些有关系。显式的追踪所有读集合所带来的开销会非常大。
不过，我们有一种更简单的手段：使用序列号（sequence numbers）或者时间戳（timestamps）来给事件定序。
我们不一定适用物理时间戳（如日历时钟），而是可以用逻辑时钟。最简单的，可以用一个计数器来递增地为每个操作安排一个序列号。
实际中尽管使用逻辑时间戳，但也会采用一些算法与物理时间戳进行关联，否则出现错误时，难以知道事件发生时的上下文，如 TSO 算法。
此种序列号和时间戳通常都非常紧凑，只占几个字节，但却能提供一种全序关系。通过给每个操作关联一个序列号，就能比较任何两个操作的先后关系。进一步，我们可以保证我们产生序列号的方式满足因果关系：如果操作 A 发生在 B 之前，则 A 获取到的序列号比 B 小。并发的（无法比较谁先谁后）操作获取到的序列号顺序不确定。
序列号本质上是一种全序，通过这种方式可以追踪因果关系，但也施加了一个比因果关系更为严格的全序，同时实现的性能也并不是特别好。
下面介绍了一些产生序列号的方式。
# 3.2.1 非因果序列生成器
如果系统中没有唯一的单主节点，那么为每个操作产生一个序列号就变得不那么简单直观了。常见的方式有如下：
- 每个节点独立地生成不相交的序列集。如，你的系统中有两个节点，一个节点只产生奇数序号，另一个节点只产生偶数序号。更通用一些，我们可以在生成的序号中保留一些位来编码对节点的标识，从而让不同的节点永远不会产生相同的序号。
- 可以为每个操作关联一个日历时钟。这些时间戳不是有序的（因为回拨），但如果有足够的精度，就可以让任意两个操作关联的时间戳不同，依次也可以达到全序的目的。此种方法有时候会被用在解决冲突使用后者胜的策略。
- 每次可以批量产生一组序列号。比如，在请求序列号时，节点 A 可以一次性声明占用 1 ~ 1000 的序列号，节点 B 会一次占用 1001~2000 的序列号。则本地的操作可以从拿到的这批序列号中直接分配，仅在快耗尽时再去请求一批。这种方法常被用在 TSO（timestamp oracle，单点授时）的优化中。
这三种方案都要比使用单点计数器生成序列号要性能好、扩展性更强，且能为系统中的每个操作产生全局唯一的、近似递增的序列号。但他们都存在着同样的问题：产生的序列号不是因果一致的。
# 3.2.2 Lamport 时间戳
虽然上面的几种方式产生的序列号不满足因果一致性，但却有一种相对简洁的方式可以做到—— Lamport 时间戳。它是由 Lesilie Lamport 在 1978 年提出的，是分布式领域被引用最多的论文之一。
下图展示了 Lamport 时间戳的使用方法。在该系统中，每个节点有一个唯一的 id 和一个记录处理过多少个操作的计数器，Lamport 时间戳是上述两者组成的二元组：(counter, node ID)。不同的节点可能会有相同的 counter 值，但通过引入 node ID，可以使所有时间戳都是全局唯一的。
Lamport 时间戳不依赖于物理时钟，但可以提供全序保证，对于任意两个 Lamport 时间戳：
- 具有较大 counter 的时间戳较大
- counter 相同，具有较大 node ID 的时间戳较大
让 Lamport 时间戳能够满足因果一致性的核心点在于：每个节点和客户端都会让 counter 追踪当前所看到（包括本机的和通信的）的最大值。当节点看到请求或者回复中携带的 counter 值比自己大，就会立即用其值设置本地 counter。
系统中所有的事件（event），和交互方（client，server）都要被纳入 Lamport Clock 体系内，才能追踪系统内的所有因果关系。因为只有通过通信才能有因果性，并通过通信来维持 counter 最大值。
只要最大的 counter 值通过每个操作被传播，就能保证 Lamport 时间戳满足因果一致。因为每次因果依赖的交互都会推高时间戳。
有时候我们会将 Lamport 时间戳和之前提到的版本向量混淆。虽然看起来相似，但其根本目的却是不同：
- 版本向量能够用于检测操作的并发和因果依赖
- Lamport 时间戳只是用于确定全序
对于 2，虽然 Lamport 时间戳能够追踪因果关系，即具有因果关系中的 happens-before 关系。但是反过来，并不能通过两个 Lamport 时间戳的大小来判断其是有因果关系、还是并发的。但相对于版本向量，Lamport 时间戳占用空间小，更为紧凑。
# 3.2.3 时间戳定序还不够
尽管 Lamport 时间戳能够给出一种能够追踪因果关系的全序时间戳生成算法，但并不足以解决分布式系统中所面临的的很多基本问题。
时间戳排序的一个问题是：只有在收集到系统中所有的操作信息之后，才能真正确定所有操作的全序。而为了获得这些信息，系统就需要检查每个节点，询问他们在做什么，一旦某个节点突然出现故障而无法连接，那么方法就无法正常运转。显然，这不是我们所期望的容错系统。
总而言之，为了实现像用户名唯一性约束这样的目标，仅仅对操作进行全序排列还是不够的，还需要知道这些操作是否发生、何时确定等。假如能够在创建用户名时，已经确定知道了没有其他节点正在执行相同用户名的创建，你大可以直接安全返回创建成功。
想要知道什么时候全序关系已经确定，就需要之后的“全序广播“。
# 3.3 全序广播
在一个分布式系统中，让所有节点就所有操作的某个确定的全局序列达成一致是相当棘手的。前一节讨论了使用序列号来定序，但相比单主模型这种方法容错能力很弱鸡（在使用时间戳定序的系统中，如果你想实现唯一性约束，就不能容忍任何故障）。
单主模型通过在所有节点中选出一个主，尔后在该节点上利用某个 CPU 对所有操作进行定序，从而确定一个唯一的全局序列。但使用单主模型的系统会面临两个问题：
- 当系统负载超过单机可以处理的尺度，如何进行扩容。
- 当主节点宕机时如何进行故障转移（failover）。
在分布式系统的语境下，该问题也被称为全序广播（total order broadcast）或者原子广播（atomic broadcast）。
顺序保证的范围。
多分区的数据库，对于每个分区使用单主模型，能够维持每个分区的操作全局有序，但并不能提供跨分区的一致性保证（比如一致性快照，外键约束）。当然，跨分区的全序保证也是可以提供的，只不过需要进行额外的协调。
全序广播是一种多个节点间交换消息的协议。它要求系统满足两个安全性质：
- 可靠交付。如果一个节点收到了消息，则系统内所有的相关节点都要收到该消息。
- 全序交付。每个节点接收到消息的顺序一致。
一个正确的全序广播算法需要保证上述两条性质在任何情况下都能够满足，包括网络故障和节点宕机。但当然，如果网络出现故障时，消息肯定不能送达所有节点；但算法可以进行重试，直到网络最终恢复（当然，恢复后也要保证所有消息送达的顺序一致）。
# 3.3.1 使用全序广播
像 Zookeeper 和 etcd 等共识服务都实现了全序广播算法。从这些共识服务我们能感觉到，全序广播和共识协议具有很强的关联性，我们会在本章稍后一探究竟。
全序广播正是数据库复制所需要的：如果我们让“消息”代表数据库中的写请求，且每个副本以相同的顺序处理相同的输入集，则每个副本必然会保持一致（除却暂时的临时同步延迟外）。该准则也被称为：状态机复制（state machine replication），在第 11 章的时候我们将继续该主题。
类似的，全序广播也可以用于实现可串行化的事务：如之前物理上串行提到的，消息在此具象为作为存储过程执行的一个确定性的事务，如果所有节点按同样的顺序处理这些消息，则数据中的所有分区和副本最终都会在数据上保持一致。
需要注意到，全序广播的一个重要性质是：当收到消息时，其顺序已经确定。这是因为，节点不能将后收到的消息，插入之前的已经收到的消息序列。这让全序广播要强于时间戳排序（timestamp order）。
还可以从另外一个角度来理解全序广播——用来写日志（比如复制日志、事务日志或者写前日志）：传递消息就像追加日志。由于所有节点都会按照同样的顺序发送消息，则所有节点在读取日志的时候也会得到同样的消息序列。
全序广播也可以用来实现提供防护令牌功能（fencing token，参见防护令牌，即关联了 id 的锁）的锁服务。每个上锁请求可以作为消息追加到日志中，依据其追加到日志中的顺序，所有请求可以被自然地编号。由于这个序列号是单调递增的，便可以充当防护令牌。在 Zookeeper 中，这个序列号便是 zxid。
# 3.3.2 使用全序广播实现线性一致性存储
在线性一致系统中，所有操作存在着一个全局序列。这是否意味着全序广播就是线性一致性？不尽然，但他们间有很深的联系。
- 全序广播是异步的：系统保证以同样的顺序交付消息，但并不保证消息的交付时刻（即，有的消息接收者间可能存在着滞后）
- 线性一致性是一种新鲜度保证：读取一定能看到最新成功的写
不过，你可以基于全序广播来构建线性一致的存储系统。如，可以用于保证用户名的唯一性约束。
对于该问题，可以这样实现。对每一个可能的用户名，我们使用一个支持 CAS 操作的线性寄存器，初始值为 null（表示该用户名没有被占用）。当用户想使用某个用户名创建账户时，使用 CAS 操作，在寄存器旧值为 null 时，将其值设置为该用户 account-id。由于寄存器的原子性，最后只有一个用户会成功。
使用全序广播系统作为日志追加服务，便可以实现这样一个支持可线性化 CAS 操作的“寄存器”：
- 向服务中追加一个带有某用户名的消息条目，表明你想使用该用户名。
- （由于全序广播是异步的）不断读取日志，直到能够读到刚才你追加的消息条目。
- 检查所有想要使用该用户名的消息，这时你可能会得到多条消息，如果你当初写下的消息在第一条，则你是成功的。此时，你可以“确认”（持久化，比如追加日志，比如写入数据库）占有该用户名的信息，然后给客户端返回成功。如果第一条消息不是你的，则终止请求。
这里其实隐藏了一些细节，即我们会将追加消息请求发送给全序广播系统，全序广播系统会真正将消息按之前提到的两条保证的方式（可靠送达和全序送达）同步到每个节点。因此，对于每个节点来说，会首先发起消息追加请求，然后之后某个时刻，可以等到真正同步回来的消息。如果觉得绕，可以带入 Raft 的付之日志来类比。
由于所有日志条目都会以同样的顺序送达每个节点，若有并发写入，则所有节点都能依靠日志顺序就谁“先来后到”达成一致。当有同名冲突时，可以选择第一条作为赢家，并舍弃其后的冲突请求。可以使用类似的方式，基于日志来实现涉及到多对象的事务的可串行化。
尽管该方式能够提供线性化的写入，却不能保证线性化的读取。如果你从一个异步同步日志的节点读取日志，就有可能读到陈旧的数据（更精确一点说，上述过程能够提供顺序一致性，sequential consistency，有时也被称为时间线一致性，timeline consistency，比线性一致性稍弱 ）。在此基础上，如果想让读取也变得可线性化，有几种做法：
- 让读取也走日志，即通过追加消息的方式将读取顺序化，然后当读取请求所在节点收到这条读取日志时才去真正的去读。则消息在日志中的位置定义了整个时间序列中读取真正发生的时间点。（etcd 中的法定读取就是用的类似的做法）
- 如果日志服务允许查询最新日志的位置，则可以在请求到来时，获取当时最新位置，然后不断查询日志看是否已经跟到最新位置。如果跟到了，就进行读取。（这是 Zookeeper 中 sync() 操作的背后的原理）
- 可以将读取路由到写入发生的那个节点，或者与写入严格同步的节点，以保证能够读到最新的内容。（这种技术用于链式复制，chain replication 中）
# 3.3.3 使用线性一致存储实现全序广播
上节展示了如何使用全序广播来实现 CAS 操作的线性化存储。我们也可以反过来，设有一个线性一致的存储系统，看如何基于其实现全序广播。
最简单的方法，假设我们有一个整数寄存器，并提供 increment-and-get 原子操作，当然提供 CAS 原子操作也是可以的，只是稍微没那么直观。
算法相当简单：对于每一个发给全序广播系统的消息，使用整数寄存器 increment-and-get 操作关联一个序列号；然后将消息发送给所有节点（重试任何丢失的消息）。每个节点接收到消息后利用序列号顺序对外交付消息。这种机制很像 TCP，但并不是描述通信双方，而是一个分布式系统。
注意到，和 Lamport 时间戳不同，从线性化的寄存器中获取的数字是连续的，非跳跃的（可以用来防止有中间的消息丢失）。如此一来，当某节点交付了消息 4 后，收到了消息 6，但不能立即交付，而需要等待消息 5 的到来。但在 Lamport 时间戳系统中则非如此——这（是否连续）也是全序广播和时间戳顺序的核心不同。
实现一个支持 increment-and-get 原子操作的线性化整数寄存器有多难？如果所有组件都不会出错，则很简单：你可以直接用单台机器上的一个变量。但如果连接到该节点的网络会出问题怎么办？这台机器机器宕机后，宕机前变量的值又该怎么恢复？理论上说，只要你对线性序列生成器思考的足够完备，就会不可避免的得到一个共识算法（consensus algorithm）。
这并不是巧合：可以证明，一个线性的 CAS 寄存器和全序广播都等价于共识协议（equivalent to consensus）。也即，如果你解决了其中任意一个问题，就可以通过某种手段将其转化为另一个问题的解决方案。这真是一个惊人的性质！
终于，说到了共识，这是本章余下将要全力探讨的问题。
上面铺垫了一大通来引出了共识协议。
# 4. 分布式事务和共识协议
在分布式计算领域，共识问题是最重要而基础的问题，目标就是让多个节点就某件事达成一致。
在很多场景下让多个节点达成共识是非常重要的：
- Leader 选举：唯一主节点来避免脑裂；
- 原子提交：让所有节点就事务的结果达成一致：成功 or 回滚
共识的不可能性
你也许听过 FLP —— 以 Fischer，Lynch 和 Paterson 三位作者姓名首字母命名的一种不可能原理——在网络可靠，但允许节点宕机（即便只有一个）的异步模型系统中，不存在总是能够达成共识的算法。在分布式系统中，我们又必须得假设节点可能会宕机，因此稳定可靠的共识算法是不存在的。但是，我们现在却在探讨可以达成共识的算法。这又是为啥？这可能吗？
答案是，FLP 不可能是基于异步系统模型（参见系统模型和现实）证明的，这是一种非常苛刻的模型，不能够使用任何时钟系统和超时检测。如果允许使用超时宕机检测、或者任何可以识别节点宕机的方法，就能够实现可靠的共识算法。甚而，只让算法用随机数来进行故障检测，也能够绕过这个不可能定理。
在实践中，分布式系统达成共识是可行的。
# 4.1 原子提交和两阶段事务
原子性能够对应用层提供一种简单的语义：成功 or 失败，不存在中间状态，这一点对于多对象事务和维持二级索引与原始数据的同步尤为重要。
# 4.1.1 从单机到分布式的原子提交
对于运行在单机数据上的事务，原子提交通常由存储引擎层来实现。单机上原子提交的实现方式：
当客户端请求数据库节点提交事务时，数据库会首先将事务所涉及到的写入进行持久化（通常通过写前日志 WAL 的方式），事务结束时在硬盘上追加一个特殊的提交记录（commit record）到日志上。如果数据库在处理事务的过程中宕机了，在重启时会从日志上对事务进行恢复：
- 如果在宕机前，提交记录已经追加到磁盘上，则该事务被认为已经成功提交。
- 否则，该事务所有的写入将会被回滚。
因此，在单机数据库里，事务是否提交主要取决于数据持久化到磁盘的顺序：首先是数据，接着是提交记录。提交事务还是中止事务，决定性时刻在于提交记录成功刷盘的那一瞬间：在此之前，事务可能会被中止（由于宕机）；在此之后，该事务一定会被提交（即使宕机）。也即，是唯一的硬件设备（某个特定节点上的某个具体的磁盘驱动）保证了提交的原子性。
然而，当事务涉及到多个节点时又当如何？
只是简单地在提交事务时给每个节点发送提交请求让其提交事务，是不能够满足事务基本要求的。这是因为，可能有的节点成功提交了，有的节点却提交失败了，导致多个节点处于不一致的状态，从而违反了原子性保证。而事务提交后是不可撤销的，否则会引起读取了该实物结果的事务也会失效，从而引起事务的级联中止。
尽管事务造成的结果可以通过补偿事务来弥补，但从数据库的视角上来看，这又是另一个事务了。所以我们需要一个算法来实现分布式的原子提交。
# 4.1.2 两阶段提交
两阶段提交（2PC，two-phase commit），是一种在多个节点上实现原子事务的算法。即，保证所有节点要么都提交，要么都中止。
相比单机事务的一次提交请求，2PC 中的提交、中止过程被拆分成了两个阶段，如下图所示：
2PC 引入了一个单机事务中没有的角色：协调者（coordinator，有时也被称为事务管理器，transaction manager）。
与协调者相对，需要完成事务的节点称为参与者（participants）。
两阶段提交
当应用层准备好提交后，协调者开始阶段一：向每个参与者发送 prepare 请求，询问他们是否能够提交。然后，协调者会根据参与者的返回而进行下一步动作：
- 如果所有参与者都回复 yes，表示能够提交，则协调者就会进入第二阶段发出 commit 请求，此时，提交事实上才开始执行。
- 如果有任何参与者回复 no，或者请求超时了，协调者就会进入第二阶段并发送一个 abort 请求，中止事务。
这个过程在某种程度上很像西方文化中的结婚仪式：牧师会分别问新娘、新郎是否愿意与对方结婚，通常，双方都会回答“我愿意”（I do）。当牧师收到双方肯定的回答后，就会宣布他们结为夫妇：即事务提交，并将这个令人高兴的事实传达给所有宾客。如果新娘、新郎有任何一方回答否，则仪式中止。
# 4.1.3 基于承诺的系统
让 2PC 能够保证原子性的核心原因到底是什么？
为了理解它的工作原理，我们把 2PC 各个阶段拆的更细一些：
- 当应用想开启一个分布式事务时，它会首先向协调者要一个事务 ID。该事务 ID 是全局唯一的。
- 当应用层准备好提交事务时，协调者会向所有参与者发送 prepare 请求，并在请求中打上事务 ID 标记。如果有请求失败或者超时，则协调者会对所有参与者发送带有该事务 ID 的中止请求。
- 当参与者收到准备提交请求时，它必须确认该事务能够在任何情况下都能被提交，才能回复 yes。这包括，将所有写入刷到磁盘（一旦承诺了，就不能反悔，即使之后遇到宕机、断电或者磁盘空间不足）、检查是否有冲突或者违反约束的情况。换句话说，如果回复 yes，意味着参与者让渡了中止事务的权利（给协调者），但此时并没有真正地提交。
- 当协调者收到所有参与者准备提交的回复后，会决定提交还是中止该事务（只有在所有参与者都回复 yes 时，才会提交）。协调者需要将该决策写入事务日志，并下刷到磁盘，以保证即使宕机重启，该决策也不会丢失。这被称为提交点（commit point）。
- 协调者将决策刷入了磁盘后，就会将决策（commit 或者 abort）请求发给所有参与方。如果某个请求失败或者超时，则协调者会对其进行无限重试，直到成功。不允许走回头路：如果协调者决定了提交，则不管要进行多少次的重试，也必须要保证该决策的执行。如果参与者在此时宕机了，则当重启时也必须进行提交——因为它承诺过要提交，因此在重启后不能拒绝提交。
因此，该协议有两个重要的“不归路”：
- 当某个参与者回复 yes 时，就做出了肯定可以提交的承诺。
- 当协调者决定提交时，该决定一旦做出，就是不可撤回的。
这两个承诺保证了 2PC 的原子性。
其实单机事务是将上述两个事件合二为一：将提交记录写入事务日志即代表提交。
# 4.1.4 协调者故障
2PC 中，如果参与者出现故障，则会对其进行无限重试。但当协调者出现故障时，系统该如何应对呢？
问题所在：如果协调者在准备提交请求发送前故障，则参与者可以放心的中止事务。然而，一旦参与者收到准备提交请求，并且回复 yes，则根据 2PC 设定，它不能单方面的中止事务 —— 而必须等待协调者的提交或者中止请求。如果此时协调者宕机或者网络故障，则参与者只能死等。参与者事务的这种状态称为存疑（in doubt）或者未定（uncertain）。
在未收到协调者的消息前，参与者无从得知是要提交还是中止。原则上，参与者之间可以互相沟通以确定该如何进行下一步，并最终达到一致，但这已经超脱了 2PC 协议范畴。实践中可能会对 2PC 做补充，但理论上并未规定该怎么做。
在 2PC 中，唯一使算法能够完成的方法就是等待协调者恢复。这也是为什么，协调者在给参与者发送提交或者中止消息时，需要先将该决策写入事务日志中：当协调者恢复时，他就能从事务日志中读取该决策，以让所有处于未决状态的参与者状态确定下来。如果协调者恢复了，发现并没有写入任何决策到事务日志中，则中止该事务。因此，2PC 的提交点（commit point）最终可以归结到协调者上的单机原子提交。
# 4.1.5 三阶段提交
省流：3PC 没人用。
由于 2PC 在等待协调者宕机恢复时系统可能会卡住，因此两阶段提交又称为阻塞式原子提交协议（blocking atomic commit protocol）。理论上，可以让使用某种办法让原子提交协议成为非阻塞的，从而在协调者宕机时，系统不会卡住。然而，在实践中该办法很不直观。
作为 2PC 的替代，人们又提出了三阶段提交（three-phase commit）。然而，3PC 对系统有一定假设：网络具有有界延迟，请求延迟也是有界的（bounded，参见超时和无界延迟）。在具有无界网络延迟进程停顿的实际系统中，3PC 无法保证原子性。
一般来说，非阻塞的原子提交依赖于一个完美的故障检测器（perfect failure detector）——即，一种可以判断某个节点是否宕机的可靠机制。在具有无界延迟的网络中，超时机制就不是一个可靠的故障检测方法，即使没有任何节点故障，一个请求仍会由于网络问题而超时。出于这个原因，即使 2PC 可能会因为协调者宕机卡住，但人们仍然在使用它，而没有转向 3PC。
# 4.2 实践中的分布式事务
2PC 实现的分布式事务毁誉参半：
- 誉：是简化应用层的一个重要 feature，提供了原子提交的安全保证
- 毁：运维复杂、降低性能、承诺过多
很多云服务选择不支持分布式事务，现在很多其实是在优化分布式事务，一般 NewSQL，也就是分布式关系型数据库会支持分布式事务机制。
“分布式事务”其实有着两种概念：
- 做分布式数据库的人的口中的“分布式事务”：数据库内部的分布式事务，它指跨节点的内部分布式事务，比如 MySQL 集群的 NDB 存储引擎就支持这样的内部事务支持。在这种情况下，所有事务参与节点都运行着同样的二进制代码，也就是不同节点是同构的。
- 做应用层的人的口中的“分布式事务”：异构分布式事务，它指所有参与者使用了两种以上的技术栈，如一个节点是 NoSQL，一个节点是 MQ。也就是不同节点是异构的。即使每个子系统内部实现完全不同，构建于其上的分布式事务也能够保证原子提交。
数据库内部的事务不需要考虑和其他系统的相容性，因此在实现时可以使用任何协议、可以针对特定技术栈进行任何优化。因此，数据库内部的分布式事务通常能够很好地工作。相反，横跨多个异构系统的事务实现则充满了挑战。
# 4.2.1 Exactly-once 消息处理
异构的分布式事务系统可以将多种异构的系统，以强大的方式进行整合。例如，当且仅当数据库中处理消息的事务成功提交时，消息队列才会将该消息标记为已处理。可以将消息确认和数据库写入打包在单个事务里进行原子提交，来实现上述行为。在分布式事务的加持下，即使消息队列和数据库是跑在不同机器上的不同技术栈的进程，上述目标也能实现。
如果消息投递或数据库事务任意一方出错，两者都会被中止。据此，消息队列可以在之后安全地重新投递该消息。通过将消息投递和消息处理打包进行原子的提交，不管成功之前重试多少次，我们都可以保证该消息只被有效地（effectively）处理恰好一次（exactly once）。中止事务时，会丢弃所有部分执行的结果。
只有参与系统都支持原子提交时，上述分布式事务才是可行的。例如，假设处理消息的一个副作用是发送邮件，且邮件服务器不支持两阶段提交。则在消息处理失败进行重试的过程中，可能出现邮件被发送多次的现象。但如果，在事务中止时，消息处理的所有副作用都可以回滚，则处理步骤可以像没有任何事情发生过一样，安全地进行重试。
我们在第十一章的时候会重新探讨对消息进行恰好一次的处理的话题。这里，我们首先看下异构系统上的分布式事务的原子提交协议（atomic commit protocol）。
# 4.2.2 XA 事务
X/Open XA （eXtended Architecture 的简写）是在异构系统间实现两阶段提交的一个标准。它于 1991 年被引入，并被广泛的实现：很多传统的关系型数据库（包括 PostgreSQL，MySQL，DB2，SQL Server 和 Oracle）和消息队列（包括 ActiveMQ，HornetQ，MSMQ 和 IBM MQ）都支持 XA 协议。
XA 不是一个网络协议——它定义了一组和事务协调者交互的 C 语言 API 接口。当然，该 API 也有其他语言实现。比如，在 Java EE 应用，XA 事务使用 Java 事务 API（JTA）实现，进而被很多支持 JDBC 的数据库使用，也被 Java Message Service（JMS）的消息队列所支持。
Open Group 组织针对 XA 定义了分布式事务处理模型，也被称为 DTP 模型。包括三个组件，
- AP(Application Program)：应用程序，通过定义组成事务的特定操作来定义事务边界。
- RM(Resouces Manager)：资源管理器，管理共享资源的服务，对应两阶段提交协议中的参与者，如数据库或消息队列服务。
- TM(Transaction Manager)：事务管理器，管理全局事务，协调事务的提交或者回滚，并协调故障恢复。
使用事务的应用层会以网络驱动（network driver）或者客户端库（client library）来使用 XA 的 API 与参与者服务（数据库或者消息队列）进行交互。如果驱动程序支持 XA 协议，则意味着应用侧可以调用 XA 的 API 来确定一个操作是否是分布式事务的一部分（即通过 XA 定义的接口来确定事务所涵盖操作的边界）；如果是，则会发送必要的消息给参与者。XA 驱动也提供了一些回调，协调者可以使用这些回调要求参与者进行准备、提交或者中止。
事务的协调者实现了 XA API。XA 的标椎并没规定协调者该如何实现，并且在实践中协调者通常以库的形式被加载进应用程序中（作为应用程序的一部分，而非额外单独的一个服务）。它会追踪事务中的所有参与者，在要求参与者准备提交（prepare）后收集其回复，使用本地磁盘上的日志来跟踪每个事务的提交/中止决策。
如果应用进程崩溃、或者应用所在机器宕机，协调者也会随之而宕机。所有已经进行过提准备过，但未真正提交的事务（未定事务）无疑会阻塞住。由于协调者的日志在应用程序的本地磁盘里，则该服务器必须能够重启，从而让协调者库能够读取磁盘上的日志，以恢复之前所做提交或中止的决策。据此，协调者才可以使用 XA 协议的回调，要求所有参与者提交或者中止。数据服务器不能直接和协调者进行通信，所有的通信必须要通过客户端的 XA 库。
# 4.2.3 阻塞时仍持有锁
为什么我们这么关心事务的参与者在未定状态时卡住呢？
问题的关键点在于存在锁（locking）。为了实现事务隔离，数据库会使用锁来对数据进行保护，而数据库在提交或者中止事务前不能够释放获取的这些锁。因此，在使用两阶段提交时，一个事务必须在其处于未定状态期间一直持有锁。如果协调者宕机导致参与者一直处于未定状态，会让锁一直不能释放，从而阻塞系统的读写。
所以，必须解决处于停顿状态的那些事务。
# 4.2.4 从协调者故障中恢复
理论上来说，如果协调者宕机重启后，就能够从日志读取之前决策，从而处理还在存疑的参与者事务。
然而，在实践中，常会产生一些孤立的（orphaned）未定事务——即，由于某种原因，事务的协调者（比如由于软件 bug 事务日志丢失或者损坏）无从判断事务的最终结果是提交还是回滚。由是，这些事务不能够被自动的处理，从而永久的卡在那里，持有锁并且阻塞其他事务。即使重启数据库服务器也不能让其从卡住中恢复，在一个正确实现的 2PC 系统中，参与者在重启后必须仍然持有事务相关锁（否则就会违反其承诺，进而原子性保证），这是一种非常棘手的情况。
唯一的出路是让管理员手动的来提交或者中止事务。管理员首先需要检查所有包含未定事务的参与者，看是否有任何参与者提交或者中止了，从而对其他卡主的参与者手动执行相同操作（通过外力来让所有参与者达成一致）。解决该问题需要大量手工操作，并且在线上环境中断服务的巨大压力和时间限制下。
很多 XA 事务的实现会留有紧急后门，称为启发式决策（heuristic decisions）：允许一个参与者不用等待协调者的决策，而单方面决定中止还是提交一个未定事务。需要说明的是，这里的启发式仅仅是可能打破原子性（probably breaking atomicity）的一种委婉说法。因为这么做可能会违反两阶段提交所提供的保证。因此这种启发式决策仅是为了救急，而不能进行日常使用。（毕竟这时候它都已经卡住了，就不要对它有过高的期待了）
# 4.2.5 分布式事务的限制
XA 事务解决了一些很现实而重要的难题：让异构的数据系统保持一致。但它也引入了一些重大的运维难点：事物的协调者由于存储了状态数据，也算是一个数据库，因此也需要像其他数据库一样小心谨慎地对待：
- 如果协调者没有使用多副本机制，仅运行在一台机器上，则它会成为系统的一个单点。然而，很多协调者的实现要么默认不是高可用的，要么只提供了很粗糙的冗余支持。
- 存储了状态的协调者无法享受现在流行的“无状态服务”的诸多好处
- 由于 XA 需要和足够广泛的数据系统进行适配，因此其 API 只能维持一个最小公共接口集，由此带来了 XA 在能力上的诸多限制。比如不能在跨系统检测死锁，因此 XA 无法提供跨系统的 SSI 隔离级别，因为这要求支持一种可以跨系统监测冲突的协议。
- 数据库内部的分布式事务在限制上就少很多了，例如 SSI 的分布式版本就是可行的。但即使成功地提交一个 2PC 事务仍有诸多问题：所有的参与者必须要回复（但可以异步回应）。因此，一旦系统内任何子模块损坏了，则事务也随之失败。从这个角度来说，分布式事务有放大故障的嫌疑，这与我们构建容错系统的目标背道而驰（这就是 tradeoff，为上层提供的更多的一致性保证，就会牺牲性能，降低可用性）。
上述事实是否意味着我们应该放弃让不同系统保持一致的努力？不尽然，有很多其他方法，既可以让我们达到同样的目标，而又不必引入异构分布式事务的痛点。我们在第 11 章和 12 章会回到对这个问题的讨论。现在让我们先把共识问题这个主题讲完。
# 4.3 容错的共识算法
千呼万唤，终于来到共识算法了。
通俗来说，共识（consensus）意味着让多个节点就某件事情达成一致。
比如说，如果多个人同时抢某次航班的最后一张票、预定剧院里的同一个座位或者使用同一个用户名注册账号，则可以使用共识协议来判断这些互斥的操作中，谁是真正的赢家（这其实利用了之前提到的可线性化）。
形式化一些，共识协议通常被描述为：一个或者多个节点可能会各自提议（propose）一些值，共识协议需要在这些值中间做出唯一的决策（decide）。在预定座位的例子中，当多个客户试图并发地获取最后一个座位时，每个处理用户请求的节点会提议一个其所处理的用户 ID，然后最终决策对应着哪个用户会得到该作为。
在这种形式化表述中，一个共识协议必须满足以下条件：
- 全局一致性（Uniform agreement）：没有任何两个节点最终做出不同决策。
- 正直性（Integrity）：没有任何节点会做出两次决策（不会反复横跳）
- 有效性（Validity）：如果一个节点做出了决策，该决策所对应的值一定来自系统内某个节点的提议（不会凭空捏造）
- 可终止性（Termination）：任何没有宕机的节点，最终都会给出对某个值的决策
全局一致和正直性定义了共识协议的核心思想：所有节点都要决策出同样的结果，并且一旦做出决策，就不能反悔。加入有效性更多的是为了排除一些无效（trivial）结果：如果无论其他节点提议什么，一个算法都会选择 null 作为决策值；该算法虽然满足一致性和正直性约束，但却不满足有效性。
如果不关心容错性，则仅满足前三个性质就足够了：比如，可以通过硬编码指定某个节点为“独裁者”，并且让其做所有决策，其他节点只要服从即可。然而，一旦该节点故障，则整个系统不能继续决策和推进。事实上，这正是我们在两阶段提交算法中看到的：一旦协调者故障，所有处于未定状态的参与者都无法独自决策是提交还是中止。
可终止性是对容错的一种形式化描述（从结果来描述）。它本质上是在说，一个共识算法不能让系统陷入一种卡在那、啥也不干，直到永远的状态。换句话说，系统必须能够正常运作，即使有些节点宕机，其他节点也必须能够继续做出决策。可终止性属于一种活性，而其他三个性质是安全性。
该模型对节点宕机做了最坏的假设——一旦节点宕机，就会凭空消失，再也不会回来。适用于该模型的场景不是软件故障造成的宕机，而是由火山喷发、地震等造成的数据中心不可逆转的损坏。在该系统模型下，任何需要等待节点回复的算法都不可能满足可终止性。具体来说，在这种设定下，2PC 就不满足可结束性要求。
当然，如果所有节点都宕机，则任何算法都不可能做出任何决策。共识算法有其能够承受的宕机节点数上限：事实上，可以证明，任何共识算法都要求多数节点存活，以确保正常运行，满足可终止性。多数派节点可以安全的构成一个法定多数（quorum）。
因此，可终止性受限于少于半数节点宕机或不可达的假设。然而，大多数共识算法的实现在大多数节点都宕机或者网络出现大范围故障时仍然能保持安全性——一致性，正直性和有效性。也即，大范围的节点下线可能会让系统不能继续处理请求，但不会因此破坏共识协议，让其做出不合法决策。
大多数共识算法会假设系统中不存在拜占庭故障，即如果某些节点故意不遵守协议，就有可能破坏协议的安全性。但其实，研究表明，只要发生拜占庭故障的节点数小于三分之一，那也可以达成共识，这其实就是区块链的原理了，本书不再继续讨论下去。
# 4.3.1 全序广播中的共识算法
最广为人知的容错性的共识算法有——VSR（Viewstamped Replication）、Paxos、Raft 和 Zab。这些共识算法间有非常多的共同点，但他们确实不完全相同。在本书中我们不会探究每个共识算法的区别的所有细节：只需知道他们在顶层设计中有很多相似之处即可。除非，你想自己实现一个共识算法。
当然，并不推荐自己去实现，因为实现一个工业级可用的共识算法很难，需要处理特别多的 corner case，而这些情况不经过大量实践是根本不会想到的。虽然 TLA 可以验证你的算法，但并不能验证你的实现。
这些共识算法通常不会直接按上述形式化的定义（如提议并在单值上进行决策，同时满足一致性、正直性，有效性和可终止性）来实现。转而，他们通常会在一系列值上做出决策，从而事实上变成一种全序广播算法，本章前面小节讨论过这个问题。
全序广播等价于多轮次的共识协议（每个轮次，会使用共识协议对全序广播中的一条消息的全局顺序做出决策）：
- 由于共识协议的全局一致性，所有节点会以同样的顺序投递同样的消息。
- 由于正直性，具有同样 id 的消息不会重复。
- 由于有效性，消息不会是损坏的，也不会是凭空捏造的。
- 由于可终止性，消息不会丢失。
VSR， Raft 和 Zab 都直接实现了全序广播，相对多次使用共识算法，每次就单个只达成一致，这种方法要更高效。对于 Paxos，其全序广播版本是 Multi-Paxos。
# 4.3.2 单主复制和共识协议
之前我们讨论的主从复制模型，主节点会接管所有写入，并且以同样的顺序复制给从节点，以此保持所有副本的数据一致。那这本质上不就是全序广播吗？为什么我们当时不需要考虑这个问题呢？
该问题的核心点在于主节点（领导者）是怎样选出的。如果主节点由管理员手动配置，那管理员本质上就变成了共识算法的独裁者，强制所有节点达成一致：只有一个节点允许接受写入（决定复制日志中所有日志的顺序），并且一旦该主节点宕机，系统便会陷入不可用的状态，直到运维人员手动的配置另外一个节点为主节点。这样的系统在实践中也可以正常运作，但是并不满足共识算法中的可终止性，因为它在停顿后要求运维人员的干预，才能继续运转。
有些数据库在遇到主节点故障时，会自动地重新进行主选举，将一个从节点提升为新的主节点（参见宕机处理）。这就让我们进一步逼近了可容错的全序广播，并且解决了共识问题。但，这中间有个循环依赖的问题。我们之前讨论了脑裂（split brain）问题，并且断言所有的节点必须就谁是领导者达成一致——否则，如果有两个不同节点都认为自己是领导者，则会有多个写入点，进而让数据库陷入不一致的状态。因此，我们需要共识算法来进行选主。但我们说共识算法本质上可以描述为全序广播算法，然后全序广播算法又和单主复制一样，然后单主复制又依赖时刻保证单个主，然后…
看起来，为了选出单个主节点，我们首先需要一个主节点；为了解决共识问题，我们首先要有一个共识算法；我们如何打破这个循环依赖呢？
# 4.3.3 纪元编号和法定人数
到目前为止所提到的共识算法都在内部需要一个某种形式上的主节点，但都不能保证主节点是唯一的。。但，他们可以给出一个稍弱的保证：协议会定义一个纪元编号（epoch number），并且保证在每一个纪元（epoch）内，主节点是唯一的。
纪元编号在不同的算法中有不同的名字：在 Paxos 中称为投票编号，ballot number； 在 Viewstamp Replication 中称为视图编号，view number；在 Raft 中称为任期编号，term number
每次当前的主节点被认为下线时（可能是宕机，也可能只是网络不通），所有认为该主下线的节点就会发起选举，以选出新的主节点。每次选举会使用一个更高的纪元编号，因此所有的纪元编号是全序且单调递增的。如果不同纪元中有两个节点都认为自己是主（比如之前的主节点并没有宕机），则具有较高纪元编号的主节点胜出。
在一个主节点被授权做任何事之前，它必须要确认不会有更权威的主节点（具有更高的纪元编号）会做出不同决策。那该一个主节点如何知道自己没有被其他节点“赶下台”呢？回忆一下，我们在真相由多数派定义一节中讨论过的：分布式系统中，一个节点不能无脑相信自己的判断——因为一个节点认为自己是主，不意味着其他节点也都认可这一点。因此，主节点在决策前需要首先从所有节点获得法定票数。对于每个决策，主节点都必须将其作为提案发给其他所有节点，并且等待法定节点的同意。法定节点通常来说，会包含多数派节点，但也不绝对（Flexible Paxos (opens new window) 介绍了一种不需要多数节点的放宽的 Paxos 算法）。如果法定节点的回复中没有任何更高纪元的，则当前主节点可以放心的认为没有发生新纪元的主选举，并可以据此认为他仍然“握有领导权”。从而，可以安全的对提案进行决策。
该投票过程非常像两阶段提交提交算法。最大的区别在于：
- 2PC 中的协调者不是选出来的，而是管理员配置的；
- 2PC 要求每一个参与者都回复 yes，而可容错的共识算法只要求多数节点的投票。
此外，共识算法在新领导者上台时，针对数据不一致的节点，还设计了一套恢复策略。这些不同点是共识算法能够保证正确性和容错性的核心设计。
# 4.3.4 共识算法的局限性
共识算法对于分布式系统是一个划时代的突破：他们能够在不确定的环境里保证安全性（一致性、正直性和有效性），在此基础上还能够进行容错（只要大多数节点还活着就能正常运转）。他们还实现了全序广播，因此能够用来实现容错的线性一致的系统。
然而，共识算法并非银弹，因为这些收益都是有代价的：
- 同步复制损失性能：每次进行决策（更改数据）前都要让多数节点进行投票，意味着这是一个同步复制系统，而同步复制相较于异步复制会有性能问题。
- 多数派会增加系统冗余：共识系统总是要求有严格多数节点存活才能正常运行。这意味着，如果你要容忍单节点故障就至少需要三个节点（三节点中的两个节点可以组成多数派），如果要容忍两个节点故障就至少需要五个节点（五个节点中的三个节点组成多数派）。如果网络故障切断了其中一些节点和其他节点的联系，则总工会有多数节点所在的分区可以继续工作，剩下的少数节点的分区则会处于事实上的停顿状态，导致了这些还可以使用的节点的浪费。
- 动态成员变更复杂：很多共识算法会假定有固定的数目节点参与投票，这意味着你不能往集群中增删节点。共识算法的动态成员变更（dynamic membership）扩展允许集群的节点集随时间推移而发生变动，但相对于静态成员算法，这种扩展版本非常难以理解。
- 复杂网络环境性能很差。共识系统通常通过超时机制来对故障节点进行检测。在延迟高度变化的网络中，尤其是多地部署的分布式系统中，某些存活节点由于网络的瞬时抖动常被误认为发生了故障。尽管这些问题并不会破坏安全性，但频繁的领导者选举会导致极差的性能表现——系统可能会大部分时间都在选主而不是正常干活上。
有时，共识算法对网络故障非常敏感。例如，我们发现 Raft 对某些边角情况处理的不尽如人意：如果整个网络都正常运行，只有某个特定的网络连接持续的抖动。Raft 会进行在两个节点间频繁切主，或者当前主节点的领导权被不断挑战，则系统不再能有效的运转，对外提供服务（这里存疑，通过预投票，pre-vote 应该可以解决这个问题）。其他共识算法也有类似的问题，针对不可靠网络设计更为鲁棒的共识算法仍是一个正在持续研究的课题。
# 4.4 成员关系和协调服务
类似于 Zookeeper 和 etcd 的项目，经常被描述为“分布式 KV 存储”或者“协调和配置服务”。这些系统的 API 看起来也非常像数据库：
- 你可以读取或者写入给定 key 的 value
- 你也可以遍历一组 keys
如果这些系统本质上是数据库，为什么它们要费这么大力气实现共识算法呢？到底是什么让他们区别于一般意义上的数据库？
为了弄清该问题的答案，我们需要简单的探讨下如何使用类似 Zookeeper 这样的服务。作为一个应用开发者，你很少直接使用 Zookeeper，因为它并不能作为通常意义上的数据库而直接被应用层使用。它更像是一种你在使用其他项目时间接依赖：例如，Hbase，Hadoop YARN，OpenStack Nove 和 Kafka 都在背后依赖了 Zookeeper。这些项目到底依赖 Zookeeper 的什么呢？
Zookeeper 和 etcd 设计目标为存储小尺度的数据，比如能装进内存里的（但在这些系统里，数据还是会落盘的）——因此你不能期望把所有应用层数据都存进这些系统里。这些系统使用可容错的全序广播算法，将小尺寸的数据被复制到所有节点上。如前所述，我们做数据库复制的时候真正需要的东西其实是全序广播：如果每条消息代表针对数据库的一个修改，以相同的顺序对所有副本应用相同的改动，能够将数据库保持在一致的状态。
Zookeeper 是模仿 Google 的 Chunk 锁服务实现的，不仅实现了全序广播算法（进而实现了共识），也实现了其他一些对分布式系统非常有用的功能集：
- 线性化的原子操作（lock）：使用原子的 CAS 操作，可以实现锁：如果多个节点并发执行同一个操作，只有一个会成功。共识协议能够保证，即使随时可能出现节点宕机或者网络故障，操作仍然是原子和线性化的。一个分布式锁通常实现为具有过期时间的租约（lease），这样即使客户端宕机，锁也能够被最终释放。
- 操作的全序保证（zxid）：在领导者和锁一节中我们讨论过，当某个资源被锁或者租约保护时，你需要防护令牌机制来防止由于进程停顿而造成的加锁冲突。防护令牌一个在每次获取锁都会单调自增的数值。Zookeeper 通过给每个操作赋予一个全局自增的事务 id（zxid）和一个版本号（cversion）来提供该功能。（zxid 就可以作为 fencing token）
- 故障检测（ephemeral node）：客户端和 ZooKeeper 的服务器间维持着一个长会话，客户端和服务端通过周期性的心跳来检测对端是否仍然存活。即使该连接短暂断掉，或者 ZooKeeper 节点故障，该会话仍然能够存活。但如果，心跳停顿间隔过长，超过了会话的超时阈值，ZooKeeper 会标记该会话死亡。所有该会话关联的锁在超时都将会被释放（ZooKeeper 将其称为暂态节点，ephemeral nodes，这类节点可以将生命周期与会话进行绑定）。
- 变动通知（watch）：客户端不仅可以读取其他节点创建的锁或者值，也可以直接对这些对象的变化进行守望（watch）。通过守望机制，客户端可以立即发现是否有其他客户端加入集群（通过这些客户端写入 ZooKeeper 的值）、其他客户端是否故障（通过这些客户端注册到 ZooKeeper 中的暂态节点的消失）。通过订阅这些通知，客户端可以避免频繁地去 ZooKeeper 拉取信息，比对以确定是否发生了某些变化。
对于这些功能，只有线性化的原子操作真正需要共识算法。但这些操作的组合，使得类似 ZooKeeper 的系统对分布式系统非常有用。
下面介绍几个使用 Zookeeper 的场景：
# 4.4.1 为节点分配任务
另一种 ZooKeeper/Chubby 非常适用的场景是选主：假设你有多个进程或服务，其中一个需要被选为领导者或者主服务，如果领导者故障，则另外一个节点需要接管。
这不仅对于单主模型的系统非常重要，对于任务调度器或其他类似有状态服务来说，该功能也十分有用。
另一个例子是，你有一些分了片的资源（数据库、消息流、文件存储、分布式的 actor 等等），并且需要决策哪些分片要放到哪些节点上去。当新节点加入集群后，一些分片需要从现有节点挪动到这些新节点上去，以进行负载均衡。当有节点故障或者被移除时，其他的节点需要接管故障节点的负载。
可以通过谨慎的组合使用 ZooKeeper 中的原子操作、暂态节点和通知机制来实现这类任务。如果实现正确，则可以让应用在遇到故障时，无人工干预的情况下自动恢复。即使有很多基于 ZooKeeper 的二次封装库（如 Apache Curator ）可以借助，实现正确仍然不容易。但总好过从头实现所需的共识算法.
刚开始时，一个应用可能会运行在单机上，但最终可能会扩展到上千节点的集群上。在如此多的节点上进行多数票选举会非常低效。相反，ZooKeeper 通常运行在固定节点的集群上（通常是三个或者五个），并且只须在这几个节点间达成共识，然后就可以支持非常多的客户端访问。这样，ZooKeeper 提供了一种可以将部分功能（共识算法、外包定序、故障检测）“外包”（outsouring）给外部服务的方法。
通常来说，ZooKeeper 所管理的数据只会很低频的改变：比如它会维护类似 “运行在 10.1.1.23 节点上的服务是分片 7 的领导者”的元信息，这种信息只会在分钟或者小时级的时间尺度上进行改变。这些系统不是为了存储应用运行时的数据，毕竟这些数据可能会以上千甚至上百万 QPS 的速率被修改。如果应用需要将数据从一个节点同步到另外一个节点，则需要使用其他工具（如 Apache 的 BookKeeper，一个类似于日志的存储服务，会将 log 切分并做冗余，Pulsar 的存储层在用）。
# 4.4.2 服务发现
ZooKeeper，etcd 和 Consul 也会用于服务发现（service discovery）——即根据服务名称找到其对应的 IP 地址以进行连接。
然而，服务发现是否真的需要共识协议暂时存疑。传统上，人们使用 DNS 服务来通过服务名找到其对应 IP 地址。DNS 通常使用多级缓存来获取高性能和高可用性。从 DNS 读取信息肯定不满足线性一致性，而且从 DNS 中偶尔读到过期的结果通常问题不大。相比线性一致性，高可用性和对网络的鲁棒性才是更重要的事情。
尽管服务发现不需要共识协议，但领导者选举需要。因此，如果你的共识系统已经知道领导者是谁，他就可以利用这些信息帮助别的服务来发现谁是领导者。处于这种目的，一些共识系统支持只读的缓存副本（如 Raft 中的 learner）。这些副本从共识协议中异步的接收数据，但并不参与投票。因此可以提供不在意线性一致性的读取。
# 4.4.3 成员服务
ZooKeeper 及类似服务可以视为成员服务（membership services）研究范畴的一部分，该研究可以上溯到上世纪八十年代，对于构建高可用系统非常重要，如空中交管系统。
成员服务可以确定当前集群中哪些节点当前时存活的。如第八章中所说，在具有无界延迟的网络中，不可能可靠的检测出一个节点是否故障。然而，如果你综合使用故障检测和共识算法，所有节点能够对哪些节点存活这件事达成共识。
使用共识协议也有可能错将一个节点认为下线了，尽管它事实上是存活的。但尽管如此，只要系统能够对当前系统包含哪些节点达成共识，就仍然很有用处。例如，选主算法可以是——在系统当前所有节点中选一个具有最小标号的节点。如果所有节点对系统当前包含哪些节点存在分歧，则这种方法就不能正常工作（不同节点眼中的的最小编号节点可能不一致，从而让大家选出的主不一致）。