一致性协议 Paxos 详解二Multi-Paxos 协议流程详解上一篇把 Basic Paxos 里 Prepare、Promise、Accept、Accepted 那一整套握手流程拆了个遍不少读者看完之后问我的问题惊人地一致原理我懂了可这东西到底怎么才能变成一个真正能落地的复制协议这个问题问到了点子上因为 Basic Paxos 本质上只共识“一个值”而分布式系统真正需要的是一台台机器对“一串值”形成完全一致的看法。Multi-Paxos 就是来解决这件事的。这篇文章会把 Multi-Paxos 的完整流程、领导者选举、日志补洞、故障切换等环节全部过一遍适合已经了解 Basic Paxos、准备动手做实现或者想把 Raft 一类协议对照起来理解的人阅读。1. 为什么需要 Multi-Paxos基础 Paxos 的“一次性”困境1.1 基础 Paxos 只能决定一个值先花点时间快速回顾。Basic Paxos 解决的是这样一个问题一群进程里每个进程可以各自提出一个值最后所有进程必须对“哪一个值被选中”达成一致。整个过程要跑两轮网络往返第一轮 Prepare/Promise 确定提案号并收集历史信息第二轮 Accept/Accepted 才真正把值定下来。这里藏着两个致命限制。第一每一轮共识都得从 Prepare 开始哪怕提案者没变、选票号也没变也必须重新做一遍全量询问成本高得离谱。第二Basic Paxos 本身没有“顺序”概念A 先提出的值、B 后提出的值彼此之间没有任何先后约束。共识出了十个互不相关的值等于系统没有任何可运转的状态机。而现实里的复制状态机要求的是完全相反的东西每台机器拿到一串完全相同的命令按同样的顺序执行才能得到同样的状态。所以问题的本质根本不是“共识一个值”而是“共识一条日志”。1.2 从“一个值”到“一条日志”最笨的方案是每条日志条目单独跑一遍 Basic Paxos。这个方案能工作但代价非常具体。假设系统每秒要共识几千条命令每条命令前面都先来一轮 Prepare 全量广播网络开销直接翻倍。更糟的是只要选举状态有任何扰动导致提案号变化所有在途的 Accept 都可能作废吞吐量会被打到骨折。Multi-Paxos 的思路反直觉但极其聪明与其让所有节点公平竞争提案权不如先选出一个稳定的“领导者”让领导者长期独占提案权。领导者不换Prepare 阶段就可以只做一次之后所有日志条目统统只走 Accept 这一轮。这样一来每条命令从两轮 RTT 降成了一轮而且因为选票号长期不变基本不会出现提案被作废的情况。可以这么说Multi-Paxos 的全部设计哲学就是围绕“领导者稳定”这四个字展开的。后面所有步骤——选举怎么选、补洞怎么补、日志怎么推——都是在为这个核心假设服务。2. Multi-Paxos 的核心模型与设计取舍2.1 日志槽位一组共享编号的 Paxos 实例Multi-Paxos 里整个日志被切成一个个槽位slot槽位编号从 1 开始单调递增。第 i 个槽位本质上就是第 i 个 Basic Paxos 实例每个实例负责共识一个值。Paxos 的经典保证可以逐槽位套用任意一个槽位里最多只有一个值能被选中。这里需要强调“选中”的定义。一个值在槽位 i 被选中当且仅当它被一个多数派接受。一台机器觉得自己提交了不代表系统真的提交了要看有没有形成法定多数。因此接受者acceptor必须为每个槽位记录自己接受了什么值、这个值是在哪个选票号下接受的并且把这些记录持久化。这是后面一切安全推理的基底。从数据结构上看每个接受者需要维护两个东西一个全局的 promised 选票号代表自己承诺过的最高选票一个按槽位索引的已接受记录表记录 (slot, value, acceptBallot)。这两个东西缺一不可少一个都会在故障场景里翻车。2.2 领导者机制把两轮 RTT 摊平成一轮Multi-Paxos 的关键设计决策是选出一个 distinguished proposer即领导者。领导者用同一个选票号 b 连续对各个槽位提案。因为 b 不变后续每个槽位的 Accept 都能通过接受者的选票号检查所以不需要再 Prepare。但“一次 Prepare”能成立有个非常硬的前提新选出来的领导者必须先搞清楚自己当选之前各个槽位里可能已经有哪些值被选中了。如果它不知道就可能对一个已经选定了 X 的槽位去提 Y结果两个值分别在系统里被多数派接受日志就裂了整个集群的状态从此分叉再也对不齐。所以选举阶段的 Prepare 消息特意不带槽位号等于一次性覆盖全部槽位。接受者收到后不仅承诺“不再接受选票号小于 b 的提案”还要把自己知道的所有已接受值都汇报上来。领导者拿到多数派的汇报后才能安全地决定哪些槽位沿用旧值、哪些槽位可以提新值。理解这一点你就理解了 Multi-Paxos 和基本 Paxos 最本质的区别基本 Paxos 的 Prepare 是在每一轮提案前做的“安全性检查”Multi-Paxos 把这一轮检查提前到了领导者上任那一刻后面整个任期都吃这轮检查的红利。2.3 选票号的工程化设计选票号在 Multi-Paxos 里比在 Basic Paxos 里更重要因为领导者整个任期都在用它。它必须满足三个性质全局唯一、严格全序、单调递增。实践中最常见的做法是二元组 (epoch, nodeId)比较时先比 epoch 再比 nodeId。比如 (2, E) 大于 (1, A)因为 epoch 更大如果两个候选并发选举nodeId 能保证不会产生完全相同的选票号。这里有一个新人最容易踩的坑选票号只在内存里自增进程重启后从零重新开始。假设某次选举选出了选票号 (2, E)E 还没来得及让所有接受者都看到就崩溃了。重启后的 E 又用 (2, E) 发起选举而另一台节点 F 已经用 (3, F) 当选了一轮那么 E 的 (2, E) 就可能被一部分没有记录过 (3, F) 的接受者当成“更新”的选票号接受两个领导者同时生效共识直接崩坏。正确做法是选票号持久化或者用单调不回退的来源生成。3. Multi-Paxos 完整协议流程拆解3.1 领导者选举阶段一次 Prepare 覆盖全部实例候选者 C 想当选完整流程分四步。第一步C 生成一个新的、比当前已知最大选票号还要大的选票号 b (epoch, C)向所有节点广播 Prepare(b)。第二步每个接受者收到后比较 b 和自己记住的最高承诺选票号 promised。如果 b 更大就更新 promised b并回复 Promise(b)同时附上自己已知的所有已接受值格式一般是 (slot, value, acceptBallot)。如果 b 不够大接受者可以回一个拒绝消息或者干脆不回复。这里要注意接受者在把 promised 写入磁盘之后才能回复顺序不能反。第三步C 等待多数派包含自己在内的 Promise。收到之后把汇报按槽位汇总对每个槽位找到汇报中出现过的最高 acceptBallot 对应的值这个值就是该槽位当前的“安全值”。第四步如果拿到了多数派 PromiseC 正式成为选票号 b 下的领导者进入补洞和提案阶段。一个容易在实现里漏掉的细节是候选者计算多数派时必须确认自己算不算一票。有的实现里接受者是独立进程候选者自己不参与 Accept那多数派就是集群中超过一半的接受者有的实现里候选者自己就是接受者之一那自己那票要算进去。漏算自己这一票会导致整个集群活活凑不出一个多数派。3.2 日志槽位补洞新领导者必须做的第一件事新领导者拿到 Promise 汇报后眼里的日志通常是不完整的。每个槽位需要分三种情况处理。第一种某个值在汇报里被多数派报告过。那么这个值确定是被选中的领导者必须原封不动地沿用没有商量余地。第二种有汇报但没有形成多数派比如只有一台机器报告了值 Y其他机器没报告。此时 Y 存在“可能已经或者即将被选中”的风险。稳妥的协议规则是领导者应当沿用所有汇报中 acceptBallot 最高的那个值。这么做牺牲了一点提案自由度换来了绝对安全。第三种没有任何汇报。这个槽位对领导者来说是未知的可以安全地填充新命令。这里经常有人问我的多数派 Promise 里根本没看到 X为什么还要沿用 X原因是汇报里出现的值可能来自一个曾经参与过多数派接受、但后来部分节点宕机消退的旧格局。你看到的只是幸存者的少量汇报真实的共识历史可能比这复杂。死守“最高选票值”这条规则才能保证任何在旧任期里真正被选中的值都能被新领导者继承下来。补洞操作本身也是走 Accept 流程领导者把安全值填充进对应槽位广播给多数派确认这个槽位被正式选中。如果旧值本来就已经被多数派接受了这轮 Accept 通常只是走个形式很快就能收到 Accepted 回复。3.3 正常提案阶段Accept 与选择判定补洞完成之后领导者进入稳态客户端命令的流转分四步。领导者为命令分配下一个空槽位 i构造 Accept(sloti, ballotb, valuev)广播给接受者。接受者检查 b 是否大于等于自己承诺过的 promised满足则接受把 (i, v, b) 持久化然后回复 Accepted(i, b)。领导者收到多数派 Accepted 后判定槽位 i 的值 v 被选中也就是提交commit并推进应用指针。这里有一个实现上的分歧点接受者回复 Accepted 之后这个消息要不要广播给所有学习者两种做法都有真实系统在用。由领导者统一转发的方案消息量小但坏处是如果领导者在提交后立即宕机其他节点可能都还没学到这个已提交的值——不过没关系后续新领导者在补洞阶段还能通过 Promise 汇报把这个值挖出来。接受者直接广播的方案学习延迟低但消息量是平方级增长每封 Accepted 都全量广播集群一大就扛不住。我建议先按领导者统一转发的简单版本做性能不够再考虑优化。配合下面的消息类型参考表可以把这一节的内容串起来。消息发送方接收方内容关键作用Prepare候选者/领导者全部接受者选票号 b申请承诺收集历史信息Promise接受者候选者选票号 b已接受值列表承诺不再接受低选票汇报历史Accept领导者接受者槽位号 i选票号 b值 v真正写入值Accepted接受者领导者槽位号 i选票号 b确认接受形成多数派依据Learn领导者学习者槽位号 i值 v提交信息传播已提交结果3.4 客户端交互与日志应用客户端协议这块最容易被忽视但线上出问题最多的恰恰在这。客户端把命令发给领导者领导者把它编进槽位提交后再把结果回给客户端。问题在于如果在“提交完成”和“回执到达客户端”之间网络闪断客户端会重试同一条命令。如果重试的时候这条命令又被当成新命令编进新槽位那状态机就会把同一条命令执行两遍产生严重的数据错误。解决办法是给每条命令分配全局唯一的请求号槽位里存的是 (requestId, command)执行时按请求号判重保证只执行一次。另一个要点是应用顺序。即使槽位 1、2、3 同时被选中也必须严格按 1→2→3 的顺序应用到状态机。Multi-Paxos 没有 Raft 那种“领导者日志完整性”的强保证所以可能出现槽位 2 已经提交、槽位 1 在某台副本上还没学到的局面。应用层必须维护一个滑动窗口只有前缀连续时才能往前推进否则先缓存等缺失的条目补齐之后再继续。4. 一个完整的故障切换例子4.1 场景设定与初始状态假设集群里有 A、B、C、D、E 五台节点A 是当前领导者选票号是 (1, A)。此时此刻的日志状态如下槽位 1 的值 X 已经被 A、B、D 三台节点接受多数派成立X 正式被选中槽位 2 的值 Y 刚发出 Accept目前只有 A 和 B 两台节点接受了C、D 还没收到这条消息E 也没收到所以 Y 还没有被选中。就在这个当口A 突然宕机。这个场景是教科书里最常见的故障案例也是最考验协议正确性的时刻。整个系统当前唯一“确定”的事情只有槽位 1 的 X 已经被共识了槽位 2 处于薛定谔状态可能被选中也可能永远达不到多数派。4.2 宕机与重新选举集群发现 A 失联触发心跳超时。E 决定发起一轮选举广播 Prepare((2, E))。B、C、D 收到之后分别检查自己记录的 promised 选票号——还是 (1, A)——发现 (2, E) 更大于是更新 promised 并回复 Promise。注意几台节点的汇报内容并不一样。B 汇报槽位 1 接受了 X选票号 (1, A)槽位 2 接受了 Y选票号 (1, A)。C 只汇报槽位 1 的 X。D 也只汇报槽位 1 的 X。A 已经宕机不回E 自己从来没有接受过任何值。E 汇总之后得到结论槽位 1 的 X 出现在 B、C、D 三份汇报里明显是多数派选中的直接沿用 X。槽位 2 只有 B 一份汇报不是多数派但汇报里最高的 acceptBallot 是 (1, A)对应的值是 Y。按安全规则E 不能自作主张给槽位 2 提新值 Z只能沿用 Y 重新发起 Accept。于是 E 开始补洞对槽位 1 发送 Accept(1, (2, E), X)对槽位 2 发送 Accept(2, (2, E), Y)。C、D 收到后接受两个槽位都正式确定为 X 和 Y。补洞完成之后E 才给后续的空槽位分配客户端新命令。这个例子值得反复咀嚼的地方在于E 是从一份不完整的、只有三台节点的 Promise 汇报里安全地重建出了完整的日志前段。它没有看到 A 对槽位 2 的接受记录但看到了 B 的所以沿用 Y。如果 B 当时也没收到 Y那么槽位 2 在整个系统里就没有任何已接受值E 直接提 Z 也完全安全因为 Y 从未进入多数派。“看得到的才继承看不到的可以另起炉灶”这条边界就是 Paxos 安全性的精髓。4.3 新领导者上任后的推进细节E 上任之后还有两个容易被忽略的动作。第一E 需要把自己缺失的日志条目从其他副本处同步过来。补洞保证了“协议层”的槽位值不冲突但 E 可能连很久以前的旧日志条目都没有比如槽位 -1 之前的快照或者更早的命令。这时候需要一条数据同步通道从某个日志完整的副本那里拉取旧条目才能让本地状态机追到最新。第二E 在接受客户端新命令之前应该确认自己的日志前缀已经连续。否则会出现“槽位 5 被选中了但槽位 4 我还没学到”的尴尬局面。强行推进应用会导致状态机跳过命令规则上决不允许。实操上我习惯把补洞分成两个层次协议层的补洞靠 Promise 汇报加 Accept 完成保证槽位值不冲突数据层的补洞靠日志同步接口完成把旧条目拉到本地保证可以连续应用。这两个层次混在一起处理是很多实现调试起来痛苦万分的根源。5. 实操中的常见问题与排查心得5.1 日志空洞与乱序应用我自己在实现里踩得最深的一个坑是某个槽位被选中了但它前面的槽位还是空洞于是我“好心”地先把后面的命令应用了。这个行为看着无害实际上会在下一轮故障切换后彻底搅乱状态机。正确做法是维护一个 nextToApply 指针只有指针指向的槽位存在且已提交才推进空洞存在时宁可让整个应用线程阻塞也不要跳过去。线上表现最多是某台副本状态落后但绝不会错。另一种常见表现是“幽灵提交”。领导者以为槽位 i 的值 v 提交了但其他副本根本没学到领导者一崩溃新领导者的 Promise 汇报里也没有 v于是槽位 i 被填了新值。这是完全合法的因为 v 没有真正被多数派确认过。但客户端可能已经收到了“执行成功”的回执。要缓解这个风险只能在提交阶段做得更保守领导者广播 Accept 之后必须等多数派 Accepted 都回来了并且确认自己这一票也在多数派之内才允许把回执发给客户端。回执发早一毫秒都可能喂出幽灵结果。5.2 领导者抖动与效率暴跌Multi-Paxos 的一切效率优势都建立在领导者稳定上。如果两个候选节点同时发起选举选票号互相压制压来压去就会进入活锁谁都没办法稳定提案系统吞吐瞬间归零。这不是理论恐怖故事我在测试环境里真实复现过——两台节点的心跳超时设置得太接近加上网络抖动每隔几秒就换一次主日志半天推不动一厘米。解法是老三样。第一选举超时加随机化让多个候选者发起选举的时间点天然错开。第二选票号递增时加入退避机制候选者发现自己的选票号落后时不要立即加一重试而是随机等一段时间。第三当选之后给领导者一个短暂的“稳定窗口”在这个窗口内其他候选者不轻易发起新的选举。Raft 很讨巧地把这套机制做成了协议标准的一部分Multi-Paxos 的实现里你要自己补上。5.3 持久化选票与已接受值安全性的最后防线接受者必须在回复 Promise 或 Accepted 之前把新的 promised 选票号、已接受值全部刷进磁盘。这一步不做前面所有协议推演全是空中楼阁。举个例子接受者承诺了 (2, E)但没持久化就宕机重启后 promised 恢复成 (1, A)这时它收到 (1, A) 的 Accept 会照单全收两个值在同一个槽位里被不同多数派选中的灾难就此埋下。这个坑几乎不可能靠常规测试发现因为需要“承诺后宕机恢复 旧选票号再次出现”这种连环巧合。正确姿势是代码评审阶段逐行检查回复路径上的持久化调用然后配合故障注入测试专门模拟“回复前断电”的场景。我见过不止一个项目在评审时把这个点漏掉最后在线上用事故换来了教训。5.4 与 Raft 的对比简化不是没有代价Raft 可以看作 Multi-Paxos 的一个强约束特例。它保证新领导者的日志必然包含所有已提交条目所以不需要补洞流程它强制日志连续性所以没有空洞它把选票号简化成 term把领导者选举做成独立模块。这些简化让 Raft 的实现难度大幅下降所以现在新项目普遍选 Raft而不是 Multi-Paxos。但这不意味着 Multi-Paxos 没有价值。它更接近共识协议的本质模型很多高级优化思路——比如乱序并行提案、慢领导者切换、日志条目分片——都是从 Multi-Paxos 的模型里生长出来的。理解 Multi-Paxos 的人回头看 Raft 会有一层“原来你只是把某些特殊情况固化了”的通透感反过来只背 Raft 流程的人遇到 Raft 处理不了的异常场景往往不知道应该往哪个方向思考。维度Multi-PaxosRaft新领导者日志完整性不保证需补洞保证补洞流程必须实现不需要日志空洞允许存在不允许提案效率同等条件下高略低受日志连续性约束实现复杂度高中学习曲线陡缓6. 最后一些来自实操的体会我个人的体会是Multi-Paxos 的代码量其实不大真正难的是让每一个全局状态转移都经得起“谁崩溃了、什么消息丢了、什么时候重启了”这三连追问。建议动手实现的时候先画一张以槽位为横轴、选票号为纵轴的二维表格把每个消息都当成在表格上的一次划线操作。然后写一个支持随机崩溃注入的测试环境跑上几百万次随机场景任何一条安全性和活性断言失败都停下来查不要跳过。另外如果有人问我“到底该用 Raft 还是 Multi-Paxos”我的回答一直很直接如果目的是做产品上线选 Raft 这一类的成熟实现稳、快、工具链齐全如果目的是吃透共识协议那无论如何也要亲手把 Multi-Paxos 的补洞流程写一遍。把那道“新领导者从 Promise 汇报里重建日志”的题做明白了你以后再看任何分布式存储系统的实现都会比别人快出不止一个身位。