分布式一致性(1)：Paxos真的很简单！

Riguz Lee · 2022-04-25 · 刨根问底, 算法, Paxos

Leslie Lamport老爷子说，Paxos很简单，简单的不能再简单🐶 我敢说，简单到全世界搞计算机起码有90%的人都得怀疑自己的智商。

“The Paxos algorithm, when presented in plain English, is very simple.” —— Leslie Lamport

为了让自己保持在自己的10%之内，最近几天又重新来学习一下Paxos。回头来看，Paxos made simple的确很简单地描述了Paxos算法。本文即记录理解此文的一些思考。

Paxos共识算法

共识问题

共识问题就是一组程序需要能够为选择某个值达成共识。首先来说，需要有至少一个提议(proposal)，然后各程序通过类似投票的方式进行选举，达成共识后，这个提议的值被称为选中(chosen)。为了保证这个过程是完备的，需要遵循几个安全性要求(safety requirements):

只有被提议的值才可能被选中，也就是说不能平白无故随便选一个值出来
有且仅有一个值会被选中
只有一个值真正被选中之后，程序才能获悉(learn)选中了此值。这个条件稍微有点奇怪，换句话表述就显得自然一些：程序必须要获悉真正被选中的值

FLP不可能原理(FLP Impossibility)已经证明，在异步的网络模型（即无超时边界）下，不存在一种共识算法能够完全满足下面三个条件：

可终止 (Liveness): 所有的节点（只要没有挂掉）最后必须要决定一个值
达成一致 (Safety): 即上述的安全性要求
容错性(Fault Tolerance)：当存在节点失败的情况下依然能够奏效

但是如果牺牲掉一些特性（比如3选2）或者使用同步的情况下，是可以实现一致性算法的。Paxos中假定遵循异步、非拜占庭容错(non-Byzantine)的网络模型：

节点可以奔溃、失败、重启，可以以任意的速度响应
消息可以经过任意长的时间投递；可以重复；可以丢失；但不会被篡改（如果是拜占庭容错，那么可以假定节点可能发出一些篡改的消息，例如被恶意攻击）

Paxos中，将参与者区分为提议者(proposers)、接受者(acceptors)、学习者(learners)。简单来说，提议者可以提出待选择的提议；接受者决定选择哪一个提议；学习者能够获悉被选中的值。

一般情况下为了简化这个过程，通常让一个分布式节点即是提议者、又是接受者。学习者不是必须的。

确定选取的提议

在Paxos made simple文中，作者通过一步一步从简单到复杂的推理过程，来得出一个最终的算法，让人印象深刻。

从最简单的情况开始。最简单的情况是，只有一个接受者，并且选择接受到的第一个提议。这样肯定可以达成一致，但是一旦这个接受者挂掉，那么就不可能会选取一个值。因此，在分布式共识算法中，需要有多个接受者，只有其中的大多数接受者都选取了一个值，才认为其被选中(chosen)。为了达成“大多数”的情况，节点总数必须为奇数 $𝑛 = 2 𝑘 + 1$ 。

这种方式下，接受者如果最多只能接受一个值，那么可以形成一个多数派，从而达成共识。考虑到消息可能丢失或者节点失败，节点是无法预测是否会有第二个消息到来，那么假设只有一个提议者，提交了一个提议，这个提议一定需要被接受。否则这种情况下，无法达成共识。这种方式被归纳为：

$𝑃 1$ : 接受者必须接受其第一次接收到的提议。 An acceptor must accept the first proposal that it receives.

这种方式存在的问题是，有可能会有多个提议者几乎同时发起了提议，而接受者分别接受到了不同的提议，假定有5个接受者、三个提议：

A，B首先接受到1，按照 $𝑃 2$ 接受了1
C，D首先收到2，接受了2
E首先收到3，接受了3

这种情况下，提议1、2、3没有一个形成多数派（至少3个接受者接受），因此无法达成一致。即便只有2个提议者1、2，一旦E挂掉，提议1、2也无法达成一致。因此，可以推论出，接受者必须要允许接受多个提议。

为了方便表示，将提议进行编号（以自然数正序），以 $< 𝑛, 𝑣 >$ 代表编号为 $𝑛$ 的提议值为 $𝑣$ 。没一个不同的提议其编号是不一样的（即便是两个提议值相同，也是不同的提议，其编号一定不相同）。在这种方式表示的情况下，一个值 $𝑣$ 被选中的条件是，有一个值为 $𝑣$ 的提议被多数派接受。

为了满足 $𝑃 1$ ，同时又能够支持接受者多次接受，那么推导出 $𝑃 2$ :

$𝑃 2$ : 如果一个值为v的提议被选中，那么其他被选中的更高序号的提议值必然为v。 If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

这个推论看起来没什么问题，但却困扰了我一段时间：既然v已经选中，又何来再选中之说呢？我们这可是basic paxos阿！选中一个值，不就结束了么？

应该这么来看待：选中首先是要站在事实的角度来看（即以上帝视角来审视），如果超过半数的接受者接受了某个提议，那么它事实上已经被选中。这是从所有接受者的角度来看的，但对于观察者（提议者）而言，是不能保证他们一定能够获悉这个结论的。提议者通过将自己的提议发送给所有的接受者，并从结果中判断是否有超过半数的接受者接受，来判断自己的提议是否被接受。

    比如两个提议者（A，B）分别提议了1,2，acceptor一定只能接受一个，
    比如1被多数接受者接受，那么<1, v1>就被选中了。
    但是假设返回给提议者的消息丢失了，对于提议者A无法确定自己的提议是否被接受；
    从而需要再发起一次投票
    但是此时，B已经获悉自己的提议被接受。
            (Acceptor 1)  (Acceptor 2)  (Acceptor 3)
   ________ ___________  ____________  _______________
   <1, v1>  | accept      | accept      |   reject 
   <2, v2>  |   reject    |   reject    | accept

因为消息可能丢失，或者节点挂掉重启。因此，当这样的情况发生时，观察者需要重新发起提议，向所有的接受者重新发起提议，然后再判断是否选中。

因此，“选中”这个事件，不论是在观察者角度、还是接受者角度，都可能发生多次；只有保证他们全部是一致的，才能满足安全性需求。所以说，即使有多个提议被事实上选中，那么他们的值必然要一致，才能保证对于所有的观察者而言，选中了一个唯一的值。

那么如何才能保证 $𝑃 2$ 呢？ $𝑃 2$ 说，如果 $𝑣$ 被选中，那么更高编号的提议被选中必然值为 $𝑣$ ；本来“选中”只需要超过半数的接受者接受即可，但是我们可以用一个更严格的条件来满足它：如果 $𝑣$ 被选中，后续所有接受者接受的更高编号的提议必然值为 $𝑣$ 。这个约束比 $𝑃 2$ 更加严格，也能够保证 $𝑣$ 被选中，因此得到：

$𝑃 2^{𝑎}$ : 如果一个值为 $𝑣$ 的提议被选中，那么其他被任意接受者接受的的更高序号的提议值都为 $𝑣$ 。 If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

P2a必须跟P1一起才能保证正确，因为 $𝑃 2^{𝑎}$ 无法适用只有一次提议的场景。而因为是异步模型，可能存在一种场景是，某个接受者接受到的第一次提议，对于其他接受者而言不是第一次了（比如一个接受者挂掉，进行第二轮投票的时候才恢复）。对于其他接受者，可以只接受自己曾经接受过的值；但是对于这个接受者，按照 $𝑃 1$ ，它必需要接受这个提议，无论其值是什么。这样就可能出现与 $𝑃 2^{𝑎}$ 冲突的情况。解决的办法也很简单，既然值是由提议者决定的，那么我们要求一旦值被选中后，提议者提出的更高序号的提议的值必须为 $𝑣$ ：

$𝑃 2^{𝑏}$ : 如果一个值为v的提议被选中，那么任意提议者提出的任意更高序号的提议值都为v。 If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v

$𝑃 2^{𝑏}$ 是比 $𝑃 2^{𝑎}$ 更严格的条件，因此 $𝑃 2^{𝑏}$ 可以满足 $𝑃 2^{𝑎}$ ，当然也满足 $𝑃 2$ 。那么如何做才能满足 $𝑃 2^{𝑏}$ 这个条件呢？通过数学归纳法，可以证明：假设提议 $< 𝑚, 𝑣 >$ 被选中，那么对于任意提议 $< 𝑛, 𝑣_{𝑛} > (𝑛 > 𝑚)$ 必定有 $𝑣_{𝑛} = 𝑣$ 。

数学归纳法分为两步：

基础步骤：验证 $𝑃 (𝑛)$ 在 $𝑛 = 1$ 时成立
归纳步骤：假设 $𝑃 (𝑘)$ 为真，证明 $𝑃 (𝑘 + 1)$ 为真

那么，如果应用到上述的条件，可以有：

基础步骤: 为m的时候， $< 𝑚, 𝑣 >$ 被选中是预设的前提，无需证明归纳假设：假设提议 $𝑚 . . (𝑛 - 1)$ 的值都为 $𝑣$ 。证明目标：现在要证明对于提议 $𝑛$ ，其值也为 $𝑣$ 。

为了完成这一目标，还需要先增加一个提议的条件 $𝑃 2^{𝑐}$ ：

$𝑃 2^{𝑐}$ : 对于任意的提议 $< 𝑛, 𝑣 >$ 被提出的条件是，存在一个多数派集合 $𝑆$ 要么满足(a)：这个集合中没有一个接受者接受过任意小于 $𝑛$ 的提议（也就是说第一次接受提议）；要么满足(b)：所有接受者中，其接受的小于 $𝑛$ 的最大编号提议的值为 $𝑣$ 。

因为 $< 𝑚, 𝑣 >$ 已经选中，所以一定存在一个多数派 $𝐶$ ，其中所有的接受者都接受了提议 $𝑚$ 。从而推断出：

$𝐶$ 中的所有接受者都接受了一个 $𝑚 . . (𝑛 - 1)$ 的提议（至少接受了 $𝑚$ ），且其中所有提议的值均为 $𝑣$ （从假设可以得出）。

对于任意一个多数派集合 $𝑆$ ，一定与 $𝐶$ 至少有一个交集，因此条件(a)不可能成立；而根据上面的推论，条件(b)是满足的。从而，一个新的提议（ $𝑛$ ）的值必然也为 $𝑣$ 。

从而，证明了 $𝑃 2^{𝑏}$ 。

要满足 $𝑃 2^{𝑐}$ ，提议者在提议 $𝑛$ 之前，必须要获悉当前小于 $𝑛$ 的最高提议的值，为了能够得到确定的结果，要求接受者不能再接受任何小于 $𝑛$ 的提议，并得到如下的一个算法：

提议者准备提交 $𝑛$ ，首先发送一个准备请求( $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒 (𝑛)$ )给接受者，要求其： = (a) 承诺不再接受任何小于n的提议
- 1. 返回其接受的小于 $𝑛$ 的最大提议（如果有的话）
如果提议者从多数接受者获得的提议值为 $𝑣$ ，那么提议者可以提议 $< 𝑛, 𝑣 >$ ；或者没有从接受者获悉已经接受的提议，那么提议者可以提议任意的值 $< 𝑛, 𝐴 𝑛 𝑦 >$ 。这个过程被称为接受请求( $𝑎 𝑐 𝑐 𝑒 𝑝 𝑡 (𝑛)$ )

对于接受者而言，可以响应任意的 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒$ 请求，而对于 $𝑎 𝑐 𝑐 𝑒 𝑝 𝑡$ 请求，必须要保证：

$𝑃 1^{𝑎}$ : 接受者当且仅当在没有响应大于 $𝑛$ 的 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒$ 请求的时候，才可以接受 $𝑛$ 。 An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n

很明显， $𝑃 1^{𝑎}$ 是包含 $𝑃 1$ 的。最后，加入了一个小的优化。如果接受者已经响应了 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒$ 的请求且大于 $𝑛$ ，那么接受者无论如何也不会再接受提议 $𝑛$ 了，因此不需要响应 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒 (𝑛)$ 和 $𝑎 𝑐 𝑐 𝑒 𝑝 𝑡 (𝑛)$ ；同样对于已经接受的提议的 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒$ 请求也不需要响应。

最终，完整的算法如下：

准备阶段: 提议者向多数派接受者发送 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒 (𝑛)$ 请求。如果接受者收到请求时 $𝑛$ 大于其响应过的任意 $𝑝 𝑟 𝑒 𝑝 𝑎 𝑟 𝑒$ 请求序号，那么它返回给提议者一个不再接受任何小于 $𝑛$ 的提议的承诺，以及其已经接受的最大的提议（如果存在的话）
提交阶段：如果从多数派接受者收到的响应

是不是真的很简单？

Ref: