Paxos 算法详解_paxos详细讲解

前言

本文隶属于专栏《大数据技术体系》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构和参考文献请见大数据技术体系

---

协调过程

在 Paxos 算法里，我们把每一个要写入的操作，称之为提案（Proposal）。

接受外部请求，要尝试写入数据的服务器节点，称之为提案者（Proposer），比如说，我们可以让一组服务器里面有 5 个提案者，可以接受外部的客户端请求。

在 Paxos 算法里，并不是提案者一旦接受到客户端的请求，就决定了接下来的操作和结果的，而是有一个异步协调的过程，在这个协调过程中，只有获得多数通过的请求才会被选择。

这也是为什么，我们通常会选择 3 个或者 5 个节点这样的奇数数字，因为如果是偶数的话，遇到 2:2 打平这样的事情，我们就没法做出判断了。

这个投票机制也是 Quorum 这个名字的由来，因为 Quorum 在英文里的意思就是法定人数。

一旦达到了过半数，那么对应的请求就被通过了。

既然我们的提案者已经准备好 5 个节点了，我们不妨就复用这 5 个节点，让这 5 个节点也作为 Quorum，来承担一个叫做 接受者（Acceptor） 的角色。

---

给提案编号

首先是每一个请求，我们都称之为一个“提案”。

然后每个提案都有一个编号，这个编号由两部分组成。

高位是整个提案过程中的轮数（Round），低位是我们刚才的服务器编号。

每个服务器呢，都会记录到自己至今为止看到过，或者用到过的最大的轮数。

那么，当某一台服务器，想要发起一个新提案的时候，就要用它拿到的最大轮数加上 1，作为新提案的轮数，并且把自己的服务器编号拼接上去，作为提案号发放出去。

并且这个提案号必须要存储在磁盘上，避免节点在挂掉之后，不知道最新的提案号是多少。

提案号，是提案轮数和服务器ID的组合

通过这个方式，我们就让这个提案号做到了两点：

• 首先是不会有重复的提案号，不会存在两个服务器发出相同提案号的情况；
• 其次是提案号能够按照数值大小，区分出先后和大小。即使是同一状态下不同服务器发出的提案，也能比较大小。

---

Prepare 阶段

那么，当提案者收到一条来自客户端的请求之后，它就会以提案者的身份发起提案。

提案包括了前面的提案号，我们把这个提案号就叫做 M。

这个提案会广播给所有的接受者，这个广播请求被称为 Prepare 请求。

而所有的 Acceptor 在收到提案的时候，会返回一个响应给提案者。

这个响应包含的信息是这样的：

• 首先，所有的接受者一旦收到前面的 Prepare 请求之后，都会承诺它接下来，永远不会接受提案号比当前提案号 M 小的请求；
• 其次，如果接受者之前已经接受过其他提案的内容（假设是 X）了，那么它要存储下已经接受过的内容和对应的提案号。并且在此之后，把这个提案号和已经接受过的内容 X，一起返回给提案者。而如果没有接受过，就把内容填为 NULL。

这样一个来回，就称之为 Paxos 算法里的 Prepare 阶段。

要注意，这里的接受者只是返回告知提案者信息，它还没有真正接受请求。

这个过程，本质上是提案者去查询所有的接受者，是否已经接受了别的提案。

---

Accept 阶段

当提案者收到超过半数的响应之后呢，整个提案就进入第二个阶段，也称之为 Accept 阶段。

提案者会再次发起一个广播请求，里面包含这样的信息：

• 首先仍然是一个提案号，这个提案号就是刚才的 Prepare 请求里的提案号 M；
• 其次，是提案号里面的内容，一般我们也称之为提案的值。不过这个值，就有两种情况了。

第一种情况，是之前接受者已经接受过值了。

那么这里的值，是所有接受者返回过来，接受的值当中，提案号最大的那个提案的值。

也就是说，提案者说，既然之前已经做出决策了，那么我们就遵循刚才的决策就好了。

而第二种情况，如果所有的提案者返回的都是 NULL，那么这个请求里，提案者就放上自己的值，然后告诉大家，请大家接受我这个值。

那么接受到这个 Accept 请求的接受者，在此时就可以选择接受还是拒绝这个提案的值。

通常来说：

• 如果接受者没有遇到其他并发的提案，自然会接受这个值。一旦提案者收到超过半数的接受者“接受”的请求。那么它就会确定，自己提交的值被选定了。
• 但也有可能，接受者刚才已经答应了某个新的提案者说，不能接受一个比提案号 N 早的请求。而 N>M，所以这个时候接受者会拒绝 M。

• 不管是接受还是拒绝，这个时候接受者都会把最新的提案编号 N，返回给提案者。
• 还是要注意，这个时候接受者接受了请求，并不代表这个请求在整个系统中被“选择”了。

提案者还是会等待至少一半的接受者返回的响应。

如果其中有人拒绝，那么提案者就需要放弃这一轮的提案，重新再来：生成新的提案号、发起 Prepare 请求、发起 Accept 请求。

而当超过一半人表示接受请求的时候，提案者就认为提案通过了。

当然，这个时候我们的提案虽然没有变，但是提案号已经变了。

而当没有人拒绝，并且超过一半人表示接受请求的时候，提案者就认为提案通过了。

---

算法优化

在上面的内容中，我们分别从 Proposer 和 Acceptor 对提案的生成和批准两方面来讲解了 Pxos 算法在提案选定过程中的算法细节，同时也在提案的编号全局唯一的前提下，获得了一个满足安全性需求的提案选定算法，接下来我们再对这个初步算法做一个小优化。

尽可能地忽略 Prepare 请求：

假设一个 Acceptor 收到了一个编号为 Mn 的 Prepare 请求，但此时该 Acceptor 已经对编号大于 Mn 的 Prepare 请求做出了响应，因此它肯定不会再批准任何新的编号为 Mn 的提案，那么很显然， Acceptor 就没有必要对这个 Prepare 请求做出响应，于是 Acceptor 可以选择忽略这样的 Prepare 请求。

同时， Acceptor 也可以忽略掉那些它已经批准过的提案的 Prepare 请求。

通过这个优化，每个 Acceptor 只需要记住它已经批准的提案的最大编号以及它已经做出 Prepare 请求响应的提案的最大编号，以便在出现故障或节点重启的情况下，也能保证 P2c 的不变性。

而对于 Proposer 来说，只要它可以保证不会产生具有相同编号的提案，那么就可以丢弃任意的提案以及它所有的运行时状态信息。

---

综述

综合前面讲解的内容，我们来对 Paxos 算法的提案选定过程进行一个综述。

结合 Proposer 和 Acceptor 对提案的处理逻辑，就可以得到如下类似于两阶段提交的算法执行过程。

---

阶段一

1. Proposer 选择一个提案编号 Mn ，然后向 Acceptor 的某个超过半数的子集成员发送编号为 Mn 的 Prepare 请求。
2. 如果一个 Acceptor 收到一个编号为 Mn 的 Prepare 请求，且编号 Mn 大于该 Acceptor 已经响应的所有 Prepare 请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给 Proposer，同时该 Acceptor 会承诺不会再批准任何编号小于 Mn 的提案。

举个例子来说，假定一个 Acceptor 已经响应过的所有 Prepare 请求对应的提案编号分别为 1、2、…、 5 和 7 ，那么该 Acceptor 在接收到一个编号为 8 的 Prepare 请求后，就会将编号为 7 的提案作为响应反馈给 Proposer 。

---

阶段二

1. 如果 Proposer 收到来自半数以上的 Acceptor 对于其发出的编号为 Mn 的 Prepare 请求的响应，那么它就会发送一个针对 [Mn, Vn] 提案的 Accept 请求给 Acceptor。注意， Vn 的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
2. 如果 Acceptor 收到这个针对 [Mn, Vn] 提案的 Accept 请求，只要该 Acceptor 尚未对编号大于 Mn 的 Prepare 请求做出响应，它就可以通过这个提案。

当然，在实际运行过程中，每一个 Proposer 都有可能会产生多个提案，但只要每个 Proposer 都遵循如上所述的算法运行，就一定能够保证算法执行的正确性。

值得一提的是，每个 Proposer 都可以在任意时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案被丢弃后会到达，但根据 Pxos 算法的一系列规约，依然可以保证其在提案选定上的正确性。

事实上，如果某个 Proposer 已经在试图生成编号更大的提案，那么丢弃一些旧的提案未尝不是一个好的选择。

因此，如果一个 Acceptor 因为已经收到过更大编号的 Prepare 请求而忽略某个编号更小的 Prepare 或者 Accept 请求，那么它也应当通知其对应的 Proposer ，以便该 Proposer 也能够将该提案进行丢弃。