图灵奖得主 Leslie Lamport：清晰思考、Paxos 与 Raft

图灵奖得主莱斯利·兰波特是分布式系统领域的奠基人之一，Paxos 算法、逻辑时钟、拜占庭将军问题……这些计算机科学的经典概念，皆出自他之手。然而在这场对谈中，兰波特呈现的并非一位高居庙堂的学术权威，而是一个习惯质疑、乐于较真的思考者。

访谈从面包店算法讲起，追溯他与迪杰斯特拉之间那段既有碰撞、又有敬意的交往；继而谈及 Paxos 与 Raft 的异同，以及"易于理解"与"严格正确"之间难以调和的张力。更值得玩味的是他对写作的看法——他认为，若不将思考诉诸文字，所谓"理解"不过是一种幻觉。

五十年职业生涯的沉淀，让兰波特对智识保持着罕见的清醒与谦逊。这篇访谈既是一部分布式系统思想史的侧记，也是一份关于如何独立思考、持续创造的朴素指南。

本期节目，我采访了图灵奖（Turing Award）得主莱斯利·兰波特（Leslie Lamport）。他以对分布式系统（distributed systems）领域的深远贡献及 Paxos 算法的发明而广为人知。我们一同梳理了他职业生涯中的重大成就，探寻这些成果背后的故事，以及他一路走来所获得的深刻洞见。

章节目录：

简介
面包店算法
与迪杰斯特拉（Dijkstra）的交往
他被引用最多的论文
“拜占庭将军"问题
Paxos 算法
Paxos 与 Raft 算法对比
构建 LaTeX
为何写作能提升思维能力
为何他没有走学术道路
并发的宏观理论
为何他认为自己并不聪明
对年轻时的自己的建议
结语

引言

莱斯利·兰波特： 如果你觉得自己懂某件事，却从不将其诉诸文字，那你只是以为自己懂而已。

Ryan Peterman： 这位是莱斯利·兰波特，图灵奖得主，以其在分布式系统领域的杰出贡献而享誉学界。我有幸对他进行了专访，请他讲述了那些论文背后的故事。

莱斯利·兰波特： 他们的反应让我大为震惊——勃然大怒。我当时真的以为他们会动手打我。

Ryan Peterman： 您觉得迪杰斯特拉原有方案有哪些不足之处，让您萌生了重新解决这个问题的念头？

莱斯利·兰波特： 对大多数人来说，这并不是一个显而易见的想法，但它确实让迪杰斯特拉印象深刻。

Ryan Peterman： 作为 Paxos 算法的发明者，我向他询问了对竞争性的 Raft 算法的看法。

莱斯利·兰波特： Raft 算法中曾发现并修复了一个漏洞，但我认为，大家觉得更易理解的那个版本，恰恰是带有这个漏洞的版本。

Ryan Peterman： 回顾他长达五十年的职业生涯，我也深受触动。您曾说从未认为自己聪明，这怎么可能呢？

莱斯利·兰波特： 愚蠢的人总以为自己聪明，因为他们太愚蠢了，根本意识不到自己并不聪明。

Ryan Peterman： 您曾说在某个阶段感到很失败，因为您想构建一套关于并发的宏大理论，却始终未能实现。您现在还有这种感觉吗？

以下是完整的访谈内容。

面包店算法

Ryan Peterman： 我想先从面包店算法说起。这个算法究竟解决的是什么问题？您当初又是怎么发现这个问题的？

莱斯利·兰波特： 这个问题最早由埃德斯格·迪杰斯特拉在1965年——我想应该是1965年——的一篇论文中提出，那篇论文标志着并发编程理论的真正开端。迪杰斯特拉是第一个真正将"并发”（concurrency）作为一种程序结构方式来运用的人——他把程序视为一组半独立任务的集合，各进程之间需要相互同步。

那是分时系统（time sharing）的萌芽时代，人们刚刚开始探索让多人共用同一台计算机的可能性。计算机的运算速度远超人类的操作速度，加之当时计算机造价极为昂贵，人们自然希望让它同时为多人服务。每位用户运行的是独立的程序，但有时不同进程之间需要共享某些资源——比如打印机。两个用户同时向同一台打印机发送任务，结果自然乱成一团。

迪杰斯特拉由此意识到，需要对多个进程进行同步，并提出了临界区（critical section）的概念：每个进程中都有一段特定的代码，在任意时刻最多只能有一个进程执行这段代码。对于打印机而言，这段代码就是实际执行打印操作的部分。问题的关键在于：如何让多个进程相互协调，确保在任意时刻最多只有一个进程处于其临界区之中。

1972年，我通过 ACM 通讯（Communications of the ACM，CACM）上的一篇介绍该问题解法的文章了解到了它。我向来喜欢编程和各种小巧的编程谜题，而这正是一道十分精妙的小谜题。

我看了那个解法，觉得相当复杂，心想：“这应该没那么难吧。“于是飞速写出了一个针对两个进程的简单算法，投稿给 CACM。几周后，我收到了编辑来信，指出了我程序中的一个漏洞。这件事带来了两个影响：其一，我意识到并发程序极难做到正确，必须要有严格的正确性证明；其二，这次挫折激起了我的斗志——我下定决心要彻底解决这个问题。

于是我提出了面包店算法，其灵感来自如今所说的"熟食柜台问题”：熟食店里摆着一台取号机，顾客进门各取一张号码票，服务员按号码从小到大依次叫号服务。我借用了这个思路，但由于迪杰斯特拉问题的设定中不存在中央控制，每个进程必须自行"选取"自己的号码。这便是算法的基本思想，实现起来也相当简洁。我为此写了一份正确性证明。

在撰写正确性证明的过程中，我发现了这个算法的一个极为有趣的性质。此前学界普遍认为——甚至有人在书中或论文中明确断言——不借助某种底层的互斥（mutual exclusion）机制，是无法实现这类互斥的。

当时普遍假设的互斥机制基于共享寄存器（shared registers）——即不同进程可以共同读写的内存区域。人们默认这些读写操作是原子性（atomic）的：两个进程不能同时写同一块内存，也不能在一个进程写入时另一个进程同时读取——所有操作都如同按某个确定顺序依次发生一样。

然而，面包店算法的神奇之处在于，它根本不需要这个假设。算法中每块共享内存只由单一进程写入，因此不存在两个进程相互干扰的问题。唯一可能出现的情况是：某个进程在另一个进程写入时读取，可能得到一个未知值——但算法依然能够正确运行。即便读取进程得到的是完全任意的值，算法仍然成立。

Ryan Peterman： 我看到您在相关文章中提到，您把这个证明分享给了一位叫 Anatol Holt 的同事，而这个结论是如此出人意料，以至于他起初根本不相信。

莱斯利·兰波特： 是的，是的，他不相信。我在白板上为他一步步展示了这个证明，他找不出任何漏洞，但回家后仍然觉得一定哪里出了问题——当然，他最终也没找到任何问题所在。

与迪杰斯特拉的交往

Ryan Peterman： 我注意到这篇论文的题目是"迪杰斯特拉并发编程问题的新解法”。您觉得迪杰斯特拉原有方案有哪些不足，促使您想要重新解决这个问题？

莱斯利·兰波特： 他原始方案有一个令人不满意的地方：如果大量进程不断尝试进入临界区，某个单独的进程可能会被"饿死"（starvation）——永远无法获得进入临界区的机会。这个问题在后来的方案中得到了解决，我想下一个解法应该是高德纳（Donald Knuth）提出的。衡量算法优劣的标准是一个进程最长需要等待多久，而我相信面包店算法是第一个真正实现"先来先服务"（first come first served）的方案：如果一个进程在另一个进程开始尝试进入临界区之前就已选定号码，那么前者必然先于后者进入临界区。我相信面包店算法是第一个具备这一性质的方案，同时我认为它比许多其他解法都要简洁。

Ryan Peterman： 在许多资料中，我看到您曾与迪杰斯特拉有过合作，1976年您甚至在荷兰与他共事了整整一个月。能跟我们聊聊那段经历吗？

莱斯利·兰波特： 迪杰斯特拉有一个习惯：每当有了某个想法，他就会把它写成简短的手稿，称为"EWD"——取自他名字的首字母缩写。他会把这些文稿寄送给相关人士。其中有一篇 EWD 是他与几位合作者——或者说门生——共同撰写的，内容是关于第一个并发垃圾回收（concurrent garbage collection）算法。

那个时代的程序内存管理方式是这样的：系统中有一个公共内存池，程序需要内存时便向某个服务进程申请；使用完毕后，这块内存理应归还，但创建这块内存的进程本身并不清楚是否还有其他进程在使用它。为此，系统中有一个专门的进程称为垃圾回收器（garbage collector），它持续扫描内存，判断哪些内存块已不再被任何进程使用，然后将它们放回空闲列表（free list），以便负责分配内存的进程重新取用。

我仔细研读了这个算法，发现可以加以简化。在迪杰斯特拉的方案中，空闲列表由一个独立的进程管理，该进程需要处理与其他内存使用进程之间复杂的协调问题。而我意识到，空闲列表完全可以作为普通数据结构的一部分来处理，根本不需要单独设立一个进程来维护。

莱斯利·兰波特： 那个想法根本不需要任何特殊处理，在我看来这是个再简单不过、显而易见的念头。我把它寄给了他，等到下一版论文到手时，我发现他已经把我列为共同作者了。我认为他这么做非常慷慨，因为在我看来这只是个微不足道的简单想法——或者说极其显而易见的想法。后来我才意识到，其实是很久之后才意识到，这个想法对大多数人而言并非那么不言自明，而且它确实给迪杰斯特拉留下了深刻的印象。那是我和迪杰斯特拉之间唯一一次真正意义上的合作。多年后，他曾说我拥有一种卓越的抽象能力。直到近年——大概是获得图灵奖之后——我才真正想明白，我之所以取得成功、最终斩获图灵奖，并不是因为我有多聪明，而是因为我拥有这种抽象的天赋。而迪杰斯特拉足够睿智，早早便看出了这一点。

为此，我受邀前往荷兰待了整整一个月——不过不是直接与迪杰斯特拉共事，而是与他的一位同事 Carl Holton 合作。那次访问中正式发表的成果只有一篇。Carl 和我每周都会与迪杰斯特拉碰面一次，在那些讨论中不知怎地冒出了一个想法，后来发展成了面包店算法的一个变体，由我整理成文并发表。这便是我在荷兰那一个月唯一有形的收获。

Ryan Peterman： 嗯，我看到你写过这段经历。你们每周有一个下午聚在迪杰斯特拉家里，一边工作、一边交谈，还一边喝啤酒，你好像也记不太清楚那篇论文究竟是谁贡献了什么。

莱斯利·兰波特： 我想我应该不至于喝得那么醉，毕竟我是开车去、又开车回来的。再说，我喝的荷兰啤酒酒精度并不高。

引用最广的论文：分布式系统的时间与事件排序

Ryan Peterman： 我想聊聊你被引用次数最多的那篇论文——题为《分布式系统中的时间、时钟与事件排序》（Time, Clocks, and the Ordering of Events in a Distributed System）。这篇论文背后有怎样的故事？当时你试图解决的是什么问题？

莱斯利·兰波特： 这篇论文的起源很简单。有人寄给我一篇关于构建分布式数据库的论文，讲的是如何在多处存储多份相同数据、并保持同步的问题。我读完后意识到，他们的方案存在一个根本缺陷：它虽然能保证所有操作按某种顺序依次执行，但这个顺序可能与操作实际发生的顺序截然不同。

“发生在先"究竟意味着什么，对大多数人来说并不是那么直觉显然，但我恰好学过狭义相对论，尤其是其中的时空观——也就是将空间与时间合并为一个四维整体来看待的视角。爱因斯坦在1905年发表了他的论文；大约在1909年，一位我一时想不起名字的学者提出了这个四维时空的视角。这一视角给出了"一个事件先于另一个事件发生"的精确定义：若一个信号从第一个事件处发出，并在第二个事件发生之前被第二个事件的行为主体所接收，则称第一个事件发生在先——前提是该信号的传播速度不超过光速，因为任何事物都无法超光速传播。

我意识到，这与分布式系统中的情形存在一个完美的类比。分布式系统中"发生在先"的定义，与相对论中的定义在本质上完全相同——只不过判断标准不再是"能否通过光速传播影响另一事件”，而是"第一个事件能否通过系统中实际发送的消息来影响另一事件"。真正令人眼前一亮的，正是这个在分布式系统中对"发生在先"的全新定义。这也是我认为第一篇真正具有科学意义的分布式系统研究成果。

不过，我可能犯了一个曾被人警告过的错误——在一篇论文里塞进了两个想法。另一个想法是：存在这样一种算法，它能对事件生成一种全序排列，并满足"若事件A发生在事件B之前，则A在排列中位于B之前"这一条件。我进一步意识到，有了这样的排序算法，便可以用它为任何分布式系统提供所需的同步机制——因为任何分布式系统都可以用状态机（state machine）来描述。

状态机，按照我当时的定义，是一种拥有内部状态的系统：进程按顺序执行一系列命令，每条命令的作用仅仅是改变状态并产生一个输出值。因此，描述一个状态机，只需说明命令如何改变状态、如何产生输出——即新状态和输出值分别是原状态的什么函数。这个思路对我来说极为显然，但它其实才是那篇论文中真正具有实践价值的核心思想：它证明了用状态机的视角来构建分布式系统、用状态机来理解并发系统，是一种切实可行的方法。

然而，这部分内容被完全忽视了。事实上，有两次我跟人谈起那篇论文，对方都说里面根本没有提到状态机。我不得不回去重读论文，确认自己没有记错——论文里确实写了状态机。

这个思路的重要性还体现在另一个维度。如果你想理解一个并发程序——面包店算法是个例外——并发程序通常是在原子性（atomic）动作的假设下编写的，即假设程序的执行表现得像一系列离散事件的序列。那么，该如何理解一个程序为什么能给出正确的答案呢？答案是：给定正确的输入，程序产生正确的输出。但当程序执行到中途时，最初的输入早已成为历史；决定程序下一步行为的，只有它当前的状态。

理解一个程序——哪怕是最简单的那种，接受输入、产生输出——的方式，是追问：在执行过程的每个节点，状态具有什么性质，才能保证最终输出的正确性？这个性质——在数学上是一个关于状态的布尔值函数——被称为不变式（invariant）。理解不变式，便是理解系统的关键所在。我意识到，对于并发系统和并发程序，同样的道理成立。

人们往往倾向于编写行为证明，即对执行序列进行推理。但问题在于，可能的执行序列数量随序列长度呈指数级增长，推理的复杂度因此急剧膨胀，非常容易遗漏情况。相比之下，不变式证明的复杂度则要低得多：可能的执行路径数量随进程数量呈指数级增长，而不变式证明的复杂度仅与进程数量的平方成正比——这就是不变式证明更为优越的根本原因。当然，分布式系统理论界长期以来仍有许多研究者试图基于偏序关系（partial orderings）建立形式化方法，发表了大量论文，但在实践中，那并非解决问题的正途。也有例外——像面包店算法那样的情形，用偏序思维来分析确实非常有效；但那毕竟是少数。真正可靠、普遍适用的方法，是使用不变式。

Ryan Peterman： 我想聊聊下一篇论文，也就是拜占庭将军问题（Byzantine Generals Problem）。这是计算机科学专业学生都会学到的经典课题，名字本身就极具画面感，我很想了解这个问题背后的故事。

莱斯利·兰波特： 写完时间时钟那篇论文之后，我已经给出了构建分布式系统的方法，但那是在假设没有故障发生的前提下。然而很显然，分布式系统的一大意义在于——你拥有多台计算机，即便其中一台出现故障，系统也能继续运行。这正是我加入 SRRI 之前，SRRI 正在攻克的问题；加入之后，我也开始着手研究。我想到的切入点是：一个故障进程究竟能做什么？于是我假设了最坏的情况——一个故障进程可以做任何事。

拜占庭将军问题的由来

莱斯利·兰波特： 基于这一假设，我设计了一个能够实现状态机的算法，而这个算法用到了数字签名（digital signatures）。其核心思想在于：即使一个故障进程可以为所欲为，它也无法伪造另一个进程的签名——这意味着消息的来源是可信的，转发的消息也能被验证是否与原始发送的一致。

到了 SRRI 之后，我发现那里的人们正在攻克同样的问题，但有两点不同。首先，我做这项工作是在 1975 年，那时很少有人知道数字签名。迪菲-赫尔曼论文（Diffie-Hellman paper）大约也是在那个时期发表的，而我之所以了解数字签名，是因为惠特·迪菲（Whit Diffie）——该论文的作者之一——是我的朋友。有一次我们在一家咖啡馆，他向我描述了他们正在研究却尚未解决的数字签名问题。我当时说：“这看起来不难嘛。“于是我坐下来，真的就在一张餐巾纸上写出了第一个数字签名算法。那个算法当时并不实用，因为大约需要 128 位才能对 1 位内容签名——尽管实际上没那么糟，因为你可以对文档的哈希值（hash）签名，而哈希值是无法被伪造或逆推的。这就是为什么数字签名成为了我工具箱的一部分。

SRRI 的人没有掌握数字签名，但他们提出了一种更简洁的抽象方式：与其让所有进程就一系列命令的顺序达成一致，不如先为单条命令设计一个共识算法，再多次执行该算法。这种描述方式比我原来的方法更为优雅。于是，第一篇发表的论文同时包含了两种算法。由于他们没有数字签名，就采用了另一种方案——要容忍一个故障进程，需要四个进程；而使用数字签名，只需三个进程。我也是那篇论文的作者之一。

不使用数字签名的算法更为复杂——对于一般情况，要容忍 n 个故障，需要 4n 个进程；而使用数字签名只需 3n 个进程。针对单个故障的情形还不算难，但针对多个故障的算法，那是 Marshall Pease 的杰作，堪称天才之作，几乎令人难以理解。后来在一篇后续论文中，我找到了一种更简洁的归纳证明：若对 3(n-1) 个进程成立，则对 3n 个进程也成立。但原始论文中的证明令人叹为观止——若非他，也不知还有谁能独立发现。

我们发表了那篇论文，我也逐渐认识到拜占庭故障（Byzantine fault）这一概念的重要价值。所谓拜占庭故障，即一个进程可以做任意的事。我之所以做出这一假设，是因为不知道还能假设什么；而 SRRI 的人关注这个问题，则是因为他们承接了一份合同，要为飞机飞行构建多机计算机系统，因此必须考虑进程出现恶意行为的可能性——他们确实无法预设故障进程会做什么。

每当设计一个算法，比如试图用三个进程容忍一个故障，你总觉得"这应该可行，实际中不可能出问题”——但随后总能找到某种看似合理的故障序列，让算法在故障进程面前失效。所以至少需要四个进程。出于某种直觉，我一直觉得数字签名在这个算法中几乎是一种隐喻——既然我们担心的是随机故障而非恶意攻击，理论上应该存在某种方案，能以足够低的失败概率来模拟数字签名的效果。但我从未深入研究这个想法，也没有其他人跟进。那个算法就此基本被束之高阁，因为在那个年代，数字签名的计算代价极为昂贵。我不清楚现在情况如何，毕竟数字签名归根到底就是计算，而计算如今已非常廉价。我记得有一次碰巧与波音的一位工程师通信，便问他们是否了解这些成果。他说知道，而且正是他本人在波音内部读了那篇论文，他的第一反应是：“那我们需要四台计算机。”

无论如何，我意识到这是一个重要的成果，值得广为人知。而我从迪杰斯特拉那里学到了一件事——他写过一篇"哲学家就餐问题”（dining philosophers problem）的论文，引发了广泛关注。就餐问题本身我就不多介绍了，我个人认为那个核心问题其实并不特别有趣，但它有一个妙趣横生的故事：一群哲学家围桌而坐，面前是一种需要两把叉子才能进食的特殊意面，而相邻两位哲学家之间只共用一把叉子。正是因为这个生动的故事，这道问题才广为流传。于是我意识到，我们的工作也需要一个好故事。

我构思出了"拜占庭将军"的场景：以单一故障为例，四位将军必须就是否发动进攻达成一致。如果全部出击，定能取胜；即便只有三人出击，也能获胜；但若只有两人出击，则必败无疑。其中可能有一位将军是叛徒。那么，他们如何在通信中共同作出一致决策——究竟是进攻还是撤退？这就是拜占庭将军问题（Byzantine Generals Problem）的由来。

主持人： 我看到您关于这个问题的笔记中提到，似乎还有一个前身版本，叫做"中国将军问题"或类似的名称？

莱斯利·兰波特： 对，那是另一个问题。吉姆·格雷（Jim Gray）提出了一个不可能性结论，那个问题被称为"中国将军问题"——具体内容我就不展开了。正是那个名字给了我"将军"这一意象。其实我最初想到的是"阿尔巴尼亚将军"，因为那个年代，阿尔巴尼亚对外界来说几乎是个黑洞——那是一个共产主义政权，隶属苏联阵营，甚至比苏联本身更为封闭保守。后来，我的上司说：“毕竟世界上是有阿尔巴尼亚人的，这个名字恐怕不太合适。“随即我意识到，“拜占庭"就完美了——如今世界上已不存在拜占庭帝国或拜占庭人，这个名字再贴切不过。

主持人： 有意思的是，这并非第一次有人提出这个问题，但却是第一次有人为它赋予了一个朗朗上口的名字，并补充了更多重要成果。您当时究竟看到了这个问题的哪些价值，觉得值得投入大量精力？或者说，您如何判断一个问题是否值得深入研究？

莱斯利·兰波特： 这个问题的价值显而易见——人们将会用计算机来驾驶飞机。这正发生在 70 年代石油危机的背景之下，人们已经意识到，通过缩小飞机操纵面（control surfaces）的尺寸，可以制造出更节能的飞机……

莱斯利·兰波特： 但这样一来，飞机在气动上就变得不稳定了。飞行员无法及时完成所有必要的调整来维持飞行，但计算机可以。所以很显然，未来的飞机将由计算机驾驶——正如今天的情形一样。当时人们并没有意识到这一点，以为只需三台计算机就能容忍一个故障，却没有认识到，面对任意故障，实际上需要四台计算机。这是一个非常重要的结论，这也是我认为它需要广为人知的原因。

主持人： 纵观您整个职业生涯所解决的问题，您是如何做出选择的？在企业工作时，决策标准可能与商业价值挂钩——能否创造更多收益、削减成本之类的。但我很好奇，在您漫长的职业生涯中——无论是面包店算法，还是后来的研究——在如此开放的研究环境下，您怎样判断哪些问题值得深入钻研？

莱斯利·兰波特： 在我整个职业生涯中，我都供职于私营公司，而非学术界或政府机构。有些问题的产生带有几分偶然——有时某位工程师遇到了难题，便来找我商量。就拿 Paxos 算法来说，确实有人实际需要一个能解决那类问题的算法。

主持人： 您之前提到了 Paxos，我知道那是您最著名的成果之一。能谈谈这篇论文背后的故事，以及您当时试图解决的问题吗？

Paxos 算法

莱斯利·兰波特： 那个问题的本质，与我在拜占庭将军问题中所解决的问题是一样的——即构建一个容错（fault tolerant）的状态机。只不过到了那个时候，工业界关注的故障类型，是计算机直接停机的那种，而非执行任意错误操作的那种。Paxos 算法就是针对这类故障来构建容错系统的。我当时所在的公司是 DEC SRC——我于 1985 年加入——他们构建了最早的分布式操作系统之一。

那里的人大多来自施乐帕克（Xerox PARC），正是他们发明了个人计算机，也提出了分布式个人计算的理念，并为此发明了以太网。他们将整栋楼里所有的计算机都连接在同一个以太网络上，共享一套公共存储，并配有一套机制来维护存储的一致性。

不过，与其说是"算法”，不如说是操作系统里的一段代码，谈不上形式化的算法。我当时不相信他们所做的事情是可能实现的。我已记不清具体是什么原因让我觉得不可能，但总之我开始尝试构造一个不可能性证明：要解决这个问题，算法必须做到某件事；要做到那件事，又必须做到另一件事……就在某个节点上，我停了下来，心想：等等，这不是证明。

这……根本证不了不可能。这分明是一个能解决问题的算法。

主持人： 您说他们有代码，但没有算法——

莱斯利·兰波特： 是的。

主持人： 这话是什么意思？大多数人开始编程时，思维方式自然是从代码出发。

莱斯利·兰波特： 这是我在职业生涯早期领悟到的一件事，具体是什么时候已记不清了。在我刚起步的年代，人们把这些东西叫做"程序”，我大概也是这么叫的。然后在某个时刻，我意识到，我做的其实并不是程序——我真正感兴趣的是算法。

算法比程序更抽象。程序是用某种特定语言写成的，而算法可以用任意语言来实现，处于更高的抽象层次。我向来喜欢抽象，这正是我的强项——即便当时自己还没有意识到这一点。

于是，在我职业生涯相当大的一段时间里——大约从 2000 年左右开始——我一直致力于让构建并发系统的人，不要只是写代码，而要先有一个算法。一个系统会做很多事情，但其中必然有某个核心部分负责协调不同进程，或在分布式系统中协调不同计算机。这部分代码极难写正确，因为在代码层面思考会把很多与并发无关的细节混为一谈。正确的做法是：先设计出能实现同步逻辑的算法，再去实现那个算法。

主持人： 我看了 Paxos 这篇论文以及您的一些相关笔记，注意到一件有趣的事：从您提出这个算法，到论文《兼职议会》（Part-Time Parliament）正式发表，中间隔了整整八年。这是为什么？

莱斯利·兰波特： 最初的审稿人认为论文还不错，但也没什么特别重要的。幸运的是，巴特勒·兰普森（Butler Lampson）认识到了这个算法的重要性。他深刻领会到，用状态机来思考几乎可以实现任何系统，便开始大力推广用 Paxos 构建系统、以状态机思维进行设计这套理念。想法已经在传播，所以我也不急于发表，就让那篇论文搁在那里。后来换了一位新编辑，他看到论文的状态是"已接受但待修改”，便推动将其出版。最终论文发表时，补充了一些阶段性研究成果的参考文献，这部分工作由 Keith Marzullo 代我完成。

这篇论文的叙事框架是这样的：Paxos 是一个古老的地方，故事发生在几百年前，文中存有一份出土的古代手稿。每当有些细节我觉得显而易见、不值赘述时，论文便用古风叙事腔调写道：“帕科斯人（Paxons）在此处的做法，目前尚无从考证。” Keith 也延续了这个风格，在论文前加了一段序言，仿佛这真的是对某段古代往事的记述，并补充了若干参考文献。

主持人： 我还注意到，据说您在最初的演讲中，甚至特意打扮成了印第安纳·琼斯（Indiana Jones）风格的考古学家。那场演讲效果如何？

莱斯利·兰波特： 演讲本身我觉得还不错，但我想，当时没有人真正理解这个算法的意义。

主持人： 听起来，除了巴特勒·兰普森，没有人真正理解它。他究竟看到了什么，使他与旁人不同？

莱斯利·兰波特： 他对于构建系统有深刻的理解，图灵奖实至名归。他是施乐帕克最初那批人之一，参与构建了分布式个人计算体系。他和 Chuck Thacker，大概是那个实验室里最核心的两位人物。

主持人： 我后来看到有一篇论文，描述了一个新的算法，解决的似乎是同一个问题。

Paxos 与 Raft 算法

主持人： 聊到 Raft 论文，我想请教您是否读过这篇论文，以及您对它与 Paxos 相比有何看法。

莱斯利·兰波特： Raft 论文的作者曾将原始草稿发给我，我看过之后提出了一些意见——我忘了当时说的究竟是"等你有了算法再拿来给我"，还是"等你有了证明再拿来给我"，反正他们领会了意思，后来确实在论文里添加了证明。此后我就再也没有读过后续版本。不过，有一位我很信赖的人读了那篇论文，他告诉我，Raft 基本上就是 Paxos 的内容，填补了 Paxos 论文中一些未竟的细节，但描述方式却截然不同。

Paxos 的基本思路是：算法分为两个阶段，目标是实现一系列决策。第一阶段只需执行一次——这一阶段涉及领导者（leader）的选举。只要领导者不变，第一阶段就无需重复，反复执行的只有第二阶段；一旦领导者失效，就需要重新选举，再次执行第一阶段。然而，工程师们更习惯于反过来理解：不断重复执行第二阶段，直到领导者失效，然后再回头执行第一阶段——这其实是以相反的顺序在解释整个过程。实际上，从全新启动时，第一阶段的内容完全可以内嵌到初始状态中。我认为从这两个阶段的角度来理解 Paxos 才是正确的方式。

Raft 的作者们声称 Raft 更简单，我必须说，很多人都觉得 Paxos 难以理解，我实在不明白为什么。我曾在五分钟内向一些人解释 Paxos，他们都听懂了。Raft 的作者们甚至做过对照实验：向一个班级讲授 Paxos，向另一个班级讲授 Raft，结果学生们普遍认为 Raft 更容易理解。不过有趣的是，后来有人发现 Raft 中存在一个漏洞并予以修复——而我相信，当时学生们觉得更好理解的，恰恰是带有这个漏洞的版本。

这让我意识到，“理解"对不同人意味着不同的事情。对我来说，理解意味着能够写出证明；但对大多数人来说，理解不过是一种模糊的感觉——一种"好像懂了"的感觉。Raft 的描述方式让人更容易产生这种感觉，因为它符合程序员习惯的思维方式：先反复执行第二阶段，直到出现故障，再回头处理第一阶段。而我描述 Paxos 的方式，则有助于真正理解算法为何能够正确工作。

构建 LaTeX

主持人： 我们聊了很多您的论文。我知道您的另一项贡献——无论您当时是否意识到——是 LaTeX，构建 LaTeX 深刻影响了整个学术界。请问您当初为何想要构建 LaTeX？

莱斯利·兰波特： 那非常简单。当时我正打算开始写一本书，很显然，TeX 是当时必须使用的基本排版系统。但我觉得需要编写一套宏包，才能让 TeX 按照我的需要工作。于是我想，多花一点力气，就可以让这套宏包也能被其他人使用。在 TeX 之前，我使用的排版系统叫做 Scribe，它的核心理念是：你描述文档的逻辑结构，由 Scribe 来处理格式排版。Scribe 的排版效果不是特别理想，但这个理念我很喜欢——重要的是抽象与思想，是写作的内容，而不是排版本身。后来，我在某次场合遇到了 Addison Wesley 出版社的 Peter Gordon——他大概是负责物色书稿的编辑——他说服我写一本关于 LaTeX 的书。那个年代，我从未想过会有人真的花钱买一本关于软件的书，但既然如此，为什么不试试呢？

Peter Gordon 把我介绍给了 Addison Wesley 的一位字体排版设计师，正是这位设计师奠定了标准 LaTeX 样式的排版设计基础。整个项目基本上是我利用"业余时间"完成的，大约花了六到九个月。我想追诉时效应该早已过去了——说实话，当时我有相当一部分时间是在做这件事，而在账目上却挂在了某个与此毫不相干的项目名下。

写作如何深化思维

主持人： 说到写作，您有一句我非常喜欢的话：“如果你思考时不写作，你只是以为自己在思考。“您能谈谈这句话的含义吗？

莱斯利·兰波特： 这句话其实主要是针对构建计算机系统的人说的。你有了一个想法，觉得它可行；或者你做了某样东西，想让别人来使用。那就写一份描述文档吧。有一条古老的格言说：先写使用手册，再写程序——这是极好的建议。写 LaTeX 时我没有这样做，但在写书的过程中，我确实发现有些内容难以描述和解释，这意味着它们需要修改，我也因此对 LaTeX 做了许多改动。只是我当初并没有从一开始就先写手册。

主持人： 为什么写作有助于良好的思考？

莱斯利·兰波特： 因为人很容易自欺欺人。这正是我一贯强调编写证明的根本原因。我认识到，为并发算法编写正确性证明是必要的。

随着算法越来越复杂，证明也变得越来越难写。我有数学博士学位，知道如何写证明，最初也是按照常规方式来写。但我发现这行不通——涉及的细节实在太多，我根本无法追踪哪些已经证明、哪些尚未证明。作为计算机科学家，处理并发的思路是层次化结构。于是我设计了一种层次化的证明结构：一个证明由一系列步骤组成，每个步骤都有自己的子证明，而这个子证明要么是一段文字，要么又是一系列各有子证明的步骤——如此递归下去。通过这种方式，整个问题被分解为越来越小的部分，永远不会有"这一步从哪里来的？“这种疑问——你明确声明这一步是从哪几个前提步骤推导出来的，如果推导不成立，证明就是错的，即使定理本身可能是正确的。

我发现这套方法用于程序的正确性证明效果极佳，于是也尝试将它用于普通数学定理的证明——同样效果出色。当我开始尝试说服数学家接受这种写法时，我参加了一个小型研讨会，向大约二十位数学家介绍了这种证明方式。他们的反应让我大为震惊：他们勃然大怒，让我感觉他们随时可能动手打我。我认为这是完全非理性的反应，而当人们非理性行事时，往往是出于恐惧。我相信，数学家们害怕的是——他们担心将来不得不把证明写得让计算机程序也能够验证。

事实上，在那些演讲中，我一再清楚地表明：这不要求你比现在更加形式化，你可以写完全相同的证明内容，只是换一种组织方式——一种简单的层次化结构，并在引用某个事实时注明你在引用它，仅此而已，与形式主义毫无关系。尽管如此，演讲结束后还是有人站起来说：“我不想为了让计算机程序能验证而去写证明。“事实是，用这种方式写证明确实需要更多工作——原因在于，它会暴露出你没有说清楚的地方，揭示出那些你认为显而易见却从未写下来的步骤。

如果你相信某件事是正确的，却没有将其写下来，那你只是"以为"自己知道，而非真正知道。错误正是由此而来。这就是论文中三分之一错误的根源——因为这种写法会真正迫使你对自己诚实。

为何选择工业界而非学术界

Ryan Peterman： 纵观您的整个职业生涯，您做出了许多人们可能认为应当出自学术界的贡献，比如那些论文等等。但您所有的工作都是在工业界完成的。您为何没有走上学术道路，而是选择在工业界工作？

莱斯利·兰波特： 我最初是一名程序员，后来逐渐进入了我们现在所说的计算机科学领域。当时我甚至没有意识到，计算本身可以成为一门科学。大概直到七十年代中后期，我才意识到：是的，存在计算机科学这门学科，而我就是一名计算机科学家。但在我看来，计算机科学从来都不像是一门学术性的学科。在某个时间点，我不得不在两件事之间做出选择：继续从事计算机科学（尽管当时还不这么称呼它），或者去大学教数学。

我选择了计算机科学——原因颇为随意。大概在八十年代中期之前，我都没有觉得计算机科学是非得进大学才能学的东西。此后，我想我只是单纯地觉得，教计算机科学不会有什么乐趣。

Ryan Peterman： 我在您的文章里看到一个注脚，说您曾在某个时刻感到自己是个失败者，因为您想建立一套关于并发的宏大理论，却始终未能实现。您现在还有这种感觉吗？对于那个注脚，您怎么看？

莱斯利·兰波特： 许多从事类似工作的人——这类人本来就不多——都怀有一个信念：他们在寻找并发领域的"图灵机”（Turing machine）。图灵机是一种抽象，真正捕捉到了计算的本质；而他们寻找的，是能够同样捕捉并发计算本质的东西。但没有人成功。当然，有些人认为自己成功了。佩特里网（Petri nets）就是这样一种尝试——我没有时间详细解释，但它在七十年代曾非常流行。令我惊讶的是，至今仍有一大批人在研究佩特里网。但我现在意识到，佩特里网以及大多数人所做的工作，本质上都是基于语言的。

并发的宏大理论

我从来对语言不感兴趣，我感兴趣的是语言所表达的东西。我意识到，从某种意义上说，也许我已经发现了并发领域的"图灵机”——那就是状态机。我现在描述状态机的方式与以往略有不同：它没有命令，只有一个状态和一个"下一状态"关系，比谈论命令、值之类的概念更加简洁。对我而言，状态机就是并发领域的"图灵机”。但它并不具备图灵机所具备的那种功能，因为图灵机描述的是"什么是可能的”，而状态机可以描述任何事物，包括那些实际上不可能实现的事情。

这其实有充分的理由。举个例子，当我描述一个算法时，我会说某个变量的值可以是任意整数。你当然可以实现一个支持任意整数的程序，但若要限定为计算机整数，则会不必要地使问题复杂化。

人们有一种奇怪的想法，认为无限的东西更复杂——他们完全搞反了。无穷的引入，恰恰是为了简化事物。你最先学的是算术，用的是无穷多个整数来学习——因为如果把整数限制在一个有限集合内，算术反而会复杂得多。

数学中的那些抽象概念——人们因缺乏适当的数学训练而觉得难以理解——恰恰是在简化事物。用数学来描述状态机，才是最有力的方式。然而，计算机从业者、计算机科学家和程序员都对语言有一种执念，他们发明了各种各样的语言。这些语言都是可描述的——事实上，若要赋予它们语义，就必须借助状态机来实现。他们就是认为，语言能够改善你的思维方式。

但并非如此。使用计算机语言而不用数学来写代码，当然有其原因——主要涉及效率。但就理解而言，没有什么能胜过数学。试图用看起来像编程语言的东西来处理并发问题，本质上就是走错了路。

为何认为自己并不聪明

Ryan Peterman： 翻阅您的文章和各种故事，我注意到一些细节。您曾说自己从不认为自己聪明，但同时您也注意到，其他孩子在理解某些东西时非常费力；您解决了某个别人觉得困难的问题，但您并不认为自己的贡献有什么了不起。这让我颇感困惑，因为您获得了图灵奖，做出了那么多令人惊叹的成就。这怎么可能呢——您说自己只不过是"发现"了一些东西、并不聪明，却又取得了如此丰厚的成就？

莱斯利·兰波特： 心理学家谈到一种普遍现象：当一个人擅长某件事时，他往往意识不到自己有多擅长，因为对他来说那是简单的。反过来也有对应的情形：不擅长某件事的人，往往会高估自己，正因为他们不擅长，所以看不到自己的不足。

更简洁地说：愚蠢的人认为自己聪明，因为他们太蠢了，意识不到自己有多蠢。我所拥有的天赋，并非某种意义上的原始智力。

我的天赋是抽象能力。直到最近——大约是过去十年左右——我才意识到，在这方面我比大多数其他人强出多少。

Ryan Peterman： 您已经经历了如此之多。回望整个职业生涯，如果可以回到刚刚大学毕业的自己，凭借您现在的认知，您会给自己什么建议？

给年轻时的自己的建议

莱斯利·兰波特： 我很早就学到一件事：不应该把时间浪费在回答那些不必回答的问题上。我不会去想"我本应该怎么做”，因为那是一个我不必回答的问题。

结语

Ryan Peterman： 感谢您收听本期播客。

术语表

英文	中文
Addison Wesley	Addison Wesley（计算机科学书籍出版社，保留原名）
Anatol Holt	Anatol Holt（保留原名）
atomic	原子性
Bakery Algorithm	面包店算法
Butler Lampson	巴特勒·兰普森（图灵奖得主，施乐帕克核心人物）
Byzantine fault	拜占庭故障
Byzantine Generals Problem	拜占庭将军问题
CACM	ACM 通讯（CACM）
Carl Holton	Carl Holton（迪杰斯特拉在荷兰的同事，保留原名）
Chinese generals problem	中国将军问题
Chuck Thacker	Chuck Thacker（保留原名，施乐帕克核心人物）
concurrent garbage collection	并发垃圾回收
control surfaces	操纵面
critical section	临界区
DEC SRC	DEC SRC（数字设备公司系统研究中心，Digital Equipment Corporation Systems Research Center）
Diffie-Hellman paper	迪菲-赫尔曼论文
digital signatures	数字签名
Dijkstra (Edsger W. Dijkstra)	迪杰斯特拉
dining philosophers problem	哲学家就餐问题
distributed systems	分布式系统
Donald Knuth (Don Kuth)	高德纳
EWD	EWD（迪杰斯特拉手稿，以其姓名首字母缩写命名）
fault tolerant / fault tolerance	容错
free list	空闲列表
garbage collector	垃圾回收器
hash	哈希（值）
Indiana Jones	印第安纳·琼斯
invariant	不变式
Jim Gray	吉姆·格雷
Keith Marzullo	Keith Marzullo（保留原名）
leader	领导者（leader，分布式系统中负责协调的节点）
Leslie Lamport	莱斯利·兰波特
Marshall Pease	Marshall Pease（保留原名）
mutual exclusion	互斥
Part-Time Parliament	《兼职议会》（Paxos 论文名）
partial orderings	偏序关系
Paxos algorithm	Paxos 算法
Peter Gordon	Peter Gordon（Addison Wesley 出版社编辑，保留原名）
Petri nets	佩特里网
Raft Algorithm	Raft 算法
Ryan Peterman	Ryan Peterman（保留原名）
Scribe	Scribe（早期文本排版系统，TeX 的前身之一）
shared registers	共享寄存器
SRRI	SRRI（斯坦福研究所，即今日的 SRI International）
starvation	饿死（进程饥饿）
state machine	状态机
time sharing	分时系统
Turing Award	图灵奖
Turing machine	图灵机
Whit Diffie (Whitfield Diffie)	惠特·迪菲（惠特菲尔德·迪菲）
Xerox PARC	施乐帕克（Xerox PARC，Palo Alto Research Center）

此文章由 AI 翻译

引言