一、核心概念

Raft 是一种 易于理解 的分布式共识算法，由 Diego Ongaro 和 John Ousterhout 于 2014 年提出，目标是成为 Paxos 的替代方案。Raft 将共识问题分解为三个相对独立的子问题：Leader 选举、日志复制 和 安全性保证。

为什么需要 Raft？

• Paxos 难以理解和实现：Raft 通过强 Leader 模型简化了共识过程
• 工程友好：提供清晰的状态机模型，易于工程实现
• 广泛应用：etcd、Consul、TiKV 等分布式系统的核心算法

核心特性

1. 强 Leader：所有日志条目只能从 Leader 流向 Follower
2. Leader 选举：通过随机超时机制快速选举
3. 日志复制：保证日志的顺序一致性
4. 安全性：已提交的日志永不丢失

---

二、三种节点角色

Raft 集群中的每个节点在任意时刻处于以下三种状态之一：

角色	职责	行为
Leader（领导者）	处理所有客户端请求	发送心跳、复制日志
Follower（跟随者）	被动响应请求	接收日志、投票
Candidate（候选人）	竞选 Leader	请求投票

状态转换图：

         超时未收到心跳
Follower ---------------> Candidate
   ^                          |
   |                          | 赢得选举
   |                          v
   |                       Leader
   |                          |
   +------发现更高任期--------+

---

三、核心机制详解

1. Leader 选举（Leader Election）

选举触发条件

• Follower 在 Election Timeout（选举超时，如 150-300ms）内未收到 Leader 心跳
• Follower 转为 Candidate，发起新一轮选举

选举流程

1. Candidate 行为：
   • 增加当前任期号（currentTerm++）
   • 投票给自己
   • 并行向所有其他节点发送 RequestVote RPC
2. Follower 投票规则：
   • 每个任期内只投一票（先到先得）
   • 候选人的日志至少和自己一样新（安全性关键）
     • 比较最后一条日志的 (term, index)
     • Term 大的更新；Term 相同则 Index 大的更新
3. 选举结果：
   • 赢得选举：获得多数派票（N/2 + 1），转为 Leader
   • 其他人当选：收到新 Leader 心跳，转为 Follower
   • 选举超时：无人获得多数票，重新选举（通过随机超时避免死锁）

代码示意：

// Candidate 发起选举
public void startElection() {
    currentTerm++;
    votedFor = self;
    int votes = 1;
    
    for (Node node : cluster) {
        RequestVoteResponse response = node.requestVote(
            currentTerm,
            self.id,
            lastLogIndex,
            lastLogTerm
        );
        
        if (response.voteGranted) {
            votes++;
        }
        
        if (votes > cluster.size() / 2) {
            becomeLeader();
            return;
        }
    }
}

// Follower 处理投票请求
public RequestVoteResponse handleRequestVote(RequestVoteRequest req) {
    // 拒绝条件1: 候选人任期小于当前任期
    if (req.term < currentTerm) {
        return new RequestVoteResponse(currentTerm, false);
    }
    
    // 拒绝条件2: 本任期已投过票且不是该候选人
    if (votedFor != null && votedFor != req.candidateId) {
        return new RequestVoteResponse(currentTerm, false);
    }
    
    // 拒绝条件3: 候选人日志不够新
    if (!isLogUpToDate(req.lastLogTerm, req.lastLogIndex)) {
        return new RequestVoteResponse(currentTerm, false);
    }
    
    // 投票给该候选人
    votedFor = req.candidateId;
    resetElectionTimer();
    return new RequestVoteResponse(currentTerm, true);
}

// 判断日志是否足够新
private boolean isLogUpToDate(int candidateTerm, int candidateIndex) {
    int myLastTerm = getLastLogTerm();
    int myLastIndex = getLastLogIndex();
    
    if (candidateTerm != myLastTerm) {
        return candidateTerm >= myLastTerm;
    }
    return candidateIndex >= myLastIndex;
}

---

2. 日志复制（Log Replication）

日志结构

每条日志条目包含：

• Index：日志索引（从 1 开始递增）
• Term：创建该条目时的任期号
• Command：状态机指令（如 SET x=5）

示例：

Index:  1    2    3    4    5    6
Term:  [1]  [1]  [2]  [3]  [3]  [3]
Cmd:   [a]  [b]  [c]  [d]  [e]  [f]

复制流程

1. 客户端请求：发送命令到 Leader

2. Leader 行为：
   • 将命令追加到本地日志
   • 并行向所有 Follower 发送 AppendEntries RPC
   • 等待多数派响应
3. Follower 行为：
   • 检查日志一致性（prevLogIndex 和 prevLogTerm 必须匹配）
   • 一致则追加新条目，不一致则拒绝
4. 提交（Commit）：
   • Leader 收到多数派成功响应后，更新 commitIndex
   • 在下次心跳中通知 Follower 更新 commitIndex
   • 所有节点将已提交的日志应用到状态机

代码示意：

// Leader 复制日志
public void replicateLog(Command cmd) {
    // 1. 追加到本地日志
    LogEntry entry = new LogEntry(currentTerm, cmd);
    log.append(entry);
    
    int successCount = 1; // Leader 自己
    int majority = cluster.size() / 2 + 1;
    
    // 2. 并行发送给 Followers
    for (Node follower : followers) {
        AppendEntriesRequest req = new AppendEntriesRequest(
            currentTerm,
            leaderId,
            follower.nextIndex - 1,  // prevLogIndex
            log.get(follower.nextIndex - 1).term,  // prevLogTerm
            Arrays.copyOfRange(log, follower.nextIndex, log.size()),
            commitIndex
        );
        
        AppendEntriesResponse resp = follower.appendEntries(req);
        
        if (resp.success) {
            follower.nextIndex = log.size() + 1;
            follower.matchIndex = log.size();
            successCount++;
            
            // 3. 多数派确认后提交
            if (successCount >= majority && log.get(log.size()).term == currentTerm) {
                commitIndex = log.size();
                applyToStateMachine(log.get(commitIndex));
            }
        } else {
            // 日志不一致，回退 nextIndex 重试
            follower.nextIndex--;
        }
    }
}

// Follower 处理日志追加
public AppendEntriesResponse handleAppendEntries(AppendEntriesRequest req) {
    // 任期检查
    if (req.term < currentTerm) {
        return new AppendEntriesResponse(currentTerm, false);
    }
    
    // 重置选举定时器（收到 Leader 心跳）
    resetElectionTimer();
    
    // 日志一致性检查
    if (!log.contains(req.prevLogIndex, req.prevLogTerm)) {
        return new AppendEntriesResponse(currentTerm, false);
    }
    
    // 追加新条目（删除冲突的旧条目）
    log.appendAfter(req.prevLogIndex, req.entries);
    
    // 更新 commitIndex
    if (req.leaderCommit > commitIndex) {
        commitIndex = Math.min(req.leaderCommit, log.lastIndex());
        applyCommittedLogs();
    }
    
    return new AppendEntriesResponse(currentTerm, true);
}

---

3. 安全性保证（Safety）

关键约束

1. 选举安全性（Election Safety）：
   • 每个任期最多只有一个 Leader
2. 日志匹配特性（Log Matching）：
   • 如果两个日志条目有相同的 Index 和 Term，则：
     • 它们存储相同的命令
     • 它们之前的所有条目都相同
3. Leader 完整性（Leader Completeness）：
   • 如果某条目在某任期被提交，则该条目必出现在更高任期 Leader 的日志中
   • 实现方式：投票时检查候选人日志是否足够新
4. 状态机安全性（State Machine Safety）：
   • 如果某节点已将某条目应用到状态机，则其他节点不会应用不同的命令到相同的索引

Leader 只提交当前任期的日志

特殊规则：Leader 不能直接提交旧任期的日志，必须通过提交当前任期的新日志来间接提交

示例场景（Figure 8 问题）：

时间线：
1. Leader S1 在 Term2 复制日志到 S2，但在提交前宕机
2. S5 当选 Leader（Term3），覆盖部分日志
3. S1 重新当选（Term4），不能直接提交 Term2 的日志
4. 必须等待 Term4 的新日志复制到多数派后，才能提交 Term2 的旧日志

原因：避免已提交的日志被新 Leader 覆盖

---

四、心跳机制与日志修复

心跳（Heartbeat）

• Leader 定期发送空的 AppendEntries RPC（无日志条目）
• 作用：
  1. 防止 Follower 超时发起选举
  2. 通知 Follower 更新 commitIndex

日志不一致修复

场景：Follower 宕机或网络分区后，日志与 Leader 不一致

修复流程：

1. Leader 维护每个 Follower 的 nextIndex（下一条要发送的日志索引）
2. 发送 AppendEntries 时携带 prevLogIndex 和 prevLogTerm
3. Follower 检查失败则返回 false
4. Leader 递减 nextIndex 并重试，直到找到匹配点
5. 从匹配点开始覆盖 Follower 的日志

优化：快速回退算法（返回冲突任期的第一条日志索引）

---

五、Raft vs Paxos

对比项	Paxos	Raft
理解难度	难（无明确流程）	易（清晰的状态机）
Leader 模型	弱 Leader（可多个 Proposer）	强 Leader（唯一入口）
日志复制	无序（需额外机制保证）	有序（日志连续）
工程实现	复杂（需处理活锁）	简单（随机超时避免冲突）
应用	Chubby、Zookeeper（ZAB）	etcd、Consul、TiKV

总结：Raft 通过强 Leader 和明确的状态转换，将 Paxos 的复杂性转化为易于理解和实现的工程方案。

---

六、实际应用

1. etcd（Kubernetes 配置中心）

• 使用 Raft 保证配置数据的强一致性
• 每个写操作都通过 Raft 日志复制

2. Consul（服务发现）

• 服务注册信息通过 Raft 同步
• 提供强一致性的健康检查

3. TiKV（分布式 KV 存储）

• 使用 Raft 实现 Region 的多副本一致性
• 支持分布式事务（基于 Raft 日志）

---

七、答题总结

Raft 算法 通过三个核心机制实现分布式共识：

1. Leader 选举：
   • 随机超时触发选举
   • 投票规则：任期唯一 + 日志足够新
   • 多数派获胜
2. 日志复制：
   • Leader 追加日志并并行发送给 Follower
   • 检查日志一致性（prevLogIndex + prevLogTerm）
   • 多数派确认后提交并应用到状态机
3. 安全性保证：
   • 选举时检查候选人日志是否最新
   • Leader 只提交当前任期的日志
   • 保证已提交日志永不丢失

关键优势：

• 强 Leader 模型：简化共识流程
• 易于理解：清晰的状态转换和角色划分
• 工程友好：被广泛应用于生产环境

面试加分项：

• 对比 Paxos，强调 Raft 的可理解性
• 说明日志匹配特性如何保证一致性
• 提到 etcd、Consul 等实际应用
• 解释 Leader 只提交当前任期日志的原因（Figure 8 问题）

口述建议：按 Leader 选举 → 日志复制 → 安全性保证的顺序讲解，结合角色状态转换图，逻辑清晰且易于理解。