为什么要有CPU Cache
CPU的处理速度和内存的访问速度差距越来越大，甚至可以达到上万倍。
当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。
缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。
为什么要有多级CPU Cache
热点数据的体积越来越大，单纯的增加一级缓存大小的性价比已经很低了。
因此，就慢慢出现了在一级缓存(L1 Cache)和内存之间又增加一层访问速度和成本都介于两者之间的二级缓存(L2 Cache)。
此外，又由于程序指令和程序数据的行为和热点分布差异很大，因此L1 Cache也被划分成
- L1i (i for instruction)
- L1d (d for data)
什么是Cache Line
Cache Line可以简单的理解为CPU Cache中的最小缓存单位。
目前主流的CPU Cache的Cache Line大小都是 64Bytes。
假设我们有一个 512Bytes 的一级缓存，那么按照 64Bytes 的缓存单位大小来算，这个一级缓存所能存放的缓存个数就是512/64 = 8个。具体参见下图：
了解Cache Line的概念对我们程序猿有什么帮助？ 我们来看下面这个C语言中常用的循环优化例子下面两段代码中，第一段代码在C语言中总是比第二段代码的执行速度要快。
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[i][j] = num;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[j][i] = num;
}
}
CPU Cache 是如何存放数据的
缓存设计的一个关键决定是确保每个主存块(chunk)能够存储在任何一个Cache Line里，或者只是其中一些Cache Line。
我们先来尝试回答一下那么这个问题：
假设我们有一块4MB的区域用于缓存，每个缓存对象的唯一标识是它所在的物理内存地址。每个缓存对象大小是64Bytes，所有可以被缓存对象的大小总和（即物理内存总大小）为4GB。那么我们该如何设计这个缓存？
最简单的思想：
把Cache设计成一个Hash数组。内存地址的Hash值作为数组的Index，缓存对象的值作为数组的Value。每次存取时，都把地址做一次Hash然后找到Cache中对应的位置操作即可。 这样的设计方式在高等语言中很常见，也显然很高效。因为Hash值的计算虽然耗时(10000个CPU Cycle左右)，但是相比程序中其他操作（上百万的CPU Cycle）来说可以忽略不计。而对于CPU Cache来说，本来其设计目标就是在几十CPU Cycle内获取到数据。如果访问效率是百万Cycle这个等级的话，还不如到Memory直接获取数据。当然，更重要的原因是在硬件上要实现Memory Address Hash的功能在成本上是非常高的。
为什么Cache不能做成Fully Associative
Fully Associative 字面意思是全关联。
在CPU Cache中的含义是：如果在一个Cache集内，任何一个内存地址的数据可以被缓存在任何一个Cache Line里，那么我们成这个cache是Fully Associative。
从定义中我们可以得出这样的结论：给到一个内存地址，要知道他是否存在于Cache中，需要遍历所有Cache Line并比较缓存内容的内存地址。而Cache的本意就是为了在尽可能少得CPU Cycle内取到数据。那么想要设计一个快速的Fully Associative的Cache几乎是不可能的。
每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。
直接映射缓存会引发冲突——当多个值竞争同一个缓存槽，它们将相互驱逐对方，导致命中率暴跌。另一方面，完全关联缓存过于复杂，并且硬件实现上昂贵。
为什么Cache不能做成Direct Mapped
和Fully Associative完全相反，使用Direct Mapped模式的Cache给定一个内存地址，就唯一确定了一条Cache Line。
设计复杂度低且速度快。那么为什么Cache不使用这种模式呢？
让我们来想象这么一种情况：一个拥有 1M L2 Cache的32位CPU，每条Cache Line的大小为 64Bytes。
那么整个L2Cache被划为了 1M/64=16384 条Cache Line。
我们为每条Cache Line从0开始编上号。同时32位CPU所能管理的内存地址范围是 2^32=4G，那么Direct Mapped模式下，内存也被划为 4G/16384=256K 的小份。也就是说每256K的内存地址共享一条Cache Line。
被映射到同一 Cache Line 上的两个内存块是不能同时换入缓存的。
但是，这种模式下每条Cache Line的使用率如果要做到接近100%，就需要操作系统对于内存的分配和访问在地址上也是近乎平均的。而与我们的意愿相反，为了减少内存碎片和实现便捷，操作系统更多的是连续集中的使用内存。这样会出现的情况就是0-1000号这样的低编号Cache Line由于内存经常被分配并使用，而16000号以上的Cache Line由于内存鲜有进程访问，几乎一直处于空闲状态。这种情况下，本来就宝贵的1M二级CPU缓存，使用率也许50%都无法达到。
什么是N-Way Set Associative N路组相联
为了避免以上两种设计模式的缺陷，N-Way Set Associative缓存就出现了。
他的原理是把一个缓存按照N个Cache Line作为一组（set），缓存按组划为等分。
这样一个64位系统的内存地址在 4MB 二级缓存中就划成了三个部分（见下图）：
另 N=16，即16路。
- 低位
6bit表示在Cache Line中的偏移量（Cache Line Offset） - 中间
12bit表示Cache组号（Set Index） - 高位
46bit就是内存地址的唯一id。
这样的设计相较前两种设计有以下两点好处：
- 给定一个内存地址可以唯一对应一个set，对于set中只需遍历16个元素就可以确定对象是否在缓存中（Full Associative中比较次数随内存大小线性增加）
- 每
2^18(256K)*16(way)=4M的连续热点数据才会导致一个set内的conflict（Direct Mapped中512K的连续热点数据就会出现conflict）
为什么N-Way Set Associative的Set段是从低位而不是高位开始的：
由于内存的访问通常是大片连续的，或者是因为在同一程序中而导致地址接近的（即这些内存地址的高位都是一样的）。所以如果把内存地址的高位作为set index的话，那么短时间的大量内存访问都会因为set index相同而落在同一个set index中，从而导致cache conflicts使得L2, L3 Cache的命中率低下，影响程序的整体执行效率。
了解N-Way Set的概念后，我们不难得出以下结论：2^(6Bits <Cache Line Offset> + 12Bits <Set Index>) = 2^18 = 256K。即在连续的内存地址中每 256K 都会出现一个处于同一个Cache Set中的缓存对象。
因此Cache Line对应的物理地址凡是以262,144字节(4096*64)的倍数区分的，将竞争同一个Cache Line。
Cache淘汰策略
常见的淘汰策略主要有LRU和Random两种。通常意义下LRU对于Cache的命中率会比Random更好，所以CPU Cache的淘汰策略选择的是LRU。当然也有些实验显示在Cache Size较大的时候Random策略会有更高的命中率。
Cache写操作
为了和下级存储（如内存）保持数据一致性，就必须把数据更新适时传播下去。这种传播通过回写来完成。一般有两种回写策略：
写回（Write back）：
写回是指，仅当一个缓存块需要被替换回内存时，才将其内容写入内存。如果缓存命中，则总是不用更新内存。为了减少内存写操作，缓存块通常还设有一个脏位（dirty bit），用以标识该块在被载入之后是否发生过更新。如果一个缓存块在被置换回内存之前从未被写入过，则可以免去回写操作。
写回的优点是节省了大量的写操作。这主要是因为，对一个数据块内不同单元的更新仅需一次写操作即可完成。这种内存带宽上的节省进一步降低了能耗，因此颇适用于嵌入式系统。写通（Write through）：
写通是指，每当缓存接收到写数据指令，都直接将数据写回到内存。如果此数据地址也在缓存中，则必须同时更新缓存。由于这种设计会引发造成大量写内存操作，有必要设置一个缓冲来减少硬件冲突。这个缓冲称作写缓冲器（Write buffer），通常不超过4个缓存块大小。不过，出于同样的目的，写缓冲器也可以用于写回型缓存。
写通较写回易于实现，并且能更简单地维持数据一致性。
