缓存一致性:实现方案介绍与 MESI 协议详解

1 缓存一致性的概念

在计算机科学中,缓存一致性(英文:Cache Coherence 或 Cache Coherency)又译为缓存连贯性、缓存同调,是指通过维护数据缓存的连贯性,使多个缓存间的数据保持一致的机制。

在多处理器系统、多核和 NUMA 系统中,每个处理器、核心或节点都会使用专用缓存提高性能,当相同的数据存储在多个缓存副本中时,就可能出现一致性问题。如下图所示:

1
2
3
4
5
6
7
8
9
 +---------+     +-------+
 | Client1 |<--->| Cache |<---+
 +---------+     +---*---+    |
                     |        +--> +-----------------+
                 coherency         | Memory Resource |
                     |        +--> +-----------------+
 +---------+     +---*---+    |
 | Client2 |<--->| Cache |<---+
 +---------+     +-------+

当两个客户端都缓存了同一块内存的副本时,如果 Client1 修改了该内存块中的数据,那么 Client2 的缓存副本就会过期。如果不采取任何措施,Client2 将基于过期数据进行计算,从而产生数据一致性问题。

2 缓存一致性实现的条件

一致性协议定义了对单个地址位置的读取和写入行为。在多处理器系统中,如果多个处理器缓存了内存位置 X 的副本,为了实现一致性,必须满足以下条件:

  • 写传播:对任何缓存中数据的更改都必须传播到对等缓存中的其他副本;
  • 事务序列化:对单个共享内存位置的读取/写入操作必须按照相同的顺序传播。

假设有一个四处理器系统,处理器分别为 P1、P2、P3、P4,每个处理器都持有共享变量 S 的初始值为 0 的缓存副本。首先,P1 处理器修改了本地缓存中 S 的值为 10,随后,P2 处理器将本地缓存中的 S 值更改为 20。为了确保 P3 和 P4 及时更新缓存,需要将这些修改操作传播给它们。同时,传播的顺序也至关重要,因为如果 P3 先收到 P1 的写事件,后获取到 P2 的写事件,而 P4 收到的事件顺序与 P3 相反,最终 P3 和 P4 之间的值就会不一致。

3 缓存一致性协议的实现方案

缓存一致性协议的实现方案主要有两种:基于侦听的方案 (Bus watching or Snooping)基于目录的方案 (Directory-based)

  • 基于侦听的方案
    • 在带宽足够的情况下,侦听类型的协议往往性能更高,因为其事务通过广播形式传播。其缺点是随着系统规模的扩大,为了将事务广播到所有节点,逻辑总线或物理总线的规模以及其提供的带宽也必须相应地扩大。
    • 通常用于基于总线的 SMP – 对称多处理器(多核)系统。
  • 基于目录的方案
    • 基于目录的协议的缺点是延迟较大(需要 3 次 请求/转发/响应),但由于其采用点对点的通信方式而非广播方式,因此能够有效地减少带宽的使用。
    • 适用于所有系统,但通常用于 NUMA 系统和大型多核系统。

3.1 基于侦听的缓存一致性协议

基于侦听的缓存一致性协议通过一致性控制器 (snooper) 监听总线事务,当共享数据被多个缓存共享时,如果某个处理器修改了这些共享数据,则将该更改传播到持有数据副本的所有其他缓存,以确保数据的一致性。

该类协议的实现主要分为 Write-invalidateWrite-update 两类:

  • 对于 Write-invalidate 类型的协议:当有处理器改写了共享内存,其他缓存中的所有副本都会通过总线侦听失效。
    • MSI、MESI、MOSI、MOESI 和 MESIF 协议属于此类别。
  • 对于 Write-update 类型的协议:当有处理器改写了共享内存,其他缓存的所有共享副本都会通过总线侦听进行更新。
    • 此方法会将写入数据广播到总线中的所有缓存,因此产生的总线流量比 Write-invalidate 类型的协议更大,因此不常用。
    • Dragon 和 firefly 协议属于这一类。

3.2 基于目录的缓存一致性协议

基于目录的缓存一致性协议通过目录来管理缓存,该类协议核心是目录的格式,常用的有以下几种:

  • 全位向量格式;
  • 粗位向量格式;
  • 稀疏目录格式;
  • 数平衡二叉树格式;
  • 链式目录格式;
  • 有限的指针格式。

由于该类协议只在大型系统中被广泛使用,因此本文就不详细展开了,接下来我们主要介绍日常开发中接触最多的 MESI 协议。

4 在线模拟工具:VivioJS MESI

在开始正式学习之前,让我们先来了解一个 MESI 在线模拟工具:VivioJS MESI

VivioJS MESI

该工具模拟了一个 3 CPU 系统,每个 CPU 都有一级本地缓存,同时整个系统还有一级共享内存。其中:

  • 共享内存中有 a0a1a2a3 四个变量,初始值 data 均为 0;
  • 每个 CPU 每次写任意一个变量时,都会让该变量的值全局 +1,即 a0a1a2a3 四个变量都以同一个步长为 1 序列递增。

    假如任意 CPU 依次写操作 a0a2a1,那么 a0a2a1 写入后的值依次为 1、2、3。

  • 每个 CPU 预设了两个缓存行(Cache Line),并且为了演示简单,工具假设了每次写入的数据大小都等于缓存行大小。
  • 系统中一共有三根总线,分别是数据总线地址总线Cache 总线。其中:
    • 数据总线跟地址总线用于主内存与缓存、缓存与缓存之间的数据传输;
    • 缓存总线仅用于缓存之间的数据传输;
    • 某根总线上有数据通过时,会高亮展示。

在学习过程中使用该工具,可以帮助我们更好地理解 MESI 工作原理。

5 基于侦听的 MESI 协议详解

MESI 是 Modified、Exclusive、Shared、Invalid 四个单词首字母的缩写,它是一种基于总线侦听方案的 Write-invalidate 类缓存一致性协议。通过缓存失效机制,该协议显著减少了带宽占用,同时简化了主内存事务的数量,显著提升了系统性能。

5.1 MESI 有限状态机

MESI 规定了一个有限状态机,其状态在以下两类请求发生时进行转换:

  1. 处理器对缓存的请求:
    • PrRd: 处理器请求读取缓存行;
    • PrWr: 处理器请求写入缓存行。
  2. 总线对缓存的请求:
    • BusRd: 监听到该信号时,表明另一个处理器对某个缓存行发出了读取请求;
    • BusRdX: 监听到该信号时,表明另一个处理器对某个缓存行发出了写入请求,而自己没有对应的副本;
    • BusUpgr: 监听到该信号时,表明另一个处理器对某个缓存行发出了写入请求,而且自己拥有对应的副本;
    • Flush: 监听到该信号时,表明另一个处理器将某个缓存行写回了主内存;
    • FlushOpt: 监听到该信号时,表明另一个处理器将某个缓存行的最新副本发布到了总线上。

具体的状态流转过程如下:

MESI 状态流转过程

5.2 处理器操作过程中的状态流转

初始状态操作响应
InvalidPrRd* 向总线发送 BusRd 信号
* 其他处理器监听到 BusRd 信号后,检查自己是否有该数据的有效副本
* 如果其他缓存行都没有有效副本,则发送该信号的缓存行状态转换为 Exclusive,然后从主内存获得数据
* 如果其他缓存行有有效的副本,则将有效副本所在的缓存行与发送该信号的缓存行状态都设置为 Shared,同时有效副本将最新数据发送到数据总线,供主内存和发起请求的缓存行读取
PrWr* 向总线发送 BusRdX 信号
* 如果其他缓存行都没有有效副本,则数据仅写入自己本地的缓存,同时将自己的状态设置为 Modified
* 如果其他缓存行有有效的副本,则其他副本将状态设置为 Invalid,同时发送该信号的缓存行将最新数据写入主内存
ExclusivePrRd* 无总线事务生成
* 状态保持不变
* 读操作为缓存命中
PrWr* 无总线事务生成
* 状态转换为 Modified
* 向缓存行中写入修改后的值
SharedPrRd* 无总线事务生成
* 状态保持不变
* 读操作为缓存命中
PrWr* 发出总线事务 BusUpgr 信号
* 状态转换为 Exclusive
* 其他缓存看到 BusUpgr 总线信号,标记其副本为 Invalid
ModifiedPrRd* 无总线事务生成
* 状态保持不变
* 读操作为缓存命中
PrWr* 无总线事务生成
* 状态保持不变
* 写操作为缓存命中

5.3 总线操作时的状态流转

初始状态监听到的信号响应
InvalidBusRd忽略信号,状态保持不变
BusRdX/BusUpgr忽略信号,状态保持不变
ExclusiveBusRd状态变为 Shared
向总线发出 FlushOpt 信号并发送本地副本内容
BusRdX状态变为 Invalid
SharedBusRd状态依旧为 Shared
其中一个副本需要向总线发出 FlushOpt 信号并发送本地副本内容,接收者为最初发出 BusRd 的缓存行与主内存
BusRdX状态变为 Invalid
ModifiedBusRd状态变为 Shared
发出总线 FlushOpt 信号并发出块的内容,接收者为最初发出 BusRd 的缓存行与主内存
BusRdX状态变为 Invalid

参考资料: