1966年，IBM研究员Laszlo Belady发表了一篇题为《A Study of Replacement Algorithms for a Virtual-Storage Computer》的论文。这篇论文提出了一个看似简单的问题：当缓存空间有限时，应该淘汰哪个数据？

Belady给出的答案是：淘汰那个在未来最久不会被访问的数据。这个算法被称为Belady最优算法或MIN算法，它在理论上达到了缓存命中率的极限——没有任何算法能比它做得更好。

问题在于，Belady最优算法需要预知未来。在实际系统中，我们无法知道下一个请求会访问什么数据。于是，过去六十年里，计算机科学家们一直在回答一个更具挑战性的问题：在没有预知未来的情况下，如何做出接近最优的淘汰决策？

这个问题的答案，构成了现代计算基础设施的隐形基石。从CPU的L1缓存到CDN边缘节点，从数据库缓冲池到浏览器本地存储，缓存淘汰算法无处不在。

一个反直觉的现象：更多内存反而更慢

在讨论算法之前，先看一个让初学者困惑的现象。

1969年，研究人员在使用FIFO（先进先出）页面置换算法时发现了一个奇怪的现象：增加物理内存的页面帧数量，缺页次数反而增加了。这被称为Belady异常（Belady’s Anomaly）。

考虑这样一个页面访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

当缓存容量为3帧时，FIFO算法产生9次缺页。但当缓存容量增加到4帧时，缺页次数反而变成了10次。

这违反直觉的原因在于：FIFO算法只关心数据进入缓存的顺序，完全不考虑数据的访问频率或最近访问时间。增加缓存空间可能改变数据的淘汰顺序，导致频繁访问的数据被更早淘汰。

这个现象揭示了一个深刻的问题：缓存大小和缓存效率之间没有简单的线性关系。选择错误的淘汰算法，增加硬件投入反而可能适得其反。

理论的天花板：Belady最优与竞争比

Belady最优算法虽然是不可实现的（它需要预知未来），但它提供了一个重要的理论基准：任何缓存淘汰算法的命中率上限。

1985年，Daniel Sleator和Robert Tarjan在《Amortized Efficiency of List Update and Paging Rules》论文中引入了竞争比（Competitive Ratio）的概念，用来衡量在线算法（无法预知未来）相对于离线最优算法的性能。

竞争比定义为：

$$\text{Competitive Ratio} = \max_{\sigma} \frac{\text{Cost}_{\text{online}}(\sigma)}{\text{Cost}_{\text{optimal}}(\sigma)}$$

其中$\sigma$是任意访问序列，Cost是算法在该序列上的代价（如缺页次数）。

Sleator和Tarjan证明了一个关键结果：LRU（Least Recently Used，最近最少使用）算法的竞争比是k，其中k是缓存容量。这意味着在最坏情况下，LRU的缺页次数最多是最优算法的k倍。

更重要的是，他们证明了任何确定性在线算法的竞争比都不可能低于k。换句话说，在竞争比的意义上，LRU已经达到了理论上的最优。

但这并不意味着LRU在实践中是最好的。竞争比分析的是最坏情况，而实际工作负载通常有更好的局部性。这也解释了为什么后来出现了那么多"比LRU更好"的算法——它们在特定场景下更聪明地利用了访问模式的特征。

LRU的致命缺陷：当历史不能预测未来

LRU的核心思想是：最近被访问过的数据，将来被访问的可能性更高。这个假设在大多数情况下成立，但有几个著名的失败场景。

扫描污染

当一个程序顺序扫描一个大文件时，LRU会将所有扫描过的数据都标记为"最近使用"。如果文件大小远超缓存容量，扫描结束后缓存中留下的都是刚刚扫描过但再也不会访问的数据。这些"一次性数据"污染了缓存，把原本有用的热点数据挤出去了。

这就是扫描污染（Scan Pollution）问题。对于数据库的全表扫描、日志分析等场景，LRU的表现可能灾难性地差。

频率陷阱

假设缓存容量为3，访问序列是：A, A, A, B, C, D, A

LRU会在访问D时淘汰A（因为B和C更"新"），但A的访问频率明显更高。在访问频率和访问时间之间存在显著差异的场景下，纯粹的LRU会做出错误的判断。

实现代价

真正的LRU需要在每次访问时更新数据的位置，这在高并发场景下会带来显著的锁竞争。Redis的创始人Salvatore Sanfilippo曾在博客中解释为什么Redis使用近似LRU而非精确LRU：“真正的LRU在每次访问时都需要更新链表，这在多线程环境下会成为严重的瓶颈。”

这些缺陷催生了LRU的众多变体。

算法的进化：从LRU到自适应策略

LRU-K：给"最近"一个阈值

1993年，Elizabeth O’Neil、Patrick O’Neil和Gerhard Weikum在SIGMOD上发表了《The LRU-K Page Replacement Algorithm for Database Disk Buffering》。

LRU-K的核心思想是：不要只看最后一次访问时间，而要看最近K次访问的时间间隔。一个数据如果最近K次访问的时间间隔很短，说明它是高频热点；如果间隔很长，即使最近被访问过，也可能是"一次性数据"。

LRU-2（K=2）是最常用的变体。它淘汰的是"第二次最近访问时间"最久远的数据。2010年的一项研究证明，LRU-2的竞争比是2k，比LRU的k要差，但在实际数据库工作负载中表现更好——这再次说明竞争比不是唯一的衡量标准。

2Q：两个队列的智慧

1994年，Theodore Johnson和Dennis Shasha在VLDB上提出了2Q算法。

2Q维护两个队列：A1队列存储只被访问过一次的数据（可能是扫描数据），Am队列存储被访问过多次的数据（真正的热点）。新数据先进入A1，只有再次被访问才会进入Am。淘汰时优先从A1队列淘汰。

这个设计天然解决了扫描污染问题：顺序扫描的数据只会停留在A1队列，不会污染Am队列中的热点数据。

LIRS：用IRR度量热度

2002年，Song Jiang和Xiaodong Zhang在SIGMETRICS上发表了LIRS（Low Inter-reference Recency Set）算法。

LIRS引入了**IRR（Inter-Reference Recency，引用间距离）**的概念。IRR是指同一个数据两次访问之间的时间间隔（以其他数据的访问次数来衡量）。

LIRS的核心洞察是：IRR比单纯的"最近访问时间"更能准确预测未来行为。一个数据的IRR很小，说明它被频繁访问；IRR很大，说明它可能是一次性数据。

LIRS将缓存中的数据分为两类：LIR（Low IRR）块和HIR（High IRR）块。LIR块是稳定的常驻数据，HIR块是可能被淘汰的候选者。这种设计使LIRS能够同时处理高频热点和扫描数据。

ARC：自适应的艺术

2003年，IBM Almaden研究中心的Nimrod Megiddo和Dharmendra Modha提出了ARC（Adaptive Replacement Cache）算法，发表在USENIX FAST会议上。

ARC的设计哲学是：不要猜测工作负载是重频率还是重时间局部性，而是自适应地平衡两者。

ARC维护四个数据结构：

  • T1：最近访问过一次的数据（实际缓存）
  • T2：最近访问过多次的数据（实际缓存）
  • B1：最近从T1淘汰的数据（影子缓存）
  • B2：最近从T2淘汰的数据（影子缓存）

关键创新在于动态调整T1和T2的大小比例。当B1中有命中时，说明最近淘汰的数据本应该留在T1，于是增大T1的配额；当B2中有命中时，说明最近淘汰的数据本应该留在T2，于是增大T2的配额。

这种设计使ARC能够自动适应工作负载的变化。在频率为主的场景下，T2会自动扩大；在时间局部性为主的场景下，T1会自动扩大。

ARC的空间开销很低——只有0.75%的缓存大小用于维护影子缓存。但它的实现复杂度比LRU高，需要维护四个队列和自适应参数。

现代的创新：更简单反而更有效？

2024年4月，NSDI会议上发表了一篇出人意料的论文：《SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches》。

这篇论文提出了SIEVE算法，它的核心思想简单到令人难以置信：让"被保留"的数据留在原位置，而不是移动到队列头部。

SIEVE的工作原理

SIEVE只需要一个FIFO队列和一个"手"指针。队列中的每个对象有一个visited标志位。

  • 缓存命中：将visited标志位设为1
  • 缓存淘汰：手指针从队列尾部向头部移动，遇到的第一个visited=0的对象被淘汰；如果遇到visited=1的对象，将其标志位重置为0并跳过（不移动位置）

这与传统的CLOCK算法（也称为Second Chance）非常相似。关键区别在于：CLOCK算法会将visited=1的对象移动到队列头部，而SIEVE让它留在原位置。

这个看似微小的改动产生了惊人的效果。在1559条生产环境缓存访问轨迹的测试中，SIEVE比ARC减少了高达63.2%的失效率。在超过45%的轨迹上，SIEVE的表现优于所有其他算法。

为什么SIEVE有效？

论文给出了理论分析。关键在于两个机制的协同：

懒提升（Lazy Promotion）：只有到了淘汰时刻才检查visited标志。这避免了每次访问都更新数据结构的高昂开销。

快淘汰（Quick Demotion）：新插入的对象总是位于队列头部，而手指针最终会扫过它们。如果新对象不被再次访问，很快就会被淘汰。

SIEVE的设计使得"幸存"的老对象和"新生"的新对象在队列中自然分开：老对象聚集在尾部，新对象聚集在头部。手指针在两者之间穿梭，形成一个自适应的过滤器。

SIEVE的实现极其简单——在五个生产级缓存库中平均只需要修改20行代码。它的吞吐量是优化后的LRU的两倍（16线程场景），因为缓存命中时不需要获取锁。

但SIEVE有一个明显的弱点：它不具备扫描抵抗能力。在存在大量顺序扫描的工作负载下，SIEVE的表现可能不如LRU。论文作者也承认，SIEVE主要针对Web缓存场景设计，这类场景很少有大规模顺序扫描。

工程实践的智慧

理论归理论，工业界的实际选择往往更加务实。让我们看看几个知名系统是如何处理缓存淘汰的。

Redis：近似是美德

Redis支持多种淘汰策略，但它的LRU实现是近似的。原因在于：真正的LRU需要在每次访问时更新链表，这在高并发下会带来严重的锁竞争。

Redis的做法是为每个key维护一个最后访问时间戳（精度为毫秒级）。当需要淘汰时，Redis随机采样N个key（N可通过maxmemory-samples配置），从中选择最久未被访问的那个。

2016年，Redis的创始人Sanfilippo在博客中解释：“经过我的测试，这个近似LRU算法的性能损失不到1%，但在64位系统上每个key只需要额外16字节。如果实现真正的LRU，性能损失会大得多。”

从Redis 4.0开始，还支持LFU模式。LFU使用Morris Counter来近似计数，每个key只需要3-4字节来存储访问频率。

MySQL InnoDB：中点插入策略

MySQL InnoDB的Buffer Pool使用一种改进的LRU算法。关键创新是中点插入策略（Midpoint Insertion Strategy）。

Buffer Pool的LRU链表被分为两部分：

  • 新生代（New Sublist）：占约5/8的空间
  • 老年代（Old Sublist）：占约3/8的空间

新读取的数据不是插入到链表头部，而是插入到老年代的头部（即新生代和老年代的交界处）。只有当数据在老年代被再次访问时，才会被提升到新生代。

这个设计天然抵抗扫描污染：顺序扫描的数据会快速进入老年代，然后快速被淘汰，不会污染新生代中的热点数据。InnoDB的innodb_old_blocks_time参数控制一个数据在老年代必须停留多久才能被提升，进一步防止扫描污染。

Linux内核：从Clock到Clock-Pro

Linux内核的页面置换算法经历了漫长的演进。早期使用的是Clock算法（也称为Second Chance），这是LRU的低成本近似。

2017年，Linux内核开始引入Clock-Pro的思想。Clock-Pro是LIRS算法在Clock框架下的实现，它使用三个"时钟手"来近似测量数据的重用距离，能够快速淘汰一次性访问或低局部性的数据。

内核开发者的选择体现了工程权衡：Clock-Pro比真正的LIRS实现简单得多，但保留了LIRS的大部分优点。

Caffeine：W-TinyLFU的实践

Caffeine是Java生态中最流行的高性能缓存库之一，它使用W-TinyLFU算法。

W-TinyLFU结合了两个思想：

  • TinyLFU：使用布隆过滤器变体高效地追踪访问频率，作为准入策略
  • Window：维护一个小型的窗口缓存，让新数据有机会证明自己的价值

W-TinyLFU的空间开销很低：每个缓存条目只需要8字节的元数据。这比ARC（17字节）和LIRS（17字节）都要低，更不用说LeCaR等机器学习方法（40-54字节）。

机器学习的入侵

2017年的Cache Replacement Championship冠军是Hawkeye算法。它使用机器学习来预测每条指令产生的内存访问是否会"缓存友好"。

Hawkeye的核心思想是：用历史行为预测未来。它采样一部分缓存集合，在这些集合上模拟Belady最优算法，记录每条指令的行为，然后用这些数据训练一个预测器。

2020年，MIT的研究者在ICML上发表了《An Imitation Learning Approach for Cache Replacement》，提出了使用模仿学习来训练缓存淘汰策略。核心洞察是：Belady最优算法的行为可以被学习。

2024年的研究综述显示，机器学习增强的缓存算法在单核设置下比LRU减少了8.9%的失效率。但代价是显著的：需要更多的元数据存储（每个条目可能需要40-50字节），以及训练和推理的计算开销。

更复杂不一定更好。在缓存场景下，简单、快速、低开销往往比极致的命中率更重要。

没有银弹：场景决定选择

经过六十年的发展，缓存淘汰算法已经形成了一个丰富的工具箱。但没有任何算法在所有场景下都是最优的——每种算法都有自己的假设和权衡。

CPU缓存：使用PLRU（伪LRU）或SRRIP等简单策略，因为硬件实现代价和访问延迟是首要考虑。每个缓存行只有几位元数据空间。

数据库缓冲池：倾向于使用LIRS或其近似（如InnoDB的改进LRU），因为需要同时处理事务处理（高频随机访问）和分析查询（大范围扫描）。

Web缓存/CDN：SIEVE或LFU变种更合适，因为访问模式通常遵循Zipf分布，少数热门对象占据大部分请求。

键值存储：TinyLFU或近似LRU是常见选择，需要在高吞吐和好命中率之间平衡。

浏览器缓存：简单的LRU或FIFO足够，因为缓存容量相对较小，且访问模式相对可预测。

一个有趣的观察是：算法复杂度与实际采用率之间往往存在负相关。LIRS、ARC、MQ等"高级"算法很少在生产系统中使用，而LRU、CLOCK、近似LRU等"简单"算法占据主导地位。

这背后的原因是多方面的：

  • 简单算法更容易调试和验证
  • 简单算法的元数据开销更低
  • 简单算法更容易在多线程环境下扩展
  • 简单算法的行为更容易预测

2016年的一项研究表明，即使是精心设计的复杂算法，在真实工作负载上的表现也可能与预期大相径庭。某些算法甚至会遇到Belady异常——增加缓存反而降低命中率。

从数学到工程

回顾六十年的缓存淘汰算法研究，可以看到一条清晰的主线：从理论最优到工程可行，从单一策略到自适应平衡，从完美主义到实用主义。

Belady最优算法告诉我们理论上限在哪里。Sleator和Tarjan的竞争比分析告诉我们在没有未来信息的情况下能做到多好。LRU及其变体展示了如何利用局部性原理。LIRS、ARC等算法展示了如何更精细地区分数据的"热度"。SIEVE则提醒我们：有时候最简单的改动可能是最有效的。

这些算法有一个共同点：它们都在回答同一个问题——当空间有限时，应该留下什么。

这个问题不仅存在于计算机系统中。人类的大脑也在不断"淘汰"记忆，保留重要的，遗忘琐碎的。图书馆需要决定哪些书留在书架上，哪些放入仓库。博物馆需要决定哪些展品值得展出。

缓存淘汰算法的智慧，某种程度上是普适的：历史是预测未来的最佳依据，但不是唯一依据；简单往往比复杂更可靠；没有放之四海而皆准的策略，只有适合特定场景的权衡。

下一次当你看到"缓存命中率"这个指标时，不妨想一想：在这个数字背后，是一个经过几十年演进的算法，在有限的空间里做出无数次艰难的取舍。

参考文献

  1. Belady, L. A. (1966). A Study of Replacement Algorithms for a Virtual-Storage Computer. IBM Systems Journal, 5(2), 78-101.

  2. Sleator, D. D., & Tarjan, R. E. (1985). Amortized Efficiency of List Update and Paging Rules. Communications of the ACM, 28(2), 202-208.

  3. O’Neil, E. J., O’Neil, P. E., & Weikum, G. (1993). The LRU-K Page Replacement Algorithm for Database Disk Buffering. ACM SIGMOD Record, 22(2), 297-306.

  4. Johnson, T., & Shasha, D. (1994). 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB, 439-450.

  5. Jiang, S., & Zhang, X. (2002). LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy. ACM SIGMETRICS Performance Evaluation Review, 30(1), 31-42.

  6. Megiddo, N., & Modha, D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache. USENIX FAST.

  7. Einziger, G., Friedman, R., & Manes, B. (2017). TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage, 13(4), 1-31.

  8. Zhang, Y., Yang, J., Yue, Y., Vigfusson, Y., & Rashmi, K. V. (2024). SIEVE is Simpler than LRU: An Efficient Turn-Key Eviction Algorithm for Web Caches. USENIX NSDI.

  9. Jiang, S., Chen, F., & Zhang, X. (2005). CLOCK-Pro: An Effective Improvement of the CLOCK Replacement. USENIX ATC.

  10. Liu, E., Hashemi, M., Swersky, K., Ranganathan, P., & Ahn, J. (2020). An Imitation Learning Approach for Cache Replacement. ICML.

  11. Jaleel, A., Theobald, K. B., Steely, S. C., & Emer, J. (2010). High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP). ISCA.

  12. Denning, P. J. (1968). The Working Set Model for Program Behavior. Communications of the ACM, 11(5), 323-333.