分布式共识算法深入：从Paxos到Raft的演进与实践

引言

在分布式系统中，共识（Consensus）是最基础也是最重要的问题之一：让多个节点就某个值达成一致。这是构建可靠分布式系统的基石，广泛应用于数据库复制、配置管理、服务选举、分布式事务等场景。

从1989年Leslie Lamport提出Paxos算法至今，共识算法经历了从理论到工程的漫长演进。本文将深入解析Paxos和Raft两大主流共识算法，探讨其工程实践中的关键细节。

一、共识问题定义

共识问题的形式化定义：系统中有n个进程p₁, p₂, ..., pₙ，每个进程有一个初始值vᵢ。算法需要满足以下属性：

• 协定性（Agreement）：所有正确进程决定相同的值
• 有效性（Validity）：决定的值必须是某个进程提出的初始值
• 终止性（Termination）：所有正确进程最终都会做出决定（不会无限等待）

著名的FLP不可能定理表明：在异步网络中，即使只有一个进程可能故障，也不存在确定性算法能同时满足以上三个属性。因此，实际系统引入超时机制等变通方法。

二、Paxos算法

2.1 基本思想

Paxos将共识分解为三个阶段：Prepare阶段、Accept阶段、Learn阶段。核心思想是通过两阶段提交和多数派（Quorum）保证安全性。

Paxos定义了三种角色：

• Proposer：提出提案（Proposal），每个提案有一个唯一递增的编号
• Acceptor：对提案进行投票，存储已接受的提案
• Learner：学习已被决定的值

2.2 Basic Paxos流程

Phase 1（Prepare）：

1. Proposer选择一个提案编号n，向多数派Acceptor发送Prepare(n)请求
2. Acceptor收到Prepare(n)：若n大于已回复的所有Prepare编号，则承诺不再接受小于n的提案，并返回已接受的最大编号提案（若有）

Phase 2（Accept）：

1. Proposer收到多数派回复。若返回了已接受提案，则选择其中编号最大的提案值；否则自由选择值v
2. Proposer发送Accept(n, v)请求给Acceptor
3. Acceptor接受提案（若n >= 已承诺的最小编号）
4. 当多数派Acceptor接受后，提案被Chosen（决定），Learner学习该值

2.3 Multi-Paxos优化

Basic Paxos每次决定一个值都需要两轮RPC。Multi-Paxos通过选举Leader将Prepare阶段"缓存"，连续决定多个值时只需一次Prepare，大幅降低延迟。Raft实质上是对Multi-Paxos的重新设计和工程化实现。

三、Raft算法

3.1 设计哲学

Raft（2014年Diego Ongaro和John Ousterhout）的核心目标是可理解性（Understandability）。与Paxos的"哲学性"抽象不同，Raft通过清晰的模块划分和状态机方法，让工程人员能够更轻松地理解和实现共识算法。

3.2 核心机制

Leader选举：

• 节点有三种状态：Leader、Follower、Candidate
• Leader定期向Follower发送心跳（AppendEntries RPC）
• Follower超时未收到心跳则转为Candidate，发起选举
• 获多数票者成为新Leader

日志复制：

• Leader接收客户端请求，追加到本地日志
• 通过AppendEntries RPC将日志复制到Follower
• 当多数Follower确认后，日志被Committed（提交），应用到状态机

安全性约束：

• 选举限制：Leader必须包含所有已提交的日志（RequestVote RPC中的lastLog比较）
• 日志匹配：相同索引和 Term 的日志内容相同
• 已提交不撤销：一旦日志被Term T提交，后续Term的Leader必然包含该日志

3.3 Term与日志一致性

Raft使用 Term（任期） 作为逻辑时钟。每个Term最多一个Leader。当Leader宕机，Candidate递增Term发起选举。

日志不一致是Raft的核心挑战。当新Leader发现Follower的日志与自己不一致时：

1. 找到最后一个一致的位置
2. 删除Follower在该位置之后的日志
3. 从该位置开始发送Leader的日志

为了加速这个回退过程，实际实现（如etcd的Raft）使用ConflictIndex和ConflictTerm进行快速回溯。

四、工程实践要点

4.1 性能优化

• Pipeline复制：Leader不等当前RPC响应就发送下一批，提高吞吐量
• Batch合并：将多个客户端请求打包成一个Raft Entry，减少RPC次数
• 异步Apply：日志Committed后异步应用到状态机，不阻塞后续复制
• Read Index/Lease Read：实现线性一致性读取而不写日志
• Pre-Vote：避免网络分区节点频繁发起选举导致Term膨胀

4.2 集群成员变更

最危险的场景之一。Raft论文提出Joint Consensus方案：在变更期间使用新旧配置的联合多数派，确保不会选出两个Leader。etcd等实现使用更简单的单步变更（Single-Server Membership Changes），通过限制每次只增减一个节点来保证安全。

4.3 Snapshot与Log Compaction

无限增长的日志会耗尽磁盘空间。Raft通过Snapshot机制解决：

1. Leader定期对状态机生成快照
2. 快照包含Last Included Index和Last Included Term
3. 快照之前的日志可以安全删除
4. 新节点或落后节点通过Install RPC接收快照追赶

五、典型应用实现

基于Raft共识算法的知名系统：

系统	用途	Raft实现
etcd	Kubernetes配置存储	go-raft（官方实现）
TiDB/TiKV	分布式数据库	Rust + raft-rs
Consul	服务发现	HashiCorp Raft（Go）
CockroachDB	NewSQL数据库	Multi-Raft（Go）
SOFAJRaft	Java分布式复制	蚂蚁金服开源

六、Paxos vs Raft对比总结

维度	Paxos	Raft
可理解性	较难，抽象度高	较易，强一致性语义清晰
Leader选举	隐式（Proposer竞争竞争）	显式（Term+选举）
日志连续性	允许空洞	强制连续
成员变更	Joint Consensus	Single-Step Consensus
成熟度	理论成熟，实现少	工程化好，大量实现
适用场景	Google Chubby等	云原生分布式系统

总结

共识算法是分布式系统可靠性的核心保障。Paxos奠定了理论基础，Raft通过工程化设计让共识算法"飞入寻常百姓家"。在实践中，选择Raft还是Paxos取决于具体场景——大多数现代分布式系统（尤其是云原生项目）选择Raft，因为其工程实现友好和良好的性能特性。理解共识算法的原理和边界，是设计可靠分布式系统的必备技能。