平行区块链之共识篇：Paxos机制
很久以前，在爱琴海上，有一个名为Paxos的小岛，它是繁华的商业中心。财富的积累带来了民主的进步，Paxos人民推翻了古老的神权政治，开始实行希腊议会制。然而，Paxos的议会有一些奇葩之处：
✔ Paxos的议员们都忙于做生意，没有人愿意把所有时间都奉献给议会，因此Paxos议会不得不允许议员们随时自由地出入议会厅；
✔ 每个议员随身携带一个小册子，记录已经通过的议案——不能被修改，以及一些笔记——可以被涂改；
✔ Paxos议会非常嘈杂，谁也不能通过大声说话让所有其他人听到自己的声音，因此议员们需要通过服务员传递纸条来维持相互之间的通信；
✔ 不幸的是，服务员们也可能也会中途离席，这样议员们有可能需要等待很长时间才能收到消息；服务员甚至可能一去不复返，导致议员们收不到消息；服务员还很健忘，可能会重复传递纸条；
✔ 很特别的一点是，Paxos的议员不会反对其他议员提出的议题；
这就是Leslie Lamport在《The Part-Time Parliament（兼职议会）》[1]中虚构的场景——一个看起来组织十分松散的议会，它所面临的问题就像容错的分布式系统一样，其中议员代表进程（process），服务员代表网络（network）,议员中途离开代表进程失败，服务员中途离开代表网络故障。因此，Paxos算法也有一些假设[4]：
✔ 进程异步执行操作；
✔ 进程有稳定的存储空间；
✔ 进程可能失败；
✔ 进程可以在失败后重新加入；
✔ 进程之间可以通过网络来通信；
✔ 进程不会作伪；
✔ 通信是异步的；
✔ 通信可能因网络故障而延迟；
✔ 信息可能被丢失、打乱次序或者重复；
✔ 信息不会被篡改；
以Paxos议会的故事为背景，Lamport提出了第一个也是目前唯一经过严格证明的一致性算法Paxos，它用于解决一致性问题（Consensus Problem）：如何在一个节点／通信不可靠的分布式系统中就某个值达成一致。
由于Paxos一直被读者诟病为难以理解，Lamport于2001年重新整理了文字撰写了《Paxos Made Simple》[2] 。
要特别指出的是，Paxos并不考虑拜占庭将军问题：由于少数节点作恶导致消息可能被篡改。该问题同样由Lamport与其合作者提出[3]。
逻辑上来说，Paxos将分布式系统中的agent划分为三类角色：proposers，acceptors和learners。
✔ proposers负责发起提案；
✔ acceptors负责批准提案；
✔ learners负责执行通过的提案。
实际应用中，分布式系统中的每个agent可能身兼数职。
每个提案都有一个独立的编号（不可重复），编号由提出它的proposer自行决定，但proposer不能使用比自己曾用编号更小的值（也就是说，proposer使用的编号序列是递增的）。
Lamport提出一种简单的编号生成规则：假设总共有M个proposer，每个proposer被分配一个1到M之间互不相同的数字；对于第i个proposer，假设其分配的数字为i，那么它第n次提案的编号为M* (n-1)+i。
如果一个提案被半数以上acceptors（多数派）批准，那么它就通过了。
考虑多个进程关于某个值提出提案的场景，达到一致性需要满足以下条件：
1) 只有被提出的值可以被选择；
2) 只有一个值可以被选择；
3) 除非一个值被选择，否则它不会被执行；
显然，如果只有一个提案被提出，那么这个提案应该被通过，因此有：
P1. 每个acceptor必须批准(accept)它收到的第一个提案；
为了满足条件（2），Lamport认为应有：
P2. 如果一个提案（其提议值为v）已经被通过，那么对于所有编号更大的被通过的提案，它们所提议的值也是v；
为了满足P2，Lamport还提出：
P2a：如果一个提案（其提议值为v）已经被通过，那么对于任何acceptor批准的编号更大的提案，它们所提议的值也是v；
P2b：如果一个提案（其提议值为v）已经被通过，那么对于任何proposer提出的编号更大的提案，它们所提议的值也是v；
P2c：对于任意的v和n，如果提案（编号n，提议值v）被提出，那么存在一个由大多数acceptors构成的集合S，满足下述两个条件之一：(a)没有成员批准过小于n的提案；（b）成员批准过的提案中，编号最大者的提议值为v；
这几个条件关系是：P2<P2a<P2b<P2c。即，P2c最严格，如果满足P2c也就满足了P2。Paxos算法就是建立在P2c上。
Paxos算法分为两阶段（如图1所示）：
1) 阶段1
a) 准备（Prepare）：一个proposer创建一个提案（编号N），向超过半数的acceptors发送包含提案的Prepare(N)消息；
b) 承诺（Promise）：acceptor收到消息后，检查提案的编号N是否大于它曾接收过的所有提案的编号，如果答案是肯定的，它会回应以Promise(Nx,Vx)消息，承诺不会回应任何编号小于N的提案，否则它将不予回应；其中，Nx和Vx是它曾批准过的提案中编号最大的提案的编号与所提议的值，如果没有批准过提案，Nx和Vx为NULL；
2) 阶段2
a) Accept Request：如果proposer收到了超过半数acceptors的Promise消息，它需要先找到这些消息中编号最大的提案的值V，然后向这些acceptors发送Accept（N，V）消息；如果所有Promise消息中Nx和Vx都为NULL，则proposer可以选择任意的值作为V；
b) Accepted：当acceptor收到Accept（N，V）消息，它首先检查是否已承诺过编号大于N的提案，如果答案是否定的，它就批准该提案。
图1 Paxos算法示意图
当部分acceptors失败时，proposer就不能收到全部消息，如图2所示。
由上图我们可以看出，当存活的acceptors占51%时（即失败的acceptors小于半数），Paxos依然可以维持运行。
当proposer失败时，等同于它放弃了当前提案，这并不会影响acceptors的工作；在实际应用中，可以由其他proposer发起新的提案[4] 。
但是，当多个proposer发起提案时，有可能造成冲突。如下图3所示。在左边的proposer（proposer1）发送Prepare消息（N=1）并且得到全部acceptors的承诺后，右边的proposer（proposer2）发送Prepare消息（N=2），并且也得到了全部acceptors的承诺。此时，proposer1再发送Accept消息，将不会得到任何来自acceptors的Accepted消息。为了能够通过提案，proposer1将再次发送Prepare消息（N=3），从而造成proposer2提案的失败。于是proposer2将发送Prepare消息（N=4）……从而陷入反复提案的死循环。
参考文献
[1] Lamport L. The part-time parliament[J]. ACM Transactions on Computer Systems, 1998, 16(2): 133-169.
[2] Lamport L. Paxos Made Simple[J]. Acm Sigact News, 2016, 32(4).
[3] Lamport L, Shostak R E, Pease M C, et al. The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.
[4] Paxos,https://en.wikipedia.org/wiki/Paxos_%28computer_science%29
注：本文由中科院自动化研究所曾帅整理
扫描上方二维码，关注公众号“平行区块链”，获取更多精彩内容！