• 1. CPU Cache
  • 1.1 CPU Cache 的数据结构
  • 1.2 CPU Cache 的读取过程
    • 1.2.1 直接映射 Cache
    • 1.2.2 全相连 Cache
    • 1.2.3 组相连 Cache
  • 1.3 CPU Cache 的数据写入
    • 1.3.1 写直达
    • 1.3.2 写回
  • 1.4 缓存一致性问题
    • 1.4.1 总线嗅探
    • 1.4.2 MESI 协议

1. CPU Cache

1.1 CPU Cache 的数据结构

CPU Cache 是由很多个 Cache Line（缓存块） 组成的，Cache Line 是 CPU 从内存读取数据的基本单位，而 Cache Line 由各种标志（Tag）+ 数据块（Data Block）组成:

查看服务器的 L1 Cache Line 大小： CPU Cache 的数据是从内存中读取过来的，它是以一小块一小块读取数据的，而不是按照单个数组元素来读取数据的。 比如，有一个 int array[100] 的数组，当载入 array[0] 时，由于这个数组元素的大小在内存只占 4 字节，不足 64 字节，CPU 就会顺序加载数组元素到 array[15]，意味着 array[0]~array[15] 数组元素都会被缓存在 CPU Cache 中了，因此当下次访问这些数组元素时，会直接从 CPU Cache 读取，而不用再从内存中读取，大大提高了 CPU 读取数据的性能。

1.2 CPU Cache 的读取过程

前面，我们提到 CPU 访问内存数据时，是一小块一小块数据读取的，具体这一小块数据的大小，取决于 coherency_line_size 的值，一般 64 字节。在内存中，这一块的数据我们称为内存块（Block），读取的时候我们要拿到数据所在内存块的地址。

通过内存地址找到 CPU Cache 中的数据的策略：

• 直接映射 Cache
• 全相连 Cache
• 组相连 Cache

1.2.1 直接映射 Cache

直接映射 Cache（Direct Mapped Cache）：把内存块的地址始终「映射」在一个 CPU Cache Line（缓存块）的地址，至于映射关系实现方式，则是使用「取模运算」，取模运算的结果就是内存块地址对应的 CPU Cache Line（缓存块）的地址。

使用取模方式映射的话，就会出现多个内存块对应同一个 CPU Cache Line:

因此，为了区别不同的内存块，在对应的 CPU Cache Line 中我们还会存储一个组标记（Tag）。这个组标记会记录当前 CPU Cache Line 中存储的数据对应的内存块，我们可以用这个组标记来区分不同的内存块。

除了组标记信息外，CPU Cache Line 还有两个信息：

• 一个是从内存加载过来的实际存放数据（Data）。
• 另一个是有效位（Valid bit），它是用来标记对应的 CPU Cache Line 中的数据是否是有效的，如果有效位是 0，无论 CPU Cache Line 中是否有数据，CPU 都会直接访问内存，重新加载数据。

CPU 在从 CPU Cache 读取数据的时候，并不是读取 CPU Cache Line 中的整个数据块，而是读取 CPU 所需要的一个数据片段，这样的数据统称为一个字（Word）。那在对应的 CPU Cache Line 中数据块中找到所需的字，就需要一个偏移量（Offset）。

因此，一个内存的访问地址，包括组标记、CPU Cache Line 索引、偏移量这三种信息。而对于 CPU Cache 里的数据结构，则是由索引 + 有效位 + 组标记 + 数据块组成。

如果内存中的数据已经在 CPU Cahe 中了，那 CPU 访问一个内存地址的时候，会经历这 4 个步骤：

1. 根据内存地址中索引信息，计算在 CPU Cahe 中的索引，也就是找出对应的 CPU Cache Line 的地址；
2. 找到对应 CPU Cache Line 后，判断 CPU Cache Line 中的有效位，确认 CPU Cache Line 中数据是否是有效的，如果是无效的，CPU 就会直接访问内存，并重新加载数据，如果数据有效，则往下执行；
3. 对比内存地址中组标记和 CPU Cache Line 中的组标记，确认 CPU Cache Line 中的数据是我们要访问的内存数据，如果不是的话，CPU 就会直接访问内存，并重新加载数据，如果是的话，则往下执行；
4. 根据内存地址中偏移量信息，从 CPU Cache Line 的数据块中，读取对应的字。

1.2.2 全相连 Cache

TODO 全相连 Cache （Fully Associative Cache）

1.2.3 组相连 Cache

TODO 组相连 Cache （Set Associative Cache）

1.3 CPU Cache 的数据写入

两种针对写入数据的方法：

• 写直达（Write Through）
• 写回（Write Back）

1.3.1 写直达

写直达（Write Through）：把数据同时写入内存和 Cache 中。

• 如果数据已经在 Cache 里面，先将数据更新到 Cache 里面，再写入到内存里面；
• 如果数据没有在 Cache 里面，就直接把数据更新到内存里面。

这种策略的性能不好。

1.3.2 写回

写回（Write Back）：当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中。

• 如果当发生写操作时，数据已经在 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 里，然后再把这个 Cache Block 标记为脏的就好了。

为什么缓存没命中时，还要定位 Cache Block？

这是因为此时是要判断数据即将写入到 cache block 里的位置，是否被「其他数据」占用了此位置，如果这个「其他数据」是脏数据，那么就要帮忙把它写回到内存。

CPU 缓存与内存使用「写回」机制的流程图如下，左半部分就是读操作的流程，右半部分就是写操作的流程:

1.4 缓存一致性问题

小林coding

现在 CPU 都是多核的，由于 L1/L2 Cache 是多个核心各自独有的，在写回策略下，会带来多核心的缓存一致性（Cache Coherence） 的问题。

要解决这一问题，就需要一种机制，来同步两个不同核心里面的缓存数据。要实现的这个机制的话，要保证做到下面这 2 点：

• 某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（Write Propagation）；
• 某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串行化（Transaction Serialization）。

要实现事务串行化，要做到 2 点：

• CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；
• 要引入锁的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。

1.4.1 总线嗅探

写传播最常见的实现方式是用 总线嗅探（Bus Snooping）来实现。

当 A 号 CPU 核心修改了 L1 Cache 中 i 变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个 CPU 核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的 L1 Cache 里面，如果 B 号 CPU 核心的 L1 Cache 中有该数据，那么也需要把该数据更新到自己的 L1 Cache。

存在的问题：

• 加重总线的负载。CPU 需要每时每刻监听总线上的一切活动；不管别的核心的 Cache 是否缓存相同的数据，都需要发出一个广播事件
• 不能保证事务串行化。

1.4.2 MESI 协议

MESI 协议基于总线嗅探机制实现了事务串行化，也用状态机机制降低了总线带宽压力。做到了 CPU 缓存一致性。

MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：

• Modified，已修改。

就是前面提到的脏标记，代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里。

• Exclusive，独占。

数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。

• Shared，共享。

代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。

• Invalidated，已失效。

表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。

这四个状态之间的转换：

可以发现当 Cache Line 状态是「已修改」或者「独占」状态时，修改更新其数据不需要发送广播给其他 CPU 核心，这在一定程度上减少了总线带宽压力。