Cache

DRAM 读取速度太慢，所以就有了缓存。但同时也引入了缓存抖动、伪共享、读后写、一致性等需要解决的问题，这篇博客中就来介绍下相关的概念。

缓存的种类

L1：指令缓存、数据缓存，核独占
L2：数据指令通用，核独占
L3：核共享

这里以包含式 L3 为例：

L3 包含 L1/L2 的所有数据
L3 的目录记录：这行在哪些核的 L1/L2 里

举例：Core 1 想读一个地址：

查 L3 目录
发现 Core 0 有 Modified 副本
通知 Core 0 写回

按照 L1 → L2 → L3 顺序访问，一个 miss 了就下一个，访问速度递减，大小递增。

缓存映射方式

缓存映射方式主要有三种：

直接映射（1 路组相联）
组相联
全相联（缓存行数 = 路数）

下面的动画中详细解释：

👉 点击查看组相联缓存动画演示

缓存行置换算法

常用的是 Tree PLRU（用二叉树近似 LRU）。为什么不用纯 LRU 呢？是因为硬件成本的问题：

存储缓存行状态需要额外的空间
- N 路组相联需要的空间 = log₂(N!) × 组数 = log₂(N!) × (缓存总大小 / 缓存行大小 / N)
更新太频繁
- 在程序运行的过程中，缓存行访问是极度密集的，每次访问就要更新状态、插入链表，会极大的拖慢速度。

这点和页面置换算法很像，由于硬件限制，它也没办法实现纯 LRU，后续的文章中再去说明。

缓存一致性协议

MESI

MESI 的状态机：它把每一行缓存（Cache Line，通常 64 字节）标记为四种状态之一：

状态	含义
M (Modified)	脏数据。只有我有最新版，内存里是旧的。我是老大，可以随便改。
E (Exclusive)	独占。只有我有，但和内存一样。想改可以直接改（变成 M）。
S (Shared)	共享。我有，别人也有。大家只能读，谁想改必须先通知其他人作废。
I (Invalid)	无效。我的数据过时了，不能用。

MOESI（AMD 采用）

在 MESI 的基础上增加了 O (Owned) 状态：

状态	含义
O (Owned)	我有脏数据且是权威副本，但别人也有共享副本（只是他们的是只读的）

解决的问题：MESI 的 S 状态要求数据必须和内存一致。当 M 态的数据被其他核心读取时，必须先写回内存，然后双方都变成 S。

MOESI 的优化：

场景：核心A有M态数据，核心B想读

MESI流程：
  A(M) → 写回内存 → A(S), B(S)  需要访问慢速内存

MOESI流程：
  A(M) → A(O), B(S)  直接核心间传输，不写回内存
  A持有O态，负责将来写回内存

好处：减少内存访问，核心间直接共享脏数据。

MESIF（Intel 采用）

在 MESI 的基础上增加了 F (Forward) 状态：

状态	含义
F (Forward)	特殊的 S 态，负责响应其他核心的读请求

解决的问题：当多个核心都是 S 态时，如果又有一个核心想读，谁来响应？

MESI：所有 S 态核心可能都响应 → 总线冲突/冗余
或者去内存读 → 慢

MESIF 的优化：

场景：A、B、C都有S态副本，D想读

MESI问题：
  A(S), B(S), C(S) 都可能响应 → 谁负责？冲突！

MESIF解决：
  A(F), B(S), C(S)  → 只有F态的A负责响应D的请求
  响应后：A(S), D(F)  → 最新读取者变成F

好处：明确谁负责响应，减少总线冲突。

为什么 Intel 不用 Owned (O) 状态？

关键原因在于 Intel 的 L3 缓存设计（Inclusive Cache）：

Intel 的 L3 通常是 Inclusive（包含式） 的
L3 包含了所有 L1/L2 的数据
如果 L1/L2 里的数据是脏的（Modified），当别的核要读时：
- Intel 的 L3 嗅探机制会介入
- 直接由 L3 或通过 L3 协调把 Modified 数据给出去

换句话说，Intel 架构在 L3 层面隐含实现了类似 “Owned” 的功能（通过缓存层级结构解决）。

所以在核心的一致性协议（MESIF）里，Intel 更关注解决带宽竞争问题（F 状态），而不是脏数据共享——因为脏数据共享已经被 L3 的设计解决了。

Store Buffer

MESI 虽然保证了一致性，但太慢了。当核心 A 要改数据时，它必须发消息给其他核心并等总线通信返回。

解决方案：CPU 引入了 Store Buffer。

核心 A 想写数据，但不想等 MESI 流程
它把数据扔进 Store Buffer（这是核心私有的）
核心 A 立刻认为写操作完成了，继续执行下一条指令
（在后台）等其他核心回复”已作废”后，Store Buffer 里的数据才真正写入 L1 缓存，并对外界可见

副作用（乱序）：这导致了”内存可见性”问题。核心 A 以为写完了，其实数据还卡在私有的 Store Buffer 里。

代码顺序：x = 1; flag = true;
实际发生：x=1 卡在缓冲里，flag=true 先进入了缓存（因为 flag 所在的缓存行可能是 E 态，不需要等）
别人看到的：flag 变成了 true，但 x 还是 0。逻辑崩了！

Invalidate Queue

Invalidate Queue（失效队列） 是与 Store Buffer 配套的另一个优化机制。

背景问题

当核心 A 要修改一个 S 态的缓存行时，它需要发送 Invalidate 消息给其他核心，并等待回复。如果核心 B 很忙，核心 A 就得干等着。

解决方案

CPU 引入了 Invalidate Queue：

核心 B 收到失效请求
不立刻处理，而是把请求扔进 Invalidate Queue
立刻回复 “已作废”（其实还没作废！）
等 B 有空了，再从队列里取出请求，真正把缓存行置为 Invalid

核心A:                           核心B:
  |                                |
  |---- Invalidate 请求 --------->|
  |                                | 放入队列，立刻回复
  |<--- Invalidate ACK -----------|
  |                                |
  | (A以为B已作废，继续执行)        | (B其实还没作废)
  |                                |
  |                                | ...稍后真正作废

副作用（读到旧值）

这会导致核心 B 读到已经被作废的旧数据：

// 初始: x = 0, y = 0

// 核心A                      // 核心B
x = 1;                        while (y == 0);
y = 1;                        print(x);  // 可能打印 0！

A 发送 x 的失效请求，B 放入队列后回复 ACK。A 继续执行 y = 1。B 读到 y == 1 跳出循环，但失效请求还在队列里没处理，读 x 得到旧值 0！

对比 Store Buffer 和 Invalidate Queue

机制	位置	作用	副作用
Store Buffer	写端	写操作先缓冲，不等失效确认	写后读乱序（自己写的别人看不到）
Invalidate Queue	读端	失效请求先缓冲，稍后处理	读到旧值（别人作废的我还没作废）

内存屏障

既然 Store Buffer 和 Invalidate Queue 都会导致乱序，我们就需要屏障指令来强制同步。

指令	作用
`sfence`	Store Fence - 刷新 Store Buffer，确保写操作对外可见
`lfence`	Load Fence - 刷新 Invalidate Queue，确保读到最新值
`mfence`	Full Fence - 同时刷新两者（= sfence + lfence）

缓存中的一些问题

两个核交替修改同一缓存行中的不同变量，互相卡 MESI，造成频繁的缓存行失效。

解决方案：

Padding 填充，让变量独占一个缓存行
设计时避免这种情况出现

冷启动（Cold Start）

第一次访问必然 miss。

解决方案：使用 __builtin_prefetch 预取一下，告诉 CPU 待会要用，让它提前放到缓存中。

缓存污染（Cache Pollution）

大量连续读入/写入时，缓存不断被填满、驱逐、写回，驱逐了热点数据。