数据密集型应用系统设计-一致性与共识

date

Dec 10, 2021

slug

reading-notes-ddia-consistency-and-consensus

status

Published

一致性保证

最终一致性意味着收敛，即预期所有的副本最终会收敛到相同的值，但这是一个非常弱的保证，它无法确认何时会收敛。

数据库不像单线程程序，数据库看上去像一个可以进行读写的变量，但事实上它内部有无比复杂的更多语义要求。

可线性化（原子一致性、强一致性）

如果数据库能提供只有单个副本的假象，让每个客户端都拥有自己的数据视图，这就是可线性化（原子一致性、强一致性）。思想是让一个系统看起来好像只有一个数据副本，且所有操作都是原子的。

在可线性化系统中，一旦某个客户端成功提交请求，所有客户端的读请求一定都能看到刚刚写入的值。换句话说，可线性化是一种就近的保证。

先看一个非线性化的例子：

Alice 看到了比赛结果，Bob 去查看时发现比赛还没有结束。这就违背了线性化规则。

如何达到线性化？

可线性化背后的基本思想很简单：使系统看上去好像只有一个数据副本。

在一个可线性化的系统中，在写操作的开始与结束之间必定存在某个时间点，x 的值发生了从 0 到 1 的跳变。如果某个客户端的读取返回了新值 1，即使写操作尚未提交，那么所以后续的读取也必须全部返回新值。

线性化的依赖条件

加锁与主节点选举

主从复制的系统需要有且只有一个主节点，否则会产生脑裂。选举新的主节点常见的方法是使用锁：即每个启动的节点都尝试获得锁，其中只有一个可以成功即成为主节点。不管锁具体如何实现，它必须满足可线性化：所有节点都必须同意哪个节点持有锁，否则就会出现问题。

提供协调者服务的系统如 Apache Zookeeper 和 etcd 等通常用来实现分布式锁和主节点选举。他们都使用了支持容错的共识算法确保可线性化。

跨通道的时间依赖

图中保存图片的处理和发送控制消息的处理属于两个不同的通道，导致读取到旧值。

实现线性化系统

系统容错最常见的方法是采用复制机制。回顾之前的复制机制，看是否满足可线性化：

主从复制（部分支持可线性化）

如果在主节点上读取，或者在同步更新的从节点上读取，是满足线性化的。但如果发生主从切换，旧的主一瞬间还在提供服务，可能就会出现读取到旧值的问题。

共识算法（可线性化）

与主从机制类似，不够共识协议通常内置一些措施来防止脑裂和过期的副本。

多主复制（不可线性化）

多主可以在多个节点上并发写入，再异步复制到其他节点，还可能出现数据冲突，所以不满足。

无主复制（可能不可线性化）

线性化的代价

CAP 理论

只要存在不可靠的网络就会有违背线性化的风险：

如果应用要求线性化，但由于网络方面的问题，某些副本与其他副本断开连接之后无法继续处理请求，就必须等待网络修复，或者直接返回错误。无论哪种方式，结果是服务不可用。

如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求例如写操作(多主复制) 。此时，服务可用，但结果行为不符合线性化。

在不可靠的网络前提下，可用性和一致性不能同时保证。

可线性化与网络延迟

虽然线性化是个很有用的保证，但实际上很少有系统真正满足线性化。例如，现代多核 CPU 上的内存甚至就是非线性化，如果某个 CPU 核上运行的线程修改一个内存地址，紧接着另一个 CPU 核上的线程尝试读取，则系统无法保证可以读到刚刚写入的值，除非使用了内存屏障或fence指令。

出现这种现象的原因是每个 CPU 核都有自己独立的 cache 和寄存器。

之所以放弃线性化的原因就是性能，而不是为了容错。

许多分布式数据库也是类似，它们选择不支持线性化是为了提高性能，而不是为了保住容错特性。无论是否发生了网络故障，线性化对性能的影响都是巨大的。

顺序保证

顺序是本书反复出现的主题，某种程度也表明它确实是一个非常重要的基本概念。让我们简要回顾一下本书讨论顺序时涉及的前后上下文：

在第5章，我们看到主从复制系统中主节点的主要作用是确定复制日志中的写入顺序，这样使从节点遵从相同的顺序执行写人。如果没有这样的唯一主节点，则可能由于并发操作而引发冲突(参阅第5章“处理写冲突" )。

第7章中讨论的可串行化则是确保事务的执行结果与按照某种顺序方式执行一样。实现方式可以是严格顺序执行，或者允许并发但需要相应的冲突解决方案(例如加锁或冲突-中止)。

第8章讨论了分布式系统的时间戳与时钟(参阅第8章“依赖于同步的时钟" ) ，试图将顺序引入到无序的操作世界，例如确定两个写操作哪一个先发生。

事实证明，排序、可线性化与共识之间存在着某种深刻的联系。尽管这些概念听起来比本书的其他部分更加理论和抽象，但它对于理解系统能做什么和不能做什么非常有帮助。

顺序与因果关系

因果关系对所发生的事件施加了某种排序：发送消息先于收到消息；问题出现在答案之前等，或者就像在现实生活中一样，一件事情会导致另一件事情：一个节点根据读取的数据做出决定，然后写入结果，另一个节点读取写入的结果之后再写入新的内容，诸如此类。这些因果关系的依赖链条定义了系统中的因果顺序，即某件事应该发生另一件事情之前。

如果系统服从因果关系所规定的顺序，我们称之为因果一致性。

因果顺序并非全序

全序关系支持任何两个元素之间进行比较，即对于任意两个元素，总是可以指出哪个更大，哪个更小。例如，自然数符合全序关系，随便给出两个数字比如 5 和 13，都可以进行比较。

但是，有些集合并不符合全序，例如集合 {a, b} 大于集合 {b, c} 么？因为它们都不是对方的子集，所以无法直接比较它们。我们称之为不可比较，数学集合只能是偏序。某些情况下，一个集合可以包含另一个(如果该集合包含另一个集合的所有元素)否则则无法比较。

全序就是无条件排序，任何时刻都能够指出排序结果。

偏序就是在一定前提约束下才能排序。

全序和偏序的差异也会体现在不同的数据库一致性模型中:

可线性化：在一个可线性化的系统中，存在全序操作关系。系统的行为就好像只有一个数据副本，且每个操作都是原子的，这意味着对于任何两个操作，我们总是可以指出哪个操作在先。

因果关系：如果两个操作都没有发生在对方之前，那么这两个操作是并发关系。换言之，如果两个事件是因果关系(一个发生在另一个之前) ，那么这两个事件可以被排序；而并发的事件则无法排序比较。这表明因果关系至少可以定义为偏序，而非全序。

可线性化强于因果一致性

那么因果序和可线性化之间是什么关系呢？答案是可线性化一定意味着因果关系：任何可线性化的系统都将正确地保证因果关系，特别是，如果系统存在多个通信通道，可线性化确保了因果关系会自动全部保留，而不需要额外的工作(比如在不同组件之间的传递时间戳)。

可线性化可以确保因果性这一结论，使线性化系统更加简单易懂而富有吸引力。但是，正如在“线性化的代价”将要阐述的，线性化会显著降低性能和可用性，尤其是在严重网络延迟的情况下(例如多数据中心) 。正因如此，一些分布式数据系统已经放弃了线性化，以换来更好的性能，但也存在可能无法正确工作的风险。

好消息是线性化并非是保证因果关系的唯一途径，还有其他方法使得系统可以满足因果一致性而免于线性化所带来的性能问题。事实上，因果一致性可以认为是，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。

在许多情况下，许多看似需要线性化的系统实际上真正需要的是因果一致性，后者的实现可以高效很多。基于这样的观察，研究人员正在探索新的数据库来保证因果关系，其性能与可用性特征与最终一致性类似。

序列号排序

我们可以使用序列号或时间戳来排序事件。时间戳不一定来自墙上时钟(或者物理时钟，但正如第8章所讨论的，物理时钟存在很多问题)。它可以只是一个逻辑时钟，例如采用算法来产生一个数字序列用以识别操作，通常是递增的计数器。

这样的序列号或时间戳非常紧凑(只有几字节的大小) ，但它们保证了全序关系。也就是说，每一个操作都有唯一的顺序号，并且总是可以通过比较来确定哪个更大(即操作发生在后)

特别是，我们可以按照与因果关系一致的顺序来创建序列号：保证如果操作 A 发生在 B 之前，那么 A 一定在全序中出现在 B 之前 (即 A 的序列号更小) 。并行操作的序列可能是任意的。这样的全局排序可以捕获所有的因果信息，但也强加了比因果关系更为严格的顺序性。

在主从复制数据库中(参阅第5章“主节点与从节点” ) ，复制日志定义了与因果关系一致的写操作全序关系。主节点可以简单地为每个操作递增某个计数器，从而为复制日志中的每个操作赋值一个单调递增的序列号。从节点按照复制日志出现的顺序来应用写操作，那结果一定满足因果一致性(虽然从节点的数据可能会滞后于主节点)。

非因果序列发生器

如果系统不存在这样唯一的主节点(例如可能是多主或者无主类型的数据库，或者数据库本身是分区的) ，如何产生序列号就不是那么简单了。实践中可以采用以下方法：

每个节点都独立产生自己的一组序列号。例如，如果有两个节点，则一个节点只生成奇数，而另一个节点只生成偶数。还可以在序列号中保留一些位用于嵌入所属节点的唯一标识符，确保不同的节点永远不会生成相同的序列号。

可以把墙上时间戳信息(物理时钟)附加到每个操作上，时间戳可能是不连续的，但是只要它们有足够高的分辨率，就可以用来区分操作。“最后写获胜“ 的冲突解决方案也使用类似的方法(参阅第8章“时间裁与事件顺序" )。

可以预先分配序列号的区间范围。例如，节点 A 负责区间 1-1000 的序列号，节点 B 负责 1001-2000，然后每个节点独立地从区间中分配序列号，当序列号出现紧张时就分配更多的区间。

但上述方法无法完全保证操作顺序，因而存在因果关系方面的问题：

每个节点可能有不同的处理速度，如每秒请求数。因此，某个节点产生偶数而另一个产生奇数，偶数的计数器产生速度可能落后于奇数的计数器，反之亦然。这样就无法准确地知道哪个操作在先。

物理时钟的时间截会受到时钟偏移的影响，也可能导致与实际因果关系不一致。如后来发生的操作实际上被分配了一个较低的时间数。

对于区间分配器，一个操作可能被赋予从 1001-2000 之间的某个序列号，而后发生的操作则路由到另一个节点，拿到了某个 1-1000 之间的序列号，导致与因果序不一致。

Lamport 时间戳

刚才所描述的三个序列号发生器可能与因果关系存在不一致，但还有一个简单的方法可以产生与因果关系一致的序列号。它被称为兰伯特时间戳(Lamport timestamp)由 Leslie Lamport 于 1978 年提出，该文献也是现代分布式系统领域被引用最多的经典论文之一。

没太搞懂，反正这个方案也不能决定因果一致性。

时间戳排序依然不够

Lamport 时间戳虽然定义了与因果序一致的全序关系，但还不足以解决实际分布式系统中许多常见的问题提。如一个账户系统需要确保用户名唯一标识用户。即两个用户如果同时尝试使用相同的用户名创建账户时，确保其中一个成功，另一个必须失败。

乍看之下，似乎全序关系(例如使用Lamport时间戳)应该可以解决问题：如果有这样并发的操作，则选择时间戳较低的那个作为获胜者(先申请用户名的那个请求) ，而让时间戳大的请求失败。由于时间戳有序，所以这样的比较方法也应该是可行的。

但是，这种方法确定胜利者有这样一个前提条件：需要收集系统中所有的用户创建请求，然后才可以比较它们的时间戳。然而，当节点刚刚收到用户的创建请求时，它无法当时就做出决定该请求应该成功还是失败。此时，节点根本不知道是否有另一个节点在同时创建相同用户名(以及那个请求所附带的时间截) 。

而为了获得上述两点信息，系统就必须检查每个节点，询问它们在做什么，如果万一某个节点出现故障或者由于网络问题而无法连接，那么方法就无法正常运转。显然这不是我们所期望的容错系统。

这里问题的关键是，只有在收集了所有的请求信息之后，才能清楚这些请求之间的全序关系。如果另一个节点执行了某些操作，但你无法知道那是什么，就无法构造出最终的请求序列。也许，来自该未知操作确实需要插入到全序集合中才能正确评估出下一步。

总而言之，为了实现像用户名唯一性约束这样的目标，仅仅对操作进行全序排列还是不够的，还需要知道这些操作是否发生、何时确定等。假如能够在创建用户名时，已经确定知道了没有其他节点正在执行相同用户名的创建，你大可以直接安全返回创建成功。

要想知道什么时候全序关系已经确定就需要之后的“全序关系广播”。

全序关系广播

如前所述，主从复制首先确定某一个节点作为主节点，然后在主节点上顺序执行操作。接下来的主要挑战在于，如何扩展系统的吞吐量使之突破单一主节点的限制，以及如何处理主节点失效时的故障切换(参阅第5章“处理节点失效" ) 。在分布式系统研究文献中，这些问题被称为全序关系广播或者原子广播。

每个分区只有一个主节点的数据库通常只会维护分区内的顺序，即它们不提供跨分区的一致性保证(例如,一致性快照,外键引用等) 。跨分区的全序关系并非不可能，但需要非常多的额外工作。

全序关系广播通常指节点之间交换消息的某种协议。下面是一个非正式的定义，它要求满足两个基本安全属性:

可靠发送

没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。

严格有序

消息总是以相同的顺序发送给每个节点。

即使节点或网络出现了故障，全序关系广播算法的正确实现也必须保证上述两条。当然，网络中断时是不可能发送成功的，但算法要继续重试，直到最终网络修复，消息发送成功(且必须以正确的顺序发送)。

使用全序关系广播

zookeeper 和 etcd 这样的共识服务实际上就实现了全序关系广播，这也暗示了全序关系广播与共识之间有着密切的联系。

全序关系和线性化都等价于共识问题。如果能解决其中一个问题，那么就可以把方案用于解决其他问题。

分布式事务与共识

共识问题是分布式计算中最重要也是最基本的问题之一。表面上看，目标只是让几个节点就某件事情达成一致。这似乎很简单，或者至少不应该太难。不幸的是，许多失败的系统正是由于低估了这个问题所导致的。

有很多重要的场景都需要集群节点达成某种一致，例如：

主节点选举

对于主从复制的数据库，所有节点需要就谁来充当主节点达成一致。如果由于网络故障原因出现节点之间无法通信，就很容易出现争议。此时，共识对于避免错误的故障切换非常重要，后者会导致两个节点都自认为是主节点即脑裂(参阅第5章“处理节点失效” ) 。如果集群中存在两个这样的主节点，每个都在接受写请求，最终会导致数据产生分歧、不一致甚至数据丢失。

原子事务提交

对于支持跨节点或跨分区事务的数据库，会面临这样的问题：某个事务可能在一些节点上执行成功，但在其他节点却不幸发生了失败，为了维护事务的原子性(即 ACID，参阅第7章“原子性" ) ，所有节点必须对事务的结果达成一致：要么全部成功提交(假定没有出错) ，要么中止/回滾(如果出现了错误)。这个共识的例子被称为原子提交问题。

原子提交与两阶段提交

原子性可以防止失败的事务破坏系统，避免形成部分成功夹杂着部分失败。这对于多对象事务(参阅第7章“单对象与多对象事务操作” )和维护二级索引格外重要。每个二级索引都有与主数据不同的数据结构，因此，如果修改了某些数据，则相应的二级索引也需要随之更新。原子性可以确保二级索引与主数据总是保持一致(如果发生了不一致，那么索引的作用将会大打折扣)。

从单节点到分布式的原子提交

在单节点上，事务提交非常依赖于数据持久写入磁盘的顺序关系：先写入数据，然后再提交记录，事务提交(或中止)的关键点在于磁盘完成日志记录的时刻：在完成日志记录写之前如果发生了崩溃，则事务需要中止；如果在日志写入完成之后，即使发生崩溃，事务也被安全提交。这就是在单一设备上(某个特定的磁盘连接到一个特定的节点)上实现原子提交的核心思路。

但是，如果一个事务涉及多个节点呢？例如，一个分区数据库中多对象事务，或者是基于词条分区的二级索引(其中索引条目可能位于与主数据不同的节点上，请参阅第6章“分区与二级索引" ) 。

向所有节点简单地发送一个提交请求，然后各个节点独立执行事务提交是绝对不够的。这样做很容易发生部分节点提交成功，而其他一些节点发生失败，从而违反了原子性保证。

两阶段提交

两阶段提交(two-phase commit, 2PC) 是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。它是分布式数据库中的经典算法之一，2PC在某些数据库内部使用，或者以 XA 事务形式(例如Java Transaction API) 或 SOAP Web 服务 WS-Atomic Transaction 的形式提供给应用程序。

2PC 的基本流程如图9-9所示。不同于单节点上的请求提交，2PC 中的提交/中止过程分为两个阶段(因此得名2PC) 。

2PC 引入了单节点事务所没有的一个新组件：协调者(也称为事务管理器)。

阶段一：协调者发送一个准备请求到所有节点，询问他们是否可以提交，然后跟踪参与者的回复。

阶段二：

如果所有参与者回答“是” ，表示他们已准备好提交，那么协调者会发出提交请求，提交开始实际执行。
如果有任何参与者回复“否” ，则协调者向所有节点发送放弃请求。

这个过程有点像西方传统的婚姻仪式：主持人会询问新郎和新娘是否愿意与对方结为夫妇，通常双方都会回答“我愿意” ，在确认之后和所有与会者共同见证下，方可宣布完成了婚姻承诺。而万一新郎或者新娘没有肯定回复，理论上仪式应该中止。

2PC 就像 2 person ceremony ，婚礼仪式上的承诺。

系统的承诺

为了理解其工作原理，我们来更详细地分解这个过程：

当应用程序启动一个分布式事务时，它首先向协调者请求事务 ID，该 ID 全局唯一。

应用程序在每个参与节点上执行单节点事务，并将全局唯一事务 ID 附加到事务上。此时，读写都是在单节点内完成，如果在这个阶段出现问题(例如节点崩溃或请求超时) ，则协调者和其他参与者都可以安全中止。（分布式事务转换成了单节点事务）

当应用程序准备提交时，协调者向所有参与者发送准备请求，并附带全局事务 ID。如果准备请求有任何一个发生失败或者超时，则协调者会通知所有参与者放弃事务。

参与者在收到准备请求之后，确保在任何情况下都可以提交事务，包括安全地将事务数据写入磁盘(不能以任何借口稍后拒绝提交，包括系统崩溃，电源故障或磁盘空间不足等) ，并检查是否存在冲突或约束违规。一旦向协调者回答“是” ，节点就承诺会提交事务，换句话说，尽管还没有真正提交，但参与者已表态此后不会行使放弃事务的权利。

当协调者收到所有准备请求的答复时，就是否提交(或放弃)事务要做出明确的决定(即只有所有参与者都投赞成票时才会提交) 。协调者把最后的决定写入到磁盘的事务日志中，防止稍后系统崩溃，并可以恢复之前的决定。这个时刻称为提交点。

协调者的决定写入磁盘之后，接下来向所有参与者发送提交(或放弃)请求。如果此请求出现失败或超时，则协调者必须一直重试，直到成功为止。此时，所有节点不允许有任何反悔：开弓没有回头箭，一旦做了决定，就必须贯彻执行，即使需要很多次重试。而如果有参与者在此期间出现故障，在其恢复之后，也必须继续执行。这是因为之前参与者都投票选择了“是” ，对于做出的承诺同样没有反悔的余地。

回到婚姻的例子里，在说“我愿意”之前，新娘/新郎都有“放弃”承诺的自由，比如说“我不愿意! "。而在做出肯定的承诺之后，就不能随便撤销。假如在说了“我愿意”之后不巧晕倒在地，即使他/她没有听到“你们现在已结为夫妻”的证词，也不会因此就能改变事实。当稍后恢复了意识，可以询问证婚人(通过事务ID状态)是否已完成婚礼，或者等待证婚人安排下一次仪式(即重试将一直持续下去)。

发出承诺就要贯彻执行到底！不论出现什么情况。

协调者发生故障

2PC 期间参与者无理在第一阶段还是第二阶段出问题，协调者都能够处理。如第一阶段出问题，协调者可以中止交易。如第二阶段出问题，协调者可以无限期的重试。

但是，如果协调者本身发生了故降，接下来会发生什么现在还不太清楚。

情况如图9-10所示。在该例子中，协调者实际上做出了提交决定，数据库2 已经收到了提交请求。但是，协调者在将提交请求发送到数据库1 之前发生了崩溃，因此数掉库1 不知道该提交还是中止。超时机制也无法解决问题：如果超时之后数据库1 决定单方面中止，最终将与完成提交的数据库2 产生不一致。同理，参与者也不能单方面决定提交，因为可能有些参与者投了否决票导致协调者最终的决定是放弃。

2PC 能够顺利完成的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交(或中止)请求之前要将决定写入磁盘的事务日志：等协调者恢复之后，通过读取事务日志来确定所有未决的事务状态。如果在协调者日志中没有完成提交记录就会中止。此时，2PC 的提交点现在归结为协调者在常规单节点上的原子提交。

协调者挂了也包括协调者的与参与者无法通信的情况。

2PC 成功与否在于证婚人身上，证婚人说成了就成了，没成就没成。

三阶段提交

两阶段提交也被称为阻塞式原子提交协议，因为 2PC 可能在等待协调者恢复时卡住。理论上，可以使其改进为非阻塞式从而避免这种情况。但是，实践中要想做到这一点并不容易。

作为 2PC 的替代方案，目前也有三阶段提交算法。然而，3PC 假定一个有界的网络延迟和节点在规定时间内响应。考虑到目前大多数具有无限网络延迟和进程暂停的实际情况(见第8章) ，它无法保证原子性。

通常，非阻塞原子提交依赖于一个完美的故障检测器，即有一个非常可靠的机制可以判断出节点是否已经崩溃。在无限延迟的网络环境中，超时机制并不是可靠的故障检测器，因为即使节点正常，请求也可能由于网络问题而最终超时。正是由于这样的原因，尽管大家已经意识到上述协调者潜在的问题，但还在普遍使用2PC。

3PC 在 2PC 基础上增加了超时机制，一定程度上环节了 2PC 卡死的问题，但依旧无法解决最终共识问题，也就无法解决由共识问题导致的数据不一致问题，参与者有的提交了，有的没提交。

实践中的分布式事务

分布式事务的某些实现存在严重的性能问题。例如，有报告显示 MySQL 的分布式事务比单节点事务慢 10 倍以上，所以不建议使用也就不足为奇了。两阶段提交性能下降的主要原因是为了防崩溃恢复而做的磁盘 I/O (fsync) 以及额外的网络往返开销。

我们还是要明确“分布式事务”的确切含义。目前由两种截然不同的分布式事务概念:

数据库内部的分布式事务

某些分布式数据库(例如那些标配支持复制和分区的数据库)支持跨数据库节点的内部事务。例如，VoltDB 和 MySQL Cluster 的 NDB 存储引擎就支持这样的内部分布式事务。此时，所有参与节点都运行着相同的数据库软件。

异构分布式事务

在异构分布式事务中，存在两种或两种以上不同的参与者实现技术。例如来自不同供应商的数据库，甚至是非数据库系统(如消息中间件) 。即使是完全不同的系统，跨系统的分布式事务业必须确保原子提交。

Exactly-once 消息处理

todo

XA 交易

todo

停顿时仍持有锁

为什么我们非常关注陷入停顿的参与者节点(即不确定该提交还是中止)呢？难道系统不能选择忽略(并最终清理)这些节点，这样系统不就可以继续工作么？问题的关键在于锁。

在事务提交(或中止)之前，数据库都不会释放这些锁，因此，在两阶段提交时，事务在整个停顿期间一直持有锁。换句话说，如果协调者崩溃并且需要 20 分钟才能重启恢复，那么这些对象将被锁定 20 分钟；如果协调者的日志由于某种原因而彻底丢失，这些数据对象将永久处于加锁状态，至少管理员采用手动方式解决之前只能如此。

数据处于加锁时，其他事务就无法执行修改。取决于数据库的具体实现，其他事务甚至无法读取这些行。因此，其他的事务事实上无法有效执行。这可能会导致很多上层应用基本处于不可用状态，所以必须解决处于停顿状态的那些事务。

从协调者故障中恢复

那些悬而未决的事务无法自动解决，而是永远留在那里，而且还持有锁并阻止其他事务。有时只能通过人工介入来处理。但这种工作需要大量手工操作，系统可能背负巨大压力和时间限制。

许多 XA 的实现都支持某种紧急避险措施称之为启发式决策：这样参与者节点可以在紧急情况下单方面做出决定，放弃或者继续那些停顿的事务，而不需要等到协调者发出指令，需要说明的是，这里的启发式其实是可能破坏原子性的委婉说法，它的确违背了两阶段提交所做出的承诺。因此，这种启发式决策只是为了应急，不能作为常规手段来使用。

分布式事务的限制

XA 事务解决了多个参与者之间如何达成一致这样一个非常现实而重要的问题，但正如上面所看到的，它也引入了不少操作方面的限制。特别是，核心的事务协调者本身就是一种数据库(存储事务的投票结果) ，因此需要和其他重要的数据库一样格外小心：

如果协调者不支持数据复制，而是在单节点上运行，那么它就是整个系统的单点故障(因为它的故障导致了很多应用阻塞在停顿事务所持有的锁上) 。而现实情况是，有许多协调者的实现默认情况下并非高可用，或者只支持最基本的复制。

许多服务器端应用程序都倾向于无状态模式(因为更受HTTP的青睐) 。而所有的持久状态都保存在数据库中，这样应用服务器可以轻松地添加或删除实例。但是，当协调者就是应用服务器的一部分时，部署方式就发生了根本的变化。突然间，协调者的日志成为可靠系统的重要组成部分，它要求与数据库本身一样重要(需要协调者日志恢复那些有疑向的事务) 。这样的应用服务器已经不再是无状态。

由于XA需要与各种数据系统保持兼容，它最终其实是多系统可兼容的最低标准。例如，它无法深入检测不同系统之间的死锁条件(因为这就将需要另一个标准化协议，使得多个系统交换事务所等待的锁信息) ，而且不适用于SSI (参阅第7章“可串行化的快照隔离” ) ，后者要求一个复杂的协议来识别不同系统闻的写冲突。

对于数据库内部的分布式事务(而不是 XA) ，限制则少很多，例如 ssl 的分布式版本是可行的。然而，2PC 要成功提交事务还是存在潜在的限制，它要求必须所有参与者都投票赞成，如果有任何部分发生故障，整个事务只能失败。所以分布式事务有扩大事务失败的风险，这与我们构建容错系统的目标有些背道而驰。

支持容错的共识

共识问题通常形式化描述如下：一个或多个节点可以提议某些值，由共识算法来决定最终值。对于预约座位的例子，当多个顾客同时试图购买最后一个座位时，处理顾客请求的每个节点可以提议它所服务的顾客 ID，最后的决定则是关于由哪个顾客获得座位。

在这个描述中，共识算法必须满足以下性质：

协商一致性(Uniform agreement)

所有的节点都接受相同的决议。

诚实性(Integrity)

所有节点不能反悔，即对一项提议不能有两次决定。

合法性(Validity)

如果决定了值 v，则一定是由某个节点所提议的。

可终止性(Termination)

节点如果不崩溃则最终一定可以达成决议。

协商一致性和诚实性属性定义了共识的核心思想：决定一致的结果，一旦决定，就不能改变。有效性属性主要是为了排除一些无意义的方案：例如，无论什么建议，都可以有一个总是为空(NULL)的决定，虽然可以满足一致性和诚实性，但没有任何实际效果。

如果不关心容错，那么满足前三个属性很容易：可以强行指定某个节点为“独裁者” ，由它做出所有的决定。但是，如果该节点失败，系统就无法继续做出任何决定。其实这就是在两阶段提交时所看到的：如果协调者失败了，那些处于不确定状态的参与者就无从知道下一步该做什么。

可终止性则引入了容错的思想。它重点强调一个共识算法不能原地空转，永远不做事情，换句话说，它必须取得实质性进展。即使某些节点出现了故障，其他节点也必须最终做出决定。可终止性属于一种活性，而另外三种则属于安全性方面的属性(参阅第8章“安全性与活性” )。

事实上，可以证明任何共识算法都需要至少大部分节点正确运行才能确保终止性，而这个多数就可以安全地构成 quorum (参阅第5章"读写quorum" )

因此，可终止性的前提是，发生崩溃或者不可用的节点数必须小于半数节点。

共识算法与全序广播

最著名的容错式共识算法包括 VSR，Paxos，Raft 和 Zab，这些算法存在诸多相似之处，但又不完全相同。

这些算法大部分其实并不是直接使用上述的形式化模型(提议并决定某个值，同时满足上面4个属性) 。相反，他们是决定了一系列值，然后采用全序关系广播算法。

全序关系广播的要点是，消息按照相同的顺序发送到所有节点，有且只有一次。如果仔细想想，这其实相当于进行了多轮的共识过程：在每一轮，节点提出他们接下来想要发送的消息，然后决定下一个消息的全局顺序。

所以，全序关系广播相当于持续的多轮共识(每一轮共识的决定对应于一条消息) ：

由于协商一致性，所有节点决定以相同的顺序发送相同的消息。

由于诚实性，消息不能重复。

由于合法性，消息不会被破坏，也不是凭空捏造的。

由于可终止性，消息不会丢失。

VSR，Raft 和 Zab 都直接采取了全序关系广播，这比重复性的一轮共识只解决一个提议更加高效。而 Paxos 则有对应的优化版本称之为 Multi-Paxos。

主从复制与共识

主从复制中所有的写入操作都由主节点负责，并以相同的顺序发送到从节点来保持副本更新。这不就是基本的全序关系广播么？那在主从复制时我们怎么没有考虑共识问题呢？

答案取决于如何选择主节点。如果主节点是由运营人员手动选择和配置的，那基本上就是一个独裁性质的“一致性算法” ：只允许一个节点接受写入(并决定复制日志中的写入顺序) ，如果该节点发生故障，系统将无法写入，直到操作人员再手动配置新的节点成为主节点。这样的方案也能在实践中很好地发挥作用，但它需要人为干预才能取得进展，不满足共识的可终止性。

一些数据库支持自动选举主节点和故障切换，通过选举把某个从节点者提升为新的主节点(参阅第5章“处理节点失效” ) 。这样更接近容错式全序关系广播，从而达成共识。

但是，还有一个问题，我们之前曾讨论过脑裂：所有的节点都需要同意主节点，否则两个主节点会导致数据库出现不一致。因此，我们需要共识算法选出一位主节点。但是，如果这里描述的共识算法实际上是全序关系广播，且全序关系广播很像主从复制，但主从复制现在又需要选举主节点等。

看起来要选举一个新的主节点,我们首先需要有一个主节点。要解决共识,必须先处理共识。怎么摆脱这样一个奇怪的循环?

Epoch 和 Quorum

目前所讨论的所有共识协议在其内部都使用了某种形式的主节点，虽然主节点并不是固定的。相反，他们都采用了一种弱化的保证：协议定义了一个世代编号(epoch number，对应于Paxos中的ballot number, VSP中view number,以及Raft中的termnumber) ，并保证在每个世代里，主节点是唯一确定的。如果发现当前的主节点失效，节点就开始一轮投票选举新的主节点。选举会赋予一个单调递增的epoch号。如果出现了两个不同的主节点对应于不同epoch号码(例如，上一个 epoch 号码的主节点其实并没有真正挂掉) ，则具有更高epoch号码的主节点将获胜。

共识的局限性

共识体系需要严格的多数节点才能运行。这意味着需要至少三个节点才能容忍一个节点发生故障(剩下的三分之二形成多数) ，或者需要最少五个节点来容忍两个节点故障(其余五分之三形成多数) 。如果由于网络故障切断了节点之间的连接，则只有多数节点所在的分区可以继续工作，剩下的少数节点分区则处于事实上的停顿状态(参阅本章前面“线性化的代价”。

多数共识算法假定一组固定参与投票的节点集，这意味着不能动态添加或删除节点。动态成员资格的扩展特性可以在集群中的按需调整节点数，但相比于静态的成员组成,其理解程度和接受程度要低很多。

共识系统通常依靠超时机制来检测节点失效。在网络延迟高度不确定的环境中，特别是那些跨区域分布的系统，经常由于网络延迟的原因，导致节点错误地认为主节点发生了故障。虽然这种误判并不会损害安全属性，但频繁的主节点选举显著降低了性能，系统最终会花费更多的时间和资源在选举主节点上而不是原本的服务任务。

此外，共识算法往往对网络问题特别敏感。例如，Raft 已被发现存在不合理的边界条件处理：如果整个网络中存在某一条网络连接持续不可靠， Raft 会进入一种奇怪的状态：它不断在两个节点之间反复切换主节点，当前主节点不断被赶下台，这最终导致系统根本无法安心提供服务。

其他共识算法也有类似的问题，所以面对不可靠网络，如何设计更具鲁棒性的共识算法仍然是一个开放性的研究问题。

成员与协调服务

应用程序很少直接使用 zookeeper，而是通过很多项目来间接使用，如 HBase、Kafka 等，为什么？

ZooKeeper和etcd主要针对保存少量、可完全载入内存的数据(虽然它们最终仍要写入磁盘以支持持久性)而设计，所以不要用它们保存大量的数据。它们通常采用容错的全序广播算法在所有节点上复制这些数据从而实现高可靠。正如之前所讨论的，全序广播主要用来实现数据库复制：每条消息代表的是数据库写请求，然后按照相同的顺序在多个节点上应用写操作，从而达到多副本之间的一致性。

Zookeeper 的实现其实模仿了 Google 的 Chubby 分布式锁服务，但它不仅实现了全序广播(因此实现了共识) ，还提供了其他很多有趣的特性。所有这些特性在构建分布式系统时格外重要：

线性化的原子操作

使用原子比较-设置操作，可以实现加锁服务。例如如果多个节点同时尝试执行相同的操作，则确保其中只有一个会成功。共识协议保证了操作满足原子性和线性化，即使某些节点发生故障或网络随时被中断。分布式锁通常实现为一个带有到期时间的租约，这样万一某些客户端发生故障，可以最终释放锁(参阅第8章“进程暂停" )。

操作全序

如第8章“主节点与锁”所述，当资源被锁或者租约保护时，需要 fencing 令牌来防止某些客户端由于发生进程暂停而引起锁冲突。 fencing 令牌确保每次加锁时数字总是单调增加。 ZooKeeper 在实现该功能时，采用了对所有操作执行全局排序，然后为每个操作都赋予一个单调递增的事务 ID (zxid) 和版本号 (cversion) 。

故障检测

客户端与 ZooKeeper 节点维护一个长期会话，客户端会周期性地与 ZooKeeper 服务节点互相交换心跳信息，以检查对方是否存话，即使连接出现闪断，或者某个 ZooKeeper 节点发生失效，会话仍处于活动状态，但是，如果长时间心跳停止且超过了会话超时设置，ZooKeeper 会声明会话失败。此时，所有该会话持有的锁资源可以配置为自动全部释放(ZooKeeper称之为ephemeral nodes即临时节点)

更改通知

客户端不仅可以读取其他客户端所创建的锁和键值，还可以监视它们的变化。因此，客户端可以知道其他客户端何时加入了集群(基于它写入ZooKeeper的值)以及客户端是否发生了故障(会话超时导致节点消失) 。通过订阅通知机制，客户端不需要频繁地轮询服务即可知道感兴趣对象的变化情况。

在上述特征中，其实只有线性化的原子操作才依赖于共识。然而ZooKeeper集成了所有这些功能，在分布式协调服务中发挥了关键作用。

节点任务分配

ZooKeeper 和 Chubby 系统非常适合的一个场景是，如果系统有多个流程或服务的实例，并且需求其中的一个实例充当主节点；而如果主节点失效，由其他某个节点来接管。显然，这非常吻合主从复制数据库，此外，它对于作业调度系统(或类似的有状态服务)也非常有用。

还有另一个场景，对于一些分区资源(可以是数据库，消息流，文件存储，分布式actor system等) ，需要决定将哪个分区分配给哪个节点。当有新节点加入集群时，需要将某些现有分区从当前节点迁移到新节点，从而实现负载动态平衡(参阅第5章“分区再平衡” ) 。而当节点移除或失败时，其他节点还需要接管失败节点。

ZooKeeper其实提供了一种将跨节点协调服务(包括共识，操作排序和故障检测)专业外包的方式。通常情况下， ZooKeeper所管理的数据变化非常缓慢，类似“分区7的主节点在 10.1.23"这样的信息，其变化频率往往在分钟甚至是小时级别。它不适合保存那些应用实时运行的状态数据，后者可能每秒产生数千甚至百万次更改。如果这样，应该考虑使用其他工具(如Apache BookKeeper)

服务发现

此外， Zookeeper， eted和Consul还经常用于服务发现。例如需要某项服务时，应该连接到哪个IP地址等。在典型的云环境中，虚拟机可能会起起停停，这种动态变化的节点无法提前知道服务节点的IP地址，因此，可以这样配置服务，每当节点启动时将其网络端口信息向Zookeeper等服务注册，然后其他人只需向ZooKeeper的注册表中询问即可。

成员服务 成员服务用来确定当前哪些节点处于活动状态并属于集群的有效成员。正如在第8章中所介绍的，由于无限的网络延迟，无法可靠地检测一个节点究竟是否发生了故障。但是，可以将故障检测与共识绑定在一起，让所有节点就节点的存活达成一致意见。

这里依然存在发生误判的可能性，即节点其实处于活动状态却被错误地宜判为故障。即便这样，系统就成员资格问题的决定是全体一致的，这是最重要的。

例如，选举主节点的方式可能是简单地投票选择编号最小的节点，一旦节点对于当前包含哪些成员出现了不同意见，那么共识过程就无法继续。

小结

本章从多个不同的角度审视了一致性与共识问题。深入研究了线性化(一种流行的一致性模型) ：其目标是使多副本对外看起来好像是单一副本，然后所有操作以原子方式运行，就像一个单线程程序操作变量一样。线性化的概念简单，容易理解，看起来很有吸引力，但它的主要问题在于性能，特别是在网络延迟较大的环境中。

我们接下来探讨了因果关系，因果关系对事件进行了某种排序(根据事件发生的原因-结果依赖关系) 。线性化是将所有操作都放在唯一的、全局有序时间线上，而因果性则不同，它为我们提供了一个弱一致性模型：允许存在某些并发事件，所以版本历史是一个包含多个分支与合并的时间线。因果一致性避免了线性化昂贵的协调开销，且对网络延迟的敏感性要低很多。

如果系统只存在一个节点，或者愿意把所有决策功能都委托给某一个节点，那么事情就变得很简单。这和主从复制数据库的情形是一样的，即由主节点负责所有的决策事宜，正因如此，这样的数据库可以提供线性化操作、唯一性约束、完全有序的复制日志等。

然而，如果唯一的主节点发生故障，或者出现网络中断而导致主节点不可达，这样的系统就会陷入停顿状态。有以下三种基本思路来处理这种情况:

系统服务停止，并等待主节点恢复。许多XA /TA事务协调者采用了该方式。本质上，这种方法并没有完全解决共识问题，因为它不满足终止性条件，试想如果主节点没法恢复，则系统就会永远处于停顿状态。

人为介入来选择新的主节点，并重新配置系统使之生效。许多关系数据库都采用这种方法。本质上它引入了一种“上帝旨意”的共识，即在计算机系统之外由人类来决定最终命运。故障切换的速度完全取决于人类的操作，通常比计算机慢。

采用算法来自动选择新的主节点。这需要一个共识算法，我们建议采用那些经过验证的共识系统来确保正确处理各种网络异常。

虽然主从数据库提供了线性化操作，且在写操作粒度级别上并不依赖于共识算法，但它仍然需要共识来维护主节点角色和处理主节点变更情况。因此，某种意义上说，唯一的主节点只是其中的一步，系统在其他环节依然需要共识(虽然不那么的频繁)。好在容错算法与共识的系统可以共存，我们在本章做了简要地介绍。 ZooKeeper 等工具以一种类似外包方式为应用提供了重要的共识服务、故障检测和成员服务等。虽然用起来依然有挑战，但远比自己开发共识算法要好得多(正确处理好第8章的所有问题绝非易事) 。如果面临的问题最终可以归结为共识，并且还有容错需求，那么这里给的建议是采用如ZooKeeper等验证过的系统。