21.6 Raft：日志复制
一句话
日志复制只有一条规则——提交 = 多数派持久化 + 当前任期；AppendEntries 的一致性检查、nextIndex 回退、冲突条目覆盖，全都是为了让这条规则在任意故障后仍然成立。
日志长什么样
index: 1 2 3 4 5 6
term: 1 1 2 2 4 4
command: a=1 b=2 c=3 d=4 e=5 f=6
▲ ▲
旧任期遗留 leader 当前任期（term 4）
三个不变量（后面所有证明都建立在它们上面）：
| 不变量 | 含义 |
|---|---|
| 日志匹配（Log Matching） | 两个日志在某个 (index, term) 相同 ⇒ 该位置之前的所有条目都相同 |
| leader 只追加 | leader 从不覆盖或删除自己的日志，只往后加 |
| 提交不可逆 | 一旦某条目被提交，之后所有 leader 都会包含它（证明见 21.7 Raft：安全性证明） |
AppendEntries：一次复制带哪些字段
| 字段 | 作用 | 出错会怎样 |
|---|---|---|
term | leader 的任期 | 旧 leader 的请求必须被拒绝 |
leaderId | 用于 follower 转发客户端请求 | 客户端打到 follower 时无法重定向 |
prevLogIndex / prevLogTerm | 一致性检查点：我发的这批日志紧接在你这个位置上 | 少了它，follower 无法判断自己是否与 leader 分叉 |
entries[] | 要追加的条目（心跳时为空） | —— |
leaderCommit | leader 已知的 commitIndex | follower 无法及时应用已提交日志 |
follower 的处理流程
收到 AppendEntries(term, prevLogIndex, prevLogTerm, entries, leaderCommit)
① term < currentTerm → 拒绝，返回自己的 term
② term ≥ currentTerm → 更新 term、转为 follower、重置选举计时器
③ 本地日志在 prevLogIndex 处不存在，或 term ≠ prevLogTerm
→ 拒绝（让 leader 回退 nextIndex 重试）
④ 与 entries 冲突的位置起，删除本地冲突条目（及之后所有），追加新的
⑤ commitIndex = min(leaderCommit, 本地最后一条的 index)，然后 apply
第 ③ 步的拒绝是"回退"的触发器；第 ④ 步的删除冲突条目是唯一允许 follower 丢弃自己日志的场合——它丢的必然是"从未提交过的条目"（因为已提交条目一定在 leader 上，见 21.7 Raft：安全性证明 的引理 3）。
nextIndex 回退：日志分叉怎么被修好
leader 为每个 follower 维护 nextIndex（下一条要发的 index）与 matchIndex（已确认复制的最高 index）。日志不一致时，从大到小试探，直到找到最后一致的位置。
package main
import (
"fmt"
"sort"
)
type entry struct {
Term int
Cmd string
}
type log []entry // log[0] 对应 index 1
func show(name string, l log) {
s := ""
for i, e := range l {
s += fmt.Sprintf(" %d(t%d)", i+1, e.Term)
}
fmt.Printf("%-10s%s\n", name, s)
}
// leader 的 nextIndex 指向 follower 的下一个待发送位置；不匹配就一步一步回退
func backtrack(leader, follower log, nextIndex int) int {
for nextIndex > 1 {
prev := nextIndex - 1 // 1-based
if prev <= len(leader) && prev <= len(follower) && leader[prev-1].Term == follower[prev-1].Term {
break
}
fmt.Printf(" nextIndex=%d：prevLogIndex=%d 的 term 对不上，回退到 %d\n", nextIndex, prev, nextIndex-1)
nextIndex--
}
return nextIndex
}
// 多数派都已复制的最高 index：5 个节点取第 3 大
func commitIndex(match []int) int {
s := append([]int(nil), match...)
sort.Ints(s)
return s[len(s)/2]
}
func main() {
fmt.Println("场景 A：follower 的日志与 leader 在 index 3 处分叉（旧任期的条目）")
leader := log{{1, "a=1"}, {1, "b=2"}, {2, "c=3"}, {2, "d=4"}, {4, "e=5"}, {4, "f=6"}}
follower := log{{1, "a=1"}, {1, "b=2"}, {3, "x=9"}, {3, "y=9"}}
show("leader:", leader)
show("follower:", follower)
next := backtrack(leader, follower, len(leader)+1)
fmt.Printf("\n回退到 nextIndex=%d：prevLogIndex=%d 的 term 匹配 → 追加并删除冲突条目\n", next, next-1)
follower = append(follower[:next-1:next-1], leader[next-1:]...)
show("追加后:", follower)
fmt.Println("\n场景 B：commitIndex 由多数派的 matchIndex 决定")
for _, match := range [][]int{{6, 6, 6, 4, 3}, {6, 5, 4, 3, 2}} {
ci := commitIndex(match)
term := leader[ci-1].Term
fmt.Printf(" matchIndex=%v → commitIndex=%d（term=%d，leader 当前 term=4）", match, ci, term)
if term == 4 {
fmt.Println(" → 可提交")
} else {
fmt.Println(" → 不能直接提交：必须等某个 term=4 的条目先被多数派复制")
}
}
fmt.Println("\n场景 C：日志匹配性质保证「同 index 同 term ⇒ 同命令」，所以分叉只能发生在 term 不同的位置")
fmt.Println(" 若 follower 在 index3 有 t2 的命令 X，而 leader 在 index3 有 t2 的命令 c，")
fmt.Println(" 则说明有人违反了 AppendEntries —— 正确实现里这种状态不可达。")
}
输出（本机实测）：
场景 A：follower 的日志与 leader 在 index 3 处分叉（旧任期的条目）
leader: 1(t1) 2(t1) 3(t2) 4(t2) 5(t4) 6(t4)
follower: 1(t1) 2(t1) 3(t3) 4(t3)
nextIndex=7：prevLogIndex=6 的 term 对不上，回退到 6
nextIndex=6：prevLogIndex=5 的 term 对不上，回退到 5
nextIndex=5：prevLogIndex=4 的 term 对不上，回退到 4
nextIndex=4：prevLogIndex=3 的 term 对不上，回退到 3
回退到 nextIndex=3：prevLogIndex=2 的 term 匹配 → 追加并删除冲突条目
追加后: 1(t1) 2(t1) 3(t2) 4(t2) 5(t4) 6(t4)
场景 B：commitIndex 由多数派的 matchIndex 决定
matchIndex=[6 6 6 4 3] → commitIndex=6（term=4，leader 当前 term=4） → 可提交
matchIndex=[6 5 4 3 2] → commitIndex=4（term=2，leader 当前 term=4） → 不能直接提交：必须等某个 term=4 的条目先被多数派复制
场景 C：日志匹配性质保证「同 index 同 term ⇒ 同命令」，所以分叉只能发生在 term 不同的位置
若 follower 在 index3 有 t2 的命令 X，而 leader 在 index3 有 t2 的命令 c，
则说明有人违反了 AppendEntries —— 正确实现里这种状态不可达。
两个细节：
- 回退是 O(日志长度) 的：一条一条退很慢。实现优化是让 follower 返回"冲突条目的 term 与这个 term 的第一条 index"，leader 一次跳过整个 term（etcd/TiKV 都这么做）。上面的代码为了看清机制，用的是逐条回退。
- 案例 B 的第二行是关键：
commitIndex=4但term=2 ≠ 当前 term=4，所以不能提交。这条规则是 Raft 安全性的补丁，理由见 21.7 Raft：安全性证明 的图 8 反例。
提交与应用：两个容易混淆的 index
| 概念 | 含义 | 更新时机 |
|---|---|---|
commitIndex | 多数派已持久化到的最高 index | leader 收到多数派 matchIndex 后计算 |
lastApplied | 状态机已经执行到的 index | 异步 apply，总是 ≤ commitIndex |
matchIndex[i] | follower i 已确认复制的最高 index | 每次 AppendEntries 成功响应 |
写请求 → leader 追加本地日志（fsync）
→ 并发发 AppendEntries
→ 多数派响应成功 → commitIndex = 中位数(matchIndex)
→ apply 到状态机（lastApplied 前移）→ 返回客户端成功
三个必须说清的边界：
- 先落盘再回 ACK：follower 必须 fsync 后才回成功，否则"多数派持久化"是假的（掉电即丢）。
- apply 失败怎么办：状态机执行必须是确定性的；apply 报错通常意味着状态机与日志不匹配（比日志回放不一致更严重），工程上要么 panic 重启回放，要么走快照重建。
- 客户端重试：leader 在 apply 后、返回前崩溃，客户端会重试 → 同一条命令可能被应用两次。Raft 只保证日志不重复，业务幂等要自己做（见 25.4 幂等设计与去重）。
吞吐与延迟：批大小是唯一的杠杆
单 leader 串行提交时：
吞吐上限 ≈ 批大小 / RTT 单条延迟 ≈ RTT + fsync
| 手段 | 效果 | 代价 |
|---|---|---|
| 流水线（pipeline） | 不等上一条 ACK 就发下一条，吞吐 ≈ 窗口 × 1/RTT | 乱序响应要按 index 归位；内存占用上升 |
| 批量（batch） | 一次 AppendEntries 带 N 条，摊薄 RTT 与 fsync | 单条延迟上升（等攒批） |
| 并行发 follower | 5 节点只需等 3 个，慢节点不拖后腿 | 慢节点日志越来越落后 → 触发快照 |
| 按 follower 分级 | 给慢节点单独限流，避免拖垮 leader 的出带宽 | 实现复杂 |
🔑 共识的吞吐不是"算法快不快"，而是每 RTT 能确认多少字节。同城 1ms RTT、批 100 条 × 200B ≈ 20 MB/s；跨城 30ms RTT 同样的批只有 0.67 MB/s——差 30 倍，全部来自 RTT。这也解释了为什么跨地域共识只用来放元数据。
落后太多的节点：补日志还是发快照
| 落后程度 | 做法 | 理由 |
|---|---|---|
| 几十~几千条 | AppendEntries 逐批补齐 | 传输小、可流水线 |
| 超过日志保留范围（已被快照截断） | InstallSnapshot 发整个状态机镜像 | 缺失的日志已经不存在，无法补 |
| 落后但网络差 | 先限速补，避免拖慢正常复制 | 慢节点会持续拉高 leader 的出带宽 |
快照的机制、截断边界与坑见 21.8 Raft：成员变更与快照。
反模式
| 反模式 | 后果 |
|---|---|
| follower 先 ACK 再落盘 | 掉电后"已提交"的日志消失，共识变戏法 |
| 把 commitIndex 当 lastApplied（收到就执行） | 未提交的日志被应用到状态机，回滚时数据错乱 |
| 用多数派 matchIndex 提交旧任期条目 | 图 8 反例：已提交条目被覆盖 |
| 允许日志有洞（学 Paxos 的 slot） | Raft 的日志匹配与提交规则都假设连续，洞会让 commitIndex 失去意义 |
| leader 把客户端请求转给 follower 处理 | follower 不发起提交，请求悬挂 |
| 忽略慢节点 | 它长期落后 → 每次重启都要全量快照 |
| 不做幂等，指望共识去重 | 重试导致重复扣款/重复下单 |
自检
Q1 follower 在 prevLogIndex 处找不到条目，或 term 不匹配，它会怎么做？leader 又怎么反应？
▸ 答案：follower 拒绝这次 AppendEntries（返回失败），不做任何修改；leader 收到失败后把该 follower 的 nextIndex 减一重试，直到找到最后一个一致的 (index, term)，再从那里开始追加。实现上会用"冲突 term + 该 term 的首个 index"一次跳过整段，避免逐条回退的 O(n) 开销。
Q2 matchIndex = [6,6,6,4,3]，5 节点集群，leader 当前 term 4，日志 index 6 的 term 是 4。commitIndex 能推进到几？
▸ 答案：6。排序后中位数（第 3 大）是 6，且 index 6 的 term（4）等于当前 term，满足"多数派 + 当前任期"两条规则，可以提交并 apply 到 6。如果 index 6 的 term 是 2，即使多数派都有它也不能直接提交——必须等某个 term=4 的条目先提交，再间接带上它。
Q3 为什么 Raft 要求日志连续，而 Paxos 允许有洞？
▸ 答案：Raft 的提交规则依赖"多数派的 matchIndex 中位数"来推进 commitIndex，只有当 index 之前的条目都确定、且每个 follower 的日志是 leader 的前缀时，中位数才等价于"该 index 及之前都已被多数派持久化"。Paxos 每个 slot 独立决定，槽位可以先空着后续再填，所以不需要连续；代价是恢复与提交位置的计算复杂得多（要在多个 slot 上分别求多数）。
Q4 客户端超时重试，会不会在 Raft 里产生两条相同的日志？
▸ 答案：会。Raft 不去重（它只管日志的顺序与一致性）：leader 可能已经提交并 apply，但响应在返回途中丢失，客户端重试后同一条命令再走一遍日志。去重必须由业务层做——用请求 id/业务唯一键 + 幂等表（见 25.4 幂等设计与去重）。把"共识"当成"恰好一次"是常见误解。
Q5 3 节点集群，写延迟由哪几段组成？为什么加批能提高吞吐却不降低单条延迟？
▸ 答案：延迟 ≈ 一次 RTT（等多数派）+ 本地 fsync + apply。批处理把 N 条写摊到同一次 RTT 与同一次 fsync 上，所以吞吐随批大小近似线性上升；但每一条仍然要等"这一批"凑齐、等一次 RTT，所以单条延迟不降反升（还可能因为攒批而增加排队）。流水线能让吞吐继续上升，但单条延迟的下限仍是 RTT。