局部性原理——从哪来、为什么、有什么用

面试官问：为什么 Redis 查一次很快，而同样的数据放远程 MySQL 上要慢几十倍？为什么数组遍历比链表快，明明两者都是"一个接一个读"？为什么 CPU 造了三级缓存，却无论如何不肯做大一点？—— 答案都指向同一条规律：局部性原理。

0. 钩子：一个几乎不可能的缓存

假设没有局部性原理，会发生一件很滑稽的事：CPU 花了几百亿造的 L1 Cache 几乎没有命中，命中率趋近于 0，缓存白装。为什么？因为缓存能起作用，靠的是"你读写过的数据，大概率很快还会再读写"——如果每次访问都落在完完全全随机的新位置，那缓存里存的旧东西永远派不上用场，装缓存等于没装。可现实是，几乎所有真实程序都有强局部性，所以缓存这条产业链才成立。局部性不是假设出来的，它是真实工作负载的结构性特征，缓存只是顺着这个特征搭的脚手架。

1. 它从哪来：Peter Denning 与工作集模型

1965 到 1968 年，虚拟内存（分页）刚铺开不久，系统遇到一个棘手问题：程序一多、内存一紧张，页面就在内存和磁盘之间疯狂换入换出，系统陷入"颠簸（thrashing）"，吞吐跌到谷底。当时人们不知道为什么，只能用"内存不够就加内存"这种笨办法硬扛。

1968 年，科学计算的学者 Peter J. Denning 在研究分页调度时，提出了局部性原理（Principle of Locality），并明确提出两个分支：

时间局部性（Temporal Locality）：最近访问过的数据，很快还会再次访问；
空间局部性（Spatial Locality）：访问过某地址，它附近的地址往往也马上会被访问。

他基于此提出**工作集（Working Set）**模型——一个进程在近窗口内活跃访问的页集合。只要物理内存能装下工作集，颠簸就消失；装不下（工作集超内存），就必然颠簸。这解释了"内存加到工作集大小"的真正含义，也让分页器的设计第一次有了理论依据。

2. 为什么需要它：没有它，这条存储链直接塌掉

计算机的存储是不连续的：寄存器、L1/L2/L3、内存、SSD、磁盘，每一层容量差几个数量级、成本差几个数量级。之所以能把这些"快而贵、慢而便宜"的介质拼成一台机器，全都押在局部性这一个假设上——快层命中率越高，整体等效性能就越接近最快的谁那一层。

反过来推，没有局部性会怎样：

命中率崩掉：访问完全随机时，任何缓存容量都约等于 0 命中，性能被最慢层主导，分层存储形同虚设；
没有它就没有"预取"：空间局部性是预取（prefetch）的理由——提前把"旁边的数据"搬上来。没有它，等用到时再去缺页，每次都撞上最高的时延；
没有它就没有 LRU/倒排设计：Redis 的 LRU 淘汰、操作系统的页面替换，全都建立在"最近用过的更可能再用"之上。抽走局部性，它们瞬间失去依据。
代价是颠簸：Denning 最重要的洞察是，局部性一旦超出内存能装的工作集，就不是"慢一点"，而是系统性崩溃式的减速。

3. 本质一句话

局部性原理的本质是：最近用过的，很快还会再用；用到的地方旁边的，往往也要用——程序的行为不是随机漫步，而是围绕一小簇热点打转。

这句话是整篇的钥匙：它同时解释了分层存储能省钱的道理，也解释了为什么"命中率"是缓存的最重要指标，更解释了为什么那些号称"随机访问"的负载（如大规模哈希、转置矩阵）总是难优化。

4. 它有什么用：从 CPU 到 Redis、MySQL、编译器

局部性不是学术名词，它写进了每一层的工程设计里。下面挑四个真实落点，尽量带代码或命令。

① CPU 缓存 + 编译器：数组比链表快，不是玄学

下面两段是无视空间局部性的典型对比。C 里二维数组默认行优先存储，所以逐行遍历（a[i][j]）命中率高，逐列遍历（a[j][i]）每步都跨到别的行，缓存 miss 暴增：

#define N 1024
int a[N][N];
long sum_row(void) {          /* 空间局部性好：一次拷进缓存的行反复用 */
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) s += a[i][j];
    return s;
}
long sum_col(void) {          /* 空间局部性差：每次都踩到缺的新行 */
    long s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++) s += a[i][j];
    return s;
}

用 perf 量化差距（命中率从接近 1 掉到很低的量级）：

1	perf stat -e cache-references,cache-misses ./prog

编译器也沿着局部性做优化：**循环展开（loop unrolling）**减少分支、让同一块数据进行复用；数据对齐与布局改写（如结构体按缓存行 padding、把热字段放一起）都是在有意制造空间局部性。

② Redis：缓存本身就是时间局部性的生意

Redis 的值常驻内存，命中靠的就是热点集中。最直接的证据是它的 LRU 淘汰：内存不富余时，把"最久没被用"的 key 淘汰，留下"最近用过"的——这正是「时间局部性」的字面运用。再看结构层面，ziplist、intset 等紧凑编码把一连串小元素压在一小段连续内存里，本质是在制造空间局部性，让一次取缓存行读到尽可能多的有用数据。

一条命令能测出热点是否真的集中（时间局部性的宏观表现）：

1 2	redis-cli --latency-history # 也常用 redis-cli INFO keyspace_hits / keyspace_misses 看命中率

③ MySQL：索引与预读都是空间局部性

InnoDB 的索引是 B+ 树，底层数据页 16KB 按页组织，顺序读一个页内多条记录就是空间局部性。更典型的是预读（read-ahead）：MySQL 发现你在顺序扫表，就预测你接下来还要读相邻页，提前把它从磁盘搬进缓冲池——预读若不是赌空间局部性，就是纯浪费 IO。

1 2	-- 强制走索引顺序扫，展示 MySQL 按页顺序批量读 EXPLAIN SELECT * FROM t WHERE user_id > 100 ORDER BY user_id;

④ 操作系统：预取与工作集调度

分页器用「按页+预取」赌空间局部性，用「LRU 类策略」赌时间局部性；调度器则按 Denning 的工作集模型给进程分配足够的物理页，避免工作集超内存导致颠簸（vmstat 里 si/so 持续偏高就是颠簸的信号）。

5. 反例与边界：什么时候它不成立、什么时候它被滥用

局部性再强，也有两条清晰的边界：

随机型负载根本不适用：大规模哈希表扫描、矩阵转置（a[j][i]）、全表随机抽样，访问近乎随机，空间局部性瓦解，此时任何"加缓存/预取"都白费力气——优化方向应该转向算法本身，而不是赌缓存。
工作集超容量就撞墙：局部性保证的是"热点小"，不是"热点无限大"。当进程工作集 > 缓存/内存容量，命中率开始塌方，CPU 里叫 cache 颠簸，OS 里叫内存颠簸（thrashing），性能不是线性下降而是悬崖式暴跌。这是 Denning 当年想根治的坑。
被过度使用的代价：为了把数据"贴得近、复用多"，多核系统会拼命把热点数据往同一份共享缓存里塞，结果就是**缓存一致性协议（MESI）**在核间疯狂发失效消息，伪共享（false sharing）反过来拖垮性能。也就是说，局部性太强也会伤人——"热点"集中与"多核并行"是一对需要平衡的矛盾。

6. 对比表 + 条目小结

维度	时间局部性	空间局部性
含义	最近用过的还会再用	用到的旁边也要用
典型负载	循环、热点 key、函数调用	数组顺序遍历、顺序读、代码段
落地机制	LRU 缓存、工作集、内存驻留	按页取、预读 readahead、缓冲池
失效场景	工作集超容量 → 颠簸	随机访问 / 列优先遍历
在 Redis	热 key 命中、LRU 淘汰	ziplist/intset 紧凑连续存储
在 MySQL	缓冲池留热页	索引顺序读、16KB 按页预读
在 CPU/编译器	循环复用、循环展开	对齐与布局改写、perf 测命中

这条原则带走的几句话 🐾

程序行为不是随机漫步，而是围绕一小簇热点打转；一切缓存、层次存储、预取都是顺着这个特征搭的。
看一个系统快不快，先问一句："它的命中率在设计上能被局部性支撑住吗？"
遇到"随机访问"型负载，别再执着于调缓存——算法和数据布局才是着力点；而遇到"多核共享热点"，则要警惕伪共享的反噬。

相关阅读

空间换时间 / 哈希与索引（同一主题池的后续条目，与局部性互为表里）