分布式一致性(1)：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)。为了达成“大多数”的情况，节点总数必须为奇数\(n = 2k + 1\)。
这种方式下，接受者如果最多只能接受一个值，那么可以形成一个多数派，从而达成共识。考虑到消息可能丢失或者节点失败，节点是无法预测是否会有第二个消息到来，那么假设只有一个提议者，提交了一个提议，这个提议一定需要被接受。否则这种情况下，无法达成共识。这种方式被归纳为：
\(P1\): 接受者必须接受其第一次接收到的提议。 An acceptor must accept the first proposal that it receives.
这种方式存在的问题是，有可能会有多个提议者几乎同时发起了提议，而接受者分别接受到了不同的提议，假定有5个接受者、三个提议：
- A，B首先接受到1，按照\(P2\)接受了1
- C，D首先收到2，接受了2
- E首先收到3，接受了3
这种情况下，提议1、2、3没有一个形成多数派（至少3个接受者接受），因此无法达成一致。即便只有2个提议者1、2，一旦E挂掉，提议1、2也无法达成一致。因此，可以推论出，接受者必须要允许接受多个提议。
为了方便表示，将提议进行编号（以自然数正序），以\(<n, v>\)代表编号为\(n\)的提议值为\(v\)。没一个不同的提议其编号是不一样的（即便是两个提议值相同，也是不同的提议，其编号一定不相同）。在这种方式表示的情况下，一个值\(v\)被选中的条件是，有一个值为\(v\)的提议被多数派接受。
为了满足\(P1\)，同时又能够支持接受者多次接受，那么推导出\(P2\):
\(P2\): 如果一个值为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因为消息可能丢失，或者节点挂掉重启。因此，当这样的情况发生时，观察者需要重新发起提议，向所有的接受者重新发起提议，然后再判断是否选中。
因此，“选中”这个事件，不论是在观察者角度、还是接受者角度，都可能发生多次；只有保证他们全部是一致的，才能满足安全性需求。所以说，即使有多个提议被事实上选中，那么他们的值必然要一致，才能保证对于所有的观察者而言，选中了一个唯一的值。
那么如何才能保证\(P2\)呢？\(P2\)说，如果\(v\)被选中，那么更高编号的提议被选中必然值为\(v\)；本来“选中”只需要超过半数的接受者接受即可，但是我们可以用一个更严格的条件来满足它：如果\(v\)被选中，后续所有接受者接受的更高编号的提议必然值为\(v\)。这个约束比\(P2\)更加严格，也能够保证\(v\)被选中，因此得到：
\(P2^{a}\): 如果一个值为\(v\)的提议被选中，那么其他被任意接受者接受的的更高序号的提议值都为\(v\)。 If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.
P2a必须跟P1一起才能保证正确，因为\(P2^{a}\)无法适用只有一次提议的场景。而因为是异步模型，可能存在一种场景是，某个接受者接受到的第一次提议，对于其他接受者而言不是第一次了（比如一个接受者挂掉，进行第二轮投票的时候才恢复）。对于其他接受者，可以只接受自己曾经接受过的值；但是对于这个接受者，按照\(P1\)，它必需要接受这个提议，无论其值是什么。这样就可能出现与\(P2^{a}\)冲突的情况。解决的办法也很简单，既然值是由提议者决定的，那么我们要求一旦值被选中后，提议者提出的更高序号的提议的值必须为\(v\)：
\(P2^{b}\): 如果一个值为v的提议被选中，那么任意提议者提出的任意更高序号的提议值都为v。 If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v
\(P2^{b}\)是比\(P2^{a}\)更严格的条件，因此\(P2^{b}\)可以满足\(P2^{a}\)，当然也满足\(P2\)。那么如何做才能满足\(P2^{b}\)这个条件呢？通过数学归纳法，可以证明：假设提议\(<m, v>\)被选中，那么对于任意提议\(<n, v_{n}>(n> m)\)必定有\(v_{n}=v\)。
数学归纳法分为两步：
- 基础步骤：验证\(P(n)\)在\(n=1\)时成立
- 归纳步骤：假设\(P(k)\)为真，证明\(P(k + 1)\)为真
那么，如果应用到上述的条件，可以有：
基础步骤: 为m的时候，\(<m, v>\)被选中是预设的前提，无需证明 归纳假设：假设提议\(m..(n-1)\)的值都为\(v\)。 证明目标：现在要证明对于提议\(n\)，其值也为\(v\)。
为了完成这一目标，还需要先增加一个提议的条件\(P2^{c}\)：
\(P2^{c}\): 对于任意的提议\(<n, v>\)被提出的条件是，存在一个多数派集合\(S\)要么满足(a)：这个集合中没有一个接受者接受过任意小于\(n\)的提议（也就是说第一次接受提议）；要么满足(b)：所有接受者中，其接受的小于\(n\)的最大编号提议的值为\(v\)。
因为\(<m, v>\)已经选中，所以一定存在一个多数派\(C\)，其中所有的接受者都接受了提议\(m\)。从而推断出：
\(C\)中的所有接受者都接受了一个\(m..(n-1)\)的提议（至少接受了\(m\)），且其中所有提议的值均为\(v\)（从假设可以得出）。
对于任意一个多数派集合\(S\)，一定与\(C\)至少有一个交集，因此条件(a)不可能成立；而根据上面的推论，条件(b)是满足的。从而，一个新的提议（\(n\)）的值必然也为\(v\)。
从而，证明了\(P2^{b}\)。
要满足\(P2^{c}\)，提议者在提议\(n\)之前，必须要获悉当前小于\(n\)的最高提议的值，为了能够得到确定的结果，要求接受者不能再接受任何小于\(n\)的提议，并得到如下的一个算法：
- 提议者准备提交\(n\)，首先发送一个准备请求(\(prepare(n)\))给接受者，要求其： = (a) 承诺不再接受任何小于n的提议
- 返回其接受的小于\(n\)的最大提议（如果有的话）
- 如果提议者从多数接受者获得的提议值为\(v\)，那么提议者可以提议\(<n, v>\)；或者没有从接受者获悉已经接受的提议，那么提议者可以提议任意的值\(<n, Any>\)。这个过程被称为接受请求(\(accept(n)\))
对于接受者而言，可以响应任意的\(prepare\)请求，而对于\(accept\)请求，必须要保证：
\(P1^{a}\): 接受者当且仅当在没有响应大于\(n\)的\(prepare\)请求的时候，才可以接受\(n\)。 An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n
很明显，\(P1^{a}\)是包含\(P1\)的。最后，加入了一个小的优化。如果接受者已经响应了\(prepare\)的请求且大于\(n\)，那么接受者无论如何也不会再接受提议\(n\)了，因此不需要响应\(prepare(n)\)和\(accept(n)\)；同样对于已经接受的提议的\(prepare\)请求也不需要响应。
最终，完整的算法如下：
- 准备阶段: 提议者向多数派接受者发送\(prepare(n)\)请求。如果接受者收到请求时\(n\)大于其响应过的任意\(prepare\)请求序号，那么它返回给提议者一个不再接受任何小于\(n\)的提议的承诺，以及其已经接受的最大的提议（如果存在的话）
- 提交阶段：如果从多数派接受者收到的响应
是不是真的很简单？
Ref: