Paxos 算法详解

基本介绍

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

发展历史

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

在 2001 年，Lamport 意识到学术同行们难以理解他这种幽默的表达方式，于是重新发表了更加简洁直接的算法描述版本《Paxos Made Simple》。这篇论文摒弃了之前的隐喻，直接阐述算法核心原理，大大提高了可理解性。

行业影响与应用

自 Paxos 问世以来，它就在分布式一致性算法领域占据主导地位，“Paxos”这个名词几乎成为了分布式一致性的代名词。该算法在工业界得到了广泛应用：

Google 系统应用：

  • Chubby：分布式锁服务
  • Megastore：高可用性存储系统
  • Spanner：全球分布式数据库

开源系统应用：

  • ZooKeeper：分布式协调服务
  • MySQL 5.7 的 Group Replication：取代传统主从复制的新机制

算法优化

上面的内容中，分别从 Proposer 和 Acceptor 对提案的生成和批准两个方面讲解了 Paxos 算法在提案选定过程中的算法细节，同时也在提案的编号全局唯一的前提下，获得了一个提案选定宣发，接下来我们再对这个初步算法做一个小优化，尽可能忽略 Prepare 请求。

“如果 Acceptor 收到一个编号为 N 的 Prepare 请求，在此之前它已经响应过编号大于 N 的 Prepare 请求。根据 P1a，该 Acceptor 不可能接受编号为 N 的提案。因此，该 Accepto 可以忽略编号为 N 的 Prepare 请求。”

通过这个优化，每个 Acceptor 只需要记住它已经批准的提案的最大编号以及它已经做出了 Prepare 请求响应的提案的最大编号，以便出现故障或节点重启的情况下，也能保证 P2c 的不变性，而对于 Proposer 来说，只要它可以保证不会产生具体相同编号的提案，那么就可以丢弃任意的提案以及它所有运行时状态信息。

算法描述

综合前面的讲解，我们来对 Paxos 算法的提案选定过程进行总结，结合 Proposer 和 Acceptor 对提案的处理逻辑，就可以得到类似的两阶段提交的算法执行过程。

阶段一

  • Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求
  • 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案

阶段二

  • 如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对【N，V】提案的 Acceptor 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 Value，如果响应中不包含任何提案，那么 V 就是由 Proposer 自己决定
  • 如果 Acceptor 收到一个针对编号为 N 的提案的 Acceptor 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案

当然，实际运行过程中，每一个 Proposer 都可能产生多个提案，但只要每个 Proposer 都遵循如上所述的算法运行，就一定能够保证算法执行的正确性。

Learn 学习被选定的 Value

方案一

Learner 获取了一个已经被选定的提案的前提是，该提案已经被半数以上的 Acceptor 批准，因此，最简单的做法就是一旦 Acceptor 批准了一个提案，就将该提案发送给所有的 Learner。

“这种做法虽然可以让 Learner 尽快的获取被选定的提案，但是却需要让每个 Acceptor 与所有的 Learner 逐个进行一次通信，通信的次数至少为二者个数的乘积。“

方案二

另一种可行的方案是，我们可以让所有的 Acceptor 将他们对提案的批准情况，统一发送给一个特定的 Learner（称为主 Learner），各个 Learner 之间可以通过消息通信来互相感知提案的选定情况，基于这样的前提，当主 Learner 被通知一个提案已经被选定时，它会负责通知其他 Learner。

“在这种方案中，Acceptor 首先会将得到的批准的提案发送给主 Learner，再由其同步给其他 Learner，因此较方案一而言，方案二虽然需要多一个步骤才能将提案通知到所有的 Learner，但其通信次数却大大减少了，通常只是 Acceptor 和 Learner 的个数总和。但同时，该方案引入一个新的不稳定因素：主 Learner 随时可能出现故障。“

方案三

在讲解方案二的时候，我们提到，方案二最大的问题在于主 Learn 存在单点问题，即主 Learner 随时可能出现故障，因此，对方案二进行改进，可以将主 Learner 的范围扩大，即 Acceptor 可以将批准的提案发送给一个特定的 Learner 集合，该集合每个 Learner 都可以在一个提案被选定后通知其他的 Learner。“这个 Learner 集合中的 Learner 个数越多，可靠性就越好，但同时网络通信的复杂程度也就越高。“

如何保证 Paxos 算法的活性

活性问题的定义

在分布式系统中，活性（liveness）是指系统最终一定会达成某些期望结果的性质。对于 Paxos 算法而言，活性具体表现为：最终一定会有一个 Value 被选定（accepted）。这是 Paxos 算法正确性的重要保证之一。

活性失效的场景分析

假设存在一种极端情况，这种场景会导致 Paxos 算法无法保证活性：

  1. 提案竞争循环：有两个 Proposer（P1 和 P2）持续交替提出一系列编号递增的提案
  2. 死锁形成：
    • P1 提出提案 n1，获得多数派 Acceptor 承诺
    • P2 提出更高编号 n2（n2 > n1），导致 P1 的提案被废弃
    • P1 随后提出更高编号 n3（n3 > n2），导致 P2 的提案被废弃
    • 这个过程不断重复，形成”提案编号竞赛”
  3. 具体流程示例：
    • 阶段 1：P1 准备（prepare）提案 n1，获得多数派承诺
    • 阶段 2：P1 尝试接受（accept）提案 n1，但此时 P2 已发出更高编号 n2 的准备请求
    • 阶段 3：P2 的准备请求 n2 获得多数派承诺，导致 n1 被废弃
    • 阶段 4：P2 尝试接受提案 n2 时，P1 又发出更高编号 n3 的准备请求
    • “这个循环会无限持续下去，没有 Value 最终被选定。“

活性问题的解决方案

为了解决这个活性问题，Paxos 算法提出了以下几种保障机制：

  1. 选举主 Proposer：

    • 系统指定一个唯一的”主”Proposer
    • 只有主 Proposer 可以提出提案
    • 当主 Proposer 失效时，选举新的主 Proposer
    • “这样可以避免多个 Proposer 之间的竞争。”

  2. 随机退避机制：

    • 当 Proposer 发现提案被拒绝时，随机等待一段时间再重试
    • 等待时间随失败次数指数增长（类似以太网的退避算法）
    • “这增加了单个 Proposer 成功完成提案的概率。”

  3. 提案编号限制：

    • 设置提案编号的上限
    • 当编号达到上限时强制选定当前最高编号的提案
    • “避免无限递增的编号竞赛。”

  4. 超时机制：

    • 为每个提案阶段设置合理的超时时间
    • 超时后自动进入下一轮提案
    • “防止单个提案无限期阻塞系统。”

在实际工程实现中，通常采用选举主 Proposer 的方案来解决活性问题，因为这种方法最可靠且易于实现。例如在 Google 的 Chubby 锁服务和很多分布式存储系统中都采用了这种方案。