做分布式存储做了几年身边同事聊到 Paxos 时最多的反应是“看过很多遍一碰到 Multi-Paxos 就晕”。Basic Paxos 好歹能对着消息编号把承诺规则捋清楚Multi-Paxos 把多个实例串成一条日志再加上选主、空洞、故障恢复这些环节整个流程就变得很难一眼看穿。我早期在一套自研的复制状态机里从头实现过这套协议活锁、乱序、持久化丢失的坑都踩过这篇文章把 Multi-Paxos 的完整流程拆开讲一遍重点说清楚选主阶段和日志提交阶段到底怎么配合、哪些地方最容易写错、线上出问题怎么定位。适合已经了解 Basic Paxos、正准备动手实现或阅读源码的开发者也适合面试前想把概念讲明白的同学。1. 为什么需要 Multi-Paxos从 Basic Paxos 到日志复制的进化1.1 Basic Paxos 的尴尬单值决策模型撑不起连续日志Basic Paxos 解决的是“一个值”达成共识的问题。协议里只有三类角色Proposer 提出提案Acceptor 负责投票Learner 学习结果。整个流程分两段Prepare 阶段让 Proposer 拿到最新编号和可能已存在的值Accept 阶段把值发给 Acceptor 投票。只要多数派接受了某个值这个值就被“选定”了。这套机制没问题但放到真实的数据库或存储系统里就尴尬了。客户端每写一条日志理论上都要完整跑一轮 Prepare 加 Accept也就是至少两个 RTT。更难受的是多个 Proposer 同时在线时编号冲突会让 Acceptor 频繁拒绝提案结果一轮 Prepare 可能反复重试活锁风险极高。你可以把 Basic Paxos 想象成每次开会都要重新选主持人、重新清点到场人数、重新表决效率低不说会议还随时可能因为另一个主持人抢话筒而中断。Paxos 论文真正想要解决的不是单个值而是让一组服务器按照相同顺序执行相同指令也就是复制状态机模型。单个值的共识只是地基不能直接拿来当日志用。1.2 Multi-Paxos 的核心思路一次选主多次提交Multi-Paxos 的思路其实非常朴素既然每次提案都要竞争编号那我干脆先在多个实例之间选出一个稳定的 Leader后续所有槽位都用同一个提案编号连续提交。这样的话Prepare 阶段只需要在 Leader 刚上任时做一次随后的每条日志都可以跳过 Prepare直接走 Accept提交一条日志的延迟就从两个 RTT 降到一个 RTT。这个“选主”并没有引入额外协议它本身就是用一次 Prepare 来完成的。新 Leader 把自己的提案编号广播给所有 AcceptorAcceptor 承诺不再接受更小编号的提案并把已经接受的值返回给 Leader。等 Leader 收到多数派的响应它就获得了对当前轮次所有未提交槽位的“提案垄断权”。之后无论日志有多少条只要编号不变Acceptor 都会接受前提是没有更高编号的提案来打扰。所有实例复用同一个编号还有一个好处编号一旦在 Prepare 阶段得到确认后续所有槽位都能直接用这个编号不需要为每个槽位重新生成一个唯一编号。你只需要保证编号单调递增逻辑上比 Basic Paxos 每轮都构造新编号要省事得多。2. Multi-Paxos 场景与角色先看懂“复制状态机”这个底子2.1 复制状态机模型日志一致状态就一致要理解 Multi-Paxos必须把视野从单个提案抬升到一整条日志。假设集群里有多个副本每个副本内部维护一个确定性的状态机。客户端提交命令时系统把命令追加到日志里日志是命令的唯一顺序来源。只要所有副本按相同的顺序执行相同的命令最终状态就完全一致。Multi-Paxos 在这里承担的任务是保证日志的每一个槽位上所有副本最终看到的命令是同一个并且槽位之间的顺序不出现矛盾。这不是“某一个命令达成共识”而是“长度为 n 的命令序列逐个达成共识”。更直白地说Multi-Paxos 把日志切成一格一格的槽位每个槽位单独跑一个 Basic Paxos 实例只是所有实例共享同一个 Leader 和同一个提案编号。槽位的概念很容易理解日志第 1 条命令放进槽位 1第 2 条放进槽位 2。不同副本第一次看到某个槽位的时间可能不同甚至槽位 5 先提交、槽位 3 还没提交这是允许的。但状态机执行时必须从槽位 1 开始连续执行绝不能因为槽位 5 已经提交就跳过槽位 3 和 4。这一条限制是工程实现里最常见也最容易忽略的约束。2.2 角色职责Leader、Acceptor、Learner 各管什么Multi-Paxos 里角色仍然分三类但相比 Basic Paxos 多了一层“选举”的含义。Leader 由某个节点担任是唯一的 Proposer。它负责分配槽位把客户端命令放进下一个空槽位然后发起 Accept。Leader 还需要维护 nextSlot下一个空闲槽位编号和一组已提交日志的视图。日常提交阶段客户端请求到达 Leader 后Leader 把它分配给一个尚未使用的槽位生成 Accept(i, n, v)其中 i 是槽位编号n 是提案编号v 是命令内容。Acceptor 的职责和 Basic Paxos 一样保存两个关键状态一个是它承诺过的最大提案编号 promisedID另一个是它接受过的最高编号提案acceptedID, acceptedValue。Acceptor 不会主动推进日志它只对收到的 Prepare 和 Accept 做出响应。多数派在这里承担所有安全性保障因为任何两个多数派集合必然有交集这保证了“同一槽位不会出现两个不同选定值”。Learner 负责学习已经被选定的日志并把命令交给状态机执行。它本身不参与投票但必须知道“某个槽位的值已经被多数派接受了”。实现时 Learning 方式很多最简单的是 Acceptor 把 Accepted 消息发回给 LeaderLeader 自己统计复杂一点可以让 Acceptor 广播给所有 Learner。后面我会单独说不同方案的消息量差异。2.3 法定人数多数派交集如何兜住安全性为什么要强调“多数派”因为两次多数派投票之间必然存在一个公共节点。假设 5 节点集群法定人数是 3任何两轮投票的 3 个节点集合至少有一个节点是重合的。这个重合节点就像桥梁让后一轮的决策者能发现前一轮已经选定的值。用反证法可以更直观地看出这一点如果同一个槽位先被值 x 选定了意味着多数派接受了 x后来又被值 y 选定那么这两个多数派集合的交集节点一定同时接受了 x 和 y。Acceptor 有一条硬性规则一旦接受了编号更高的提案就不允许再接受编号更低的提案。所以 x 和 y 要同时出现在同一个 Acceptor 上只能是一方编号更高而编号更高的那一个应被新的 Leader 通过 Prepare 继承。只要遵守“保留最高编号已接受值”的规则冲突就无法发生。法定人数的计算很固定假设集群允许 f 个节点故障节点总数 N 至少为 2f1法定人数 Q f1。例如 3 节点集群允许 1 个故障法定人数 25 节点集群允许 2 个故障法定人数 3。实际部署中不要为了省资源把节点压到 2f1 以下那样无法同时满足可用性和线性一致读的要求。3. Multi-Paxos 完整流程拆解从选主到一条日志的提交3.1 选主阶段用一次 Prepare 抢占提案权新 Leader 上线后的第一件事就是广播 Prepare(n)n 必须大于所有历史提案编号。这里我不展开编号生成方案只说结论编号必须全局单调不能因进程重启或机器时间回拨而重复。Acceptor 收到 Prepare(n) 后做两件事如果 n 大于本地 promisedID把 promisedID 更新为 n并承诺不再接受编号小于 n 的任何提案。返回自己的已接受记录acceptedID, acceptedValue如果没有接受过任何提案就返回空。Leader 只有收到多数派的 Prepare 响应才算真正获得提案权。此时它检查所有返回的已接受记录从中挑出 acceptedID 最高的那条值。如果存在这样的值后续 Accept 阶段必须复用这个值不能换成自己的新命令。只有所有记录都为空时Leader 才能自由选择新值。这里有一条新手最容易犯的错看到多数派空记录就以为自己可以为所欲为忽略了那个没有响应的节点上其实可能留着旧值。但安全性保证了新编号 n 已经大于所有参与 Prepare 的 Acceptor 的 promisedID而没响应的少数派节点不可能单独把旧值提交到多数派所以旧值不可能成为已提交值。反过来如果旧值已经提交那么提交它的多数派必然与本次 Prepare 的多数派有交集这个交集节点一定会把旧值返回给 Leader。这套逻辑就是 Multi-Paxos 安全的根。选主完成之后Leader 不需要对每个槽位重新 Prepare。它对之前没有值的历史槽位需要用从响应中学到的值去补齐然后对后续新命令直接 Accept(i, n, v)。3.2 日志提交阶段一条日志消息的旅程我模拟一个三节点场景节点 A、B、C法定人数为 2。假设 A 刚当选 Leader提案编号为 1nextSlot 为 5此时槽位 1 到 4 都已完成提交A 要把客户端命令 v 写入槽位 5。A 直接向 B、C 发送 Accept(5, 1, v)。Acceptor 收到后判断提案编号 1 大于等于本地 promisedID 吗如果是就接受这条提案把 acceptedValue 更新为 vpromisedID 保持 1然后向 A 回复 Accepted(5, 1)。这里要注意Acceptor 并不需要等待其他节点再接受一次。只要 A 收到了 B、C 中的任意一个 Accepted再加上自己这一票就凑够了法定人数A,B 或 A,C 或 B,C 都行。A 一旦在本地标记槽位 5 为已提交就可以通知状态机执行 v并异步把“槽位 5 已提交”的消息广播给其他 Learner。但如果 C 因为网络分区没收到 AcceptA 只收到 B 的 Accepted加上 A 自己的票仍然满足 2 节点多数派槽位 5 依然可以提交。C 上线后会通过日志同步或者 Learner 消息补上这段日志而不是重新投票。这也是多数派机制的优势少数派落后完全不影响系统继续推进。3.3 Learner 如何学习提交结果并推进状态机提交和学习是两个环节很多人容易混在一起。Leader 自己可以统计 Accepted 消息确认某个槽位已提交但其他节点并不知道这个事实。工程上常见三种学习方式每个 Acceptor 把 Accepted 消息同时发给所有 LearnerLearner 自己数票数。消息量是 O(n^2)节点一多就爆炸。所有 Acceptor 只把 Accepted 发给 LeaderLeader 统计后广播 Commit 消息。消息量 O(n)是工程里最常用的方式。Acceptor 把 Accepted 发给自己所属 Learner由 Learner 之间再同步适合 Learner 和 Acceptor 分离部署的场景。任何一个 Learner 收到“多数派已接受”的信息后就可以更新本地提交视图。但更新视图不等于可以执行命令因为状态机要求日志连续。如果槽位 5 已提交而槽位 4 还没提交状态机必须等槽位 4 也提交按顺序执行。这个“连续性”约束会在下一节引出填洞问题。3.4 一个完整实例的时序示例我用一张时序表把这套流程压缩起来看节点还是 A、B、C法定人数 2。步骤发送方消息接收方接收方状态变化1APrepare(1)B, CpromisedID 12B, CPromise(1, 无已接受值)AA 获得提案权3AAccept(5, 1, v)B, CacceptedID 1, acceptedValue v4BAccepted(5, 1)AA 统计后判定槽位 5 已提交5ACommit(5, v)B, CB、C 学习已提交日志这张表压缩了实际实现里的很多细节比如步骤 2 里如果 B、C 曾接受过别的值Promise 就会带上那条记录。但核心顺序就是这样先拿提案权再逐槽位提交最后通过 Leader 广播 Commit。从客户端发起到写入成功理想状态就是一个 RTT这也是 Multi-Paxos 相比 Basic Paxos 最大的性能优势。4. 工程实战中的四大难点与我的处理记录4.1 活锁两个 Leader 交替 Prepare 为什么会让系统空转活锁在理论协议里就存在工程实现中更明显。场景是这样的Leader A 用编号 1 完成了 Prepare开始 Accept此时节点 D 因为网络分区没收到 A 的消息它认为 A 已经死了自己用编号 2 发起 Prepare。两个 Leader 同时存在Acceptor 的 promisedID 在 1 和 2 之间来回横跳。A 发现自己的 Accept 被拒绝于是重新用编号 3 发起 PrepareD 看到编号 3 又把编号改成 4。结果就是两个节点不停地抬高编号谁都无法稳定提交。Paxos 协议本身并不保证活性它只是保证一旦有值提交不会被推翻。所以工程系统必须在协议之上增加额外的活性机制。我实践过比较有效的方案是两层配合一层是随机退避Leader 在 Prepare 失败之后等一个随机时长再重试降低两个节点同时抢主的概率另一层是租约机制当前 Leader 在租约期内独占提案权其他节点看到有效租约就不会发起新一轮 Prepare。租约依赖时钟同步这在纯 Paxos 证明里属于额外假设但工程上值得引入它能显著降低活锁频率。4.2 乱序与空洞槽位之间互相等待的坑Multi-Paxos 的日志允许乱序提交这是它比 Raft 灵活的地方也是坑最多的地方。考虑这个场景旧 Leader 在崩溃前已经把槽位 8 填上了命令 x并把 Accept 发给了多数派但槽位 6 和 7 还没有任何值。新 Leader 上台后如果它只按自己的 nextSlot 从 6 开始分配命令就会发现槽位 8 已经被多数派接受了而自己的提案编号又不能篡改那个值只能继承它。问题随之而来状态机必须连续执行槽位 6、7 的空缺不填上槽位 8 即使提交了也执行不了。最直接的解决办法是让新 Leader 为空洞主动提交一条特殊的 no-op 命令占住槽位使得日志可以被连续执行。no-op 命令不会改变状态机状态但它能让日志变完整。实现时需要在 Leader 里维护一个“已分配槽位”的高水位一旦某个更高槽位的提交消息到达遍历它前面的空洞并快速发起 Accept(no-op)。我见过有系统在这里偷懒等到有客户端请求时再顺手填洞结果就是空洞存在期间所有后续日志提交都停摆客户端延迟飙升。填洞应该由后台任务主动触发不能依赖新业务流量。4.3 持久化与故障恢复Acceptor 掉电丢状态的代价Acceptor 必须持久化两样东西promisedID 和 acceptedID/acceptedValue。丢掉 acceptedValue 的后果容易理解新 Leader Prepare 时学不到旧值可能覆盖已提交日志直接破坏一致性。丢掉 promisedID 的后果更隐蔽叫“遗忘承诺”。如果 Acceptor 重启后忘掉了曾经承诺过的编号一个编号很低的旧提案可能被它重新接受而该提案其他节点之前已经拒绝过了重新接受它等于让系统出现分叉。我的处理原则是先落盘后回包。Acceptor 在收到 Prepare(n) 后先把 promisedID 写入磁盘成功后再返回 Promise收到 Accept 后先把 acceptedID 和 acceptedValue 写入磁盘成功后再返回 Accepted。整个过程不许在内存里先答应再异步持久化否则一条日志在 k8s 里不停调度的时候特别容易丢状态。Leader 故障恢复同样要注意顺序。新 Leader 必须先通过 Prepare 从多数派学习已接受值把那些已经提交但还没学到的高槽位补上然后再分配新槽位。如果新 Leader 一上来就急着处理客户端请求而旧 Leader 留下的已提交日志又没有被完整继承就可能造成日志分叉。4.4 编号重生的坑进程重启后如何保证提案编号不重复提案编号必须全局唯一且单调递增这一点在单进程里很容易做用一个原子计数器就行。真正麻烦的是进程重启之后计数器归零而此时其他节点可能还持有旧消息。如果新进程用较小的编号再次发起 Prepare这些旧消息就会被当成更高编号的提案接受系统直接乱掉。我常用的做法是把编号拆成两部分高位为纪元号低位为序号。纪元号可以由节点 Id 加启动时间戳生成也可以从共享存储里读取后加一。每次进程重启时先从集群中查询当前已知最大提案编号再取 max(最大编号 1, 当前时间戳)。同时把发起 Prepare 的编号持久化到本地文件防止异常宕机后丢编号。还有一个容易忽略的细节编号不能只用本地单调递增而是要保证全局所有节点都认为这个编号大于历史上所有编号。最稳妥的办法是让 Leader 在启动时用一次 Prepare 带上它打算使用的编号如果收到任何 Acceptor 返回的 promisedID 更大的信息就立刻抬高编号重试。不要试图靠时间戳打天下时钟回拨是常态。5. Multi-Paxos 与 Raft 的对照同样解决共识为什么 Raft 更受欢迎5.1 协议结构对照Raft 是不少人接触的第一个共识协议它把问题拆成选主、日志复制、安全性三个子问题并且用强 Leader 模型简化了很多场景。这里我不讨论优劣只说它们之间的真实差异。对比项Multi-PaxosRaft日志模型每个槽位独立实例允许乱序写入日志严格连续append 只能从尾部追加选主方式通过 Prepare 抢占编号允许多个 Leader 竞争随机超时触发选举Term 单调递增提交判定某个槽位的值被多数派接受即提交当前任期日志复制到多数派即提交空洞处理需要主动填 no-op天然不存在空洞已提交值继承Prepare 阶段返回最高编号已接受值选举时通过日志匹配找到可追加点实现复杂度细节多容易踩坑结构清晰对实现者友好本质上的安全保证都一样任何已提交的日志都不会被新决策覆盖靠的都是多数派交集。区别在于 Raft 通过日志连续性和选举限制消除了很多病态场景Multi-Paxos 保留更多自由但也把复杂度留给了开发者。5.2 为什么大多数系统选择 Raft 而不是 Multi-Paxos实现难度是第一原因。Multi-Paxos 允许日志空洞状态机执行要处理乱序选主和提交之间还要小心 offset 对应关系。任何一步没做对调试成本都极高。Raft 的日志连续性让实现者少考虑一大类问题不需要填洞不需要处理被旧 Leader 提前分配的高槽位不需要在提交时检查槽位顺序。学习曲线平缓新人也能快速理解。第二是运维和排查成本。Raft 的状态更容易可视化每个节点的 term、vote、log index 都比 Multi-Paxos 的 promisedID、acceptedID、nextSlot 直观。线上出了故障工程师看日志时更愿意看到一个“当前 term5logIndex1024”的界面而不是一堆协议状态机。不过 Multi-Paxos 也不是没有价值。它没有跨节点的日志连续性约束天然适合把不同分片独立提交某些场景下吞吐优势更明显。部分要求极致性能和定制化的闭源系统或者基础架构团队有能力维护复杂协议的场景仍然会选择在 Paxos 家族之上做自研。对大多数团队而言直接落地 Raft 是更现实的选择。5.3 我的选型建议新项目第一次引入共识协议时我的建议是先实现 Raft 或直接使用成熟实现把精力放在业务上。当团队有足够强的分布式协议背景且确实遇到 Raft 无法满足的低延迟或高吞吐瓶颈再考虑 Multi-Paxos 以及它之上的优化方案。毕竟协议只是一层后续的日志 GC、快照、成员变更、流控全是更大的工程问题。如果你只是想理解 Paxos 思想本身也建议先啃完 Basic Paxos 再看 Multi-Paxos再回头看 Raft 的日志连续性设计你会发现 Raft 很多看似“额外”的约束其实都是在帮实现者挡住 Multi-Paxos 里最麻烦的那批坑。6. 常见问题快查表与调试经验6.1 问题速查表现象可能原因排查思路日志长期不提交请求超时Leader 未获得多数派响应或者编号被反复拒绝检查 Leader 选举是否完成检查 Prepare/Accept 是否因网络分区只到达少数节点两个节点同时认为自己可提交活锁或租约失效查看提案编号是否在多个节点间来回跳确认租约到期时间是否过短同一槽位出现不同值Acceptor 丢失持久化状态或新 Leader 未继承最高编号已接受值重点检查 Acceptor 落盘顺序以及新 Leader 是否只看了多数派中的部分记录状态机执行序号跳变日志空洞被错误跳过或提交视图不完整检查 Learner 的提交 index 推进逻辑确认是否等待槽位连续后才执行重启后编号冲突编号生成未持久化或重启后从低值重新计数检查编号生成方案至少保证纪元号或本地水位持久化这些现象里最多见的是第一条说白了就是多数派没凑齐。多数派凑不齐有两种情况一是节点数太少二是网络分区把节点劈成了两个对等的小团体。排查时先看 Leader 是否稳定存在再看 Accept 消息是否到达了足够的 Acceptor。6.2 调试方法如何让 Multi-Paxos 的状态变“可观测”我给所有实现过 Multi-Paxos 的团队一个建议在协议层打日志时务必带上四个字段提案编号、槽位号、acceptedValue、promisedID。没有这几个数字故障时间线根本画不出来。调试时先用三节点集群复现问题通过模拟网络延迟和分区制造边界条件。比如在 Accept 请求发出前停掉节点 B观察 A 是否还能提交在 Prepare 完成后立刻杀掉新 Leader观察新 Leader 能否正确继承旧值。这些场景比压测更能暴露协议实现的 bug。还有一个经验把“提交”和“执行”严格分开打点。提交表示多数派已接受执行表示状态机已经应用。很多问题出在 Learner 把提交当成执行条件导致日志跳跃。如果日志中看到提交 index 有跳跃而执行 index 必须连续就可以快速确认是学习逻辑还是执行逻辑的问题。6.3 一句话安全自查每次修改协议实现后用一个固定脚本连续跑三种场景单节点宕机、双节点分区、连续选主轮换。只要其中任何一个场景出现槽位重复值或执行顺序分叉直接回滚改动。安全属性一旦被破坏靠日志基本救不回来。最后再分享一点我的个人体会把 Multi-Paxos 亲手实现一遍远比读十篇文章有用。我一开始也是对着论文里的伪代码照抄结果第一个版本活锁频发、日志空洞填不上线上测试一跑就崩。后来把每台节点的状态矩阵画出来把消息序列和时间线手工推演了好几遍才算真正理解“Prepare 学到值必须继承”这句话的含义。建议想入门的同学先画一张三节点状态表把 Prepare、Promise、Accept、Accepted 四条消息的一次交互完整走一遍再开始写代码。你会发现 Multi-Paxos 的复杂度不在于单个消息的处理逻辑而在于这些消息在故障和乱序条件下如何保持一致性。