Raft：让共识算法不再是黑魔法

Leslie Lamport 在 1990 年提交了 Paxos 论文。审稿人看不懂，退回。1998 年他换了种写法重新发，审稿人还是看不太懂。2001 年他又写了一篇《Paxos Made Simple》，开头第一句话是：“The Paxos algorithm, when presented in plain English, is very simple.” 讽刺的是，这篇”很简单”的论文至今仍是分布式系统课程里最令人头疼的阅读材料之一。

Paxos 被引用了几千次。能正确实现它的人，可能不超过几十个。

2014 年，Diego Ongaro 和 John Ousterhout 发表了 Raft。它解决的问题和 Paxos 一模一样——管理复制日志的共识算法。但设计目标完全不同：可理解性优先。不是比 Paxos 更正确，不是比 Paxos 更快，而是让普通工程师也能读懂、能实现、能调试。

结果是：Raft 论文发表十年后，etcd、TiKV、CockroachDB、Consul、RethinkDB……大半个云原生基础设施的共识层都建立在 Raft 或其变体之上。不是因为 Raft 在理论上比 Paxos 更好，而是因为人能理解它，就能正确实现它。

一、共识问题：我们到底在解决什么

假设你有一个服务存储了关键状态（配置、锁、元数据）。单机部署，机器一挂，状态就没了。自然的想法是搞多台机器存多份副本。

问题是：多个副本怎么保证一致？

客户端发了一个写请求，Leader 收到了，它需要把这个操作同步给所有副本。但网络会丢包、会乱序，节点会宕机、会重启。怎么保证所有活着的节点最终看到同一份数据，同一个顺序？

这就是复制状态机（Replicated State Machine）模型：

所有节点维护同一份有序日志。只要日志顺序一致，每个节点按顺序应用日志到自己的状态机，最终状态就一致。

共识算法要保证两件事：

• Safety（安全性）：永远不返回错误的结果。不会有两个节点在同一个位置 apply 了不同的命令。
• Liveness（活性）：只要多数节点还活着且能通信，系统最终能响应请求。

FLP 不可能定理告诉我们：在完全异步的网络中，即使只有一个节点可能崩溃，也不存在一个确定性算法能同时保证 Safety 和 Liveness。Raft 的工程回答是：用随机化超时打破对称性，在实践中让 Liveness 几乎总是成立。

二、Raft 怎么拆问题

Paxos 的一个大问题是它把所有东西混在一起。对一个值达成共识的是 single-decree Paxos，对一系列值达成共识的是 Multi-Paxos，但 Lamport 从没写过 Multi-Paxos 的完整协议。日志怎么管、Leader 怎么选、成员怎么变更——你自己想办法。

Raft 明确把共识问题分解成三个相对独立的子问题：

1. Leader Election（选举）：谁来做主？
2. Log Replication（日志复制）：Leader 怎么把决定同步给所有人？
3. Safety（安全性）：怎么保证换了 Leader 之后不丢数据、不出错？

在讲这三个子问题之前，先定义几个贯穿全文的核心概念。

Term（任期）

Raft 的逻辑时钟。整数，单调递增。每次新一轮选举开始，term 加 1。每个 term 内至多一个 Leader。

如果一个节点收到了比自己 term 更高的消息，立刻更新自己的 term 并变成 Follower。如果收到比自己 term 更低的消息，直接拒绝。

Term 是 Raft 的纪元。旧 term 的消息在新 term 里毫无权威。

三种角色

• Follower：被动角色。只响应 Leader 和 Candidate 的请求。如果一段时间没收到心跳，变 Candidate。
• Candidate：过渡角色。发起选举，要么赢了变 Leader，要么输了/超时回 Follower。
• Leader：处理所有客户端请求。向 Follower 复制日志，周期性发心跳维持权威。

一个集群在任何时刻最多只有一个合法 Leader。这是 Raft 最重要的不变量之一。

三、Leader Election：谁来做主

选举怎么触发

每个 Follower 维护一个 election timeout。这个超时是从一个范围内（比如 150ms ~ 300ms）随机选的。

如果 Follower 在 election timeout 内没收到 Leader 的心跳（AppendEntries RPC），它认为 Leader 挂了，自己变成 Candidate 发起选举。

随机化是关键。 如果所有节点用同一个超时值，Leader 挂了之后所有 Follower 同时发起选举，谁也拿不到多数票，死循环。随机化让某个节点大概率先超时，先发起选举，先拿到票。

选举流程

function startElection():
  currentTerm += 1
  votedFor = self
  votesReceived = {self}

  for each node in cluster (except self):
  send RequestVote(term  = currentTerm,
  candidateId  = self,
  lastLogIndex = log.lastIndex(),
  lastLogTerm  = log.lastTerm()) to node

Candidate 给自己投一票，然后并行向所有其他节点发送 RequestVote RPC。

之后有三种结局：

赢了：收到了多数节点（包括自己）的投票。变成 Leader，立刻向所有节点发心跳（空的 AppendEntries），宣告权威并阻止新的选举。

输了：收到了来自合法 Leader 的 AppendEntries（term ≥ 自己的 term）。说明已经有 Leader 了，自己变回 Follower。

平（Split Vote）：超时了还没拿到多数票。重置 election timeout（再次随机化），重新来一轮。

投票规则

收到 RequestVote 的节点按以下规则决定是否投票：

function handleRequestVote(request):
  if request.term < currentTerm:
  return reject  # 过期的 term，直接拒绝

  if request.term > currentTerm:
  currentTerm = request.term
  state = Follower
  votedFor = null

  # 每个 term 只投一票
  if votedFor != null and votedFor != request.candidateId:
  return reject

  # 候选人的日志必须"至少和自己一样新"
  if not isLogUpToDate(request.lastLogIndex, request.lastLogTerm):
  return reject

  votedFor = request.candidateId
  reset election timeout
  return grant

两个关键约束：

1. 每个 term 只投一票。防止同一个 term 内出现两个 Leader。
2. 候选人的日志必须至少和投票者一样新。这是 Safety 的核心保障，后面详细说。

一次成功的选举

以三节点集群（S1、S2、S3）为例，当前 term=1，S1 是 Leader：

整个过程的延迟 ≈ 一个 election timeout + 一个 RTT。在局域网环境下通常在几百毫秒内完成。

Split Vote

五节点集群，S1 宕机。S2 和 S3 几乎同时超时，同时发起选举：

S2 (Candidate, term=2): 投自己, 拿到 S4 的票  → 2 票
S3 (Candidate, term=2): 投自己, 拿到 S5 的票  → 2 票
  都没到 3 票多数 → 超时

S2: 重新随机 timeout = 210ms
S3: 重新随机 timeout = 280ms
  S2 先超时 → term=3 → 发 RequestVote → 拿到 S3/S4/S5 的票 → 当选

随机化超时使得 split vote 在实践中几乎只持续一轮。Raft 论文的实验数据显示，用 150~300ms 的随机范围，选举通常在一个 election timeout 周期内完成。

四、Log Replication：怎么把决定同步给所有人

日志的结构

每条日志 entry 包含三个东西：

• index：在日志中的位置（从 1 开始，连续递增）
• term：这条 entry 被创建时的 Leader 任期
• command：要应用到状态机的操作

commitIndex 标记了已经安全提交的最新位置。index ≤ commitIndex 的 entry 可以安全地 apply 到状态机。

正常的复制流程

function handleClientRequest(command):
  # 1. 追加到自己的日志
  entry = Entry(term=currentTerm, index=log.nextIndex(), command=command)
  log.append(entry)

  # 2. 并行发给所有 Follower
  for each follower in cluster:
  send AppendEntries(term  = currentTerm,
  leaderId  = self,
  prevLogIndex = nextIndex[follower] - 1,
  prevLogTerm  = log[prevLogIndex].term,
  entries  = log[nextIndex[follower] .. ],
  leaderCommit = commitIndex) to follower

  # 3. 多数确认后 commit
  # （在收到回复的回调中处理）

Leader 收到客户端请求后，先写本地日志，然后并行发 AppendEntries RPC 给所有 Follower。当多数节点（包括 Leader 自己）都确认写入成功后，这条 entry 就被 commit 了。Leader 更新 commitIndex，然后把 entry apply 到状态机，回复客户端。

Follower 通过 AppendEntries 中的 leaderCommit 字段知道哪些 entry 已经被 commit 了，自行 apply。

一致性检查：prevLogIndex 和 prevLogTerm

AppendEntries 中有两个关键字段：prevLogIndex 和 prevLogTerm。它们标识了”新 entry 紧接在哪条旧 entry 后面”。

function handleAppendEntries(request):
  if request.term < currentTerm:
  return reject

  # 一致性检查
  if log[request.prevLogIndex].term != request.prevLogTerm:
  return reject  # 在 prevLogIndex 位置的 entry 的 term 不匹配

  # 检查通过，追加新 entry（覆盖冲突的旧 entry）
  log.appendFrom(request.prevLogIndex + 1, request.entries)

  # 更新自己的 commitIndex
  if request.leaderCommit > commitIndex:
  commitIndex = min(request.leaderCommit, log.lastIndex())

  return success

这个检查实现了 Raft 的 Log Matching Property：

如果两个节点的日志在某个 index 上有相同的 term，那么它们在这个 index 及之前的所有 entry 都完全相同。

归纳法证明：每次 AppendEntries 成功，都确认了 prevLogIndex 位置的一致性。而 prevLogIndex 的一致性又是上一次 AppendEntries 成功确认的。一直递推到日志的开头。

不一致怎么修复

正常运行时所有节点的日志是一致的。但 Leader 崩溃可能导致日志不一致。比如：

S2 只是落后了，补上就行。S3 更麻烦：index 4 开始和 Leader 不一样（term=2 而非 term=3），是旧 Leader 时期写下但未被 commit 的 entry。

Leader 对每个 Follower 维护一个 nextIndex（下次发送的起始 index）。初始值是 Leader 日志最后一条的下一个 index。

修复流程：

Leader → S3: AppendEntries(prevLogIndex=6, prevLogTerm=t3, entries=[7])
  S3: log[6].term = t2 ≠ t3 → reject

Leader: nextIndex[S3] -= 1  (回退到 6)
Leader → S3: AppendEntries(prevLogIndex=5, prevLogTerm=t3, entries=[6,7])
  S3: log[5].term = t2 ≠ t3 → reject

Leader: nextIndex[S3] -= 1  (回退到 5)
...（继续回退）...

Leader → S3: AppendEntries(prevLogIndex=3, prevLogTerm=t2, entries=[4,5,6,7])
  S3: log[3].term = t2 == t2 → success!
  S3 用 Leader 的 entries 覆盖 index 4-7

Leader 靠逐步回退 nextIndex，找到两份日志的最后一个一致点，然后从这个点开始把自己的日志覆盖过去。Follower 的冲突 entry 被无条件丢弃。

这个逻辑的核心假设是：Leader 的日志永远是权威的。 Follower 上任何和 Leader 冲突的 entry 都是未被 commit 的残留数据，可以安全丢弃。这个假设为什么成立？答案在 Safety 部分。

优化：逐条回退在日志差距很大时效率低。实际实现中 Follower 可以在 reject 回复中附带冲突 term 和该 term 的第一个 index，让 Leader 一次跳过整个 term，大幅减少回退轮数。

最关键的 commit 规则：Figure 8

这是 Raft 论文最精妙也最容易被忽略的地方。

一个 Leader 不能通过计数副本数来 commit 旧 term 的日志 entry。 只有当前 term 的 entry 才能通过多数确认直接 commit。旧 term 的 entry 只能被间接 commit——当一条新 term 的 entry 被 commit 时，在它之前的所有 entry 自动被 commit。

为什么？看这个场景（改编自论文 Figure 8）：

阶段 1-3 的关键：S1 在 term=2 写了一条 entry 到 index=2，只复制到了 S2。S1 宕机后 S5 当选 term=3 Leader，在 index=2 写了自己的 entry。S5 也宕机。S1 恢复后当选 term=4 Leader，把 index=2 (t2) 复制到了 S3——此时 t2 已在 S1/S2/S3 三个节点上，看起来是多数。

阶段 4a（灾难）：如果 S1 直接把 index=2 (t2) 标记为 committed，然后宕机——S5 恢复后能当选（它的 lastLogTerm=3 > 其它节点在 index=2 的 term=2），然后用自己的 t3 覆盖掉所有节点的 index=2。已 commit 的数据丢失。

阶段 4b（正确做法）：S1 不直接 commit 旧 term 的 entry，而是先在 index=3 追加一条 term=4 的 entry 并复制到多数。index=3 (t4) commit 后，index=2 (t2) 被间接 commit。此时 S5 即使恢复也选不上——S1/S2/S3 的 lastLogTerm=4 > S5 的 3。

这条规则是 Raft Safety 的基石。没了它，已 commit 的数据可能丢失。

五、Safety：怎么保证不丢数据

Raft 需要保证一个核心性质：Leader Completeness Property。

如果一条 entry 在某个 term 被 commit 了，那么所有更高 term 的 Leader 的日志中都包含这条 entry。

换句话说：新 Leader 的日志一定包含所有已 commit 的 entry。 否则新 Leader 会用自己的日志覆盖 Follower，已 commit 的数据就丢了。

Election Restriction

Raft 通过投票规则来保证这一点。还记得 RequestVote 中 Candidate 要带上自己的 lastLogIndex 和 lastLogTerm 吗？投票者用这个判断候选人的日志是否”至少和自己一样新”：

function isLogUpToDate(candidateLastIndex, candidateLastTerm):
  myLastTerm = log.lastTerm()
  myLastIndex = log.lastIndex()

  # 先比最后一条 entry 的 term
  if candidateLastTerm != myLastTerm:
  return candidateLastTerm > myLastTerm

  # term 相同，比日志长度
  return candidateLastIndex >= myLastIndex

规则很简单：先比 term，term 大的更新。term 相同，比 index，长的更新。

如果候选人的日志不够新，投票者拒绝投票。这意味着一个 Candidate 必须拿到多数票才能当选，而所有已 commit 的 entry 至少存在于多数节点上。两个多数必有交集——交集中的那个节点既有已 commit 的 entry，又要给候选人投票。如果候选人缺少这条 entry，这个节点就不会给它投票。

这就是 Election Restriction 的核心直觉：两个多数派的交集确保了已 commit 数据的传递。

State Machine Safety

有了 Leader Completeness，State Machine Safety 就自然成立了：

如果一个节点在某个 index 应用了一条 entry 到状态机，那么其他任何节点在同一个 index 不会应用不同的 entry。

证明链条： 1. 一条 entry 被 commit → 它在所有后续 Leader 的日志中都存在（Leader Completeness） 2. Leader 的日志是权威的 → Follower 的日志最终会和 Leader 一致（Log Matching Property + 不一致修复） 3. 所有节点在同一个 index 看到同一条 entry → apply 同一个 command → 状态一致

三个性质环环相扣，共同构成了 Raft 正确性的完整证明。

六、日志压缩与快照

日志不能无限增长。一个运行了几个月的集群可能有数百万条日志 entry。全量存储浪费空间，新加入的节点要从头重放效率极低。

Snapshot（快照）

每个节点独立决定何时做快照（不需要 Leader 协调）。快照包含：

• lastIncludedIndex：快照覆盖的最后一条 entry 的 index
• lastIncludedTerm：该 entry 的 term
• 状态机的完整状态

做完快照后，lastIncludedIndex 之前的所有日志 entry 可以丢弃。

InstallSnapshot RPC

当一个 Follower 落后太多——它需要的日志 entry 已经被 Leader 做快照丢弃了——Leader 就不能通过正常的 AppendEntries 来补日志，而是直接发送整个快照：

Leader → slow Follower:
  InstallSnapshot(term  = currentTerm,
  leaderId  = self,
  lastIncludedIndex = snapshot.lastIndex,
  lastIncludedTerm  = snapshot.lastTerm,
  data  = snapshot.bytes  # 状态机的完整二进制数据)

Follower:
  1. 如果 snapshot 覆盖了自己的部分日志 → 保留快照之后的 entry
  2. 如果 snapshot 覆盖了自己的全部日志 → 丢弃全部日志
  3. 加载 snapshot 到状态机
  4. 后续通过正常 AppendEntries 追赶剩余日志

快照的代价是传输量大（完整的状态机序列化）。但这是极端情况——只有当 Follower 长时间宕机或新节点刚加入集群时才需要。在正常运行中，增量的 AppendEntries 就够了。

七、Raft vs Paxos

Raft 不是凭空发明的新算法。它本质上是 Multi-Paxos 的一个具体化、规范化的工程协议。差异在设计约束上：

Raft 的代价：

• 强 Leader 意味着 Leader 是性能瓶颈。 所有读写都经过 Leader，Leader 的网络带宽和 CPU 是整个集群的天花板。
• Leader 挂了必须重新选举。 选举期间集群不可用（通常几百毫秒，但在网络抖动时可能更长）。
• 日志连续性限制了并发。 Paxos 允许对不同 slot 并行达成共识，Raft 的日志顺序是串行的。

但 Raft 的收益更大：如果工程师理解不了算法，那算法再优秀也没用。 Ongaro 在论文中做了用户实验：33 个斯坦福和华盛顿大学的学生分别学习 Raft 和 Paxos，然后回答同等难度的测试。结果 Raft 的测试成绩显著优于 Paxos，学生自评”理解程度”也更高。

可理解性不是学术美德。可理解性是工程可靠性的前提条件。

八、总结

把 Raft 的核心机制收拢成一张表：

Raft 论文 18 页。核心思想三句话就能说完：选一个 Leader，Leader 把日志复制给多数节点，用投票规则保证新 Leader 一定有所有已 commit 的数据。

难的从来不是理解这三句话。难的是在真实的网络延迟、磁盘故障、节点宕机、时钟漂移面前，让这三句话持续成立。 论文解决了正确性。把正确性变成能跑的代码，是工程师的事。

如果你想知道工程师是怎么做的——etcd 的 15000 行 Go 代码里藏着论文没写的所有答案：PreVote、流水线复制、ReadIndex、Learner 节点。这些在 Raft 实现拆解：etcd 的共识算法到底长什么样 里详细讲。

Raft 论文的伟大不在于它证明了什么新定理——而在于它证明了共识算法不需要是黑魔法。

延伸阅读：

• Raft 实现拆解：etcd 的共识算法到底长什么样 —— 论文和 etcd 源码之间的差距
• CAP 定理再审视：从理论误区到工程实践 —— 分布式系统不可能三角的真实含义

参考资料：

1. Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC.
2. Ongaro, D. (2014). Consensus: Bridging Theory and Practice. Stanford PhD Dissertation.
3. Lamport, L. (2001). Paxos Made Simple.
4. raft.github.io —— Raft 可视化，强烈推荐对着它走一遍选举和日志复制流程
5. etcd/raft —— etcd 的 Raft 实现，Go 语言