1. 共识问题与Paxos的起源在分布式系统这个领域待久了你会慢慢发现一个绕不过去的核心问题共识。通俗点说就是一群各自为政的节点怎么对同一个结论点头认可。比如有三个数据库节点用户刚写入了一条数据“余额100”结果落到了节点A上另外两个节点还不知道。这时候客户端去节点B查询发现余额还是0数据就“丢”了。解决这类问题的关键在于所有节点必须对“哪个值是最终版本”达成一致而且这个一致不能靠某个节点发号施令因为节点本身也会宕机、网络也会分区。这个问题的学术名字叫“拜占庭将军问题”的简化版也就是在不存在恶意节点、但存在宕机和消息丢失的情况下如何安全地达成一致。1982年Lamport老爷子提出了这个问题但真正给出一个工程上可用的答案是在1990年他发表的Paxos论文里。有意思的是这篇论文最初被多个期刊拒绝因为评审觉得“太抽象、太数学化了”。后来Lamport在1998年重新整理并加入了大量童话故事般的类比才逐渐火起来。你可能会问为什么今天还在学一个三十多年前的算法理由很现实Google的Chubby锁服务用它做底层ZooKeeper的Zab协议本质上借鉴了Paxos的精髓etcd的Raft也是在Paxos基础上做了更易理解的工程改良。可以说没有Paxos打底现代分布式系统的一致性设计就无从谈起。理解了Paxos你再看其它一致性协议基本就是“换了个马甲”而已。2. Paxos解决的问题与基本运行机制2.1 什么场景下非用Paxos不可先说清楚Paxos不是银弹它解决的问题极其具体在一个由多个节点组成的集群中客户端会提出某个值比如一条数据库写操作、一次配置更新、一次选主结果Paxos的任务是让所有节点最终选定同一个值并让这个选定结果被所有节点感知到。听起来简单但难点在于节点可能随时宕机也可能恢复消息可能延迟、重复也可能丢失网络可能分区导致节点之间暂时无法通信整个系统没有全局时钟无法用时间戳来判断先后。Paxos不处理拜占庭问题恶意节点伪造消息也不保证“实时性”或“活锁绝对避免”——这两点是它后来被Raft改进的地方。也就是说Paxos视野里的节点最多是“懒”或“慢”但不会撒谎。从工业实践来看Paxos最典型的落地场景是分布式锁服务中多副本对锁状态的确认配置管理系统里多节点对同一版本配置的加载日志复制系统中确保每个节点的日志序列完全一致。2.2 Paxos中的“官衔”划分Paxos把参与者分成三种角色你可以直接理解为三种“职位”Proposer提案者负责发起提案替客户端提交要写入的值。客户端可以把Proposer理解成一个窗口它专门接收外部请求然后尝试推动集群达成一致。Acceptor接受者负责投票。它对收到提案进行审核有权决定“我同意”或“我拒绝”。集群中的节点通常既是Acceptor又是其他请求的存储者。Learner学习者不参与投票只记录最终结果。在实际系统中Learner往往也是存储节点负责把最终确定的值落盘。有个关键点必须强调角色之间不是物理隔离的。同一个节点可以同时扮演Proposer和Acceptor。比如一个三节点集群三个节点都既是Proposer又是Acceptor这是最常见的部署模式。为了帮助理解我用一个投票类比来预演一遍假设你们公司要选一个年会场地A、B、C三位同事负责投票但A可能临时出差、B可能网络不好。Paxos相当于设计了一套规则保证只要有过半数人至少两人在线并同意就能选出一个确定地点且不会被另一位后到场的同事推翻。2.3 关键概念任期编号与法定人数Paxos最容易被初学者忽略的是“提案编号”的设计。每个提案都带一个全局递增的编号n而且这个编号必须满足两个要求每个Proposer生成的编号必须唯一不能和别的Proposer产生冲突每次新提案的编号必须大于之前所有提案的编号。这里隐含着一个工程难点如果集群里有多个Proposer并发发起提案怎么保证编号唯一没有全局时钟不能靠时间戳。实际工程中常用的做法是在编号中拼接节点标识例如用“轮次号×节点总数 节点ID”的方式或者采用“高32位是轮次低32位是节点ID”保证同一个轮次内不会有重复编号。法定人数Quorum是另一个核心参数。Paxos要求所有投票环节必须获得超过半数的Acceptor确认。为什么要“超过半数”而不是“全员”原因是要在“容忍故障”和“防止脑裂”之间取得平衡。打个比方如果要求全员同意那么只要一个节点宕机系统就无法工作可用性太差如果只要求一个节点同意那两个节点各自同意不同值系统就会分裂。过半数的设计恰好保证了任意两个Quorum之间必然存在交集这个交集节点就是打通两个决策的桥梁。这也是整个Paxos正确性的几何学基础。3. Phase 1详解Prepare——侦察与许诺Paxos操作被分成两个阶段每个阶段又细分成两步。第一阶段叫Prepare它的任务是“侦察”集群的现状并“锁定”后续操作的边界。3.1 Prepare请求的发送与编号选择Proposer决定发起编号为n的提案它会向所有或至少半数以上的Acceptor发送Prepare(n)请求。这个请求不携带具体提案值只带编号。你没看错第一阶段是“空手探路”。所以Prepare请求本质上是询问两件事你之前接受过编号小于n的提案吗如果接受过请把那个提案的编号和值告诉我。设计这个环节的动机在于后续真正提交值时我需要确保我的值不会和之前集群已经暗示接受的值冲突。如果之前有过被多数派接受的值新的提案者必须“继承”这个值而不是另起炉灶。这个设计在许多分布式系统中都有对应物。你可以把它类比成一次房产交易前的“产权调查”你相中一块地先不急着签合同而是去国土局查一下这块地有没有已被抵押或转让的记录。如果有你的合同必须基于已有的记录来写而不能凭空编造一个新的合同。3.2 Acceptor如何响应Prepare每个Acceptor在收到Prepare(n)后会变得“守信用”。它承诺两件事如果当前没有接受过编号更大的Prepare就对n做出承诺不再接受编号小于n的Prepare请求如果自己之前接受过任何提案就把“编号最大的已接受提案值和编号”作为响应附带给Proposer。这里有个细节需要反复咀嚼Acceptor不是简单回复“好的我看过了”而是做了一个单方面的“断交声明”“只要我答应了n任何编号小于n的后续请求我都不会再响应了”。这意味着Prepare会不断压缩可协商空间直到只剩一条路可走。我经历过的一个真实案例有一次在实现Paxos时最初没有保存“已接受提案值”的响应结果出现了这样一个问题——新提案者永远不知道集群之前已达成过什么结论导致新提案覆盖掉了旧结果。我们必须明白Acceptor在Prepare阶段不仅要说“我同意这个编号”还要“报告历史”这个历史是后续Phase 2能够正确传值的关键。3.3 Prepare阶段的“多数派”意义Prepare阶段只需要收到过半Acceptor的响应就可以继续。假设集群有5个节点发送Prepare到全部5个节点只要收到其中3个的响应哪怕另外2个宕机Proposer就能进入Phase 2。为什么过半就够了回顾Quorum交集的原理如果另一个Proposer也发起了编号更高的Prepare它必然要获得另一个过半集合的响应。两个过半集合必有重合节点那个重合节点既然回复过你的Prepare它就不会接受更高编号之前的旧值。这个逻辑是数学上的保证不依赖任何节点的“自觉”。不过落到工程实现上还要处理一个令人头疼的问题Acceptor对Prepare的响应可能是异步的Proposer怎么知道“等了多久算超时”没有万能的通解常见的处理是把超时时间设置为基础网络RTT的3到5倍并辅以指数退避重试。4. Phase 2详解Accept——提交与确认Prepare是“问路”Accept则是“走路”。但这条路不是一开始就能大步走的它的路线完全被Prepare阶段的结果锁死了。4.1 值的选择规则Proposer收到过半Acceptor对Prepare(n)的响应后开始构造真正的提案。这里存在一个决定全局正确性的规则如果所有响应中“已接受的提案值”字段都为空说明之前的提案都没有被过半接受过那Proposer可以自由选择任意值比如客户端传入的新值如果响应中至少有一个“已接受的提案值”Proposer必须选择其中编号最大的那个值而不能选择自己的新值。为什么强制继承因为那个值可能已经形成了事实上的多数派认可如果新提案者强行插入新值就会破坏“已存在的多数决定”这条基本原则。这就好比一场选举中已有人获得了51%的票数后来的计票员必须按照当前数据继续统计不能重新定义选票。用一句话概括Prepare决定了“我允许用哪个编号提交”Accept决定了“我用什么值提交”。前者是路由器后者是货物。4.2 Accept请求与Acceptor的最终承诺Proposer构造好提案(n, v)后向Acceptor发送Accept(n, v)请求。每次Acceptor接收这个请求都要做一次检查如果当前没有响应过编号大于n的Prepare就接受该提案并将(n, v)记录到本地存储如果已经响应过编号大于n的Prepare就拒绝这个Accept请求返回一个带有“当前最大编号”的拒绝响应。这里需要特别注意Acceptor接受提案后理论上可以立刻响应客户端“值已选定”但更稳妥的做法是等本阶段也拿到多数派的确认由Proposer汇总后统一向Learner广播。工程上还有一个容易踩坑的地方Acceptor必须持久化自己“已响应的最大编号”和“已接受的提案值”否则一旦节点重启它就忘了自己对编号n的承诺那个承诺就形同虚设。我当时在测试环境中忽略了这一点直接用内存存储结果节点一重启整个Paxos流程就像失忆症患者一样重新开始最终“一致”的结果在所有节点上根本对不齐。4.3 两阶段为什么缺一不可你可能已经在想Phase 2直接向Acceptor发Accept不就行了吗干嘛要先走一轮Prepare用一个例子解释假设集群有3个节点P1先发送Accept(1, vA)给A和B同时P2发送Accept(2, vB)给B和C。如果B先收到编号1的请求并接受然后收到编号2的请求并接受最终C也接受了vB那集群里A和C各自认定不同值A认为选了vAC认为选了vB系统彻底分叉。加入Prepare阶段后这种情况就被“编号压制”机制避免了。编号低的提案在Prepare阶段就会被节点预设的“更高编号优先”规则直接拦住根本无法形成规模。从抽象设计角度来看这两阶段本质上是把一个“不稳定的瞬时多数”升级为“稳定且可追溯的持久多数”。Paxos真正的巧妙之处不在哪个阶段单独做了什么而在两个阶段的约束组合起来的情况下任意并发交错都能收敛到同一个值。5. 形式化描述与正确性直觉5.1 打个比方拍卖行的举牌规则很多人第一次学Paxos觉得晦涩主要卡在各种“承诺”“接受”的语义上。我换个场景拍卖行。想象一个拍卖师正在主持一场“特殊拍卖会”规则如下每一轮竞拍有一个递增的轮次号竞拍者Proposer先向拍卖行Acceptor提交一个“探测牌号”询问“我下一轮能拍到多少号”拍卖行回复“探测牌号”时会标记一个保证如果已经有更高的成交记录这个牌号就不能再低拿到探测反馈后竞拍者再带着具体出价来竞拍。这个例子里Prepare阶段就是“探测行情的合法性”Accept阶段就是“正式出价的执行权”。之所以要“探测先行”是因为拍卖行要避免你出价时发现已经有人以更高的号牌锁定了同一件拍品那样就会造成混乱。这和Paxos对编号的约束如出一辙。5.2 核心正确性证明的直觉Paxos的正确性可以通过归纳法证明但我不打算堆数学公式只说证据链的直觉假设有两个Proposer P1和P2各自提出编号为n1和n2的提案且n1 n2。如果P1的提案在某个Quorum Q1中被接受了那么P2的提案若要被接受必须经过一个Quorum Q2的Prepare确认。由于Q1和Q2必定相交交点节点X一定响应了P1的Accept且接受了v1同时X也会响应P2的Prepare并把它已接受的值v1告知P2。根据“继承最大值”规则P2就必须选择v1而不是自己新生成的值。这样即使有两个并发提案最终也只可能收敛到同一个v1。这个几何证明是Paxos的核心骨架。每次我看到有人问“Paxos怎么保证不分裂”我都建议他们先画这个两个圆相交的图而不是急着看代码。只要交集节点一直遵守“报告历史值”的规则后续所有新提案都会被迫跟随历史。5.3 多数派为什么是N/21而不是N/2有人会抠细节为什么多数派要求 N/21 而不是 N/2比如3节点集群过半是2那N/2向下取整是1为什么不是1从数学上讲两个过半集合的交集非空必须满足 |Q1| |Q2| N。而最小的情况是 |Q1| |Q2| K那么 2K Nk最小为 floor(N/2) 1。如果k取 floor(N/2)在N为偶数时可能 2K N两个集合可以完美不相交。比如4节点集群两个各有2个节点的Quorum完全可能互不重叠。一旦互不重叠一致性保证就土崩瓦解了。这也能解释为什么生产环境很多系统选择奇数节点奇数节点同样能够保证N/21的多数派不会因网络分区而出现两个对等多数派。比如5节点集群分成2和3只有3能形成多数派下结论的唯一路径就在这个3节点组内另一个组无法单独决策。6. Paxos的具体运行案例一步一步走通6.1 场景设定三节点集群无故障假设集群有节点A、B、C客户端通过Proposer P1提交值“x1”。P1初始化提案编号为1向A发送Prepare(1)同时向B发送Prepare(1)也可以发给全部3个节点。A和B都没有接受过任何提案因此响应一个空的历史记录“已接受编号无已接受值无”。P1收到来自A、B两个节点超过半数的响应后确认没有历史提案值于是自由选择新值x1。接着P1构造Accept(1, x1)发送给A和B。A和B收到后各自检查自己“已响应的最大编号”发现都是0小于1于是接受并记录。A和B返回接受确认P1汇总后有2个确认达成共识向Learner广播“x1已确认”。整个过程干净直接。6.2 场景设定三节点集群旧值被选中则必须继承现在稍微复杂一点。假设在P1运行到一半时另一个Proposer P2也准备提交“x2”。P2选取编号2向B和C发送Prepare(2)。注意P2选的是B和C这节点集合恰好和P1的接受集合A、B有交集B。B在收到Prepare(2)时已经接受了提案(1, x1)于是它返回“已接受编号1已接受值x1”。C没有接受过任何值返回“无”。P2收到B和C的响应后检查发现存在历史值x1且其编号为1于是P2丢弃自己的值x2构造提案(2, x1)向B和C发送Accept(2, x1)。B和C接受后集群最终确认的还是x1。这个例子充分展示了“继承历史值”规则的价值即使后来者试图提交新值只要历史上有过半节点接受过某个值新提案者就只能当“搬运工”不能当“创作者”。6.3 场景设定节点宕机但系统仍可用假设集群五节点其中D节点宕机。P1向A、B、C、D发送Prepare(1)D无响应A、B、C返回“无历史值”。P1收到A、B、C三个响应满足过半继续Accept(1, x1)D仍然无响应但A、B、C确认接受。即便D恢复后看不到x1的记录它也没有资格推翻结果因为每当它作为Acceptor收到更高编号的Prepare时它只能报告自己没有接受过值但这个“无值”并不会影响已经形成的多数派。系统整体可用性不受单节点宕机影响这就是Paxos容忍故障能力的表现。但注意如果D恢复后参与新的Prepare且它刚好是“已接受历史值”的交集节点那么它会报告空历史而另一个节点B会报告x1最终依然会追回正确值。这里最怕的情况是D恢复后既没有持久化又成为了新提案的Quorum中的唯一“历史记录者”那依赖的就是其他节点的报告来补全历史了工程上必须确保持久化有效。6.4 活锁Paxos的“隐形坑”活锁是Paxos最有趣的“缺陷”两个Proposer交替提高编号导致没有提案能够稳定通过Prepare阶段。实操中的典型表现P1用编号1发送PrepareP2用编号2发送Prepare。Acceptor收到编号2后可响应P2并拒绝编号1P1收到拒绝后重试编号3此时P2可能被编号3压制P2再重试编号4……如此循环永远无法进入Accept阶段。算法理论允许这种情况但工程上必须处理引入随机退避被拒绝的Proposer等待一个随机时间再重试降低两个Proposer死磕的概率引入Leader机制选举一个Leader只有Leader能发起Proposal从根本上消除并发竞争。这也是Multi-Paxos最常见的优化方式后面会细说。7. 从基础Paxos到Multi-Paxos工程化改造7.1 基础Paxos为什么不适合直接在生产环境使用基础Paxos有两个“工程原罪”一是每确认一个值都要经过两轮RTTPrepare Accept写入延迟高二是不指定谁是Leader任何节点都能发起提案活锁风险大。如果每次写入都跑一遍Paxos三节点集群的写入性能大约只有几百TPS这在现代生产环境中不可接受。所以工程上几乎不会直接部署单实例Paxos而是扩展成Multi-Paxos。7.2 Multi-Paxos的核心优化Multi-Paxos的思路是在集群中先选举出一个稳定的LeaderLeader选举本身也可以用Paxos来实现。一旦Leader确认后续所有提案都可以跳过Prepare阶段只用一轮RTT就能完成Accept确认。流程变为Leader启动时执行一次Prepare获得一个最大的编号m之后所有提案直接使用m 1、m 2……这样的连续编号发起Accept如果Leader宕机或失去多数派支持其他节点通过新一轮Prepare触发重选。这个模式后来被Raft继承并发扬光大。你去看Raft的论文里面Leader选主、日志复制的框架本质上是Multi-Paxos的精简实现只是把“编号”换成了“Term Index”把“Prepare”换成了“RequestVote”。7.3 从Paxos到Raft工程取舍的启示Raft比Paxos好懂很大程度上是因为Paxos的论文把“值”抽象得太彻底导致读者很难把它和“日志复制”关联起来。而Raft直接把“值”定义为“日志条目”把提案编号定义为逻辑时钟Term把Accept阶段定义成“日志追加”一切顺理成章。但如果你真正理解了Paxos再回来看Raft你会发现Raft做减法的地方正是Paxos里最复杂、最难实现的部分Raft限制了“只有Leader能发起提案”消除了多Proposer并发竞争Raft用日志连续性简化了“历史值”的传播Raft用“多数派匹配日志”替代了Paxos中更通用的值约束。这些东西不是Raft凭空发明的而是针对Paxos工程痛点做的定向简化。8. 常见误区与排查技巧8.1 误区一多人同时提案会把数据弄乱Paxos不会让多个提案在同一编号下并行提交因为Acceptor会在同一编号上只接受一个值对于不同编号的提案继承规则会迫使后续提案跟随先前的值。所以多Proposer并发不会造成系统分叉只会引入性能损耗和活锁风险。误区表现有人担心P1提交x1、P2提交x2最终集群会出现“一会是1一会是2”的不一致。如果配置正确Paxos不会这样。最终被选定的值只有一个后面所有Learner都会看到同一个值。8.2 误区二必须所有节点都确认才算成功从理论角度过半节点确认即可视为成功但从应用层角度看Leader需要知道“哪些节点成功了”才能向客户端返回。如果宕机节点太多虽然一致性安全保住但可用性下降系统可能无法对外服务。实际部署中三节点集群挂掉一个系统可继续工作挂掉两个就不行了因为无法形成多数派。这个边界条件必须提前在运维监控中对齐清楚。8.3 排错手记从真实Bug中学到的三件事排错场景一Acceptor重启后丢“已接受提案值”会导致新提案者无法通过Prepare获取历史值可能重新选择不同值。排查时需要检查节点是否持久化了“已接受提案值”和“已响应编号”两个字段不能只存一个。排错场景二两个Proposer并发提交导致相位抖动。最常见的是死循环式Prepare重试。解决方式是引入随机退避窗口并合理设置Leader lease租约确保同一时间只有一个活跃Proposer。排错场景三网络分区下两个节点组各自以为自己是多数派。Paxos能保证安全性不会出现两个不同的已接受值但不能保证可用性小的分区组无法形成法定人数因此不会确认任何新值。如果业务需要“分区后少数派仍可读”你就必须用额外的机制去解决Paxos本身不能做到。8.4 工程实现速查表持久化至少两个字段已接受的最高提案编号、已接受的最新的提案值和编号收到编号小于本地已响应编号的Prepare或Accept直接拒绝向Acceptor发Prepare时要带上自己的提案编号而不是直接发“我要提交这个值”若Prepare响应中含有历史值务必继承编号最大的那个值不要自作聪明收到拒绝响应时升级自己的编号重试但要注意设置随机退避或切换到Leader模式测试时不能只测正常流程要故意杀节点、断网络、延迟消息才能暴露真实问题。9. 延伸思考Paxos之外的世界Paxos作为共识算法家族的老大哥近年来的讨论热度被Raft超过。但如果你做实际架构选型两者没有绝对优劣Chubby、ZooKeeper采用了类Paxos方案侧重高可用和成熟生态Raft以可理解性取胜etcd、consul、TiKV大量采用Debug成本更低对极致一致性有要求的场景比如分布式事务、跨数据中心同步仍需以Paxos系算法为基础来定制。我个人在实际项目中最深的体会是共识算法不能当黑盒使用。很多团队直接引入etcd以为天然就“一致”了却在网络分区测试时发现业务侧读到了旧数据——原因是应用层没有用线性一致读接口。Paxos给你的只是一个“值选定”的保证但你的应用是否读取选定后的值、是否在正确时机发起请求决定了最终一致性体验。Paxos保证的是“每个值选定后不会再变”但“什么时候能读到被选定后的值”取决于你程序里选择的时钟和读取路径。最后再分享一个实操小技巧在测试环境里模拟Paxos行为时我会把每个节点的“已接受编号”打到日志里而不是只打印“是否成功”。在排查不一致问题时光看当前值会让人头晕只有打印编号变化序列你才能画出每个节点的时间线迅速定位到是Prepare阶段还是Accept阶段的疏漏。这个方法在很多分布式调试中都管用比看监控图直观得多。