Paxos Made Simple | tiny-sky 的个人博客

《Paxos Made Simple》是 Lamport 另一篇关于 Paxos 的论文，从一个一致性算法所需要满足的条件展开，向读者讲解 paxos 算法的合理性。

从整体上来说， Paxos 算法的目标就是要确保最终会有一个提案被选定，当提案被选定后，其他节点也会获取到被选定的提案。

在 Paxos 算法中存在三个角色：

Proposer (发送提案)
Acceptor (选定提案)
Learner (获取最终选定的提案)

在具体的实现中，一个节点可能充当不同的角色，这里不关心角色与节点之间的转换，不同参与者之间可以通过首发消息来进行通信，当然通信时可能会遇到各种状况：

消息在传递时的延迟、丢失，但是假设并不会被篡改(非拜占庭式容错)
节点可能会宕机，长时间任务导致的对外不可用
网络分区

提案的选定

首先从一个最简单的方式出发，如果只有一个 Acceptor 负责选定提案，多个 Proposer 来提交提案，那么只需要约定 Acceptor 选定接受到的第一个提案就行，这种方式非常的简单且易于理解，但是问题也很明显，存在单点问题，当Acceptor 宕机时，整个系统就无法工作了。

因此，为了解决这种问题，自然可以想到可以使用多个 Accepter 来接受提案，那么只要每一个 Accepter 批准它所收到的第一个提案，当有足够多的 Acceptor 也通过这条提案时(quorum 原则，满足 n/2+1),那么就可以选定此条提案。

所以，引入第一条约定：

1	P1：一个Acceptor必须批准它收到的第一个提案。

但是这样做会存在一个问题，两个 Acceptor A 与 B,两个 Proposer a 与 b,当 a 向 A 申请提案，b 向 B 申请提案，按照约定 P1 批准接受到的第一条，那么会出现每一个提案都被一半的 Acceptor 批准了，此时会导致无法选定哪个提案。

所以这势必要求我们 Acceptor 必须能够批准不止一个提案，但是 Proposer 发送提案的时机是任意的，如果不加以限制，那么提案的选定将是无法预测的，并且可能刚选定的提案，稍后就会被推翻。

所以这里我们使用一个全局的编号来标识不同的提案，并且这种编号全局唯一且递增，此时提案变成了一个由编号和 Value 组成的组合体，我们用 [编号，Value] 来表示一个提案。

但是我们的目的是确保最终只会有一个值被确立，那么现在允许多轮次的投票，势必要求我们无论经过几轮(即递增的编号值)投票，我们所能确定的 Value 有且只有一个。

所以，引入第二条约定：

1 2	P2：如果编号为 M0、Value 值为 V0 的提案（即[M0，V0]）被选定，那么所有比编号 M0 更高的，且被选定的提案，其 Value 值必须也是 V0。

因为提案的编号是全序的(唯一且单增), P2 保证了只有一个 Value 值被选定这一安全特性，同时，这句话其实还意味着既然比 M0 编号还高的提案被选定了，那么一定满足至少被一个 Acceptor 批准，随所以我们可以对 P2 进行引伸：

1
2
3

P2a：如果编号为 M0、Value 值为 V0 的提案（即[M0，V0]）被选定了，
那么所有比编号 M0 更高的，且被 Acceptor 批准的提案，其Value值
必须也是V0。

注意，此时 P2a 是对 P2 的强化，P2 针对的是比 M0 更高，且被选定的提案，而 P2a 强调的是被 Acceptor 批准的提案。Acceptor 可以批准所接触到的第一个提案，而只有被大多数 Acceptor 批准后的提案才能被选定。

消息通信是异步的，一个提案可能会被某个从来没有收到过任何提案的特殊接受者 c 所接受。设想一个新的提议者“醒来”并且提议了一个更高编号且值不同的提案的场景。P1 要求 c 不得不接受这个提案，但这又会打破 P2a 的条件。为了同时满足 P1 和 P2a，需要对 P2a 做进一步加强：

1 2	P2b：如果一个提案 [M0，V0] 被选定后，那么之后任何 Proposer 产生的编号更高的提案，其 Value 值都为 V0。

由于只有被 Proposer 提议的提案，才可以被 Acceptor 接受，所以 P2b 隐含了 P2a，也进一步隐含了 P2。

因此，接下来的重点就是论证 P2b 成立即可

假设某个提案 [M0，V0] 已经被选定了，证明任何编号 Mn＞M0 的提
案，其 Value 值都是 V0。

论文中使用数学归纳法进行论证，感兴趣的可以去看看原文，或者《从Paxos到Zookeeper：分布式一致性原理与实践》一书中的第二章，得出约束如下：

P2c：对于任意的 Mn 和 Vn，如果提案 [Mn，Vn] 被提出，那么肯定
存在一个由半数以上的 Acceptor 组成的集合 S，满足以下两个条件中的
任意一个。
· S 中不存在任何批准过编号小于Mn的提案的 Acceptor。
· 选取 S 中所有 Acceptor 批准的编号小于 Mn 的提案，其中编号最大
的那个提案其 Value 值是 Vn。

为了保证 P2c ，那么想要提议编号为 n 的提案的提议者必须获取到编号小于 n 的最大编号的提案，如果存在这样的提案，那它肯定是已经或者即将被大多数接受者所接受的提案。获知已经被接受的提案是足够简单的，但是预测未来哪些（提案会被）接受则是困难的。与其尝试去预测未来，不如让 Acceptor 承诺将来不会接受任何这样的提案来控制这个过程。换句话说，Proposer 请求 Acceptor 们不再接受任何编号比 n 小的提案。

Proposer 生成提案

现在我们来看看，在 P2c 的基础上如何进行提案的生成。对于一个 Proposer 来说，获取那些已经被通过的提案远比预测未来可能会被通过的提案来得简单。因此，Proposer 在产生一个编号为 Mn 的提案时，必须要知道当前某一个将要或已经被半数以上 Acceptor 批准的编号小于 Mn 但为最大编号的提案。并且，Proposer 会要求所有的 Acceptor都不要再批准任何编号小于Mn的提案——这就引出了如下的提案生成算法。

Proposer 选择一个新的提案编号 Mn，然后向某个 Acceptor 集
合的成员发送请求，要求该集合中的 Acceptor 做出如下回应。

向Proposer承诺，保证不再批准任何编号小于Mn的提案。
如果 Acceptor 已经批准过任何提案，那么其就向 Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值。

我们将该请求称为编号为 Mn 的提案的 Prepare 请求。

Acceptor批准提案

根据上面的内容，一个 Acceptor 可能会收到来自 Proposer 的两种请求，分别是 Prepare 请求和 Accept 请求，对这两类请求做出响应的条件分别如下。

Prepare请求：Acceptor 可以在任何时候响应一个 Prepare 请求。
Accept请求：在不违背 Accept 现有承诺的前提下，可以任意响应 Accept请求。

因此，对 Acceptor 逻辑处理的约束条件，大体可以定义如下：

1 2	P1a：一个Acceptor只要尚未响应过任何编号大于 Mn 的 Prepare 请求，那么它就可以接受这个编号为Mn的提案。

算法陈述

阶段 1：
（a）提议者选择一个提案编号 n，向“大多数”接受者发送一个带有编号 n 的 prepare 请求；
（b）如果接受者收到一个编号为 n 的 prepare 请求，且 n 比它已经响应过的任何一个 prepare 请求的编号都大，则它会向这个请求回复响应，内容包括：一个不再接受任何编号小于 n 的提案的承诺，以及它已经接受过的最大编号的提案（假如有的话）。

阶段 2：
（a）如果提议者从“大多数”接受者收到了对它前面发出的 prepare 请求的响应，它就会接着给那每一个接受者发送一个针对编号为 n 且值为 v 的提案的 accept 请求，而 v 就是它所收到的响应中最大编号的提案的值，或者是它在所有响应都表明没有接受过任何提案的前提下自由选择的值 v；
（b）如果接受者收到了一个针对编号为 n 的提案的 accept 请求，它就会接受这个请求，除非它之前已经响应过编号大于 n 的 request 请求。

提案的获取

接下来我们再来看看如何让 Learner 获取提案，大体可以有以下几种方案：

每个 Acceptor 向所有 Learner 广播

当 Acceptor 批准一个提案时，立即将该提案发送给所有 Learner。优点在与Learner 可以最快速地获取选定的提案。但是通信开销大，通信次数为 Acceptor 和 Learner 个数的乘积，效率低下，特别是在参与者众多的情况下。

主 Learner 转发

所有 Acceptor 将批准的提案发送给一个特定的主 Learner，再由主 Learner 通知其他 Learner。好处在与通信次数减少，仅为 Acceptor 和 Learner 个数的总和，降低了通信复杂度。但是主 Learner 存在单点故障问题，一旦主 Learner 故障，整个系统的提案同步过程会被阻塞。

Learner 集合协作

扩展方案二的主 Learner 概念，将主 Learner 扩展为一个 Learner 集合，Acceptor 将批准的提案发送给这个集合中的每个 Learner，集合中的 Learner 彼此通知。好处在于提高了系统的可靠性，避免了单点故障问题，Learner 集合越大，系统越稳健。但是随着 Learner 集合规模增加，网络通信复杂度也随之上升，需要在可靠性与通信开销之间找到平衡。