知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - Raft 算法详解 ## Raft 简介 Raft 是由 Diego Ongaro 和 John Ousterhout 在 2014 年提出的分布式共识算法,目标是比 Paxos 更易理解和实现。 > "In Search of an Understandable Consensus Algorithm" > — Raft 论文标题 ### Raft vs Paxos | 对比项 | Paxos | Raft | |--------|-------|------| | 易理解性 | 困难 | 相对容易 | | 实现复杂度 | 高 | 中等 | | Leader | 可选 | 必须 | | 日志结构 | 未规定 | 连续日志 | | 工程实现 | 较少 | 广泛(etcd, Consul) | ## Raft 核心概念 ### 节点角色  *图:Raft 的 Leader、Candidate、Follower 三种角色与转换* ``` ┌─────────────────────────────────────────────────────────────┐ │ Raft 三种角色 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────────┐ │ │ │ Leader │ ─ 处理所有客户端请求 │ │ │ (领导者) │ ─ 向 Follower 复制日志 │ │ └─────────────┘ ─ 发送心跳维持领导地位 │ │ │ │ │ 超时/选举 │ │ │ │ │ ▼ │ │ ┌─────────────┐ │ │ │ Candidate │ ─ 请求其他节点投票 │ │ │ (候选者) │ ─ 可能当选或失败 │ │ └─────────────┘ │ │ │ │ │ 发现新Leader │ │ │ │ │ ▼ │ │ ┌─────────────┐ │ │ │ Follower │ ─ 被动接收 Leader 的请求 │ │ │ (跟随者) │ ─ 参与投票 │ │ └─────────────┘ ─ 转发客户端请求给 Leader │ │ │ └─────────────────────────────────────────────────────────────┘ ``` ### 任期(Term)  *图:Term 时间轴:四个任期的选举结果与任期规则* ``` Term 是 Raft 的逻辑时钟 时间轴 ──────────────────────────────────────────────────→ │←─ Term 1 ─→│←─ Term 2 ─→│←── Term 3 ──→│←─ Term 4 ─→│ 选举成功 选举失败 选举成功 选举成功 Leader A (无Leader) Leader B Leader C 规则: 1. 每个 Term 最多一个 Leader 2. Term 单调递增 3. 发现更高 Term 时,立即变为 Follower 4. 拒绝 Term 小于自己的请求 ``` ### 日志结构  *图:日志条目结构:Index、Term 与 Cmd 及 Commit Index* ``` ┌─────────────────────────────────────────────────────────────┐ │ Log Entry │ ├───────┬───────┬───────┬───────┬───────┬───────┬───────────┤ │ Index │ 1 │ 2 │ 3 │ 4 │ 5 │ ... │ ├───────┼───────┼───────┼───────┼───────┼───────┼───────────┤ │ Term │ 1 │ 1 │ 1 │ 2 │ 2 │ ... │ ├───────┼───────┼───────┼───────┼───────┼───────┼───────────┤ │ Cmd │ x=1 │ y=2 │ z=3 │ x=5 │ y=7 │ ... │ └───────┴───────┴───────┴───────┴───────┴───────┴───────────┘ ↑ Commit Index (已提交到这里) 日志特点: - Index 从 1 开始,连续递增 - 每个 Entry 包含 Term 和 Command - 已提交的 Entry 不会改变 ``` ## Leader 选举 ### 选举触发条件 ``` Follower 在选举超时(Election Timeout)内没有收到 Leader 的心跳 ↓ 转变为 Candidate ↓ 开始选举 Election Timeout: 通常 150ms - 300ms(随机) 随机化是为了避免多个节点同时发起选举 ``` ### 选举流程  *图:Node A 超时发起选举,获多数票当选 Leader* ``` 初始状态:所有节点都是 Follower 时间 ─────────────────────────────────────────────────────→ Node A (Follower) Node B (Follower) Node C (Follower) │ │ │ 超时 150ms │ │ │ │ │ ▼ │ │ (Candidate) │ │ Term: 1 → 2 │ │ Vote for self │ │ │ │ │ │──RequestVote(term=2)─→│ │ │ │ │ │──RequestVote(term=2)───────────────────→│ │ │ │ │←───VoteGranted─────│ │ │ │ │ │←───VoteGranted─────────────────────────│ │ │ │ 获得多数票 (3/3) │ │ │ │ │ ▼ │ │ (Leader) │ │ │ │ │ │──AppendEntries(heartbeat)──→│ │ │ │ │ │──AppendEntries(heartbeat)─────────────→│ ```  ### 选举规则 ```java public class RaftNode { private int currentTerm = 0; private Integer votedFor = null; private List<LogEntry> log = new ArrayList<>(); private Role role = Role.FOLLOWER; // 处理 RequestVote 请求 public VoteResponse handleRequestVote(RequestVote request) { // 规则 1:Term 比自己小,拒绝 if (request.term < currentTerm) { return new VoteResponse(currentTerm, false); } // 规则 2:Term 比自己大,更新 Term,变为 Follower if (request.term > currentTerm) { currentTerm = request.term; votedFor = null; role = Role.FOLLOWER; } // 规则 3:本 Term 已投票给其他人,拒绝 if (votedFor != null && votedFor != request.candidateId) { return new VoteResponse(currentTerm, false); } // 规则 4:候选人的日志必须至少和自己一样新 if (!isLogUpToDate(request.lastLogIndex, request.lastLogTerm)) { return new VoteResponse(currentTerm, false); } // 投票给候选人 votedFor = request.candidateId; return new VoteResponse(currentTerm, true); } // 日志新旧比较 private boolean isLogUpToDate(int lastLogIndex, int lastLogTerm) { int myLastIndex = log.size(); int myLastTerm = log.isEmpty() ? 0 : log.get(log.size() - 1).term; // 先比较 Term,Term 大的更新 if (lastLogTerm != myLastTerm) { return lastLogTerm > myLastTerm; } // Term 相同,Index 大的更新 return lastLogIndex >= myLastIndex; } } ``` ### 选举超时的随机化 ``` 为什么需要随机超时? 如果所有 Follower 的超时时间相同 → 同时变为 Candidate → 同时投票给自己 → 都拿不到多数票 → 超时 → 再次同时选举 → 死循环! 解决方案:每个 Follower 的超时时间在 [150ms, 300ms] 范围内随机 → 先超时的先变成 Candidate → 发起选举 → 大概率拿到多数票 ### 日志复制流程(Log Replication) ``` Raft 日志复制是 Leader 将客户端的写操作同步到所有 Follower 的过程。 正常日志复制流程(5 节点集群,Leader=Node1): ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ Node1 │ │ Node2 │ │ Node3 │ │ Node4 │ │ Node5 │ │(Leader)│ │(Follower)│ │(Follower)│ │(Follower)│ │(Follower)│ └───┬────┘ └────────┘ └────────┘ └────────┘ └────────┘ │ │ ① 客户端发送 SET x=5 │ ├── ② Leader 写入本地日志(未提交) │ index=4, term=2, cmd="SET x=5" │ ├── ③ 并行发送 AppendEntries(prevLogIndex=3, prevLogTerm=2, entries=[{x=5}]) │ ├────→ Node2: 收到,写入本地日志,返回 Success │ ├────→ Node3: 收到,写入本地日志,返回 Success │ ├────→ Node4: 收到,写入本地日志,返回 Success │ └────→ Node5: 收到,写入本地日志,返回 Success │ ├── ④ 收到多数派(≥3)响应 Success │ → commitIndex 推进到 4,标记日志已提交 │ → 将 commitIndex 通知给 Follower(下一次心跳) │ └── ⑤ 返回客户端 "OK" (此时 Node1~Node5 的日志都包含 x=5,但 commitIndex 可能不同) 下一次心跳同步 commitIndex,Follower 各自应用到状态机 关键点: 1. 日志 append 和 commit 是分离的 append:日志写入磁盘 commit:应用到状态机(数据对客户端可见) 2. 已提交的数据不会丢失 只要多数派节点持久化了日志条目,就算宕机重启也能恢复 3. Leader 的 commitIndex 决定了什么数据对客户端可见 Follower 的 commitIndex 由 Leader 在 AppendEntries 中告知 4. 日志一致性保证: 如果两个节点的同 index 日志有相同 term,则它们前面所有日志完全一致 (Log Matching Property) ```  ### 日志冲突与修复 ``` Follower 日志可能落后或不一致,Leader 通过回退重试修复: Leader 的日志: index: 1 2 3 4 5 6 term: 1 1 2 3 3 3 cmd: a b c d e f Follower A: index: 1 2 3 4 term: 1 1 2 3 ← 落后 2 条 发送 AppendEntries(prevLogIndex=4, prevLogTerm=3, entries=[e,f]) → Follower A 有 [4,term=3],匹配! → 追加 e, f → 一致 ✓ Follower B: index: 1 2 3 4 5 term: 1 1 2 2 2 ← 第 4 条起冲突! 发送 AppendEntries(prevLogIndex=3, prevLogTerm=2, entries=[d,e,f]) → Follower B 的 [3,term=2] 匹配! → 但 index=4 是 term=2(冲突),被 Leader 的 [4,term=3] 覆盖 → 追加 d, e, f → 一致 ✓ 冲突修复过程: Leader 为每个 Follower 维护 nextIndex(下一个要发送的日志索引) 初始值 = Leader 的最新日志 index 发送 AppendEntries(prevLogIndex=nextIndex-1, ...) ├── Follower 发现 prevLogIndex 处 term 不匹配 → 返回 Failure └── Leader 收到 Failure → nextIndex--,重试 (逐步回退,直到找到匹配点,然后覆盖冲突部分)  *图:固定超时会选票瓜分,随机超时选出 Leader* ```  场景:3 个节点,Leader 宕机 如果超时时间固定(如 150ms): ───────────────────────────────────── Node A: ──超时──变Candidate──RequestVote──→ Node B: ──超时──变Candidate──RequestVote──→ Node C: ──超时──变Candidate──RequestVote──→ 每个节点都投给自己,无法选出 Leader! 随机超时(150ms - 300ms): ───────────────────────────────────── Node A: ──超时(152ms)──变Candidate──RequestVote──→ Node B: ────────超时(201ms)── 收到A的投票请求 ── 投A Node C: ──────────超时(287ms)── 收到A的投票请求 ── 投A Node A 获得多数票,成为 Leader ``` ## 日志复制 ### AppendEntries RPC  *图:AppendEntries RPC 的六个参数与含义* ``` Leader 通过 AppendEntries RPC 向 Follower 复制日志 AppendEntries 参数: ┌────────────────────────────────────────────────────────────┐ │ term │ Leader 的 Term │ │ leaderId │ Leader 的 ID │ │ prevLogIndex │ 前一条日志的索引 │ │ prevLogTerm │ 前一条日志的 Term │ │ entries[] │ 要复制的日志条目(心跳时为空) │ │ leaderCommit │ Leader 的 commitIndex │ └────────────────────────────────────────────────────────────┘ ```  ### 日志复制流程  *图:写请求全流程:追加日志、多数派确认、提交与通知* ``` 客户端请求: SET x = 10 Leader Follower A Follower B │ │ │ Client ───────→ │ │ │ SET x = 10 │ │ │ │ │ │ 1. 追加到本地日志 │ │ │ [x=10] │ │ │ │ │ │ 2. 发送AppendEntries │ │ │──AppendEntries([x=10])──→ │ │ │ │ │ │──AppendEntries([x=10])────────────────────→ │ │ │ │ 3. Follower 追加日志并响应 │ │ │ │──追加日志 │ │←─────Success──────────────│ │ │ │ │ │ │ 追加日志 ──── │ │←─────Success────────────────────────────────── │ │ │ │ 4. 多数派确认后提交 │ │ commitIndex++│ │ │ │ │ │ 5. 响应客户端 │ │ │ │ │ │ ←───Success─────│ │ │ │ │ │ 6. 下次心跳通知 Follower 提交 │ │ │──AppendEntries(commit)──→ │ │ │──AppendEntries(commit)────────────────────→ │ ``` ### 日志一致性检查 ```java public class Follower { private List<LogEntry> log = new ArrayList<>(); public AppendEntriesResponse handleAppendEntries(AppendEntries request) { // 检查 Term if (request.term < currentTerm) { return new AppendEntriesResponse(currentTerm, false); } // 一致性检查:prevLogIndex 处的 Entry Term 必须匹配 if (request.prevLogIndex > 0) { if (request.prevLogIndex > log.size()) { // 日志不够长 return new AppendEntriesResponse(currentTerm, false); } LogEntry prevEntry = log.get(request.prevLogIndex - 1); if (prevEntry.term != request.prevLogTerm) { // Term 不匹配,删除这之后的所有日志 log = log.subList(0, request.prevLogIndex - 1); return new AppendEntriesResponse(currentTerm, false); } } // 追加新日志 for (int i = 0; i < request.entries.length; i++) { int index = request.prevLogIndex + i + 1; if (index <= log.size()) { // 覆盖现有日志 log.set(index - 1, request.entries[i]); } else { // 追加新日志 log.add(request.entries[i]); } } // 更新 commitIndex if (request.leaderCommit > commitIndex) { commitIndex = Math.min(request.leaderCommit, log.size()); } return new AppendEntriesResponse(currentTerm, true); } } ``` ### 日志不一致处理 ``` 场景:Follower 日志落后或不一致 Leader 日志: [1:a] [1:b] [2:c] [2:d] [3:e] Follower 日志: [1:a] [1:b] [2:x] (Term 2 时宕机,重新选举) 处理流程: 1. Leader 发送 AppendEntries(prevLogIndex=5, prevLogTerm=3) 2. Follower 检查 Index=5 不存在,返回 false 3. Leader 递减 nextIndex,重发 AppendEntries(prevLogIndex=4, prevLogTerm=2) 4. Follower 检查 Index=4 不存在,返回 false 5. Leader 递减 nextIndex,重发 AppendEntries(prevLogIndex=3, prevLogTerm=2) 6. Follower 检查 Index=3,Term 不匹配,删除 [2:x],返回 false 7. Leader 递减 nextIndex,重发 AppendEntries(prevLogIndex=2, prevLogTerm=1, entries=[2:c,2:d,3:e]) 8. Follower 检查成功,追加日志 最终: Leader 日志: [1:a] [1:b] [2:c] [2:d] [3:e] Follower 日志: [1:a] [1:b] [2:c] [2:d] [3:e] ✓ 一致 ``` ## 安全性保证 ### 选举限制 ``` 只有拥有所有已提交日志的节点才能当选 Leader 场景: Node A (Leader): [1:a] [1:b] [2:c] 已提交 Node B: [1:a] [1:b] Node C: [1:a] 如果 A 宕机,B 和 C 中只有 B 能当选,因为 B 的日志更新 日志新旧比较规则: 1. 先比较最后一条日志的 Term 2. Term 相同则比较 Index 3. 新的获胜 ``` ### 提交规则 ``` Leader 只能提交当前 Term 的日志 反例(如果允许提交之前 Term 的日志): 时间 1: S1 是 Leader (Term=2),复制日志 [2:x] 到 S2 S1: [1:a][2:x] S2: [1:a][2:x] S3: [1:a] 时间 2: S1 宕机,S5 当选 (Term=3),写入 [3:y] S1: [1:a][2:x] S5: [1:a][3:y] 时间 3: S5 宕机,S1 恢复,当选 (Term=4) 如果 S1 提交 [2:x]... 危险! 时间 4: S1 宕机,S5 恢复当选 (Term=5) S5 会用 [3:y] 覆盖 [2:x] 已提交的数据丢失! 正确做法: Leader 必须在当前 Term 有日志被提交后,才能间接提交之前 Term 的日志 ``` ## 成员变更 ### 单节点变更 ``` 一次只增加或删除一个节点,保证新旧配置的多数派有重叠 旧配置: {A, B, C} 多数派: 2/3 新配置: {A, B, C, D} 多数派: 3/4 旧多数派:{A, B} 或 {A, C} 或 {B, C} 新多数派:{A, B, C} 或 {A, B, D} 或 {A, C, D} 或 {B, C, D} 任意旧多数派和新多数派必有交集 → 安全 ``` ### Joint Consensus(联合共识)  *图:集群成员变更的联合配置两阶段流程* ``` 用于一次变更多个节点 阶段 1: 进入联合配置 C(old,new) 需要同时获得旧配置和新配置的多数派同意 阶段 2: 进入新配置 C(new) ┌─────────────┐ ┌───────────────┐ ┌─────────────┐ │ C(old) │ → │ C(old,new) │ → │ C(new) │ │ 旧配置 │ │ 联合配置 │ │ 新配置 │ └─────────────┘ └───────────────┘ └─────────────┘ ``` ## Raft 优化 ### 日志压缩(Snapshot)  *图:快照清理旧日志,InstallSnapshot 补发落后 Follower* ``` 问题:日志无限增长 解决:定期生成快照,删除旧日志 状态机: Snapshot 新日志 ┌────────────┐ ┌────────────┐ ┌───────────────────┐ │ x=5, y=10 │ │ 快照数据 │ │ [100:z=3][101:..] │ │ z=3 │ │ lastIndex=99│ │ │ └────────────┘ │ lastTerm=5 │ └───────────────────┘ └────────────┘ InstallSnapshot RPC: 用于发送快照给落后太多的 Follower ``` ### 批量处理 ```java // 批量发送日志,减少 RPC 次数 public void replicateLogs() { for (Follower follower : followers) { int nextIndex = follower.getNextIndex(); int lastIndex = log.size(); if (lastIndex >= nextIndex) { // 批量发送 nextIndex 到 lastIndex 的所有日志 List<LogEntry> entries = log.subList(nextIndex - 1, lastIndex); sendAppendEntries(follower, entries); } } } ``` ### Pipeline  *图:传统串行与 Pipeline 连续发送的吞吐对比* ``` 不等待上一个请求的响应,持续发送新请求 传统方式: Leader: ──Send[1]──Wait──Recv──Send[2]──Wait──Recv──Send[3]── Pipeline: Leader: ──Send[1]──Send[2]──Send[3]──Recv[1]──Recv[2]──Recv[3]── 显著提升吞吐量 ``` ## 本章小结 - **角色**:Leader、Candidate、Follower 三种角色轮转 - **任期**:Term 是逻辑时钟,每个 Term 最多一个 Leader - **选举**:随机超时避免冲突,日志更新的节点获胜 - **复制**:Leader 负责复制,多数派确认后提交 - **安全性**:选举限制和提交规则保证已提交日志不丢失 - **成员变更**:单节点变更或联合共识保证安全 ## 思考题 1. 如果两个节点同时发起选举且获得相同票数,会发生什么? 2. 为什么 Leader 不能直接提交前一个 Term 的日志? 3. Raft 和 Multi-Paxos 的主要区别是什么? ## QA ### Q1:如果两个节点同时发起选举且获得相同票数,会发生什么? 这就是典型的 split vote。两个候选人都拿不到多数票,当前任期不会产生新 Leader,随后各节点等待新的随机选举超时,再进入下一轮选举。因为超时时间是随机的,后续通常会有一个候选人更早发起请求并赢得多数,从而恢复稳定。 ### Q2:为什么 Leader 不能直接提交前一个 Term 的日志? Raft 的规则是:Leader 只能依据“当前任期的某条日志已经复制到多数节点”来推进 `commitIndex`。这样做是为了间接把之前任期的未提交日志也一并安全提交。如果允许 Leader 直接提交旧任期日志,可能出现该日志虽然在当前 Leader 看来复制够多,但未来被另一个更“新”的 Leader 覆盖,从而破坏安全性。 ### Q3:Raft 和 Multi-Paxos 的主要区别是什么? 两者都能实现强一致日志复制,但设计风格不同。Raft 更强调工程可理解性,明确区分 Leader、Follower、Candidate,并把日志复制、选举和提交规则讲得更直观;Multi-Paxos 理论表达更抽象,理解门槛更高。工程上它们性能级别接近,Raft 通常更适合作为教学和通用基础设施实现。 --- 下一篇:[06 - ZooKeeper 与协调服务](./06-coordination.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入