CPU缓存和伪共享

CPU缓存

CPU是计算机的大脑，它负责执行程序的指令；内存负责存数据，包括程序自身数据。内存比CPU慢很多，现在获取内存中的一条数据大概需要200多个CPU周期(CPU cycles)，而CPU寄存器一般情况下1个CPU周期就够了。

网页浏览器为了加快速度，会在本机存缓存以前浏览过的数据；传统数据库或NoSQL数据库为了加速查询,常在内存设置一个缓存，减少对磁盘(慢)的IO。同样内存与CPU的速度相差太远，于是CPU设计者们就给CPU加上了缓存(CPU Cache)。如果需要对同一批数据操作很多次，那么把数据放至离CPU更近的缓存，会给程序带来很大的速度提升。例如，做一个循环计数，把计数变量放到缓存里，就不用每次循环都往内存存取数据了。下面是CPU Cache的简单示意图：

随着多核的发展，CPU Cache分成了三个级别：L1、 L2、L3。级别越小越接近CPU，所以速度也更快，同时也代表着容量越小。L1是最接近CPU的，它容量最小，例如32K，速度最快，每个核上都有一个L1 Cache(准确地说每个核上有两个L1 Cache，一个存数据 L1d Cache，一个存指令 L1i Cache)。L2 Cache 更大一些，例如256K，速度要慢一些，一般情况下每个核上都有一个独立的L2 Cache；L3 Cache是三级缓存中最大的一级，例如12MB，同时也是最慢的一级，在同一个CPU插槽之间的核共享一个L3 Cache。就像数据库cache一样，获取数据时首先会在最快的cache中找数据，如果没有命中(Cache miss)则往下一级找，直到三层Cache都找不到，那只有向内存要数据了。一次次地未命中，代表取数据消耗的时间越长。

缓存行(Cache Line)

Cache的最小组成单位是cache line。每一个缓存都是由很多个cache line组成的。每个cache line的大小一般的32字节或者64字节。cache中的数据操作也是以cache line为单位的，也就是一个cache line上的数据会被同时操作。一个Java long型占8个字节，所以从一条缓存行上可以获取到8个long型变量，如果访问一个long型数组，当有一个long被加载到cache中，将会无消耗地加载了另外7个，所以可以非常快地遍历数组。

MESI协议

多核CPU都有自己的专门缓存(一般伪L1,L2),以及用一个CPU插槽之间的核共享缓存(一般为L3)，不同核心的CPU缓存中难免会加载同样的数据，那么如何保证数据的一致性呢，就是 MESI 协议了。
在 MESI 协议中，每个 Cache line 有4个状态，可用 2 个 bit 表示，它们分别是：

1. M(Modified)：这行数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本 Cache 中
2. E(Exclusive)：这行数据有效，数据和内存中的数据一致，数据只存在于本 Cache 中；
3. S(Shared)：这行数据有效，数据和内存中的数据一致，数据存在于很多 Cache 中
4. I(Invalid)：这行数据无效

那么，假设有一个变量i=3（应该是包括变量i的缓存块，块大小为缓存行大小）；已经加载到多核（a,b,c）的缓存中，此时该缓存行的状态为S；此时其中的一个核a改变了变量i的值，那么在核a中的当前缓存行的状态将变为M，b,c核中的当前缓存行状态将变为I。如下图：

伪共享

然而缓存行也存在问题：假设CPU的第一个核需要操作a变量，第二个核需要操作b变量，表面看a和b是没有任何关系的，但是a和b在同一个cache line中，这样假设核心一修改了变量a的值，那么它将会刷新所有和a相关的缓存的数据，b变量也就会受到牵连，最后导致核心二再去缓存读取b变量的时候出现cache miss，需要重新到主存加载新数据，这就是所谓的false share(伪共享)

如何避免伪共享？

为了避免由于 false sharing 导致 Cache Line 从 L1,L2,L3 到主存之间重复载入，我们可以使用数据填充的方式来避免，即单个数据填充满一个CacheLine。
一个典型的例子就是lmax disruptor中的缓存行填充技术。假设cache line的大小是64字节，一个cache line能容纳8个long型变量，disruptor中的做法是在long变量的前面和后面分别填充7个long变量，这样就可以避免我们需要的变量和其他变量在同一个cache line，解决伪共享问题。这就是用空间换时间。

小结

内存执行速度跟不上CPU执行速度，设置缓存改善CPU对数据的读取。缓存容易引发伪共享问题：多核下同个数据可能分布在不同的缓存中或者同一个cache line下，为了避免数据出现不同步的问题，根据MESI协议对数据进行标记，判断数据是否"干净"；解决伪共享的问题可以通过数据填充的方式进行，即单个cache line上只填一个数据。