分布式共识-Paxos算法分析

概述

上一篇分布式共识理论基础中分析了SMR模型，SMR模型是分布式系统中实现容错性和强一致性的最重要、最基础的范式之一，它提供了一种机制，使得一组服务器能够像一个单一、可靠的、高性能的服务器一样运行，即使其中一些服务器发生故障，实现 SMR 通常需要依赖一个分布式共识算法来管理操作日志的同步，其中Paxos、Raft、ZAB等分布式共识算法就是其具体的实现。

Paxos算法

Paxos算法，是由Leslie Lamport提出的一种基于消息传递的协商共识算法，是第一个被证明能在允许节点故障和网络不可靠的异步系统中实现共识的算法。通常用于解决在一个可能发生消息丢失、延迟、重复，但节点不会恶意篡改（即“非拜占庭”）的异步分布式系统中，如何就单个值（例如，谁是主节点，下一个操作是什么）达成 一致（Consensus） 的问题。

Basic Paxos

在 Basic Paxos 中，一个节点可以同时扮演一个或多个角色，主要由三种角色组成：

• Proposers（提议者）：它们向系统提交提案，提案包含一个值（Value）和一个全局唯一的、递增的提案编号（Proposal Number, N）。
• Acceptors（接受者）：它们对提案进行投票，接受或拒绝一个提案。负责在多个提案中进行权衡，并最终接受或拒绝一个值。达成共识的关键在于 Acceptor 的多数派，最终一致性的保证来自于接受者对提案的接受。
• Learners（学习者）：它们用于学习已被接受的提案的结果，通常是系统的客户端。

在Basic Paxos算法系统中总共有 N 个 Acceptor。一个多数派（Majority / Quorum）指的是至少 floor(N/2) + 1 个 Acceptor。任意两个“多数派”集合必然至少有一个共同的 Acceptor 成员，这是 Paxos 安全性的数学基础。

算法流程：两阶段提交（Basic Paxos）

基本的 Paxos 算法通过一个两阶段提交过程来确保即使有多个提议者同时竞争，也能最终选定一个唯一值。这个过程在每一轮共识中重复进行：

阶段一：准备阶段 (Prepare Phase)：目标是选择一个唯一的提案编号，并保证不会有编号更小的提案被接受。

• 提议者发起准备请求: 提议者选择一个全局唯一的、单调递增的提案编号 N（通常由时间戳或递增计数器加上节点ID生成），并向多数接受者发送一个“准备 (Prepare)”请求。
• 接受者响应: 接受者收到编号为 N 的 Prepare 请求后，如果其尚未向任何编号大于 N 的 Prepare 请求作出过承诺，则：
  • 承诺 ( Promise) 不再接受任何编号小于 N 的提案。
  • 如果接受者之前已经接受过某个提案，它必须返回其已接受的编号最大的提案的值 V 和对应的编号 M (M < N)。
  • 如果接受者已经对编号大于 N 的请求做出了承诺，它将忽略该请求或返回一个拒绝消息。

阶段二：接受阶段 (Accept Phase)：目标是让多数接受者接受提议者的值。

• 提议者发送接受请求: 提议者在收到多数（法定人数）接受者的 Promise 响应后，开始准备发送“接受 (Accept)”请求。

  • 如果所有响应的接受者都没有返回任何已接受的值，提议者可以使用自己最初想要提出的值 V。
  • 如果响应中存在“已经接受过的值”，Proposer 必须选择那个accepted_N 编号最大的 accepted_V，作为自己这次要提议的值（保证已选定的值不会被覆盖）。
  • Proposer 选定了值（我们称之为 Final_V）后，它向所有（至少是那些回应了的多数派）Acceptor 发送 Accept(N, Final_V) 请求。
  • 如果 Proposer 未能获得“多数派”的 Promise（比如超时或收到了太多 Nack）：它必须放弃此次尝试，在未来选择一个更大的提案编号，重新从阶段一开始。

• 接受者接受提案: 当一个 Acceptor (A) 收到 Accept(N, Final_V) 请求时，它会检查这个 N 是否“足够新”。

  • N >= max_promised_N (这个提案编号 N 至少和我承诺过的一样大)，Acceptor 接受这个提议。它将自己的 accepted_N 更新为 N，accepted_V 更新为 Final_V。同时向 Proposer 和所有 Learner 发送 Accepted(N, Final_V) 消息。
  • N < max_promised_N (这个提案已经过时了)，Acceptor 拒绝这个 Accept 请求。

• 学习者获知结果: 一旦一个值被多数接受者接受，该值即被确定（Chosen）。Learner 负责发现这个被“选择”的值，它会监听来自所有 Acceptor 的 Accepted 消息，一旦 Learner 发现有多数派的 Acceptor 都宣称接受了同一个值 V，它就知道 V 已经成为共识。接受者或提议者会将此信息通知给学习者，学习者从而得知最终的共识值。

Paxos的核心特性是通过多数接受（quorum）来确保一致性，即一个提议必须被大多数接受者接受才能成为最终决定的值：

• Safety（安全性）：Paxos 确保任何时刻只有一个提议会被接受并作为决策。即使系统出现故障，只要仍然有多数接受者存活，就能够达成一致。
• Liveness（终止性）：只要系统有足够的提议者和接受者，Paxos会最终达成一致。也就是说，只要有足够的消息传递，系统会最终决定一个值。

Basic Paxos问题分析

假设一个分布式系统有五个节点，分别是S1、S2、S3、S4和S5；全部节点都同时扮演着提案节点和决策节点的角色。此时，有两个并发的请求希望将同一个值分别设定为X（由S1作为提案节点提出）和Y（由S5作为提案节点提出）；我们用P代表准备阶段、用A代表批准阶段，这时候可能发生下面四种情况。

情况一: 已选值被新值替换。如下图，S1的提案被大多数授受，当S5发起提案时，同样可以被大多数授，最终系统会使用S5的提案Y。

情况二：两个节点发起提案，前一个提案未被大多数授受，后发起的提案在的某个Accept节点包含前一个提案的Accept值，这种情况尽管后一个节点的提案N更大，但是不会被选为共识值。如下同，S5发起提案的Prepare请求时，X并未获得多数派批准，但由于S3已经批准的关系，最终共识的结果仍然是X。

情况三：先前的值未被选中，新的提议者Accept节点未包含前一个提案值，最终会被授受的提案为后一个提案值。如下图，应答S5提案时，节点S1、S2已经批准了X，S3未批准但返回了Promise应答，此时S5以更大的提案ID获得了S3、S4和S5的Promise。这三个节点均未批准过任何值，那么S3将不会再接受来自S1的Accept请求，因为它的提案ID已经不是最大的了，这三个节点将批准Y的取值，整个系统最终会对“取值为Y”达成一致。

情况四：活锁问题，两个 Proposer 轮流用更高的提案编号打断对方的阶段 1，导致没有提案能成功进入阶段 2。如下图，从情况三可以推导出另一种极端的情况，如果两个提案节点交替使用更大的提案ID使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。在算法实现中，会引入随机超时时间来避免活锁的产生。

小结

虽然Paxos在理论上非常强大，但是它的实际实现较为复杂，主要有如下挑战：

• 消息复杂性：Paxos 需要多个阶段的消息交换（准备、提议、决定），这会导致系统的延迟和消息量增加。
• 活跃性问题：虽然Paxos保证安全性，但它可能出现无法达成一致的情况，尤其是在提议者或接受者出现故障时。为了增强活跃性，Paxos通常需要配合其他机制（如领导选举、超时重试等）来处理。
• 高可用性：为了保证一致性和高可用性，Paxos要求系统中的大多数节点（超过半数）必须正常工作。这就要求系统有较高的容错能力。

Multi Paxos

Basic Paxos 只用于就单个值达成一次共识，同时每次决策都需要完整的两阶段（Prepare + Accept），如果每次都执行完整的协议步骤，会导致非常高的通信开销和性能问题，特别是当系统需要多次达成一致时，而且容易产生“活锁”。在实际系统实现中需要对一系列值（Log Entry 1, 2, 3…）快速连续地达成共识，Multi-Paxos 的引入是为了在多次决策中减少通信开销，并确保在多个连续的决策过程中只需要执行最少的操作，最大化效率。

如果说 Basic Paxos 像一个混乱的议会，任何人（Proposer） 都可以随时发起提案（Prepare），导致“活锁”；那么 Multi-Paxos 就引入了一个“总统”——Leader（领导者）。Multi-Paxos 的核心就是选举一个唯一的、稳定的 Leader，并让这个 Leader 成为系统中唯一的 Proposer。 通过这个核心思想，Multi-Paxos 解决了 Basic Paxos 的两大痛点：

• 效率问题： 避免了对每一个日志条目都执行完整的两阶段（Prepare/Accept）。
• 活锁问题： 因为只有一个 Proposer（Leader），杜绝了 Proposer 之间相互“打架”导致活锁的可能性。

Multi-Paxos原理分析

Leader 选举 (Leader Election)：在 Multi-Paxos 集群启动或当前领导者失效时，节点会触发领导者选举流程，这个过程本质上就是运行一轮标准的 Basic Paxos 算法，就“谁是当前领导者”达成共识。

• 发起选举： 任何一个节点（Proposer）如果发现当前没有 Leader（例如，通过心跳超时检测），它都可以发起一轮 Leader 选举。
• 提案内容： 这次 Basic Paxos 提案的“值（Value）”不再是具体的操作，而是Proposer 自己的 ID。
• 达成共识： 节点们运行 Basic Paxos 的两阶段（Prepare/Accept）。最终，如果一个节点（比如 Node A）的 ID 被“选择”（Chosen）为 Leader，那么它就获得了 Leader 身份。
• 提案编号 (N)： 赢得选举的 Leader 会使用它在 Basic Paxos 中胜出的那个提案编号 N 作为自己的“任期号”(term)或“时代号”（Epoch）。

Leader 在刚当选时，会先执行一次完整的 Basic Paxos（Prepare + Accept）。Leader 向所有 Acceptor 广播 Prepare(N)，让所有 Acceptor 承诺（Promise）“不再接受任何小于 N 的提案”。这实质上“罢免”了所有旧的 Leader。同时，Leader 会检查 Promise 响应中返回的 accepted_V（之前已接受的值），来发现并补全自己可能缺失的日志（称为“日志空洞填充”）。一旦上述 Prepare 阶段成功，Leader 就获得了“多数派”的 Promise 承诺，只要 Leader 不变，它在为新的日志条目（Log Entry）发起提议时，就可以完全跳过 Prepare 阶段！

日志复制：一旦领导者被选出并稳定运行，Multi-Paxos 进入高效的常态运行阶段，处理客户端请求并复制日志。

• 客户端请求与日志追加：客户端向领导者发送一个操作请求。领导者将请求封装成一个日志条目，包含一个值 (Value)（即客户端指令）和一个唯一的日志索引 (Log Index / Slot Number)。这个日志索引对应于一个特定的 Paxos 实例。
• 简化的 Accept 阶段 (一阶段提交)：在 Basic Paxos 中，每一个值都需要完整的 Prepare/Accept 两阶段。在 Multi-Paxos 中，由于领导者已经预先获得了多数派的承诺，可以直接跳过 Prepare 阶段：
  • 发送 Accept: 领导者直接向多数接受者发送一个Accept 请求，其中包含当前的任期编号 N、日志索引 I 和值 V。
  • 接受者响应: 接受者收到 Accept 请求后，如果请求的任期编号 N 不小于它之前承诺或看到的任何编号，它会立即接受该值，并将其写入本地日志，然后回复领导者一个确认（ACK）。
• 学习与提交 (Learn/Commit 阶段)：领导者收到多数接受者的确认响应后，即可确定该日志条目已经达成共识（Chosen）。这时领导者会通知所有节点（包括学习者和其他接受者）该日志条目已提交，通常这个提交信息会搭载在后续的心跳包或下一个 Accept 请求中发送。最终，所有节点将已提交的日志条目按顺序应用到本地的状态机（如数据库），从而实现全系统的强一致性。

失败恢复：Multi-Paxos 也面临着系统中节点失败的挑战，特别是 Leader 失败时。为了保证系统能继续运行，Multi-Paxos 需要能够快速恢复，确保系统能够选举出新的 Leader 并继续达成一致。

• Leader 失败后的恢复：当当前的 Leader 发生故障时，系统需要通过选举过程选出新的 Leader，并且新的 Leader 会继续使用合适的提议编号发起新的提议，直到恢复一致性。
• 恢复策略：可以通过超时机制（比如 Paxos 的超时机制）来启动选举。新的 Leader 可能需要进行一些额外的协调，特别是如果在 Leader 失败期间出现了其他提议。

小结

Multi-Paxos 的本质是通过 Basic Paxos 选举出一个 Leader，然后将共识的执行过程（Propose）和 Leader 的租期（Lease）绑定。

• 只要 Leader 的“租期”（由其提案编号 N 代表）有效，它就可以绕过 Basic Paxos 繁琐的 Prepare 阶段，实现高效的“一阶段提交”共识（Fast Path）。
• 当 Leader 失败时，系统通过新一轮的 Basic Paxos（使用 N+1）来“抢占”租期，选举出新 Leader，从而实现容错。

Multi-Paxos 极大地提高了 Paxos 的实用性，但其实现（特别是 Leader 切换和日志空洞填充）非常复杂。这也催生了后来更易于理解和实现的 Raft 算法。