爱讲故事的计算机科学家，和他的分布式系统

2022 年 4 月 17 日
本文字数：3132 字
阅读完需：约 10 分钟

《人类简史》提到，人类之所以开启认知革命，站到生物链的最顶端，主要是因为智人会讲虚构的故事。智人不但会讲故事，智人还相信虚构的故事。

善于讲故事的人，总能轻而易举地获得更广泛的关注和影响力，量子力学领域就有一只著名的“薛定谔的猫”。计算机领域也是如此，计算机大师 Dijkstra 就讲过一个“哲学家就餐问题”，通过哲学家、意大利面和叉子把这个故事描绘得妙趣横生，这个经典的故事被写进各种计算机教材，广泛传播。

“哲学家就餐问题”经典到，即使你忘了细节，但只要想到这个故事，也能联想到死锁问题。

上世纪 70 年代，另外一位计算机大师 Leslie Lamport 就认为，死锁问题因为这个故事得到了超出预期的关注，受此启发，他决定也编一个故事。

当时 Lamport 正受雇于斯坦福研究院，受 NASA 所托，正在钻研飞机和航天器的高可用和容错问题，这是一个性命攸关的任务，需要让多个不可靠的处理器对某个指令达成共识，作出一致的决定。

Lamport 认为这是一个非常重要的问题，需要一个引人入胜的故事。于是他编了一个“拜占庭将军问题”，具体指，有多个拜占庭将军各率领一支军队，想要占领一座防守坚固的城市，将军们只能通过信使进行交流，来做出进攻或者撤离的判断。倘若一部分军队进攻而另一部分军队撤离行动将会失败，所以各位将军必须通过投票来达成一致的策略，即所有军队一起进攻或者所有军队一起撤离。

麻烦的事情在于，信使可能会丢失、篡改或伪造消息，将军中也可能有间谍，扰乱整个行动。

这个故事中，将军便是计算机，信使就是通信系统，间谍指被非法控制的计算机。

当然，只有故事也是不行的，Lamport 在讲故事的同时，也提出了解决方案：

如果存在 m 个间谍，那么至少需要 3m+1 个将军，才能最终达成一致的行动计划。

“拜占庭将军问题”的论文发表后取得很好的效果。30 年后，由拜占庭将军问题发展出区块链，可见 Lamport 研究内容的超前性。而这种“标题党”讲故事带来的讨论让 Lamport 感到很过瘾。

到了上世纪 80 年代，计算机行业飞速发展，人们发现企业使用的局域网，出现拜占庭将军问题的可能性不大，更有可能的是机器故障、消息丢失和消息重传等，这种情况被称为非拜占庭容错。

Lamport 对非拜占庭容错的分布式系统也做了深入的研究，他发现了一个绝妙且重要的算法。由于从“拜占庭将军问题”中尝到甜头，他决定故技重施。

这次，Lamport 把目光转向古希腊，那里有一个岛屿名叫 Paxos，这个岛屿非常民主，岛上的立法者需要按照民主议会投票的方式制定法律。以此为类比，展开 Paxos 算法。关于 Paxos 算法的细节可参见我的《理解Paxos（含伪代码）》

Lamport 还皮了一下，用该领域的计算机科学家的名字来命名立法者，并将他们的名字音译为奇怪的伪希腊方言。

为了进一步提升影响，Lamport 模仿了电影《夺宝奇兵》中的考古学家印第安那·琼斯的形象，戴着牛仔帽拿着酒壶开了几场讲座。

不幸的是，这次幽默的尝试失败了。参加讲座的人只记得印第安那·琼斯 cosplay，不记得算法。阅读论文的人也被故事分散了注意力，没有人理解和记住其中的算法。

不甘心的 Lamport 又将论文发给了 Nancy Lynch 等人，几个月后，Lamport 发邮件问他们：“你能否实现一个分布式数据库，能够容忍任意数量的进程(甚至是所有进程)故障而不破坏一致性，并且在一半以上的进程再次正常工作后，使系统恢复正常？”

令 Lamport 再次失望的是，他们中没有人注意到这个问题与 Paxos 算法之间的联系。

Nancy Lynch 也是分布式系统领域的大牛，就是“FLP 不可能”中的 L

1990 年，Lamport 向 TOCS（美国计算机协会计算机系统会报）提交了这篇论文，但是依然遭遇滑铁卢。三个审稿者都认为该论文尽管不重要但还有些意思，只是应该把其中所有与 Paxos 相关的背景故事都删掉。

Lamport 对这些缺乏幽默感的审稿者感到恼火，他觉得这个领域的工作者都非常无趣，他不打算对论文做任何修改，所以该论文的发表只能暂时搁置。

多年后，几个在 SRC 工作的人正在为他们构建的分布式系统寻找一个合适的算法，他们得知 Lamport 发现了一个未发表的共识算法，于是向 Lamport 寻求建议，Lamport 就将论文发给他们。

这次 Lamport 终于遇到了知音，根据两位研究员 Chandu Thekkath 和 Ed Lee 的回忆，他们当时正在寻找某种提交算法，来确保分布式系统中的全局操作在部分节点失效的情况下依然能够正确完成。他们找到了三阶段提交算法，可是觉得难以理解和实现，便放弃尝试。而当他们读完 Lamport 的论文之后，非常喜欢 Lamport 的幽默感，并且赞叹 Paxos 算法具备了他们所需的一切。Lamport 帮助他们首次实现了 Paxos 算法。一年后，他们需要为 Frangipani 文件系统开发一个分布式锁服务时，他们再一次实现了 Paxos 算法。

有了这次成功的经验以后，Lamport 想也许论文重新发表的时间到了。

与此同时，Butler Lampson 也是理解这个算法的人之一。他读完后立即明白了这篇论文的重要性，并在他的讲座和论文《How to Build a Highly Available System Using Consensus》(中文“如何使用共识构建高可用系统”) 中提到这篇论文。之后，De Prisco, Lynch 和 Lampson 一起发表了他们对 Paxos 算法的证明。

此时，Lamport 更加坚定要重新发表论文。

于是， Lamport 找到 TOCS 的编辑 Ken Birman 帮忙修改论文，编辑提议出个修订版，并增加一些 TLA 规范。但 Lamport 重读这篇论文后确信，算法的描述和证明已经足够精确和严谨。为了继续保持幽默感和节省工作量，Lamport 建议不要搞什么修订版，而是直接以最新发现的形式重新出版论文。

新论文的开头有一段 Keith Marzullo 的注释，非常有趣：

“最近在 TOCS 编辑部的一个文件柜后面发现了这份材料。尽管年代久远，但主编仍然认为值得出版。因为作者目前正在希腊群岛做实地考察，无法联系，所以由我来出版。”

“作者似乎是一位考古学家，对计算机科学只有一点点兴趣。这是不幸的；尽管大多数计算机科学家对他描述的晦涩的古 Paxon 文明没什么兴趣，但论文提到的系统是一个如何在异步环境中实现分布式计算系统的优秀模型。”

最终这篇论文终于在 1998 年正式发表，距离首次提交已经过去 8 年。

可是很多人还是抱怨这篇论文根本看不懂啊，人们只记住了那个奇怪的故事，困扰于其中的伪希腊方言，没有人理解什么是 Paxos 算法。Lamport 走到哪都要被人抱怨一通。

在 2001 年的 PODC（分布式计算原理）会议上，Lamport 终于厌倦了大家抱怨 Paxos 算法多么难以理解。因此，他把几个人拉到会议一角，不用论文，口头向他们解释了 Paxos 算法。回家后他把这一解释记录了下来，经修改后于 2001 年重新发表了一篇关于 Paxos 的简短的论文——《Paxos Made Simple》。

Lamport 表示论文只有 13 页，且没有比 n1 > n2 更复杂的公式。有趣的是，Lamport 就像是在故意嘲讽人们的抱怨一样，在这篇论文的摘要部分只写了一句话：“Paxos 算法，如果以简单的英文呈现，是非常简单的(The Paxos algorithm, when presented in plain English, is very simple.)。”

然而，可能是表述顺序的原因，这篇论文留给读者的第一印象依旧较为晦涩难懂，仍然未引起重视。

直到 21 世纪，随着大规模分布式系统逐渐成为大企业的刚需，分布式系统变得越来越重要。2006 年 Google 发布了 Chubby 论文，其中提到的 Paxos 部分引起不少人的关注，随后这一领域的研究开始爆发，不仅产生了越来越多的变体（如 Multi-Paxos、EPaxos 和 Raft 等）；也产生了越来越多的著名分布式系统（如：Zookeeper、etcd 等）。

如今，共识算法已经作为分布式基础设施最重要的部分，Paxos 也走上神坛，成为共识算法的事实标准。