共识算法：从 Paxos 到 Raft 的推导

本文是分布式系统系统学习系列的 L2 核心篇。前置：27. 一致性模型与时钟：从线性一致性到向量时钟。学完可以配合面试题食用：Paxos prepare/promise/accept、Raft vs Paxos 选举对比、etcd Raft 线性读

共识要解决什么问题

分布式系统里，多个节点就"一个值"达成一致，并且这个一致不能被推翻——这就是共识问题。注意和一致性模型的区别：线性一致性是客户看到的"像单机一样"的读写顺序；共识是内部机制，让多个副本对某个值达成不可回退的多数派同意。共识是线性一致性的实现手段之一，但不止于此。

一个典型的场景：三个节点各自存了 x = 0。客户端 A 写 x = 1，客户端 B 写 x = 2，如果不同节点看到不同顺序，就乱了。共识算法要保证：最终所有节点只认其中一个值，且一旦认了就翻不了盘。

Paxos 直觉推导：两阶段为什么能挡住旧提案

Paxos 的原始推导围绕两个角色展开：Proposer（提议者）和 Acceptor（接受者）。协议分两个阶段：

阶段一：Prepare

Proposer 生成一个全局唯一且递增的编号 N，向所有 Acceptor 发 Prepare(N)
Acceptor 收到后，如果 N 大于自己见过的最大编号，则承诺不再接受小于 N 的提案，并返回自己已接受的最大编号的提案值（如果有的话）

阶段二：Accept

Proposer 收集多数派回复。如果回复中有已接受的值，则取其中编号最大的那个作为提案值；否则可以用自己的值
向所有 Acceptor 发 Accept(N, value)
Acceptor 收到后，如果 N 不小于自己承诺过的最大编号，就接受这个提案

这个机制的核心是：编号压制。编号小的提案即使先发出，也会被编号大的提案的 Prepare 拦截。已经写入多数派的值，后续的 Proposer 通过 Prepare 阶段一定会在"编号最大的返回值"中看到它，从而不能不"继承"这个值。这就是 Paxos 的安全性（Safety）：一旦值被选定，后面的提案只能选同一个值。

mermaid

sequenceDiagram
    participant P1 as Proposer A (N=1)
    participant P2 as Proposer B (N=2)
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    Note over P1,A3: 阶段一：Prepare
    P1->>A1: Prepare(1)
    P1->>A2: Prepare(1)
    A1-->>P1: Promise(1, no previous)
    A2-->>P1: Promise(1, no previous)
    P1->>A3: Prepare(1)
    A3-->>P1: Promise(1, no previous)

    Note over P1,A3: 阶段二：Accept
    P1->>A1: Accept(1, X)
    P1->>A2: Accept(1, X)
    A1-->>P1: Accepted
    A2-->>P1: Accepted

    Note over P1,A3: 此时系统已多数派接受 X
    P2->>A2: Prepare(2)
    P2->>A3: Prepare(2)
    A2-->>P2: Promise(2, accepted N=1 value=X)
    A3-->>P2: Promise(2, no previous)
    Note over P2: 看到已接受的最大编号是 1（value=X），必须继承
    P2->>A2: Accept(2, X)
    P2->>A3: Accept(2, X)

Paxos 为什么难落地

Lamport 的 Paxos 论文是出了名的难读——文章用 "The Part-Time Parliament" 的寓言故事写的，核心的 Multi-Paxos 也是点到为止。但更根本的问题是 Paxos 的工程缺口：

多值问题：Basic Paxos 只解决"一个值"的共识。实际系统要复制日志，需要连续对多个值跑 Paxos，每个值一轮 Prepare + Accept，效率极低。
Leader 缺失：Paxos 不强制选 Leader，多个 Proposer 同时提案会产生"活锁"——互相抢编号升高，谁也没法结束一轮 Accept。
成员变更：Paxos 论文没有讨论怎么安全地增减节点，而工程上这是必须的。

Lamport 自己也承认："Paxos 的工程实现远比论文推导复杂"。业界对 Paxos 的评价是"证明你懂分布式系统，但你不会真的用它"。

Raft 三模块拆解

Raft 的核心理念是可理解性——Raft 论文（Diego Ongaro 的 PhD 论文）把共识算法拆成三个独立的子问题，每个子问题在论文的单独章节里讲清楚。

Leader 选举

Raft 把系统分成三种角色：Leader（唯一处理写入）、Candidate（竞选者）、Follower（从者）。时间是任期（term）来划分的，每个任期最多一个 Leader。

每个节点有一个随机超时（150-300ms）。Follower 在超时内没收到 Leader 的心跳，就认为 Leader 挂了，自己变成 Candidate
Candidate 给自己投票，并向其他节点发起 RequestVote RPC
获得多数派票的成为新 Leader，并开始发心跳（AppendEntries RPC 空包）
如果多个 Candidate 同时发起选举，没有谁拿到多数派，就进入下一轮随机超时重试

随机超时是 Raft 最巧妙的工程细节——它让同时发起选举的概率极低，保证了快速收敛。

日志复制

Leader 收到客户端请求后：

把请求追加到自己的日志（log entry），包含 term 和 index
并行向所有节点发 AppendEntries RPC，带上日志条目和前一条日志的 index + term
收到多数派确认后，标记该条目为已提交（committed），应用到状态机
在后续心跳中通知 Follower 该条目已提交

AppendEntries 的匹配机制是关键：Leader 选出来后，Follower 的日志可能和 Leader 不一致（滞后、多余、或冲突的条目）。Raft 的做法是强制 Follower 复制 Leader 的日志——如果 Follower 的日志在匹配位置不一致，Leader 逐层回退，直到找到双方一致的 index，然后删掉 Follower 从该位置之后的所有日志，补上 Leader 的日志。

mermaid

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2

    C->>L: SET x=1
    L->>L: Append to log (term=3, index=5)
    L->>F1: AppendEntries(term=3, prevLog(term=3,idx=4), entries=[(3,5,x=1)])
    L->>F2: AppendEntries(term=3, prevLog(term=3,idx=4), entries=[(3,5,x=1)])
    F1-->>L: OK
    F2-->>L: OK
    Note over L: 收到多数派(含自己)，commit index=5
    L->>F1: AppendEntries(commitIndex=5) [心跳/下次追加]
    L->>F2: AppendEntries(commitIndex=5)
    L-->>C: OK x=1

安全性（选举限制）

Raft 的安全性靠一个硬性约束保证：只有拥有全部已提交日志的节点才能当选 Leader。

具体说，Candidate 在 RequestVote 中带上自己的日志的最后一条 term 和 index。Follower 投票时，如果自己的日志比 Candidate 更新（按 term 比较，term 相同则 index 更大），就拒绝投票。这个机制保证了新任 Leader 一定拥有所有已提交的日志条目，不会出现新 Leader 覆盖已提交值的情况。

动手实操：用 etcdctl 观察任期变化

etcd 是一个 Raft 实现的生产级系统。下面用它的命令行工具观察 Leader 选举和任期变化。

bash

# 启动一个 3 节点 etcd 集群（单机伪集群）
etcd --name node1 --data-dir /tmp/etcd1 \
  --listen-peer-urls http://localhost:2380 \
  --listen-client-urls http://localhost:2379 \
  --advertise-client-urls http://localhost:2379 \
  --initial-advertise-peer-urls http://localhost:2380 \
  --initial-cluster 'node1=http://localhost:2380,node2=http://localhost:2381,node3=http://localhost:2382' \
  --initial-cluster-token mytoken \
  --initial-cluster-state new &

etcd --name node2 --data-dir /tmp/etcd2 \
  --listen-peer-urls http://localhost:2381 \
  --listen-client-urls http://localhost:22379 \
  --advertise-client-urls http://localhost:22379 \
  --initial-advertise-peer-urls http://localhost:2381 \
  --initial-cluster 'node1=http://localhost:2380,node2=http://localhost:2381,node3=http://localhost:2382' \
  --initial-cluster-token mytoken \
  --initial-cluster-state new &

etcd --name node3 --data-dir /tmp/etcd3 \
  --listen-peer-urls http://localhost:2382 \
  --listen-client-urls http://localhost:32379 \
  --advertise-client-urls http://localhost:32379 \
  --initial-advertise-peer-urls http://localhost:2382 \
  --initial-cluster 'node1=http://localhost:2380,node2=http://localhost:2381,node3=http://localhost:2382' \
  --initial-cluster-token mytoken \
  --initial-cluster-state new &

# 等待集群就绪
sleep 3

# 查看当前 Leader 和任期
etcdctl --endpoints=http://localhost:2379 endpoint status --write-out=table

# 停止当前 Leader（假设是 node1）
etcdctl --endpoints=http://localhost:2379 member list
# 找到 leader 的 member id，然后 kill 对应的进程

# 观察新 Leader 选出后的任期变化
etcdctl --endpoints=http://localhost:22379 endpoint status --write-out=table

运行后你会看到：当 Leader 节点被 Kill 后，其余节点会发起新一轮选举，任期号（Raft Term） 递增 1。新 Leader 的 IS LEADER 列变为 true，其他节点的 TERM 也会同步到新任期。

常见误区与小结

误区：Paxos 和 Raft 都是"选举出一个 Leader" — 不对。Paxos 本身不强制选 Leader，Multi-Paxos 才通过 leader 提升效率；Raft 把选举作为第一等公民，Leader 是系统正常运行的前提。
误区：Raft 比 Paxos 慢 — 两者在性能上接近（都是多数派写入），Raft 的强 leader 模型反而减少了冲突，吞吐不一定差。etcd 的 benchmark 显示单机可达 10k+ ops/s。
误区：共识算法保证数据不丢 — 共识只保证"已提交的日志不会被覆盖"。数据在写入多数派确认前丢失（如 Leader 挂了但日志没复制到 Follower），共识算法也无能为力。
误区：Raft 的日志复制慢是因为要等所有 Follower 确认 — 实际 Raft 只需要多数派确认（包括 Leader 自己），不是所有节点。3 节点集群等 2 个确认，5 节点集群等 3 个确认。
误区：Leader 换了，未提交的日志自动丢失 — 对，这是设计行为。Raft 不会把未提交的日志传给新 Leader，新 Leader 会强制 Follower 同步自己的日志，未提交的旧日志被覆盖。

小结

共识算法是分布式系统最难啃的骨头之一，但理解它让你对"为什么分布式这么难"有根本认识。Paxos 给出了理论框架，Raft 给出了工程实现。两者的关系不是对手，而是"理论 -> 工程"的演进路径。下一篇文章我们看基于共识构建的协调服务——ZooKeeper 和 etcd 怎么把 Paxos/Raft 包装成实用的分布式锁和配置中心。

参考

参考：In Search of an Understandable Consensus Algorithm (Raft 论文, Diego Ongaro) / Paxos Made Simple (Lamport 2001) / etcd 源码：https://github.com/etcd-io/raft

共识算法：从 Paxos 到 Raft 的推导 ​

共识要解决什么问题 ​

Paxos 直觉推导：两阶段为什么能挡住旧提案 ​

Paxos 为什么难落地 ​

Raft 三模块拆解 ​

Leader 选举 ​

日志复制 ​

安全性（选举限制） ​

动手实操：用 etcdctl 观察任期变化 ​

常见误区与小结 ​

小结 ​

参考 ​