Raft 论文完全指南

        客户端请求
            |
            v
+-------------------+     +-------------------+     +-------------------+
|     Server 1      |     |     Server 2      |     |     Server 3      |
|                   |     |                   |     |                   |
| +---------------+ |     | +---------------+ |     | +---------------+ |
| | 共识模块      | |<--->| | 共识模块      | |<--->| | 共识模块      | |
| +-------+-------+ |     | +-------+-------+ |     | +-------+-------+ |
|         |         |     |         |         |     |         |         |
| +-------v-------+ |     | +-------v-------+ |     | +-------v-------+ |
| | 复制日志      | |     | | 复制日志      | |     | | 复制日志      | |
| | x←3 y←1 x←5  | |     | | x←3 y←1 x←5  | |     | | x←3 y←1 x←5  | |
| +-------+-------+ |     | +-------+-------+ |     | +-------+-------+ |
|         |         |     |         |         |     |         |         |
| +-------v-------+ |     | +-------v-------+ |     | +-------v-------+ |
| | 状态机        | |     | | 状态机        | |     | | 状态机        | |
| | x=5, y=1     | |     | | x=5, y=1     | |     | | x=5, y=1     | |
| +---------------+ |     | +---------------+ |     | +---------------+ |
+-------------------+     +-------------------+     +-------------------+

                         收到多数选票
                    +-------------------+
                    |                   |
                    |                   v
+----------+    超时开始选举    +------------+    选举成功    +----------+
| Follower |  ------------->  | Candidate  |  ---------->  |  Leader  |
+----------+                  +------------+               +----------+
     ^                             |                            |
     |     发现更高 term           |    发现更高 term            |
     |     或新 Leader             |    或新 Leader              |
     +-----------------------------+----------------------------+

  Term 1       Term 2       Term 3       Term 4       Term 5
|---------|  |---------|  |---------|  |---------|  |---------|
| 选举 |  正常运行  | 选举 |  正常运行  | 选举 |选举| 选举 |  正常运行  |
| S1当选|  S1是Leader|  S3当选|  S3是Leader| 失败 |失败| S5当选|  S5是Leader|
|---------|  |---------|  |---------|  |---------|  |---------|

步骤 1：所有节点启动为 Follower，Term = 0
  S1[Follower] S2[Follower] S3[Follower] S4[Follower] S5[Follower]

步骤 2：S1 的选举超时先到期，转为 Candidate，Term = 1
  S1[Candidate, T=1] → 向 S2-S5 发送 RequestVote

步骤 3：S2, S3, S4 投票给 S1（加上 S1 自己的票 = 4 票，超过多数 3）
  S1 成为 Leader

步骤 4：S1 立即向所有节点发送心跳（空的 AppendEntries）
  S1[Leader] → 心跳 → S2, S3, S4, S5

步骤 5：客户端发送命令 "x←3" 给 S1
  S1 追加到本地日志 → 向 S2-S5 发送 AppendEntries

步骤 6：S2, S3, S4 成功追加（多数确认）
  S1 提交该日志 → 应用到状态机 → 回复客户端

时间线：
Leader S1:     ♥ ---- ♥ ---- ♥ ---- [崩溃]
Follower S3:   收到   收到   收到   等待......超时！→ 开始选举
               |                     |<--- election timeout --->|

步骤 1：S3 的选举超时先到期
  S3: currentTerm = 1 → 2（自增）
  S3: votedFor = S3（投票给自己）
  S3: 状态 = Candidate
  S3: 重置选举超时
  S3: 向 S1, S2, S4, S5 发送 RequestVote(term=2, candidateId=S3, ...)

步骤 2：各节点收到 RequestVote
  S1: [已崩溃，无响应]
  S2: term=2 > currentTerm=1，更新 term=2
      votedFor=null，S3 的日志至少一样新 → 投票给 S3 ✓
  S4: term=2 > currentTerm=1，更新 term=2
      votedFor=null，S3 的日志至少一样新 → 投票给 S4 ✓
  S5: term=2 > currentTerm=1，更新 term=2
      votedFor=null，S3 的日志至少一样新 → 投票给 S3 ✓

步骤 3：S3 收到 S2, S4, S5 的投票（加上自己 = 4 票，多数 = 3）
  S3: 状态 = Leader
  S3: 初始化 nextIndex[] 和 matchIndex[]
  S3: 立即向所有节点发送心跳

S1 超时：237ms
S2 超时：189ms  ← 最先超时，率先发起选举
S3 超时：291ms
S4 超时：162ms  ← 第二个超时（但 S2 可能已经赢得选举）
S5 超时：253ms

S1 的日志：[T1, T1, T2, T3]      最后条目：index=4, term=3
S2 的日志：[T1, T1, T2, T2, T2]  最后条目：index=5, term=2
S3 的日志：[T1, T1, T3]          最后条目：index=3, term=3

比较结果：
  S1 vs S2: S1 更新（term 3 > term 2）
  S1 vs S3: S1 更新（term 相同，index 4 > index 3）
  S3 vs S2: S3 更新（term 3 > term 2）

broadcastTime  <<  electionTimeout  <<  MTBF

broadcastTime：  发一轮 RPC 的平均时间    （通常 0.5ms - 20ms）
electionTimeout：选举超时时间              （通常 150ms - 300ms）
MTBF：           服务器平均无故障间隔时间   （通常数月）

日志示例（5 节点集群，Leader 是 S1）：

index:   1      2      3      4      5      6      7
       +------+------+------+------+------+------+------+
S1:    | x←3  | y←1  | x←5  | y←9  | z←2  | x←1  | y←3  |  Leader
       | T=1  | T=1  | T=1  | T=2  | T=3  | T=3  | T=3  |
       +------+------+------+------+------+------+------+
S2:    | x←3  | y←1  | x←5  | y←9  | z←2  | x←1  |       |  Follower
       | T=1  | T=1  | T=1  | T=2  | T=3  | T=3  |       |
       +------+------+------+------+------+------+       +
S3:    | x←3  | y←1  | x←5  | y←9  | z←2  |              |  Follower
       | T=1  | T=1  | T=1  | T=2  | T=3  |              |
       +------+------+------+------+------+              +
S4:    | x←3  | y←1  | x←5  | y←9  | z←2  | x←1  | y←3  |  Follower
       | T=1  | T=1  | T=1  | T=2  | T=3  | T=3  | T=3  |
       +------+------+------+------+------+------+------+
S5:    | x←3  | y←1  | x←5  |                             |  Follower
       | T=1  | T=1  | T=1  |                             |
       +------+------+------+                             +

                              ^commitIndex = 5
                        （S1, S2, S3, S4 都有 index 5 = 多数）

步骤 1：Leader 追加到本地日志
  S1 的日志末尾追加：{index=8, term=3, command="z←7"}

步骤 2：Leader 并行发送 AppendEntries 给所有 Follower
  S1 → S2: AppendEntries(prevLogIndex=7, prevLogTerm=3, entries=[{8,T3,"z←7"}])
  S1 → S3: AppendEntries(prevLogIndex=5, prevLogTerm=3, entries=[{6,T3,"x←1"},{7,T3,"y←3"},{8,T3,"z←7"}])
  S1 → S4: AppendEntries(prevLogIndex=7, prevLogTerm=3, entries=[{8,T3,"z←7"}])
  S1 → S5: AppendEntries(prevLogIndex=3, prevLogTerm=1, entries=[{4,T2,"y←9"},{5,T3,"z←2"},...,{8,T3,"z←7"}])

步骤 3：Follower 接收并追加
  S2: prevLogIndex=7 处没有条目（日志只到 6）→ 返回 false
      Leader 递减 nextIndex[S2]，下次重试
  S3: prevLogIndex=5 匹配 → 追加 entries → 返回 success
  S4: prevLogIndex=7 匹配 → 追加 entry → 返回 success
  S5: prevLogIndex=3 匹配 → 追加 entries → 返回 success

步骤 4：Leader 收到多数确认（S3, S4, S5 成功 + S1 自己 = 4/5）
  commitIndex 更新到 8
  （注意：还需要满足 log[8].term == currentTerm 的条件）

步骤 5：Leader 应用 log[6..8] 到状态机，回复客户端

步骤 6：下一次心跳或 AppendEntries 携带新的 leaderCommit
  Follower 更新自己的 commitIndex，应用到状态机

Leader 的日志（Term=8）：
index:   1    2    3    4    5    6    7    8    9    10   11   12
       +----+----+----+----+----+----+----+----+----+----+----+----+
Leader | T1 | T1 | T1 | T4 | T4 | T5 | T5 | T6 | T6 | T6 |    |    |
       +----+----+----+----+----+----+----+----+----+----+----+----+

可能的 Follower 状态：

(a)    | T1 | T1 | T1 | T4 | T4 | T5 | T5 | T6 | T6 |         缺少条目
       +----+----+----+----+----+----+----+----+----+

(b)    | T1 | T1 | T1 | T4 |                                    缺少更多条目
       +----+----+----+----+

(c)    | T1 | T1 | T1 | T4 | T4 | T5 | T5 | T6 | T6 | T6 | T6 | 多余条目
       +----+----+----+----+----+----+----+----+----+----+----+

(d)    | T1 | T1 | T1 | T2 | T2 | T2 | T3 | T3 | T3 | T3 | T3 | 不同的条目
       +----+----+----+----+----+----+----+----+----+----+----+

(e)    | T1 | T1 | T1 | T4 | T4 | T4 | T4 |                    缺少 + 不同
       +----+----+----+----+----+----+----+

(f)    | T1 | T1 | T1 | T2 | T2 | T2 | T3 | T3 | T3 | T3 | T3 | T3 | 更长且不同
       +----+----+----+----+----+----+----+----+----+----+----+----+

Leader 日志：[T1, T1, T4, T4, T5, T5, T6, T6, T6]
Follower 日志：[T1, T1, T4, T4, T4]  （index 5 不一致）

修复过程：
  1. Leader 初始化 nextIndex[follower] = 10（Leader 最后日志 + 1）
  2. 发送 AppendEntries(prevLogIndex=9, ...)
     Follower 日志只到 5 → 失败
  3. nextIndex-- = 9，发送 AppendEntries(prevLogIndex=8, ...)
     失败
  ... 反复递减 ...
  4. nextIndex = 5，发送 AppendEntries(prevLogIndex=4, prevLogTerm=T4, ...)
     Follower 的 index 4 是 T4 → 匹配！
  5. Follower 删除 index 5 及之后的日志（T4 那条冲突的）
     追加 Leader 的 index 5 起的所有条目
  6. 修复完成，Follower 的日志与 Leader 一致

// Follower 拒绝时：
reply.ConflictTerm = rf.log[args.PrevLogIndex].Term
reply.ConflictIndex = // 找到 ConflictTerm 的第一条日志 index

// Leader 收到拒绝时：
if leader 的日志中找到 ConflictTerm {
    nextIndex[follower] = leader 中该 term 最后一条日志的 index + 1
} else {
    nextIndex[follower] = reply.ConflictIndex
}

初始状态（5 节点，Leader S1 在 Term 2）：
  S1: [T1, T2]   Leader（已将 T2 复制到 S1, S2, S3 = 多数 → 已提交）
  S2: [T1, T2]
  S3: [T1, T2]
  S4: [T1]
  S5: [T1]

如果没有选举限制，假设 S1 崩溃后 S5 当选 Term 3 的 Leader：
  S5 的日志只有 [T1]
  S5 在 index 2 写入新的 T3 日志
  S5 把 T3 日志复制给 S4 和 S3
  结果：S3 的 index 2 从 T2 被覆盖为 T3

  问题：已提交的 T2 日志被覆盖了！违反安全性！

步骤 (a)：S1 是 Term 2 的 Leader，在 index 2 写入 T2 日志
         只复制给了 S2（还没有多数确认）

  index:    1    2
  S1:      [T1] [T2]   ← Leader (Term 2)
  S2:      [T1] [T2]
  S3:      [T1]
  S4:      [T1]
  S5:      [T1]


步骤 (b)：S1 崩溃。S5 成为 Term 3 的 Leader
         （S5 得到 S3, S4, S5 的投票 — S3, S4 的日志不比 S5 新）
         S5 在 index 2 写入 T3 日志

  index:    1    2
  S1:      [T1] [T2]   ← 崩溃
  S2:      [T1] [T2]
  S3:      [T1]
  S4:      [T1]
  S5:      [T1] [T3]   ← Leader (Term 3)


步骤 (c)：S5 崩溃。S1 重启，成为 Term 4 的 Leader
         （S1 得到 S1, S2, S3 的投票 — S1 日志最新）
         S1 开始复制日志，把 index 2（T2）复制给了 S3
         现在 T2 在 index 2 出现在 S1, S2, S3 上 = 多数

  index:    1    2    3
  S1:      [T1] [T2] [T4]  ← Leader (Term 4)，index 3 是新的 T4 日志
  S2:      [T1] [T2]
  S3:      [T1] [T2]       ← 刚从 S1 复制了 T2
  S4:      [T1]
  S5:      [T1] [T3]       ← 崩溃


关键问题：此时 S1 能否提交 index 2 (T2) 的日志？

答案是 不能！原因见步骤 (d)。


步骤 (d)：如果 S1 提交了 index 2 然后崩溃，S5 可能重新当选
         S5 成为 Term 5 的 Leader
         （S5 得到 S3(?), S4, S5 的投票 — S5 的最后日志 T3 > S3 的 T2）
         S5 把自己的 index 2 (T3) 复制给所有节点

  index:    1    2
  S1:      [T1] [T3]   ← 被覆盖！
  S2:      [T1] [T3]   ← 被覆盖！
  S3:      [T1] [T3]   ← 被覆盖！
  S4:      [T1] [T3]
  S5:      [T1] [T3]   ← Leader (Term 5)

  灾难：已提交的 T2 日志被 T3 覆盖了！


步骤 (e)：正确的做法 — S1 不直接提交 T2，而是先提交 T4 的日志
         当 index 3 (T4) 被多数确认并提交时，index 2 (T2) 也被间接提交
         此后 S5 不可能当选（S5 的日志 T3 < 任何拥有 T4 的节点）

  index:    1    2    3
  S1:      [T1] [T2] [T4]  ← Leader (Term 4)
  S2:      [T1] [T2] [T4]
  S3:      [T1] [T2] [T4]  ← T4 已被多数确认
  S4:      [T1]
  S5:      [T1] [T3]

  现在 index 2 和 3 都是安全的：
  S5 不可能当选（S1/S2/S3 的日志都比 S5 新，T4 > T3）

// 在 Leader 更新 commitIndex 时：
for n := rf.commitIndex + 1; n <= lastLogIndex; n++ {
    if rf.log[n].Term != rf.currentTerm {
        continue  // 跳过：不能直接提交旧任期的日志
    }
    count := 1
    for i := range rf.peers {
        if i != rf.me && rf.matchIndex[i] >= n {
            count++
        }
    }
    if count > len(rf.peers)/2 {
        rf.commitIndex = n  // 提交当前任期日志，同时间接提交之前所有日志
    }
}

1. 如果 term < currentTerm，返回 false
   → 拒绝过期 Leader 的请求

2. 如果日志中 prevLogIndex 处没有 term 为 prevLogTerm 的条目，返回 false
   → 一致性检查失败，需要 Leader 回退 nextIndex

3. 如果已有的日志条目和新条目冲突（相同 index 但不同 term），
   删除该条目及其之后的所有条目
   → 清除不一致的日志（注意：只在冲突时才删除！）

4. 追加日志中没有的新条目
   → 正常追加

5. 如果 leaderCommit > commitIndex，
   设 commitIndex = min(leaderCommit, 最后一条新条目的 index)
   → 更新提交进度

1. 如果 term < currentTerm，返回 false
   → 拒绝过期候选人

2. 如果 votedFor 为 null 或 candidateId，
   且候选人的日志至少和自己一样新，
   则投票给该候选人
   → 每个任期只投一票，且只投给日志足够新的候选人

- 如果 commitIndex > lastApplied：
    lastApplied++
    把 log[lastApplied] 应用到状态机
  → 确保已提交的日志最终被执行

- 如果收到的 RPC 请求或响应中 term > currentTerm：
    currentTerm = term
    转变为 Follower
  → 发现更高任期，立即退位（适用于所有角色）

- 响应来自 Candidate 和 Leader 的 RPC
  → Follower 是纯被动的

- 如果选举超时期间没有收到 Leader 的 AppendEntries，
  也没有投票给任何 Candidate：
    转变为 Candidate
  → Leader 可能崩溃了，发起新选举

- 转变为 Candidate 时：
    currentTerm++
    votedFor = 自己
    重置选举超时计时器
    向所有其他节点发送 RequestVote
  → 开始竞选

- 如果收到多数节点的投票：
    成为 Leader
  → 选举成功

- 如果收到新 Leader 的 AppendEntries（term >= currentTerm）：
    转变为 Follower
  → 别人已经当选

- 如果选举超时：
    开始新一轮选举（重新递增 term）
  → 本轮选举失败（可能分裂投票），重试

- 选举后立即向所有节点发送空的 AppendEntries（心跳），之后定期发送
  → 建立权威，防止其他节点发起选举

- 如果收到客户端命令：
    追加到本地日志
    在日志被提交后响应客户端
  → 处理客户端请求

- 如果 lastLogIndex >= nextIndex[i]：
    向 Follower i 发送 AppendEntries（从 nextIndex[i] 开始的日志）
  → 推进 Follower 的日志

- 如果 AppendEntries 成功：
    更新 nextIndex[i] = 发送的最后一条日志 index + 1
    更新 matchIndex[i] = nextIndex[i] - 1
  → 记录 Follower 的复制进度

- 如果 AppendEntries 因为日志不一致而失败：
    递减 nextIndex[i]，重试
  → 回退找到一致点

- 如果存在 N 使得：
    N > commitIndex
    且多数 matchIndex[i] >= N
    且 log[N].term == currentTerm
  则 commitIndex = N
  → 提交新日志（注意 term 检查！这就是 Figure 8 的规则）

假设集群从 3 节点 {S1,S2,S3} 扩展到 5 节点 {S1,S2,S3,S4,S5}

某个时刻，部分节点已切换到新配置，部分还在旧配置：

  旧配置 {S1,S2,S3}：          新配置 {S1,S2,S3,S4,S5}：
  多数 = 2                     多数 = 3

  S1: 旧配置  ←┐               S3: 新配置  ←┐
  S2: 旧配置  ←┘ S1+S2=多数    S4: 新配置  ←┤ S3+S4+S5=多数
               → S1 当选       S5: 新配置  ←┘
                                → S3 当选

  结果：S1 和 S3 同时是 Leader！违反安全性！

时间线：
         C_old              C_old,new            C_new
         旧配置              联合配置              新配置
  --------|---------------------|---------------------|--------
          Leader 提交          Leader 提交
          C_old,new 日志       C_new 日志

+----------------------------------------------------------+
|                        快照                                |
|                                                          |
|  lastIncludedIndex = 5    （快照覆盖到的最后日志 index）    |
|  lastIncludedTerm  = 3    （该 index 对应的 term）         |
|                                                          |
|  状态机状态：                                              |
|    x = 5                                                 |
|    y = 1                                                 |
|    z = 9                                                 |
|                                                          |
|  集群配置（最新的）                                        |
+----------------------------------------------------------+

快照之后保留的日志：
index:   6      7      8      9
       +------+------+------+------+
       | T=3  | T=3  | T=4  | T=4  |
       +------+------+------+------+

丢弃的日志（已被快照覆盖）：
index:   1      2      3      4      5
       [不再保留]

客户端                        集群
  |
  |--- 请求 ---> S3 (Follower)
  |<-- 拒绝+Leader地址 ---    S3 告诉客户端 "Leader 是 S1"
  |
  |--- 请求 ---> S1 (Leader)
  |<-- 响应 ---               正常处理
  |
  |--- 请求 ---> S1 (已崩溃)
  |    (超时)
  |--- 随机选一个节点重试 ---> S4 (Follower)
  |<-- 拒绝+Leader地址 ---    S4 告诉客户端 "Leader 是 S2"（新Leader）
  |--- 请求 ---> S2 (Leader)
  |<-- 响应 ---

type Command struct {
    ClientId  int64  // 客户端唯一标识
    SeqNum    int64  // 单调递增的序列号
    Op        string // 操作内容
}

// 服务器端去重表
type DedupTable map[int64]DedupEntry  // key: ClientId

type DedupEntry struct {
    SeqNum int64       // 该客户端最后处理的序列号
    Result interface{} // 该命令的执行结果
}

// 应用日志到状态机时：
func (sm *StateMachine) Apply(cmd Command) interface{} {
    entry := sm.dedupTable[cmd.ClientId]
    if cmd.SeqNum <= entry.SeqNum {
        return entry.Result  // 重复命令，直接返回缓存结果
    }
    result := sm.execute(cmd.Op)
    sm.dedupTable[cmd.ClientId] = DedupEntry{cmd.SeqNum, result}
    return result
}

客户端 → Leader: 读取 x 的值

Leader 的处理：
  1. 记录当前 commitIndex
  2. 向多数节点发送心跳
  3. 等待多数节点回复
  4. 如果自己仍是 Leader 且 commitIndex 处的日志已应用到状态机
     → 读取状态机中 x 的值，返回给客户端
  5. 如果发现更高的 term → 退位，告诉客户端重试

Election Safety + Leader Append-Only + Log Matching
            ↓
    Leader Completeness
            ↓
    State Machine Safety

// 推荐值
const (
    HeartbeatInterval  = 100 * time.Millisecond   // 心跳间隔（课程要求 ≤ 150ms）
    ElectionTimeoutMin = 300 * time.Millisecond    // 选举超时下限
    ElectionTimeoutMax = 500 * time.Millisecond    // 选举超时上限
)

// Figure 8 规则 —— 只能提交当前任期的日志
if rf.log[N].Term == rf.currentTerm && count > len(rf.peers)/2 {
    rf.commitIndex = N
}

func (rf *Raft) persist() {
    w := new(bytes.Buffer)
    e := labgob.NewEncoder(w)
    e.Encode(rf.currentTerm)
    e.Encode(rf.votedFor)
    e.Encode(rf.log)
    rf.persister.SaveRaftState(w.Bytes())
}