一文读懂 Cache 工作原理，Cache 一致性-技术圈

你知道的越多，不知道的就越多，业余的像一棵小草！

你来，我们一起精进！你不来，我和你的竞争对手一起精进！

编辑：业余草

zhuanlan.zhihu.com/p/386919471

推荐：https://www.xttblog.com/?p=5277

可以随便到网上查一查，各大互联网公司笔试面试特别喜欢考一道算法题，即 LRU 缓存机制，又顺手查了一下「LRU 缓存机制」最近有哪些企业喜欢考察，超级大热门！

今天给大家分享一篇关于 Cache 的硬核的技术文，基本上关于 Cache 的所有知识点都可以在这篇文章里看到。

关于 Cache 这方面内容图比较多，不想自己画了，所以图都来自《Computer Architecture : A Quantitative Approach》。

这是一本体系架构方面的神书，推荐大家看一下。

本文主要内容如下，基本涉及了 Cache 的概念，工作原理，以及保持一致性的入门内容。

为什么需要 Cache

我们首先从一张图来开始讲为什么需要 Cache。

上图是 CPU 性能和 Memory 存储器访问性能的发展。

我们可以看到，随着工艺和设计的演进，CPU 计算性能其实发生了翻天覆地的变化，但是 DRAM 存储性能的发展没有那么快。

所以造成了一个问题，存储限制了计算的发展。

容量与速度不可兼得。

如何解决这个问题呢？可以从计算访问数据的规律入手。

我们随便贴段代码:

for (j = 0; j < 100; j = j + 1){
    for( i = 0; i < 5000; i = i + 1){
        x[i][j] = 2 * x[i][j];
    }
}

可以看到，由于大量循环的存在，我们访问的数据其实在内存中的位置是相近的。

换句专业点的话说，我们访问的数据有局部性。

我们只需要将这些数据放入一个小而快的存储中，这样就可以快速访问相关数据了。

总结起来，Cache 是为了给 CPU 提供高速存储访问，利用数据局部性而设计的小存储单元。

实际系统中的 Cache

我们展示一下实际系统中的 Cache。

如上图所示，整个系统的存储架构包括了 CPU 的寄存器，L1/L2/L3 CACHE，DRAM 和硬盘。

数据访问时先找寄存器，寄存器里没有找 L1 Cache, L1 Cache 里没有找 L2 Cache 依次类推，最后找到硬盘中。

同时，我们可以看到，速度与存储容量的折衷关系。容量越小，访问速度越快！

其中，一个概念需要搞清楚。

CPU 和 Cache 是 word 传输的，而 Cache 到主存是以块传输的，一块大约 64Byte。

现有 SOC 中的 Cache 一般组成如下。

Cache 的分类

Cache 按照不同标准分类可以分为若干类。

按照数据类型划分：I-Cache 与 D-Cache。其中 I-Cache 负责放置指令，D-Cache 负责方式数据。两者最大的不同是 D-Cache 里的数据可以写回，I-Cache 是只读的。
按照大小划分：分为 small Cache 和 large Cache。没路组（后文组相连介绍）< 4KB 叫 small Cache，多用于 L1 Cache，大于 4KB 叫 large Cache。多用于 L2 及其他 Cache。
按照位置划分：Inner Cache和Outer Cache。一般独属于CPU微架构的叫Inner Cache, 例如上图的L1 L2 CACHE。不属于CPU微架构的叫outer Cache。
按照数据关系划分：Inclusive/exclusive Cache: 下级 Cache 包含上级的数据叫 inclusive Cache。不包含叫 exclusive Cache。举个例子，L3 Cache 里有 L2 Cache 的数据，则 L2 Cache 叫 exclusive Cache。

Cache的工作原理

要讲清楚 Cache 的工作原理，需要回答 4 个问题：

数据如何放置
数据如何查询
数据如何被替换
如果发生了写操作，Cache 如何处理

数据如何放置

这个问题也好解决。我们举个简单的栗子来说明问题。

假设我们主存中有 32 个块，而我们的 Cache 一共有 8 个 Cache 行( 一个 Cache 行放一行数据）。

假设我们要把主存中的块 12 放到 Cache 里。

那么应该放到 Cache 里什么位置呢？

三种方法：

全相连（Fully associative）。可以放在 Cache 的任何位置。
直接映射（Direct mapped）。只允许放在 Cache 的某一行。比如 12 mod 8。
组相连（set associative）。可以放在 Cache 的某几行。例如 2 路组相连，一共有 4 组，所以可以放在 0,1 位置中的一个。

可以看到，全相连和直接映射是 Cache 组相连的两种极端情况。

不同的放置方式主要影响有两点：

组相连组数越大，比较电路就越大，但 Cache 利用率更高，Cache miss 发生的概率小。
组相连数目变小，Cache 经常发生替换，但是比较电路比较小。

这也好理解，内存中的块在 Cache 中可放置的位置多，自然找起来就麻烦。

如何在 Cache 中找数据

其实找数据就是一个比对过程，如下图所示。

我们地址都以 Byte 为单位的。

但主存于 Cache 之间的数据交换单位都是块（block，现代 Cache 一般一个 block 大约 64Byte)。所以地址对最后几位是 block offset。

由于我们采用了组相连，则还有几个比特代表的是存储到了哪个组。

组内放着若干数据，我们需要比较 Tag，如果组内有 Tag 出现，则说明我们访问的数据在缓存中，可以开心的使用了。

比如举个 2 路组相连的例子，如下图所示。

T 表示 Tag。直接比较 Tag，就能得知是不是命中了。如果命中了，则根据 index(组号）将对应的块取出来即可。

如上图所示。用 index 选出位于组相连的哪个组。然后并行的比较 Tag，判断最后是不是在 Cache 中。上图是 2 路组相连，也就是说两组并行比较。

那如果不在缓存中呢？这就涉及到另一个问题。

不在缓存中如何替换 Cache ？

如何替换 Cache 中的数据

Cache 中的数据如何被替换的？这个就比较简单直接。

随机替换。如果发生 Cache miss 里随机替换掉一块。
Least recently used. LRU。最近使用的块最后替换。
First in, first out (FIFO), 先进先出。

实际上第一个不怎么使用，LRU 和 FIFO 根据实际情况选择即可。

Cache 在什么时候数据会被替换内？也有几种策略。

不在本 Cache 替换。如果 Cache miss 了，直接转发访问地址到主存，取到的数据不会写到 Cache。
在读 MISS 时替换。如果读的时候 Cache 里没有该数据，则从主存读取该数据后写入 Cache。
在写 MISS 时替换。如果写的时候 Cache 里没有该数据，则将本数据调入 Cache 再写。

如果发生了写操作怎么办

Cache 毕竟是个临时缓存。

如果发生了写操作，会造成 Cache 和主存中的数据不一致。如何保证写数据操作正确呢？

也有三种策略。

通写：直接把数据写回 Cache 的同时写回主存。极其影响写速度。

回写：先把数据写回 Cache，然后当 Cache 的数据被替换时再写回主存。

通写队列：通写与回写的结合。先写回一个队列，然后慢慢往主存储写。如果多次写同一个数据，直接写这个队列。避免频繁写主存。

Cache一致性

Cache 一致性是 Cache 中遇到的比较坑的一个问题。

什么原因需要 Cache 处理一致性呢？

主要是多核系统中，假如 core 0 读了主存储的数据，写了数据。core 1 也读了主从的数据。这个时候 core 1 并不知道数据已经被改动了，也就是说，core 1 Cache 中的数据过时了，会产生错误。

Cache 一致性的保证就是让多核访问不出错。

Cache 一致性主要有两种策略。

策略一：基于监听的一致性策略

这种策略是所有 Cache 均监听各 Cache 的写操作，如果一个 Cache 中的数据被写了，有两种处理办法。

写更新协议：某个 Cache 发生写了，就索性把所有 Cache 都给更新了。

写失效协议：某个 Cache 发生写了，就把其他 Cache 中的该数据块置为无效。

策略 1 由于监听起来成本比较大，所以只应用于极简单的系统中。

策略二：基于目录的一致性策略

这种策略是在主存处维护一张表。记录各数据块都被写到了哪些 Cache, 从而更新相应的状态。一般来讲这种策略采用的比较多。又分为下面几个常用的策略。

SI: 对于一个数据块来讲，有 share 和 invalid 两种状态。如果是 share 状态，直接通知其他 Cache, 将对应的块置为无效。
MSI：对于一个数据块来讲，有 share 和 invalid，modified 三种状态。其中 modified 状态表表示该数据只属于这个 Cache，被修改过了。当这个数据被逐出 Cache 时更新主存。这么做的好处是避免了大量的主从写入。同时，如果是 invalid 时写该数据，就要保证其他所有 Cache 里该数据的标志位不为M，负责要先写回主存储。
MESI：对于一个数据来讲，有 4 个状态。modified, invalid, shared, exclusive。其中 exclusive 状态用于标识该数据与其他 Cache 不依赖。要写的时候直接将该 Cache 状态改成 M 即可。

我们着重讲讲 MESI。图中黑线：CPU 的访问。红线：总线的访问，其他 Cache 的访问。

当前状态时I状态时，如果发生处理器读操作 prrd。

如果其他Cache里有这份数据，如果其他 Cache 里是 M 态，先把 M 态写回主存再读。否则直接读。最终状态变为 S。
其他 Cache 里没这个数据，直接变到 E 状态。

当前状态为 S 态。

如果发生了处理器读操作，仍然在 S 态。
如果发生了处理器写操作，则跳转到 M 状态。
如果其他 Cache 发生了写操作，跳到 I 态。

当前状态 E 态。

发生了处理器读操作还是 E。
发生了处理器写操作变成 M。
如果其他 Cache 发生了读操作，变到 S 状态。

当前状态 M 态。

发生了读操作依旧是 M 态。
发生了写操作依旧是 M 态。
如果其他 Cache 发生了读操作，则将数据写回主存储，变换到 S 态。

总结

Cache 在计算机体系架构中有非常重要的地位，本文讲了 Cache 中最主要的内容，具体细节可以再根据某个点深入研究。