图解 Paxos 算法

一致性是分布式系统必须要解决的的问题，Paxos 算法就是解决分布式系统一致性的经典算法。在这篇文章中，我会用例子和图示讲解 Paxos 算法。

我们先撇开细节和定义，直接用一个例子来直观地理解一下这个算法。

想象一个用来卖票的分布式系统，就像 12306 那样。这个系统一共有五台机器，分布在不同的地点。为了讲解的方便，我们设定这个系统只卖一张票。五台机器有各自的数据库，用来储存买票者的名字。如果机器 A 认为把票卖给了我，而机器 B 认为把票卖给了你，那就糟糕了。于是我们要分布式系统的一致性，具体到这个例子就是保证不同机器中买票者的名字是同一个。

此时机器 D 收到了来自 Alice 的买票请求。于是 D 首先进入 Prepare 阶段：,

D 向其他 4 台机器发送了一条 提议（这里用蓝色的箭头表示提议）：

其中 P-1D 表示：

  1. 这是一个提议（P for Prepare）
  2. 提议的 ID 是 1D

每个提议都需要一个递增的全局唯一 ID，最简单的方法就是当前时间加上当前机器的名字。这个 ID 会贯穿整个 Paxos 流程。值得注意的是，在提议阶段，D 并没有把购买者的名字 Alice 告诉其他机器。

其他机器收到这个提议后，他们发现之前并没有收到过提议，于是同意了这份提议。具体来说是做了下面几件事：

  1. 将 P-1D 记录下来
  2. 承诺以后不再接受 ID < "1D" 的提议
  3. 向 D 回复 OK，这里用红色的箭头表示对提议的回复

D 收到其他机器的回复后，发现加上自己的同意，发现已经有超过半数的机器同意将票卖给 Alice（事实上，所有五台机器都同意这点）。即然多数派已经同意了这份提议，那么 D 就认为认为这个提议已经被通过了，于是进入了 Commit 阶段。

在 Commit 阶段，D 向所有机器发出了一个决议（这里用绿色的箭头表示表示决议）：

其中 A-1D-Alice 表示

  • 这是一个决议（A for Accept）
  • 决议的 ID 是 1D
  • 决议内容：将票卖给 Alice

其他四台机器到了这个决议后，就会把决议的内容记录下来，并返回给 D。D 最后把买票成功的消息发给 Alice，用图表示就是这样，这里用紫色的箭头表示对决议的回复：

此时，所有五台机器都认为票卖给了 Alice，一致性得到了保证。

上面的情况是所有机器和网络都能正常运行的理想情况，可使现实中总是不理想的，而分布式系统的最大价值之一就是能应对部分节点的故障，所以下面我们来模拟一下节点故障的情况。

节点故障的例子

我们假设有两台机器 B 和 E 发生了故障，那么重复一下上面的步骤，看看会发生什么。

第一步，D 接受到了 Alice 的请求，于是向其他机器发送提议：

第二步，除了发生故障的 B 和 E，其他机器都回复了提议：

第三步，D 认为提议得到了多数派（A、C、D）的认可，于是向大家发送决议

第四步，除了故障机外，其他机器都回复了决议。最后 D 向 Alice 发送购票成功的消息。

到目前为止，一切都 OK。由于只有少数的机器发生了故障，依然有一个多数派（3 台机器 > 5 台机器 / 2）存在，所以系统的运行没有受到影响。但是，如果我们这时候修好了 B 和 D，就会发现一个问题：B 和 D 就像刚苏醒的植物人，他们还以为这张票没卖出去呢！Paxos 算法如何解决这种情况呢？让我们继续这个例子：

↑ B 和 E 恢复工作了，但是他们此时没有 P-1D 和 C-1D-Alice 的信息

假如这时候 Bob 来买票了，他向机器 B 发出了买票请求，于是 B 向其他机器发送了一个提议。

对于这个提议，E 的回复是 OK，但是 A、C 和 D 的回复是 "1B" < "1D", Fail。因为在之前，A、C、D 已经承诺过了，他们不会接受 id < "1D" 的提议请求。

于是 B 只能放弃 1B 提议，而是紧接着又提出一个 ID 为 2B 提议，并将提议发送给其他机器：

然后机器其他机器都同意了这个提议，不过 A、C 和 D 在同意提议的同时，还返回了这样一条信息：「我已经把票卖给 Alice 了，你不可能通知我把票买给其他人」：

B 收到了包括自己在内的五分针对 2B 提议的同意，所以 B 可以进入下一步，也就是发表决议了。但是知道了票已经被 Alice 拿走后，由于卖掉的票是不能再拿回来的，所以 B 被迫修改决议的内容，也就是发表一个将票卖给 Alice 的决议，毕竟：

其他机器收到了这个决议后，也把这个决议写在自己的数据库中，并且将结果返回给 B。B 再通知 Bob 票已经被卖掉了：

在这个例子中，我们的分布式系统非常好地处理了节点故障的情况，最后达到的效果如下：

  1. 同一张票没有被卖给两个人。虽然 Bob 请求的机器 B 一开始并不知道票已经被 Alice 拿走了，但是最终 Bob 还是知道了。这就是最终一致性。
  2. 最终所有机器上都储存了相同的信息，也就是 P-2B 和 C-2B-Alice。

更加现实的情况

同时处理多个 paxos 实例：

在现实中，一个卖票系统不可能像上面的例子中只卖一张票。我们只要把每一张票当成一个独立的 paxos 算法流程，比如说在每个请求和响应中添加上票的唯一标示，就能从逻辑上同时处理多张票的售卖。

我们做的另一个假设是一张票只会被卖出一次，但是在现实中由于可以退票，一张票可以在退票后卖个另一位顾客。在 paxos 中，我们需要引入状态机的概念：简单来说就有一个 状态 经过一个 操作 后变成了另一个状态。

一张票被卖掉之后，它的状态由 可买 变成了 不可买，退票后其状态又重新变成了 可买。

火车票的售卖 和 银行账号的余额 都可以表示为这样的逻辑：

只要知道初始状态和所有的操作，根据状态机的逻辑就能算出当前的状态。我们可以为每一个状态制定一个 Paxos 算法实例，所有机器上使用 Paxos 算法同步了状态 1, 2, 3, … 这样就能在所有机器上都保存相同的记录。

Paxos 的详细定义

上面的例子中，整个流程并不是非常的严谨。为了更深入地理解 Paxos，我们需要在这里做一些枯燥的介绍。

一个分布式系统中又若干个节点（上面的例子中一共有五个节点，也就是五台机器），在 Paxos 算法中，每个节点可能有三种角色：proposer、acceptor 和 learner。一个节点可以身担一个或者多个角色。其中 learner 并不会影响到决策本身，所以我们在这篇文章中不会涉及到 learner。

Proposer 是提出提议（prepare request）和决议（accept request）的节点，acceptor 是接受提议和决议，并对其提议或者决议进行回复的节点。在上面的例子中，所有五个节点同时是 proposer 和 acceptor。

下面是严谨地定义一次 Paxos 流程：这里我直接引用并翻译了论文原文，斜体的部分是我自己添加的一些解释：

Phase 1. (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Phase 2. (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.，

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

阶段 1. (a) 一个 proposer 选择一个提议编号 n，然后将提议编号 n 放入 prepare request 中并发送给 acceptors 中的多数派。

在我们的例子中，proposer 会将 prepare request 发送给了所有的 acceptors，但是出于性能优化的考虑，即然它只需要大多数的 acceptors 同意，那么他可以只给 acceptors 中的一个多数派发送 prepare requests。具体发送给哪些 acceptors 由 proposer 自己决定。

(b) 如果一个 accptor 接受了一个 prepare request，其中的数字 n 大于这个 acceptor 已经回复过的所有 prepare request，那么他会回复这个 request，同时承诺不接受比 n 小的提议编号，而且会返回它已经接受过的提议中编号最大的那个提议（如果有的话）。

在我们上面的某张图中，E 只返回了 OK，因为它之前没有接受过提议，但是 ACD 除了来返回 OK 之外，还返回了之前接受过的编号最大的提议，也就是 Alice

阶段 2. (a) 如果这个 proposer 收到了来自多数 acceptors 对 prepare requests (编号 n) 的回复，那么他会对这些 acceptors 分别发送一个 accept request，其中包含提议编号 n 和一个值 v。v 是响应中的提议中编号最大的那个提议的值，如果响应中没有提议，那 v 可以是任何值。

在图 2-1-3 和 2-2-6 中，proposer 发送了 accept request（绿色的箭头）。其中 2-1-3 中的 v 可以是任何值 ，这里 proposer 选择了 Alice，但是 2-2-6 中的

(b) 如果一个 acceptor 收到了一个带有提议编号 n 的 accept request，除非它已经回应过一个有着比 n 更大的编号的 prepare request ，它会接受这个提议。

参考资料

Paxos算法的维基百科页面

Paxos Made Simple Lamport 于 2001年发布的论文。

https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf FLP 不可能原理

http://rystsov.info/2016/05/01/paxos.html 一个 Paxos 的 JavaScript 实现