Paxos 和 Raft

Paxos 和 Raft 是两种最具影响力的实用共识协议，它们在复制日志上提供容崩溃的协议，是现实世界协调系统的基础。

Definition

Paxos 和 Raft 是基于法定人数的协议，允许一组副本就命令的有序序列（复制日志）达成一致，尽管存在崩溃故障，只要大多数副本保持可用，就能确保已提交的条目永不丢失或重新排序。

Scope

本主题涵盖 Paxos 家族——单决议 Paxos、Multi-Paxos 及其工程改进——以及 Raft 协议，后者围绕显式领导者、日志复制和成员变更重新组织了相同的保证，以提高可理解性。它涵盖了提议者/接受者和领导者/追随者的角色、法定人数交集、领导者选举和任期、日志匹配以及快照和重新配置的实际问题。

Core questions

• 法定人数交集和提案编号如何在不同轮次和领导者变更中保持 Paxos 的安全性？
• Raft 如何将共识分解为领导者选举、日志复制和安全性？
• 将这些协议转化为生产系统时会出现哪些工程挑战？

Key theories

单决议 Paxos 和 Multi-Paxos

Paxos 通过由单调提案编号和多数法定人数控制的准备和接受阶段就一个值达成一致；Multi-Paxos 通过由稳定领导者领导的一系列决策摊销准备阶段，以构建复制日志。

Raft 的分解

Raft 通过在每个任期选举一个单一领导者，让领导者追加追随者复制的条目，并强制执行日志匹配属性，从而达到与 Paxos 相同的安全性，刻意用可理解性和易于实现性换取最小性。

从规范到运行系统

在实践中部署 Paxos 需要处理磁盘故障、领导者租约、日志压缩和重新配置，这些细节在原始算法中通常被忽略，但对于正确性和性能至关重要。

Clinical relevance

Paxos 和 Raft 运行在广泛使用的协调服务、分布式数据库和配置存储中；理解它们对于构建或操作任何必须在故障中保持副本强一致性的系统至关重要。

History

Lamport 在其 1998 年的“兼职议会”论文中描述了 Paxos，并在 2001 年的“Paxos made simple”中对其进行了澄清；Chandra 及其同事在 2007 年报告了使其大规模运行的实际情况；Ongaro 和 Ousterhout 于 2014 年引入了 Raft，旨在使等效的保证更容易教授和实现。

Debates

共识协议中的可理解性与最小性

Raft 被明确设计为比 Paxos 更易于理解，引发了关于其额外结构（一个强大的领导者）是否牺牲了灵活性的争论；支持者认为可理解性减少了实现错误，而另一些人则指出 Paxos 变体可能更通用。

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos 和 Raft 是根本不同的算法吗？

不是——它们通过相同的多数法定人数核心和等效的安全保证解决了相同的问题。Raft 主要围绕一个强大的领导者和显式日志重新组织了 Paxos，以使协议更易于理解和实现。