Raft 共识算法实现深入

Paxos 以简洁的数学原理著称，却因难以工程化而劝退无数实现者。Raft 是 Diego Ongaro 为了可理解性重新设计的共识算法：它把共识问题拆解为领导人选举、日志复制、安全性、成员变更四个独立子问题，让每个子问题都可以被直接理解和正确实现。本文从复制状态机讲起，逐层深入到 Raft 的完整实现与测试方法。

一句话：Raft 不是新共识理论，而是把 Paxos 的核心思想用一种工程师可实现的形态表达出来。

1. 从复制状态机说起

1.1 复制状态机模型

共识算法的目标不是"让多台机器达成一致"这么抽象，而是构建复制状态机（Replicated State Machine）：

Client ──► 共识模块（日志复制）──► 各节点状态机按相同顺序执行
                                   ┌─► State Machine A
                                   ├─► State Machine B
                                   └─► State Machine C
      只要日志顺序一致，状态机执行结果就一致

日志是一串有序条目，每个条目包含任期（term）、索引（index）和命令（command）。只要各节点以相同顺序应用日志，状态机就收敛到相同状态。

1.2 三种角色与状态

每个节点任一时刻处于三种角色之一：

// 节点持久化状态（必须落盘）
type PersistentState struct {
    CurrentTerm int       // 当前任期
    VotedFor    int       // 本任期投给谁，-1 表示未投
    Log         []Entry   // 日志条目
}

// 节点易失状态
type VolatileState struct {
    CommitIndex int       // 已提交的最大索引
    LastApplied int       // 已应用到状态机的最大索引
}

1.3 任期（Term）

时间被划分为任期，每个任期从一次选举开始。任期是一个单调递增的逻辑时钟，也是 Raft 正确性的基石：

• RPC 请求中总是携带发送方的 term
• 接收方发现请求任期更高，立即转为 Follower 并更新自己的任期
• 接收方发现请求任期更低，直接拒绝

一句话：任期让网络分区、消息乱序、陈旧 Leader 都变得可判定——永远听任期更高的人。

2. 领导人选举

2.1 选举超时与随机化

Follower 在 [T, 2T]（典型 T=150ms）内没有收到 Leader 心跳，就自增任期并转成 Candidate 发起选举。随机化超时是避免"选票分裂"的关键：多个候选人不至于同时过期、同时互投。

func (n *Node) resetElectionTimer() {
    // 随机化选举超时，避免候选人间互相干扰
    timeout := baseElectionTimeout + time.Duration(rand.Intn(extra)) * time.Millisecond
    n.electionDeadline = time.Now().Add(timeout)
}

2.2 选举过程

Candidate 发出 RequestVote，携带 lastLogIndex 与 lastLogTerm 用于"选举限制"判定：

Candidate ──RequestVote(term, candidateId, lastLogIndex, lastLogTerm)──► 其他节点
   ◄── VoteGranted / Reject ──
获得多数票（含自己）→ 成为 Leader，广播空 AppendEntries（心跳）

// RequestVote 处理：投票的前提是日志不比对方旧
func (n *Node) RequestVote(req RequestVote) VoteResponse {
    if req.Term < n.currentTerm {
        return VoteResponse{Term: n.currentTerm, Granted: false}
    }
    if req.Term > n.currentTerm {
        n.becomeFollower(req.Term)
    }
    // 任期已投票给别人 → 拒绝
    if n.votedFor != -1 && n.votedFor != req.CandidateId {
        return VoteResponse{Term: n.currentTerm, Granted: false}
    }
    // 选举限制：候选人的日志至少与本地一样新
    if n.upToDate(req.LastLogIndex, req.LastLogTerm) {
        n.votedFor = req.CandidateId
        n.persist()
        return VoteResponse{Term: n.currentTerm, Granted: true}
    }
    return VoteResponse{Term: n.currentTerm, Granted: false}
}

2.3 新 Leader 上任动作

新 Leader 立即做三件事，保证系统快速回到正常：

1. 广播心跳（空 AppendEntries），重置 Follower 的选举超时
2. 把自己的 nextIndex[] 初始化为 len(log)+1，matchIndex[] 初始化为 0
3. 提交空条目（No-op），从而间接提交上个任期遗留的已复制条目

3. 日志复制

3.1 AppendEntries 一致性检查

Leader 收到客户端命令后追加到本地日志，然后向每个 Follower 发送 AppendEntries，携带 prevLogIndex 与 prevLogTerm。Follower 做一致性检查：若本地日志在 prevLogIndex 处的任期与 prevLogTerm 不一致，就拒绝，Leader 回退 nextIndex 重试。

Leader:    [1][2][3][4][5]
Follower:  [1][2][3]          prevLogIndex=4 不匹配 → 拒绝
Leader 回退 nextIndex 到 3 重发 → [3][4][5]

func (n *Node) AppendEntries(req AppendEntries) AppendResponse {
    if req.Term < n.currentTerm {
        return AppendResponse{Term: n.currentTerm, Success: false}
    }
    if req.Term > n.currentTerm {
        n.becomeFollower(req.Term)
    }
    // 一致性检查：prevLogTerm 不匹配则拒绝
    if req.PrevLogIndex > 0 &&
        n.logTerm(req.PrevLogIndex) != req.PrevLogTerm {
        return AppendResponse{Term: n.currentTerm, Success: false}
    }
    // 冲突条目删除，追加新条目
    n.log = append(n.log[:req.PrevLogIndex], req.Entries...)
    n.persist()
    // 按 leaderCommit 更新 commitIndex
    if req.LeaderCommit > n.commitIndex {
        n.commitIndex = min(req.LeaderCommit, n.lastIndex())
    }
    return AppendResponse{Term: n.currentTerm, Success: true}
}

3.2 日志匹配性质

Raft 正确性的核心是日志匹配性质：如果两个日志在索引 i 处的任期相同，那么它们在此之前的所有条目完全相同。该性质由"任期唯一 + 一致性检查 + 冲突条目删除"共同保证。

3.3 提交规则

Leader 统计各节点 matchIndex，若某个条目被多数节点复制，且该条目是当前任期的条目，就可以提交。为什么必须是当前任期？因为上一任期的条目即使被多数复制，也无法确认是否真正会存活——必须靠当前任期的条目被提交来"间接确认"。

一句话：上一任期的日志由当前任期日志的提交来间接提交，这是 Raft 最精妙也最容易实现错的地方。

4. 安全性

4.1 选举限制

RequestVote 只投给日志"至少一样新"的候选人：比较 lastLogTerm，若相同再比较 lastLogIndex。这保证已提交的日志永远出现在新任 Leader 的日志中，杜绝"日志丢失已提交命令"。

4.2 领导权转移

候选人在 [T, 2T] 内收不到多数票就等待下一次随机超时重新选举；遇到更高任期的 RPC 立即降级为 Follower。任期内只会有一个 Leader 赢得多数票，因此每个任期至多一个 Leader。

4.3 成员变更（联合共识）

Raft 的配置变更使用联合共识（Joint Consensus），把变更拆成两个阶段：

阶段1：Leader 追加 C_old-new 条目 → 提交（需要新旧都过半数）
阶段2：Leader 追加 C_new 条目 → 提交 → 移除旧节点

联合共识解决了变更过程中"两个 Leader 同时存在"的理论风险，是生产系统必须处理的问题。

5. 持久化与快照

5.1 必须持久化的状态

只有三类状态需要落盘：currentTerm、votedFor、log[]。其余状态（commitIndex、lastApplied）可以从日志重放恢复。持久化失败时节点必须拒绝接受新日志：

func (n *Node) persist() error {
    data := encode(n.currentTerm, n.votedFor, n.log)
    return n.storage.Write(data) // 追加写 + fsync，保证崩溃后可恢复
}

5.2 日志压缩与快照

日志无限增长会导致重放时间过长、空间爆炸。Raft 用快照压缩：把"截止到某索引的状态机状态"打包成快照，丢弃该索引之前的日志。

InstallSnapshot RPC
Leader ──(snapshot, lastIncludedIndex, lastIncludedTerm)──► Follower
Follower 丢弃 lastIncludedIndex 之前的日志，替换状态机状态

type Snapshot struct {
    LastIncludedIndex int    // 快照包含的最后日志索引
    LastIncludedTerm  int    // 对应的任期
    Data              []byte // 状态机状态序列化
}

快照带来的权衡：快照频率高则磁盘占用小、恢复快，但快照本身要传网络；频率低则相反。通常以日志字节数阈值（如 10MB）触发。

5.3 只追加不修改

日志是只追加结构，唯一的修改操作是"冲突时删除未提交的尾部条目"。绝不能修改已提交的条目——任何形式的覆盖已提交日志都会破坏安全性。

6. 实现要点

6.1 并发模型

Raft 节点由多个并发源驱动：RPC 处理器、选举计时器、日志应用协程。推荐单线程事件循环或者"所有状态变更集中在持有锁的临界区"：

type Node struct {
    mu   sync.Mutex // 所有状态字段的锁
    ...
}

func (n *Node) tick() {
    n.mu.Lock()
    defer n.mu.Unlock()
    // 判断是否超时触发选举
}

把"任期判断、角色转换、日志追加"全部放进锁内，RPC 处理器与计时器共享同一把锁，可以显著降低并发 bug。

6.2 RPC 幂等与超时

Raft RPC 天然幂等：重复的 AppendEntries 只会追加相同的日志。但网络层必须处理超时重发。客户端请求超时后重试，Leader 需要识别重复请求——配合 https://plumephp.com/distributed-idempotency-reliability/ 的幂等设计。

6.3 心跳与批处理

• 心跳间隔（如 50ms）应显著小于选举超时下限（如 150ms），保证稳定 Leader 不触发选举
• 批量复制日志：一轮 AppendEntries 尽量携带更多条目，减少 RPC 次数
• 乐观更新 matchIndex：成功即更新，无需等待额外 RPC

6.4 存储层

真实系统（etcd 的 bbolt、TiKV 的 RocksDB）都要求日志写入具备持久性语义：fsync 之后再确认。批量写日志比逐条写快一个数量级。

7. 测试方法

7.1 单元测试：状态机转换

用确定性测试覆盖角色转换矩阵：Candidate 收到更高任期心跳 → Follower；Leader 收到更高任期投票 → Follower。这类测试成本低、覆盖面大。

7.2 线性一致性测试

共识实现的最终标准是线性一致性：任何操作的效果等同于按某个串行顺序执行。社区标准做法是 Jepsen 注入网络分区、进程崩溃、时钟偏移，验证不变量不破：

7.3 故障注入与混沌

把故障注入和混沌实验自动化，与 https://plumephp.com/distributed-fault-injection/ 的故障注入方法论结合，在 CI 中持续跑故障注入用例。重点验证：每次选举后日志完整、每次分区恢复后日志收敛、状态机始终线性一致。

7.4 参考实现

• etcd/raft：生产级 Go 实现，模块化极好，适合对照阅读
• Hashicorp/raft：另一个生产级 Go 实现
• LogCabin：Raft 作者本人的 C++ 教学实现

8. 常见实现错误清单

1. 忘记持久化 votedFor：重启后可能重复投票，造成双 Leader
2. 提交规则实现错：直接提交上个任期被复制的条目，而不是靠当前任期间接提交
3. nextIndex 回退太慢：逐条回退导致故障恢复极慢，应使用二分回退
4. 选举超时固定：候选人们同时超时形成死锁，必须随机化
5. 任期判断遗漏：所有 RPC 都要先判任期，遗漏任何一条都会破坏安全性
6. 状态机重复应用：lastApplied 与 commitIndex 管理错位导致同一命令执行两次

总结

Raft 的成功在于它把共识的复杂度分解成可独立实现、可独立验证的子问题。理解它的关键不是背诵算法流程，而是吃透"为什么"：为什么投票要限制日志新旧、为什么提交要靠当前任期、为什么配置变更要两阶段。把这些为什么想明白，再对照 etcd 等参考实现，就能写出正确且可维护的共识模块。与 https://plumephp.com/consensus-algorithms/ 和 https://plumephp.com/zookeeper-coordination/ 配合阅读，可以看清 Paxos、Raft、ZAB 三种共识实现各自的取舍。