缓存一致性协议

CPU缓存

在计算机系统中，用于减少处理器访问内存所需要的平均时间的部件是CPU高速缓存(CPU Cache，后续段落称为缓存)，位于金字塔式存储体系自顶向下的第二层，仅次于CPU寄存器。

当处理器发出内存访问请求时，会先查看缓存内是否有请求数据：如果存在，则不经访问内存直接返回该数据；如果不存在，则要先把内存中的相应数据载入缓存，再将其返回处理器。

一般CPU提供了三级缓存：L1、L2和L3。其中L1分两部分：L1P用于存放代码，L1D存放数据；通常L2是core独占的，然后整个socket共享L3。CPU想要访问一段数据的时候，会先访问缓存，当我们需要的数据在cache中被缓存了，我们就称为一次“命中（hit）”，反之当数据不存在的时候，我们称为一次”缺失（miss）“。当我们的计算机系统存在多级缓存的时候，计算机在进行数据访问的时候会逐级进行查找，即：CPU首先从 L1 cache 进行查找，当数据幸运躺在L1 cache时，我们就将数据返回给CPU（一次缓存命中），但是当L1 cache不存在这段数据的话，CPU会将这一次查找延伸到下一级缓存L2 cache，那么L1 cache的访问就是一次缓存缺失；CPU在L2 cache进行查找的时候，如果命中了就会将数据返回给CPU，如果缺失就继续延伸到下一级缓存（如果不存在后续缓存就到内存中查找）。

[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index
index0/ index1/ index2/ index3/ 
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/size 
32K
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index1/size 
32K
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index2/size 
4096K
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index3/size 
16384K
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 
64
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size 
64
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size 
64
[root@mysql-server ~]# cat /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size 
64

缓存有多快

缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。

Q: 先遍历再排序速度快还是先排序再遍历速度快？

在处理器看来，缓存是一个透明部件。因此，程序员通常无法直接干预对缓存的操作。但是，确实可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。

• 空间局部性：最近引用过的内存位置以及其周边的内存位置容易再次被使用。空间局部性比较常见于循环中，比如在一个数列中，如果第3个元素在上一个循环中使用，则本次循环中极有可能会使用第4个元素。

• 时间局部性：最近刚刚被引用过的一个内存位置容易再次被引用，比如在调用一一个函数的时候，前不久才调取过的本地参数容易再度被调取使用。

  更详细的内容可以参考如何理解计算机操作系统中的局部性原理，如果感兴趣，可以看一下StackOverflow上的讨论java - Why is processing a sorted array faster than processing an unsorted array? - Stack Overflow

缓存一致性问题

上一部分提及了访问数据是如何在不同level的cache中查找的，但是缓存不光有读操作，还有写操作。现在CPU都是多核设计，通常L1/L2 cache是核心各自都有的，那么在多个CPUcache中存在同一个内存对象的值情况下，多个CPU同时操作该对象时会发生什么呢？

MESI Protocol

常用的一致性协议有 snooping 协议，也称为窥探协议。

该协议对总线上的操作进行监听，例如：一个CPU_A，对变量X进行了写操作，但是还未回写到memory，而另外一个CPU_B需要读取变量X，这时如果直接从memory获取变量X的值，是过期值，而CPU_A能够从总线上窥探到该次读操作，把X值写入memory，而CPU_B的读操作由于未得到响应，其会重新发起读请求，这时就能从memory读取到最新值。

具体的实现有MESI协议，MESI指的是4个状态：

状态	描述
I(Invalid、无效)	该CPU的缓存中该对象已失效
S(Shared、共享)	该CPU的缓存中该对象存在在其他CPU缓存中，即共享
E(Exclusive、独占)	该CPU的缓存中该对象只存在该CPU缓存中，其他CPU缓存中的该对象变为Invalid状态
M(Modified、已修改)	该CPU的缓存中该对象已经被修改，在变为Invalid状态时需要将数据写回内存

要理解这4个状态之间如何流转，需要先区分当前CPU对缓存行的本地操作与在总线上窥探到的其他CPU的远程操作：

• 本地读（Local Read）：当前CPU读取自己缓存中的该对象
• 本地写（Local Write）：当前CPU修改自己缓存中的该对象
• 远程读（Remote Read）：在总线上窥探到其他CPU发起了对该对象的读请求
• 远程写（Remote Write）：在总线上窥探到其他CPU发起了对该对象的写请求（即其他CPU发出了Invalidate广播）

MESI协议的状态转移可以总结为下表：

当前状态	本地读	本地写	远程读	远程写
I(Invalid)	→ E（其他CPU缓存中没有该行）或 → S（其他CPU缓存中有该行）	→ M（先发起RFO获取独占权）	保持I	保持I
S(Shared)	保持S	→ M（先广播Invalidate使其他缓存失效）	保持S	→ I
E(Exclusive)	保持E	→ M（无需总线事务）	→ S	→ I
M(Modified)	保持M	保持M	→ S（数据写回内存或直接转发给请求方）	→ I（数据写回内存或直接转发给请求方）

其中“本地写、当前状态为I → M”意味着写未命中：CPU需要先在总线上发起一个RFO（Read For Ownership）请求，拿到该缓存行的独占权之后才能进行修改。

结合文章开头的例子，推演一下CPU_A写X、CPU_B读X的过程中两个缓存的状态变化：

1. CPU_A读X：A本地缺失，从内存加载X，假设此时没有其他CPU持有X → A：E
2. CPU_B读X：B发起读请求，A在总线上窥探到该读请求，直接把数据转发给B（cache-to-cache transfer），无需访问内存 → A：S、B：S
3. CPU_A写X：A先广播Invalidate将B缓存中的X置为无效，再修改本地副本，此时内存中的X还是旧值 → A：M、B：I
4. CPU_B再读X：B发起读请求，A在总线上窥探到该请求，把最新的X写回内存（也可以直接转发给B），B的本次读由于未得到响应会重新发起读请求，这时就能从内存读取到最新值 → A：S、B：S

MESI在线演示demo： https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm

Store Buffer与Invalidate Queue

严格按MESI执行仍然存在性能问题：广播Invalidate的CPU需要等待其他CPU回复确认（Invalidate Acknowledge）才能继续，发起RFO的CPU也要等待数据返回，等待期间当前CPU都被白白阻塞。为此硬件引入了两个缓冲：

• Store Buffer（存储缓冲）：本地写先写入Store Buffer并异步等待其他CPU的确认，当前CPU不必阻塞，可以继续执行后面的指令
• Invalidate Queue（失效队列）：收到Invalidate请求的CPU先将其放入队列并立即回复确认，等空闲时再真正处理（将对应的缓存行置为Invalid）

这两个缓冲提高了性能，代价是放松了一致性：Store Buffer中的写对当前CPU之外还不可见，Invalidate Queue中的请求没处理完之前当前CPU可能仍在使用实际已失效的缓存行。程序实际执行的顺序和内存操作对其他CPU可见的顺序不再一致，并发编程中的“可见性”问题的硬件根源正在于此。

可以看一个经典例子：

CPU0	CPU1
x = 1	y = 1
r1 = y	r2 = x

即使x、y的初始值都是0，程序结束后r1和r2也完全可能同时为0：CPU0把x=1放入自己的Store Buffer（对CPU1不可见）之后就去读y，CPU1同理。要让程序的行为符合直觉，就需要使用内存屏障（Memory Barrier，CPU层面也称Fence）：写屏障会等待Store Buffer排空，保证屏障之前的写操作先于之后的写操作对其他CPU可见；读屏障会先处理完Invalidate Queue中的请求，保证屏障之后的读操作能看到之前其他CPU写入的最新值。这也是Java的volatile、Go的atomic等上层同步原语的硬件基础。

顺带一提，MESI并不是终点：MOESI增加了O(Owned)状态，允许脏数据处于共享状态，由持有者直接转发给请求方，省去一次内存写回；MESIF则用F(Forward)状态优化共享数据的转发。这类变体的思路都是一致的——尽量避免访问下一级存储。

是否被CPU cache的数据访问差异

这一节的重点在于：如何借助缓存的空间局部性来优化代码的执行速度，并回答文章开头留下的问题——先排序再遍历和先遍历再排序，谁更快？

数据是否命中缓存，访问延迟的差距是按数量级来计的，现代CPU各级存储的典型访问延迟大致如下：

存储层级	典型延迟（cycles）	典型延迟（时间）	典型容量
寄存器	<1	<1ns	-
L1 cache	~4	~1ns	32K
L2 cache	~12	~4ns	4096K
L3 cache	~40	~15ns	16384K
内存	~200+	~60~100ns	-

具体数值随CPU型号不同而不同，这里只关心数量级，容量的例子来自文章开头的机器。

缓存的意义就在于利用程序的局部性，让大部分访问落在靠上的层级，把平均访问延迟大幅拉低。

顺序访问与随机访问

同样的时间复杂度，访问模式不同，实际性能可以差出一个数量级。以遍历二维数组为例：

// 行优先遍历：相邻访问的地址连续
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

// 列优先遍历：相邻访问的地址相隔一整行
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += a[i][j];

数组在内存中按行优先（row-major）排列，行优先遍历时，一次miss载入的整条cache line（64字节，例如16个int）会被后续访问全部命中；列优先遍历时，相邻两次访问的地址相差N个元素，每次访问基本都会跨入新的cache line。当N较大、数组远超缓存容量时，两者的性能差距可达数倍。此外顺序访问还会被CPU的硬件预取器（Prefetcher）识别，提前把后续数据取入缓存，随机访问则没有这个待遇——这也是数组和链表理论上遍历复杂度都是O(n)，实际性能却差出数倍的原因：链表节点分散在堆内存的各个位置，指针跳转对缓存极不友好。

回到开头的问题

先排序再遍历，还是先遍历再排序？这个问题的答案取决于“遍历”里做了什么：

1. 遍历中有数据相关的分支：StackOverflow上那个著名案例就是这种情况，对未排序的数组执行 if (data[i] >= 128) sum += data[i];，分支的结果近似随机，CPU的分支预测器大量预测失败，而每次失败都要清空流水线（大约十几到二十个cycle）；排序之后分支的结果变得稳定，预测几乎全部命中，执行速度大幅提升。注意这个案例提速的主因是分支预测而非缓存，这点常被误解；
2. 遍历是纯顺序扫描（例如单纯求和）：排不排序对访问模式影响很小，反正都是顺序读，而排序本身却是实打实的开销，此时先排序并不划算；
3. 遍历中包含随机访问（例如按key查找、去重）：排序能让访问范围收敛、分布集中，甚至可以用二分替代线性查找，此时排序的收益非常明显。

所以并不存在绝对答案：排序是O(N log N)的开销，遍历是O(N)的开销，只有当排序让遍历阶段的收益超过排序自身的成本时（遍历逻辑重、需要多趟遍历、或遍历中存在随机访问与不可预测分支），先排序再遍历才更快。

伪共享（False Sharing）：多核场景下的缓存行陷阱

前面提到MESI以缓存行（cache line，通常64字节）为单位维护一致性，这带来了多核场景下一个非常隐蔽的性能问题：当两个不相关的变量恰好落在同一条缓存行上、又分别被运行在不同CPU上的线程频繁修改时，该缓存行会在两个CPU之间来回失效、来回传输（即缓存行在核间“乒乓”），每次写都要触发一轮Invalidate与状态的来回切换。两个线程明明没有共享任何数据，性能却因为一致性协议而急剧下降，这就是伪共享（False Sharing）。

例如下面这个Go结构体：

type Counter struct {
    a int64
    b int64
}

a和b一共只占16字节，会落在同一条64字节的缓存行上。两个goroutine分别在不同的核上高频修改a和b时，这条缓存行就会在两个核的缓存间反复弹跳，谁的写都会让对方的缓存行失效，性能远低于预期。

解决思路是空间换时间——缓存行填充（padding），让热点变量各自独占一条缓存行：

type PaddedCounter struct {
    a int64
    _ [56]byte // 填充56字节，a与填充共占满一条64字节的缓存行，使b从下一条缓存行开始
    b int64
    _ [56]byte
}

Java中也有对应的手段（@Contended 注解或手动填充），JDK中的 LongAdder 则是另一种思路：把热点分散到多个cell上再汇总。伪共享的排查依赖性能工具（例如perf的cache-miss指标），因为它不会带来错误，只会让人“莫名其妙地慢”。

Reference

1. MESI protocol - Wikipedia
2. What Every Programmer Should Know About Memory - Ulrich Drepper
3. Memory Barriers: a Hardware View for Software Hackers - Paul E. McKenney
4. False sharing - Wikipedia
5. Why is processing a sorted array faster than processing an unsorted array? - Stack Overflow