Raft 实现拆解：etcd 的共识算法到底长什么样

Raft 论文写得很清楚。Leader election、log replication、safety proof，18 页纸讲得明明白白。你读完觉得自己理解了共识算法。

然后你去看 etcd 的 raft 库。15000 行 Go。一个 Step() 函数几百行 switch-case。PreVote、LeaderTransfer、ReadIndex、ConfChangeV2、流水线复制、快照传输、Learner 节点。论文里一句话带过的东西，代码里是几百行的状态机。

论文告诉你”什么是对的”。工程告诉你”对的东西要多少代码才能不出错”。

这篇文章不重复论文内容。我假设你读过 Raft 论文（没读过先去读，不长）。我只讲论文和 etcd 实现之间的差距。

一、Leader Election：论文说的和没说的

论文版本

Follower 超时 -> 变 Candidate -> 给自己投票 -> 向所有节点发 RequestVote -> 拿到多数票就当 Leader。简单直接。

etcd 的问题

问题一：网络分区恢复后的选举风暴

假设一个 5 节点集群，节点 E 被网络隔离了。E 不断超时，不断自增 term，发起选举。没人理它，因为网络不通。

分区恢复的瞬间，E 的 term 已经远大于 Leader 的 term。E 发出的 RequestVote 会让当前 Leader step down（因为 term 更高），但 E 的 log 又不够新，选不上。结果：集群短暂不可用，需要重新选举。

etcd 的解法：PreVote

// raft.go: Step() 函数中处理 MsgPreVote
case pb.MsgPreVote:
    // PreVote 不增加 term，不会打断现有 Leader
    // 只有当发起者的 log 至少和接收者一样新时才回复 grant
    if r.lead != None && r.electionElapsed < r.electionTimeout {
        // 我还能正常收到 Leader 心跳，拒绝 PreVote
        return nil
    }
    // ... 检查 log 是否足够新 ...

PreVote 是两阶段选举。第一阶段（PreVote）不增加 term，只检查”如果我发起选举，能不能拿到多数票”。只有 PreVote 通过了，才真正增加 term 发起 Vote。

这意味着被隔离的节点恢复后，它的 PreVote 会被拒绝（因为集群有正常工作的 Leader），它不会打断现有 Leader。

论文里没有 PreVote。这是 etcd 贡献给 Raft 生态的核心改进之一。

问题二：Leader Transfer

有时候你需要主动迁移 Leader（比如要维护当前 Leader 节点）。论文没提这个。

etcd 的做法：Leader 停止接受新提案，先把目标节点的 log 追平，然后给目标节点发一个 MsgTimeoutNow。目标节点收到后立刻发起选举（跳过 election timeout），并且因为它的 log 是最新的，所以一定能赢。

func (r *raft) sendTimeoutNow(to uint64) {
    r.send(pb.Message{To: to, Type: pb.MsgTimeoutNow})
}

整个 Leader Transfer 在 etcd 里大约 50 行代码。逻辑不复杂，但论文没告诉你需要这个。

二、Log Replication：从正确到高效

论文版本

Leader 维护每个 Follower 的 nextIndex 和 matchIndex。发 AppendEntries，等多数确认，commit。如果 Follower 的 log 和 Leader 不一致，回退 nextIndex 直到找到一致点。

这个描述完全正确。但如果你原样实现，性能很差。

etcd 的优化

流水线复制（Pipeline）

论文的模型是同步的：发 AppendEntries -> 等回复 -> 发下一批。实际实现中，如果 Follower 正常跟上（状态是 StateReplicate），etcd 不等回复就继续发：

// progress.go
type Progress struct {
    State ProgressStateType  // Probe, Replicate, Snapshot

    // Replicate 模式下用 inflight 窗口控制
    Inflights *Inflights     // 滑动窗口，限制未确认的消息数量
    // ...
}

const maxInflightMsgs = 256  // 默认最大 256 条未确认消息

Inflights 是一个固定大小的滑动窗口。Leader 对每个处于 StateReplicate 的 Follower 持续发送 AppendEntries，直到 inflight 窗口满。收到 ACK 后窗口向前滑动。

这把复制的吞吐量从”一个 RTT 一批”变成了”窗口大小 / RTT”，和 TCP 的滑动窗口是一个思路。

Probe vs Replicate 状态机

当 Follower 刚恢复，Leader 不知道它的 log 状态。此时 Follower 处于 StateProbe：Leader 每发一条 AppendEntries 就等一条回复，收到拒绝就回退 nextIndex。

一旦确认了 matchIndex（收到第一个成功回复），切换到 StateReplicate，开始流水线模式。

如果 Follower 的 log 落后太多（差距超过 snapshot 阈值），切换到 StateSnapshot：发快照而不是逐条补日志。

                    +-- 成功 ACK ---> StateReplicate (流水线)
                    |
StateProbe ---------+
                    |
                    +-- 落后太多 ---> StateSnapshot
                                         |
                                         +-- 快照完成 -> StateProbe

论文只有”正常复制”和”快照”两种情况。etcd 加了 Probe 作为中间状态，避免了在 Follower 状态未知时浪费带宽。

Batching

etcd 的 Ready() 结构体把多个状态变更打包返回给应用层：

type Ready struct {
    SoftState    *SoftState
    HardState    pb.HardState      // 需要持久化的状态
    Entries      []pb.Entry         // 需要持久化的日志
    Snapshot     pb.Snapshot
    CommittedEntries []pb.Entry     // 可以 apply 的日志
    Messages     []pb.Message       // 需要发送的网络消息
}

应用层处理一个 Ready 的流程： 1. 写 WAL（持久化 HardState + Entries） 2. 发送 Messages 3. Apply CommittedEntries 到状态机 4. 调用 Advance() 告诉 raft 库可以产生下一个 Ready

这个设计把 raft 库和 I/O 完全解耦。raft 库本身不做网络通信、不做磁盘 I/O，所有 I/O 由应用层决定。这使得同一个 raft 库可以跑在不同的存储引擎和网络栈上。

三、Configuration Change：最容易出错的部分

论文的 Section 6 用了不到一页讲 configuration change。它提出了一个方案：joint consensus，新旧配置同时生效，通过两阶段切换保证安全。

etcd 最初没实现 joint consensus。它用的是单步变更（one-at-a-time）：每次只添加或删除一个节点。这在大多数情况下是安全的，但有一个微妙的 bug：

单步变更的边界条件

假设集群从 3 节点扩展到 5 节点。如果你连续快速添加两个节点（还没等第一个 ConfChange 被 commit），新旧配置的多数派可能不重叠，violating safety。

etcd 的解法：ConfChange 本身也是 raft log 的一个 entry，必须被 commit 之后才能应用。在 ConfChange entry 被 commit 之前，Leader 拒绝接受新的 ConfChange。

// 简化的检查逻辑
func (r *raft) addNode(id uint64) {
    if r.pendingConfIndex > r.raftLog.applied {
        // 上一个 ConfChange 还没 apply，拒绝
        return
    }
    // ... 执行变更 ...
}

这个”一次只变一个”的约束，在实践中覆盖了 99% 的场景。但 etcd 后来还是实现了 joint consensus（ConfChangeV2），用于需要同时变更多个节点的场景（比如替换节点：同时移除旧节点、添加新节点）。

Learner 节点

另一个论文没提的东西。当你添加一个新节点时，它的 log 是空的。在它追上集群进度之前，它会拖慢 commit（因为多数派确认需要等它）。

etcd 的解决方案：先把新节点加为 Learner（不参与投票，不影响多数派），等它追上 log 之后再 promote 为正式 Voter。

type ConfChange struct {
    Type    ConfChangeType  // AddNode, RemoveNode, AddLearnerNode
    NodeID  uint64
    // ...
}

四、Linearizable Read：不走 log 的读

Raft 保证的是写的线性一致性。读呢？

最简单的做法：读也走 raft log。发一个空的 Propose，等它 commit 之后再读状态机。线性一致，但开销巨大——每次读都要一轮共识。

ReadIndex

etcd 实现了 ReadIndex 优化：

1. Leader 记录当前 commit index 为 readIndex
2. Leader 向所有 Follower 发送心跳，确认自己仍然是 Leader
3. 收到多数心跳回复后，等状态机 apply 到 readIndex
4. 执行读操作

func (r *raft) handleReadIndex(m pb.Message) {
    if r.raftLog.committed < r.raftLog.applied {
        return // 状态机还没追上
    }
    r.readStates = append(r.readStates, ReadState{
        Index:      r.raftLog.committed,
        RequestCtx: m.Entries[0].Data,
    })
    // 发心跳确认 leadership
    r.bcastHeartbeatWithCtx(m.Entries[0].Data)
}

这避免了写 log 的开销，但仍然需要一轮心跳往返（确认 Leadership）。在延迟敏感场景下，这个往返也有代价。

LeaseRead

更激进的优化：如果 Leader 刚收到过多数节点的心跳确认（在 election timeout 以内），直接读，不再发心跳。

代价：依赖时钟。如果机器的时钟漂移超过 election timeout，可能读到过期数据。在物理机上通常没问题，在 VM 里时钟漂移是真实风险。

etcd 默认用 ReadIndex，不用 LeaseRead。正确性优先。

五、为什么读论文不够

把上面的差距列成表：

论文的 18 页是正确的。但工程需要处理的不是”正确”——而是”在真实网络、真实磁盘、真实运维操作下持续正确”。

每一行 etcd 的代码背后，都有一个论文里没提到的 edge case。PreVote 来自 Diego Ongaro 的博士论文的第 9.6 节，不在原始 Raft 论文里。ReadIndex 是 etcd 社区自己想出来的。流水线复制是任何做过分布式复制的工程师都会做的优化，但论文不需要提它，因为论文的目标是证明正确性，不是追求性能。

如果你想理解 Raft，读论文。如果你想实现 Raft，读 etcd 源码。两者之间的差距，就是分布式系统工程的本质。

延伸阅读：

• SQLite 是怎么做到”十亿行每秒”的 – 另一个”正确性先于性能”的工程典范
• 大多数”无锁”代码其实不是无锁的 – 正确性证明和工程实现之间的鸿沟

参考资料：

1. Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC. – 原始 Raft 论文
2. Ongaro, D. (2014). Consensus: Bridging Theory and Practice. Stanford PhD Dissertation. – 包含 PreVote 等扩展
3. etcd/raft – etcd 的 Raft 实现，Go 语言
4. TiKV raft-rs – etcd/raft 的 Rust 移植，由 PingCAP 维护