Paxos 这四个字母在分布式系统工程师圈子里几乎是“劝退级”的存在。我最早去啃 Lamport 那篇《The Part-Time Parliament》的时候满脑子都是希腊小岛上的议员、牧师、法案编号硬看了两星期感觉懂了合上书又不知道它到底凭什么让一群节点达成一致。后来因为要自己搭配置中心、做跨机房金额对账被迫把 Paxos 重新拆了一遍才发现它一点都不复杂——复杂的是它被包装在一个议会隐喻里。把“议员”换成服务器“法案编号”换成提案编号整个算法就一句话大家商量着来但是由多数派拍板。这篇文章我打算用最具体的场景、最直白的口语把 Paxos 的三个角色、两阶段流程、安全性原理、工程坑位一次讲透。适合刚接触分布式一致性的同学也适合面试前想快速把 Paxos 理清楚的开发。我不保证你看完能背出 Lamport 原文但我保证你看完能跟同事把一个共识过程从头到尾讲明白并且能动手写出一个最小实现。1. 先从一件糟心事说起为什么系统需要 Paxos1.1 一个能复现的分布式事故双主脑裂假设你维护了一个配置中心两个机房各自有一台服务器正常情况下一台是主Master一台是备Backup主挂了备顶上。这个模型最大的隐患不是服务器宕机而是网络抖动。比如说机房间的交换机充血了 30 秒主节点照样活着备机却以为自己联系不上主了于是它立刻把自己提升为新的主节点。问题来了老主还在服务流量新主也在接受写请求。同一个业务配置两个机房写成了两个版本而且两边都认为自己才是合法的主节点。这是我在生产环境里真实遇到过的问题现象非常隐蔽业务方读配置时从本地机房走所以两边看到的配置一时半会儿不会不一致等网络恢复两个主开始同步数据冲突记录大量弹出业务才炸锅。传统的高可用方案比如心跳、租约本质上是在“预分配权力”你先约定好谁是主大家都听他的。但网络不可靠的时候你没法保证所有节点对“现任主是谁”这件事看法一致。Paxos 换了一个思路任何一次领导权的更迭、任何一条数据的写入都必须让整个集群中的多数派节点亲口确认。只要多数派点头这件事就算定案谁也不能反悔。这样一来两个机房各自拿到半数以下的确认就无法同时当选双主脑裂从根上被堵住了。1.2 Paxos 到底保证了一个什么性质用一句话抽象一群节点里每个节点都可以提出一个值Paxos 保证最终所有活着且能通信的节点会就“选哪一个值”达成一致而且选出来的值必须是某一次真正被某个节点提出过的值不能凭空冒出来一个新值。这里有个容易忽略的点。Paxos 解决的是一次性的“单值共识”大家商量好一个值是 v共识就算完成。真实系统里我们要写一条条日志、一个个配置所以后来才有了 Multi-Paxos 的做法把无数个单值共识串成一个日志序列。但理解 Paxos 的最佳路径永远是先把“一次共识”搞清楚。一次共识搞明白了后面无非是套模板。2. 角色、编号、法定人数三个概念盘清楚算法就懂了一半2.1 Proposer、Acceptor、Learner 分别是谁Paxos 把参与者分成三种角色虽然名字听着洋气但本质特别朴素。Proposer 是“发起提案的人”它负责提出一个编号再提出一个值推动讨论往前走。Acceptor 是“投票箱”它收到提案后表态答应、拒绝、或者告诉对方自己之前收过什么票。Learner 是“吃瓜群众”它不参与决策只需要把已经定案的结果记录走。工程实现里同一个节点往往同时担任三种角色因为服务器身兼数职很正常。我用一个生活化类比帮你把角色焊死在脑子里。一栋老楼要决定加装电梯热心业主Proposer拿着方案挨家挨户征求意见每户代表Acceptor在意见表上签字表态物业和施工队Learner最后只管照着定案开工。如果两拨热心业主同时拿着不同方案敲门整栋楼要怎么避免先签了 A 方案的人又被 B 方案撬走这就是 Paxos 要解决的“盖章”难题。Acceptor 是算法的核心角色它的一切行为非常简单只能记住两个东西一是“我现在最大的承诺编号是多少”二是“我最终接受过的提案编号和值”。只有这两个本地变量没有全局列表也不需要互相通信。这正是 Paxos 厉害的地方全局一致性是靠每个节点只做局部决策达成的。2.2 提案编号全局唯一且单调递增Paxos 每一步都围绕着提案编号Proposal Number展开它必须满足两个条件任何两个节点提出的编号都不会重复编号之间可以比较大小。在工程上最常见的做法是用“逻辑任期号 节点 ID”组成一个复合编号。比如节点 ID 是 3当前逻辑时钟是 41那么编号就可以是41.3比较时先比整数部分再比小数部分。这样做既保证了全局唯一又让“后来者编号一定更大”这个条件天然成立。为什么编号要“更大”因为 Paxos 的规矩是编号大的提案有权打断编号小的提案。如果两个 Proposer 同时跑编号小的那个先发动的流程很可能被编号大的半路截胡。这不是 bug而是设计如此用编号来决定优先级才能让整个系统在任何乱序场景下都能收敛到同一个值。2.3 多数派为什么就够用了quorum 交集的魔力法定人数quorum的标准是 (N/2 1)也就是多数派。比如 3 节点集群2 个节点就算多数5 节点集群3 个节点就算多数。为什么不是所有节点都点头才算数因为活着的节点数量是未知的你没法保证每个节点都不宕机、不分区。如果要求全员确认任何一个节点掉线整个系统就卡死了可用性为零。多数派的好处是只要超过半数的节点还活着系统就能继续推进。多数派还有一个更深层的数学性质任意两个多数派必然有交集。5 个节点的集群两个多数派分别是 3 个节点无论怎么选这两个三人小组里至少有 1 个节点是重合的。这个性质直接构成了 Paxos 的安全底座。后面你会看到当一个新的提案者拿到“多数派承诺”时它必然会收到某个节点报告之前已经接受过的旧值于是它只能在旧值的基础上继续推进而不是另起炉灶。3. 两阶段提交把一次提案的完整流程走给你看3.1 阶段一 Prepare先查旧账再做承诺现在假设我们有 A、B、C 三个节点B 作为 Proposer 打算提交一个值v hello。B 先生成一个编号1然后把Prepare(1)广播给 A、B、C 三个节点。Acceptor 收到 Prepare 请求后逻辑很简单如果这个编号大于自己见过的最大编号它就答应下来记录“我已经承诺不再接受编号小于 1 的提案”然后把自己的承诺反馈回去顺带把以前接受过的最高编号提案的值也告诉 Proposer如果编号不够大就直接拒绝告诉对方“我已经承诺过更高的编号了你往后稍稍”。在我们的例子中A、B、C 都是第一次接触编号 1所以都会回复 B“行我记住了以后小于 1 的我不理但我没接受过任何值。”B 收到两个以上的肯定回复即可进入下一阶段。这里要特别注意B 自己也算一票本地节点可以直接模拟一个 Acceptor 回复自己不需要真的发一条网络消息给自己。3.2 阶段二 Accept正式盖章定案B 拿到多数派承诺后检查这些回复里有没有携带“旧值”。如果有多个旧值就选编号最大的那个如果没有旧值就用自己最开始想写的值。在此例中没有任何旧值所以 B 决定用hello于是广播Accept(1, hello)。Acceptor 收到 Accept 请求后再做一个简单判断如果这个提案编号大于等于自己承诺过的最大编号就接受它记录(1, hello)并且向 Proposer 回复“我接受了”。如果这个编号比自己承诺过的最大编号小就必须拒绝哪怕之前没接受过也不能破例。最终 B 只要收到多数派接受回复就可以断定hello已经被集群“选定”了。就算此时有节点掉线只要多数人记住了这个值它就永久有效。第一次看这个流程的人很容易问“既然 Prepare 时已经拿到了承诺为什么 Accept 阶段还要再次检查编号”因为从 B 发 Prepare 到发 Accept 之间有时间差这期间可能有另一个节点 C 也发起了编号更大的 Prepare并且已经抢走了多数派的支持。Accept 时的二次检查保证了“最后盖章”的那一刻选票仍然有效。3.3 核心安全点为什么后来者必须继承旧值这个点值得单独拉出来细讲因为它是 Paxos 里最容易听糊涂的一环。我换一个反面场景说明。假设 B 带着编号 1 提案helloC 同时带着编号 2 提案world。如果 Paxos 允许 C 在拿到更高编号后直接提world就可能出现这样的乱局B 已经把hello在 A、B 两个节点上盖了章C 又在 A、C 两个节点上把world盖了章而 A 这个节点连着盖了两次。两个值在各得一票的情况下最后谁也没法说服谁系统就分裂了。所以 Paxos 定了铁律Proposer 在收到多数派的 Prepare 回复时只要听到任何一个人说“我之前已经接受过(1, hello)”那么无论自己多想写world都必须在 Accept 阶段改写为hello。你看到没有这不是道德约束而是算法强制。这个强制规则保证了同一轮共识里不可能出现两个没有交集的值只要某个值已经被多数派看重后面所有试图写新值的提案者都会在 Prepare 阶段收到来自交集节点的“旧案通报”然后被迫继承旧值。我建议你把这一小段场景在自己的草稿纸上画一遍画三个圆圈代表 A、B、C用两条箭头分别代表 B 和 C 的提案路径再标出哪个节点同时出现在两个多数派里。画完你会发现Paxos 的所有防错逻辑都只是为了让一句话成立第二个提案者永远不可能带着一个与旧值无关的新值横空出世。4. 从单个值到日志流Multi-Paxos 到底优化了什么4.1 单次 Paxos 的问题每写一条数据要跑两轮广播如果每写一个日志条目都完整跑一遍 Prepare Accept性能会很糟心。每轮共识是两次全集群广播写一条日志要两轮这些成本乘上高吞吐场景网络会先扛不住。况且 Prepare 阶段本身不写入任何新值它只是在反复确认“我有没有资格写”这个确认在系统平稳运行时是多余的。你可以把这种状态类比成每次开会都要重新选一次主持人而实际上会议室里大部分人明明还在讨论同一个议题。重复选主持人就是一种浪费。4.2 Multi-Paxos 的套路先选出一个稳定的 LeaderMulti-Paxos 的核心思路是让系统长期维护一个 Leader也叫主 Proposer由它连续不断地使用递增的提案编号发起请求。因为 Leader 在短时间内是唯一会发起 Prepare 的节点集群里的 Acceptor 已经把承诺编号提到很高的位置再也没有别的提案者来抢票所以跳过 Prepare直接发送 Accept 就是安全的。也就是说稳定场景下 Multi-Paxos 把每次写入从两轮广播压到一轮广播。但这并不意味着可以完全不做 Prepare。Leader 刚上任、或者旧 Leader 失联、新 Leader 接替的那一刻仍然需要跑一轮 Prepare把自己的编号推到全场最高同时确认一下之前有没有被“已定案但还没来得及通知”的值。这个动作等于重新建立权威后续就又可以一路绿灯了。4.3 日志即共识把状态机映射到 Paxos真实系统里我们不是只共识一个hello而是共识一连串操作。常见做法是给每个日志条目分配一个“槽位编号”槽位编号从 0、1、2 一直递增每个槽位用一次 Multi-Paxos 共识来决定该写什么。所有节点把同一条日志序列从头到尾应用一遍就能得到相同的状态机结果。这样数据库的每次写入、配置项的每次变更本质都是“在槽位 N 上共识出一个值”。这里有一个体验上的细节一旦某节点落后它不需要等所有槽位都共识完才补它可以按顺序把漏掉的槽位逐个补上。因为共识结果已经是多数派敲定的补日志只是复制已定案的数据不会再产生新的分歧。也可以多提一句很多知名共识系统的工作原理都是在这个模型的骨架上做工程优化。5. 实操中的坑活锁、乱序、持久化5.1 活锁Paxos 的不一致之锁Paxos 的安全性已经由理论保证意思是它永远不可能出现两个不同的值都被选定。但 Paxos 的一个历史痛点叫“活锁”livelock系统一直在忙却迟迟无法产生共识。假设两个 Proposer 互为死对头。Proposer P1 发起了编号 5 的 PrepareP2 发起了编号 6 的 PrepareP2 抢走多数派承诺。P1 的 Accept 被拒于是 P1 提高编号到 7 再战P2 看到 7 更高也把编号提高到 8两者反复互相打断谁也收集不到稳定的多数派承诺系统陷入永无止境的“抬杠”。解决活锁的标准套路是引入 Leader 选举正常情况下只允许一个 Proposer 干活其他 Proposer 只作为备份。再用随机退避时间进一步降低两个备份同时抢跑的概率。这也是 Raft 等算法更注重“强 Leader”风格的原因它们牺牲了部分灵活性换来了更可预测的活性。5.2 乱序与丢包工程实现对算法正确性的威胁我在第一次实现 Paxos demo 时犯过一个很典型的错误Acceptor 收到编号更高的 Prepare本地改了自己的承诺编号结果进程崩溃了重启后承诺编号丢失又接受了旧编号的提案。从 Paxos 纯理论的角度看算法假设节点不会“失忆”但真实的计算机随时可能断电重启。所以工程化时必须把 Acceptor 的max_promised和last_accepted持久化到磁盘。每次更新必须先落盘再返回确认否则一旦宕机就可能违反承诺破坏安全性。另一个容易忽视的是网络乱序Accept(1, hello) 可能比 Prepare(5) 后到。Acceptor 不能因为刚到的是 Accept 就盲目覆盖必须看编号是否符合承诺。5.3 一张表记住常见故障与排查思路现象可能原因推荐处理办法提案一直被 reject有其他 Proposer 在用更高编号竞争等待随机退避后重试或让 Leader 定期发布心跳压制竞争者Prepare 回复丢失网络瞬时抖动或节点繁忙Proposer 增加超时重试机制重新发起同编号 Prepare 或提升编号某节点宕机重启后参与投票持久化未保证承诺状态没了检查磁盘写入顺序必须落盘后再回 ACK多数派不可达网络分区、节点大面积故障系统进入只读或等待恢复状态因为 Paxos 无法在少数派中完成共识学习到的值有延迟Learner 只能从多数派收集 accepted 消息不需要特殊处理最终一致即可若需快速感知可引入专线通知 Learner6. 一行一行看代码最少可运行的 Paxos 长什么样6.1 Acceptor 的本体就两个状态变量加两个判断我在最开始学习时总以为 Paxos 的实现会很复杂。真正动手做最小实现之后才明白Acceptor 的代码比想象中短得多。核心逻辑如下# 单个 Acceptor 的本地状态 class Acceptor: def __init__(self, node_id): self.max_promised None # 承诺过的最大提案编号 self.last_accepted None # 最近接受的 (编号, 值) def handle_prepare(self, n): # 如果 n 比之前承诺的都大则承诺不再接受小于 n 的提案 if self.max_promised is None or n self.max_promised: self.max_promised n return (promise, n, self.last_accepted) # 否则拒绝并告诉对方当前的最大承诺编号 return (reject, n, self.max_promised) def handle_accept(self, n, value): # 编号必须不小于承诺编号才允许接受 if self.max_promised is None or n self.max_promised: self.max_promised n self.last_accepted (n, value) return (accepted, n, value) return (reject, n, self.max_promised)注意handle_accept里的判断条件是n max_promised因为只要编号没小于自己的承诺接受它就是安全的。而handle_prepare里用的是严格大于因为如果编号等于当前承诺编号说明可能是重复消息不必重复承诺。6.2 Proposer 的最小流程收集承诺再决定写什么class Proposer: def __init__(self, node_id, logical_round): self.node_id node_id self.round logical_round # 构造全局唯一的提案编号用 round node_id 的小数部分复合 self.n round node_id def propose(self, value): promises broadcast_prepare(self.n) # 广播 Prepare if not has_quorum(promises): return False # 从所有 promise 中找到编号最大的旧值 highest None for msg in promises: if msg.last_accepted and (highest is None or msg.last_accepted[0] highest[0]): highest msg.last_accepted # 核心规则如果已经有旧值必须继承旧值 final_value highest[1] if highest else value acks broadcast_accept(self.n, final_value) # 广播 Accept return has_quorum(acks)broadcast_prepare和broadcast_accept是网络层封装真实实现中要处理重试、超时、节点列表变更等。但当你看懂了这段骨架再去看任何成熟的共识库源码你会发现它们的主体逻辑并没有跳出这个框架。6.3 几个从实操中悟出来的经验第一个经验不要把编号做得太随意。用“纳秒时间戳”或“随机数”做提案编号表面看唯一性没问题但无法保证单调递增。我在团队里推荐的做法是每个 Proposer 自己维护一个本地轮次计数器生成编号时把计数器叠加到上一次见过的全球最大编号之上再用节点 ID 保证唯一。这样即使旧 Leader 失联后又回来它的新编号也一定比之前见过的都大。第二个经验测试 Paxos 时不要只测“完好网络”。我当时写了个小脚本在每个消息上按比例随机丢弃、延迟、乱序再同时并发发起多个不同值的提案最终结果依然只可能是某一个值被选定。这类混沌测试是验证安全性的神器。如果你的实现有条日志打出来发现两个节点各自拿到了不同的“共识结果”赶紧回去检查 Acceptor 的持久化逻辑而不是怀疑算法本身错了。第三个经验Paxos 的“共识”只保证一致性不保证即时全局感知。某个 Learner 宕机了恢复后它可能需要追赶之前已经定案的日志这很正常不要把它误判成系统故障。很多运维事故都是因为把“某个节点暂时不知道结果”当成了集群分裂。个人在实际操作中的体会是Paxos 的难点从来不是记住那几个阶段的名字而是搞懂为什么阶段顺序和值继承规则设计成这个样子。我见过不少人能熟练说出 Prepare、Accept、Promise、Quorum但问他“两个多数派一定有交集这个交集为什么能防止提案者提出新值”就卡壳了——而对 Paxos 的理解深度恰恰就体现在这种“追问为什么”的时刻。我自己的学习路径是先把三节点场景手动画十遍再去看 Lamport 原文最后亲手实现一个 100 行不到的 demo。这样一遍走下来Almost 你能应付绝大多数分布式系统的面试和设计讨论。