论文笔记：Paxos Made Simple

发表于 更新于 分类于

Paxos 是一种分布式共识算法，用于解决在异步通信网络中存在节点失效且本地存储可靠的情况下多个分布式节点达成一致的问题。文中的算法只解决了决议一条法案（decree）的情况。如果需要决议多条法案，可以将该算法执行多次，每次分别对应一条法案。可以想象，有可能存在一些步骤在多次决议时无需重复执行，因此在多次决议法案的情况下，该算法可以进一步优化，但没有在本文中进行具体展开。

算法原理

为了确保算法的正确性，我们需要以下 3 个基础的 safety 性质：

  1. Only a value that has been proposed may be chosen,

  2. Only a single value is chosen, and

  3. A process never learns that a value has been chosen unless it actually has been.

其中 1 排除了选中错误的提案的情况，2 排除了节点之间不一致的情况，3 排除了事先选中提案的情况（non-triviality）。

除了需要保证算法的正确性，我们还需要保证算法确实能够进行到我们想要的状态。但是在此时我们还无需精确地定义 liveness 条件，而是考虑如何在保证正确性的情况下，使得某一个值最终能被选中，并且一个进程最终能够得知这一结果。

根据以上要求，我们引入 3 个角色：提议者（proposer），仲裁者（acceptor）和学习者（learner）。每个进程都可以扮演其中一个或多个角色。

最简单的方法就是我们选定唯一一个仲裁者，所有提议者都向这一仲裁者提议，仲裁者只需接受第一个收到的提案即可满足上述所有要求。但是这种方法一旦这唯一的仲裁者失效，我们就不能获得任何进展了。因此我们必须设立多个仲裁者，集体进行多数表决。多数表决可以满足上面提到的所有基础 safety 性质，尤其是 2（反证法可证明）。

在不考虑节点失效和消息丢失的情况下，我们希望即便全局只存在 1 个提案，我们也能选中这一提案。这就要求我们满足如下性质：

P1

An acceptor must accept the first proposal that it receives.

但是这一要求会带来这样一个问题，每个提议者同时分别向一个不同的仲裁者提交不同的提案，此时每个仲裁者都接受了一个不同的提案，从而无法形成多数派。这一问题并非只能由非常罕见的情况触发，例如即便是只有两个提案同时分别被恰好一半的仲裁者所接受，此时由于一个仲裁者节点失效，导致剩下的仲裁者以同样的数量分别支持两个不同的提案，此时虽然有且仅有一个提案被选中了，我们却不能得知这是哪个提案。

因此性质 P1 和多数表决选中提案的方式决定了我们必须允许仲裁者接受多个提案。为此我们将每一个不同的提案内容进行标号，使得每一个不同的提案内容都具有不同的标号，而标号具有全序关系。这样，每个提案就都具有 \((n, v)\) 这样的形式。因此我们就可以允许仲裁者选中多个提案，只需保证这些提案具有相同的提案内容 \(v\) 即可。通过在提案编号上应用数学归纳法，我们可以用如下性质来保证这一点：

P2

If a proposal with value \(v\) is chosen, then every higher-numbered proposal that is chosen has value \(v\) .

一个提案想被选中，必须先由仲裁者接受。因此我们可以考虑在仲裁者接受提案时，对其加以约束以满足性质 P2：

P2a

If a proposal with value \(v\) is chosen, then every higher-numbered proposal accepted by any acceptor has value \(v\) .

由于通信是异步的，就会存在某个仲裁者，其并不清楚其他某个仲裁者已经接受了一个提案这种情况。此时，如果这一仲裁者收到了一份新的提案，由于性质 P1，它必须接受这份提案，而这就有可能和性质 P2a 相违背。由于所有提案都是先由提议者提出的才被仲裁者接受的，因此我们可以考虑加强条件，由提议者保证这一性质：

P2b

If a proposal with value \(v\) is chosen, then every higher-numbered proposal issued by any proposer has value \(v\).

对提案编号 \(n\) 使用数学归纳法，可知满足以下性质即可保证性质 P2b：

P2c

For any \(v\) and \(n\), if a proposal with value \(v\) and number \(n\) is issued, then there is a set \(\mathbb{S}\) consisting of a majority of acceptors such that either (a) no acceptor in \(\mathbb{S}\) has accepted any proposal numbered less than \(n\), or (b) \(v\) is the value of the highest-numbered proposal among all proposals numbered less than \(n\) accepted by the acceptors in \(\mathbb{S}\).

为了满足性质 P2c，提议者若想提议编号为 \(n\) 的提案，必须知道是否存在小于编号 \(n\) 的提案已经或者将要（在编号为 \(n\) 的提案被多数仲裁者所接受之前）被多数仲裁者所接受。我们可以获知已经被接受的提案，但是很难预测将要发出的编号为 \(n\) 的提案被多数仲裁者接受之前是否还会有其他提案被多数仲裁者所接受。为了避免这一情况，我们可以提前要求仲裁者做出承诺，不去接受小于编号为 \(n\) 的任何提案。由于 P2c 蕴含 P2b，P2b 蕴含 P2a，P2a 蕴含 P2，我们可以使用如下的算法来保证 P2c，进而满足性质 P2：

  1. A proposer chooses a new proposal number \(n\) and sends a request to each member of some set of acceptors, asking it to respond with:

    1. A promise never again to accept a proposal numbered less than \(n\), and

    2. The proposal with the highest number less than \(n\) that it has accepted, if any.

    I’ll call such a request a prepare request with number \(n\)

  2. If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number \(n\) and value \(v\), where \(v\) is the value of the highest-numbered proposal among the responses, or is any value selected by the proposer if the responders reported no proposals.

这一方法实际上违背了性质 P1。考虑到性质 P1 适用于只发起 accept 请求的情况，而我们的算法实际上存在两种请求：prepare 和 accept。收到一个 prepare 请求意味着接下来还会收到一个具有相同提案编号的 accept 请求，因此如果我们收到一个不同编号的 accept 请求时，总是可以忽略这一请求，同时不违背我们至少可以保证还有一个提案可以接受这一性质。由此我们可以得到性质 P1 的加强形式：

P1a

An acceptor can accept a proposal numbered \(n\) iff it has not responded to a prepare request having a number greater than \(n\).

由于 P1a 蕴含 P1 ，我们就得到了一个能够满足所有 safety 性质的算法。对其细节进行一些优化，可以得到以下版本：

Phase 1

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

  2. 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

  1. 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.

  2. 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\).

提议者只需遵循上述算法，就允许发起多个提议。提议者也可以在任何时间放弃一个已经发起的提案而不影响正确性。一个仲裁者如果因为已经承诺不再接受更低编号的提案而忽略（ignore）一个提议时，尽管不影响正确性，但是为了性能考虑，最好告诉该提议者目前已知的最大提案编号。

这一算法可以正确的选中一个提案，但是还需要学习者使得所有进程都知道这一结果。尽管可以让所有的仲裁者在自己选中某一提案的时候都将这一结果告知所有的学习者，这一方案需要多次（两个集合的笛卡儿积的大小）广播，性能较低。此时只需选择几个 distinguished learner 告知，再由它们告知所有 learner 即可。需要考虑到，由于消息可能丢失，可能所有的 distinguished learner 都不能得知当前被选中的提案。此时只需令提议者再次发起提案，直到有一个提案被选中，即可知道被选中的提案是什么。

这一算法虽然可以保证正确性，但是不能保证在算法结束前时时都有进展，即不能保证最终一定能达到一致决议的状态。例如两个提议者交替的提议新的提案，每个提案编号都比对方的提案编号高，这样每次的 prepare 请求都会成立，但是 accept 请求都会被拒绝，使得算法不能停机。为了保证算法能够停机，我们需要选出一个唯一的 distinguished proposer，（此处开始到本段结束不确定）只有这个提议者会在发现自己的提议被多数仲裁者忽略（ignore）时，重新选择一个新的足够大的提案号重新提交提案（其他提议者在消息丢失时可以用原来的提案号重发来保证多数仲裁者能够收到这个提案，但是被仲裁者拒绝时不重新提交提案）。这意味着，在决议冲突的情况下，总是令 distinguished proposer 获胜。此外也可以采用计算机网络中冲突避免的方式来解决这一问题，比如说发生冲突时乘性增加重新提交提案的时间间隔，不冲突时加性减少时间间隔。这样就可以实现完全不需要 leader 的情况，但是潜在的风险就是 latency 增加。

如果系统中足够多的部分（包括提议者，仲裁者和通信网络等组件）工作正常，那么选举出唯一的 distinguished proposer 即可保证 liveness。（原文并没有证明这一点，不过据说在 [4] 中有一个关于 liveness 的证明，目测在 [3] 中含有一个不太正式的证明，在 [5] 中有一个对该算法加强形式的算法的证明，但是我都还没有看）论文 [2] 中蕴含了这样一个结论，一个可靠的选举算法必须依赖于随机性或 real time（比如说 timeout 机制）。无论选举的结果如何，本论文中提到的算法的正确性都是可以保证的。（无论是否有 distinguished proposer，无论是否只有一个 distinguished proposer，都可以保证算法的正确性）

其他细节

算法需要保证每个不同的提案都有不同的提案编号，这可以通过事先给每个提议者分别指定一个不相交的数集来做到。例如，一共有 3 个提议者，则提议者 1 的提案编号只能从除以 3 余 0 的非负整数集合中取。

算法中的提案内容 \(v\) 可能需要多次传递，因此也应该保证其大小不会过大。但是有的时候确实需要对一个较大的对象达成共识，比如说 block replica。个人认为可以使用类似于 GFS 中的控制流和数据流相分离的策略 [6]，通过流式传输以节点链的顺序将较大的值事先标记并传播到每一个节点上，各个节点使用 LRU 之类的策略缓存这一内容，然后通过 Paxos 算法进行决议，这样提案内容 \(v\) 只需能够索引到这一较大的值即可。

之前的算法只能对单一法令（decree）进行决议。在实际使用中，我们经常需要使用这样的算法维护分布式节点中每个节点的状态一致 [7]。为此我们可以令每个节点保存最近的若干条状态机的指令，对指令日志进行 replica 的方式来保证状态机状态的一致。这样，我们只需确定每一条状态机指令在这个日志中的位置，即可保证状态机的一致性，即对指令日志中的每个位置运行一次 single-decree Paxos 算法。（此处开始到本段结束为个人理解）令每个进程都同时扮演提议者，仲裁者和学习者这三种角色。由于我们同时需要至少一个 distinguished learner 和唯一一个 distinguished proposer，因此不妨通过选主算法在这些进程中选出一个 leader，同时扮演 distinguished learner 和 distinguished proposer。所有的状态机指令总是发给 leader。如果状态机指令发给了其他节点，由于在决议冲突中总是 leader 获胜，将会导致该指令总是失败。每个节点保持运行固定数量的 single-decree Paxos 算法实例（instance），比如说 \(\alpha\) 个。在没有接收到任何状态机指令的时候，这些算法实例即可完成算法的 Phase 1，并且总是 leader 获胜。当 leader 收到状态机指令时，只需将该指令确定位置，并令对应该位置的 Paxos 算法实例进行 Phase 2 即可（原作者说这应该是共识算法的复杂度下界，貌似论文 [8] 证明了这一点，但是我还没看）。由于通信是异步的，因此可能会导致状态机指令中编号靠前的指令还没有提交完成 Phase 2，但是后面的指令已经提交完成 Phase 2。此时，若 leader 失效，重新选主，就会在状态机指令日志中留下一些空洞。而且由于原来的 leader 失效，也没有其他节点能够知道对应该位置的状态机指令是什么。为了不使整个状态机的运行卡住，新的 leader 可以选择在这些位置填入空指令来跳过这些空洞位置，使得整个过程继续运行下去。上面提到的针对状态机指令进行 replica 的算法，只适用于固定的节点集合。如果需要在运行时调整节点集合，最简单的方法就是将调整集合的指令也作为一条状态机指令，当前的节点集合作为状态机所维护的状态。

从两阶段提交（2PC）的角度理解 Paxos：Phase 1 要求多数节点做 Promise（prepare），Phase 2 要求这些节点 Commit（accept）。从 Quoraum 的角度理解：已经选出 Leader 的情况下，直接执行 Phase 2，此时只需写成功多数节点即可。

Reference

  • [1] Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News 32, 4 (2001), 51–58. DOI:https://doi.org/10.1145/568425.568433

  • [2] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:https://doi.org/10.1145/3149.214121

  • [3] Leslie Lamport. 1998. The Part-Time Parliament. ACM Trans. Comput. Sys-tems 16, 2 (1998), 133–169. DOI:https://doi.org/10.1145/279227.279229

  • [4] Roberto De Prisco, Butler Lampson, and Nancy Lynch. 2000. Revisiting the paxos algorithm. Theor. Comput. Sci. 243, 1–2 (2000), 35–91. DOI:https://doi.org/10.1016/S0304-3975(00)00042-6

  • [5] Leslie Lamport. 2005. Generalized Consensus and Paxos. April (2005), 60. DOI:https://doi.org/MSR-TR-2005-33

  • [6] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. Proc. Ninet. ACM Symp. Oper. Syst. Princ. - SOSP ’03 (2003), 29. DOI:https://doi.org/10.1145/945449.945450

  • [7] Fred B. Schneider and Fred B. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22, 4 (December 1990), 299–319. DOI:https://doi.org/10.1145/98163.98167

  • [8] Leslie Lamport. 2006. Lower bounds for asynchronous consensus. Distrib. Comput. 19, 2 (2006), 104–125. DOI:https://doi.org/10.1007/s00446-006-0155-x