06. 存储层次结构

0. 本章先解决什么问题

程序运行时,数据不在一个统一的“存储空间”里。它可能在:

寄存器
L1 Cache
L2 Cache
L3 Cache
主内存
SSD
磁盘
网络存储

这些层次速度、容量、价格完全不同。

本章要解决:

• 为什么存储一定要分层?
• 每一层解决什么问题?
• 局部性为什么能让缓存有效?
• 为什么慢不一定慢在 CPU,而可能慢在数据到不了 CPU?
• 为什么数据结构和访问模式会决定真实性能?
• 写入、持久化、掉电风险和缓存有什么关系?

这张图怎么读

读存储层次图时,看三条梯度:

• 越靠近 CPU:越快、越小、越贵、越易失
• 越远离 CPU:越慢、越大、越便宜、越适合持久化

每一层都在缓存下一层:

性能问题经常不是“CPU 不会算”,而是数据没有及时从下层送到上层。

1. 理想存储不存在

理想存储应该:

• 非常快。
• 非常大。
• 非常便宜。
• 永久保存。
• 随机访问也快。

现实中这些目标冲突。

所以系统用分层结构折中:

小而快的层保存近期会用的数据
大而慢的层保存更多数据

2. 存储层次的基本形态

简化:

CPU
-> Registers
-> L1 Cache
-> L2 Cache
-> L3 Cache
-> DRAM
-> SSD / Disk

越往上:

更快、更小、更靠近 CPU

越往下:

更慢、更大、更适合长期保存

程序访问数据时,硬件和系统会尽量让热数据留在上层。

3. 局部性:缓存有效的根本原因

缓存不是魔法,它依赖局部性。

如果程序完全随机访问巨大数据,缓存很难帮忙。

如果程序顺序扫描连续数组,缓存非常有效。

访问 a[0]
-> 缓存线把 a[0] 附近数据一起带入
访问 a[1], a[2], a[3]
-> 很可能已经在 Cache

这就是数组遍历通常比指针乱跳更友好的原因。

3.1 working set:程序真正热的数据集合

一个程序可能拥有很多数据,但某段时间内真正频繁访问的只是其中一小部分。这部分叫工作集。

• 总数据集:很大
• 当前工作集:正在反复访问的一小块

如果工作集能放进 Cache 或内存,程序会很快;如果工作集超过上层容量,就会频繁 miss 或换页。

这解释了很多“数据量到某个点突然变慢”的现象。不是算法突然变了,而是工作集越过了某层存储容量边界。

4. 每一层都在缓存下一层

存储层次可以看成一层缓存下一层:

寄存器缓存正在计算的数据
L1 缓存近期 CPU 使用的数据
L2/L3 缓存更大的热点集合
内存缓存运行中的程序和数据
操作系统页缓存缓存磁盘文件

所以“缓存”不只是应用层概念。硬件和操作系统里到处都是缓存。

这也意味着缓存问题到处都会出现:

• 命中还是未命中。
• 脏数据什么时候写回。
• 多副本是否一致。
• 空间满了淘汰谁。
• 预取是否有效。

4.1 命中率和 miss penalty

缓存性能取决于两个量:

• 命中率:有多少访问能在上层找到
• miss penalty:未命中后要等下层多久

如果 miss penalty 很大,就算 miss 比例不高,也可能拖慢整体。

例如:

99% 命中很快
1% miss 很慢

这 1% 可能决定尾延迟。硬件 Cache、页缓存、应用缓存都有这个规律。

所以分析存储层次时,不只看“有没有缓存”,还要看:

手推:平均访问时间 AMAT 为什么会被少量 miss 拉高

缓存常用一个简化模型:

AMAT = hit time + miss rate * miss penalty

其中:

• hit time:命中上层缓存的时间
• miss rate:未命中比例
• miss penalty:未命中后去下层等待的额外时间

假设:

hit time = 1 ns
miss penalty = 100 ns
miss rate = 1%

那么:

AMAT = 1 ns + 0.01 * 100 ns = 2 ns

只有 1% miss,平均访问时间已经翻倍。

如果访问模式变差,miss rate 从 1% 升到 10%:

AMAT = 1 ns + 0.10 * 100 ns = 11 ns

平均访问时间变成原来的 5 倍以上。这里真正可怕的不是某一次 miss,而是 miss penalty 很大时,少量比例变化就能支配整体。

这个模型能解释很多现象:

分析时不要只问“缓存多大”,还要问“热数据是否能稳定命中”。

5. 主内存 DRAM 的角色

主内存保存正在运行的程序和数据。

特点:

• 比 Cache 大很多。
• 比 Cache 慢很多。
• 断电后数据丢失。
• CPU 通常不能像访问寄存器一样快地访问它。

操作系统会把进程的代码、堆、栈、映射文件等放在内存里,并通过虚拟内存机制管理地址空间。

组成原理和操作系统在这里交汇:

硬件提供内存访问和地址转换基础
操作系统负责分配、保护、换页、共享

5.1 TLB:地址转换也需要缓存

程序使用虚拟地址,硬件要把虚拟地址翻译成物理地址。这个翻译通常依赖页表。

如果每次内存访问都去查完整页表,成本会很高。所以处理器会缓存最近的地址翻译结果,这类缓存通常叫 TLB。

简化路径:

虚拟地址
-> TLB 命中: 快速得到物理地址
-> TLB 未命中: 查页表,成本更高
-> 再访问 Cache/内存

这说明内存访问不只是“拿数据”:

先翻译地址
再查 Cache
再可能访问内存

大工作集、随机访问、跨很多页跳转,都可能增加 TLB 压力。

反例:数据都在内存里,也可能因为 TLB 慢下来

很多人以为只要数据在内存里,就不会有“存储问题”。但内存访问前还要做地址翻译。

假设一个程序随机访问很多页:

访问 page 1 的一个元素
访问 page 9000 的一个元素
访问 page 42 的一个元素
访问 page 70000 的一个元素
…

每次访问的数据量很小,但跨越的页很多。即使这些页都在 DRAM 里,TLB 也可能频繁未命中:

所以“数据在内存”只是第一层判断。还要继续问:

访问是否连续?
工作集跨多少页?
TLB 和 Cache 是否能复用?

这也是分块处理和连续布局有效的底层原因之一。

边界条件:working set 同时压垮 Cache 和 TLB 时,会出现断崖

working set 是一段时间内真正被反复访问的数据集合。它有两个关键尺度:

• 热字节数:是否放得进 Cache
• 热页数:是否放得进 TLB

假设一个循环反复访问 64 MB 数据。单看 DRAM 容量,这点数据很小;但如果上层 Cache 只能容纳其中一小部分,且访问顺序接近随机,就会发生:

Cache 装不下热数据
-> 数据访问频繁 miss
TLB 装不下热页翻译
-> 地址翻译也频繁 miss
CPU 指令流没有停,但大部分时间在等数据

这类问题常有一个明显指纹:

分块处理的直觉是把大 working set 切成小窗口:

一次只处理能放进缓存和 TLB 的一块
处理完再移动到下一块

所以“数据量一大突然慢”不一定是算法复杂度变了,也可能是工作集跨过了硬件层次边界。

6. 存储设备和持久化

SSD、磁盘等外存用于长期保存数据。

特点:

写入外存不等于数据立刻安全。

可能路径:

程序写入
-> 用户缓冲区
-> 内核页缓存
-> 设备队列
-> 存储控制器缓存
-> 介质

中间任何缓存都可能让“写成功”和“真正持久化”之间有距离。

这解释了为什么数据库、文件系统会关心 flush、fsync、日志、事务。

6.1 写成功、刷盘成功、事务成功是三件事

写路径里有多个成功层级:

如果你关心崩溃后不丢数据,就不能只看“写函数返回成功”。要看数据是否越过了持久化边界。

这也解释了为什么可靠系统常用:

write temp
fsync temp
rename
fsync directory

具体细节依平台和文件系统而异,但核心思想是:先让新内容完整持久化,再切换引用。

7. 延迟和带宽

访问存储要看两个指标:

小随机读主要受延迟影响。

大顺序读主要受带宽影响。

例子:

随机读很多小块
-> 每次都要等待
-> 延迟累积

顺序读一个大块
-> 一旦开始传输
-> 带宽更重要

这就是为什么批量、顺序、预取常常能提升性能。

7.1 小随机 IO 和大顺序 IO 是两种问题

同样读 1GB 数据:

很多系统把小随机 IO 转换成更顺序的访问:

日志顺序追加
批量写入
合并小请求
预读
LSM / B+ 树等结构设计

你后面学数据库和文件系统时,会反复看到同一个思想:硬件更喜欢顺序、大块、可预测的数据流。

8. 内存带宽也会成为瓶颈

很多人以为 CPU 忙才叫性能瓶颈。实际上内存带宽也会限制程序。

如果程序主要做:

读取大量数据
做很少计算
写回结果

它可能是 memory-bound。

也就是:

CPU 算得动
但数据供不上

这类程序优化方向不是换更复杂算法,而是:

• 减少数据量。
• 改善访问局部性。
• 顺序访问。
• 批量处理。
• 减少中间拷贝。
• 使用更紧凑的数据结构。

8.1 结构体数组和数组结构体

数据布局会改变内存带宽利用率。

假设有很多对象,每个对象有:

x, y, z, status, name, metadata

如果某个循环只需要 x:

for each object:
sum += object.x

对象数组可能每次把 y/z/status/name/metadata 也一起拉进 cache line,浪费带宽。另一种布局是把所有 x 连续放在一起:

x[] y[] z[] status[] …

这样访问 x 时更连续、更紧凑。没有一种布局永远正确,取决于访问模式:

这就是组成原理和数据结构的连接:结构怎么放,决定 CPU 怎么等。

9. 虚拟内存和存储层次的连接

虚拟内存是操作系统和硬件一起提供的抽象。

程序看到的是虚拟地址:

进程以为自己有连续地址空间

硬件和操作系统负责映射到物理内存。

如果某页不在内存,可能发生缺页:

访问虚拟地址
-> 页表发现不在内存
-> 触发缺页异常
-> 操作系统把数据从磁盘或文件加载进内存
-> 继续执行

缺页成本很高,因为它可能触发磁盘 IO。

这解释了:

• 内存不足时程序突然变慢。
• 频繁换页会让系统卡顿。
• 大内存顺序访问和随机访问差异明显。

9.1 缺页不是普通函数调用

缺页会让 CPU 从普通指令执行转到异常处理路径:

访问地址
-> 页表发现页面不在内存
-> 触发缺页异常
-> 操作系统介入
-> 找空闲物理页或换出旧页
-> 从文件/磁盘加载数据
-> 更新页表
-> 回到原指令继续

这条路径非常长。轻微缺页可以被系统处理,频繁缺页会导致程序像“卡死”一样慢。

如果系统进入反复换页:

刚换进来的页很快又被换出
刚换出去的页马上又要用

CPU 大量时间都花在等存储设备,真正计算反而很少。

10. 联系实际:看到程序慢时先判断是哪一层慢

排查性能时,先问:

1. CPU 是否满载?
2. 内存是否足够?
3. 是否频繁缺页?
4. Cache 命中率是否差?
5. 数据访问是顺序还是随机?
6. 磁盘或 SSD 是否忙?
7. 网络存储是否慢?
8. 是否产生大量小 IO?
9. 是否有重复拷贝和格式转换?

如果瓶颈在存储层次,优化方向可能是:

• 改数据布局。
• 批量读取。
• 减少随机访问。
• 使用缓存。
• 减少中间对象。
• 避免无意义复制。
• 让热数据更小、更连续。

可以把它当作一张性能观察卡:

小实验方向:同样大小的数据,分别顺序访问和随机访问。它们的大 O 可能一样,但缓存命中率完全不同。这个实验能把“局部性”从抽象概念变成可观察现象。

排障卡:判断慢在缓存、内存还是存储设备

看到“读取数据慢”,先按访问尺度拆:

练习:设计三种访问模式:顺序读、固定大步长读、随机读。即使不跑实验,也试着预测哪种更容易命中缓存,哪种会触发更多地址转换和内存等待。这个预测能力比记住“内存层次”四个字更重要。

问题:为什么数据量一大,程序突然慢几十倍?

学完本章,可以分析这种真实现象:

同一段处理逻辑,在 10 万条数据时很快;
到 1000 万条数据时突然慢几十倍。

不要只说“大数据量慢”。按存储层次拆:

修复方向可能是:

分块处理
流式处理
压缩数据表示
改连续布局
减少临时对象
按访问模式建立索引或缓存

关键不是“换更快机器”,而是让工作集重新适配存储层次。

11. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 为什么计算机存储要分成寄存器、Cache、内存、磁盘?
2. 时间局部性和空间局部性为什么重要?
3. 为什么顺序访问通常比随机访问快?
4. 为什么写入成功不一定代表数据已经持久化?
5. 延迟和带宽有什么区别?
6. 什么是 memory-bound,为什么 CPU 不忙程序也可能慢?
7. 虚拟内存和缺页为什么会让程序突然变慢?
8. 如何从存储层次角度分析性能瓶颈?

程序性能的核心问题之一是:数据能不能以足够快的速度到达 CPU。

延伸阅读

• 运行时数据区 - 程序计数器
• from - zero · computer-organization