第五章 大而快的存储层次

导读

存储层次结构是现代计算机系统中最重要设计之一，它巧妙地利用了局部性原理，在速度、容量和成本之间取得了精妙的平衡。处理器速度的提升远远快于内存速度的提升，形成了所谓的"内存墙"问题。存储层次通过多级缓存、虚拟内存等技术，让程序员感受到既大又快的存储空间，成为突破内存墙的关键。

本章将系统介绍存储层次结构的设计原理、缓存技术、虚拟内存、以及现代存储系统的关键技术。我们将从局部性原理出发，深入分析缓存的设计和优化，讨论缓存一致性和内存保护等高级话题。通过学习本章，读者将理解存储层次如何工作，掌握缓存设计和优化的方法，了解现代存储系统的关键技术。

核心概念详解

5.1 存储层次基本原理

5.1.1 局部性原理

局部性原理是存储层次结构的理论基础，包括时间局部性和空间局部性。

时间局部性（Temporal Locality）：

• 最近访问过的数据很可能在不久的将来再次被访问
• 原因：循环、函数调用、重复访问
• 应用：缓存保留最近访问的数据

空间局部性（Spatial Locality）：

• 访问某个地址后，很可能在不久的将来访问相邻的地址
• 原因：数组遍历、顺序指令执行
• 应用：缓存行（Cache Line）包含相邻数据

局部性的度量：

• 命中率：访问在缓存中的比例
• 缺失率：访问不在缓存中的比例
• 命中率 + 缺失率 = 1

局部性示例：

// 良好的空间局部性
for (i = 0; i < N; i++)
    sum += a[i];  // 顺序访问

// 良好的时间局部性
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i];  // 重复访问a[i]

// 差的局部性
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[rand() % N];  // 随机访问

5.1.2 存储层次结构

存储层次由多级存储组成，从上到下速度递减、容量递增、成本递减。

典型存储层次：

寄存器：

• 速度：最快（< 1ns）
• 容量：最小（几十到几百个）
• 成本：最贵（每个触发器）
• 管理：编译器

缓存（L1、L2、L3）：

• 速度：快（1-20ns）
• 容量：小（KB到几十MB）
• 成本：贵（SRAM）
• 管理：硬件

主存（DRAM）：

• 速度：中等（50-100ns）
• 容量：中等（GB到TB）
• 成本：中等
• 管理：硬件+操作系统

辅助存储（SSD、HDD）：

• 速度：慢（μs到ms）
• 容量：大（TB到PB）
• 成本：便宜
• 管理：操作系统

远程存储：

• 速度：最慢（ms到s）
• 容量：最大
• 成本：最便宜
• 管理：分布式系统

5.1.3 存储层次性能分析

平均访问时间（AMAT）：

AMAT = 命中时间 + 缺失率 × 缺失惩罚

多级存储层次：

AMAT = L1命中时间 + L1缺失率 × (L2命中时间 + L2缺失率 × (L3命中时间 + L3缺失率 × 主存访问时间))

示例计算：

L1：命中时间1周期，缺失率5%
L2：命中时间10周期，缺失率10%
L3：命中时间50周期，缺失率20%
主存：访问时间200周期

AMAT = 1 + 0.05 × (10 + 0.1 × (50 + 0.2 × 200))
     = 1 + 0.05 × (10 + 0.1 × 90)
     = 1 + 0.05 × 19
     = 1.95 周期

5.2 缓存设计基础

5.2.1 缓存基本概念

缓存是位于处理器和主存之间的高速小容量存储器，用于缓解速度差距。

缓存行（Cache Line）：

• 缓存的基本单位
• 通常为64字节
• 包含地址标签、数据和有效位

缓存操作：

读操作：

检查缓存中是否有请求数据

如果有（命中），返回数据

如果没有（缺失），从下级存储加载数据

将数据放入缓存，返回

写操作：

• 写通（Write Through）：同时写缓存和主存
• 写回（Write Back）：只写缓存，标记为脏，替换时写回主存

5.2.2 缓存映射方式

缓存映射决定了主存地址如何映射到缓存位置。

直接映射（Direct Mapped）：

• 每个主存块只能映射到一个缓存位置
• 地址分为：标签、索引、偏移
• 索引选择缓存行，标签比较，偏移选择字节

优点：

• 实现简单
• 访问速度快
• 硬件开销小

缺点：

• 冲突缺失高
• 灵活性差

全相联（Fully Associative）：

• 主存块可以映射到任何缓存位置
• 需要比较所有标签

优点：

• 冲突缺失最低
• 灵活性最高

缺点：

• 硬件复杂
• 访问速度慢
• 成本高

组相联（Set Associative）：

• 缓存分为多个组，每组多个行
• 主存块映射到特定组，可以在组内任意位置
• n路组相联：每组n行

优点：

• 平衡性能和成本
• 冲突缺失适中
• 实现复杂度适中

选择依据：

• L1缓存：直接映射或2-4路组相联（速度优先）
• L2缓存：4-8路组相联（平衡）
• L3缓存：8-16路组相联（容量优先）

5.2.3 缓存缺失类型

缓存缺失分为三类： compulsory、capacity和conflict。

强制缺失（Compulsory Miss）：

• 第一次访问数据时的缺失
• 也称为冷启动缺失
• 无法避免，只能通过预取减少影响

容量缺失（Capacity Miss）：

• 缓存容量不足导致的缺失
• 即使缓存无限大也不会发生
• 增加缓存容量可以减少

冲突缺失（Conflict Miss）：

• 缓存映射方式导致的缺失
• 即使缓存容量足够也会发生
• 提高相联度可以减少

3C模型：

缺失率 = 强制缺失率 + 容量缺失率 + 冲突缺失率

5.2.4 缓存替换策略

当缓存满时，需要选择替换哪个缓存行。

随机替换（Random）：

• 随机选择替换行
• 实现简单
• 性能一般

先进先出（FIFO）：

• 替换最早进入缓存的行
• 实现简单
• 不考虑访问频率

最近最少使用（LRU）：

• 替换最久未访问的行
• 性能好
• 实现复杂（需要记录访问时间）

近似LRU：

• 使用位矩阵近似LRU
• 性能接近LRU
• 实现简单

伪LRU（PLRU）：

• 使用树结构近似LRU
• 8路以上常用
• 平衡性能和复杂度

5.3 高级缓存技术

5.3.1 多级缓存

现代处理器通常有2-3级缓存。

L1缓存：

• 速度最快
• 容量最小（32-64KB）
• 与核心紧密耦合
• 分为指令缓存和数据缓存（Harvard架构）

L2缓存：

• 速度和容量适中（256KB-1MB）
• 每个核心私有
• 统一缓存（指令和数据）

L3缓存：

• 容量最大（几MB到几十MB）
• 多个核心共享
• 速度较慢

设计考虑：

• 包含（Inclusive）：L2包含L1的所有数据
• 排他（Exclusive）：L2和L1不重叠
• 非包含非排他（NINE）：灵活但复杂

5.3.2 虚拟缓存与物理缓存

虚拟地址缓存：

• 使用虚拟地址访问缓存
• 优点：可以并行进行地址转换和缓存访问
• 缺点：需要处理别名和同义词问题

物理地址缓存：

• 使用物理地址访问缓存
• 优点：避免别名问题
• 缺点：需要先进行地址转换

虚拟索引物理标签（VIPT）：

• 使用虚拟地址索引，物理地址比较标签
• 结合两者优点
• 需要保证页大小是缓存大小的倍数

5.3.3 缓存一致性

多核处理器中，每个核心有自己的缓存，需要保证一致性。

一致性问题：

• 多个核心可能缓存同一数据的副本
• 一个核心修改数据后，其他核心的副本失效

一致性协议：

监听协议（Snoopy Protocol）：

• 所有缓存监听总线
• 检测到写操作时更新或失效本地副本
• 适用于总线互连

目录协议（Directory Protocol）：

• 使用目录记录每个缓存行的状态
• 目录存储在每个节点或集中存储
• 适用于大规模系统

MESI协议：

• Modified：本地修改，与主存不一致
• Exclusive：独占，与主存一致
• Shared：共享，多个核心有副本
• Invalid：无效

状态转换：

• 读请求：I→S或I→E
• 写请求：S→M或E→M
• 失效：S→I或E→I

5.3.4 内存一致性模型

内存一致性模型定义了多处理器系统中内存操作的可见顺序。

强一致性模型：

• 所有处理器看到相同的操作顺序
• 编程简单
• 硬件复杂

弱一致性模型：

• 允许不同的处理器看到不同的顺序
• 需要显式同步
• 硬件简单

常见模型：

顺序一致性（Sequential Consistency）：

• 所有处理器的操作按程序顺序执行
• 所有处理器看到相同的全局顺序
• 最直观的模型

处理器一致性（Processor Consistency）：

• 每个处理器的操作按程序顺序
• 不同处理器的写操作顺序可能不同

弱一致性（Weak Consistency）：

• 普通内存操作不保证顺序
• 同步操作保证顺序

释放一致性（Release Consistency）：

• 获取（Acquire）和释放（Release）操作
• 获取前的操作在获取后可见
• 释放后的操作在释放前不可见

5.4 虚拟内存

5.4.1 虚拟内存基本概念

虚拟内存为每个进程提供独立的地址空间，通过页表映射到物理内存。

虚拟地址空间：

• 每个进程有独立的虚拟地址空间
• 通常为48位或64位
• 远大于物理内存

物理地址空间：

• 实际内存的地址空间
• 通常小于虚拟地址空间

地址转换：

• 虚拟地址 → 物理地址
• 通过页表进行映射
• 由MMU（Memory Management Unit）硬件完成

5.4.2 分页机制

分页是虚拟内存的基本实现方式。

页面（Page）：

• 虚拟内存的基本单位
• 通常为4KB
• 支持大页面（2MB、1GB）

页帧（Page Frame）：

• 物理内存的基本单位
• 与页面大小相同

页表（Page Table）：

• 记录虚拟页面到物理页帧的映射
• 每个进程有独立的页表
• 包含权限位、有效位等

页表项（PTE）：

• 物理页帧号
• 有效位（Valid）
• 保护位（Read/Write/Execute）
• 脏位（Dirty）
• 引用位（Referenced）

5.4.3 TLB（Translation Lookaside Buffer）

TLB是页表的缓存，加速地址转换。

TLB结构：

• 全相联或组相联
• 通常32-1024项
• 包含虚拟页号和物理页帧号

TLB操作：

• 地址转换时先查TLB
• TLB命中：直接得到物理地址
• TLB缺失：查页表，更新TLB

TLB缺失处理：

• 硬件处理：硬件遍历页表
• 软件处理：操作系统处理（如MIPS）

TLB刷新：

• 进程切换时需要刷新TLB
• 使用ASID（Address Space ID）避免刷新

5.4.4 页面置换算法

当物理内存满时，需要选择替换哪个页面。

最优置换（OPT）：

• 替换将来最久不使用的页面
• 理论最优，无法实现
• 用于性能评估

最近最少使用（LRU）：

• 替换最久未使用的页面
• 性能好
• 实现复杂

时钟算法（Clock）：

• 使用引用位近似LRU
• 页面排成环形
• 指针循环扫描

工作集模型：

• 跟踪进程的活跃页面集合
• 只保留工作集在内存中
• 减少抖动

5.4.5 页面错误处理

页面错误（Page Fault）是访问不在内存中的页面时触发的异常。

页面错误类型：

缺页（Page Fault）：

• 页面不在物理内存中
• 需要从磁盘加载

保护错误（Protection Fault）：

• 访问权限不足
• 如写只读页面

段错误（Segmentation Fault）：

• 访问无效地址
• 如空指针解引用

页面错误处理流程：

CPU检测到页面错误

陷入操作系统

操作系统检查错误类型

如果是缺页，分配页帧

从磁盘读取页面

更新页表

重新执行指令

5.5 存储系统优化

5.5.1 内存带宽优化

内存带宽是存储系统的重要性能指标。

带宽计算：

带宽 = 总线宽度 × 频率 / 传输次数

提高带宽的方法：

增加总线宽度：

• 64位 → 128位 → 256位
• DDR内存使用双倍数据率

提高频率：

• DDR、DDR2、DDR3、DDR4、DDR5
• 每代频率翻倍

多通道：

• 双通道、四通道、八通道
• 并行访问多个通道

突发传输：

• 一次传输多个数据
• 减少地址传输开销

5.5.2 内存延迟优化

内存延迟是存储系统的性能瓶颈。

延迟组成：

• 行访问延迟（tCAS）
• 列访问延迟（tRCD）
• 预充电延迟（tRP）
• 刷新延迟

优化技术：

乱序内存访问：

• 允许内存访问乱序执行
• 隐藏内存延迟

内存级并行（MLP）：

• 同时发起多个内存请求
• 隐藏延迟

预取：

• 提前加载数据
• 减少缺失惩罚

5.5.3 非易失性内存

非易失性内存（NVM）结合了DRAM和磁盘的优点。

NVM特性：

• 非易失性：断电不丢失
• 字节可寻址
• 接近DRAM的速度
• 比DRAM容量大

NVM类型：

• PCM（Phase Change Memory）
• ReRAM（Resistive RAM）
• MRAM（Magnetic RAM）
• Intel Optane（3D XPoint）

NVM应用：

• 存储级内存（Storage Class Memory）
• 持久内存
• 内存数据库

5.6 存储系统安全

5.6.1 内存保护

内存保护防止进程访问其他进程的内存。

保护机制：

页表保护：

• 每个页面有权限位
• 读、写、执行权限
• 硬件检查权限

段保护：

• 段描述符包含权限
• 基址和界限检查

隔离技术：

• 用户态和内核态
• 不同权限级别

5.6.2 内存加密

内存加密保护数据不被物理攻击窃取。

加密方式：

全内存加密：

• 所有内存数据加密
• 使用内存控制器加密引擎
• 性能开销小

选择性加密：

• 只加密敏感数据
• 需要软件支持
• 灵活性高

实现技术：

• AES加密
• 每行独立密钥
• 完整性验证

5.6.3 侧信道防护

侧信道攻击通过观察物理特征（如时间、功耗、缓存）窃取信息。

缓存侧信道：

• 观察缓存访问模式
• 推断加密密钥
• 如Prime+Probe攻击

防护技术：

缓存分区：

• 不同安全域使用不同缓存分区
• 防止跨域访问

缓存刷新：

• 上下文切换时刷新缓存
• 防止信息泄露

恒定时间算法：

• 避免数据依赖的分支
• 避免数据依赖的内存访问

重要知识点

知识点1：AMAT计算

平均内存访问时间（AMAT）是评估存储层次性能的关键指标。

公式：

AMAT = 命中时间 + 缺失率 × 缺失惩罚

多级存储：

AMAT = T1 + M1 × (T2 + M2 × (T3 + M3 × Tmain))

示例：

L1: T1=1周期, M1=5%
L2: T2=10周期, M2=10%
Main: Tmain=200周期

AMAT = 1 + 0.05 × (10 + 0.1 × 200)
     = 1 + 0.05 × 30
     = 2.5 周期

知识点2：缓存容量计算

缓存容量由多个参数决定。

计算公式：

缓存大小 = 缓存行数 × (标签大小 + 数据大小 + 有效位 + 脏位)

示例：

32KB 4路组相联缓存
缓存行大小：64字节
标签大小：20位
有效位：1位
脏位：1位

组数 = 32KB / (64B × 4) = 128组
总行数 = 128 × 4 = 512行
总大小 = 512 × (20 + 64×8 + 1 + 1) / 8
      = 512 × 532 / 8
      = 34,048 字节
      ≈ 33.25 KB

知识点3：TLB性能影响

TLB缺失会显著影响性能。

有效访问时间：

EAT = TLB命中时间 + TLB缺失率 × 页表访问时间 + 缓存访问时间

示例：

TLB命中时间：1周期
TLB缺失率：0.1%
页表访问时间：100周期
缓存访问时间：4周期

EAT = 1 + 0.001 × 100 + 4
    = 5.1 周期

知识点4：页面大小权衡

页面大小影响多个性能指标。

小页面优点：

• 内部碎片少
• 页面置换更精细

小页面缺点：

• 页表更大
• TLB覆盖范围小
• 页表遍历次数多

大页面优点：

• 页表更小
• TLB覆盖范围大
• 减少TLB缺失

大页面缺点：

• 内部碎片多
• 分配困难

知识点5：内存带宽计算

内存带宽决定数据传输能力。

计算公式：

带宽 = 总线宽度 × 频率 × 传输次数/周期

示例：

DDR4-3200
总线宽度：64位 = 8字节
频率：3200 MHz
传输次数：2（DDR）

带宽 = 8B × 3200M × 2
     = 51,200 MB/s
     = 51.2 GB/s

常见误区

误区1：缓存越大越好

缓存大小需要权衡多个因素。

问题：

• 大缓存访问延迟高
• 大缓存占用芯片面积
• 大缓存功耗高
• 收益递减

正确做法：

• 根据工作集大小选择
• 多级缓存平衡
• 考虑访问延迟

误区2：相联度越高越好

高相联度增加性能，但也增加成本。

问题：

• 硬件复杂度高
• 访问延迟增加
• 功耗增加

正确做法：

• L1：低相联度（速度优先）
• L2/L3：中等相联度（平衡）
• 根据应用场景选择

误区3：虚拟内存可以无限大

虚拟内存受多个因素限制。

限制因素：

• 地址空间大小
• 磁盘空间
• 页表大小
• 性能开销

实际情况：

• 虚拟内存远大于物理内存
• 但不是无限的
• 过度使用导致抖动

误区4：缓存一致性协议不影响性能

一致性协议有显著性能开销。

开销来源：

• 监听总线流量
• 目录访问延迟
• 状态转换开销
• 缓存失效

优化方法：

• 减少共享数据
• 使用同步原语
• 优化协议实现

误区5：内存速度会跟上处理器速度

内存速度提升远慢于处理器。

实际情况：

• 处理器速度每年提升20-30%
• 内存速度每年提升7-10%
• 差距持续扩大

应对策略：

• 更大的缓存
• 更好的预取
• 内存级并行
• 新型存储技术

实践应用

应用1：缓存优化编程

编写缓存友好的代码可以显著提高性能。

数据布局优化：

// 差的缓存利用
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        a[i][j] = b[i][j] + c[i][j];

// 好的缓存利用
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        a[i][j] = b[i][j] + c[i][j];

数据结构优化：

• 使用连续内存（数组而非链表）
• 数据对齐
• 结构体成员按使用频率排序

循环优化：

• 循环融合
• 循环分块
• 循环交换

应用2：性能分析工具

使用性能分析工具识别存储瓶颈。

缓存分析：

• perf stat：统计缓存缺失
• cachegrind：缓存行为分析
• VTune：内存带宽分析

关键指标：

• L1/L2/L3缺失率
• 每指令缺失数
• 内存带宽利用率

优化方向：

• 减少缓存缺失
• 提高空间局部性
• 提高时间局部性

应用3：数据库存储优化

数据库系统对存储性能要求很高。

缓冲池管理：

• 数据库自己的缓存管理
• 绕过操作系统缓存
• 直接I/O

索引优化：

• B+树索引
• 减少随机访问
• 提高顺序访问

查询优化：

• 减少数据访问
• 利用索引
• 避免全表扫描

应用4：嵌入式存储设计

嵌入式系统对存储有特殊要求。

设计考虑：

• 低功耗
• 小面积
• 实时性
• 可靠性

技术选择：

• SRAM缓存
• eDRAM
• MRAM
• 嵌入式Flash

优化策略：

• 紧密耦合内存（TCM）
• 指令和数据分离
• 内存映射I/O

本章小结

本章系统介绍了存储层次结构的设计原理和技术，主要内容包括：

存储层次基本原理：介绍了局部性原理（时间局部性和空间局部性），这是存储层次的理论基础。存储层次由寄存器、缓存、主存、辅助存储等多级组成，在速度、容量和成本之间取得平衡。

缓存设计基础：详细讲解了缓存的基本概念、映射方式（直接映射、全相联、组相联）、缺失类型（强制、容量、冲突）和替换策略（LRU、FIFO等）。缓存设计需要在性能、面积和功耗之间权衡。

高级缓存技术：讨论了多级缓存、虚拟缓存与物理缓存、缓存一致性协议（MESI）和内存一致性模型。这些技术是现代多核处理器存储系统的关键。

虚拟内存：介绍了分页机制、TLB、页面置换算法和页面错误处理。虚拟内存为每个进程提供独立的地址空间，是现代操作系统的基础。

存储系统优化：讨论了内存带宽优化、延迟优化和非易失性内存。这些技术对于突破内存墙、提高存储性能至关重要。

存储系统安全：介绍了内存保护、内存加密和侧信道防护。随着安全威胁的增加，存储安全变得越来越重要。

存储层次结构是计算机系统设计中最重要的创新之一。它巧妙地利用局部性原理，让程序员感受到既大又快的存储空间。随着处理器速度的持续提升和内存速度的相对滞后，存储层次结构的重要性将更加突出。未来的存储技术，如非易失性内存、3D堆叠存储、近存计算等，将继续推动存储系统的发展。

下一章将讨论并行处理器，这是提高计算性能的另一个重要途径。