《云计算技术系列丛书 云原生分布式存储基石： etcd深入解析》—1.3Paxos协议

1.3　Paxos协议

       Leslie Lamport对类似拜占庭将军这样的问题进行了深入研究，并发表了几篇论文。总结起来就是回答如下的三个问题。

       1）类似拜占庭将军这样的分布式一致性问题是否有解？

       2）如果有解的话需要满足什么样的条件？

       3）基于特定的前提条件，提出一种解法。

       Leslie Lamport在论文“拜占庭将军问题”中已经给出了前两个问题的回答，而第三个问题在他的论文“The Part-Time Parliament”中提出了一种基于消息传递的一致性算法。有意思的是，Lamport在论文中使用了古希腊的一个城邦Paxos作为例子，描述了Paxos通过决议的流程，并以此命名算法，也就是后来人们耳熟能详的Paxos算法。

       Paxos算法从提出到为大众所熟知，中间还有一段小插曲。1990年，Lamport向ACM Transactions on Computer Systems提交了他那篇关于Paxos算法的论文。主编回信建议他用数学而不是神话描述他的算法，否则他们不会考虑接受这篇论文。Lamport觉得那些人太迂腐，拒绝做任何修改，转而将论文贴在了自己的个人博客上。

       起初Paxos算法由于难以理解并没有引起多少人的重视，直到2006年Google的三大论文初现“云”端，其中Chubby Lock服务使用了Paxos作为Chubby Cell的一致性算法，这件事使得Paxos算法的人气从此一路飙升，几乎垄断了一致性算法领域。在Raft算法诞生之前，Paxos几乎成了一致性协议的代名词。Chubby作者关于Paxos协议有一句经典的评价：

     “There is only one consensus protocol, and that抯 Paxos - all other approaches are just broken versions of Paxos.” （所有的一致性协议都是Paxos协议的变种。）

       由此可见，Paxos协议在一致性协议领域具有重要地位。

       尽管Lamport本人觉得Paxos很简单，但事实上对于大多数人来说，Paxos还是太难理解了。引用NSDI社区上的一句话就是：

     “The dirty little secret of the NSDI community is that at most five people really, truly understand every part of Paxos.”（全世界真正理解Paxos算法的人只有5个！）

       Paxos不仅难，而且难以实现，引用Chubby工程师的一段话就是：

       There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.

       上面这段话的核心含义是Paxos算法与现实世界之间有条鸿沟，而且Paxos论文本身并未提供工程实现方法，算法实现者不得不对Paxos协议做一些拓展，因此最终的系统实现实际上是建立在一个Paxos的衍生算法上的，而这个衍生算法的正确性却未被证明！

       正因为Paxos协议存在这些问题，而一致性协议对大规模分布式系统又非常重要，因此，斯坦福大学的Diego Ongaro和John Ousterhout决定设计一种比Paxos更容易理解的一致性算法。Raft就是这样的一个算法，从论文题目“In Search of an Understandable Consensus Algorithm”就可以看出Raft算法把可理解性作为算法设计的主要目标之一。