## 缓存及缓存一致
以下是 Intel Core i5-4258U 处理器结构图，图中的 L1、L2、L3 就是缓存（高速缓存）。
程序运行的过程，就是 CPU 从内存读取指令（数据）并执行的过程。而缓存的出现，离不开 **局部性原理**：
> 时间局部性：如果 CPU 访问了一块内存，短时间会再次访问同一块内存。
> 空间局部性：如果 CPU 访问了一块内存，短时间会访问这块内存相邻的内存。
当 CPU 访问一个内存地址时，会将该地址及相邻地址数据拷贝到缓存中，短时间内 CPU 大概率只与缓存进行数据交换。再加上缓存材料及所处位置的特殊性，CPU 访问缓存的速度比访问内存的速度要快。
就拿图中的 Intel 处理器来说，CPU 会先从 L1 缓存中读取数据，如果读到了表示命中，直接使用，没有读到则继续从 L2 缓存读取，同理 L3 缓存也是一样的，L3 缓存未命中则到主内存中读取。同理 CPU 计算结果也要从缓存写回内存中，所以缓存一致首先表示缓存中的数据和内存中的数据一致。
Intel 处理器的 L1、L2 缓存是每个 Core 独享的，假设 Core 0 与 Core 1 正好都从内存中读取了同一个 **缓存行**，如果 Core 0 对缓存行做了修改，那么就必须告诉 Core 1 的缓存，这个缓存行已经失效了，否者就会出现缓存不一致的问题。
> 缓存是由多个缓存行组成的，内存与缓存行交换数据的单位是**缓存行（Cache Line）**，通常为 64Byte。
所以总结一下，缓存一致首先是缓存和内存数据的一致，其次是多核处理器中每个核心缓存之间数据的一致。
## 缓存一致性协议
要解决多核缓存一致必须做到以下 2 点：
- 某个核的缓存有更新时，必须传播到其他核，称为写传播（Write Propagation）
- 某个核对缓存数据的操作顺序，在其他核看起来顺序是一样的，称为事务的串行化（Transation Serialization）
如何实现，最常见的实现方式是 **总线嗅探（Bus Snooping）**，即当某个核的缓存的缓存行有更新时，要把该消息发送到总线，其它核时刻监听总线上的消息。这样做的缺点是大大增加了总线的负担，还有就是，其他核的缓存并不一定也有该缓存行，那么收到的这个消息就是无效的。
针对总线嗅探的缺点，**Directory-based 机制**采用的是点对点的传播，即所有缓存行的信息，都被记录在 directory 中。比如会记录每个缓存行当前都在那些核的缓存中，直接将缓存行修改的消息发送到那些核。这么做的也有个缺点是每次总线的传输都到 directory 做一次检查，产生耗时。
不论是 Snooping 还是 Directory-based，总之能将缓存修改的消息通知到其他核。现在假设有 2 个核 C1 和 C2，各自的缓存分别为 Cache1 和 Cache2，有一个变量 x 同时被读到各自的缓存中，那么如果 C1 修改 x 的值后，并通过总线通知 C2，C2 是否要立刻更新？
Core 对共享变量有写操作之后立刻更新的做法称为 **Write Update**，这种方式逻辑简单但是效率不高，如果 C2 只是读取变量，后续其实没有任何操作，那么 Write Update 其实做了无用功。
所以还有一种做法是 **Write Invalidate**，即 C2 将该变量所在的缓存行标记为 Invalid 状态，如果后续 C2 访问了该变量，C1 将 x 值同步到内存（变量 x 所在的缓存行一同被同步到内存）， C2 再重新读取。
#### MSI 协议
大部分处理器使用 Write Invalidate 的做法保证多核缓存一致，具体实现由不同的协议。其中 比较著名的是 MSI 协议，MSI 三个字母分别代表了**缓存行**的 3 种状态：Modified、Shared 和 Invalid。
简单来说，这三种状态的转换如下：
- 当有多个核的缓存都从内存中读取了相同的 缓存行A，那么这时缓存行状态是 Shared
- C1 核对 缓存行A 中数据修改，则 Cache1 中的 缓存行A 状态为 Modified，其他核缓存中 缓存行A 状态为 Invalid
- C2 核读取 缓存行A 中数据，因为状态已经是 Invalid，将触发 read miss，Cache1 将 缓存行A 写回内存，C2 核从内存中读取，此时 C1 和 C2 的缓存中 缓存行A 状态是 Shared，其他核中 缓存行A 状态还是 Invalid
- 当总线其他设备（如DMR设备）直接修改内存数据，则缓存行失效，此时都为 Invalid
读取 Shared 状态的缓存行时，不需要通知其他核，读取或写入 Modified 状态的缓存行时，不需要通知其他核。
#### MESI 协议
缓存一致性协议 MESI 增加了 Exclusive 状态，表示缓存行被独占。
缓存一致性协议除了 MSI、MESI 还有 big.LITTLE、ACE等协议，总的目标都是使总线的通信量尽可能的小，同时优化某些频繁执行的操作。
## 伪共享
理解了缓存行，以及多核心处理器缓存和内存之间数据传递的过程后，伪共享就比较好理解了。
假设 C1、C2 的缓存同时读了一个缓存行，而这个缓存行有变量 x、y。如果 C1 要对变量 x 做修改，C2 要对变量 y 做修改，那么就会出现这样一个现象：x 先被修改，C2 缓存中的缓存行被标记为 Invalid，C2 修改变量 y 时就会重新到内存中读取。也就是说本来根据局部性原理 x 和 y 在同一个缓存行，原本预想会提高运行速度，现在由于 2 个核同时操作这个缓存行，反而是缓存失去了优势。这个现象就是伪共享。
**如果避免伪共享？**
上述类似场景在多线程编程中常常遇到，既然操作同一个缓存行速度变慢，最简单的办法就是让 x、y 处于不同缓存行，缓存行一般为 64Byte，那么可以在 x、y 中间填充字节保证不再同一个缓存行。
```java
class Data {
volatile long x;
volatile long y;
}
class Data {
volatile long x;
volatile long a1,a2,a3,a4,a5,a6,a7;
volatile long y;
}
```
在 JDK 中有个 Striped64 类，其中的内部类 Cell 有一个注解 @sun.misc.Contended 也能达到填充的效果，但是需要在虚拟机启动的时候加上参数 -XX:-RestrictContended
从 CPU 的缓存一致性开始