Raft 与 Paxos 共识算法完全指南:从原理到 etcd 实战

Raft 和 Paxos 是分布式系统里两个最重要的共识算法 —— 你看到的所有"多副本一致性"功能(etcd 选主、Kafka Controller、TiDB PD、Consul 选主)背后都是它们。Paxos 久负盛名但出了名难懂,Raft 是"给人读的 Paxos",从教学角度专门设计。这篇文章把两个算法的核心讲透,重点放在 Raft(因为更易懂且现代实现更多),Paxos 讲到能看懂论文的程度。

共识算法要解决什么

简化描述:多个节点对同一个值达成一致。听起来简单,但加上"有节点可能宕机、网络可能丢消息延迟、不能等失败节点恢复"这三个条件,问题立刻变得困难。

"FLP 不可能定理"早就证明:在异步网络 + 至少一个节点可能宕机的条件下,没有任何算法能保证总是达成共识。所以实用算法都做了某种妥协 —— Paxos / Raft 假设网络最终是同步的(消息最终能送达),用超时机制驱动进度。

Raft 的核心设计

Raft 把共识问题拆成三块,各自独立解决:

1. Leader 选举(Leader Election)
2. 日志复制(Log Replication)
3. 安全性(Safety / 各种约束保证不出错)

这种"拆分子问题"是 Raft 比 Paxos 易懂的根本原因。Paxos 把这些混在一起,Raft 解耦它们。

角色与术语

每个节点在任意时刻是三种角色之一:

• Follower:被动接收 Leader 的指令和心跳。集群启动时默认。
• Candidate:发现 Leader 没了之后,变成候选人开始拉票。
• Leader:被多数节点投票选出来,负责接收客户端请求、复制日志。

时间被分成"任期"(Term)。每个任期最多一个 Leader,Term 号单调递增。每个节点本地存当前 Term,通信时带上,看到更高 Term 的消息立刻"跟随" —— Term 是 Raft 的逻辑时钟。

Leader 选举的完整流程

初始:所有节点是 Follower,Term = 0

每个 Follower 有一个"选举超时"(150~300ms 随机),
心跳定时器在每次收到 Leader 心跳时重置。

超时未收到心跳:
  Follower -> Candidate,Term + 1,给自己投一票
  向所有其他节点发 RequestVote RPC
  其他节点:
    如果收到的 Term 高于自己:
      更新自己的 Term
      如果本任期没投过票:同意,投给该 Candidate
      已经投过:拒绝
    如果收到的 Term 低于或等于自己当前任期:拒绝

  Candidate 收到多数票(过半):成为 Leader,开始发心跳
  Candidate 收到更高 Term 的消息:变回 Follower
  Candidate 选举超时仍未当选:重新发起选举(Term + 1)

关键设计:

• 随机超时:避免所有 Follower 同时变成 Candidate 平票。
• 多数票:N 个节点需要 ⌊N/2⌋ + 1 票。这保证了"任何时刻最多一个 Leader"。
• Term 是单调时钟:任何过期消息(低 Term)都被忽略。

为什么用"多数(Majority)"

任何两个"多数"集合必然有交集 —— 这保证两个 Leader 不可能同时存在。N=5 时多数 = 3,任何两个大小为 3 的集合在 5 个里必有交集。

日志复制的完整流程

Leader 选出后,负责接收客户端命令并复制到所有 Follower:

1. 客户端 -> Leader: 命令 "set X = 5"

2. Leader:
   - 追加到自己的本地日志:Entry{term=T, index=I, cmd=...}
   - 并发向所有 Follower 发 AppendEntries RPC

3. Follower:
   - 检查 prevLogIndex / prevLogTerm 是否匹配(防止日志冲突)
   - 不匹配:拒绝,Leader 会逐步退回更早的位置重试
   - 匹配:追加日志,回 OK

4. Leader 收到多数 Follower 的 OK:
   - 把这条日志标记为"已提交"(committed)
   - 应用到状态机
   - 回复客户端成功
   - 下次心跳告知 Follower:已提交到 index I,Follower 也应用

日志结构

每个日志条目:
  index:第几条
  term:在哪个任期被加入
  cmd:实际命令

日志匹配规则(Log Matching Property):
  如果两个日志有相同的 index 和 term,那么它们包含的命令也相同;
  如果两个日志在某个 index 之前完全相同,那么从该 index 之前的所有内容也相同。

这两条性质让 Raft 的日志可以用"简单的回滚 + 追加"恢复一致 —— Follower 发现日志和 Leader 不一致时,Leader 一步步往前找到双方相同的位置,然后用 Leader 的日志覆盖 Follower 后面的部分。

安全性保证

Raft 用几条规则保证"已提交的日志永远不会丢":

选举限制

只有"日志至少和多数节点一样新"的 Candidate 才能当选。这通过 RequestVote 里附带 lastLogIndex / lastLogTerm 实现 —— 投票时比较,Candidate 日志比自己旧就拒绝。这保证新 Leader 一定包含所有已提交的日志。

不能直接提交"前任的日志"

新 Leader 看到自己日志里有上任期未提交的条目,不能直接通过"多数确认"提交它。必须先在自己任期内提交一个新条目(可以是空操作 no-op),搭便车把旧条目提交。这避免了一个微妙的安全 bug。

状态机的提交

只有提交了的日志才能应用到状态机。提交意味着"多数节点持久化",且 Leader 知道这一点。一旦提交,即使后续 Leader 切换,这条日志依然存在。

成员变更

集群从 3 节点扩到 5 节点 / 故障节点换新,要怎么动?Raft 提供"联合共识(Joint Consensus)":

旧配置 C_old        ->        新配置 C_new
        \              /
         C_old,new(过渡配置)

过渡期间,任何决策需要 C_old 多数 AND C_new 多数同时同意。
当 C_old,new 被提交后,Leader 提议切换到 C_new。

这避免了"新旧配置的两个多数集合不重叠"导致脑裂的可能。现代实现更多用"单步成员变更"(每次只加 / 减一个节点),数学上等价但实现更简单。

Raft 的实战实现:etcd 的代码

etcd 是 Raft 实现的工业标杆,3.x 用 Go 写,代码在 github.com/etcd-io/raft。简化的关键数据结构:

// 节点状态
type RaftNode struct {
    id        uint64
    term      uint64           // 当前任期
    state     StateType        // Follower / Candidate / Leader
    votedFor  uint64
    log       []LogEntry
    commitIdx uint64
    nextIdx   map[uint64]uint64   // Leader 维护每个 Follower 下次发什么
    matchIdx  map[uint64]uint64
}

// 主循环
func (r *RaftNode) Run() {
    for {
        select {
        case msg := <-r.recvC:
            r.handleMessage(msg)
        case <-r.electionTimer.C:
            r.becomeCandidate()
            r.broadcastRequestVote()
        case <-r.heartbeatTimer.C:
            if r.state == Leader {
                r.broadcastAppendEntries()
            }
        }
    }
}

Paxos 简介

Paxos 由 Leslie Lamport 1989 年提出。它的"难懂"几乎成了行业玩笑(Lamport 后来专门写了《Paxos Made Simple》)。基本结构:

角色

• Proposer:提议一个值。
• Acceptor:对提议投票。
• Learner:学习最终被接受的值。

Basic Paxos 两阶段

阶段 1:Prepare
  Proposer 选一个提议号 n,向多数 Acceptor 发 Prepare(n)
  Acceptor:
    如果 n 大于已收到的所有提议号:
      承诺不再接受小于 n 的提议
      回复:"已接受的最大提议(若有)"
    否则:拒绝

阶段 2:Accept
  Proposer 收到多数承诺后:
    选择"已被接受的提议中,提议号最大的那个的值"作为本次值;
    如果没有,用自己想提的值。
  发 Accept(n, value) 给多数 Acceptor。
  Acceptor 没在阶段 1 给出更高 n 的承诺,就接受。

被多数 Accept 的值就是"被选定"的值。

Basic Paxos 只决定一个值,实用要决定一串值(就是一个 log),用 Multi-Paxos:固定一个 Leader 提议,跳过 Prepare 阶段,直接 Accept。这就和 Raft 非常像了。

Raft vs Paxos:不是谁更好,是谁更适合教学和实现

本质算法等价 —— 都能达到分布式共识。差别:

• Raft:模块化设计(选举 / 复制 / 安全独立讲),概念清晰,易于实现和教学。
• Paxos:更基础、更通用,但角色和阶段交织,易写错。

工业界主流:新系统几乎都用 Raft(etcd、Consul、TiKV、CockroachDB、Hashicorp Vault、Kafka KRaft)。Paxos 主要在老系统(Google Chubby、Spanner 早期版本、MegaStore)。

常见误解

误解 1:"Raft 比 Paxos 快"。 错。两者性能相当,Raft 的优势在易懂和易实现。

误解 2:"Leader 是性能瓶颈"。 单 Leader 处理写,但读可以走 Follower(用 lease + 读最新 index)。且 Raft Multi-Raft 设计(每个分片自己一个 Raft Group)能让多 Leader 并行。TiKV 单集群 PB 级数据靠这个。

误解 3:"Raft 不能容忍 N/2 故障"。 能 —— 但需要 N 是奇数。3 节点容忍 1 故障,5 节点容忍 2 故障。N=2 永远容忍不了 1 节点故障(2/2 不算多数)—— 所以 Raft 集群必定奇数。

误解 4:"已提交的日志一定持久"。 是的,但前提是"多数节点真的写盘了"。如果你的实现是异步刷盘,机器突然断电仍可能丢。生产 Raft 一定要 fsync。

排查 Raft 问题的工具

# etcd
etcdctl endpoint status -w table        # 看哪个节点是 Leader、Term、Index
etcdctl endpoint health                 # 健康检查

# 看选举日志
journalctl -u etcd | grep -E "raft|election|leader"

# Prometheus 指标
etcd_server_leader_changes_seen_total   # 选举切换次数,频繁说明问题
etcd_server_proposals_failed_total      # 失败的提议
etcd_disk_wal_fsync_duration_seconds    # WAL fsync 延迟,过高影响性能

常见生产问题

问题 1:频繁 Leader 切换。 通常是网络抖动或磁盘 IO 跟不上(WAL fsync 慢)。检查节点间网络 + 磁盘 IOPS。

问题 2:日志膨胀。 日志不能无限增长。Raft 用快照(Snapshot):周期性把状态机状态快照,然后截断快照之前的日志。新加入的节点直接拉快照,而不是回放整个日志。

问题 3:写性能差。 每次写要等多数 fsync。优化:SSD、批量提交(把多个写合成一个 entry)、Pipeline(不等上一条 ack 就发下一条)。

问题 4:跨数据中心 Raft。 跨 DC 网络延迟高,Raft 性能下降明显。解决:多 Raft Group(每个分片在最佳 DC)、或用 Spanner 风格的 Paxos + TrueTime。

Multi-Raft:让 Raft 支持大数据量

单 Raft Group 的吞吐受单 Leader 限制。Multi-Raft:把数据分成多个 shard,每个 shard 一个 Raft Group,各组 Leader 可以在不同物理节点上,并行处理写入。

shard 0:Leader 在 node-1,follower 在 2、3
shard 1:Leader 在 node-2,follower 在 1、3
shard 2:Leader 在 node-3,follower 在 1、2

# 3 个节点同时做 Leader,负载均衡

TiKV、CockroachDB、YugabyteDB 都是 Multi-Raft 架构。一个集群里上千个 Raft Group 并存,自动 rebalance。这是"Raft 不可扩展"误解的反例 —— 单 Group 不可扩,但 Multi-Raft 极其可扩。

Raft 的 PreVote 优化

原始 Raft 有个问题:网络分区时,被孤立的 Follower 不停增加 Term 重选,等网络恢复后用很高的 Term 当选 Leader → 强制其他节点放弃当前 Leader,造成不必要的切换。

PreVote:正式选举前先"预投票"(不增 Term),只在能拿多数预投票时才真正发起选举。这让"被孤立的节点"不会浪费集群的 Term。etcd、TiKV、CockroachDB 都实现了 PreVote。

Joint Consensus:Raft 集群扩容的安全实现

Raft 集群从 3 节点扩到 5 节点不能"瞬间替换" —— 中途可能形成两个独立多数派(老 3 节点的多数 = 2,新 5 节点的多数 = 3,有重叠才安全)。

错误做法:配置直接 [A,B,C] -> [A,B,C,D,E]
  A 还以为多数 = 2,觉得 {A,B} ok 就 commit
  D 已经看到新配置,觉得多数 = 3,等 {A,B,D} 才 commit
  两边可能独立 commit,数据冲突!

正确:Joint Consensus 过渡
  配置 1:[A,B,C]
  配置 2:[A,B,C,D,E](过渡,需要同时是 [A,B,C] 多数 AND [A,B,C,D,E] 多数)
  配置 3:[A,B,C,D,E]

  在配置 2 期间,任何决策都需要 "旧多数 AND 新多数" 同时同意,保证不会脑裂。

这是 Raft 论文 6.2 节的内容,实际实现中可以简化为"一次只加/减一个节点",数学上保证不会脑裂(单节点变化的多数总有重叠)。etcd 现在用的就是单步成员变更。

读优化:Leader Lease 和 Read Index

Raft 严格要求"读也要走 Leader 且确认仍是 Leader 才能返回",否则可能读到陈旧数据。这让读性能受限。两种优化:

Read Index

Leader 收到读请求,先发一轮心跳确认自己仍是多数派认可的 Leader → 才返回 commitIndex 处的数据。一次网络往返而非全 Raft 提议。

Leader Lease

Leader 在心跳成功后,"租约"内可以直接答读请求,不用确认。租约时间小于选举超时,保证不会有两个 Leader 同时认为自己有效。

TiKV / etcd 都用 Lease Read 优化常规读,延迟降到一次本地 read 的成本。

Snapshot 与日志截断

Raft 日志理论上无限增长。生产实现必须周期性快照:

每 10000 条日志或每小时:
  1. 把状态机当前状态序列化到磁盘(snapshot 文件)
  2. 截断 snapshot 之前的日志

新加入节点 / 落后太多的 Follower:
  Leader 发送 InstallSnapshot RPC,直接发当前快照
  Follower 加载快照 + 后续日志,快速追上

没有 snapshot 机制的 Raft 实现是不能上生产的 —— 几天就会因为日志膨胀爆磁盘。

写在最后

Raft / Paxos 不是要你自己实现,而是要你理解你用的系统的脾气。etcd 选举抖动、Consul 集群脑裂、Kafka 控制器切换 —— 这些线上问题的根因都在共识算法的工作机制里。理解 Raft,你看 etcd 日志就能立刻判断"是不是 Leader 频繁切换""是不是某个 Follower 跟不上",而不是把这些当作黑魔法。

给一个工程心得:共识算法的核心不是"怎么投票",而是"多数派"这个概念给你的安全保证。任何"需要在多个节点间保持一致状态"的功能,问"它的多数派是什么" —— 多数派定了,一致性就有保障。这就是为什么 Zookeeper / etcd / Consul 这些"小规模强一致存储"如此重要 —— 它们是其他大型系统的"多数派服务",承担"选主、配置、协调"的角色。