分布式共识算法入门：从 Paxos 到 Raft

引言

在分布式系统中，多个节点需要就某个值达成一致——这就是共识（Consensus）问题。 共识算法是构建高可用、强一致分布式系统的基石，ZooKeeper 的 Zab、etcd 的 Raft、 Google 的 Chubby 都是其工业实现。

本文将梳理从 Paxos 到 Raft 的演进脉络，重点解释核心概念和设计取舍。 如果你从未接触过共识算法，这篇文章可以作为良好的起点。

什么是共识问题

想象一个由三台服务器组成的集群。用户发来一条写请求：“将 X 的值设为 1”。 如果所有服务器都正常，一切好办。但如果其中一台宕机或网络中断了呢？ 我们仍然需要确保存活的服务器对该值达成一致。

这就是 共识算法 要解决的核心问题：即便存在故障， 集群中的多数节点也能对某个值达成一致，并且这个一致的结果是确定的、可被其他节点获知的。

FLP 不可能定理告诉我们：在异步通信模型中，即使只有一个节点可能故障， 也不存在一个确定性算法能保证所有非故障节点达成共识。 因此实际系统中的共识算法都做了不同程度的假设（如部分同步模型）。

Paxos：理论奠基

Lamport 在 1998 年提出了 Paxos 协议。这是共识算法的鼻祖， 后来的几乎所有共识算法都在 Paxos 的基础上做了简化和改进。

Paxos 中的核心角色有三个：

• Proposer（提议者）：提出议案，争取让某个值被接受
• Acceptor（接受者）：对议案进行投票
• Learner（学习者）：学习已被多数接受的最终结果

经典的 Paxos 分两个阶段执行：

Phase 1：Prepare 阶段

Proposer 选择一个提案编号 N，向所有 Acceptor 发送 Prepare(N) 请求。 Acceptor 承诺不再接受编号小于 N 的提案，并返回已接受的最高编号提案（如果有的话）。

Phase 2：Accept 阶段

如果 Proposer 收到多数 Acceptor 的响应，它就发送 Accept(N, Value) 请求。 Acceptor 接受该提案，除非已经响应过更高编号的 Prepare。

// Paxos 核心伪代码
class Acceptor:
    min_proposal = 0
    accepted_proposal = nil
    accepted_value = nil

    def receive_prepare(n):
        if n > min_proposal:
            min_proposal = n
            return (accepted_proposal, accepted_value)
        return reject

    def receive_accept(n, value):
        if n >= min_proposal:
            min_proposal = n
            accepted_proposal = n
            accepted_value = value
            return ok
        return reject

Paxos 的正确性早已被严格证明，但它存在几个问题：

• 难以理解：Lamport 用了一个寓言故事来解释，反而让事情变得更复杂
• Multi-Paxos：如何将单轮 Paxos 扩展为日志复制协议，原始论文没有给出清晰的指导
• 实践中的坑：活锁、Leader 选举的额外复杂性等

Raft：可理解的共识

Ongaro 在 2014 年的博士论文中提出了 Raft。它的目标是——让共识算法容易被理解， 同时在实际系统中易于实现。

Raft 的核心创新在于将共识问题分解为三个相对独立的子问题：

1. 领导者选举（Leader Election）

在 Raft 中，节点有三种状态：Leader、Follower 和 Candidate。 系统正常运行时有且仅有一个 Leader，所有的写操作都由 Leader 处理。

Leader 定期发送心跳（Heartbeat）来维持权威。如果 Follower 在超时时间内未收到心跳， 它会转换为 Candidate 并发起选举。收到多数节点投票的 Candidate 成为新 Leader。

选主超时是一个关键参数。Raft 使用随机化超时（通常是 150-300ms） 来避免多个 Candidate 同时发起选举导致的选票瓜分。

2. 日志复制（Log Replication）

Leader 收到客户端请求后，将操作追加到自己的日志中，然后并行发送 AppendEntries RPC 给所有 Follower。 当多数节点确认写入后，Leader 将该条目提交（commit），并通知 Follower。

// Raft 日志条目结构
type LogEntry struct {
    Index   uint64    // 日志索引
    Term    uint64    // 任期编号
    Command []byte    // 操作指令
}

// 日志复制流程
func (l *Leader) Replicate(entry LogEntry) {
    l.log = append(l.log, entry)
    for _, peer := range l.peers {
        go l.sendAppendEntries(peer)
    }
    // 等待多数确认
    if l.quorumAcknowledged(entry.Index) {
        l.commitIndex = entry.Index
        l.applyEntry(entry)
    }
}

3. 安全性（Safety）

Raft 通过几条约束来保证安全性（State Machine Safety）：

• Election Safety：每个任期最多只有一个 Leader
• Leader Append-Only：Leader 不会覆盖或删除自己的日志条目
• Log Matching：如果两个日志条目有相同的 Index 和 Term， 那么它们之前的所有日志都一致
• Leader Completeness：被提交的日志条目最终一定存在于后续 Leader 的日志中

Raft vs Paxos

两者的核心区别：

工业实践

以下是共识算法在工业界的典型应用：

• etcd：使用 Raft 实现的分布式 KV 存储，Kubernetes 的核心组件
• Consul：HashiCorp 的服务发现和配置工具，基于 Raft
• ZooKeeper：使用 Zab 协议（类 Paxos），Hadoop 生态的基石
• TiKV：分布式 KV 数据库，使用 Raft 实现多副本一致性

总结

Paxos 奠定了共识算法的理论基础，Raft 则在可理解性和工程实践上迈出了重要一步。 理解这两个算法，对于学习分布式系统来说是必不可少的。

值得一提的是，共识算法虽然看上去抽象，但它的设计哲学——将复杂问题分解为可管理的子问题、 用合理的假设简化模型——是值得所有系统设计者借鉴的。