Transcription
如果你认为你知道某事但没有写下来，那么你只是认为你知道。 >> 这是莱斯利·兰波特。他是一位图灵奖得主，以其在分布式系统领域的贡献而闻名。我采访了他，了解他论文背后的故事。 >> 他们的反应让我震惊。他们变得愤怒。我真的认为他们可能会动手打我。 >> 迪克斯特拉的旧解决方案中，有什么让你觉得不满意？对于大多数人来说，一个真正给迪克斯特拉留下深刻印象的想法并不是显而易见的。 >> 作为 Paxus 算法的发明者，我问了他对竞争对手 raft 算法的看法。 >> Raft 中发现了一个 bug 并进行了修复，但我相信他们发现更易于理解的算法是那个有 bug 的算法。 >> 我也很享受回顾他 50 年的职业生涯。你说：“你从不认为自己聪明。怎么会这样？”愚蠢的人认为自己聪明，因为他们太愚蠢而无法意识到自己并不聪明。 >> 你曾经觉得自己是个失败者，因为你想开发这个宏大的并发理论，但你从未发现它。你现在还这么觉得吗？完整剧集在这里。我想从面包店算法开始。面包店算法解决了什么问题？你知道你是如何发现这个问题的吗？ >> 嗯，这个问题是由埃德加·迪克斯特拉在 1965 年的一篇论文中发明或发现的，我认为是 1965 年的论文，我认为那才是并发编程理论的真正开端。他第一个真正利用并发作为一种组织程序的方式，将其视为一组半独立的任务，而进程必须相互同步。嗯，其中一个进程，或者说在进程之间，嗯，那是在分时时代，嗯，你知道，就在分时的开端，多人使用同一台计算机的想法。人们意识到计算机比人类工作得快，而且在那时计算机非常昂贵。所以他们想让计算机同时被多人使用。每个用户运行的程序，嗯，是一个独立的程序，但有时，嗯，会有共享的资源。例如，一台打印机，两个人同时尝试在同一台打印机上打印。嗯，结果将是，嗯，不那么令人满意。所以，嗯，他意识到存在这个问题，即通过他称之为“临界区”或每个进程中的一段代码来同步多个进程，这样一次最多只有一个进程可以执行那段代码。所以那段代码可能是打印机上的代码。所以问题是如何让进程在它们之间同步，以便一次最多只有一个进程执行其临界区。嗯，我是在 1972 年了解到这个问题的，因为 CACM 通信中有篇文章给出了解决方案，我以前会编程，我喜欢小编程问题，嗯，这只是一个非常好的小编程问题。所以我看了那个解决方案，它相当复杂，我说，“哦，天哪，这不应该那么难。”所以我写了一个非常简单的双进程算法并提交给了 CACM。几周后，我收到了一封编辑的信，指出了我程序中的 bug。这产生了两个影响。第一个是我意识到并发程序很难写对，你需要证明它们是正确的。第二个是让我觉得我要解决那个该死的问题。我提出了面包店算法，它的灵感来自于，嗯，现在称为熟食店问题的想法，你有一个熟食店柜台，它收集，嗯，票据，一卷票据，每个顾客进来都会拿一张票据，然后下一个要服务的人将是那个还没有被服务过的、拥有最低编号票据的人。基本上，我采用了这个想法，但是因为没有中央服务器，或者至少迪克斯特拉指定的这个问题不涉及中央控制。每个进程基本上都必须选择自己的票据。那就是，嗯，基本想法，算法，嗯，相当简单。我写了一个正确性证明。而正确性证明向我揭示了这个算法具有这个非常有趣的属性。事实上，有人在一本书或论文中发表说，嗯，不可能在不使用某些低级互斥的情况下实现互斥。而当时普遍假设的互斥是共享寄存器。嗯，共享内存块，可以被不同的进程读写。而想法是，嗯，你不能让一个进程，嗯，两个进程同时写入，或者一个进程在另一个进程写入时读取。人们假设这些操作是原子的。它们总是表现得好像它们按特定顺序发生。但面包店算法的惊人之处在于它不需要这个假设。它使用，嗯，每个共享内存块只由一个进程写入。所以它不必担心两个进程相互干扰。你可能遇到的唯一问题是有人在读取值时，嗯，可能会得到一些未知的值，但算法仍然有效。如果一个进程在读取寄存器时，嗯，读取了正在写入的值，那么那个读取进程可能会得到任何值，而算法仍然有效。我在你关于这个问题的写作中看到，你与一位名叫阿纳托尔·霍尔的同事分享了它，而证明非常出色，以至于他们不相信。>> 嗯，结果非常出色。>> 是的。是的。他们不相信。>> 嗯，我把证明写在了白板上，他找不到，但他回家后说一定有什么问题，嗯，他显然从未发现任何问题。>> 对。我看到论文的标题是“迪克斯特拉并发编程问题的新解决方案”。迪克斯特拉的旧解决方案有什么让你觉得不满意，并让你想解决这个问题？>> 嗯，他的原始解决方案有一个不令人满意的方面，那就是如果有很多进程不断尝试进入它们的临界区，那么单个进程可能会被饿死。可能永远无法访问临界区，嗯，下一个解决方案，我认为是唐·库斯的，所解决的条件是，嗯，人们期望的或衡量其效率的标准是进程可能需要等待多长时间，我相信面包店算法是第一个真正意义上的“先到先服务”。也就是说，如果一个进程先选择了它的号码，然后另一个进程试图进入，那么第一个进程将比另一个进程先进入临界区。我相信面包店算法是第一个具有该属性的算法。而且我认为它比其他解决方案更简单。>> 在很多写作中，我看到你和迪克斯特拉一起工作，我看到在 1976 年，你实际上在荷兰工作了一个月，并与他一起工作。你能谈谈那一点吗？>> 迪克斯特拉以前有一些被称为 EWD 的东西，是他的首字母缩写。小论文，当他想到某事，有了某个想法时，他会写下来并发送给别人。嗯，其中一个 EWD 是关于他和一些同事，或者实际上是门徒，我猜你可以这么称呼他们，写了这个算法。这是第一个并发垃圾回收算法。一种程序编写方式发生了演变，有一个内存池，当程序需要一块内存时，它会向某个服务器请求并获得这块内存。嗯，但有时它会停止使用这块内存。但程序本身不知道，创建这块内存的特定进程，嗯，不知道是否有其他进程正在使用这块内存。所以有一个额外的进程叫做垃圾回收器，它会检查内存，判断哪些内存块不再被使用，然后将它们放回，嗯，称为空闲列表，嗯，在那里，嗯，提供内存的服务器，嗯，进程可以取用。我看了看，我意识到，嗯，我可以简化算法。嗯，因为他有一些，嗯，空闲列表的处理是由一个特殊进程完成的，嗯，它需要担心它自己与，嗯，使用内存的进程的协调。我意识到那个空闲列表可以只是常规数据结构的一部分。嗯，所以它不需要特殊处理，这对我来说是一个非常简单的想法，一个非常显而易见的想法，我发给了他，然后当我拿到下一版论文时，我发现他把我列为作者，我认为他非常慷慨，嗯，做了这件事，因为这似乎是一个非常简单的想法，我的意思是，非常显而易见的想法，后来我才意识到，对于大多数人来说，这并不是一个显而易见的想法，而且这实际上给迪克斯特拉留下了深刻印象，那是我唯一真正与迪克斯特拉一起做的事情，很多年后他说我有一个非凡的抽象能力，只有在最近几年，我的意思是，也许在我获得图灵奖之后，我才意识到我成功的理由以及我最终获得图灵奖的原因不是因为我特别聪明，而是因为我拥有这种抽象的天赋，而迪克斯特拉足够聪明，意识到我被邀请去待一个月，但不是和迪克斯特拉，而是和他的一位同事卡尔·卡尔·霍尔顿。从那次访问中，只有一件事被发表了。我和卡尔每周都会与迪克斯特拉会面。嗯，在讨论过程中，这个想法不知怎么就出现了，导致了我写并发表的一个面包店算法的变体。所以，那是从我在荷兰度过的一个月里产生的唯一有形的结果。>> 是的。我看到你写了。是的。你每周花一个下午的时间，在迪克斯特拉的房子里工作、交谈和喝酒，你不太记得那篇论文上具体是谁负责什么，但是>> 是的。嗯，我不认为我真的能喝醉，因为嗯，我可能开车去参加会议又开回来了。所以，>> 对。对。>> 我喝的荷兰啤酒酒精含量不高。>> 我想谈谈你引用次数最多的论文，题目是“分布式系统中的时间时钟和事件排序”。这篇论文的背景是什么，以及你用它解决了什么问题？>> 起源很简单。嗯，嗯，有人给我发了一篇关于构建分布式数据库的论文，嗯，其中有数据的多个副本在不同的地方，你需要以某种方式保持它们同步。我看了看，我意识到他们的解决方案存在这个问题，即它们会像它们发生的顺序一样被执行，但那个顺序可能与它们实际发生的顺序不同。嗯，发生之前意味着什么，这个概念并不明显，或者对大多数人来说并不明显，但我碰巧，嗯，了解了，嗯，特别是狭义相对论，嗯，也就是狭义相对论的时空观，你基本上将空间和时间视为一个四维的东西，爱因斯坦在 1905 年发表了他的论文，然后在，我想是 1909 年，一个我记不起名字的人提供了这个四维视图，而这个四维视图具有，嗯，一个事件发生在另一个事件之前的具体概念，那个概念是，一个事件发生在另一个事件之前。如果一个信号从第一个事件发出，并在第二个事件发生之前被第二个事件的执行者接收到，但通信速度不能超过光速，因为没有任何东西能比光速更快。嗯，我意识到有一个明显的类比。嗯，发生之前这个概念与相对论中的完全相同，只是不再是关于一个事件是否可以通过以光速传播的事物影响另一个事件，而是关于第一个事件是否可以通过系统中实际发送的消息来影响另一个事件。嗯，让人们震惊的是这个定义，嗯，在分布式系统中发生之前，这篇论文也是我称之为，嗯，第一篇关于分布式系统的科学成果。我可能犯了一个错误，有人警告过我，在一篇论文中包含两个想法。另一件事是我意识到有一个算法可以显示一个事件是否会产生一个满足该条件的排序，即如果一个事件发生在另一个事件之前，那么第一个事件将被排序在另一个事件之前。我意识到如果你有一个算法来做到这一点，你就可以用它来提供任何分布式系统所需的同步，因为你可以用状态机来描述该系统。而我当时描述的状态机就是，嗯，它有一个状态，进程执行，嗯，需要按顺序执行的命令，而命令只是改变状态并产生一个值。所以你可以简单地将这个状态机描述为，嗯，事件如何影响状态，以及它们如何产生，以及，嗯，新的状态是什么，以及值是什么，作为原始状态的函数。事实证明，这对我来说非常明显，但实际上这篇论文中最重要的想法是，它表明了通过思考状态机来构建分布式系统的方法，以及思考并发系统作为状态机的方法。嗯，但那部分被完全忽略了。事实上，我两次与人谈论那篇论文，他们说那篇论文里没有任何关于状态机的说法，我不得不回去重读那篇论文，以确保我没有发疯，它确实提到了状态机。它也很重要，嗯，因为另一个原因。嗯，如果你试图理解一个并发程序，嗯，并发程序是这样写的，面包店算法确实是一个例外，嗯，并发程序是这样写的，假设原子操作，所以你假设执行就像一个序列，你，你可以假设执行是一个事件序列。事实证明，理解，嗯，为什么程序会产生正确答案？嗯，答案是，嗯，你给它，嗯，嗯，正确的输入。你给它输入，然后它会产生正确的答案。嗯，但是当你执行到一半时，它一开始得到的东西已经是陈年旧事了。唯一能告诉程序下一步做什么的是它的当前状态。而理解一个程序的方法，嗯，一个简单的程序，它只是，嗯，接受输入并产生答案，就是说，在每个点上，状态的属性是什么，能够确保它产生的答案是正确的？而那个属性，在数学上是一个布尔值函数，称为不变式。而理解不变式就是理解系统的关键。嗯，嗯，程序，我知道并发系统和并发程序也是如此。人们喜欢写证明，嗯，关于序列的行为证明。问题是，可能的序列数量，嗯，序列长度的指数级，而推理的复杂性变得非常复杂。很容易错过案例。嗯，但是不变式证明的复杂性，不变式的复杂性基本上是，嗯，哦天哪，可能的执行次数是进程数量的指数级，但是，嗯，不变式证明的行为是进程数量的二次方。嗯，基本上这就是为什么不变式证明更好，但是，嗯，仍然有很长一段时间，嗯，人们，嗯，从事分布式系统理论的人，正在尝试，嗯，开发，嗯，方法和形式化，一些基于偏序的方法，他们，嗯，发表了很多论文，但这只是，嗯，不是实际操作的方法，如果你想在实践中这样做，那不是方法，我不应该说，嗯，不是方法，嗯，有一些算法，比如面包店算法，嗯，你知道，嗯，用偏序思考实际上是很好的方法，但那些是例外，嗯，有效的方法，嗯，你可以确信它会有效的方法是使用不变式。>> 我想谈谈，嗯，下一篇论文，嗯，是“拜占庭将军问题”。我认为这是我们在大学计算机科学课程中经常听到和学到的东西，而且名字很棒，我想知道这个问题的背景故事。在我写完那篇“时间时钟”论文之后，它告诉了你如何构建一个分布式系统，但假设没有故障，而很明显，嗯，分布式系统的一个原因是你有多个计算机，所以如果一个失败了，你可以，嗯，继续运行。特别是，嗯，那是我加入 SRRI 时正在解决的问题，但我在加入 SRRI 之前就开始研究这个问题，而我，嗯，没有关于我应该考虑什么的观念，嗯，故障会做什么，所以我假设，嗯，最坏的情况是，一个故障进程可能会做任何事情。我提出了一个算法，它基本上会在该假设下实现一个状态机，而我提出的算法使用了数字签名。是的。所以它利用了这样一个事实：一个故障进程可以做任何事情，但它不能伪造另一个进程的签名。>> 这意味着消息可以被信任，它来自私人。>> 对，所以你可以转递消息，而人们知道可以检查转递的消息是否确实是最初发送的消息。>> 嗯，所以使用这个的解决方案，当我加入 SRRI 时，我意识到人们正在尝试解决同一个问题。嗯，但有两个区别。首先，在我做这件事的时候，嗯，是 1975 年。很少有人知道数字签名，事实上，我不记得 Diffy Helman 论文是什么时候发表的，但大约是 1975 年，我碰巧知道数字签名，因为 Whit Diffy，他是那篇论文的两位作者之一，是我的朋友，事实上，有一次我们在一家咖啡馆，他正在描述这些事情，他说我们有一个构建数字签名的问题，嗯，我们还没有解决，我说哦，这看起来足够容易了，嗯，我坐下来，字面上是在一张餐巾纸上写出了，嗯，第一个数字签名算法。当时它并不实用，因为它基本上需要，嗯，大约 128 位来签名你正在签名的东西的一位。它并没有那么糟糕，因为，嗯，你可能会认为，因为你可以签名不是整个文档，而是文档的哈希值，你假设，嗯，人们无法伪造。>> 哈希值，他们无法逆转。>> 是的，你无法逆转，你取一个哈希值，然后，嗯，找到另一个满足该哈希值的哈希值或另一个文档。但总之，这就是为什么我有，嗯，数字签名是我工具箱的一部分。嗯，所以 SRRI 的人们没有那个，但他们也有一个更好的抽象。与其就命令序列达成一致，嗯，他们会达成一致，有一个算法来就单个命令达成一致，然后该算法将被执行多次，嗯，这是一种更好的描述方式，嗯，你正在做什么，而不是，嗯，我的方法。所以第一篇发表的论文，嗯，同时包含了他们的原始，哦，但是因为他们没有数字签名，他们使用了不同的算法，嗯，并且他们有一个属性，即容忍一个故障进程，你需要四个进程，而如果使用数字签名，你只需要三个进程。所以原始论文包含两个算法，所以我也是作者之一。没有数字签名的另一个算法更复杂，而针对 N 个进程的通用算法确实是天才之作。它几乎是不可理解的。你只需要阅读那个复杂的证明，嗯，对于任意数量的进程，你需要 4N 个进程来容忍 N 个故障，而使用数字签名，你需要 3N 个进程，而单个故障的算法并不难，但多个故障的算法是马歇尔·皮斯完成的，真是太棒了。后来在一篇后续论文中，我发现了一个更简单的证明，一个归纳证明，如果它适用于 N-1，嗯，它适用于 3N 个进程，如果它适用于 3N*(N-1)，原始论文是，嗯，原始论文真是太棒了，谁会发现它呢？嗯，所以我们发表了那篇论文，我意识到这是，这是整个拜占庭故障的想法。嗯，拜占庭故障是指一个进程可以做任何事情。现在我假设，嗯，进程可以做任何事情，因为，嗯，我不知道该假设什么，但 SRRI 的人们有合同，用于构建一个多进程多计算机系统来驾驶飞机，所以他们是那些欣赏解决可以做恶意事情的进程的必要性的人，因为他们真的无法假设它会做什么。每次你得到一个算法，你就会看到，哦，嗯，这个算法，嗯，试图得到一个有三个进程的算法，嗯，对于一个故障，嗯，你会发现，嗯，哦，嗯，这，这有效，而且它一定，嗯，在实践中不可能发生。然后你就能找到一些看似合理的故障序列，导致算法被击败，如果有一个故障进程。所以你需要四个，嗯，不知何故，嗯，我认为数字签名几乎是算法中的一个隐喻，它应该是可能的，嗯，因为我们不担心恶意故障，而是担心随机发生的事情，应该有一种方法来编写一个数字签名算法，嗯，它应该有一个足够低的失败概率，但我从未研究过它，其他人也从未研究过。所以那个算法基本上被忽略了，因为当时数字签名非常昂贵。我不知道现在在做什么，因为，嗯，计算机是数字签名只是计算，而计算是，嗯，便宜的。嗯，但我记得有一次我碰巧与波音公司的一位工程师交流，我问他们是否知道这些结果，他说是的，他实际上是波音公司负责阅读那篇论文的人，他的反应是哦，我们需要四台计算机。嗯，但总之，我意识到这是一个重要的结果，它应该广为人知，我从迪克斯特拉那里学到了一件事。嗯，迪，嗯，我从迪克斯特拉那里学到的其中一件事是，他写了一篇名为“Dining Philosophers Problem”的论文。那篇论文引起了很多关注，但“Dining Philosophers Problem”，我不会深入探讨它是什么，但我认为基本问题并不特别有趣，但它有一个可爱的故事。它涉及一群哲学家围坐在一张桌子旁，吃着一种需要两把叉子的奇怪意大利面，每把叉子由两个人共享，但是，嗯，我认为正是因为这个可爱的故事，这个问题才如此受欢迎。所以，我决定，嗯，我们的工作需要一个可爱的故事，嗯，一个好故事，我发明了“拜占庭将军”，想法是，嗯，对于一个故障情况，有四个将军必须就是否攻击达成一致。嗯，如果他们都攻击，他们将赢得战斗。但如果只有一部分人攻击，或者即使三个人攻击，他们也会赢得战斗。但如果只有两个人攻击，嗯，他们会输。但是其中一位将军可能是叛徒。那么，你如何，嗯，解决这个问题？所以，嗯，它被表述为这些将军必须沟通并决定是进行一次攻击还是撤退的决定。嗯，我称之为“拜占庭将军”问题。>> 我在你关于这个问题的笔记中看到，也许有一个子集的问题或一个早期版本叫做“中国将军问题”或类似的东西。>> 哦，是的，是的，我，嗯，吉姆·格雷描述了一个不同的问题，嗯，一个不可能的结果，基本上它被称为“中国将军问题”，我不会费心去解释它是什么，所以这给了我将军的想法。我最初想到了阿尔巴尼亚将军的想法，因为当时阿尔巴尼亚对世界其他地方来说是一个黑洞，它是一个共产主义政权，属于苏联集团，但比苏联共和国更苏联，嗯，更具限制性。所以有人，嗯，我的老板说，“嗯，你知道，世界上有阿尔巴尼亚人，所以不应该有不同的名字吗？”然后我意识到拜占庭人，嗯，没有拜占庭人，那是完美的名字。所以，>> 有趣的是，这个故事中，因为这不是第一次指定这个问题，但这是你第一次给它命名，嗯，给它一个好听的名字，基本上，嗯，并添加了一些额外的结果。你在这个问题中看到了什么让你觉得它有趣？或者说，你怎么知道一个问题值得投入额外的时间？哦，嗯，这是因为，嗯，人们将要建造的计算机将驾驶我们的飞机，这是显而易见的，事实上，这是因为在 70 年代的石油危机期间，人们知道他们可以通过减小控制面的尺寸来制造更节能的飞机。但这使得飞机在空气动力学上不稳定。嗯，飞行员无法进行所有必要的调整来，嗯，保持飞机飞行，但计算机可以。所以很明显，未来是，嗯，飞机将由计算机驾驶，就像今天一样。嗯，人们没有意识到，他们认为，哦，如果你想容忍一个故障，你只需要使用三台计算机，他们没有意识到，嗯，对于任意故障，你需要四台，所以这是一个非常重要的结果，这就是为什么我相信它需要广为人知。>> 通常当你回顾你工作中解决的问题时，嗯，你是如何决定的？因为如果你在一家公司工作，你可以根据，嗯，对公司的影响来决定，比如它是否会赚更多的钱或节省成本之类的。但我想知道在你整个职业生涯中的工作，嗯，想想面包店问题或你后来的一些工作。你怎么知道哪些问题是值得的？在我整个职业生涯中，我为私营公司工作，嗯，不是，嗯，不是在学术界或政府部门。嗯，所以有些问题是由于，嗯，有时，嗯，一位工程师遇到了一个问题，然后来找我。所以，嗯，例如，DIS Paxos 就是这种情况，有人实际上想要一个算法来做它。你之前提到了 Paxos，我知道这是你最著名的作品之一。对那个论文的背景故事或者你正在解决的问题感到好奇。>> 嗯，我试图解决的问题与我在拜占庭将军工作中解决的问题完全相同，基本上是构建一个容错状态机。但那时，嗯，工业界感兴趣的故障是那种故障意味着计算机只是停止，而不是做任意事情。所以，嗯，Paxos 是一个算法，用于，嗯，用于构建容错系统，以处理那类故障。嗯，我工作的人，嗯，是 DEC 的 circ，我于 1985 年加入，他们构建了一个，嗯，最早的操作系统之一，它是一个分布式操作系统。所以，嗯，基本上每个人都有，他们基本上是那些来自 Xerox Park 并发明了个人计算的人，但他们也有分布式个人计算的概念，他们发明了以太网，嗯，为此。所以基本上，嗯，大楼里的所有计算机都在一个以太网网络上，并共享一个公共存储，嗯，他们有一个算法来维护该存储的一致性，我不相信，嗯，他们没有算法，他们有一个操作系统，里面有代码，我当时不相信，嗯，他们所做的，嗯，是可能的。也就是说，我当时不认为，嗯，我忘了具体为什么我不认为它可能，但总之，我开始，嗯，试图提出一个，嗯，一个不可能证明，然后开始证明，嗯，一个解决这个问题的算法必须做到这一点，而为了做到这一点，它必须做到那个，在某个时候，我停下来，说哦，这不是一个证明。它不能。这是一个解决问题的算法。>> 你说他们有代码但没有算法。>> 是的。>> 嗯，你这话是什么意思？当大多数人坐下来开始写程序时，嗯，他们开始从代码的角度思考，而我早期职业生涯中学到的一件事，我不记得具体是什么时候了，在我开始写算法的时候，人们称它们为程序，我当时可能也称它们为程序，我的意思是，我记得当时我意识到我不是在谈论程序。我感兴趣的是算法。嗯，算法比程序更抽象。嗯，算法可以是，嗯，程序是用某种特定的代码编写的。但是算法可以被实现，如果程序是用任何代码编写的。它，它是在一个更高的抽象级别。当然我喜欢它，因为抽象是我擅长的，嗯，即使我没有意识到我正在做什么。嗯，所以我的职业生涯的大部分时间，基本上从大约，嗯，2000 年左右开始，就是让那些构建并发系统的人，不仅仅是写代码，而是拥有一个算法。现在一个系统有很多功能，但应该有一个程序的核心，嗯，涉及到同步不同的进程或分布式系统中的不同计算机，而那段代码，嗯，很难写对，嗯，你，你不想从代码的角度思考，因为静态编码，嗯，混淆了很多与并发方面无关的问题。所以你应该思考，嗯，首先得到一个执行同步的算法，然后实现该算法。我看了 Paxos 的论文，嗯，以及你的一些笔记，我看到，嗯，有一个八年的时间间隔，在你提出算法到论文实际发表之间，论文名为“Part-Time Parliament”。为什么会有八年的间隔？哦，嗯，最初的审稿人说，嗯，这篇论文还可以，嗯，不是非常重要，但幸运的是，巴特勒·兰姆森意识到了算法的重要性，再加上，嗯，我想你可以实现任何东西，因为它是在实现一个状态机，嗯，然后，嗯，继续，嗯，构建你的系统，嗯，使用 Paxos，嗯，嗯，并以状态机的形式思考。所以，嗯，我没有，嗯，所以这个想法正在传播，所以，嗯，我并不急于发表，所以，嗯，我只是让论文搁置，最终，嗯，来了一位新编辑，嗯，他说，嗯，我认为论文的状态是它刚刚被接受但还没有完成，需要修改。所以他决定，是的，让我们，嗯，发表它，它最终被发表了，有一些，嗯，需要提及的，嗯，在那期间完成的工作，而我得到了，嗯，基思·马祖洛，嗯，为我做了那部分。嗯，所以故事是，这个手稿，这个是，嗯，故事是关于 Paxos 的，嗯，这是，嗯，发生在几个世纪前，嗯，这个手稿，我用它来，嗯，当一些，嗯，我当时认为显而易见且不有趣的事情的故事时，嗯，论文会说，不清楚 Paxons 在这一点上做了什么，但是，嗯，总之，嗯，基思，嗯，坚持了这个想法，嗯，这是一个，嗯，对这个古老事物的描述，他写了一个，嗯，小前言或序言之类的，嗯，并添加了，也许，我想，一些参考文献。我在你的写作中也看到，当你谈论最初展示论文时，>> 你甚至打扮成印第安纳琼斯风格的考古学家。嗯，当你展示这篇 Paxos 论文和算法时，那效果怎么样？>> 嗯，我想讲座可能很顺利，但我认为没有人理解算法，或者没有人理解算法的重要性。>> 听起来除了巴特勒·兰姆森，没有人理解。他看到了什么让他与众不同？我想。>> 嗯，他对构建系统有很好的理解，嗯，他确实配得上他的图灵奖。他是 Xerox Park 的早期成员之一，他们正在构建分布式个人计算。他和查克·撒克，我想，可能是那个实验室的两位资深人士。我后来看到一篇论文，描述了一个新的算法，似乎解决了同样的问题。Raft 论文。我想知道你是否读过它，以及你对它与 Paxos 的看法。那篇论文的作者实际上把原始论文的草稿发给了我，我看了看，我说，嗯，我不记得我是否说“当你有一个算法时把它发给我”还是“当你有一个证明时把它发给我”。我忘了是哪个了，嗯，你明白了，他们确实在论文中添加了证明，或者没有。嗯，是的，我从未读过以后的版本，一个我重视的人说，嗯，读过它，说它基本上是 Paxos 论文，但是，嗯，Paxos 论文中一些未完成的故事，嗯，嗯，填补了一些故事，但是他们，嗯，用一种非常不同的方式描述它。嘿，Paxos 的基本思想是，它有两个阶段，你试图实现一系列，嗯，决策，事实证明，你可以为整个过程执行第一个阶段，它涉及一个领导者。嗯，领导者必须被选举出来。嗯，但事实证明，你可以只执行第一个阶段一次，只要你有同一个领导者，你就不必再执行它了。但是你只需要做第二个部分，然后你必须选举新的领导者，如果新的领导者失败了，然后做第一个部分。所以想想这两个阶段。但是人们，嗯，工程师喜欢这样想，嗯，你这样做，嗯，你谈论第一个部分，第二个阶段，你一直这样做，直到领导者失败，然后你回到，然后你必须做这件事，所以它解释的顺序是相反的。事实上，嗯，当你从头开始时，嗯，你不需要做第一个，嗯，第一个阶段，你基本上，嗯，第一个阶段所做的事情可以被内置到初始状态中，但是，嗯，我认为那是正确的，嗯，这两个阶段，理解它的方式。嗯，但是，嗯，Raft 的人们也有这个想法，嗯，Raft 更好，因为它更简单，我必须说，很多人说 Paxos 很难理解，我不明白为什么。我的意思是，我向一些人解释了五分钟，他们就明白了。总之，Raft 的人们说，其中一个想法更简单，因为他们甚至在，嗯，教，嗯，Paxos 给一个班级，嗯，Raft 给另一个班级，他们花了，然后是的，所有的学生都说，是的，它更容易理解。嗯，有趣的是，嗯，Raft 中发现了一个 bug 并进行了修复，但我相信他们发现更易于理解的算法是那个有 bug 的算法。所以，嗯，这让我意识到，嗯，嗯，大多数人，嗯，理解意味着什么，对我来说，理解意味着，嗯，你可以写一个证明，但是对大多数人来说，理解意味着温暖的模糊感觉，嗯，而 Raft 的描述给了他们，嗯，更多的温暖的模糊感觉，因为，嗯，你知道，那似乎是，嗯，程序员，嗯，喜欢思考算法的方式，嗯，嗯，第二个阶段，嗯，首先，直到，嗯，你遇到故障，然后，但是我的描述方式有助于你更好地理解它为什么实际上有效。>> 所以，是的，我们谈论了很多你的论文。我知道你的另一项贡献，无论你当时是否知道，那就是 Latte，以及构建它，并且它对整个学术界产生了影响。你想构建 Latte 的故事是什么？>> 哦，那很简单。嗯，我当时正在写一本书，嗯，很明显，TeX 是基本排版系统，一个人必须使用。但是，嗯，我觉得我需要宏来让 TeX 做我想让它做的。嗯，所以我想，嗯，多花一点精力，我就可以让其他人使用这些宏。我之前使用的系统是 TeX，它叫做 Scribe。嗯，Scribe 的基本思想是，你描述文档的逻辑结构，嗯，而不是，而 Scribe 会进行格式化。嗯，Scribe 的格式化效果并不好。所以，嗯，但显然，嗯，我喜欢抽象的想法，即想法很重要，而不是文本，嗯，写作很重要，而不是排版。所以，嗯，我实际上在某个时候，嗯，我遇到了 Peter Gordon，Addison Wesley，我不确定你该怎么称呼他，但他寻找，嗯，要出版的书。嗯，他说服我写一本关于它的书。在那时，我从没想过人们会花钱买一本关于软件的书。但，嗯，管他呢。他介绍了我认识了一位在 Addison Wesley 的排版设计师，他负责了标准 LaTeX 样式的排版设计。嗯，基本上，我只是在我的“业余时间”做的。嗯，花了六到九个月左右。我认为，嗯，时效性已经过了，但我确实花了一些时间在这上面，当时我声称，嗯，将时间计入一个与此无关的项目。>> 关于写作，你有一句我非常喜欢的名言。它是“如果你在不写的情况下思考，你只是认为你在思考。”我想听听你对这句话的看法。>> 嗯，这实际上是为，嗯，构建计算机系统的人准备的。你有一个想法，你认为它会奏效。嗯，或者你有一个东西，嗯，你认为别人会想要使用。嗯，写一个描述。嗯，有一个古老的格言，我不知道，我听说过，那就是“在写程序之前写说明手册”。这是个好建议。嗯，我没有用 Latte 这样做，但确实，当我写书的时候，我发现有些东西很难描述，很难解释，需要改变，我因此做了，嗯，一些改变。但我并没有从一开始就写说明手册。为什么写作有助于思考？>> 因为很容易，嗯，很容易欺骗自己。嗯，我的意思是，这支撑了我，嗯，我写证明的整个想法。我学到的一件事是，你必须写一个，嗯，正确性证明。
并发算法。而且当我的算法开始变得更复杂时，证明开始我开始写数学博士论文。我知道如何写证明，并且我开始像往常一样写证明。我意识到这根本行不通，因为涉及的细节太多了，我根本无法跟踪它们，也无法确定我是否已经完成了。因此，作为一名计算机科学家，我知道如何处理并发的层次结构，所以我设计了这个层次结构，其中一个证明是你所知道的，它是一系列步骤，每个步骤都有一个证明，而证明要么是一个段落，要么是一个陈述，一系列步骤，每个步骤都有其证明，而证明可以是段落，也可以是带有其证明的步骤序列，你知道，所以你把整个问题分解成这些小块。因此，从来没有关于“这是从哪里来的”的问题。你知道你在陈述这个步骤是从这个步骤、这个步骤、这个步骤、这个步骤推导出来的，如果它不是从那个步骤推导出来的，那么你的证明就是错误的。定理可能是正确的，但但这意味着你的证明是错误的。嗯，你知道，所以我发现这在写程序证明方面效果很好，但我决定真正地，你知道，我也写定理证明，你知道，你知道，呃，你知道，想想证明是那些更像普通数学的东西，我开始尝试用它们来做，我发现它效果非常好。所以当我开始试图说服数学家写这些证明时，我开始在一个小型研讨会上，我去了，你知道，我不会描述它是什么，但是，我向大约 20 位数学家描述了这个证明，他们的反应让我震惊，他们变得愤怒，我真的以为他们可能会动手打我。所以我相信正在发生的是，当人们，我的意思是，我相信那是完全不合理的，当人们做出不合理的行为时，往往是出于恐惧，我相信人们害怕的是，数学家害怕的是，他们将不得不写他们的证明来让一个计算机程序信服，事实上，你知道，我给了一个演讲，我非常清楚地说，这并不一定，你不必比你现在更正式，你可以写完全相同的证明，你知道，但这只是一个组织问题，而且它非常简单，你知道，层次结构，然后当你使用一个事实时，提到你正在使用它，而不是关于形式主义或任何东西，你知道，在我发表那个演讲后，有人站起来说，我不想为计算机程序写我的证明，我的证明。事实上，这样做的工作量更大，因为工作量更大的原因是它揭示了你没有说出的东西，以及其中有一些步骤，你知道，你可能认为它们是显而易见的，但你没有写下来。如果你相信某件事是正确的，但实际上并没有，如果你认为你知道某件事但没有写下来，你只是认为你知道它。这就是错误发生的地方。你知道，这就是你论文中三分之一的错误可能，你知道，你知道，呃，出现的地方，因为它确实让你诚实。当我回顾你的职业生涯时，我认为你做出了很多贡献，人们可能期望来自学术界，这些论文之类的，但你所有的工作都在工业界。你为什么不认为自己是学术界人士，而更像是为工业界工作？嗯，我一开始是编程，我最终找到了工作，把我带入了我们现在称之为计算机科学的领域。当时我甚至从未意识到，你知道，可能存在计算机，计算科学。你知道，直到 70 年代中期到后期，我才意识到是的，存在计算机科学，并且作为一名计算机科学家。嗯，但对我来说，计算机科学似乎从来都不是一门学术学科。在某个时候，我，你知道，不得不在做计算机科学（不称其为计算机科学）和在大学教数学之间做出选择。我出于相当随机的原因选择了做计算机科学。嗯，所以，你知道，在最初的，我不知道，嗯，直到 80 年代中期左右，对我来说，似乎并没有，你知道，你知道，计算机科学是人们需要去大学学习的东西。而且，我想之后，我有点，我想我只是觉得教计算机科学不会有趣。所以>> 我在你的写作中看到你有一个脚注，说你在某个时候觉得自己是个失败者，因为你想开发一个宏大的并发理论，但你从未发现它。嗯，你仍然这么认为吗？或者你对那个脚注有什么看法？很多人，你知道，很大一部分像我一样做事的人，而这样做的人并不多，有一种观念，他们正在寻找并发的图灵机，你知道，图灵机是这个抽象，它真正捕捉了计算是什么，他们正在寻找能够成为，你知道，并发计算的图灵机，你知道，没有人成功。我的意思是，有些人认为他们成功了。嗯，帕特里内特是，我猜我没有时间解释，但是，它在 70 年代很流行。嗯，我实际上很惊讶地认为仍然有很大一部分人在做，帕特里内特。但我现在意识到的是，帕特里内特和大多数人所做的事情实际上是基于语言的。而我从来不关心语言。我关心的是语言所表达的内容。而且，你知道，我意识到在某种意义上，你知道，也许我意识到了计算的图灵机是什么，状态机。嗯，状态机是我现在描述它们的方式略有不同。它们没有命令。它们只有一个状态和一个下一个状态关系。嗯，甚至比谈论命令和值之类的东西更简单。嗯，你知道，对我来说，你知道，那就是，嗯，那就是并发的图灵机，但它，它没有图灵机提供的功能，因为它，它没有，图灵机所做的就是描述，你知道，什么是可能的，而状态机可以描述任何东西，包括不可能的事情。嗯，事实上，有一个很好的理由。嗯，例如，当我描述一个算法时，我会谈论，你知道，一个变量的值，你知道，可以是任何整数。现在你可以实现一个程序，其中你有任何整数，但这使得，但谈论，你知道，计算机整数会不必要地使事情复杂化。人们有一种奇怪的想法，你知道，因为某样东西是无限的，所以它更复杂。他们弄反了。引入无限是为了简化事情。你知道，你学到的第一件事就是算术。你正在学习无限整数的算术，因为如果你限制在一组有限的整数，算术会变得复杂得多。所以，你知道，数学的抽象，人们发现，你知道，因为他们没有 proper 的数学训练，发现，你知道，困难，实际上是简化事情，这就是你所使用的，数学状态机是由我用数学描述的，这是正确的，你知道，最强大的做事方式。但计算机人员和计算机科学家以及程序员非常热衷于语言，所以他们正在寻找，你知道，他们发明了各种各样的语言，它们都可以被描述，事实上，如果你想给它们一个语义，你会用状态机来做，而他们只是认为，你知道，这种语言 ES 提高了你的思维。嗯，它不会，你可能，我的意思是，有使用计算机语言的理由，你不会用数学写你的程序代码，它们基本上涉及效率，但为了理解，你知道，你无法构建数学，你无法击败数学，你知道，试图通过看起来像编程语言的东西来做到这一点，只是处理并发时错误的应对方式。>> 当我看到你写的所有东西和所有故事时，有这些小轶事。有些地方你说你从不认为自己聪明，但你注意到其他孩子在理解事物方面有很大困难，或者是的，你解决了一个别人有困难的问题，但你并不认为你的贡献是杰出的，或者别的什么。这让我无法理解，因为你也赢得了图灵奖，并做了所有这些了不起的事情。那么，你怎么会仅仅发现事物而不聪明，却取得了如此大的成就呢？>> 嗯，心理学家谈论的这种普遍现象是，当一个人擅长某事时，他们不意识到自己有多擅长，因为这对他们来说很简单。还有一种相反的情况，那些不擅长某事的人认为自己比实际情况要好，因为他们不擅长。或者更简洁地说，愚蠢的人认为自己聪明，因为他们太愚蠢而无法意识到自己不聪明。嗯，我的天赋不在于某种意义上的原始智力。它是抽象，而且直到最近，你知道，大约过去 10 年，我才意识到我在这方面比其他人，大多数其他人要好得多。在这一点上，你经历了这么多，当你回顾你的职业生涯时。如果你能回到你刚大学毕业的时候，用你现在的知识给自己一些建议，你会说什么？>> 我很早就学到的一件事是，我不应该浪费时间去回答那些我不必回答的问题。我不会去想，你知道，我应该做什么，因为，这是一个我不必回答的问题。>> 感谢您收听播客。这是我一直很享受的一个热情项目。另一个我一直在秘密进行的另一个热情项目是制造一把我希望存在的符合人体工程学的键盘，我终于有了一个原型。所以，我很想向你展示我们制造的东西。它超薄且符合人体工程学。而且我在市场上找不到类似的东西。所以，这就是我们制造它的原因。我会在描述中放一个键盘的链接。你可以看看，了解更多关于这个项目的信息。我们绝对需要你的支持。另外，如果你对这个节目有任何反馈，我很想听听。YouTube 上的评论促成了像 Ilia Gregoric 和 David Fowler 这样的嘉宾的到来。直到有人评论，我才知道他们。另外，评论中的反馈帮助我学会减少介绍中的悬念。所以，你的评论绝对有影响。请继续告诉我你希望在节目中看到更多什么，我们下期再见。