刘芷溢

最近更新

容错共识与 Paxos

创建于更新于24分钟阅读

容错共识与 Paxos

一、为什么需要容错共识？

回顾 GFS（Google File System）中的协调者：

  • 如果协调者发生故障怎么办？
  • GFS 论文对这种情况没有给出太多解释。
  • 许多服务构建在 GFS 之上，因此故障恢复应当是自动且可靠的。
  • 应该如何实现？

一个好的系统应该具备的总体目标

1. 通过复制实现高可用性（High Availability）

  • 即使一台服务器崩溃或无法通信，系统仍然能够继续运行。
  • 不存在单点故障（Single Point of Failure）。

2. 强一致性（Strong Consistency）

  • 整个系统对外应该表现得像只有一台服务器一样。

为什么设计容错协调者很困难？

假设我们希望使用主备复制（Primary/Backup Replication）：当主服务器发生故障时，客户端应该切换到备份服务器。

考虑一个有问题的方案：

C1、C2：客户端
S1：主服务器
S2：备份服务器

C1 ─────── S1（Primary）
             │
             │ Replication
             ▼
C2 ─────── S2（Backup）

正常情况下：

  1. 客户端将所有操作发送给 S1。
  2. S1 回复客户端，同时将操作转发给 S2 进行复制。
  3. S1 是 Primary，S2 是 Backup。
  4. 如果客户端无法收到 S1 的回复，就将请求重新发送给 S2。

这样，系统似乎能够容忍 S1 发生故障。

问题：如果发生网络故障呢？

假设：

  • C1 和 S1 可以相互通信。
  • C2 和 S2 可以相互通信。
  • 但是 C1/S1 无法与 C2/S2 通信。

此时，网络被分割成两个互不通信的部分。

在两边看来，对方似乎都已经发生故障。

因此：

  • S1 仍然认为自己是 Primary。
  • S2 也开始作为 Primary 独立运行。

这种情况叫作：

  • 网络分区（Network Partition）
  • 脑裂（Split Brain）

计算机无法区分“服务器崩溃”和“网络断开”。

它们唯一能够观察到的现象是：

我的请求没有收到响应。

这个问题会在容错系统设计中反复出现！

自动故障切换曾经被认为是不可能的

由于网络分区的存在，人们曾经认为自动容错切换无法实现。

因此，会使用特殊的外部代理（例如人工操作）来切换主服务器。

但这种方案：

  • 本身存在单点故障。
  • 不适合大规模系统。

大约在 1989 年，出现了一些解决方案。

其中，Paxos 是最简单、最容易理解的方案。

它启发了许多广泛使用的协议。

二、Paxos 解决什么问题？

Paxos 提供容错的共识（Consensus）。它允许一组计算机对某个值达成一致。

例如：谁是当前的 Primary？

如果一些 Paxos 参与者已经对值 X 达成一致，那么其他参与者就不会认为另一个不同的值已经被确定。

即使出现计算机故障或网络故障，这一性质仍然成立。

因此，即使发生网络分区，也不会出现脑裂。

需要注意：

基本 Paxos 只执行一次共识，而实际系统需要一系列 Paxos 共识过程。

例如，每次协调者发生故障后，都需要重新进行一次共识，以恢复系统运行。

三、Paxos 的核心思想：Quorum（法定多数）

Paxos 的一个关键思想是 Quorum。

假设系统拥有三台服务器：

S1       S2       S3

      3 Servers

服务器数量通常为奇数，例如 3 台。

任何操作都需要获得多数服务器的响应。

对于 3 台服务器：，即至少需要 2 台服务器同意。

如果无法联系到多数服务器，系统就不能继续取得进展。

注意：Quorum 的思想比 Paxos 早得多。

1. 多数派的一个重要性质：任意两个多数派必然相交

假设某个信息已经被多数服务器知道。

那么之后任何一个多数派中，必定至少包含一台知道该信息的服务器。

因此，Quorum 系统中的每个步骤通常类似于：

  1. 向所有参与者发送消息。
  2. 收集多数服务器的响应，不必等待其余服务器。
  3. 检查这些响应，找到最新的状态。
  4. 将更新后的状态发送给所有参与者。

这种机制有两个好处：

  • 可以容忍少数服务器故障或响应缓慢。
  • 多数派之间的交集确保状态变更不会丢失。

2. 多数派的另一个重要性质

最多只有一个网络分区能够包含多数服务器。

处于少数派分区的服务器无法形成 Quorum，因此不能继续推进操作。

于是，最多只有一个分区可以执行需要 Quorum 的操作。

这有助于避免脑裂。

注意：多数派是相对于所有服务器而言的，而不是相对于当前存活的服务器而言的。

3. 容错能力

对于 台服务器，系统能够容忍 台服务器发生故障。

因为剩余的 台仍然构成多数派。

服务器总数可容忍故障数所需多数派
312
523
734

增加服务器数量可以提高系统的可用性，但需要付出一定代价。

四、Paxos 保证哪些性质？

1. 正确性（Correctness）

  • 如果已经达成共识，那么所有达成共识的服务器都同意相同的值。
  • 一旦达成共识，系统就不会改变已经确定的值。

2. 容错性（Fault Tolerance）

只要 台服务器中有 台能够相互通信，系统就能够继续运行。

也就是说，最多可以容忍 台服务器发生故障。

如果不存在多数派：

  • 系统无法继续推进共识。
  • 但是当至少 台服务器重新可用时，系统可以正确恢复运行。

例如，系统能够从整个站点的断电故障中恢复。

3. 活性（Liveness）

如果多数服务器能够持续通信足够长的时间，Paxos 最终能够达成共识。

这是一个相对较弱的性质。

五、Paxos 算法

下面开始研究 Paxos 算法。

这是论文中的一个伪代码版本。

为了处理共识协议执行过程中可能发生的故障，Paxos 可能经历多个带编号的轮次（Round）。

每个轮次由一个 Proposer（提议者）驱动。

如果任意服务器认为共识尚未达成，它都可以发起提议。

每个轮次包含两轮消息交互：

  • prepare → prepare_ok
  • accept → accept_ok

关键定义

定义 1：服务器 S 接受了 n/v

指服务器 S 收到 accept(n, v) 后，回复了 accept_ok。

其中：

  • n：提议编号。
  • v：提议的值。

定义 2：n/v 被选定（Chosen）

指多数服务器已经接受了 n/v。

最重要的性质

如果值 v 已经被选定，那么之后任何一次成功选定的值也必须是 v。

协议永远不会改变已经做出的决定。

即使：

  • 后续由不同的 Proposer 发起提议。
  • 提议编号发生变化。

最终被选定的值仍然必须相同。

但这里存在一个困难：

Chosen 是一个系统全局性质。

例如：

  1. 多数服务器已经接受某个值。
  2. 随后 Proposer 崩溃。
  3. 其他服务器可能不知道多数派已经接受该值。

因此，任何一台服务器都无法仅凭自己的本地状态判断某个值是否已经被选定。

六、Paxos 伪代码

1. Proposer

proposer(v):

    选择 n
        n 必须唯一
        n 必须大于此前见过的所有提议编号

    向所有服务器发送 prepare(n)
        包括自己

    如果收到多数服务器的：
        prepare_ok(n, n_a, v_a)

        如果响应中包含已接受的值：
            选择 n_a 最大的响应对应的 v_a
            将其作为 v'

        否则：
            v' = 自己原本提议的 v

        向所有服务器发送：
            accept(n, v')

        如果收到多数服务器的：
            accept_ok(n)

            向所有服务器发送：
                decided(v')

2. Acceptor 状态

Acceptor（接受者）需要维护以下状态：

n_p：见过的最大 prepare 编号

n_a：已经接受过的最大提议编号

v_a：对应 n_a 已接受的值

这些状态必须在重启后仍然保留，因此需要持久化。

3. Acceptor 的 prepare 处理函数

prepare(n):

    if n > n_p:
        n_p = n

        reply prepare_ok(
            n,
            n_a,
            v_a
        )

    else:
        reject

4. Acceptor 的 accept 处理函数

accept(n, v):

    if n >= n_p:
        n_p = n
        n_a = n
        v_a = v

        reply accept_ok(n)

    else:
        reject

七、示例 1：正常运行

系统包含三台服务器：

S1
S2
S3

但 S3 已经故障，或者响应速度很慢。

S1 开始发起提议：

n = 5
v = A

事件如下：

S1: p5    a5A    dA
S2: p5    a5A    dA
S3: dead...

符号含义：

  • p5：服务器收到 prepare(n=5)。
  • a5A：服务器收到 accept(n=5, v=A)。
  • dA：服务器收到 decided(v=A)。

这些图并不特别说明谁是 Proposer。

我们只关心 Acceptor 收到了什么消息，以及如何回复。

由于 Proposer 只需要等待多数派，因此即使 S3 已经故障，也能继续执行。

问题

如果 S3 并没有崩溃，而只是被网络隔离，并试图提议值 B，会发生什么？

答案：S3 无法收集到多数服务器的 Prepare 响应，因此无法推进自己的提议。

八、如何确保已经确定的值不会改变？

考虑以下场景。

S1 希望提议值 X，并在发送两个 Accept 消息后崩溃。

S2 希望提议值 Y。

事件序列：

S1: p1 a1X
S2: p1     p2 a2?
S3: p1 a1X p2 a2?

问题：

Paxos 如何确保错误情况不会发生？

实际会发生什么？

最终会选择哪个值？

答案

S3 对 prepare(2) 的 prepare_ok 回复中，会包含值 X。

因此，第二轮实际上会发送：

a2X

而不是：

a2Y

这很好，因为 X 已经在第一轮被选定，因此第二轮仍然选定 X。

核心原因：

  1. 如果系统已经达成共识，多数派就会知道对应的值。
  2. 之后任何新的 Prepare 多数派，都必定与之前的多数派存在交集。
  3. 因此，新的 Proposer 会得知此前已经确定的值。
  4. 随后，它会在 Accept 消息中继续使用这个值。

九、示例 2：多个 Proposer 并发执行

S1 开始发起编号为 10 的提议。

S1 发送第一个 Accept 消息，提议值 X。

与此同时，S3 发起编号为 11 的提议。

但是 S1 没有收到 S3 的提议消息。

S3 只需要等待多数服务器的 Prepare 响应。

事件如下：

S1: p10 a10X
S2: p10        p11
S3: p10        p11  a11Y

此时 S1 仍然在继续发送 Accept 消息。

问题：

  • 是否已经有值被选定？
  • 接下来会发生什么？
  • 如果 S2 收到了 S1 发来的 accept(10, X)，它应该怎么处理？
  • 如果 S1 收到了 S3 发来的 accept(11, Y)，它应该怎么处理？
  • 如果 S3 在只发送一个 a11Y 后崩溃，并且永远不重启，会怎样？

一个重要的设计模式

如果有证据表明共识可能已经达成，那么就必须按照共识已经达成的情况进行处理。

Proposer 可能并不知道某个值是否已经被选定。

因为它的新多数派与此前多数派之间，可能只有一台服务器重合。

但即便如此，也必须采取保守策略。

十、到底什么时候才算达成共识？

考虑以下事件序列：

S1: p10  a10X               p12
S2: p10          p11  a11Y
S3: p10          p11        p12   a12X

此时，系统是否已经对某个值达成共识？

毕竟，多数服务器都接受过值 X。

Commit Point 是什么？

也就是：

  • 系统究竟在什么时候达成共识？
  • 服务器从什么时候开始，可以安全地根据共识结果采取行动？
  • 从什么时候开始，其他服务器可能已经根据共识结果执行操作？

是否只要多数服务器拥有相同的 v_a，就算达成共识？

不是。

上面的例子就是反例。

那么，是否需要多数服务器同时拥有相同的 v_a 和 n_a？

是。

也就是说，在这个单次 Paxos 协议中，必须有多数 Acceptor 接受了相同提议编号和相同值，才能认为该提议已被选定。

十一、为什么 Proposer 必须选择最大的 n_a 对应的 v_a？

考虑：

S1: p10  a10A               p12
S2: p10          p11  a11B
S3: p10          p11  a11B  p12   a12?

编号为 11 的提议已经确定了值 B。

当编号为 12 的 Proposer 收集响应时，它可能同时看到：

v_a = A
v_a = B

那么应该选择哪个值？

必须选择 B。

原因可以分成两种情况。

情况 1：在编号 11 之前，已经有某个值被选定

那么编号 11 的 Prepare 阶段一定会看到这个值，并重新使用它。

因此，编号 12 继续使用编号 11 所接受的值，是安全的。

情况 2：在编号 11 之前，没有任何值被选定

那么编号 11 可能已经获得了多数派。

因此，编号 12 必须继续使用编号 11 所接受的值。

这就是为什么 Proposer 必须选择 最高 n_a 对应的 v_a。

十二、为什么 Accept Handler 必须检查 n ≥ n_p？

如果不检查：

n >= n_p

就可能出现下面的错误情况：

S1: p1 p2 a1A
S2: p1 p2 a1A a2B
S3: p1 p2     a2B

这意味着：

  1. A 曾经被多数服务器接受并选定。
  2. 随后 B 又被多数服务器接受并选定。

结果：

系统一度选定 A，随后又改变为 B！

这违反了 Paxos 的安全性。

十三、为什么 Accept Handler 还需要更新 n_p = n？

代码：

if n >= n_p:
    n_p = n
    n_a = n
    v_a = v

为什么不能只更新 n_a 和 v_a？

因为必须防止后续接受更早编号的提议。

服务器可能收到 accept(n, v)，即使它从未收到对应的 prepare(n)。

如果不更新 n_p = n，可能出现：

S1: p1    a2B a1A p3 a3A
S2: p1 p2         p3 a3A
S3:    p2 a2B

结果：

  1. B 一度被选定。
  2. 随后 A 又被选定。

这同样违反了 Paxos 的安全性。

十四、如果 Proposer 使用了更小的提议编号会怎么样？

假设：

S2 选择的 n < S1 使用的 n

例如，S2 根本没有看到 S1 的任何消息。

结果：

S2 无法继续推进提议。

因此，这不会造成正确性问题。

十五、为什么 Acceptor 的状态必须持久化？

1. Acceptor 在发送 accept_ok 后崩溃并重启

考虑：

S1: p1  a1X
S2: p1  a1X reboot  p2  a2?
S3: p1              p2  a2?

我们知道 X 已经被选定。

但是编号 2 的提议是否会保留 X？

分析：

  1. 第一轮的多数派是 S1、S2。
  2. 第二轮的多数派是 S2、S3。
  3. S2 是两个多数派唯一的交集。
  4. 因此，S2 是系统已经选定 X 的唯一证据来源。

所以 S2 必须在：

prepare_ok(n=2)

中返回 X。

这意味着 S2 必须能够恢复崩溃前的：

n_a
v_a
n_p

因此，如果 S2 希望在崩溃后重新加入当前 Paxos 实例，就必须将 n_p、n_a、v_a 持久化到磁盘。

如果这些信息已经丢失，就不能重新加入该 Paxos 实例！

2. Acceptor 在发送 prepare_ok 后崩溃并重启

它是否需要将 n_p 持久化？

答案：需要。

如果没有记住 n_p，就可能出现：

S1: p10            a10X
S2: p10 p11 reboot a10X a11Y
S3:     p11             a11Y

编号 11 的 Prepare 响应中没有包含 X，因此编号 11 的 Proposer 选择了自己的值 Y。

但就在此之前，X 已经被选定！

这是因为 S2 重启后没有记住自己应该拒绝 a10X。

因此：

持久化 n_p 可以防止这一问题。

十六、Paxos 会不会卡住？

会。

如果系统中不存在能够相互通信的多数派，Paxos 就会无法取得进展。

当网络和计算机恢复后，Paxos 可以继续运行。

十七、Paxos 的性能如何？

Paxos 通常被认为比较慢，因为它需要多轮通信。

不过，存在很多优化方案，例如：

  • 通信流程优化。
  • 批处理（Batching）。

Paxos 也被认为成本较高，因为实现容忍一台服务器故障通常需要 3 个副本，而不是 2 个。

但是，对于真正需要容错的系统，这种成本很难避免。

十八、Paxos 在实际系统中的使用方式

许多系统在内部使用 Paxos，主要有以下几种方式：

  1. 当旧协调者没有响应时，通过 Paxos 选出新的协调者。
  2. 通过 Paxos 确定备份服务器何时应该接管主服务器。
  3. 通过 Paxos 确定复制状态机中的操作执行顺序。

十九、如何用 Paxos 构建数据库复制状态机？

RSM：Replicated State Machine，复制状态机。

基本结构：

工作流程：

  1. 客户端可以将操作发送给任意副本。
  2. 服务器通过 Paxos 对下一条应该追加到日志中的操作达成共识。
  3. 服务器将已经达成共识的操作记录到日志中。
  4. 所有服务器按照日志顺序，将操作应用到状态机中，例如 KV 数据库。

示例 1：写入操作

客户端向 S1 发送：

x = 1

S1 选择日志位置 3。

随后，S1 使用 Paxos，让所有服务器对日志位置 3 中应该存储 x=1 达成一致。

共识达成（Commit）后，所有数据库执行：

x = 1

示例 2：读取操作

客户端向 S2 发送：

x?

即读取 x。

S2 选择日志位置 4。

随后，S2 通过 Paxos，让所有服务器一致同意：

Log[4] = "x?"

共识达成后，S2 的数据库执行读取操作，并将结果返回客户端。

二十、为什么需要日志（Log）？

1. 处理并发

日志可以帮助系统处理并发操作。

在前面的操作提交之前，后续操作必须等待。

这样才能保证所有副本按照相同顺序执行操作。

2. 帮助副本追赶进度

例如：

  • 某个副本没有参与之前的多数派。
  • 某台服务器短暂离线。
  • 某个副本落后于其他副本。

日志可以帮助这些副本恢复缺失的操作。

3. 日志截断

通常，系统不需要永久保存完整日志。

一般只保留日志的尾部，以及对应的状态（State）。

二十一、课程后续安排

  • 下一讲：由一位 Go 语言专家进行客座讲座。
  • 再下一部分：Raft。
  • Lab 1 明天截止。

知识图谱

同目录聚类 · 悬浮查看文章

全站知识图谱

颜色对应目录 · 连线表示文章引用 · 拖动平移，按钮缩放