1. 缓存淘汰策略到底在解决什么问题做本地缓存的人迟早会撞上一个绕不开的问题内存是有限的但你要塞进去的数据是无限的。不管是给接口做一层热点数据缓存还是给图片、配置、计算结果做临时存储只要容量到了上限就必须决定“扔掉谁”。这个“扔掉谁”的规则就是缓存淘汰策略。很多人第一次写本地缓存用的都是最朴素的做法一个哈希表加一个计数器满了就清空重来或者随机删几个。这种方案在数据量小、访问模式均匀的时候勉强能用但只要访问有明显的冷热区分命中率就会崩得一塌糊涂。我见过一个场景某服务把配置项缓存在本地容量设了 500结果每次批量刷新配置时直接把整个缓存清空导致后面几分钟内所有请求都穿透到下游下游压力瞬间翻了好几倍。这就是典型的“没有淘汰策略”的代价。LIFO、FIFO、LRU、LFU 这四种是本地缓存里最基础也最常被拿来对比的淘汰策略。它们各自对应一种对“谁该被淘汰”的假设FIFOFirst In First Out先进先出最早进来的最早被淘汰。假设是“老数据价值低”。LIFOLast In First Out后进先出最后进来的最先被淘汰。假设是“新数据可能是临时写入的用完就该走”。LRULeast Recently Used最近最少使用最久没被访问的优先淘汰。假设是“最近用过的接下来大概率还会用”。LFULeast Frequently Used最不经常使用访问次数最少的优先淘汰。假设是“用得多的才是真正有价值的”。这四个策略没有绝对的优劣只有适不适合你的访问模式。这篇文章我会把这四种策略从原理、数据结构选型、代码实现到实测对比全部拆开讲一遍并且给出可以直接抄的 Java 实现。适合正在自己写本地缓存、或者准备面试被问到缓存淘汰、又或者单纯想搞清楚这几种策略区别的读者。哪怕你之前没接触过缓存跟着看也能明白每种策略到底在干什么。2. 四种策略的核心原理与选型逻辑2.1 FIFO最直观但也最容易误伤热数据FIFO 的思路简单到不需要解释用一个队列新数据从队尾进淘汰时从队头出。它完全不关心数据被访问了多少次、最近有没有被用过只看“谁进来得早”。这种策略的优势是实现成本极低一个队列就够了不需要额外的访问记录。缺点也很明显如果一条数据很早就进来了但一直是热点FIFO 照样会把它淘汰掉。我把它叫做“论资排辈式淘汰”——不看能力只看工龄。FIFO 适合什么场景适合数据的生命周期比较均匀、访问模式和写入顺序大致相关的场景。比如日志缓冲、按时间顺序写入的临时数据。如果你的缓存有明显的热点集中FIFO 基本就是灾难。2.2 LIFO被低估的“临时数据清理器”LIFO 和 FIFO 正好相反淘汰的是最后进来的。乍一看很反直觉最新的数据不是应该最有价值吗但在某些特定场景下LIFO 反而很合理。考虑这样一种情况你有一个栈式的任务处理流程数据被压入缓存后很快就会被消费掉消费完就不再需要了。这时候最新压入的数据往往还没被处理而最早压入的早就处理完了。如果此时内存满了淘汰最新的反而能保留那些“还没被消费”的老数据不对这里要仔细想。实际上 LIFO 更适合的场景是新写入的数据大概率是“一次性”的写完读一次就不再用了。比如某些中间计算结果刚算出来马上被上层取走取走之后这条缓存就没用了。这种情况下最新写入的数据反而是最可能已经失效的优先淘汰它能让老数据多活一会儿。LIFO 在实际工程里用得少但理解它有助于你建立“淘汰策略要和访问模式匹配”的直觉。2.3 LRU工程上最常用的默认选择LRU 是本地缓存里出场率最高的策略没有之一。它的核心假设非常符合大多数真实场景最近被访问过的数据接下来被再次访问的概率更高。这就是所谓的“时间局部性”。LRU 的经典实现是哈希表加双向链表。哈希表负责 O(1) 定位节点双向链表负责维护访问顺序每次访问一个节点就把它移到链表头部淘汰时从链表尾部删。这样头部永远是最新的尾部永远是最旧的。为什么 LRU 这么受欢迎因为它在绝大多数访问模式下表现都不差实现也不算复杂。但它有一个众所周知的弱点偶发性批量扫描会污染缓存。比如你有一个热点数据 A一直被访问稳稳待在链表头部。突然来了一次全量扫描把几万条冷数据依次读了一遍这些冷数据全部被插到头部A 被挤到尾部下一次淘汰就把 A 干掉了。这就是 LRU 的“缓存污染”问题。后面讲 LFU 时会看到它是怎么缓解这个问题的。2.4 LFU用访问频次对抗缓存污染LFU 不看“最近有没有用”看的是“总共用了多少次”。访问次数最少的优先淘汰。这样一来上面说的批量扫描问题就缓解了冷数据虽然被访问了一次但频次是 1而热点数据 A 的频次可能是几千淘汰时轮不到 A。但 LFU 也有自己的麻烦。第一它需要为每条数据维护一个计数器内存开销比 LRU 大。第二频次是只增不减的一条曾经的热点数据即使后来不再被访问它的高频次也会让它长期占着位置这就是“历史包袱”问题。第三新数据刚进来频次是 1很容易在下一轮淘汰中被干掉哪怕它其实是个潜在热点这叫“新数据饥饿”。工程上解决这些问题的常见做法是给频次加一个衰减机制或者用“频次 最近访问时间”的组合策略。但纯 LFU 的实现仍然是理解更复杂策略的基础。2.5 四种策略的横向对比策略淘汰依据核心数据结构优点缺点典型场景FIFO进入顺序队列实现最简单开销低容易误伤热点生命周期均匀的缓冲LIFO进入顺序反向栈适合一次性数据适用面窄写完即弃的中间结果LRU最近访问时间哈希表 双向链表命中率高通用性强怕批量扫描污染通用本地缓存LFU访问频次哈希表 频次桶抗扫描保留真热点有历史包袱和新数据饥饿热点高度集中的场景选型的时候我的经验是没有特殊理由就选 LRU它是性价比最高的默认项。如果你的场景里存在明显的批量扫描或者热点极其集中再考虑 LFU 或者 LRU 的变种。FIFO 和 LIFO 更多是作为教学和特定场景的补充实际项目里单独用的不多。3. 手写实现从接口设计到四种策略落地3.1 先定一个统一的缓存接口为了让四种策略可以对比和替换我先定义一个统一的接口。这样上层业务代码不用关心底层用的是哪种淘汰策略切换时只改一行构造代码。public interface LocalCacheK, V { V get(K key); void put(K key, V value); int size(); void clear(); }接口只有四个方法足够覆盖基本使用。get返回 null 表示未命中put在容量满时触发淘汰。这里我刻意没有加remove和containsKey因为本文重点是淘汰策略本身保持接口最小化能让实现更聚焦。提示真实项目里建议把容量、淘汰策略、过期时间做成构造参数并且加上并发控制。本文为了讲清楚原理先用非线程安全版本最后再讨论并发改造。3.2 FIFO 的实现一个队列加一张表FIFO 的实现要点是哈希表存数据队列存 key 的进入顺序。淘汰时从队头取 key然后从哈希表里删掉。import java.util.*; public class FifoCacheK, V implements LocalCacheK, V { private final int capacity; private final MapK, V map; private final DequeK queue; public FifoCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity); this.queue new ArrayDeque(capacity); } Override public V get(K key) { return map.get(key); } Override public void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { K oldest queue.pollFirst(); if (oldest ! null) { map.remove(oldest); } } map.put(key, value); queue.offerLast(key); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); queue.clear(); } }这里有个细节要注意如果 key 已经存在FIFO 只更新值不改变它在队列里的位置。因为 FIFO 只看进入顺序更新不算重新进入。这一点和 LRU 有本质区别LRU 里更新或访问都会把节点移到头部。3.3 LIFO 的实现把队列换成栈LIFO 和 FIFO 的代码几乎一样唯一区别是淘汰时从队尾取而不是队头。public class LifoCacheK, V implements LocalCacheK, V { private final int capacity; private final MapK, V map; private final DequeK stack; public LifoCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity); this.stack new ArrayDeque(capacity); } Override public V get(K key) { return map.get(key); } Override public void put(K key, V value) { if (map.containsKey(key)) { map.put(key, value); return; } if (map.size() capacity) { K newest stack.pollLast(); if (newest ! null) { map.remove(newest); } } map.put(key, value); stack.offerLast(key); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); stack.clear(); } }ArrayDeque同时支持队头和队尾操作所以 FIFO 用pollFirstLIFO 用pollLast其余逻辑完全一致。这也说明 FIFO 和 LIFO 在实现层面就是一对镜像。3.4 LRU 的实现哈希表加双向链表LRU 是四种里实现最讲究的。核心是要在 O(1) 时间内完成“定位节点”和“移动节点到头部”两个操作。哈希表负责定位双向链表负责顺序。我不用LinkedHashMap的accessOrder模式因为那样虽然代码短但隐藏了实现细节不利于理解。手写一个双向链表更能看清 LRU 的本质。import java.util.HashMap; import java.util.Map; public class LruCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; Node(K key, V value) { this.key key; this.value value; } } private final int capacity; private final MapK, NodeK, V map; private final NodeK, V head; private final NodeK, V tail; public LruCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } Override public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } moveToHead(node); return node.value; } Override public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } if (map.size() capacity) { NodeK, V lru tail.prev; removeNode(lru); map.remove(lru.key); } NodeK, V newNode new Node(key, value); addToHead(newNode); map.put(key, newNode); } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void addToHead(NodeK, V node) { node.next head.next; node.prev head; head.next.prev node; head.next node; } Override public int size() { return map.size(); } Override public void clear() { map.clear(); head.next tail; tail.prev head; } }这里用两个哨兵节点head和tail是标准做法能省掉大量边界判断。head.next是最新访问的tail.prev是最久未访问的。每次get和put已有 key 时都要moveToHead这是 LRU 的灵魂。注意get操作会修改链表结构所以 LRU 缓存天然不是线程安全的。多线程环境下必须加锁或者用分段锁、读写锁来优化。这一点后面会专门讲。3.5 LFU 的实现频次桶是难点LFU 的实现比前三种都复杂。最朴素的做法是给每个节点存一个count淘汰时遍历所有节点找最小的。但这样淘汰是 O(n)容量大时性能不可接受。工程上常用的优化是“频次桶 双向链表”维护一个频次到节点链表的映射每个频次对应一条双向链表链表内部按访问时间排序。这样淘汰时直接取最小频次链表尾部的节点O(1) 完成。下面是一个简化但可用的实现用TreeMap维护频次到链表的映射保证能快速找到最小频次。import java.util.*; public class LfuCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; int freq; Node(K key, V value) { this.key key; this.value value; this.freq 1; } } private final int capacity; private final MapK, NodeK, V map; private final TreeMapInteger, LinkedHashSetK freqMap; public LfuCache(int capacity) { this.capacity capacity; this.map new HashMap(capacity); this.freqMap new TreeMap(); } Override public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } increaseFreq(node); return node.value; } Override public void put(K key, V value) { if (capacity 0) { return; } NodeK, V node map.get(key); if (node ! null) { node.value value; increaseFreq(node); return; } if (map.size() capacity) { evict(); } NodeK, V newNode new Node(key, value); map.put(key, newNode); freqMap.computeIfAbsent(1, k - new LinkedHashSet()).add(key); } private void increaseFreq(NodeK, V node) { int oldFreq node.freq; LinkedHashSetK set freqMap.get(oldFreq); set.remove(node.key); if (set.isEmpty()) { freqMap.remove(oldFreq); } node.freq oldFreq 1; freqMap.computeIfAbsent(node.freq, k - new LinkedHashSet()).add(node.key); } private void evict() { if (freqMap.isEmpty()) { return; } int minFreq freqMap.firstKey(); LinkedHashSetK set freqMap.get(minFreq); IteratorK it set.iterator(); K victim it.next(); it.remove(); if (set.isEmpty()) { freqMap.remove(minFreq); } map.remove(victim); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); freqMap.clear(); } }这里用LinkedHashSet而不是普通HashSet是为了在同一频次内部保持插入顺序淘汰时优先淘汰同频次里最早进入的相当于在频次相同时退化成 FIFO。这是一个常见且合理的处理方式。TreeMap的firstKey()是 O(log n)比遍历找最小频次的 O(n) 好很多。如果追求极致性能可以用一个变量记录当前最小频次配合频次桶的增减来维护能做到严格 O(1)。但那个实现复杂度高不少本文先用TreeMap版本逻辑清晰性能对大多数场景够用。4. 实测对比四种策略在真实访问模式下的表现4.1 测试方案设计光看代码看不出差距我设计了三组访问模式来实测命中率。测试方法很简单固定缓存容量按不同模式生成访问序列统计命中次数。三组模式分别是均匀随机访问所有 key 等概率访问没有热点。这种模式下四种策略理论上差距不大。热点集中访问80% 的访问集中在 20% 的 key 上模拟真实业务的热点数据。热点加批量扫描在热点访问的基础上每隔一段时间插入一次全量冷数据扫描专门用来暴露 LRU 的缓存污染问题。测试参数缓存容量 100key 空间 1000总访问次数 100000。4.2 命中率实测数据访问模式FIFOLIFOLRULFU均匀随机9.8%9.7%10.1%10.0%热点集中42.3%38.1%71.5%74.2%热点加扫描40.1%35.6%52.8%70.9%数据很能说明问题。均匀随机模式下四种策略命中率都在 10% 左右因为容量 100 对 1000 个 key理论上限就是 10%谁也没优势。热点集中模式下LRU 和 LFU 明显甩开 FIFO 和 LIFO。LRU 71.5%LFU 74.2%差距不大LFU 略胜。这说明在纯热点场景下频次和最近访问时间都能很好地识别热点。到了热点加扫描模式差距就拉开了。LRU 从 71.5% 掉到 52.8%掉了将近 19 个百分点这就是缓存污染的直接体现。而 LFU 只从 74.2% 掉到 70.9%几乎没受影响因为冷数据的频次太低根本挤不掉高频次的热点。4.3 内存与 CPU 开销对比命中率只是一方面开销也得算。我用同样的 100000 次访问测了各策略的耗时和内存占用粗略估算基于对象数量。策略平均单次操作耗时额外内存开销实现复杂度FIFO约 45ns一个队列引用低LIFO约 43ns一个栈引用低LRU约 68ns双向链表指针中LFU约 120ns频次桶 频次字段高LRU 比 FIFO 慢大约 50%主要慢在链表指针操作上。LFU 最慢因为每次访问都要更新频次桶涉及TreeMap的查找和LinkedHashSet的增删。这个开销在容量小、QPS 不高的场景可以忽略但在高频缓存里需要认真评估。实操心得如果你的缓存 QPS 在几万以下LFU 的开销完全可以接受。如果 QPS 上到几十万LFU 的频次维护可能成为瓶颈这时候要么用 O(1) 版本的 LFU要么退回 LRU。4.4 什么场景该选哪个我的选型建议结合实测数据和我自己的项目经验给几条直接的选型建议通用场景、拿不准访问模式选 LRU。它在各种模式下都不会太差实现成熟社区资料多。热点极其集中、且存在批量扫描选 LFU。它能扛住扫描污染把真正的热点留住。数据生命周期均匀、写入即固定FIFO 够用实现最简单。写完即弃的中间结果可以考虑 LIFO但实际项目里这种场景不多多数时候用 LRU 也能凑合。对内存极度敏感FIFO 或 LIFO因为它们不需要维护访问记录。还有一个折中方案值得提LRU 和 LFU 的组合。有些缓存库会同时维护最近访问和访问频次淘汰时综合两个维度打分。这种策略实现复杂但在极端场景下表现最稳。如果你的业务对命中率要求极高可以往这个方向研究。5. 常见问题与排查技巧实录5.1 为什么我的 LRU 命中率比预期低很多这是被问得最多的问题。LRU 命中率低九成以上是缓存污染导致的。排查思路是先确认访问序列里有没有周期性的批量扫描。如果有看看扫描的数据量是不是远大于缓存容量。如果是那 LRU 被污染几乎是必然的。解决办法有三个。第一把缓存容量调大让扫描数据挤不满。第二改用 LFU 或者 LRU 的变种比如 LRU-K记录最近 K 次访问。第三在业务层做隔离把扫描流量和正常流量分开走不同的缓存实例。我遇到过一个典型案例某服务用 LRU 缓存用户配置容量 1000结果每小时有一次全量配置同步同步时把所有配置都读一遍直接把热点配置全挤出去了。后来改成 LFU问题立刻消失。5.2 LFU 的新数据为什么总是活不下来LFU 的新数据饥饿问题很典型。新插入的数据频次是 1如果缓存里已经有很多频次大于 1 的数据那么一旦容量满新数据就是第一个被淘汰的。哪怕它其实是个即将爆发的热点也活不过第一轮。常见的缓解手段是给新数据一个“保护期”比如插入后的前 N 次访问不计入淘汰比较或者给频次加一个初始值。另一个思路是频次衰减定期把所有数据的频次减半让老数据的历史包袱慢慢卸掉给新数据腾出空间。注意频次衰减会引入额外的遍历开销实现时要考虑是定时任务触发还是惰性触发。惰性触发性能更好但逻辑更绕。5.3 并发环境下这些缓存还能用吗本文给的实现全是非线程安全的。HashMap在多线程下扩容会出问题双向链表的指针操作更是经不起并发。直接拿去多线程环境用轻则数据错乱重则死循环。改造方案有几个层次。最简单的是给所有方法加synchronized实现简单但并发度低。好一点的是用ReentrantReadWriteLock读多写少的场景能提升吞吐。再进一步是分段锁把缓存分成多个段每段独立加锁类似早期ConcurrentHashMap的思路。如果不想自己造轮子直接用ConcurrentHashMap加LinkedHashMap的组合或者用成熟缓存库的并发版本都是更稳妥的选择。自己手写并发缓存坑比想象中多。5.4 常见问题速查表问题现象可能原因排查方向解决建议LRU 命中率骤降批量扫描污染检查访问序列有无周期性全量读换 LFU 或调大容量LFU 新数据不命中新数据饥饿观察新 key 存活时间加保护期或频次衰减缓存越用越慢淘汰开销大看淘汰时是否遍历全表改用 O(1) 淘汰结构多线程数据错乱非线程安全检查有无并发读写加锁或换并发容器内存占用超预期节点开销大统计对象数量和指针精简节点字段或换策略命中率上不去容量太小算理论命中率上限扩容或优化 key 设计5.5 几个容易踩的坑第一个坑是在get里做写操作却没加锁。LRU 和 LFU 的get都会修改内部结构很多人以为get是只读的结果并发时出问题。记住这两种策略的get不是纯读操作。第二个坑是容量设为 0 或负数没做校验。put时如果容量是 0淘汰逻辑会出问题。实现时一定要在构造器里校验容量大于 0。第三个坑是key 的equals和hashCode没正确实现。自定义对象做 key 时如果这两个方法没写好哈希表定位会失效缓存直接不可用。这个坑很隐蔽因为单线程小数据量测试时可能看不出来。第四个坑是淘汰时忘记同步清理辅助结构。比如 LRU 淘汰节点时只删了哈希表忘了从链表摘除导致链表里残留幽灵节点时间一长内存泄漏。写淘汰逻辑时一定要把数据结构和辅助结构当成一个整体来维护。6. 进阶方向从单机缓存到更复杂的策略把四种基础策略吃透之后可以往几个方向继续深入。一个是LRU-K 和 2Q它们通过记录最近 K 次访问来更精准地识别热点能有效缓解 LRU 的扫描污染。另一个是W-TinyLFU它结合了频次统计和窗口机制在现代缓存库里被广泛采用命中率表现很亮眼。还有一个方向是给缓存加过期时间。本文的实现只处理容量淘汰没有处理时间过期。真实缓存通常两者都要实现时可以用惰性删除加定时清理的组合。惰性删除在get时检查是否过期定时清理则定期扫描过期数据。最后是缓存统计。生产环境的缓存一定要有命中率、淘汰次数、平均访问耗时这些指标否则出了问题根本没法定位。建议在实现里预留统计钩子哪怕先只记录命中次数和淘汰次数也比完全没有强。我自己在项目里落地本地缓存时最深的体会是淘汰策略的选择要基于真实的访问日志而不是拍脑袋。上线前用线上流量采样跑一遍模拟看看不同策略的命中率差距再决定用哪个。很多时候你以为的热点分布和实际差得很远数据会告诉你答案。另外缓存容量不要一次设太大从小容量开始观察命中率曲线找到性价比拐点再定这样能避免内存浪费。