问题

三台服务器要对"当前值是什么"达成一致。任何一台随时可能宕机，网络消息可能延迟或丢失。怎样设计一套协议，使得所有正常运行的节点最终看到同一个结果？

这就是分布式共识问题。Paxos、ZAB、Raft 用不同的方式回答了这个问题，但背后的数学内核只有一个——鸽巢原理推出的多数派交叉。

唯一需要的数学工具

鸽巢原理

鸽巢原理（抽屉原理）是高中数学竞赛的常客：n+1 只鸽子飞进 n 个巢，至少有一个巢里有两只鸽子。

多数派一定交叉

设集群有 N = 2f + 1 个节点，f 是允许同时宕机的节点数。多数派（quorum）的大小是 f + 1。

任取两个多数派 Q₁ 和 Q₂：

1
|Q₁| + |Q₂| = (f+1) + (f+1) = 2f+2 > 2f+1 = N

元素总数超过了全集大小，鸽巢原理给出结论：Q₁ ∩ Q₂ ≠ ∅，至少有一个节点同时属于两个多数派。

这条性质是 Paxos、ZAB、Raft 共同的地基。后面的推导都建立在它之上。

从零推导 Paxos

单提案者：没有任何困难

集群里只有一个提案者（proposer），问题极其简单：

  1. 提案者把值 v 发给所有接受者（acceptor）。
  2. 超过半数接受者回复"已接受"，v 就被选定（chosen）了。

一步搞定。

多提案者：矛盾出现

提案者也会宕机，所以必须允许多个提案者。假设提案者 A 想提 v₁，提案者 B 想提 v₂，两者各自发给不同的半数节点——系统可能产生分歧，或者两边都拿不到多数派。

需要一种机制，让后来的提案者发现之前是否已经有值被（可能）选定。如果有，顺从那个值，而不是硬推自己的。

两阶段协议

Paxos 的解法是把一轮共识拆成两步。

阶段一 Prepare：提案者选一个全局递增的编号 n，向多数派发送 Prepare(n)。接受者收到后，如果 n 比自己见过的所有编号都大，就作出承诺——以后不再接受编号小于 n 的提案，同时把自己已接受的最高编号提案（如果有）告诉提案者。

阶段二 Accept：提案者收齐多数派的回复后：

  • 如果有接受者报告了已接受的值，提案者必须采用其中编号最大的那个值。
  • 如果没人报告过已接受的值，提案者可以用自己想提的值。
  • 然后发送 Accept(n, v) 给多数派。

为什么这套规则是对的

用反证法。假设值 v 已经被编号 n 的提案选定（被多数派 Q₁ 接受），现在一个编号 n’ > n 的提案想选定不同的值 v’ ≠ v。

提案 n’ 在 Prepare 阶段需要收到某个多数派 Q₂ 的回复。根据前面证明的性质，Q₁ ∩ Q₂ ≠ ∅，至少有一个节点 x 同时属于两个多数派。x 已经接受了 (n, v)，会把这个信息报告给提案者。提案者收到后，按规则必须采用 v（或编号更高的已接受值，用归纳法可以证明那也是 v）。于是 v’ = v，与假设矛盾。

整个正确性证明的关键：多数派交叉保证了信息传递——旧的决定不会被新的提案者遗漏。

消息轮次

没有冲突的情况下，Prepare 请求+响应一轮，Accept 请求+响应一轮，共 2 轮消息交换（4 次网络传输）。

ZAB：给 Paxos 加上顺序

原始 Paxos 解决的是"对一个值达成共识"。实际系统需要对一连串操作依次达成共识。ZAB（Zookeeper Atomic Broadcast）是 Paxos 思路在 Zookeeper 场景下的工程化延伸，做了三处关键调整。

调整一：固定领导者

Paxos 允许任何节点发起提案。ZAB 把提案权收归一个领导者（leader/primary）。好处直接——没有两个提案者互相打断的问题，正常运行期间 Prepare 阶段可以省掉。

调整二：纪元 + 计数器

ZAB 用 (epoch, counter) 二元组给每条提案编号。同一个领导者在同一个纪元内，counter 递增即可；领导者换届时 epoch 加 1，counter 重置。这比 Paxos 的全局编号更容易管理。

调整三：显式的恢复流程

领导者宕机后，ZAB 有三个阶段完成换届：

发现（Discovery）：新领导者候选人收集各 follower 的历史，找到数据最完整的那份。

同步（Synchronization）：把所有 follower 的状态拉齐到同一进度。

广播（Broadcast）：恢复正常运转——领导者提议，follower 确认，多数派确认后提交。

Paxos 的论文没有详细规定这些步骤，工程团队需要自己补全。ZAB 直接写进了协议规范。

正确性仍然来自多数派交叉

广播阶段的提交需要多数派确认。换届时新领导者也需要多数派投票。两个多数派必然交叉，新领导者一定能看到旧领导者已经提交的操作。

Raft：为可理解性重新设计

Diego Ongaro 在博士论文里直言：Paxos 太难理解了。Raft 的首要设计目标就是让工程师能看懂。

强领导者

Raft 的规则很硬：日志条目只能从领导者流向跟随者（follower），不能反向。这条规则大幅减少了需要考虑的状态组合。

领导者选举

每个节点设一个随机选举超时（例如 150~300ms）。超时没收到领导者心跳的节点变成候选人（candidate），递增任期号（term），向其他节点拉票。

投票规则：如果候选人的日志至少和自己的一样新，就投票给它。"至少一样新"的判定标准是——最后一条日志的任期更大，或任期相同但日志更长。

拿到多数票就当选。随机超时避免了多个节点同时竞选造成的活锁。

日志复制

  1. 客户端请求发给领导者。
  2. 领导者把新条目追加到本地日志，然后发 AppendEntries RPC 给所有跟随者。
  3. 多数派确认后，领导者提交该条目并回复客户端。

正确性

Raft 的关键性质叫领导者完整性（Leader Completeness）：如果某条日志在任期 T 被提交，那么任期大于 T 的所有领导者的日志中都包含这条记录。

证明思路和 Paxos 相同——反证法加多数派交叉。如果新领导者缺少某条已提交的日志，它不可能在选举中拿到多数票，因为多数派中至少有一个节点持有那条日志，而投票规则要求候选人的日志不能比投票者旧。

三者的差异

维度 Paxos ZAB Raft
领导者 不要求，任何节点可提案 要求 要求
一次共识的对象 单个值 一连串操作 一连串日志条目
顺序保证 无内建顺序 同一领导者内 FIFO 全局日志顺序
编号方式 全局递增提案号 (epoch, counter) (term, index)
换届恢复 论文未详细规定 显式发现 + 同步阶段 日志比较 + 覆盖落后节点
成员变更 基础协议未涉及 独立协议 联合共识或单节点变更
可理解性 公认困难 中等 以可理解为首要设计目标

三套算法的安全性（safety）保证等价——都建立在多数派交叉上。差别在活性（liveness）策略和工程可操作性。

实战中的缺陷

Paxos

规范与实现之间的鸿沟。 Lamport 的论文描述的是单值共识。要走到实际可用的 Multi-Paxos（连续对多个值达成共识），需要补全领导者选举、日志压缩、成员变更等大量细节，论文里全都没有。Google Chubby 团队在《Paxos Made Live》中写过一句话：从 Paxos 论文到真实系统的距离，远比想象中大。

活锁。 两个提案者轮流用更大的编号打断对方的 Prepare 阶段，谁也完不成 Accept。可以用随机退避或领导者租约缓解，但基础协议本身不保证活性。

ZAB

和 Zookeeper 强耦合。 ZAB 的规范和实现紧密绑定在 Zookeeper 的场景上（层级 key-value 存储、watch 机制），很难单独拿出来给其他系统复用。

换届开销。 发现 + 同步两个阶段在数据量大时耗时显著。Zookeeper 的设计假设数据量较小（单 znode 限制 1MB），总数据量一旦增长，恢复时间会拉长。

单点写入瓶颈。 所有写请求必须经过领导者，写吞吐上限就是单机的处理能力。

Raft

同样的单点写入瓶颈。 和 ZAB 一样，写入必须经过领导者。

日志膨胀与快照。 Raft 的日志是只追加的，不能无限增长，需要周期性做快照并截断旧日志。快照的实现引入了额外复杂度，原始论文对这部分的描述也比较简略。

Pre-Vote 问题。 一个被网络分区隔离的节点会不断递增任期号发起选举。分区恢复后，这个节点的高任期号会干扰正常集群，迫使当前领导者下台。后来引入了 Pre-Vote 机制来缓解，但这不在原始论文中。

成员变更的工程难度。 论文提出了联合共识（Joint Consensus）来安全地变更集群成员。Ongaro 后来自己也承认这个机制实现起来很复杂，并提出了更简单的单节点变更方案。但单节点变更在某些边界条件下也有正确性陷阱。

选型建议

不必纠结"哪个更正确"——三者的安全性等价。看生态即可：etcd 和大多数云原生系统选 Raft，Zookeeper 用 ZAB，纯 Paxos 实现在工业界已经很少直接出现。

参考资料

  • Lamport, L. “The Part-Time Parliament.” ACM Transactions on Computer Systems, 1998.
  • Lamport, L. “Paxos Made Simple.” 2001.
  • Chandra, T., Griesemer, R., and Redstone, J. “Paxos Made Live: An Engineering Perspective.” PODC, 2007.
  • Junqueira, F., Reed, B., and Serafini, M. “Zab: High-performance broadcast for primary-backup systems.” DSN, 2011.
  • Ongaro, D. and Ousterhout, J. “In Search of an Understandable Consensus Algorithm.” USENIX ATC, 2014.
  • Ongaro, D. “Consensus: Bridging Theory and Practice.” PhD thesis, Stanford University, 2014.