【分布式算法】Paxos算法详解

一、为什么需要分布式一致性算法

分布式系统通常由异步网络连接的多个节点构成，每个节点有独立的计算和存储。通常来说，分布式一致性一般指的是数据的一致性。比如分布式存储系统，通常以多副本冗余的方式实现数据的可靠存储。同一份数据的多个副本必须保证一致，而数据的多个副本又存储在不同的节点中，这里的分布式一致性问题就是存储在不同节点中的数据副本的取值必须一致。

如果不保证一致性，那么就说明这个系统中的数据根本不可信，数据也就没有意义，那么这个系统也就没有任何价值可言。

在分布式系统中，各个节点之间需要进行通信来保持数据的一致性，而通信的实现方式有共享内存和消息传递两种模型。基于消息传递通信模型的分布式系统，不可避免的会发生下面的错误：机器宕机，进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。那么在这种复杂的情况下该如何保证一致性呢？

而Paxos算法就是如何快速正确的在一个分布式系统中对某个数据的值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

二、什么是Paxos算法？

Paxos 算法由 Leslie Lamport 在 1989 年提出的一个分布式共识算法，Paxos 算法较难理解，本文尝试以图形化方案解释 Paxos 算法。

Lamport 提出的 Paxos 算法包括两个部分：

• Basic Paxos 算法：多节点如何就某个值达成共识

• Multi Paxos 思想：执行多个 Basic Paxos ，就一系列的值达成共识

三、Basic Paxos算法实现流程

3.1、Basic Paxos算法能够解决什么问题？

先来看下Paxos算法能够解决什么问题，才来具体介绍Paxos的具体实现。

假设一个集群包含三个节点 A, B, C，提供只读< key-value >存储服务。只读 key-value 的意思是指，当一个 key 被创建时，它的值就确定下来了，且后面不能修改。

客户端 1 和客户端 2 同时试图创建一个 X 键。客户端 1 创建值为 "blblccc_1" 的 X ，客户端 2 创建值为 "blblccc_2" 的 X 。在这种情况下，集群如何达成共识，实现各节点上 X 的值一致呢？

3.2、Basic Paxos算法的角色组成

在Basic Paxos 算法中，存在提议者（Proposer），接受者（Acceptor），学习者（Learner）三种角色，它们的关系如下：

• 提议者（Proposer）：提议一个值，用于投票表决，可以将上图客户端 1 和客户端 2 看作提议者。实际上，提议者更多是集群内的节点，这里为了演示的方便，将客户端 1 和 2 看作提议者，不影响 Paxos 算法的实质

• 接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，例如，上图集群内的节点 A、B、C

• 学习者（Learner）：被告知投票的结果，接受达成共识的值，不参与投票的过程，存储接受数据

需要指出的是，一个节点，既可以是提议者，也可以是接受者。

在 Paxos 算法中，使用提案表示一个提议，提案包括提案编号和提议的值。接下来，我们使用 [n, v] 表示一个提案，其中， n 是提案编号， v 是提案的值。

在 Basic Paxos 中，集群中各个节点为了达成共识，需要进行 2 个阶段的协商，即准备（Prepare）阶段和接受（Accept）阶段。

3.3、如何达成共识？

想象这样一个场景，现在疫情这么严重，每个村的路都封得差不多了，就你的村委会不作为，迟迟没有什么防疫的措施。你决定给村委会提交个提案，提一些防疫的建议，除了建议之外，为了和其他村民的提案做区分，你的提案还得包含一个提案编号，来起到唯一标识的作用。 与你的做法类似，在 Basic Paxos 中，兰伯特也使用提案代表一个提议。不过在提案中，除了提案编号，还包含了提议值。为了方便演示，我使用[n, v]表示一个提案，其中 n 为提案编号，v 为提议值。 我想强调一下，整个共识协商是分 2 个阶段进行的（也就是我在 03 讲提到的二阶段提交）。那么具体要如何协商呢？

我们假设客户端 1 的提案编号为 1，客户端 2 的提案编号为 5，并假设节点 A、B 先收到来自客户端 1 的准备请求，节点 C 先收到来自客户端 2 的准备请求。

3.3.1、准备（Prepare）阶段

先来看第一个阶段，首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求：

接着，当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，将进行这样的处理：

• 由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。

• 节点 C 也是如此，它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

另外，当节点 A、B 收到提案编号为 5 的准备请求，和节点 C 收到提案编号为 1 的准备请求的时候，将进行这样的处理过程：

• 当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

• 当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。

3.3.2、接受（Accept）阶段

第二个阶段也就是接受阶段，首先客户端 1、2 在收到大多数节点的准备响应之后，会分别发送接受请求：

• 当客户端 1 收到大多数的接受者（节点 A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空（也就是图 5 中的“尚无提案”），所以就把自己的提议值 3 作为提案的值，发送接受请求[1, 3]。

• 当客户端 2 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空（也就是图 5 和图 6 中的“尚无提案”），所以就把自己的提议值 7 作为提案的值，发送接受请求[5, 7]。

当三个节点收到 2 个客户端的接受请求时，会进行这样的处理：

• 当节点 A、B、C 收到接受请求[1, 3]的时候，由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5，所以提案[1, 3]将被拒绝。

• 当节点 A、B、C 收到接受请求[5, 7]的时候，由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案[5, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。

3.4、总结

概括来说，Basic Paxos 具有以下特点：

• Basic Paxos 通过二阶段方式来达成共识，即准备阶段和接受阶段

• Basic Paxos 除了达成共识功能，还实现了容错，在少于一半节点出现故障时，集群也能工作

• 提案编号大小代表优先级。对于提案编号，接受者提供三个承诺：

  • 如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者承诺不响应这个准备请求

  • 如果接受请求中的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者承诺不通过这个提案

  • 如果按受者已通过提案，那些接受者承诺会在准备请求的响应中，包含已经通过的最大编号的提案信息

四、Multi-Paxos 算法思想

4.1、什么是Multi-Paxos 算法？

上文提到的 Basic Paxos 算法只能对单个值达成共识，对于多个值的情形，Basic Paxos 算法就不管用了。因此，Basic Paxos 算法几乎只是用来理论研究，并不直接应用在实际工作中。

所以在这里，我补充一下：兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。

4.2、Multi-Paxos 的思考

4.2.1、多次执行 Basic Paxos 的问题

如果直接通过多次执行 Basic Paxos 实例方式，来实现一系列值的共识，存在以下问题：

• 如果集群中多个提议者同时在准备阶段提交提案，可能会出现没有提议者接收到大多数准备响应，导致需要重新提交准备请求。例如，在一个 5 个节点的集群中，有 3 个节点同时作为提议者同时提交提案，那就会出现没有一个提议者获取大多数的准备响应，而需要重新提交

• 为了达成一个值的共识，需要进行 2 轮 RPC 通讯，分别是准备阶段和接受阶段，性能低下

为了解决以上问题，Multi Paxos 引入了领导者（Leader）和优化了 Basic Paxos 的执行过程。

4.2.2、领导者的引入

我们可以通过引入领导者节点，也就是说，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了：

在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法，进行投票选举产生的。

那么，如何解决第二个问题，也就是如何优化 Basic Paxos 执行呢？

4.2.3、优化 Basic Paxos 执行

准备阶段的意义，是发现接受者节点上已通过的提案的值。引入领导者后，只有领导者才可发送提议，因此，领导者的提案就已经是最新的了，不再需要通过准备阶段来发现之前被大多数节点通过的提案，领导者可以独立指定提议的值。

这样一来，准备阶段存在就没有意义了，领导者可以直接跳过准备阶段，直接进行接受阶段，减少了 RPC 通讯次数。和重复执行 Basic Paxos 相比，Multi-Paxos 引入领导者节点之后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。

4.3、Chubby 的 Multi-Paxos 实现

Google 分布式锁 Chubby 实现了 Multi Paxos 算法。Chubby 的 Multi Paxos 算法主要包括：

• Chubby 引入主节点作为领导者，即主节点作为唯一提议者，不存在多个提议者同时提交提案的情况，也不存在提案冲突的情况。Chubby 通过执行 Basic Paxos 算法进行投票选举产生主节点

• 在 Chubby 中，由于引入了主节点，因此，也去除了 Basic Paxos 的准备阶段

• 在 Chubby 中，为实现强一致性，所有的读请求和写请求都由主节点来处理

4.3.1、写请求由主节点来处理

当主节点接收到客户端的写请求，作为提议者，将数据发送给所有节点，在大多数服务器接受了这个写请求后，给客户端响应写成功。

4.3.2、读请求由主节点来处理

当主节点接收到读请求，主节点只需要查询本地数据，然后返回给客户端。

Chubby 的 Multi-Paxos 实现，尽管是一个闭源的实现，但这是 Multi-Paxos 思想在实际场景中的真正落地，Chubby 团队不仅编程实现了理论，还探索了如何补充细节。其中的思考和设计非常具有参考价值，不仅能帮助我们理解 Multi-Paxos 思想，还能帮助我们理解其他的 Multi-Paxos 算法（比如 Raft 算法）。

五、总结

本节课我主要带你了解了 Basic Paxos 的局限，以及 Chubby 的 Multi-Paxos 实现。

• 兰伯特提到的 Multi-Paxos 是一种思想，不是算法，而且还缺少算法过程的细节和编程所必须的细节，比如如何选举领导者等，这也就导致了每个人实现的 Multi-Paxos 都不一样。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列数据的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。

• Chubby 实现了主节点（也就是兰伯特提到的领导者），也实现了兰伯特提到的 “当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段” 这个优化机制，省掉 Basic Paxos 的准备阶段，提升了数据的提交效率，但是所有写请求都在主节点处理，限制了集群处理写请求的并发能力，约等于单机。

• 因为在 Chubby 的 Multi-Paxos 实现中，也约定了“大多数原则”，也就是说，只要大多数节点正常运行时，集群就能正常工作，所以 Chubby 能容错（n - 1）/2 个节点的故障。

• 本质上而言，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，是通过减少非必须的协商步骤来提升性能的。这种方法非常常用，也很有效。比如，Google 设计的 QUIC 协议，是通过减少 TCP、TLS 的协商步骤，优化 HTTPS 性能。

六、参考

• Paxos算法详解

• 分布式系列文章—Paxos算法原理与推导

• Paxos算法（一）：如何在多个节点间确定某变量的值？

• 微信自研生产级paxos类库PhxPaxos实现原理介绍