技术分享
分布式的共识：原子提交和两阶段提交
在分布式计算领域，共识问题是最重要而基础的问题。从表面上看含义很直接：可以粗略的理解为多个节点就某件事达成共识。乍看起来，你会觉得，这有什么难的？但不幸的是，很多系统都因为低估了共识算法的实现难度而问题百出。
尽管共识问题非常之重要，但在本书中直到现在才才被提及，似乎有点晚了。这是因为这个主题实在是太艰深了，而欣赏其精妙需要非常多的前置知识。即使在学术界，对共识问题的研究也是历经数十年坎坷才逐渐有了一些沉淀。在本书里，之前09.01 发布的《分布式数据之多副本的主从模型选择》🔗 铺垫了冗余（replication），在 09.15 发布的《分布式系统中的事务之那些棘手的概念们》🔗 铺陈了事务，在 10.27 开始连载的《分布式系统中的麻烦事（上）：系统故障，以及不可靠的网络》🔗 探讨了分布式系统的系统模型，在 11.17 开始发布的《什么是分布式系统中的一致性？》🔗 又讨论了线性一致性和全序广播，到现在，我们终于做足了准备来好好谈谈共识问题了。
在很多场景下让多个节点达成共识是非常重要的。比如：
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）最终可以归结到协调者上的单机原子提交。
三阶段提交
由于 2PC 在等待协调者宕机恢复时系统可能会卡住，因此两阶段提交又称为阻塞式原子提交协议（blocking atomic commit protocol）。理论上，可以让使用某种办法让原子提交协议成为非阻塞的，从而在协调者宕机时，系统不会卡住。然而，在实践中该办法很不直观。 作为 2PC 的替代，人们又提出了三阶段提交（three-phase commit）。然而，3PC 对系统有一定假设：网络具有有界延迟，请求延迟也是有界的（bounded，参见超时和无界延迟 🔗）。在具有无界网络延迟进程停顿的实际系统中，3PC 无法保证原子性。 一般来说，非阻塞的原子提交依赖于一个完美的故障检测器（perfect failure detector）——即，一种可以判断某个节点是否宕机的可靠机制。在具有无界延迟的网络中，超时机制就不是一个可靠的故障检测方法，即使没有任何节点故障，一个请求仍会由于网络问题而超时。出于这个原因，即使 2PC 可能会因为协调者宕机卡住，但人们仍然在使用它，而没有转向 3PC。
实践中的分布式事务
分布式事务，尤其是使用两阶段提交实现的分布式事务，毁誉参半。一方面，他们可以提供其他方式难以实现的安全保证；另一方面，由于运维复杂、降低性能、承诺过多，他们广受诟病。为了避免分布式事务带来的运维复杂度，很多云服务选择不支持分布式事务。
很多分布式事务的实现会带来严重的性能下降——如 MySQL 中的分布式事务据说比单机事务慢一个数量级，也无怪乎人们建议不要用。两阶段提交的很多性能损耗是算法内生的：
处理协调者宕机恢复所需要的额外刷盘（fsync）
协调者和参与者额外的网络往返开销
相较于完全弃之不用，我们应当更加细致的考量分布式事务，因为可以从其中学到相当多的经验教训。首先，我们需要精确地定义什么是“分布式事务”。有两种完全不同的分布式事务经常被混淆：
数据库内部分布式事务：在一些分布式数据中（标配支持多分区和多副本的数据库），支持跨节点的内部分布式事务。如，VoltDB 和 MySQL 集群的 NDB 存储引擎就有这样的内部事务支持。在这种情况下，所有事务参与节点都运行着同样的二进制代码。
异构的分布式事务：在异构的分布式事务中，所有参与者使用了两种以上的技术栈：如，来自不同厂家的两种数据库实例，甚至可能包含非数据库系统，如消息队列。即使每个子系统内部实现完全不同，构建于其上的分布式事务也能够保证原子提交。
数据库内部的事务不需要考虑和其他系统的相容性，因此在实现时可以使用任何协议、可以针对特定技术栈进行任何优化。因此，数据库内部的分布式事务通常能够很好地工作。相反，横跨多个异构系统的事务实现则充满了挑战。
恰好一次的消息
异构的分布式事务系统可以将多种异构的系统，以强大的方式进行整合。例如，当且仅当数据库中处理消息的事务成功提交时，消息队列才会将该消息标记为已处理。可以将消息确认和数据库写入打包在单个事务里进行原子提交，来实现上述行为。在分布式事务的加持下，即使消息队列和数据库是跑在不同机器上的不同技术栈的进程，上述目标也能实现。
如果消息投递或数据库事务任意一方出错，两者都会被中止。据此，消息队列可以在之后安全地重新投递该消息。通过将消息投递和消息处理打包进行原子地提交，不管成功之前重试多少次，我们都可以保证该消息只被有效地（effectively）处理恰好一次（exactly once）。中止事务时，会丢弃所有部分执行的结果。
只有参与系统都支持原子提交时，上述分布式事务才是可行的。例如，假设处理消息的一个副作用是发送邮件，且邮件服务器不支持两阶段提交。则在消息处理失败进行重试的过程中，可能出现邮件被发送多次的现象。但如果，在事务中止时，消息处理的所有副作用都可以回滚，则处理步骤可以像没有任何事情发生过一样，安全地进行重试。
我们在后面会重新探讨对消息进行恰好一次的处理的话题。这里，我们首先看下异构系统上的分布式事务的原子提交协议（atomic commit protocol）。
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 库。
阻塞时持有锁
为什么我们这么关心事务的参与者在未定状态时卡住呢？系统的其他部分不能够无视该未定事务而继续干自己的事情吗？反正该未定事务最终会被处理。
问题的关键点在于存在锁（locking）。在读已提交 🔗一小节中，数据库中的事务通常会使用行级别的互斥锁来保护对某一行的修改，以防止脏写。更进一步，如果想获得可串行化隔离级别，数据库在使用两阶段锁进行实现时，会对事务所有读过的行加共享锁（参见两阶段锁 🔗）。
数据库在提交或者中止事务前不能够释放获取的这些锁。因此，在使用两阶段提交时，一个事务必须在其处于未定状态期间一直持有锁。如果协调者在宕机后花了 20 分钟才重新启动起来，则对应参与者的锁就要持有 20 分钟。如果参与者日志由于某种原因丢掉了，这些锁会被永远的持有——除非系统管理员会手动释放它们。
如果这些锁一直被持有，则其他事务不能够更改这些数据。取决于数据库的实现，有些事务甚至会在读这些行的数据是被阻塞。因此，其他的事务并不能正常的运行——如果他们要访问这些上锁的数据，就会被阻塞。这会造成应用的大部分功能不可用，直到未定事务被解决。
从协调者故障中恢复
理论上来说，如果协调者宕机重启后，就能够从日志读取之前决策，从而处理还在存疑的参与者事务。然而，在实践中，常会产生一些孤立的（orphaned）未定事务——即，由于某种原因，事务的协调者（比如由于软件 bug 事务日志丢失或者损坏）无从判断事务的最终结果是提交还是回滚。由是，这些事务不能够被自动的处理，从而永久的卡在那里，持有锁并且阻塞其他事务。
即使重启数据库服务器也不能让其从卡住中恢复，在一个正确实现的 2PC 系统中，参与者在重启后必须仍然持有事务相关锁（否则就会违反其承诺，进而原子性保证），这是一种非常棘手的情况。
唯一的出路是让管理员手动的来提交或者中止事务。管理员首先需要检查所有包含未定事务的参与者，看是否有任何参与者提交或者中止了，从而对其他卡主的参与者手动执行相同操作（通过外力来让所有参与者达成一致）。解决该问题需要大量手工操作，并且在线上环境中断服务的巨大压力和时间限制下（不然，为什么协调者会处在此种错误状态下？）。
很多 XA 事务的实现会留有紧急后门，称为启发式决策（heuristic decisions）：允许一个参与者不用等待协调者的决策，而单方面决定中止还是提交一个未定事务。需要说明的是，这里的启发式仅仅是可能打破原子性（probably breaking atomicity）的一种委婉说法。因为这么做可能会违反两阶段提交所提供的保证。因此这种启发式决策仅是为了救急，而不能进行日常使用。
分布式事务的限制
XA 事务解决了一些很现实而重要的难题：让异构的数据系统保持一致。但正如所见，它也引入了一些重大的运维难点。具体来说，引入这些难点的核心原因在于——从某种角度看，事务的协调者也是一个“数据库”（事务决策结果得存在里面）。因此，也需要像其他数据库一样小心谨慎地进行对待：
如果协调者没有使用多副本机制，仅运行在一台机器上，则它会成为系统的一个单点（因为它的宕机会造成存疑的参与者，进而阻塞其他应用服务的继续运行）。然而，令人惊讶的是，很多协调者的实现要么默认不是高可用的，要么只提供了很粗糙的冗余支持。
很多服务端应用本身被设计为无状态的（stateless，HTTP 比较偏好无状态，如 Restful 设计风格）的，然后将状态都外存到数据库中。这样做的好处是，应用侧进程可以随意增删，按需扩展和收缩。但如果事务的协调者成为了应用层的一部分，就改变了这个本质设定。协调者的日志变成了应用层一个至关重要的、需要持久化的状态——需要像数据库一样按同等重要性对待。因为在宕机重启后，参与者会利用这些日志来推进卡住的参与者。由是，应用层不再是无状态的。
由于 XA 需要和足够广泛的数据系统进行适配，因此其 API 只能维持一个最小公共接口集，由此带来了 XA 在能力上的诸多限制。如，XA 不能在跨系统检测死锁，因为这要求增加一种可以获取所有正在等待的锁信息接口（需要使用 Wait-For-Graph 死锁检测）；XA 也不能提供跨系统的 SSI 隔离级别（参见可串行的快照隔离 🔗），因为这要求支持一种可以跨系统监测冲突的协议（SSI 要在 SI 的基础上进行读写冲突检测）。
对于数据库的内部分布式事务（非 XA），就没有这些限制——例如，可以提供分布式版本的 SSI。然而，要成功地提交一个 2PC 事务仍有诸多问题：所有的参与者必须要回复（但可以异步回应）。因此，一旦系统内任何子模块损坏了，则事务也随之失败。从这个角度来说，分布式事务有放大故障的嫌疑，这与我们构建容错系统的目标背道而驰（这就是 tradeoff，为上层提供的更多的一致性保证，就会牺牲性能，降低可用性）。
上述事实是否意味着我们应该放弃让不同系统保持一致的努力？不尽然，有很多其他方法，既可以让我们达到同样的目标，而又不必引入异构分布式事务的痛点。我们在后面会回到对这个问题的讨论。现在让我们先把共识问题这个主题讲完。
容错的共识算法
通俗来说，共识（consensus）意味着让多个节点就某件事情达成一致。比如说，如果多个人同时抢某次航班的最后一张票、预定剧院里的同一个座位或者使用同一个用户名注册账号，则可以使用共识协议来判断这些互斥的操作中，谁是真正的赢家（这其实利用了之前提到的可线性化）。
形式化一些，共识协议通常被描述为：一个或者多个节点可能会各自提议（propose）一些值，共识协议需要在这些值中间做出唯一的决策（decide）。在预定座位的例子中，当多个客户试图并发地获取最后一个座位时，每个处理用户请求的节点会提议一个其所处理的用户 ID，然后最终决策对应着哪个用户会得到该作为。
在这种形式化表述中，一个共识协议必须满足以下条件：
全局一致性（Uniform agreement） 没有任何两个节点最终做出不同决策。
正直性（Integrity） 没有任何节点会做出两次决策（不会反复横跳）
有效性（Validity） 如果一个节点做出了决策，该决策所对应的值一定来自系统内某个节点的提议
可终止性（Termination） 任何没有宕机的节点，最终都会给出对某个值的决策
全局一致和正直性定义了共识协议的核心概念：所有节点都要决策出同样的结果，并且一旦做出决策，就不能反悔。加入有效性更多的是为了排除一些无效（trivial）结果：如果无论其他节点提议什么，一个算法都会选择 null 作为决策值；该算法虽然满足一致性和正直性约束，但却不满足有效性。
如果不关心容错性，则仅满足前三个性质就足够了：比如，可以通过硬编码指定某个节点为“独裁者”，并且让其做所有决策，其他节点只要服从即可。然而，一旦该节点故障，则整个系统不能继续决策和推进。事实上，这正是我们在两阶段提交算法中看到的：一旦协调者故障，所有处于未定状态的参与者都无法独自决策是提交还是中止。
可终止性是对容错的一种形式化描述（从结果来描述）。它本质上是在说，一个共识算法不能让系统陷入一种卡在那、啥也不干，直到永远的状态。换句话说，系统必须能够正常运作，即使有些节点宕机，其他节点也必须能够继续做出决策。（可结束性是存活性，liveness，而其他三个性质是安全性，safety，参见安全性和存活性 🔗）。
该模型对节点宕机做了最坏的假设——一旦节点宕机，就会凭空消失，再也不会回来。适用于该模型的场景不是软件故障造成的宕机，而是由火山喷发、地震等造成的数据中心不可逆转的损坏。在该系统模型下，任何需要等待节点回复的算法都不可能满足可终止性。具体来说，在这种设定下，2PC 就不满足可结束性要求。
当然，如果所有节点都宕机，则任何算法都不可能做出任何决策。共识算法有其能够承受的宕机节点数上限：事实上，可以证明，任何共识算法都要求多数节点存活，以确保正常运行，满足可终止性。多数派节点可以安全的构成一个法定多数（quorum，参见 Quorum 读写 🔗）。
因此，可终止性受限于少于半数节点宕机或不可达的假设。然而，大多数共识算法的实现在大多数节点都宕机或者网络出现大范围故障时仍然能保持安全性——一致性，正直性和有效性。也即，大范围的节点下线可能会让系统不能继续处理请求，但不会因此破坏共识协议，让其做出不合法决策。
大多数共识算法会假设系统中不存在拜占庭故障（参见拜占庭错误 🔗）。即如果某些节点故意不遵守协议（例如，对不同节点返回完全不同的信息），就有可能破坏协议的安全性。当然，我们也有办法让系统足够鲁棒以容忍拜占庭错误，但就得要求集群中不能有超过三分之一的恶意节点（具有拜占庭错误的节点），但本书中没有足够精力来详细讨论这种算法的细节了。
全序广播中的共识算法
最广为人知的容错性的共识算法有——VSR（Viewstamped Replication）、Paxos、Raft 和 Zab。这些共识算法间有非常多的共同点，但他们确实不完全相同（虽然 Lamport 说过类似，世界上只有一种共识算法——Paxos）。在本书中我们不会探究每个共识算法的区别的所有细节：只需知道他们在顶层设计中有很多相似之处即可。除非，你想自己实现一个共识算法。
“当然，并不推荐这么做，因为实现一个工业级可用的共识算法很难，需要处理特别多的边角情况，而这些情况不经过大量实践是根本不会想到的。虽然 TLA 可以验证你的算法，但并不能验证你的实现。”
这些共识算法通常不会直接按上述形式化的定义（如提议并在单值上进行决策，同时满足一致性、正直性，有效性和可终止性）来实现。转而，他们通常会在一系列值上做出决策，从而事实上变成一种全序广播算法，上文 🔗前面小节讨论过这个问题。
全序广播等价于多轮次的共识协议（每个轮次，会使用共识协议对全序广播中的一条消息的全局顺序做出决策）：
由于共识协议的全局一致性，所有节点会以同样的顺序投递同样的消息。
由于正直性，具有同样 id 的消息不会重复。
由于有效性，消息不会是损坏的，也不会是凭空捏造的。
由于可终止性，消息不会丢失。
VSR，Raft 和 Zab 都直接实现了全序广播，相对多次使用共识算法，每次就单个只达成一致，这种方法要更高效。对于 Paxos，其全序广播版本是 Multi-Paxos。
单主复制和共识协议
在前面，我们讨论了基于单主模型的复制协议（参见领导者与跟随者 🔗），在该模型中，主节点会接管所有写入，并且以同样的顺序复制给从节点，以此保持所有副本的数据一致。这本质上不也是全序广播么？为什么我们在第五章不需要考虑共识问题呢？
该问题的核心点在于主节点（领导者）是怎样选出的。如果主节点由运维团队的管理员手动配置，你本质上就获得了一个“共识算法”的独裁变种：只有一个节点允许接受写入（决定复制日志中所有日志的顺序），并且一旦该主节点宕机，系统便会陷入不可用的状态，直到运维人员手动的配置另外一个节点为主节点。这样的系统在实践中也可以正常运作，但是并不满足共识算法中的可终止性，因为它在停顿后要求运维人员的干预，才能继续运转。
有些数据库在遇到主节点故障时，会自动地重新进行主选举，将一个从节点提升为新的主节点（参见宕机处理 🔗）。这就让我们进一步逼近了可容错的全序广播，并且解决了共识问题。
但，这中间有个循环依赖的问题。我们之前讨论了脑裂（split brain）问题，并且断言所有的节点必须就谁是领导者达成一致——否则，如果有两个不同节点都认为自己是领导者，则会有多个写入点，进而让数据库陷入不一致的状态。因此，我们需要共识算法来进行选主。但我们说共识算法本质上可以描述为全序广播算法，然后全序广播算法又和单主复制一样，然后单主复制又依赖时刻保证单个主，然后…
看起来，为了选出单个主节点，我们首先需要一个主节点；为了解决共识问题，我们首先要有一个共识算法；我们如何打破这个循环依赖呢？
纪元编号和法定人数
到目前为止所提到的共识算法都在内部需要一个某种形式上的主节点，但都不能保证主节点是唯一的。但，他们可以给出一个稍弱的保证：协议会定义一个纪元编号（epoch number；在 Paxos 中称为投票编号，ballot number；在 Viewstamp Replication 中称为视图编号，view number；在 Raft 中称为任期编号，term number），并且保证在每一个纪元（epoch）内，主节点是唯一的。
每次当前的主节点被认为下线时（可能是宕机，也可能只是网络不通），所有认为该主下线的节点就会发起选举，以选出新的主节点。每次选举会使用一个更高的纪元编号，因此所有的纪元编号是全序且单调递增的。如果不同纪元中有两个节点都认为自己是主（比如之前的主节点并没有宕机），则具有较高纪元编号的主节点胜出。
在一个主节点被授权做任何事之前，它必须要确认不会有更权威的主节点（具有更高的纪元编号）会做出不同决策。那该一个主节点如何知道自己没有被其他节点“赶下台”呢？会议一下，我们在真相由多数派定义 🔗 一节中讨论过的：分布式系统中，一个节点不能无脑相信自己的判断——因为一个节点认为自己是主，不意味着其他节点也都认可这一点。
因此，主节点在决策前需要首先从所有节点获得法定票数（参见 Quorum 读写 🔗）。对于每个决策，主节点都必须将其作为提案发给其他所有节点，并且等待法定节点的同意。法定节点通常来说，会包含多数派节点，但也不绝对（Flexible Paxos 介绍了一种不需要多数节点的放宽的 Paxos 算法）。如果法定节点的回复中没有任何更高纪元的，则当前主节点可以放心的认为没有发生新纪元的主选举，并可以据此认为他仍然“握有领导权”。从而，可以安全的对提案进行决策。
该投票过程非常像两阶段提交提交算法。最大的区别在于：
2PC 中的协调者不是被选出来的。
2PC 要求每一个参与者都回复“可以”，而可容错的共识算法只要求多数节点的投票。
此外，共识算法在新领导者上台时，针对数据不一致的节点，还设计了一套恢复策略。这些不同点是共识算法能够保证正确性和容错性的核心设计。
共识算法的局限性
共识算法对于分布式系统是一个划时代的突破：他们能够在不确定的环境里保证安全性（一致性、正直性和有效性），在此基础上还能够进行容错（只要大多数节点还活着就能正常运转）。他们还实现了全序广播，因此能够用来实现容错的线性一致的系统。
然而，共识算法并非银弹，因为这些收益都是有代价的。
同步复制损失性能。每次进行决策（更改数据）前都要让多数节点进行投票，意味着这是一个同步复制系统。在同步复制和异步复制 🔗 一节中我们讲过，很多数据库都会配置为异步复制。在这种配置下，有些已经提交的数据在进行恢复时可能会丢失，但很多人仍然选择这种模式——承担这种风险，以换取更好的性能。
多数派会增加系统冗余。共识系统总是要求有严格多数节点存活才能正常运行。这意味着，如果你要容忍单节点故障就至少需要三个节点（三节点中的两个节点可以组成多数派），如果要容忍两个节点故障就至少需要五个节点（五个节点中的三个节点组成多数派）。如果网络故障切断了其中一些节点和其他节点的联系，则只有连通的多数派节点可以正常运行，其他节点都会被阻塞。
动态成员变更复杂。很多共识算法会假定有固定的数目节点参与投票，这意味着你不能往集群中增删节点。共识算法的动态成员变更（dynamic membership）扩展允许集群的节点集随时间推移而发生变动，但相对于静态成员算法，这种扩展版本非常难以理解。
复杂网络环境性能很差。共识系统通常通过超时机制来对故障节点进行检测。在延迟高度变化的网络中，尤其是多地部署的分布式系统中，某些存活节点由于网络的瞬时抖动常被误认为发生了故障。尽管这些问题并不会破坏安全性，但频繁的领导者选举会导致极差的性能表现——系统可能会大部分时间都在选主而不是正常干活上。
有时，共识算法对网络故障非常敏感。例如，我们发现 Raft 对某些边角情况处理的不尽如人意：如果整个网络都正常运行，只有某个特定的网络连接持续的抖动。Raft 会进行在两个节点间频繁切主，或者当前主节点的领导权被不断挑战，则系统不再能有效的运转，对外提供服务（这里存疑，通过预投票，pre-vote 应该可以解决这个问题）。其他共识算法也有类似的问题，针对不可靠网络设计更为鲁棒的共识算法仍是一个正在持续研究的课题。
成员关系和协调服务
类似于 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）来提供该功能。
故障检测（ephemeral node）：客户端和 ZooKeeper 的服务器间维持着一个长会话，客户端和服务端通过周期性的心跳来检测对端是否仍然存活。即使该连接短暂断掉，或者 ZooKeeper 节点故障，该会话仍然能够存活。但如果，心跳停顿间隔过长，超过了会话的超时阈值，ZooKeeper 会标记该会话死亡。所有该会话关联的锁在超时都将会被释放（ZooKeeper 将其称为暂态节点，ephemeral nodes，这类节点可以将生命周期与会话进行绑定）。
变动通知（watch）：客户端不仅可以读取其他节点创建的锁或者值，也可以直接对这些对象的变化进行守望（watch）。通过守望机制，客户端可以立即发现是否有其他客户端加入集群（通过这些客户端写入 ZooKeeper 的值）、其他客户端是否故障（通过这些客户端注册到 ZooKeeper 中的暂态节点的消失）。通过订阅这些通知，客户端可以避免频繁地去 ZooKeeper 拉取信息，比对以确定是否发生了某些变化。
对于这些功能，只有线性化的原子操作真正需要共识算法。但这些操作的组合，使得类似 ZooKeeper 的系统对分布式系统非常有用。
为节点分配任务
另一种 ZooKeeper/Chubby 非常适用的场景是选主，假设你有多个进程或服务，其中一个被选为领导者或者主服务。如果领导者故障，则另外一个节点需要接管。这不仅对于单主模型的系统非常重要，对于任务调度器或其他类似有状态服务来说，该功能也十分有用。
另一个例子是，你有一些分了片的资源（数据库、消息流、文件存储、分布式的 actor 等等），并且需要决策哪些分片要放到哪些节点上去。当新节点加入集群后，一些分片需要从现有节点挪动到这些新节点上去，以进行负载均衡。当有节点故障或者被移除时，其他的节点需要接管故障节点的负载。
可以通过谨慎的组合使用 ZooKeeper 中的原子操作、暂态节点和通知机制来实现这类任务。如果实现正确，则可以让应用在遇到故障时，无人工干预的情况下自动恢复。即使有很多基于 ZooKeeper 的二次封装库（如 Apache Curator）可以借助，实现正确仍然不容易。但总好过从头实现所需的共识算法，很少有人能够成功的从头实现一个工业可用的共识系统。
刚开始时，一个应用可能会运行在单机上，但最终可能会扩展到上千节点的集群上。在如此多的节点上进行多数票选举会非常低效。相反，ZooKeeper 通常运行在固定节点的集群上（通常是三个或者五个），并且只须在这几个节点间达成共识，然后就可以支持非常多的客户端访问。这样，ZooKeeper 提供了一种可以将部分功能（共识算法、外包定序、故障检测）“外包”（outsouring）给外部服务的方法。
通常来说，ZooKeeper 所管理的数据只会很低频的改变：比如它会维护类似“运行在 10.1.1.23 节点上的服务是分片 7 的领导者”的元信息，这种信息只会在分钟或者小时级的时间尺度上进行改变。这些系统不是为了存储应用运行时的数据，毕竟这些数据可能会以上千甚至上百万 QPS 的速率被修改。如果应用需要将数据从一个节点同步到另外一个节点，则需要使用其他工具（如 Apache 的 BookKeeper，一个类似于日志的存储服务，会将 log 切分并做冗余，Pulsar 的存储层在用）。
服务发现
ZooKeeper，etcd 和 Consul 也会用于服务发现（service discovery）——即根据服务名称找到其对应的 IP 地址以进行连接。在数据中心的环境中，虚拟机的来来去去非常普遍，因此很难事先知道某个服务的 IP 地址。因此，你可以对服务进行配置，让其在启动的时候在某个服务（通常是名字服务器，nameserver）注册自己的地址和端口，其他人就能使用名字来找到该服务的最终地址。
然而，服务发现是否真的需要共识协议暂时存疑。传统上，人们使用 DNS 服务来通过服务名找到其对应 IP 地址。DNS 通常使用多级缓存来获取高性能和高可用性。从 DNS 读取信息肯定不满足线性一致性，而且从 DNS 中偶尔读到过期的结果通常问题不大。相比线性一致性，高可用性和对网络的鲁棒性才是更重要的事情。
尽管服务发现不需要共识协议，但领导者选举需要。因此，如果你的共识系统已经知道领导者是谁，他就可以利用这些信息帮助别的服务来发现谁是领导者。处于这种目的，一些共识系统支持只读的缓存副本（如 Raft 中的 learner）。这些副本从共识协议中异步的接收数据，但并不参与投票。因此可以提供不在意线性一致性的读取。
成员服务
ZooKeeper 及类似服务可以视为成员服务（membership services）研究范畴的一部分，该研究可以上溯到上世纪八十年代，对于构建高可用系统非常重要，如空中交管系统。
成员服务可以确定当前集群中哪些节点当前时存活的。如前面 🔗 所说，在具有无界延迟的网络中，不可能可靠的检测出一个节点是否故障。然而，如果你综合使用故障检测和共识算法，所有节点能够对哪些节点存活这件事达成共识。
使用共识协议也有可能错将一个节点认为下线了，尽管它事实上是存活的。但尽管如此，只要系统能够对当前系统包含哪些节点达成共识，就仍然很有用处。例如，选主算法可以是——在系统当前所有节点中选一个具有最小标号的节点。如果所有节点对系统当前包含哪些节点存在分歧，则这种方法就不能正常工作（不同节点眼中的的最小编号节点可能不一致，从而让大家选出的主不一致）。
