分布式协议与算法（一）Paxos 算法

什么是 Paxos 算法？

Paxos 算法是莱斯利·兰伯特于 1990 年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。

兰伯特提出的 Paxos 算法包含 2 个部分：

• 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；
• 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。

Paxos 算法在分布式领域具有非常重要的地位，开源分布式锁组件 Google Chubby 的作者 Mike Burrows 说过，这个世界上只有一种一致性算法，那就是 Paxos 算法，其他的算法都是残次品。

Quorum 机制

在学习 Paxos 算法之前，我们先来看分布式系统中的 Quorum 选举算法。在各种一致性算法中都可以看到 Quorum 机制的身影，主要数学思想来源于抽屉原理，用一句话解释那就是，在 N 个副本中，一次更新成功的如果有 W 个，那么我在读取数据时是要从大于 N－W 个副本中读取，这样就能至少读到一个更新的数据了。

和 Quorum 机制对应的是 WARO，也就是Write All Read one，是一种简单的副本控制协议，当 Client 请求向某副本写数据时（更新数据），只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。

WARO 优先保证读服务，因为所有的副本更新成功，才能视为更新成功，从而保证了

所有的副本一致，这样的话，只需要读任何一个副本上的数据即可。写服务的可用性较低，因为只要有一个副本更新失败，此次写操作就视为失败了。假设有 N 个副本，N－1 个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。

WARO 牺牲了更新服务的可用性，最大程度地增强了读服务的可用性，而 Quorum 就是在更新服务和读服务之间进行的一个折衷。

Quorum 的应用

Quorum 机制无法保证强一致性，也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。

Quorum 机制的使用需要配合一个获取最新成功提交的版本号的 metadata 服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据。

Quorum 是分布式系统中常用的一种机制，用来保证数据冗余和最终一致性的投票算法，在 Paxos、Raft 和 ZooKeeper 的 Zab 等算法中，都可以看到 Quorum 机制的应用。

什么是共识问题？

假设您有一个计算机的集合，并希望它们所有人都同意某件事。这就是共识。共识意味着达成共识。

共识在分布式系统设计中经常出现。我们之所以有多种理由，需要达成共识：就谁可以访问资源（互斥）达成共识，就谁在负责资源（选举）达成共识，或者就一系列计算机之间的事件共同排序达成共识（例如，接下来要采取的措施，或状态机复制）。

共识问题可以用一种基本的，通用的方式来陈述： 一个或多个系统可以提出一些值。我们如何获得一组计算机以就这些提议的值之一达成一致？

用个场景问题来解释一下：

假设我们要实现一个分布式集群，这个集群是由节点 A、B、C 组成，提供只读 KV 存储服务。

创建只读变量的时候，必须要对它进行赋值，而且这个值后续没办法修改。因此一个节点创建只读变量后就不能再修改它了，所以所有节点必须要先对只读变量的值达成共识，然后所有节点再一起创建这个只读变量。

那么，当有多个客户端（比如客户端 1、2）访问这个系统，试图创建同一个只读变量（比如 X），客户端 1 试图创建值为 3 的 X，客户端 2 试图创建值为 7 的 X，这样要如何达成共识，实现各节点上 X 值的一致呢？

共识算法的要求：

达成共识的问题是使一组流程一致地就单个结果达成共识。这种算法有四个要求：

• 有效性。结果必须是至少一个过程提交的值。共识算法不能仅仅弥补一个值。
• 统一协议。所有节点必须选择相同的值。
• 诚信。节点只能选择一个值。也就是说，节点无法宣布一个结果，而后改变主意。
• 终止。也称为进度，每个节点最终都必须做出决定。

只要大多数进程都能正常工作，该算法就必须起作用，并且假定：

• 某些处理器可能会发生故障。流程以故障停止或故障重新启动的方式运行。
• 网络是异步的并且不可靠。邮件可能会丢失，重复或乱序接收。
• 没有拜占庭式的失败。如果传递了一条消息，则该消息没有损坏或恶意。

Basic Paxos 角色

• 提议者（Proposer）：收到客户端请求后，发起二阶段提交，提议一个值，进行共识协商。

• 接受者（Acceptor）：投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存。

• 学习者（Learner）：存储数据，不参与共识协商，只接受达成共识的值，存储保存。

一个节点（或进程）可以身兼多个角色。比如一个 3 节点的集群，1 个节点收到了请求，那么该节点将作为提议者发起二阶段提交，然后这个节点和另外 2 个节点一起作为接受者进行共识协商，就像下图的样子：

Basic Paxos 如何达成共识？

在 Basic Paxos 中，兰伯特使用提案代表一个提议。在提案中除了提案编号，还包含了提议值。

使用 [n, v] 表示一个提案，其中 n 为提案编号，v 为提议值。

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

准备（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，所以丢弃该准备请求，不做响应。

准备阶段做的事情：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求。

接受（Accept）阶段

客户端 1、2 在收到大多数节点的准备响应之后，会分别发送接受请求：

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

当客户端 2 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空（“尚无提案”），所以就把自己的提议值 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 达成了共识。

接收阶段做的事情：

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

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

深入理解

如果节点 A、B 已经通过了提案[5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 时，通过 Basic Paxos 执行“SET X = 6”，最终三个节点上 X 值是多少呢？

最终节点值应该是[9,7]，过程如下：

1、在准备阶段，节点 C 收到客户端 3 的准备请求[9,6]，因为节点 C 未收到任何提案，所以返回“尚无提案”的响应。这时如果节点 C 收到了之前客户端的准备请求[5,7]，根据提案编号 5 小于它之前响应的准备请求的提案编号9，会丢弃该准备请求。

2、客户端 3 发送准备请求[9,6] 给节点 A，B，这时因为节点 A，B 已经通过了提案[5,7]，节点 A，B 会返回 [5,7] 给客户端 3。

3、当客户端 3 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为来自节点 A、B 的准备响应中为[5, 7]和 C 的"尚无提案"，所以就把节点 A、B 的响应值 7 作为提案的值，发送接受请求[9, 7]。

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

继续深入理解

如果只有一个节点 A 通过提案[5, 7]，另外两个节点 B，C 未通过任何提案，这个时候客户端发起[9,6]的请求时，三个结点的最终值还会是[9,7]么？

答案：最终的值，可能是 6，也可能是 7，取决于节点 A 的准备响应，是否是“大多数”中的一个。

Multi-Paxos

Basic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用了。兰伯特提出可以通过多次执行 Basic Paxos 实例（比如每接收到一个值时，就执行一次 Basic Paxos 算法）实现一系列值的共识。

Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。

如果我们直接通过多次执行 Basic Paxos 实例，来实现一系列值的共识，就会存在这样两个问题：

• 如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。比如，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。

• 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。

解决第一个问题：新增的角色领导者（Leader）

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

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

解决第二个问题：优化 Basic Paxos 执行

采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化 Basic Paxos 执行。也就是说，领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段。

正常流程：

优化后流程：

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

为什么可以跳过准备阶段？

在领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。

准备阶段的意义是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。

Chubby 的 Multi-Paxos 实现

1、首先，它通过引入主节点，实现了兰伯特提到的领导者（Leader）节点的特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。

2、其次，在 Chubby 中实现了兰伯特提到的，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。

3、最后，在 Chubby 中，实现了成员变更（Group membership），以此保证节点变更的时候集群的平稳运行。

在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。为了实现了强一致性，读操作也只能在主节点上执行。 也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。

参考资料

扩展阅读

拜占庭将军问题论文

The Part-Time Parliament

参考资料

极客时间专栏：分布式技术原理与算法解析

Understanding Paxos