共识问题是分布式计算中最重要也是最基本的问题之一。有很多重要的场景都需要集群节点达成某种一致，例如：
- 主节点选举
- 原子事务提交：对于支持跨节点或跨分区事务的数据库，会面临这样的问题：某个事务可能在一些节点上执行成功，但在其他节点却不幸发生了失败。为了维护事务的原子性，所有节点必须对事务的结果达成一致：要么全部成功提交（假定没有出错），要么中止/回滚（如果出现了错误）。这个共识的例子被称为原子提交（atomic commit）问题。
原子性可以防止失败的事务破坏系统，避免形成部分成功夹杂着部分失败。这对于多对象事务和维护二级索引格外重要。
==对于在单个数据库节点上执行的事务，原子性通常由存储引擎来负责==。当客户端请求数据库节点提交事务时，数据库首先使事务的写入持久化（通常保存在预写日志中），然后把提交记录追加写入到磁盘的日志文件中。如果数据库在该过程中间发生了崩溃，那么当节点重启后，事务可以从日志中恢复：如果在崩溃之前提交记录已成功写入磁盘，则认为事务已安全提交；否则，回滚该事务的所有写入。
但是，如果一个事务涉及多个节点呢？例如，一个分区数据库中多对象事务，或者是基于词条分区的二级索引（其中索引条目可能位于与主数据不同的节点上，请参阅第 6 章 ”分区与二级索引“）。
如果一部分节点提交了事务，而其他节点却放弃了事务，节点之间就会变得不一致（见图 7-3）。而且某个节点一旦提交了事务，即使事后发现其他节点发生中止，它也无法再撤销已提交的事务。正因如此，如果有部分节点提交了事务，则所有节点也必须跟着提交事务。
事务提交不可撤销，不能事后再改变主意（在提交之后再追溯去中止）。这些规则背后的深层原因是，一旦数据提交，就被其他事务可见，继而其他客户端会基于此做出相应的决策。这个原则构成了读-提交隔离级别的基础（参阅第 7 章 ”读-提交“）。==如果允许事务在提交后还能中止，会违背之后所有读-提交的事务，进而被迫产生级联式的追溯和撤销。==
当然已提交事务的效果可以被之后一笔新的事务来抵消掉，即==补偿性事务==（ compensating transaction）。不过，从数据库的角度来看，前后两个事务完全互相独立。类似这种跨事务的正确性需要由应用层来负责。
两阶段提交（two-phase commit, 2PC）是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。它是分布式数据库中的经典算法之一。2PC 在某些数据库内部使用，或者以 XA 事务形式（例如 Java Transaction API）或 SOAP Web 服务 WS-AtomicTransaction 的形式提供给应用程 序。
2PC 的基本流程如图 9-9 所示。
2PC 引入了单节点事务所没有的一个新组件：==协调者==（coordinator，也称为事务管理器）。协调者通常实现为共享库，运行在请求事务相同进程中（例如嵌入在 Java EE 容器中），但也可以是单独的进程或服务。常见协调者的例子包括 Narayana，JOTM，BTM 或 MSDTC。
只从上面简单的描述可能还是不清楚为什么两阶段提交可以确保跨节点的原子性，而单一提交却做不到。试想，即使对于 2PC，准备和提交请求也一样可能发生丢失，那么 2PC 究竟为何不同？
为了理解其工作原理，我们来更详细地分解这个过程：
- 当应用程序启动一个分布式事务时，它首先向协调者请求事务 ID，该 ID 全局唯一。
- 应用程序在每个参与节点上执行单节点事务，并将全局唯一事务 ID 附加到事务上。此时，读写都是在单节点内完成。如果在这个阶段出现问题（例如节点崩溃或请求超时），则协调者和其他参与者都可以安全中止。
- 当应用程序准备提交时，协调者向所有参与者发送 prepare 请求，并附带全局事务 ID 。如果 prepare 请求有任何一个发生失败或者超时，则协调者会通知所有参与者放弃事务。
- 参与者在收到 prepare 请求之后，确保在任何情况下都可以提交事务，包括安全地将事务数据写入磁盘（不能以任何借口稍后拒绝提交，包括系统崩溃，电源故障或磁盘空间不足等），并检查是否存在冲突或约束违规。==一旦向协调者回答 ”是“ ，节点就承诺会提交事务。换句话说，尽管还没有真正提交，但参与者已表态此后不会行使放弃事务的权利。==
- 当协调者收到所有 prepare 请求的答复时，就是否 commit（或 abort）事务要做出明确的决定（即只有所有参与者都投赞成票时才会提交）。==协调者把最后的决定写入到磁盘的事务日志中，防止稍后系统崩溃，并可以恢复之前的决定==。这个时刻称为==提交点==（ commit point）。
- 协调者的决定写入磁盘之后，接下来向所有参与者发送 commit（或 abort）请求。==如果此请求出现失败或超时，则协调者必须一直重试，直到成功为止==。此时，==所有节点不允许有任何反悔==：开弓没有回头箭，一旦做了决定，就必须贯彻执行，即使需要很多次重试。而==如果有参与者在此期间出现故障，在其恢复之后，也必须继续执行==。这是因为之前参与者都投票选择了 ”是“，对于做出的承诺同样没有反悔的余地。
如果参与者或者网络在 2PC 期间发生失败，例如在第一阶段，任何一个准备请求发生了失败或者超时，那么协调者就会决定中止交易；或者在第二阶段发生提交（或中止）请求失败，则协调者将无限期重试。但是，如果协调者本身发生了故障，接下来会发生什么现在还不太清楚。
==如果协调者在发送 prepare 请求之前就已失败，则参与者可以安全地中止交易==。==但是，一旦参与者收到了 prepare 请求并做了投票 ”是“，则参与者不能单方面放弃，它必须等待协调者的决定。如果在决定到达之前，出现协调者崩溃或网络故障，则参与者只能无奈等待。此时参与者处在一种不确定的状态。==
情况如图 9-10 所示。在该例子中，协调者实际上做出了提交决定，数据库 2 已经收到了 commit 请求。但是，协调者在将 commit 请求发送到数据库 1 之前发生了崩溃，因此数据库 1 不知道该提交还是中止。超时机制也无法解决问题：如果超时之后数据库 1 决定单方面中止，最终将与完成提交的数据库 2 产生不一致。同理，参与者也不能单方面决定提交，因为可能有些参与者投了否决票导致协调者最终的决定是放弃。
没有协调者的消息，参与者无法知道下一步的行动（是 commit 还是 abort）。理论上，==参与者之间可以互相通信，通过了解每个参与者的投票情况并最终达成一致==，不过这已经不是 2PC 协议的范畴了。
==2PC 能够顺利完成的唯一方法是等待协调者恢复，这就是为什么协调者必须在向参与者发送 commit（或 abort）请求之前要将决定写入磁盘的事务日志：等协调者恢复之后，通过读取事务日志来确定所有未决的事务状态。==如果在协调者日志中没有完成提交记录就会中止。此时，2PC 的提交点现在归结为协调者在常规单节点上的原子提交。
两阶段提交也被称为阻塞式原子提交协议，因为 2PC 可能在等待协调者恢复时卡住。理论上，可以使其改进为非阻塞式从而避免这种情况。但是，实践中要想做到这一点并不容易。
作为 2PC 的替代方案，目前也有三阶段提交算法。然而，3PC 假定一个有界的网络延迟和节点在规定时间内响应。考虑到目前大多数具有无限网络延迟和进程暂停的实际情况（见第 8 章），无法保证原子性。
通常，非阻塞原子提交依赖于一个完美的故障检测器，即有一个非常可靠的机制可以判断出节点是否已经崩溃。在无限延迟的网络环境中，超时机制并不是可靠的故障检测器，因为即使节点正常，请求也可能由于网络问题而最终超时。
略
略
略
理论上，如果协调者崩溃之后重新启动，它应该可以从日志中恢复那些停顿的事务。然而，在实践中，孤立的不确定事务确实会发生。无论何种原因，例如由于软件 bug 导致交易日志丢失或者损坏，最终协调者还是出现了恢复失败。那些悬而未决的事务无法自动解决，而是永远留在那里，而且还持有锁并阻止其他事务。
即使重启那些处于停顿状态的数据库节点也无法解决这个问题，这是由于 2PC 的正确实现要求即使发生了重启，也要继续保持重启之前事务的加锁（否则就会违背原子性保证）。
- 如果协调者不支持数据复制，而是在单节点上运行，那么它就是整个系统的单点故障（因为它的故障导致了很多应用阻塞在停顿事务所持有的锁上）。而现实情况是，有许多协调者的实现默认情况下并非高可用，或者只支持最基本的复制。
- 许多服务器端应用程序都倾向于无状态模式（因为更受 HTTP 的青睐)，而所有的持久状态都保存在数据库中，这样应用服务器可以轻松地添加或删除实例。但 是，当协调者就是应用服务器的一部分时，部署方式就发生了根本的变化。突然间，协调者的日志成为可靠系统的重要组成部分，它要求与数据库本身一样重要（需要协调者日志恢复那些有疑问的事务）。这样的应用服务器已经不再是无状态。
共识问题通常形式化描述如下：一个或多个节点可以提议某些值，由共识算法来决定最终值。
在这个描述中，共识算法必须满足以下性质：
- 协商一致性（Uniform agreement）：所有的节点都接受相同的决议。
- 诚实性（Integrity）：所有节点不能反悔，即对一项提议不能有两次决定。
- 合法性（Validity）：如果决定了值 v，则 v 一定是由某个节点所提议的。
- 可终止性（Termination）：节点如果不崩溃则最终一定可以达成决议。
如果不关心容错，那么满足前三个属性很容易：可以强行指定某个节点为 “独裁者”，由它做出所有的决定。但是，如果该节点失败，系统就无法继续做出任何定。其实这就是在两阶段提交时所看到的：如果协调者失败了，那些处于不确定状态的参与者就无从知道下一步该做什么。
==可终止性则引入了容错的思想。它重点强调一个共识算法不能原地空转，永远不做事情，换句话说，它必须取得实质性进展。即使某些节点出现了故障，其他节点也必须最终做出决定==。可终止性属于一种活性，而另外三种则属于安全性方面的属性。
当然，如果所有的节点都崩溃了，那么无论何种算法都不可能继续做出决定。算法所能够容忍的失败次数和规模都有一定的限制。事实上，可以证明任何共识算法都需要至少大部分节点正确运行才能确保终止性。而这个多数就可以安全地构成 quorum（参阅第 5 章 “读写quorum"）。
因此，可终止性的前提是，发生崩溃或者不可用的节点数必须小于半数节点。即便是多数节点出现了故障或者存在严重的网络问题，现在有很多实现的共识系统也可以满足安全属性：协商一致性、诚实性和合法性。所以大规摸的失效情况可能会导致系统无法处理请求，但不会破坏系统做出无效的决定。
大多数共识算法都假定系统不存在拜占庭式错误。
最著名的容错式共识算法包括 VSRI、Paxos、Raft 和 Zab。这些算法大部分其实并不是直接使用上述的形式化模型（提议并决定某个值，同时满足上面 4 个属性）。相反，他们是决定了一系列值，然后采用全序关系广播算法（参阅本章前面的 “全序关系广播”）。
全序关系广播的要点是，消息按照相同的顺序发送到所有节点，有且只有一次。如果仔细想想，这其实相当于进行了多轮的共识过程：在每一轮，节点提出他们接下来想要发送的消息，然后决定下一个消息的全局顺序。
VSR、Raft 和 Zab 都直接采取了全序关系广播，这比重复性的一轮共识只解决一个提议更加高效。而 Paxos 则有对应的优化版本称之为 Multi-Paxos。
第 5 章讨论了主从复制（参阅第 5 章 “主节点与从节点”），所有的写入操作都由主节点负责，并以相同的顺序发送到从节点来保持副本更新。这不就是基本的全序关系广播么？那在主从复制时我们怎么没有考虑共识问题呢？
答案取决于如何选择主节点。如果主节点是由运营人员手动选择和配置的，那基本上就是一个独裁性质的 “一致性算法”：只允许一个节点接受写入（并决定复制日志中的写入顺序），如果该节点发生故障，系统将无法写入，直到操作入员再手动配置新的节点成为主节点。这样的方案也能在实践中很好地发挥作用，但它需要人为干预才能取得进展，不满足共识的可终止性。
一些数据库支持自动选举主节点和故障切换，通过选举把某个从节点者提升为新的主节点（参阅第 5 章 “处理节点失效”）。这样更接近容错式全序关系广播，从而达成共识。
但是，还有一个问题，我们之前曾讨论过脑裂：所有的节点都需要同意主节点，否则两个主节点会导致数据库出现不一致。因此，我们需要共识算法选出一位主节点。但是，如果这里描述的共识算法实际上是全序关系广播，且全序关系广播很像主从复制，但主从复制现在又需要选举主节点等。
看起来要选举一个新的主节点，我们首先需要有一个主节点。要解决共识，必须先处理共识。怎么摆脱这样一个奇怪的循环？
目前所讨论的所有共识协议在其内部都使用了某种形式的主节点，虽然主节点并不是固定的。相反，他们都采用了一种弱化的保证：协议定义了一个世代编号（epoch number，对应于 Paxos 中的 ballot number，VSP 中 view number，以及 Raft 中的 term number），并保证在每个世代里，主节点是唯一确定的。
如果发现当前的主节点失效，节点就开始一轮投票选举新的主节点。选举会赋予一个单调递增的 epoch 号。如果出现了两个不同的主节点对应于不同 epoch 号码（例如，上一个 epoch 号码的主节点其实并没有真正挂掉），则具有更高 epoch 号码的主节点将获胜。
在主节点做出任何决定之前，它必须首先检查是否存在比它更高的 epoch 号码，否则就会产生冲突的决定。主节点如何知道它是否已被其他节点所取代了呢？还记得上一章 “真理由多数决定” 么？节点不能依靠自己所掌握的信息来决策，例如自认为是主节点并不代表其他节点都接受了它的 “自认为“。
相反，它必须从 quorum 节点中收集投票（参阅第 5 章 “读写 quorum”）。主节点如果想要做出某个决定，须将提议发送给其他所有节点，等待 quorum 节点的响应。quorum 通常（但不总是）由多数节点组成。并且，只有当没有发现更高 epoch 主节点存在时，节点才会对当前的提议（带有 epoch 号码）进行投票。
因此，这里面实际存在两轮不同的投票：首先是投票决定谁是主节点，然后是对主节点的提议进行投票。其中的关键一点是，参与两轮的 quorum 必须有重叠：如果某个提议获得通过，那么其中参与投票的节点中必须至少有一个也参加了最近一次的主节点选举。换言之，如果在针对提议的投票中没有出现更高 epoch 号码，那么可以得出这样的结论：因为没有发生更高 epoch 的主节点选举，当前的主节点地位没有改变，所以可以安全地就提议进行投票。
投票过程看起来很像两阶段提交（2PC）。最大的区别是，2PC 的协调者并不是依靠选举产生；另外容错共识算法只需要收到多数节点的投票结果即可通过决议，而 2PC 则要求每个参与者都必须做出 “是” 才能最终通过。此外，共识篇法还定义了恢复过程，出现故障之后，通过该过程节点可以选举出新的主节点然后进入一致的状态，确保总是能够满足安全属性。所有这些差异之处都是确保共识算法正确性和容错性的关键。
- 在达成一致性决议之前，节点投票的过程是一个同步复制过程。
- 共识体系需要严格的多数节点才能运行。 如果由于网络故障切断了节点之间的连接，则只有多数节点所在的分区可以继续工作，剩下的少数节点分区则处于事实上的停顿状态（参阅本章前面 “线性化的代价”）。
- 多数共识算法假定一组固定参与投票的节点集，这意味着不能动态添加或删除节点。
- 共识系统通常依靠超时机制来检测节点失效。在网络延迟高度不确定的环境中，特别是那些跨区域分布的系统，经常由于网络延迟的原因，导致节点错误地认为主节点发生了故障。虽然这种误判并不会损害安全属性，但频繁的主节点选举显著降低了性能，系统最终会花费更多的时间和资源在选举主节点上而不是原本的服务任务。
- 共识算法往往对网络问题特别敏感。
ZooKeeper 或 etcd 这样的项目通常称为 “分布式键值存储” 或 “协调与配置服务”。从它们对外提供服务的 API 来看则与数据库非常相像：读取、写入对应 Key 的值，或者遍历 Key。如果他们只是个普通数据库的话，为什么要花大力气实现一个共识算法呢？它们与其他数据库有何不同之处？
ZooKeeper 和 etcd 主要针对保存少量、可完全载入内存的数据（虽然它们最终仍要写入磁盘以支持持久性）而设计，所以不要用它们保存大最的数据。它们通常采用容错的全序广播算法在所有节点上复制这些数据从而实现高可靠。正如之前所讨论的，全序广播主要用来实现数据库复制：每条消息代表的是数据库写请求，然后按照相同的顺序在多个节点上应用写操作，从而达到多副本之间的一致性。
ZooKeeper 的实现其实模仿了 Google 的 Chubby 分布式锁服务，但它不仅实现 “全序广播（因此实现了共识），还提供了其他很多有趣的特性。所有这些特性在构建分布式系统时格外重要：
- 线性化的原子橾作：使用原子比较-设置操作，可以实现加锁服务。
- 橾作全序：ZooKeeper 在实现该功能时，采用了对所有操作执行全局排序，然后为每个操作都赋予一个单调递增的事务 ID (zxid) 和版本号 (cversion)。
- 故障检测：客户端与 ZooKeeper 节点维护一个长期会话，客户端会周期性地与 ZooKeeper 服务节点互相交换心跳信息，以检查对方是否存活。即使连接出现闪断，或者某个 ZooKeeper 节点发生失效，会话仍处于活动状态。但是，如果长时间心跳停止且超过了会话超时设置，ZooKeeper 会声明会话失败。此时，所有该会话持有的锁资源可以配置为自动全部释放（ZooKeeper 称之为 ephemeral nodes 即临时节点）。
- 更改通知：客户端不仅可以读取其他客户端所创建的锁和键值，还可以监视它们的变化。因此，客户端可以知道其他客户端何时加入了集群（基于它写入ZooKeeper 的值）以及客户端是否发生了故障（会话超时导致节点消失）。通过订阅通知机制，客户端不需要频繁地轮询服务即可知道感兴趣对象的变化情况。
在上述特征中，其实只有线性化的原子操作才依赖于共识。然而 ZooKeeper 集成了所有这些功能，在分布式协调服务中发挥了关键作用。
ZooKeeper 和 Chubby 系统非常适合的一个场景是，如果系统有多个流程或服务的实例，并且需求其中的一个实例充当主节点；而如果主节点失效，由其他某个节点来接管。显然，这非常吻合主从复制数据库，此外，它对于作业调度系统（或类似的有状态服务）也非常有用。
还有另一个场景，对于一些分区资源（可以是数据库，消息流，文件存储，分布式 actor system 等），需要决定将哪个分区分配给哪个节点。当有新节点加入集群时，需要将某些现有分区从当前节点迁移到新节点，从而实现负载动态平衡（参阅第 5 章 “分区再平衡”）。而当节点移除或失败时，其他节点还需要接管失败节点。
上述场景中的任务，可以借助 ZooKeeper 中的原子操作，ephemeral nodes 和通知机制来实现。
应用程序最初可能只运行在单节点，之后可能最终扩展到数千节点。试图在如此庞大的集群上进行多数者投票会非常低效。ZooKeeper 通常是在固定数最的节点（通常三到五个）上运行投票，可以非常
高效地支持大量的客户端。因此，ZooKeeper 其实提供了一种将跨节点协调服务（包括共识，操作排序和故障检测）专业外包的方式。
略
略
线性化：使多副本对外看起来好像是单一副本，然后所有操作以原子方式运行，就像一个单线程程序操作变显一样。线性化的概念简单，容易理解，看起来很有吸引力，但它的主要问题在于性能，特别是在网络延迟较大的环境中。
因果关系：因果关系对事件进行了某种排序（根据事件发生的原因-结果依赖关系）。线性化是将所有操作都放在唯一的、全局有序时间线上，而因果性则不同，它为我们提供了一个弱一致性模型：允许存在某些并发事件，所以版本历史是一个包含多个分支与合并的时间线。因果一致性避免了线性化昂贵的协调开销，且对网络延迟的敏感性要低很多。
然而，即使意识到因果顺序（例如采用 Lamport 时间戳），我们发现有时无法在实践中采用这种方式，在 “时间戳排序还不够“一节有这样的例子：确保用户名唯一并拒绝对同一用户名的并发注册请求。如果某个节点要同意请求，则必须以某种方式查询其他节点是否存在竞争请求。这个例子最终引导我们去探究系统的共识问题。
共识意味着就某一项提议，所有节点做出一致的决定，而且决定不可撤销。通过逐一分析，事实证明，多个广泛的问题最终都可以归结为共识，并且彼此等价（这就意味着，如果找到其中一个解决方案，就可以比较容易地将其转换为其他问题的解决方案）。 这些等价的问题包括：
- 可线性化的比较-设置寄存器
- 原子事务提交：数据库需要决定是否提交或中止分布式事务。
- 全序广播：消息系统要决定以何种顺序发送消息。
- 锁与租约：当多个客户端争抢锁或租约时，要决定其中哪一个成功。
- 成员/协调服务：对于失败检测器（例如超时机制），系统要决定节点的存活状态（例如基于会话超时）。
- 唯一性约束：当多个事务在相同的主键上试图并发创建冲突资源时，约束条件要决定哪一个被允许，哪些违反约束因而必须失败。
如果系统只存在一个节点，或者愿意把所有决策功能都委托给某一个节点，那么事情就变得很简单。这和主从复制数据库的情形是一样的，即由主节点负责所有的决策事宜，正因如此，这样的数据库可以提供线性化操作、唯一性约束、完全有序的复制日志等。
然而，如果唯一的主节点发生故障，或者出现网络中断而导致主节点不可达，这样的系统就会陷入停顿状态。有以下三种基本思路来处理这种情况：
- 系统服务停止，并等待主节点恢复。
- 人为介入来选择新的主节点，并重新配置系统使之生效。
- 采用算法来自动选择新的主节点。这需要一个共识算法，我们建议采用那些经过验证的共识系统来确保正确处理各种网络异常。
虽然主从数据库提供了线性化操作，且在写操作粒度级别上并不依赖于共识算法，但它仍然需要共识来维护主节点角色和处理主节点变更情况。因此，某种意义上说，唯一的主节点只是其中的一步，系统在其他环节依然需要共识（虽然不那么的频繁）。好在容错算法与共识的系统可以共存，我们在本章做了简要地介绍。
ZooKeeper 等工具以一种类似外包方式为应用提供了重要的共识服务、故障检测和成员服务等。
尽管如此, 并不是每个系统都需要共识。例如无主复制和多主复制复制系统通常并不支持全局共识。正因如此，这些系统可能会发生冲突，但或许也可以接受或者寻找其他方案，例如没有线性化保证时，就需要努力处理好数据多个冲突分支以及版本合并等。