罗罗编程学习记录
本页内容 展开查看

09.9.3 Raft 与 Paxos 对照

所属:全栈开发面试题库 / 09 高阶架构:高并发与分布式 / 09.9 分布式基础算法

覆盖范围

  • Raft 角色、选主、日志复制流程
  • Raft 安全性约束(Election Safety、Log Matching)
  • Paxos 基本协议(Proposer/Acceptor/Learner)
  • Raft 与 Multi-Paxos 的工程对照
  • 典型实现:etcd、ZooKeeper、Chubby

高频题速览

编号 题目 难度 频率
09.9.3-001 Raft 三个角色是什么 高级 ★★★★★
09.9.3-002 Raft 选主流程 高级 ★★★★★
09.9.3-003 Raft 日志复制流程 高级 ★★★★☆
09.9.3-004 Raft 安全性怎么保证 高级 ★★★★☆
09.9.3-005 Paxos 基本协议流程 高级 ★★★★☆
09.9.3-006 Raft 和 Paxos 有什么区别 高级 ★★★★☆
09.9.3-007 Multi-Paxos 是什么 高级 ★★★☆☆
09.9.3-008 Raft 脑裂怎么避免 高级 ★★★★☆
09.9.3-009 Raft 线性一致读怎么实现 高级 ★★★☆☆
09.9.3-010 etcd 用的是 Raft 吗 进阶 ★★★☆☆

09.9.3-001 Raft 三个角色是什么?

一句话结论

Raft 集群有三种角色:Leader(处理所有客户端写请求,复制日志到 Follower)、Follower(被动接收 Leader 的日志和心跳,不发起请求)、Candidate(选举阶段的临时角色,Follower 超时未收到心跳后转为 Candidate 发起投票)。

概念解释

  • Leader:唯一的写入口,处理客户端请求,维护日志复制。
  • Follower:被动接收,回复 Leader 的心跳和日志复制。
  • Candidate:选举中,向其他节点请求投票。

原理流程

正常运行:
  1 个 Leader,N-1 个 Follower
  Leader 定期发心跳,Follower 保持状态
选举:
  Follower 选举超时 → 转 Candidate → 请求投票

代码或图示

状态转换:
  Follower --(选举超时)--> Candidate
  Candidate --(获多数票)--> Leader
  Candidate --(发现新 Leader)--> Follower
  Leader --(发现更高 term)--> Follower

常见误区

  • 误区:Raft 有多个 Leader。Raft 任何时刻只有一个 Leader(term 内),多个 Leader 是脑裂,Raft 设计上避免。
  • 误区:Follower 可以响应客户端写。写请求必须走 Leader,Follower 只读或转发。

追问

  • 问:集群规模怎么选?答:奇数个节点(3、5、7),容忍 (N-1)/2 故障,详见 09.5.1.2。
  • 问:为什么用奇数?答:3 节点容忍 1 故障,4 节点也只容忍 1 故障(多数派 > 2),奇数性价比最高。

09.9.3-002 Raft 选主流程是什么?

一句话结论

Follower 在 election timeout(通常 150~300ms)内未收到 Leader 心跳,转为 Candidate,term +1,给自己投票,并行发 RequestVote RPC;收到多数派投票就成为 Leader;如果收到其他人的投票请求且 term 更高,则退回 Follower;如果超时未选出,重新选举。

概念解释

  • term:逻辑时钟,每次选举 +1,单调递增。
  • RequestVote:Candidate 向其他节点请求投票。
  • 投票规则:每个节点每个 term 只投一票,先到先得;Candidate 的日志必须至少和投票者一样新(日志匹配约束)。
  • 选举超时:随机化,避免多个 Candidate 同时开始选举。

原理流程

1. Follower 等不到心跳,election timeout 触发
2. term = term + 1,状态 → Candidate,投自己
3. 并行发 RequestVote(term, candidateId, lastLogIndex, lastLogTerm)
4. 收到多数票 → 成为 Leader,发心跳
5. 收到更高 term 的 RequestVote → 退回 Follower
6. 超时(split vote)→ 重新随机超时,再选举

代码或图示

投票条件(投票者同意):
  - candidate.term >= voter.term
  - 本 term 未投过票
  - candidate 的日志至少和 voter 一样新
    (lastLogTerm 大,或 lastLogTerm 相同但 lastLogIndex 大)

常见误区

  • 误区:选举超时固定值。固定值会导致多个 Follower 同时超时同时竞选,split vote 概率高;随机化(150~300ms 随机)避免。
  • 误区:投票只看 term。投票还要看日志新鲜度,保证选出的 Leader 有完整日志,详见 09.9.3-004。

追问

  • 问:split vote 怎么处理?答:随机超时重新选举,概率上很快选出一个。
  • 问:为什么日志新鲜度重要?答:保证旧 Leader(日志落后)不会被选出来,丢失已提交日志。

09.9.3-003 Raft 日志复制流程是什么?

一句话结论

客户端写请求发给 Leader,Leader 追加到本地日志(未提交),并行发 AppendEntries RPC 给 Follower;Follower 追加日志并回复成功;Leader 收到多数派确认后,标记该日志为 committed,应用到状态机,并回复客户端;下次心跳时告诉 Follower 提交位置。

概念解释

  • 日志条目:(term, index, command),每个条目是一条写命令。
  • 未提交:Leader 本地写了,但未获多数派确认。
  • 已提交:多数派复制成功,Leader 应用到状态机。
  • AppendEntries:Leader 复制日志到 Follower,同时作心跳。

原理流程

1. 客户端写 → Leader 追加日志条目 (term, index, cmd)
2. Leader 并行发 AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries, commitIndex)
3. Follower:
   - 检查 term >= 自己 term
   - 检查 prevLogIndex/prevLogTerm 匹配(日志一致性)
   - 匹配则追加 entries,回复 success
   - 不匹配则回复失败,Leader 回退 prevLogIndex 重试
4. Leader 收到多数 success → commitIndex = index
5. Leader 应用到状态机,回复客户端
6. 下次 AppendEntries 带 commitIndex,Follower 应用已提交日志

代码或图示

日志:
  Leader:   [T1:1] [T1:2] [T2:3] [T2:4]
  Follower: [T1:1] [T1:2] [T2:3] [T2:4] (复制成功)
  commitIndex = 3(多数派已确认 index=3)

常见误区

  • 误区:Leader 写本地日志就回复客户端。必须等多数派复制成功才提交并回复,否则 Leader 故障会丢数据。
  • 误区:Follower 日志和 Leader 不一致会自动对齐。不一致时 AppendEntries 失败,Leader 回退 prevLogIndex 逐步重试,找到一致点后覆盖。

追问

  • 问:日志不一致怎么修复?答:Leader 维护 nextIndex,AppendEntries 失败就 nextIndex--,直到找到 Follower 和 Leader 一致的点,然后覆盖 Follower 后续日志。
  • 问:已提交日志会被覆盖吗?答:不会,Raft 安全性保证已提交日志不会被删除或覆盖。

09.9.3-004 Raft 安全性怎么保证?

一句话结论

Raft 通过五条安全性约束保证一致性:Election Safety(一个 term 最多一个 Leader)、Leader Append-Only(Leader 不覆盖/删除日志,只追加)、Log Matching(相同 term 和 index 的日志条目内容相同,且之前日志也相同)、Leader Completeness(已提交日志一定出现在新 Leader 中)、State Machine Safety(已应用到状态机的日志不会被覆盖)。

概念解释

  • Election Safety:一个 term 内最多一个 Leader 获多数票。
  • Leader Append-Only:Leader 只追加日志,不修改历史。
  • Log Matching:相邻日志条目 term 和 index 都相同则内容相同。
  • Leader Completeness:新 Leader 的日志包含所有已提交日志。

原理流程

Election Safety:
  每个节点每 term 投一票 → 最多一个 Candidate 获多数票
Leader Completeness:
  投票时要求 Candidate 日志至少和投票者一样新
  → 有最新日志的 Candidate 才能当选
  → 已提交日志一定在新 Leader 中

代码或图示

日志新鲜度比较:
  Candidate.lastLogTerm > voter.lastLogTerm → Candidate 新
  lastLogTerm 相同,lastLogIndex >= voter.lastLogIndex → Candidate 新
  → 否则投票者拒绝

常见误区

  • 误区:Raft 可能丢已提交日志。Leader Completeness 保证已提交日志一定在新 Leader 中,不会丢。
  • 误区:Follower 可以主动改日志。Follower 日志由 Leader 复制覆盖,自己不改。

追问

  • 问:Leader Completeness 怎么保证?答:投票时比较日志新鲜度,日志落后的 Candidate 不会被选出来。
  • 问:Raft 论文里的安全性证明?答:见 Raft 论文 "In Search of an Understandable Consensus Algorithm",Figure 3 的五个性质。

09.9.3-005 Paxos 基本协议流程是什么?

一句话结论

Basic Paxos 有三个角色:Proposer(发起提案)、Acceptor(投票)、Learner(学习结果);分两阶段:Prepare(Proposer 发 prepare,Acceptor 承诺不再接受更低编号提案)和 Accept(Proposer 发 accept,Acceptor 接受提案值);多数派达成一致后提案被选定。

概念解释

  • Proposal:(编号 n, 值 v),编号单调递增。
  • Prepare 阶段:Proposer 发 prepare(n),Acceptor 承诺不接受 < n 的提案,并返回已接受的最高编号提案。
  • Accept 阶段:Proposer 发 accept(n, v),Acceptor 接受(如果未违背承诺)。
  • 多数派:超过半数 Acceptor 同意则提案选定。

原理流程

阶段 1 (Prepare):
  Proposer → Acceptor: prepare(n)
  Acceptor 回复:promise(n),并返回已接受的最高编号提案 (n_a, v_a)
阶段 2 (Accept):
  Proposer 收到多数 prepare 回复
  → 选 v = 回复中最高编号提案的值(或自己的提案值)
  → 发 accept(n, v)
  Acceptor 接受(如果未承诺更高编号)→ 回复 accepted
  多数 accepted → 提案选定

代码或图示

Prepare:
  P1: prepare(1) → A1(ok, 无), A2(ok, 无), A3(ok, 无)
Accept:
  P1: accept(1, "X") → A1(ok), A2(ok), A3(ok)
  → 多数派 → 选定 "X"

常见误区

  • 误区:Paxos 一轮就成功。可能两个 Proposer 交替 prepare 导致活锁,需要选主(Multi-Paxos)或随机退避。
  • 误区:Paxos 值可以由 Proposer 随便选。如果 prepare 回复中已有其他 Proposer 的值,必须用那个值(保证已选定的值不被覆盖)。

追问

  • 问:活锁怎么处理?答:随机退避重试,或选一个 Proposer 作为 Leader(Multi-Paxos)。
  • 问:Learner 干嘛?答:学习选定结果,应用到状态机。

09.9.3-006 Raft 和 Paxos 有什么区别?

一句话结论

Paxos 是理论协议,描述了"如何就一个值达成一致",但没有指定工程实现细节(选主、日志复制);Raft 是为可理解性设计的工程化共识协议,显式选主(Leader)、日志复制、term 逻辑时钟,把共识拆成选主和日志复制两个子问题;两者都保证线性一致,但 Raft 更易实现和理解。

概念解释

  • Paxos:抽象的共识协议,Basic Paxos 就一个值达成一致,Multi-Paxos 扩展到多个值。
  • Raft:工程化,显式 Leader,日志按 term 组织,选主即共识的一部分。
  • 可理解性:Raft 论文目标就是"让共识像教科书一样易懂"。

原理流程

Paxos:
  Basic Paxos 就一个值达成一致
  Multi-Paxos 选一个持久 Leader,避免每次 prepare
Raft:
  选主(Leader Election)+ 日志复制(Log Replication)
  每个 term 一个 Leader,日志顺序复制

代码或图示

对比:
  Paxos:角色灵活(Proposer/Acceptor/Learner),无显式 Leader
  Raft:显式 Leader,Follower 被动,Candidate 临时
  Paxos:两阶段(Prepare/Accept)
  Raft:Leader 追加日志 + AppendEntries 复制

常见误区

  • 误区:Paxos 比 Raft 强。两者都证明安全(线性一致),Raft 是工程化更友好的实现,不是更弱。
  • 误区:Multi-Paxos 就是 Raft。Multi-Paxos 是 Paxos 的工程扩展(选主),但没有 Raft 的 term、日志匹配、选举超时等具体机制。

追问

  • 问:哪些系统用 Paxos?答:Chubby(Google)、Spanner(基于 Paxos)、一些 ZooKeeper 变体。
  • 问:哪些系统用 Raft?答:etcd、Consul、TiKV、Neo4j、NATS。

09.9.3-007 Multi-Paxos 是什么?

一句话结论

Multi-Paxos 是 Basic Paxos 的工程扩展:选一个持久的 Leader(Active Proposer),避免每次都走 Prepare 阶段;Leader 直接发 Accept,就一系列连续编号的提案达成一致;本质上是把 Paxos 的选主与日志复制工程化,与 Raft 的设计目标类似但机制不同。

概念解释

  • Active Proposer:固定的 Leader,长期担任 Proposer。
  • 跳过 Prepare:Leader 稳定后,直接发 Accept,不再 prepare。
  • 连续编号:日志按编号连续,类似 Raft 的 log index。

原理流程

Basic Paxos:每个值都走 Prepare + Accept 两阶段
Multi-Paxos:
  1. 选一个 Leader(通过 Basic Paxos 或其他机制)
  2. Leader 稳定后,直接发 Accept(n, v)
  3. 连续编号日志,类似 Raft

代码或图示

Multi-Paxos 优化:
  Leader 稳定 → 跳过 Prepare
  → 写延迟从两轮降为一轮

常见误区

  • 误区:Multi-Paxos 就是 Raft。Multi-Paxos 是 Paxos 论文中的扩展,Raft 独立设计,两者机制不同(term、日志匹配规则、选举超时)。
  • 误区:Multi-Paxos 没有选主问题。Leader 故障后仍要重新选主,仍可能走 Basic Paxos 流程。

追问

  • 问:Multi-Paxos 工程实现难点?答:Leader 变更、日志空洞(proposal 编号不连续)、垃圾回收。
  • 问:Raft 在这些方面怎么简化?答:term 单调、日志连续、commitIndex 推进,工程上更简单。

09.9.3-008 Raft 脑裂怎么避免?

一句话结论

Raft 脑裂指网络分区时两边都认为自己是 Leader;Raft 通过 term 单调递增和多数派投票避免:分区后少数派侧无法获得多数票,无法选出新 Leader;旧 Leader 在多数派侧仍然有效,少数派侧的旧 Leader 发心跳时 term 落后,被 Follower 拒绝;分区恢复后,term 对齐,旧 Leader 自动退位。

概念解释

  • 网络分区:集群分成两部分,无法通信。
  • 多数派:只有多数派侧能选出 Leader。
  • term 检查:AppendEntries/RequestVote 带 term,发现更高 term 就退位。

原理流程

分区:
  多数派侧(3/5):旧 Leader 继续工作
  少数派侧(2/5):旧 Leader 发心跳,但 Follower 在多数派侧不响应
    → 少数派侧 Follower 选举超时,选新 Leader
    → 但只有 2 票,不够多数派 → 选不出
    → 少数派侧不可用
分区恢复:
  少数派侧旧 Leader 发现多数派侧 term 更高 → 退位 Follower

代码或图示

5 节点,分区 3 vs 2:
  3 侧:Leader 正常,可写
  2 侧:选举超时,但只有 2 票 < 多数派 → 不可写
  → 不会出现两个可写 Leader

常见误区

  • 误区:Raft 可能脑裂。多数派规则保证只有多数派侧能选 Leader,少数派侧不可写,避免双主。
  • 误区:网络分区时两侧都能写。少数派侧无法形成多数派,写请求无法提交,集群不可用(CP)。

追问

  • 问:Raft 是 CP 还是 AP?答:CP,分区期间少数派不可写,详见 09.5.1.1。
  • 问:和 ZooKeeper 比?答:Zab(ZooKeeper 协议)类似,也是多数派 + 主从,详见 09.5.1.2。

09.9.3-009 Raft 线性一致读怎么实现?

一句话结论

Raft 读请求如果直接读 Leader 本地状态,可能在 Leader 已被取代但自己不知道的情况下读到旧值(旧 Leader 分区恢复后);线性一致读有两种方案:读 quorum(Leader 发心跳给多数派确认自己仍是 Leader,再读)或 ReadIndex(记录当前 commitIndex,等状态机应用到该 index 再读)。

概念解释

  • 旧 Leader 问题:网络分区时旧 Leader 还在少数派侧,分区恢复后它不知道自己已被取代。
  • ReadIndex:Leader 记录读请求时的 commitIndex,等状态机应用到该 index 再读。
  • Lease Read:Leader 持有租约,租约内不需要发心跳,直接读。

原理流程

方案 1(ReadIndex):
  1. Leader 记录当前 commitIndex = idx
  2. 发心跳确认自己仍是 Leader(多数派响应)
  3. 等本地状态机应用到 idx
  4. 读状态机,返回
方案 2(Lease Read):
  Leader 获得多数派心跳后,在租约期(如 50ms)内直接读
  租约内不会有新 Leader

代码或图示

etcd Linearizable Read:
  默认 ReadIndex 方式,需要一次 RTT 确认 Leader
  Serializable Read 不确认 Leader,可能读到旧值

常见误区

  • 误区:读 Leader 本地就是线性一致。如果 Leader 是旧 Leader(分区恢复后),本地状态可能落后。
  • 误区:读 quorum 要读多个节点。Raft 线性一致读仍走 Leader,只是 Leader 先确认自己身份。

追问

  • 问:Lease Read 有什么风险?答:依赖时钟,租约期不能太长,时钟漂移可能导致脑裂。
  • 问:etcd 默认读一致性?答:默认 Serializable Read(读 Leader 本地,不确认),Linearizable Read 需要显式打开。

09.9.3-010 etcd 用的是 Raft 吗?

一句话结论

是的,etcd 基于 Raft 协议,每个 etcd 节点是一个 Raft peer,写请求走 Leader 复制日志到多数派;etcd 的 Raft 实现是 etcd-io/raft,被很多项目复用(TiKV、Dubbo3 等);etcd 是 Raft 最经典的工程实现之一。

概念解释

  • etcd Raft:etcd-io/raft 库,纯 Raft 实现。
  • 应用:etcd 元数据存储、Kubernetes 后端。
  • 特性:ReadIndex 线性读、快照压缩、成员变更。

原理流程

etcd 写:
  客户端 → Leader → 复制到多数派 → 提交 → 应用到 mvcc 存储
etcd 读:
  Serializable:读 Leader 本地
  Linearizable:ReadIndex 确认 Leader

代码或图示

etcd Raft 组:
  3 或 5 节点
  Leader 处理写,Follower 复制
  快照:日志压缩,保留最近状态

常见误区

  • 误区:etcd 是 ZooKeeper 的翻版。etcd 用 Raft,ZK 用 Zab,机制类似但不同。
  • 误区:etcd 读性能高。Raft 写必须多数派确认,读默认 Serializable 走 Leader 本地,性能不如读扩散。

追问

  • 问:etcd 快照怎么工作?答:定期把当前状态机快照,日志从快照点开始保留,节省空间。
  • 问:etcd 成员变更怎么做?答:单节点加入/退出,通过 joint consensus 或单节点变更(etcd 用单节点变更)。

待整理清单

  • [ ] Raft 论文关键术语对照
  • [ ] etcd Raft 源码走读
  • [ ] ZooKeeper Zab 与 Raft 对照