第 5 章大且快：利用存储层级 (Large and Fast: Exploiting Memory Hierarchy)

核心结论

存储技术金字塔：寄存器（1 ns）→ L1 缓存（~1 ns）→ L2/L3 缓存（~10 ns）→ DRAM（~100 ns）→ SSD（~100 μs）→ HDD（~10 ms）——速度差 7 个数量级。
缓存基础（§5.3）：直接映射 / N-路组相联 / 全相联；3 个字段 = tag / index / offset；替换策略 LRU / Random / FIFO。
缓存性能（§5.4）：AMAT = Hit time + Miss rate × Miss penalty；3C 失效（compulsory / capacity / conflict）；优化从降低 miss rate 入手。
虚拟内存（§5.7）：页表 + TLB + 缺页处理；进程隔离 + 内存保护；OS / 硬件协作。
缓存一致性（§5.10）：多核间 cache 同步——MESI 协议（Modified / Exclusive / Shared / Invalid）；snooping / directory。
RAID（§5.11）：0（条带）/ 1（镜像）/ 5（条带 + 单校验）/ 6（条带 + 双校验）；可靠性 vs 性能权衡。

本章主旨

本章是计算机体系结构的"内存章"——理解 CPU 与 DRAM / 磁盘之间的速度鸿沟如何被 存储层级（缓存 / 虚拟内存 / RAID）弥合。CPU 再快，若内存跟不上，性能受限于"内存墙"。理解缓存原理才能写出 cache-friendly 代码（数据局部性）、理解虚拟内存才能理解 OS 与硬件的协作、理解 RAID 才能理解数据中心存储。

一、核心概念

本章围绕 6 个核心概念展开：从存储技术金字塔出发，介绍缓存基础与性能分析，再深入虚拟内存、缓存一致性、RAID 等高级主题。

概念	定义 + 重要性	实现提示
存储技术金字塔	寄存器 / 缓存 / DRAM / SSD / HDD 速度差 7 个数量级；容量 / 成本反相关。	§5.1-§5.2；存储层级的硬件基础。
缓存基础	直接映射 / N-路组相联 / 全相联；tag / index / offset 字段；替换策略。	§5.3；所有缓存设计的通用框架。
缓存性能分析	AMAT = Hit time + Miss rate × Miss penalty；3C 失效（compulsory / capacity / conflict）。	§5.4；优化缓存 = 降低 miss rate + miss penalty。
虚拟内存	页表 + TLB + 缺页；进程隔离 + 内存保护 + 按需分页。	§5.7；OS 与硬件协作管理内存。
缓存一致性 (MESI)	Modified / Exclusive / Shared / Invalid；多核同步；snooping 总线 / directory。	§5.10；多核编程必须理解。
RAID	0（条带）/ 1（镜像）/ 5 / 6 / 10；可靠性 / 性能 / 容量权衡。	§5.11；数据中心存储标准。

概念

定义 + 重要性

实现提示

存储技术金字塔

寄存器 / 缓存 / DRAM / SSD / HDD 速度差 7 个数量级；容量 / 成本反相关。

§5.1-§5.2；存储层级的硬件基础。

缓存基础

直接映射 / N-路组相联 / 全相联；tag / index / offset 字段；替换策略。

§5.3；所有缓存设计的通用框架。

缓存性能分析

AMAT = Hit time + Miss rate × Miss penalty；3C 失效（compulsory / capacity / conflict）。

§5.4；优化缓存 = 降低 miss rate + miss penalty。

虚拟内存

页表 + TLB + 缺页；进程隔离 + 内存保护 + 按需分页。

§5.7；OS 与硬件协作管理内存。

缓存一致性 (MESI)

Modified / Exclusive / Shared / Invalid；多核同步；snooping 总线 / directory。

§5.10；多核编程必须理解。

RAID

0（条带）/ 1（镜像）/ 5 / 6 / 10；可靠性 / 性能 / 容量权衡。

§5.11；数据中心存储标准。

二、详细笔记

2.1 存储技术金字塔 (Memory Technology Pyramid)

What：从寄存器到 HDD 的存储层级，速度 / 容量 / 成本差异巨大。

Why：理解存储层级才能理解为什么"内存墙"是计算机性能的主要瓶颈。

How：

存储层级（§5.1-§5.2）：

层级	访问时间	容量	典型用途
寄存器	~1 ns	1 KB	CPU 内部运算
L1 缓存 (SRAM)	~1-2 ns	32-64 KB / 核	CPU 立即访问
L2 缓存 (SRAM)	~5-10 ns	256-512 KB / 核	私有缓存
L3 缓存 (SRAM)	~20-30 ns	4-32 MB 共享	末级缓存
DRAM	~50-100 ns	8-64 GB	主内存
SSD (NAND Flash)	~50-200 μs	256 GB - 4 TB	持久存储
HDD	~5-15 ms	1-20 TB	大容量归档

层级

访问时间

容量

典型用途

寄存器

~1 ns

1 KB

CPU 内部运算

L1 缓存 (SRAM)

~1-2 ns

32-64 KB / 核

CPU 立即访问

L2 缓存 (SRAM)

~5-10 ns

256-512 KB / 核

私有缓存

L3 缓存 (SRAM)

~20-30 ns

4-32 MB 共享

末级缓存

DRAM

~50-100 ns

8-64 GB

主内存

SSD (NAND Flash)

~50-200 μs

256 GB - 4 TB

持久存储

HDD

~5-15 ms

1-20 TB

大容量归档

速度差异的工程意义

寄存器 vs HDD：差 7 个数量级（10⁷ 倍）。
"内存墙"：CPU 性能受限于内存访问；cache 是唯一可行的弥合方法。
编程含义：尽量利用 cache（数据局部性）；访问模式决定性能。

When：所有性能优化场景；硬件选型（内存 / SSD / HDD 比例）；代码优化（cache-friendly data structures）。

Example：访问连续内存（数组）远快于链式访问（链表）——前者命中 cache，后者每跳都 miss。

2.2 缓存基础 (Cache Basics)

What：缓存用快速 SRAM 存储最近访问的内存块；命中 / 未命中决定性能。

Why：缓存是现代 CPU 性能的核心；理解后才能写 cache-friendly 代码。

How：

地址划分（§5.3）：

\[\text{Address} = \underbrace{\text{Tag}}_{\text{high bits}} | \underbrace{\text{Index}}_{\text{middle bits}} | \underbrace{\text{Offset}}_{\text{low bits}} \end{bmatrix]\]

Tag：高位，标识内存地址。
Index：定位 cache 行（组）。
Offset：定位块内字节。

3 种映射（§5.3）：

直接映射：每个地址映射到固定 cache 行（简单但冲突）。
N-路组相联：每组 N 行，硬件并行比较 tag（平衡性能与复杂度）。
全相联：任何 cache 行都可放任何地址（最灵活但成本高）。

替换策略：LRU / Random / FIFO；LRU 接近最优但硬件昂贵。

cache 设计的工程权衡

直接映射：硬件最简单，但 conflict miss 高（多个地址映射到同一行）。
N-路组相联：硬件中等（并行比较 tag），conflict miss 大幅降低——现代 CPU 标准。
全相联：硬件昂贵（每行都要 tag 比较），仅用于小容量 TLB / L1。

When：所有 cache 设计；性能分析（conflict miss）；算法设计（避免 hot-spot 冲突）。

Example：Intel Core i7 L1 是 8 路组相联（32 KB / 核）；L2 是 8 路（256 KB / 核）；L3 是 16 路共享。

2.3 缓存性能分析 (Cache Performance Analysis)

What：AMAT（Average Memory Access Time）= Hit time + Miss rate × Miss penalty。

Why：量化缓存性能；定位优化方向（命中时间 vs 失效率 vs 失效代价）。

How：

AMAT 公式（§5.4）：

\[\text{AMAT} = T_{\text{hit}} + \text{Miss rate} \times T_{\text{miss}} \end{bmatrix>\]

典型值：L1 hit = 1 ns、L1 miss = 10 ns（去 L2）；miss rate = 5% ⇒ AMAT = 1 + 0.05 × 10 = 1.5 ns。

3C 失效（§5.4）：

Compulsory miss：第一次访问某地址（不可避免）。
Capacity miss：cache 容量不够（工作集 > cache）。
Conflict miss：N-路组相联中多个地址映射到同一行（直接映射最严重）。

优化缓存的 4 个方向

降低 miss rate：更大容量 / 更高相联度 / 预取 / 编译器重排。
降低 miss penalty：多级缓存 / 写缓冲 / 牺牲 cache。
降低 hit time：小容量 L1 / 虚拟 cache / 路预测。
增加 cache 带宽：bank 化 / 多端口 / 非阻塞 cache。

When：所有性能优化；硬件选型（容量 / 相联度）；代码优化（数据局部性）。

Example：数组顺序访问 for (i) sum += a[i] —— 时间局部性 + 空间局部性都很好，miss rate < 1%；链表访问则相反。

2.4 虚拟内存 (Virtual Memory)

What：用磁盘模拟比物理内存大的"虚拟"内存空间；OS 与硬件协作管理。

Why：进程隔离 + 内存保护 + 按需分页；现代 OS 的基础。

How：

虚拟内存机制（§5.7）：

页表：每个进程一个页表，记录虚拟页 → 物理页的映射。
TLB（Translation Lookaside Buffer）：页表项的硬件缓存（虚拟地址 → 物理地址）。
缺页：访问的虚拟页不在物理内存时，OS 从磁盘加载（典型 1-10 ms）。

地址转换（MMU）：

\[\text{Virtual address} \xrightarrow{\text{TLB}} \text{Physical address} \xrightarrow{\text{cache}} \text{Data} \end{bmatrix>\]

虚拟内存的工程优势

进程隔离：每个进程有独立虚拟地址空间，互不干扰。
内存保护：硬件检查每页权限（读 / 写 / 执行）。
按需分页：物理内存不足时自动 swap 到磁盘。
简化编程：程序员无需关心物理内存布局。

When：OS 内核开发；性能分析（缺页率）；编程（避免大内存工作集）。

Example：Linux 默认 4 KB 页；64-bit 虚拟地址空间 256 TB；进程独立地址空间。

2.5 缓存一致性 MESI (Cache Coherence)

What：多核间共享数据的 cache 同步协议——MESI（Modified / Exclusive / Shared / Invalid）。

Why：多核编程必须理解；否则会出现"数据不一致"的诡异 bug。

How：

MESI 状态（§5.10）：

M（Modified）：本核 cache 独占且已修改；其他核无此数据。
E（Exclusive）：本核 cache 独占且未修改；其他核无此数据。
S（Shared）：多个核 cache 都有此数据；未修改。
I（Invalid）：本核 cache 数据无效（已过期）。

总线监听（snooping）：

当某核写入 S 状态数据时，广播 Invalidate 消息；其他核把自己 cache 标记为 I。
当某核读 S 状态数据时，广播 Read 消息；其他核可保持 S。
协议保证一致性但有性能开销（总线流量）。

MESI 的工程权衡

snooping：简单但总线瓶颈（>8 核不可扩展）。
directory：可扩展但硬件复杂（Intel QPI / AMD HyperTransport 用混合方案）。
现代 CPU：两者混合（小核数 snoop、大核数 directory）。

When：多核编程；lock-free 算法；性能分析（false sharing）。

Example：std::atomic / __sync_lock_test_and_set 等原子操作依赖 MESI 保证；volatile 不保证顺序。

2.6 RAID (Redundant Arrays of Inexpensive Disks)

What：用多块廉价磁盘组合提供可靠性 + 性能。

Why：数据中心存储标准；理解 RAID 才能选型 + 配置。

How：

常见 RAID 级别（§5.11）：

RAID 0：条带（striping），性能好但无冗余。
RAID 1：镜像（mirroring），可靠性高但容量减半。
RAID 5：条带 + 单校验，平衡性能 / 可靠性 / 容量。
RAID 6：条带 + 双校验，可容忍两块盘同时坏。
RAID 10（1+0）：先镜像再条带，性能 + 可靠性都好但容量减半。

RAID 的工程权衡

RAID 0：无冗余但性能最高；适合临时数据。
RAID 1：读快写慢；适合关键小数据（OS 盘）。
RAID 5：读快写需校验（4 IOPS 写）；适合大文件存储。
RAID 6：可容忍两块坏；适合大容量存储（NAS / SAN）。
RAID 10：性能 + 可靠性都好；适合数据库（高 IOPS）。

When：存储选型；数据库 / 文件系统设计；数据中心运维。

Example：AWS EBS 默认 RAID；Linux mdadm 软件 RAID；硬件 RAID 卡。

三、关键图表

视觉图表

Figure 1. 图 5-1：存储技术金字塔

Figure 2. 图 5-2：直接映射 cache

Figure 3. 图 5-3：N-路组相联 cache

Figure 4. 图 5-4：AMAT 公式示意

Figure 5. 图 5-5：虚拟地址转换（TLB + 页表）

Figure 6. 图 5-6：MESI 状态转换

Figure 7. 图 5-7：RAID 0 / 1 / 5 / 6 数据布局

非可视化条目

非可视化条目（表 / 算法）

编号

内容摘要

表 5.1

存储技术对比（SRAM / DRAM / Flash / HDD）。

表 5.2

cache 替换策略对比（LRU / FIFO / Random）。

式 5-1 至 5-8

AMAT 公式、3C miss 分解、虚拟地址转换、TLB miss 率。

列表 5.1-5.x

cache 模拟、虚拟地址翻译、MESI 状态机、RAID 5 恢复算法。

表 5.3

ARM Cortex-A53 / Intel Core i7 内存层级对比。

核心公式对照表

概念

公式

AMAT

\(\text{AMAT} = T_{\text{hit}} + \text{Miss rate} \times T_{\text{miss}}\)

3C miss

\(\text{Miss rate} = \text{Compulsory} + \text{Capacity} + \text{Conflict}\)

多级 AMAT

\(\text{AMAT}_n = T_{\text{L1}} + \text{Miss}_{L1} \cdot (T_{L2} + \text{Miss}_{L2} \cdot (\ldots))\)

虚拟地址转换

\(\text{Virtual page} = \text{VA} \gg \text{Page offset bits}\)

TLB miss 率

\(\text{AMAT}_{\text{VM}} = T_{\text{TLB hit}} + \text{TLB miss rate} \times T_{\text{page walk}}\)

四、思维导图

mindmap
  root((第 5 章 内存层级))
    存储金字塔
      SRAMDRAMFlashDisk
      速度差7个量级
      容量成本反相关
    缓存基础
      直接组相联全相联
      tagindexoffset
      LRU替换
    缓存性能
      AMAT公式
      3Cmiss
      命中时间失效率失效代价
    虚拟内存
      页表TLB
      缺页处理
      进程隔离
    缓存一致性
      MESI状态
      snooping
      false sharing
    RAID
      0条带1镜像
      5单校验6双校验
      性能容量可靠性

五、重点与易错点

存储层级速度差异 7 个数量级：访问模式决定性能；cache-friendly 代码比"快算法"更重要。
AMAT 公式优化 3 个变量：hit time / miss rate / miss penalty；任一项优化都提升性能。
3C miss 的工程对策：compulsory（预取 / 大块）、capacity（更大 cache）、conflict（更高相联度）。
MESI 协议是硬件自动维护的：程序员无需关心（除非写 lock-free 代码）；volatile 与 atomic 不同。
false sharing 性能杀手：两个独立变量共享同一 cache 行，写入会触发"snoop invalidation"——padding 解决。
虚拟内存按需分页：进程启动时不立即加载全部；首次访问触发缺页加载。
TLB miss 代价高：一次 TLB miss 需走页表（典型 100 ns+）；大页（HugePage）减少 TLB miss。
RAID 5 写性能差：每次写需读-改-写（4 IOPS）；写密集场景用 RAID 10。
跨章衔接：第 4 章 CPU 微架构用本章缓存加速；第 6 章多核用本章 MESI；附录 D 介绍 ARM Cortex-A53 与 Intel Core i7 的实际内存层级。

第 5 章 大且快：利用存储层级 (Large and Fast: Exploiting Memory Hierarchy)

核心结论

一、核心概念

二、详细笔记

2.1 存储技术金字塔 (Memory Technology Pyramid)

2.2 缓存基础 (Cache Basics)

2.3 缓存性能分析 (Cache Performance Analysis)

2.4 虚拟内存 (Virtual Memory)

2.5 缓存一致性 MESI (Cache Coherence)

2.6 RAID (Redundant Arrays of Inexpensive Disks)

三、关键图表

视觉图表

非可视化条目

核心公式对照表

四、思维导图

五、重点与易错点

第 5 章大且快：利用存储层级 (Large and Fast: Exploiting Memory Hierarchy)