核心目标Raft 的日志寻找匹配本质上是在寻找 Leader 和 Follower 的最大公共前缀找到最大的 index M使得 Leader.log[M].term Follower.log[M].term根据 Raft 的日志匹配性质只要同一位置的index term相同那么该位置之前的日志也应相同。找到M后Leader 就可以把M1之后的日志发送给 Follower。(usenix.org)最朴素的回退Leader 为每个 Follower 保存nextIndex[i]它表示下一条准备发送的日志位置。因此每次发送prevLogIndex nextIndex[i] - 1 prevLogTerm Leader.log[prevLogIndex].term entries Leader.log[nextIndex[i] ...]如果 Follower 回复不匹配最简单的处理是nextIndex[i]--;然后重新发送。假设Leader.nextIndex 1001 真正匹配位置 500那么可能需要1000 → 999 → 998 → ... → 501也就是大约 500 次失败 RPC。论文中的基础算法就是逐项递减优化版本则允许一次跳过整个冲突任期。为什么可以按 Term 跳跃Raft 日志中的任期具有分段特征index: 1 2 3 | 4 5 | 6 7 8 | 9 10 term: 1 1 1 | 2 2 | 3 3 3 | 5 5同一任期生成的日志通常连续出现。如果 Follower 告诉 Leader你探测的位置属于我的 term4 term4 在我的日志中从 index20 开始Leader 就没有必要对 Follower 的整个 term 4 区间逐个尝试可以直接跳到这个任期的边界。优化后失败 RPC 数量通常从和冲突日志条数成正比降为和冲突任期段数量成正比标准加速回复一个完整的快速回退回复通常包含struct AppendEntriesReply { int term; bool success; int conflictTerm; int conflictIndex; };两个关键字段conflictTerm Follower 在 prevLogIndex 位置上的任期。 conflictIndex conflictTerm 在 Follower 日志中第一次出现的位置。Follower 有两种主要失败情况。情况一Follower 日志太短例如Leader 发送 prevLogIndex 10 Follower lastLogIndex 6Follower 根本不存在日志 10因此返回conflictTerm 无 conflictIndex 7Leader直接执行nextIndex[follower] 7;这样一次就从 11 跳到 7而不是执行11 → 10 → 9 → 8 → 7当前项目已经实现了这种优化reply-set_updatenextindex( getLastLogIndex() 1 );Leader 收到后直接更新m_nextIndex[server]。情况二下标存在但 Term 不同假设 Leader 探测prevLogIndex 12 prevLogTerm 5Follower 的日志 12 存在但属于Follower.log[12].term 4Follower 不只是返回失败而是向前扫描整个 term 4index: 8 9 10 11 12 term: 4 4 4 4 4最终返回conflictTerm 4 conflictIndex 8表示我的日志 12 属于 term 4并且这一段 term 4 从日志 8 开始。Leader 如何利用两个字段Leader收到conflictTerm4后先在自己的日志里找 term 4。如果 Leader 也有 term 4Leader 最后一个 term 4 日志位于 index6则设置nextIndex[follower] 6 1;下一次发送prevLogIndex 6 prevLogTerm 4为什么找 Leader 中 term 4 的最后一个位置因为这是双方最有希望匹配的最靠后位置。如果匹配成功可以保留更多已有日志减少重复传输。如果 Leader 完全没有 term 4则设置nextIndex[follower] conflictIndex;也就是直接跳到 Follower 的 term 4 之前让 Leader 日志覆盖这段冲突日志。完整例子假设双方日志为index: 1 2 3 4 5 6 7 8 9 10 11 12 Leader: 1 1 1 2 2 3 3 5 5 5 5 5 Follower: 1 1 1 2 2 2 2 2 4 4 4 4Leader 初始nextIndex 13 prevLogIndex 12 prevLogTerm 5Follower 在日志 12 看到 term 4返回conflictTerm 4 conflictIndex 9Leader没有 term 4于是nextIndex 9第二次探测prevLogIndex 8 Leader.log[8].term 5 Follower.log[8].term 2Follower返回conflictTerm 2 conflictIndex 4Leader存在 term 2并且最后一个 term 2 位于日志 5所以标准算法设置nextIndex 6 prevLogIndex 5双方日志 5 都是 term 2匹配成功。Leader随后发送日志612。整个过程只有两次失败13 → 9 → 6逐项回退则可能需要13 → 12 → 11 → 10 → 9 → 8 → 7 → 6当前项目实现了哪一部分Follower 的冲突处理代码逻辑是int conflictTerm term(args-prevlogindex()); reply-set_updatenextindex( args-prevlogindex() ); for (int index args-prevlogindex(); index snapshotIndex; --index) { if (term(index) ! conflictTerm) { reply-set_updatenextindex(index 1); break; } }也就是1. 取得 Follower 在 prevLogIndex 上的本地 term。 2. 向前扫描。 3. 找出该 term 第一次出现的位置。 4. 通过 updateNextIndex 返回这个位置。Leader端则直接执行m_nextIndex[server] reply-updatenextindex();所以当前实现能够一次跳过 Follower 的整个冲突任期而不是只执行nextIndex--。