CPU缓存一致性
一、引言
本文参考 小林coding 的《图解操作系统》，也是我十分喜欢的一个公众号博主，为他打 call
老读者知道我之前再写 Kafka 的博文，为什么突然开始写操作系统的呢？
原因在于：
当我看到 Kafka 服务端的一些 IO 操作时，我发现我看不懂了，了解之后发现这里 Netty 的概念。
当我尝试了解 IO 时，我发现一些内存、磁盘的交换，搞的我焦头烂额，于是，想静下心来从头开始。
当我把 小林coding 的 《图解操作系统》看完之后，我发现对操作系统的理解更上一层楼。
用一段话，作为今天的开场白：
读书的根本目的，未必是解决现实问题，它更像一场心灵的抚慰。
一个喜欢读书的人，可能不会记得自己读过哪些书。
但是那些看过的故事、收获的感悟、浸染过的气质，就像一颗种子，会在你的身体里慢慢发芽长大，不断提升你的认知，打开你的视野。
二、CPU Cache 的数据写入
随着时间的推移，CPU和内存的访问性能越来越大，于是在 CPU 的内部嵌入了 CPU Cache（高速缓存）。
我们简单的介绍下 CPU Cache 的结构：
CPU Cache 由很多的 CPU Line（缓存块）组成，CPU Line 是 CPU 从内存读取数据的基本单位，而 CPU Line 是由各种标志（Tag）+ 数据块（Data Block）组成。
我们之前介绍了 CPU 读取数据的时候，尽可能的从 CPU Cache 中读取，极大的提高的我们 CPU 的性能。
当然，对于数据不仅有读取，还有写入。
如果我们将一个修改的数据写入 Cache 之后，Cache 的数据将和内存的数据存在不一致，我们需要将 Cache 中的数据同步到内存。
用什么方法将 Cache 的数据同步的内存极为重要，提供两种方法：
- 写直达（write through）
- 写回（write back）
1. 写直达
上面我们讲到，什么时候将 Cache 的数据同步到内存极为重要。
我们采取写直达的方法：当数据写入Cache时，我们会将该数据同步到内存。
其实这里一开始有个疑问，不知道读者有没有这个问题。
为什么我们的CPU写入数据的时候，这个数据会不在 CPU Cache 中呢？
按道理来说，CPU 需要获取某些数据时，会在磁盘/内存中将数据缓存到 CPU Cache 中，然后读入到相应的寄存器进行数据的计算，那为什么会出现数据不在 CPU Cache 的情况呢？
我们的 CPU Cache 是有大小限制的，比如 L1 Cache，一般数据和指令一共占 64KB。如果我们的CPU Cache 满了，那么会启动 CPU Cache 的淘汰策略，
将一些CPU Cache 淘汰掉。注意：这里淘汰的是 CPU Cache 的单位，也就是 CPU Line（缓存块）
这里介绍下 CPU Cache 的淘汰策略：
- LRU策略：老生常谈，淘汰当前最近最少使用的
- Random策略：随机淘汰
测试人员发现，一般情况下，LRU 的淘汰策略要比 Random 的淘汰策略效果要好一点。
2. 写回
我们观察上面的 写直达，可以发现存在一个缺点，我们每次 CPU 执行写入操作时，都会将该笔操作写入到内存中。
我们之前聊过，CPU 写内存是十分浪费时间的，如果频繁写的话，会极大的降低 CPU 的性能。
于是，新的写回机制出现了：**当发生写操作时，新的数据仅仅被写入 CPU Block 中，只有当修改过的 CPU Block 被替换时，
才需要写入到内存中。**极大的减少了写回内存的频率，这样便可以提高系统的性能。
CPU Block：CPU Line 中存放数据的位置
- 当前发生写操作时，首先检查我们当前的数据是否在 CPU Cache 中
- 如果存在 CPU Cache 里面，则直接将当前数据更新到 CPU Blcok 中并将 CPU Blcok 标记为 脏
- 如果不存在 CPU Cache 中，则需要给当前的数据分配一个 CPU Block
- 如果这个 CPU Block 不为脏，则需要从内存读取当前要写入的数据到 CPU Block 中，在写入到 CPU Block 中，随后将该 CPU Block标记为 脏
- 如果这个 CPU Block 为脏，则需要将之前这个位置的写回到内存，然后需要从内存读取当前要写入的数据到 CPU Block 中，在写入到 CPU Block 中，随后将该 CPU Block标记为 脏
- 这里比较疑惑的地方，主要在于：为什么我们会再次去内存重新读取一遍数据？
- 这里我们先明确下，缓存块（Cache Line）大小为 64字节，CPU 写入高速缓存可以是不同的大小（1、2、4、8字节）
- 如果我们的 CPU 一次性写入 4 字节，将这 4 字节全部更新到 Cache Block 中，会导致什么问题？
- 可能会出现数据不一致性，你当前的更新仅仅更新了这个 4 字节的数据，而其余 60 字节的数据有没有更新，你这边无法得知
- 所以，我们只有去主内存中重新加载一遍该 Cache Block，在重新写入 4 字节的数据，才会保持数据一致
- 发生的场景：主要发生在多CPU、多核心的状态下，不同的核心对内存的改变。
三、缓存一致性问题
目前，由于电脑的飞速发展，我们的 CPU 都是多核的。我们前面讲过 L1 Cache、L2 Cache 是核心各自独有的，那么就会带来缓存不一致性。
我们下面举一个缓存不一致的例子：
如果我们的 A 号执行了 i++ 的语句后，为了性能考虑，为执行我们之前所说的写回策略，将 i = 1 的值写回到 L1/L2 Cache，然后将对应的 Block 标记为脏的，等下次被替换时，再重新刷新到内存中。
但这个时候，我们可以明显的发现，如果我们 B 号重新读取 i 的话，其实读到的数据是 i = 0
这样，我们 B 号读取的数据其实是错误的，此时 i 的值已经被修改为 1 了。这就是所谓的 缓存一致性问题
那么，怎么解决此问题呢？简单来说，我们需要实现一种机制，能够让两个核心的数据进行同步。
实现这个机制的，要做到以下两点：
- 第一点：某个核心CPU里面的 Cache 数据更新时，需要通知到其他核心的 Cache，这个被称为写传播
- 第二点：某个CPU核心对数据的操作顺序，必须在其他核心看起来顺序是一样的，被称为事务的串行化
第一点很容易理解，第二点如下：
要实现事务，就要做到两点：
- CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；
- 要引入「锁」的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。
1. 总线嗅探
对于我们的第一点，也就是写传播，利用的是 CPU 总线嗅探的方式。
总线嗅探的工作机制：当 A 号 CPU 核心修改了 L1 Cache 中 i 变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个 CPU 核心都会监听总线上的广播事件，
并检查是否有相同的数据在自己的 L1 Cache 里面，如果 B 号 CPU 核心的 L1 Cache 中有该数据，那么也需要把该数据更新到自己的 L1 Cache。
我们的总线嗅探并不能保证事务的串行化，于是，这个时候出现了一个协议，解决了事务串行化的问题。
这个协议的名称叫做：MESI协议
2. MESI 协议
MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：
- Medified：已修改
- Exclusive：独占
- Share：共享
- Invalidated：无效的
「已修改」状态就是我们前面提到的脏标记，代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里。而「已失效」状态，表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。
「独占」和「共享」状态都代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致性的。
独占」和「共享」的差别在于，独占状态的时候，数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。
另外，在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态。
那么，「共享」状态代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。
可能只看上面的有点绕，我们举个例子：
当 A 号 CPU 核心从内存读取变量 i 的值，数据被缓存在 A 号 CPU 核心自己的 Cache 里面，此时其他 CPU 核心的 Cache 没有缓存该数据，于是标记 Cache Line 状态为「独占」，此时其 Cache 中的数据与内存是一致的；
然后 B 号 CPU 核心也从内存读取了变量 i 的值，此时会发送消息给其他 CPU 核心，由于 A 号 CPU 核心已经缓存了该数据，所以会把数据返回给 B 号 CPU 核心。在这个时候， A 和 B 核心缓存了相同的数据，Cache Line 的状态就会变成「共享」，并且其 Cache 中的数据与内存也是一致的；
当 A 号 CPU 核心要修改 Cache 中 i 变量的值，发现数据对应的 Cache Line 的状态是共享状态，则要向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后 A 号 CPU 核心才更新 Cache 里面的数据，同时标记 Cache Line 为「已修改」状态，此时 Cache 中的数据就与内存不一致了。
如果 A 号 CPU 核心「继续」修改 Cache 中 i 变量的值，由于此时的 Cache Line 是「已修改」状态，因此不需要给其他 CPU 核心发送消息，直接更新数据即可。
如果 A 号 CPU 核心的 Cache 里的 i 变量对应的 Cache Line 要被「替换」，发现 Cache Line 状态是「已修改」状态，就会在替换前先把数据同步到内存。
四、总结
CPU 在读写数据的时候，都是在 CPU Cache 读写数据的，原因是 Cache 离 CPU 很近，读写性能相比内存高出很多。对于 Cache 里没有缓存 CPU 所需要读取的数据的这种情况，CPU 则会从内存读取数据，并将数据缓存到 Cache 里面，最后 CPU 再从 Cache 读取数据。
而对于数据的写入，CPU 都会先写入到 Cache 里面，然后再在找个合适的时机写入到内存，那就有「写直达」和「写回」这两种策略来保证 Cache 与内存的数据一致性：
写直达，只要有数据写入，都会直接把数据写入到内存里面，这种方式简单直观，但是性能就会受限于内存的访问速度；
写回，对于已经缓存在 Cache 的数据的写入，只需要更新其数据就可以，不用写入到内存，只有在需要把缓存里面的脏数据交换出去的时候，才把数据同步到内存里，这种方式在缓存命中率高的情况，性能会更好；
当今 CPU 都是多核的，每个核心都有各自独立的 L1/L2 Cache，只有 L3 Cache 是多个核心之间共享的。所以，我们要确保多核缓存是一致性的，否则会出现错误的结果。
要想实现缓存一致性，关键是要满足 2 点：
第一点是写传播，也就是当某个 CPU 核心发生写入操作时，需要把该事件广播通知给其他核心；
第二点是事物的串行化，这个很重要，只有保证了这个，才能保障我们的数据是真正一致的，我们的程序在各个不同的核心上运行的结果也是一致的；
基于总线嗅探机制的 MESI 协议，就满足上面了这两点，因此它是保障缓存一致性的协议。
MESI 协议，是已修改、独占、共享、已失效这四个状态的英文缩写的组合。整个 MSI 状态的变更，则是根据来自本地 CPU 核心的请求，或者来自其他 CPU 核心通过总线传输过来的请求，从而构成一个流动的状态机。另外，对于在「已修改」或者「独占」状态的 Cache Line，修改更新其数据不需要发送广播给其他 CPU 核心。
