MESI 缓存一致性协议

1. 背景

问题 ①：CPU 与内存读写速度差距大，直接与内存交互影响 CPU 性能。

解决方法：在 CPU 与内存之间插入多级缓存。

CPU 访问内存数据时，拷贝一块连续的“缓存行”到 cache 中，再操作 cache 中的数据；cache 中的数据再在需要时同步回内存。（扩展：存在 “伪共享问题”）

问题 ②：单核 CPU 性能发展遇到瓶颈。

解决办法：多核 CPU 并行工作。

为减少缓存行冲突，提高缓存命中率，多核 CPU 都拥有独立的 cache。（不同线程通常执行不同代码，访问的内存数据不聚集，共用缓存会经常无法命中）

问题 ③：对于同一份内存数据，当有 CPU 在修改时，该数据在不同 CPU 缓存的值可能不一致。

解决方法：总线锁。

限制同一时间内，只有一个 CPU 能访问内存数据。

问题 ④：总线锁开销太大，且仍需额外解决缓存的冲突。

解决办法：MESI 缓存一致性协议。

核心思想：通过降低锁的粒度，减少使用总线锁的频率，从而达到性能优化。

2. 原理

MESI 协议维护一个有限状态机，对每个 CPU 拷贝的每个缓存行都赋予一个状态属性；当感知到对某个缓存行的读写事件发生时，根据该缓存行的状态，对其进行一致性处理。

CPU 通过 “总线嗅探（Bus snooping）” 来感知其他 CPU 读写事件的发生：每个缓存中包含一个监视器（snooper），监听器会监视总线上的每个事务。如果总线上出现修改共享缓存行的事务，则所有监听器都会检查其缓存行是否具有该共享缓存行的相同副本。

3. 缓存行状态

MESI 协议对每个缓存行赋予一个状态属性，MESI 协议就是由这四种状态的首字母来命名的：

• M：Modified，修改
• E：Exclusive，独占
• S：Shared，共享
• I：Invalid，失效

由于只有 4 种状态，可以只用 2 bit 进行编码。

对单个缓存行，根据缓存数据与内存数据是否一致，还可分为两种状态：

• 脏的（dirty）：该缓存行的数据与内存数据不一致。可能是由于缓存行被修改，也可能是内存数据被修改。
• 干净的（clean）：缓存行与内存数据相同。

“脏的” 与 “干净的” 只是为了便于理解而划分的状态，能与 MESI 四个状态相对应，不会消耗 bit 去记录。

Modified 状态

Modified 状态表示缓存行数据已被当前 CPU 修改，且该缓存行是“脏的”，此时缓存行的数据是最新的。

Modified 状态的缓存行仅被当前 CPU 独占式缓存。

Exclusive 状态

Exclusive 状态表示缓存行仅被当前 CPU 独占式缓存，且该缓存行是“干净的”。

Exclusive 状态是对 Shared 状态的一种优化，目的是在写入时减少发布一次 BusUpgr 总线事件。

Shared 状态

Shared 状态表示缓存行 可能 被其他 CPU 同时缓存。该缓存行是“干净的”。

Shared 状态不是精确的，当其他 CPU 丢弃了共享的缓存行，此时当前缓存行为独占缓存，但不会变为 Exclusive 状态。

Invalid 状态

Invalid 状态表示缓存行已失效。该缓存行是“脏的”，此时内存的数据是最新的。

Invalid 状态可以视作没有缓存该数据，可以忽略其他 CPU 的读写事件。

4. 读写事件

引起缓存行状态转换的事件可分为两类：

• CPU 侧事件：当前 CPU 对该缓存行的读写行为。
• 总线侧事件：其他 CPU 对与该缓存行相同的内存数据的读写缓存行为。这些事件会通过总线通知所有 CPU。

此外，还有一些衍生处理事件，在某些事件发生时辅助缓存行进行状态更新。

1）CPU 侧事件

PrRd 事件

当前 CPU 对该缓存行进行读取。

缓存命中时，不会改变缓存行状态；缓存未命中时，根据是否已经被其他 CPU 缓存，设置为 Shared 或 Exclusive 状态。

• 缓存命中时，直接读取缓存。
• 缓存未命中时，发布 BusRd 事件，尝试从其他 CPU 拉取缓存后再读取： - 其他 CPU 有缓存：从其他 CPU 发布的 FlushOpt 事件中获取缓存行。 - 其他 CPU 都没有缓存：从内存中拷贝缓存行。

PrWr 事件

当前 CPU 对该缓存行进行修改。

会将缓存行设置为 Modified 状态。

• 缓存命中时，判断命中缓存行的具体状态： - Modified / Exclusive 状态：直接写入缓存。 - Shared 状态：发布 BusUpgr 事件，将共享缓存转换为独占式缓存，再写入。
• 缓存未命中时，发布 BusRdX 事件，尝试从其他 CPU 拉取缓存后再写入： - 其他 CPU 有缓存：从其他 CPU 发布的 FlushOpt 事件中获取缓存行。 - 其他 CPU 都没有缓存：从内存中拷贝缓存行。

发布 BusUpgr 或 BusRdX 获取独占式缓存的行为，又称为 RFO（Request For Ownership）操作。当 CPU 试图写入 Shared / Invalid 状态的缓存行时，会发出此操作，将所有其他 CPU 的该行缓存状态设置为 Invalid。

2）总线侧事件

BusRd 事件

其他 CPU 请求读取与该缓存行相同的内存数据。

• 只有读取时缓存未命中时（Invalid && PrRd），才会发布此事件。 - 读取时，若缓存命中（缓存行状态为 Modified / Exclusive / Shared），则直接读取缓存。
• 事件的发送端必定未命中缓存，因此需要让接收方发布 FlushOpt 事件，将缓存行同步给发送端。 - 协议根据设定的算法，从有缓存的 CPU 中选出一个来发布 FlushOpt 事件（不是每个都发）。
• 若接收方缓存命中（缓存行状态为 Modified / Exclusive / Shared），则需要转换为 Shared（独占变共享）。

BusRdX 事件

其他 CPU 请求写入与该缓存行相同的内存数据，且该数据尚未被待写入的 CPU 缓存。

该事件目的是获取该数据的独占缓存权，为后续的写入操作铺平道路。

BusRdX 中的 X 即是“独占（Exclusive）”的意思，Rd 表示要先将数据缓存到 cache，之后再对缓存进行修改。

• 只有写入时缓存未命中时（Invalid && PrWr），才会发布此事件。 - Modified / Exclusive 状态是独占的，可直接写入缓存，不用发事件通知其他 CPU。 - Shared 状态缓存命中，写入时发布的是 BusUpgr 事件。
• 事件的发送端必定未命中缓存，因此需要让接收方发布 FlushOpt 事件，将缓存行同步给发送端。
• 若接收方缓存命中（缓存行状态为 Modified / Exclusive / Shared），则需要转换为 Invalid。

BusUpgr 事件

其他 CPU 请求写入与该缓存行相同的内存数据，且该数据已经被待写入的 CPU 缓存。

BusUpgr 中的 Upgr 即是“升级（Upgrade）”的意思，将共享缓存转换为独占缓存，以便后续对缓存进行修改。

• 只有在对 Shared 状态的缓存行进行写入时（Shared && PrWr），才会发布此事件。 - Modified / Exclusive 状态是独占的，可直接写入缓存，不用发事件通知其他 CPU。 - Invalid 状态缓存未命中，写入时发布的是 BusRdX 事件。
• 事件的发送端必定是 Shared 状态，是缓存命中且“干净的”，因此接收端不用进行 FlushOpt 缓存行同步。
• 只有 Shared 或 Invalid（缓存未命中）状态会收到此事件。 - Modified / Exclusive 状态是独占的，不会有其他 CPU 拥有相同数据缓存，更不会有对相同数据的写入。因此这两个状态的缓存行不会收到 BusUpgr 事件。
• 若接收方缓存行状态为 Shared （缓存命中），则需要转换为 Invalid。

3）衍生处理事件

Flush 事件

将缓存行强制写回内存中。

FlushOpt 事件

将缓存行发布到总线上，通过总线从一个 CPU 的 cache 直接同步到另一个 CPU 的 cache，而不是先写回内存再从内存读取。

内存也可以设置监听器，从总线上监听 FlushOpt 事件、获取缓存行并更新内存。

这使得 “更新其他 CPU 的缓存行” 与 “更新内存” 从串行改为并行，提高了性能。

5. 状态转换

1）当前为 Modified 状态

stateDiagram-v2
Modified --> Modified : PrRd / PrWr
Modified --> Shared : BusRd
Modified --> Invalid : BusRdX

Modified -- PrRd --- Modified

本地 CPU，对 Modified 状态缓存行，发起读取请求：

• 缓存命中，直接读取缓存行的数据。
• 不影响其他 CPU（Modified 状态是独占的）。
• 状态不变。

Modified -- PrWr --- Modified

本地 CPU，对 Modified 状态缓存行，发起写入请求：

• 缓存命中，直接写入缓存行的数据。
• 不影响其他 CPU（Modified 状态是独占的）。
• 状态不变。

Modified -- BusRd --- Shared

其他 CPU，对与该 Modified 缓存行相同的内存数据，发起读取请求：

• 由于 Modified 状态的缓存行数据比内存数据要新，所以要让其他 CPU 获取到该缓存行的数据。
• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给内存与发布事件的 CPU。
• 当前 CPU 缓存行状态转换为 Shared。
• 要读取的 CPU 缓存行状态为 Shared。

Modified -- BusRdX --- Invalid

其他 CPU，对与该 Modified 缓存行相同的内存数据，发起写入请求：

• 由于 Modified 状态的缓存行数据比内存数据要新，所以要让其他 CPU 获取到该缓存行的数据。
• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给内存与发布事件的 CPU。
• 当前 CPU 缓存行状态转换为 Invalid。
• 要写入的 CPU 缓存行状态为 Modified。

2）当前为 Exclusive 状态

stateDiagram-v2
Exclusive --> Exclusive : PrRd
Exclusive --> Modified : PrWr
Exclusive --> Shared : BusRd
Exclusive --> Invalid : BusRdX

Exclusive -- PrRd --- Exclusive

本地 CPU，对 Exclusive 状态缓存行，发起读取请求：

• 缓存命中，直接读取缓存行的数据。
• 不影响其他 CPU（Exclusive 状态是独占的）。
• 状态不变。

Exclusive -- PrWr --- Modified

本地 CPU，对 Exclusive 状态缓存行，发起写入请求：

• 缓存命中，直接写入缓存行的数据。
• 不影响其他 CPU（Exclusive 状态是独占的）。
• 当前 CPU 缓存行状态改为 Modified。

Exclusive -- BusRd --- Shared

其他 CPU，对与该 Exclusive 缓存行相同的内存数据，发起读取请求：

• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给发布事件的 CPU（缓存行是干净的，无需同步到内存）。
• 当前 CPU 缓存行状态转换为 Shared。
• 要读取的 CPU 缓存行状态为 Shared。

Exclusive -- BusRdX --- Invalid

其他 CPU，对与该 Exclusive 缓存行相同的内存数据，发起写入请求：

• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给发布事件的 CPU（缓存行是干净的，无需同步到内存）。
• 当前 CPU 缓存行状态转换为 Invalid。
• 要写入的 CPU 缓存行状态为 Modified。

3）当前为 Shared 状态

stateDiagram-v2
Shared --> Shared : PrRd / BusRd
Shared --> Modified : PrWr
Shared --> Invalid : BusRdX / BusUpgr

Shared -- PrRd --- Shared

本地 CPU，对 Shared 状态缓存行，发起读取请求：

• 缓存命中，直接读取缓存行的数据。
• 不影响其他 CPU（只读）。
• 状态不变。

Shared -- PrWr --- Modified

本地 CPU，对 Shared 状态缓存行，发起写入请求：

• 缓存命中，写入缓存行的数据。
• 由于其他 CPU 也缓存了相同数据，写入前需向总线发送 BusUpgr 事件，通知其他 CPU 处理。
• 当前 CPU 缓存行状态改为 Modified。
• 其他 CPU 缓存行状态从 Shared 改为 Invalid。

Shared -- BusRd --- Shared

其他 CPU，对与该 Shared 缓存行相同的内存数据，发起读取请求：

• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给发布事件的 CPU（缓存行是干净的，无需同步到内存）。
• 当前 CPU 缓存行状态不变。
• 要读取的 CPU 缓存行状态为 Shared。

Shared -- BusRdX / BusUpgr --- Invalid

其他 CPU，对与该 Shared 缓存行相同的内存数据，发起写入请求：

• 发出 FlushOpt 事件，将当前缓存行发布到总线上，同步给发布事件的 CPU（缓存行是干净的，无需同步到内存）。
• 当前 CPU 缓存行状态转换为 Invalid。
• 要写入的 CPU 缓存行状态为 Modified。

4）当前为 Invalid 状态

stateDiagram-v2
Invalid --> Shared/Exclusive : PrRd
Invalid --> Modified : PrWr
Invalid --> Invalid : BusRd / BusRdX / BusUpgr

Invalid -- PrRd --- Shared / Exclusive

本地 CPU，对 Invalid 状态缓存行，发起读取请求：

• 缓存未命中。需向总线发布 BusRd 事件。
• 若其他 CPU 有缓存，则从其他 CPU 收到 BusRd 事件后发布的 FlushOpt 事件中获取缓存行。 - 此时当前 CPU 缓存行状态转换为 Shared。 - 其他 CPU 缓存行状态会在收到 BusRd 事件后转换为 Shared。
• 若其他 CPU 都没有缓存，则从内存中拷贝缓存行。 - 当前 CPU 缓存行状态为 Exclusive。

Invalid -- PrWr --- Modified

本地 CPU，对 Invalid 状态缓存行，发起写入请求：

• 缓存未命中。需向总线发布 BusRdX 事件。
• 若其他 CPU 有缓存，则从其他 CPU 收到 BusRdX 事件后发布的 FlushOpt 事件中获取缓存行。 - 其他 CPU 缓存行状态会在收到 BusRdX 事件后转换为 Invalid。
• 若其他 CPU 都没有缓存，则从内存中拷贝缓存行。
• 当前 CPU 缓存行状态为 Modified。

Invalid -- BusRd --- Invalid

其他 CPU，对与该 Invalid 缓存行相同的内存数据，发起读取请求：

• 忽略事件，状态不变。

Invalid -- BusRdX / BusUpgr --- Invalid

其他 CPU，对与该 Invalid 缓存行相同的内存数据，发起写入请求：

• 忽略事件，状态不变。

6. 性能优化

MESI 协议的最大性能开销源于写入前的 RFO 操作，该操作负责获取独占式缓存（仅在命中 Shared 或 Invalid 时触发）。

RFO 操作会发出 BusRdX 或 BusUpgr 事件，并执行以下等待：

• 缓存未命中时，等待从内存或其他 CPU 获取缓存行；
• 其他 CPU 有缓存副本时，等待其他缓存副本失效（转换为 Invalid）。

主要的优化方式有两种：写缓冲区、无效化队列。

这两种优化结合，能大幅提高 CPU 性能。但会失去缓存状态的强一致性，取而代之的是最终一致性，会带来内存重排的问题。

写缓冲区

写缓冲区（Store Buffer）的作用是将 RFO 操作异步化，CPU 无需等待 RFO 完成即可继续执行后续指令。

这是在写入操作的当前 CPU 端进行的优化，即对 PrWr 事件处理的优化。·

写缓冲区的工作流程如下：

1. 写入时，若触发 RFO 操作，将写入信息暂存到写缓冲区中。
2. CPU 不等待写入完成，继续执行后续指令。
3. RFO 操作完成后，将写缓冲区中暂存的写入信息取出，写入新获取的独占式缓存行。

可将写缓冲区理解为 “待处理写入任务表”，其大小有限（通常 4~64 条目），若持续写入超出容量，CPU 仍需阻塞。

写缓冲区具有写入合并（Write Combining）特性：在 RFO 操作期间，若该缓存行发生了多次写入，写缓冲区会将多次写入合并为同一条目，不会重复触发 RFO 操作。

若对数据的写入操作暂存到写缓冲区，RFO 正在异步执行时，对该数据的读取可能会有如下情况：

• 同一 CPU 发起读取，会直接读取到写缓冲区中的最新数据（不影响同一线程的逻辑）。这个机制称为 “存储转发（Store Fowarding）” 。
• 其他 CPU 发起读取，若命中缓存，直接读取缓存中的旧数据（发生内存重排）。
• 其他 CPU 发起读取，未命中缓存，则发布 BusRd 事件。若当前 CPU 在收到事件后已完成写入，则同步新数据；否则可能由其他 CPU 同步旧数据。

写缓冲区优化后，会先执行后续操作，RFO 完成才真正写入缓存，才能被其他 CPU 获取到这次写入。这相当于把前面的 Store 操作移到任意后续操作之后，可能造成 StoreStore 或 StoreLoad 重排。

X86 架构的 CPU 强制写缓冲区按程序顺序提交写入操作，即使后续写入操作命中缓存，也要等待前面的写入 RFO 操作完成后再开始处理。

• 因此，X86 架构不会有 StoreStore 重排。
• 以上规则仅限制写入操作，所以 StoreLoad 重排在 X86 架构上是有可能的。

写屏障（store barrier）会刷新写缓冲区，强制等待所有写操作都已应用到当前 CPU 的缓存中后，才能执行后续指令。确保屏障之前的写操作，不会被重排到屏障后面（必然写入到内存）。

写屏障不能保证其他 CPU 一定对当前写入后的值立即可见，因为其他 CPU 存在无效化队列，在未处理无效事件时仍会访问到旧值。

无效化队列

无效化队列（Invalidate Queues）的作用是减少其他 CPU 发起的 RFO 操作中，等待缓存副本失效的时间。

这是在写入操作的其他 CPU 端进行的优化，即对 BusRdX 或 BusUpgr 事件处理的优化。·

CPU 在收到 BusRdX 或 BusUpgr 事件时，无优化情况下会先将缓存行转换为 Invalid，状态转换完成后才返回 ACK 确认。在使用无效化队列优化时，工作流程如下：

1. 若缓存命中，不执行状态转换，立即返回 ACK 确认。
2. 将该事件暂存到无效化队列中。
3. 后续 CPU 空闲时，从无效化队列中取出事件进行处理（包括状态转换、发布 FlushOpt 事件等）。

无效化队列也会合并多个 BusRdX 或 BusUpgr 事件，当作一个无效事件进行处理。

若缓存行的无效事件已存入无效化队列，对该缓存的读写操作根据不同 CPU 架构有不同的行为：

• X86 架构：每次读写前，强制处理无效事件（包括状态转换、发布 FlushOpt 事件等）。
• ARM 架构：按原本的状态进行读写（视作尚未收到无效事件，直到 CPU 空闲再无效化）。

无效化队列优化后，读取到的值可能是个旧值。相当于把后面的 Load 操作移到任意操作之前（读取之前的值），可能造成 LoadLoad、StoreLoad 重排。

X86 架构每次读写前强制处理无效事件，所以无效队列在该架构不会造成重排。

读屏障（read barrier）会刷新无效化队列，强制等待缓存更新后才能执行后续指令，从而确保其他 CPU 的写操作对当前 CPU 可见。确保屏障之后的读操作，不会被重排到屏障前面（必然读取到最新值）。

写屏障和读屏障不等同于 Release 和 Acquire 语义。Release 和 Acquire 语义还需要处理配对操作、跨线程可见性等。这些语义的底层是通过读写屏障实现的。

7. 衍生协议

MOESI 协议

若多个 CPU 对相同的数据连续写入，每次读写都会将数据发布到总线上，以维持最新的缓存。

MOESI 协议增加了一个 Own 状态，该状态是脏的且共享的。CPU 之间可以直接共享 Own 状态的缓存行，再进行写入操作，无需写入内存。

MESIF 协议

在 Shared 状态下，若遇到 BusRd 等事件，可能每个持有缓存的 CPU 都会同时发出 FlushOpt 事件，造成冗余。

MESIF 协议增加了一个 Forward 状态，等价于 Shared 状态，且指定只有 Forward 状态的 CPU 缓存行才能发出 FlushOpt，避免冗余发送。

只要有 Shared 状态的缓存，则必然有且只有一个 Forward 状态。