4.2 Paxos 简述与 Raft 的动机
上一节用 FLP 证明了「完全异步网络里共识不可能保证终止」,也指出现实出路的形状:引入超时、弱化完全异步、接受概率性活性。那么具体怎么做共识?这一节补上历史线:Paxos 是第一个被严格证明的答案,Raft 是它之后面向工程的重构。K8s 控制面把全部集群状态押在 etcd 的共识上,而 etcd 选的是 Raft——要理解这个选择,先得看清 Paxos 的边界在哪。
本节的路数不是罗列两个算法,而是做一次「工程决策复盘」:先理解 Paxos 承诺了什么、又留白了什么,再对照 Raft 把每个留白怎么补上的。这样读到最后,「etcd 为什么用 Raft 不用 Paxos」就不是一个记忆点,而是一个可以自己推出来的结论。
共识问题的第一个严格答案
Paxos 解决的问题可以一句话说清:一群进程各自提出一个值,系统必须让它们最终选出一个相同的值,并且这个值一旦被确定,永远不许再变。这是复制状态机(replicated state machine)的底层原语——只要所有副本对每一条命令都达成一致的顺序,状态机自然一致。
Paxos 的历史绕不开一段轶事:Leslie Lamport 在 1989 年写成论文,用一个虚构的希腊小岛议会作比喻,结果审稿人看不懂「The Part-Time Parliament」,论文被拒;直到 1998 年才在 ACM TOCS 上发表,1999 年他补了一篇「Paxos Made Simple」把比喻剥掉。这本身就暗示了 Paxos 的处境:证明它容易,理解它难。
对 K8s 读者,Paxos 不是遥不可及的学术名词。etcd 没有用 Paxos,但 etcd 依赖的很多概念——多数派、编号、承诺、法定确认——都是从 Paxos 继承下来的家族基因。先看懂 Paxos,再看 Raft 就只剩「它改了什么、为什么改」。
要把它和 4.1 的 FLP 接起来看:FLP 说「完全异步下共识无法保证终止」,Paxos 的回应是「我承认无法保证终止,但我保证一旦终止结果就一致」。这就是分布式系统里最常用的一次分工:用协议保证安全性(safety),用现实假设(超时、重试、随机化)换取活性(liveness)。Paxos 把安全性的证明做得很扎实,把活性的兜底丢给了实现者。
Basic Paxos 的三类角色
Basic Paxos 把进程按职责分成三类角色。同一台机器可以身兼多职,但职责必须分开说清楚:
| 角色 | 英文名 | 职责 | 类比 |
|---|---|---|---|
| 提议者 | proposer | 提出提案(编号 + 值),推动两阶段流程 | 想写入的客户端进程 |
| 接受者 | acceptor | 持久化存储,对提案做承诺和接受 | 存储副本,如 etcd 的单个节点 |
| 学习者 | learner | 得知哪个值被确定,供状态机消费 | 需要读取「已提交结果」的下游 |
- proposer 是发起方:它给提案分配一个全局唯一的编号
n,编号只在同一 acceptor 内比较大小,不要求跨进程单调连续,只要「任意两个提案编号不相等且可比大小」。实践中常用「轮次号 + 进程 ID」拼成编号,比如轮次 * 节点数 + 节点ID。 - acceptor 是裁决方:它只做两件事——对编号
n做出承诺,以及在某编号上接受一个值。acceptor 没有「谁对谁错」的立场,它只按编号纪律办事。acceptor 要持久化的状态只有两个:承诺过的最高编号、已接受的(编号最高)提案。 - learner 是观察方:它自己不发消息,只从 acceptor 那里收集「已经有多少节点接受了提案」,一旦收集到多数,就宣布该值已确定。
把角色分开的价值在于:错误容忍只依赖 acceptor。proposer 崩溃随时可由另一个 proposer 顶替,learner 崩溃不影响正确性,但任何两个 acceptor 的持久状态必须可恢复。所以 etcd 里最重的持久化逻辑都在「存储副本」上,写请求必须刷盘后才算接受——这个「持久化后才算数」的纪律就是 acceptor 角色在 etcd 里的直接化身。
多数派的最小数字这里要先定下来:设集群 N 个 acceptor,多数 quorum q = N/2 + 1(整除向下取整)。3 节点时 q = 2,5 节点时 q = 3。这个 q 是所有后续正确性论证的地基。
两阶段协议:prepare/promise 与 accept/accepted
Basic Paxos 对单个值的确认要跑完整两阶段。用 5 个 acceptor(A1–A5,N=5,q=3)的数字场景走一遍。
阶段一:prepare → promise。
proposer P 选一个编号 n = 3,向所有 acceptor 广播 prepare(3)。每个 acceptor 本地记住自己「承诺过的最高编号」promised:
- 若
3 >= promised:acceptor 更新promised = 3,回复promise(3, v_old)。v_old是该 acceptor 已接受过的、编号最高的值;如果从未接受过任何值,v_old为空。 - 若
3 < promised:acceptor 拒绝,不更新承诺。
假设 A1 曾接受过 (n=2, v="key=foo"),A2、A3 从未接受值。三者的 promise 回复分别是:A1 → (3, v="key=foo")、A2 → (3, 空)、A3 → (3, 空)。注意「承诺」的含义:acceptor 一旦 promise 编号 3,就放弃了「以后接受编号小于 3 的提案」的权利——这是后面正确性论证的锚点。
阶段二:accept → accepted。
proposer 收集 promise。规则是:如果任一 promise 带回了旧值,新提案必须沿用编号最高的那个旧值,而不是 proposer 自己的新值;只有当所有 promise 都为空时,proposer 才能自由选自己的值。
A1带回v="key=foo",编号 2 是已知最高的。于是P不再提交自己原本想写的v="key=bar",而是广播accept(3, "key=foo")。- acceptor 收到 accept:只要
3 >= promised就接受并持久化,然后回复accepted(3, "key=foo")(通知 learner)。 P收到 3 个accepted即宣布v="key=foo"已确定。
这一轮的取舍很关键:proposer 为了多数承诺,可能被迫放弃自己刚提出的值、改提一个「历史值」。如果 P 不遵守「沿用旧值」的规则、强行写自己的 key=bar,那么 A1 同时接受了 key=foo(编号 2)和 key=bar(编号 3),A2、A3 接受了 key=bar——此时「多数接受的值」就不唯一,learner 会看到两个值,共识破裂。所以这条规则不是风格选择,是安全性的咽喉。
把整个过程的消息序列整理成表,方便后面跟 Raft 对比:
| 步骤 | 消息 | 发送方 → 接收方 | 携带内容 | 接收方动作 |
|---|---|---|---|---|
| 1 | prepare | proposer → acceptor(广播) | 编号 n | 检查 n 与 promised |
| 2 | promise | acceptor → proposer | 编号 n、已接受旧值 v_old | 更新 promised=n,返回承诺 |
| 3 | accept | proposer → acceptor(广播) | 编号 n、值 v | 检查 n 与 promised,持久化 |
| 4 | accepted | acceptor → learner | 编号 n、值 v | 累计确认,多数则宣布确定 |
为什么 Paxos 正确:两个 quorum 交集非空
Paxos 的正确性论证浓缩成一句话:任意两个多数 quorum 的交集非空。这句话靠 acceptor 的承诺纪律变成一条不变量:「编号为 n 的提案一旦在多数 acceptor 上被接受,任何编号大于 n 的提案也只能带同一个值 v」。
推理过程用反证。设一个值 v 已经在一轮 (n, v) 中被多数 acceptor 接受(acceptor 集合 Q1,|Q1| = 3)。后来某个 proposer P' 用更大的编号 n' > n 重新走流程,它的 prepare 需要另一组多数 acceptor 的 promise(集合 Q2,|Q2| = 3)。由于 5 个节点中 Q1 和 Q2 各占 3 个,交集 Q1 ∩ Q2 至少包含 3 + 3 - 5 = 1 个节点:
- 这个共同节点 promise 时,要么 promise 发生在
(n, v)被接受之后——它会把已接受的(n, v)带给P',于是P'被迫沿用v; - 要么 promise 发生在
(n, v)被接受之前——但Q1接受(n, v)时必然包含这个节点(它在交集中),一个 acceptor 不可能「先 promise 了更大的编号 n’,又接受编号 n < n’ 的提案」——那会违反它自己的承诺纪律。矛盾,所以第一种情况必然成立。
把两个 quorum 换成任意大小都成立:q + q - N >= 1 当且仅当 q > N/2。用表格把几个常见规模算一遍,验证「多数派交集非空」是普适的:
| 集群节点数 N | quorum q | 两个 quorum 的最小交集 | 可容忍故障数 f |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 3 | 2 | 1 | 1 |
| 5 | 3 | 1 | 2 |
| 7 | 4 | 1 | 3 |
| 9 | 5 | 1 | 4 |
所以多数派不是「选一个方便的数字」,而是保证任何两次成功决策必须读到同一份见证的最小票数。一旦一个值被 learner 观察到「多数接受」,后来的提案无论编号多大都只能携带同一个值——learned 值确定后不可变,正确性就此闭环。
注意这个论证只依赖 acceptor 的本地承诺,不依赖任何全局时钟、消息有序或网络可靠。FLP 说共识在完全异步下不能保证终止,但 Paxos 证明的是如果终止则结果一致——安全性不依赖时间假设,这是 Paxos 最漂亮的地方,也是它做教学模板的原因。
为什么 Paxos 难实现、难用
Paxos 的正确性没有问题,问题出在「证明之外」的部分。业界对它的批评不是算法错,而是把工程问题留白了。逐条拆开看,每一条都能在 K8s/etcd 的运维现场找到对应:
1. 没有显式 leader,活锁难以避免。
任何 proposer 都可以随时发起流程。两个 proposer 交替抬编号:P1 prepare(3) → 多数 promise;P2 prepare(4) → 多数 promise,P1 的 accept(3) 被拒;P1 改 prepare(5),P2 的 accept(4) 被拒……每一轮都无疾而终,系统能一直「转圈」而不提交任何值。用 3 节点集群推演:
| 轮次 | P1 动作 | P2 动作 | 结果 |
|---|---|---|---|
| 1 | prepare(3) | — | P1 拿到多数 promise |
| 2 | — | prepare(4) | P2 拿到多数 promise,P1 的 accept 将被拒 |
| 3 | accept(3) | — | 多数 acceptor 因 promised=4 拒绝 |
| 4 | prepare(5) | — | P1 再次抬编号 |
| 5 | — | accept(4) | 多数 acceptor 因 promised=5 拒绝 |
Paxos 论文只保证正确性,不保证这种情况不会发生;生产中往往要额外钦定一个 distinguished proposer(通常就是 leader),但这已经是协议外的补丁——补丁做得不好,又会引入新的正确性风险。
2. 日志如何拼接没有答案。
Basic Paxos 解决的是「一个值」。复制状态机需要的是「一串命令按序执行」,于是要把 Paxos 实例化到日志的每个下标上:Paxos(下标0)、Paxos(下标1)、Paxos(下标2)……谁来分配下标?某个实例卡住了后面的实例等不等它?崩溃后日志从哪续?multi-Paxos 论文里「把实例串成日志」的接线逻辑几乎没有展开,实现者各自发明,结果互不兼容。etcd 的日志复制则是 Raft 的显式答案:leader 按 term+index 给日志条目编号,follower 严格按序追加。
3. 重配置复杂。
成员变化(加节点、减节点、换副本)在 Paxos 里没有显式协议。增删一个 acceptor 会直接改变 quorum 集合,交集论证需要重推;两个并发配置变更叠加时,正确性极易被破坏——比如从 3 节点扩到 5 节点,如果旧 quorum=2、新 quorum=3 同时生效,可能选出两个互不知晓的多数。etcd 扩缩容是生产运维的常规操作,Raft 为此有显式的配置变更协议(联合共识),Paxos 在这里几乎是裸奔。
4. 故障恢复晦涩。
acceptor 需要记住「承诺过的最高编号」和「已接受的值」,而且有个著名的坑:一个 acceptor 如果「遗忘」了自己接受过的旧值,可能让新 proposer 以为没有历史值、从而用新值覆盖——这是不可接受的。崩溃恢复的规则散落在各种 corner case 里:什么时候刷盘、重启后先恢复什么、promise 编号恢复到哪个值,实现错一个就可能在重启后把已确定的值改掉。Raft 把需要持久化的状态收敛成少数几个变量(currentTerm、votedFor、log[]),并明确规定重启恢复路径。
Paxos 的工程化后代:Multi-Paxos 与 Chubby
不是说 Paxos 没有工程实现。Google 的 Chubby(2006 年论文)就是基于 Multi-Paxos 的分布式锁服务,后来的 Megastore、Spanner 也用了 Paxos 家族算法。Multi-Paxos 的思路正是「钦定 leader + 稳定期省掉 prepare 轮」:leader 用一次 prepare 建立一轮「豁免权」,之后所有实例都直接 accept,于是稳定期每条命令从 2 轮降到 1 轮。
但 Multi-Paxos 没有一个「标准实现」。不同系统的 leader 选择、日志拼接、成员变更各不相同,正确性论证也散落在各自的技术报告里。这正是 Raft 出现的背景:把 Multi-Paxos 的各个隐式假设全部显式化。Raft 论文开头就说「Paxos 的简洁来自抽象,但抽象掩盖了工程上必须做出的选择」——Raft 的选择是:与其隐藏复杂性,不如把它摆到台面上逐一设计。
Raft 的设计动机:把缺位逐个补上
Raft 的论文标题就是它的宣言:In Search of an Understandable Consensus Algorithm——「可理解的共识算法」。Raft 不是发明了新的共识思想,而是把 Paxos 的每个留白都显式补上,并把正确性论证拆成可独立验证的子问题。对照看最直观:
| 维度 | Basic Paxos | Raft |
|---|---|---|
| 领导者 | 无显式,任意 proposer 可竞争 | 显式 leader,一次只允许一个 |
| 写路径 | 任意 proposer 直接提值 | leader 独占写,只有 leader 能追加日志 |
| 日志 | 单值独立实例,拼接留给实现者 | 严格有序、连续编号的日志条目 |
| 选主 | 无(靠 distinguished proposer 补丁) | 完整选举协议:RequestVote + 任期 + 随机超时 |
| 成员变更 | 无显式协议 | 显式配置变更协议(联合共识) |
| 快照 | 无 | 显式快照与日志压缩协议 |
| 提交判定 | 多数 acceptor 接受 | 多数节点确认 AppendEntries,leader 更新 commitIndex |
| 可理解性 | 简洁但抽象 | 以「每个机制都能独立解释」为第一目标 |
Raft 的方法论是把共识大问题拆成五个可独立讨论的子问题:领导者选举、日志复制、安全性、成员变更、日志压缩与快照。每个子问题都有自己的协议和证明,代码结构也随之分块——etcd 的 raft 包、Consul、TiKV 的实现都可以按这个目录读。这正是 4.1 结尾说的「把活性放回协议内」:Paxos 把活性踢给外部补丁,Raft 把活性做成显式选举协议的一部分。
对「强领导者」要特别注意:Raft 假设 leader 是唯一写者,这个假设简化了几乎所有交互。follower 收到写请求一律转给 leader;leader 挂了集群先选新 leader;选出来的 leader 保证日志最新。代价是 leader 成为性能焦点——etcd 的所有写入都经它串行化,所以它必须刷盘快、心跳稳,这也是下一节和 5.1 节反复出现的主题。
消息往返对比:1 轮 vs 2 轮
把「提一条命令」的路径画出来,Raft 与 Basic Paxos 的差距很直观。假设集群已有健康 leader,client 要把 PUT /registry/deployments/app 3 写进状态机:
- Raft(1 轮):client → leader(客户端请求);leader 把命令追加进日志并广播
AppendEntries(携带新条目)给所有 follower;多数节点回AppendEntriesResponse;leader 更新 commitIndex 后回包 client。一次请求-确认的往返里,多数确认已经拿到。 - Basic Paxos(2 轮):proposer 先
prepare(n)等多数 promise,再accept(n, v)等多数 accepted——至少两次网络往返,且每次都要等多数,两轮串行不可合并。
用 3 节点 etcd 的场景算一笔账:写入 100 条命令,Raft 在稳定期是 100 轮请求-确认;Basic Paxos 即便忽略活锁,也要 200 轮起。Paxos 有一个优化是「固定 leader 后省略 prepare 轮」(即 Multi-Paxos),但前提是你得先有 leader——这正是 Raft 显式选主解决的问题。换句话说:Raft 用「先花一轮选主」的固定成本,换来了稳定期每条命令省一轮。
时间上再量化一层:假设单跳网络延迟 1 ms、多数确认需要 2 跳,Raft 一条命令约 3 ms(client→leader 1 ms,leader→多数 1 ms 与多数→leader 1 ms 并不同源,取近似 2 ms,再加回包 1 ms),Paxos 至少翻倍到 6 ms 量级。延迟差在 etcd 这种每次 API 写都要过一次共识的路径上会直接放大成客户端可感知的延迟差异。
这解释了 lab 里 TestRaftCommitRounds 为什么断言 raftRoundsToCommit() < paxosRoundsToCommit():仿真把这两个数硬编码为 1 和 2,检查的正是「Raft 提交更快」这一设计目标的直观表现。数字本身简单,背后是协议结构上的本质差。
K8s 的 etcd 为什么用 Raft 而非 Paxos
最终落回 K8s 的选择。etcd(CoreOS 2013 年启动)从一开始就选 Raft,理由可以概括为工程可读性:
- 可理解才能可运维。etcd 的故障排查要能回答「为什么这个节点拒绝投票」「为什么这条日志没提交」。Raft 的每个机制都有名字和明确协议,状态转移能画成状态机;Paxos 的「承诺与接受」需要推演不变量才能解释现场。
- 可读才能可信。etcd 的
raft包按 Raft 论文的章节组织:raft.go做状态机、log.go做日志、quorum子包算多数派。K8s 团队要做共识算法的审计和修改,代码和论文能逐段对照。 - 生态效应。Consul、etcd、TiKV,以及 K8s 的控制面,都跑 Raft;围绕 Raft 的测试工具、故障注入、论文解析多得足以形成社区知识。Paxos 的实现各自为政,出了 bug 很难借鉴别人。
- 与 K8s 的契合。K8s 需要的不是「最优雅的共识」,而是「在 3–5 节点、网络偶尔抖动、必须让运维看得懂」场景下最稳的共识。Raft 的显式选主、严格日志顺序、显式成员变更,恰好覆盖 etcd 扩缩容和 leader 切换这些 K8s 运维天天要面对的场景。
还有一个容易被忽视的现实因素:调试与教学。Raft 的状态机可以画成一张三角色迁移图,任何人看 20 分钟就能描述一个故障现场;Paxos 的正确性依赖「promise/accept」两层纪律,多数运维和研发无法在故障现场快速定位是哪层纪律被违反。对一个要长期维护、允许新人接手的系统,这种「可解释性红利」是实打实的成本节约。
一句话总结本节立场:Paxos 证明了「共识可以做到」,Raft 证明了「共识可以做到让人读懂」。etcd 要的不是证明,而是能修的代码。
本节 lab
本节的 lab 是 raft 包里的 TestRaftCommitRounds。它把两种协议提交一条命令所需的网络往返分别实现为 raftRoundsToCommit() 和 paxosRoundsToCommit(),返回 1 和 2,然后断言 Raft 的往返数必须严格小于 Paxos。跑它验证的正是本节「消息往返对比」小节里的数字:
cd private/labs/k8s-etcd-lab
go test ./raft -run TestRaftCommitRounds -v
读到测试源码 private/labs/k8s-etcd-lab/raft/raft_test.go 时注意:TestRaftCommitRounds 的注释里写着「Raft 在已有 leader 时提交一个命令只需一轮 AppendEntries → Response」,这句话的成立前提是 leader 已经存在——而 leader 怎么来,就是下一节和 5.1 节要解决的问题。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。