第 19 章 缓存算法的战争——1969年，为什么给计算机增加内存，反而可能让它变慢？标记本章已读大字阅读打印本章回到上次阅读位置交互模块加载失败。正文仍可阅读，请刷新重试。正在加载交互实验…第一季 · 人类如何驯服数据来源历史主线：1966—2003年 · Bélády、虚拟内存、FIFO、LRU、工作集、Clock 与 ARC1969年6月。IBM 的三位研究者发表了一篇论文。论文讨论的不是如何设计更快的处理器，也不是如何增加内存容量。而是一个看起来完全违反常识的实验结果：减少一台计算机可以使用的内存，程序的运行时间竟然可能缩短。反过来说：给程序增加内存，反而可能让它运行得更慢。这三位研究者是：László Bélády、Robert A. Nelson 和 Gerald S. Shedler。他们的论文标题是：An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine《分页计算机中某些程序时空特性的一种异常现象》。论文发表于1969年《Communications of the ACM》第12卷第6期。[IBM Research][Mendeley]后来，计算机科学界用第一作者的名字称呼这个现象：Bélády's Anomaly——贝拉迪异常。但这个故事最值得研究的，不是“增加内存竟然可能更差”这句话有多惊人。而是它暴露了操作系统设计中的一个根本问题：缓存算法并不知道未来。它只能根据过去的信息，猜测哪些数据值得留下。而有时候，一套看起来完全合理的保留规则，会作出极其糟糕的决定。第一幕：1960年代，内存为什么如此宝贵？来源来源来源来源来源来源来源来源来源今天，我们很容易找到配备16GB、32GB甚至更大内存的个人电脑。但在1960年代，大型计算机的主存容量非常有限，而且价格昂贵。许多程序与数据不可能同时全部放进内存。于是，操作系统必须回答：哪些数据现在留在主存？哪些数据暂时存放在更慢的外部存储？程序需要访问某些不在内存中的数据时，又应该怎样把它们装载回来？这就是虚拟内存和分页存储管理逐渐发展的重要背景。页面与页框为了管理内存，操作系统可以把虚拟地址空间划分成固定大小的页面（Page）。物理内存划分成相应大小的页框（Page Frame）。假设一个程序需要访问六个页面：A、B、C、D、E、F但系统只为它分配三个页框。那么，同一时刻只能有三个页面驻留在这三个页框里。程序有六个页面，主存只有三个页框虚拟页面ABCDEF物理页框ABC这是单进程分页模型的简化示意。真实操作系统还涉及地址转换、权限、脏页、共享页面等机制。如果程序访问A，A已经在主存中。这叫作：Page Hit，命中。但如果程序访问D，而内存里只有A、B、C，那么就发生了：Page Fault，缺页。系统需要把D对应的数据装入内存。如果三个页框都已经占满，就必须决定：淘汰A、B、C中的哪一个？这便是：Page Replacement——页面替换问题。第二幕：最直观的答案——谁最早进来，就先淘汰谁现在假设你是1960年代的操作系统工程师。内存空间只有三个页框。需要不断装入页面。你可能想到一个非常简单的规则：最早装进内存的页面，应该最早被替换。这就是 FIFO：First In, First Out，先进先出。我们在第三章已经学过队列。FIFO页面替换，本质上就是使用队列维护页面进入内存的先后顺序。假设访问顺序为：1、2、3、4而物理内存只能容纳三个页面。先装入：1、2、3队列从旧到新：[1,2,3]接下来访问4。内存已经满了。于是淘汰最早装入的1，再加入4：[2,3,4]非常简单。甚至不需要维护页面最近一次被访问的时间。FIFO 最大的问题是什么？假设页面1虽然是最早装入的，但此后被访问过1000次。页面2、3可能很久没被用过。FIFO 仍然会优先淘汰1。为什么？因为它只记录：页面是什么时候进入内存的。它不关心：页面最近有没有被使用。但即便如此，你可能认为：“只要增加更多页框，FIFO 的缺页次数应该总会下降吧？”这是一个非常自然的猜测。但接下来，Bélády 将证明它是错的。第三幕：Bélády 异常——12次访问，揭穿一个常识我们先准备一段经典页面访问序列：text复制代码1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5一共12次访问。我们分别模拟：只有3个页框。以及拥有4个页框。二者都使用 FIFO。一开始内存全部为空。当页面不在内存中时，记一次缺页。三个页框按FIFO规则进行全部12次访问：FIFO · 3个页框9 次缺页四个页框把内存增加到四个页框。访问顺序完全相同。仍然使用FIFO。结果却变成：FIFO · 4个页框10 次缺页这是经典反例：3个页框缺页9次，4个页框缺页10次。[Logical Art]3个页框9次缺页4个页框10次缺页增加了33%的页框容量，却多发生了一次缺页。这个结果为什么可能成立？因为 FIFO 的淘汰顺序受到此前所有换入操作影响。增加页框之后，一些页面不再需要立刻被淘汰。但这也改变了它们在 FIFO 队列中的相对位置。后续访问时，两种容量的缓存不再具有简单的包含关系。某个页面可能还留在3页框系统里，却已经从4页框系统中被淘汰。这就是反常现象的本质。历史日期必须讲清楚Bélády 在1966年已经发表了关于虚拟存储替换算法的重要研究：A Study of Replacement Algorithms for a Virtual-Storage Computer。而三位作者系统研究和正式发表上述异常现象的论文，日期是1969年6月。所以，严格讲，本章标题中的历史节点应以1969年的异常论文为准，而不是把1966年早期替换算法研究与1969年三人合作的正式论文混为一谈。[IBM Research][Logical Art]第四幕：一台时间机器——逐步重现1969年的异常现在我们把12次访问放在同一个实验室里。你可以切换3个或4个页框，也可以切换 FIFO、LRU 和 OPT。每点击一次，程序就执行一次页面访问。页面替换实验室经典 Bélády 异常序列 · 逐次执行0/12FIFOLRUOPT3个页框4个页框页面访问序列123412512345当前内存内容页框 1—页框 2—页框 3—累计缺页0当前访问结果尚未开始点击“下一次访问”，让操作系统逐步处理页面请求。下一次访问 →↶运行到底建议你先完成三个实验。首先选择 FIFO、3个页框，运行到底。其次切换 FIFO、4个页框，重新运行。最后切换 LRU，看看同样的访问序列会发生什么。你将发现：相同的硬件容量、相同的访问序列，换一种淘汰规则，就可能得到完全不同的缺页结果。这意味着：决定缓存效率的，不只是缓存有多大。还包括缓存到底如何管理。第五幕：LRU——为什么最近用过的东西，更可能被再次使用？现在，我们介绍另一个经典替换策略：Least Recently Used，简称 LRU。中文通常叫：最近最少使用。它的规则是：缓存满了，需要淘汰一个页面时，选择距离当前时刻最久没有被访问的页面。这与 FIFO 有一个本质区别。FIFO 关注装入时间。LRU 关注最近访问时间。一个很简单的例子缓存容量为3。先访问：A、B、C缓存包含：A、B、C接下来再次访问 A。FIFO 不会改变 A 的装入先后顺序。但 LRU 会认为：A 刚刚被使用，因此它现在非常“新鲜”。如果下一次需要装入 D：FIFO 可能淘汰 A。LRU 则会淘汰 B，因为 B 是最近最久没有被访问的页面。为什么 LRU 有道理？因为许多程序具有一种重要性质：时间局部性（Temporal Locality）。如果程序刚刚访问某段代码或某块数据，短时间内再次访问它的概率往往比较高。例如：循环体中的指令。正在处理的数据结构。当前正在浏览的数据库索引页。热点商品缓存。这些内容往往会被反复访问。因此，LRU 利用最近访问历史，预测未来访问倾向。但注意：LRU 不是数学上对所有访问序列都最优的策略。它只是一种常常符合真实工作负载特征的启发式规则。经典序列的结果刚才的12次访问，在不同算法下得到：算法3个页框4个页框FIFO910LRU108OPT76这个表很有意思。对于3个页框，LRU 的缺页次数竟然比 FIFO 还多。这说明：LRU 通常是很好的通用策略，但不能保证在每一条具体访问序列上都击败 FIFO。而当内存增加到4个页框时，LRU 的表现又明显改善。更重要的是，LRU 不会出现与 FIFO 相同类型的 Bélády 异常。原因涉及一个叫作 Stack Property（栈性质）的数学性质。第六幕：1970年，为什么 LRU 不会发生 Bélády 异常？1970年，IBM 的研究者 Richard L. Mattson、Jan Gecsei、Donald R. Slutz 和 Irving L. Traiger 发表了一篇重要论文：Evaluation Techniques for Storage Hierarchies《存储层次结构的评估技术》。其中研究了一类重要的替换算法：Stack Algorithms，栈算法。这里的“栈”并不完全等同于我们第二章讲过的后进先出程序栈。它强调的是：在不同容量的缓存之间，驻留页面集合必须满足一种包含关系。[Logical Art]假设：容量为3的 LRU 缓存，其驻留集合为：S3S_3S3容量为4的 LRU 缓存，其驻留集合为：S4S_4S4对于同一段访问历史，LRU 能够保证：S3⊆S4\boxed{S_3\subseteq S_4}S3⊆S4也就是说：容量较小的 LRU 缓存拥有的所有页面，一定也存在于更大的 LRU 缓存中。为什么？因为 LRU 可以把所有页面按照最近使用时间排序。容量为3的缓存，保留最近使用的前3个页面。容量为4的缓存，保留最近使用的前4个页面。前3个显然包含在前4个中。于是，如果容量为4的缓存发生缺页，容量为3的缓存也不可能拥有那个页面。所以增加容量不会导致更多缺页。这是一项比“通常性能更好”更强的结论：LRU 对任意固定访问序列，都不可能因为单纯增加缓存容量而出现更多缺页。FIFO 则没有这种包含性质。因为不同容量下的页面入队、出队顺序可能发生分叉。这就是 Bélády 异常与 Stack Property 之间的联系。第七幕：1966年，Bélády 还研究过一个永远知道未来的算法我们暂时把目光放回1966年。在那篇早期页面替换研究中，Bélády 讨论了一种特殊算法，常称为 MIN 或 OPT。它的规则与 FIFO、LRU 完全不同。当缓存满了，需要淘汰一个页面时：选择下一次被访问的时间距离现在最远的那个页面。如果某个页面以后再也不会被访问，那么淘汰它自然是最理想的选择。例如：缓存里有 A、B、C。未来访问顺序为：A、D、B、E、A、F、C那么：A 很快会再次使用。B 稍后会使用。C 要更久之后才会使用。所以 OPT 应该优先淘汰 C。为什么 OPT 是最优的？因为它掌握完整的未来访问序列。它不需要根据过去猜测下一步。它直接知道每个页面下一次什么时候被需要。在理想的离线页面替换模型中，OPT 能够最小化缺页次数。这可以通过交换论证证明：如果另一种策略淘汰了未来更早需要的页面，而保留了更晚才需要的页面，那么适当交换这两者的淘汰选择，不会让结果变差。所以，选择未来最晚再使用的页面是安全的。这也是一种非常漂亮的贪心算法。但问题是：现实中的操作系统一般不知道程序未来会访问哪些页面。因此，OPT 很难作为在线页面替换的实际策略。它最重要的用途是：作为理论最优基准。如果某种现实算法在一段访问序列上的缺页次数非常接近 OPT，说明它已经取得相当好的结果。如果差距很大，则说明仍有优化空间。这与我们第九章的贪心算法再次产生了联系。第八幕：1968年，Peter Denning 发现真正的问题是“工作集”来源Peter J. Denning1942年出生 · 美国计算机科学家长期研究虚拟内存、操作系统、计算机性能及计算科学教育。1968年5月，Denning 在《Communications of the ACM》发表：The Working Set Model for Program Behavior《程序行为的工作集模型》。他的研究指出，一个程序在某段时间内，通常会集中访问某个较小的页面集合。这个集合随着程序执行阶段不断变化。[Communications of the ACM][denninginstitute.com]Denning 把它称为：Working Set，工作集。假设某个程序不断访问：A、B、C、A、B、C、A、B、C那么，它当前主要使用的页面就是：{A,B,C}。如果分配给程序的内存能够同时容纳这三个页面，那么大部分访问都能命中。但如果只分配两个页框呢？程序就可能不断换出一个很快又要使用的页面。这样，系统的大量时间都花在页面换入换出上。这种现象被称为：Thrashing，抖动。为什么增加并发程序数量，有时反而降低吞吐量？假设系统原本运行三个程序。每个程序都能获得足够内存保存自己的工作集。后来，操作系统为了充分利用 CPU，又增加两个同时运行的程序。结果总工作集需求超过了可用物理内存。所有程序都开始频繁缺页。磁盘或后备存储 I/O 增加。CPU 反而经常等待数据装载。最终整体吞吐量下降。Denning 的工作集模型指出：不应只关注当前 CPU 是否空闲。还必须保证正在运行的程序拥有足够容纳活跃工作集的内存。这一研究为虚拟内存管理和操作系统调度提供了极为重要的理论基础。[MIT开放学术]这里有一个与 Bélády 异常的重要区别。Bélády 异常是：固定访问序列下，某些页面替换策略在增加页框数后反而产生更多缺页。系统抖动则是：活跃工作集超出可用内存，导致频繁换页和性能下降。它们都会带来违反直觉的性能表现，但不是同一种现象。第九幕：Clock 算法——如果精确 LRU 太贵，能不能只记录一个访问位？LRU 的思想简单，但精确实现未必便宜。例如，系统需要知道：每个页面最近一次是什么时候被访问的？每发生一次命中，是否都要调整一个链表节点？如果页面数量非常多，持续维护精确访问顺序可能产生明显开销。尤其在操作系统内核中，页面访问经常由硬件直接完成，不一定能低成本地为每次访问更新一个全局 LRU 队列。于是，工程实践中出现了许多近似 LRU 方法。其中最经典的一种，就是：Clock Page Replacement，时钟页面替换算法。为什么叫 Clock？想象一组页面按照圆环排列。系统维护一根“时钟指针”。每个页面还拥有一个访问位：reference bit当页面被访问时，硬件或系统可以将访问位设为1。需要替换页面时，时钟指针依次检查。如果访问位为1：说明它最近曾经被访问。先给它一次机会。把访问位清为0，然后继续前进。如果访问位为0：就选择这个页面作为淘汰对象。这也被称为 Second Chance（二次机会）思想。时钟页面替换实验Clock 页面替换实验室Second ChanceAR=1BR=1CR=0DR=1ER=0FR=1时钟指针沿顺时针方向扫描指针从第0个页框开始。点击检查下一页框。检查当前页框↶Clock 的优势在于，它不必实时维护所有页面的精确最近访问顺序。它只使用少量状态，近似保留近期访问过的页面。但它也不是完美 LRU。一个页面访问位为1，只说明自上次清零以来被访问过，并不能精确区分它访问了一次还是一千次。因此，Clock 的实际表现依赖工作负载和实现方式。现代操作系统也可能使用更复杂的多队列、世代分类和访问位采样机制，并不一定直接采用最朴素的 Clock。第十幕：2003年，IBM 两位研究者决定同时利用“最近”和“经常”来源Nimrod Megiddo 与 Dharmendra S. Modha2003年3月，两人在 USENIX FAST 会议发表：ARC: A Self-Tuning, Low Overhead Replacement Cache。这项工作提出了一种非常有影响力的自适应缓存替换策略：ARC，Adaptive Replacement Cache。它研究的问题是：LRU 只强调最近是否被使用。但有些页面虽然刚刚被访问，却可能以后再也不会出现。另一些页面虽然不是最新访问的，却长期反复出现。我们能否同时考虑：Recency（最近性）以及：Frequency（访问频率）并且让缓存根据工作负载自动调整二者的权重？这就是 ARC 的核心。[IBM Research][USENIX]一个非常典型的 LRU 问题：顺序扫描假设缓存容量为4。缓存中已经有四个频繁使用的页面：A、B、C、D现在程序开始顺序扫描大量只访问一次的新页面：X1、X2、X3、X4、X5、X6...对于简单 LRU，每次新页面进入缓存，都可能淘汰一个旧的热点页面。扫描结束后：A、B、C、D 可能全部被赶出缓存。但这些扫描页面以后或许根本不会再被访问。这叫作：Scan Pollution，扫描污染。ARC 的设计ARC 把缓存内部的页面管理组织成不同类别。其中重要的思想，是区分：近期只出现过一次的页面。以及已经表现出重复访问特征的页面。它还使用只记录身份、不保存实际缓存内容的“幽灵列表”（Ghost Lists），记录最近被淘汰的页面历史。如果某个刚刚淘汰的页面又被访问，说明之前的淘汰可能并不理想。ARC 可以利用这些信号，动态调整偏向最近性还是频率。这与普通 LRU 只维护单一顺序的设计不同。为什么这是一种进步？因为不同应用程序的访问模式变化很大。数据库随机查询。大文件顺序扫描。网页热点缓存。文件系统元数据。它们需要的缓存策略可能不同。ARC 不要求管理员提前准确知道工作负载性质，而是利用访问历史进行自适应调整。2003年的原始论文在多个真实访问轨迹上进行了实验，并报告了相对于 LRU 的显著收益，包括更好的抗扫描污染能力。[USENIX]不过，这不意味着 ARC 在所有可能访问序列上都优于 LRU，也不意味着所有系统都可以不考虑成本直接替换为 ARC。实际工程中还要考虑元数据开销、并发同步、实现复杂度，以及相关知识产权和许可问题。第十一幕：用 Python 复现这场缓存算法的战争下面写一个简化但完整的页面替换模拟器。支持：FIFO。LRU。OPT。输入同一访问序列，返回总缺页数。python复制代码def page_faults(pages, capacity, policy): cache = [] inserted_at = {} last_used = {} faults = 0 for time, page in enumerate(pages): if page in cache: last_used[page] = time continue faults += 1 if len(cache) == capacity: if policy == "FIFO": victim = min( cache, key=lambda x: inserted_at[x] ) elif policy == "LRU": victim = min( cache, key=lambda x: last_used[x] ) elif policy == "OPT": future = pages[time + 1:] def next_use(x): try: return future.index(x) except ValueError: return float("inf") victim = max( cache, key=next_use ) else: raise ValueError("Unknown policy") cache.remove(victim) cache.append(page) inserted_at[page] = time last_used[page] = time return faults运行经典测试：python复制代码pages = [ 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ] for policy in ["FIFO", "LRU", "OPT"]: print( policy, page_faults(pages, 3, policy), page_faults(pages, 4, policy) )输出：text复制代码FIFO 9 10 LRU 10 8 OPT 7 6这里需要区分两件事。这段教学代码可以正确模拟缓存容量和策略，但由于使用 Python 列表查找页面与计算未来位置，并不是高性能实现。例如：python复制代码page in cache需要线性搜索。而真正的 O(1)O(1)O(1) 平均复杂度 LRU 缓存，通常使用：哈希表 + 双向链表。哈希表负责快速定位页面。双向链表负责维护最近使用顺序。命中页面时，把对应节点移动到链表头部。容量满时，从链表尾部淘汰最近最少使用的页面。这就是我们第一章链表、第四章哈希表又一次在实际系统里组合起来的例子。第十二幕：缓存算法应该如何选择？现在我们回到今天的系统设计。算法核心规则优势主要局限FIFO淘汰最早装入的页面简单、元数据少可能发生 Bélády 异常LRU淘汰最近最久未使用的页面利用时间局部性容易受到顺序扫描污染OPT淘汰未来最晚使用的页面理论最优在线系统无法预知未来Clock使用访问位和循环扫描相对低成本地近似最近性不精确记录访问顺序ARC自适应平衡最近性与频率能适应多种负载，抗扫描污染实现更复杂有一点尤其重要：缓存命中率不是唯一性能指标。例如，对磁盘页面缓存而言，一次未命中可能引发昂贵的存储访问。但对 CPU Cache 而言，访问延迟、硬件实现复杂度和功耗也非常重要。在分布式缓存中，还可能涉及网络请求、缓存重建、数据一致性和热点分布。同样一套策略，在不同层次的缓存中未必都合适。这也解释了为什么今天仍然同时存在 LRU、LFU、Clock、ARC、2Q、LIRS、TinyLFU 等多种方法。现代缓存算法已经不只是选择一个牺牲页面。而是在不断估计：未来哪些数据最可能再次被使用？保留它们能节省多少代价？终章挑战：你真的理解 Bélády 异常了吗？现在有一个三页框 FIFO 缓存。它当前的页面装入顺序是：A → B → CA 最早装入。程序后来再次访问 A。请问，此时 FIFO 淘汰优先级会怎样变化？选择正确答案A 刚刚被访问，因此自动移到队列末尾FIFO 不因命中而改变进入队列的先后顺序，A 仍然最先淘汰FIFO 会重新随机选择淘汰候选尾声：计算机真正需要的，不只是更多内存，而是更聪明地使用内存1966年，Bélády 系统研究虚拟存储中的页面替换问题。1968年，Peter Denning 通过工作集模型解释程序局部性与内存抖动。1969年，Bélády、Nelson 和 Shedler 正式揭示：某些页面替换算法甚至可能因为增加内存而产生更多缺页。1970年，Mattson 等研究者进一步发展缓存层次评估理论，帮助解释为什么 LRU 等栈算法不会出现这种异常。2003年，Megiddo 和 Modha 提出 ARC，让缓存管理能够自适应地平衡最近性与访问频率。几十年间，研究者不断尝试回答同一个问题：当资源永远不足以保存全部数据时，我们究竟应该舍弃什么？这其实是算法研究中一种非常深刻的设计问题。而最值得记住的结论是：资源增加，不保证错误策略会自动变成正确策略。缓存容量固然重要。但数据访问模式、局部性、替换规则和维护开销，同样决定最终性能。第十九章知识总结概念核心思想Page / Frame虚拟页面与物理页框Page Fault请求页面不在内存中FIFO淘汰最早进入缓存的页面Bélády's Anomaly某些策略在增加页框后反而产生更多缺页LRU淘汰最近最久没有使用的页面Stack Property较小缓存的驻留集合包含于较大缓存OPT / MIN利用未来信息获得离线最优替换Working Set程序近期活跃的页面集合Thrashing频繁换页导致整体性能恶化Clock用访问位近似最近使用情况ARC自适应地平衡最近性与访问频率本章历史原始资料Bélády、Nelson、Shedler（1969）：异常现象原始论文档案ACM：1969年《An Anomaly in Space-Time Characteristics》Peter Denning（1968）：工作集模型原始论文 PDFPeter Denning 本人的工作集研究历史资料Megiddo、Modha（2003）：ARC 原始论文与实验结果ARC 2003年完整论文 PDF下一章预告第二十章：数据库事务——1970年代，为什么一笔转账绝不能只成功一半？1970年代，IBM 的研究人员开始把关系数据库从数学理论变成真正能够服务商业应用的系统。一笔银行转账需要执行两次更新：从账户 A 扣除100元。向账户 B 增加100元。如果第一步成功，第二步却因为断电失败，应该怎么办？又如果两名用户同时操作相同的账户，怎样避免金额被错误覆盖？这些问题推动了数据库事务、并发控制、日志恢复与后来 ACID 概念的成熟。下一章，我们将从 Edgar F. Codd 的关系模型、IBM System R、Jim Gray 的事务研究，讲到 Write-Ahead Logging、两阶段提交和 MVCC。最值得研究的问题是：即使计算机在最糟糕的时刻突然断电，数据库为什么仍然有可能保证一笔事务要么全部完成，要么完全不生效？上一章第十八章：跳表——1989年，一位计算机科学家为什么决定用抛硬币代替平衡树的旋转？下一章第二十章：数据库事务——1970年代，为什么一笔转账绝不能只成功一半？