LRU 缓存淘汰算法

每次你访问一个网站，浏览器从本地缓存中加载它，而不是从服务器重新下载——这背后有一个决策：当缓存满了，哪个页面应该被删除，为新内容腾出空间？

最近最少使用（Least Recently Used, LRU） 是这个问题最经典的答案：删除最久没有被访问的那个。

缓存替换问题#

缓存（Cache）是一个容量有限的快速存储区，存放频繁访问的数据以加速读取。缓存的效果依赖于时间局部性（Temporal Locality）——最近被访问的数据，近期再次被访问的概率更高。

缓存命中（Cache Hit）：所需数据在缓存中，直接返回。

缓存未命中（Cache Miss）：数据不在缓存中，需要从慢速存储（内存、磁盘、网络）加载，并决定替换哪个缓存条目。

主要的缓存替换策略：

Bélády 最优算法（OPT，Bélády, 1966）：每次淘汰在未来最长时间内不会被使用的页面，是页面替换的理论最优界，但需要"预知未来"，只能用于离线分析，不能用于实际系统。

栈性质：LRU 为什么没有 Bélády 异常#

Bélády 在研究替换算法时发现了一件怪事（Bélády, Nelson & Shedler，1969）：对引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，用 FIFO 替换，3 个页帧产生 9 次缺页；把页帧加到 4 个，缺页反而升到 10 次。缓存变大，性能反而变差——这被称为 Bélády 异常（Bélády's Anomaly）。

Mattson 等人（1970）找出了异常的判据：栈性质（Stack Property）。一个替换策略满足栈性质，如果对任意引用序列，容量为 $m$ 时缓存的内容永远是容量为 $m+1$ 时缓存内容的子集。满足栈性质的策略，缺页率必然随容量单调不增——异常不可能发生。

LRU 满足栈性质，论证只有一行：容量为 $k$ 的 LRU 缓存里装的，恰好是最近访问过的 $k$ 个不同页面——这个集合只随 $k$ 增长而扩张，天然嵌套。FIFO 不满足：它的留存集合取决于到达顺序而非使用历史，容量不同的两个队列内容可以互不包含。

栈性质还有一项巨大的工程红利：一次模拟算出所有容量的命中率。把访问序列按"栈距离"（本次访问距该项上次被访问之间隔着多少个不同项，即重用距离）处理一遍，容量 $k$ 的命中情况就是"栈距离 $\le k$ 的访问占比"——整条容量-命中率曲线一次扫描得到，无需对每个容量各跑一遍模拟。

LRU 的 $O(1)$ 实现#

朴素的 LRU 实现——维护访问时间列表，每次查找最久未使用的——查找时间为 $O(n)$。

经典的 $O(1)$ 实现结合了两种数据结构：

哈希表（Hash Map）：键 → 双向链表节点的指针，支持 $O(1)$ 查找。

双向链表（Doubly Linked List）：按访问时间排序，最近访问的节点在链表头部，最久未访问的在尾部，支持 $O(1)$ 移动和删除。

操作：

• Get(key)：在哈希表中找到节点，将其移动到链表头部，时间 $O(1)$
• Put(key, value)：若键存在，更新值并移到头部；若键不存在且缓存已满，删除链表尾部节点（LRU 条目），插入新节点到头部，时间 $O(1)$

这是一道著名的面试题（LeetCode 第 146 题），考查对数据结构组合的理解。

虚拟内存中的页面置换#

LRU 最重要的工业应用之一是操作系统的虚拟内存管理。

物理内存（RAM）有限，而进程的虚拟地址空间可以远大于物理内存。操作系统将内存分成固定大小的页（Page）（通常 4KB），把不常用的页换到磁盘（交换区），需要时再调回。

为什么内核不做精确 LRU：精确 LRU 要求每次内存访问都把一个链表节点移到头部——等于在最热的访存路径上额外加一次写操作（甚至加锁），硬件不允许这个开销。维护全局时间戳同理不可行。

Second Chance / Clock 的思路来自 Corbató 1968 年在 Multics 上的分页实验：把淘汰决策压缩到硬件免费提供的那一位上。MMU 在页被访问时自动把"使用位（Reference Bit）"置 1，不花操作系统任何指令。淘汰时，时钟指针循环扫描页表：使用位为 1 的页清零、跳过（"再给一次机会"）；为 0 的页淘汰。机制的直觉是：指针扫过一整圈的这段时间构成一个免费的观察窗——活跃页必在窗内被再次访问、把位置回 1；冷页的位上不来，下一轮指针到来时便束手就擒。一位信息买到的不是 LRU 本身，而是"最近一个周期内是否活跃"的粗糙近似——实践表明这个粒度足够。

页面置换算法决定当内存满时换出哪个页面：

• Linux 内核使用近似 LRU（Clock 算法）：给每个页设置一个"使用位"（Reference Bit），时钟指针循环扫描，遇到使用位为 0 的页则淘汰，使用位为 1 的则清零继续扫描
• 精确 LRU 需要维护全局时间戳或链表，开销大；近似 LRU 在实践中效果相当

LRU 的变体与改进#

LRU-K（1993）：将"最近使用"改为"最近 $K$ 次使用"的时间，避免偶发性大规模扫描（如全表扫描）污染缓存。PostgreSQL 用了类似思路。

2Q（Two-Queue）：用两个队列——新数据先进入"新生区（FIFO 队列）"，被再次访问后才进入"常驻区（LRU 链表）"，防止只访问一次的数据长时间占用缓存。

ARC（Adaptive Replacement Cache，Megiddo & Modha, 2003）：同时追踪最近使用（LRU）和最近频繁使用（LFU）的缓存历史，自适应地平衡两者，在多种访问模式下性能都优于纯 LRU。ZFS 文件系统使用 ARC。

TinyLFU / W-TinyLFU（Einziger, Friedman & Manes，2017）：换了一个提问方式——传统策略都问"该淘汰谁"，TinyLFU 问"新来者值不值得进来"。准入时用一个基于 Count-Min Sketch 的紧凑频率草图，比较新条目与候选牺牲者的历史频率：新条目更"热"才准入，否则直接拒之门外。这给缓存加了一道几乎零成本的"准入门卫"，专门拦截只访问一次的扫描流量。W-TinyLFU 再在前面挂一个很小的 LRU 窗口区吸收突发流量。Java 的 Caffeine、Go 的 Ristretto 等现代缓存库均采用这一族策略。

LIRS（Low Inter-reference Recency Set, 2002）：用"重用距离（Reuse Distance）"替代简单的时间戳，理论上更接近 OPT。

CPU 缓存中的 LRU#

CPU 有多级缓存（L1/L2/L3），也需要替换策略。硬件 LRU 用伪 LRU（Pseudo-LRU）近似实现：对于每组 $2^k$ 路组相联缓存，用 $k$ 个 bit 组成的二叉树记录每个路最近是否被使用，近似追踪 LRU 顺序。这避免了精确 LRU 需要全序排列的硬件开销。

工作集模型与局部性理论#

1968 年，彼得·丹宁（Peter Denning）提出了工作集模型（Working Set Model）：进程在时间 $[t - \Delta, t]$ 内访问过的不同页面集合称为其"工作集"。若物理内存能容纳工作集，缺页率将很低；若不能，缺页将频繁发生（"颠簸 Thrashing"）。

工作集模型为缓存替换提供了理论基础：好的替换算法应该尽量保留当前工作集中的页面。LRU 是工作集模型的一个近似实现——最近访问过的页面更可能在当前工作集中。

访问局部性的量化：实际测量发现，大多数程序的访问遵循Zipf 分布（幂律分布）：最热的 20% 内容贡献约 80% 的访问（"80-20 法则"）。这意味着缓存容量达到数据总量的 20–30% 时，命中率往往接近 80–90%，是系统设计中的重要经验参数。

数据库缓冲池的 LRU 变体#

数据库管理系统（DBMS）有自己的缓存层——缓冲池（Buffer Pool），缓存磁盘上的数据页（Page）在内存中的副本。数据库不依赖操作系统的页面缓存，而是自己管理缓冲池，因为它对访问模式有更多领域知识。

MySQL InnoDB 的 Young/Old 子列表设计：InnoDB 将 LRU 链表分成两段——"新生区（Young, 5/8 长度）"和"老化区（Old, 3/8 长度）"。新页面先进入老化区的头部；若在老化区内被再次访问，则移入新生区。这有效防止了全表扫描（顺序读入大量页面）污染新生区，因为一次性扫描的页面通常不会被再次访问。

PostgreSQL 的 Clock-Sweep 算法：类似 Linux 的 Clock 算法，为每个缓冲页维护一个"使用计数（Usage Count）"（最大值 5），每次访问加 1，Clock 指针扫描时将计数减 1，计数归零时淘汰。比纯 LRU 更宽容地对待"偶尔访问"的页面。

这两种设计体现了缓存策略的工程现实：没有放之四海皆准的最优策略，需要结合访问模式做针对性设计。

代价与争议#

顺序扫描攻击（Cache Pollution）：LRU 对全表扫描、批量预取等访问模式表现差——这些访问会把所有真正热点数据驱逐出缓存，只使用一次的"冷"数据却占满缓存。这是数据库中的经典问题，通常用 2Q/LRU-K 等变体应对。

线程安全：LRU 的双向链表需要在每次 Get 时修改（移到头部），高并发场景下锁竞争激烈。Caffeine（Java）、ristretto（Go）等现代缓存库用分段锁或异步更新策略缓解这个问题。

内存开销：每个缓存条目需要额外存储哈希表指针和链表前后指针，对缓存大量小对象的场景，开销比例较高。

跨域连接#

• 语料语言学：词频服从幂律，少数高频词覆盖大部分文本，这条经验规律最早正是在词表上被发现的。它直接决定了命中率曲线的形状：容量增加带来的命中率提升先陡后缓，达到数据总量的两三成后近乎饱和。所以扩容收益可以从访问分布的斜率预估，而不必逐档试。
• 随机过程：命中率其实由重用距离的分布唯一决定——两次访问同一项之间隔了多少个不同项。容量大于重用距离就命中，否则不命中，所以把这个分布测出来就能一次性画出容量与命中率的整条曲线，不必逐个容量跑模拟。这也解释了顺序扫描为何致命：它把所有热点的重用距离一次性推到超出容量。
• 系列位置效应：自由回忆中最近呈现的项目最易被提取，近因效应与"最近用过的更可能再被用"是同一条时间局部性假设。但人的记忆同时有首因效应与频率效应，最早出现的与最常出现的也被保住，这更接近把最近性与频率混起来的策略。缓存领域后来走的正是这条路——自适应地在两者之间调权重，比纯粹的最近性稳健。
• 神经可塑性：突触修剪同样是容量约束下的淘汰，但判据不是"最后一次被用是什么时候"，而是长期的共激活强度。这更接近按频率淘汰而非按最近性淘汰，代价也对应：频率策略对突发的新模式反应迟钝。两种策略的取舍在生物与工程里是同一道题，而混合方案在两边都被选中并非巧合。
• 存储层次与缓存：硬件缓存不实现精确的最近使用顺序，因为维护全序的电路代价太高，改用二叉树形的近似标记。这说明淘汰策略的选择常受实现层的硬约束：软件层可以用哈希表加双向链表做到常数时间，硬件层连一次链表操作都嫌贵。同一个策略在不同层级会退化成不同的近似。

参考文献#

• Bélády, L. A. A Study of Replacement Algorithms for Virtual Storage Computers. IBM Systems Journal 5(2), 78–101 (1966).
• Bélády, L. A., Nelson, R. A. & Shedler, G. S. An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine. CACM 12(6), 1969.（Bélády 异常的原始报告）
• Mattson, R. L., Gecsei, J., Slutz, D. R. & Traiger, I. L. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal 9(2), 78–117 (1970).（栈性质的原始论文）
• Corbató, F. J. A Paging Experiment with the Multics System. In In Honor of Philip M. Morse, MIT Press, 1969.（Clock/Second Chance 算法的来源）
• Megiddo, N. & Modha, D. S. ARC: A Self-Tuning, Low Overhead Replacement Cache. USENIX FAST 2003.
• Einziger, G., Friedman, R. & Manes, B. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage 13(4), 2017.
• Johnson, T. & Shasha, D. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994.

延伸阅读#

• Tanenbaum, A. S. Modern Operating Systems. 4th ed. Pearson, 2015.（第3章：内存管理）