玻尔百科现代处理器每秒能够执行数十亿次操作，但它们常常受到相对较慢的主内存速度的制约。这个巨大的性能差距，通常被称为“内存墙”，如果CPU必须从动态随机存取存储器（DRAM）中获取每一份数据，那么它大部分时间都将处于空闲状态。针对这一根本问题的巧妙解决方案是缓存层次结构，一个由更小、更快的存储器组成的分层系统，充当处理器和主内存之间的中介。本文将揭开这个计算机体系结构中关键组件的神秘面纱。
在接下来的章节中，您将对这个系统有一个全面的了解。第一章，“原理与机制”，将剖析使缓存工作的核心概念，从使用平均内存访问时间（AMAT）衡量性能，到相联度和写策略等复杂的设计权衡。然后，我们将在“应用与跨学科联系”中拓宽视野，探讨这些硬件原理如何对算法设计、操作系统行为乃至计算机安全产生深远且常常令人惊讶的影响。我们首先将审视催生缓存层次结构的根本矛盾及其运行所遵循的优雅原则。
在每台现代计算机的核心，都存在着一个深刻的矛盾，一个关于两种截然不同速度的故事。一方面，是中央处理单元（CPU），一个工程奇迹，能在眨眼之间完成数十亿次计算。另一方面，是主内存，或称动态随机存取存储器（DRAM），一个巨大的数据仓库，相比之下，其运行速度慢如蜗牛。如果CPU每次需要信息时都必须等待缓慢的主内存，那么它大部分时间都将处于空闲状态，就好比一位大厨需要为每一种食材都跑到城外的农场去取。这道“内存墙”将严重削弱性能。解决这个问题的巧妙方案不是单一、完美的存储器，而是一个缓存层次结构。
这个想法简单而优雅，植根于我们日常生活中都会使用的一个原则：局部性原理。当你在做一个项目时，你不会把所有的工具和材料都放在遥远的仓库里。你会把你正在使用的，以及你预期很快会用到的东西，带到你旁边的 workbench（工作台）上。缓存就是CPU的工作台。它是一小块紧邻CPU核心的、速度极快、因此也十分昂贵的存储器。通过保存最常用和最近使用过的数据的副本，缓存可以几乎瞬时地满足CPU的大部分请求，使处理器能够全速运行。但正如任何优雅的想法一样，其精妙与复杂之处都体现在细节中。
我们如何衡量缓存是否工作良好？我们可以用两种方式来描述任何内存访问：要么是命中，要么是未命中。当CPU需要的数据已经在缓存中时，就发生了缓存命中。这是最佳情况——一次快速、低延迟的访问。当数据不在缓存中时，就发生了缓存未命中，这迫使系统踏上前往下一级存储器的更慢旅程来检索数据。
存储系统的性能可以通过一个强大而单一的指标完美地体现出来：平均内存访问时间（AMAT）。它是任何给定内存请求的期望时间。我们可以从第一性原理推导出它。对于一个只有一个缓存和主内存的简单系统，任何访问都必须首先检查缓存。假设这需要时间 。如果命中，这就是总时间。如果未命中，其发生的概率称为未命中率（），我们就必须支付命中时间加上一个额外的未命中惩罚（），用于从更慢的主内存中获取数据。命中的概率就是 。
所以，平均时间是每种结果的时间乘以其概率的总和：
经过一点代数简化，就得到了这个经典公式：
这个方程是缓存性能的“罗塞塔石碑”。它告诉我们，要让存储系统更快，只有三种方法：减少命中时间、减少未命中率，或者减少未命中惩罚。现代缓存层次结构的每一个特性，都是为了优化这三个变量中的一个或多个。
让我们把这个具体化。想象一台拥有三级缓存系统的计算机，这是现代处理器中的常见设计。一次访问首先检查一级（L1）缓存。如果未命中，它会检查二级（L2）缓存。如果在那里也未命中，它会检查三级（L3）缓存。如果三级都未命中，它最终会去访问主内存。每一级都有自己的命中时间和自己的局部未命中率（在访问已经到达该级别的情况下，在该级别未命中的概率）。AMAT的计算变成了一个嵌套的期望：
L1的未命中惩罚是从L2系统获取数据所需的时间，而这本身就是一个AMAT计算：。将此一直延伸下去，我们得到：
对于一个具有如下参数的系统： ns, ns, ns, ns，以及局部未命中率 , , 和 ，其AMAT仅为 纳秒。尽管一次主内存之旅是痛苦的 纳秒，但因为大多数访问都被更快的缓存捕获了，所以平均体验非常迅速。这就是层次化方法的力量。
缓存不仅仅是一个无结构的数据桶；它是一个高度组织的图书馆。为了实现高速，它必须有一套系统化的方法来放置和再次找到数据。这种组织有几个关键参数。
缓存行：数据不是逐字节移动的。相反，它是以固定大小的块进行传输的，这些块被称为缓存行（或缓存块），在现代系统中通常为64字节。当你对单个字节发生未命中时，硬件不仅仅获取那个字节；它会获取包含该字节的整个64字节块。这是对空间局部性的赌注——即观察到如果一个程序访问了一块数据，它很可能很快就会访问附近的数据。通过获取一整行，缓存预加载了CPU接下来可能需要的数据，将潜在的未来未命中转化为了命中。
相联度：当一行数据从主内存中取来时，它应该放在缓存的什么位置？这是最关键的设计问题之一。
最简单的方法是直接映射缓存。在这里，每个内存地址只能存储在缓存中的一个特定位置。这就像一个图书馆，每本书在书架上都有一个单一、预定的位置。这种方式构建简单，但会遭受冲突未命中。如果一个程序反复需要两个恰好映射到同一缓存位置的不同数据块，它们会不断地相互驱逐，即使缓存的其余部分是空的，也会导致未命中。
最灵活的方法是全相联缓存，其中任何一行数据都可以放在缓存中的任何位置。这完全消除了冲突未命中，但同时搜索整个缓存所需的硬件复杂且耗电，使其只适用于非常小的缓存。
实际的折衷方案是组相联缓存。缓存被划分为若干个组，一个内存地址映射到一个特定的组。然而，在该组内，数据可以放置在任何可用的槽位中，这些槽位被称为路。一个路组相联缓存每个组有个槽位。这就像一个图书馆，一本书有一个指定的书架（组），但可以放在该书架上个位置中的任何一个。相联度对设计者来说是一个强大的调节旋钮。增加相联度可以减少冲突未命中，但有代价。逻辑变得更加复杂，会略微增加命中时间，并显著增加每次访问的能耗。
运行一个缓存所需的逻辑电路——用于识别每个缓存行中存储了哪个内存地址的标签（tags）、用于表示某一行是否持有有效数据的有效位（valid bits）、用于写策略的脏位（dirty bits）以及其他元数据——的总大小是相当可观的。对于一个有个组和路，且每行需要位作为标签和一些位用于元数据的缓存，总开销与成正比。这种在硅片面积上的物理成本不断提醒我们，每一个设计选择，比如增加相联度，都有其切实的代价。
我们拥有一个层次结构的缓存（L1, L2, L3）是物理学和经济学直接作用的结果。速度非常快的存储器也非常昂贵和耗电，所以你用不起太多。速度较慢的存储器更便宜、更高效，所以你可以拥有更多。一个典型的层次结构可能如下所示：
这个层次结构通过过滤内存请求来工作。绝大多数访问（希望是 >90%）都由L1缓存满足。L2缓存捕获了大部分L1的未命中，L3缓存捕获了大部分L2的未命中，只有极小一部分的原始请求需要踏上漫长而缓慢的主内存之旅。这种分层防御机制是保证CPU数据供给的关键。
除了基本结构，设计者还必须做出几个微妙的策略选择，这些选择对性能和行为有着深远的影响。
当CPU想要写入数据时会发生什么？
这个选择会带来有趣的现实世界后果。考虑一下当你让笔记本电脑休眠时会发生什么。在关闭内存系统电源之前，它必须确保主内存包含系统状态的完整镜像。对于写通缓存，这已经实现了——不需要额外的工作。但对于写回缓存，系统必须首先执行一次“刷回”，找到整个缓存层次结构中所有的脏行并将它们写回内存。这所需的时间与脏行的数量（）和内存接口的带宽（）成正比，延迟为 。这个架构选择可能就是你的笔记本电脑是瞬间挂起还是需要等待几秒钟的区别。
另一个写决策是在写未命中时该怎么做。如果CPU想要写入一个不在缓存中的地址，它是否应该先将相应的行带入缓存？
这个选择对流式工作负载至关重要。想象一个程序正在向磁盘写入一个大的视频文件。它对每个内存位置只写入一次。如果使用写分配策略，对于每一次小的写入（例如8字节），系统都会浪费地从内存中获取一整个64字节的缓存行，结果只是立即覆盖其中的一小部分。对于1.5亿次这样的写入流，这可能导致近10GB完全浪费的内存带宽！对于这类模式，非写分配策略的效率要高得多。
在多级缓存中，L1和L2中的数据之间是什么关系？
这个看似深奥的选择对缓存系统的有效容量有着巨大的影响。采用互斥策略，唯一数据行的总数是两个缓存容量之和：。你可以将L1的容量用作“额外”空间。这意味着互斥缓存可以处理更大的程序工作集，然后才会开始“颠簸”——一种持续发生容量未命中导致性能骤降的状态。对于一个大小为的工作集，包含型缓存当时开始颠簸，而互斥型缓存可以坚持到。
缓存是在单核处理器时代发明的。现在的世界是多核的，这带来了一个艰巨的挑战：缓存一致性。如果核心0在其私有L1缓存中有一份内存位置X的副本，而核心1有另一份副本，那么如果核心0向X写入一个新值会发生什么？核心1的副本现在就过时了，如果它使用了那个过时的数据，程序就会产生不正确的结果。
确保所有核心看到一致的内存视图是一致性协议的工作，比如常见的MESI（已修改、独占、共享、无效）协议。在这里，缓存层次结构再次扮演了至关重要的角色。
在一个基于监听的系统中，一个核心可能需要向所有其他核心广播一条消息，以检查它们是否拥有某数据行的副本。这会产生大量的流量。然而，一个大型、共享且包含型的L3缓存可以充当一个监听过滤器（snoop filter）。因为L3知道所有核心的L1/L2缓存中的所有内容，所以一个核心可以简单地检查L3。如果L3的跟踪信息表明没有其他核心拥有该行，就可以跳过昂贵的广播，从而显著减少一致性开销并改善AMAT。
对于拥有许多核心的系统，广播变得不可行。这些系统使用基于目录的一致性，其中一个中央目录存储系统中每个缓存行的状态和位置。在这里，包含策略同样会产生影响。如果L3缓存是包含型的，目录的元数据可以保持精简，因为它可以依赖L3的标签。但如果缓存是非包含型的，目录必须跟踪那些可能在L1/L2中但不在L3中的行。这迫使目录为其跟踪的每一行都存储一个完整的标签副本，从而极大地增加了其存储开销。一个单一的设计选择——包含型与互斥型——会波及整个系统，影响从有效容量到一致性机制成本的方方面面。
我们为什么如此执着于这些细节？因为它们是连接硅的物理极限与我们日常使用的软件性能之间的桥梁。一个算法的性能往往不是由它执行了多少计算决定的，而是由它利用缓存层次结构的程度决定的。
一个经典的例子是矩阵乘法。一个简单的三层循环实现对缓存来说可能是灾难性的，它不断地流式处理巨大的矩阵，并受限于主内存带宽。但通过重新排序循环，并将矩阵分成适合L1缓存的小块进行处理，算法可以被转变。大多数内存访问变成了L1命中，数据被密集地重用，操作变成了计算密集型而不是内存密集型。处理器不再等待数据；它以其峰值计算吞吐量运行。这个基于对缓存层次结构理解的单一优化，可以将计算速度提高一个数量级甚至更多。
缓存层次结构的设计是一场优美的平衡艺术。没有单一的“最佳”缓存。正如我们所见，增加相联度可以降低未命中率，但会增加延迟和能耗。不同的写策略在不同的工作负载下表现出色。包含策略用简单性换取有效容量。芯片设计者必须在这些权衡中导航，目标是在一定的性能预算下，最小化像能量延迟积（EDP）这样的指标。这场由物理、逻辑和概率交织而成的复杂舞蹈的结果，就是那个默默无闻、无形地驱动着我们数字世界的引擎，将等待遥远内存的 frustrating 等待，变成了我们习以为常的瞬时响应。
在探讨了支配缓存层次结构的优雅原则之后，我们可能会倾向于将这些知识归档为一项巧妙的硬件工程，一个只是让我们的计算机变快的黑盒子。然而，这样做将是只见树木，不见森林。缓存不仅仅是一个组件；它是一种强大而普遍的力量，深刻地塑造了计算领域的整个面貌。它的影响从硅片向外扩散，塑造了算法设计的艺术，决定了操作系统的策略，甚至在数据安全领域开辟了未曾预见的疆界。让我们踏上一段旅程，追溯这些联系，见证缓存层次结构给数字世界带来的美丽，且时而令人惊讶的统一性。
想象一下，你让一个工人建造一栋房子。蓝图和材料都存放在一个需要走很远路才能到达的巨大仓库里。如果这个工人取来一颗钉子，走回房子，把它钉进去，然后再走回仓库取一颗螺丝，这个项目将耗费永恒的时间。大部分时间都花在了走路，而不是建造上。这正是现代处理器在运行一个设计拙劣的算法时所处的困境——“走路”就是等待主内存数据的时间。
现在，如果我们雇佣八个工人，并将房子分成八个部分呢？可能会发生一件有趣的事情。每个工人负责的小区域所需的材料清单可能足够短，可以放在一个方便的工具带里。他们早上只去一次仓库，然后整天都在建造，所需的一切都触手可及。令人惊讶的是，我们可能会发现这八个工人完成房子的时间不到原来时间的八分之一。我们实现了超线性加速比：一种似乎违背简单算术的效率增益。
这不是魔法；这是缓存的魔力。在串行情况下，问题的总“工作集”对于缓存（工具带）来说太大了，迫使它不断地、缓慢地往返于主内存（仓库）。通过划分问题，每个核心的较小工作集突然能够装入其私有缓存中。内存停顿时间的急剧减少使得每个核心的效率远高于原始场景中的单个核心。
这种洞察将算法设计从纯粹的数学练习转变为一门实用的内存管理艺术。考虑一下科学计算中的一个基本任务，比如大矩阵的Cholesky分解。一个直接的、教科书式的实现，逐个元素地处理矩阵，就像我们那个拿钉子和螺丝的工人一样；它表现出糟糕的缓存性能，不断地从矩阵的各个角落获取数据。然而，高性能计算库使用“分块”或“缓存无关”的递归算法。这些方法类似于一个聪明的学者，他不是一次从巨大的图书馆里取一本书，而是带一小堆相关的书到自己的桌子上。他们会深入地处理这些书（矩阵的一个“块”），然后再去取下一批。通过最大化对已在缓存中的数据的处理工作，他们将内存密集型的爬行变成了计算密集型的冲刺。
缓存的影响甚至延伸到我们对基本数据结构的选择。例如，一个经典的二叉堆在理论上看起来非常高效。但是，当我们追踪它在更新过程中的内存访问时，会发现它在内存中跳跃的方式让缓存很难受，表现出很差的空间局部性。一个简单的改变——将堆扩展为一个“d-叉”结构，其中每个父节点有更多的子节点——缩短了堆的高度。这减少了沿结构向下的“跳跃”次数，并且因为一个节点的子节点是连续存储的，我们可以用一次缓存友好的突发读取加载所有子节点。我们用每一层级多出的几次CPU比较，换来了内存访问时间的大幅减少，这是一笔非常值得的交易。
幸运的是，我们不必总是如此深入地参与缓存的管理。你电脑上最复杂的两个软件——编译器和操作系统——充当着内存层次结构的无形主宰。
编译器是一位大师级工匠，它将我们人类可读的源代码锻造成高度优化的机器指令。它最聪明的技巧之一是循环分块（loop tiling）。面对一个处理大数组的简单嵌套循环，编译器可以自动将其重构为一个复杂的循环嵌套，以小块（tile）的方式处理数组。它会计算出理想的块大小，以确保每个块的数据都能舒适地放入缓存中。它甚至可以同时为多个缓存级别进行这种优化，选择一个内存占用量既是L1又是L2缓存行大小的最小公倍数的块大小。这种自动转换将一个缓存颠簸的噩梦变成了一场处理器与内存之间完美编排的舞蹈。
操作系统（OS），作为硬件资源的最高仲裁者，扮演着更为深刻的角色。它与缓存的关系始于最基本的层面：虚拟内存。OS为每个程序提供了其自己私有的、连续的地址空间的幻象。硬件的内存管理单元（MMU）将这些虚拟地址转换为物理内存位置。这对缓存提出了一个难题：它应该由虚拟地址索引（速度快，但可能存在歧义）还是由物理地址索引（无歧义，但需要等待转换）？
这个选择有深远的影响。一个虚拟索引、物理标签（VIPT）的缓存可以在MMU进行转换的同时开始查找，这是一个巨大的性能胜利。然而，它面临“别名”问题的风险：两个不同的虚拟地址映射到同一个物理位置，但可能指向不同的缓存组。这可能导致相同的数据同时存在于两个地方，这是灾难的根源。解决方案揭示了一个优美而并非显而易见的约束：只有当用于缓存索引的位数加上块内偏移的位数小于或等于内存页中的位数时，才能避免这种别名问题。突然之间，缓存设计者对容量和相联度的选择与OS设计者对页面大小的选择变得密不可分。
在多核世界中，OS作为调度者的角色变成了一场与共享缓存的精妙舞蹈。当OS将一个进程从一个核心迁移到另一个核心（“软亲和性”）时，该进程会失去其旧核心私有L1和L2缓存中所有宝贵的数据，这是一个代价高昂的事件。在这里，共享的末级缓存（LLC）的架构变得至关重要。如果LLC是包含型的——意味着它包含了私有缓存中所有内容的副本——它就充当了一个温暖的“安全网”。迁移后，进程可以从快速的共享LLC中迅速重新填充其新的私有缓存。而互斥型的LLC，只持有不在私有缓存中的数据，则不提供这样的好处，使得迁移的惩罚要大得多[@problem_d:3672764]。
但包含性是一把双刃剑。当多个核心共享一个资源时，它们会相互干扰。想象一下，一个核心正在运行一个行为良好的应用程序，其工作集完美地装在其L2缓存中。现在，在相邻的核心上，OS调度了一个“吵闹的邻居”——一个流式应用程序，它会处理海量数据。这个吵闹的邻居会不断地污染共享的LLC。在一个包含型系统中，每当污染者为了腾出空间而从LLC中驱逐一行时，硬件必须向私有缓存发送一个“反向失效”消息，以维持包含属性。这意味着行为良好的应用程序的数据可以被另一个核心的行为远程地从其私有L2缓存中驱逐！那个有助于迁移的机制现在却造成了一种新的跨核干扰形式，这是系统设计中一个经典的“天下没有免费的午餐”情景。
故事并未就此结束。随着技术的发展，我们与缓存层次结构的关系继续以令人惊讶的方式变化，在数据正确性和安全性方面都开启了新的挑战。
持久性内存（PMem）的出现——这种内存像DRAM一样快，但在断电时仍能保留其内容——是一场革命。几十年来，缓存纯粹是为了性能；它们易失的内容在电源故障中无足轻重。现在，易失性缓存位于CPU和持久存储之间。一个程序可能写入数据并相信它已经被“保存”，但它可能只是停留在CPU的缓存中，一旦断电就会消失。
为了解决这个问题，我们必须为保证正确性而显式地管理缓存。像clwb这样的新指令允许软件温和地将一个缓存行推送到内存控制器。然后，一个内存栅栏（sfence）确保写操作确实到达了内存控制器自身的掉电安全队列。硬件本身也提供了不同的保证：一个ADR平台只保护内存控制器的队列，要求软件在使用clwb和sfence时要非常勤勉。一个更先进的eADR平台将掉电持久域扩展到包括CPU缓存本身，简化了软件的工作。缓存不再只是一个加速器；它已成为数据持久性管道中的一个关键阶段。
也许最令人震惊的联系是缓存层次结构与计算机安全之间的联系。缓存，就其本质而言，会根据其所持有的数据改变其状态。这种状态变化——访问内存所需的时间——是可以被观察到的。攻击者可以预先填充共享LLC中的一个特定组，然后通过计时自己的内存访问，来检测自己的哪些行被共享该组的受害者进程所驱逐。这种“基于驱逐”的攻击允许攻击者了解受害者正在访问哪些内存位置，从而在不直接读取受害者内存的情况下泄露像加密密钥这样的秘密信息。
在这里，架构选择再次具有安全隐患。一个包含型缓存层次结构会产生驱逐级联：当攻击者从LLC中驱逐一行时，硬件会自动使该行在受害者的L2和L1缓存中失效。这放大了时间信号，使信息泄露更清晰，侧信道攻击更有效。一个为性能而设计的特性，无意中变成了间谍活动的工具。
从加速算法到促成侧信道攻击，缓存层次结构证明了一个简单而强大的思想所带来的深远且常常出人意料的后果。它的原则是一条贯穿现代计算机科学几乎所有方面的统一线索，是性能、正确性和安全性的无声仲裁者。理解缓存，就是理解驱动我们数字世界的那个深刻、复杂而美丽的机器。