Raft如何维持日志一致性

记录自己在学习Raft过程中的一些理解
相关参考：
1.MIT6.824公开课：https://www.bilibili.com/video/BV16M4m1m7YP/
2.课程及实验：http://nil.csail.mit.edu/6.824/2020/schedule.html
3.Raft论文：http://nil.csail.mit.edu/6.824/2020/schedule.html

先看一种比较特殊的日志错乱情况

[1]左边表示服务器节点，分别是S1、S2、S3
[2]上边横轴表示日志索引，索引从1开始（日志索引与任期无关）
[3]中间方框代表日志，方框内的数字代表该日志是在哪个任期下产生的

一、导致这种日志错乱的一种情景

1. 初始情况，假设S3是term1的leader，term1下的第一个日志成功被S1、S2复制成功，但是第二个日志由于某些网络/故障问题使得S1没有复制成功，随后S3宕机重启，进入term2选举。
2. 在term2时，由S2成功获得多数选票（得到了自己和S1的），成为leader。但是term2的第一个日志还没来得及复制到S1、S3，S2就宕机了，进入term3选举。
3. 在term3时，由S3成功获得多数选票（得到了自己和S1的），成为leader。同样地。term3的第一个日志还没来得及复制到S1、S2，S3就宕机了，进入term4选举。
4. 此时进入term4，由S2成功获得多数选票（得到了自己和S1的），成为leader。系统后续将正常运行....

二、Raft的选举机制

在 Raft 协议中，一个候选人 (Candidate) 想要赢得Follower的选票，必须满足以下两个核心条件：

• Candidate 的任期号必须大于或等于 Follower 本地记录的最新任期号
• Candidate 的日志需要至少和Follower本地记录一样新，即：
  所以投票规则是：

1. 先比较任期号：Candidate最新的日志任期更高则投票，任期更低则拒绝
2. 任期相同的情况下，看最后一条日志的索引，Candidate索引>=Follower，则投票，否则拒绝

所以依据这个选举规则：

1. 在term2时，由S2成功获得多数选票（得到了自己和S1的）
2. 在term3时，由S3成功获得多数选票（得到了自己和S1的）
3. 在term4时，由S2成功获得多数选票（得到了自己和S1的）
   均是合理的

三、选举日志完整性保障

在Raft协议中，会保证：最终被选出的 Leader 必然包含了所有已提交（committed）的日志条目。
可以证明如下：

1. 已提交日志的特性： Raft 保证，任何已提交的日志条目 L_committed 必然存在于大多数节点的日志中。
2. Leader 选举约束： Raft的选举赢得选票的要求是 Candidate 的日志必须至少和 Follower 一样新。
3. 安全推论： 既然 已提交的日志 存在于多数节点中，那么一个 Candidate 想要获得多数选票，它必然需要从这个包含 已提交的日志 的多数派中获得选票。任何缺失 已提交的日志 的 Candidate 都会被包含 已提交的日志 的节点拒绝，因为它会被认为日志不如多数派节点完整。
4. 结论： 最终被选出的 Leader 必然拥有集群中所有已提交的日志条目。

这段话的逻辑，对于那些“已被复制到大多数，但尚未被任何 Leader 提交”的日志来说，也是适用的。
这是因为如果一个 日志条目 存在于大多数节点的日志中，但是仍然未被提交（部分节点的复制确认丢失、leader宕机等等情况），那么这样一个 日志条目 几乎不可能被回滚，因为它已经存在于多数派的log[]中，得到了多数派的认可，任何 Leader 都难以找到一个能覆盖它的多数派。

四、日志一致性的保证

回到最开始所描述的情况，此时S2被选为了term4的leader。一个 Leader（无论是新当选还是重启后再次当选）在赢得选举后，会重新初始化其内存中关于 Follower 进度的两个数组：

1. nextIndex[]： 对于每个 Follower，Leader 维护的下一条要复制给该 Follower 的日志条目索引。
   初始化值：初始化时所有follower的nextIndex都会被初始化为Leader 自己的最后一条日志索引 L_last 加 1。
   此时：S2的最后日志索引是3，那么所有 nextIndex[i] 都会被设置为4。
2. matchIndex[]： 对于每个 Follower，Leader 维护的该 Follower 已经成功复制的最高日志索引。
   初始化值： 都会被初始化为 0。

Leader 获取 Follower 进度（日志匹配）的过程：
Leader 获取 Follower 进度的过程，本质上是 Leader 通过不断发送 AppendEntries RPC 来试探 Follower 的日志匹配点，直到找到第一个匹配的索引为止。

---

步骤一：Leader 初始化 nextIndex
S2 赢得选举后，初始化 nextIndex[]，都设置为自己的 lastLogIndex + 1 = 3 + 1 = 4：

Follower	S2 初始nextIndex
S1	4
S2	4

(也就是S2初始时会很理想地认为自己的日志都已被其他follower复制成功)

---

步骤二：Leader 尝试发送（心跳/同步）
S2 发送 AppendEntries RPC。由于 nextIndex 都是 4，所以RPC 中的 prevLogIndex 参数是 3，prevLogTerm是 2（S2 索引 3 处的任期）。

🔹 S1 (日志落后) 的同步过程：

1. S2 尝试 ( nextIndex=4): 发送 RPC，要求 S1 必须拥有 prevLogIndex=3, prevLogTerm=2 的日志。
2. S1 拒绝: S1 日志只到索引 1。S1 在索引 3 找不到匹配日志。
3. S2 回退 nextIndex=3: S2 尝试发送 prevLogIndex=2, prevLogTerm=1 的 RPC。
4. S1 拒绝: S1 在索引 2 找不到匹配日志。
5. S2 回退 nextIndex=2: S2 尝试发送 prevLogIndex=1, prevLogTerm=1 的 RPC。
6. S1 匹配点: S1 接受！ 双方在 ( I=1, T=1 ) 处找到匹配点。
7. S2 同步 Log: S2 将 索引 2、3 的日志 ( T1, T2 ) 追加给 S1。
8. 结果: S1 日志更新为 ( I=1, T=1 ), ( I=2, T=1 ), ( I=3, T=2 )。S2 更新 matchIndex[S1]=3。

🔹 S3 (日志冲突) 的同步过程：

1. S2 尝试 ( nextIndex=4): 发送 RPC，要求 S3 必须拥有 prevLogIndex=3, prevLogTerm=2 的日志。
2. S3 拒绝: S3 在索引 3 的日志任期是 T3，与 S2 期望的 T2 不匹配。
3. S2 回退 nextIndex=3: S2 尝试发送 prevLogIndex=2, prevLogTerm=1 的 RPC。
4. S3 匹配点: S3 接受！ S3 确认索引 2 的日志任期是 T1，与 S2 匹配。
5. S2 同步 Log 并覆盖: S2 从匹配点后开始发送日志，即发送 索引 3 的日志 ( T2 )。
   • S3 会 删除 其冲突日志 ( I=3, T=3 )。
   • S3 追加 Leader 发送的 ( I=3, T=2 )。
6. 结果: S3 日志更新为 ( I=1, T=1 ), ( I=2, T=1 ), ( I=3, T=2 )。S2 更新 matchIndex[S3]=3。

---

最终同步状态
经过多次心跳后，S1、S2、S3 的日志都将保持一致：

term3的日志将被leader丢弃，但是因为它并没有被复制到大多数节点，所以自然也可以被丢弃