CPU Cache 与缓存一致性
在计算机中，存储体系是一个典型的金字塔结构，按照速度排列从上到下依次是：CPU 寄存器、CPU Cache（L1/L2/L3）、内存、SSD 固态硬盘以及 HDD 传统机械硬盘。越上层的存储设备速度越快，当然价格也更贵，容量也越小。
从广义上讲，上一级的存储器都是下一级存储器的缓存。当然这里我们只关注 CPU Cache。现代 CPU 缓存通常都有三个等级，分为 L1、L2 和 L3，其中 L1 和 L2 在每个 CPU 核心中都有，而 L3 则是所有核心共享的。在 L1 高速缓存中，指令和数据是分开存储的；而在 L2 和 L3 中则不区分，称为统一缓存（unified cache）。
在 Linux 系统中，我们可以通过以下命令来查看 L1/L2/L3 的大小：
1 | # L1 数据缓存 |
CPU Cache 映射策略
CPU Cache 从内存读取到的数据是一块一块存储的，这一块可以理解为 CPU Cache 的最小缓存单位，它有一个专门的名字：Cache Line，一般它的大小为 64 Byte。在 Linux 中可以通过以下命令来查看它的大小：
1 | $ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size |
由于 CPU Cache 与内存容量上的差异，必然需要某种映射规则，来确定 Cache Line 与内存地址的关系，这种关系就是我们所说的映射策略，一般常见的策略有：直接映射、全相联和组相联。
直接映射
直接映射是一种多对一的映射，这种方式下，主存中的每个内存块只能有一个 Cache Line 与之对应，因此它也叫做“单路组相联”。具体来说就是使用内存块地址对 Cache Line 的个数取模。比如内存共被划分了 32 个内存块，而 CPU Cache 共有 8 个 Cache Line，假如 CPU 想要访问第 15 号内存块，如果该内存块的数据已经缓存在了 Cache Line 中，那么一定是映射在了 7 号 Cache Line 中。一般来说，缓存的索引号可以通过以下公式计算：
1 | I = (Am / B) mod N |
其中 I 为缓存索引，Am 为内存地址，B 为 Cache Line 的大小，N 为 Cache Line 的个数。Am 除以 B 是内存块的个数。
直接映射的优点就是结构简单，易于实现，但是存在显著的冲突问题。由于多个不同的内存块会共享同一个缓存块，一旦缓存失效则必须将缓存块当前的数据清除，这在频繁更换缓存内容时会造成大量的延迟，并且也无法有效利用程序运行期间所具有的时间局部性特征（近期访问的地址在不久的将来很有可能被再次访问）。
组相联
组相联是把缓存划分为多个组，每个组有若干个 Cache Line。用一句话来概括就是：组间直接映射，组内全相联。以下是一个 2 路组相联的例子：
上图将缓存分成了 s 组，每组 2 个 Cache Line，即 2 路（2 ways），主存中的每个数据块只能位于分组中的某一个，但是可以在指定分组中的任意一个 Cache Line 中。一般来说，组相联的缓存索引可以通过以下公式计算：
1 | I = (Am / Nw / Na) mod N |
其中，I 为缓存索引，Am 为内存地址，Nw 为缓存块内字数（也可以认为是 Cache Line 的大小），Na 为相联路数，N 为分组个数。
全相联
全相联是指主存中的数据块可能出现在任意一个 Cache Line 中，这种方式使得替换具有最大的灵活性（可以使用 LFU 或者 LRU 等算法），同时也意味着有最低的 miss 率。但是由于没有索引可以使用，检查一个 cache 是否命中需要在整个 cache 范围内搜索，这带来了查找电路的大量延时。因此只有在缓存极小的情况才有可能使用这种方式。
小结
其实上面的三种映射方式，其实都可以看作是组相联，直接映射是单路组相联，而全映射则只有一个分组。因此，一个主存地址映射到高速缓存大体上有三个步骤：组选择（查找 Cache Set），行匹配（查找 Cache Line）和字抽取（查找 Cache Line 中一个字的起始字节）。
比如一个 32 位系统的内存地址映射到 4 MB 高速缓存中。首先是组选择，对于直接映射来说，分组数等于 Cache Line 的个数：65536，也就意味着需要中间 16 bit 来表示 Cache Line 的编号。接下来是行匹配，对于直接映射来说，一个分组只有一个 Cache Line，不用选择。最后是字抽取，由于一般 Cache Line 的大小是 64 Byte，同时现代处理器中，存储单元一般是以字节为单位的，也是最小的寻址单元，这也就意味着一个 Cache Line 可以存储 64 个存储单元，因此内存地址的低位 6 个 bit 用于表示在 Cache Line 中的偏移量（数据从第几个字节开始）。剩余的高位 10 bit 作为内存地址的一部分，同样也会映射到 Cache Line 中，作为标记位。
上图是组映射的一般表示，对于一个 E 路组相联来说，缓存被划分为了 2^s 组，即通过内存地址的中间 s 位即可找到目标 Cache Line 的对应分组。找到分组后，遍历分组中所有的 Cache Line，检查 Cache Line 中的有效位，以及对比 Cache Line 中的标记位与内存地址的高位 t bit 是否一致。当 tag 和 valid 校验成功，我们称为缓存命中，此时只需要根据内存地址的低位 b bit 计算出 Cache Line 中数据的起始字节，向后读取一个字放入 CPU 寄存器即可。
计算机各个硬件之间进行信息传递是通过贯穿整个系统的一组电子管道，称做总线，它携带信息字节并负责在各个部件间传递。硬件之间进行信息交流需要有一个统一的标准，也就是二进制信息传递规则，为了高效考虑，通常总线被设计成传送定长的字节块，也就是字（word）。字中的字节数（即字长）是一个基本的系统参数，在各个系统中的情况都不尽相同。操作系统中的 32 位（4 个字节）或 64 （8 个字节）位就叫总线的字长单位。
写回和写直达
既然有缓存，那必然会出现缓存与主存数据不一致的情况，此时就需要将最新的数据更新到对应的内存当中。通常有两种更新方式：写直达（Write Through）和写回（Write Back）。写直达要求 CPU 在写数据的时候，同时更新缓存和内存，这样缓存和内存的数据就会始终保持一致，但是对性能影响较大。而写回则要求 CPU 在写数据的时候，仅修改缓存，只有当缓存需要被替换时才会去更新内存，这样就大大减少了写内存的操作，提高了性能。关于写回，我们详细展开描述。
如果发生写操作时，数据已经在 CPU Cache 里的话，则把数据更新到 CPU Cache 里，同时标记 CPU Cache 里的这个 Cache Block 为脏（Dirty）的，这个标记代表 CPU Cache 里的这个 Cache Block 的数据和内存是不一致的，此时不需要把数据写到内存里。
如果发生写操作时，数据对应的 Cache Block 里存放的是「别的内存地址的数据」的话，就要检查这个 Cache Block 里的数据有没有被标记为脏的，如果是脏的话，就要把这个 Cache Block 里的数据写回到内存，然后再把当前要写入的数据，写入到这个 Cache Block 里，同时也把它标记为脏的；如果 Cache Block 里面的数据没有被标记为脏，则直接将数据写入到这个 Cache Block 里，然后再把这个 Cache Block 标记为脏的即可。
MESI 协议
在多核 CPU 中，由于每个核心都有自己的 L1 和 L2 缓存，因此必然存在核心之间的缓存一致性问题，MESI 协议就是为解决这个问题而存在的。在 MESI 协议中，Cache Line 有 4 种不同的状态：
已修改（Modified），表示缓存行是脏的，与主存的值不一致，如果别的 CPU 核心要读取主存中的这块数据，该缓存行必须写回主存，然后缓存行的状态变为共享。
独占的（Exclusive），表示缓存行只在当前缓存中，与已修改不同的是，该缓存行是干净的，即没有发生修改。CPU 可以直接对其进行修改，然后状态变为已修改。
共享的（Shared），表示缓存行也存在于其他缓存中且都是干净的。处于该状态的缓存行不能直接被修改，需要该 CPU 核心向其他核心广播一个消息，要求其他拥有相同数据的核心把各自对应的缓存行标记为无效。
无效的（Invalid），表示缓存行是无效的，不可以再读取该状态的缓存行数据。另外，一般的 Cache 会优先填充 Invalid 状态的缓存行。
缓存行的状态转换可以通过一个有限状态机来描述，触发状态转换的场景有两种：缓存所在处理器的读写，其他处理器的读写。有时一个处理器对于缓存的请求可能需要通过总线来发送，而总线请求会被总线窥探器监听。以下是某个 CPU 操作时，当前缓存行的状态转换表：
| 初始状态 | 操作 | 响应 |
|---|---|---|
| Invalid | 读 | 此时向总线发送读缓存的请求，其他处理器监听到该请求后，会检查自己是否有有效的数据副本。如果有，则通过总线发送该数据副本，此时该缓存行状态变为 Shared；如果没有，则会请求主存获取数据，缓存行状态变为 Exclusive |
| Invalid | 写 | 此时向总线发送写缓存的请求，其他处理器监听到该请求后，会检查自己是否有有效的数据副本。如果有，则其中一个通过总线发送该数据副本，同时这些拥有有效副本的缓存都将设置为 Invalid；如果没有，则会请求主存获取数据。为什么要获取最新的值？答案是因为此前没有该缓存，获取是为了独占缓存。之后该处理器会向缓存块中写入修改后的值 |
| Exclusive | 读 | 只有当前处理器拥有该缓存，因此不会发送总线请求，状态保持不变 |
| Exclusive | 写 | 只有当前处理器拥有该缓存，因此不会发送总线请求，此时直接写入修改后的值，缓存行状态变为 Modified |
| Shared | 读 | 没有总线请求产生，状态保持不变 |
| Shared | 写 | 其他处理器拥有该缓存，因此需要发送总线请求，其他处理器监听到该请求后，会将自己的有效副本标记为 Invalid，然后当前缓存行的状态变为 Modified |
| Modified | 读 | 此时没有总线请求产生，直接读取缓存，状态保持不变 |
| Modified | 写 | 同样没有总线请求产生，同时状态保持不变，直接修改缓存为新值即可 |
写操作仅在缓存行是已修改或者独占状态时可以自由执行，如果在共享状态，其他处理器的缓存都需要先设置为无效，这种广播操作称为 RFO（Request For Ownership）。对于已修改状态的缓存行，要监听各处理器对其的读请求，发送其数据到总线的同时还要写回主存。对于共享状态的缓存行，要监听使其无效或请求拥有的广播，当匹配时把该缓存行置为无效。
Store Buffer
当某个处理器尝试修改其他处理器的 Cache Line 中的数据时，MESI 的广播操作带来的延迟对于处理器来说是难以忍受的。为了解决这个问题，在 CPU 和 Cache 中间又引入了 Store Buffer。这是一个容量比高速缓存还小的私有部件，当处理器需要修改数据时，会先将数据写入写缓冲器中，然后继续处理其他事情，当收到其他处理器的响应时，才将数据从写缓冲器转移到 Cache Line 中。
Store Forwarding
在同一个处理器中，写缓冲器的引入必然会带来一个问题，即异步操作引发的数据滞后性。自处理器的写操作将最新的数据放入写缓冲器时起，高速缓存中的数据就已经过时，此后所有的加载操作看到的都是旧的数据，直到写缓冲器将数据同步到高速缓存。
为了解决这个问题，硬件工程师实现了 Store Forwarding 技术，这个技术可以使 CPU 直接从 Store Buffer 加载数据，即支持将 CPU 放入 Store Buffer 的数据传递给后续的加载操作而不经过高速缓存。
需要注意的是，虽然处理器可以直接读取其 Store Buffer 中自己以前的写操作，但是在将这些操作从写缓冲区刷新到高速缓存之前，其他处理器是无法看到这些写操作的。这就意味着，Store Forwarding 技术只能解决单个处理器中的缓存滞后问题，无法解决多核处理器的此类问题。
Invalid Queue
由于 Store Buffer 的容量很小，因此它很容易就会被填满，此时处理器必须等待它发出的使缓存无效的广播请求得到响应，才可以将 Store Buffer 中的数据转移到高速缓存，从而释放空间。
为了解决这个同步操作带来的延迟问题，硬件工程师又为每个处理器添加了一个无效队列。处理器在监听到使缓存无效的消息后，直接将消息放入无效队列中排队，然后立即发送回复消息，这就大大降低了响应的延迟。
有些处理器并没有实现 Invalid Queue。
内存屏障
内存屏障（memory barrier）又叫内存栅栏（memory fence），其目的是用来阻止 CPU 对指令的重排序（有些编译器也会对指令进行重排序）。根据 CPU 对于变量的操作读（load）和写（store），两两组合可以有四种内存屏障：
| 名称 | 描述 |
|---|---|
| LoadLoad 屏障 | 保证屏障前的 load 操作一定在屏障后的 load 操作之前完成 |
| StoreStore 屏障 | 保证屏障前的 store 操作一定在屏障后的 store 操作之前完成 |
| LoadStore 屏障 | 保证屏障前的 load 操作一定在屏障后的 store 操作之前完成 |
| StoreLoad 屏障 | 保证屏障前的 store 操作一定在屏障后的 load 操作之前完成 |
内存屏障除了有阻止指令重排序的作用，还与 MESI 协议有关。我们知道 MESI 为了优化性能，引入了 Store Buffer 和 Invalid Queue，因此写类型的内存屏障还能触发内存的强制更新，让 Store Buffer 中的数据立刻写回到高速缓存中。读类型的内存屏障会让 Invalid Queue 中的缓存行在后面的 load 操作之前全部标记为失效。