Max Lab

Focus on backend, big data, and AI.

dev

Computer Fundamentals - Cache Fundamentals

/note-bak/dev/computer/cache/computer_cache/

Computer - Cache Coherency

CPU Memory Hierarchy

CPU运行速度非常快，而主内存相对来说很慢，因此CPU并不直接访问主内存，两者之间有多次缓存结构。

  CPU
   |
L1 Cache
   |
L2 Cache
   |
L3 Cache
   |
Main Memory

The Cache Coherency Problem

如果多个CPU共享一个Cache，那从数据正确性角度没有问题，但是这样处理效率低下，因为多个CPU要争抢一个缓存。

所以，实际的设计是每个CPU有自己单独的Cache。如下：

CPU1 - Cache 1 - Main Memory
CPU2 - Cache 2 - Main Memory
...

但是，这样会有一个问题：Cache 1和Cache 2同时修改一个变量，那么到底谁说了算呢？这就是一致性问题。

Approaches to Solving the Coherency Problem

一致性问题的本质是两个人竞争同一个资源，怎么办？

解决方案，有人总结说是3种，笔者认为是2.5种吧。

排队：排好队，先到先得。实现是各种锁，屏障等等。

投票：多个人可以同时发表意见，最后投票表决听谁的。实现是分布式系统中常见的Paxos和Raft算法。

避免：把一个资源复制多份，分给每个人，然后大家就可以自己玩自己的了。实现是Java的ThreadLocal。 （笔者认为，这个只能算半个方法，因为最后多个拷贝汇总起来还是会有竞争问题，所以ThreadLocal没有做汇总的功能）

Cache Coherency Problem Analysis

这里对缓存一致性问题作出具体分析。

举个例子：两个CPU分别执行指令，如下：

a = 0

CPU 1 -> cmd 1: a = a + 1
CPU 2 -> cmd 2: b = a

按照正常思路，一种可能的结果是：

cmd 1先执行完，然后执行cmd 2

结果
a = 1
b = 1

另外，还有一种可能的执行过程如下：

在CPU1上，先执行cmd 1
从内存读取a到Cache1上，Cache1_a = 0
然后进行计算，a = a + 1 = 1
将数据写回到Cache1上，Cache1_a = 1
（还没来得及写回内存！！！）

同时

在CPU2上，执行cmd 2
从内存读取a到Cache2上，Cache2_a = 0
然后进行计算，b = a = 0
一路将b写回到内存上

最终
a = 1
b = 0

这就是缓存一致性问题。（在上例中，缓存1和缓存2的中a的值不一致。） 也可以称为缓存可见性问题。（在上例中，缓存1和缓存2中的a互不可见。）

同样的代码，跑两次结果不一样，显然（在这里）这是不能接受的。

以上问题的解决的方案，有两种：

  • 锁总线
    • 简单粗暴，同一时间，只能有一个CPU和内存进行数据交换，也就只有一个缓存，也就不存在缓存不一致了
    • 但是这样开销也很大，把多核玩成了单核，浪费资源
  • 锁缓存
    • 把锁的粒度更细化一点，放在缓存级别。也就是缓存一致性协议 cache protocol

Cache Coherency Protocols

缓存一致性协议有很多种，可以分为两类：

  • 窥探 snooping 协议
  • 基于目录的 directory-based 协议

Snooping Protocol

snooping的本质，就和它的名字一样，Cache会不停地 snoop “窥探” 总线上的数据交换，了解其它Cache在做什么。 当一个Cache代表它所属的CPU去读写内存时，其它CPU都会得到通知，以此保持Cache同步。

MESI Protocol

Cache 由 Cache Line 组成，每个 Cache Line 是64位（根据不同架构，也可能是32位或128位）， 这个Cache Line可以理解为 Cache 的最小组成单位。

MESI协议属于一种窥探协议。它有两个重要组成部分：Cache Line的状态 和 消息通知机制。

Cache Line的状态：

  • Modified：有已经被修改的数据
  • Exclusive：有独享的数据
  • Shared：有共享的数据
  • Invalid：数据已失效

消息机制：

  • Read，CPU发起读请求
  • Read Response，其它CPU或者内存说：读请求收到
  • Invalidate，CPU发出写请求：我要独占一个Cache Line
  • Invalidate ACK，其它CPU说，写请求收到，我会把自己的Cache Line置为Invalid
  • Write back，把状态为Modified的Cache Line写回到内存

结合起来:

  • CPU要写的时候，发起写请求Invalidate，然后等待其它CPU的回应

    • （如果另外一个CPU正在独占这一块数据，那写请求失败。下面也就进行不下去了）
    • 其它CPU把自己的Cache Line置为Invalid，然后发送Invalidate ACK。
    • 该CPU收到了所有的响应之后，知道自己可以独占，于是把状态置为Exclusive。
    • 该CPU修改完了之后，把状态置为Modified。
    • 最终再发送Write back请求，把数据写回内存。

  • CPU要读的时候，发起读请求Read

    • 先看看其它CPU有没有处于Modified的状态，如果有，读修改后的值；如果没有，直接从内存中读取。
    • 把这一块的状态置为Shared。

打个比方，就好一群人围坐在一起喝酒，只有拿到酒瓶的人才能喝（写），其他人只能看着（读）。

但是，缓存一致性协议的工作效率不高，因为每次修改数据，都要等其它CPU的反馈。 于是，在此基础上又有了一系列的优化。

Store Buffer + Store Forwarding

一个优化思路是，采用异步。

原来的Flow是这样的：

CPU想要写
-> 给其它CPU发送 Invalidate 消息
-> 等待
-> 收到其它CPU都发送的 Invalidate ACK 消息之后
-> 将数据写进 Cache Line

改进后，在CPU和Cache之间加一个Store Buffer， CPU想要写，给其他CPU发送消息之后，可以不用等待，而是把数据先写到Store Buffer，然后继续做其它事情。 等收到其它CPU发过来的响应消息，再将数据从Store Buffer移到Cache Line。

同时，如果这时候，其它CPU想要访问这个数据，直接从Store Buffer中取，而不是从Cache Line取。这个技术叫Store Forwarding。

Flow变成这样：

CPU想要写
-> 给其它CPU发送 Invalidate 消息
-> （没有等待环节）直接把数据写到 Store Buffer
-> （干其他事去了）
-> 收到其它CPU都发送的 Invalidate ACK 消息之后
-> 将数据从 Store Buffer 写进 Cache Line

但是，其实这样会有问题，待会再讲。

Invalid Queue

失效队列

Store Buffer的大小是有限的，如果装满了怎么办？ 那就不能再往里面装了，还是要等其它CPU都发送的 Invalidate ACK 消息，然后清空 Store Buffer。

这里的瓶颈在于，其它CPU处理 Invalidate ACK 太慢了。怎么优化呢？还是异步，引入一个Invalid Queue。

原先的其它CPU的Flow是这样的：

CPU 接收到消息 Invalidate
-> 将 Cache Line 的状态置为 Invalid （耗时）
-> 返回 Invalidate ACK

现在的Flow是：

CPU 接收到消息 Invalidate
-> 将这条消息放到 Invalid Queue
-> 直接返回 Invalidate ACK
-> 等有空了，处理Invalid Queue的消息，将 Cache Line 的状态置为 Invalid （耗时）

OK，效率提高了，但是这样也存在问题。下面讲。

Memory Barrier

内存屏障

The Problem

上面谈到了 Store Buffer + Store Forwarding 以及 Invalid Queue，它们的本质都是采用了异步的形式，来提高运行效率。

但是，异步和一致性，本来就是不可兼得的。会带来一系列问题。简单描述如下：

以Store Buffer为例，Invalid Queue也是类似的：

CPU1要对a进行写操作，把值存在Store Buffer里面，记为CPU1_SB_a = 1。

然后，CPU2要对a进行读操作，会直接读CPU1_SB_a的值（由于Store Forwarding），这里没有问题。

但是CPU3，之前已经读取过a的初始值，还在缓存中，记为CPU3_a = 0。而CPU1给它的Invalidate消息，它还没来得及处理。
这时，CPU3又碰到一个读取a的指令，返回的值就是CPU3_a = 0。（因为缓存还未失效）

所以，CPU1的Store Buffer的值，和CPU3的缓存的值，就不一致了。

The Solution

解决的方法就是使用内存屏障。

内存屏障分为：

  • 写屏障 Store Memory Barrier (smp_wmb)
    • 告诉处理器，先把Store Buffer处理完，再执行Barrier之后的指令
  • 读屏障 Load Memory Barrier (smp_rmb)
    • 告诉处理器，先把Invalid Queue处理完，再执行Barrier之后的指令

需要注意的是，内存屏障是一个软件实现，需要程序员手动写进程序里，如下例：

void foo(void)
{
  a = 1;
  smp_mb();
  b = 1;
}

参考：

Summary

多核CPU，从硬件设计的角度上来说，存在缓存一致性问题。

为了解决这个问题，可以使用总线锁（但是代价太大），也可以使用缓存锁（缓存一致性协议）。

为了优化缓存一致性协议，还使用了Store Buffer + Store Forwarding，以及Invalid Queue技术。 同时，必须搭配使用Memory Barrier技术（需要从软件层面实现）。