计算机系统设计箴言

Butler W. Lampson

计算机科学实验室 Xerox Palo Alto Research Center Palo Alto, CA 94304

摘要

通过研究若干计算机系统的设计与实现，我总结出一些关于系统设计（system design）的一般性提示。本文描述这些提示，并用许多例子加以说明，例子范围从 Alto 和 Dorado 这样的硬件，到 Bravo 和 Star 这样的应用程序（application program）。

1. 引言

设计一个计算机系统与设计一个算法非常不同：外部接口（external interface），也就是需求，定义得不那么精确，更复杂，也更容易变化。系统有多得多的内部结构（internal structure），因此也有许多内部接口（internal interface）。成功的衡量标准也远不那么清楚。

设计者通常会在一片可能性的海洋中挣扎，不清楚某个选择会怎样限制自己作出其他选择的自由，或者会怎样影响整个系统的规模和性能。构建系统，甚至构建系统的任何主要部分，可能并没有一种“最佳”方式；更重要的是避免选择糟糕的方式，并在各部分之间建立清楚的职责划分。

我设计并构建过若干计算机系统，其中有些成功，有些失败。我也使用和研究过许多其他系统，包括成功的和不成功的。本文这些关于成功系统设计的一般性提示就来自这些经验。我并不声称它们有什么原创性；其中大多数都是有经验的设计者口口相传的常识。尽管如此，即使专家也常常会忘记，而且在第二个系统 [6] 之后还会有第四个系统。

免责声明：这些提示并不是新颖的，少数例外；不是万无一失的配方；不是系统设计或运行的定律；没有被精确定义；不一定彼此一致；不一定总是适用；没有得到所有权威专家的认可；也不保证有效。

本文最初发表于第 9 届 ACM Symposium on Operating Systems Principles，并刊登于 Operating Systems Review 15, 5, Oct. 1983, p 33-48。当前版本略有修订。

它们只是提示。有些相当一般而含糊；另一些则是具体技术，其适用范围比许多人知道的更广。无论是提示还是用于说明的例子，都必然经过了简化。许多提示也存在争议。

我尽量避免重复那些已经广泛传播的说教，比如模块化（modularity）、自顶向下、自底向上或迭代式设计（iterative design）方法、数据抽象（data abstraction）技术，以及其他系统设计方案。有时我会指出在鲁莽套用流行系统设计方法时可能遇到的陷阱。

这些提示由若干例子说明，大多来自我参与过的系统。它们覆盖的范围很广：硬件如 Ethernet 局域网（local area network）、Alto 和 Dorado 个人计算机；操作系统（operating system）如 SDS 940 和 Alto 操作系统；编程系统（programming system）如 Lisp 和 Mesa；应用程序如 Bravo 编辑器和 Star 办公系统；网络服务器（network server）如 Dover 打印机和 Grapevine 邮件系统。我试图避开最显而易见的例子，转而选择那些能展示某些著名方法意外用途的例子。几乎所有具体例子都有参考文献，但只有少数思想有参考文献；许多思想属于民间经验，如果要追溯它们的多重来源，将需要大量工作。

愿这些箴言留在你的记忆里， 铭刻于心。

用《哈姆雷特》中的引文来装饰一篇关于系统设计这一充满不确定性的过程的指南，似乎很合适。除非另有说明，引文都取自 Polonius 对 Laertes 的忠告（I iii 58-82）。也有一些引文来自其他来源，文中会注明。每一段引文都意在适用于紧随其后的文字。

每条提示都用一句口号概括；如果正确理解，这句口号会揭示该提示的要点。图 1 沿两个轴组织这些口号：它为什么有助于做出一个好的系统，即功能性（functionality，它能工作吗？）、速度（它足够快吗？）或容错性（fault-tolerance，它能持续工作吗？）；以及它在系统设计的哪个位置发挥作用，即保证完整性（completeness）、选择接口（interface）或制定实现。

粗线连接同一口号的重复出现，细线连接相关的口号。

本文主体按照“为什么”这一轴分成三节：功能性（第 2 节）、速度（第 3 节）和容错性（第 4 节）。

2. 功能性

最重要、也最含糊的提示，涉及如何从系统中获得正确的功能性，也就是让系统做你希望它做的事情。这些提示大多依赖接口这一概念：接口把某个抽象（abstraction）的实现与使用该抽象的客户隔开。两个程序之间的接口由这样一组假设组成：每个程序员为了证明自己程序的正确性，需要对另一个程序作出的假设（转述自 [5]）。定义接口是系统设计中最重要的部分。通常它也是最困难的部分，因为接口设计必须同时满足三个相互冲突的要求：接口应该简单，应该完整，并且应该允许足够小而快的实现。遗憾的是，接口中体现的假设常常最终变成误解。Parnas 的经典论文 [38] 以及一篇较新的设备接口论文 [5] 对这个主题给出了很好的实践建议。

在哪里？	功能性 它能工作吗？	速度 它足够快吗？	容错性 它能持续工作吗？
完整性	区分正常情况（normal case）和最坏情况（worst case）	削减负载（shed load） 端到端（end-to-end） 安全第一	端到端
接口	一次做好一件事： 不要泛化（don’t generalize） 把它做对 不要隐藏能力（don’t hide power） 使用过程参数（procedure arguments） 把事情留给客户 保持基本接口（basic interface）稳定 保留一个立足点	让它快 拆分资源 静态分析（static analysis） 动态翻译（dynamic translation）	端到端 记录更新日志（log updates） 使动作原子化（make actions atomic）
实现	准备扔掉一个版本（plan to throw one away） 保守秘密 再次使用好想法（use a good idea again） 分而治之（divide and conquer）	缓存答案（cache answers） 使用线索（hint） 使用蛮力（brute force） 在后台计算 批处理	使动作原子化 使用线索

图 1：口号汇总

接口之所以难以设计，主要原因是每个接口都是一种小型编程语言：它定义了一组对象以及可用于操纵这些对象的操作。具体语法（concrete syntax）不是问题，但编程语言设计（language design）的其他每个方面都存在。因此，Hoare 关于语言设计的提示 [19] 可以看作本文的补充。

2.1 保持简单

完美并非在无物可加时达到， 而是在无物可减时达到。 (A. Saint-Exupery)

你已经考验过的朋友， 要用钢箍把他们紧紧箍在心上； 但不要为了每个新结识的轻浮同伴， 把自己的手掌磨钝。

• 一次只做一件事，并把它做好。接口应该捕捉一个抽象的最低限度本质。不要泛化（don’t generalize）；泛化通常是错的。

我们面对的是一个无法克服的机会。 (W. Kelley)

当一个接口承担过多任务时，它的实现很可能会庞大、缓慢而复杂。接口是一份契约，承诺提供一定数量的服务；接口的客户依赖这份契约，而契约通常记录在接口规范（interface specification）中。客户还依赖于使用接口时付出合理的成本，也就是时间或其他稀缺资源（scarce resources）；但“合理”的定义通常不会写在任何地方。如果有六层抽象，而每一层都比“合理”成本高出 50%，那么顶层交付的服务就会偏离超过 10 倍。

KISS：Keep It Simple, Stupid.（保持简单，别犯傻。）(Anonymous)

如果犹豫，就先省略。 (Anonymous)

消灭功能。 (C. Thacker)

另一方面，

一切都应尽可能简单，但不能更简单。 (A. Einstein)

因此，服务必须有相当可预测的成本，接口也不应承诺实现者不知道如何交付的东西。尤其是，接口不应承诺只有少数客户需要的功能，除非实现者知道如何在不惩罚其他客户的情况下提供这些功能。更好的实现者，或者十年后在问题被更好理解时出现的实现者，或许能够交付；但除非你手上的实现者能做到，否则降低期望是明智的。

例如，PL/1 曾试图在大量数据类型（data type）上为大量通用操作（generic operation）提供一致含义，因此陷入严重麻烦。早期实现往往低效地处理所有情况；即使到了 15 年后的优化编译器时代，程序员也很难判断什么会快、什么会慢 [31]。像 Pascal 或 C 这样的语言更容易使用，因为每个构造的成本大致恒定，不依赖上下文或参数；事实上，大多数构造的成本也差不多。

当然，这些观察最强烈地适用于客户频繁使用的接口，例如虚拟内存（virtual memory）、文件、显示处理（display handling）或算术。对于很少使用的接口，例如密码检查（password checking）、解释用户命令或打印 72 点字符，为了功能性牺牲一些性能是可以的。（这真正的意思是，虽然成本仍然必须可预测，但它可以是最低可实现成本的许多倍。）这些谨慎规则也不适用于目标是学习如何做出更好实现的研究。但由于研究很可能失败，其他人不应依赖它的成功。

Algol 60 不仅优于它的前辈， 也优于几乎所有后继者。 (C. Hoare)

提供过多功能的例子数不胜数。Alto 操作系统 [29] 对文件提供普通的 read/write-n-bytes 接口，并为 Interlisp-D [7] 扩展了一个普通分页系统（paging system），把每个虚拟页（virtual page）存放在专用磁盘页（disk page）上。二者的实现都很小（文件约 900 行代码，分页约 500 行代码），也很快（一次缺页（page fault）只需要一次磁盘访问（disk access），计算成本恒定且只是磁盘访问时间的一小部分，客户也相当容易让磁盘满速运行）。继 Alto OS 之后的 Pilot 系统 [42] 追随 Multics 和其他若干系统，允许虚拟页映射到文件页，从而把文件输入/输出（file input/output）纳入虚拟内存系统（virtual memory system）。它的实现要大得多（约 11,000 行代码），也更慢（处理一次缺页常常需要两次磁盘访问，并且不能让磁盘满速运行）。额外功能是以很高代价买来的。

这并不是说这个接口不可能有好的实现，而只是说它很难。这个系统由几位非常能干且经验丰富的人设计和编码。问题的一部分在于避免循环依赖（circularity）：文件系统想使用虚拟内存，但虚拟内存又依赖文件。解决这个问题的相当一般的方法是已知的 [22]，但它们很棘手，而且容易在正常情况下导致更高成本和复杂度。

因这结局，误解了的意图 反落到发明者头上。 (V ii 387)

另一个例子说明，通用性多么容易导致意外的复杂性。Tenex 系统 [2] 有以下看似无害的功能组合：它通过陷阱（trap）转交给用户程序来报告对未分配虚拟页（unassigned virtual page）的引用。系统调用（system call）被看作扩展机器（extended machine）的一条机器指令（machine instruction），因此它对未分配虚拟页的任何引用也同样报告给用户程序。传给系统调用的大参数，包括字符串，按引用传递（passed by reference）。有一个 CONNECT 系统调用用于取得对另一个目录的访问权；它的参数之一是包含该目录密码的字符串。如果密码错误，该调用在三秒延迟后失败，以防止高速猜测密码。

CONNECT 的实现形式如下：for i := 0 to Length(directoryPassword) do if directoryPassword[i] ≠ passwordArgument[i] then Wait three seconds; return BadPassword end if end loop; connect to directory; return Success

下面这个技巧能在平均 64n 次尝试中找出长度为 n 的密码，而不是 128^n / 2 次（Tenex 字符串使用 7 位字符）。安排 passwordArgument，使它的第一个字符位于某一页的最后一个字符位置，并使下一页未分配，然后尝试每一个可能的第一个字符。如果 CONNECT 报告 BadPassword，则猜错了；如果系统报告对未分配页的引用，则猜对了。接着安排 passwordArgument，使第二个字符位于该页的最后一个字符位置，然后按显然的方法继续。

这个隐蔽而有趣的错误没有被设计者注意到，是因为 Tenex 系统调用提供的接口相当复杂：它包括报告对未分配页引用的可能性。或者换一种说法，系统代码中的普通内存引用指令提供的接口相当复杂：它包括这样一种可能性，即不当引用会被报告给客户，而系统代码没有任何机会先取得控制权。

工程师就是能用一角钱做到 傻瓜用一块钱才能做到的事的人。 (Anonymous)

不过，有时为了一个干净而强大的接口做大量工作，使其实现快速，是值得的。如果该接口被足够广泛地使用，投入到设计和调优实现上的努力可以多次收回。但只有当接口的重要性已经从现有使用中得知时才这样做。而且要确保你知道如何让它快。

例如，用于操纵光栅图像（raster image）的 BitBlt 或 RasterOp 接口 [21]、[37]，是 Dan Ingalls 在对 Alto 的高分辨率交互显示器进行了多年实验之后设计出来的。它的实现所需微码（microcode）大约相当于 Alto 标准指令集（standard instruction set）整个仿真器（emulator），并且需要大量技巧和经验才能构造。但它的性能几乎与此前专用的字符到光栅操作一样好，而它的简单性和通用性使构建显示应用（display application）容易得多。

Dorado 内存系统（memory system） [8] 包含一个缓存（cache），以及一条用于快速输入/输出（input/output）的独立高带宽路径（high-bandwidth path）。它在每个 64 ns 周期中提供一次缓存读或写，同时提供 500 MBits/second 的 I/O 带宽（I/O bandwidth）、来自缓存和 I/O 的虚拟寻址（virtual addressing），并且没有需要微程序员（microprogrammer）操心的特殊情况。然而，它的实现需要 850 个 MSI 芯片，并消耗了数个人年的设计时间。只有凭借关于这个接口的大量先前经验（30 年！），以及知道内存访问通常是性能瓶颈，这才说得过去。即便如此，事后看来，高 I/O 带宽似乎不值得它的成本；它主要用于显示，而双端口帧缓冲区（dual-ported frame buffer）几乎肯定会更好。

最后，为免这个建议显得太容易接受：

• 把它做对。抽象和简单都不能替代“做对”。事实上，抽象可能成为严重困难的来源，如下面这个警示故事所示。文字处理和办公信息系统通常允许在它们处理的文档中嵌入命名字段（named field）。例如，一封套用信函可能有 address 和 salutation 字段。通常文档被表示为字符序列（sequence of characters），字段则用类似 {name: contents} 的形式编码。在其他操作之外，会有一个 FindNamedField 过程，用来寻找给定名称的字段。某个大型商用系统曾有一段时间使用一个运行时间为 O(n 2) 的 FindNamedField 过程，其中 n 是文档长度。这个惊人的结果是这样得到的：先写一个 FindIthField 过程来寻找第 i 个字段（如果没有辅助数据结构（auxiliary data structure），它必然需要 O(n) 时间），然后用非常自然的程序实现 FindNamedField(name)：for i := 0 to numberofFields do FindIthField; if its name is name then exit end loop

一旦提供了选择不当的抽象 FindIthField，只有对其成本保持敏锐意识，才能避免这场灾难。当然，这并不是反对抽象的论据，但意识到抽象的危险是有益的。

2.2 推论

关于简单性和泛化的规则有许多有趣的推论。

衣着应尽财力所能承受而体面， 但不要流于奇装异服；富足而不浮华。

• 让它快，而不是一般或强大。如果它快，客户就可以编程实现自己想要的功能，另一个客户也可以编程实现另一种功能。让基本操作（basic operation）快速执行，远比提供更强大但更慢的操作要好（当然，如果你知道怎么做到，一个又快又强大的操作最好）。缓慢而强大的操作的问题在于，不需要其强大能力的客户也要为基本功能付出更多。通常结果会发现，那个强大的操作并不是正确的操作。

若我还有时间（这严厉的死神 正在严格拘捕我），啊，我本可以告诉你—— 但就这样吧。 (V ii 339)

例如，许多研究（如 [23]、[51]、[52]）表明，程序大部分时间都在做非常简单的事情：加载、存储、相等性测试、加一。像 801 [41] 或 RISC [39] 这样能快速执行这些简单操作的机器，在使用相同硬件量时，可以比 VAX 这类在简单情况下耗时更长、指令更通用更强大的机器更快地运行程序。在实现使用相同硬件量时，程序运行时间很容易损失 2 倍。那些对客户需要什么抱有更宏大想法的机器表现更糟 [18]。

为了找出大型系统中时间花在哪里，需要能够精确指出耗时代码（time-consuming code）的测量工具（measurement tool）。很少有系统能被理解到足以在没有这类工具的情况下正确调优；80% 的时间花在 20% 的代码中是正常的，但先验分析或直觉通常无法可靠地找出那 20%。Interlisp-D 的性能调优（performance tuning）使用一组有效工具 [7]，使其速度提高了 10 倍。

• 不要隐藏能力。这个口号与上一个紧密相关。当较低抽象层（low level of abstraction）允许某件事快速完成时，较高层不应把这种能力埋进更一般的东西里。抽象的目的在于隐藏不良性质；有益性质不应被隐藏。当然，有时抽象是在复用某个资源，这必然有一些成本。但应该能够以很小的性能损失，把全部或几乎全部能力交付给单个客户。

例如，Alto 磁盘硬件（disk hardware） [53] 能以磁盘速度传输一个完整柱面（cylinder）。基本文件系统 [29] 能以满磁盘速度把连续文件页传输到客户内存，并给客户留出在每个扇区（sector）上做一些计算的时间；因此，只要有几个扇区的缓冲，整个磁盘就能以磁盘速度扫描。这个能力已被用于编写各种应用，从重建损坏文件系统的 scavenger，到在文件中搜索匹配模式的子串的程序。文件系统的流层（stream level）可以从客户内存读或向客户内存写 n 个字节；这 n 个字节中占据完整磁盘扇区的部分会以满磁盘速度传输。装载器、编译器、编辑器以及许多其他程序的性能，都依赖这种快速读取大文件的能力。在这一层，客户放弃了在页到达时查看它们的能力；这是为更高抽象层（higher level of abstraction）支付的唯一代价。

• 使用过程参数为接口提供灵活性。如果出于保护或可移植性（portability）的需要，可以用各种方式限制或编码这些参数。这种技术可以极大简化接口，消除一堆实际上构成一种小型编程语言的参数。一个简单例子是枚举过程（enumeration procedure），它返回集合中满足某种性质的所有元素。最干净的接口允许客户传入一个测试该性质的过滤过程（filter procedure），而不是定义一种特殊的模式语言或其他东西。

但这个主题有许多变体。一个更有趣的例子是 Berkeley 940 系统中的 Spy 系统监控设施（system monitoring facility） [10]，它允许不受信任的用户程序在监督程序（supervisor）代码中植入补丁。补丁用机器语言（machine language）编写，但安装补丁的操作会检查它没有任意分支、没有循环、不太长，并且只写入指定的、专用于收集统计信息的内存区域。使用 Spy，系统研究者可以精细调整自己的测量，而不用担心破坏系统，甚至不用担心显著扰动系统运行。

另一个说明这种方法威力的不寻常例子，是 CDC 6400 上 Cal 分时系统中的 FRETURN 机制 [30]。对于任何监督程序调用 C，都可以构造另一个 CF：在正常情况下它与 C 完全一样执行，但如果 C 返回错误，它会把控制转移到指定的失败处理器（failure handler）。CF 操作可以做更多事（例如，它可以把快速但容量有限的存储设备上的文件扩展到较慢设备上的更大文件），但在希望出现的正常情况下，它运行得和 C 一样快。

不过，如果一种专用语言更适合用于优化的静态分析，那么它可能更好。例如，这是数据库查询语言（database query language）设计中的一个主要标准。

• 把事情留给客户。只要来回传递控制很便宜，一个接口就可以通过只解决一个问题、把其余问题留给客户，来同时获得简单性、灵活性和高性能。例如，许多解析器（parser）只负责做上下文无关识别（context-free recognition），并调用客户提供的“语义例程（semantic routine）”来记录解析结果。这显然优于总是构建一棵解析树（parse tree），再让客户遍历它来弄清发生了什么。

监视器（monitor） [20]、[25] 作为同步机制（synchronization device）的成功，部分原因在于它的锁定和信号机制（signaling mechanism）做得很少，把真正的工作都留给监视器过程（monitor procedure）中的客户程序。这简化了监视器实现并使其保持快速；如果客户需要缓冲区分配（buffer allocation）、资源记账（resource accounting）或其他附加功能，它可以自己提供这些功能，或调用其他库设施，并为自己需要的东西付费。人们常常把监视器不能控制等待监视器锁或条件变量（condition variable）的进程调度视为缺点；其实这是一项优点，因为它让客户可以自由提供自己需要的调度（例如为每一类进程使用单独的条件变量），而不必为某种内建机制付费或与其对抗，而这种内建机制很可能做不对。

Unix 系统 [44] 鼓励构建小程序：它们以一个或多个字符流（character stream）为输入，产生一个或多个字符流为输出，并完成一个操作。当这种风格被正确模仿时，每个程序都有简单接口，并且把一件事做好，让客户把一组这样的程序与自己的代码组合起来，精确实现期望效果。

第 3 节讨论的端到端口号，是保持简单的另一个推论。

2.3 连续性（continuity）

改进设计的愿望与稳定性（stability）或连续性的需要之间，始终存在张力。

• 保持基本接口稳定。由于接口体现了系统中多个部分共享的假设，有时甚至是许多部分共享的假设，因此非常希望不要改变接口。当系统使用没有类型检查（type-checking）的语言编写时，改变任何公共接口（public interface）几乎不可想象，因为无法追踪它的客户，也无法检查基本不兼容，例如参数个数（number of arguments）不一致，或把指针和整数混淆。像 Mesa [15] 这样具有完整类型检查并有语言级接口支持（language support for interfaces）的语言，使改变接口而不导致系统崩溃容易得多。但即使类型检查通常可以检测到某个假设不再成立，程序员仍然必须修正这个假设。当系统增长到超过 250K 行代码时，变化量会变得无法忍受；即使毫无疑问知道必须做什么，也要花太久才能完成。别无选择，只能把系统拆成更小的片段，而这些片段之间只通过多年稳定的接口相互关联。传统上，只有编程语言或操作系统内核定义的接口才会如此稳定。

• 如果必须改变接口，要保留一个立足点。下面用两个相当不同的例子说明这个思想。一个是兼容包（compatibility package），它在新系统之上实现旧接口（old interface）。这允许依赖旧接口的程序继续工作。许多新操作系统（包括 Tenex [2] 和 Cal [50]）通过模拟旧系统（分别是 TOPS-10 和 Scope）的监督程序调用，让旧软件（old software）继续可用。通常，与重新实现旧软件的成本相比，这些模拟器（simulator）只需要很少努力，而且不难获得可接受的性能。在不同层次上，IBM 360/370 系统提供了对 1401 和 7090 等旧机器指令集（instruction set）的仿真（emulation）。再往前一步，这就导向虚拟机（virtual machine），即在机器自身上模拟（若干份）机器 [9]。

另一个相当不同的例子是 world-swap 调试器（debugger）。它的工作方式是把目标系统（正在被调试的系统）的真实内存写到二级存储（secondary storage）设备上，并把调试系统读入其位置。然后调试器向用户提供对目标世界的完整访问，把每个目标内存地址（target memory address）映射到二级存储上的正确位置。小心处理的话，可以把目标系统（target system）换回并继续执行。这有些笨拙，但它允许方便地调试系统的很低层，因为调试器不依赖目标系统中任何东西的正确运行，只依赖非常简单的 world-swap 机制。它在自举（bootstrapping）期间尤其有用。还有许多变体。例如，调试器可以运行在另一台机器上，目标世界中只有一个小的“远程调试（tele-debugging）”小桩，解释通过网络从调试器发来的 ReadWord、WriteWord、Stop 和 Go 命令。或者，如果目标是分时系统中的一个进程，调试器可以运行在另一个进程中。

2.4 让实现可行

完美必须逐步达到；她需要时间缓慢的手。 (Voltaire)

• 准备扔掉一个版本；反正你会这样做 [6]。如果系统功能中有任何新东西，那么第一个实现都必须彻底重做，才能得到满意的结果，也就是可接受地小、快且可维护（maintainable）。如果一开始就计划做原型（prototype），成本会低得多。不幸的是，有时需要两个原型，特别是在创新很多的时候。如果幸运，你可以从先前系统中复制很多东西；例如 Tenex 基于 SDS 940 [2]。即使先前系统过于宏大，这也可能奏效；Unix 就从 Multics [44] 中借鉴了许多思想。

即使某个实现已经成功，随着系统演化重新审视旧决策也是值得的；特别是，针对负载或环境某些特性（例如内存大小）的优化，常常会变得远非最优。

不要把你的思想轻易说出口， 也不要让不成熟的想法付诸行动。

• 保守实现的秘密（secrets of the implementation）。秘密是客户程序不被允许对某个实现作出的假设（转述自 [5]）。换句话说，它们是可以改变的东西；接口定义的是不能改变的东西（除非实现和客户同时改变）。显然，如果系统各部分对彼此作出的假设更少，编写和修改系统就更容易。另一方面，系统未必更容易设计，因为设计好接口很难。而且这也与不要隐藏能力的愿望存在张力。

高效程序是在逻辑边缘上的练习。 (E. Dijkstra)

保守秘密还有另一个危险。改进性能的一种方法，是增加系统某一部分对另一部分作出的假设数量；额外假设常常允许少做工作，有时少得很多。例如，如果已知大小为 n 的集合已经排序，成员测试需要 log n 时间，而不是 n。这个技术在算法设计（algorithm design）和小模块调优中非常重要。在大型系统中，分别改进每个部分的能力通常更重要。找到正确平衡仍然是一门艺术。

啊，抛弃它较坏的一半， 与较纯的一半一起生活。 (III iv 157)

• 分而治之。这是解决难题的著名方法：把难题化为几个更容易的问题。得到的程序通常是递归的。当资源受限时，这个方法呈现出稍有不同的形式：先咬下能容纳的那一块，把其余留到下一轮迭代。

Alto 的 Scavenger 程序提供了一个好例子。它扫描磁盘，并根据每个磁盘扇区上记录的文件标识符（file identifier）和页号（page number），重建文件系统的索引和目录结构（directory structure） [29]。该程序最近一次重写中有一个阶段，会在主存（main storage）中构建一个数据结构：磁盘页中每个连续区间（contiguous run），只要同时也是某个文件中连续页集合，就对应一个条目。通常文件大致连续分配，所以这个结构不会太大。但如果磁盘严重碎片化（fragmentation），该结构就无法装入内存。这时，Scavenger 会丢弃一半文件的信息，并继续处理另一半。重建这些文件的索引后，再对另一半文件重复此过程。如有必要，工作还会进一步细分；只有当单个文件的索引都无法装入内存时，该方法才会失败。

另一个有趣例子来自 Dover 光栅打印机（raster printer） [26]、[53]。它把字符和矩形列表扫描转换（scan-convert）成一个大的 m × n 位数组（array of bits），其中 1 对应纸上的墨点，0 对应无墨点。在这台打印机中，m=3300，n=4200，因此数组包含一千四百万位，太大而无法存入内存。打印机消耗位的速度快于可用磁盘交付位的速度，所以数组也不能存到磁盘上。取而代之，整个数组被划分为 16 × 4200 位的切片（band），称为 bands；打印机电子部件包含两个单 band 缓冲区。字符和矩形被分拣到桶中，每个 band 一个桶；对象从哪个 band 开始，就进入对应的桶。扫描转换通过如下方式进行：从一个桶填充一个 band 缓冲区，然后把它输出到打印机并清零，同时从下一个桶填充另一个缓冲区。跨过一个 band 边界的对象会被加入下一个桶；正是这个技巧使问题可以被细分。

有时人为限制资源会很方便，方法是把资源量化为固定大小的单位；这会简化记账，并防止一种碎片化。经典例子是虚拟内存使用固定大小的页，而不是可变大小的段。尽管把逻辑相关的信息放在一起，并作为一个单位在主存和后备存储（backing storage）之间传输，看起来有明显优点，但分页系统最终效果更好。原因很复杂，而且尚未被系统研究。

这使我们宁愿忍受已有的苦难， 也不愿飞向未知的苦难。 (III i 81)

• 再次使用一个好想法，而不是把它泛化。这个想法的专用实现可能比通用实现有效得多。下面关于缓存的讨论给出了若干应用这一一般原则的例子。另一个有趣例子是数据复制（data replication）这一概念。少量数据很容易通过写到两个或更多磁盘驱动器上来本地复制 [28]。当数据量很大，或数据必须记录在不同机器上时，确保各副本始终相同就不容易。Gifford [16] 展示了如何在事务性存储（transactional storage）系统之上构建复制数据来解决这个问题；事务性存储允许任意大的更新作为原子操作（atomic operation）完成（见第 4 节）。事务性存储本身依赖简单的本地复制方案来可靠存储其日志（log）。这里没有循环依赖，因为重复使用的是想法，而不是代码。在这个语境中第三种使用复制的方式，是把提交记录（commit record）存储在多台机器上 [27]。

Star 办公系统的用户接口（user interface） [47] 有一小组操作（输入文本、移动、复制、删除、显示属性），它们适用于系统中几乎所有对象：文本、图形、文件夹和文件柜、记录文件、打印机、收件篮和发件篮等。某个操作的确切含义随对象类别而变化，但限制在用户可能觉得自然的范围内。例如，把文档复制到发件篮会使它作为消息发送；移动一条线的端点会使这条线像橡皮筋一样跟随。当然，在许多情况下实现相当不同。但这些通用操作并不只是让系统更容易使用；它们代表了一种关于哪些操作是可能的，以及每类对象的实现应如何组织的观点。

2.5 处理所有情况

危急的病症， 需要危急的疗法来缓解， 否则全无办法。 (III vii 9)

因此这个计划 应有后援或第二方案支撑， 若它经不起检验。 (IV iii 151)

• 通常要分别处理正常情况和最坏情况，因为二者的要求很不相同：

正常情况必须快。

最坏情况必须有所进展。

在大多数系统中，只要事件能被自动检测到，并且不太经常发生，不公平调度而不给某些进程服务，甚至让整个系统死锁，都是可以接受的。通常的恢复方式是使某些进程崩溃，甚至使整个系统崩溃。乍听之下这很糟糕，但为了 20% 的性能提升，每周一次崩溃通常是很便宜的代价。当然，系统必须有体面的错误恢复（端到端原则的一个应用；见第 4 节），但无论如何这都是必需的，因为崩溃还有许多其他可能原因。

缓存和线索（第 3 节）是对正常情况特殊处理的例子，但还有许多其他例子。Interlisp-D 和 Cedar 编程系统使用一种引用计数垃圾收集器（reference-counting garbage collector） [11]，其中有一个重要的此类优化。过程的局部帧（local frame）或活动记录（activation record）中的指针不计数；相反，在每次垃圾收集（garbage collection）时扫描这些帧。这节省了大量引用计数，因为多数指针赋值都是给局部变量（local variable）。帧数量并不多，所以扫描它们的时间很小，收集器几乎是实时（real-time）的。Cedar 更进一步，不跟踪哪些局部变量包含指针；相反，它假设全部都包含指针。这意味着，如果一个整数恰好包含某个不再被引用对象的地址，它会阻止该对象被释放。测量显示，被错误保留的存储不到 1% [45]。

引用计数使增量式收集器（incremental collector）容易实现，因此计算不必在收集期间停止。不过，它不能回收不再可达的循环结构（circular structure）。因此 Cedar 还配有一个传统的追踪并清扫收集器（trace-and-sweep collector）。它不适合实时应用，因为它会让整个系统停止许多秒；但在交互式应用（interactive application）中，可以在咖啡休息时用它回收累积的循环结构。

引用计数的另一个问题是，计数可能溢出为它提供的空间。这很少发生，因为只有少数对象有超过两三个引用。让最大值粘住很简单。不幸的是，在某些应用中，一个大型结构的根会被许多地方引用；如果根变成粘住状态，许多存储会意外地变为永久。一个有吸引力的解决方案是设置一个“溢出计数（overflow count）”表，它是以对象地址为键的哈希表（hash table）。当计数达到上限时，将其减半，溢出计数加一，并在对象中设置溢出标志（overflow flag）。当计数到达零时，如果溢出标志已设置，就反向执行这个过程。这样，即使只有 4 位，也有空间计数到 7，且只有在计数摆动超过 4 的少见情况下才会访问溢出表。

在许多情况下，资源会被动态分配（dynamically allocated）和释放（例如分页系统中的真实内存），而释放一个项目有时还临时需要额外资源（可能必须换入某个表，才能知道把一个页写到哪里）。通常会有一个缓冲垫（干净页（clean page），无需工作即可释放），但在最坏情况下缓冲垫可能消失（所有页都是脏的）。这里的技巧是在床垫下保留一点东西，只在危机时拿出来。必须界定释放一个项目所需的资源上限；这决定了床垫下保留量的大小，而它必须被视为资源复用（resource multiplexing）的固定成本。危机到来时，一次只应释放一个项目，使整个保留量都用于这项工作；这可能会大大降低速度，但能确保取得进展。

有时，正常情况和最坏情况适合采用截然不同的策略。Bravo 编辑器 [24] 使用“片段表（piece table）”表示正在编辑的文档。片段表是一个片段数组，片段是指向文件中字符字符串的指针；每个片段包含字符串首字符的文件地址（file address）和长度。在正常编辑期间，字符串从不被修改。相反，当删除一些字符时，包含被删除字符的片段会被分成两个片段，分别指向第一个未删除字符串和第二个未删除字符串。从键盘插入的字符会追加到文件中，包含插入点（insertion point）的片段会被分成三个片段：一个用于前面的字符，第二个用于插入的字符，第三个用于后面的字符。编辑数小时之后，会有数百个片段，事情开始变慢。这时就该清理了：写出一个包含文档所有字符且顺序正确的新文件。现在片段表可以由指向新文件的单个片段替换，编辑可以继续。清理是一种专门的垃圾收集。它可以在后台完成，使用户不必停止编辑（尽管 Bravo 没有这样做）。

3. 速度

本节描述让系统更快的提示，不再进一步讨论为什么这很重要。Bentley 的优秀著作 [55] 对其中一些想法有更多说明，并给出了许多其他想法。

既不要借钱，也不要放债； 因为借贷常常既失钱又失友， 而借钱会钝化节俭的锋芒。

• 如果犹豫，就固定划分资源（split resources in a fixed way），而不是共享它们。分配专用资源（dedicated resources）通常更快，访问它们也常常更快，分配器（allocator）的行为也更可预测。显而易见的缺点是，如果忽略复用开销（multiplexing overhead），所需总资源会比来自一个公共池（common pool）时更多。然而在许多情况下，额外资源的成本很小，或者开销大于碎片化，或者二者兼有。

例如，访问信息时，从处理器寄存器取总是比从内存取快，即使机器有高性能缓存（high-performance cache）。寄存器名声不好，是因为智能分配它们可能很棘手，也因为在过程调用（procedure call）之间保存和恢复它们可能抵消其速度优势。但当程序按认可的现代风格编写，包含许多小过程时，16 个寄存器几乎总是足够容纳所有局部变量和临时变量（temporary variable），因此分配不是问题。如果有 n 组寄存器按栈排列，只有在连续 n 次调用而没有返回时才需要保存 [14]、[39]。

输入/输出通道（input/output channel）、浮点协处理器（floating-point coprocessor）以及类似的专用计算设备（specialized computing device），是这一原则的其他应用。当额外硬件昂贵时，这些服务通过复用单个处理器提供；但当硬件便宜时，为各种用途静态分配计算能力（computing power）是值得的。

前面提到的 Interlisp 虚拟内存系统 [7] 需要跟踪每个虚拟地址（virtual address）对应的磁盘地址（disk address）。这些信息本身可以保存在虚拟内存中（许多系统，包括 Pilot [42]，就是这样做的），但避免循环依赖会使这变得相当复杂。相反，该系统把真实内存专用于这个目的。除非磁盘碎片化得荒谬，否则这样消耗的空间少于防止循环依赖所需代码占用的空间。

• 如果可以，使用静态分析；这是上一个口号的推广。静态分析发现程序的性质，而这些性质通常可用于改进性能。关键是“如果可以”：当好的静态分析不可能时，不要用糟糕的静态分析自欺欺人，而应退回到动态方案（dynamic scheme）。

上面关于寄存器的说法依赖这样一个事实：编译器可以很容易决定如何分配它们，只要把局部变量和临时变量放在那里即可。多数机器缺少多组寄存器，或缺少高效堆叠它们的方法。这时好的分配就困难得多，需要复杂的跨过程分析（inter-procedural analysis），而这种分析可能不会成功，并且无论如何每次程序变化后都必须重做。因此，一点动态分析（堆叠寄存器）能起很大作用。当然，如果编译器足够聪明，静态分析在大过程中仍然能带来回报。

程序顺序读取（sequential read）数据时，可以快得多。这使预测下一步需要哪些数据并提前读入缓冲区变得容易。通常，数据也可以在磁盘上顺序分配，从而至少快一个数量级地传输。这些性能收益依赖于程序员已经安排数据，使其按某种可预测模式被访问，也就是使静态分析成为可能。人们曾多次尝试在事后分析程序并优化磁盘传输，但据我所知，这从未成功。按需分页（demand paging）所做的动态分析总是至少同样好。

某些静态分析利用了某个不变式（invariant）被维持这一事实。依赖这些事实的系统，在面对会破坏不变式的硬件故障（hardware failure）或软件错误（software bug）时，可能不那么健壮。

• 从方便的表示（紧凑、易修改或易显示）动态翻译为可快速解释的表示，是编译这一老思想的一个重要变体。一次翻译一小部分，是分离编译（separate compilation）背后的思想，至少可以追溯到 Fortran 2。增量编译器（incremental compiler）在语句、过程或其他东西发生变化时自动这样做。Mitchell 研究了在方便表示（convenient representation）和快速表示（fast representation）之间的连续体上平滑移动 [34]。他的方案的一个简化版本是始终按需翻译（translation on demand）并缓存结果；这样只需要一个解释器，除了缓存替换（cache replacement）之外不需要任何决策。

例如，一个实验性 Smalltalk 实现 [12] 使用标准 Smalltalk 编译器产生的字节码（bytecode）作为方便表示（在此情况下是紧凑表示），并在某个过程被调用时，把单个过程从字节码翻译为机器语言。它保留一个可容纳数千条翻译后指令的缓存。要使该方案划算，缓存必须足够大，使得平均而言一个过程至少执行 n 次，其中 n 是翻译时间与未翻译代码执行时间之比。

C-machine 栈缓存（stack cache） [14] 提供了一个相当不同的例子。在这个设备中，指令被取入指令缓存（instruction cache）；当它们被装入时，任何相对于局部帧指针（local frame pointer） FP 的操作数（operand）地址，都会使用 FP 的当前值（在过程执行期间保持不变）转换成绝对地址（absolute address）。此外，如果得到的地址位于当前栈数据缓存的地址范围内，操作数会被改为寄存器模式（register mode）；稍后执行该指令时，就会直接访问数据缓存中的寄存器。FP 值与指令地址拼接起来，形成缓存中翻译后指令的键，因此同一过程的多次激活仍然可以工作。

如果你曾把我放在心上。 (V ii 349)

• 缓存昂贵计算的答案，而不是重复计算。通过在关联存储（associative store）中保存三元组 [f, x, f(x)]，以 f 和 x 为键，我们可以通过查找取回 f(x)。如果 f(x) 在被替换出缓存之前会再次需要，这就更快。快多少取决于计算 f(x) 有多昂贵。一个严重问题是，当 f 不是函数式（functional）的，也就是同一参数可能给出不同结果时，如果 f(x) 的值变化，我们需要一种方式使缓存项（cache entry）失效（invalidate）或更新它。更新依赖形如 f(x + ∆) = g(x, ∆, f(x)) 的等式，其中 g 的计算比 f 便宜得多。例如，x 可以是 1000 个数的数组，f 是数组元素之和，∆ 是其中一个元素的新值，即一对 [i, v]。那么 g(x, [i, v], sum) 就是 sum - xi + v。

如果缓存太小，装不下所有“活跃”值，就会抖动（thrashing）；如果重新计算 f 很昂贵，性能会严重受损。因此，明智的做法是自适应地选择缓存大小：当命中率（hit rate）下降时增大缓存，当许多条目长期未使用时缩小缓存。

缓存的经典例子是加速主存访问的硬件；它的条目是三元组 [Fetch, address, contents of address]。Fetch 操作当然不是函数式的：在执行 Store(x) 之后，Fetch(x) 会给出不同答案。因此，存储之后必须更新或使缓存失效。虚拟内存系统做的正是同一件事；主存扮演缓存角色，磁盘扮演主存角色，传输单位是页、段或其他东西。

但几乎每个非平凡系统都有更专门的缓存应用。对于交互式或实时系统（real-time system）尤其如此，因为基本问题是响应频繁的小变化，增量更新（incremental update）一个复杂状态。用临时拼凑的方式做这件事极易出错。最好的组织原则是在每次变化后重新计算整个状态，但缓存这次计算中所有昂贵的结果。一次变化必须至少使它所使无效的缓存项失效；如果这些项太难精确识别，可以让更多条目失效，代价是需要更多计算来重新建立它们。成功的秘诀是组织缓存，使小变化只使少数条目失效。

例如，Bravo 编辑器 [24] 有一个函数 DisplayLine(document, firstChar)，返回显示文档中以 document[firstChar] 作为首字符的那一行文本的位图（bitmap）。它还返回 lastChar 和 lastCharUsed，即该行显示的最后一个字符编号，以及计算位图时检查过的最后一个字符编号（二者通常不同，因为必须向行末之后看一段，以便选择断行（line break）位置）。这个函数计算断行、做两端对齐（justification）、使用字体表（font table）把字符映射到其光栅图像（raster picture），等等。缓存中为屏幕上当前显示的每一行保存一个条目，有时还保存上方或下方几行。若一次编辑改变了字符 i 到 j，则任何 [firstChar .. lastCharUsed] 与 [i .. j] 相交的缓存条目都失效。显示通过以下循环重新计算：loop (bitMap, lastChar, ) := DisplayLine(document, firstChar); Paint(bitMap); firstChar := lastChar + 1 end loop

如果 [document, firstChar] 的缓存条目存在，就用它短路调用 DisplayLine。最后，任何没有被使用的缓存条目都会被丢弃；这些条目并非无效，但它们不再有意义，因为断行已经改变，使某一行不再从这些位置开始。

同一思想可用于非常不同的场景。Bravo 允许文档被组织成段落，每个段落有指定的左右边距、行间距等。在普通页面布局中，完成布局所需的关于段落的全部信息可以非常紧凑地表示：行数、每行高度（通常所有行高度相同）、任何保持属性、前后间距。

在通常情况下，这可以编码为三四个字节。一个 30 页的章节也许有 300 个段落，因此所有这些数据约需 1k 字节；这比指定一页上的字符所需信息还少。由于布局计算与一页的行布局计算相当，因此应该可以在少于渲染一页所需的时间内完成该章节的分页。每个章节可以独立布局。

使这个想法奏效的是一个 [paragraph, ParagraphShape(paragraph)] 条目的缓存。如果段落被编辑，缓存条目无效，必须重新计算。这可以在编辑时完成（如果段落在屏幕上，这通常是合理的；但对全局替换不太好）、在后台完成，或只在请求重新分页（repagination）时完成。

因为衣着常常宣示人的身份。

• 使用线索来加速正常执行。线索与缓存项一样，是某些计算结果的保存。它有两点不同：它可能是错的，并且不一定通过关联查找到达。因为线索可能是错的，所以在采取任何不可恢复动作之前，必须有一种方法检查它的正确性。它要与“真相（truth）”核对；真相是必须正确的信息，但可以为此目的优化，而不是为高效执行优化。与缓存项一样，线索的目的是让系统运行得更快。通常这意味着它几乎必须总是正确。

例如，在 Alto [29] 和 Pilot [42] 操作系统中，每个文件都有唯一标识符（unique identifier），每个磁盘页都有一个“标签”字段，其内容可以在读写数据前检查，而不会减慢数据传输。标签包含拥有该页的文件的标识符，以及该页在文件中的页号。每个文件的第 0 页称为“leader page”，其中除其他内容外，还包含文件所在目录，以及它在该目录中的字符串名称。这就是文件系统所依据的真相，它们非常努力地保持它正确。

然而，仅有这些信息，就无法从目录中的名称找到文件标识符，也无法找到第 i 页的磁盘地址，除非搜索整个磁盘；这种方法可行，但慢到不可接受。因此，每个系统都维护线索来加速这些操作。两个系统都把目录表示为一个包含三元组 [string name, file identifier, address of first page] 的文件。每个文件都有一个数据结构，把页号映射到页的磁盘地址。Alto 在每个标签中使用一个指向下一个标签的链接；这使从第 n 页到第 n + 1 页很快。Pilot 使用 B 树（B-tree）直接实现映射，并利用连续文件页通常占据连续磁盘页这一常见情况。从任何这些线索获得的信息在使用时都会被检查，方法是检查标签，或从 leader page 读取文件名。如果证明它是错的，所有这些信息都可以通过扫描磁盘重建。同样，跟踪空闲磁盘页的位表（bit table）也是线索；真相由空闲页（free page）标签中的一个特殊值表示，在分配该页时，以及在用文件标识符和页号覆盖标签之前，会检查这个值。

线索的另一个例子是最早在 Arpanet [32] 中使用的存储转发路由（store and forward routing）。网络中的每个节点（node）都保存一张表，给出到其他每个节点的最佳路由。这个表通过周期性广播（periodic broadcast）更新；在广播中，每个节点向所有其他节点宣布它对自己到邻居链路质量（link quality）的看法。由于这些广播消息不同步，也不保证送达，节点在任一瞬间可能没有一致视图。在这种情况下，真相是每个节点知道自己的身份，因此知道自己何时收到发给自己的包。至于其他事情，路由尽力而为；当情况变化不太快时，它几乎是最优的。

一个更奇特的例子是 Ethernet [33]，其中电缆上没有载波信号（carrier signal）被用作一个线索，表示可以发送包（packet）。如果两个发送者同时接受这个线索，就会发生冲突（collision），双方都能检测到；二者都停止，延迟一个随机选择的时间间隔，然后重试。如果连续发生 n 次冲突，这被作为发送者数量为 2 n 的线索，每个发送者把其随机延迟（random delay）间隔的均值设为初始值的 2 n 倍。这种“指数退避（exponential backoff）”确保网络不会过载（overload）。

线索的一个非常不同的应用，是加速 Smalltalk 程序执行 [12]。在 Smalltalk 中，调用过程时执行的代码由第一个参数的类型动态决定。因此 Print(x, format) 调用的是 x 的类型中包含的 Print 过程。由于 Smalltalk 没有声明，x 的类型无法静态得知。相反，每个对象都有一个指针，指向由 [procedure name, address of code] 对组成的表；当执行这个调用时，会在 x 的表中查找 Print（我规范化了 Smalltalk 中不寻常的术语和语法，并稍作简化）。这很昂贵。事实证明，x 的类型通常与上一次相同。因此，调用 Print(x, format) 的代码可以这样安排：push format; push x; push lastType; call lastProc

每个 Print 过程开始时执行：lastT := Pop(); x := Pop(); t := type of x; if t ≠ lastT then LookupAndCall(x, “Print”) else the body of the procedure end if.

这里 lastType 和 lastProc 是存储在代码中的立即值（immediate value）。思想是 LookupAndCall 应该把它找到的 x 的类型和代码地址（address of code）写回 lastType 和 lastProc 字段。如果下一次类型相同，就直接调用该过程。测量显示，该缓存命中约 96% 的时间。在带有指令取指单元（instruction fetch unit）的机器上，这个方案有个很好的性质：转移到 lastProc 可以全速进行；因此当线索正确时，调用与普通子程序调用（subroutine call）一样快。t ≠ lastT 的检查可以安排成通常不发生分支。

同一思想以不同形式用于 S-1 [48]，它在指令缓存中为每条指令设置一个额外位。指令被装入时清除此位；当指令导致分支被采用时设置此位；并使用它选择指令取指单元走哪条路径。如果预测错误，就改变该位并走另一条路径。

• 犹豫时，使用蛮力。尤其是随着硬件成本下降，一个直接、容易分析、需要大量专用计算周期的解决方案，优于一个复杂、特性不清、只有在某些假设满足时才可能运行良好的解决方案。例如，Ken Thompson 的国际象棋机器 Belle 主要依赖专用硬件来生成走法和评估局面，而不是依赖复杂的国际象棋策略。Belle 已多次赢得世界计算机象棋锦标赛。另一个有启发性的例子是个人计算机相对于分时系统的成功；后者包含更多聪明技巧，浪费的周期也少得多，但前者越来越被认为是进行交互式计算最具成本效益的方式。

即使渐近更快的算法也不一定更好。有一种算法能比 O(n^2.5) 更快地乘两个 n × n 矩阵，但常数因子（constant factor）高得令人无法接受。更普通一点的例子是，7040 Watfor 编译器使用线性搜索（linear search）查找符号；学生程序中的符号太少，以至于更好算法的准备时间无法收回。

• 可能时在后台计算。在交互式或实时系统中，响应请求之前应尽量少做工作。原因有二：第一，快速响应对用户更好；第二，负载通常变化很大，因此稍后很可能有空闲处理器时间可用于后台工作（background work）。许多工作都可以推迟到后台。Interlisp 和 Cedar 垃圾收集器 [7]、[11] 几乎所有工作都这样做。许多分页系统在后台写出脏页（dirty page）并准备替换候选页。电子邮件可以由后台进程（background process）投递和取回，因为一两个小时内投递通常可以接受。许多银行系统在夜间合并账户数据，并在第二天早晨准备好。这四个例子中，前台任务（foreground task）和后台任务（background task）之间对同步的需要依次减少。随着同步量增加，需要更小心以避免微妙错误；一个极端例子是 [13] 中给出的并发垃圾收集算法。但在大多数情况下，两个除此之外相互独立的进程之间，可以形成简单的生产者-消费者关系（producer-consumer relationship）。

• 如果可能，使用批处理。增量地做事情几乎总是成本更高，即使不考虑磁盘和磁带在顺序访问（sequential access）时工作得好得多这一事实。此外，批处理允许更简单的错误恢复（error recovery）。Bank of America 有一个交互式系统（interactive system），允许柜员记录存款和支票取款。它在早晨装入当前账户余额，并在白天尽力维护这些余额。但第二天清晨，在线数据（on-line data）会被丢弃，并替换为夜间批处理（night batch run）运行的结果。这种设计使银行更容易满足对可信长期数据（long-term data）的要求，而且功能上没有显著损失。

那就小心些；最好的安全在于恐惧。 (I iii 43)

• 安全第一。在分配资源时，努力避免灾难，而不是追求最优。多年在虚拟内存、网络、磁盘分配、数据库布局（database layout）以及其他资源分配（resource allocation）问题上的经验表明，通用系统（general-purpose system）无法优化资源使用。另一方面，使系统过载并大幅降低服务质量（service quality）却很容易。除非负载可以被极好地刻画，否则如果任何资源的需求超过容量的三分之二，就不能期望系统良好运行。幸运的是，硬件很便宜，而且越来越便宜；我们负担得起提供多余容量。内存尤其便宜，这尤其幸运，因为在某种程度上，大量内存可以使处理器周期或通信带宽（communication bandwidth）等其他资源被更充分地利用。

第一个分页系统让人深刻认识到优化的可悲真相。在那些日子里，内存非常昂贵，人们幻想通过聪明地优化换入换出（swapping），从每个字节中榨出最大价值：把相关过程放在同一页上，根据先前引用预测下一批要引用的页，把共享数据或代码的作业一起运行，等等。没人真正学会如何做到这一点。相反，内存变便宜了，系统花内存来提供足够缓冲，使简单的按需分页可行。我们学到，唯一重要的是避免抖动，或者说避免对可用内存的需求过大。发生抖动的系统会把所有时间花在等待磁盘上。

只有负载非常清楚的系统中，聪明技巧才有效。例如，360/50 APL 系统 [4] 为每个用户提供相同大小的工作区，并让所有用户共享公共系统代码。它使所有系统代码常驻，为每个用户分配一块连续磁盘区域，并把每个计算单位与一次换出和一次换入重叠起来。这效果很好。

Alto 最好的一点是，它不会在夜里跑得更快。 (J. Morris)

处理器时间方面也学到了类似教训。在交互式使用中，对计算请求的响应时间很重要，因为有人在等待。人们曾多次尝试根据计算的优先级、工作集（working set）大小、内存负载、历史记录、I/O 请求可能性等调优处理器调度（processor scheduling）。这些努力失败了。只有最粗糙的参数会产生可理解的效果：交互式与非交互式计算（non-interactive computation），或高优先级、前台优先级（foreground priority）和后台优先级（background priority）。最成功的方案给每个作业固定份额的周期，并且不分配超过 100%；未用周期被浪费掉，或者运气好时被后台作业消耗。这一策略的自然延伸是个人计算机，其中每个用户至少有一个属于自己的处理器。

把耳朵给每个人，声音却少给几个人； 听取每个人的批评，但保留自己的判断。

• 削减负载以控制需求，而不是允许系统过载。这是前一条规则的推论。削减负载有许多方式。交互式系统可以拒绝新用户，甚至拒绝为现有用户服务。内存管理器（memory manager）可以限制被服务的作业，使它们的工作集都能装入可用内存。网络可以丢弃包。如果情况糟到极点，系统可以崩溃并更谨慎地重新开始。

Bob Morris 曾建议，共享交互式系统（shared interactive system）应在每个终端上设置一个大红按钮。如果用户对服务不满意，就按下按钮；系统必须要么改善服务，要么把该用户踢出去；它在足够长的时期内作出公平选择。这个想法是防止人们在不能提供有用服务量的终端前浪费时间。

Arpanet [32] 的原始规范是：网络接受的包保证会被递送，除非接收机器宕机，或某个网络节点在持有该包时失败。事实证明这是个坏主意。这个规则使最坏情况下避免死锁非常困难，而试图遵守它会导致许多复杂性和低效率，即使在正常情况下也是如此。此外，客户并不能受益，因为它仍然必须处理由主机或网络故障造成的包丢失（lost packet，见第 4 节的端到端）。最终该规则被放弃。Pup 互联网 [3] 面对一组变化更大的传输设施（transport facility），从一开始就在出现拥塞（congestion）迹象时无情地丢弃包。

4. 容错性

可靠性（reliability）不可避免的代价是简单性。 (C. Hoare)

如果你知道如何着手，让系统可靠并不真的困难。但给已有设计补装可靠性非常困难。

最重要的是：对你自己忠实； 那么必然如黑夜跟随白昼一样， 你就不会对任何人虚假。

• 端到端。应用层（application level）的错误恢复对于可靠系统绝对必要，而任何其他错误检测（error detection）或恢复在逻辑上并非必要，只是严格用于性能。这一观察最早由 Saltzer [46] 提出，并且适用范围非常广。

例如，考虑把一个文件从连接到机器 A 的磁盘上的文件系统，传输到连接到机器 B 的另一块磁盘上的另一个文件系统。要确信正确的位真的在 B 的磁盘上，你必须从 B 的磁盘读出该文件，计算一个合理长度（比如 64 位）的校验和（checksum），并发现它等于 A 磁盘上那些位的校验和。检查从 A 的磁盘到 A 的内存、从 A 经网络到 B、或从 B 的内存到 B 的磁盘的传输都不充分，因为其他地方可能出问题，位可能在内存中停留时被破坏，或者发生别的事情。这些其他检查也不是必要的，因为如果端到端检查失败，整个传输可以重复。当然，这需要大量工作；如果错误频繁，中间检查（intermediate check）可以减少必须重复的工作量。但这严格说是性能问题，与文件传输（file transfer）的可靠性无关。事实上，在 Cambridge 的环形系统中，通常复制一整包 58 MBytes 的磁盘时只做端到端检查；错误如此罕见，以至于 20 分钟的工作很少需要重复 [36]。

线索的许多用途都是这个思想的应用。例如，在前面描述的 Alto 文件系统中，在写扇区前检查磁盘扇区标签，可以确保写入的磁盘地址正确。采取任何措施让地址更可能正确，可能对性能很重要，甚至至关重要，但它们不影响文件系统的可靠性。

Pup 互联网 [4] 在几个层次上采用端到端策略。网络提供的主要服务是把数据包从源传输到目的地。包可能穿过若干网络，而这些网络的错误率（error rate）和其他性质差异很大。存储并转发包的互联网节点可能耗尽空间并被迫丢弃包。可用的只是对包最佳路由的粗略估计，而当网络部分失败或恢复运行时，这些估计可能大错特错。面对这些不确定性，Pup 互联网通过只尝试“尽力而为”投递，以简单实现提供良好服务。包可能无通知地丢失，也可能在传输中损坏。客户必须提供自己的错误控制（error control）来处理这些问题；事实上，更高层的 Pup 协议确实提供了更复杂的服务，例如可靠字节流（byte stream）。不过，包传输确实试图向客户报告问题，方法是提供适度的错误控制（16 位校验和）、在可能时通知发送者包被丢弃等。这些服务意在面对不可靠通信和过载时改进性能；由于它们本身也是尽力而为，因此不会使实现复杂太多。

端到端策略有两个问题。第一，它要求有便宜的成功测试。第二，它可能导致能工作的系统带有严重性能缺陷，而这些缺陷可能要到系统投入运行并处于重负载时才会显现。

记得你？是的，我要从记忆的板上抹去 所有琐碎而愚蠢的记录，所有书本的格言， 所有过去的形式和印痕， 那些年轻和观察曾复制在那里； 只让你的命令独自存活在我大脑的书卷之中， 不与低贱之物混杂。 (I v 97)

• 记录更新日志，以记录对象状态的真相。日志是一种非常简单的数据结构，可以可靠地写入和读取，并能廉价地强制写到磁盘或其他能在崩溃后幸存的稳定存储（stable storage）上。由于它只追加，写入量被最小化，并且相当容易确保无论何时发生崩溃，日志都是有效的。复制日志、把副本写到磁带上或做其他类似事情也容易且便宜。多年来，日志一直用于确保数据库中的信息不丢失 [17]，但这个想法非常一般，也可用于普通文件系统 [35]、[49] 和许多其他不那么明显的场景。当日志保存真相时，对象的当前状态很像一个线索（它并不完全是线索，因为没有便宜方式检查其正确性）。

使用这个技术时，把对象的每一次更新记录为一个日志条目（log entry），条目由更新过程（update procedure）的名称和参数组成。该过程必须是函数式的：用同一参数应用时，它必须总是产生同样效果。换句话说，不存在影响过程操作的、参数之外的状态。这意味着日志条目指定的过程调用可以稍后重新执行；如果被更新的对象处于与第一次执行更新时相同的状态，它最终会到达与第一次执行更新后相同的状态。归纳可知，从相同对象开始，重新执行一系列日志条目，会产生与原始执行中产生的相同对象。

要使这起作用，必须满足两个要求：

• 更新过程必须是真正的函数：

它的结果不依赖参数之外的任何状态。

除了出现在其日志中的对象外，它没有副作用（side effect）。

• 参数必须是值，属于以下之一：

立即值，例如整数、字符串等。立即值可以是很大的东西，比如数组甚至列表，但整个值必须复制进日志条目。

对不可变对象（immutable object）的引用。

当然，多数对象不是不可变的，因为它们会被更新。然而，对象的一个特定版本是不可变的；对对象的改变会改变版本。明确引用一个对象版本（object version）的简单方法，是使用 [object identifier, number of updates] 这一对。如果对象标识符（object identifier）能导向该对象的日志，那么重放（replay）指定数量的日志条目就会得到特定版本。当然，做这种重放可能需要找到其他对象版本；但只要每次更新只引用已有版本，就不会有循环，这个过程也会终止。

例如，Bravo 编辑器 [24] 对文档编辑恰好有两个更新函数：

Replace(old: Interval, new: Interval) ChangeProperties(where: Interval, what: FormattingOp)

Interval 是三元组 [document version, first character, last character]。FormattingOp 是从属性到属性的函数；属性可以是斜体或 leftMargin，而 FormattingOp 可以是 leftMargin: = leftMargin + 10 或 italic: = true。因此只需要两种日志条目。所有编辑命令都归约为这两个函数的应用。

当心 进入争端；但既然进入， 就要让对手也当心你。

• 使动作原子化，或可重新启动（restartable）。原子动作（atomic action，常称为事务 transaction）是要么完成、要么没有效果的动作。例如，在大多数主存系统中，取一个字或存一个字是原子的。原子动作对容错性的好处显而易见：如果动作期间发生故障，它没有效果，因此从故障中恢复时，不必处理该动作的任何中间状态 [28]。数据库系统早已提供原子性 [17]，使用日志存储完成或取消动作所需的信息。基本思想是为每个原子动作分配唯一标识符，并用它标记与该动作相关的所有日志条目。该动作的提交记录 [42] 说明它是进行中、已提交（逻辑上完成，即使还剩一些清理工作）还是已中止（逻辑上取消，即使还剩一些清理工作）；提交记录状态的变化也记录为日志条目。除非某个动作所有更新都有日志条目，否则它不能提交。故障之后，恢复过程（recovery）应用每个已提交（committed）动作的日志条目，并撤销每个已中止（aborted）动作的更新。这个方案有许多可能的变体 [54]。

要使这起作用，日志条目通常需要可重新启动。这意味着在一次完整执行之前，它可以被部分执行任意多次，而不改变结果；有时这种动作称为“幂等（idempotent）”。例如，把一组值存入一组变量是可重新启动的动作；把变量加一则不是。可重新启动的日志条目可以应用于对象当前状态；不需要恢复旧状态。

这个基本方法可以用于任何类型的永久存储（permanent storage）。如果事情足够简单，一个相当扭曲的版本也能工作。例如，前面描述的 Alto 文件系统实际上把磁盘标签和 leader page 当作日志，并在必要时从这些信息重建其他数据结构。与多数文件系统一样，只有文件分配和目录动作是原子的；文件系统不帮助客户使其更新成为原子。Juniper 文件系统 [35]、[49] 走得更远，允许每个客户把任意一组更新作为单个原子动作完成。它使用一种称为“影子页（shadow pages）”的技巧：只需改变 B 树中的指针，就可以把数据页从日志移动到文件中；该 B 树实现从文件地址到磁盘地址的映射。这个技巧最早用于 Cal 系统 [50]。普通文件系统的协作客户也可以实现原子动作，方法是在每次访问文件前检查是否需要恢复；如果需要，就执行特殊命名日志文件中的条目 [40]。

一般来说，原子动作并非实现起来微不足道，尽管前面的讨论试图表明，它们远没有公众形象中那么难。有时更弱但更便宜的方法就够了。例如，Grapevine 邮件传输和注册系统 [1] 在全国网络的大量机器上维护一个包含名称和分发列表（distribution list）的复制数据库（replicated data base）。更新在一个站点完成，并使用邮件系统自身传播到其他站点。这保证更新最终会到达；但随着站点失败和恢复、网络分区（network partition），更新到达的顺序可能大不相同。每条更新消息都带有时间戳（timestamp），最新者胜出。经过足够时间后，所有站点都会收到所有更新，并且都会达成一致。不过在传播过程中，站点可能会产生分歧，例如某人是否属于某个分发列表。这种偶发的不一致和延迟，对这个特定系统的有用性并不十分重要。

5. 结论

主啊，我最谦卑地告退。

这样一组好建议和轶事读起来相当乏味；也许最好在睡前小剂量阅读。作为辩解，我只能说，这些规则中大多数我至少违反过一次，而且几乎总是后悔。参考文献更完整地讲述了我只是略述的系统或技术。它们中的许多也提供了更完整的理由说明。

所有口号都汇集在本文开头附近的图 1 中。

致谢

我感谢许多富有同情心的读者阅读本文早期草稿，也感谢程序委员会的意见。

References

1. Birrell, A.D. et al. Grapevine: An exercise in distributed computing. Comm. ACM 25, 4, April 1982, pp 260-273.
2. Bobrow, D.G. et al. Tenex: A paged time-sharing system for the PDP-10. Comm. ACM 15, 3, March 1972, pp 135-143.
3. Boggs, D.R. et al. Pup: An internetwork architecture. IEEE Trans. Communications COM-28, 4, April 1980, pp 612-624.
4. Breed, L.M and Lathwell, R.H. The implementation of APL/360. In Interactive Systems for Experimental Applied Mathematics, Klerer and Reinfelds, eds., Academic Press, 1968, pp 390-399.
5. Britton, K.H., et al. A procedure for designing abstract interfaces for device interface modules. Proc. 5th Int’l Conf. Software Engineering, IEEE Computer Society order no. 332, 1981, pp 195-204.
6. Brooks, F.H. The Mythical Man-Month, Addison-Wesley, 1975.
7. Burton, R.R. et al. Interlisp-D overview. In Papers on Interlisp-D, Technical report SSL-80-4, Xerox Palo Alto Research Center, 1981.
8. Clark, D.W. et al. The memory system of a high-performance personal computer. IEEE Trans. Computers TC-30, 10, Oct. 1981, pp 715-733.
9. Creasy, R.J. The origin of the VM/370 time-sharing system. IBM J. Res. Develop. 25, 5, Sep. 1981, pp 483-491.
10. Deutsch, L.P. and Grant. C.A. A flexible measurement tool for software systems. Proc. IFIP Congress 1971, North-Holland.
11. Deutsch, L.P. and Bobrow, D.G. An efficient incremental automatic garbage collector. Comm. ACM 19, 9, Sep. 1976, pp 522-526.
12. Deutsch, L.P. Efficient implementation of the Smalltalk-80 system. Proc. 11 th ACM Symposium on Principles of Programming Languages, 1984..
13. Dijkstra. E.W. et al. On-the-fly garbage collection: An exercise in cooperation. Comm. ACM 21, 11, Nov. 1978, pp 966-975.
14. Ditzel, D.R. and McClellan, H.R. Register allocation for free: The C machine stack cache. SIGPLAN Notices 17, 4, April 1982, pp 48-56.
15. Geschke, C.M, et al. Early experience with Mesa. Comm. ACM 20, 8, Aug. 1977, pp 540-553.
16. Gifford, D.K. Weighted voting for replicated data. Operating Systems Review 13, 5, Dec. 1979, pp 150-162.
17. Gray, J. et al. The recovery manager of the System R database manager. Computing Surveys 13, 2, June 1981, pp 223-242.
18. Hansen, P.M. et al. A performance evaluation of the Intel iAPX 432, Computer Architecture News 10, 4, June 1982, pp 17-26.
19. Hoare, C.A.R. Hints on programming language design. SIGACT/SIGPLAN Symposium on Principles of Programming Languages, Boston, Oct. 1973.
20. Hoare, C.A.R. Monitors: An operating system structuring concept. Comm. ACM 17, 10, Oct. 1974, pp 549-557.
21. Ingalls, D. The Smalltalk graphics kernel. Byte 6, 8, Aug. 1981, pp 168-194.
22. Janson, P.A. Using type-extension to organize virtual-memory mechanisms. Operating Systems Review 15, 4, Oct. 1981, pp 6-38.
23. Knuth, D.E. An empirical study of Fortran programs, Software−Practice and Experience 1, 2, Mar. 1971, pp 105-133.
24. Lampson. B.W. Bravo manual. In Alto Users Handbook, Xerox Palo Alto Research Center, 1976.
25. Lampson, B.W. and Redell, D.D. Experience with processes and monitors in Mesa. Comm. ACM 23, 2, Feb. 1980, pp 105-117.
26. Lampson, B.W. et al. Electronic image processing system, U.S. Patent 4,203,154, May 1980.
27. Lampson, B.W. Replicated commit. Circulated at a workshop on Fundamental Principles of Distributed Computing, Pala Mesa, CA, Dec. 1980.
28. Lampson, B.W. and Sturgis, H.E. Atomic transactions. In Distributed Systems — An Advanced Course, Lecture Notes in Computer Science 105, Springer, 1981, pp 246-265.
29. Lampson, B.W. and Sproull, R.S. An open operating system for a single-user machine. Operating Systems Review 13, 5, Dec. 1979, pp 98-105.
30. Lampson, B.W. and Sturgis, H.E. Reflections on an operating system design. Comm. ACM 19, 5, May 1976, pp 251-265.
31. McNeil, M. and Tracz, W. PL/1 program efficiency. SIGPLAN Notices 5, 6, June 1980, pp 46-60.
32. McQuillan, J.M. and Walden, D.C. The ARPA network design decisions. Computer Networks 1, Aug. 1977, pp 243-299.
33. Metcalfe, R.M. and Boggs, D.R. Ethernet: Distributed packet switching for local computer networks. Comm. ACM 19, 7, July 1976, pp 395-404.
34. Mitchell, J.G. Design and Construction of Flexible and Efficient Interactive Programming Systems. Garland, 1979.
35. Mitchell, J.G. and Dion, J. A comparison of two network-based file servers. Comm. ACM 25, 4, April 1982, pp 233-245.
36. Needham, R.M. Personal communication. Dec. 1980.
37. Newman, W.M. and Sproull, R.F. Principles of Interactive Computer Graphics, 2nd ed., McGraw-Hill, 1979.
38. Parnas, D.L. On the criteria to be used in decomposing systems into modules. Comm. ACM 15, 12, Dec. 1972, pp 1053-1058.
39. Patterson, D.A. and Sequin, C.H. RISC 1: A reduced instruction set VLSI computer. 8th Symp. Computer Architecture, IEEE Computer Society order no. 346, May 1981, pp 443-457.
40. Paxton, W.H. A client-based transaction system to maintain data integrity. Operating Systems Review 13, 5, Dec. 1979, pp 18-23.
41. Radin, G.H. The 801 minicomputer, SIGPLAN Notices 17, 4, April 1992, pp 39-47.
42. Redell, D.D. et al. Pilot: An operating system for a personal computer. Comm. ACM 23, 2, Feb. 1980, pp 81-91.
43. Reed, D. Naming and Synchronization in a Decentralized Computer System, MIT LCS TR-205. Sep. 1978.
44. Ritchie, D.M. and Thompson, K. The Unix time-sharing system. Bell System Tech. J. 57, 6, July 1978, pp 1905-1930.
45. Rovner, P. Personal communication. Dec. 1982.
46. Saltzer, J.H. et al. End-to-end arguments in system design. Proc. 2nd Int’l. Conf. Distributed Computing Systems, Paris, April 1981, pp 509-512.
47. Smith, D.C. et al. Designing the Star user interface. Byte 7,4, April 1982, pp 242-282 .
48. Smith, J.E. A study of branch prediction strategies. 8th Symp. Computer Architecture, IEEE Computer Society order no. 346, May 1981, pp 135-148.
49. Sturgis, H.E, et al. Issues in the design and use of a distributed file system. Operating Systems Review 14, 3, July 1980, pp 55-69.
50. Sturgis, H.E. A Postmortem for a Time Sharing System. Technical Report CSL-74-l, Xerox Palo Alto Research Center, 1974.
51. Sweet, R., and Sandman, J. Static analysis of the Mesa instruction set. SIGPLAN Notices 17, 4, April 1982, pp 158-166.
52. Tanenbaum, A. Implications of structured programming for machine architecture. Comm. ACM 21, 3, March 1978, pp 237-246.
53. Thacker, C.P. et al. Alto: A personal computer. In Computer Structures: Principles and Examples, 2nd ed., Siewiorek, Bell, and Newell, eds., McGraw-Hill,1982.
54. Traiger, I.L. Virtual memory management for data base systems. Operating Systems Review 16, 4, Oct. 1982, pp 26-48.
55. Bentley, J.L. Writing Efficient Programs. Prentice-Hall, 1982.