今天探究的主题是cache。我们围绕几个问题展开。为什么需要cache？如何判断一个数据在cache中是否命中？cache的种类有哪些，区别是什么？

对于没有接触过底层技术的朋友来说，或许从未听o H 8 - k $ u 4 o说过cache。毕竟cache的存在对程序员来说是透明的。在接触cache之前，先为G y p你准备段code分析。

int arr;

for (i = 0; i < 10; i++)

        for (j = 0; j < 128; j++);

                arr = 1;

如果你曾经学习过C/C++语言，这段code自然不会陌生。如此简单的将arr数组所有元素置1。你有没有想过这段code还有下面的一种写法。

int arr;

for (i = 0; i < 128; i++)

        for (j = 0; j < 10; j++);

                arr = 1;

功能完全一样，但是我们一直在重y v V % w 7 l复着第一种写法（或许很多的书中也是建议这么编码），你是否想过这其中的缘由？文章的主角是cache，所以你一定猜到了答案。那么cache是如何影响这2段code的呢？

为什么需要cache memory

在思考cache是什么之前我们首先6 # - Q 6 { y {先来思考第一个问题：我们的程序是如何运行起来的？

我们应该知道程序是运E & % : G n 4行在 RAM之中，RAM 就是我们常说的Dp v 0 o yDR（例如 DDR3、DDR4等）。我们称J S : F o之为main memory（主存）当我们需要运行一个进程的时候，首先会从Flash设备（例如，eMMC、UFS等）中将可执行程序load到main memory中，然后开始执行。在CPU内部存在一堆的通用寄存器（register）。如果CPU需要将一个变量（假设地址是A）加1，一般分为以下3个步骤：

• Cl 2 J x SPU 从主存中读取地址A的数据到内部通用寄存器 x0（AX * 7 gRM64架构的通用寄存器之一）。
• 通用寄存器 x0 加1。
• CPU 将通用寄存器 x0 的值写入主存。

我们将这个过程可以表示如下：

其实现实中，CPU通用寄存器的速度和主存之间存在着太大的差异。两者之间的速度大致如下关系：

CPU register的速度一般小于1ns，主存的速度一般是65ns左右。速度差异近百倍。因此，上面举例的3个步骤中，步骤1和步骤3实际上速度很慢。当CPU试图从主存中load/store 操作` 5 a u 2 0 )时，由于主存的速度限制，CPU不得不等待这漫7 O G 1 = N长的65ns时间。如果我们可以提升主存的速度，那么系统将会获得很大的性能提升。

如今的DDR存储设Q e 2 f a H H备，动不动就是几个GB，S t u c ( Q @容量很大。如j U q / # X Z果我们采用更n w 2 ~ N c 7 k快材料制作更快速度的 z . t , !主存，并且拥有几乎差不多的容量。其成本将会大幅度上升。

我们试图提升主存的速度和容量，又期望其成本很低，这就有点难为人S 5 k | #了。因此，我们有一种折中的方法，那就是制作一块速度极快但是容量极小的存储设备。那么其成本也不会太高。这块存储设备我们称之: m ; n ?为cache memory。

在硬件上，我们将cache放置在CPU和主存之间，作: l * 1为主存数据的缓存。当CPU试图从主存中load/store数据的时候， CPU会首先从cache中查找对应地址的数, w y u n @ d H据是否缓存在cache中。如果w X A . / G a &其数据缓存在K ! d = w K ecache中，直接从cache中拿到数据并返回给CPU。当存在ca7 T ?che的时候} C s v { B ，以上程序如何运行的例子的流程将会变成如下：

CPU和主存之间直接数据传输的方式转变成CPU和cache之间直接数据传输。cache负责和主存之间数据传输。

多级cache memory

cahe的速度在一定程度上同样影响着系统的性能。一般情况cache的速度可以达到1ns，几乎可以和Co L 6 V 0 ! : + IPU寄存器速度媲美。但是，这就满足人们对性能的追求了吗？并没有。当cache中没有缓# s O {存我们想要的数据的时候，依然需要漫长的等待从主存中load数据。

为了进一步提升性能，引入多级cache。前面提到的cache，称之为L1 cache（第一级cache）。我们在L13 p 0 4 r 2 u cache 后面连2 V ( 9 I接L2 cache，o C ~ } w f , |在L2 caa m Q k B S tche 和主存之间连接L3O e j I w ? o K cache。x 5 0 2 S S ^ ! )等级越高，速度越慢，容量越大。但是速度相比较主存而言，依然很快。不同等级cache速度之间关系如下：

经过3级cache的缓冲，各级cache和主存之间的速度最萌差也逐级减小8 ~ G 5 _ C q。在一个真实的系统上，各级cache之间硬E ! n [ P % o 6件上是如何关联的呢？我们看下Cortex-A53架构上各级cache之间的硬件抽象框图如下：

在Cortex-A53架构上，L1 cache分为单独的instruction cache（ICache）和data cache（w & g b 6 EDCache）。L1 cache是CU f n W K 7 X 0 {PU私有的，每个CPU都? & r有一个l a q r 内的所有CPU共e n X w f y ~ `享一个L2 cache，L2 cache不区分指令和数据，都可以缓存。所有cluster之间共享L3 cacJ x % &hU z { ! r x . 3e。L3 cache通过总线和主存相连。

多级cachn d l i V ;e之间的配合工作

首先引入两个名词概念，命中和缺失j V / O。CPU要访问的数D C m据在cache中有缓存，称为“b R 7 - * p ) _命中” (hit)，反之则称为“缺失” (miss)。多级cache之间是如何配合工作的呢？我们假设现在考虑的系统只有两级cache。

当CPU试图从某地址load数据时，首先从L1 cache中查询是否命中，如果命中则把数据返回给CPU。如果L1 cache缺失，则继续从L2 cache中查找。当L2 cache命中时，数据会返回给L1 cs / ] $ `ache以及CPU。如果L2 cache也缺失，很不幸，我们需要从主存中load数据，将数据返回给L2 cache、L1 cache及CPU。

这种多级cache的工作方式称之为inclusive cache。某一地址的数据可能存在多级缓! B U s G ~ ,存中。与inclusive cache对应的a = u是exclusive cache，这种cache保证某一地址的数据缓存只会存在于多级cache其中一级B ! . ] -。也就是说，任意地址的数据不可能同时在L1和L2 cache中缓存。

直接映射缓存（Direct mapped cache）

我们继续引入一些cache相关的名词。cache的大小称之为cahe size，# : &代表cache可以缓存最大数据的大小。我们将cache平均分成相等的很多块，每一r N x ~ l l 0 V %个块大小称之d P D $ D 5 C j为cache line，其大小是cache line size。

例如一个64 Bytes大小的cache。如果我们将64 Bytes平均分成64块，那么cacheV n N i liD r W 共8个元素，每个元素大小是8字h o e N r @节。就像下图这样：

现在我们考虑一个问题，CPU从0x0654地址读取一个字节，cache控制器是如何判断数据是否J L J . V在cache中命中呢？cache大小相对于g U 3 `主存来说，可谓是小巫见大巫。所以cache肯定是只能缓存主存中极小一部分数据。我们如何根据地址在有限大小的ca_ ~ P Q Z , m O 8che中查找} # ^ n v _ 3 i l数据呢？现在` I w E硬件采取的做法是对地址进行散列（可以理解成地址取模操作）。我们接下来看看是如何做到的？

我们一共有8行cache linea n 2 F w G )，cache line大小是8 Bytes。所以我们可以利用地址低3 bits（如上图地址蓝色部分）用来寻址8 bytes中某一字节，我们称这部分bit组合为offset。同理，8行cache lix H 8 Nne，为了覆盖所有行。我们需要3 bits（如上图地址黄色部分）查找某一行e ; r，这部分地址部分称之为c 3 x | a ] w *index。

现在我们知道，如果两个不同的地址，其地址的bit3-bit5y z h A _如果完全一样的话，那么这两个地址经过硬件散列之后都会找到同一个cache line。所以，当我们找到S I Y b 4cache line之后，只代表我们访问的地址对应的数据可能存在这个cache line中，但是也有可能是其他地址对应的数据。所& ^ P g D u以，我们又引入tag array o % M l h区域，tag array和data arr~ f q - c #ay一一对应。

每一8 h T个cache line都对应唯一一个tag，tag中保存的是整个地址位宽G s F { ) z g v Q去除i# v p } : 5 `ndex和offset使用的b. : B Lit剩余部分1 , 9 z 2 ,（如上图地址绿色部分）) r ; Q n i T ( V。tag、index和; h q X ^ 7offset三者组合就可以唯一确定一个地址了。

因此，当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，这说明cache命中。如果不相等g p f ) ! c { e，说明当前cache lineX w j ^ 2 M存储的是其他地址的数据，这就是cache缺失。

在上述图中，我们看到tag的值是0x19，7 9 A R和地址中的tag部分相等，因此在本次R ? T I访问会命中。由于tag的引入，因此解答了我们之前的一个疑问“为什么硬件cac@ : Z F ; O l V Vhe ll I a } z ~ / Uine不做成一个字节？”。这样会导致x w | P F % j硬件成本的上升，因为原本8个字节对应一个tag，现在N : ( a 9 t C 2 d需要8个tag，占用了很多内存。

我们可以从图B 0 B H k中看到tag旁边还有一个V { 3 G | i E ( Wvalid bit，这个bit用来表+ k 6 ( O D l i示cache line中数据是否有效（例如：1代表有效；0代表无效）。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。cache控制器可以根据valid bit确认当前cache line数据是否有效。所以，上述比较tag确认cache line是否r & d命中之前还会检查valid bit是否有效。只有在有效的情况下，比较tag才有意义。如果无效，直接判定cache缺失。

上面的例子中，cache sA x Andex和tag分别使用+ & ^ 0 a ? U6 bits、3 bits和39 bits。如下图所示：

直接映射缓存的优缺点

直接映射缓z k [ / R {存在硬H $ u F * ^ k件设计上会更加简单，因N ? N 3 ; :此成本上也会较低。根据直接映射缓存的工作方式，我们可以画出主存地址0x00-0x88地址对应的cache分布图：

我们可以看到，地址0x00-0x3f地址处对应的数据可以覆盖整个cache。0x40-0x7f地址的数据也同样2 0 y 7 ,是覆盖整个cache。我们现在思考一个问题，如果一个程序W Y B 9 n ,试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？首先我们应该明白0x00、0x40、0x80地址中index部分是一样的。因此，这3个地址对应的cache line是同一个。

所以，= S n当我们访问0x00地址时，cache会缺失，然后数据会从主存中加载到cache中第0行cache line。当我们访问0x40地址时，依然索引到cache中第0行cache line，由于此时cache line中存储的是地址0x00地址对应的数据，所以此时依然会cache缺失。然后从主存中加载0x40地址数据到第一行cache line中。

同理，继续访问0x80地址，依然会cache缺失。这就相当于每次访问数据都要从主存中读取，所以e Q y Ccache的存在并没有对性能有什么提升。访问0x40地址时，就会把0x00地址缓存的数据替换。这: . i b种现象叫做cac W K h ^ ) + _che颠簸（cache thrashing）。

针对这个问题，我们引入多路组相连缓存。我们首先研究) 0 = R s j O u下最简单的两路组相连缓存的工作原理。

两路组相连缓存

我们依然假设64 Bytes cache size，caL Q u Y U q 4 b 9 7 * S也可以称作set index（组索引）。先根据index找到set，然后将组内的所有cache line对应的tag取出来和地址中的tag部分对比，如果其中一个相等就意味着命中。

因此，两路组相连缓存较直接映射缓存最大的差异就是：第一个地址对应的数据可以对应2个cache line，而直接映射缓存一个地址只对应一个cache line。那么这究竟有什么好处呢？

两路组相连缓存优缺点

两路组相连缓存的硬件成本相对于直接映射缓存更高。因为其每次比较tag的时候需要比较多个cache line对应的tag（某些硬件可能还会做并行b * H W + = w比较，增加比较速度，这就增加了r 9 = H ; y L #硬件设计复杂度）。

为什么我们还需A A ~ 2 ^要两路组相连缓存呢？因为其可以有助于降低caY h Tche颠: p L簸可能性。那么是如何降低的呢？B a r 1 N R j根据两路组相连缓存1 5 | z % # d的工作方式，我们可以画出主存地N { E q 9 R N址0x00-0x4f地址对应的d Y H 1cache分J # E | 6布图：

我们依然考虑直接映射缓存一节Z & :的问题“如果一个程序试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？”。现在0x00地址的数据n : a W s I可以被加载到way 1，0x40可以被加载到way 0。这W c F y样是不是就在一定程度上避免了直接映射缓存的尴尬境地呢？在两路组相8 $ n d - @ ` k g连缓存的情况下，0x00和0x40地址的数据都缓存在cache中。试想一下，如果我们是4路组相连缓存，后面继续访问0x80，也可能被被缓存。

因此，当cache size一定的情况下d J &，组相连缓存对性能的提升最差情况下也和直接映射缓存一样，在大部分情况下组相连缓存效果比直接映射缓存好。同时，其降低了cach1 # G V 6 * Ve颠簸的频率。从某种程度上来说，直接映射缓存是组相连缓存的一U X C |种特殊情况，每个组只有一个cache line而已。因此，直接映射缓存也可以称作单路组相连缓存。

全n ) & S F L o e Y相J I L连缓存（Full associative cache）

既然组相连缓存那么好，如果所有的cache line都在一= 6 * u k ` w ^ 7个组内。岂不是性能更好。是的，这种缓存就是全相连缓O I ^ S u xugh）

当CPU执行store指令并在cache命中时，我们更新cache中的数据并且更新主存中的数据。cache和主存的7 w ( 7 ! W U y u终保持一致。

写回（write back）

当CPU执行store指令并在cache命中时，我们只更新cache中的数据。并且每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit（翻翻前面的图片，cache line旁边有一个D就是dirty bit）。我们会将dirty bit置位。主存中的数据只会在cache line被替换或者显示clean操作时更新。因此，主存中的数据可能是未修改的数据，而修改的数据躺在cache line中。cache和主存的数据可能不一致。

同时思考个问题，为什么cache lineH d ; c y F K大小是cache控制器和主存之间数据传输的最小单位呢？这也是因为每个cache line只有一个dirty bit。这一个dirty bit代表着整个cache line是否被修改的状态。

实例

假设我们有一个64 Byt) a j T h g % zes大小直接映射缓存，g ~ C ; _ , d Ncache linT ] { } w B 8 je大小是8 Bytes，采用写分配和写回机制。当m $ , J 7 & % CPU从地址0x2a读取一个字节，cache中的数据将会如何变化呢？假设当前cache状态如下图所示：

根据index找到对应的cD p x D z B =ache line，对应的tag部分valid biK $ V | F |t是合法的，但是tag的值不相等，因此发生缺U ，我们发现当前cache line的dirtf q Y ? * J N C ^y bit置位。因此，cache line里面的数据不能被简单的丢弃，由于采用写回机制，所以我们需要将cache中的数据0x11223344写到地址0x0128地址（这个地址根据tax . k 5 m Kg中的值及所处的cache line行计算得到）。这个过程如下图所示：

当写回操作完成，我们将主存中0x28地址开始的8个字节加载到该cache line中，并清除dirty bit。然后根据offset找到0x52返回给CPU。

扩展阅? 4 L : u E F读

• 《smcdef：图说Cache -{ - K 6 q Cache对代码的影响w e $ @ _ f ^ z》https://zhuanlan.zhihu.com/p/1023261n a ( U u 6 J A 684
• 《smcdef：图说Cac) j i k ?he - Cache组织方式》https://zhuanlan.zhihu.co^ N J v jm/~ 8 F : bp/107096130

作者丨smcde} 0 Mf

来源丨http://www.wowotech.net/memory_@ 6 ) Kmanagement/458.html

dbaplus社群欢迎广大技术人员投稿，投稿邮箱：editor@dbaplus.cn

随着人工智能的兴起，运维也迎来了新的契机，想破解运维转型困局，让Gdevops全球x . R ;敏捷运维峰会北京站给你新思路：

• 《浙江移动AIOps实G K p F $ b @践》浙江移动云计算中心NOC及AIOps负责人 潘宇虹
• 《数据智能时代：构建能力开放的运营商大数据DataOps体系》中国联通大9 y g j i L数据基础平台负责人/D K , M a ?资深架构师 尹正军
• 《云时代下，传统行业的运维转型，如何破局？》新炬网络董事/副总经理 程永新
• 《银行日志监控系统优化手记》中国银行DevOps负责人 付大o ] = V亮和中国银行 高级软件工程师 李晓宁
• 《x A P民生银行智能运维平台实践之路》民生银行智能运维平台负责人/应用运维专家 张舒伟
• 《建设敏捷型消费金融中台及云原l I h .生下的DevOps实践》中邮消费金融总经理助理 李远鑫

让我们在新技术的冲击下站稳脚跟，攀登运维高峰！那么2020年9月11日，我们在北京不见不散。