缓存一致性协议的工作方式

现代计算机都是多核cpu，cpu需要和内存交互，但内存相对cpu的速度实在太慢，于是cpu和内存之间还有cache层，每个cpu都有属于自己的cache，cache由cache line组成，每个cache line 64位（根据不同架构，也可能是32位或128位），每个cache line知道自己对应什么范围的物理内存地址，当cpu需要读取某一个内存地址的值时，它会把内存地址传递给一级cache，一级cache会检查它是否有这个内存地址对应的cache line。如果没有，它会以cache line为单位从内存加载数据，是的，一次加载整个cache line，这是基于这样一个假设：内存访问倾向于本地化（localized），如果我们当前需要某个地址的数据，那么很可能我们马上要访问它的邻近地址。



这是最原始的cpu架构



窥探协议的基本思想

所有cache与内存，cache与cache（是的，cache之间也会有数据传输）之间的传输都发生在一条共享的总线上，而所有的cpu都能看到这条总线，同一个指令周期中，只有一个cache可以读写内存，所有的内存访问都要经过仲裁（arbitrate）。



窥探协议的思想是，cahce不但与内存通信时和总线打交道，而且它会不停地窥探总线上发生的数据交换，跟踪其他cache在做什么。所以当一个cache代表它所属的cpu去读写内存时，其它cpu都会得到通知，它们以此来使自己的cache保持同步。



MESI协议的工作方式

”MESI“该名称来自4个状态的首字母的缩写，协议中最重要的内容有两部分：cache line的状态以及消息通知机制。



cache line的状态有4个：

• Invalid，表明该cache line已失效，它要么已经不在cache中，要么它的内容已经过时。处于该状态下的cache line等同于它从来没被加载到cache中。

• Shared，表明该cache line是内存中某一段数据的拷贝，处于该状态下的cache line只能被cpu读取，不能写入，因为此时还没有独占。不同cpu的cache line都可以拥有这段内存数据的拷贝。

• Exclusive，和 Shared 状态一样，表明该cache line是内存中某一段数据的拷贝。区别在于，该cache line独占该内存地址，其他处理器的cache line不能同时持有它，如果其他处理器原本也持有同一cache line，那么它会马上变成“Invalid”状态。

• Modified，表明该cache line已经被修改，cache line只有处于Exclusive状态才能被修改。此外，已修改cache line如果被丢弃或标记为Invalid，那么先要把它的内容回写到内存中。



我们发现，cpu有读取数据的动作，有独占的动作，有独占后更新数据的动作，有更新数据之后回写内存的动作，根据”窥探协议“的规范，每个动作都需要通知到其他cpu，于是有以下的消息机制：

• Read，cpu发起读取数据请求，请求中包含需要读取的数据地址。

• Read Response，作为Read消息的响应，该消息可能是内存响应的，也可能是某cpu响应的(比如该地址在某cpu cache Line中为Modified状态，则该cpu必须返回该地址的最新数据)。

• Invalidate，cpu发起”我要独占一个cache line，其他cpu请失效对应的cache line“的消息，消息中包含了内存地址，所有的其它cpu需要将对应cache line置为Invalid状态。

• Invalidate ACK，收到Invalidate消息的cpu在将对应cache line置为Invalid后，返回Invalid ACK。

• Read Invalidate，相当于Read消息+Invalidate消息，即取得数据并且独占它，将收到一个Read Response和所有其它cpu的Invalidate ACK。

• Write back，写回消息，即将状态为Modified的cache line写回到内存，通常在该行将被替换时使用。现代cpu cache基本都采用”写回(Write Back)”而非”直写(Write Through)”的方式。



结合cache line状态以及消息机制，我们来看看cpu之间是如何协作的。为了简化，假设我们有个四核cpu系统，每个cpu只有一个cache line，每个cache line大小为1个字节，内存地址空间一共两个字节的数据，地址分别为0x0和0x8，有如下操作序列:



cache line时序变化图



1. 初始状态，4个cpu的cache line都为Invalid状态（黑色表示Invalid）。

2. cpu0发送Read消息，加载0x0的数据，数据从内存返回，cache line状态变为Shared。

3. cpu3发送Read消息，加载0x0的数据，数据从内存返回，cache line状态变为Shared。

4. cpu0发送Read消息，加载0x8的数据，导致cache line被替换，由于之前状态为Shared，即与内存中数据一致，可直接覆盖，而无需回写。

5. cpu2发送Read Invalidate消息，从内存返回最新数据，cpu3返回Invalidate ACK，并将状态变为Invalid，cpu2获得独占权，状态变为Exclusive。

6. cpu2修改cache line中的数据，cache line状态为Modified，同时内存中0x0的数据过期。

7. cpu1 对地址0x0的数据执行原子(atomic)递增操作，发出Read Invalidate消息，cpu2将返回Read Response(而不是内存)，包含最新数据，并返回Invalidate ACK，同时cache line状态变为Invalid。最后cpu1获得独占权，cache line状态变为Modified，数据为递增后的数据，而内存中的数据仍然为过期状态。

8. cpu1 加载0x8的数据，此时cache line将被替换，由于之前状态为Modified，因此需要先执行写回操作，此时内存中0x0的数据得以更新。



总结



这就是缓存一致性协议，一个状态机，仅此而已。因为该协议的存在，每个cpu就可以放心操作属于自己的cache，而不需要担心本地cache中的数据会不会已经被其他cpu修改了之类的烦心事。



但到目前为止，cpu并不满足，觉得在缓存一致性协议的框架下工作性能不够高，但这并不是协议的问题，协议本身逻辑很严谨，没毛病（同类协议之间的优劣那是另外一回事）。性能差在哪里？假如某数据存在于其他cpu的cache中，那自己每次需要修改数据时，都需要发送Read Invalidate消息，除了等待最新数据的返回，还需要等待其他cpu的Invalidate ACK才能继续执行其他指令，这是一种同步行为，cpu可忍不了，我们看看cpu如何优化自己？



Memory Barriers: a Hardware View for Software Hackers​www.puppetmastertrading.com

缓存一致性（Cache Coherency）入门-InfoQ​www.infoq.cn



题图：珠穆朗玛峰