Paxos 算法

引言：希腊议会

20 世纪 80 年代，萊斯利·蘭波特 (Leslie Lamport) 构思了一个发生在希腊 Paxos 小岛上的虚构立法系统。那里的立法者（节点）经常缺席或表现得反复无常，但他们仍需通过法律（达成共识）。

Paxos 是第一个在数学上被证明能解决不可靠网络中“共识问题”的方案。它以极难理解而著称，但它却是几乎所有现代分布式系统（如 Google 的 Spanner）赖以生存的根基。

算法要解决什么问题？

• 输入： 多个节点提议不同的值。
• 输出： 所有节点对 单个 值达成一致。
• 承诺： 安全性 (Safety，只有被提议的值才会被选中) 和 活性 (Liveness，最终一定会有一个值被选中)。

核心思想 (直觉版)

Paxos 通过 三阶段协议 运行：

1. 准备 (Prepare)： 提议者发送一个带有唯一编号 ($N$) 的提议给大多数接受者。
2. 承诺 (Promise)： 如果编号 $N$ 是接受者见过的最高的，它就承诺永远不再接受编号更低的提议。
3. 接受 (Accept)： 一旦提议者收到了足够多的承诺，它就请求接受者正式“接受”这个值。

这就像一场 拍卖会：除非你的竞价编号比别人都高，否则你无法获胜；而一旦大多数人点头，这笔交易就成交了。

如何运作 (Multi-Paxos)

原始的 Paxos 只能决定 一个 值。为了构建现实中的系统（如数据库），我们使用 Multi-Paxos：

• 节点们先选出一个“领导者”（提议者）。
• 之后，领导者可以跳过后续值的“准备”阶段，使其运行速度与 Raft 相当。

典型业务场景

• ✅ 高端分布式存储： Google 的 Chubby 和 Spanner 是 Paxos 最著名的实现。

• ✅ 数据库内核： Microsoft SQL Server 和 Oracle 的内部复制机制使用了 Paxos 变体。

• ✅ 协议的标杆： 如果你正在设计一个新的分布式协议，你必须证明它是“Paxos 等价的”。

• ❌ 开发者自行实现： 除非你是分布式系统研究员，否则 永远不要 尝试为生产环境从零实现 Paxos。请使用 Raft 或成熟的组件如 Zookeeper。

性能与复杂度总结

• 复杂度： 极高。“世界上只有一种共识算法，那就是 Paxos。其他所有的一致性算法都是 Paxos 的特例。”
• 效率： 在 Multi-Paxos 形式下，效率与 Raft 类似。

小结：一句话记住它

“Paxos 是分布式系统的‘教父’。它提供了共识可能的数学证明，尽管可能需要一个博士学位才能解释清楚它到底是怎么运作的。”