罗罗编程学习记录
本页内容 展开查看

01.5.2 存储层次与缓存一致性

所属:全栈开发面试题库 / 01 计算机基础与通用工程 / 01.5 计算机组成与体系结构

覆盖范围

  • 寄存器/L1/L2/L3/内存/磁盘层级与访问代价
  • 缓存行(cache line)、对齐与局部性原理
  • MESI 协议四态与总线事务
  • 伪共享(false sharing)成因与规避
  • 缓存对齐、填充与性能影响

高频题速览

编号 题目 难度 频率
01.5.2-001 存储层次为什么这么分 基础 ★★★★★
01.5.2-002 缓存行是什么,为什么是 64 字节 进阶 ★★★★★
01.5.2-003 时间局部性和空间局部性 基础 ★★★★☆
01.5.2-004 MESI 四个状态分别什么含义 高级 ★★★★★
01.5.2-005 伪共享是怎么产生的 高级 ★★★★★
01.5.2-006 怎么用代码规避伪共享 进阶 ★★★★☆
01.5.2-007 缓存一致性怎么保证多核看到一致内存 高级 ★★★★★
01.5.2-008 缓存对齐为什么能提性能 进阶 ★★★☆☆

01.5.2-001 存储层次为什么这么分?各层访问代价大概是多少?

一句话结论

因为 CPU 速度远超内存速度,用越小越快越贵的存储做缓存,逐级放大容量:寄存器 → L1 → L2 → L3 → 内存 → 磁盘,上层缓存下层数据,靠局部性让大多数访问落在最快的层。

概念解释

  • 寄存器:CPU 内部,周期级访问,数量极少。
  • L1 cache:每个核私有,约 1~2 周期;L2:每核私有,约 10~15 周期;L3:多核共享,约 40~60 周期。
  • 内存:约 200~300 周期(数十纳秒);磁盘:毫秒级,比内存慢约十万倍。
  • 上述数字为量级参考,具体频率与延迟随 CPU 型号变化,以本机实测为准。

原理流程

  1. CPU 访问数据先查 L1,命中即用。
  2. L1 缺失查 L2,再缺失查 L3。
  3. L3 缺失才到内存,数据按缓存行逐级回填。

代码或图示

寄存器   ──  周期级
L1       ──  ~1-2 周期
L2       ──  ~10-15 周期
L3       ──  ~40-60 周期
内存     ──  ~200-300 周期(数十纳秒)
磁盘     ──  毫秒级(比内存慢 ~10^5 倍)

常见误区

  • 以为 L3 是每个核私有:L3 通常多核共享(多 chip 架构每 chip 一片 L3,见 01.5.4 NUMA)。
  • 以为内存访问就是一次:cache miss 多级访问累加,缺失代价是数量级跳变。

追问

  • 怎么测本机延迟?答:lscpu 看 cache 大小;用 lmbench、perf c2c、或自编指针链循环测,具体数字以实测为准。
  • 为什么要 L3 共享而不是每核更大 L2?答:共享 L3 让多核间数据传递走片内,且缓存利用率更高。

01.5.2-002 缓存行是什么?为什么常见是 64 字节?

一句话结论

缓存行是 cache 与内存之间数据传输的最小单位,主流 x86 为 64 字节;即使只读一个字节,CPU 也会把整条 64 字节行加载进 cache,这是空间局部性的硬件基础。

概念解释

  • 缓存行对齐:主存与 cache 以行为单位映射,行地址 = 地址 / 64。
  • 一次传输一行:取一个字节会连带相邻 63 字节,所以顺序访问相邻数组元素几乎免费。
  • 行大小权衡:大行利于空间局部性但浪费带宽;现代 64 字节是经验折中。

原理流程

  1. 地址换算出所在缓存行号。
  2. 若该行不在 cache,从内存读整条 64 字节。
  3. 后续访问同一行任意字节都命中 cache。

代码或图示

访问 a[0](地址 0x1000)→ 加载 0x1000~0x103F 整行
之后访问 a[1]..a[15](若每元素 4 字节)全部命中

常见误区

  • 以为只读一字节只传一字节:实际传整行,跨行走访(stride 很大)会浪费行内其他字节。
  • 以为缓存行大小是软件决定的:硬件固定,软件只能按它对齐来规避问题。

追问

  • 怎么查本行大小?答:getconf LEVEL1_DCACHE_LINESIZE 或读 /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size。
  • 跨 NUMA 访问时缓存行传输有什么不同?答:跨节点内存延迟更高,见 01.5.4。

01.5.2-003 时间局部性和空间局部性分别指什么?

一句话结论

时间局部性是刚访问过的数据很快还会再访问(循环变量、栈),空间局部性是访问过地址附近的数据很快会被访问(数组顺序遍历);缓存与预取都靠这两条假设生效。

概念解释

  • 时间局部性:数据进 cache 后短期重复使用就不会 miss。
  • 空间局部性:相邻地址顺序访问,硬件预取器自动往后预取。
  • 反例:随机哈希表、跳跃式链表节点,两种局部性都差,cache miss 高。

原理流程

  1. 顺序遍历数组:预取器识别 stride,提前把后续行拉进 cache。
  2. 循环复用变量:变量留在 L1。
  3. 随机访问:预取失效,每次 miss 到内存。

代码或图示

好:for (i=0; i<n; i++) sum += a[i];   // 顺序,预取命中
差:for (i=0; i<n; i++) sum += hash_table[i];  // 随机散列

常见误区

  • 以为数组二维遍历时按列也快:按列访问 C 行主序数组 stride = 行宽,浪费行带宽,应按行遍历。
  • 以为链表比数组省 cache:链表节点分散在堆上,指针跳转破坏空间局部性,缓存局部性通常更差。

追问

  • 矩阵转置为什么要分块?答:分块(tiling)让子块留在 cache 内,减少按列访问的 miss,这是局部性优化经典手法。
  • 哈希表怎么改善局部性?答:开放寻址比链地址连续,布隆过滤器、紧凑键值(如 Abseil flat_hash_map)靠连续内存提升缓存命中。

01.5.2-004 MESI 四个状态分别什么含义?怎么保证多核缓存一致?

一句话结论

MESI 用 Modified(已改脏)、Exclusive(独占干净)、Shared(共享干净)、Invalid(无效)四个状态描述每个缓存行在各核的副本状态;核间通过总线嗅探(snoop)监听事务,任一核写前把其他核副本置 Invalid,从而保证同一时刻只有一份有效副本或唯一脏副本。

概念解释

  • Modified(M):本行在本核被修改过,与内存不一致,且只在本核存在;其他核副本必须 Invalid。
  • Exclusive(E):本行在本核干净,且只在本核缓存;可无需总线事务直接改写成 M。
  • Shared(S):本行干净,可能有多个核持有;写之前必须先把其他副本失效。
  • Invalid(I):本行无效,访问需重新从下层获取。

原理流程

  1. 某核读缺失:查总线,若其他核有干净副本则本核标 S,否则标 E。
  2. 某核要写:先发无效化事务,其他嗅探到的核把该副本置 I,本核获得 E 后改为 M。
  3. M 行被替换时写回内存(或在新架构写回式 cache 下随机制回写)。
  4. M 行被其他核读:触发干预(intervention),脏数据直接转给请求核,避免读旧内存。

代码或图示

M ──其他核读──> (脏行转给对方,双方 S)
E ──自己写──> M
S ──别人写──> I
S ──自己写──> 先广播 Invalidate,拿到 E 后改 M
I ──读缺失──> 总线决定 E 或 S

常见误区

  • 以为 Modified 状态的行会立刻写回内存:MESI 是写回(write-back)策略,脏行通常等到被替换或被窥探时才回写,不是每次写都回内存。
  • 以为只要多核各自 cache 一致就行:MESI 保证的是"缓存间一致性",不保证"内存序"——多核看到写的顺序仍需内存屏障,见 01.5.3。

追问

  • MOESI 比 MESI 多了什么?答:O(Owned)状态,允许脏行直接在核间转发而不先回内存,减少带宽,具体随架构实现,待确认。
  • 怎么观察缓存一致性流量?答:perf c2c(cache-to-cache 分析)看伪共享与行迁移,具体事件名随 perf 版本待确认。

01.5.2-005 伪共享(false sharing)是怎么产生的?

一句话结论

两个核各自频繁修改不同变量,但这两个变量落在同一条缓存行上;MESI 每次写都会把整行在两个核之间来回失效/迁移,结果本来独立的变量互相拖累,就像在共享一份数据一样,称为伪共享。

概念解释

  • 根因:缓存一致性以行为单位,行内任何字节被改,整行都要做 MESI 事务。
  • 典型场景:数组相邻元素被多线程分别写、计数器相邻放在结构体里。
  • 症状:多核并行反而比单核慢,CPU 大量时间耗在缓存行迁移与一致性流量上。

原理流程

  1. 核 A 修改变量 a(与 b 同行),该行变 M@A,核 B 的副本被置 I。
  2. 核 B 修改 b(同行),需先把 A 的 M 行拉过来,A 的副本变 I。
  3. 来回乒乓,每写一次都触发一次跨核一致性事务。

代码或图示

缓存行 [a | b | .....]
线程 A 写 a ── 行变 M@A,B 的行失效
线程 B 写 b ── 拉行到 B,A 的行失效
结果:a、b 逻辑独立,物理上却反复乒乓

常见误区

  • 以为只要两个变量不共享锁就不会互相影响:它们虽然逻辑独立,物理上同处一行就会触发伪共享。
  • 以为 L3 共享就不会伪共享:L3 是共享干净副本,但核间 L1/L2 仍私有且走 MESI,伪共享照样发生。

追问

  • 怎么定位伪共享?答:perf c2c 报告行在哪些核之间反复迁移;或实验单核 vs 多核并行时间对比,多核反而慢即高度怀疑。
  • 伪共享和真共享怎么区分?答:真共享是多线程确实读写同一变量;伪共享是读写不同变量但同处一行,性能特征类似但代码逻辑无依赖。

01.5.2-006 怎么用代码规避伪共享?

一句话结论

把高频独立变量用缓存行填充(padding)隔开,让它们落在不同缓存行;现代语言提供 alignas/缓存行填充注解,把每线程独立计数放在对齐到 64 字节的结构里。

概念解释

  • 填充:在变量后加占位字节,凑满 64 字节,避免下一个变量挤进同一行。
  • 每线程数据(per-thread):把统计计数器设计为线程本地,避免跨核共享行。
  • 语言支持:C11 alignas(64),Java @Contended(需 JVM 参数开启,具体随版本待确认),Go 标准库内部用 padding。

原理流程

  1. 定义每个计数器结构对齐到 64 字节并填充。
  2. 线程 A 的计数独占一行,线程 B 的计数独占另一行。
  3. 各自写不触发对方行失效。

代码或图示

struct Counter {
    alignas(64) long value;
    char pad[64 - sizeof(long)];  /* 填满整行 */
};
struct Counter cnt[THREAD_N];

常见误区

  • 以为加几个字节 padding 就够:要凑满整行(64 字节)且起始对齐到行边界,否则仍可能跨边界。
  • 以为 padding 越多越好:过度填充浪费内存,只对高频热变量做,冷变量不必。

追问

  • Java 的 @Contended 默认生效吗?答:需要 JVM 启动参数(如 -XX:-RestrictContended 或相关选项,具体随版本待确认),否则内部注解被限制。
  • 除了 padding 还有什么办法?答:线程本地计数最后归并(sharded counter),写时只动本地分片,读时求和,从根上避免共享。

01.5.2-007 缓存一致性怎么保证多核看到一致的内存?

一句话结论

靠硬件一致性协议(MESI 家族)在核间做嗅探与总线事务,让每个缓存行在任意时刻只有一个有效状态;软件层面还需配合内存屏障,才能约定多核看到写操作的先后顺序(缓存一致性 ≠ 内存序)。

概念解释

  • 硬件层:MESI 保证副本不会同时出现两份脏数据。
  • 软件层:即使副本一致,各核对不同地址写的观察顺序仍可能不同,需要 acquire/release 屏障,见 01.5.3。
  • 关键区分:一致性(coherence)保证同一地址的副本一致;内存序(memory ordering)约定多地址操作的全局可见顺序。

原理流程

  1. 读:命中私有副本即用;缺失按 MESI 流程获取。
  2. 写:先发失效事务独占该行。
  3. 跨核可见性:写结果先在发起核变 M,其他核下次读该行时拿到最新值。

代码或图示

一致性(coherence):同一地址,多核最终看到同一份值
内存序(ordering):a=1 先于 b=1 对其他核可见?
                   这是 MESI 不管的,需屏障

常见误区

  • 以为 MESI 保证 a=1 对核 B 可见后 b=1 也一定可见:不保证,可能乱序,需要 release/acquire 配对。
  • 以为一致性协议就是内存屏障:屏障是软件控制重排与可见性顺序,MESI 是硬件副本一致性,二者协同。

追问

  • x86 是强内存模型吗?答:x86(TSO)对loads-after-loads、stores-after-loads 等有较强保证,常见重排较少;弱内存模型(ARM)更需要显式屏障,见 01.5.3。
  • 无锁队列正确性靠什么?答:MESI 保证副本一致 + 内存序保证关键写的顺序 + CAS 原子性,三者缺一不可。

01.5.2-008 缓存对齐为什么能提性能?

一句话结论

让数据结构起始地址对齐到缓存行(或更大边界),避免一个结构跨两行边界——跨边界的访问需要拆成两次 cache 行操作,还会干扰相邻结构的独占性;对齐后单次访问即可命中一行。

概念解释

  • 自然对齐:变量地址是其大小的整数倍(4 字节 int 对齐 4,8 字节 long 对齐 8)。
  • 缓存行对齐:关键结构起始对齐到 64 字节,避免跨行。
  • 大页对齐:配合大页(见 01.5.4)减少 TLB miss。

原理流程

  1. 对齐分配:分配器按 64 字节边界返回地址。
  2. 结构完全落在一行内,访问一次取整。
  3. 相邻结构不被同一行切碎,减少相互干扰。

代码或图示

未对齐:[结构尾 | 下一结构头] 跨在两行边界
       访问下一结构要触两行
对齐:  每个结构独占一段 64 字节边界

常见误区

  • 以为对齐只是编译器的事:关键热数据要显式 alignas 或专用分配器,默认分配未必按行对齐。
  • 以为对齐越大越好:过度对齐浪费内存,只对高频热路径做。

追问

  • 结构体填充(padding)和对齐关系?答:对齐解决起始位置,padding 解决结构间是否同处一行,二者常配合使用规避伪共享。
  • malloc 返回地址对齐多少?答:通常 16 字节(glibc),不是 64 字节;需要行对齐用 aligned_alloc/posix_memalign,具体以本机 man 为准。

01.5.2-009 缓存行对齐和伪共享怎么在代码里验证?

一句话结论

写两个版本的计数器:一个无 padding 让多核写相邻变量,一个用 64 字节 padding 隔开;在多核并行写时对比吞吐,无 padding 版本因伪共享显著慢于 padding 版本,即可验证。

概念解释

  • 验证方法:A/B 对比测试。
  • 无 padding:多变量同处一行,MESI 乒乓。
  • 有 padding:每变量独占一行。

原理流程

  1. 版本 A:多线程写相邻 long 变量。
  2. 版本 B:每个 long 后补 64 字节。
  3. 多核并行跑,对比吞吐。

代码或图示

// 版本 A(伪共享)
long cnt[8];
// 版本 B(填充)
struct { long v; char pad[64-sizeof(long)]; } cnt[8];

常见误区

  • 单线程测不出伪共享:必须多核并行写才暴露。
  • 只看单次延迟:要看吞吐趋势,伪共享在高并发下才明显。

追问

  • 怎么用 perf 观察?答:perf c2c 报告缓存行在核间迁移次数,具体事件名随 perf 版本待确认。
  • 伪共享和缓存对齐的关系?答:对齐解决起始位置,padding 解决变量间隔离,二者配合。

待整理清单

  • [ ] MOESI 与现代 x86/ARM 一致性协议细节
  • [ ] perf c2c 实操命令与报告解读
  • [ ] 非一致缓存(NUCA)与片上互连
  • [ ] 预取指令(PREFETCHT0/T1/T2)软件实践