在分布式计算领域，共识问题是最重要而基础的问题。从表面上看含义很直接：可以粗略的理解为多个节点就某件事达成共识。乍看起来，你会觉得，这有什么难的？但不幸的是，很多系统都因为低估了共识算法的实现难度而问题百出。
尽管共识问题非常之重要，但在本书中直到现在才才被提及，似乎有点晚了。这是因为这个主题实在是太艰深了，而欣赏其精妙需要非常多的前置知识。即使在学术界，对共识问题的研究也是历经数十年坎坷才逐渐有了一些沉淀。在本书里，我们在第五章铺垫了冗余（replication），在第七章铺陈了事务，在第八章探讨了分布式系统的系统模型，在本章又讨论了线性一致性和全序广播，到现在，我们终于做足了准备来好好谈谈共识问题了。
在很多场景下让多个节点达成共识是非常重要的。比如：
- Leader 选举在使用单主模型的数据库中，所有节点需要对谁是主节点达成一致。当网络问题导致有些节点不能正常通信时，领导权就会出现争议。在这种情形下，共识对于避免错误的故障转移非常重要。引入如果出现两个领导者可以同时接受写入（脑裂），所有副本上的数据就会产生分叉，从而变得不一致甚而数据丢失。
- 原子提交在一个横跨多节点或具有多分区的数据库中，可能会出现某个事务在一些节点执行成功，但在另外一些节点却运行失败。如果我们想保持事务的原子性（ACID 中的 A，参见原子性），我们就必须让所有节点就事务的结果达成一致：要么全部回滚（只要有故障），要么提交（没有任何故障）。这个共识的特例也被称为原子提交（atomic commit）。
共识的不可能性。你也许听过 FLP —— 以 Fischer，Lynch 和 Paterson 三位作者姓名首字母命名的一种不可能原理——在网络可靠，但允许节点宕机（即便只有一个）的异步模型系统中，不存在总是能够达成共识的算法。在分布式系统中，我们又必须得假设节点可能会宕机，因此稳定可靠的共识算法是不存在的。但是，我们现在却在探讨可以达成共识的算法。这又是为啥？这可能吗？
答案是，FLP 不可能是基于异步系统模型（参见系统模型和现实）证明的，这是一种非常苛刻的模型，不能够使用任何时钟系统和超时检测。如果允许使用超时宕机检测、或者任何可以识别节点宕机的方法，就能够实现可靠的共识算法。甚而，只让算法用随机数来进行故障检测，也能够绕过这个不可能定理。
因此，尽管在理论上，FLP 定理非常重要，断言异步网络中共识不可能达到；但在实践中，分布式系统达成共识是可行的。
在本小节，我们首先会详细探讨原子提交。特别的，我们将会讨论两阶段提交（2PC，two-phase commit）算法，这是一种解决原子提交的最为常见的算法，很多数据库和服务端应用都实现了该算法。可以看出，2PC 在某种程度上是一种共识协议——虽然不是很完美。
在学习完 2PC 之后，我们将会转向更完善的共识算法，比如 Zookeeper 中用的 Zab 算法和 etcd 中用的 Raft 算法。
原子提交和两阶段提交
在第七章我们探讨过，在多个写操作中途出现故障时，原子性能够对应用层提供一种简单的语义。事务结果是要么成功提交（事务的全部写入都成功持久化），要么全部丢弃（事务的所有写入都被回滚，即取消或者扔掉）。
原子性能够避免失败的事务通过半完成（half-finished）或者半更新（half-updated）的结果来破坏数据库系统。这一点对于多对象事务（参见单对象和多对象操作）和支持二级索引的数据库来说尤为重要。二级索引是独立于原始数据的一种数据结构，因此如果你更新了原始数据，对应的二级索引也需要进行同步更新。原子性能够保证二级索引和原始数据时刻保持一致。（如果索引不和原始数据保持同步更新，那该索引就失去了其作用）
从单机到分布式的原子提交
对于运行在单机数据上的事务，原子提交通常由存储引擎层来实现。当客户端请求数据库节点提交事务时，数据库会首先将事务所涉及到的写入进行持久化（通常通过写前日志 WAL 的方式，参见让 B 树更可靠），事务结束时在硬盘上追加一个特殊的提交记录（commit record）到日志上。如果数据库在处理事务的过程中宕机了，在重启时会从日志上对事务进行恢复：
- 如果在宕机前，提交记录已经追加到磁盘上，则该事务被认为已经成功提交。
- 否则，该事务所有的写入将会被回滚。
因此，在单机数据库里，事务是否提交主要取决于数据持久化到磁盘的顺序：首先是数据，接着是提交记录。提交事务还是中止事务，决定性时刻在于提交记录成功刷盘的那一瞬间：在此之前，事务可能会被中止（由于宕机）；在此之后，该事务一定会被提交（即使宕机）。也即，是唯一的硬件设备（某个特定节点上的某个具体的磁盘驱动）保证了提交的原子性。
然而，当事务涉及到多个节点时又当如何？例如，一个跨分区的多对象事务，或者基于关键词分区的二级索引（在该情况下，索引数据和基础数据可能不在一个分区里，参见分片和次级索引）。大多数“NoSQL”分布式存储不支持这种跨节点的分布式事务，但很多分布式关系型数据库则支持。
在上述场景中，只是简单地在提交事务时给每个节点发送提交请求让其提交事务，是不能够满足事务基本要求的。这是因为，可能有的节点成功提交了，有的节点却提交失败了，从而违反了原子性保证：
- 有些节点在提交时检测到完整性约束被破坏了，因此中止事务；但另外一些节点却能够成功提交。
- 有些提交请求由于网络过慢而超时丢弃，另外一些提交请求却成功抵达。
- 有一些节点在写入提交记录前宕机重启，导致事务回滚；另外一些节点却成功提交。
如果有些节点提交了该事务，但另外的一些节点却中止该事务了，多个节点间就会处于不一致的状态。而且，一旦事务在一个节点上提交了（即便之后发现了该事务在其他节点上失败了）就难以进行撤销。由于这个原因，我们需要仅在确信所有相关节点都能成功提交时，本节点才能提交。
事务提交后是不可撤销的——在事务提交后，你不能再改变主意说，我要重新中止这个事务。这是因为，一旦事务提交了，就会对其他事务可见，从而可能让其他事务依赖于该事务的结果做出一些新的决策；这个原则构成了读已提交（read commited）隔离级别的基础（参见读已提交）。如果事务允许在提交后中止，其他已经读取了该事务结果的事务也会失效，从而引起事务的级联中止。
当然，事务所造成的结果在事实上是可以被撤销的，比如，通过补偿事务（_compensating transaction_）。但，从数据库的视角来看，这就是另外一个事务了；而跨事务的正确性，需要应用层自己来保证。
两阶段提交简介
两阶段提交（2PC，two-phase commit）是一种在多个节点上实现原子事务的算法——即，保证所有节点要么都提交，要么都中止。这是数据库中一个经典的算法。2PC 算法会在某些数据库内部使用，有时也会以 XA 事务（支持 Java 事务 API）或者 SOAP Web 服务原子事务形式，供应用层使用。
2PC 基本流程如下图所示。相比单机事务的一次提交请求，2PC 中的提交、中止过程被拆分成了两个阶段（即名字由来）。
一次成功执行的两阶段提交
不要混淆 2PC 和 2PL。Two-phase commit (2PC) 和 two-phase locking (2PL，参见两阶段锁) 是两个完全不同的概念。2PC 是为了在分布式系统中进行原子提交，而 2PL 是为了进行事务并发控制的一种加锁方式。为了避免歧义，可以忽略他们在名字简写上的相似性，而把它们当成完全不同的概念。
2PC 引入了一个单机事务中没有的角色：协调者（coordinator，有时也被称为事务管理器，transaction manager）。协调者通常以库的形式出现，并会嵌入到请求事务的应用进程中，但当然，它也可以以单独进程或者服务的形式出现。比如说，Narayana, JOTM, BTM, or MSDTC.
和单机事务一样，2PC 事务通常也由应用层对多个节点上的数据读写开始。和协调者相对，我们将这些数据节点称为事务的参与者（participants）。当应用层准备好提交后，协调者开始阶段一：向每个参与者发送 prepare 请求，询问他们是否能够提交。然后，协调者会根据参与者的返回而进行下一步动作：
- 如果所有参与者都回复“可以”（yes），表示能够提交，则协调者就会进入第二阶段发出提交（ commit ）请求，此时，提交事实上才开始执行。
- 如果有任何参与者回复“不行”（no），或者请求超时了，协调者就会进入第二阶段并发送一个 中止（abort）请求，中止事务。
这个过程在某种程度上很像西方文化中的结婚仪式：牧师会分别问新娘、新郎是否愿意与对方结婚，通常，双方都会回答“我愿意”（I do）。当牧师收到双方肯定的回答后，就会宣布他们结为夫妇：即事务提交，并将这个令人高兴的事实传达给所有宾客。如果新娘、新郎有任何一方回答否，则仪式中止。
基于承诺的系统
从上面的简要描述中，我们可能很难想通为什么两阶段提交能够保证原子性？而多个节点的单阶段提交就做不到这一点。毕竟，虽然是两阶段，但是两阶段中的任何一个请求都有可能在网络中丢失。让 2PC 能够保证原子性的核心原因到底是什么？
为了理解它的工作原理，我们把 2PC 各个阶段拆得更细一些：
- 当应用想开启一个分布式事务时，它会首先向协调者要一个事务 ID。该事务 ID 是全局唯一的。
- 应用会使用前述事务 ID 向所有的参与者发起一个单机事务，所有节点会各自完成读写请求，在此过程中，如果有任何出错（比如节点宕机或者请求超时），协调者或者任意参与者都可以中止事务。
- 当应用层准备好提交事务时，协调者会向所有参与者发送准备提交（prepare）请求，并在请求中打上事务 ID 标记。如果有请求失败或者超时，则协调者会对所有参与者发送带有该事务 ID 的中止请求。
- 当参与者收到准备提交请求时，它必须确认该事务能够在任何情况下都能被提交，才能回复“可以”。这包括，将所有写入刷到磁盘（一旦承诺了，就不能反悔，即使之后遇到宕机、断电或者磁盘空间不足）、检查是否有冲突或者违反约束的情况。换句话说，如果回复“可以”，意味着参与者让渡了中止事务的权利（给协调者），但此时并没有真正地提交。
- 当协调者收到所有参与者准备提交的回复后，会决定提交还是中止该事务（只有在所有参与者都回复“可以”时，才会提交）。协调者需要将该决策写入事务日志，并下刷到磁盘，以保证即使宕机重启，该决策也不会丢失。这被称为提交点（commit point）。
- 协调者将决策刷入了磁盘后，就会将决策（提交或者中止）请求发给所有参与方。如果某个请求失败或者超时，则协调者会对其进行无限重试，直到成功。不允许走回头路：如果协调者决定了提交，则不管要进行多少次的重试，也必须要保证该决策的执行。如果参与者在此时宕机了，则当重启时也必须进行提交——因为它承诺过要提交，因此在重启后不能拒绝提交。
因此，该协议有两个重要的“不可回退点”：
- 当某个参与者回复“可以”时，就做出了（将来无论发生什么）肯定可以提交的承诺。（当然，协调者可以中止事务）
- 当协调者决定提交时，该决定一旦做出（写入磁盘），就是不可撤回的。
这两个承诺保证了 2PC 的原子性（其实单机事务是将上述两个事件合二为一：将提交记录写入事务日志即代表提交）。
说回婚礼的比喻，在说“我愿意”之前，双方都有说“没门”（或者任何相当言论）来中止事务的自由。然而，一旦承诺“我愿意”，就不能收回该承诺。即使你在说出“我愿意”之后昏倒过去，哪怕没有听到牧师说“你们现在已结为夫妻”，也不影响对应事务已经提交的事实。当你之后恢复意识时，可以凭借事务 ID 向牧师询问你们的婚姻状态，或者简单的等待牧师下一次重试的提交请求（重试会在你昏迷期间一直进行）。
协调者故障
我们已经讨论了在 2PC 中如果任何一个参与者（participant）或者网络故障时的系统行为：
- 如果任意准备提交（prepare）请求失败，则协调者中止事务。
- 如果任意提交（commit）或者中止（abort）请求失败，则协调者会进行无限重试。
然而，我们还没有讨论，当协调者故障（coordinator failure）时，系统应当如何应对。
如果协调者在准备提交请求发送前故障，则参与者可以放心的中止事务。然而，一旦参与者收到准备提交请求，并且回复“可以”，则根据 2PC 设定，它不能单方面的中止事务——而必须等待协调者的提交或者中止请求。如果此时协调者宕机或者网络故障，则参与者只能死等。参与者事务的这种状态称为存疑（in doubt）或者未定（uncertain）。
图 9-10 就是一个这样的例子。在该例子中，系统处于第二阶段，协调者准备提交，并且数据库实例 2 收到了提交请求。此时，协调者宕机，还没来得及给数据库实例 1 发送提交请求，因此该实例不知道是要提交还是中止事务。超时机制在这里并不能解决问题：超时后，如果数据库实例 1 单方面决定中止事务，则会和数据库实例 2 处于不一致的状态。类似的，单方面提交事务也不靠谱，毕竟另外的参与者也可能收到请求并中止了事务。
第一阶段后协调者故障
在未收到协调者的消息前，参与者无从得知是要提交还是中止。原则上，参与者之间可以互相沟通以确定该如何进行下一步，并最终达到一致，但这已经超脱了 2PC 协议范畴。
在 2PC 中，唯一使算法能够完成的方法就是等待协调者恢复。这也是为什么，协调者在给参与者发送提交或者中止消息时，需要先将该决策写入事务日志中：当协调者恢复时，他就能从事务日志中读取该决策，以让所有处于未决状态的参与者状态确定下来。如果协调者恢复了，发现并没有写入任何决策到事务日志中，则中止该事务。因此，2PC 的提交点（commit point）最终可以归结到协调者上的单机原子提交。
参考资料
[1]
DDIA 读书分享会: https://ddia.qtmuniao.com/
题图故事
秋日碎金
