缓存如何工作：一个非常具体的解释

随着技术进步，处理器速度迅速提升，但内存速度却没有跟上。无论处理器多快，如果内存响应缓慢，整个系统最终都会变慢。解决这个问题的设备就是缓存（cache）。

缓存是位于 CPU 芯片内部的一小块高速存储器（同时也很昂贵）。每次都到主内存取数据很慢，因此缓存会保存经常使用的数据，让处理器可以直接从缓存而非主内存访问它们，从而提高速度。

局部性原理

判断哪些数据“经常使用”，遵循的是局部性原理（principle of locality）。它可以分为时间局部性和空间局部性。

时间局部性是指，最近访问过的数据往往会被再次访问。例如，作为循环索引的变量 i 会在很短的时间内被访问多次。

for (i = 0; i < 10; i += 1) {
  arr[i] = i;
}

空间局部性是指，最近访问的数据周边的空间，往往也会很快被访问。在上面的循环中，程序逐个引用数组 arr 的元素，也就是连续访问临近的内存位置，因为数组元素在内存中是连续分配的。

即使在同一个进程内，也有些部分常被使用，有些部分很少被使用。因此，操作系统将进程划分为页（page）进行管理。页引用轨迹的横轴是执行时间，纵轴是内存地址：水平方向的连续引用表示同一内存地址被长时间反复引用，垂直方向的连续引用则表示在同一时间访问了相互靠近的内存地址。由此可以看出，页访问同样遵循局部性原理。

缓存层级

一颗 CPU 芯片中包含多级缓存，各自有不同用途和角色。

+-------------+------+------+     +---------------+     +--------+
|             |  I$  |      | <-- |               | <-- |        |
+  Processor  +------+  L2  |     |  Main Memory  |     |  Disk  |
|             |  D$  |      | --> |               | --> |        |
+-------------+------+------+     +---------------+     +--------+

• L1 Cache：距离处理器最近的缓存。为了提高速度，它分为 I$ 和 D$。
  • Instruction Cache（I$）：处理内存 TEXT 段数据的缓存。
  • Data Cache（D$）：处理 TEXT 段以外所有数据的缓存。
• L2 Cache：容量更大的缓存。为了容量，它不像 L1 那样拆分。
• L3 Cache：多核系统中由多个核共享的缓存。

如今，缓存占据一颗 CPU 芯片面积的 30% 至 70%。1989 年生产的单核处理器 i486 只有一个 8KB I/D 缓存。相比之下，Intel Core i7 四核芯片的裸片图显示，四个核心各自拥有 256KB L2 缓存，所有核心还共享一个 8MB L3 缓存。（L2 上方的区域看起来像 L1 缓存，但作者无法确定，因此没有标注。）

缓存指标

衡量缓存性能时，命中延迟（hit latency）和缺失延迟（miss latency）是两个重要因素。

当 CPU 请求的数据位于缓存中时，称为缓存命中（cache hit）。命中延迟是命中时取得缓存数据所需的时间。当请求的数据不在缓存中时，称为缓存缺失（cache miss）。缺失延迟是缺失时从更高层缓存或内存取得数据的时间；例如 L1 中没有数据时，继续在 L2 中查找。

平均访问时间计算如下：

缺失率 = 缓存缺失次数 / 缓存访问次数
平均访问时间 = 命中延迟 + 缺失率 × 缺失延迟

要提高缓存性能，可以缩小缓存以降低命中延迟，扩大缓存以降低缺失率，或者使用更快的缓存来降低延迟。

缓存组织方式

缓存由响应快速的 SRAM（Static Random Access Memory，静态随机存取存储器）构成，给定地址作为键，就能立即访问对应位置。DRAM（Dynamic Random Access Memory，动态随机存取存储器）也具有这种特性，但由于硬件设计不同，DRAM 比 SRAM 慢。人们所说的“主内存”通常指 DRAM。

给定地址作为键便能立即访问某个位置，这意味着缓存本质上是一张用硬件实现的哈希表。缓存快，一方面是因为它只保存经常使用的数据，另一方面则是因为哈希表的时间复杂度很低，为 O(1)。

缓存由多个块（block）组成。每个块保存数据，并可以用地址作为键来访问。块的数量和块大小共同决定缓存的容量。

索引

缓存不会把整个地址都用作键，而是只使用其中一部分。例如，对于拥有 1,024 个块、每块 32 字节的缓存，可以按下图对 32-bit 地址建立索引。

完整地址的低 5 bit 用作偏移，接下来的 10 bit 用作索引来访问某个块。之所以索引为 10 bit，是因为要表示 2^n 个块的所有索引，需要 log₂(blocks) bit。这里有 2^10 = 1024 个块，而 log₂(1024) = 10，因此使用 10 bit 作为索引。（偏移位稍后再解释。）

不过，如果只做到这一步，不同数据共用同一索引的风险会非常高。

标签匹配

为减少索引冲突，地址的一部分会用作标签（tag）。假设缓存有 1,024 个块，块大小为 32 字节，现在访问 32-bit 地址 0x000c14B8：

1. 先访问标签数组中与索引 0010100101 对应的字段。
2. 检查该标签字段的有效位（valid bit）。
3. 如果有效位是 1，比较标签字段 00000000000011000 和地址标签 00000000000011000 是否相等。
4. 对比较结果（true、1）和有效位（1）执行 AND 运算。

有效位为 1 表示该块中存在正确的值。在上面的例子中，标签字段与地址标签相同，有效位又是 1，因此结果是命中。命中时，从数据数组中引用该索引下的数据。（数据数组和标签数组都是硬件。）

如果有效位是 0，表示该块中没有值或其值无效，因此发生缺失。此时，把地址的标签写入标签字段，从更高层缓存或内存取得请求的值并写入数据字段，然后把有效位改为 1。

即使有效位是 1，标签不匹配时也会发生缺失。处理方式取决于替换策略。如果使用 FIFO（First-In First-Out，先进先出）策略，即最早进入的数据最先被替换，那么现有块会始终被替换。标签数组字段改为当前地址的标签，从更高层缓存或内存取得请求的数据，再用新数据替换数据字段中的值。实际上不仅会取回请求的数据，还会取回它周围的数据。现有数据则被推向更高层缓存。

地址高位中用作标签的 bit 数按下式决定：

标签位数 = 地址位数 − (log₂(块大小) + 索引位数)

在本例中，32 - (5 + 10) = 17，因此 17 bit 用作标签，剩下 5 bit 用作偏移。

标签开销

添加标签数组意味着需要更多空间。不过，“32KB 缓存”仍然指能够保存 32KB 数据的缓存，因为标签所占的空间被视为独立于块大小的额外开销。

以由 1,024 个 32B 块组成的 32KB 缓存为例，其标签开销为：

17 bit 标签 + 1 bit 有效位 = 18 bit
18 bit × 1024 = 18 Kb 标签 = 2.25 KB

也就是说，标签产生了 7% 的空间开销。

除了空间成本，还有时间成本。如果先访问标签数组检查是否命中，然后才访问数据数组取得数据，命中延迟会增加。因此这两个步骤会并行执行：在标签数组中检查命中的同时，提前访问数据数组。这会降低命中延迟，但发生缺失时则必须接受资源被浪费的代价。

相联缓存

当两个不同地址拥有相同索引时，会发生冲突，并按照替换策略替换某个块。但如果每次冲突都更换缓存内容，会造成更多缺失，还可能出现乒乓问题（ping-pong problem）：同一槽位中的内容被无休止地换出。

创建多组标签数组和数据数组可以改善这个问题，也就是让一个索引指向多个块。按照一个索引指向的块数量，缓存可分为：

• 直接映射（direct mapped）：索引只指向一个槽位。处理快，但容易发生冲突。
• 全相联（fully associative）：索引指向所有槽位。冲突少，但因为必须搜索每个块，所以速度慢。
• 组相联（set associative）：索引指向两个或更多槽位，称为 n-way 组相联缓存。

直接映射和全相联缓存的优缺点都很极端，因此通常使用组相联缓存。

组相联缓存的组织方式

下图简要展示了 2-way 组相联缓存的工作方式。

通过地址索引访问块的方式，与前面看到的直接映射缓存相同。区别在于现在有两路（way），因此检查数据是否已被缓存时，要同时检查两个块，而不是只检查一个。最后对两路的结果执行 OR 运算，得到最终结果。如果每一路都缺失，便按照替换策略把数据写入两个块之一。

与直接映射缓存相比，这种设计用更高的命中延迟，换取了更低的冲突概率。

一个具体例子

假设我们有一个 8 字节的 2-way 缓存，由 2 字节的缓存块组成，并且给定一个 4-bit 地址。

一条引用内存地址 0001 的指令开始执行。索引位数为 log₂(2) = 1，标签位数为 4 - (log₂(2) + 1) = 2，最后的偏移位数为 1。因此，地址 0001 的索引是 0，标签是 00。这意味着该内存位置的数据可以缓存在索引为 0 的两个槽位之一。

因为 Way 0 中的块是空的，数据被保存到 Way 0 中索引为 0 的块。同时还缓存了地址 0010，因为为提高缓存命中率，内存数据会以一个完整缓存块（2B）为单位取回，这利用了空间局部性。所以，与被引用数据 0001 相邻的 0010 也被一起缓存。

接着，一条引用内存地址 0101 的指令开始执行。这个地址同样可以放入索引为 0 的两个槽位之一。

但 Way 0 中索引为 0 的块已经有数据，所以新数据被缓存到仍为空的 Way 1 中。同样，相邻的 0110 也被一起缓存。Way 0 中两个块的 LRU（Least Recently Used，最近最少使用）值也增加了。LRU 是优先替换较少在近期被使用数据的策略，它也用于操作系统的进程调度和页面替换算法。LRU 值越高，表示缓存缺失时该块越可能最先被替换。

随后，一条引用内存地址 1000 的指令开始执行。缓存检查了索引为 0 的两个块，但都没有标签为 10 的数据，因此发生缓存缺失。

于是，现有缓存数据将被替换。两个槽位中，Way 0 的块具有更高的 LRU 值，因此 Way 0 中的第一个块被替换；由于它现在被引用，其 LRU 值重置为 0。发生缓存命中时，LRU 值也会重置。基于同一原理，与被引用数据相邻的 0111 也被一起缓存。Way 1 中的两个块这次没有被引用，所以它们的 LRU 值上升。

处理缓存写入

当操作不是读取而是写入，且要修改的地址已被缓存时（写命中），更新的是缓存块中的数据，而不是内存中的数据。于是产生一个问题：缓存中已更新的数据应该什么时候写回内存？这里有两种写入策略。

第一种是写通（write-through）：每次数据写入缓存时，也同时更新内存中的数据。这会产生大量流量，但能使内存和缓存中的数据保持一致。

第二种是写回（write-back）：只有当缓存块被替换时，才更新内存中的数据。为判断数据是否改变，每个缓存块都需要增加一个脏位（dirty bit），数据改变时把它设为 1。之后当该块被替换时，如果脏位为 1，就更新内存中的数据。

如果要修改的数据地址并未被缓存（写缺失），则使用写分配（write-allocate）方式：缺失时将数据载入缓存。跳过写分配虽然会暂时节省资源，但也无法实现缓存的目的。

软件重构

到目前为止，我们都在从底层观察缓存的结构和行为，但也可以在代码层面提高缓存效率。先看下面的嵌套循环：

for (i = 0; i < columns; i += 1) {
  for (j = 0; j < rows; j += 1) {
    arr[j][i] = pow(arr[j][i]);
  }
}

这段循环对二维数组的每个元素求平方。看起来没有问题，但从空间局部性的角度看，这段代码效率很低，因为数组 arr 的元素在内存中连续存放，但实际访问顺序却不连续。

0          4          8          12         16         20         24
+----------+----------+----------+----------+----------+----------+
|  [0, 0]  |  [0, 1]  |  [0, 2]  |  [1, 0]  |  [1, 1]  |  [1, 2]  |
+----------+----------+----------+----------+----------+----------+

1. i = 0、j = 0：访问第一个槽位 [0, 0]。
2. i = 0、j = 1：访问第四个槽位 [1, 0]。
3. i = 1、j = 0：访问第二个槽位 [0, 1]。

可以看到，访问在内存中四处跳跃。因此，应该像下面这样，让外层循环遍历 rows，内层循环遍历 columns。

for (i = 0; i < rows; i += 1) {
  for (j = 0; j < columns; j += 1) {
    arr[i][j] = pow(arr[i][j]);
  }
}

利用时间局部性也有一个类似的例子。请看下面的循环：

for (i = 0; i < n; i += 1) {
  for (j = 0; j < len; j += 1) {
    arr[j] = pow(arr[j]);
  }
}

这段嵌套循环把“对数组 arr 中的每个元素求平方”这个操作重复 n 次。按照现有写法，无法保证某份数据被缓存后，下一次访问能再次命中它。如果整个数据集比缓存大，遍历数组时就会出现下图所示的情况。

循环前半段会缓存一部分数据，但等循环结束时，这些缓存已被后半段访问的数据覆盖。因此，第二轮遍历时，前半段数据必须重新缓存。也就是说，在已缓存数据得到再次访问之前，整个缓存块就已被替换。可以将数组的遍历周期分割成与缓存大小相同的块，从而解决这个问题。

循环次数增加了，但缓存命中率也提高了。前三轮只处理前半部分数据，之后再只处理后半部分数据。写成代码，它会变成一个三重循环：

for (i = 0; i < len; i += CACHE_SIZE) {
  for (j = 0; j < n; j += 1) {
    for (k = 0; k < CACHE_SIZE; k += 1) {
      arr[i + k] = pow(arr[i + k]);
    }
  }
}

当然，如今编译器会负责这些优化，应用开发者并不需要操心这类事情。只要知道“代码可以在底层像这样优化”，大概就足够了。

参考资料

• David Patterson, John Hennenssy, Computer Organization and Design 5th Ed., MK, 2014.
• Abraham Silberschatz, Peter Galvin, Greg Gagne, Operating System Concepts 9th Ed., Wiley, 2014.
• K. G. Smitha, Para Cache Simulator.

原文以 CC BY-NC 4.0 许可证发布。