#distributed-systems #共识协议
本页目录

Raft

当前最广泛部署的共识协议——etcd、Consul、TiKV、CockroachDB 全部基于 Raft。它的设计目标不是"最强",而是"比 Paxos 更容易理解和实现":把共识拆成 leader 选举、日志复制和安全保证三个正交的子问题。

概述

共识要解决的问题：让一组会宕机、消息会丢会乱序的机器，对"一串操作的顺序"达成一致——这是分布式数据库、配置中心、分布式锁的地基。Paxos 在理论上解决了它，但出了名地难懂难实现（连论文作者 Lamport 都补写了 Paxos Made Simple）。Diego Ongaro 2014 年的博士论文干脆把可理解性本身当设计目标，产物就是 Raft。

Raft 的分解思路：整个协议围绕一个强 leader 展开——所有写入都经过 leader、日志只从 leader 流向 follower。于是共识被拆成三个可以分开理解的子问题：

  1. Leader 选举⁠——leader 挂了怎么选出新的
  2. 日志复制⁠——leader 怎么把日志安全地铺到多数节点
  3. 安全性⁠——怎么保证换了 leader 也不会丢已提交的数据

节点只有三种角色，状态迁移一张图说完：

flowchart LR
    F["🙋 <b>Follower</b><br><small>被动应答 · 等心跳</small>"]
    C["🗳️ <b>Candidate</b><br><small>term+1 · 向全体拉票</small>"]
    L["👑 <b>Leader</b><br><small>唯一写入口 · 广播心跳</small>"]
    F -->|"选举超时:150-300ms<br>没收到心跳"| C
    C ==>|"获得多数票 ✓"| L
    C -.->|"收到新 leader 心跳<br>甘拜下风"| F
    C -.->|"选票分裂<br>term+1 重来"| C
    L -.->|"看到更高 term<br>立即退位"| F
    classDef follower fill:#64748b1f,stroke:#64748b,stroke-width:2px
    classDef candidate fill:#d2992226,stroke:#d29922,stroke-width:2px
    classDef leader fill:#4493f826,stroke:#4493f8,stroke-width:2.5px
    class F follower
    class C candidate
    class L leader

时间被切成一段段任期（term），term 号单调递增、全局起逻辑时钟的作用：每个 term 至多一个 leader；任何 RPC 双方都先比 term，看到更高的 term 就立刻降级为 follower 并更新自己——这一条规则杀死了所有"过时 leader 还以为自己是 leader"的脑裂分支。

核心数据结构

状态字段含义
持久化(每次 RPC 应答前落盘)currentTerm本节点见过的最新 term
votedFor本 term 把票投给了谁
log[]日志,每条 {term, index, command}
易失commitIndex已提交的最后一个 index
lastApplied已应用到状态机的最后一个 index
仅 leader(内存)nextIndex[]下一条要发给各 follower 的 index
matchIndex[]各 follower 已确认复制到的 index

前三个必须持久化的原因:节点重启后若忘了 votedFor,可能在同一 term 内投两次票 → 两个 leader;忘了 log 则丢已确认的数据。

Leader 选举流程

每个 follower 维护一个随机化的选举超时⁠（150-300ms）。收到 leader 的 AppendEntries（也是心跳）或投出选票就重置计时;超时了就认为 leader 已死:自增 term、转为 candidate、给自己投一票，向所有节点发 RequestVote {term, candidateId, lastLogIndex, lastLogTerm}。

收到 RequestVote 的节点按三条规则决定投不投:

  1. term < currentTerm → 拒绝（过时的 candidate）。
  2. 本 term 已经投过别人 → 拒绝（votedFor 一人一票）。
  3. candidate 的日志必须至少和我一样新⁠——比较最后一条日志:lastLogTerm 更大者新;term 相同则 lastLogIndex 更大者新。不满足 → 拒绝。

结局三选一:拿到多数票 → 成为 leader,立即广播心跳宣示主权;收到合法新 leader 的心跳 → 退回 follower;超时没有结果（选票分裂）→ term 再加一重来。⁠随机超时正是防选票分裂的手段:大家超时时间不同,几乎总有一个节点先发起并赢得选举,实践中一轮就能选出。

第 3 条投票规则是安全性的半壁江山:commit 需要多数节点确认,当选也需要多数节点投票——两个多数集必有交集⁠,交集里的节点手握已提交的日志,又只会投给"日志不比自己旧"的人,所以任何能当选的 leader 必然已经拥有全部已提交的日志。Raft 因此不需要像 Paxos 那样在选主后"补学"旧值。

日志复制(Log Replication)

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: 写请求
    L->>L: append 到本地 log (index=N, term=T)
    par 并发复制
        L->>F1: AppendEntries(prevLogIndex, prevLogTerm, entry)
        L->>F2: AppendEntries(...)
    end
    F1-->>L: ok (matchIndex=N)
    Note over L: 多数已复制 → commitIndex = N
    L->>L: apply 到状态机
    L-->>C: 返回结果
    Note over L,F2: 下次 AppendEntries 捎带新 commitIndex,<br>followers 各自 apply

AppendEntries 自带一致性检查:leader 在每条日志前捎带前一条日志的 index 和 term（prevLogIndex/prevLogTerm），follower 对不上就拒绝。leader 收到拒绝后把该 follower 的 nextIndex 往回退一格重试,直到找到两边日志最后的公共点,然后用自己的日志覆盖 follower 从那之后的所有内容⁠。这个机制保证一个不变式:⁠两条日志若在某 index 上 term 相同,则该 index 之前的内容完全一致⁠。

Commit 为什么是安全的

Commit 的定义:一条日志被多数节点持久化即算提交。关键不变式:⁠已提交的日志必然出现在此后所有 leader 的日志里⁠。

证明梗概:entry E 提交 → 多数集 S1 都有 E;新 leader 当选 → 多数集 S2 都投了票;S1 ∩ S2 非空 → 交集里的节点既有 E 又投了票 → 按投票规则,新 leader 的日志至少和它一样新 → 新 leader 必有 E。∎

一个微妙的坑(论文 Figure 8):leader 不能直接 commit 旧 term 的日志⁠,哪怕它已经铺到了多数节点——旧 term 的多数复制可能被更高 term 的日志覆盖。正确做法是只 commit 当前 term 的日志,旧日志随之间接提交。工程上 leader 上任后先提交一条本 term 的 no-op 日志,就是为了尽快把这件事了结。

Snapshot 与日志压缩

日志无限增长不可持续。做法是把状态机当前状态整体落盘,然后丢弃之前的日志:

  1. 状态机生成 snapshot,记录 lastIncludedIndex / lastIncludedTerm。
  2. 若某个 follower 落后太多(nextIndex ≤ lastIncludedIndex,对应日志已删),leader 改发 InstallSnapshot RPC,follower 直接用快照替换自己的状态。
  3. 安全删除 log[0..lastIncludedIndex]。

成员变更:Joint Consensus

集群从 3 节点扩到 5 节点,不能一刀切换配置——切换瞬间,老配置的多数(2/3)和新配置的多数(3/5)可能互不相交,⁠新旧两边各选出一个 leader,脑裂。

Raft 的解法是两阶段过渡,中间插入一个"联合配置" C(old,new):

  1. Phase 1:leader 广播 C(old,new)。此后任何决议(包括选举)都要同时取得老配置和新配置各自的多数——两边多数都点头,不可能出现两个 leader。
  2. Phase 2:C(old,new) 提交后,leader 广播 C(new),只需新配置的多数确认,过渡完成。

即使 leader 在中途崩溃,新 leader 也只会在 C(old,new) 或 C(new) 之下工作,安全性不破。工程上 etcd 采用了更简单的单节点变更⁠:每次只加/减一个节点,新旧多数集天然相交,不需要 joint consensus。

Raft 与 Paxos 的区别

RaftMulti-Paxos
Leader 选举独立子问题,随机超时驱动与复制耦合
日志连续 index,不允许空洞任意 index,允许空洞
已提交值的学习当选即拥有(投票规则保证)选主后需补学旧值
成员变更joint consensus / 单节点变更通常依赖外部机制
可理解性明确拆成 3 个子问题全耦合,需整体理解

Paxos 的原始形态与推导见 Paxos;etcd/TiKV 等生产系统在 Raft 之上的工程取舍见实际系统;共识为什么绕不开多数派、CAP 的约束见 CAP 与一致性模型。

参考

  • 论文⁠: "In Search of an Understandable Consensus Algorithm" (Ongaro & Ousterhout, 2014) · Ongaro 博士论文(含 Figure 8 反例与修正)
  • 可视化⁠: raft.github.io (交互动画,极好) · thesecretlivesofdata.com/raft
  • 实现⁠: etcd/raft (Go, 生产级) · hashicorp/raft (Go) · tikv/raft-rs (Rust)

Keywords: Raft, 共识协议, leader election, leader 选举, log replication, 日志复制, term, 任期, split vote, 脑裂, joint consensus, 成员变更, snapshot, InstallSnapshot, etcd, TiKV, quorum, 多数派

相关页面

© 2026 liz's doc