基础 Paxos 算法

原论文：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

共识算法的目标：多个进程/节点提案数值，共识算法确保在提案的值中选中一个；如果没有任何值被提案，就不应该选中任何值；如果已经选中了一个值，所有进程/节点都应该学习到。

Paxos 共识算法中有三种角色：

• proposer 提议者
• acceptor 决策者
• learner 记录者

一个节点可能担任多重角色。

整套理论基于非拜占庭将军模型：

• 节点可能会出问题。所有节点都有可能在值被选中后故障或重启，要有记忆能力，不然就没法玩了。
• 消息可能延迟可能重复可能丢失，但不会损坏。

推导

最简单的办法是单决策者。存在单点故障问题，不可行。

一定是多决策者。提议者将提案发给所有决策者，当大多数决策者（超过 1/2）采纳时，该提案就被确定下来。

为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个。

P1：决策者必须采纳它收到的第一个提案。

但是存在问题：多个提议者同时的提案可能不同，导致当时每个决策者都收到了不同的提案，无法确定到底采纳那个；而且某个决策者的故障会导致它不知道哪个提案被采纳了。

要满足 P1 的隐式条件是单个决策者一定可以收到多个提案。我们通过给每个提案分配一个编号来区分决策者可能采纳的不同提案，一个完整的提案由提案编号和提案内容组成，现在假设携带了不同内容的提案的编号一定不同。

要保证所有选中（采纳）的提案都有相同的内容。

提案编号保证了：

P2：如果值为 v 的提案被选中（采纳），所有被选中（采纳）的更大编号的提案的值都为 v。

因为提案编号是递增的，所以 P2 能够保证只有一个值被采纳。

要满足 P2，必须要满足：

P2a：如果值为 v 的提案被选中，所有被选中的编号更大提案的值都是 v。

因为通讯是异步的，某个提案可能被某些从未收到过提案的决策者 c 选中。P1 要求 c 采纳该提案，但是可能违反 P2a，要同时满足 P1 和 P2a 意味着要增强 P2a：

P2b：如果值为 v 的提案被选中，所有将被处理的编号更大提案的值都是 v。

所以在提议者发出提案前就要先对其处理。

P2c：任何提案内容 v 和提案编号 n，如果编号为 n 值为 v 的提案被处理了，也就是说存在由大多数决策者组成的集合 S，S 中的决策者一个都没采纳编号小于 n 的提案，或者即使 S 中的决策者采纳了编号小于 n 的提案，其中编号最大的那个提案的值也是 v。

要满足 P2c，提议者要发出编号为 n 的提案就必须先知道哪个编号小于 n 的提案被采纳了。询问已被采纳的提案相对“预测未来”简单多了。提议者要求决策者作出承诺：决策者不会再采纳编号小于 n 的提案了。

提议者选了一个全新的编号 n 并给所有决策者发送被称为 prepare 请求的提案，要求应答：

• 一个承诺：决策者不会再采纳编号小于 n 的提案
• 决策者采纳的那个编号最大的（还是小于 n）的提案

如果提议者从大多数决策者收到 prepare 阶段的应答，就可以使用编号 n 和内容 v 组装成提案：如果决策者给了编号最大的提案的值，那就要使用 v 作为该提案的值；如果决策者没有给出被采纳的提案，就可以随心所欲用任何值。

这条提案就是 accept 请求。

以上就是提议者的算法。那决策者呢？决策者从提议者那边接收 prepare 和 accept 两种请求，忽略掉所有编号小于已采纳提案的编号的提案。决策者一定会应答 prepare 请求，但是不一定应答/采纳 accept 请求。换句话说：

P1a：如果决策者从未应答过编号大于 n 的 prepare 提案，那它会采纳编号为 n 的提案。

P1a 包含了 P1。

最后还要做点小优化。

假设一个决策者收到编号为 n 的提案，但是已经应答过编号大于 n 的 prepare 请求了，遵守承诺是不会采纳这个提案的。所以我们要让决策者忽略这类 prepare 请求，内容是已被采纳的提案的 prepare 请求也要忽略掉。

经过上述优化，决策者只需记住已被采纳的编号最大的那个提案和它应答过的 prepare 请求中的最大编号，这些信息要落盘以防决策者崩溃和重启。

the algorithm operates in the following two phases.

1. Phase 1.
   • A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
   • 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.
2. Phase 2.
   • 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.
   • 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. 阶段 1
   • 提议者选择 n 为提案编号向决策者们发送 prepare 请求。
   • 如果这条请求在决策者这大于所有已应答的 prepare 请求的编号，会给提议者承诺和应答：不会再采纳编号小于 n 的提案；已采纳的编号最大的提案，如果该提案从没被采纳过，就返回空值。
2. 阶段 2
   • 提议者收到大多数决策者 prepare 请求的应答，向所有决策者发送 accept 提案，编号为 n，如果 prepare 应答带回来的提案存在值 v，就使用这个值替换掉自己原本想要发送的提案内容 v。
   • 决策者收到编号为 n 的 accept 提案，除非已经应答过编号大于 n 的 prepare 请求，否走采纳该提案的内容 v。

当某个值被选中，未来的提案只能使用同一个值。

学习被采纳的值

记录者必须找出被大多数决策者采纳的提案。最简单粗暴的算法是每个决策者采纳提案就将它广播给所有记录者。这样记录者就可以尽快知道被采纳的值。这个消息量巨大，是决策者与记录者数量的乘积。

既然是基于非拜占庭将军模型的，那么一个记录者就可以很轻易从另一个记录者处得知被采纳的值。让决策者将提案告知某一个记录者，通过它来通知其他记录者，如此消息数量相当于决策者与记录者数量之和，但是这样是不可靠的，万一那个记录者挂了。

更普遍的是，决策者告知一组记录者来避免单点故障。

实现

Paxos 需要网络。

进程担任提议者、决策者、记录者中一个或多个角色。

要保证提案的编号不相同，这也是一个比较有趣的话题。

编号唯一的一种实现方法

• 每个提议者存下它所知道的最大的轮次 maxRound
• 生成新的提案编号
  • 递增轮次
  • 连上服务器 ID
• 将 maxRound 落盘

基础 Paxos 算法存在的问题

• 两阶段控制导致高并发情景下网络开销太大
• 如果两个提议者交替使用更大的提案编号使得准备阶段成功，但采纳失败的话，这个过程理论上可以无限持续下去，形成活锁