跳至主要內容

Cache一致性

Cache一致性

Linc：这一章我个人有些疑问和总结，详见 ../../../../其他抽象/竞争算法.md

Cache与内存交换

读写过程

当我们定义了一个数据结构或者分配了一段数据缓冲区之后，在内存中就有一个地址和其相对应，然后程序就可以对它进行读写。

  • 对于读，首先是从内存加载到Cache，最后送到处理器内部的寄存器；

  • 对于写，则是从寄存器送到Cache，最后通过内部总线写回到内存。

两个问题

而这两个过程其实引出了两个问题：

  1. CacheLine不对齐时可能存在问题。

    假如读写的某个数据结构或者数据缓冲区的起始地址不是Cache Line对齐的。

    一方面，带来了额外的损耗。即使读写的数据区域的大小小于Cache Line，那么也需要占用两个Cache entry；

    另一方面，可能有同步问题。假设第一个Cache Line前半部属于另外一个数据结构并且另外一个处理器核正在处理它，那么当两个核都修改了该Cache Line从而写回各自的一级Cache，准备送到内存时，如何同步数据？毕竟每个核都只修改了该Cache Line的一部分。

  2. CacheLine对齐了，也依然存在其他问题。

    如可能存在竞争冲突。有多个核同时对该段内存进行读写，当同时对内存进行写回操作时，如何解决冲突？

接下来，我们先回答第一个问题，然后再回答第二个问题。

(1) 尽量Cache Line对齐，避免一个数据被分到两个CacheLine中

对于第一个问题，其实有多种方法来解决。

其中一个简单的方法，就是定义该数据结构或者数据缓冲区时就申明对齐，DPDK对很多结构体定义的时候就是如此操作的。见下例：

struct rte_ring_debug_stats {
    uint64_t enq_success_bulk; 
    uint64_t enq_success_objs;
    uint64_t enq_quota_bulk;  
    uint64_t enq_quota_objs;  
    uint64_t enq_fail_bulk;   
    uint64_t enq_fail_objs;
    uint64_t deq_success_bulk;
    uint64_t deq_success_objs;
    uint64_t deq_fail_bulk;
    uint64_t deq_fail_objs; 
} __rte_cache_aligned;

// 其中 `__rte_cache_aligned` 的定义如下所示：
#define RTE_CACHE_LINE_SIZE 64 
#define __rte_cache_aligned
	__attribute__((__aligned__(RTE_CACHE_LINE_SIZE)))

其实现在编译器很多时候也比较智能，会在编译的时候尽量做到Cache Line对齐。

另一个解决方式，是用解决第二个问题的方法去解决它，从本质来讲，第一个问题和第二个问题都是因为多个核同时操作一个Cache Line进行写操作造成的。

(2) 避免Cache Line竞争，避免一个CacheLine被两核同时读写，即Cache一致性问题

Note

什么是Cache一致性问题？

上文提到的第二个问题，即多个处理器对某个内存块同时读写，会引起冲突的问题，这也被称为Cache一致性问题。

我来画图理解一下：

如图。Cache一致性说的是CPU_Core_1的一级Cache的数据和CPU_Core_2的一级Cache所对应的同一数据。
后面CPU的两个核将Cache写回内存时，无论直写还是回写策略，a的值都是一个可能为12也可能为24的状态

Note

Cache一致性问题的出现原因与前提

  • 根本原因：多个处理器独占的Cache

  • 直接原因：有多个，关于一致性问题的阐述，我们附加了很多限制条件，如果当中有一个或者多个条件不成立时可能就不会引发一致性的问题了。比如：

    1. 多核。假设只是单核处理器，不会出现问题

    2. 独占Cache。如果Cache是所有处理器共享的不会出现问题

      原因：那么当一个处理器对内存进行修改并且缓存在Cache中时，其他处理器都能看到这个变化，因而也不会产生一致性的问题（即这个问题发生才一二级Cache，三级Cache是共享的则不会发生）。在每个指令周期内，只有一个处理器核心能够通过这个Cache做内存读写操作

    3. Cache写策略。前面说了写策略有两种，无论回写还是直写都会有问题。

      原因：回写显然。而直写的原因考虑之前的一个例子：线程A把结果写回到内存中，但是线程B只会从独占的Cache中读取这个变量（因为没人通知它内存的数据产生了变化）

因而，Cache一致性问题的根源是因为存在多个处理器独占的Cache，而不是多个处理器。如果多个处理器共享Cache，也就是说只有一级Cache，所有处理器都共享它，在每个指令周期内，只有一个处理器核心能够通过这个Cache做内存读写操作，那么就不会存在Cache一致性问题。

一致性协议

解决Cache一致性问题的机制有几种：

低性能错误方案

不独占Cache

DPDK方法

避免多个数据备份、避免多个核访问同一内存地址

多个核同时需要一些数据结构，为每个核都单独定义一份

多个核访问同一个网卡的接收队列/发送队列，为每个核都准备一个单独的接收队列/发送队列

基于目录的协议（Directory-based protocol）

全局统一管理

总线窥探协议（Bus snooping protocol）

利用总线进行的分布式的广播和被通知

Snarfing协议

在此不作讨论

(1) 低性能错误方案：不独占Cache

  • 操作：只要所有的处理器共享Cache，那么就不会有任何问题
  • 缺点：
    • 首先，既然是共享的Cache，势必容量不能小，那么就是说访问速度相比之前提到的一级、二级Cache，速度肯定几倍或者十倍以上；
    • 其次，太慢了。每个处理器每个时钟周期内只有一个处理器才能访问Cache，那么处理器把时间都花在排队上了，这样效率太低了。

还是得用其他一致性协议

(2) DPDK方法：避免多个数据备份、避免多个核访问同一内存地址

（详见后面的章节）

(3) 基于目录协议：全局统一管理

  • 操作：需要缓存在Cache的内存块被统一存储在一个目录表中。目录表统一管理所有的数据，协调一致性问题。该目录表类似于一个仲裁者
    • 当处理器需要把一个数据从内存中加载到自己独占的Cache中时，需要向目录表提出申请；
    • 当一个内存块被某个处理器改变之后，目录表负责改变其状态，更新其他处理器的Cache中的备份，或者使其他处理器的Cache的备份无效。

(4) 总线窥探协议：利用总线进行的分布式的广播和被通知

总线窥探协议是在1983年被首先提出来

  • 操作：这个协议提出了一个窥探（snooping）的动作。即对于被处理器独占的Cache中的缓存的内容，该处理器负责监听总线
    • 如果该内容被本处理器改变，则需要通过总线广播；
    • 反之，如果该内容状态被其他处理器改变，本处理器的Cache从总线收到了通知，则需要相应改变本地备份的状态。

比较、总结

共同点：

这两种协议中，每个 Cache Block 都必须有自己的一个状态字段。而维护Cache一致性问题的关键在于维护每个Cache Block的状态域。Cache控制器通常使用一个状态机来维护这些状态域。

区别：

基于目录的协议总线窥探协议
操作目录表负责更新/使无效其他处理器Cache总线可以广播/被通知其他处理器的Cache操作
本质区别全局统一管理不同Cache的状态类似于分布式的系统
每个处理器能够监听其他处理器对内存的访问
每个处理器负责管理自己的Cache的状态，通过共享的总线同步Cache状态
缺点延迟性较大
优点/选用在拥有很多个处理器的系统中，它有更好的可扩展性
（总线或许更适用多核而非多处理器）		适用于具有广播能力的总线结构，适合小规模的多核系统

MESI协议 (一种总线窥探协议)

接下来，我们将主要介绍总线窥探协议。

最经典的总线窥探协议Write-Once由C.V.Ravishankar和James R.Goodman于1983年提出，继而被x86、ARM和Power等架构广泛采用，衍生出著名的MESI协议，或者称为Illinois Protocol。

命名解释：

  • MESI Protocol：这是 Cache Line 四种状态的首字母的缩写。Modified Exclusive Shared Invalid
  • Illinois Protocol：之所以有这个名字，是因为该协议是由伊利诺伊州立大学研发出来的。

四种状态

Cache中缓存的每个 Cache Line 都必须是这四种状态中的一种。详见［Ref2-2］。

  • 修改态（Modified）

    • 如果该Cache Line在多个Cache中都有备份，那么多个备份中只有一个备份能处于这种状态，并且“dirty”标志位被置上。

      拥有修改态Cache Line的Cache需要在某个合适的时候把该Cache Line写回到内存中。但是在写回之前，任何处理器对该Cache Line在内存中相对应的内存块都不能进行读操作。

      Cache Line被写回到内存中之后，其状态就由修改态变为共享态。

  • 独占态（Exclusive）

    • 和修改状态一样，如果该Cache Line在多个Cache中都有备份，那么多个备份中只有一个备份能处于这种状态，但是“dirty”标志位没有置上，因为它是和主内存内容保持一致的一份拷贝。

      如果产生一个读请求，它就可以在任何时候变成共享态。

      相应地，如果产生了一个写请求，它就可以在任何时候变成修改态。

  • 共享态（Shared）

    • 意味着该Cache Line可能在多个Cache中都有备份，并且是相同的状态，它是和内存内容保持一致的一份拷贝。

      而且可以在任何时候都变成其他三种状态。

  • 失效态（Invalid）

    • 该Cache Line要么已经不在Cache中，要么它的内容已经过时。一旦某个Cache Line被标记为失效，那它就被当作从来没被加载到Cache中。

状态矩阵

对于某个内存块，当其在两个（或多个）Cache中都保留了一个备份时，只有部分状态是允许的。

如表2-3所示，横轴和竖轴分别表示了两个Cache中某个Cache Line的状态，两个Cache Line都映射到相同的内存块。即：

  • 如果一个Cache Line设置成M态或者E态，那么另外一个Cache Line只能设置成I态；
  • 如果一个Cache Line设置成S态，那么另外一个Cache Line可以设置成S态或者I态；
  • 如果一个Cache Line设置成I态，那么另外一个Cache Line可以设置成任何状态。

表2-3　MESI中两个Cache备份的状态矩阵

img

状态迁移表

那么，究竟怎样的操作才会引起Cache Line的状态迁移，从而保持Cache的一致性呢？以下所示表2-4是根据不同读写操作触发的状态迁移表。

表2-4　MESI状态迁移表

img

DPDK如何保证Cache一致性

从上面的介绍我们知道，Cache一致性这个问题的最根本原因是处理器内部不止一个核，当两个或多个核访问内存中同一个Cache行的内容时，就会因为多个Cache同时缓存了该内容引起同步的问题。

DPDK与生俱来就是为了网络平台的高性能和高吞吐，并且总是需要部署在多核的环境下。因此，DPDK必须提出好的解决方案，避免由于不必要的Cache一致性开销而造成额外的性能损失。

其实，DPDK的解决方案很简单，首先就是避免多个核访问同一个内存地址或者数据结构。这样，每个核尽量都避免与其他核共享数据，从而减少因为错误的数据共享（cache line false sharing）导致的Cache一致性的开销。

以下是两个DPDK为了避免Cache一致性的更具体的例子。

  1. 多个核同时需要一些数据结构，为每个核都单独定义一份
  2. 多个核访问同一个网卡的接收队列/发送队列，为每个核都准备一个单独的接收队列/发送队列

避免Cache一致性的例子1 (数据结构定义)

例子1： 数据结构定义。

DPDK的应用程序很多情况下都需要多个核同时来处理事务，因而，对于某些数据结构，我们给每个核都单独定义一份，这样每个核都只访问属于自己核的备份。

具体案例

如下例所示：

struct lcore_conf {
    uint16_t n_rx_queue;
    struct lcore_rx_queue rx_queue_list[MAX_RX_QUEUE_PER_LCORE];
    uint16_t tx_queue_id[RTE_MAX_ETHPORTS];
    struct mbuf_table tx_mbufs[RTE_MAX_ETHPORTS];
    lookup_struct_t * ipv4_lookup_struct;
    lookup_struct_t * ipv6_lookup_struct;
} __rte_cache_aligned;  // 该结构体 Cache 行对齐，不会出现该数据结构横跨两个Cache行的问题

// RTE_MAX_LCORE 为一个系统中最大核的数量
// DPDK对每个核都进行编号，核n只需要访问 lcore[n]，避免了多个核访问同一个结构体
struct lcore_conf lcore[RTE_MAX_LCORE] __rte_cache_aligned;

避免Cache一致性的例子2 (网络端口访问)

例子2： 对网络端口的访问。

在网络平台中，少不了访问网络设备，比如网卡。

多核情况下，有可能多个核访问同一个网卡的接收队列/发送队列，也就是在内存中的一段内存结构。这样，也会引起Cache一致性的问题。那么DPDK是如何解决这个问题的呢？

需要指出的是，网卡设备一般都具有多队列的能力，也就是说，一个网卡有多个接收队列和多个访问队列，其他章节会很详细讲到，本节不再赘述。

DPDK中，如果有多个核可能需要同时访问同一个网卡，那么DPDK就会为每个核都准备一个单独的接收队列/发送队列。这样，就避免了竞争，也避免了Cache一致性问题。

具体案例

图2-9是四个核可能同时访问两个网络端口的图示。其中，网卡1和网卡2都有两个接收队列和四个发送队列；核0到核3每个都有自己的一个接收队列和一个发送队列。

核0从网卡1的接收队列0接收数据，可以发送到网卡1的发送队列0或者网卡2的发送队列0；
同理，核3从网卡2的接收队列1接收数据，可以发送到网卡1的发送队列3或者网卡2的发送队列3。

图2-9　多核多队列收发示意图

img

链接到当前文件 1
竞争冲突算法