玻尔百科在现代计算中，处理器的速度从根本上与其内存系统相关联，其中多级缓存层次结构是连接 CPU 与慢速主存的关键桥梁。在这些级别之间高效地管理数据——从小型、快速的 L1 缓存到更大的末级缓存（LLC）——对性能至关重要。这引出了一个基本的设计问题：较低级别缓存中的数据是否也应存在于较高级别的缓存中？这种在“包容性”和“排他性”策略之间的选择，不仅仅是一个技术细节，更是一个具有深远影响的深层架构权衡。本文剖析了这一关键选择，探讨了在容量、复杂性和速度之间的精妙平衡。第一章“原理与机制”将分解每种策略的核心机制，分析它们对有效容量、性能以及多核系统中一致性的影响。随后的“应用与跨学科联系”将揭示这一个设计决策如何向外扩散，影响从软件同步和硬件预取到系统安全和算法设计的方方面面。
在计算机处理器的宏大舞台上，数据扮演着主角，而缓存则是其众多的更衣室。访问主存就像一次漫长而缓慢的返回拖车的旅程，而访问缓存则像在舞台边上快速换装。整个系统的性能取决于能否在正确的时间将正确的数据保存在正确的缓存中。但这引出了一个非常简单而深刻的问题：如果我们有多级缓存——比如说，一个小型、闪电般快速的 1 级（L1）缓存和一个更大、稍慢的 2 级（L2）缓存——它们应该如何组织其内容？较小缓存的内容应该是较大缓存一小部分的镜像，还是应该完全不同？
这不仅仅是一个整洁与否的问题；它是在两种对立的数据管理哲学之间的根本选择：包容性（inclusion）和排他性（exclusion）。理解这一选择揭开了计算机体系结构中关键的一层，展现了一幅在空间、速度和复杂性之间权衡取舍的精美画卷。
让我们想象你是一个在工作室里的木匠。你面前有一个小而整洁的工作台（L1 缓存），几步之外有一个大工具箱（L2 缓存）。
包容性哲学规定，你工作台上的任何工具也必须在你的工具箱里有一个预留的位置。如果你的工作台上有把锤子，那么工具箱里也有一个锤子形状的空位，在某种意义上也被占用了。这非常有条理。要找到你拥有的任何工具，你只需要查看大工具箱；如果不在那里，你就没有这个工具。缺点是什么？工具箱里被工作台上已有工具的复制品占用的空间，无法用于存放其他不同的工具。你手头能准备的独一无二的工具总数受限于工具箱的大小。
排他性哲学在空间上更为节俭。你的工作台和工具箱里存放着完全不同的工具。如果你想从工具箱里拿一把螺丝刀，你必须通过把（比如说）锤子放回工具箱来为你的工作台腾出空间。你总是在交换。巨大的优势在于没有空间浪费在复制品上。你可用的独一无二的工具总数是你工作台容量和工具箱容量的总和。
将此转换回缓存，包容性层次结构坚持 L1 中的数据块集合（）必须是 L2 中数据块集合（）的子集，写作 。而排他性层次结构，在其理想形式下，要求它们的内容是不相交的，。这导致了有效容量上的显著差异。对于一个拥有大小为 的 L1 缓存和大小为 的 L2 缓存的包容性系统，它能容纳的唯一数据总量仅为 。而对于一个排他性系统，有效容量是 。
这看似一个抽象的差异，但其性能影响可能令人震惊。考虑一个程序，它需要处理的数据集比 L2 缓存稍大一些。假设我们的 L1 能容纳 512 个块，L2 能容纳 4096 个块，而我们程序的工作集是 4300 个块。
在一个包容性系统中，总容量是 4096 个块。4300 个块的工作集根本放不下。随着程序运行，它将不断地驱逐它稍后就需要的数据。几乎每次访问都会在 L1 和 L2 中都未命中，迫使从主存进行慢速读取。性能是灾难性的。
在一个排他性系统中，总容量是 个块。4300 个块的工作集可以轻松容纳！经过一个初始的预热期后，每一次访问都将会在 L1-L2 层次结构的某个地方命中。速度上的差异不仅仅是几个百分点；这是一个系统在优雅执行与一个永久停滞的系统之间的区别。
这种容量优势对于混合工作负载变得更加关键。想象一个程序，它处理一个永久存在于 L1 中的小型“热”数据集，同时又流式处理一个大型“冷”数据集。在一个包容性的 L2 缓存中，其宝贵容量的一部分被这个热数据集的无用副本永久占用。这减少了可用空间，可能导致空间太小而无法容纳流式处理的冷数据集，从而引发持续的 L2 未命中。然而，排他性的 L2 缓存将其全部容量用于冷数据集，有可能将一场颠簸的噩梦变成一次平稳的旅程。
那么，既然有如此明显的容量优势，为什么不是每个缓存都是排他性的呢？因为，俗话说，“天下没有免费的午餐”。排他性设计的优雅之处伴随着其自身的一系列成本。
最直接的成本是交换（swap）。在包容性缓存中，一次在 L2 命中但在 L1 未命中的情况很简单：数据从 L2 复制到 L1。在排他性缓存中，同样的事件会引发一个更复杂的舞蹈。被请求的块从 L2 移动到 L1，为了腾出空间，必须从 L1 中驱逐一个“受害者”块并将其移入 L2。这个交换操作需要更多时间，并给本应是快速的 L2 命中增加了开销。排他性缓存中的 L2 命中实际上可能比包容性缓存中的 L2 命中更慢。
这就产生了一种引人入胜的性能张力。排他性缓存更善于避免访问主存的灾难，但它为其一些成功的缓存命中支付了一点小小的税。总体收益取决于哪种效应占主导。我们可以用一个优美的数学表达式来描述排他性缓存相对于包收性缓存的性能增益（）：
让我们来分解一下。 是 L1 的未命中率。增益只在 L1 未命中时才重要，所以所有东西都按此比例缩放。在括号内，我们看到了这场战斗。项 是收益： 是排他性缓存的 L2 命中率， 是包容性缓存的 L2 命中率。由于排他性缓存容量更大，所以 通常高于 。这个差值 代表排他性设计避免了访问主存的那部分内存访问，每次节省了 的时间。这是巨大的回报。项 是惩罚：在所有 的排他性 L2 命中上，我们都要支付交换开销的税，。 是否为正（对排他性缓存有净增益）取决于避免内存访问带来的巨大节省是否超过了交换所累积的微小成本。
我们甚至可以将其进一步推广。想象一个系统，其中有应用程序缓存和操作系统页面缓存，我们可以选择包容性或排他性策略。只有当排他性策略的交换开销 低于某个阈值时，它才更好。这个阈值是多少？可以证明，最大可容忍开销 由一个非常直观的公式给出：
更正式地，使用一个栈距离模型，其中 是访问的重用距离小于或等于 的概率：
分子，，是访问恰好命中于排他性设计提供的“额外”容量的概率，从而节省了一次时间为 的慢速磁盘访问。这是总收益。分母，，是在二级缓存中命中的概率，这正是支付交换成本的时候。这个公式精美地表达了每次交换可接受的成本取决于你为每次执行的交换避免了多少次灾难性的未命中。
差异不仅仅在于容量和交换时间。策略的选择从根本上改变了缓存级别之间的关系。
在一个排他性层次结构中，L1 缓存是自己的主人。它的命中率和未命中率由其自身的大小和程序的行为决定。增大或减小 L2 缓存的大小对某次访问是否在 L1 中命中或未命中没有直接影响。这些层级之间实现了美妙的解耦。
而包容性层次结构则创建了一种紧密、有时甚至是麻烦的耦合。包容性规则（）有一个强大的推论：如果一个块从 L2 中被驱逐，它必须也从 L1 中被移除以维持该属性。这被称为反向失效（back-invalidation）。想象一下 L2 缓存控制器，为了腾出空间而驱逐一个块。然后它向 L1 发送一个命令：“丢掉块 X。” 即使块 X 是 L1 中最近使用的项，这种情况也可能发生！
来自下层的这种干扰有效地降低了 L1 管理其自身内容的能力，缩小了其有效容量。一个有趣的后果是，在包容性系统中，增加 L2 缓存的大小可以降低 L1 的未命中率。一个更大的 L2 驱逐块的频率较低，这意味着它发送的破坏性反向失效命令更少，从而让 L1 更有效地完成其工作。这种微妙的连锁反应是包容性契约的直接后果。
当我们从单个处理器转向拥有多个核心、共享末级缓存（LLC）的现代芯片时，情节变得戏剧性地复杂起来。现在，“数据在哪里？”的问题变成了一个系统范围内的一致性（coherence）问题。
在一个包容性系统中，共享的 LLC 充当了一个中央信息交换所。如果核心 3 想要读取一块数据，它会检查 LLC。LLC 的目录不仅知道数据是否存在，还知道哪些其他核心可能拥有副本。搜索是有界且有序的。这个记录共享者的目录只需要管理物理上存在于 LLC 中的块的条目。
在一个排他性系统中，混乱迫在眉睫。核心 3 想要的数据可能在 LLC 中，也可能藏在核心 1 的私有 L1 缓存里，或者核心 7 的私有 L2 中。没有一个单一的地方可以查找。目录现在必须跟踪整个系统中每个缓存块的位置，无论它是在 LLC 中还是在众多私有缓存中的任何一个。
这对目录存储开销（directory storage overhead）产生了毁灭性的影响。对于包容性缓存，目录大小与 LLC 的大小成比例。对于排他性缓存，目录不仅需要存储共享者信息，还需要存储所有专属于私有缓存的块的完整地址标签。这种额外的存储可能相当可观。更糟糕的是，排他性系统的目录大小可能与核心数量（）的平方成比例，而包容性系统则与 呈线性关系。对于拥有数十或数百个核心的芯片来说，这种二次方扩展的成本可能会变得高得令人望而却步。
此外，包容性策略尽管有其他缺陷，但在多核系统中有一个隐藏的好处。当 LLC 驱逐一个被多个核心共享的块时，它发出的反向失效强制执行了一个干净的、系统范围的状态。在排他性系统中，这种清理不是自动的，这给一致性协议增加了又一层的复杂性。
因此，这是一个深刻的选择。排他性提供了更多有效容量的诱人前景——一个简单而强大的想法。但随着我们扩展到多核世界并面临其复杂性时，包容性设计的简单和有序，尽管其表面上看起来很浪费，却为缓存一致性这个极其复杂的问题提供了一个更易于管理的基础。从一个简单的工作台到核心林立的繁忙工厂，一切都改变了。
既然我们已经探讨了包容性和排他性缓存的原理，我们就可以开始认识到，这种设计选择远非处理器蓝图中的一个纯粹的技术注脚。这是一个根本性的决定，它会在整个计算系统中引发连锁反应，影响从原始性能和功耗到软件设计、系统公平性，甚至对网络攻击的脆弱性等方方面面。就像在一个玩具宇宙中选择基本法则一样，强制执行包容性属性——或不执行——会产生一连串的后果，揭示了计算机体系结构中美妙而错综复杂的相互联系。没有单一的“正确”选择；只有权衡，而理解这些权衡正是计算机设计艺术如此引人入胜的原因。
让我们从最直接和最具体的影响开始。从核心上讲，包容性与排他性之间的选择是在有序性与效率之间的权衡。
想象一个小程序，它的工作集——即它在任何时刻需要的数据——刚好比一个核心的私有缓存大一点。对于包容性层次结构，其中共享的末级缓存（LLC）必须包含私有缓存中所有内容的副本，该层次结构能容纳的唯一数据块总数受限于最大缓存——LLC 的大小。如果我们的程序工作集对于一组给定的冲突地址超过了 LLC 的容量，系统就会开始“颠簸”（thrash）：它不断地从 LLC 中驱逐数据，结果片刻之后又需要这些数据，导致一场慢速内存访问的风暴。
现在，考虑一个排他性缓存。在这里，LLC 更像是一个溢出区域，或者是从私有缓存中被驱逐数据的“受害者缓存”（victim cache）。总有效容量是私有缓存和 LLC 的总和。同样是那个程序，其工作集对包容性 LLC 来说有点太大了，但现在可能完美地容纳在私有缓存和排他性 LLC 的组合空间内。通过避免重复，排他性缓存提供了更大的有效存储空间，将一场颠簸的噩梦变成了一次平稳高效的执行。这种效应不仅仅是理论上的；通过精心构建的访问模式可以证明这一点，这些模式会瘫痪一个包容性缓存系统，但在排他性系统上却能完美运行。
但这种额外的容量是以复杂性为代价的。包容性缓存，尽管有其容量限制，却有一种优雅的简单性：要找到一块数据，你只需检查 LLC。如果它不在那里，那它就不在芯片上的任何地方。然而，这种有序性也产生了其自身的性能代价。为了维持严格的包容性属性，每当一个缓存行从 LLC 中被驱逐时，系统必须向所有私有缓存发送“反向失效”消息，以确保没有副本被遗留。这些消息并非没有成本；它们在芯片的互连上产生了额外的相干性流量。虽然每条消息可能只给内存访问延迟增加几分之一周期，但当乘以数十亿次操作时，这种开销可能导致整体性能的明显下降，表现为更高的平均内存访问时间（AMAT）和每指令周期数（CPI）。
包容性系统中这种更紧密的耦合也可能导致性能更不可预测。在多核处理器中，一个核心的内存访问模式可能会干扰另一个核心。一个核心上激进的应用程序可能会导致共享 LLC 中发生大量驱逐。在包容性系统中，这些驱逐会触发一连串的反向失效，这些失效会“伸入”另一个核心的私有缓存，使其正在积极使用的数据失效。这给受害核心带来了突发、意外的性能尖峰，使得系统性能变得不稳定且更难预测。排他性缓存由于缺少这种反向失效机制，能更好地将私有缓存与 LLC 的驱逐压力隔离开来，从而带来更稳定、可预测的行为。
现代处理器不仅仅是一个简单的缓存层次结构；它们是一个由相互作用的组件组成的复杂生态系统。缓存策略的选择对这些其他组件的行为有着深远的影响。
考虑硬件预取器（hardware prefetcher），它是一个聪明的助手，试图猜测程序接下来需要哪些数据，并提前将其取入缓存。当预取器猜对时，性能会飙升。但如果它猜错了呢？对于包容性 LLC，一个过于激进或不准确的预取器可能成为一种负累。想象一个核心上的预取器用无用的数据淹没了一个共享的 LLC 集合。这种“预取污染”可能会取代属于另一个核心的有用数据。这个有用数据从 LLC 中被驱逐，接着触发反向失效，将其从受害核心的私有缓存中清除。结果是，一个核心出于好意但被误导的预取器主动损害了另一个核心的性能——在非包容性系统中，这种情况不会发生，因为 LLC 的驱逐不会自动使私有缓存行失效。
这种意外交互的主题延伸到了计算中最基本的挑战之一：同步。当多个核心需要协调对共享资源的访问时，它们通常使用“自旋锁”（spin lock）。使用测试并设置（Test-and-Set, TAS）指令的简单实现会导致每个等待的核心反复尝试对锁变量进行写操作。在一个缓存一致性系统中，每次尝试都需要获得缓存行的独占所有权，导致当缓存行在核心之间疯狂传递时，出现大规模的“失效风暴”。在这里，缓存策略决定了这场风暴的路径。对于包容性 LLC，所有这些疯狂的流量都必须通过中央 LLC，可能会使其带宽饱和。而排他性缓存则允许更直接的核心到核心的热点缓存行传输，使流量风暴远离 LLC，并为其保留带宽用于其他更有用的工作。这种流量路径的微妙差异可能对并行软件的可扩展性产生重大影响。缓存策略的选择甚至影响了更好的锁算法的设计，如测试-测试-并-设置（TTAS），这些算法专门设计用来最小化这种失效流量。
现代处理器特性的精妙本质或许可以通过硬件事务内存（HTM）得到最好的说明。HTM 允许程序员将一个代码块作为单个原子“事务”来执行，该事务要么完全完成，要么被中止并回滚。事务是一种脆弱的、推测性的操作，就像一座纸牌屋。它维护着一个它所接触过的所有内存位置的“读集”。如果在事务完成前，这些行中的任何一行被驱逐或失效，事务就会中止。包容性 LLC 引入了一种毁灭性的新失败模式。如果一个事务读取了大量项目，而这些项目恰好都映射到共享 LLC 的同一个集合中，LLC 集合就会溢出。这会导致 LLC 的驱逐，进而触发反向失效，杀死私有缓存中的读集行，导致事务中止。相比之下，排他性 LLC 提供了私有缓存的全部容量来跟踪读集，而没有这种由 LLC 引起的冲突，为事务的成功提供了更多的“喘息空间”[@problem__id:3645895]。
缓存设计的后果甚至超越了性能，延伸到公平性、安全性和甚至抽象算法设计的领域。
在异构计算的世界里，处理器经常将强大的“大”核与高效的“小”核配对。这些核心频繁共享缓存层次结构的部分。当它们共享一个包容性缓存时会发生什么？包容性属性规定，共享缓存必须“保留”空间来存放私有 L1 缓存中所有内容的副本。由于大核的 L1 缓存比小核大得多，它含蓄地占据了共享缓存容量中更大、不成比例的份额。这可能会使小核缺乏共享缓存资源，仅仅因为强制执行包容性这一副作用而不公平地惩罚其性能。排他性缓存避免了这个问题，自然而然地创造了更公平的资源共享。
也许缓存包容性最令人惊讶的后果在于计算机安全领域。我们已经看到的反向失效机制，作为一种性能开销，可以被转变为一种武器。在“刷新+重载”（Flush+Reload）旁路攻击中，攻击者通过计时自己的内存访问来推断受害者的与秘密相关的内存访问。 “刷新”步骤涉及驱逐一个共享缓存行。对于包容性 LLC，这是毁灭性地有效：从 LLC 驱逐该行保证了它通过反向失效从受害者的私有缓存中被移除。“重载”步骤如果受害者没有访问该行则会很慢，如果访问了则会很快。讽刺的是，排他性缓存由于更“混乱”，允许一个行即使从 LLC 中被驱逐后仍能停留在受害者的私有缓存中，这使得这种攻击更难执行。包容性缓存的干净、有序的特性变成了一个安全漏洞。
最后，缓存策略的影响一直延伸到高性能数值算法的设计。考虑像高瘦 QR 分解（Tall-Skinny QR, TSQR）这样的算法，它用于科学计算中对大型矩阵进行因式分解。这些算法被设计为“通信避免型”，仔细管理哪些数据驻留在内存层次结构的小而快速的层级中。每一步的内存占用至关重要。一个包容性缓存，由于其数据的重复，对于给定的操作可能比排他性缓存有显著更大的内存占用。对于算法设计者来说，这意味着在一台具有包容性缓存的机器上，你可能需要一个大得多的快速内存来达到相同的性能，或者你可能被迫使用一个更深、更慢版本的算法。这表明，超级计算机的架构师和为它们设计算法的数学家生活在同一个世界里，受到同样的基本权衡的约束，甚至细致到缓存包容性的选择。
从一个简单的规则——“复制还是不复制？”——一个完整的后果宇宙就此展开。缓存排他性的选择证明了一个深刻的原则：在任何复杂的、统一的系统中，没有孤立的决策。每一个选择，在任何地方，都很重要。