Cache Consistency in CPU and Distributed System

CPU 和内存之间，我们有两种东西：

这一节的内容会比较长，我们会介绍：

  • 如何在 CPU 中维护上面的一致性：我们将介绍 snooping-based （国内翻译类似基于监听的协议）和 directory（基于目录的协议）。
  • 如何在分布式系统中维护一致性：我们将介绍这与计算机系统中有什么不同，然后介绍 Lease 机制。

Preview

我们在之前内容聊到过 cacheline/cacheblock 的基本概念：

https://zhuanlan.zhihu.com/p/271020814

D0BB5BAB-3486-4EC9-BF8E-D470DAF87BE3

我们还有一些 design 上的区别：

  1. Write-through：写入的时候需要更新cache 和 memory

  2. Write-back:

    1. 写入的时候更新 cache block
    2. 添加一个 dirty flag
    3. OS 在 IO 之前 flush cache

write-through 也有 write allocate 等策略。write allocate 是指：如果目标内存不在 cache 中，是否要把它捞上来。

Snooping cache-coherence

Idea: 所有与 coherence 相关的活动，会被广播给各个 cache-controller. Cache controller 舰艇这些操作，来维持 memory coherence。

那么我们可以想到一个最朴素的实现：

在 write-through + cache line 为粒度的场景下

任何一次写，在完成的时候，都会 Invalid 掉所有的 cache。所以别的 P 下一次读都会 cache miss

那么，我们可以维护一个如下图的状态机器，cache 有两种逻辑状态：

7350CB1E-748C-42CC-9803-D26D06523C98

这里对 bus 有需求：

  • 所有的 write txn 被所有的 cache controller 以同种顺序观察到。

同时可以有下面的假设：

DA90A8BF-2444-4257-B217-74A0025DFC6A

当然，以上是 write-through 的场景。相对 write-back 来说，write-through 只是优化了读，同时，这样的缺点是：每次写都要写内存，需要很高的 bandwidth. write-back 大大减少了这种场景，但是，在 write-back 的情况下，实现 cache coherence 会复杂得多。

现在，我们需要区分 dirty/clean, exclusive 和 shared. 这个需要靠 cacheline 的 valid 标记来区分。

  • Exclusive: 被写入之后，变成独占的，只有写入者的是有效的
  • Owner: 别的 cache 需要 load 的时候，不能从 memory 读，因为 memory 的数据是 stale 的。需要从写入的唯一一份 cache 中读。

那么，我们有下面的 ideas：

  • exclusive 状态的 cache 可以不通知别的进程，就可以完成修改
  • P 只能写 exclusive 的 cache, 所以它写之前需要广播
  • 当 P 收到别的 P 的写请求时，他必须 Invalid 自己的 cache

MSI

Key tasks:

  • 确保在写入时是 Exclusive 的
  • 能够读到最近写入的 cacheline, 即使不在内存中

同时，有三个 cache line 状态：

  • M: Modified
  • I: Invalid
  • S: Shared

有两种来自 local P 的操作：

  • PrRd: 处理器读
  • PrWr: 处理器写

三种来自 remote cache 的操作：

  • BusRd：当某个处理器的高速缓存的读操作出现未命中，它会向总线发送一个BusRd请求，并预期能够收到该缓存块的数据。
  • BusRdX：当某个处理器的高速缓存的写操作出现未命中，它会向总线发送一个BusRdX请求，预期能够收到该缓存块的数据，并且使其他处理器中对应相同地址的缓存块无效。
  • Flush：该请求表明一个缓存块正在被写回内存。

4487FEFE-0B95-49B4-B54A-FA49AB0D8836

MSI 对于 coherence 的满足性：

  • 写是 total order 的，如果状态不是 M 本处理器的写会 Invalid 所有的 cache；如果本身是 M, 没有被读占有，那么本身写按照 order 进行。任何一个读需要把 M 变成 S。

现代化的系统使用的MSI协议的变种以减少保持缓存一致性所需要的通信量。MESI协议增加了一个Exclusive（独占）状态，以减少对于只存在于一个高速缓存的块的写操作造成的通信。MOSI协议增加了一个Owned（持有）状态，以减少对于被其他缓存读取过的高速缓存的块的写回操作造成的通信。MOESI协议同时做了这两件事情。

B914D377-13F5-4E3B-BE58-089149C98CA6

Multi-level Cache

现在的处理器都是有多级缓存的，这暗示要引入额外的复杂度：包含关系。

因为 L1 某种意义上是 L2 的子集，所以即使 L1 不修改 L2，协议上仍然要在 L2 上作修改。

2C8CC59F-687A-4AA7-8FF9-5EA96DBD152E

Directory-Based cache-coherence

在 SMP 中，我们有如上的视图。但是，我们可能会为了降低 latency, 增大内存访问的带宽而使用 NUMA 架构：

FA197163-9E91-427B-9D4B-4F99632A2157

Snoop 协议肯定还能用，但是要把修改通过 interconnect 告诉别的 P 和 cache controller…

一种可选的方案是，使用 directory 来存放 cacheline 对应的状态。而 cacheline 也会从 directory 中寻找需要的信息。

0C173BDB-774B-4CDB-BBC5-224246586921

directory 协议维护了一个 directory, 来表示每一个 Line 的状态。请求不需要过每一个 Processor, 而是通过 memory 所对应的 directory, 来完成一致性的维护。

没有 interconnect 的系统

Lease: Basics

我们上述内容中看到，为了维护 write serialization 以及更大的 cache coherence, 需要依赖一点：

  • interconnect 是可靠的
  • 它能够帮我们 total order 的广播写

在分布式系统中，我们很难依赖第一点假设，实际上，异步系统的共识甚至是没有下限的，详见 FLP。对于第二点，实现全序广播是相当昂贵的，我们可能熟悉一些基于复制状态机的协议。

89 年的 Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency 提出了 Lease 机制，这是我们在今天的分布式系统里面非常常见的协议。当然，这个原 paper 只介绍了 write-through 的场景。我们试图介绍基本之后，之后会讲讲各种地方的 Lease 使用和问题。

  • “A lease is a contract that gives its holder specified rights over property for a limited period of time.”
  • “ A lease grants to its holder control over writes to the covered datum during the term of the lease, such that the server must obtain the approval of the leaseholder before the datum may be written.”

25A8DE4A-BD8F-46B3-BA18-34A15C4D21D8

  • 写入：client 需要向一个逻辑上的单点（我们在 Redis 里面会看到这个）发送 Lease Request, 拿到对应的 lease 之后，才能在 lease 期间写资源
  • 另外一个写入需要写时，server 会尝试 invalid 之前 grant 的 lease，然后再 grant lease
  • 如果 invalid 联系不上（比如发生网络分区），这里会等待到 grant 的 lease 时间结束。

这里隐含了时间这个要求。实际上分布式系统的时间只是一个偏序概念。这里只能假定大家 system clock 的运行偏差在一定范围内。