Cache 映射策略：直接映射、组相联与全相联

上一篇已经知道，Cache 能发挥作用，核心在于局部性原理。但如果继续往下问，就会遇到一个非常现实的问题：

主存里有那么多数据块，而 Cache 容量又这么有限，某个主存块到底该放到 Cache 的哪个位置上？

这就是 Cache 映射策略要解决的问题。

它不是一个细枝末节，而是直接决定了 Cache 的组织方式、实现复杂度、命中率表现和访问速度。很多时候，Cache 性能好不好，不只是看容量大小，还要看“怎么放”。

一、为什么 Cache 需要映射策略

因为主存通常远远大于 Cache。

这意味着：

  • 主存中可被访问的数据块数量非常多；
  • Cache 中能容纳的位置非常少；
  • 不可能让每个主存块都固定拥有一个独占位置；
  • 必须规定一套规则，决定“哪些块可以放在哪些地方”。

如果没有这套规则，CPU 访问时就不知道该去哪里查找，硬件也无法组织索引和替换逻辑。

所以映射策略本质上是在回答两个问题：

  • 一个主存块允许放到哪些 Cache 位置；
  • CPU 访问某地址时，应该如何快速判断它在不在 Cache 中。

二、为什么映射策略会影响性能

因为不同映射策略在几个关键维度上会有明显差异：

  • 查找速度；
  • 冲突概率；
  • 硬件复杂度；
  • 替换灵活性。

有的策略实现简单、访问很快，但容易发生冲突；有的策略更灵活，命中率可能更好，但实现成本更高。

所以它本质上是一次典型的体系结构取舍：

用多少硬件复杂度，换多少访问效率和命中率收益。

三、理解映射策略前，先抓住“块”和“行”

讲映射时最容易绕，是因为“主存块”和“Cache 行”容易混。

可以先这样理解：

  • 主存按块 block 划分；
  • Cache 按行 line 或块槽位组织；
  • 当一次不命中发生时，通常是把一个主存块装进某个 Cache 行里。

所以映射策略，实际上是在规定：

某个主存块可以映射到哪些 Cache 行。

只要这句话抓住了，后面三种经典策略就容易多了。

四、什么是直接映射

直接映射是最简单的一种策略。它的核心规则是：

每个主存块只能映射到 Cache 中唯一确定的一个位置。

也就是说，主存块编号一旦确定，它能去的 Cache 行就唯一固定。

这样做的好处非常明显：

  • 地址分解简单；
  • 查找速度快；
  • 硬件实现成本低。

因为 CPU 只需要根据地址中的索引部分，直接定位到一个候选行，再检查标记位是否匹配即可。

五、直接映射为什么容易发生冲突

问题也恰恰出在“位置唯一”上。

如果两个不同的主存块恰好都映射到同一条 Cache 行，那么：

  • 它们不能同时存在于 Cache；
  • 后装入的会把前一个挤掉；
  • 如果程序反复交替访问这两个块，就会频繁 miss。

这种情况就叫冲突不命中。

所以直接映射的核心问题不是容量不够，而是：

放置自由度太低，容易让本可共存的数据彼此抢位置。

六、什么是全相联映射

全相联几乎走到了另一个极端。它的核心规则是：

任意主存块可以放到 Cache 中任意一行。

这意味着映射限制最少，灵活性最高。

好处是：

  • 冲突概率更低；
  • Cache 空间利用更灵活；
  • 替换策略更容易在全局范围做决定。

但代价也很明显：

  • CPU 查找时不能只看一个固定位置；
  • 必须在很多行中比较标记；
  • 硬件比较逻辑更复杂，代价更高。

所以全相联的核心优势是灵活，核心代价是贵。

七、什么是组相联映射

组相联是现实里非常常见的折中方案，可以理解成：

先把 Cache 分成若干组，每个主存块只能映射到某一组，但在组内可以放到任意一行。

这样一来：

  • 比直接映射更灵活；
  • 比全相联更容易实现；
  • 冲突情况和查找开销都处于中间位置。

如果每组只有 1 行，它就退化成直接映射；如果整个 Cache 只有 1 组，它就退化成全相联。

所以组相联本质上是在两个极端之间做平衡。

八、为什么组相联常被看成最实用的方案

因为它在工程上通常能取得不错的平衡：

  • 不像直接映射那样太容易冲突；
  • 也不像全相联那样比较逻辑代价太高；
  • 可以通过调整“每组几路”来控制复杂度和命中率。

例如常听到的 2 路组相联、4 路组相联、8 路组相联，本质上就是在说：

  • 每组允许同时放多少个候选块。

路数越高，一般冲突越少，但查找和硬件代价也会继续增加。

九、地址在不同映射策略下通常怎么拆分

虽然这里先不做复杂位数计算，但必须先建立基本直觉。

一个地址通常会被拆成几部分：

  • 块内偏移；
  • 索引或组号；
  • 标记 tag。

其中：

  • 偏移用于确定块内具体哪个字节或字；
  • 索引用于定位某一行或某一组；
  • 标记用于判断当前 Cache 中的候选项是不是你真正要的那个主存块。

直接映射和组相联都高度依赖这种地址拆分，而全相联通常索引最少、比较范围最大。

十、三种策略最本质的差异到底是什么

如果只抓一句话，可以这样记：

  • 直接映射：一个块只能去一个位置；
  • 组相联：一个块只能去一个组，但组内多个位置都行；
  • 全相联：一个块想去哪都行。

而对应的权衡则是：

  • 直接映射最简单最快，但冲突最多；
  • 全相联最灵活，冲突更少，但实现最复杂；
  • 组相联居中，因此最常见。

只要这组关系理解清楚，很多题和很多工程设计讨论都会一下变得顺畅。

十一、为什么映射策略和命中率直接相关

因为命中率不只是“Cache 有没有足够容量”的问题，还取决于：

  • 有容量时，数据能不能合理共存；
  • 热点块会不会因为映射冲突互相挤掉；
  • 程序访问模式是否刚好撞到映射弱点。

这也是为什么有些程序在同样容量下，换一种映射组织后表现会明显变化。

所以 Cache 不只是“空间大小问题”，也是“空间调度方式问题”。

十二、从工程角度看，这部分为什么重要

理解映射策略，会帮助你更自然地理解很多真实现象：

  • 为什么某些访问模式会莫名其妙地频繁 cache miss；
  • 为什么看起来容量够了，性能还是不好；
  • 为什么硬件设计不会无限追求最灵活的方案；
  • 为什么程序的数据布局和访问步长会影响缓存效果。

对后端和系统开发来说，这种理解会直接影响你对“缓存友好性”的直觉。

十三、学习这一部分最容易踩的坑

1. 只背三种名字，不理解“一个块能去多少位置”

这才是三种策略最核心的本质差别。

2. 误以为全相联一定绝对最好

命中率可能更有优势，但硬件成本和访问复杂度也更高。

3. 把冲突 miss 和容量不够混为一谈

有时候 miss 不是因为空间不够，而是因为允许放的位置太少。

总结

Cache 映射策略决定了主存块如何进入有限的 Cache 空间。真正值得先抓住的，是这些认识：

  • 映射策略本质上是在规定一个主存块能放到哪些 Cache 位置；
  • 直接映射最简单但冲突明显；
  • 全相联最灵活但硬件最复杂；
  • 组相联在灵活性和实现代价之间做平衡，因此最常见；
  • 映射策略会直接影响冲突不命中、访问效率和整体缓存表现。

把这一篇理解透之后，下一步再看写策略和替换算法，就会更容易知道：当 Cache 已经决定“放哪”，后面真正要解决的就是“怎么写”和“挤掉谁”。

参考资源：