在计算机系统中，缓存是提升性能的关键组件。无论是 CPU 的 L1/L2 缓存、操作系统的页面缓存，还是应用层的 Redis、Memcached，其核心目标都是将频繁访问的数据保留在快速存储介质中，从而降低延迟、减轻后端负载。然而，缓存空间总是有限的。当缓存写满时，必须决定哪些数据被删除，为新数据腾出空间——这就是缓存淘汰策略。
一个优秀的淘汰策略，能以最小的代价最大化缓存命中率（即用户请求的数据已在缓存中的概率）。本文将系统梳理从经典到现代的各类缓存淘汰策略，解析其原理、优缺点及适用场景，并提供一个实用的选型指南。
一、经典基础策略
这些策略是缓存淘汰的基石，它们以最直观的逻辑定义“哪些数据最不值得保留”。
1. 先进先出（FIFO, First In First Out）
原理：将缓存看作一个队列，新数据从队尾插入，淘汰时移除队首元素。它只关心数据进入缓存的时间，不关心访问频率或访问间隔。
实现：只需维护一个简单的队列。新数据入队，淘汰时出队。
优点：实现极其简单，无额外维护开销（无需记录访问时间或次数）。
缺点：无法适应程序的局部性原理——一个频繁访问的“热数据”如果因为进入较早，可能被后续的“冷数据”挤出缓存，导致命中率下降。
适用场景：数据访问模式非常均匀（无明显热点），或缓存容量远大于工作集大小，例如某些日志系统的缓存。
2. 最近最少使用（LRU, Least Recently Used）
原理：淘汰最久未被访问的数据。它基于时间局部性：如果数据最近被访问过，那么将来被访问的概率也较高。
实现：经典实现是双向链表 + 哈希表。
- 哈希表实现 O(1) 的键查找，定位链表节点。
- 链表维护访问顺序：每次访问一个数据，就将其移动到链表头部；淘汰时，移除链表尾部的节点。
优点：实现相对成熟，命中率高，能很好地捕捉短时热点。
缺点：
- 突发流量敏感：如果短时间内涌入大量新数据（如爬虫请求），这些数据会迅速占据链表头部，把原本的热点数据挤到尾部淘汰，造成缓存污染。
- 每次访问都要调整链表节点，存在一定的锁开销（尤其在并发环境下）。
适用场景：热点数据明显且访问模式相对稳定的场景，如电商商品详情页、新闻资讯网站。典型实现包括 Redis 的近似 LRU、MySQL InnoDB 缓冲池。
3. 最不经常使用（LFU, Least Frequently Used）
原理：淘汰访问次数最少的数据。它基于频率局部性：过去被频繁访问的数据，未来也可能被频繁访问。
实现：为每个数据维护一个访问计数器，新数据初始为 1，每次命中加 1。淘汰时选择计数最小的数据（若计数相同，可再按时间戳淘汰最久未访问的）。
优点：对长期热点数据非常友好，不会因为“来得晚”而被误淘汰。
缺点：
- 新数据易被淘汰：新数据的计数为 1，刚进入缓存就可能被挤出，不利于应对突发热点。
- 计数老化问题：旧数据的计数可能累积到很大，导致即使不再热门也长期占据缓存。需要引入定期衰减机制（如计数器减半）。
- 维护计数器有额外开销。
适用场景：访问频率分布稳定、数据生命周期长的场景，如统计报表、高频查询接口。Redis 的 LFU 策略使用对数计数器并带有衰减机制，解决了部分老化问题。
4. 最近最常使用（MRU, Most Recently Used）
原理：淘汰最近刚被访问的数据。这与 LRU 完全相反。
适用场景：这种反直觉的策略仅在特殊情况下有用，比如循环遍历一个大表时，刚刚访问过的记录很可能不会再立即被访问，此时 MRU 反而能提高命中率。实际应用极少。
二、经典变种策略
针对基础策略的不足，研究者提出了多种改进方案，在实现复杂度和命中率之间寻求平衡。
1. 第二次机会（Second Chance）
原理：改进 FIFO。为队列中的每个数据增加一个“引用位”（0 或 1）。当需要淘汰时：
- 检查队首数据的引用位，若为 1，则将其置 0，并移到队尾（给予第二次机会）；
- 若为 0，则直接淘汰。
优点：相比 FIFO，能避免淘汰刚被访问过的数据，实现简单。
缺点：当引用位频繁为 1 时，数据可能被多次移到队尾，导致扫描开销。
2. 时钟算法（Clock）
原理：将缓存空间组织成一个环形，每个数据有一个引用位，并有一个指针（时钟指针）指向候选淘汰位置。淘汰过程：
- 若指针指向的数据引用位为 1，则置 0，指针前移（或后移）；
- 若为 0，则淘汰该数据，指针前移。
优点：无需移动数据，效率高于 Second Chance，且能近似 LRU 的效果。
适用场景：操作系统的页面置换（如 Linux 的 Clock 算法），以及需要高性能的缓存系统。
3. LRU-K
原理：LRU 只考虑最近一次访问，而 LRU-K 考虑最近 K 次访问的时间。数据只有在被访问 K 次后才进入缓存；淘汰时，选择第 K 次访问时间最远的数据。
优点：有效抵御突发流量造成的缓存污染，因为新数据需积累 K 次访问才会被保留。通常 K=2 较常用，称为 LRU-2。
缺点：需要维护每个数据的 K 次访问历史，内存开销较大，K 值选择困难。
4. 自适应替换缓存（ARC, Adaptive Replacement Cache）
原理：动态结合 LRU 和 LFU。ARC 维护四个队列：
- T1：最近访问的 LRU 列表
- T2：频繁访问的 LFU 列表
- B1：从 T1 淘汰的数据的历史记录（仅记录元数据，无数据）
- B2：从 T2 淘汰的数据的历史记录
根据 B1 和 B2 的命中情况，自动调整 T1 和 T2 的容量比例：若近期 B1 命中多，说明最近访问模式偏向 LRU，则增大 T1 容量；反之则增大 T2 容量。
优点：自适应性强，能根据访问模式动态调整，命中率通常优于 LRU 和 LFU。
缺点：实现复杂，需要维护额外的历史队列。
适用场景：访问模式波动较大的场景，如混合了热点和冷门的 Web 应用。
三、现代高效策略
随着高并发和大数据场景的普及，缓存淘汰策略需要在命中率、性能和内存开销之间取得极致平衡。
1. Window-TinyLFU（W-TinyLFU）
原理：结合 LRU 和 LFU 的优点，使用一个小的 LRU 窗口（Window）来捕捉近期热点，并用 TinyLFU（一种紧凑的频率估计器）来长期记录数据的访问频率。
- 新数据先进入 LRU 窗口。
- 当窗口满时，触发淘汰决策：由 TinyLFU 比较窗口中的数据和缓存中已有数据的频率，决定保留高频者。
TinyLFU 使用 Count-Min Sketch 或布隆过滤器变体，以极低的内存开销近似记录频率，并引入衰减机制避免计数饱和。
优点：
- 高命中率（接近 LFU），且能快速响应突发热点（得益于 LRU 窗口）。
- 内存开销低，适合大容量缓存。
- 抗突发流量能力强。
适用场景：高并发、大数据量的缓存系统，如分布式缓存、本地堆缓存。典型代表是 Caffeine（Java 生态中最流行的本地缓存），其默认策略就是 W-TinyLFU。
2. Redis 的近似算法
Redis 作为内存数据库，需要在 O(1) 时间内完成淘汰，因此对严格的 LRU/LFU 进行了近似优化。
- 近似 LRU：Redis 不维护全局链表，而是随机采样 N 个键（默认 5 个），淘汰其中 idletime 最大的（即最久未访问）。采样数可配置，采样越多越精确，但性能略有下降。
- 近似 LFU：Redis 使用 4 位计数器（0~15）记录频率，每次访问以概率方式递增，并定期对所有计数器进行衰减（避免旧热点长存）。通过调整配置，可控制衰减速度。
优点：时间复杂度 O(1)，性能极高，适合 Redis 的单线程模型。
3. 随机淘汰（Random）
原理：当缓存满时，随机选择一个数据淘汰。
优点：实现极简，无任何额外开销。
缺点：命中率不稳定，可能淘汰重要数据。
适用场景：缓存容量极大（如 CDN 边缘节点），或对命中率不敏感的应用。
四、组合策略：过期与淘汰的协同
在实际系统中，缓存策略通常是 “过期策略 + 淘汰策略” 的组合：
- 过期策略：决定数据何时失效，一般由业务方通过 TTL（生存时间）或 TTI（空闲时间）控制。到期数据会被主动删除或惰性删除。
- 淘汰策略：当缓存空间满时，在未过期的数据中选择一部分删除。
例如：
- Redis：支持 TTL + 多种淘汰策略（volatile-lru, allkeys-lfu, volatile-random 等）。
- Memcached：默认使用 TTL + LRU（可调整）。
- Caffeine：支持基于 TTL/ TTI 的过期，淘汰策略为 W-TinyLFU。
设计注意：过期策略优先于淘汰策略，即过期数据可以提前释放空间，减轻淘汰压力。但若过期数据不及时清理，仍需淘汰机制介入。
五、策略选择指南
| 策略 | 核心逻辑 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| FIFO | 先进先出 | 极简，无开销 | 可能淘汰常用数据 | 访问均匀、大缓存 |
| LRU | 最久未访问 | 符合局部性，命中率高 | 突发流量敏感，链表开销 | 热点明显，访问稳定 |
| LFU | 访问次数最少 | 保留频繁数据 | 新数据易被淘汰，计数老化 | 频率稳定，长期热点 |
| Clock | 循环扫描+引用位 | 高效，近似LRU | 需维护引用位 | 操作系统页置换，高性能缓存 |
| ARC | 动态结合LRU/LFU | 自适应强，命中率高 | 实现复杂 | 访问模式波动大 |
| W-TinyLFU | 窗口LRU+TinyLFU | 高命中，低开销，抗突发 | 实现较复杂 | 高并发，大数据量 |
| Random | 随机淘汰 | 极简，无开销 | 命中率波动大 | 缓存极大，对命中率不敏感 |
选型建议
- 通用首选：LRU 或 LFU。多数业务场景下，两者都能良好工作。若热点短期变化快，选 LRU；若热点长期稳定，选 LFU。
- 高并发、大容量：考虑近似策略或 W-TinyLFU。Caffeine 的 W-TinyLFU 在 Java 社区广受认可；Redis 的近似 LRU/LFU 也足够高效。
- 突发流量频繁：避免纯 LRU，可选用 ARC 或 W-TinyLFU，它们能更快适应热点变化。
- 简单场景：如缓存容量远大于工作集，可选用 FIFO 甚至 Random，降低实现复杂度。
- 系统底层：操作系统或嵌入式环境，常用 Clock 或其变体，平衡性能与命中率。
最终选择还需结合业务访问模式、缓存容量、性能要求（延迟敏感度）以及维护成本综合权衡。没有万能策略，只有最适合当前场景的策略。
结语
缓存淘汰策略是性能优化的核心环节，也是计算机体系结构、操作系统、分布式系统等多个领域的交汇点。从最简单的 FIFO 到现代的自适应 W-TinyLFU，每一种策略都在特定历史条件和应用需求下诞生。理解它们背后的权衡，不仅能帮助我们更好地配置和使用现有缓存系统，也能在设计新系统时做出更明智的决策。
在实际工程中，不妨通过压测观察不同策略下的命中率和延迟，结合业务特点，选择那把最趁手的“淘汰之钥”。
