Raft 共识协议 | Codeboy's Blog

形式陈述

Raft 在固定配置的crash-stop或带持久存储的 crash-recovery 节点间实现复制日志，等价于按日志索引连续解决共识实例。节点在 follower、candidate 与 leader 角色间切换；任期是单调递增的逻辑编号，收到更高任期消息便更新任期并退为 follower。

每个节点在回复相关 RPC 前持久化 currentTerm、votedFor 与日志条目 (term,command)。commitIndex 与 lastApplied 可以从 leader 信息和持久日志恢复。若重启后遗忘任期或投票，节点可能在同一任期投两票；若遗忘日志，选举时便会谎报自己的证据，两者都会破坏安全证明。

选举与日志复制

Candidate 递增任期并请求投票。节点每任期最多投一票，而且只投给日志至少与自己一样新的候选者；新旧关系按 (lastLogTerm,lastLogIndex) 字典序比较，先比较最后条目的任期，同任期才比较索引。候选者取得多数quorum后成为该任期 leader。任意两个多数相交，加上一任期一票，推出每任期至多一个 leader。

Leader 用 AppendEntries(prevLogIndex,prevLogTerm,entries,leaderCommit) 复制日志。Follower 只有在 prevLogIndex 处任期匹配时才接受；若新条目与本地同索引条目任期冲突，就删除该处起的后缀再追加。由此得到日志匹配性质：若两份日志在同一索引有相同任期，则该索引及之前的全部条目相同。

提交规则

当前 leader 只能用“已复制到多数”直接推进当前任期条目：若某个 $N>\texttt{commitIndex}$ 满足多数节点的 matchIndex 至少为 $N$ ，且 log[N].term == currentTerm，leader 才把 commitIndex 推到 $N$ 。该动作同时提交 $N$ 之前仍在日志中的旧任期条目。Follower 从 leaderCommit 学到提交位置，并严格按索引顺序应用 committed 前缀。

直觉

Raft 让选举证据与复制证据在多数交点相遇。日志新旧限制使含有更高任期或更长同任期前缀的节点阻止过时候选者获多数，AppendEntries 检查再把 leader 的前缀向 followers 扩散。两条规则结合可推出 leader completeness：一旦条目按 Raft 规则 committed，每个更高任期 leader 都含有它；再结合日志匹配，任何两个节点在同一索引应用的命令相同。

“按 Raft 规则”中的当前任期条件不可省略。旧任期条目即使后来出现在多数日志上，少数节点仍可能持有同索引、更高任期的冲突条目；该节点的日志在下一次选举中反而更新。当前 leader 先提交一个本任期条目后，支持它的多数拥有不低于本任期的日志证据，任何缺少该前缀的候选者都无法再凑齐多数。于是旧前缀随本任期条目间接提交。

例子与边界

五节点集群可容忍两个 crash-stop。旧 leader 网络隔离后可能继续接收请求，却无法获得三个节点的复制确认，因此不能提交；它稍后收到更高任期消息便退位。安全性不依赖超时长短，分区只会让不含多数的一侧失去进展。

Figure 8 式轨迹说明旧任期边界。任期 2 的 leader 只把 $x$ 写到两个节点；任期 3 的另一 leader 在少数节点同一索引写入 $y$ 。原 leader 在任期 4 重新当选并把旧条目 $x$ 补到三个节点。若仅凭“ $x$ 现在位于多数”就宣布提交，随后持有任期 3 条目 $y$ 的候选者仍因最后日志任期更高而可能在任期 5 获选，并覆盖 $x$ 。若任期 4 leader 先追加并把本任期条目复制到多数，这个本任期证据会阻止上述候选者，且连带提交 $x$ 。

Raft 旧任期条目不能仅凭多数直接提交 — 左侧旧任期条目 x 已位于三个节点，却因不是当前任期条目而不能直接提交；右侧当前任期条目 z 复制到多数后，同时提交 z 与旧前缀 x。

若选举实现只比较日志长度而忽略最后日志任期，较长却过时的候选者可能获胜；若比较顺序颠倒，同样会破坏 leader completeness。快照必须携带 last included index/term，才能继续参与相同的匹配与新旧判断。

推论与应用

Raft 用任期、领导者选举、投票限制和 AppendEntries 具体实现复制日志的提交接口，再由复制状态机应用 committed 前缀。这一接口可写成实现状态到抽象日志状态的精化关系：冲突尾部和重试属于实现行为，已提交前缀必须映到同一抽象历史。模型检查可以发现遗漏当前任期条件或持久化顺序后的短反例，却不能替代抽象映射。

在固定配置中， $2f+1$ 个节点可承受 $f$ 个崩溃并仍凑齐多数。活性还要求多数正确节点可达、消息与处理最终足够稳定，并让随机化选举超时最终产生一个未被竞争者打断的 leader；这通常以部分同步表述。完全异步调度仍可不断制造分票或任期更替，而不破坏任何安全性质。

成员变更要用 joint consensus 让过渡期决定同时取得旧、新配置所需的 quorum，不能直接把成员列表瞬间替换。客户端去重、线性一致读、磁盘写入屏障与快照安装仍是完整服务的额外义务，不能从日志匹配性质直接推出。

参考资料

Diego Ongaro and John Ousterhout, “In Search of an Understandable Consensus Algorithm,” USENIX ATC, 2014，pp. 305–319，§§5.2–5.4 and Fig. 8。
Diego Ongaro, Consensus: Bridging Theory and Practice, PhD dissertation, Stanford University, 2014，Chs. 3–4。

形式陈述 ​

选举与日志复制 ​

提交规则 ​

反向链接

形式陈述

选举与日志复制

提交规则