设计数据密集型应用—一致性与共识（9）

超、凢脫俗 2022-09-11 02:15 320阅读 0赞

### 文章目录 ###

*   *  1. 分布式系统中的错误
     *  2. 一致性保证
     *  3. 线性一致性
     *   *  2.1 什么使得系统线性一致
         *  2.2 线性一致性与可串行化
         *  2.3 依赖线性一致性
         *   *  2.3.1 锁定和领导者选举
             *  2.3.2 约束和唯一性保证
             *  2.3.3 跨信道的时序依赖
         *  2.4 实现线性一致性的系统
         *   *  2.4.1 单主复制（可能线性一致）
             *  2.4.2 共识算法（线性一致）
             *  2.4.3 多主复制（非线性一致）
             *  2.4.4 无主复制（也许不是线性一致的）
             *  2.4.5 线性一致性和法定人数
         *  2.5 线性一致性的代价
         *   *  2.5.1 CAP 定理
             *  2.5.2 线性一致性和网络延迟
     *  3. 顺序保证
     *   *  3.1 顺序与因果关系
         *   *  3.1.1 因果顺序不是全序的
             *  3.1.2 线性一致性强于因果一致性
             *  3.1.3 捕获因果关系
         *  3.2 序列号顺序
         *   *  3.2.1 非因果序列号生成器
             *  3.2.2 兰伯特时间戳
             *  3.2.3 光有时间戳还不够
         *  3.3 全序广播
         *   *  3.3.1 使用全序广播
             *  3.3.2 使用全序广播实现线性一致的存储
             *  3.3.3 使用线性一致性存储实现全序广播
     *  4. 分布式事务与共识
     *   *  4.1 原子提交与两阶段提交
         *   *  4.1.1 从单节点到分布式原子提交
             *  4.1.2 两阶段提交简介
             *  4.1.3 系统承诺
             *  4.1.4 协调者失效
             *  4.1.5 三阶段提交
         *  4.2 实践中的分布式事务
         *  4.3 容错共识
         *   *  4.3.1 共识算法和全序广播
             *  4.3.2 单领导者复制与共识
             *  4.3.3 纪元编号和法定人数
             *  4.3.4 共识的局限性
         *  4.4 成员与协调服务
         *   *  4.4.1 将工作分配给节点
             *  4.4.2 服务发现
             *  4.4.3 成员资格服务
     *  5. 碎碎念

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9ceOV0L6-1631278777058) ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 1. 分布式系统中的错误 ##

分布式系统中许多问题都可能引起故障，处理故障的方式：

*  简单的方式即让整个服务失效，并向用户显示错误信息。
 *  复杂的方式——服务自身具有容错功能，即使某些内部组件出现故障，服务也能正常运行。

构建容错服务的最好方式，是实现一些带有保证的通用抽象功能，然后让应用依赖这些保证。比如事务，通过使用事务，应用程序可以：

*  无需考虑崩溃前后的数据一致性
 *  无需考虑并发访问数据库的问题
 *  存储成功的数据是可靠

> 注：事务的抽象功能确保，即使发生崩溃、竟态条件和磁盘故障数据仍然是有效的。

**分布式系统最重要的抽象之一就是共识：让所有节点对某件事达成一致**。一旦达成共识，就可以有各种用途：

*  数据库节点可以使用共识来选举新的领导者。

## 2. 一致性保证 ##

在「复制延迟问题」中，提到因为数据库复制中发生的时序问题，导致的数据不一致现象。

*  比如，同一时刻查看两个数据库节点，则可能在两个节点上看到不同的数据，因为写请求可能在不同的时间到达不同的节点。

但是，大多数数据库都提供了最终一致性的功能，即停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读请求都会返回相同的值。

> 注：不一致性是暂时的，我们预计所有的副本最终会收敛到相同的值。

分布式一致性模型和前几章讨论的事务隔离级别的层次结构有一些相似。但是：

*  事务隔离主要是为了避免由于同时执行事务而导致的竞争状态
 *  分布式一致性主要是在面对延迟和故障时如何协调副本间的状态

## 3. 线性一致性 ##

在一个线性一致的系统中，只要一个客户端成功完成写操作，则所有客户端从数据库中读取数据必须能够看到刚刚写入的值。要维护数据的单个副本假象，系统应保障读到值时最近的，最新的，而不是来自陈旧的缓存或副本。

> 线性一致性也称为原子一致性、强一致性、立即一致性或外部一致性

非线性一致性的例子

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

*  Alice 和 Bob 正坐在同一个房间里，都盯着各自的手机，关注世界杯决赛的结果。在最后得分公布后
 *  Alice 刷新手机页面，看到了结果，并告知了 Bob
 *  Bob 刷新了自己的手机，但是他的请求路由到了一个落后的数据库副本上，手机显示比赛正在进行。

### 2.1 什么使得系统线性一致 ###

线性一致性背后的基本思想很简单：使系统看起来好像只有一个数据副本。以下例子展示线性一致性的复杂性：

**不做限制的读写并发请求，可能会导致返回值不一致的问题**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

*  客户端 A 的第一个读操作，完成于写操作开始之前，因此必须返回旧值 0
 *  客户端 A 的最后一个读操作，开始于写操作完成之后。
    
     *  如果数据库是线性一致性的，它必然返回新值 1
    
    > 注：因为读操作和写操作一定是在各自的起止区间的某个时刻被处理。如果写入结束后开始读取，则它必须看到写入的新值。
 *  与写操作的时间上重叠的任何读操作， 可能会返回 0 或 1 ，因为客户端并不知道读取时，写操作是否已经生效。这些操作是并发的。

**增加约束后的，系统的线性一致**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]

在一个线性一致的系统中，在 x 的值从 0 自动翻转到 1 的时候必定有一个时间点。因此，如果一个客户端读取返回新的值 1，即使写操作尚未完成，所有后续读取也必须返回新值。

> 注：上图的黑色箭头说明了时序依赖关系。是客户端 A 第一个读取新的值 1 的位置。在 A 的读取返回之后，B 开始新的读取。由于 B 的读取严格发生于 A 的读取之后，因此即使 C 的写入仍在进行中，也必然返回 1。

**增加比较并设置约束**

下图中的每个操作都在我们认为执行操作的时候用竖线标出。这些标记按顺序连在一起，其结果必然是一个有效的读取序列。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]

线性一致性的要求是，操作标记的连线总是按时间从左向右移动。这个要求去报了我们之前的保证：一旦新的值被写入或读取，所有后续的读都会看到写入的值，直到它被再次覆盖。

### 2.2 线性一致性与可串行化 ###

**可串行化**： 是事务的隔离属性，每个事务可以读写多个对象（行、文档、记录）。它确保事务的行为，与它们按照某种顺序依次执行的结果相同。

**线性一致性**： 是读取和写入单个对象的新鲜度保证。它不会将操作组合为事务，因此它不会阻止写入偏差等问题。

一个数据库可以提供可串行化和线性一致性，这种组合被称为严格的可串行化或强的单副本可串行化。基于两阶段锁定的可串行化实现或真的串行执行通常是线性一致性的。但是，可串行化的快照隔离不是线性一致性的：按照设计，它从一致的快照中进行读取，以避免读者和写者之间的锁竞争。一致性快照的要点就在于它不会包括该快照之后的写入，因此快照读取不是线性一致性的。

### 2.3 依赖线性一致性 ###

对于少数领域，线性一致是系统正确工作的一个先决条件。

#### 2.3.1 锁定和领导者选举 ####

在单主复制的系统，需要确保领导者只存在一个，而不是有多个领导者出现了脑裂现象。

*  一种选择领导者的方法是使用锁：每个节点在启动时尝试获取锁，成功获取锁的即为领导者。该锁是线性一致的，所有节点必须就哪个节点拥有锁达成一致。

例如 Apache ZooKeeper 和 etcd 的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作。

> 注：严格地锁，ZooKeeper 和 etcd 提供线性一致性的写操作，但读取可能是陈旧的，因为默认情况下，它们可以由任何一个副本提供服务。但是仍然可以选择请求线性一致性读取：etcd 称之为法定人数读取。

#### 2.3.2 约束和唯一性保证 ####

唯一性约束在数据库中很常见：

*  用户名或电子邮件地址必须唯一标识一个用户
 *  确保银行账户余额永远不会是负数
 *  不会出售比仓库的存货更多的物品
 *  不会两个人都预定了航班或剧院里同一时间的同一个位置。

> 注：以上都需要线性一致性。

#### 2.3.3 跨信道的时序依赖 ####

假设有一个网站，用户可以上传照片，一个后台进程会调整照片大小，降低分辨率以加快下载速度。该系统的架构和数据流如下图所示：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]

上图存在一种竞争条件的可能：

*  假设消息队列比存储服务内部复制的更快
 *  这种情况的出现的时候，当缩放器读取图片（步骤5）时，可能会看到图像的旧版本，或者什么都没有。
 *  如果从文件存储中拿到的是旧版本的数据，则全尺寸的图和缩略图就产生了永久的不一致。

> 注：出现这个问题的原因是 Web 服务器和缩放器之间存在两个不同的信道。

### 2.4 实现线性一致性的系统 ###

线性一致性本质上意味着：表现得好像只有一个数据副本，而且所有的操作都是原子的。所以最简单的答案就是，真的只用一个数据副本，但是这种方法无法容错：如果该副本的节点失效，数据将会丢失。

使系统容错最常见的方法就是复制。

#### 2.4.1 单主复制（可能线性一致） ####

在具有单主复制功能的系统中，主库具有用于写入数据的主副本，而追随者在其他节点上保留数据的备份副本。如果从主库或同步更新的从库读取数据，它们可能是线性一致的。

> 注：对单主数据库进行分区（分片），使得每个分区有一个单独的领导者，不会影响线性一致性，因为线性一致性只是对单一对象的保证。

#### 2.4.2 共识算法（线性一致） ####

共识算法与单领导者复制类似。然而，共识协议包含防止脑裂和陈旧副本的措施。所以，共识算法被 Zookeeper 和 etcd 的使用。

#### 2.4.3 多主复制（非线性一致） ####

具有多主程序复制的系统通常不是线性一致的，因为它们同时在多个节点上处理写入，并将其异步复制到其他节点。因此，它们可能会产生需要被解决的写入冲突。

#### 2.4.4 无主复制（也许不是线性一致的） ####

对于无领导者复制的系统（Dynamo），在法定人数的读写（w+r > n ）的情况下，可以获得「强一致性」。但是这取决于法定人数的具体配置，以及强一致性如何定义。

基于时钟的（Cassandra）的「最后写入胜利」冲突解决方法几乎可以确定是非线性一致的，由于时钟偏差，不能保证时钟的时间戳与实际事件顺序一致。

> 注：宽松的法定人数也会破坏线性一致性的可能。

#### 2.4.5 线性一致性和法定人数 ####

直觉上在 Dynamo 风格的模型中，严格的法定人数读写应该是线性一致的。但是当网络延迟是，就可能存在竞争条件：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]

*  Writer 客户端向三个副本发送写入 x=1 的请求
 *  Reader A 并发从两个节点读取数据（满足法定人数限制），并在其中一个节点看到新值 1
 *  Reader B 也并发从两个节点读取数据，并从两个节点中返回旧值 0

法定人数条件满足，但是这个执行确是非线性的：B 的请求在 A 的请求完成后开始，但是 B 返回旧值，而 A 返回新值。

### 2.5 线性一致性的代价 ###

对多数据中心的复制而言，多主复制通常是理想的选择。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]

考虑这样的情况：如果两个数据中心之间发生网络中断？

*  使用多主数据库，每个数据中心都可以继续正常运行：由于在一个数据中心写入的数据是异步复制到另一个数据中心，所以在恢复网络连接时，写入操作只是简单地排队并交换。
 *  单主配置的条件下，如果数据中心之间的网络被中断，则无法对数据库执行任何写入，从而导致应用不可用。

> 注：假设每个数据中心内的网络正常工作，客户端可以访问数据中心，但数据中心之间无法互相连接。

#### 2.5.1 CAP 定理 ####

CAP 即一致性、可用性和分区容错性。其三者只能选择其二。在发生网络故障时，必须在线性一致性和整体可用性之间做出选择。

> 注：不幸的是，这种说法很有误导性，因为网络分区是一种故障类型

#### 2.5.2 线性一致性和网络延迟 ####

虽然线性一致是一个很有用的保证，但是实际上，线性一致性的系统惊人的少。比如，现代多核 CPU 上的内存甚至都不是线性一致的。

如果一个 CPU 核上运行的线程写入某个内存地址，而另一个 CPU 核上运行的线程不久之后读取相同的地址，并不能保证一定能读取到第一个线程写入的值。（除非使用内存屏障）。

这种行为的原因是每个 CPU 核都要自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，任何变更会异步写入主存。

许多分布式数据库也是如此\*\*：为了提高性能而选择牺牲线性一致性，而不是为了容错。\*\*

## 3. 顺序保证 ##

顺序是一个重要的概念，因此在本书中反复被提到过：

*  在第五章中，领导者在单主复制中的主要目的就是，在复制日志中确定写入顺序——也就是从库应用这些写入的顺序。如果存在不止一个领导者，则并发操作可能会导致写入冲突。
 *  在第七章中讨论的可串行化，是关于事务表现得像按某种先后顺序执行的保证。它可以字面意义上地以串行顺序执行事务来实现，或运行并行执行，但同时防止序列化冲突来实现。
 *  在第八章中讨论过的在分布式系统中使用时间戳和时钟是另一种将顺序引入无序世界的尝试，例如，确定两个写入操作哪个更晚发生。

### 3.1 顺序与因果关系 ###

顺序反复出现有以下原因：

*  顺序有助于保持因果关系，因果关系对事件施加了一种顺序：因在果之前，消息发送在消息收取之前。
    
    > 注：如果一个系统服从因果关系所规定的顺序，则其是**因果一致**的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，一定能到其因果前驱。

#### 3.1.1 因果顺序不是全序的 ####

**全序**：允许任意两个元素进行比较，如果有两个元素，总可以说出哪个更大，哪个更小。例如，自然数集是全序的。

**偏序**：数学集合是偏序的，比如 \{a, b\} 和 \{b, c\} 是没有办法比较大小的。在某些情况下，可以说一个集合大于另一个（在一个集合包含另一个集合的所有元素的情况下），其他情况下是无法比较的。

全序和偏序之间的差异反映在不同的数据库一致性模型中：

**线性一致性**

在线性一致的系统中，操作是全序的。即系统表现得好像只有一个数据副本，并且所有操作都是原子的，这意味着对任何两个操作，总能判断哪个操作先发生。

**因果性**

如果两个时间是因果相关的（一个发生在另一个事件之前），则它们之间是有序的，但如果它们是并发的，则它们之间的顺序是无法比较的。这意味着因果关系定义了一个偏序，而不是全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

> 注：这句话太难理解了。线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。

#### 3.1.2 线性一致性强于因果一致性 ####

那么因果顺序和线性一致性之间的关系是什么？

答案：线性一致性隐含着因果关系：任何线性一致的系统都能正确保持因果性。特别是，如果系统中有多个通信通道，线性一致性可以自动保证因果性，系统无需任何特殊操作。

线性一致性确保因果性的事实使线性一致系统变得简单易懂，更有吸引力。然而，正如线性一致性的代价中所讨论的，使系统线性一致可能会损害其性能和可用性，尤其是在系统具有严重的网络延迟的情况下。但是线性一致性并不是保持因果性的唯一途径——还有其他方法。一个系统可以使因果一致的，而无需承担线性一致性带来的性能折损。实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行性最强的一致性模型。而且在网络故障时仍能保持可用。

**在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一致性，且性能与可用性与最终一致的系统类似。**

#### 3.1.3 捕获因果关系 ####

用于确定哪些操作发生在其他操作之前的技术，与我们在检测并发写入中所讨论的内容类似。在无领导这数据存储中的因果性：为了防止丢失更新，需要检测对同一个键的并发写入。因果一致性则更进一步：它需要跟踪整个数据库中的因果依赖，而不是仅仅一个键。

为了确定因果顺序，数据库需要知道应用读取了哪个版本的数据。比如将先前操作的版本号在写入时传回到数据库。

### 3.2 序列号顺序 ###

虽然因果是一个重要的理论概念，但实际上跟踪所有的因果关系是不切实际的。更好的方法是使用序列号或时间戳来排序事件。时间戳不一定来自日历时钟，它可以是一个逻辑时钟，一个用来生成标识操作数字序列的算法，典型是使用一个每次操作自增的计数器。

在单主复制的数据库中，复制日志定义了与因果一致的写操作。主库可以简单地为每个操作自增一个计数器，从而为复制日志中的每个操作分配一个单调递增的序列号。如果从库按照它们在复制日志中出现的顺序来应用写操作，那么从库的状态始终是因果一致的。

#### 3.2.1 非因果序列号生成器 ####

序列号生成器的几种方式：

*  每个节点都可以生成自己独立的一组序列号。例如有两个节点，一个节点只生成奇数，而另一个节点只生成偶数。
 *  可以将日历时钟的时间戳附加到每个操作上。这种时间戳并不连续，但是如果它具有足够高的分辨率，那也许足以提供一个操作的全序关系。这一事实应用于「最后写入胜利」的冲突解决方法中。
 *  可以预先分配序列号区块。例如，节点 A 可能要求从序列号 1 到 1000 区块的所有权，而节点 B 可能要求序列号 1001 到 2000 区块的所有权。然后每个节点可以独立分配所属区块中的序列号，并且在序列号不足时分配一个新的区块。

> 注：以上这些序列号生成器不能正确的捕获节点的操作顺序，所以会出现因果关系的问题。

#### 3.2.2 兰伯特时间戳 ####

兰伯特时间戳，莱斯特·兰伯特于1978年提出的，现在是分布式系统领域被引用最多的论文之一。

兰伯特时间戳与物理的日历时钟没有任何关系，但是它提供一个全序：如果有两个时间戳，则计数器值大者有更大的时间戳。如果计数器值相同，则节点 ID越大的，时间戳越大。

> 注：使兰伯特时间戳因果一致的关键思想如下所示：每个节点和客户端跟踪迄今为止所见到的最大计数器值，并在每个请求中包含这个最大计数器的值。当一个节点收到最大计数器值大于自身计数器值的请求或响应是，它立即将自己的计数器设置为这个最大值。
> 
> 兰伯特时间戳有时会与「检测并发写入」中看到的版本向量相混淆。但是它们有着不同的目的：版本向量可以区分两个操作是并发的，还是一个因果依赖另一个，而兰伯特时间戳总是全序的。

#### 3.2.3 光有时间戳还不够 ####

**虽然兰伯特时间戳定义了一个与因果一致的全序，但它还不足以解决分布式系统中的常见问题。**

考虑一个需要确保用户名能唯一标识用户账户的系统。如果两个用户同时尝试使用相同的用户名创建用户，则其中一个应该成功，另一个应该失败。

在多节点的情况下，为了确保没有其他节点正在使用相同的用户名和较小的时间戳并发创建同名账户，必须检查每个节点。如果其中一个节点由于网络问题出现故障或不可达，则整个系统可能被拖至停机。

> 注：总之，为了实现诸如用户名的唯一约束这种东西，仅有操作的全序是不够的，还需要知道全序何时会尘埃落定。

### 3.3 全序广播 ###

如果你的程序只运行在单个 CPU 核上，那么定义一个操作全序是很容易的：可以简单地就 CPU 执行这些操作的顺序。但是在分布式系统中，让所有节点对同一个全局操作顺序达成一致可能相当棘手。

> 顺序保证的范围
> 
> 每个分区各有一个主库的分区数据库，通常只在每个分区内维持顺序，这意味着它们不能提供跨分区一致性保证。跨所有分区的全序是可能的，但需要额外的协调。

全序广播通常被描述为在节点间交换消息的协议。它需要满足两个安全属性：

*  可靠交付：没有消息丢失，如果消息被传递到一个节点，它将被传递到所有节点
 *  全序交付：消息以相同的顺序传递给每个节点

#### 3.3.1 使用全序广播 ####

全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将保持一致。这个原理被称为状态机复制。

全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将先前消息插入顺序中的较早位置。这个试试使得全序广播比时间戳排序更强。

#### 3.3.2 使用全序广播实现线性一致的存储 ####

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达。相比之下，线性一致性是新鲜性的保证：读取一定能看到最新的写入值。

如果有了全序广播，则可以在此基础上构建线性一致的存储。例如，可以确保用户名能唯一标识用户账户。

可以通过将全序广播当成仅追加日志的方式来实现这种线性一致的 CAS 操作：

*  在日志中仅追加一条消息，试探性地指明你要声明的用户名
 *  读日志，并等待你刚才追加的消息被读回
 *  检查是否有任何消息声称目标用户名的所有权

#### 3.3.3 使用线性一致性存储实现全序广播 ####

上一节介绍了如何从全序广播构建一个线性一致的 CAS 的操作。我们可以将其反过来，基于线性一致的存储，构建全序广播。

最简单的方法就是假设有一个线性一致的寄存器来存储一个整数，并且有一个原子自增并返回的操作。这种算法很简单：每个要通过全序广播发送的消息首先对线性一致寄存器执行并自增返回操作。然后将该寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点，而收件人将按需要依次传递消息。

可以证明，线性一致的 CAS 寄存器与全序广播都有等价共识问题。也就是说，你能解决其中的一个问题，你可以把它转化为其他问题的解决方案。

## 4. 分布式事务与共识 ##

共识是分布式计算中最重要的也是最基本的问题之一。其目标是让几个节点达成一致。

节点能达成一致，在许场景下都非常重要，例如：

**领导选举**：在单主复制的数据库中，所有节点需要就哪个节点是领导者达成一致。如果一些节点由于网络故障而无法与其他节点通信，则可能会对领导权的归属引起争议。在这种情况下，共识对于避免错误的故障切换非常重要。

**原子提交**：在支持跨多节点或跨分区事务的数据库中，一个事务可能会在某些节点上失败，但在其他节点上成功。要维护事务的原子性，必须让所有节点对事务的结果达成一致：要么全部中止/回滚，要么它们全部提交。

> 注：原子提交的形式化与共识稍有不同：原子事务只有在所有参与者提交的情况下才能提交，如果有任何参与者需要中止，则必须中止。共识则允许就任意一个被参与者提出的候选值达成一致。然而，原子提交和共识可以互相简化对方。

### 4.1 原子提交与两阶段提交 ###

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

对于在单个数据库节点执行的事务，原子性通常由存储引擎实现。当客户端请求数据库节点提交事务时，数据库将使事务的写入持久化，然后将提交记录追加到磁盘中的日志里。

但是，如果一个事务涉及多个节点呢？

在这些情况下，仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况：提交在某些节点成功，而在其他节点失败。

#### 4.1.2 两阶段提交简介 ####

两阶段提交时一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。它是分布式数据库中的经典算法。2PC 在某些数据库内部使用，也以 XA 事务的形式对应用可用。（比如：Java Transaction API支持）

> **不要把2PC和2PL搞混了**
> 
> 两阶段提交和两阶段锁定时两个完全不同的东西。两阶段提交在分布式数据库中提供原子提交，而两阶段锁定提供可串行化的隔离等级。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 8]

当应用准备提交时，协调者开始阶段1：它发送一个准备请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应。

*  如果所有参与者都回复：是，则表示它们已经准备好提交，协调者在阶段 2 发出提交请求，然后提交
 *  如果任意一个参与者回复：否，则协调者在阶段 2 中向所有节点发送中止

#### 4.1.3 系统承诺 ####

上述描述并没有说清楚为什么两阶段提交保证了原子性，而跨多个节点的一阶段提交却没有：

为了理解它的工作原理，详细分析其过程：

*  当应用想要启动一个分布式事务时，它向协调者请求一个事务 ID。该事务 ID全局唯一
 *  应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务 ID。所有的读写都是在这些单节点中各种完成的。如果在这个阶段出现任何问题，则协调者或任何参与者都可以中止
 *  当应用准备提交时，协调者向所有参与者发送一个准备请求，并打上全局事务 ID 的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务 ID 的中止请求。
 *  参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘以及检查是否存在任何冲突或违反约束。通过向协调者回答「是」，节点承诺，只要请求，这个事务一定可以不出差错的提交。
 *  当协调者收到所有准备请求的答复时，会就提交或中止事务作明确的决定。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所有的决定。这被称为提交点。
 *  一旦协调者决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。如果参与者在此执行期间崩溃，事务将在其恢复后提交—由于参与者投了赞成，因此恢复后它不能拒绝提交。

#### 4.1.4 协调者失效 ####

如果协调者在发送准备请求之前失败，参与者可以安全中止事务。但是，一旦参与者收到了准备请求并回复：是，就不能再单方面放弃—必须等待协调者回答事务是否已经提交或中止。

> 注：如果此时参与者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为存疑或不确定的。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 9]

完成 2PC 的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取事务日志来确定所有存疑事务的状态。

#### 4.1.5 三阶段提交 ####

两阶段提交被称为阻塞原子提交协议，因为存在 2PC 可能卡住并等待协调者恢复的情况。作为 2PC 的替代方案，已将提出了一种被称为三阶段提交算法（3PC）。然而，3PC 假定网络延迟有界，节点响应时间有限；在大多数具有无限网络延迟和进程暂停的实际系统中，它并不能保证原子性。

### 4.2 实践中的分布式事务 ###

分布式事务的名声毁誉参半，尤其是那些通过两阶段提交实现的。一方面，它被视作提供了一个难以实现的重要的安全性保证；另一方面，它们容易导致运维问题，造成性能下降，做出超过能力范围的承诺而饱受批评。

两种容易被混淆的分布式事务类型：

**数据库内部的分布式事务**

一些分布式数据库支持数据库节点之间的内部事务。例如，VoltDB 和 MySQL Cluster 的 NDB 存储引擎就有这样的内部事务支持。在这种情况下，所有参与事务的节点都运行相同的数据库软件。

**异构分布式事务**

在异构事务中，参与者是由两种或两种以上的不同技术组成的：例如来自不同供应商的两个数据库，甚至是非数据库系统（如消息代理）。跨系统的分布式事务必须确保原子提交，尽管系统可能完全不同。

**恰好一次的消息处理**

异构的分布式事务处理能够以强大的方式集成不同的系统。例如：消息队列中的一条消息可以被确认为已处理，当且仅当用于处理消息的数据库事务成功提交。这是通过在同一个事务中原子提交消息确认和数据库写入两个操作来实现的。由分布式事务的支持，即使消息代理和数据库是在不同的机器上运行的两种不相关的技术，这种操作也是可能的。

**XA 事务**

是跨异构技术实现两阶段提交的标准。它于 1991 年推出并得到广泛的实现：许多传统关系数据库（包括 PostgreSQL、MySQL、DB2、SQL Server和Oracle）和消息代理（包括ActiveMQ、HornetQ、MSMQ 和 IBM MQ）都支持 XA

XA 不是一个网络协议—它只是一个用来与事务协调者连接的 C API。事务协调者需要实现 XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中。它在事务中跟踪所有的参与者，并在要求它们准备之后收集参与者的响应，并使用本地磁盘上的日志记录每次事务的决定（提交/中止）。

**怀疑时持有锁**

问题在于锁。正如在「读已提交」中所讨论的那样，数据库事务通常获取待修改行上的行级排他锁，以防止脏写。此外，如果要使用可串行化的隔离等级，则使用两阶段锁定的数据库也必须为数据库所读取的行加上共享锁。

在事务提交或中止之前，数据库不能释放这些锁。因此，在使用两阶段提交时，事务必须在整个存疑期间持有这些锁。如果协调者已经崩溃，需要 20 分钟才能重启，那么这些锁将会被持有 20 分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有——或至少在管理员手动解决该情况之前。

**从协调者故障中恢复**

理论上，如果协调者崩溃并重新启动，它应该干净地从日志中恢复其状态，并解决存疑事务。然而在实践中，**孤立**的存疑事务确实会出现，即无论处于何种理由，协调者无法确定事务的结果。唯一的出路是让管理员手动决定提交还是回滚事务。管理员必须检查每个存疑事务的参与者，确定是否有任何参与者已经提交或中止，然后将相同的结果应用到其他参与者。解决这类问题可能需要大量的人力，并且可能发生严重的生产期间的中断。

**分布式事务的限制**

XA 事务解决了保持多个参与者相互一致的现实和重要的问题，但正如我们所看到的那样，它也引入了严重的运维问题。特别来讲，这里的核心认识是：事务协调者本身就是一种数据库（存储了事务的结果），因此需要像其他重要数据库一样小心地打交道。

### 4.3 容错共识 ###

共识问题通常形式化为：一个或多个节点可以提议某些值，而共识算法决定采用其中的某些值。比如剧院中的统一座位，当几个顾客同时试图订购最后一个座位时，处理顾客的请求的每个节点可以提议将服务的顾客的 ID 作为决策的关键

共识算法必须满足以下性质：

*  一致同意：没有两个节点的决定不同
 *  完整性：没有节点决定两次
 *  有效性：如果一个节点决定了值 v，则 v 由某个节点所提议
 *  终止：由所有未崩溃节点来最终决定值

每种性质的解释如下：

一致同意和完整性属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。

有效性属性主要为了排除平凡的解决方案。例如，无论提议什么值，你都可以有一个始终决定值为 null 的算法。

终止属性形式化了容错的思想。它实质上说的是，一个共识算法不能简单地永远闲做等死——换句话说，它必须取得进展。

#### 4.3.1 共识算法和全序广播 ####

最著名的容错共识算法是视图戳复制（VSR），Paxos、Raft、以及 Zab 。这些算法之间有不少的相似之处，但是它们并不同。本节不会介绍其详细细节，了解一些它们共同的高级思想通常已经足够了。

大多数这些算法实际上并不直接使用这些描述的形式化模型。取而代之的是，它们决定了值的顺序，这使它们成为全序广播算法。全序广播算法要求消息按照相同的顺序，恰好传递一次，准确传送到所有节点。如果仔细思考，这相当于进行了几轮共识：在每一轮中，节点提议下一条要发送的消息，然后决定在全序中下一条要发送的消息。

所以，全序广播相当于重复进行多轮共识：

*  由于一致同意属性，所有节点决定以仙童的顺序传递相同的消息
 *  由于完整性属性，消息不会重复
 *  由于有效性属性，消息不会被破坏，也不能凭空编造
 *  由于终止属性，消息不会丢失

#### 4.3.2 单领导者复制与共识 ####

在第五章中，讨论了单领导者复制，它将所有写入的操作都交给主库，并以相同的顺序将它们应用到从库，从而使副本保持在最新状态。这实际上就是一个全序广播。

如何选择领导者？

如果主库是由运维人员手动选择和配置的，那么实际上拥有一种独裁类型的共识算法：只有一个节点被允许接受写入，如果该节点故障，则系统无法写入，直到运维手动配置其他节点作为主库。

> 注：上述的系统在实践中可以表现良好，但它无法满足共识的终止属性，它需要人为干预才能取得进展。

一些数据库会自动执行领导者选举和故障切换，如果旧主库失效，会提拔一个从库为新主库。这使我们向容错的全序广播更进一步，从而达成共识。

#### 4.3.3 纪元编号和法定人数 ####

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义一个纪元编号（在 Paxos 中称为投票编号，视图戳复制中的视图编号，以及 Raft 中的任期号码），并确保每个时代中，领导者都是唯一的。

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的纪元编号，因此纪元编号是全序单调递增的。如果两个不同的时代的领导者之间出现冲突，那么带有更高纪元编号的领导说的算。在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高纪元编号的领导者。

> 注：领导者必须获得「法定人数」的节点的投票。对于领导者要做出的每一个决定，都必须将体移植发送给其他所有节点，并等待「法定人数」的节点响应并赞成提案。「法定人数」通常（但不总是）由多数节点组成，只有在没有意识到任何带有更高纪元编号的领导者的情况下，一个节点才会投票赞成提议。
> 
> 投票过程表面看起来很像两阶段提交。最大的区别在于，2PC 中协调者不是由选举产生的，而且2PC 要求所有参与者投赞成票，而容错共识算法只需要多数节点的投票。

#### 4.3.4 共识的局限性 ####

*  共识系统总是需要严格多数来运转。如果网络故障切断了某些节点同其他节点的连接，则只有多数节点所在的网络可以继续工作，其余部分将被阻塞。
 *  大多数共识算法假定参与投票的节点是固定的集合，这意味着你不能简单的在集群中添加或删除节点。
 *  共识系统通常依靠超时来检测失效的节点。在网络延迟高度变化的环境中，特别是在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。

### 4.4 成员与协调服务 ###

Zookeeper 和 etcd 被设计为容纳少量完全可以放在内存中的数据，所以不会将所有应用数据放在这里。这些少量数据会通过容错的全序广播算法复制到所有节点上。正如前文锁讨论的，数据库复制需要的就是全序广播：如果每条消息代表对数据库的写入，则以相同的顺序应用相同的写入操作可以使副本之间保持一致。

**线性一致性的原子操作**

使用原子 CAS 操作可以实现锁：如果多个节点同时尝试执行相同的操作，只有一个节点会成功。共识协议保证了操作的原子性和线性一致性，即使节点发生故障或网络在任意时刻中断。分布式锁通常以「租约」的形式实现，租约有一个到期时间，以便在客户端失效的情况下最终能被释放。

**操作的全序排列**

当某个资源受到锁或租约的保护时，需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。防护令牌是每次锁被获取时单调增加的数字。Zookeeper 通过全序化所有操作来提供这个功能，它为每个操作提供一个单调递增的事务ID和版本号。

**失效检测**

客户端在 Zookeeper 服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检测节点是否还活着。即使连接暂时中断，或者 ZooKeeper 节点失效，会话仍保持在活跃状态。但如果心跳停止的持续时间超出了会话时，Zookeeper 会宣告该会话已死亡。

**变更通知**

客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。因此，客户端可以知道另一个客户端何时加入集群或故障。通过订阅通知，客户端不再通过频繁轮询的方式来找出变更。

#### 4.4.1 将工作分配给节点 ####

Zookeeper/Chubby 模型运行良好的例子

*  如果有你有几个进程实例或服务，需要选择其中一个实例作为主库或首选服务。如果领导者失败，其他节点之一应该接管。
 *  当你有一些分区资源（数据库、消息流、文件存储、分布式 Actor 系统等），并需要决定哪个分区分配给哪个节点是。以及当新节点加入集群时，需要将某些分区从现有节点移动到新节点，以便重新平衡负载。当节点被移除或失效时，其他节点需要接管失效节点的工作。

这类任务可以通过在 Zookeeper 中明智地使用原子操作，临时节点与通知来实现。

#### 4.4.2 服务发现 ####

Zookeeper、etcd 和 Consul 也经常用于服务发现——也就是找出你需要连接到哪个 IP 地址才能到达特定的服务。在云数据中心环境中，虚拟机来来往往很常见，通常不会事先知道服务的 IP 地址。相反，可以配置你的服务，使其在启动时注册服务注册表中的网络端点，然后可以由其他服务找到它们。

> 注：向 Zookeeper 这样的工具为应用提供了「外包」的共识、故障检测和成员服务。它们扮演了重要的角色，虽说使用不易，但总比自己开发一个能经受第八章中所有问题考验的算法要好得多。

#### 4.4.3 成员资格服务 ####

成员资格服务确定哪些节点当前处于活动状态并且是集群的活动成员。正如我们在第八章中看到的那样，由于无限的网络延迟，无法可靠地检测到另一个节点是否发生故障。但是，如果通过共识来进行故障检测，那么节点就哪些节点应该被认为是存在或不存在达成一致。

即使它确实存在，仍然可能发生一个节点被共识错误地宣告死亡。但是对于一个系统来说，知道哪些节点构成了当前的成员关系是非常有用的。例如，选择领导者可能意味着简单地选择当前成员中编号最小的成员

## 5. 碎碎念 ##

赶在中秋的假期前把笔记整理好啦，就阔以开开心心的过节了。

*  好不容易来到这个世界上，一定要找到一件让你庆幸你出生的事，一件需要你去做，你愿意竭尽全力去做的事。
 *  人一到群体中，智商就严重降低，为了获得认同，个体愿意抛弃是非，用智商去换取那份让人备感安全的归属感。
 *  因为年少，总觉得前面的时间很长，长得一切皆有可能重新来过，却不知道时光的河，只能往前流，从来没有重新来过。

请务必要继续加油。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/a47775ed8c1e4acab6be42d5a23e1ede.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/c48cb4060524476697de78de8aadb482.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220829/aa5288eeac4c4dd1b5b014a39555672f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220829/a889e30eae0a42b8b57371dded8dcb12.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]: /images/20220829/fe0967a158c94abe9f2089cb1eb4199a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]: /images/20220829/fa6f17b1efa24513a151d838405c10e4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]: /images/20220829/16946b26e89e4f39ae8eafc3852577e0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]: /images/20220829/9906fd4325da457abdd5a7a48d9739cf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 8]: /images/20220829/a960a48dc216499f9046d37a79f3ed9f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAcGhhbnRvbV8xMTE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 9]: /images/20220829/46f8ddeaa2d54060a036c484df3f7b05.png