12 共识：Paxos、Raft、两阶段提交

开篇提问

先给你一个看起来很简单、实则困扰了计算机科学几十年的场景：

5 台机器组成一个集群，它们要对”现在的时间是下午 3 点”这件事达成一致。每台机器的本地时钟都略有偏差，而且其中可能有 1 台机器随时会宕机、网络消息可能延迟、可能乱序、可能丢失。

请问：这 5 台机器，怎么才能”一致地”做出一个决定，而且这个决定不会因为某台机器挂掉就出错？

这不是学术问题。这就是：

分布式数据库决定”这条记录的值是多少”
分布式锁决定”谁拿到了锁”
集群决定”谁是主节点”

共识（Consensus）是分布式系统的心脏。 而它之所以出名，是因为它难——难到 Lamport 为此写了两篇论文、拿了图灵奖，难到后来又有人专门写了个”更好懂”的 Raft 论文。

我想让你先想一个问题：为什么”达成一致”这么难？5 台机器，让它们投个票不就行了吗？

子主题一：为什么”投票”不够——共识的真正难点

你说”投票不就行了”，那我们试试最简单的投票方案：

方案： 每台机器提出自己的值，大家互相告知，最后”少数服从多数”。

问题立刻出现了：

问题一：每个人提的值可能不同。 A 说”3 点”，B 说”3 点 01”，C 说”2 点 59”。多数派是哪个？如果有 5 台机器、5 个不同的值，可能根本形成不了多数派。

问题二：消息会丢、会乱序、会重复。 你收到 3 票支持”3 点”，但这 3 票里有没有重复计数的？有没有谁的票在半路丢了导致你没统计到？

问题三（最要命）：机器会宕机，而且会”宕机后恢复”。 一台机器投了票然后挂了，恢复回来之后它记得自己投过票吗？如果它忘了、又投了一次，票数就乱了。

问题四（最阴险）：没有”同时”。 在分布式系统里，你没法说”现在是第 3 轮，大家都该投票了”——因为每台机器的时钟不同步，消息延迟也不同，不存在一个所有人共享的”当前时刻”。

看到核心困难了吗？共识的难点不是”投票”，而是”在没有任何全局时钟、消息不可靠、节点会故障的情况下，让所有人最终认同同一个值，且这个值一旦确定就不能改变”。

用更精确的话说，共识算法必须同时满足：

一致性（Agreement）：所有正确节点最终决定同一个值
有效性（Validity）：决定的值必须是某个节点提出的（不能凭空产生）
终止性（Termination）：所有正确节点最终都会做出决定（不能永远卡住）
完整性（Integrity）：值一旦决定，不能改变

而著名的 FLP 不可能结果（Fischer-Lynch-Paterson, 1985）证明了一个残酷的结论：

在纯异步网络模型下（没有时钟、无法判断节点是崩溃还是慢），即使只有一个节点可能崩溃，也不存在一个”总能终止”的确定性共识算法。

这句话很重要，但经常被误读。它的真正含义是：你不可能做出一个”在任何情况下都保证在有限时间内达成共识”的算法。 但——你可以通过引入”一点点的同步性假设”（比如假设大多数时候网络是好的、时钟大致同步）来绕过它。

这就是所有实用共识算法的做法：它们不保证”总是终止”，但保证”在网络正常的时候会终止”。 Paxos、Raft 都是这样。

子主题二：Paxos —— 第一个被证明正确的共识算法

Lamport 在 1990 年提出 Paxos（1998 年才发表，因为论文写得太晦涩被审稿人拒了很久）。

Paxos 的核心机制，用一句话说：用”两阶段”+“多数派”+“提案编号”来保证安全性。

角色：

Proposer（提案者）：提出值
Acceptor（接受者）：投票决定是否接受
Learner（学习者）：学习最终决定的值

核心流程（单法令 Paxos，简化版）：

阶段一（Prepare / 准备）：

Proposer 选择一个全局唯一、递增的提案编号 n，向所有 Acceptor 发 “Prepare(n)”
Acceptor 收到 Prepare(n)：如果 n 比它见过的所有编号都大，就回复”承诺不再接受编号小于 n 的提案”，并带上它已经接受过的编号最大的提案值（如果有的话）

阶段二（Accept / 接受）： 3. Proposer 收到多数派的承诺后，发出 Accept(n, v)。关键：v 怎么选？如果 Acceptor 们回复里有已接受的提案值，Proposer 必须用”编号最大的那个提案的值”；否则可以用自己的值。 4. Acceptor 收到 Accept(n, v)：如果它没对更大的编号做过承诺，就接受这个提案

为什么这样能work？ 核心在于第 3 步那个”必须用已有提案值”的规则。它保证了：

一旦某个值 v 被多数派接受了，那么之后任何更高编号的提案，提出的值都必然是 v。

为什么？因为任何新的提案都要先问多数派，而多数派和之前那个多数派必然有交集——交集里的 Acceptor 会告诉 Proposer”我之前接受过 v”，于是 Proposer 就必须用 v。这就是 Quorum 交集性质（第 9 章讲过）的又一次关键应用。

Paxos 的问题： 难懂、难实现、而且单法令 Paxos 只能决定一个值（要决定一系列值需要 Multi-Paxos，工程实现极其复杂）。这就是为什么后来有了 Raft。

子主题三：Raft —— 为”可理解性”而设计的共识算法

2014 年，Stanford 的 Ongaro 和 Ousterhout 发表了 Raft，论文标题就写着”In Search of an Understandable Consensus Algorithm”（寻找可理解的共识算法）。

Raft 的核心设计思路：用”强领导者”模型 + 问题分解，让共识变得可以被人理解。

三个关键设计：

设计一：强领导者（Strong Leader）。

任何时刻只有一个 Leader，所有写请求都经过 Leader
Leader 负责把日志复制给 Follower
这大大简化了流程：不用像 Paxos 那样处理多个 Proposer 并发提案的复杂情况

设计二：问题分解成三个子问题。

Leader 选举：Leader 挂了怎么选新的
日志复制：Leader 怎么把数据同步给 Follower
安全性：怎么保证已提交的日志不会丢失

设计三：用”任期（Term）“作为逻辑时钟。

每个任期有一个编号，每个任期最多一个 Leader
任期编号在消息中传递，节点看到更大的任期就更新自己
任期解决了”谁是最新”的判断问题——不需要全局时钟

Raft 的核心机制：

Leader 选举：

节点有 Follower / Candidate / Leader 三种状态
Follower 超时没收到 Leader 心跳 → 变成 Candidate，发起选举
获得多数派选票 → 成为 Leader
选举超时随机化：避免多个节点同时发起选举导致分裂投票

日志复制：

Leader 接收写请求，追加到自己的日志
并行发给所有 Follower
多数派确认后，Leader 提交（commit）并通知 Follower
关键安全性保证：只有拥有所有已提交日志的节点，才能成为 Leader（通过选举时的日志比较实现）

为什么 Raft 比 Paxos 好懂？ 不是因为它更简单（本质复杂度一样），而是因为：

强领导者模型让”并发提案”这个最混乱的部分消失了
三个子问题的分解让你可以分块理解
任期机制提供了清晰的时序概念

Raft 的工程影响： etcd、Consul、TiKV、CockroachDB……几乎所有新一代分布式系统都用 Raft。它证明了”可理解性”本身就是一种工程价值——一个能被正确实现的算法，比一个理论上更优雅但没人敢实现的算法有价值得多。

子主题四：两阶段提交（2PC）—— 共识的一个”不完美”亲戚

讲完共识，必须讲一个经常和它混淆的东西：两阶段提交（2PC）。

2PC 解决的是”分布式事务”问题：一个事务要跨多个节点（比如扣 A 账户、加 B 账户），要么全成功，要么全失败。

流程：

阶段一（Prepare / 投票）：协调者问所有参与者”你能提交吗”，参与者各自执行事务但不提交，回复 Yes/No
阶段二（Commit / 执行）：如果所有参与者都 Yes，协调者发”提交”；否则发”回滚”

听起来很像共识？但 2PC 有个致命缺陷：协调者是单点。

如果协调者在阶段二挂了（在发出提交命令之前），所有参与者都卡住了——它们投了 Yes、锁住了资源，但永远等不到协调者的最终命令。

这就是 2PC 的”阻塞”问题。它不是一个真正的共识算法，因为它无法容忍协调者故障。

解决 2PC 阻塞问题的办法：

3PC（三阶段提交）：加一个预提交阶段，试图解决阻塞问题——但实际上在异步网络下 3PC 依然可能出问题，工程上很少用。
用真正的共识算法来做事务协调：让”提交决定”本身通过 Raft/Paxos 达成共识（协调者也做成多副本）。这是现代分布式数据库（TiDB、Spanner）的做法。

关键区分：2PC 是”原子提交协议”，不是”共识算法”。 前者关心”所有节点要么都做、要么都不做”，后者关心”所有人认同一个值”。它们相关但不同。

子主题五：共识的现实意义与代价

共识能给你什么：

分布式一致性存储（etcd、ZooKeeper）
分布式锁
主从选举（谁当主节点）
分布式事务的原子提交

共识的代价（很重要，很多人的幻想在这里破灭）：

代价一：性能。 每次写都要多数派确认、要落盘、要走网络往返。共识的写延迟通常在毫秒到几十毫秒级。

代价二：可用性受多数派限制。 N 个节点要容忍 f 个故障，需要 N ≥ 2f+1。3 节点容忍 1 个，5 节点容忍 2 个。无法通过增加节点来提高写性能（反而会更慢，因为多数派更大）。

代价三：共识不能解决所有问题。 它只解决”就一个值达成一致”。它不能防止脑裂之外的应用层 bug，不能解决拜占庭故障（节点故意作恶，需要 PBFT 类算法）。

最重要的一个实践建议：

能用”无共识”方案解决，就不要用共识。

很多时候，你不需要共识——你需要的是幂等 + 重试 + 最终一致。共识是最后的手段，因为它昂贵、复杂、有延迟。

一个实用的判断：如果你需要的是”选主”或”存储关键元数据”（量小、要求强一致），用共识；如果你需要的是”高吞吐的数据存储”，用分区 + 复制 + 最终一致，只在关键处用共识。

子主题六：复制状态机（Replicated State Machine）——共识到底在为谁服务

先停下来，问一个很容易被跳过的问题：

我们费了那么大劲，就为了”大家对同一个值达成一致”。可是……一个值有什么用？

我定下”现在时间是下午 3 点”，然后呢？我能拿它干嘛？写数据库？显然不是。

答案是：共识本身不产生价值，共识是用来复制”状态机”的。 理解了这一点，你才算真正理解了”共识有什么用”。

核心思想只有一句话：

如果所有副本从相同的初始状态出发，按照相同的顺序，执行相同的确定性操作序列，那么它们一定会到达相同的最终状态。

这句话朴素得像废话。但它是整个分布式一致性领域的地基。

想想两个人各拿一本一模一样的账本，然后按同样的顺序抄写同样的流水账——第 1 笔转 100、第 2 笔转 50、第 3 笔转 200。抄完之后两本账本会不会不一样？不可能。 除非他们抄的顺序不一样。

所以：

状态机（State Machine）：就是你的数据结构 + 业务逻辑。一个 KV 表、一个锁表、一个路由表、一个账户余额。
日志（Log）：就是那个”操作序列”。每个条目是一条命令。
共识算法：负责让所有副本就这条日志达成一致。

于是，共识的职责从”就一个值达成一致”升级成了”就整个操作序列达成一致”。这一个转换，就是 Paxos/Raft 能撑起整个分布式数据库的全部秘密。

这个模型里有一个致命的前提，工程上极其容易踩坑：

状态机必须是确定性的。

什么叫确定性？同样的初始状态 + 同样的命令序列 → 同样的结果，一次不多一次不少。

这意味着你的状态机里不能出现：

time.Now() / System.currentTimeMillis() —— 每个副本执行的时间点不同，结果不同
rand() —— 除非种子也在日志里
读本地文件、读环境变量、读另一个服务的返回值 —— 这是外部 IO
依赖 map / HashMap 的遍历顺序 —— Go 的 map 遍历顺序是故意随机化的，Java 的 HashMap 顺序由 hash 决定（跨 JVM 版本可能变）
依赖未定义行为的浮点运算、依赖线程调度的并发写入

我见过最经典的事故：有人在状态机里用 time.Now().UnixNano() 生成 ID 并写进状态。主节点执行出 ID=1000，从节点执行出 ID=1003。两个副本从此永久分叉。 而且这种 bug 极其阴险——它在单元测试里 100% 通过，因为单进程里时间是确定的。

正确的做法是什么？ 把不确定性提前到日志里：让 Leader 在追加日志时就写入时间戳 / 随机数，所有副本看到的都是日志里那个已经固定的值。时间戳不再由执行时刻决定，而由”Leader 决定日志条目的那一刻”决定。

一句话记住：所有不确定性，都必须在”进日志之前”被消除。进了日志的东西，必须是死的。

从这个模型能立刻推出三个重要结论：

结论一：你真正需要的不是”值一致”，而是”全序（total order）”。

只要所有节点对”第 1 条是 A、第 2 条是 B、第 3 条是 C”达成一致，那么每个副本的账本就一样。这个”把并发操作排成一条线”的能力，就是**线性一致性（Linearizability）**的物理来源：所有操作看起来就像在某一个副本上，按照真实时间顺序原子执行。

结论二：日志是真相，状态机只是缓存。

状态是日志的前缀回放结果。所以状态机可以随时丢掉重建 —— 这就是快照（Snapshot）与日志压缩的依据。当日志长到几百 GB，你把当前状态打个包存下来（快照），然后把快照之前的日志全删了。Raft 里这就是 InstallSnapshot RPC 干的活。

这条推论的实践价值极大：它意味着”备份”和”恢复”有了统一的抽象。etcd 的 boltdb 快照、ZooKeeper 的 snapshot.* 文件、Kafka 的 __consumer_offsets 日志压缩，本质都是同一件事。

结论三：全序是”过度收费”的，你可能根本不需要它。

注意这句话很重要。全序意味着：即使两个操作毫无关系（比如改用户 A 的昵称、改用户 B 的地址），共识也强制给它们排了先后。 这个排序是白付的代价。

两个互不相关的操作，为什么非要争一个先后？答案是：不需要，如果你愿意放弃线性一致性。这就是 CRDT、因果一致性、最终一致性的出发点。共识的代价，本质上是你为”全序”付的钱。 想少付钱，就要接受更弱的模型（第 9、10 章的矛盾在这里又出现了）。

还有一个直击灵魂的反问：那”共识”和”复制”到底什么关系？

异步主从复制也是”复制”啊，MySQL binlog 复制也是”复制”，它们有共识吗？

没有。 区别就一句话：

普通复制：保证数据最终会流过去。切换主节点时，可能会丢掉还没流过去的数据。
共识：保证顺序也是一致的，并且保证”已提交”的东西在切换后一定还在。

所以判定一个系统有没有真共识，只看一个场景：主节点在”我已经告诉客户端成功了”之后立刻断电，新主上台，这笔数据还在不在？

还在 → 有共识。不在 → 你只有复制，没有共识。（顺便说：MySQL 的 rpl_semi_sync_master_wait_no_slave… 算了，MySQL 半同步在超时后会退化成异步，这就是它没有真共识的铁证。）

另一个容易踩的坑：读。

既然状态机在每个副本上都有，客户端能不能直接读任意一个副本的状态机？不能。 因为那个副本可能已经不是 Leader 了，它的状态机是过期的（stale）。你读到了 5 秒前的值。

这就是 ReadIndex / Lease Read 存在的原因（子主题十二详述）。共识给你的是”写”的全序，“读”的正确性需要额外机制。

子主题七：Raft 深入（一）—— Leader 选举的完整过程

好，现在我们知道共识是在复制日志了。那 Raft 具体怎么干的？先看选举。

先问一个挑衅的问题：为什么要选主？Paxos 不选主不也挺好？

因为并发提案是共识里最混乱的部分。多个 Proposer 同时提案、互相抢占、活锁……Paxos 为此引入了两阶段 + 提案编号 + 承诺机制，复杂度爆炸。

Raft 的做法极其粗暴：别并发了。选一个人说了算，其他人都听他的。

类比：一群人开会，如果所有人都可以随时打断别人发言，最后一定是 chaos。所以先选一个主持人，只有他能往白板上写，其他人只能抄。 这就是 Raft 的”强领导者”模型。

粗暴，但有效。所有的并发冲突，被”只允许一个写入者”这个约束一举消灭。 剩下的问题变成了：这个主持人挂了怎么办？

任期（Term）：没有时钟的情况下，怎么定义”谁最新”？

分布式系统里没有全局时钟（第 11 章），那怎么判断一条消息是”新的”还是”陈旧的”？

Raft 的答案：任期（Term）——一个单调递增的整数，充当逻辑时钟。

规则：

每个任期最多一个 Leader（可能 0 个，比如选举失败）
任期编号在所有 RPC 里传递
任何节点看到比自己大的任期号，立刻更新自己的任期并退化为 Follower
节点持久化保存：currentTerm（当前任期）、votedFor（本任期投给了谁）、log[]

第 3 条是整个系统的”秩序维护者”。它意味着：一个过期的 Leader 只要发出去一个 RPC，收到比它大的任期回复，就会立刻自杀退位。 这条规则是 Raft 处理”脑裂后老 Leader 复活”的全部机制。

任期怎么递增？ 只在 Follower 超时发起选举时 +1（Candidate 阶段）。所以任期号暴露了一个信息：这个集群历史上发生过多少次选举。 运维上看到一个 etcd 集群的 term 疯涨，第一反应就是：网络抖了，或者在反复选主。这是个非常实用的诊断信号。

三种状态与状态机

每个节点在任一时刻处于三种状态之一：

       超时/发起选举            获得多数派选票
Follower ──────────────> Candidate ──────────────> Leader
    ^                        |                        |
    |                        | 发现更高任期 / 选举超时 |
    |________________________|________________________|
         发现更高任期（收到合法 Leader 的心跳）

Follower：被动。只响应 RPC。有一个选举超时定时器。
Candidate：主动发起选举。给自己投票，向所有人要票。
Leader：周期性发心跳（空 AppendEntries），维持权威。

选举超时为什么要随机化？

这是一道经典面试题，但 90% 的人只答对一半。

如果所有节点的选举超时都是一样的 200ms，会发生什么？

Leader 挂了 → 所有 Follower 同时在 200ms 后超时 → 全部变成 Candidate → 全部给自己投票 → 没有任何人能拿到多数派 → 分裂投票（split vote）→ 全部超时重试 → 再次同时超时 → 再次分裂 → 系统可能长时间无主。

类比：一群人同时抢着发言，结果谁也听不清，一片嗡嗡声。

Raft 的解法：把选举超时随机化，比如从 [150ms, 300ms] 里随机取一个值。

于是总有一个节点先超时。它先把任期 +1，抢先向所有人要票。此时其他节点的定时器还没到，它们收到 RequestVote 后会重置自己的选举定时器（因为投票本身也是一个”集群还活着”的信号）。于是先动手的那个大概率拿到多数派。

这就是”随机化”的全部意义：把”同时行动”变成”随机错开”，从而让一个人先赢。

补充一个 Raft 论文里的细节：这个随机区间不是随便定的，它必须满足一个不等式：

广播时间（broadcastTime） ≪ 选举超时（electionTimeout） ≪ 平均故障间隔（MTBF）

广播时间 ≪ 选举超时：否则心跳还没送到，Follower 就超时了，永远选不出主。论文给的参考值：广播 0.5~~20ms，选举超时 10~~500ms。
选举超时 ≪ MTBF：否则选举耗时比故障间隔还长，系统大部分时间都在选主。

这句话的实践意义：你把 etcd 部署到跨地域、RTT 200ms 的环境里，还用默认的 1000ms 心跳 / 10000ms 选举超时，就是在玩火。时间参数必须跟着物理网络走。

投票规则：不是”谁先来投谁”

这是最容易被忽略、但最关键的部分。Follower 收到 RequestVote 时，必须同时满足三个条件才投票：

RequestVote 请求携带：term（候选人任期）、candidateId、lastLogIndex、lastLogTerm。

条件一（任期检查）：候选人的 term < 我的 currentTerm？→ 拒绝。（这是”过期候选人”防线）

条件二（一票不多投）：我这个任期已经投过票了，且投的不是他？→ 拒绝。（这保证了每个任期最多一个 Leader，这是 Election Safety 的直接来源）

条件三（日志新旧检查）：候选人的日志至少和我一样新吗？→ 不如我新就拒绝。

“至少一样新”怎么比？ 规则是：

先比 lastLogTerm，任期大的更新；任期相同，再比 lastLogIndex，索引大的更新。

为什么先比任期？因为任期是”合法性”的代际标记。 一个任期 5 的日志条目，一定比任期 4 的任何条目更新——哪怕它的索引更小。这是 Raft 里”信任任期甚于信任索引”的核心哲学：高任期的日志来自更晚的 Leader，而 Leader 只在拥有一个条目之后才会产生更高任期的日志。

条件三就是子主题九要讲的”选举限制”，它是 Raft 安全性的命门。 先记住它存在。

一次选举的三种结局

Candidate 发出 RequestVote 后，可能遇到三种情况：

赢得选举：拿到多数派选票 → 成为 Leader → 立刻向所有人发心跳，宣告权威。注意：新 Leader 上台后第一件事是追加一条空的 no-op 日志条目（子主题八解释为什么）。
别人赢了：收到任期 ≥ 自己任期的 AppendEntries（来自新 Leader）→ 立刻退化为 Follower。
分裂投票：超时了，没人赢 → 任期 +1，重新随机化定时器，发起新一轮选举。

第 3 种情况的处理有个细节：必须重新随机化定时器。如果沿用旧值，可能再次同时超时，陷入循环。

子主题八：Raft 深入（二）—— 日志复制的流程与提交规则

有了 Leader，就有了一个”全序的制造机”。所有客户端写请求都发给 Leader，由它排定顺序。

一次写入的完整路径

客户端 ──写请求──> Leader
                    ① 追加到本地日志（记下 term + index，落盘）
                    ② 并行发 AppendEntries 给所有 Follower
                    ③ 收到多数派确认 → 该条目"已提交(committed)"
                    ④ 应用到状态机
                    ⑤ 返回成功给客户端
                    ⑥ 后续 RPC（含心跳）捎带 leaderCommit → Follower 也应用

第 ① 步的”落盘”是刚性的。 Leader 必须先把日志条目写进持久存储（fsync）才能继续。因为：没落盘就回复 = 断电后这个条目消失 = 你对客户端撒了谎。

同理，currentTerm 和 votedFor 也必须持久化。想象一下：节点 A 给 X 投了票然后断电重启，忘了自己投过票，于是在同一个任期又给 Y 投了一票。结果：同一个任期选出了两个 Leader，日志直接分叉。 这类 bug 极其隐蔽，因为它只在「恰好在投票后、落盘前断电」这个纳秒级窗口触发。

AppendEntries：一致性检查是怎么做的

AppendEntries 请求携带：

term、leaderId
prevLogIndex、prevLogTerm —— 前一条日志的位置和内容
entries[] —— 要追加的条目（心跳时为空）
leaderCommit —— Leader 已提交的位置

Follower 的检查逻辑（这是精髓）：

我自己的日志里，prevLogIndex 那一条的任期，等于 prevLogTerm 吗？

不等于 → 拒绝。说明我的日志和 Leader 的不一致（缺条目、或有冲突条目）。

等于 → 接受。追加 entries[]，并删除后面所有冲突的条目。

为什么检查”前一条”而不是”当前条”？

因为这是一个归纳式的链条。prevLogIndex/prevLogTerm 匹配，说明”到此为止，我的日志和 Leader 完全一致”。于是新追加的条目接在一条已确认一致的尾巴上 —— 归纳法成立。

由此推出 Raft 最重要的性质（论文 Figure 3）：

日志匹配性质（Log Matching Property）：如果不同节点的日志中，有两个条目拥有相同的 index 和 term，那么这两个条目相同，且它们之前的所有条目也都相同。

这条性质是后面所有安全性证明的出发点。如果你只能记住 Raft 的一条性质，记这条。

不一致时怎么恢复？ Leader 为每个 Follower 维护 nextIndex。被拒绝 → nextIndex-- → 重试。逐条回退（论文原始做法）在落后很多时很慢，所以真实实现都有优化：让 Follower 在拒绝时返回”冲突任期的第一条索引”，Leader 直接跳到那个任期之前。etcd/raft 就是这么做的。

顺带说一个反直觉的事实：Leader 永远不会删除或覆盖自己日志里的条目（Leader Append-Only 性质）。它只会追加。哪怕某些条目从未被提交，只要 Leader 没下台，它的日志就是”只增不改”的。这个不变式简化了大量推理。

提交规则：一个连很多实现者都搞错的细节

“多数派确认即可提交”——这句话对吗？

基本对，但有一个致命的例外。Raft 论文用 Figure 8 整整一幅图来讲这件事。

考虑这个序列（f = 故障节点）：

(a) S1 是 Leader(term 2)，把条目 2 复制到了 S1、S2 → 还没提交 → S1 挂
(b) S5 成为 Leader(term 3)，在索引 2 处写入自己的条目 3 → S5 挂
(c) S1 重新成为 Leader(term 4)，把条目 2 复制给 S3
    此时条目 2 已经在 S1、S2、S3 上 —— 达到多数派！
    但 S1 此时崩溃，S5 又成为 Leader(term 5)...
(d) S5 用自己的条目 3 覆盖了所有人的索引 2
    → 灾难：一个"曾经达到多数派"的条目被覆盖了

问题出在哪？出在 (c) 里，S1 认为”条目 2 达到多数派了，可以提交”。 但条目 2 是任期 2 的条目，S1 当前是任期 4。用”当前任期下的多数派”去判定”旧任期条目的提交状态”是不安全的，因为旧条目随时可能被一个更新的 Leader 覆盖。

Raft 的解法是一条硬规则：

Leader 只能通过”数副本个数”来提交自己当前任期的日志条目。一旦当前任期的某个条目被提交，根据日志匹配性质，它之前的所有条目间接地被提交了。

这条规则怎么落地？ 新 Leader 上任后，立刻追加一条空的 no-op 条目（携带自己的任期）。等这条 no-op 被多数派复制并提交后，它前面所有旧任期的条目就”搭便车”一起安全提交了。

这个 no-op 是必需的，不是优化。 没有它，一个新 Leader 上台后，即使复制了很多旧条目，也不能提交它们，客户端的写请求就会一直挂在那里。etcd 里你能明确看到新 Leader 上台时会 appendEntry(EntryConfChange / empty)。

这是”读论文不读图”和”读论文连图都读”的分水岭。 Figure 8 是 Raft 论文里最值钱的一幅图。

Follower 什么时候应用日志？

Follower 不能自己决定提交。它跟着 Leader 走：

Follower 应用所有 index ≤ min(leaderCommit, 自己最后一条新条目的 index) 的条目。

为什么要取 min？因为 leaderCommit 可能大于 Follower 本地已有的最大索引（Follower 还在追赶中）。取 min 保证”只应用我确实拥有的、且 Leader 说已提交的”部分。

子主题九：Raft 深入（三）—— 安全性到底怎么保证

现在把 Raft 的安全性讲透。Raft 论文 Figure 3 列了五条性质，它们是逐层推导出来的：

性质	内容	靠什么保证
选举安全性 Election Safety	每个任期最多一个 Leader	一票不多投 + 多数派
Leader 只追加 Leader Append-Only	Leader 从不删除/覆盖自己的日志	协议设计
日志匹配 Log Matching	相同 (index, term) → 相同内容 + 相同前缀	AppendEntries 一致性检查
Leader 完整性 Leader Completeness	若某条目在任期 T 被提交，则之后所有任期 > T 的 Leader 都拥有它	选举限制 + 提交规则
状态机安全性 State Machine Safety	若某节点在索引 i 应用了某条目，则其他节点不会在索引 i 应用不同条目	前四条共同推出

前三条是机制，第四条是核心，第五条是终局。我们要证明的就是第四条：已提交的日志永不丢失。

选举限制的证明（反证法，非常漂亮）

命题：如果条目 E 在任期 T 被提交，那么任期 T 之后的每个 Leader 都拥有 E。

证明：

设未来某个任期 U > T 的 Leader 为 L，假设 L 没有 E。
L 要成为 Leader，必须拿到多数派的选票。设给它投票的多数派集合为 Q_vote，|Q_vote| ≥ ⌊n/2⌋ + 1。
E 被提交，意味着 E 存在于多数派节点上。设这个集合为 Q_commit，|Q_commit| ≥ ⌊n/2⌋ + 1。
两个多数派必然相交（Quorum 交集性质）：|Q_vote| + |Q_commit| = 2(⌊n/2⌋+1) > n。设交集里有个节点 S。
S 既投了 L 的票，又拥有 E。
关键：投票规则（条件三）要求 S 只有在”L 的日志至少和我一样新”时才投票。而 S 拥有 E，其任期是 T。
但 L 是在更晚的任期 U 当选的。而 L 在索引 E 的位置上，要么没有条目，要么是一个任期 < T 的条目 —— 总之在 E 那个位置，L 的日志任期比 S 的小。
所以 L 的日志不如 S 新 → S 根本不会投票给 L。矛盾。
因此假设不成立。∎

看明白了吗？安全性的全部秘密，就是”两个多数派必然相交” + “投票时比较日志新旧”这两件事的组合。 而”两个多数派相交”这个东西，你在第 9 章已经见过了。同一个结构，在不同的层次上反复出现 —— 这就是本教程想让你看到的东西。

还有一个必须讲清的点：选举限制只是”必要条件”

注意一个微妙之处：选举限制保证的是”Leader 有全部已提交的条目”，而不是”Leader 拥有最长的日志”。

也就是说：

一个日志更长但包含未提交条目的节点，可能输给一个日志稍短但更”干净”的节点。
这没问题。因为未提交的条目本来就不算数，可以被安全地丢弃。

这引出一个重要的实践认知：Raft 保证的是”已提交的不丢”，它不保证”Leader 收到但还没提交的写不丢”。这些写在 Leader 崩溃时会被静默丢弃，客户端会看到超时或错误。

所以：客户端必须处理”写入结果未知”这种状态。 唯一的答案就是幂等——带上一个 request ID，重试时服务端能识别”这笔我已经做过了”。共识解决不了”我不知道写成功没有”这个边界，幂等才行。

五条持久化的字段

Raft 要求以下状态在响应 RPC 之前必须落盘：

currentTerm
votedFor
log[]

而 commitIndex、lastApplied 可以放在内存里（崩溃后由 Leader 重新告知）。

为什么这个区分很重要？ 因为它定义了”崩溃恢复的最小真相”。一个节点重启后，它知道自己投过谁的票、自己的日志是什么 —— 有这两样就足以正确参与协议。它不需要记住”提交到哪了”，因为那是全集群的事情，不是它一个人的事。

这个设计哲学值得玩味：把”必须由自己记住的”和”可以从别人那里重新学到的”严格分开，是分布式系统设计的通用手法。

子主题十：Raft 的成员变更（Membership Change）—— 最容易被低估的深坑

到现在为止，我们都假设集群的成员是固定的 3 个或 5 个。但现实呢？

节点要换机器、要扩容、要缩容、机房要迁移。集群的成员是会变的。

你会说：这有什么难的？改个配置，重启一下不就行了？

不行。这是 Raft 里最危险的坑之一，因为它能直接导致双主。

为什么”直接切换配置”会双主？

先看为什么不能”停机改配置、一起重启”。简单：停机 == 不可用，而我们用共识就是为了高可用。所以必须在线变更。

那就在线改吧：给所有节点发一个新的配置文件，让它们同时切换到新配置。

问题：你没法让所有节点”同时”切换。 网络延迟不同、处理速度不同，总有一个时间窗口里，一部分节点用旧配置，一部分用新配置。

具体看这个灾难场景：3 节点 {1,2,3} 扩容到 5 节点 {1,2,3,4,5}

旧配置的多数派 = ⌈3/2⌉ = 2 个
新配置的多数派 = ⌈5/2⌉ = 3 个

如果节点 1、2 还在旧配置，节点 3、4、5 已经切到新配置：

{1, 2} 满足旧配置的多数派 → 它们可以选出一个 Leader（比如 1）
{3, 4, 5} 满足新配置的多数派 → 它们也可以选出一个 Leader（比如 3）

这两个集合不相交！

类比：公司董事会从 3 人扩到 5 人。2 个老董事在旧会议室宣布”我们 2 票通过了 A 方案”（符合旧章程），3 个人（1 老 + 2 新）在新会议室宣布”我们 3 票通过了 B 方案”（符合新章程）。两个都合法，两份相互矛盾的决议。这就是双主。

一旦双主，同一任期之外就会出现两个”全序”，日志永久分叉，数据损坏。 这是最严重的事故等级。

为什么单靠 Raft 的”一任一期一票”救不了？ 因为投票规则里的”多数派”是用本地配置算的。用旧配置的节点认为 {1,2} 就是多数派。本地配置的合法性，是整个问题的根源。

解法一：Joint Consensus（联合共识）

Raft 论文（2014）给出的正式方案。思路极其聪明：

既然新旧配置会同时存在，那就别回避它 —— 把”同时存在”变成一个受协议保护的正式状态。

引入一个中间配置 C_old,new，它是新旧配置的并集。在这个配置下：

日志条目必须在 C_old 中达到多数派，且同时在 C_new 中达到多数派，才算提交（双重多数派）
选举也同理：候选人必须同时拿到 C_old 的多数派选票和 C_new 的多数派选票
集群里的任何节点（无论是旧的还是新的）都可以成为 Leader

于是整个变更是三步走：

C_old  ──① 复制到 C_old,new 的多数派──>  C_old,new 提交
       ──② 一旦 C_old,new 提交，Leader 立刻写 C_new ──>  C_new 复制
       ──③ C_new 提交 ──>  变更完成，不在新配置里的节点下线

为什么这样就安全？ 因为：

在 C_old,new 状态下，任何决议都需要 C_old 多数 + C_new 多数，所以绝不可能出现”两个不相交的多数派各自做决定”。
一旦 C_old,new 被提交（双双多数派确认），就没有任何节点能单独使用 C_old 做决定了。因为 C_old,new 的提交本身就意味着 C_old 的多数派已经知道了这件事。
所以从那一刻起，C_old 就”死”了，可以安全地写 C_new。

Joint Consensus 的三个优点（论文原话）：

可以一次增减多个节点（3→5、5→3 都行）
全程不停机
变更期间集群继续正常服务客户端

代价是什么？ 复杂。你要维护”配置”这种特殊日志条目、要实现双重多数派计数、要处理”一个节点被移除后它还在发 RPC 怎么办”。论文自己也说，成员变更是 Raft 里被研究得最少的部分。

还有一个工程细节：新加入的节点往往是空的，得从 Leader 那里同步几 GB 的日志，这段时间它会拖慢”多数派”的达成。所以 Raft 引入了 Learner（非投票成员） 角色：新节点先以 Learner 身份同步数据，同步追上之后再正式加入投票集合。etcd 的 raft.addLearner / promote 就是这个机制。这几乎是生产环境的标配。

解法二：Single-Server Change（单节点变更）

Ongaro 的博士论文（以及 Raft 论文的扩展版）提出了一个更简单的方案，也是 etcd 实际采用的方案：

一次只变更一个节点。

为什么这样就不会双主？ 因为一个漂亮的数学事实：

当集群从 n 个节点变成 n+1 个（或 n-1 个）时，旧配置的任意多数派和新配置的任意多数派，必然相交。

证明（加法就够了）：

加节点：|Q_old| = ⌊n/2⌋ + 1，|Q_new| = ⌊(n+1)/2⌋ + 1
两个集合的元素来自同一个 n+1 个节点的池子
|Q_old| + |Q_new| = ⌊n/2⌋ + ⌊(n+1)/2⌋ + 2 ≥ (n-1)/2 + n/2 + 2 > n + 1

和大于总数 → 必然相交。（减节点的情形同理，读者可以自己验算 n=4→3：3 + 2 = 5 > 4 ✓）

相交意味着什么？ 意味着不可能有两个不相交的多数派。而 Raft 的”一任一期一票”保证了每个任期最多一个 Leader —— 所以每个任期最多一个 Leader，双主不可能出现。

就这么简单。 一个 O(1) 的加法论证，替代了整套 joint consensus 的复杂状态机。

单节点变更的额外细节（实现者必须知道）：

配置变更条目追加即生效（不需要等提交）。因为等提交会形成鸡生蛋问题——你得先用新配置算出多数派，才能判定提交。etcd 的做法是 Leader 一追加 EntryConfChangeV2 就立刻切换到新配置。
必须串行：上一次变更没完成，不能开始下一次。否则又退化成”一次变多个”。
Leader 被移除自己的情形：Leader 必须先把领导权转移给另一个节点（Transfer Leadership），然后再把自己移除。否则它一下台，新配置里没有它，变更就卡住了。
历史教训：这个”简化方案”在提出后曾被社区发现存在关于旧任期 Leader 的边界问题，etcd/Consul 的实现都经过了修正。这正是”不要自己实现共识”的又一个注脚（子主题十二）。

怎么选？ 实践中：

etcd / Consul / TiKV：单节点变更（简单、够用，扩容 3→5 就做两次）
论文规范 / 需要一次换掉多个节点：joint consensus

子主题十一：拜占庭容错（BFT）—— 当节点会撒谎

到目前为止，我们一直假设：节点要么正常工作，要么崩溃（crash）。 崩溃的节点是”睡着了”。

类比：崩溃故障是”睡着了”，拜占庭故障是”喝醉了，而且会撒谎，还会对不同的人说不同的话，甚至和别人串供陷害你”。

拜占庭故障（Byzantine fault） 指的是节点可以做任意事情：

对 A 说”值是 X”，对 B 说”值是 Y”（** equivocation，模棱两可**）
伪造、篡改、重放消息（除非有签名保护）
故意不转发消息、选择性沉默
多个恶意节点串谋
甚至被攻击者完全控制

什么时候要面对这个？

区块链 / 公有链：参与者互不信任，有经济动机作弊
航空航天：辐射可能导致比特翻转，硬件会”胡说八道”（所以叫”拜占庭”，源自 Lamport 1982 年的拜占庭将军问题）
金融清算、多方安全计算

什么时候不用？ 你自己机房里的服务器集群。它们跑你写的代码，被你的运维管控。如果一台机器开始对你撒谎，你更大的问题是怎么进了它的 root。

为什么 BFT 需要 3f+1，而崩溃容错只要 2f+1？

这是本主题最漂亮的推导。先看崩溃容错的 2f+1：

崩溃容错（CFT）：f 个节点崩溃，它们只是沉默，不会撒谎。

需要 n = 2f + 1
多数派 = f + 1
f 个节点崩溃后，还剩 f+1 个活的，全部说真话，刚好构成多数派 ✓
Quorum 交集：两个大小为 f+1 的集合，从 2f+1 里取，交集 = 2(f+1) - (2f+1) = 1。这 1 个节点是诚实的（它没崩溃），所以能传递”我之前见过值 v”的信息。✓

拜占庭容错：f 个节点撒谎。

现在问题来了。假设你问了 n-f 个节点（f 个恶意的可能沉默），收到回复。

其中最多 f 个是恶意的，它们可能说任何话（比如”我没见过任何值”）
剩下至少 n-2f 个是诚实的

为了让诚实者的意见压过撒谎者，你需要：诚实票数 > 恶意票数

$n - 2 f > f ⟹ n > 3 f ⟹ n \geq 3 f + 1$

用 Quorum 交集严格地说：

n = 3f+1，Quorum 大小取 2f+1（因为可能有 f 个节点不响应，必须能在只收到 n-f = 2f+1 个回复时就做决定）
两个大小为 2f+1 的 Quorum 相交：2(2f+1) - (3f+1) = f+1
这 f+1 个交集中的节点里，最多 f 个是恶意的，所以至少有 1 个是诚实的
这 1 个诚实节点是关键：它不会撒谎，所以它会如实告诉新的提案者”我之前见过值 v”

于是：只要有一个诚实节点在交集里，“已决定的值不可改变”就能传递下去。

对比一下：

	崩溃容错	拜占庭容错
节点数	2f+1	3f+1
Quorum 大小	f+1	2f+1
交集大小	1	f+1
交集里必须有几个”好节点”	1 个（没崩溃就行）	1 个诚实的（要排除 f 个恶意的）
容错 1 个故障	3 台	4 台

为什么交集要大那么多？ 因为崩溃节点不投票，但恶意节点会投假票。你得用”多出来的人数”把假票淹没掉。

经典反例：3 个节点容不了 1 个拜占庭故障。 Lamport 1982 年就证明了：3 个将军、其中 1 个叛徒，无论如何都无法达成一致。直观地说：忠诚的将军 B 收到”司令说进攻、A 说撤退”，他无法判断是司令叛变了还是 A 叛变了。信息不对称 + 无法验证来源 = 不可能。

PBFT：第一个”能用”的 BFT 算法

PBFT（Practical Byzantine Fault Tolerance），Castro & Liskov，1999（OSDI’99，期刊版 2002）。

在它之前，BFT 算法慢到无法实用。PBFT 第一次让 BFT 接近实用性能。

核心设定：

n = 3f+1 个副本，最多 f 个作恶
部分同步（partial synchrony） 网络模型：安全性不依赖任何时序假设（这一点非常重要——无论网络多烂，都不会产生两个不同的决定），活性（liveness） 才要求网络最终恢复正常
有一个 Primary（主节点），其余是 Backup，可以视图切换（view change）

三阶段流程：

客户端 ──请求──> Primary
                   │
 ① PRE-PREPARE：Primary 给请求分配序号 n，广播给所有 Backup
                   │
 ② PREPARE：Backup 校验（签名、序号合法、视图正确）后，
             广播 PREPARE 给所有人
             某节点收到 2f+1 个匹配的 PREPARE → 进入 "prepared" 状态
                   │
 ③ COMMIT：节点广播 COMMIT
             收到 2f+1 个匹配的 COMMIT → 本地执行并回复客户端
                   │
客户端等到 f+1 个相同回复 → 确认（因为有 f+1 个相同回复，至少 1 个来自诚实节点）

为什么 BFT 需要三个 Phase，而崩溃容错只要两个？ 这是理解 BFT 的关键反问。

答案是：“我知道”和”我知道大家都知道”是两件事。

PREPARE 阶段解决的是”我确认有 2f+1 个人同意了排序 n”
但这还不够 —— 视图切换时，新的 Primary 怎么知道旧的决定是什么？如果只有部分节点进入了 prepared 状态，新 Primary 可能完全看不到它，就会重新分配一个不同的序号，造成分叉。
所以必须有 COMMIT 阶段：它保证”有 2f+1 个人都知道有 2f+1 个人同意了”。这样视图切换时，新 Primary 从任意 2f+1 个节点收集信息，交集中那个诚实节点一定能说出”这个视图里 prepared 的最高序号是多少”。

这就是”共同知识（common knowledge）“的代价：你要多花一轮通信，去确认”别人也知道”。崩溃容错不需要，因为崩溃的节点不会撒谎，一轮就够了。

PBFT 的代价：

消息复杂度 O(n²)：每个阶段都是全广播。n=4 还好，n=100 就是 10000 条消息。所以 BFT 集群通常只有 4~几十个节点，和 Raft 的 3~5 个其实差不多量级，但消息量高一个数量级。
视图切换复杂：这是 PBFT 最容易出 bug 的地方，论文光是 view change 就写了好几页。
需要密码学：消息签名（防伪造）。这是 O(n²) 之外的 CPU 开销。

区块链里的共识：和 PBFT 完全不是一回事

公有链面对的是一个更狠的问题：你连参与者是谁都不知道。

PBFT 假设”节点身份已知，最多 f 个作恶”。比特币面对的是开放成员（open membership）——任何人都能加入，你连总共有多少节点都不知道，“多数派”根本无从定义。

中本聪共识（Nakamoto Consensus） 的解法完全不同：

用算力投票代替节点投票：工作量证明（PoW）。谁先算出符合难度的哈希，谁就获得记账权
最长链原则：所有节点总是认可累计工作量最大的那条链
假设”诚实节点掌握多数算力”（替代”多数节点诚实”）
概率性最终性（probabilistic finality）：一笔交易被确认后，仍有可能被更长的链推翻，只是概率随确认数指数下降。这就是”等 6 个确认”的由来

这是用”概率”换”开放性”的交易：

	PBFT 类	PoW（中本聪）
成员	固定、已知	开放、匿名
容错假设	f < n/3 作恶	诚实算力 > 50%
最终性	立即确定（提交即终局）	概率性（等 6 个块）
吞吐	数千 TPS	个位数 ~ 数十 TPS
能耗	无	极高
适用	联盟链、许可链	公有链

PoS（权益证明） 把”算力”换成”质押的代币”，用**经济惩罚（slashing）**替代能源消耗——作恶者会被没收押金。但注意：PoS 仍然需要 BFT 式的最终性机制来保证不会分叉。 以太坊 2.0 的 Casper FFG 就是 PoS + BFT 最终性的混合。

现代 BFT 的一大进展：HotStuff（PODC’19）。 它做了两件事：

链式化（chaining）：把三阶段流水线化，每个阶段都可以成为下一个决策的 prepare 阶段，吞吐大幅提升
线性视图切换：用**门限签名（threshold signature）**把 view change 的消息复杂度从 O(n³) 降到 O(n)
乐观响应性（optimistic responsiveness）：网络好的时候，协议速度只受网络延迟限制，不依赖预设的超时

HotStuff 最初被 Facebook 的 Libra/Diem 采用，现在 Aptos、Sui 等新一代公链的共识都源自它的谱系。这是”学术成果 2 年内进入工业界”的罕见案例。

子主题十二：共识的工程实践 —— etcd / ZooKeeper 与”不要自己实现”

讲了这么多理论，来看看生产环境里它长什么样。

etcd：Raft 的工业级实现

etcd 是 Raft 最成功的落地（CoreOS 出品，现在是 Kubernetes 的唯一存储后端）。

核心 API 设计：

KV 存储 + 版本（revision）：每次修改，集群的全局 revision 单调递增。你可以 watch 某个 key 从某个 revision 开始的变化。这是 etcd 最有价值的原语 —— 它把”共识日志”的能力直接暴露给了用户。
租约（Lease）：一个带 TTL 的实体，key 可以绑定到 lease 上，lease 过期 key 自动删除。服务发现就是靠它：服务注册时创建一个 lease 并定期续约，服务挂了 lease 自动过期，key 自动消失。
事务 + CAS：if revision == X then put。分布式锁就是靠这个实现的——先尝试创建，创建成功就是拿到锁。
前缀查询 + Watch：get /services/ --prefix 拿到所有服务实例。

一个关键API细节：线性一致读（Linearizable Read）

前面说过，直接读本地状态机会读到旧值。etcd 怎么解决？

ReadIndex（默认）：Leader 收到读请求时，先记录当前 commitIndex，然后向全体发一轮心跳确认自己还是 Leader，确认成功后，等到状态机应用到 commitIndex 才返回。代价：一轮网络往返。
Lease Read：Leader 在 electionTimeout 内不发起心跳就已确认自己还是 Leader，于是可以直接读本地。代价：依赖时钟（时钟漂移会导致读到旧值，这就是为什么 Raft 论文说需要谨慎设置）。
Serializable Read：直接读本地，最便宜，但可能读到任意旧值。适合对一致性无要求的监控类查询。

这个 API 设计本身就是一堂课：它把”一致性级别”变成了用户可选项，而不是一刀切。好的系统不是只给你最强的那档，而是让你显式地为每一档付费。

etcd 的使用边界（重要，很多人踩坑）：

它是元数据存储，不是数据库。单个请求默认上限 1.5MiB，官方建议整个后端数据库控制在数 GB 量级
别用它存大对象、别用它做消息队列、别高频写
5 个节点就够了，7 个以上只会更慢（多数派更大）
磁盘 fsync 延迟是命门。etcd 对磁盘延迟极其敏感，用机械盘或共享存储会痛不欲生。生产环境必须 SSD

ZooKeeper：ZAB 与”配方（Recipe）“哲学

ZooKeeper（雅虎出品，Hadoop 生态的核心）走的是另一条路。它不给你 KV，它给你一个”文件系统”：

层次化命名空间：/services/user-service/instance-1
Znode 类型：持久节点、临时节点（Ephemeral）、顺序节点（Sequential）、临时顺序节点
Watch：监听节点变化（一次性，触发后要重新注册）
Session：客户端与 ZK 的会话。会话超时 → 该会话创建的所有临时节点自动删除

ZooKeeper 的精髓是”配方（Recipe）“：用这几个极简原语，拼出复杂功能。

分布式锁：

所有竞争者：create /lock/lock- -e -s   （临时 + 顺序节点）
谁创建的节点序号最小，谁拿到锁
其他人 watch 自己前一位的那个节点
前一位消失 → 自己检查是否变成最小 → 是则拿到锁

这个设计的优雅之处：没有轮询、没有惊群（herd effect），链式唤醒，一个节点消失只唤醒一个等待者。而且用临时节点，客户端崩溃后锁自动释放——不需要超时机制。

选主：同样的配方，序号最小者为主。

服务发现：服务注册为临时节点，客户端 watch 父节点的子节点列表。

ZooKeeper 的坑（经验之谈）：

Watch 是一次性的，而且在事件和重新 watch 之间有窗口，可能丢事件。所以正确用法是：收到事件后重新 getData 拉取最新状态，而不是依赖事件内容
Session 超时 会导致所有临时节点消失，如果应用没处理好 session expired，会出现”主节点还在跑但临时节点没了”的诡异状态
ZK 不是数据库，znode 有 1MB 限制，且所有数据都在内存

顺带说一句：Kafka 从 2.8 开始用 KRaft（自己的 Raft 实现）取代了 ZooKeeper。为什么？ 因为 ZK 是外部依赖，运维两套集群、两套配置、两套故障模型。用内嵌的 Raft 做元数据管理，一套系统搞定。这是”共识作为库”战胜”共识作为服务”的一个标志性事件。

分布式锁的残酷真相：共识给你的锁，可能锁不住你的资源

这一节值得单独讲，因为它是共识工程实践里最经典的认知陷阱。

2016 年，Martin Kleppmann（《数据密集型应用系统设计》作者）发了一篇著名的文章《How to do distributed locking》，质疑 Redis Redlock 的正确性。其中提出的论点，对任何基于共识的分布式锁都成立。

场景：

1. 客户端 A 获取锁
2. A 开始写共享资源（比如往存储里写数据）
3. A 发生了一次长时间的 STW GC 暂停（比如 30 秒）
4. 锁因为 lease 超时自动释放
5. 客户端 B 获取锁，开始写同一个资源
6. A 从 GC 中醒来，认为自己还持有锁，继续写
7. 两个客户端同时写 —— 数据损坏

关键点：A 的锁是合法的、共识是完美的、锁服务没有任何 bug。问题出在 A 自己”卡住了”却不知道时间已经流逝。

共识解决不了这个问题。 因为共识保证的是”锁的归属顺序是一致的”，它无法保证持锁者不会在持锁期间发疯。

正确的解法：Fencing Token（栅栏令牌）

锁服务每次授予锁时，返回一个单调递增的令牌（etcd 的 revision 天然就是！）
客户端每次写共享资源时，必须带上这个令牌
共享资源端必须检查令牌：如果收到的令牌小于自己见过的最新令牌，拒绝这个写操作

看清楚这个架构的关键：安全性的最终防线不在锁服务，而在被保护的资源本身。

类比：锁服务给你一张通行证，上面有编号。你拿着 5 号通行证去开门，保安（资源端）见过 7 号了，直接把 5 号拦下。 锁服务只负责发号，真正挡住人的是保安。

这条结论非常深刻：很多”分布式锁”的 bug，不是共识算法的 bug，而是”共享资源不支持 fencing”的架构缺陷。 如果你的存储服务不支持条件写入（CAS / test-and-set），那么无论你用 etcd、ZooKeeper 还是 Redis 做锁，锁都是不可靠的。

为什么”不要自己实现共识算法”

最后，把这条铁律讲透。

Google 内部有一句流传很广的话，通常归于 Chubby 的作者 Mike Burrows：

“世界上只有一种共识协议，那就是 Paxos —— 所有其他方法都只是 Paxos 的残缺版本。”

这句话的潜台词是：共识的正确性证明极其微妙，你觉得你自己发明的那个”更简单”的方案，几乎肯定是错的。

具体理由有五条：

理由一：论文描述的是”算法骨架”，不是”可运行系统”。

Google 的《Paxos Made Live》（Chandra、Griesemer、Redstone，2007）是这方面的里程碑文献。他们记录了把”已被证明正确的 Paxos”变成 Chubby 生产系统的过程，结论极其坦诚：

“Paxos 算法的描述与真实系统的需求之间存在巨大的鸿沟……最终的系统实际上是建立在一个未经证明的协议之上的。”

他们不得不额外发明一堆论文里没写的东西：磁盘损坏处理、主节点租约（master lease）、快照与日志压缩、成员变更、epoch 编号、状态机确定性保证……

换句话说：证明正确的那个协议，和你最终跑在生产上的那个系统，是两回事。 中间那段工程距离，才是真正的坑。

理由二：正确性 bug 只在极罕见的时序下暴露。

共识的 bug 在正常运行时永远不出现。它们只在「网络分区 + 节点崩溃 + 消息乱序 + 恰好在那个时间点」的组合下爆炸。你的单元测试、集成测试、甚至几个月的跑量都发现不了。

理由三：Jepsen 测试反复证明，成熟系统也有共识 bug。

Kyle Kingsbury 的 Jepsen 项目对大量分布式系统做了严格的线性一致性测试，发现过 etcd、Consul、ZooKeeper、Cassandra、MongoDB、Riak 等系统的一致性缺陷。这些系统是由最顶尖的团队写的、有形式化验证、有多年生产验证。连它们都会踩坑，你凭什么觉得自己不会？

理由四：有成熟实现，直接用。

Go：etcd-io/raft（etcd 用的，最成熟）
C++：braft（百度，BRPC 生态）
Java：Apache Ratis
Rust：openraft、tikv/raft-rs
服务形态：直接用 etcd / ZooKeeper / Consul

理由五：调试成本不成比例。

自己实现的共识算法出问题时，你没有工具、没有经验、没有社区。而 etcd 出问题时，你能在 GitHub 上搜到别人踩过的坑。

那什么时候该自己实现？ 只有一种情况：你在做共识算法的研究，或者你在写一个共识库本身。 如果你在写业务系统，答案永远是不。

子主题十三：业界对照 —— ZAB、Chubby、Spanner 的三种玩法

理论讲够了，看看真实世界的巨头们怎么干的。这三个案例分别代表了三种截然不同的思路。

ZooKeeper 的 ZAB：共识即”原子广播”

ZAB（ZooKeeper Atomic Broadcast） 经常被称为”类似 Paxos 的协议”，但它其实有自己独特的定位。

ZAB 的视角和 Raft 不一样：

Raft 说的是”我们就日志达成共识”，然后顺带得到了全序
ZAB 说的是”我们要实现原子广播（Atomic Broadcast）”—— 保证所有消息以相同的顺序被所有副本恰好传递一次

这两者是等价的（都能互相实现），但视角差异导致了设计差异。

ZAB 的核心机制：

zxid：一个 64 位的全局事务 ID，高 32 位是 epoch（纪元），低 32 位是计数器。epoch 类似 Raft 的 term，每次换主 +1
四个阶段：
- Leader Election（选举）：Fast Leader Election 算法，节点互相交换（epoch, zxid, sid），选出 zxid 最大的节点当 Leader
- Discovery（发现）：新 Leader 收集 Follower 的信息，确定”最新的已提交历史”
- Synchronization（同步）：Leader 把自己的历史推给落后的 Follower，直到多数派完全同步
- Broadcast（广播）：正常服务，类似 Raft 的两阶段提交（Proposal → ACK → Commit）

ZAB 和 Raft 最关键的差异在选举：

	Raft	ZAB
选举时的日志约束	投票时就检查：候选人的日志必须至少和我一样新（否则不投票）	选的时候不严格比较，选出 zxid 最大者
落后的日志怎么办	靠 `nextIndex` 回退，在正常复制流程里修复	有独立的 Synchronization 阶段，先同步完再开始广播
保证的性质	Leader Completeness（Leader 拥有全部已提交条目）	Primary Order：若 Leader 先提议 a 后提议 b，则新 Leader 必然也保持 a 在 b 之前

一句话总结差异：Raft 把”日志必须最新”放在投票的准入条件里；ZAB 把”日志必须最新”放在独立的同步阶段里。

这个差异有意思在哪？ 它揭示了一个通用的设计张力：是”事前限制”（投票时就卡住）还是”事后修复”（选完再补齐）？ Raft 选了前者，逻辑更集中；ZAB 选了后者，选举更快（不用在投票 RPC 里比日志）。没有对错，只有取舍。

还有个实践细节：ZooKeeper 的 sync() 操作。因为 ZK 的读默认可能落到落后的 Follower，需要强一致读时客户端要先调 sync()，它会强制该 Follower 追上 Leader。这是”读一致性需要额外机制”的又一个例证。

Chubby：把共识包装成”锁服务”

Chubby（OSDI’06，Mike Burrows） 是 Google 的分布式锁服务。它的设计哲学极其值得学习：

不给开发者一个”共识库”，而是给一个”锁服务”。

为什么？ 因为 Burrows 他们发现：大多数开发者根本不需要共识，他们需要的是”选主”和”存一点点元数据”。

让每个团队都去接一个 Paxos 库、自己处理成员变更和日志压缩，是灾难。不如提供一个极简的高可用服务，把共识的复杂度藏在里面。

Chubby 的设计：

一个 Chubby Cell = 5 个副本，跑 Paxos
提供粗粒度锁（coarse-grained lock）：持有时间以小时/天计，不是毫秒级
提供小文件存储：存元数据，比如”谁是 GFS 的 master”、“Bigtable 的 schema 在哪”
有客户端缓存 + 失效通知机制

“粗粒度”这个设计决策非常聪明：锁的获取频率极低，所以性能完全不是问题，5 个副本的 Paxos 完全扛得住。

Chubby 的经典用户：

GFS：用 Chubby 选主（master）
Bigtable：用 Chubby 选主、存 schema、发现 tablet server、存 access control list
Google 内部几乎所有系统：用 Chubby 做名字服务

Chubby 的两个深远贡献：

证明了”共识即服务”的可行性 —— 直接影响了 ZooKeeper（ZooKeeper 的论文明确说自己是 Chubby 的开源对标）。etcd 也是这条路线。
《Paxos Made Live》这篇工程总结，把”论文算法 → 生产系统”的巨大鸿沟第一次公开讲清楚了。这篇文章的价值，可能比很多算法论文还高。

类比：Chubby 的做法就像”不卖发动机，卖整车”。 你想去某个地方，不需要懂内燃机原理。抽象层次的提升，让一项技术从”少数专家的玩具”变成”所有人的基础设施”。

Spanner：用硬件时钟打破”强一致必然慢”的直觉

这是本主题最有野心的一个案例。

先建立共识：Spanner（OSDI’12，Google）是全球分布式数据库，跨洲部署，支持外部一致（externally consistent，等价于线性一致）的分布式事务。

在 Spanner 之前，业界的普遍认知是：

全球范围的强一致 = 慢到无法接受。

因为每次写都要跨洲跑 Paxos / 2PC，RTT 就是几百毫秒。

Spanner 做了三件事：

1. 数据分片 + 每片一个 Paxos 组

不是整个数据库一个 Paxos 组，而是每个 tablet（分片）一个独立的 Paxos 组。这样：

不同分片可以并行复制、并行提交
单个分片内的复制是 Paxos（多副本 + 选出的 leader）
跨分片的事务用 2PC，且参与者是各个 Paxos 组的 Leader

注意这里 2PC 和 Paxos 是怎么配合的：2PC 负责跨分片的原子性，而每个”参与者”本身是一个 Paxos 组（高可用，不阻塞）。这正是子主题四讲的”用共识消除 2PC 单点”的落地。

2. TrueTime：给不确定性一个上界

这是 Spanner 最革命的部分。

普通服务器的时钟是不可信的（NTP 误差几十毫秒，还可能跳变）。Google 的做法是用硬件消灭误差：

每个数据中心部署 GPS 接收器 + 原子钟，两者互为备份（GPS 会受天线故障影响，原子钟会漂移，两者互补）。

TrueTime 提供的 API 极其简单：

TT.now() → 返回一个区间 [earliest, latest]，而不是一个点
真实时间保证落在这个区间内
TT.after(t) → 判断 t 是否确定已经过去
TT.before(t) → 判断 t 是否确定还没到来

关键：它返回的是区间，不是值。 区间宽度 ε 论文给的典型范围是约 1~7 毫秒（取决于时钟同步间隔和漂移率）。

类比：普通时钟告诉你”现在 3 点”（但可能是 2:59:50 也可能是 3:00:10）。TrueTime 告诉你”现在在 2:59:57 到 3:00:04 之间”（而且保证是真的）。 承认不确定性并给出严格上界，比假装精确有用得多。

3. Commit Wait：等不确定性过去

有了 TrueTime，怎么实现外部一致性？规则极简：

给事务分配一个提交时间戳 s = TT.now().latest，然后 Leader 必须等待，直到 TT.after(s) 为真（即 s 这个时刻确定已经过去了），才允许提交生效。

为什么这样就够？ 假设事务 T1 提交、然后客户端发起 T2。因为 T1 在提交前等待了 s 已经确定过去，所以 T2 开始时，物理时间一定 > s。于是 T2 拿到的时间戳一定 > s。外部因果序得到保证。

代价：约 2ε 的提交等待（论文说典型值 10ms 左右）。

Spanner 真正打破了什么？

现在做诚实的评估。Spanner 并没有让写变快。 每次写仍然要：

Paxos 跨副本往返（跨洲就是几十到上百 ms）
2PC 跨分片协调（再来一轮）
Commit Wait（再加 ~10ms）

那它”打破”了什么？打破了”读必须也要付出这个代价”的直觉。

Spanner 的杀手锏是：只读事务不需要任何锁和协调。

因为 TrueTime 给出了全局时间的严格上界，一个副本可以直接回答：“给我 t 时刻的快照”，只要它的数据已经复制到 t 之后（TT.after(t) 且副本的 safe time ≥ t）。读请求完全在本地完成，不需要跨洲通信、不阻塞写。

这就是”用硬件换软件”的精髓：

你要么在协议里花通信代价（读也要走一轮共识），要么在硬件上花钱（GPS + 原子钟）。Google 选了后者，并且把省下来的通信成本，变成了全球规模的线性一致读。

三个必须说清的诚实提醒：

TrueTime 是 Google 专属硬件，别的公司没有。所以开源社区的方案是 CockroachDB + HLC（混合逻辑时钟）+ 不确定性区间重启，或者 TiDB + 中心化 TSO（时间戳授时服务）。它们都能做到外部一致，但代价形态不同（CockroachDB 可能需要事务重启，TiDB 的 TSO 有单点瓶颈）
Spanner 的写延迟并不低，跨洲事务的提交延迟是几十毫秒量级。它赢在读，不赢在写
TrueTime 依赖”不确定性有上界”这个假设。如果 ε 突然暴涨（时钟故障），Spanner 会主动延长等待甚至拒绝服务，用可用性换取正确性。这又是一次 CAP 的取舍

三个案例的对照总结

	ZAB / ZooKeeper	Chubby	Spanner
共识算法	ZAB（原子广播）	Paxos	Paxos（每分片一组）
对外抽象	层次命名空间 + 配方	锁服务	数据库
核心创新	独立同步阶段 + 配方生态	共识即服务	TrueTime 换通信
解决的问题	让开源界用上共识	让普通开发者用上共识	让全球强一致可用
影响	Kafka、Hadoop、Dubbo	ZooKeeper、etcd 的精神祖先	CockroachDB、TiDB、YugabyteDB

看到共同点了吗？这三者的价值，都不在”发明新共识算法”，而在”找到正确的抽象层次”。 共识算法本身几十年没本质变化，变化的是它被包装成什么东西交到用户手里。

子主题十四：共识的边界 —— 它解决什么，不解决什么

最后，把共识的边界画清楚。这是全章最实用的部分，因为绝大多数的过度设计，都源于搞错了这个边界。

共识解决什么？

而且只有一件事：

让一组节点，就一个”值”或一条”操作序列”，在部分节点故障的情况下，达成不可撤销的一致。

展开成五种具体用法：

选主（Leader Election）：让集群对”谁是主”达成一致
分布式锁 / 租约：对”这个资源归谁”达成一致
关键元数据存储：配置、路由表、schema、成员列表 —— 量小、要求强一致
原子提交的决定点：分布式事务里”提交还是回滚”这个决定，用共识存下来，协调者就不再是单点
全序广播：给事件排序（这就是 Raft / ZAB 的直接形态）

注意这五条的共同特征：量小、值关键、变化不频繁。 这不是巧合。

共识不解决什么？—— 八条边界

边界一：不解决应用层逻辑错误。

共识会极其忠实地、一字不差地把你的 bug 复制到每一个副本上。

如果你的状态机里有”余额可以为负”的漏洞，共识保证的是所有副本都一致地允许余额为负。

类比：五个人一致同意把钱转给骗子。共识保证了他们意见一致，但这改变不了他们被骗的事实。

共识是复制机，不是校验机。 “这个操作该不该做”的语义校验，永远在应用层。

边界二：不解决性能和容量。

这是最常见的误解。有人以为”上了 Raft 就能扩容”。

错。加节点只会让共识更慢（多数派更大，要等更多副本确认）。

3 节点：写需要 2 个确认
5 节点：写需要 3 个确认
7 节点：写需要 4 个确认

共识组的最优规模是 3 或 5。 想扩容？分片（sharding），每个分片一个独立的共识组。这是 Spanner、TiKV、CockroachDB 的统一答案：用分片扩容量，用共识保一致，两者正交。

边界三：不解决拜占庭故障。

Raft、Paxos、ZAB 全部假设节点只会崩溃，不会撒谎。要防作恶，得上 BFT（子主题十一），代价是 3f+1 和 O(n²) 消息。

边界四：不保证”永远可用”。

共识是 CP 系统（第 9 章）。发生网络分区时，少数派一侧完全不可用（它凑不出多数派，无法提交任何写）。

所以用共识的前提是：你能接受”宁可不可用，也不能出错”。 如果你的业务是”宁可数据不一致也要能下单”，那共识不是你的答案。

边界五：不解决延迟问题，它就是延迟的来源。

共识的写延迟构成：

客户端 → Leader 网络 RTT
+ Leader 本地 fsync（磁盘）
+ Leader → Follower 网络 RTT
+ Follower fsync（磁盘）
+ Follower → Leader 网络 RTT

跨地域部署时，这就是 100ms 量级。 而且这个延迟无法优化掉——它是”多数派确认 + 持久化”这个语义的固有成本。

你能做的只有：

用更好的磁盘（NVMe SSD）
缩短物理距离（同城多机房而不是跨洲）
批处理（batching）：把多个写合并成一条日志条目，摊薄 fsync 和网络开销。这是所有 Raft 实现的标配优化
流水线（pipelining）：不等上一个条目确认就发下一个，提升吞吐

但注意：批处理和流水线提升的是吞吐，不是单条延迟。 这是两回事，别搞混。

边界六：不提供”时间”。

共识给的是顺序（全序），不是时间戳。“第 100 条日志”不等于”下午 3 点整”。

如果你的应用需要时间（比如”这条记录什么时候写的”），你得额外要：NTP、HLC、TSO、或者 TrueTime。这是 Spanner 那节的核心洞察：顺序和时间是两件事。

边界七：不保证读的一致性（除非你用对 API）。

前面讲过：直接读本地副本会读到旧值。线性一致读需要 ReadIndex（多一轮 RTT）或 Lease Read（依赖时钟）。

这是生产事故高发区：很多人把 etcd 当普通缓存读，然后在”刚写完立刻读不到”上debug两天。

边界八：不解决”我不知道刚才那笔写成功没有”。

客户端发起了写，网络断了，客户端不知道 Leader 是收到了还是没收到。

共识不会告诉你答案。 唯一的解药是幂等：请求带上唯一 ID，重试时服务端识别”这笔我做过了”，返回同样的结果。

记住这条：共识管的是”副本之间的一致性”，不管”客户端和服务端之间的不确定性”。后者是幂等和重试的地盘。

子主题十五：实操视角 —— 什么时候真的需要共识

把边界画完了，最后给一套能直接用的决策框架。

先问自己三个问题

问题一：我需要”全序”吗？还是只需要”最终一致”？

判定方法：如果两个操作的先后顺序会影响最终结果的正确性，你需要全序。

需要：账户余额（先扣后加，顺序反了就透支）、库存扣减、锁的归属
不需要：点赞数、页面浏览量、日志收集、社交动态流

问题二：出错的代价是”可逆”的吗？

这是最关键的一问。

不可逆：选主选错了 → 两个主同时写 → 数据物理损坏。锁发重了 → 两个任务同时转账 → 钱没了。这类错误无法通过事后对账修复。→ 用共识
可逆：计数器少加了几次 → 跑个批处理重算。消息重复消费了 → 幂等兜住。→ 别用共识

这是最锋利的一刀：能用对账/重算/幂等修正的错误，就不要用共识去预防。

问题三：数据量有多大？

几条、几百条、几 MB 级的元数据 → 共识完全 OK
GB 级、TB 级、每秒几十万写 → 共识直接跪。分片 + 异步复制 + 最终一致

决策表

场景	需要共识吗	方案
选主（避免双主写坏数据）	需要	etcd / ZK 的临时节点 + 租约
分布式锁（保护不可逆操作）	需要，且必须配 fencing token	etcd CAS + revision 做令牌
集群配置、路由表、schema	需要	etcd / ZK
分布式事务的提交决定	需要	每个参与者本身是共识组；2PC 协调者也多副本
服务发现	通常用现成的	etcd lease / ZK 临时节点 / Consul
消息队列	不需要	分区 + offset + 至少一次投递 + 消费端幂等
计数器、点赞、PV	不需要	Redis INCR / CRDT / 异步聚合
业务主数据（大吞吐）	不需要（只在元数据处用）	分片 + 主从复制 + 最终一致 + 对账
缓存	不需要	过期时间 + 失效
Session	不需要	存 Redis（丢了重新登录就行）
定时任务调度（避免重复执行）	需要轻量共识或外部锁	可以接受”偶尔执行两次”就用幂等；不能接受就用锁

一个”够用就好”的替代方案清单

在下共识之前，先看看这些能不能解决你的问题。它们全都比共识便宜几个数量级：

幂等 + 重试：解决”不知道有没有成功”
唯一约束：数据库的 UNIQUE 索引。想防重复？一条约束就够了，比分布式锁简单一万倍
乐观锁 / CAS：UPDATE ... WHERE version = ?。单机数据库的事务就够
单写入者：能不能就让一个进程负责写？很多”分布式”问题，本质是”没想清楚就把职责分散了”
最终一致 + 对账：允许短暂不一致，用定时任务校正
CRDT：适合”多写、无冲突语义”的场景（计数器、集合、协作编辑）
定时任务兜底：很多一致性要求，用”每天凌晨跑一次对账”就能满足

注意第 3、4 条。它们的共同点是：先问”能不能不分布式”。

最好的分布式系统，是没有分布式的系统。 这句话不是玩笑。把状态收拢到单机数据库、用它的事务，能解决 90% 的”一致性需求”。剩下 10%，再考虑共识。

三条实践铁律

铁律一：共识组的规模是 3 或 5，别再多了。

3 节点：容忍 1 个故障，性价比最高
5 节点：容忍 2 个故障，适合要求高的场景
7 节点以上：只会更慢，收益递减。除非你有特殊的跨地域需求（比如 Spanner 需要副本靠近不同地区的用户）

为什么总是奇数？ 因为偶数不增加容错能力：4 节点的多数派是 3，也只能容忍 1 个故障（和 3 节点一样），但你多付了一台机器的成本和一次网络往返。纯粹的浪费。

铁律二：能”共识即服务”就别”共识即库”。

优先用 etcd / ZooKeeper / Consul 这样的现成服务
只有在”性能或部署形态不允许外部依赖”时（比如 Kafka 去 ZK 化），才内嵌共识库

理由：运维复杂度、故障排查、人才储备。一套系统的故障模型，远好过两套。

铁律三：把”要不要共识”当成架构评审的固定议题。

在评审会上明确问：“这个组件为什么需要线性一致？不用会怎样？”

如果答案是”因为听起来更可靠” → 驳回。 如果答案是”选错主会导致数据物理损坏，且无法对账修复” → 批准。

共识是一种昂贵的保险。买保险之前，先算清楚你保的东西值多少钱、以及不买的话损失有多大。

最后，把整章串成一句话

从 FLP 的绝望结论，到 Paxos 的理论突破，到 Raft 的可理解性革命，到复制状态机的抽象，到 BFT 的信任模型升级，到 Spanner 用硬件换软件的疯狂 —— 这条线上反复出现的是同一个模式：

每一次进步，都不是”发明了一个更强的算法”，而是”找到了正确的抽象层次，或者诚实地承认了某个约束”。

Raft 承认了”并发提案太难” → 用强领导者绕开它
复制状态机承认了”确定性是前提” → 把不确定性提前到日志
BFT 承认了”节点会撒谎” → 用 3f+1 的多数把谎言淹没
Spanner 承认了”时钟有误差” → 用 GPS 和原子钟给出误差上界
FLP 承认了”异步网络下无法保证终止” → 于是所有实用算法都引入了部分同步假设

这就是本章想让你带走的”通用问题及其解法演进”：当一个问题在理论上被证明困难甚至不可能时，工程上的答案从来不是死磕，而是——重新定义问题的边界，或者把代价转移到别的地方。

演进脉络

1982：Lamport 发表《The Byzantine Generals Problem》，提出”节点会撒谎”的容错模型，证明 3f+1 的必要性。
1985：FLP 不可能结果发表，证明异步网络下共识无法保证总是终止。
1990（1998 发表）：Lamport 提出 Paxos，第一个被证明正确的共识算法，但极难理解和实现。
1999：Castro & Liskov 提出 PBFT，让拜占庭容错第一次接近实用。
2000s：ZooKeeper 用 ZAB 协议（类似 Paxos 的变体）把共识带入工业界；Chubby 把 Paxos 包装成”锁服务”。
2007：Google 发表《Paxos Made Live》，第一次公开讲清楚”论文算法 → 生产系统”的巨大鸿沟。
2012：Spanner 发表，用 Paxos + TrueTime（GPS + 原子钟）实现全球规模的外部一致性分布式事务。
2014：Raft 论文（USENIX ATC）发表，以”可理解性”为设计目标，迅速成为新一代分布式系统的标配。
2010s 至今：etcd/TiKV/CockroachDB 等用 Raft；区块链领域用 PBFT/PoW/PoS 等拜占庭容错共识；HotStuff（2019）把 BFT 的通信复杂度降到线性。
2020s：Kafka 用 KRaft 去掉 ZooKeeper 依赖，标志”共识作为内嵌库”的成熟。

本章思考题

【思考题】

为什么”投票”解决不了共识问题？请列出至少三个困难。FLP 不可能结果到底说了什么（以及它没说什么）？
Paxos 的 Quorum 交集机制，为什么能保证”一旦某个值被多数派接受，后续提案必然还是这个值”？
Raft 为”可理解性”做了哪三个关键设计？为什么说”强领导者”简化了一切？
2PC 和共识算法的区别是什么？2PC 的致命缺陷是什么，现代系统怎么解决？
什么是复制状态机？为什么说”共识算法的作用就是就操作序列达成一致”？它对状态机提出了什么硬性要求，工程上最容易在哪里踩坑？
Raft 的 Leader 选举完整过程是怎样的？任期（Term）的作用是什么？为什么选举超时必须随机化？投票时必须同时满足哪三个条件？
Raft 的”日志匹配性质”是什么？AppendEntries 为什么要检查”前一条”日志的 index 和 term，而不是检查当前这条？
Raft 论文 Figure 8 揭示了什么问题？为什么 Leader 不能靠”数副本个数”提交旧任期的日志条目？新 Leader 上任后为什么要追加一条空的 no-op 条目？
请叙述”Leader 完整性”的反证法证明：为什么已提交的条目一定会被未来的每个 Leader 拥有？这个证明依赖哪两个机制？
集群从 3 节点直接扩容到 5 节点，为什么会导致双主？Joint Consensus 是怎么解决的？单节点变更（single-server change）为什么天然安全？请给出数学论证。
为什么拜占庭容错需要 3f+1 个节点，而崩溃容错只要 2f+1？请用 Quorum 交集给出严格论证。PBFT 为什么需要三个阶段，而崩溃容错算法两个阶段就够了？
已经有了可靠的共识服务（etcd/ZooKeeper）实现的分布式锁，为什么仍然可能锁不住资源？Fencing Token 是什么，它的安全性防线最终落在哪里？
Spanner 的 TrueTime 到底”打破”了什么？它让写变快了吗？请诚实评估它的代价和适用边界。
请列出共识”不解决”的至少六件事，并给出一套判断”这个场景到底要不要上共识”的决策框架。

【参考答案】

困难：各节点提出的值可能不同导致形不成多数派；消息会丢/乱序/重复导致计数不可靠；节点会宕机恢复导致重复投票；没有全局”同时”概念（时钟不同步、延迟不同），无法定义”当前轮次”。FLP 说的是：在纯异步模型下（无时钟、无法区分崩溃与慢），即使只有一个节点可能故障，也不存在总能终止的确定性共识算法。它没说”共识不可能”——实用算法通过引入”部分同步性假设”（假设网络大多数时候正常）绕过了它，保证”网络正常时会终止”而非”永远保证终止”。
因为新提案必须先向多数派发 Prepare，而这个多数派与”已接受 v 的多数派”必然有交集（Quorum 交集性质）。交集里的 Acceptor 会回复”我之前接受过 v”，Paxos 规则强制 Proposer 必须用”编号最大的已接受提案的值”，于是新提案的值必然是 v。这就保证了已决定的值不可改变。
三个设计：强领导者（任何时刻只有一个 Leader，所有写都经它，消除了 Paxos 最混乱的”多 Proposer 并发提案”）、问题分解成三个子问题（Leader 选举 / 日志复制 / 安全性）、用任期（Term）作为逻辑时钟（解决”谁最新”的判断，不需要全局时钟）。强领导者简化了一切，因为并发提案的冲突处理是共识里最难理解的部分，有了单一 Leader 后这部分直接消失。
2PC 是”原子提交协议”（关心所有节点要么都做要么都不做），共识是”就一个值达成一致”，相关但不同。2PC 致命缺陷：协调者是单点——若协调者在发出提交命令前挂了，所有参与者已投票并锁住资源，却永远等不到最终命令，系统阻塞。现代解法：用真正的共识算法（Raft/Paxos）来做提交决定，把协调者本身也做成多副本高可用（Spanner 就是每个 2PC 参与者本身是一个 Paxos 组，协调者不再单点）。
复制状态机的核心思想：若所有副本从相同初始状态出发、按相同顺序执行相同的确定性操作序列，必到达相同最终状态。于是共识的职责从”就一个值达成一致”升级为”就整条操作日志达成一致”，状态机只是日志的回放结果。它对状态机提出的硬性要求是确定性：同样的输入序列必须产生同样的状态和输出，因此状态机里不能出现 time.Now()、随机数、读本地文件/环境变量/外部服务、依赖 map 遍历顺序、依赖线程调度或浮点未定义行为。工程上最容易踩的坑就是在状态机里用本地时钟生成 ID、或用 map 遍历顺序生成配置——单进程测试 100% 通过，多副本下永久分叉。正确做法是把所有不确定性提前到日志里：由 Leader 在追加条目时就把时间戳/随机数固定下来。由这个模型还推出三条：日志是真相、状态机是缓存（故可快照 + 日志压缩）；共识给的是全序（这是线性一致的物理来源）；全序对互不相关的操作是”过度收费”，想省这笔钱就得放弃线性一致（CRDT / 因果一致）。另外，判定一个系统有没有真共识，只看一个场景：主节点在”已告诉客户端成功”之后立刻断电，新主上台，这笔数据还在不在——不在，就只是复制，没有共识。
完整过程：Follower 的选举超时定时器到期仍未收到心跳 → currentTerm +1 → 转为 Candidate → 投自己一票、重置定时器 → 并行发 RequestVote（携带 term、candidateId、lastLogIndex、lastLogTerm）→ 三种结局：（a）拿到多数派选票 → 成为 Leader，立刻发心跳宣告权威并追加一条 no-op；（b）收到任期 ≥ 自己的 AppendEntries → 退化为 Follower；（c）超时分裂投票 → 任期再 +1、重新随机化定时器、重来。Term 是逻辑时钟：每任期最多一个 Leader；任何节点看到更大任期立即更新并退化为 Follower（这是”脑裂后老 Leader 复活”的唯一处理机制）；Term 增速也是运维诊断信号（疯涨说明网络抖动或反复选主），并且 currentTerm / votedFor / log 必须在回复 RPC 前落盘（否则重启后可在同一任期投两次票 → 双主）。随机化的必要性：固定超时会让所有节点同时超时、同时给自己投票，谁也拿不到多数派，且下一轮再次同时超时；随机化（如 [150ms, 300ms]）让一人先动手，其余节点被 RequestVote 重置定时器，从而大概率一次选出主。约束：广播时间 ≪ 选举超时 ≪ MTBF。投票三条件：①候选人 term 不小于我的 currentTerm；②我本任期尚未投给别人（保证每任期最多一主）；③候选人日志至少和我一样新——先比 lastLogTerm，大者新；相同则比 lastLogIndex，大者新（信任任期甚于信任索引，因为高任期的条目来自更晚的 Leader）。
日志匹配性质：如果两个日志中有两个条目 index 与 term 都相同，则这两个条目内容相同，且它们之前的所有条目也都相同。AppendEntries 检查”前一条”是因为这是一个归纳链条：prevLogIndex/prevLogTerm 匹配，即证明”到此为止我的日志与 Leader 完全一致”，新条目接在一条已确认一致的尾巴上，归纳成立；若只检查当前条目，无法排除前面存在缺失或冲突。不匹配时 Follower 拒绝，Leader 将 nextIndex 递减重试（真实实现会让 Follower 返回冲突任期的首索引，直接跳过整个任期以加速回退）。另外 Leader 永不删除或覆盖自己日志中的条目（Leader Append-Only），这个不变式简化了大量推理。Follower 只在收到 leaderCommit 后应用 index ≤ min(leaderCommit, 自己最后一条新条目 index) 的条目。
Figure 8 的场景：S1 在 term 2 把条目复制到 S1、S2 后崩溃（未提交）；S5 在 term 3 于同一索引写入自己的条目后崩溃；S1 在 term 4 重新当选并把旧条目复制到 S3——此时它已在多数派上，若 S1 据此判定”已提交”并让客户端读到，随后 S1 崩溃、S5 当选并用自己的条目覆盖该索引，就出现”已提交的条目被覆盖”的分叉。根因：用当前任期的多数派去判定旧任期条目的提交状态是不安全的，旧条目随时可能被更新的 Leader 覆盖。Raft 的硬规则：Leader 只能通过数副本来提交自己当前任期的条目；一旦当前任期某个条目被提交，它之前的所有条目由日志匹配性质间接地被提交。 落地方式：新 Leader 上任后立刻追加一条携带自己任期的空 no-op，等它被多数派复制并提交，前面所有旧任期的条目就”搭便车”一起安全提交——这不是优化而是必需，否则新 Leader 上台后客户端的写会一直挂着无法提交。
命题：若条目 E 在任期 T 被提交，则任期 > T 的每个 Leader 都拥有 E。反证：设任期 U > T 的 Leader L 没有 E。①L 当选需多数派选票，记投票集合 Q_vote；②E 被提交意味着它存在于多数派集合 Q_commit；③两者大小之和为 2(⌊n/2⌋+1) > n，故必相交，交集中有节点 S；④S 既投了 L 又拥有 E；⑤投票规则第三条要求 S 只在”L 的日志至少和我一样新”时才投票，而 S 在 E 那个位置上的日志任期大于 L（L 在该位置要么无条目、要么任期更小）；⑥故 L 的日志不如 S 新，S 根本不会投票给 L，矛盾。∎ 这个证明只依赖两个机制：Quorum 交集（任意两个多数派必相交）+ 投票时的日志新旧比较（选举限制）。注意它保证的是”Leader 拥有全部已提交条目”，而非”日志最长”——含未提交条目的更长日志节点可能输选，这是安全的，但未提交的写在 Leader 崩溃时会被静默丢弃，客户端因此必须靠幂等处理”写入结果未知”这一边界。另外 Raft 只需持久化 currentTerm、votedFor、log 三项，commitIndex / lastApplied 可由 Leader 重新告知。
3→5 双主：旧配置多数派 = 2，新配置多数派 = 3，而 {1,2} 与 {3,4,5} 是两个不相交的合法多数派，各自都能选出 Leader；由于无法让所有节点”同时”切换配置，中间窗口必然存在，且”一任期一票”救不了——因为多数派是按本地配置计算的。Joint Consensus：引入中间配置 C_old,new（新旧并集），在该配置下选举与提交都必须同时拿到 C_old 的多数派和 C_new 的多数派（双重多数派）；C_old,new 一旦提交，就没有任何节点还能单独用 C_old 做决定，于是可安全写入并切到 C_new。它支持一次增减多个节点、全程不停机、变更期间继续服务，代价是复杂（实践上还要用 Learner 先让新节点追数据再投票，避免拖慢多数派）。单节点变更：n→n+1 时，旧多数派 ⌊n/2⌋+1 与新多数派 ⌊(n+1)/2⌋+1 之和 > n+1，故任意两个多数派必相交（n=3→4 为 2+3=5>4；n=4→5 为 3+3=6>5），再结合”一任一期一票”，每任期最多一个 Leader，双主不可能；减一节点的情形同理。实现细节：配置条目追加即生效（否则形成鸡生蛋）、必须串行变更、Leader 移除自己前要先 Transfer Leadership；历史上该简化方案关于旧任期 Leader 的边界问题曾被社区修正——这也是”不要自己实现共识”的注脚。
崩溃容错：节点只会沉默不会撒谎，n = 2f+1，Quorum = f+1，两个 Quorum 交集 = 2(f+1) − (2f+1) = 1，这 1 个节点没崩溃、说的都是真话，足以传递”我见过值 v”。拜占庭容错：恶意节点会投假票，n = 3f+1，Quorum 必须取 2f+1（因为 f 个可能沉默，必须能在只收到 n−f 个回复时就决策），两个 Quorum 交集 = 2(2f+1) − (3f+1) = f+1，其中最多 f 个恶意，故至少 1 个诚实，它能如实传递已决定的值。等价表述：要求诚实票数 > 恶意票数，即 n − 2f > f ⇒ n ≥ 3f+1。直观上崩溃节点”不投票”、恶意节点”投假票”，所以需要多出来的人数把假票淹没；经典反例是 3 将军 1 叛徒无解（Lamport 1982）。PBFT 需要三阶段（pre-prepare / prepare / commit）而崩溃容错只要两阶段，是因为要保证共同知识：prepare 只让”我”知道有 2f+1 个节点同意了某排序，若此时视图切换，新 Primary 可能完全看不到这个决定而重新分配序号造成分叉；commit 保证”有 2f+1 个节点都知道有 2f+1 个节点同意了”，于是新 Primary 从任意 2f+1 个节点收集信息时，交集中那个诚实节点一定能说出本视图 prepared 的最高序号。代价是 O(n²) 消息 + 签名开销 + 复杂的 view change；且它安全性不依赖时序、活性才依赖部分同步。
因为共识只保证”锁的归属顺序一致”，无法保证持锁者在持锁期间不”发疯”：客户端 A 拿到锁后发生长时间 STW GC（或网络暂停、进程被挂起），锁因租约超时自动释放，B 拿到锁开始写，A 醒来后以为自己仍持锁继续写——两个客户端同时写，数据损坏。这里锁服务没有任何 bug，问题出在客户端无法感知时间已经流逝。解法是 Fencing Token：锁服务每次授予锁时返回一个单调递增的令牌（etcd 的 revision 天然满足），客户端每次写共享资源都带上它，而共享资源端必须校验令牌，拒绝任何小于自己已见最大令牌的写。安全性的最终防线不在锁服务，而在被保护的资源本身——如果存储不支持条件写入（CAS / test-and-set），那么无论用 etcd、ZooKeeper 还是 Redis 做锁都不可靠。
Spanner 并没有让写变快：每次写仍要跨副本 Paxos 往返、跨分片 2PC、再加约 2ε 的 Commit Wait，跨洲事务提交延迟是几十毫秒量级。它真正打破的是”读也必须付这个代价”的直觉：有了 TrueTime 给出的严格误差上界（典型 ε 约 1~7ms），副本可在本地直接回答”给我 t 时刻的快照”（只要其 safe time 已覆盖 t 且 TT.after(t) 成立），只读事务无需加锁、无需跨洲通信、不阻塞写。机制上：每个 tablet 一个独立 Paxos 组（而非全库一组），跨分片用 2PC 且参与者是各组的 Leader，从而消除 2PC 协调者单点；提交时间戳取 TT.now().latest 并等待 TT.after(s) 成立才生效，由此保证外部一致性（因果序）。代价与边界：①TrueTime 依赖 Google 专属的 GPS + 原子钟硬件，其他公司的替代方案是 HLC + 不确定性区间重启（CockroachDB）或中心化 TSO（TiDB），代价形态不同；②ε 暴涨时 Spanner 会延长等待甚至拒绝服务，用可用性换正确性，又一次 CAP 取舍；③它返回的是区间而非时间点——“承认不确定性并给出严格上界”才是精髓。
共识不解决：①应用层逻辑错误（它会忠实地把 bug 复制到每个副本，语义校验永远在应用层）；②性能与容量（加节点只会更慢，扩容要靠分片而非扩大共识组，最优规模是 3 或 5）；③拜占庭故障（需 BFT，代价 3f+1 与 O(n²)）；④永远可用（CP 系统，分区时少数派完全不可用）；⑤延迟（它本身就是延迟来源，批处理/流水线只提升吞吐、不降单条延迟）；⑥时间（共识给的是全序不是时钟，要时钟就得 NTP / HLC / TSO / TrueTime）；⑦读一致性（直接读本地会 stale，需 ReadIndex 或 Lease Read）；⑧”客户端不知道刚才那笔写成功没有”（这是幂等与重试的地盘）。决策框架三问：①我需要全序吗（顺序会影响正确性才需要，如余额、库存、锁归属；点赞 / PV / 日志收集不需要）；②出错代价可逆吗（不可逆——如双主写坏数据、重复转账——才用共识；能靠对账 / 重算 / 幂等修正的就别用）；③数据量多大（元数据级 OK，GB/TB 级必须分片 + 最终一致）。替代清单（都比共识便宜几个数量级）：幂等 + 重试、数据库唯一约束、乐观锁 / CAS、收拢成单写入者、最终一致 + 对账、CRDT、定时对账兜底。三条铁律：共识组规模取 3 或 5（偶数不增加容错，纯属浪费）；优先”共识即服务”（etcd / ZK / Consul）而非内嵌库；架构评审固定问”为什么需要线性一致，不用会怎样”——答”听起来更可靠”则驳回，答”选错主会导致数据物理损坏且无法对账”则批准。

徐术挺-漫思录

探索

12-共识