CPU Cache原理与示例
基础知识现在的 CPU 多核技术，都会有几级缓存，老的 CPU 会有两级内存（L1 和 L2），新的CPU会有三级内存（L1，L2，L3 ），如下图所示：
其中：
L1 缓存分成两种，一种是指令缓存，一种是数据缓存。L2 缓存和 L3 缓存不分指令和数据。
L1 和 L2 缓存在每一个 CPU 核中，L3 则是所有 CPU 核心共享的内存。
L1、L2、L3 的越离CPU近就越小，速度也越快，越离 CPU 远，速度也越慢。
再往后面就是内存，内存的后面就是硬盘。看一些速度：
L1 的存取速度：4 个CPU时钟周期
L2 的存取速度：11 个CPU时钟周期
L3 的存取速度：39 个CPU时钟周期
RAM内存的存取速度 ：107 个CPU时钟周期
L1 的速度是 RAM 的 27 倍，但是 L1/L2 的大小基本上也就是 KB 级别的，L3 会是 MB 级别的。例如：Intel Core i7-8700K ，一个 6 核的 CPU，每核上的 L1 是 64KB（数据和指令各 32KB），L2 是 256K，L3 有 2MB（苹果电脑是 Intel Core i9-8950HK，和Core i7-8700K 的Cache大小一样）。
数据就从内存向上，先到 L3，再到 L2，再到 L1，最后到寄存器进行 CPU 计算。为什么会设计成三层？这里有下面几个方面的考虑：
一个方面是物理速度，如果要更大的容量就需要更多的晶体管，除了芯片的体积会变大，更重要的是大量的晶体管会导致速度下降，因为访问速度和要访问的晶体管所在的位置成反比，当信号路径变长时，通信速度会变慢。这是物理问题。
另外一个问题是，多核技术中，数据的状态需要在多个CPU中进行同步，cache 和RAM 的速度差距太大，多级不同尺寸的缓存有利于提高整体的性能。
这个世界永远是平衡的，一面变得有多光鲜，另一面也会变得有多黑暗。建立这么多级的缓存，一定就会引入其它的问题，这里有两个比较重要的问题，
一个是比较简单的缓存的命中率的问题。
另一个是比较复杂的缓存更新的一致性问题。
尤其是第二个问题，在多核技术下，这就很像分布式的系统了，要对多个地方进行更新。
缓存的命中在说明这两个问题之前。需要了解一个术语 Cache Line。缓存就是把后面的数据加载到离自己近的地方，对于 CPU 来说，不会一个字节一个字节的加载的，非常没有效率，都是要一块一块的加载的，对于这样的一块一块的数据单位，术语叫 Cache Line。
一般来说，一个主流的 CPU 的 Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），64 Bytes也就是 16 个 32 位的整型，这就是 CPU 从内存中捞数据的最小数据单位。
比如：Cache Line是最小单位（64Bytes），先把 Cache 分布多个 Cache Line，比如：L1 有 32KB，32KB/64B = 512 个 Cache Line。
一方面，缓存需要把内存里的数据放进来，英文叫 CPU Associativity。Cache 的数据放置的策略决定了内存中的数据块会拷贝到 CPU Cache 中的哪个位置上，因为 Cache 的大小远远小于内存，需要有一种地址关联的算法，能够让内存中的数据可以被映射到 Cache 中来。这个有点像内存地址从逻辑地址向物理地址映射的方法，但不完全一样。
有如下的一些方法。
一种方法是，任何一个内存地址的数据可以被缓存在任何一个 Cache Line 里，这种方法是最灵活的，但是，如果要知道一个内存是否存在于 Cache 中，就需要进行 O(n) 复杂度的 Cache 遍历，这是很没有效率的。
另一种方法，为了降低缓存搜索算法，需要使用像Hash Table这样的数据结构，最简单的hash table就是做求模运算，比如： L1 Cache 有 512 个 Cache Line，公式：（内存地址 mod 512）* 64 就可以直接找到所在的Cache地址的偏移了。但是，这样的方式需要程序对内存地址的访问要非常平均，不然冲突就会非常严重。这成了一种非常理想的情况了。
为了避免上述的两种方案的问题，就要容忍一定的hash冲突，出现了 N-Way 关联。把连续的N 个 Cache Line 绑成一组，先把找到相关的组，再在这个组内找到相关的 Cache Line。这叫 Set Associativity。如下图所示。