一次搞懂Paxos算法

概念

Paxos算法是由计算机科学家Leslie Lamport在1990年提出的一种基于消息传递的分布式一致性算法，为了解决分布式系统中多个节点如何在面临故障或网络分区的情况下，达成一致性决策的问题。

在分布式系统中，由于网络故障、节点崩溃等因素，保证一致性变得非常困难。Paxos算法的核心目标是：即便系统中的某些节点可能出现故障或网络分区，只要大多数节点可以正常工作，算法依然能够确保结果一致性。

Paxos算法是分布式系统中解决“一致性问题”的经典方案。简单说，就是一群节点（比如多台服务器）在可能出现故障（如崩溃、网络延迟）的情况下，如何商量出一个统一的结果。

注意：Basic Paxos算法它只能对单个值达成共识，对于一系列值的共识，需要运行多个Basic Paxos实例，或者使用Multi-Paxos等优化变种。

Paxos算法比较难以理解，不过没关系，今天我们一起把它搞清。

角色与职责

Paxos算法将分布式系统中的角色分为三类。

• • 提议者（Proposer）：负责提出提案，提案包含提案编号和提议的值。提议者向接受者发送提案，尝试让接受者接受其提议的值。
• • 接受者（Acceptor）：对提议者的提案进行投票，可以接受或拒绝提案。当多数接受者接受某个提案时，该提案的值就被选定。
• • 学习者（Learner）：不参与投票决策过程，当多数接受者批准提案后，学习并记录被批准的最终结果。

图片

算法流程与步骤

Paxos算法的核心流程主要分为三个阶段：准备阶段（Prepare Phase）、批准阶段（Accept Phase）和学习阶段（Learn Phase）。

准备阶段（Prepare）：

1. 1. 提议者生成一个唯一且递增的提案编号 n，向所有接受者发送包含编号 n 的准备请求。
2. 2. 接受者收到请求后，如果编号 n 大于它之前响应过的所有提案编号，就接受该提案并承诺不再接受编号小于 n 的提案。
3. 3. 接受者返回它之前接受过的编号最大的提案（如果有的话），如何没有则返回空值。

批准阶段（Accept）：

1. 1. 提议者在收到多数接受者对准备请求的响应后，如果发现存在接受者之前批准过的提案，就将这些提案中编号最大的提案值作为自己要提议的值；否则，使用自己原本想提议的值。
2. 2. 提议者向接受者发送包含提案编号和提议值的接受请求(n, value)。
3. 3. 接受者在没有收到编号更大的准备请求的情况下，则批准该提案。

学习阶段 (Learn Phase)

当多数接受者批准提案后，学习者学习并记录最终结果。

流程图如下:

图片

（图片来源：周志明著.凤凰架构：构建可靠的大型分布式系统.机械工业出版社有限公司.2021:298.）

图片

举个例子

提议者1要把变量X的值设置成：我不会编程； 提议者2要把变量X的值设置成：编程我也会。

准备阶段

假设提议者 1 的提案编号是 1，提议者 2 的提案编号为 2，并假设接受者 A, B 先收到来自提议者 1 的准备请求，接受者 C 先收到来自提议者 2 的准备请求。

1. 1. 接受者 A, B 之前没有收到任何提案，提案1的编号是目前最大的，所以接受者 A，B 将返回“尚无提案”的准备响应，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。
2. 2. 接受者 A, B 在收到提案 2 之后，发现提案 2 的编号大于提案 1 ，于是返回“尚无提案”的准备响应，并承诺以后不再响应提案编号小于等于 2 的准备请求，不会通过编号小于 2 的提案。
3. 3. 接受者 C 之前没有收到任何提案，提案 2 的编号是目前最大的，所以接受者 C 将返回“尚无提案”的准备响应，并承诺以后不再响应提案编号小于等于 2 的准备请求，不会通过编号小于 2 的提案。
4. 4. 接受者 C 在收到提案 2 之后，又收到提案 1，直接忽略提案 1，因为提案 1 < 提案 2。

图片

批准阶段

1. 1. 提议者 1 收到接受者 A，B 返回“尚无提案”的准备响应，即提案值为空，提议者 1 把值“我不会编程”作为提案 1 的值发送给接受者 A，B，C。
2. 2. 提议者 2 收到接受者 A，B，C 返回“尚无提案”的准备响应，即提案值为空，提议者 2 把值“编程我也会”作为提案 2 的值发送给接受者 A，B，C。
3. 3. 由于接受者 A，B，C 已经承诺了提案 2 ，于是拒绝了提案 1，因为提案 1 < 提案 2， 批准了提案 2 ，最终把 X 的值设置成“编程我也会”。

图片

学习阶段

提议者将最终达成一致的提案值 X 广播给所有的学习者，学习者学习并记录该值，整个处理过程结束。

接受者存在已批准提案的情况

假设接受者 A 已经批准了提案 2 ，接受者 B、C 还未批准提案 2 ，这时候提议者 3 发起了请求，想把X的设置成“画画我也会”。

由于接受者 A 已经批准了提案 2，所以提议者 3 必须接受提案 2 的值“编程我也会”，接受者 B、C会返回空值，因为接受者 B、C 还未批准任何提案。

提议者 3 接受了提案 2 的值“编程我也会”之后，会发起批准提案 3 的请求，最终接受者会批准提案 3 ，最终值还是“编程我也会”。

这就保证了最终值的唯一性。

图片

活锁（Live Lock）

还有，要注意，多个提议者竞争可能会形成活锁（Live Lock）。

如果两个提案节点交替使用更大的提案编号使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。在算法实现中，会引入随机超时时间来避免活锁的产生。

图片

(图片来源：https://ongardie.net/static/raft/userstudy/paxos.pdf)

总结

核心要点

记住Paxos算法的几个核心要点：

• • 提案编号与优先级：提案编号用于标识提案的先后顺序，编号越大的提案优先级越高。接受者总是优先处理编号更大的提案，这保证了新的提案能够覆盖旧的提案，避免出现旧提案干扰新提案的情况。
• • 提案值一致：提议者如果发现存在接受者之前批准过的提案，就将这些提案中编号最大的提案值作为自己要提议的值；否则，使用自己原本想提议的值。
• • 多数派原则：系统中超过半数的接受者接受某个提案，就可以确定该提案的值最终达成一致。这确保了在分布式环境下，即使部分节点出现故障，也能达成一致性，并且不会出现多个不同的值同时被选定的情况。

最后，说说Paxos算法的优缺点。

优点

• • 强一致性：严格遵循多数派原则，只要多数接受者正常工作，就能保证所有节点最终对某个值达成一致，在理论上能够确保分布式系统的数据一致性，适用于对一致性要求极高的场景，如金融交易系统、分布式数据库等。
• • 容错性好：允许部分节点（不超过一半）出现故障、网络延迟等问题，不影响整个系统达成一致性。因为只要有超过半数的接受者能够正常响应，系统就能继续工作。
• • 通用性强：作为分布式一致性的基础算法，不依赖于特定的硬件环境或编程语言，可广泛应用于各种分布式系统，如分布式数据库、分布式存储系统、分布式锁等场景。

缺点

• • 实现复杂：算法本身的逻辑较为复杂，尤其是两阶段提交过程和对提案编号的管理，导致在实际实现时难度较大，开发人员需要对算法原理有深入理解，并且实现过程中容易出现错误。
• • 性能问题：在每次达成一致的过程中，提议者需要与多数接受者进行两次通信（准备阶段和接受阶段），这在网络延迟较高或节点数量较多的情况下，会导致较大的通信开销，影响系统的性能和响应速度。
• • 活锁：极端情况下可能形成活锁。

参考资料：

1、周志明著.凤凰架构：构建可靠的大型分布式系统.机械工业出版社有限公司.2021:295. 得到电子书：https://d.dedao.cn/G1mYejPQH5lLyEYA 2、https://leehao.me/%E5%9B%BE%E8%A7%A3-Paxos-%E7%AE%97%E6%B3%95/ 3、https://ongardie.net/static/raft/userstudy/paxos.pdf

zhanyd