Paxos算法之旅（一）追本溯源

1982年，Leslie Lamport与另两人共同发表论文描述了一种计算机容错理论。为了形象的表达其中的问题，Lamport设想出了一种场景：

拜占庭帝国有许多支军队，军队的将军们必须制订一个统一的行动计划——进攻或者撤退。将军们在地理上是分隔开来的，只能靠通讯员进行通讯。并且将军中存在叛徒。叛徒可以任意篡改消息，欺骗某些将军进攻或撤退
这就是著名的“拜占廷将军问题”。理论研究显示，在一个3N+1的系统中，只有叛徒数目小于等于N的情况下，才有可能设计出一种协议，使得不管叛徒怎样作梗也能达成一致。

大多数系统在同一局域网中，消息被篡改的情况很罕见；因硬件和网络造成的消息不完整，只需简单的校验，丢弃不完整的消息即可。因此可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。在这种情况下需要什么样的算法保证一致性呢？

Leslie Lamport在1990年提出了理论上的解决方案，并给出了严格的数学证明。介于阐述“拜占廷将军问题”时这种类比方式的成功，Lamport同样用心良苦地设想出了一种场景来描述这种算法面对的问题和解决的过程：

在古希腊有一个Paxos小岛，岛上以议会的形式通过法令。议会中的议员通过信使传递消息，议员和信使都是兼职的，随时可能离开议会厅，并且信使可能重复投递消息，也可能一去不复返。议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突
这也是Paxos算法名称的由来。于是有了《The Part-Time Parliament》这篇论文。但是论文中压根没有说Paxos小岛是虚构出来的，而是煞有介事的说是考古工作者发现了Paxos议会事务的手稿，从这些手稿猜测Paxos人议会的做法。从问题的提出到算法的推演论证，通篇贯穿了对Paxos议会历史的描述。

这篇论文提交之后，几个编辑都认为不够吸引人，要求Lamport将所有Paxos相关的类比描述都去掉。Lamport觉得这些人太没幽默感了，拒绝修改。直到8年后，有一个团队需要建设一个分布式系统，需要一种保证一致性的方法，Lamport将当年的论文交给他们，他们马上明白并去实行了。Lamport觉得时机成熟了，于是再次发表这篇论文。这次编辑同意了，并且在编者按中一本正经的说：“作者貌似是个对计算机科学偶尔感兴趣的考古学家，现在正在希腊小岛上进行野外考古作业，委托我来发表它”。。。也算是配合Lamport幽默了一把。—-这就是1998年Paxos算法的第一次公开发表。

Paxos算法用来解决通信不可靠的分布式系统中的一致性问题。通信不可靠包括：消息会延迟、重复投递甚至丢失，但是消息不会被篡改（没有拜占庭问题）。

在《The Part-Time Parliament》中议会协议以一个基本的Synod协议为基础。Synod协议描述了在早期的宗教会议中，多个牧师在随机缺席的情况下如何通过一项法令，并能保证一致性：每个牧师用结实耐用的律簿和擦不掉的墨水来记录法令，他们会把一些重要的表决信息记在律簿的背面。律簿上的法令条目永远不会改变，但是律簿背面的备注可能会被划掉。每个牧师p必须且只需在他的律簿后面记录如下信息：

lastTried[p]：由p试图发起的最后一个表决的编号，如果没有发起过则记录-∞

prevVote[p]：由p投票的所有表决中，编号最大的表决对应的p的投票，如果没有投过票则记录-∞

nextBal**[p]**：由p发出的所有LastVote(b,v)消息中，表决编号b的最大值。
基本协议的完整过程为：
(1) 牧师p选择一个比lastTried[p]大的表决编号b，设置lastTried[p]为b，然后发送NextBallot(b)消息给某些牧师。

(2) 在从p收到一个b大于nextBal[q]的NextBallot(b)消息后，牧师q将nextBal[q]设置为b，然后发送一个LastVote(b,v)消息给p，其中v等于prevVote[q]。（b<= nextBal[q]的NextBallot(b)消息将被忽略）

(3) 在从某个多数集合Q中的每个成员都收到一个LastVote(b,v)消息后，牧师p发起一个编号为b，法定人数集为Q，法令为d的新表决，其中d的选择遵守B3条件。然后他发送一个BeginBallot(b,d)消息给Q中的每一个牧师

(4) 在收到一个b= nextBal[q]的BeginBallot(b,d)消息后，牧师q在编号为b的表决中投出他的一票，设置prevVote[p]为这一票，然后发送Voted(b,q)消息给p（b!= nextBal[q]的BeginBallot(b,d)消息将被忽略）

(5) 在p收到Q中每一个q的Voted(b,q)消息后（这里Q是表决b的法定人数集合，b= lastTried[p]），他将d（这轮表决的法令）记录到他的律簿上，然后发送一条Success(d)消息给每个q

(6) 一个牧师在接收到Success(d)消息后，将法令d写到他的律簿上。
[caption id=”attachment_403” align=”alignleft” width=”624” caption=”paxos-basic-protocol”]paxos-basic-protocol[/caption]

上图是在《The Part-Time Parliament》中描述的基本协议的交互过程。在基本协议的基础上完善各种问题得到了最终的议会协议。

为了让人更容易理解《The Part-Time Parliament》中描述的Paxos算法，Lamport在2001发表了《Paxos Made Simple》，以更平直的口头语言描述了Paxos，而没有包含正式的证明和数学术语。《Paxos Made Simple》中，将算法的参与者更细致的划分成了几个角色：Proposer**、Acceptor**、Learner。另外还有Leader和Client。将算法的过程明确的划分为4个阶段：

Phase 1a: Prepare

Proposer (当时的leader) 选择一个编号N，发送Prepare消息给所有Acceptor的某个子集（quorum）
Phase 1b: Promise
如果N比之前接受到的Prepare编号都大, 那么Acceptor承诺不再接受小于N的Prepare，并且发送本轮算法中他上一次接受的值给Proposer (当时的leader**，以便leader作出符合算法的决定)。如果N比之前接受到的Prepare的编号小，那么拒绝发送消息。为什么要有这个承诺? 其实Lamport在《The Part-Time Parliament》中给出了很关键的说明和论证。因为消息的延时性，这个承诺可以保证在Leader选择一个value时，一致性成立的前提条件能够得到保证。但是在《Paxos Made Simple》中说的不是很透彻，因此这里会显得比较突兀。 Phase 2a: Accept!
如果Proposer接收到了多数（quorum）Acceptor的响应, 他就根据这些响应的返回值，选择一个恰当的值，将选出的值通过Accept!消息发送给Acceptor集合。怎样选择一个值是《Paxos Made Simple》重点说明的。选择值的规则保证了算法的一致性。 Phase 2b: Accepted
如果Acceptor收到了他承诺过的proposal对应的Accept!消息，那么接受其值，并发送Accepted消息给Proposer和每个Learner**
在随后的几年，Lamport陆续发表了《Consensus on Transaction Commit》、《Cheap Paxos》、《Fast Paxos》等一系列论文，阐述了Paxos算法的各种演化、优化、简化和变种。这些算法和变种，在维基百科中概括的很好：http://en.wikipedia.org/wiki/Paxos_algorithm

[caption id=”attachment_404” align=”alignnone” width=”300” caption=”Leslie Lamport(莱斯利·兰伯特)”]Leslie Lamport(莱斯利·兰伯特)[/caption]

参考资料：

《The Byzantine Generals Problem 》http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

《The Part-Time Parliament》 http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf

《Paxos Made Simple》 http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf