最近整理学习笔记时重读到存储设备形成层次结构这一节突然发现这个知识点比想象中重要得多——它不只是教科书上那张金字塔图而是贯穿硬件设计、操作系统调度和日常代码优化的一条主线。这篇笔记我尽量用自己的话把逻辑讲清楚为什么存储设备必须分成好几层每一层具体是什么、速度容量差多少以及怎样用局部性原理去理解整个系统。适合正在学计算机组成原理、操作系统或者写代码时总想知道程序为什么这么慢的读者。说实话当年学这节我也就是背下了寄存器快、内存快、磁盘慢的结论直到后来调一个数据处理程序的时候才发现层次结构的知识直接决定了我怎么改代码能提速十倍。所以这篇不打算只抄书我会结合自己踩过的坑、算过的数尽量写成一份能直接拿走用的笔记。1. 为什么存储设备要分等级而不是全部用最快的1.1 一台机器里最快的存储贵到离谱先把最朴素的问题摆出来既然寄存器最快为什么我们不把整个电脑都做成寄存器答案是价格和物理密度都不允许。寄存器本质上是用高速触发器电路做出来的它在CPU内部跟运算单元紧贴在一起访问延迟是纳秒级。但你看看一块CPU里寄存器总共才多少——通常几十到几百个字节撑死也就一KB级别。反过来硬盘的容量能做到几十TB单价确实便宜但机械盘的寻道时间是以毫秒计的。毫秒和纳秒之间差了六个数量级你不可能让CPU等一个来回要几毫秒的数据。这里就出现了计算机系统里最核心的矛盾快的存储贵且容量小慢的存储便宜但容量大。层次结构就是调和这个矛盾的产物。1.2 快慢之间差了六个数量级我习惯把这个差距用一张数量级表来记比纯文字直观很多存储层次典型访问延迟典型容量每GB成本大致量级寄存器0.3 ~ 1 ns几十到几百字节极高无法用GB算L1缓存1 ~ 2 ns32 ~ 64 KB/核极高L2缓存3 ~ 8 ns256 KB ~ 1 MB/核很高L3缓存10 ~ 20 ns8 ~ 64 MB共享高主存RAM50 ~ 100 ns8 ~ 64 GB中等固态盘SSD5 ~ 50 μs256 GB ~ 4 TB低机械硬盘HDD5 ~ 15 ms1 ~ 20 TB很低磁带/归档存储秒级及以上PB级极低从寄存器到机械盘延迟大概差了七到八个数量级容量差了上百万倍。如果只能选一种存储要么快得装不下一个程序要么大得慢到没法用。层次结构的设计目标就一句话用少数极贵的快速存储搭配大量便宜的慢速存储让程序访问的时候大部分数据都能从快的里面拿到。1.3 层次结构要解决的三个问题把目标拆开层次结构其实要回答三个问题第一数据放在哪一层由谁决定第二数据什么时候从慢层搬到快层第三快层满了之后把谁踢出去。这三个问题在不同层次有不同的答案。在寄存器这一层放哪些变量是编译器在编译期决定的在缓存这一层数据搬移和淘汰完全由硬件自动完成程序员无感知在主存和磁盘之间则由操作系统负责比如虚拟内存、文件页缓存。理解了这个分工之后再回看整张图你会发现层次结构不是一个静态的仓库列表而是一套动态的数据调度机制。上层的容量小所以它是下层的缓存下层的容量大所以它是上层的后备仓库。每一层对上层而言都像是一个更大更慢的影子存储。2. 逐层拆解从寄存器到磁带2.1 金字塔顶端的寄存器与缓存寄存器是离CPU运算单元最近的存储它本身就在CPU的核心电路里。一个时钟周期内就能完成读写所以很多指令的源操作数和目的操作数都要求放到寄存器里。编译器在优化代码时做的寄存器分配就是尽可能把最热门的变量放到寄存器里避免频繁访问主存。寄存器下面是L1、L2、L3这三级缓存。为什么缓存也要分三级因为单级缓存做不大做大了延迟就又上去了。L1要跟CPU同频工作只能做得又小又专属一个核放个几十KB已经是极限L2稍微大一点延迟也相应高一些L3再大一圈通常被多个核共享。这三者严格说都是SRAM做的断电丢数据但读写不需要刷新周期所以能跟着CPU跑得飞快。这里有个特别容易被新手忽略的点缓存并不是主存的备份它是主存中一小部分数据的副本。CPU要读一个地址先看它在不在缓存里在就命中不在就去主存取取回来同时写入缓存。缓存是硬件自动管理的你写代码时根本感觉不到但它对性能的影响却大到令人吃惊——一个缓存命中不到2ns一次缓存缺失去主存可能是80ns差了四十倍。2.2 主存承接一切的工作台主存DRAM就是大家平时说的内存条。DRAM的每一位数据靠电容上的电荷来表示电容会漏电所以需要周期性地刷新这也是它比SRAM慢的原因之一。但DRAM每个比特的成本比SRAM低很多所以可以做到几十GB成为所有正在运行的程序共同的工作台。所有进程的代码、数据都要从磁盘加载到主存里才能被CPU访问这也就是存储程序式计算机的基本工作方式。主存的地址空间是所有层次里唯一被统一编址的CPU发出的虚拟地址经过MMU翻译成物理地址物理地址对应的存储单元就落在主存里。上层缓存只是主存的影子下层磁盘则按文件或页面的粒度去映射到主存。值得多提一句的是DRAM的访问方式。主存按行和列寻址一次突发传输会连续读出整行的一段数据。所以如果你的程序连续访问内存里相邻的地址实际访问效率会高很多如果隔一个很大的步长跳着访问就会频繁触发新的行激活白白增加延迟。这一点是很多为什么乱序访问数组那么慢的底层原因。2.3 外存SSD、HDD与大容量归档再往下是外存。SSD用的是闪存颗粒没有机械运动随机读写的延迟在几十微秒级别比机械盘快了两三个数量级但它内部有擦写寿命和垃圾回收机制随机小写比顺序写慢很多。HDD靠磁盘旋转和磁头寻道顺序读可以做到每秒几百兆随机寻道一个IO要花十几毫秒对付随机小IO非常吃力。在HDD之下还有磁带和光存储这类归档介质。磁带的特点是顺序读写极快、随机访问极慢单位容量的成本低到极致适合冷数据备份、日志归档这种一万年读一次的场景。很多人觉得磁带古董其实大型数据中心到现在还在大量用因为它在容量和成本这个维度上没有对手。外存这一层跟上层最大的区别是CPU不能直接访问外存。所有数据都必须先通过系统调用进入页缓存然后由内存映射机制让CPU看到。也就是说磁盘到主存这一级的数据搬运是操作系统按页常见4KB来管理的程序员层面看到的就是文件读写。3. 层次结构成立的基石局部性原理3.1 时间局部性与空间局部性整个层次结构能奏效靠的不是硬件有多聪明而是一个经验规律程序对存储的访问不是均匀分布的而是集中在很小的一个范围内。这个规律叫局部性原理分两种。时间局部性指的是刚刚访问过的数据短时间内很可能再次被访问。比如循环里的计数器i每次迭代都要用它在循环期间就是超级热门数据。空间局部性指的是访问了一个地址它附近的地址很可能很快也会被访问。比如遍历数组时arr[0]读完之后大概率接着读arr[1]、arr[2]所以一次性把一整块数据加载进缓存后续访问就都能命中。这两条规律看着简单但合在一起推导出了一个重要结论只要把最近用过的和它旁边的数据放到快层就能以很小的快层容量覆盖程序绝大部分的访问请求。这也解释了为什么缓存容量只有主存的几百分之一却能达到90%以上的命中率。3.2 用一段循环代码看懂局部性我自己最喜欢用矩阵乘法的例子来演示空间局部性。假设有两个2000×2000的数组A、B要算C[i][j] A[i][k] * B[k][j]。如果按i、j、k的顺序写三层循环内层对B的访问是逐列进行的也就是B[k][j]在内存里是跨行跳着取的——每跳一次就错失一次缓存行整个程序会被拖慢好几倍。把循环顺序换成i、k、j之后B[k][j]变成逐行连续访问每次取一个缓存行通常64字节也就是16个float都能被后续访问复用。同样是矩阵乘法一改循环顺序运行时间能缩短一个数量级。我在某一次图像处理的Demo里就亲测过这个效果相同的数据规模循环交换后耗时从3秒降到0.4秒左右。这个小例子说明一个问题层次结构是否高效不只取决于硬件更取决于你的代码访问模式。编译器能帮你做一部分循环变换但它没法完全猜透你的算法意图很多时候还得靠人写代码时注意访问顺序。3.3 局部性不成立时会发生什么反过来看如果程序完全没有局部性比如随机访问一个超大哈希表每次访问都落在不同的内存页和缓存行上那么缓存命中率会跌到惨不忍睹CPU大部分时间都在等着从主存取数据。这时候连SSD和HDD的差距都会被放大因为任何一层缓存都形同虚设。这也是为什么有些看起来数据量不大的程序会突然慢到离谱。我在实际开发中就遇到过一种情况有人把链表节点用new分散分配每个节点在堆里相距很远遍历链表时每条数据都触发一次缓存缺失性能立刻掉到一个数量级以下。改成用连续数组存储节点之后遍历速度直接提了六七倍。这就是空间局部性被破坏之后付出的代价。4. 数据在各层之间如何搬家4.1 缓存硬件自动替你调度缓存和主存之间的数据搬运完全由硬件电路完成不需要操作系统参与。CPU访问某个主存地址时会先用地址的一部分做索引判断数据是否在缓存中。如果在直接返回如果不在就把包含该地址的一整块数据称为缓存行一般是64字节从主存拉进来同时淘汰一个旧行。这里有一件事很多人学的时候容易绕晕缓存里存的是以行为单位的块不是单个字节。所以哪怕你只读了一个字节硬件也会把周围64字节全部加载进来。这就是空间局部性在硬件层面的落地。代价则是如果程序频繁访问相隔正好64字节的地址每个地址都会单独占一行缓存利用率会非常低这种问题有个专门的称呼叫缓存抖动。4.2 映射方式、替换策略与写策略缓存设计里三个经典问题数据放哪、满了踢谁、写的时候怎么办。放哪的问题有三种方案——直接映射、全相联、组相联。直接映射是把每个主存地址固定映射到唯一的缓存行硬件简单但冲突率高全相联是可以放任意位置灵活但比较电路太复杂组相联是折中方案把缓存分成若干组每组内多路选择这也是现代CPU普遍采用的方式。替换策略最经典的是LRU最近最少使用。它的思路是如果一个缓存行很久没被访问了那它接下来被访问的概率也比较低所以优先把它踢出去。实现上硬件会记录每条缓存行的访问顺序近似地维护一个最近使用列表。写策略则有写直达和写回两种写直达是每次写都同步到主存简单但慢写回是只改缓存等行被替换时再一次性写回主存性能更好但需要额外的脏位标记。这些细节看似是硬件课才关心的实际上写代码时也有影响。比如无锁并发编程中伪共享问题就是因为多个核各自修改同一缓存行里的不同变量导致整行数据在核间反复失效性能暴跌。理解了缓存行的概念才能在布局数据结构时主动做填充对齐把不同线程的热点变量隔开。4.3 主存与磁盘之间靠操作系统主存和磁盘之间没有纯硬件那么快的自动机制这一层主要由操作系统管理。常见的手段有两块一是页缓存读文件时内核把磁盘页缓存到主存下次再读同样的文件就直接命中缓存避免重复读盘二是虚拟内存当物理内存不足时操作系统把暂时不用的页换出到磁盘上的交换分区需要时再换回来。这两套机制对应用来说是透明的但应用的行为会明显影响它们的效果。比如顺序读一个大文件页缓存会做预读就算你只读了一部分内核也会把后续几MB提前搬进主存这是对空间局部性在操作系统层的应用。反过来如果你以很小的随机大小频繁写文件页缓存会被不停地刷盘写放大非常严重程序就会表现出明明数据不大但磁盘IO飙满的怪现象。另外SSD这一层还有FTL闪存转换层在做地址映射、磨损均衡和垃圾回收它把闪存先擦后写的限制伪装成普通的块设备接口。所以严格说现代存储的层次里一个SSD内部也是一个小型层次结构这正好印证了层次化设计是可以递归套用的。5. 平均访问时间怎么算几个亲手算过的例子5.1 命中率与缺失代价理解层次结构之后最实用的能力是估算平均访问时间。公式很好记平均访问时间 命中时间 缺失率 × 缺失代价。命中时间是访问上一层快层的时间缺失代价是数据从下一层取回来需要额外花的时间。举个例子假设L1缓存命中时间1ns主存访问100ns缺失率5%。平均访问时间 1 0.05 × 100 6ns。相比完全没有缓存直接访问主存的100ns快了大概16倍。注意缺失代价通常是命中时间的几十上百倍所以哪怕缺失率只有几个百分点对性能的拖累也相当可观。这个公式最反直觉的地方在于缺失率不是越低越好而是要和缺失代价一起看。如果在L2和主存之间再插一层每一层的缺失代价都要乘上上一层的缺失率逐级放大。所以做优化时优先消灭代价最大的那层缺失性价比最高。5.2 加一层缓存能快多少我手工算过另一个例子更能说明层次结构的威力。假设一个程序100次访存里98次命中L12ns2次落到主存100ns。平均每次访存 0.98×2 0.02×100 3.96ns。如果完全不命中L1每次都要走100ns差距大概是25倍。再把L2加进来98%命中L11.5%命中L210ns0.5%走主存100ns。平均 0.98×2 0.015×10 0.005×100 1.96 0.15 0.5 2.61ns。加了L2之后平均延迟从3.96ns降到了2.61ns。因为L2兜住了部分L1缺失真正走到主存的请求被压到了更低的占比。这类计算不需要精确到小数点关键是建立起每一层都在降低远程访问概率的直觉。你可以在Excel里列张表把各层命中率和延迟填进去最后得到的平均访问时间几乎总是比主存速度磁盘速度直观感受快很多这就是层次结构的价值。5.3 计算结果的直觉理解算过几遍之后你会发现一个规律只要上层命中率足够高高到90%以上平均访问时间就主要由上层速度决定下层再慢也影响有限。反过来一旦上层命中率掉到70%甚至更低平均访问时间会急剧恶化接近下一层的速度。所以我们在实际中经常会做二八判断程序80%以上的时间都花在等待数据上而绝大多数访存应该落在缓存里。要是发现某个热点函数的缓存命中率异常低基本可以断定问题出在数据结构或访问模式上从算法层面去改效果往往比更换硬件立竿见影得多。这也是为什么层次结构不只是硬件工程师的知识写应用代码的人同样值得吃透。6. 实操心得如何用层次结构的思路排查性能问题6.1 看程序慢先判断瓶颈在哪一层我调性能问题时的第一步永远不是盲目优化代码而是先判断时间到底花在哪一层。基本思路是分层检查先用性能分析工具看CPU周期和缓存缺失率再通过系统监控看内存带宽和磁盘IO。如果缓存缺失率高说明问题在代码的访问模式如果大量时间在内核态等待IO完成说明问题在存储层。这里我常用一个简单粗暴的判断法把程序的数据集从内存里抠出来试试。比如先把文件全部读进内存再做处理如果速度立刻提升几十倍说明瓶颈在磁盘IO如果把数据从SSD挪到内存后速度变化不大那瓶颈多半在CPU缓存或算法本身。用这种分层排除法通常十分钟内就能定位到是慢在盘还是慢在码。6.2 写代码时怎么讨好缓存要充分利用层次结构我总结了几条屡试不爽的经验第一尽量顺序访问数据把循环改成对连续内存的遍历第二让热点数据尽量紧凑能用结构体数组就别用指针链表第三多线程并发修改数据时注意缓存行对齐防止伪共享。这些改动的共同本质都是提升空间局部性让硬件自动替你多命中缓存。另外还有个冷门但实用的技巧如果你的数据会被反复多次读取可以主动利用操作系统的页缓存。比如一次完整地顺序读一遍文件再处理会比反复随机定位读取快很多因为内核会预读并把后续页提前放进主存。做大数据处理时把中间结果写成顺序文件而不是频繁打开关闭大量小文件也能明显减少磁盘寻道开销。6.3 几个常见误区和检查清单最后整理几个我踩过或者常看别人踩的坑。第一只盯CPU占用率不看内存等待CPU占用率低时往往不是CPU闲着而是在等内存和磁盘这时候调代码比加核更有用。第二以为SSD快就能随意随机IOSSD随机IO虽然比机械盘好很多但比顺序IO还是差距明显大批量随机读写照样能把系统拖慢。第三忽视数据在内存中的布局同样的逻辑用不同的数据结构组织实测性能能差一个数量级这在层次结构下是常态而不是意外。我整理了一份简易自检清单写代码前可以过一遍数据访问是不是按内存地址的顺序走的热点数据有没有可能被反复从慢层加载多线程共享数据会不会互相拖累缓存行是否有大量小粒度随机文件IO可以改成顺序批处理瓶颈是CPU算力、内存等待还是磁盘IO有没有先用监控数据判断过这套清单对应到层次结构上其实就是一句话每一层都希望你的访问模式尽量连续、尽量复用谁违反了这条规律谁就得付出成倍的性能代价。个人体会是存储层次结构这个知识点学的时候感觉全是概念用的时候才知道它是整个性能优化的第一性原则。不管你是写上层业务还是啃底层系统只要程序还在处理数据就绕不开缓存、主存、磁盘这三层之间的博弈。把这套思维装进脑子里以后再遇到莫名其妙的性能问题至少不会毫无头绪地瞎猜。
最近整理学习笔记时重读到存储设备形成层次结构这一节突然发现这个知识点比想象中重要得多——它不只是教科书上那张金字塔图而是贯穿硬件设计、操作系统调度和日常代码优化的一条主线。这篇笔记我尽量用自己的话把逻辑讲清楚为什么存储设备必须分成好几层每一层具体是什么、速度容量差多少以及怎样用局部性原理去理解整个系统。适合正在学计算机组成原理、操作系统或者写代码时总想知道程序为什么这么慢的读者。说实话当年学这节我也就是背下了寄存器快、内存快、磁盘慢的结论直到后来调一个数据处理程序的时候才发现层次结构的知识直接决定了我怎么改代码能提速十倍。所以这篇不打算只抄书我会结合自己踩过的坑、算过的数尽量写成一份能直接拿走用的笔记。1. 为什么存储设备要分等级而不是全部用最快的1.1 一台机器里最快的存储贵到离谱先把最朴素的问题摆出来既然寄存器最快为什么我们不把整个电脑都做成寄存器答案是价格和物理密度都不允许。寄存器本质上是用高速触发器电路做出来的它在CPU内部跟运算单元紧贴在一起访问延迟是纳秒级。但你看看一块CPU里寄存器总共才多少——通常几十到几百个字节撑死也就一KB级别。反过来硬盘的容量能做到几十TB单价确实便宜但机械盘的寻道时间是以毫秒计的。毫秒和纳秒之间差了六个数量级你不可能让CPU等一个来回要几毫秒的数据。这里就出现了计算机系统里最核心的矛盾快的存储贵且容量小慢的存储便宜但容量大。层次结构就是调和这个矛盾的产物。1.2 快慢之间差了六个数量级我习惯把这个差距用一张数量级表来记比纯文字直观很多存储层次典型访问延迟典型容量每GB成本大致量级寄存器0.3 ~ 1 ns几十到几百字节极高无法用GB算L1缓存1 ~ 2 ns32 ~ 64 KB/核极高L2缓存3 ~ 8 ns256 KB ~ 1 MB/核很高L3缓存10 ~ 20 ns8 ~ 64 MB共享高主存RAM50 ~ 100 ns8 ~ 64 GB中等固态盘SSD5 ~ 50 μs256 GB ~ 4 TB低机械硬盘HDD5 ~ 15 ms1 ~ 20 TB很低磁带/归档存储秒级及以上PB级极低从寄存器到机械盘延迟大概差了七到八个数量级容量差了上百万倍。如果只能选一种存储要么快得装不下一个程序要么大得慢到没法用。层次结构的设计目标就一句话用少数极贵的快速存储搭配大量便宜的慢速存储让程序访问的时候大部分数据都能从快的里面拿到。1.3 层次结构要解决的三个问题把目标拆开层次结构其实要回答三个问题第一数据放在哪一层由谁决定第二数据什么时候从慢层搬到快层第三快层满了之后把谁踢出去。这三个问题在不同层次有不同的答案。在寄存器这一层放哪些变量是编译器在编译期决定的在缓存这一层数据搬移和淘汰完全由硬件自动完成程序员无感知在主存和磁盘之间则由操作系统负责比如虚拟内存、文件页缓存。理解了这个分工之后再回看整张图你会发现层次结构不是一个静态的仓库列表而是一套动态的数据调度机制。上层的容量小所以它是下层的缓存下层的容量大所以它是上层的后备仓库。每一层对上层而言都像是一个更大更慢的影子存储。2. 逐层拆解从寄存器到磁带2.1 金字塔顶端的寄存器与缓存寄存器是离CPU运算单元最近的存储它本身就在CPU的核心电路里。一个时钟周期内就能完成读写所以很多指令的源操作数和目的操作数都要求放到寄存器里。编译器在优化代码时做的寄存器分配就是尽可能把最热门的变量放到寄存器里避免频繁访问主存。寄存器下面是L1、L2、L3这三级缓存。为什么缓存也要分三级因为单级缓存做不大做大了延迟就又上去了。L1要跟CPU同频工作只能做得又小又专属一个核放个几十KB已经是极限L2稍微大一点延迟也相应高一些L3再大一圈通常被多个核共享。这三者严格说都是SRAM做的断电丢数据但读写不需要刷新周期所以能跟着CPU跑得飞快。这里有个特别容易被新手忽略的点缓存并不是主存的备份它是主存中一小部分数据的副本。CPU要读一个地址先看它在不在缓存里在就命中不在就去主存取取回来同时写入缓存。缓存是硬件自动管理的你写代码时根本感觉不到但它对性能的影响却大到令人吃惊——一个缓存命中不到2ns一次缓存缺失去主存可能是80ns差了四十倍。2.2 主存承接一切的工作台主存DRAM就是大家平时说的内存条。DRAM的每一位数据靠电容上的电荷来表示电容会漏电所以需要周期性地刷新这也是它比SRAM慢的原因之一。但DRAM每个比特的成本比SRAM低很多所以可以做到几十GB成为所有正在运行的程序共同的工作台。所有进程的代码、数据都要从磁盘加载到主存里才能被CPU访问这也就是存储程序式计算机的基本工作方式。主存的地址空间是所有层次里唯一被统一编址的CPU发出的虚拟地址经过MMU翻译成物理地址物理地址对应的存储单元就落在主存里。上层缓存只是主存的影子下层磁盘则按文件或页面的粒度去映射到主存。值得多提一句的是DRAM的访问方式。主存按行和列寻址一次突发传输会连续读出整行的一段数据。所以如果你的程序连续访问内存里相邻的地址实际访问效率会高很多如果隔一个很大的步长跳着访问就会频繁触发新的行激活白白增加延迟。这一点是很多为什么乱序访问数组那么慢的底层原因。2.3 外存SSD、HDD与大容量归档再往下是外存。SSD用的是闪存颗粒没有机械运动随机读写的延迟在几十微秒级别比机械盘快了两三个数量级但它内部有擦写寿命和垃圾回收机制随机小写比顺序写慢很多。HDD靠磁盘旋转和磁头寻道顺序读可以做到每秒几百兆随机寻道一个IO要花十几毫秒对付随机小IO非常吃力。在HDD之下还有磁带和光存储这类归档介质。磁带的特点是顺序读写极快、随机访问极慢单位容量的成本低到极致适合冷数据备份、日志归档这种一万年读一次的场景。很多人觉得磁带古董其实大型数据中心到现在还在大量用因为它在容量和成本这个维度上没有对手。外存这一层跟上层最大的区别是CPU不能直接访问外存。所有数据都必须先通过系统调用进入页缓存然后由内存映射机制让CPU看到。也就是说磁盘到主存这一级的数据搬运是操作系统按页常见4KB来管理的程序员层面看到的就是文件读写。3. 层次结构成立的基石局部性原理3.1 时间局部性与空间局部性整个层次结构能奏效靠的不是硬件有多聪明而是一个经验规律程序对存储的访问不是均匀分布的而是集中在很小的一个范围内。这个规律叫局部性原理分两种。时间局部性指的是刚刚访问过的数据短时间内很可能再次被访问。比如循环里的计数器i每次迭代都要用它在循环期间就是超级热门数据。空间局部性指的是访问了一个地址它附近的地址很可能很快也会被访问。比如遍历数组时arr[0]读完之后大概率接着读arr[1]、arr[2]所以一次性把一整块数据加载进缓存后续访问就都能命中。这两条规律看着简单但合在一起推导出了一个重要结论只要把最近用过的和它旁边的数据放到快层就能以很小的快层容量覆盖程序绝大部分的访问请求。这也解释了为什么缓存容量只有主存的几百分之一却能达到90%以上的命中率。3.2 用一段循环代码看懂局部性我自己最喜欢用矩阵乘法的例子来演示空间局部性。假设有两个2000×2000的数组A、B要算C[i][j] A[i][k] * B[k][j]。如果按i、j、k的顺序写三层循环内层对B的访问是逐列进行的也就是B[k][j]在内存里是跨行跳着取的——每跳一次就错失一次缓存行整个程序会被拖慢好几倍。把循环顺序换成i、k、j之后B[k][j]变成逐行连续访问每次取一个缓存行通常64字节也就是16个float都能被后续访问复用。同样是矩阵乘法一改循环顺序运行时间能缩短一个数量级。我在某一次图像处理的Demo里就亲测过这个效果相同的数据规模循环交换后耗时从3秒降到0.4秒左右。这个小例子说明一个问题层次结构是否高效不只取决于硬件更取决于你的代码访问模式。编译器能帮你做一部分循环变换但它没法完全猜透你的算法意图很多时候还得靠人写代码时注意访问顺序。3.3 局部性不成立时会发生什么反过来看如果程序完全没有局部性比如随机访问一个超大哈希表每次访问都落在不同的内存页和缓存行上那么缓存命中率会跌到惨不忍睹CPU大部分时间都在等着从主存取数据。这时候连SSD和HDD的差距都会被放大因为任何一层缓存都形同虚设。这也是为什么有些看起来数据量不大的程序会突然慢到离谱。我在实际开发中就遇到过一种情况有人把链表节点用new分散分配每个节点在堆里相距很远遍历链表时每条数据都触发一次缓存缺失性能立刻掉到一个数量级以下。改成用连续数组存储节点之后遍历速度直接提了六七倍。这就是空间局部性被破坏之后付出的代价。4. 数据在各层之间如何搬家4.1 缓存硬件自动替你调度缓存和主存之间的数据搬运完全由硬件电路完成不需要操作系统参与。CPU访问某个主存地址时会先用地址的一部分做索引判断数据是否在缓存中。如果在直接返回如果不在就把包含该地址的一整块数据称为缓存行一般是64字节从主存拉进来同时淘汰一个旧行。这里有一件事很多人学的时候容易绕晕缓存里存的是以行为单位的块不是单个字节。所以哪怕你只读了一个字节硬件也会把周围64字节全部加载进来。这就是空间局部性在硬件层面的落地。代价则是如果程序频繁访问相隔正好64字节的地址每个地址都会单独占一行缓存利用率会非常低这种问题有个专门的称呼叫缓存抖动。4.2 映射方式、替换策略与写策略缓存设计里三个经典问题数据放哪、满了踢谁、写的时候怎么办。放哪的问题有三种方案——直接映射、全相联、组相联。直接映射是把每个主存地址固定映射到唯一的缓存行硬件简单但冲突率高全相联是可以放任意位置灵活但比较电路太复杂组相联是折中方案把缓存分成若干组每组内多路选择这也是现代CPU普遍采用的方式。替换策略最经典的是LRU最近最少使用。它的思路是如果一个缓存行很久没被访问了那它接下来被访问的概率也比较低所以优先把它踢出去。实现上硬件会记录每条缓存行的访问顺序近似地维护一个最近使用列表。写策略则有写直达和写回两种写直达是每次写都同步到主存简单但慢写回是只改缓存等行被替换时再一次性写回主存性能更好但需要额外的脏位标记。这些细节看似是硬件课才关心的实际上写代码时也有影响。比如无锁并发编程中伪共享问题就是因为多个核各自修改同一缓存行里的不同变量导致整行数据在核间反复失效性能暴跌。理解了缓存行的概念才能在布局数据结构时主动做填充对齐把不同线程的热点变量隔开。4.3 主存与磁盘之间靠操作系统主存和磁盘之间没有纯硬件那么快的自动机制这一层主要由操作系统管理。常见的手段有两块一是页缓存读文件时内核把磁盘页缓存到主存下次再读同样的文件就直接命中缓存避免重复读盘二是虚拟内存当物理内存不足时操作系统把暂时不用的页换出到磁盘上的交换分区需要时再换回来。这两套机制对应用来说是透明的但应用的行为会明显影响它们的效果。比如顺序读一个大文件页缓存会做预读就算你只读了一部分内核也会把后续几MB提前搬进主存这是对空间局部性在操作系统层的应用。反过来如果你以很小的随机大小频繁写文件页缓存会被不停地刷盘写放大非常严重程序就会表现出明明数据不大但磁盘IO飙满的怪现象。另外SSD这一层还有FTL闪存转换层在做地址映射、磨损均衡和垃圾回收它把闪存先擦后写的限制伪装成普通的块设备接口。所以严格说现代存储的层次里一个SSD内部也是一个小型层次结构这正好印证了层次化设计是可以递归套用的。5. 平均访问时间怎么算几个亲手算过的例子5.1 命中率与缺失代价理解层次结构之后最实用的能力是估算平均访问时间。公式很好记平均访问时间 命中时间 缺失率 × 缺失代价。命中时间是访问上一层快层的时间缺失代价是数据从下一层取回来需要额外花的时间。举个例子假设L1缓存命中时间1ns主存访问100ns缺失率5%。平均访问时间 1 0.05 × 100 6ns。相比完全没有缓存直接访问主存的100ns快了大概16倍。注意缺失代价通常是命中时间的几十上百倍所以哪怕缺失率只有几个百分点对性能的拖累也相当可观。这个公式最反直觉的地方在于缺失率不是越低越好而是要和缺失代价一起看。如果在L2和主存之间再插一层每一层的缺失代价都要乘上上一层的缺失率逐级放大。所以做优化时优先消灭代价最大的那层缺失性价比最高。5.2 加一层缓存能快多少我手工算过另一个例子更能说明层次结构的威力。假设一个程序100次访存里98次命中L12ns2次落到主存100ns。平均每次访存 0.98×2 0.02×100 3.96ns。如果完全不命中L1每次都要走100ns差距大概是25倍。再把L2加进来98%命中L11.5%命中L210ns0.5%走主存100ns。平均 0.98×2 0.015×10 0.005×100 1.96 0.15 0.5 2.61ns。加了L2之后平均延迟从3.96ns降到了2.61ns。因为L2兜住了部分L1缺失真正走到主存的请求被压到了更低的占比。这类计算不需要精确到小数点关键是建立起每一层都在降低远程访问概率的直觉。你可以在Excel里列张表把各层命中率和延迟填进去最后得到的平均访问时间几乎总是比主存速度磁盘速度直观感受快很多这就是层次结构的价值。5.3 计算结果的直觉理解算过几遍之后你会发现一个规律只要上层命中率足够高高到90%以上平均访问时间就主要由上层速度决定下层再慢也影响有限。反过来一旦上层命中率掉到70%甚至更低平均访问时间会急剧恶化接近下一层的速度。所以我们在实际中经常会做二八判断程序80%以上的时间都花在等待数据上而绝大多数访存应该落在缓存里。要是发现某个热点函数的缓存命中率异常低基本可以断定问题出在数据结构或访问模式上从算法层面去改效果往往比更换硬件立竿见影得多。这也是为什么层次结构不只是硬件工程师的知识写应用代码的人同样值得吃透。6. 实操心得如何用层次结构的思路排查性能问题6.1 看程序慢先判断瓶颈在哪一层我调性能问题时的第一步永远不是盲目优化代码而是先判断时间到底花在哪一层。基本思路是分层检查先用性能分析工具看CPU周期和缓存缺失率再通过系统监控看内存带宽和磁盘IO。如果缓存缺失率高说明问题在代码的访问模式如果大量时间在内核态等待IO完成说明问题在存储层。这里我常用一个简单粗暴的判断法把程序的数据集从内存里抠出来试试。比如先把文件全部读进内存再做处理如果速度立刻提升几十倍说明瓶颈在磁盘IO如果把数据从SSD挪到内存后速度变化不大那瓶颈多半在CPU缓存或算法本身。用这种分层排除法通常十分钟内就能定位到是慢在盘还是慢在码。6.2 写代码时怎么讨好缓存要充分利用层次结构我总结了几条屡试不爽的经验第一尽量顺序访问数据把循环改成对连续内存的遍历第二让热点数据尽量紧凑能用结构体数组就别用指针链表第三多线程并发修改数据时注意缓存行对齐防止伪共享。这些改动的共同本质都是提升空间局部性让硬件自动替你多命中缓存。另外还有个冷门但实用的技巧如果你的数据会被反复多次读取可以主动利用操作系统的页缓存。比如一次完整地顺序读一遍文件再处理会比反复随机定位读取快很多因为内核会预读并把后续页提前放进主存。做大数据处理时把中间结果写成顺序文件而不是频繁打开关闭大量小文件也能明显减少磁盘寻道开销。6.3 几个常见误区和检查清单最后整理几个我踩过或者常看别人踩的坑。第一只盯CPU占用率不看内存等待CPU占用率低时往往不是CPU闲着而是在等内存和磁盘这时候调代码比加核更有用。第二以为SSD快就能随意随机IOSSD随机IO虽然比机械盘好很多但比顺序IO还是差距明显大批量随机读写照样能把系统拖慢。第三忽视数据在内存中的布局同样的逻辑用不同的数据结构组织实测性能能差一个数量级这在层次结构下是常态而不是意外。我整理了一份简易自检清单写代码前可以过一遍数据访问是不是按内存地址的顺序走的热点数据有没有可能被反复从慢层加载多线程共享数据会不会互相拖累缓存行是否有大量小粒度随机文件IO可以改成顺序批处理瓶颈是CPU算力、内存等待还是磁盘IO有没有先用监控数据判断过这套清单对应到层次结构上其实就是一句话每一层都希望你的访问模式尽量连续、尽量复用谁违反了这条规律谁就得付出成倍的性能代价。个人体会是存储层次结构这个知识点学的时候感觉全是概念用的时候才知道它是整个性能优化的第一性原则。不管你是写上层业务还是啃底层系统只要程序还在处理数据就绕不开缓存、主存、磁盘这三层之间的博弈。把这套思维装进脑子里以后再遇到莫名其妙的性能问题至少不会毫无头绪地瞎猜。
