分层存储体系
@[toc]
---
## 什么是分层存储体系
每个人都希望自己的计算机拥有这样一个存储器：它容量无限大，CPU 访问它的速度无限快，并且能够永久性的存储数据（断电不会丢失数据），而且价格不能太高昂。
But，遗憾的是，现阶段的技术仍然满足不了我们的幻想。
为此，经过多年的探索，人们提出了分层存储体系的概念，把我们的幻想一个一个拆开对应到不同的存储器上
- 在这个体系中，计算机拥有若干 KB 超级快速、超级昂贵且易失性的**寄存器**
- 若干 MB 快速、昂贵且易失性的**高速缓存**（CPU Cache，也称为 **CPU 缓存**）
- 若干 GB 的速度与价格都适中、且同样易失性的**内存**
- 以及若干 TB 低速、廉价、非易失性的**磁盘**存储
- 另外还有诸如磁带等可移动的存储装置
至于为什么这些存储器的造价不同，那就和它们的成本、材料、制作工艺等息息相关了。
> 寄存器和高速缓存都直接内嵌在 CPU 中
## 三级缓存架构 L1、L2、L3
为了缓解内存和 CPU 之间速度不匹配的矛盾，引入了高速缓存这个东西，它的容量比内存小很多，但是交换速度却比内存要快得多。
CPU Cache 按照访问速度由快到慢又分为 L1 Cache、L2 Cache、L3 Cache 三层架构：
- L1 和 L2 一般是内嵌在 CPU Core 里面的，L1 最快，L2 其次，他俩都是都是只能被一个单独的 CPU Core 使用
- 而 L3 在 Core 的外面，可以被单个 CPU 上的所有 CPU Core 共享
**越靠近 CPU 的缓存，速度越快，容量也越小**。所以 L1 缓存容量最小但是速度最快；L3 缓存容量最大同时速度也最慢
当 CPU 执行运算的时候，它会先去 L1 缓存查找所需的数据、如果没有找到的话就再去 L2 缓存、然后是 L3 缓存，如果最后这三级缓存中都没有命中，那么 CPU 就要去访问内存了。
显然，**CPU 走得越远，运算耗费的时间就越长。所以尽量确保数据存在 L1 缓存中能够提升大计算量情况下的运行速度**。
需要注意的是，CPU 和三级缓存以及内存的对应使用关系：
- L1 和 L2 都是只能被一个单独的 CPU 核心使用
- L3 可以被单个 CPU 上的所有 CPU 核心共享
- 内存由全部 CPU 上的所有 CPU 核心共享
如下图所示：
## 缓存行 Cache Line
这三级缓存空间中的数据是如何组织起来的呢？换句话说，数据在这三级缓存中的存储形式是什么样的呢？
**Cache Line**（缓存行）！
**缓存中的基本存储单元就是 Cache Line**。
每个 Cache Line 通常是 64 字节，也就是说，一个 Java 的 `long` 类型变量是 8 字节，一个 Cache Line 中可以存 8 个 `long` 类型的变量。
所以小伙伴们看出来了吗~ **缓存中的数据并不是按照一个一个单独的变量这样存储组织起来的，而是多个变量会放到一行中**。
## 伪共享问题 False Sharing
### 什么是伪共享
在程序运行的过程中，**由于缓存的基本单元 Cache Line 是 64 字节，所以缓存每次更新都会从内存中加载连续的 64 个字节**。
如果访问的是一个 `long` 类型数组的话，当数组中的一个值比如 v1 被加载到缓存中时，接下来地址相邻的 7 个元素也会被加载到缓存中。（这也能解释为啥我们数组总是能够这么快，像链表这种离散存储的数据结构，就无法享受到这种红利）。
But，这波红利很可能带来无妄之灾。
举个例子，**如果我们定义了两个 `long` 类型的变量 a 和 b，他们在内存中的地址是紧挨着的，会出现什么问题**？
如果我们想要访问 a 的话，那么 b 也会被存储到缓存中来。
懵了懵了，这有什么问题吗，看起来似乎没有什么毛病，多么 nice 的特性啊
<br>
来来来，直接上个例子
回想下上文提到的 CPU 和三级缓存以及内存的对应使用关系，设想这种情况，如果一个 CPU 核心的线程 T1 在对 a 进行修改，另一个 CPU 核心的线程 T2 却在对 b 进行读取。
当 T1 修改 a 的时候，除了把 a 加载到 Cache Line，还会享受一波红利，把 b 同时也加载到 T1 所处 CPU 核心的 Cache Line 中来，对吧。
根据 MESI 缓存一致性协议，修改完 a 后这个 Cache Line 的状态就是 M（Modify，已修改），而其它所有包含 a 的 Cache Line 中的 a 就都不是最新值了，所以都将变为 I 状态（Invalid，无效状态）
这样，**当 T2 来读取 b 时，诶，发现他所处的 CPU 核心对应的这个 Cache Line 已经失效了，mmp，它就需要花费比较长的时间从内存中重新加载了**。
问题已经显而易见了，**b 和 a 没有任何关系，每次却要因为 a 的更新导致他需要从内存中重新读取，拖慢了速度**。这就是伪共享
表面上 a 和 b 都是被独立线程操作的，而且两操作之间也没有任何关系。只不过它们共享了一个缓存行，但所有竞争冲突都是来源于共享。
用更书面的解释来定义伪共享：**当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，导致无法充分利用缓存行特性，这就是伪共享**。
### 伪共享解决方案
我们先来举个例子看看一段伪共享代码的耗时，如下所示，我们定义一个 Test 类，它包含两个 long 的变量，分别用两个线程对这两个变量进行自增 1 亿次，这段代码耗时 5625ms
对于伪共享，一般有两种方法，其实思想都是一样的：
1）**padding**：就是增大数组元素之间的间隔，使得不同线程存取的元素位于不同的缓存行上，以空间换时间
上面提到过，一个 64 字节的 Cache Line 中可以存 8 个 `long` 类型的变量，我们在 a 和 b 这两个 `long` 类型的变量之间再加 7 个 `long` 类型，使得 a 和 b 处在不同的 Cache Line 上面：
```java
class Pointer {
volatile long a;
long v1, v2, v3, v4, v5, v6, v7;
volatile long b;
}
```
再次运行程序，会发现输出时间神奇的缩短为了 955ms
2）**JDK1.8 提供了 `@Contended` 注解**：就是把我们手动 padding 的操作封装到这个注解里面了，这个注解可以放在类上也可以放在字段上，这里就不多做说明了
```java
class Test {
@Contended
volatile long a; // 填充 a
volatile long b;
}
```
需要注意的是，默认使用这个注解是无效的，需要在 JVM 启动参数加上 `XX:-RestrictContended` 才会生效
## CPU 缓存一致性
### Cache 写策略
数据写入 CPU Cache 之后，在什么时机才把 Cache 中的数据写回到内存呢？有两种常见的写入数据的方法：
1）**写直达**（*Write Through*）：把数据<u>同时</u>写入内存和 Cache 中
写直达的缺点：无论数据在不在 Cache 里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，无疑性能会受到很大的影响
2）**写回**（*Write Back*）：当发生写操作时，新的数据仅仅被写入 Cache Line 里，只有当修改过的 Cache Line「被换出」时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能。
<img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/image-20220630160220444.png" style="zoom: 67%;" />
### CPU 缓存一致性的问题
以一个含有两个 CPU Core 的 CPU 作为例子
假设 A 号核心和 B 号核心同时运行两个线程，都操作共同的变量 i（初始值为 0 ）。
这时如果 A 号核心执行了 `i++` 语句的时候，为了考虑性能，使用了我们前面所说的写回策略，先把值为 `1` 的执行结果写入到 L1/L2 Cache 中，这个时候数据其实没有被同步到内存中的，因为写回策略，只有在 A 号核心中的这个 Cache Line 要被替换的时候，数据才会写入到内存里。
如果这时旁边的 B 号核心尝试从内存读取 i 变量的值，则读到的将会是错误的值，因为刚才 A 号核心更新 i 值还没写入到内存中，内存中的值还依然是 0。**这个就是所谓的缓存一致性问题，A 号核心和 B 号核心的缓存，在这个时候是不一致，从而会导致执行结果的错误。**
### 保证 CPU 缓存一致性：MESI 协议
**MESI 协议就保证了 CPU 缓存一致性，是支持写回（write-back）缓存的最常用协议**。MESI 其实是 4 个标识 Cache Line 状态单词的开头字母缩写，分别是：
- **Modified，已修改**：代表该 Cache Line 上的数据已经被更新过，但是还没有写到内存里
- **Exclusive，独占**：代表数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。
- **Shared，共享**：代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。
- **Invalidated，已失效**：表示的是这个 Cache Line 里的数据已经失效了，不可以读取该状态的数据。