土法炼钢兴趣小组的算法知识备份

【分布式系统百科】Raft 深度重写：从论文的 18 页到 etcd 的 15000 行

2026-04-13 · distributed · #raft #consensus #etcd #tikv #paxos #distributed-systems #leader-election #log-replication #prevote #multi-raft

文章导航

分类入口
distributed
标签入口
#raft#consensus#etcd#tikv#paxos#distributed-systems#leader-election#log-replication#prevote#multi-raft

目录

Raft 深度重写：从论文的 18 页到 etcd 的 15000 行

2014 年，Diego Ongaro 和 John Ousterhout 在 USENIX ATC 发表了 In Search of an Understandable Consensus Algorithm。论文 18 页，核心贡献只有一句话：把共识算法设计成人能理解的样子。

十年过去，etcd、TiKV、CockroachDB、Consul、RethinkDB、SOFAJRaft——大半个云原生基础设施的共识层都建立在 Raft 或其变体之上。etcd 的 raft 库大约 15000 行 Go。中间的差距不是代码量级的问题，是论文没有也不需要讨论的那些工程 edge case：网络分区恢复后的选举风暴（PreVote）、线性一致性读的性能（ReadIndex / LeaseRead）、Leader 主动迁移（LeaderTransfer）、多节点同时变更（ConfChange V2）、流水线复制的滑动窗口、异步 Apply 对吞吐量的影响。

这篇文章合并并完全重写了本系列之前的两篇 Raft 文章（基础篇 420 行，etcd 实现篇 254 行），目标是用一篇文章覆盖从论文到生产级实现的全部关键细节。

如果你已经熟悉 Raft 论文的基本内容，可以直接跳到第五节 “etcd/raft 工程实现”。

一、Raft 概览：为什么可理解性是设计目标

1.1 Paxos 的教训

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

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

更关键的问题是：Paxos 只定义了对单个值（single decree / single-decree Paxos）达成共识的协议。真实系统需要的是对一系列值达成共识——Multi-Paxos。但 Lamport 从没写过 Multi-Paxos 的完整协议规范。Leader 怎么选、日志怎么管、成员怎么变更——你自己想办法。结果每个 Multi-Paxos 实现都不太一样，都各自发明了一套未经严格验证的扩展。

1.2 Raft 的设计选择

Raft 解决的问题和 Multi-Paxos 一样：管理复制日志（Replicated Log）的共识算法。但设计目标完全不同——可理解性优先（Understandability）。不是比 Paxos 更正确，不是比 Paxos 更快，而是让普通工程师能读懂、能实现、能调试。

Ongaro 在论文中做了一个受控实验：33 个斯坦福和华盛顿大学的学生分别学习 Raft 和 Paxos，然后回答同等难度的测试。Raft 的测试成绩显著优于 Paxos，学生的自评理解程度也更高。

可理解性不是学术美德。可理解性是工程可靠性的前提条件。 你理解不了的算法，你就实现不对；实现不对的共识层，就是定时炸弹。

可理解性带来的工程红利在 Raft 的工业采用史中得到了充分验证。2014 年论文发表后，CoreOS 在 2014 年底发布了 etcd，Raft 成为 Kubernetes 控制面的共识基础。HashiCorp 于 2014 年将 Consul 的服务发现和配置管理构建在自己的 Raft 实现之上。2015 年，CockroachDB 选择 Raft 作为其分布式 SQL 数据库的复制层。PingCAP 的 TiKV 从 2016 年起使用 raft-rs（etcd/raft 的 Rust 移植）驱动 Multi-Raft 架构，将单个集群扩展到数万个 Raft Group。此外还有 RethinkDB、Dgraph、Dragonboat、SOFAJRaft 等项目。截至目前，Raft 是工业界采用最广泛的共识协议，没有之一。这不是因为 Raft 在理论上比 Paxos 更强，而是因为工程师能读懂它、能正确实现它、能在出问题时调试它。

1.3 复制状态机（Replicated State Machine）

Raft 的理论模型是复制状态机。

复制状态机模型

所有节点维护同一份有序日志（Replicated Log）。共识算法保证所有节点的日志内容和顺序一致。每个节点按顺序将日志条目（Entry）应用到自己的状态机（State Machine），最终状态就一致。

共识算法要保证两个性质：

FLP 不可能定理（FLP Impossibility）告诉我们：在完全异步的网络模型中，即使只有一个节点可能崩溃，也不存在一个确定性算法能同时保证 Safety 和 Liveness。Raft 的工程回答是用随机化超时（Randomized Timeout）打破对称性，在实践中让 Liveness 几乎总是成立。Safety 是绝对保证——Raft 永远不会返回错误结果，最坏情况是暂时不可用。

1.4 问题分解

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

  1. Leader Election（领导者选举）：选出一个 Leader 来协调所有决策。
  2. Log Replication（日志复制）：Leader 把客户端的操作以日志条目的形式复制到所有 Follower。
  3. Safety（安全性）：保证换了 Leader 之后不丢已提交的数据、不出错。

加上两个辅助机制：

  1. Log Compaction（日志压缩）：通过快照（Snapshot）防止日志无限增长。
  2. Membership Change（成员变更）：在不停机的情况下增减集群节点。

在展开这些子问题之前，先定义贯穿全文的核心概念。

1.5 核心概念

Term（任期）

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

节点收到比自己 term 更高的消息时，立刻更新自己的 term 并变成 Follower（Follower）。收到比自己 term 更低的消息时，直接拒绝。Term 是 Raft 的纪元——旧 term 的消息在新 term 里毫无权威。

三种角色

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

多数派（Quorum / Majority）

N 个节点的集群，多数派 = ⌊N/2⌋ + 1。任何两个多数派至少有一个公共节点。这个交集保证了信息不会丢失——committed 的数据一定被至少一个多数派成员持有，而新 Leader 一定从多数派中选出，所以新 Leader 一定持有所有 committed 数据。

二、Leader Election：从随机超时到 PreVote

2.1 选举触发

每个 Follower 维护一个 election timeout。这个超时从一个范围内（论文建议 150ms–300ms）随机选取。

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

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

2.2 选举流程

Candidate:
  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()
    )

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

  1. 赢：收到多数节点投票（包括自己）。变成 Leader，立刻向所有节点发心跳宣告权威。
  2. 输：收到合法 Leader 的 AppendEntries（term ≥ 自己的 term）。已经有 Leader 了，变回 Follower。
  3. 平（Split Vote）：超时了还没拿到多数票。重新随机化 election timeout，重新来一轮。

2.3 投票规则

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

function handleRequestVote(request):
  if request.term < currentTerm:
    return reject                            // 过期 term

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

  if votedFor != null && votedFor != request.candidateId:
    return reject                            // 本 term 已投给别人

  if not isLogUpToDate(request.lastLogIndex, request.lastLogTerm):
    return reject                            // 候选人日志不够新

  votedFor = request.candidateId
  reset election timeout
  return grant

两个关键约束：

  1. 每个 term 只投一票。 防止同一 term 内出现两个 Leader。votedFor 需要持久化，否则节点重启后可能重复投票。
  2. 候选人的日志必须至少和投票者一样新。 “至少一样新”的定义：先比较最后一条日志的 term，term 大的更新；term 相同则 index 大的更新。这个约束是 Safety 的核心保障——它阻止了日志落后的节点当选 Leader。

2.4 Term 号的防线作用

Term 是 Raft 里的逻辑围墙。每条消息都带着发送方的 term：

这意味着一个集群中不可能同时存在两个同 term 的 Leader（因为多数派只投一票），也不可能出现旧 Leader 在新 term 里继续发号施令的情况（它的消息会被拒绝）。

2.5 Split Vote 与随机化

五节点集群，Leader 宕机。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 的随机范围，选举通常在一个超时周期内完成。

2.6 PreVote 扩展（etcd 贡献）

Leader Election：标准选举 vs PreVote

标准 Raft 有一个工程问题：网络分区恢复后的选举风暴。

假设一个 5 节点集群，节点 E 被网络隔离了。E 不断超时、不断自增 term、发起选举。没人理它，因为网络不通。分区恢复的瞬间，E 的 term 已经远大于当前 Leader 的 term。E 发出的 RequestVote 会让 Leader step down（因为 term 更高），但 E 的日志又不够新，选不上。结果：集群短暂不可用，需要重新选举。

PreVote 是 etcd 贡献给 Raft 生态的核心改进之一。来自 Ongaro 博士论文（第 9.6 节），不在原始 Raft 论文里。

PreVote 把选举分成两阶段：

  1. PreVote 阶段：Candidate 不增加 term，向所有节点发 MsgPreVote，询问”如果我发起选举，你会投票给我吗？”
  2. 真正选举阶段：只有 PreVote 拿到多数同意，才真正增加 term 发起 RequestVote。

关键在于：收到 PreVote 的节点如果仍然能正常收到 Leader 心跳（electionElapsed < electionTimeout），就拒绝 PreVote。

etcd/raft 中的核心逻辑（源自 etcd v3.5 raft.go）：

// raft.go: Step() 函数中处理 MsgPreVote
case pb.MsgPreVote:
    // 如果当前能正常收到 Leader 心跳，拒绝 PreVote
    if r.lead != None && r.electionElapsed < r.electionTimeout {
        return nil
    }
    // 检查候选人的日志是否至少和自己一样新
    if r.raftLog.isUpToDate(m.Index, m.LogTerm) {
        r.send(pb.Message{
            To:   m.From,
            Type: pb.MsgPreVoteResp,
            Term: m.Term,
        })
    }

被隔离的节点恢复后，它的 PreVote 会被拒绝（因为集群有正常运行的 Leader），它无法进入真正的选举阶段，也就不会打断现有 Leader。

2.7 Split Brain 防护的完整链条

Raft 通过以下机制防止脑裂（Split Brain）：

  1. 每个 term 最多一票：多数派投票，两个不同的 Candidate 不可能在同一 term 都拿到多数票。
  2. Term 单调递增：旧 Leader 的消息在新 term 里被拒绝，无法继续写入。
  3. Commit 需要多数派确认：只有被多数节点持久化的 entry 才算 committed。
  4. PreVote（工程扩展）：阻止分区节点用高 term 干扰正常集群。

这四层防线叠加，使得 Raft 在实践中极少出现脑裂问题。在 Jepsen 对 etcd 的多轮测试中，没有发现过脑裂导致的数据不一致。

三、Log Replication：AppendEntries 的完整流程

3.1 日志的结构

每条日志条目（Entry）包含三个字段：

Leader 维护一个 commitIndex，标记已经安全提交的最新位置。所有 index ≤ commitIndex 的 entry 可以安全地 apply 到状态机。

3.2 正常复制流程

客户端发请求给 Leader。Leader 把操作追加到本地日志，然后并行向所有 Follower 发送 AppendEntries RPC：

Leader:
  entry = Entry(term=currentTerm, index=log.nextIndex(), command=cmd)
  log.append(entry)

  for each follower:
    send AppendEntries(
      term         = currentTerm,
      leaderId     = self,
      prevLogIndex = nextIndex[follower] - 1,
      prevLogTerm  = log[prevLogIndex].term,
      entries      = log[nextIndex[follower]..],
      leaderCommit = commitIndex
    )

Leader 为每个 Follower 维护两个状态：

当多数节点（包括 Leader）都确认写入成功后，Leader 更新 commitIndex，将 entry apply 到状态机，回复客户端。

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

下图展示了稳态运行时一次完整的日志复制流程。从客户端发起写请求，到 Leader 将响应返回给客户端，整个过程涉及的消息交互和状态变迁如下：

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower-1
    participant F2 as Follower-2

    C->>L: 写请求 (Put key=x, val=1)
    Note over L: 追加 Entry 到本地日志<br/>index=5, term=3
    par 并行发送 AppendEntries
        L->>F1: AppendEntries(prevLogIndex=4, entries=[5], leaderCommit=4)
        L->>F2: AppendEntries(prevLogIndex=4, entries=[5], leaderCommit=4)
    end
    F1-->>L: Success (matchIndex=5)
    Note over L: 多数派确认 (Leader+F1=2/3)<br/>commitIndex 更新为 5
    F2-->>L: Success (matchIndex=5)
    Note over L: Apply index=5 到状态机
    L-->>C: 写成功响应
    Note over F1,F2: 下一次 AppendEntries 携带<br/>leaderCommit=5，Follower 执行 apply

该时序图展示了 Raft 稳态下最常见的操作路径。Leader 收到客户端请求后先写本地日志，再并行向所有 Follower 发送 AppendEntries。只要多数派（这里是 Leader 加上 Follower-1）确认持久化成功，Leader 就可以推进 commitIndex 并将结果应用到状态机。Follower 的 commit 和 apply 是延迟的，通过后续心跳或 AppendEntries 中的 leaderCommit 字段得知最新的提交位置。

3.3 一致性检查

AppendEntries RPC 中的 prevLogIndex 和 prevLogTerm 是一致性检查的关键。Follower 收到 AppendEntries 时：

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

  // 一致性检查：prevLogIndex 处的 entry 的 term 必须匹配
  if log[request.prevLogIndex].term != request.prevLogTerm:
    return reject   // 日志不一致，Leader 需要回退

  // 删除冲突 entry，追加新 entry
  for each entry in request.entries:
    if log[entry.index].term != entry.term:
      log.deleteFrom(entry.index)  // 删除从这里开始的所有 entry
    log.append(entry)

  commitIndex = min(request.leaderCommit, log.lastIndex())
  return success

这个一致性检查构成了 Log Matching Property（日志匹配属性）的归纳证明：

由此推出：如果两个节点在某个 index 处有相同的 term，则该 index 之前的所有 entry 都相同。

3.4 日志不一致的修复

Follower 的日志可能和 Leader 不一致。可能缺少 entry（落后），也可能有 Leader 没有的 entry（旧 Leader 的遗留数据）。Raft 的规则是：Leader 的日志是权威，Follower 必须与 Leader 保持一致。

修复策略：Leader 维护每个 Follower 的 nextIndex。如果 AppendEntries 的一致性检查失败（Follower 拒绝），Leader 将 nextIndex 减 1，重试。重复这个过程直到找到一个匹配点（最近的共同前缀），然后从那个点开始覆盖 Follower 的所有后续 entry。

论文的逐步回退每次只减 1，效率低。etcd 和其他实现通常做优化：Follower 在拒绝时返回冲突 entry 的 term 和该 term 的第一条 entry 的 index，Leader 可以一次跳过整个 term 的 entry。

3.5 Commit 规则与 Figure 8

这是 Raft 最微妙的部分。

直觉上，一条 entry 只要被多数节点写入就可以 commit。但 Raft 有一条额外的限制：Leader 只能 commit 当前 term 的 entry，不能直接 commit 旧 term 的 entry。 旧 term 的 entry 通过当前 term 的 entry 被 commit 时”间接 commit”。

这个限制来自 Raft 论文的 Figure 8，是整个 Raft 正确性论证中最难理解的部分。

日志复制与 Commit 规则

Figure 8 场景的完整推演：

考虑一个 5 节点集群 {S1, S2, S3, S4, S5}：

(a) S1 在 term=2 当选 Leader，在 index=2 写入一条 entry (term=2)。只复制到了 S2，还没来得及复制到多数节点，S1 宕机。

(b) S5 当选 term=3 的 Leader（S3、S4 投票给它——它们的日志不比 S5 旧）。S5 在 index=2 写入 entry (term=3)。S5 也宕机了，这条 entry 只在 S5 上。

(c) S1 恢复，当选 term=4 的 Leader。S1 继续复制 index=2 的 entry (term=2) 到 S3。此时 S1、S2、S3 都有 index=2 (term=2)——多数派。

(d) 如果此时 Leader 直接 commit index=2 的 entry (term=2)——这就错了。 因为 S5 有可能在后续当选 Leader（term=5，如果 S1 再次宕机，S5 的 index=2 term=3 日志比 S3/S4 的更新），S5 会用 index=2 (term=3) 覆盖已经被”commit”的 index=2 (term=2)。committed 的数据被覆盖，Safety 被违反。

(e) 正确做法：S1 在 term=4 先写入一条当前 term 的 entry（index=3, term=4），复制到多数节点。当 index=3 (term=4) 被 commit 后，index=2 (term=2) 也被间接 commit（因为它在 index=3 之前）。此时 S5 不可能再当选 Leader——因为它的日志不如持有 index=3 (term=4) 的节点新。

这条规则（只 commit 当前 term 的 entry）对应 etcd/raft 的一个具体实现细节：Leader 当选后第一件事是提交一条空的 no-op entry。 这条 no-op 不携带任何用户命令，唯一的作用是让 Leader 能通过 commit 自己 term 的 entry 来间接 commit 之前所有 term 的 entry。

etcd/raft 中的相关代码（源自 etcd v3.5 raft.go）：

// becomeLeader() 中提交一条空 entry
func (r *raft) becomeLeader() {
    r.step = stepLeader
    r.reset(r.Term)
    r.tick = r.tickHeartbeat
    r.lead = r.id
    r.state = StateLeader
    // 提交空 entry，确保能间接 commit 旧 term 的数据
    r.appendEntry(pb.Entry{Data: nil})
}

四、Safety：Raft 正确性的完整论证

4.1 要证什么

Raft 的核心安全性目标是 State Machine Safety Property：

如果一个节点已经在 index=i 处 apply 了某条 entry，那么其他任何节点在 index=i 处 apply 的一定是同一条 entry。

换句话说：所有节点的状态机在任何 index 处看到的都是同一条命令。

要证明这个性质，核心支柱是 Leader Completeness Property（领导者完备性）：

如果一条 entry 在某个 term 被 commit，那么它一定出现在所有更高 term 的 Leader 的日志中。

只要 Leader Completeness 成立，加上 Raft 的日志覆盖规则（Leader 的日志覆盖 Follower 的冲突 entry），State Machine Safety 就自然成立。

4.2 Leader Completeness 的证明

证明方法：反证法（Proof by Contradiction）。

假设 Leader Completeness 不成立。即存在某个 term T 的 Leader \(L_T\)，它 commit 了 entry e（index=i, term=T），但在某个后续 term U > T 中，Leader \(L_U\) 的日志里不包含 e。

取最小的这样的 U（即 T 和 U 之间的所有 Leader 都包含 e）。

Step 1：\(L_U\) 在当选时不包含 e。\(L_U\) 当选后不会删除自己日志中已有的 entry（Leader 只追加），所以 e 不在 \(L_U\) 日志中意味着 \(L_U\) 当选前就没有 e。

Step 2：\(L_T\) commit 了 e，意味着 e 被多数节点写入。\(L_U\) 赢得选举也需要多数节点投票。两个多数派至少有一个公共节点——称为 voter。

Step 3：voter 在投票给 \(L_U\) 之前一定已经持有 e（因为 voter 在 \(L_T\) commit e 的多数派中）。如果 voter 在投票之前把 e 删了——不可能。Raft 的规则是 Follower 只在 Leader 指示下删除冲突 entry，而 T 和 U 之间的 Leader 都包含 e（U 是最小的不包含 e 的 term），所以不会指示删除 e。

Step 4：voter 在 term U 投票给 \(L_U\)。投票规则要求 \(L_U\) 的日志”至少和 voter 一样新”。voter 持有 e (index=i, term=T)。

结论：假设不成立。Leader Completeness Property 成立。

4.3 从 Leader Completeness 到 State Machine Safety

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

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

4.4 Figure 8 规则在证明中的位置

回到 Section 3.5 的 Figure 8 问题。如果允许 Leader 直接 commit 旧 term 的 entry，Step 3 中”voter 投票前一定持有 e”这个推理就不一定成立了——因为 e 可能在 voter 投票后被一个中间 Leader 覆盖。“只 commit 当前 term 的 entry”这条规则堵住了这个漏洞：它保证了 commit 的 entry 的 term 就是当前 Leader 的 term，而当前 Leader 的 term 一定不小于任何 voter 的 term，所以不可能被更高 term 的 Leader 覆盖。

4.5 选举限制与 Safety 的关系

投票规则中”候选人日志必须至少和投票者一样新”这条约束，是 Safety 成立的必要条件。去掉这个约束会怎样？

假设任何节点都可以当选 Leader，不检查日志的新旧。那么一个日志落后的节点可能当选，它的日志里缺少某些已经被 commit 的 entry。当它开始用自己的日志覆盖 Follower 时，committed 的数据就被丢弃了。

“日志至少一样新”的定义是刻意设计的：先比最后一条 entry 的 term，再比 index。这确保了持有更新的 committed entry 的节点永远不会投票给一个日志更旧的 Candidate。

这个投票限制和 Figure 8 的 commit 规则是 Raft Safety 的两根支柱：

  1. 投票限制保证新 Leader 的日志包含所有 committed entry。
  2. Commit 规则保证不会错误地认为一条 entry 已经 committed。

缺一不可。

4.6 Safety 与 Liveness 的权衡

Raft 的 Safety 是绝对保证：在任何网络条件、任何故障模式下，Raft 永远不会返回错误结果。最坏情况是不可用，不是不正确。

Liveness 则依赖一个实际假设：最终存在一段足够长的时间，在这段时间内多数节点存活且能相互通信。 如果网络永久分区，把集群分成两个少数派，那两个分区都无法选出 Leader，系统永久不可用。

这不是 Raft 的 bug，而是 FLP 不可能定理的必然结果。任何正确的共识算法在异步网络中都不能同时保证 Safety 和 Liveness。Raft 选择了 Safety 优先——这对数据库、配置中心这类系统来说是正确的选择。

五、etcd/raft 工程实现

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

etcd 的 raft 库（go.etcd.io/raft/v3）大约 15000 行 Go，是 Raft 在工业界最被广泛使用的实现之一。它的设计有一个独特之处：raft 库本身不做任何 I/O——不做网络通信，不做磁盘持久化。所有 I/O 通过 Ready 结构体交给应用层处理。

5.1 架构：库而非框架

etcd/raft 的核心数据结构（源自 etcd v3.5 raft.go、node.go）：

// raft.go: Raft 状态机核心
type raft struct {
    id    uint64
    Term  uint64
    Vote  uint64        // 本 term 投给了谁
    lead  uint64        // 当前 Leader
    state StateType     // Follower / Candidate / Leader

    raftLog *raftLog    // 日志存储
    prs     tracker.ProgressTracker  // 每个 Follower 的复制进度

    msgs []pb.Message   // 待发送的消息（网络 I/O 由应用层负责）

    electionElapsed  int
    heartbeatElapsed int
    electionTimeout  int
    heartbeatTimeout int
    randomizedElectionTimeout int

    tick func()         // tickElection 或 tickHeartbeat
    step stepFunc       // stepFollower / stepCandidate / stepLeader
}

核心处理循环在应用层：

for {
    select {
    case rd := <-node.Ready():
        // 1. 持久化 HardState 和 Entries 到 WAL
        wal.Save(rd.HardState, rd.Entries)
        // 2. 如果有快照，应用快照
        if !raft.IsEmptySnap(rd.Snapshot) {
            saveSnap(rd.Snapshot)
        }
        // 3. 发送网络消息
        transport.Send(rd.Messages)
        // 4. 将已 commit 的 entry 应用到状态机
        for _, entry := range rd.CommittedEntries {
            applyToStateMachine(entry)
        }
        // 5. 告知 raft 库可以产生下一个 Ready
        node.Advance()

    case <-ticker.C:
        node.Tick()
    }
}

Ready 结构体（源自 etcd v3.5 node.go）：

type Ready struct {
    SoftState        *SoftState     // Leader/Follower 状态（不需要持久化）
    HardState        pb.HardState   // Term, Vote, Commit（需要持久化）
    Entries          []pb.Entry     // 需要持久化的新日志
    Snapshot         pb.Snapshot    // 需要保存的快照
    CommittedEntries []pb.Entry     // 可以 apply 到状态机的日志
    Messages         []pb.Message   // 需要发送的网络消息
    ReadStates       []ReadState    // ReadIndex 的结果
}

这个设计的好处：同一个 raft 库可以跑在不同的存储引擎（BoltDB、RocksDB、BadgerDB）和不同的网络栈（gRPC、自定义 TCP）上。TiKV 的 raft-rs 就是这个设计的 Rust 移植。

5.2 PreVote

详见 Section 2.6。这里补充 etcd/raft 的实现细节。

PreVote 在 etcd 中默认开启。配置项是 Config.PreVote。PreVote 的 message 类型是 MsgPreVote 和 MsgPreVoteResp。

一个微妙的实现点：PreVote 消息中携带的 term 是 r.Term + 1（当前 term + 1），而不是 r.Term。这样接收方可以判断”如果这个节点真的发起选举，它的 term 会是多少”。但 PreVote 不修改发送方自己的 r.Term。

// raft.go: 发起 PreVote
func (r *raft) campaign(t CampaignType) {
    var term uint64
    var voteMsg pb.MessageType
    if t == campaignPreElection {
        r.becomePreCandidate()
        voteMsg = pb.MsgPreVote
        term = r.Term + 1  // PreVote 携带 term+1 但不修改本地 term
    } else {
        r.becomeCandidate()
        voteMsg = pb.MsgVote
        term = r.Term       // 真正选举时 term 已经递增过
    }
    // ... 发送投票请求 ...
}

5.3 ReadIndex

Raft 保证写的线性一致性（Linearizability）。读呢？

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

ReadIndex 是 etcd 实现的一个重要优化，避免了读走 log 的开销：

  1. Leader 记录当前 commitIndex 为 readIndex。
  2. Leader 向所有 Follower 发送心跳，确认自己仍然是 Leader。
  3. 收到多数心跳回复后，等状态机 apply 到 readIndex。
  4. 执行读操作并返回结果。
// raft.go: 处理 ReadIndex 请求
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,
    })
    r.bcastHeartbeatWithCtx(m.Entries[0].Data)
}

ReadIndex 的核心保证：心跳确认了 Leader 在这一刻仍然是 Leader。如果 Leader 已经被罢免（有新 Leader 了），心跳不会拿到多数回复，ReadIndex 失败，客户端重试。

性能对比：

方法 延迟 一致性 时钟依赖
读走 Log（Propose） 1 次共识 RTT 线性一致 无
ReadIndex 1 次心跳 RTT 线性一致 无
LeaseRead 0 RTT 线性一致（依赖时钟） 有
Follower Read 1 次 ReadIndex + 1 次转发 线性一致 无

LeaseRead 更激进：如果 Leader 刚在 election timeout 以内收到过多数心跳确认，直接读，不再发心跳。代价是依赖时钟——如果机器时钟漂移超过 election timeout，可能读到过期数据。etcd 默认用 ReadIndex，不用 LeaseRead。正确性优先。

5.4 LeaderTransfer

运维场景：需要维护当前 Leader 节点，希望主动把 Leader 迁走。论文没提这个。

etcd 的做法：

  1. Leader 停止接受新的 Propose。
  2. Leader 把目标节点的日志追平（发送缺失的 AppendEntries）。
  3. Leader 给目标节点发 MsgTimeoutNow。
  4. 目标节点收到后立刻发起选举（跳过 election timeout），因为日志已追平所以一定能赢。
// raft.go: 发起 LeaderTransfer
func (r *raft) handleTransferLeader(m pb.Message) {
    leadTransferee := m.From
    // 如果目标节点日志已追平
    if pr.Match == r.raftLog.lastIndex() {
        r.sendTimeoutNow(leadTransferee)
    } else {
        // 先追日志
        r.sendAppend(leadTransferee)
    }
    r.leadTransferee = leadTransferee
}

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

整个 LeaderTransfer 大约 50 行代码。有一个超时机制：如果目标节点在一个 election timeout 内没有当选，放弃 Transfer，Leader 恢复正常接受请求。

5.5 ConfChange V2 与 Joint Consensus

论文 Section 6 用了不到一页讲 Configuration Change（成员变更）。论文提出了 Joint Consensus（联合共识）：新旧配置同时生效，通过两阶段切换保证安全。

etcd 最初用的是单步变更（One-at-a-Time）：每次只添加或删除一个节点。实现简单，在大多数场景下安全。但有一个微妙的 bug。

单步变更的边界条件： 假设集群从 3 节点扩到 5 节点。如果连续快速添加两个节点（第一个 ConfChange 还没被 commit），新旧配置的多数派可能不重叠，违反 Safety。

etcd 的防御措施：ConfChange 本身也是 raft log 的一条 entry，必须被 commit 后才能应用。在上一条 ConfChange entry 被 apply 之前，Leader 拒绝新的 ConfChange。

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

但”一次只变一个”无法覆盖所有场景。比如替换节点：同时移除旧节点、添加新节点。如果先移除再添加，中间多数派数量变化可能导致不可用；如果先添加再移除，集群扩大后多数派要求变高，也可能不可用。

etcd 后来实现了 ConfChange V2，支持完整的 Joint Consensus：

// confchange.go: V2 支持批量变更
type ConfChangeV2 struct {
    Transition ConfChangeTransition  // Auto / Implicit / Explicit
    Changes    []ConfChangeSingle    // 可以包含多个变更
}

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

Joint Consensus 的两阶段：

  1. 进入联合配置：集群同时使用旧配置 \(C_{old}\) 和新配置 \(C_{new}\)。任何决策需要同时在 \(C_{old}\) 和 \(C_{new}\) 中都拿到多数派。
  2. 退出联合配置：\(C_{old,new}\) 的 entry 被 commit 后，Leader 发起第二阶段，切换到 \(C_{new}\)。\(C_{new}\) 的 entry 被 commit 后，旧配置中不在新配置里的节点可以安全关闭。

Learner 节点

另一个论文没提的工程补充。当添加新节点时，它的日志为空。在它追上集群进度之前，作为 Voter 参与多数派会拖慢 commit（因为需要等它确认）。

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

六、性能优化：从正确到高效

论文的目标是证明正确性，不追求性能。如果你按论文逐字实现，能跑，但性能很差。以下是 etcd/raft 和其他生产级实现中的关键性能优化。

6.1 BatchAppend

论文的模型是每次客户端请求产生一条 entry，发一次 AppendEntries。实际实现中，Leader 可以把多条 entry 打包在一个 AppendEntries RPC 中批量发送。

etcd 的 Ready 结构体天然支持 batching：一个 Ready 可以包含多条 Entries 和多条 CommittedEntries。应用层可以在一次 WAL 写入中持久化所有 entry，在一次网络调用中发送所有消息。

// 应用层的处理循环（简化）
rd := <-node.Ready()
// 一次 WAL fsync 持久化所有新 entry
wal.Save(rd.HardState, rd.Entries)
// 一次网络调用发送所有消息
transport.Send(rd.Messages)
// 批量 apply 所有已 commit 的 entry
for _, entry := range rd.CommittedEntries {
    applyToStateMachine(entry)
}
node.Advance()

Batching 把”每条 entry 一次 fsync”变成”一批 entry 一次 fsync”。在高吞吐场景下，这个优化可以将吞吐量提升一个数量级。

6.2 Pipeline（流水线复制）

论文的复制模型是同步的：发 AppendEntries → 等回复 → 发下一批。每次复制的延迟 = 一个 RTT。

etcd/raft 在 Follower 正常跟上时（状态 = StateReplicate），不等回复就继续发下一批。使用一个固定大小的滑动窗口（Inflights）控制未确认的消息数量：

// tracker/progress.go
type Progress struct {
    State StateType  // StateProbe, StateReplicate, StateSnapshot

    Match uint64     // 已确认持久化的最新 index
    Next  uint64     // 下一次发送的起始 index

    // StateReplicate 模式下的滑动窗口
    Inflights *Inflights
}

Inflights 是一个环形缓冲区，默认大小 256。Leader 对每个 StateReplicate 的 Follower 持续发送 AppendEntries，直到 inflight 窗口满。收到 ACK 后窗口向前滑动。

吞吐量从”一个 RTT 一批”变成”窗口大小 × 批量大小 / RTT”。和 TCP 的滑动窗口是同一个思路。

6.3 Probe / Replicate / Snapshot 三状态机

etcd 为每个 Follower 维护一个三状态的复制状态机：

                    +-- 首次成功 ACK --> StateReplicate (流水线)
                    |
  StateProbe -------+
  (逐条确认)        |
                    +-- 落后太多 -----> StateSnapshot (发快照)
                                          |
                                          +-- 快照完成 --> StateProbe

论文只有”正常复制”和”快照”两种情况。etcd 加了 Probe 作为中间状态，避免在 Follower 状态未知时浪费带宽发送它无法接受的数据。

6.4 Async Apply

etcd 的默认处理流程是：持久化 → 发送消息 → Apply → Advance。其中 Apply 是将已 commit 的 entry 应用到状态机。如果状态机操作很慢（比如涉及复杂的数据库写入），Apply 会阻塞整个 Ready 循环。

Async Apply 是一个进阶优化：Apply 在独立的 goroutine 中异步执行，Ready 循环不等 Apply 完成就调用 Advance。这允许 raft 层继续处理新的 Propose 和 AppendEntries，而状态机在后台追赶。

标准流程：
  WAL fsync → Send Messages → Apply → Advance → 下一个 Ready

Async Apply：
  WAL fsync → Send Messages → Advance → 下一个 Ready
                                  |
                      Apply (异步，不阻塞)

Async Apply 的注意事项：

  1. 读一致性：ReadIndex 需要确保状态机已经 apply 到 readIndex 才能返回。Async Apply 下需要额外等待。
  2. 快照：做快照时需要状态机的一致视图。如果 Apply 是异步的，需要一个 snapshot barrier。
  3. 重启恢复：重启后需要从 WAL 重放所有已 commit 但未 apply 的 entry。

TiKV 在其 Multi-Raft 实现中大量使用 Async Apply，是其高吞吐量的关键因素之一。

6.5 WAL fsync 优化

WAL（Write-Ahead Log）的 fsync 是 Raft 性能的最大瓶颈。每次 fsync 在 HDD 上约 5-10ms，在 SSD 上约 0.1-0.5ms，在 NVMe 上约 0.02-0.05ms。

常见优化：

  1. Group Commit：积攒多条 entry 在一次 fsync 中写入。etcd 的 Ready batching 天然支持这个。
  2. 并行 WAL 与网络：WAL fsync 和发送 Messages 可以并行——Leader 不需要等自己的 WAL fsync 完成就可以发 AppendEntries 给 Follower。Leader 的持久化和 Follower 的持久化可以并行进行。只要多数节点（可能不包括 Leader 自己）持久化成功，entry 就可以 commit。
  3. io_uring / O_DIRECT：绕过 page cache 减少 fsync 延迟。PingCAP 的 Titan 存储引擎在这方面做过实验。

七、TiKV 实践：Multi-Raft 架构

单个 Raft Group 管理一个复制状态机。但一个数据库的数据可能有几个 TB——全部放在一个 Raft Group 里，Leader 是绝对的瓶颈。

TiKV 的答案是 Multi-Raft：把数据分成很多个 Region（区间），每个 Region 是一个独立的 Raft Group。

7.1 Region

TiKV 的数据按 key 的字典序分成连续的区间，每个区间称为一个 Region。每个 Region 默认 96MB，包含一段连续的 key range，例如 [key_0001, key_1000)。

每个 Region 是一个独立的 Raft Group，有自己的 Leader、Follower、日志和状态机。不同 Region 的 Leader 可以分布在不同的物理节点上，实现负载均衡。

Node 1              Node 2              Node 3
+--------+          +--------+          +--------+
| R1(L)  |          | R1(F)  |          | R1(F)  |
| R2(F)  |          | R2(L)  |          | R2(F)  |
| R3(F)  |          | R3(F)  |          | R3(L)  |
+--------+          +--------+          +--------+

Region 1: [a, m)    Leader on Node 1
Region 2: [m, t)    Leader on Node 2
Region 3: [t, ~)    Leader on Node 3

7.2 Region Split

当一个 Region 的数据量超过阈值（默认 96MB），Region 需要分裂。

Split 的过程：

  1. Leader 检测到 Region 大小超过阈值。
  2. Leader 选择一个 split key（通常是 Region 中间位置的 key）。
  3. Leader 提交一个特殊的 Raft 日志：AdminCmd::Split。
  4. 所有节点 apply 这条日志后，原 Region 分裂成两个新 Region。
  5. 新 Region 继承原 Region 的副本分布，但后续可以被 PD（Placement Driver）调度到其他节点。

Split 的关键：它是通过 Raft 日志来协调的，保证所有副本在同一个 log index 处执行 split，不会出现一部分副本 split 了另一部分没 split 的情况。

7.3 Region Merge

Split 的逆操作。当相邻两个 Region 都很小时（比如大量 delete 之后），Merge 可以减少 Region 数量，降低元数据开销。

Merge 比 Split 复杂得多：

  1. 两个 Region 有独立的 Raft Group，需要协调两个独立的状态机。
  2. 源 Region 需要先停止接受新的写入。
  3. 源 Region 提交一个 PrepareMerge 日志，目标 Region 提交一个 CommitMerge 日志。
  4. 源 Region 的数据合并到目标 Region，源 Region 销毁。

Merge 的难点在于两个 Raft Group 之间的协调。如果源 Region 提交了 PrepareMerge 但目标 Region 还没提交 CommitMerge 时发生了 Leader 切换，需要正确处理这个中间状态。TiKV 在这里花了大量代码处理各种 edge case。

7.4 Batch Raft 与 Store 线程模型

一个 TiKV 节点可能有几万个 Region。如果每个 Region 的 Raft 独立运行，线程数和 context switch 开销会非常大。

TiKV 的优化：

  1. Batch Raft：多个 Region 的 Raft 消息在一次网络调用中批量发送。同一个 Store 之间的所有 Region 共享一个 gRPC 连接。
  2. Store 线程池：使用固定大小的线程池处理多个 Region 的 Raft tick、Step、Ready。不是每个 Region 一个线程。
  3. 共享 WAL：多个 Region 的 WAL 写入合并成一次 fsync，降低持久化开销。

这些优化使得单个 TiKV 节点可以承载几万甚至十几万个 Region，同时保持合理的 CPU 和 I/O 开销。

7.5 PD 调度与 Leader Balance

PD（Placement Driver）是 TiKV 集群的大脑。它负责：

PD 的调度决策本身也需要共识——PD 自身是一个 etcd 集群。这就形成了一个有意思的嵌套结构：PD 用 Raft（通过 etcd）来管理元数据，元数据描述了哪些 TiKV 节点上有哪些 Region，而每个 Region 又是一个 Raft Group。

7.6 Raft 在 TiKV 事务中的角色

TiKV 使用 Percolator 模型实现分布式事务。事务的 Prewrite 和 Commit 操作都需要写入数据，而写入数据要通过 Raft 共识。一个跨 Region 的事务涉及多个 Raft Group 的独立写入：

事务 T 操作 key_a (Region 1) 和 key_b (Region 2)：

Phase 1 - Prewrite:
  Region 1: Raft Propose → commit → apply → 写入 lock
  Region 2: Raft Propose → commit → apply → 写入 lock

Phase 2 - Commit:
  Region 1 (primary): Raft Propose → commit → apply → 写入 write 列
  Region 2: Raft Propose → commit → apply → 写入 write 列

每个 Raft Propose → commit 需要一次多数派确认。一个涉及 N 个 Region 的事务，至少需要 2N 次 Raft 共识（N 次 Prewrite + N 次 Commit）。这就是为什么 TiKV 的 Raft 层性能对事务延迟有直接影响——Pipeline、Batch、Async Apply 这些优化不是锦上添花，而是实际可用的必要条件。

八、Raft vs Paxos：精确对比

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

8.1 结构对比

维度 Raft Multi-Paxos
协议规范完整性 论文包含完整协议：选举、复制、安全性、成员变更、快照 原始论文只定义 single-decree；Multi-Paxos 无标准规范
Leader 强制单 Leader，所有写经过 Leader 可以无 Leader（basic Paxos），也可以有（Multi-Paxos），协议不规定
日志结构 严格连续，无空洞 允许空洞（不同 slot 独立达成共识）
选举协议 明确定义：RequestVote + 随机超时 无标准选举协议，各实现自行设计
日志冲突 Leader 日志一定是对的，覆盖 Follower 的冲突 entry Leader 需要先”学习”已有决议，再填充空洞
成员变更 论文内置 Joint Consensus / 单步变更 需自行设计，原始论文不涉及
可理解性 核心设计目标，有受控实验验证 Lamport 自己承认”不幸地选择了希腊议会的表述方式”

8.2 Raft 放弃了什么

  1. 日志的并行性。 Paxos 允许对不同 slot 并行达成共识——slot 3 和 slot 7 可以同时 commit，中间有空洞没关系。Raft 的日志严格连续，index=7 必须等 index=6 commit 后才能 commit。这限制了理论上的并行度。EPaxos（Egalitarian Paxos）和 Flexible Paxos 就是在这个方向上的改进尝试。

  2. 无 Leader 的可能性。 Basic Paxos 不需要 Leader——任何节点都可以发起提案。这在 Leader 不可用时有理论优势。Raft 的 Leader 挂了之后必须等待选举完成（通常几百毫秒），期间集群不可用。

  3. 更灵活的 Quorum 配置。 Flexible Paxos 指出，Phase 1（选举 / Prepare）的 Quorum 和 Phase 2（复制 / Accept）的 Quorum 只需要有交集，不需要都是多数派。比如 5 节点集群可以用 Phase 1 Quorum = 4, Phase 2 Quorum = 2，降低正常操作的延迟。Raft 的多数派是固定的 ⌊N/2⌋ + 1。

8.3 Raft 获得了什么

  1. 完整的协议规范。 论文 18 页覆盖了所有必要的子协议。Multi-Paxos 的每个实现都在发明自己的扩展，缺乏统一的参考规范。

  2. 可理解性带来的工程可靠性。 etcd/raft 的代码经过了 Jepsen 测试、TLA+ 形式化验证、数千个生产集群的验证。Paxos 实现因为各自不同，难以享受同等规模的验证。

  3. 更简单的正确性推理。 强 Leader + 连续日志 + 明确的覆盖规则，使得 Raft 的正确性证明相对直观。Paxos 的正确性推理需要处理并发 Proposer、空洞、乱序等更多情况。

  4. 工业生态。 etcd/raft、raft-rs、SOFAJRaft、Dragonboat、hashicorp/raft——高质量的开源实现遍布 Go、Rust、Java、C++ 各语言。Multi-Paxos 的高质量开源实现相对稀少。

8.4 性能差距有多大

理论上，Paxos 的日志并行性和灵活 Quorum 可以在特定场景下优于 Raft。实际上，在局域网、正常运行（Leader 存活）的情况下，两者的性能差距很小。原因：

  1. Multi-Paxos 在有 Leader 时的操作路径和 Raft 几乎一样：Leader 写入 → 复制到多数派 → commit。Leader 存活期间不需要 Phase 1。
  2. 性能瓶颈通常在 WAL fsync 和网络延迟，不在共识协议本身的差异。
  3. Raft 的工程优化（Pipeline、Batch、Async Apply）已经把协议层面的理论差距抹平了。

差距在跨数据中心场景下会放大：Raft 的 Leader 必须参与每次写入，跨数据中心的 RTT 成为硬性瓶颈。Paxos 的灵活 Quorum 可以让写入只等最近的多数派，不需要等 Leader（如果 Leader 在远端）。

九、Raft 的已知缺陷

Raft 的设计选择带来了明确的限制。以下是工程实践中遇到的主要问题。

9.1 Leader 瓶颈

所有读写都经过 Leader。Leader 的 CPU、内存、网络带宽是整个集群的天花板。在单 Raft Group 场景下，这个限制是根本性的。

缓解方式：

9.2 跨数据中心延迟

Raft 要求 Leader 参与每次写入。如果 Leader 在数据中心 A，写请求来自数据中心 B，延迟 = 跨数据中心 RTT（通常 30-100ms）+ 本地处理时间。

更关键的是：commit 需要多数派确认。3 副本分布在 3 个数据中心时，commit 延迟 = 至少一次跨数据中心 RTT。5 副本分布在 5 个数据中心时，commit 延迟 = 至少两次跨数据中心 RTT。

CockroachDB 的做法是允许 Leaseholder（负责读的节点）和 Raft Leader 分离，把读延迟和 Raft Leader 位置解耦。但写延迟仍然受 Leader 位置影响。

9.3 单写者限制

Raft 是 single-writer 协议。同一时刻只有一个 Leader 可以写入。这意味着写入吞吐量受限于单节点的处理能力。

对比：EPaxos 允许任何节点发起提案，在命令不冲突的情况下可以并行 commit，不需要 Leader 协调。但 EPaxos 的实现复杂度远高于 Raft，且在命令冲突时退化为类似 Paxos 的两阶段协议。

9.4 选举不可用窗口

Leader 宕机后，集群在选举完成前不可用。不可用时间 ≈ election timeout（通常 1-5 秒配置，实际选举在几百毫秒内完成）。

在网络分区或频繁抖动的情况下，选举可能反复失败，不可用时间会延长。PreVote 缓解了分区恢复后的问题，但不能完全消除选举期间的不可用。

9.5 日志复制的串行性

Raft 的日志是严格有序的。即使两条命令完全不相关（比如操作不同的 key），它们也必须被排成一个线性顺序。

在状态机是一个 KV 存储的场景下，对不同 key 的操作本可以并行处理，但 Raft 的日志顺序把它们串行化了。这是正确性的要求（保证所有节点看到同一个顺序），但在某些场景下是不必要的性能损失。

Multi-Raft 在一定程度上缓解了这个问题——不同 Region 的操作是并行的。但单个 Region 内的操作仍然是串行的。

9.6 快照的代价

当 Follower 落后太多时，Leader 需要发送完整的快照。快照大小 = 整个状态机的序列化数据。对于一个几个 GB 的状态机，快照传输会占用大量网络带宽和磁盘 I/O。

快照涉及几个层面的问题：

传输开销。 一个 96MB 的 TiKV Region 做快照，在千兆网络上需要约 0.8 秒。如果多个 Region 同时需要快照（比如一个节点宕机 30 分钟后恢复），网络带宽会被迅速吃满。TiKV 通过 snap-max-write-bytes-per-sec 限制快照传输速率，默认 100MB/s。同时限制并发快照数量（snap-max-total-size）。

做快照的 CPU 和内存开销。 快照需要序列化整个状态机的一致视图。如果状态机是一个 LSM-Tree（RocksDB），可以利用 RocksDB 的 Checkpoint 功能做硬链接快照，避免完整拷贝。etcd 使用 BoltDB，BoltDB 的 Tx.WriteTo() 可以直接将事务视图写出。

做快照期间的写入阻塞。 有些实现在做快照时需要暂停写入以获取一致视图。etcd 使用 BoltDB 的只读事务来做快照，不阻塞写入。TiKV 使用 RocksDB 的 snapshot 也不阻塞写入。但在某些自定义状态机实现中，如果没有 MVCC 支持，做快照可能需要 stop-the-world。

InstallSnapshot RPC 的设计。 快照可能很大，不能在一个 RPC 中传输。Raft 论文建议分块传输（chunked transfer）。etcd 的实现把快照写入临时文件，通过 HTTP 传输。TiKV 使用 gRPC 的流式传输。

InstallSnapshot RPC:
  term           = currentTerm
  leaderId       = self
  lastIncludedIndex = snapshot 覆盖的最后一条 entry 的 index
  lastIncludedTerm  = 该 entry 的 term
  offset         = 当前块在快照中的偏移（分块传输用）
  data           = 快照数据块
  done           = 是否是最后一块

Follower 收到后：
  1. 如果 term < currentTerm → 拒绝
  2. 写入临时文件
  3. done=true 时：
     - 如果 snapshot 覆盖了部分日志 → 保留后续 entry
     - 如果 snapshot 覆盖了全部日志 → 丢弃全部日志
     - 加载 snapshot 到状态机
     - 后续通过正常 AppendEntries 追赶

9.7 成员变更的运维风险

成员变更是 Raft 运维中出错率最高的操作。常见问题：

  1. 在 Leader 不稳定时变更：如果集群正在选举或 Leader 频繁切换，ConfChange 可能失败或被重复提交。
  2. 同时移除多数节点：比如 3 节点集群移除 2 个节点，剩余 1 个节点无法形成多数派。
  3. Learner 长时间无法追上：如果新节点的网络或磁盘太慢，它可能永远追不上日志，阻塞 promote 流程。

生产环境的经验法则：

总结：论文与工程之间的距离

把论文和 etcd/raft 的差距总结成一张表：

论文内容 etcd 工程补充 动机
基础选举 PreVote 两阶段选举 防止分区恢复后的选举风暴
无 LeaderTransfer 运维需求：优雅迁移 Leader
同步复制 流水线复制 + 滑动窗口 吞吐量差 10 倍以上
一致性检查失败时逐步回退 Probe / Replicate / Snapshot 三状态机 避免在未知状态下浪费带宽
逐条 Apply Ready batching + Async Apply 把 raft 和 I/O 解耦，提升吞吐
Joint Consensus（一页） ConfChange V2 + Learner 节点 单步变更的安全漏洞 + 新节点追赶
无 ReadIndex / LeaseRead 读性能优化
无 Follower Read 读负载分散

论文的 18 页是正确的。但工程需要处理的不是”正确”，而是”在真实网络、真实磁盘、真实运维操作下持续正确”。每一行 etcd 的代码背后，都有一个论文没提到的 edge case。

Raft 论文的伟大不在于它证明了什么新定理——那些性质 Paxos 也能保证。它的伟大在于它证明了共识算法不需要是黑魔法。如果工程师理解不了算法，那算法再优秀也没用。可理解性不是学术上的审美偏好，而是工程可靠性的前提条件。

参考资料：

  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. 包含 PreVote（§9.6）、LeaderTransfer 等扩展。
  3. Lamport, L. (2001). Paxos Made Simple.
  4. Moraru, I., Andersen, D. G., & Kaminsky, M. (2013). There Is More Consensus in Egalitarian Parliaments. SOSP. （EPaxos 论文）
  5. Howard, H., Malkhi, D., & Spiegelman, A. (2016). Flexible Paxos: Quorum Intersection Revisited. OPODIS.
  6. etcd/raft — etcd 的 Raft 实现，Go 语言，约 15000 行。
  7. TiKV raft-rs — etcd/raft 的 Rust 移植，PingCAP 维护。
  8. TiKV Deep Dive: Multi-Raft — TiKV 官方文档，Multi-Raft 架构说明。
  9. raft.github.io — Raft 可视化，推荐对着它走一遍选举和日志复制流程。

Prev: Paxos | Next: EPaxos 与 Flexible Paxos

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-01 · distributed

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

Paxos 被引用了几千次，能正确实现它的人不超过几十个。Raft 用可理解性换工程落地，它的 Leader Election、Log Replication 和 Safety 三板斧，撑起了 etcd、TiKV 和大半个云原生基础设施。

By .