# 10. 一致性与共识


一致性与共识

<!-- more -->

## 1. 共识算法的概述
本节我们将讨论构建容错式分布式系统的相关算法和协议。这里我们假设第 8 章中所有的故障都可能发生: 网络会丢失、顺序紊乱、重复发送或延迟；时钟也有一定偏差，节点可能发生暂停甚至随时崩溃。为了构建容错系统，最好先建立一套**通用的抽象机制**和**与之对应的技术保证**，这样只需实现一次，其上的各种应用程序都可以安全的信赖底层的保证。这与引入事务是一样的道理。

接下来我们将沿着这个思路，尝试建立**让分布式应用忽略内部各种问题的抽象机制**，比如**共识**，即所有的节点就某一项提议达成一致。我们将研究解决共识问题的相关算法，以及讨论**分布式系统可提供的若干保证和抽象机制**。

我们需要了解系统能力的边界，在什么情况下，系统可以容忍故障并继续工作。我们将探索分布式系统下比最终一致性更强的一致性模型(之前介绍复制的内容时，我们已经介绍了一部分)。

分布式一致性模型与之前讨论的多种事务隔离级别有相似之处，但总体上他们有着显著的不同:
1. 事务隔离主要是为了处理**并发执行事务时**的各种临界条件
2. 分布式一致性则主要是**针对延迟和故障等问题**来**协调副本之间的状态**

分布式一致性包括:
1. 写后读
2. 单调读
3. 前缀一致读
4. 线性化
5. 顺序一致性，满足线性化的写，不满足线性化的读
5. 因果一致性

前面三个我们已经介绍过了，接下来我们将讨论:
1. **线性化**: 这是最强的一致性模型
2. 分布式系统中**事件顺序问题**，特别是**因果关系**和**全局顺序**
3. 如果自动提交分布式事务，并最终解决共识问题

## 2. 可线性化
可线性化的基本想法是**让一个系统看起来好像只有一个数据副本**，且**所有的操作都是原子的**。有了这个保证，应用程序就不需要多副本带来的复制延迟问题，每个客户端都拥有相同的数据视图。这种看似单一副本的假设意味着，它可以保证**读取最近最新值**，而不是过期的缓存。换句话说,**可线性化是一种就近保证**。

可线性化的基本思想很简单，但是它有更多的含义:
1. 一旦某个读操作返回了新值，之后所有的读(**包括相同和不同的客户端**)都必须返回新值
2. 某个客户端读取了新值，即使**写操作尚未提交**，那么所有后续的读取也必须全部返回新值(当然尚未提交，数据库完全可以不让客户端读取到新值)

对于可线性化的系统要格外注意**时序依赖关系**，在下面的读写时序中:
1. 客户端 A 读取到新值 1，在 A 读取返回之后，B 开始读取，由于 **B 的读取严格在 A 的读取发生之后**，因此即使 C 的写入仍在进行之中，也必须返回 1。

![一个可线性化的系统](/images/db/line.png)

可以进一步细化时序图来可视化每部操作具体在哪个时间点生效，如下图所示。这里我们引入了第三种类型的操作: `Cas(x, V-old, V-new)`

![细化读、写操作的生效时间，客户端B的最后读取不满足可线性化](/images/db/line_detail.png)

在上图中每个操作都有一条竖线，表示实际的执行时间点，这些标记**以前后关系依次连接起来**，最终的结果必须是一个有效的寄存器读写顺序，即每个读操作返回最近写操作所设置的值。

可线性化要求，如果连接这些标记的竖线，它们必须总是按时间箭头(从左往右)向前移动，而不能向后移动。这个要求确保了之前所讨论的**就近性保证**: **一旦新值被写入或读取**，所有后续的读都看到的是最新的值，直到被再次覆盖。

上图中有一些细节值得仔细研究:
1. **模型没有假定事务间的隔离**，即另一个并发客户端可能随时会修改值。我们可以使用原子比较和设置(Cas)操作来检查是否被其他并发客户端修改
2. 客户端 B 的最后一次读取不满足线性化。该操作与 C 的 Cas 写操作同时发生，后者将 x 从 2 变成 4。在没有其他请求时，B读取可以返回 2。但在 B 读取开始之前，A 已经读取了新值 4，所以不允许 B 读取到比A更老的值。
3. 通过记录所欲请求和响应的时序，然后检查他们是否可以顺序排列，可以用来测试系统是否可线性化

### 2.1 可线性化与可串行化(重要)
注意可线性化与可串行化非常容易混淆，但它们完全不同:
1. 可串行化
    - 是事务的隔离属性，每个事务可以读写多个对象
    - 用来确保事务执行的结果与串行执行(每次执行一个事务)的结果完全相同，即使串行执行的顺序与事务实际执行的顺序不同
2. 可线性化:
    - 是**读写寄存器(单个对象)**的最新值保证
    - 不要求将操作组合到事务中，因此无法避免写倾斜等问题，除非采取其他额外措施

数据库可以同时支持可串行化和线性化，这种组合被称为**严格的可串行化**或**强的单副本可串行化**。基于两阶段加锁或者实际以串行执行都是典型的可线性化。但是可串行化的快照隔离则不是线性化的: 按照设计，它可以从一致性快照中读取，以避免读写之间的竞争。一致性快照的要点在于它里面不包括快照点创建时刻之后的写入数据，因此从快照读取肯定不满足线性化。


### 2.2 线性化的依赖条件
那么什么时候需要线性化呢？在下列场景中，线性化对于保证系统正确工作至关重要:
1. 主节点的选举:
    - 选举主节点通常的方式是使用锁，谁获取锁谁就是主节点
    - 不管锁如何实现，它必须满足可线性化: 所有节点都必须同意那个节点持有锁
    - **线性化存储服务是所有协调服务的基础**
2. 约束与唯一性保证: 与加锁类似，都要求所有节点就某个最新值达成一致
3. 跨通道的时间依赖
    - 线性化违例之所以被注意到，是因为**系统中存在其他的通信渠道**

什么叫系统中存在其他的通信渠道，我们看下面这个示例:
1. 用户上传图片至 Web 服务器，Image resizer 用于产生缩略图方便快速加载
2. Web 服务通过消息队列通知调整器，因为消息队列通常不适合大数据流而照片可能数兆大小，Web 服务会先将图片写入文件存储服务，写入完成后发消息通知调整器

![多个通信渠道](/images/db/channel_multi.png)

注意这里 Web 服务器和图片调整器之间存在两个不同的通信通道: 文件存储器和消息队列(注: 文件存储服务这里是分布式的)

如果没有线性化的就近保证，这两个通道之间存在竞争条件: 消息队列(步骤3)可能比**存储服务内部的复制**(步骤4)执行更快，这种情况下步骤5 可能会看到图片的旧版本或根本读不到任何内容。如果文件存储服务是可线性化的系统将可以正常工作。

线性化并非避免这种竞争的唯一方法，但却是最容易理解的。例如可以控制某一个通信通道(消息队列)"读自己写"，但会引入额外的复杂性。

### 2.3 实现线性化系统
由于线性化的本质意味着"表现得好像只有一个数据副本 + 所有操作都是原子的"。所以最贱的方案自然是只用一个数据副本，但是这样无法容错。系统容错最常见的方法是采用复制机制。前面我们介绍了多种复制机制，那么它们符合线性化要求么?
1. 主从复制: 读写必须都从主节点才满足线性化要求，但此时无法容错
2. 多主复制: 无法满足
3. 无主复制: 无法满足

直觉上对于 Dynamo 风格的复制模型(无主复制)，如果读写遵从严格的 quorum，应该是可线性化的，然而如果遭遇不确定的网络延迟，就会出现竞争条件，如下图所示:

![严格的 quorum 仍然不满足线性化](/images/db/line_quorum.png)

1. x 初始值为 0，写客户端向所有三个副本发送写请求将 x 置为 1
2. A 从两个节点读取到新值 1
3. B 在 A 之后，但在写请求同步到副本 2/3 之前读取，读到旧值 0

显然这不符合线性化要求。可以通过牺牲性能为代价来满足线性化: 读操作在返回结果给应用之前，必须同步执行读修复；而写操作在发送结果之前，必须读取 quorum 节点以获取最新值。当然这个的前提是数据不会采用最终写入这获胜的方法来处理写冲突。此外这种方法**只能支持线性化读、写操作**，但不能支持线性化的比较和设置操作。

总而言之最安全的假设是类似 Dynamo 风格的无主复制系统无法保证线性化。线性化的唯一实现方式是共识算法。

### 2.4 CAP 理论的误解
无论是主从复制还是多主复制，任何可线性化的数据库都存在这样的问题:
1. 如果应用要求线性化，但由于网络的问题，某些副本与其他副本断开连接后无法继续处理请求，就必须等待网络修复，服务不可用
2. 如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求，此时服务可用，但结果行为不符合线性化

因此，**不要求线性化的应用更能容忍网络故障**，这被称为 CAP 理论。CAP 代表**一致性、可用性、分区容错性**系统只能支持其中两个特性。但是这种理解存在误导性:
1. **网络分区是一种故障**，无法选择。网络正常时可以同时保证可用性和一致性，一旦发生网络故障，要么选择一致性，要么选择可用性。
2. 一致性指的是**线性化**，很多博客和文章在讲解 CAP 时都没有明确说明过
3. 可用性存在争议，其形式化定理中的可用性与通常意义上的理解有些差别(记得没错的话，CAP 的可用性指的是可访问的到的所有节点中，每一个都可用)。许多所谓的"高可用性"(**容错**)系统实际上并不符合 CAP 对可用性的特殊定义。

总之避免使用 CAP。

### 2.5 可线性化与网络延迟
实际上很少有系统真正满足线性化。例如现代多核 CPU 上的内存就是非线性化的(这个就是为什么类似 Go 语言有所谓的内存模型)。如果某个 CPU 核上运行的线程修改了一个内存地址，紧接着另一个 CPU 核上的线程尝试读取，则系统无法保证可以读到刚刚写入的值，除非使用了内存屏障或 fence 指令。

出现这种现象的原因是每个 CPU 都有自己独立的 cache 和寄存器。内存访问受限进入 cache系统，所有修改默认会异步刷新到主存。由于访问 cache 比访问主存快得多，所以这样的异步刷新对于现代 CPU 性能至关重要。但是，这就导致出现了多个数据副本(主存+几个不同级别cache)，而副本更新是异步的，无法保证线性化。

CAP 理论不适用于当今的**多核-内存一致性模型**: 在计算机内部，我们通常假设通信是可靠的，我们会假设一个 CPU核在于其他核断开之后操作系统还没down机。之所以放弃线性化的原因是**性能**，而不是为了容错。

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

是否存在一个更有效的线性化实现方案呢？目前来看是否定的，已经有证明: **如果想要满足线性化，读、写请求的响应时间至少要与网络延迟成正比**。考虑到网络高度不确定的网络延迟，线性化读写的性能势必非常差。

虽然没有足够快的线性化算法，但弱一致性模型的性能则快得多，这种取舍对于延迟敏感的系统非常重要。后面我们将讨论一些避免线性化但有可以保证正确性的方法。

所以**可线性化的缺点就是读写性能必然非常差**。

## 3. 顺序保证
线性化寄存器对外呈现的好像只有一份数据拷贝，并且每一个操作都是原子性生效。这意味着**操作是按照某种顺序执行的**。顺序是一个非常重要的概念，我们已经多次提及:
1. 主从复制中主节点的主要作用就是**确定复制日志的写入顺序**，正因为有主节点确定写入顺序，主从复制才不会出现并发写冲突
2. 可串行化是确保事务的执行结果与**按照某种顺序方式**执行一样
3. 分布式系统的时间戳和时钟，试图将顺序引入无序的操作，比如确定两个写操作哪一个先发生。

**排序、可线性化与共识**存在着某种深刻的联系。理解它们对于理解系统能做什么不能做什么非常有帮助。

### 3.1 顺序与因果关系
之所以反复出现**顺序问题**，其中一个原因是它有助于**保持因果关系**。因果关系对所发生的事件施加了某种顺序: 发送消息先于收到消息，问题出现在答案之前等等。**这些因果关系的依赖链条**定义了系统中的**因果顺序**，即某件事应该发生在另一件事情之前。

如果系统服从因果关系所规定的顺序，我们称之为**因果一致性**。例如快照隔离级别提供了因果一致性: 当从数据库中读数据时，如果查询到了某些数据，也一定能看到触发该数据的前序事件(假设期间没有发生删除操作)。

### 3.2 因果顺序并非全序
全序关系支持任何两个元素之间进行比较，但是某些集合并不符合全序，例如集合{a,b} 和 {b,c} 无法直接比较，数据集合只能是偏序，即某些情况下一个集合可以包含另一个，否则无法比较。

**全序和偏序**的差异也体现在不同的数据库一致性模型中:
1. 可线性化: **存在全序操作关系**，总是可以指出哪个操作在先
2. 因果关系: 
    - 如果两个操作都没有发生在对方之前，这两操作是并发关系，Happen-before
    - 如果两个事件是因果关系，那么这两个事件可以被排序
    - 并发的事先无法排序比较
    - 因果关系至少可以定位为偏序，而非全序

因此根据这个定义，可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行，所以单个时间轴，单个数据副本，没有并发。可能存在多个请求，但出于等待状态。

并发意味着时间线会出现分支和合并，而不同分支上的操作无法直接比较。

### 3.3 可线性化与因果一致性
可线性化一定意味着因果关系，特别是如果系统存在多个通信通道，可线性化确保了因果关系会自动全部保留，而不需要额外的工作。

但是线性化会显著降低性能和可用性，尤其是在严重网络延迟的情况下。

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

许多情况，看似需要线性化的系统实际真正需要的是因果一致性。这也正是当下数据库发展的方向: 新的数据库保证因果关系，性能与可用性与最终一致性类似。

### 3.4 捕获因果依赖关系
为保持有听过关系，需要知道哪一个操作发生在前，如果一个操作发生在另一个操作之前，那么每个副本都应该按照相同的顺序处理。我们需要一些手段来描述系统中节点所知道的"知识"。与前面介绍的检测并发写的方法类似:
1. 无主复制中的因果关系，需要去检查对同一个主键的并发写请求，从而避免更新丢失
2. 因果一致性则要更近异步，需要跟踪整个数据库请求的 因果关系，而不仅仅是某个主键，版本向量可以推广为一种通用的解决方案。
3. 为了确定因果关系，数据库需要知道应用程序读取的是哪个版本的数据

因果关系很重要，但实际上跟踪所有的因果关系不切实际。客户端可能在写之前读取大量数据，系统无法了解写入究竟是依赖于全部读取内容内容，还仅仅是其中一部分。更好的办法是可以使用序列号或时间戳来排序时间。

在主从复制中，主节点可以简单为每个操作递增某个计数器，从而为复制日中的每个操作赋值一个单调递增的序列号。但如果系统不存在唯一的主节点，序列号的产生就不简单了。序列号要保证与因果关系一致，特别是保证跨节点操作的顺序。

#### Lamport 时间戳
有一种简单方法可以产生与因果关系一致的序列号，叫做兰伯特时间戳。下面是 Lamport 时间戳的示例:

![Lamport时间戳](/images/db/lamport.png)

1. 每一个节点都有一个唯一的标识符，且每个节点都有一个计数器来记录各自已处理的请求总数
2. Lamport 时间戳是一个值对(计数器，节点ID)
3. 给定两个 Lamport 时间戳，计数器较大那个时间戳大，如果计数器值相等，节点 ID 越大，时间戳越大

Lamport 时间戳的核心亮点在于使它们与因果关系保持一致:
1. 每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值
2. 并在每个请求中附带该最大计数器值
3. 当节点收到某个请求或回复时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则立即把自己的计数器修改为改最大值

**只要把最大计数器值嵌入到每一个请求中**，该方案可以确保 Lamport 时间戳与因果关系一致性，而**请求的因果依赖性一定会保证后发生的请求得到更大的时间戳**

Lamport 时间戳与版本向量存在相似之处，但它们的目的不同:
1. 版本向量用以区分两个操作是并发还是因果依赖
2. Lamport 时间戳则主要用于确保全序关系，但是即便 Lamport 时间戳与因果序一致，但**根据其全序关系却无法区分两个操作属于并发关系，还是因果依赖关系**。(Lamport 时间戳中，并发操作也被排序)


#### 时间戳排序依然不够
虽然Lamport时间戳定义了与因果序一致的全序关系，但还不足以解决实际分布式系统中许多常见的问题，例如账号的全局唯一性。乍看总是选择时间戳最小的作为获胜者是可行的，但是这个方法有一个前提条件: 需要收集系统中所有的用户创建请求，然后才可以比较它们的时间戳。当节点刚刚收到用户的创建请求时，它无法当时就做出决定该请求应该成功还是失败。此时节点根本不知道是否有另一个节点在同时创建相同的用户名。

为了获取以上两点信息，系统必须检查每个节点，如果因为节点故障或网络问题无法连接，这个方法就无法正常运转。

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

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

要想知道**什么时候全序关系已经确定**就需要**全序关系广播**。

## 4. 全序关系广播
在分布式系统上，让所有节点就全序关系达成一致面临巨大挑战。在分布式系统文献中，这些问题被称为**全序关系广播**或者原子广播。

全序关系广播通常指**节点之间交换信息的某种协议**。下面是一个非正式的定义:
1. 可靠发送: 没有消息丢失，如果消息发送到某一节点，一定发送到所有节点
2. 严格有序: 消息总以相同的顺序发送给每个节点

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

全序关系广播:
1. 正是数据库复制所需要的，如果每条消息代表数据库写请求，并且每个副本都按相同的顺序处理这些写请求，那么所有副本可以保持一致(或许有滞后)，该原则也被称为**状态机复制**
2. 可以实现**串行化事务**: 每条消息表示一个确定性事务，并且作为存储过程来执行，且每个节点遵从相同的执行顺序，可以保证数据库各分区以及各副本的一致性
3. 另一个要点是: **顺序在发送消息时已经确定**，**如果消息发送成功，节点不允许追溯地将某条消息插入到先前的某个位置上**(重要)。这一点是的全序关系广播比基于时间戳排序要求更强。

全序关系广播中，消息就像**追加方式更新日志**。

### 4.2 采用全序关系广播实现线性化存储(非常重要)
一个可线性化的系统中有全序操作集合。这是否意味着可线性化与全序关系广播是完全相同的呢？不完全是，但它们有着密切的联系:
1. 全序关系广播是基于异步模型: **保证消息以固定的顺序可靠发送**，但是**不保证消息何时发送成功**。某个接收者可能明显落后于其他接收者。可线性化则强调就近性: **读取时保证能够看到最新的写入值**
2. 如果有了全序关系广播，就可以在其上构建线性化的存储系统。

#### 基于全序关系广播实现线性化存储
通过使用全序关系广播以追加日志的方式来实现**线性化的原子比较-设置**:
    - 在日志中追加一条消息，并指明想要的用户名
    - 读取日志，将其广播给所有节点，并等待回复
    - 检查是否有任何消息生成用户名已被占用，如果没有其他节点回复已占用，可以提交该获取声明并返回客户端。反之则中止操作

由于日志条目以相同的顺序发送到所有节点，如果存在多个并发写入，则所有节点将首先决定哪个请求在先，选择第一个写请求作为获胜者，并中止其他请求，以确保所有节点同意一个写请求最终要么提交成功要么中止。类似的方法还可以用来在日志之上实现可串行化的多对象事务。

虽然此过程**可以确保线性化写入**，但它**无法保证线性化读取**。即从异步日志更新的存储中读取数据时，可能是旧值。具体来说，这里**只提供了顺序一致性**，也称为**时间线一致性**，它弱于线性化保证。

为了同时满足线性化读取，有以下几个方案:
1. 采用**追加的方式**把读请求排序、广播，然后各个节点获取该日志，当本节点收到消息时才执行真正的读操作。**消息在日志中的位置**已经决定了读取发生的时间点。etcd 的 quorum 读取和这个思路有相似之处
2. 如果可以**以线性化的方式获取当前最新日志中消息的位置**，则查询位置，等待直到该位置之前的所有条目都已经发送给你，接下来再执行读取。这与 Zookeeper的 sync() 操作思想相同。
3. 可以从同步更新的副本上读取，这样确保总是读取最新值

#### 采用线性化存储实现全序关系广播
最简单的方法是假设有一个线性化的寄存器来存储一个计数，然后使其支持原子自增-读取操作或者原子比较-设置操作。

思路很简单: 对于每个要通过全序关系广播的消息，**原子递增并读取**该线性化的计数，然后将其作为序列号附加到消息中。接下来广播到所有节点，接收者也严格按照序列化来发送回复消息。

这与 Lamport 时间戳不同，通过递增线性化寄存器获得的数字不会存在任何间隙。因此节点完成了消息 4 的发送，且收到了序列化 6 的消息，那么**在它对消息 6 回复之前必须等待消息 5**。Lamport时间戳不是这样的，这样是区别**全序关系广播**和**基于时间戳排序**的关键。

原子自增操作的线性化整数有多难？如果没有失效很容易，难点在于如何处理网络故障和节点失效。事实上，如果对**线性化的序列号发生器**深入思考之后所得到的的最终结果，毫无意外的指向了共识算法。

可以证明(非常重要):
1. **线性化的原子比较-设置(或自增)寄存器**与**全序关系广播**二者都等价于共识问题
2. 如果你能解决其中的一个问题，那么就可以把方案用于解决其他问题

接下来我们就正式进入共识问题。

#### 概念的递推关系总结(重要)
在可线性化，因果关系一致性，全序关系广播他们之间存在这样的关系:
1. 可线性化是分布式系统中最强的一致性模型，但是不能容错
2. 退而求次，大多数系统需要的是因果关系一致性，因果关系一致性可以容忍网络异常，提供和最终一致性一样的性能和容错性
3. 要捕获全局因果关系是不现实的，系统转而去捕获因果依赖关系，通过确定事件顺序来间接实现因果关系一致性
4. 通过 Lamport 时间戳可以获取**全序关系**，但是仅仅对操作进行全序排列还是不够的，需要确切知道操作是否发生、何时确定
5. 要想获取操作的全序关系，同时让所有节点达成共识就是全序关系广播。
6. 基于全序关系广播就可以实现线性化存储，反之亦然

## 5. 分布式事务与共识
在讨论了复制、事务、系统模型、线性化和全序关系广播等问题之后，我们终于可以直面共识问题了。有很多重要的场景都需要集群节点达成某种一致:
1. 主节点选举: 所有节点对谁来当主节点达成共识
2. 原子事务提交: 支持跨节点或跨分区事务，所有节点必须对事务的结果达成一致，要么全部提交，要么中止/回滚，这个共识的例子被称为**原子提交问题**

接下来我们将首先研究原子提交问题，我们将集中于**两阶段提交(2PC)**算法，2PC 是一种共识算法，虽然不是很有优秀。之后我们将讨论更好的共识算法，比如 Zookeeper(Zab)和 etcd(Raft)所使用的算法。


### 5.1 两阶段提交
原子性可以为应用程序提供非常简单的语义: 事务的结果要么成功提交，要么失败回滚，避免形成部分成功夹杂着部分失败。这对于多对象事务和维护二级索引格外重要。原子性可以确保二级索引与主数据库总是保持一致。

#### 单节点原子提交实现
单节点数据库节点上事务的原子性由存储引擎负责:
1. 数据库首先使事务的写入持久化，通常是保存在预写日志中，然后把**提交记录**追加写入到磁盘的日志文件中
2. 如果在数据的写入过程中数据库奔溃，此时:
    - 如果奔溃之前预写日志未完成，则回滚事务
    - 如果预写日志完成，提交记录未成功，节点重启后，事务可以从日志中恢复重新提交
    - 如果提交记录已完成则认为事务已安全提交

当事务涉及多个节点时，向所有节点简单发送一个提交请求，然后各个节点独立执行事务提交是绝对不够的。因为节点可能因为校验规则、网络异常、节点故障而提交失败。如果某些节点提交了事务，而其他节点放弃了事务就会出现不一致。

而且某个节点一旦提交了事务，即使事后发现其他节点发生中止，它也**没法撤销已提交的事务**。

**事务提交不可撤销**的深层次原因是，一旦数据提交，就被其他事务可见，继而其他客户端会基于此做出相应的决策。这个原则构成了读-提交隔离级别的基础。如果允许事务在提交之后还能中止，会违背之后所有读-提交的事务，进而被迫产生级联式的追溯和撤销。

#### 两阶段提交
2PC 是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。2PC 的基本流程如下图所示:

![两阶段提交的一次成功执行](/images/db/2pc.png)

2PC 引入了单节点事务所没有的一个新组件: 协调者(又称事务管理器)。整个事务过程如下:
1. 事务从应用程序执行数据读/写开始
2. 当应用程序准备提交事务时，协调者开始阶段 1：发送一个准备请求到所有节点(这些节点被称为参与者)，询问他们是否可以提交
2. 协调者然后跟踪参与者的回应:
    - 所有参与者回答是，那么协调者在接下来的阶段2提交请求
    - 如果有任何参与者回复否，则协调者在阶段2中向所有节点发送放弃请求

对于 2PC 准备和提交请求也一样可能丢失，那 2PC 是如何处理的，我们来详细分解上面过程:
1. 应用程序从协调者请求事务ID，该ID 全局唯一
2. 应用程序想每个参与节点发送请求，执行单节点事务，如果出现问题，协调者和其他参与者都可以安全中止
3. 进入提交阶段，第一阶段发送准备请求，参与者确保事务不会有任何异常可以提交后，回复可以提交。**一旦节点回复是，节点就承诺会提交事务**
4. 事务提交第二阶段，协调者收到所有**是**的准备答复后，先将最后的决定写入到磁盘的事务日志之后，接下来向所有参与者发送提交请求
1. 第一阶段中，任何一个准确请求发生了失败或超时，协调者就会中止事务
2. 第二阶段发生提交请求失败，协调者将无限期重试
3. 2PC 中每一步都会记录在事务日志中，因此当协调者崩溃重启后，就可以根据事务日志判断，哪些事务未完成需要中止，哪些事务已经决定提交还未收到参与者回复需要重复发送阶段二的提交请求

2PC 有两个关键的不归路: 
1. 阶段1，当参与者投票是时，它做出了肯定提交的承诺，如果协调者决定提交事务，参与者必须提交不可撤销
2. 阶段2，协调者做出了提交(或放弃)的决定，这个决定也是不可撤销的

正是这两个承诺确保了2PC的原子性。

#### 协调者故障
如果协调者本身发生故障会出现什么情况呢?

在协调者发送准备请求之前故障，参与者可以安全的中止交易

参与者收到了准备请求并投票是，参与者不能单方面放弃，它必须等待协调者的决定，如果决定到达之前，协调者崩溃或网络故障，则参与者只能无奈等待，此时参与者处于一种不确定的状态。2PC 能顺利完成的唯一方法是等待协调者恢复。这就是为什么**协调者必须在向参与者发送提交或中止请求之前要将决定写入磁盘的事务日志**: 等待协调者恢复之后，通过读取事务日志来确定所有未决的事务状态。如果协调者日志中没有完成提交记录就会中止。此时 2PC 的提交点归结为协调者在常规单节点上的原子提交。

两阶段提交也被称为**阻塞式原子提交协议**，因为 2PC **可能在等待协调者恢复时卡住**。

## 5.2 实践中的分布式事务
2PC由于操作上的缺陷、性能问题、承诺不可靠等问题遭受诟病，其性能下降的主要原因是为了防崩溃恢复而做的磁盘I/O，以及额外的网络往返开销。要不要使用分布式事务，我们首先要明确分布式事务的确切含义，现在有两种截然不同的分布式事务概念:
1. 数据库内部的分布式事务: 支持跨数据库节点的内部事务，所有参与者运行着相同数据库软件
2. 异构分布式事务: 
    - 存在两种或以上不同的参与者，即完全不同的系统，跨系统的分布式事务
    - 旨在无缝集成多种不同的系统，提供**Exactly-one 语义**
    - 只有在所有受影响的系统都使用相同的原子提交协议的前提下，这种分布式事务才是可行的

X/Open X/A 是异构环境下实施两阶段提交的一个工业标准。

### 5.3 停顿时持有锁
为什么我们非常关注陷入停顿的参与者节点，问题的关键在于锁，数据库事务通常持有带修改行的独占锁。可串行化隔离级别下还有读-共享锁

在事务提交和终止前，数据库不会释放这些锁。所以在两阶段提交时，事务在整个停顿期间一直持有锁；如果协调者的日志由于某种原因而彻底丢失，这些数据对象将永远处于加锁状态，需要管理员手动介入。数据加锁时，其他事务就无法执行修改甚至无法读取。这可能会导致很多上层应用基本处于不可用状态。所以必须解决处于停顿状态的那些事务。

### 5.5 分布式事务的限制
XA 事务解决了多个参与者如何达成一致这样一个非常重要的问题。但是核心的事务协调者本身就是一种数据库，需要格外小心:
1. 如果协调者不支持数据复制，那么它就是单点故障
2. XA 需要与各种数据库保持兼容，它最终其实是多环境可兼容的最低标准，比如无法检测死锁，不适用于SSI
3. 数据库内部的分布式事务限制少很多。然而 **2PC要成功提交事务要求必须所有参与者都投票赞成**，如果部分发生故障整个事务只能失败。所以分布式事务**有扩大事务失败的风险**，这与我们构建容错系统的目标有背道而驰。

如何保持多个系统一直，后面我们会继续讨论，现在我们应该可以总结一下共识问题。

## 6. 支持容错的共识
共识是让几个节点就某项提议达成一致。可以用共识算法来决定不相同的操作之中谁是获胜者。共识问题通常形式描述如下:
1. 一个或多个节点可以提议某些值，由共识算法来决定最终值
2. 比如多个客户预定相同的座位，处理客户请求的每个节点都可以提议它所服务的客户ID，共识算法决定哪个客户获得座位

共识算法必须满足以下性质:
1. 协商一致性: 所有节点都接受相同的决议
2. 诚实性: 所有节点不能**反悔**，即对一项提议不能有两次决定
3. 有效性: 如果决定了值 v，则 v 一定是有某个节点所提议的
4. 可终止性: 节点如果不崩溃则最终一定可以达成决议

协商一致和诚实性定义了共识的核心: **决定一致的结果，一旦决定，就不能改变**。如果不关心容错，前三个属性很容易满足: 可以强行指定某个节点为独裁者，但如果它失效了，系统就无法继续做出任何决定。其实这就是2PC所看到的: 如果协调者失败，那些处于不确定状态的参与者就无从知道下一步该做什么。

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

上述共识的系统模型假设: **当某个节点发生崩溃后，节点就彻底消失，永远不再回来**。在这样的系统模型下，所有采取等待节点恢复的算法都无法满足终止性，特别是2PC 不符合可终止性要求。(我的理解是这里节点彻底消失不是一个限制条件，即不是不允许节点偶尔失效之后又回来)

可终止性的前提是，发生崩溃或者不可用的节点数必须小于半数节点。并且大多数共识算法都假定系统不存在拜占庭式错误。

### 6.1 共识算法与全序广播
著名的共识算法包括 VSR、Paxos、Raft、Zab。他们有诸多相似之处，但又不完全相同。除非你要实现他们中的一个，否则只需了解它们共同的设计思想即可。

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

全序关系广播算法的要点是，**消息按照相同的顺序发送到所有节点，有且只有一次**。这其实相当于进行了多轮共识过程:
1. 在每一轮，节点提出他们接下来想要发送的消息，然后决定下一个消息的全局顺序。
2. 所以全序广播相当于持续的多轮共识，每一轮共识决定一条消息
3. 由于协商一致性，所有节点决定以相同的顺序发送相同的消息
4. 由于诚实性，消息不能重复
5. 由于合法性，消息不会被破坏，也不能凭空捏造
6. 由于可终止性，消息不会丢失

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

### 6.2 主从复制与共识
主从复制中，所有的写入操作都由主节点负责，并以相同的顺序发送到从节点。这不就是全序关系广播么？那为什么我们没有在主从复制中说过共识。

答案取决于如何选择主节点。

如果主节点由运营人员手动配置，这就是一种独裁性质的**一致性算法**。这个方案在实际中也很好的发挥作用，但是不满足共识的可终止性。

如果主节点是数据库自动选举的，这样更接近容错式全序关系广播，从而达成共识。但是这里出现了一个**逻辑循环**: 
1. 共识算法实际上是全序关系广播
2. 全序关系广播是主从复制
3. 主从复制有需要选举主节点

看起来要选举一个主节点，我们首先需要有一个主节点。要解决共识，必须先处理共识。怎么摆脱呢？

### 6.3 Epoch和Quorum(非常重要)
目前所讨论的所有共识协议在其**内部都使用了某种形式的主节点**，虽然主节点并不是固定的。相反他们都采用了一种弱化的保证: **协议定义了一个世代编号(epoch number)**，对应于 Paxos 中的 ballot number，VSP 中的 view number，Raft 中的 term number。并保证**每个世代里，主节点是唯一确定的**

如果发现当前的主节点失效，节点就开始一轮投票选举新的主节点。选举会赋予一个单调递增的 epoch 号。如果出现了两个不同的主节点对应于不同的 epoch 号，则更高 epoch 号的主节点将获胜。

**在主节点做出任何决定之前，它必须首先检查是否存在比它更高的 epoch 号码(每轮提议都要进行的)**。主节点如何知道它是否它已经被其他节点所取代呢？它必须从 quorum 节点中收集投票。主节点如果想要做出某个决定，须将提议发送给其他所有节点，等待 quorum 节点的响应。quorum 通常由多数节点组成。**并且只有当没有发现更高 epoch 主节点存在时，节点才会当前的提议(带有 epoch号)进行投票**。

因此这里实际存在两轮不同的投票:
1. 首先是投票决定谁是主节点 -- 准确来说是判断主节点有没有发生变化
2. 然后对主节点的提议进行投票

关键点是两轮投票的quorum 必须由重叠: 如果某个提议获得通过，那么其中参与投票的节点必须至少有一个也参加了最近一次的主节点选举。换言之如果在针对提议的投票中没有出现更高 epoch号码，那么可以得出这样的结论: 因为没有发生更高 epoch 的主节点选举，当前的主节点低位没有变化，所以可以安全的就提议投票。

#### 对比2PC
投票过程看起来很像 2PC，两者的区别在于:
1. 2PC 的协调者是运营人员配置的，不是徐阿奴的
2. 容错共识算法只需要多数节点的投票即可通过决议，2PC 必须要所有参与者通过
3. 共识算法还定义了恢复过程，出现故障后，通过该过程节点可以选举出新的主节点然后进入一致的状态，确保总是能够满足安全绳属性。


### 6.4 共识的局限性
共识算法对分布式系统至关重要，它为一切不确定的系统带来了明确的安全属性(一致性、完整性、有效性)，还支持容错(只要大多数节点还在工作和服务可达)。

共识算法可以提供全序关系广播，以容错的方式实现线性化的原子操作。但是共识是有代价的:
1. 在达成一致性决议前，节点投票的过程是一个同步复制过程
2. 共识体系需要严格的多数节点才能运行
3. 多数共识算法假定一组固定参与投票的节点集，这意味着不能动态添加或删除节点
4. 共识系统通常依靠超时机制来检测节点失效，在网络延迟高度不确定的环境中，会因为网络延迟的原因，导致节点错误的认为主节点发生了故障。虽然这种误判不会损害安全属性，但频繁的主节点选举显著降低了性能，系统最终会花费更多的时间和资源在选举主节点上而不是原本的服务本身。
5. 共识算法往往对网络问题特别敏感。例如 Raft 已被发现存在不合理的边界条件处理: 如果整个网络中存在某一条网络连接持续不可靠，Raft 会进入一种奇怪的状态: 它不断在两个节点之间反复切换主节点，当前主节点不断被赶下台，这最终导致系统根本无法安心提供服务。其他共识算法也有类似的问题，所以面对不可靠网络，如何设计更具鲁棒性的共识算法仍然是一个开放性的研究问题。

## 7. 成员与协调服务
Zookeeper 和 etcd 通常被称为**分布式键值存储**或**协调与配置服务**。Zookeeper 和 etcd 主要针对**保存少量、可以完全载入内存的数据**(虽然数据最终还是有写入磁盘以支持持久化)而设计，所以不要用他们保存大量的数据。它们通常采用容错的全序广播算法在所有节点上复制这些数据从而实现高可靠。全序广播主要用来实现数据库复制: 每条消息代表的是数据库写请求，然后按照相同的顺序在多个节点上应用写操作，从而达到多副本之间的一致性。

### 7.1 Zookeeper
Zookeeper 的实现模仿了 Google 的 Chubby 分布式锁服务，但它不仅实现了全序广播(因此实现了共识)，还提供了其他很多有趣的特性，所有这些特性在构建分布式系统时格外重要:
1. 线性化的原子操作:
    - 使用原子比较-设置操作，可以实现分布式加锁服务
    - 分布式锁通常实现为一个带有到期时间的租约，保证万一客户发生故障，可以最终释放锁
    - 锁和租约需要 fencing 令牌来防止客户端由于发生进程暂停而引发锁冲突
2. 操作全序
    - fencing 令牌确保每次加锁时数字总是单调增加的
    - Zookeeper 在实现该功能时，采用了**对所有操作执行全局排序**，然后为每个操作都赋予一个单调递增的事务ID(zxid)和版本号 cversion
3. 故障检测:
    - 客户端与Zookeeper节点维护一个长期会话，客户端会周期性地与Zookeeper服务节点互相交换心跳信息，会检查对方是否存活。
    - 即使出现闪断或者某些Zookeeper节点发生失效，会话仍处于活动状态
    - 但是，如果长时间心跳停止且超过了会话超时设置，Zookeeper 会声明会话失败，此时所有该会话持有的锁资源可以配置为自动全部释放
4. 更改通知:
    - 客户端不仅可以读取其他客户端所创建的锁和键值，还可以监视它们的变化
    - 因此客户端可以知道其他客户端何时加入集群，以及客户端是否发生故障
    - 通过订阅通知机制，客户端不需要频繁的轮询服务即可知道感兴趣对象的变化情况

在上述特征中，**只有线性化的原子操作才依赖共识**。

### 7.2 节点任务分配
Zookeeper 和 Chubby 非常适合如下场景: 
1. 如果系统由多个流程或服务的实例，并且需求其中的一个示例充当主节点，而如果主节点失效，由其他某个节点来接管
2. 对于一些分区资源，需要决定将哪个分区分配给哪个节点。当有新节点加入集群时，需要将某些现有分区从当前节点迁移到新节点，从而实现负载动态均衡。而当节点移除或失败时，其他节点还要接管失败节点

试图在数千个节点的集群上进行多数者投票会非常低效。Zookeeper通常是在固定数量的节点上运行投票，可以非常高效的支持大量的客户端。因此 Zookeeper 其实提供了一种将**跨节点协调服务**(包括共识，操作排序和故障检测)专业外包的方式。

通常情况下，Zookeeper 管理的数据变化非常缓慢。它不适合保存那些应用实时运行的状态数据，后者可能每秒产生数千甚至百万次更改。

### 7.3 服务发现
Zookeeper 和 etcd 还经常用于服务发现。可以这样配置服务，每当节点启动时将其网络端口信息向Zookeeper等服务注册，然后其他人只需向Zookeeper的注册表询问即可。

但是，服务发现是否需要达成共识还不太清楚。 DNS是查找服务名称的IP地址的传统方式，它使用多层缓存来实现良好的性能和可用性。从DNS读取是绝对不线性一致性的，如果DNS查询的结果有点陈旧，通常不会有问题【109】。 DNS的可用性和对网络中断的鲁棒性更重要。

尽管服务发现并不需要共识，但领导者选举却是如此。因此，如果你的共识系统已经知道领导是谁，那么也可以使用这些信息来帮助其他服务发现领导是谁。为此，**一些共识系统支持只读缓存副本**。这些副本异步接收共识算法所有决策的日志，但**不主动参与投票**。因此，它们能够**提供不需要线性一致性的读取请求**。

### 7.4 成员服务
Zookeeper等还可以看作是成员服务范畴的一部分。成员服务用来确定当前哪些节点处于活动状态并属于集群的有效成员。由于网络等原因无法可靠的检测一个节点究竟是否发生故障。但可以将故障检测和共识绑定在一起，让所有节点就节点的存活达成一致。

虽然可能存在误判，即节点其实处于活动状态，却被错误的宣判为故障。即便这样，系统就成员资格问题的决定是全体一致的，这是最重要的。例如选举主节点的方式可能是简单的投票选择编号最小的节点，一旦节点对于当前包含哪些成员出现了不同意见，那么共识过程就无法继续。

## 7.5 为什么要使用 Zookeeper
1. 要在多节点集群中达成共识，可以自己实现一个共识算法(很难)，所以可以直接使用 Zookeeper 提供的服务
2. Zookeeper 通常在固定数量的节点上运行投票，相比于在 1000 甚至更多的节点上达成共识效率更高

因此我们需要某种算法对写入的最终顺序进行确定，即达成共识。这就涉及到两个问题:
1. 如何达成共识
2. 如何让客户端感知到共识发生了变化

如果我们假设网络始终稳定，且不存在单点故障(类似单机情况下)通过锁就可以解决并发问题。但是这些问题无法避免单点故障可能导致数据丢失，这就需要多台机器提供冗余，此时就需要对同一项配置达成共识，我们需要共识算法。

共识算法需要解决的另一个问题是，当配置发生变化时，如何让客户端感知到共识发生了变化。我们可以让所有节点抖注册监听器，但是这样会引起惊群效应。因此我们只能让少量节点，即所谓的主节点注册监听器。然后通过版本矢量，让与主节点同步的从节点感知配置的变化。

kafka 为什么要引入 Zookeeper 是因为如果对所有 kafka 的节点都通过共识算法解决数据一致性问题，效率将非常低。数据一致性是以吞吐量为代价的。

## 8. 总结
事实证明，多个广泛的问题最终都可以归结为共识，并且彼此等价，这些等价问题包括；
1. 可线性化的比较-设置寄存器
2. 原子事务提交: 决定是否提交或中止分布式事务
3. 全序广播: 消息系统要决定以何种顺序发送消息
4. 锁与租约: 当多个客户端抢锁或租约时，决定哪一个成功
5. 成员/协调服务: 决定节点的存活状态
6. 唯一性约束: 多个事务在相同的主键上并发创建冲突资源时，决定哪一个能成功

简单的实现是只有一个主节点，有主节点负责所有的决策事宜。这样就可以提供线性化操作、唯一性约束、完全有序的复制日志等。

但是如果唯一的主节点故障或网络中断导致主节点不可达，这样就陷入停顿状态。有三种方法可以处理这个问题:
1. 系统停止服务，等待主节点恢复
    - 许多 XA/JTA 事务协调者采用这种方式
    - 本质上这种方法没有解决共识问题，因为它不满足终止性条件
    - 如果主节点无法恢复，系统就会永远处于停顿状态
2. 人为介入来选择新的主节点，并重新配置系统使之生效:
    - 本质上引入了一种**上帝旨意**的共识
    - 故障切换的速度取决于人类的操作
3. 采用算法自动选择新的主节点，需要一个共识算法

尽管如此，并不是每个系统都需要共识。例如无主复制和多主复制系统通常不支持全局共识。正因为如此，这些系统可能会发生冲突。但也可以接受或者寻找其他方案，处理冲突。

接下来的地方部分，我们将面向实际环境，讨论如何**基于异构模块**来构建强大的应用系统。