3.1 Raft：选举、日志复制与提交

共识让多个节点在部分失败和消息延迟下，对同一条复制日志形成不可冲突的决定。复制状态机从相同初始状态出发，把确定性命令按相同顺序应用，就能得到相同状态。命令若依赖当前时间或随机数，应把选定的值写入日志；各副本自己抽签，日志再整齐也救不了结果。

Raft 将节点组织为 Follower、Candidate 和 Leader，并用单调增加的 term 区分领导时期。

多数派是交集基础

一个由 2f + 1 个投票成员组成的集群，在剩余成员能够互相通信并持续处理请求的条件下，可以容忍最多 f 个成员不可用。例如 5 个成员需要 3 票，可容忍 2 个不可用。

把节点从 3 增加到 4 不会提升故障容忍度，仍需 3 票，却增加复制成本。见证者、学习者和非投票副本的语义取决于具体实现，不能只数进程数量。

状态和持久数据

每个节点至少维护：

• currentTerm、votedFor：变更后须在依赖它们的 RPC 响应或消息发出前持久化；
• log entries：每条含 index、term 和 command，确认复制成功前必须持久化；
• commitIndex、lastApplied；
• Leader 为每个 follower 维护的 nextIndex、matchIndex。

commitIndex 等进度可以按协议重建；若状态机本身持久化，lastApplied 必须与状态机数据协调恢复，不能把已经生效的增量再执行一次。状态机只能按 index 顺序应用已提交条目。崩溃恢复后，已持久化投票和日志不能丢失，否则可能破坏安全性。

Leader 选举

Follower 在随机化选举超时内没有收到有效 Leader 通信时：

1. 增加 term，成为 Candidate；
2. 持久化新的 term 和给自己的投票；
3. 向其他成员发送 RequestVote；
4. 获得当前 term 的多数票后成为 Leader；
5. 收到更高 term RPC 时退回 Follower。

每个成员在一个 term 最多投一票。投票还要求 Candidate 的日志至少与投票者一样新：先比较最后条目的 term，再比较 index。例如末条为 (term=5, index=8) 的日志，比 (term=4, index=20) 更新，日志更长不代表更有资格当选。Candidate 收到当前 term 的有效 Leader AppendEntries 时也应退回 Follower。

随机超时减少平票概率，不保证永不平票。网络最终恢复及时后，新一轮通常会选出 Leader；持续分区或极端抖动期间，系统可以长期没有 Leader，同时保持安全。

AppendEntries 同时复制和校验前缀

Leader 接收客户端命令后先追加本地日志，再向 Followers 发送：

term
leaderId
prevLogIndex
prevLogTerm
entries[]
leaderCommit

Follower 先拒绝过期 term，再检查 prevLogIndex/prevLogTerm。前缀不匹配时拒绝请求，Leader 回退 nextIndex 寻找共同前缀。前缀匹配后，只在某条新条目与本地同 index 条目的 term 不同时，从冲突条目开始删除本地未提交后缀，再追加缺失条目。已经匹配的条目不重写，未被这次请求覆盖的后缀也不随意截断。

AppendEntries 空 entries 时也承担心跳和 commitIndex 传播，仍需校验前缀。提交位置只能推进到 leaderCommit 与本次请求确认匹配的末尾位置两者中的较小者，不能越过已校验前缀。

例如 Follower 已有 index 1–5，收到一条延迟心跳，只确认到 index 3。它不能因此删除 4、5，也不能凭这条心跳把尚未验证的 4、5 提交。消息迟到不是日志变短的理由。

提交规则的关键限制

Leader 可以通过多数副本确认，直接推进“当前 term 的条目”到已提交。某个当前 term 条目一旦提交，它之前的日志也随之前缀被视为提交。

不能仅凭旧 term 条目当前存在于多数副本，就直接按计数提交它。Raft 通过提交一个当前 term 条目，间接确认此前条目。

设五节点 A–E：A 在 term 2 写入 x，只留在自己；随后 E 在 term 3 当选，在同一 index 写入另一个值 y，也只留在自己。A 在 term 4 重新当选，把旧 term 的 x 复制到 A、B、C，看起来已有多数。可是一旦 A 失联，E 的末条 term 3 仍比 C 的 term 2 新，E 能靠 C、D、E 当选并覆盖 x。这说明那次“多数”还不能证明 x 已提交。若 A 先把 term 4 的新条目复制并提交到多数，E 才会被投票时的日志新旧检查挡住。

客户端命令
  → Leader append
  → 多数派持久化
  → Leader commit
  → 状态机 apply
  → 返回客户端

实现何时向客户端响应必须与持久化和状态机语义一致。响应前 Leader 崩溃会产生结果未知，客户端仍需要请求 ID 去重。

日志安全来自选举限制与多数交集

已提交条目（或包含其效果的快照）被多数派保存。未来 Leader 必须从另一个多数派获得投票，两者至少相交一个节点；候选日志新旧判断阻止缺少已提交前缀的节点获胜。

直觉有助理解，但生产实现不能只凭直觉省略 fsync、term 持久化、冲突处理或恢复测试。

下一课讨论线性一致读、成员变更、快照和 Raft 的运营边界。

参考资料

• Ongaro, Ousterhout, In Search of an Understandable Consensus Algorithm
• Raft Visualization