关于CPU上的高速缓存

CPU高速缓存基本知识

最高速的缓存是CPU的寄存器，它们和CPU的材料相同，最靠近CPU或最接近CPU，访问它们没有时延(<1ns)。但容量很小。
CPU要操作数据，必然要从内存中将数据取入寄存器，但寄存器和内存的速率相差极大。如果直接从内存取数据到寄存器，CPU将经常处于空转等待状态。于是在CPU中加入了中间的缓存层：高速缓存。事实上，很早期的计算机层次里，确实只有三层存储系统：CPU寄存器、内存、外存(如磁盘)，是没有高速缓存层的。而且，L1、L2、L3也并非是一次性引入的，而是随着发展，CPU和内存的性能差距变得越来越大而逐层引入的，最先引入的是L1、再是L2、再是L3。
寄存器之下，是CPU的高速缓存。分为L1缓存、L2缓存、L3缓存，每层速度按数量级递减、容量也越来越大(关于下图中每级缓存的大小和N-way的含义，后面会解释)。L1缓存速度接近寄存器速度，大约1ns时延。
**每核心都有一个自己的L1缓存。L1缓存分两种：L1指令缓存(L1-icache, L1i)和L1数据缓存(L1-dcache, L1d)**。L1指令缓存用来存放已解码指令，L1i通常是只读的，L1数据缓存用来放访问非常频繁的数据。
L2缓存用来存放近期使用过的内存数据。更严格地说，存放的是很可能将来会被CPU使用的数据。
**多数多核CPU的各核都各自拥有一个L2缓存，但也有多核共享L2缓存的设计。无论如何，L1是各核私有的(但对某核内的多线程是共享的)**。
CPU读取数据时，要从内存读取到L3，再读取到L2再读取到L1，同样写到内存时也会经过这些层次。
之所以要在L3上还要提供L2和L1，原因之一是协调速率，原因之二是L3缓存由各核心共享。多核共享会导致对L3的访问出现竞争现象，为了避免进程1放进L3的数据可能会被进程2覆盖，需要额外的仲裁管理，而如果没有各核心的本地L1、L2缓存，所有数据都要从L3访问，仲裁管理任务将非常繁忙。
Core1上运行的进程1的数据存放在L1、L2和寄存器，如果进程切换后被调度到Core2，则进程1缓存在Core1上L1、L2的数据将失效，即缓存未命中，将不得不再次从L3读取到Core2的L1、L2，这会导致效率下降，特别是那些非常繁忙的机器。
为了避免在进程切换时因多核导致的高速缓存未命中问题，可以对进程绑定CPU核心，实现CPU的亲缘性(Processor Affinity，也称为缓存亲缘性cache affinity)。CPU亲缘性表示某进程或某线程将总被调度到同一个核心或范围允许的核心上。
高速缓存的空间极其有限(特别是L1、L2)，它们也更显珍贵。但一个事实是，数据有局部性现象：即某次访问的数据，很可能下次会再次被访问或它周围的数据会被紧跟着访问。这称为缓存局部性。
缓存局部性(cache locality)：
- 时间局部性(temporal locality)：某次从内存中读取的数据，可能会在不远的将来被重用。例如在一个循环中指令和量是不断被重用的。
- 空间局部性(spatial locality)：某次从内存中读取数据后，该数据周围的数据很可能会在不远的将来被使用。如，取数组索引1的数据后，很可能马上会用到索引2上的数据，再比如正常指令的执行，执行完某指令后，很可能会上执行它的一条指令。这都是空间局部性。其实，时间局部性也是空间局部性的一种，只不过它的预期位置和当前位是相同的，是数据用，是将同一份数据拷贝几份放入缓存。
- 因为缓存局部性的存在，CPU会根据预测，加载更多数据到高速缓存：针对时间局部性，CPU努力地将可能重用的据拷几份放入高速缓存；针对空间局部性，CPU努力地将周围数据也放入高速缓存。如此一来，就不用在需要数据临时去内存加载数据，毕竟访问内存的速度比访问高速缓存的速度要慢。
- 自己写的程序也应当尽量符合局部性，有良好局部性的程序比没有良好局部性的程序性能要高得多。
CPU想要读写数据时，都会先计算目标数据的内存地址，然后将目标数据的内存地址随读写请求发送给总线，最终通过内存总线到达内存，内存将根据请求操作的类型来读数据或写数据。换句话说，CPU读写数据完全是根据内存地址来的，例如读arr[0]数据时先计算数组地址，然后取出第一个元素，而arr[5]=3则表示将3写入数组第六个元素所在地址处。

CPU读数据的缓存判断和多路关联

第一次从内存中读取某数据时，由于数据不在高速缓存中，所以需要从内存中读取数据，速度较慢，同时还会将读取后的数据将逐层缓存在各高速缓存层中。之后再读取该数据，将命中高速缓存中的数据，直接从高速缓存中取数据，速度非常快。再加上空间局部性带来的数据预加载，使得访问随后的周边数据也非常快，例如访问数组a的a[0]时，因为未命中缓存，所以需从内存加载并缓存在各层，但该元素随后的几位可能也一起缓存(至于具体能缓存多少，由高速缓存中的每个缓存块大小决定)，所以访问a[1]也会直接命中缓存。

因为高速缓存有三个层次L1、L2和L3，加上多核共享L3，超线程共享L1、L2，每一层的数据可能都会被覆盖，所以每一层的数据可能是不一样的。当所需数据不在L1中时会找L2，L2中不存在时会找L3，每一次上层缓存的未命中，都会带来未命中惩罚：从下层检索数据并加载到上层缓存中。而越往下层，速度越慢，代价越大。比如超线程曾经有一种简单的切换逻辑：当遇到代价较大的阻塞时，比如L2层的缓存丢失，就会进行超线程切换。换句话说，仅仅是L2层的几个时钟周期的延迟，也认为是一个较大的代价，也可能会导致CPU转让执行权。当然，现在的超线程可能未采用这种超线程切换逻辑。

读数据的过程并不简单，需要判断想要读取的数据是否在高速缓存中，因为是按内存地址读写数据的，所以这个问题转变成判断目标地址处的数据是否在缓存中。针对这个问题，最简单的一种解决方案是将内存中每个数据字按照地址取模，余数相同的放在高速缓存区的同一个位置。比如某高速缓存区可以放置8个数据字，地址00011、11011、01011、10011等后三位是011的，都放在高速缓存的011位置，即index=3的位置处，地址01010、10010、11010后三位都是010，都放在index=2的位置处。所以，如果CPU想要读取00111地址的数据时，直接看高速缓存的111位置是否有数据即可，如果这里没数据，需要从内存中读取。

因为多个内存地址的数据可以存放在高速缓存区的同一个索引位置处，所以读取数据时还要判断高速缓存中的数据是否是目标数据。比如00111已经存放在高速缓存区的111位置处，下次要读取10111数据时，显然高速缓存区111这个位置处的数据不是想要的数据，所以高速缓存还需要一个标记位来标记目标地址。

因为index标记本身就来自于内存地址，所以标记目标地址时可结合这个index。比如10111地址处的数据存放在111位置，然后使用10作为地址标记。那么下次读取00111目标地址的数据时，111确定高速缓存的索引，00确定高速缓存中的该数据是否是目标地址的数据。

所以，高速缓存中的index和地址标记位结合，可以唯一确定每一个内存地址。另一方面，也是显然的，高速缓存中并非只包含从内存中读取的数据，还包含一些索引位、判断标记位等。

按照如上简单的解决方案，高速缓存中的每个数据行缓存的结构如下：索引位+标记位+数据块。

例如：

注意上图中的数据块部分并非只有单个字节的数据，显然也是不可能每次只缓存一个字节的。事实上，每次能缓存多少数据，是由高速缓存的行大小决定的，比如行大小为4个字，如果是64位地址，那么每个字8字节，于是每个缓存行能存放32字节的数据，加上额外的标记位，每行中的数据块部分能缓存小于32字节的数据。因为缓存块中有多个字节的数据，在检索高速缓存中的数据时需要通过块偏移来确定所需数据在数据块中的哪个位置。

如果读取数据时，发现高速缓存中对应索引位置处已经存放数据了，但是却不是目标数据，将会从内存中读取目标数据并驱逐覆盖高速缓存中已有的数据行。

这种简单的高速缓存机制并不如意，因为高速缓存中的数据太容易被驱逐了。所以用的更多的缓存结构是多路关联(多组联合)的方式，即有多个缓存组，每个组内有多个缓存行，其中的缓存行就是上面的简单缓存结构里的缓存行，每个组内有n行就表示n-way关联。如下图，是2-way关联：

现在，目标地址00011、11011、01011、10011的数据全都放在同一个组中，因为组中有多行可以存放数据，所以任何一个空闲行都可以存放属于这个组的数据。换言之，检索数据是否在此缓存组时，需要逐行扫描这个缓存组，并将扫描的行和目标数据的标记位进行对比。如果确定是目标行，则还需根据块偏移来取出缓存在该块中的目标数据。

因为高速缓存进行了分组，且组中可有多行存放同一个索引位置的多个地址数据，相比之前的简单缓存结构，数据被驱逐的概率要大大降低。

虽然多路关联降低了未命中而驱逐数据的几率，但是却增加了每次检索数据的时间，每个组中行数越多(即n-way的n越大)，检索的时间越久。

其实简单的缓存结构是多路关联方式的一种特例：多个缓存组，每个缓存组中只有一行，这种方式称为直接映射高速缓存。多路关联还有另外一种特例：只有一个缓存组，所有的缓存行全放在这一个组内，这种方式称为全关联高速缓存。

下图是cpu-z工具中显示的CPU的缓存结构，此CPU为4核8线程的i7-7700k：

从图中可推知一些信息:

因为一级、二级都有4 x #，这个4表示核数，所以该CPU的每核拥有自己的L1i、L1d和L2，它们共享L3
由于组中每行大小为64字节，而每行中包含有效位、标记位和数据位，所以每行能存储的数据小于64字节
L1数据缓存4核共4x32=128KB，每核L1数据缓存大小是32KB，因为L1数据缓存是8-way，即每组8个缓存行，由于每行大小64字节，所以每个缓存组能存放512字节，所以共有64个缓存组
L1指令缓存同L1数据缓存结构完全一致
L2缓存4核共4 x 256=1024KB，每核L2缓存大小是256KB，由于是4-way，即每组4个缓存行，由于每行大小64字节，所以每个缓存组能存放256字节，所以共有1024个缓存组
L3缓存是8MB，4核共享，因为是16-way，即每组16个缓存行，由于每行大小64字节，所以每个缓存组能存放1KB数据，所以共有8192个缓存组

下图是我画的i7-7700K CPU中高速缓存的大概结构：

CPU写数据时的缓存一致性

CPU写数据到内存时，过程要比读数据复杂一点。

如果CPU只有单核，且没有超线程，因为没有并行，也没有竞争，那么此单核CPU的数据可以直接从寄存器写入L1，再写入L2、L3以及内存。

例如，从内存中读取变量a=5，然后将其修改为a=3，那么a=3会写入L1，写入L2、L3以及内存。

甚至，数据可以先写入L1，以后有需要的时候再写入L2、L3以及内存。延迟写操作是有好处的，比如CPU重复修改同一个变量a，先修改为3，再修改为4，再修改为8，如果每次修改都同步到内存，效率会比较低，而多次写操作只写入L1，并且在需要写入底层缓存时才写入(比如L1空间不足了)，可以避免无谓的多次底层的缓存写操作，提升效率。

但如果有多个数据写者，问题就陡然变得复杂。

比如多核处理器(先不考虑超线程)，每核处理器拥有独立的L1、L2缓存，但共享L3缓存。由于L1和L2是每核本地的缓存，只有自己可以写，所以数据在L1和L2上是没有问题的，但是L3是共享的，每核CPU都可以写，任何一方对L3上某数据的修改都可能会导致和其它方获取到的该数据值不一致。

例如，Core1的某进程读取了变量a=5到寄存器中，几乎同时(因为多核是可以并行运行的)，Core2也读取了a=5到自己的寄存器，随后，Core1中运行的进程将a设置为3，如果此时Core3读取变量a的值，得到的将是几？Core2中仍然保留a=5合理吗？以及内存中的a应该为几？如果Core2将a设置为4，Core1和Core3获取到的值将是几？内存中的值应该是几？

当有多方数据的写者时，必须要保证数据的一致性以及写的顺序性：

一致性：任何一个时刻，所有Core看到的数据必须是一致的
写的顺序性：先执行的写操作，必须先被看到，后执行的写，必须后被看到

所以，针对上图的问题，当Core1修改a=3后，Core2和Core3所看到的值必须都是3，内存中的值也应该改为3。如果Core2修改a=4，那么Core1和Core3看到的a必须是4，内存中的a也必须为4。此外，各核心必须是先看到a=3，再看到a=4。

以上便是最终目标，即**缓存一致性(Cache coherence)**的目标，至于如何保证多核CPU在高速缓存中的数据一致性，通常有两种实现方式：

cache snooping(bus snooping)：即高速缓存监控或总线监控的方式。对于此方式，所有核心的CPU都运行一个缓存控制器(cache controller或snooper)用来监视总线，如果某Core想要修改共享缓存(L3)上的某数据，它会先进行广播，其它Core的snooper就会监视到这个事务，它们会判断自己本地的高速缓存中是否也有所修改的目标数据的副本，如果没有则不管，如果有，则要进行处理，处理的方式通常有两种，称为缓存一致性协议(只在snoop方式中存在)：
- write-invalidate：当要修改共享缓存(L3)上某数据时，会让其它所有带有该数据副本的缓存失效，所以称为”写无效协议”。实际上的过程是这样的，当某Core监视到自己本地缓存有将要修改的数据副本时，会让自己本地缓存的该数据失效，如此一来，所有Core上带有副本数据的缓存都将被置为无效，也因此它们想要再次访问该数据时，只能从共享缓存(L3)重新加载该数据，而共享缓存中的数据是已经被修改的新数据。此外，写方具有独占性(exclusive)，当开始写时(成功在总线上发送广播)，其他方均不可读不可写，如果双方同时写，则成功在总线上发送广播的写方抢得写权，失败方的缓存被置为无效
- write-update：当修改共享缓存(L3)上某数据时，会将修改的数据拷贝到所有带有该数据副本的缓存中进行覆盖，所以称为”写更新协议”。实际上的过程是这样的，当某Core监视到自己本地缓存有将要修改的数据副本时，会将监视到的数据拷贝到自己的本地缓存中进行覆盖，如此一来，所有Core上的同一份数据都是相同的
- 对于bus snoop来说，一般只会使用write invalidate，因为write-update一致性协议要求所有具有副本数据的Core拷贝数据，这会产生大量的总线流量
- write-invalidate或write-update其实还更为严格，Core1写数据A到L3，Core2读数据A，但如果Core1写操作还未到达共享缓存L3，Core2就开始读自己本地缓存L1或L2中的值，Core2将读到不一致的数据，这是可能的，因为写L3需要好几个接近数十个时钟周期，而Core2此时还未监控到写事务的发生。这是需要避免的问题。解决方案是，写操作只有在被其它方确认后才认为此次写成功。对于write-invalidate，Core1写数据A时，其它Core将本地缓存的数据A置为无效，但Core1此时还不会将数据更新到共享缓存L3，仅仅只是导致其它缓存副本无效，当某Core2要读取数据A时，由于它们的数据已无效，只能从共享缓存加载，这时Core1才认为数据写成功，并将数据写入共享缓存，同时Core2读取该数据。对于write-update，则是在所有需要拷贝的Core拷贝完成后，写者才认为此次写成功
Directory-based cache conherence：基于目录实现的缓存一致性方式。这会在共享缓存中维护一个目录表格，其中记录所有待修改或修改过的行，任何读、写操作，都需要先查询该目录中是否有对应的记录
cache snooping的方式适用于核数少的CPU，因为核数多时，任何一核要修改数据都会进行广播，这会产生大量总线流量，也就是说这种方式不利于核数扩展。而Directory-based方式适合扩展到多核，但是它的开销稍大一些。

写缓存策略

提前说明

在开始介绍写缓存策略前，先做个说明。

数据可以存在于4个层次：L1、L2、L3和内存，中间的每两个相邻层次都是自己的存放、读、写缓存策略。所以这四个层次间，每两两相邻的层次都有自己的缓存控制，即3个缓存控制层。

比如CPU操作L1时，它只会考虑L1和L2，操作L2时只会考虑L3，操作L3时只会考虑内存，不会跨层考虑或整体考虑。比如L1缓存未命中时将从L2读不会直接从L3读，数据写入L1时会考虑是否同时写入L2，但不会考虑是否同时写入L3，数据写入L2时才会考虑是否写入L3。再比如L1到L2之间使用的写缓存策略可以是write-through，而L2到L3之间使用的写缓存策略可以是write-back。

因为有多个层次，为了方便解释，下面将**假设只有L3层和更低一层的内存存储层(即站在L3的角度上，考虑L3和内存之间的缓存控制行为)**，因为L3是多核共享的缓存层，但其实L1到L2和L2到L3的逻辑是一样的，L1和L2毕竟也是多个超线程共享的缓存层。如果某个缓存层次不是共享缓存，则没必要考虑缓存写策略，比如非超线程的CPU下，L1和L2都是每核心的私有本地缓存，不会出现多方写。

此外，写缓存策略适用于所有多方写、带共享缓存和后端存储的场景，比如redis作为共享缓存，后端存储是数据库的场景。只不过对于CPU的各层高速缓存和内存之间来说，为了追求极致的速度，可能会做一些策略上的优化。

写缓存策略的类型

参考资料：

对于多方写共享缓存的操作(不仅是这里的L3高速缓存)，都需要考虑写缓存策略：数据如何写入共享的缓存层(如L3)以及如何写入共享缓存层的后端存储(如内存，在L3的后端)。

有4种缓存策略，分为写命中和写未命中两种情况：

写命中时的策略：write-through(直写)、write-back(写回或回写)
写未命中时的策略：write-allocate(写时分配)、non-write-allocate(非写分配)

因为涉及到写操作时是否命中缓存，所以有必要了解一个事实：共享缓存层的空间是有限的，不同地址的数据可能会存放在共享缓存的同一个位置(什么样的数据位置会相同参考CPU如何读数据)。

例如，在加载低层数据B到共享缓存时可能会覆盖共享缓存层的A，写向共享缓存的数据C也可能会覆盖数据A，无论何种情况，在数据A面临被驱逐时，都需要处理数据A使其保存到后端存储，也正因为数据A被驱逐，导致下次对数据A的读、写操作未命中。

写命中时：write through策略

最简单的缓存写策略是write through(直写)，它是写命中时的策略，它表示将准备写入的数据写入共享缓存后且写入了后端存储(内存)后才认为写入成功。它是一种同步模式，整个过程会占用内存总线的流量。效率相对差，但数据安全性高。

想象一下，按照write through策略，如果Core1将数据A写入L3，其它Core如何对待数据A的读写操作？因为缓存一致性的存在，Core1写数据A时可能会让其它核心的数据A缓存失效(假设采用的是bus snooping缓存一致性协议)，使得其它Core操作数据A时都会未命中，并总会从L3获取最新数据状态。

因为write through策略效率较低，CPU对此做了一些优化，在L3和内存之间添加一层写缓冲空间(write buffer)，这段缓冲空间抽自L3。即：

1	CPU(L1,L2) --> CPU(L3) --> write buffer --> Memory

此时，所有write through的写操作只需要写入到write buffer便认为写成功，然后CPU就可以执行其它任务，而write buffer实际上也在L3中，它还可以累积多次写操作，所以效率提高很多。直到write buffer空间已满或达到其它条件时，CPU才会转来将write buffer中的数据写入内存。

写命中时：write back策略

另一种写命中时的策略是write back，常称为写回、回写策略。该策略表示将准备写入的数据写入共享缓冲(L3)后便认为本次写成功，CPU可以继续执行其它任务。写回策略效率相对较高，但数据安全性低。

因为写入共享缓存中的数据还尚未写入后端存储，所以共享缓存中需要使用一个标记位来标记该数据是否修改过，即该缓存数据是否是脏数据(dirty data)。

对于write back来说，同一个写入者可能会在随后的操作中连续多次修改共享缓存中的同一份数据(比如修改a为3，接着又修改a为4，接着又修改a为5)，延迟写操作可以避免不必要的写入后端存储(内存)的操作。所以为了尽量推迟写入后端存储，写入共享缓存(L3)的数据不会立即写入后端存储(内存)，而是在该数据面临被驱逐时才写入后端存储。

在write back策略下，如果读数据B未命中但正好需要驱逐共享缓存中数据A时，或者写未命中数据B也正好需要驱逐缓存中数据A时，将需要先将缓存数据A保存到后端存储，然后将后端存储的数据B读取到共享缓存或者写数据B到共享缓存。关于写未命中时，还需在下面的介绍。

写未命中：write allocate和no write allocate

no write allocate是写未命中时的一种缓存写策略，该策略表示在写未命中时直接写入后端存储(内存)，而不会写入共享缓存。该策略也称为绕写(write around)，应该不难理解。

write allocate策略表示写未命中时需要在共享缓存中腾出一个空间(即一个缓存行)供数据写入，所以叫做写分配，即为写操作分配空间。

但问题并非这么简单。由于高速缓存中的一个缓存行可包含多字节数据(因为以数据块为单元进行读写，假设为8字节)，如果本次写未命中时要写入的数据仅仅只是一个字节，那么这个缓存行中剩下的7字节都是空，于是出现了严重的问题：这个缓存行在以后写入内存时因会直接覆盖整个数据块，将会导致了7个字节的数据丢失。

所以在写未命中时，应该先将后端存储数据读取到共享缓存，然后在此基础上去写数据。由于数据已经从后端存储读取到共享缓存，所以一开始的写未命中操作会转变成写命中。

其实，在写未命中的策略之下，还有两个分支策略：

fetch on write(写时获取)：即上面所介绍的，先从后端存储将缓存行对应的数据读取到共享缓存行，然后再修改共享缓存中的数据(此时再改相当于写命中)
no fetch on write(写时不获取)：不从后端取对应数据到共享缓存，而是在共享缓存中使用一些额外的标记位来跟踪所写入的数据位于缓存块的哪部分，以后写入后端存储时可根据这些标记写入对应地址，而不会覆盖额外数据导致数据丢失

一般会采用fetch on write策略。

写缓存策略图示

写命中时的两种策略(write through和write back)和写未命中时的两种策略(write allocate和no write allocate)可以互相结合：

write through + write allocate
write through + no write allocate
write back + write allocate
write back + no write allocate

但基本上都采用write through和no write allocate结合的方式，write back和write allocate结合的方式。即写回加写分配，直写加非写分配。而且越往低层次方向，因读写效率越差，越建议采用写回加写分配的写策略。比如自己设计缓存程序时，因在内存和磁盘间进行读写，更建议采用写回策略。

下面两图来自于wiki cache。