计算机内存中的缓存Cache Memories

这篇写一下计算机系统中的缓存Cache应用场景和实现方式介绍。

Memory hierarchy

在讲缓存之前，首先要了解计算机中的内存结构层次Memory hierarchy。也就是下图金字塔形状的结构。

从上到下，内存层次结构如下：

寄存器：这是计算机中最快速的存储区域。它们位于处理器内，用于存储即将被处理器执行的指令和数据。
高速缓存（Cache）：位于处理器和主内存之间，用于存储最近或频繁访问的数据和指令。高速缓存有多级（L1、L2、L3），其中L1最接近处理器且速度最快，但也最小。
主内存（RAM）：当计算机运行程序时，程序的代码和数据被加载到主内存中。
硬盘驱动器（HDD）或固态硬盘（SSD）：这些是非易失性的存储设备，用于长期存储数据和程序。
网络存储和云存储：这些存储设备位于本地计算机之外，数据通常通过网络进行访问。

从上到下离CPU就越来越远，越往下的部分，容量往往越大，价格也越便宜；而越靠近CPU的部分，速度越快但是价格高且容量小。

Locality

局部性原理 (Locality of Reference) 是设计内存层次结构时需要考虑的重要因素，也是后面缓存为什么能够起作用的原因。

时间局部性（Temporal Locality）：如果一个数据或指令在某个时间点被访问，那么在未来的一段时间内，这个数据或指令可能会被再次访问。这是由于程序的执行往往具有重复性，例如循环和递归。高速缓存就是基于时间局部性设计的，将最近访问过的数据和指令存储在快速访问的缓存中。
空间局部性（Spatial Locality）：如果一个数据或指令被访问，那么在未来的一段时间内，其附近的数据或指令也可能会被访问。这是由于程序的执行通常具有连续性，例如顺序执行的指令和数组的元素。内存管理系统会将整个块（包含了访问数据或指令的附近地址）加载到高速缓存或主内存中，以利用空间局部性。

缓存Cache

如果我们把用过地址放在CPU里的存储单元，或者说一个更接近CPU、更能快速获取的地方，就有了我们广义概念上的“Cache”了。虽然这个地方很小，但基于locality的原理，程序倾向于使用之前的地址或者之前地址附近地址，每次CPU像访问数据，它都会优先从cache里查找（因为离得更近），如果是那种多次反复需要的数据，就可以直接让cache来提前处理了，提高数据获取速度。

当然，毕竟cache的位置有限，如果请求的数据没有在cache里（这叫做cache miss），就只能把cache中的数据删掉（比如最久没用的那个），然后把新数据从下面更慢的内存结构中获取后替换上去。

几种Cache miss

Cache miss主要有以下三种：

冷（强制）未命中（Cold or Compulsory Miss）
冷未命中是因为缓存开始时是空的，而这是对该块的第一次引用。换句话说，这是无法避免的未命中，因为当你第一次访问一个数据块时，它不可能已经在缓存中。
容量未命中（Capacity Miss）
当活动的缓存块集合（工作集）大于缓存的容量时，就会发生容量未命中。即使数据块之前已在缓存中，但由于缓存空间有限，可能已经被其他更近期访问的数据块替换出去。
冲突未命中（Conflict Miss）
前两个都比较好理解，这个冲突未命中比较复杂，我用通俗的语言讲大概是这样：比如我们教室有三排学生，每排都有一个椅子当作cache，那么我们cache一共有3个，学生有3排。这个时候如果规定每排学生只能用对应的一把椅子，就会发生conflict miss。比如第一排第一个同学有了一个行为，他被存储在了第一个椅子上；这个时候第一排第二个同学又有一个行为，我们只会用第二个同学去换下第一个同学——即使这个时候还有两把椅子是空的。当最后再次访问第一个同学时，你会发现明明第一个同学之前访问过，明明cache里有空位，但就是在cache里找不到他，这种情况下的miss就叫做conflict miss。

Cache的参数和大小表示

高速缓存（Cache）的总大小可以由以下三个参数描述：

S：缓存的集数（Set）。
E：每个集中的线数（Line），也就是每个集中的缓存块数量（Cache blocks per set）。
B：每个缓存块的大小（Size of each block）。

而Cache set就等于 S × E × B。

Cache的结构看起来这么麻烦，如何存储数据呢？对于一个数据，如cache会根据它的地址来划分和存储。

如上图所示，通常地址会被划分成3部分：块偏移量（block offset）、集索引（set index）和标签（tag）。

块偏移量（Block Offset）：这部分的位数取决于每个cache块（或行）的大小。例如，如果一个块的大小是16字节，那么块偏移量就需要4位（因为2^4 = 16），用于确定一个字节在其块中的位置。
集索引（Set Index）：这部分的位数取决于cache的集数。例如，如果有64个集，集索引就需要6位（因为2^6 = 64），用于确定一个块应该存储在哪个集中。
标签（Tag）：地址中剩下的位被用作标签，用于在cache查找过程中区分不同的内存块。

所以对于一个地址，大致的查找流程是这样的：首先进行地址分割，就像上面说的那样分成三部分；其次拿着集索引去cache中找到对应的集，拿到了这个集（可以理解成图里的一整行蓝色背景，包含很多line），我们查找所有line（通常会并行查找来提高速度），找到那个line，which有效位（valid bit）是1以及tag标签和地址划分出来的tag部分一样，如果找到了，则使用块偏移量从这个集中取出所需的数据。

再举个例子，在上面这个图中， block块大小是8，因此我们需要3个位作为block offset，这里offset是100也就是4，那么数据到时候会从第4位开始，也就是图中绿色块部分；集的个数不知道，集索引的位数也不确定，但这里0...01不管中间几个0，都是1，表示对应第一个集。在剩下的部分就是两个红色部分的tag比较了。

用这句话来检查一下你是否理解：这里虽然得到的块偏移量是4，但是你可以发现我们把4往后的部分也都放在cache里了（绿色部分）。因为这样的话如果下次访问这个同样的地址+1，按找那套流程算下来其实直接就对应块偏移量为5的部分，直接就在cache里了！这就是cache对Spatial Locality也友好的地方——不止是之前访问过的我有，之前访问过的邻居我也有！

Cache的写操作

当我们讨论写操作（write operations）在缓存系统中的行为时，我们需要考虑两种基本的情况：写命中（write hit）和写未命中（write miss）。在处理这两种情况时，有几种常见的策略：

1 写命中（Write Hit）：当我们试图写入的数据已在缓存中时，我们有两种基本策略：
- 写直达（Write-Through）：这种策略立即将更改写入到主存储器和缓存中。这种策略的优点是它保持了主存储器和缓存中的数据一致性，但缺点是每次写操作都需要访问主存储器，这可能会带来较大的性能开销。
- 写回（Write-Back）：这种策略仅将更改写入到缓存中，并将缓存行标记为"dirty"（通过设置一个"dirty bit"）。只有当缓存行被替换出缓存时，更改才会被写回到主存储器。这里的dirty bit就是替换时用来判断的，如果是1，那么就需要把整个缓存行（包含2^b字节的数据块）写回（write-back）到主内存。这种策略的优点是减少了对主存储器的访问次数，从而提高了性能。但是，这也可能会导致主存储器与缓存之间的数据不一致。

2 写未命中（Write Miss）：当我们试图写入的数据不在缓存中时，我们有两种基本策略：
- 不写分配（No-Write-Allocate）：这种策略直接将数据写入主存储器，而不将其加载到缓存中。这种策略适用于不希望单次写操作污染缓存的情况。
- 写分配（Write-Allocate）：这种策略在写入数据之前，先将相关的缓存行加载到缓存中，再将新的写操作应用到这个缓存行。如果预计将来会有更多对同一位置的写操作，这种策略可能会很有用。

在实际的系统中，可能会组合使用这些策略。比如，一种常见的组合是使用写直达和不写分配策略，这种组合可以保持数据的一致性，而且适合处理散列的、非连续的写操作。另一种常见的组合是使用写回和写分配策略，这种组合可以减少对主存储器的访问次数，从而提高性能，尤其是在处理连续的、集中的写操作时。

小结

这篇文章写了下cache的概念以及读写过程中的读取策略。cache的缓存命中是非常有用和关键的，可以为程序或许数据节省下非常多时间。一个有趣的观点是，99%的命中率可能比97%的命中率好两倍。比如假设缓存命中的时间为1个周期，未命中的惩罚为100个周期。那么：

对于97%的命中率，平均访问时间为：1个周期（命中时间） + 0.03（未命中率） * 100个周期（未命中惩罚） = 4个周期。
对于99%的命中率，平均访问时间为：1个周期（命中时间） + 0.01（未命中率） * 100个周期（未命中惩罚） = 2个周期。

因此，尽管两者的命中率只相差2%，但是平均访问时间却差了一倍。

所以对于程序员来说，尽量写出“缓存友好”的代码也是能很好提升程序的效率。通过理解缓存的工作方式，我们可以编写出更有效地利用缓存的代码，一些常见方式有：

重复引用变量：这是好的（利用时间局部性Temporal Locality）：如果一个变量被反复引用，它可能会留在缓存中，这样每次引用都会命中缓存，从而提高性能。
使用跨度为1的引用模式：这是好的（利用空间局部性Spatial Locality）。如果你的代码按顺序访问数据（例如，遍历数组），那么缓存系统可能会预先加载你即将访问的数据，从而提高缓存命中率。这就是为什么我们一行一行地遍历二维数组要比一列一列地遍历快很多，因为数组在内存中是按行存储，缓存可以帮助我们提前加载到接下来的数据。

结束！