（审稿中）

单个人完不成的任务，组成一个团队去完成；单台机器完不成的任务，组成一个分布系统去完成。

企业级业务系统中，分布系统技术的使用已是非常普遍，部分原因是希望用更多机器达到更高的性能，部分原因是需要冗余来提高整体可用性。

不可避免的，多台机器构成的分布系统相比单台机器增加了成倍的复杂性。核心问题在于，如何在不可靠的机器上建立可靠的系统，如何通过异步的通讯方式设计同步的运行模式。

Paxos算法[1]为解决这一问题而提出。这是个带点传奇色彩的算法，它的作者是Leslie Lamport。Lamport是在计算机领域非常多才多艺的一个科学家。他在1978年发表的关于分布系统时序的一篇论文是被引用最多的文章之一，他在1982年描述的拜占庭将军问题成为阐述分布系统协商机制的经典案例，他在1985年推出的LaTeX语言成为学术界最流行的排版语言，他在1990年设计的行为时序逻辑语言（TLA）为并发事件推演提供了数学工具。

Lamport在1990年为解决分布系统协商问题提出了Paxos算法[2]，论文投给顶级学术期刊TOCS（ACM Transaction on Computer Systems）。Lamport那时有点突发奇想，他觉得之前拜占庭将军问题的描述方式很有趣，于是也想通过一个寓言故事来讲述他的Paxos算法。那是一千年前的古希腊，爱琴海上有个叫作Paxos的小岛，岛上民主议会制度很发达，但是人们忙着经商，参加议会的工作只能分时参加。这篇名为Part-Time Parliament（非全时议会）的论文通篇都是讲述古希腊议会制度，只在最后半页纸说了两句这个算法可以用在分布系统上解决协商问题。不想可知，这篇文章被拒了。

Lamport由于文章被拒很恼火，对于编辑要求把诸如希腊小岛的内容全部删掉的修改要求置之不理。尽管Paxos算法未正式发表，但其名声在学术界不胫而走。DEC系统研究中心采用Paxos算法构建分布系统。一些学术前沿的研究引用Paxos算法作为参考文献。于是8年后，TOCS编辑重新审视这篇有点离经叛道的论文，在再度要求Lamport修改内容未果后，以原文发表。1998年发表的这篇论文有个很有趣的编者按，编辑称原作者兴趣从计算机科学转向了希腊小岛考古，并为计算机领域流失了这么一个人才表示遗憾。

后来Lamport自己也觉得非全时议会这篇文章似乎确实有不少人读不大懂，于是在2001年又另写了一篇较为通俗的Paxos简化版[3]。简化版里面不但没有考古故事，连公式都没有，直接通过计算机实例来讲解如何实现Paxos算法。这篇简化版Paxos很受欢迎，大学里分布系统课程教学一般直接用这一简化版来讲解Paxos算法。

Paxos被誉为分布系统协商算法中最有效的一个。DEC公司被解体收购后Lamport转投微软研究院养老。微软公司为简化的Paxos申请了专利，微软在Bing应用中使用了Paxos算法。Google公司使用Paxos算法来实现分布锁Chubby，并作为其BigTable架构的基础，在Google的各项服务中广泛应用。其它使用Paxos算法的公司还有WANDisco、Keyspace等。[4]

回过头来我们再来看看Paxos算法本身。

算法要解决的问题是分布系统协商问题。以议会为例，为通过议案，需要超过半数议员投票赞同。这些议员忙于商业事务，可能投票的时候不在会场，要等到再度来到会场时才能得知之前的议案内容。在一个议案尚未通过前，可能会出现另一个与之矛盾的提议，后一提议的提出会导致前一提议作废，有些议员所知的议案内容可能已过期。议员即便已经对某一议案投票赞同，但由于人数不足未能及时通过，可能在议案内容发生变动后还要再度投票。

算法设定了一些假设前提，以使得场景更接近真实系统，协商更易达成。首先所有议员都相信发起议案者的人品，只要是议案，议员都会倾向于赞同。其次对于同一议案的两次提议，新提议无条件地覆盖旧提议，旧提议作废。最后一旦该议案得到超过半数议员投票通过，对该议案后续再度提出的提议均无效。

为方便实现，在Paxos简化版中引入几个角色。提议者（proposer）发起提议，允许有多个提议者。为保证议案顺利表决，通常可选出一个唯一提议者（leader）。投票者（acceptor）对提议进行投票。其他还有向提议者发起请求的客户（client），从议员处获取议案结果的观察者（learner）。每个角色可以有多个，一个人可以兼任多个角色。设定足够灵活，场景足够抽象，应用算法者完全可以根据实际系统需求进行定制，这也是Paxos算法具备生命力的原因之一。

算法的大致流程如下：

1a）提议者发起议案的第n次提议，并将该预备（prepare）提议发给其它投票者；

1b）投票者发现序号n过期则不予理会；投票者发现序号n为最新的预备提议，则投票给提议者赞同该预备提议，并告知提议者之前收到的最后一次序号；

2a）提议者收到该提议的赞同投票超过半数，即发起正式（accept）提议发给所有投票者；正式提议中会附上从投票者中收集到的最后一次提议内容v，如果投票者之前都没有收到过该议案的提议，那么提议者可自行设置议案内容v；

2b）投票者在从未收到大于n次的预备提议情况下，会接受第n次正式提议。

分布系统协商问题的难点在于组成分布系统的各组件不稳定，各机器间的通讯不可靠。议案投票超过半数，但是提议者人间消失了，这个议案怎么继续？议案内容修改了，某个投票者的赞同投票因为通讯问题滞后到达了，算是同意还是弃权？Paxos算法给与议员多次提议的自由，以避免议案无法推进，同时又通过时序约束和超过半数投票的限制，保证不会对同一议案产生两个矛盾的结果。这也就是我们想要的，在分布系统中，无论发生主机故障、网络混乱、磁盘阻塞以及各种想象不到的事件，只要还有超过半数的机器在工作，整体系统就能够正常运转下去，而且数据保证正确。

最后让我们引Leslie Lamport对于分布系统的一个另类定义作为结尾。A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable. （你电脑无法使用，结果发现原因是不知道在哪个角落的某台机器发生了故障，这就是分布系统）。这个定义告诉我们要把分布系统做好，还有很长的路要走。

致谢：

本文是上证联合研究计划证券IT前沿技术专题《低延迟交易架构技术研究》课题的中间成果。作为课题承接方，清华大学的张勇老师和他带的硕士研究生黄晓东，搜集了大量有关分布算法的文献，是本文成文的基础，在此致谢。

参考文献

[1] 维基百科，Paxos算法：http://zh.wikipedia.org/wiki/Paxos算法

[2] L. Lamport. The part-time parliament. ACM Transactions on Computer Systems 16(2):133-169, 1998

[3] L. Lamport. Paxos made simple. SIGACT News 32(4):18-25, 2001

[4] 维基百科，Paxos Algorithm：http://en.wikipedia.org/wiki/Paxos_algorithm