基本介绍

Paxos 算法是由计算机科学家 Leslie Lamport 提出的一种基于消息传递的分布式一致性算法，这项开创性工作使他获得了2013年图灵奖。该算法解决了分布式系统中如何就某个值（决议）达成一致的问题，即使在部分节点失效或网络不稳定的情况下也能保证系统一致性。

发展历史

Paxos 算法最早由 Lamport 于 1998 年在《The Part-Time Parliament》论文中首次公开。论文采用了一种独特的叙述方式，使用希腊的一个名为 Paxos 的小岛作为比喻，详细描述了 Paxos 小岛中通过议会决议的流程，并以此命名这个算法。

在2001年，Lamport 意识到学术同行们难以理解他这种幽默的表达方式，于是重新发表了更加简洁直接的算法描述版本《Paxos Made Simple》。

行业影响与应用

自 Paxos 问世以来，它就在分布式一致性算法领域占据主导地位。该算法在工业界得到了广泛应用：

  • Google 系统应用：Chubby（分布式锁服务）、Megastore（高可用性存储系统）、Spanner（全球分布式数据库）
  • 开源系统应用：ZooKeeper（分布式协调服务）、MySQL 5.7 的 Group Replication

算法特点

Paxos 算法虽然强大，但以难以理解和实现著称。其难点主要体现在：

  1. 算法描述抽象，需要深入理解分布式系统原理
  2. 实现时需要处理各种边界条件和异常情况
  3. 性能优化需要考虑实际网络环境

解决了什么问题

问题背景

在现代分布式系统中，数据通常采用多副本机制存储以提高可用性和容错性。典型场景包括：分布式数据库（如 Google Spanner）、分布式存储系统（如 HDFS）、分布式计算框架等。

具体挑战

  • 网络分区：节点间通信可能中断
  • 消息延迟：操作指令到达不同节点的时间不一致
  • 节点故障：部分节点可能暂时或永久失效
  • 并发冲突：多个客户端同时发起修改请求

解决方案细节

Paxos 通过以下机制保证一致性：

  • 提案阶段（Prepare）：节点提议值并收集多数派响应
  • 接受阶段（Accept）：确定最终值并获得多数派确认
  • 学习阶段（Learn）：将确定的值传播给所有副本

Paxos 能在半数以上节点正常工作的情况下，保证系统对外展现一致的状态，即使面对网络问题和节点故障。

相关概念

提案（Proposal）机制

提案是 Paxos 算法的核心概念，它是一个包含两个关键组成部分的信息包：

  1. 提案编码（Proposal ID）：一个全局唯一的标识符，通常由提案编号（通常是递增的数字）和提案者的唯一标识（如服务器 ID）组成。例如：<5, ServerA> 表示由 ServerA 发起的第 5 号提案。
  2. 提议的值（Value）：这是希望分布式系统达成一致的最终数据值。

Paxos 算法中的角色分工

Paxos 算法定义了四个关键角色，各司其职：

1. Client（客户端）

  • 是系统外部请求的发起方
  • 向分布式系统发出操作请求（如读写请求）
  • 等待系统响应和确认

2. Proposer（提案发起者）

  • 核心职责：接收客户端请求并转化为提案，推动提案的接受过程，处理提案冲突时的协调工作
  • 工作流程：
    1. 准备阶段：向 Acceptors 发送准备请求
    2. 提议阶段：收到多数 Acceptors 响应后发送正式提案

3. Acceptor（决策者）

  • 关键功能：接收并处理 Proposer 的请求，决定是否接受某个提案，保证安全性约束
  • 决策规则：只接受编号高于已承诺编号的提案，必须记住已接受的最高编号提案
  • 重要特性：通常需要多数派（quorum）Acceptors 接受才能选定提案

4. Learner（学习者）

  • 主要任务：观察并学习被选定的 Value，将最终决议传播到整个系统
  • 实现方式：可以监听 Acceptors 的决定，或者由 Proposer 通知选定结果

这些角色在实际系统中通常由服务器节点兼任，例如一个节点可能同时扮演 Proposer 和 Acceptor 的角色。

推导过程

最简单的方案：只有一个 Acceptor

在 Paxos 算法的实现中，最简单的方案是只使用一个 Acceptor（可以有多个 Proposer）。在这种配置下，系统的工作流程如下：

  1. 任何 Proposer 都可以向唯一的 Acceptor 提交提案
  2. Acceptor 遵循”先到先接受”的原则，即接受它收到的第一个提案
  3. 一旦 Acceptor 接受某个提案，该提案就被选定
  4. 该提案中包含的 Value 就成为整个系统最终选定的值

这种方案的优势在于实现简单，可以确保系统最终会选定一个值。但是，这个方案存在严重的问题：

  1. 单点故障风险：如果这个唯一的 Acceptor 宕机，整个系统将完全停止工作
  2. 性能瓶颈：所有请求都必须经过单个 Acceptor 处理
  3. 缺乏容错能力：无法应对网络分区等异常情况

因此，在实际生产环境中，必须使用多个 Acceptor 来构建可靠的分布式系统。

多个 Acceptor

如何保证多个 Proposer 和多个 Acceptor 的情况下选定一个 Value 呢？

P1：一个 Acceptor 必须接受它收到的第一个提案。

但是，如果每个 Proposer 分别提出不同的 Value，发送给不同的 Acceptor。根据刚才的约束，Acceptor 分别接受自己收到的第一个提案，就导致不同的 Value 被选定，出现了不一致。

因此，我们需要加一个规定：一个提案被选定需要被半数以上的 Acceptor 接受。

根据上面的内容，我们现在虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同 Value 值，否则又会出现不一致。

P2：如果某个 Value 为 v 的提案被选定了，那么每个编号更高的被选定提案的 Value 也必须是 v。

一个提案只有被 Acceptor 接受才可能被选定，因此我们可以把 P2 约束改写成 Acceptor 接受的提案的约束 P2a。

P2a：如果某个 Value 为 v 的提案被选定了，那么每个编号更高的被 Acceptor 接受的提案 Value 必须也是 v。

只要满足了 P2a，就能满足 P2。

但是，考虑如下的情况：假设总的有 5 个 Acceptor，Proposer 提出【M1,V1】的提案，Acceptor25（半数以上）接受了提案，于是对于 Acceptor25 和 Proposer2 来讲，它们都认为 V1 被选定。Acceptor1 刚从宕机状态恢复过来（之前 Acceptor1 没有收到任何提案），此时 Proposer1 向 Acceptor1 发送了【M2, V2】的提案（V2 不等 V1 且 M2 大于 M1），对于 Acceptor1 来讲，这是它收到的第一个提案。根据 P1（一个 Acceptor 必须接受它收到的第一个提案），Acceptor1 必须接受该提案，同时 Acceptor1 认为 V2 被选定。

这就出现了如下的两个问题：

  • Acceptor1 认为 V2 被选定，Acceptor2~5 和 Proposer2 认为 V1 被选定，出现了不一致
  • V1 被选定了，但是编号更高的被 Acceptor1 接受的提案【M2,V2】的 value 为 V2，且 V2 != V1。这就跟 P2a 矛盾了

所以我们需要对 P2a 约束进行强化！

P2a 是对 Acceptor 接受的提案约束，但其实提案是 Proposer 提出来的，所以我们可以对 Proposer 提出的提案进行约束，得到 P2b：

P2b：如果某个 Value 为 v 的提案被选定了，那么之后任何 Proposer 提出的编号更高的提案 value 也必须是 v。

有 P2b 可以推出 P2a 进而推出 P2。那么，如何确保在某个 Value 为 v 的提案之后，Proposer 提出的编号更高的提案的 Value 都是 v 呢？

只要满足 P2c 即可：

P2c：对于任意的 Mn 和 Vn，如果提案 [Mn，Vn] 提出，那么肯定存在一个由半数以上的 Acceptor 组成的集合 S，满足以下两个条件中的任意一个：

  1. 要么 S 中的每个 Acceptor 都没有接受过编号小于 Mn 的提案
  2. 要么 S 中所有 Acceptor 批准的所有编号小于 Mn 的提案中，编号最大的那个提案的 Value 值为 Vn

从上面的内容，可以看出，从 P1 到 P2c 的过程其实是对一系列条件的逐步加强，如果需要证明这些条件可以保证一致性，那么就可以进行反向推导：P2c => P2b => P2a => P2，然后通过 P2 和 P1 来保证一致性。