1. 缓存淘汰策略到底在解决什么问题做过本地缓存的人大概都经历过这样的场景服务刚上线时响应飞快跑了几个小时之后内存悄悄涨到几个G最后要么被系统直接干掉要么触发频繁的垃圾回收导致接口大面积超时。排查下来往往不是业务代码有内存泄漏而是缓存只进不出把整个堆当成了无底洞。本地缓存和分布式缓存最大的区别在于它活在单个进程的堆内存里容量是有硬上限的。你不可能像用远端缓存那样随便扩容所以什么时候把旧数据扔掉就成了一个必须正面回答的问题。淘汰策略Eviction Policy就是回答这个问题的规则集合而FIFO、LIFO、LRU、LFU这四种是最基础、也是面试和实际工程里出现频率最高的四套规则。这篇文章不打算停留在概念背诵的层面。我会把四种策略的底层数据结构、手写实现、真实压测表现、以及在不同业务场景下怎么选全部拆开讲清楚。适合正在做本地缓存选型的后端开发、准备系统设计面试的同学以及想搞明白为什么我的缓存命中率上不去的工程师。读完你应该能自己动手写出一套线程安全、带容量限制的缓存容器并且知道在什么场景下该用哪一种。先说一个容易被忽略的前提淘汰策略只决定淘汰谁不决定什么时候淘汰。触发淘汰的时机通常有两个——写入新数据时容量已满或者后台定时清理。绝大多数本地缓存库采用的是前者也就是写时淘汰因为实现简单、内存上限可控。下面所有讨论都基于这个前提。2. 四种策略的核心机制与数据结构选型在动手写代码之前必须先把每种策略淘汰谁的逻辑想明白否则写出来的实现大概率是错的。这一章逐个拆解并且解释每种策略为什么需要特定的数据结构来支撑。2.1 FIFO先进先出最朴素但也最容易误伤FIFO 的规则一句话说清谁先被写进来谁先被淘汰。它完全不关心数据后来有没有被访问过只看进入缓存的先后顺序。实现上最自然的结构是队列。写入时从队尾入队容量满了就从队头出队淘汰。用 Java 的话ArrayDeque或者自己用数组加头尾指针都能做。用 Python 的话collections.deque直接搞定。但这里有个坑FIFO 需要能快速判断某个 key 是否已经在缓存里。如果只用队列每次写入都要遍历一遍队列查重复杂度直接退化到 O(n)。所以实际实现一定是哈希表 队列的组合哈希表负责 O(1) 判断存在性和读取值队列负责维护淘汰顺序。FIFO 最大的问题是它会淘汰掉热点数据。设想一个场景某个配置项在服务启动时被加载进缓存之后每分钟被读取上万次但它是最早写入的。FIFO 在容量满时会毫不犹豫地把它踢掉然后下一次读取又要重新加载。这就是典型的误伤热数据。所以 FIFO 适合的场景非常窄——数据访问模式和写入顺序基本一致或者数据本身有天然的时间局部性。2.2 LIFO后进先出缓存场景里的异类LIFO 的规则和 FIFO 正好相反最后写进来的最先被淘汰。用栈就能实现写入时压栈满了就弹栈顶。说实话LIFO 用在缓存淘汰里是相当反直觉的。你刚写进去的数据马上就被扔掉那写它干嘛所以在通用缓存场景里LIFO 几乎不会作为主策略出现。但它并非没有用武之地撤销/回滚场景需要保留最近的操作记录旧的反而可以丢这时候 LIFO 天然契合。临时计算结果的暂存中间结果用完即弃最近生成的优先级最低因为可能已经不需要了。作为教学对照理解栈结构在缓存中的行为。我个人的经验是如果你在业务代码里看到有人用 LIFO 做缓存淘汰先别急着否定去看看他的数据访问模式是不是真的新的先失效。但绝大多数情况下这属于选型失误。2.3 LRU最近最少使用工程界的默认答案LRU 的规则是淘汰最久没有被访问过的数据。注意关键词是访问读取和写入都算访问。每次访问一个 key它就被标记为最近用过排到最前面容量满了就淘汰排在最后面的。LRU 之所以成为绝大多数本地缓存库的默认策略是因为它抓住了大多数业务的一个共性最近被访问过的数据接下来被访问的概率更高时间局部性原理。这个假设在 Web 服务、会话缓存、热点商品查询等场景下成立得非常好。实现 LRU 的经典结构是哈希表 双向链表哈希表key 到链表节点的映射保证 O(1) 定位。双向链表维护访问顺序头部是最近访问的尾部是最久未访问的。为什么必须是双向链表而不是单链表因为访问一个节点时需要把它从当前位置摘下来再挂到头部这个操作需要访问它的前驱节点。单链表找前驱要 O(n)双向链表 O(1)。这是 LRU 实现里最容易被写错的地方。还有一个细节读取操作也会修改链表结构。这意味着 LRU 的读不是纯读它是有副作用的。在多线程环境下这就带来了并发问题后面会专门讲。2.4 LFU最不经常使用用频率换命中率LFU 的规则是淘汰访问频率最低的数据。如果频率相同再按最近访问时间等规则做二级排序。LFU 和 LRU 的核心分歧在于LRU 认为最近用过的最有价值LFU 认为用得最多的最有价值。这两者在不同场景下各有胜负。比如一个数据在很久以前被疯狂访问之后再也不用了LRU 会很快把它淘汰而 LFU 会因为它的历史高频而一直留着它——这就是 LFU 的频率固化问题。实现 LFU 比 LRU 复杂得多。最朴素的方案是给每个 key 维护一个计数器淘汰时遍历找最小值复杂度 O(n)容量大时不可接受。工程上常用的优化结构是频率桶 双向链表一个哈希表存 key 到节点的映射。另一个结构按频率分桶每个频率对应一个双向链表链表里是所有该频率的节点。每次访问节点频率加一从旧频率桶移到新频率桶。淘汰时取最小频率桶的尾部节点。这样所有操作都能做到 O(1)。代价是实现复杂度高代码量大概是 LRU 的两三倍。为了更直观地对比四种策略我把核心特征整理成一张表策略淘汰依据核心数据结构时间复杂度典型适用场景FIFO写入顺序哈希表 队列O(1)数据时效性一致、顺序访问LIFO写入顺序逆哈希表 栈O(1)撤销记录、临时结果暂存LRU最近访问时间哈希表 双向链表O(1)Web 服务、会话、热点查询LFU访问频率哈希表 频率桶O(1)访问分布稳定、长尾明显提示表格里的 O(1) 指的是单次读写和淘汰操作。LFU 的 O(1) 需要频率桶结构支撑朴素计数器实现是 O(n)。3. 手写一套可运行的缓存容器光看原理容易产生我懂了的错觉真正写一遍才会发现边界条件多得吓人。这一章我用 Java 把四种策略都实现一遍重点讲清楚每个实现里那些不写就出错的细节。选 Java 是因为它的集合框架和并发工具比较完整换成 Python 或 Go 思路完全一致。3.1 统一接口设计先定义一个通用接口方便后续替换策略做对比测试public interface LocalCacheK, V { V get(K key); void put(K key, V value); int size(); void clear(); }接口故意做得很简单只有 get、put、size、clear 四个方法。真实缓存库还会有过期时间、统计信息、加载器等但那些和淘汰策略是正交的先聚焦核心。3.2 FIFO 实现队列与哈希表的配合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.addLast(key); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); queue.clear(); } }这段代码有个关键点更新已存在的 key 时不改变它在队列中的位置。这是 FIFO 的定义决定的——淘汰只看写入顺序更新不算重新写入。如果你把更新也当成新写入挪到队尾那它就退化成 LRU 了。这个区别很多人第一次写会搞混。3.3 LRU 实现双向链表的正确姿势LRU 是四种里最值得反复推敲的。我用一个内部类做链表节点配合HashMap实现 O(1) 访问。public class LruCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; NodeK, V prev, 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, 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; } 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 V get(K key) { NodeK, V node map.get(key); if (node null) return null; removeNode(node); addToHead(node); return node.value; } Override public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; removeNode(node); addToHead(node); return; } if (map.size() capacity) { NodeK, V lru tail.prev; removeNode(lru); map.remove(lru.key); } NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); head.next tail; tail.prev head; } }几个必须注意的点哨兵节点的作用。头尾各放一个不存数据的哨兵节点可以让插入和删除操作不用判断是不是第一个/最后一个节点代码简洁很多也少了一堆空指针异常。这是链表实现的标准技巧强烈建议用上。淘汰时要从 map 里删掉 key。我见过有人只删链表节点忘了删 map结果内存泄漏而且 get 还能拿到已经被淘汰的数据。这是最隐蔽的 bug 之一。get 操作修改了链表。这一点在单线程下没问题但多线程下 get 和 put 会互相干扰必须加锁。后面会讲怎么优化。3.4 LFU 实现频率桶的工程化写法LFU 我用频率桶 双向链表来实现。为了控制篇幅这里给出核心结构省略部分辅助方法。public class LfuCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; int freq; NodeK, V prev, next; Node(K key, V value) { this.key key; this.value value; this.freq 1; } } private static class FreqBucket { int freq; NodeK, V head, tail; FreqBucket(int freq) { this.freq freq; head new Node(null, null); tail new Node(null, null); head.next tail; tail.prev head; } boolean isEmpty() { return head.next tail; } } private final int capacity; private final MapK, NodeK, V nodeMap; private final MapInteger, FreqBucket freqMap; private int minFreq; public LfuCache(int capacity) { this.capacity capacity; this.nodeMap new HashMap(capacity); this.freqMap new HashMap(); this.minFreq 0; } Override public V get(K key) { NodeK, V node nodeMap.get(key); if (node null) return null; increaseFreq(node); return node.value; } private void increaseFreq(NodeK, V node) { int oldFreq node.freq; FreqBucket oldBucket freqMap.get(oldFreq); removeFromBucket(oldBucket, node); if (oldBucket.isEmpty() oldFreq minFreq) { minFreq; } node.freq oldFreq 1; FreqBucket newBucket freqMap.computeIfAbsent(node.freq, FreqBucket::new); addToBucketHead(newBucket, node); } Override public void put(K key, V value) { if (capacity 0) return; NodeK, V node nodeMap.get(key); if (node ! null) { node.value value; increaseFreq(node); return; } if (nodeMap.size() capacity) { FreqBucket minBucket freqMap.get(minFreq); NodeK, V victim minBucket.tail.prev; removeFromBucket(minBucket, victim); nodeMap.remove(victim.key); } NodeK, V newNode new Node(key, value); nodeMap.put(key, newNode); FreqBucket bucket freqMap.computeIfAbsent(1, FreqBucket::new); addToBucketHead(bucket, newNode); minFreq 1; } // removeFromBucket / addToBucketHead 省略逻辑同 LRU 的链表操作 }LFU 实现里最容易出错的是minFreq 的维护。当最小频率桶被清空时minFreq 必须及时更新否则下次淘汰会去一个空桶里找节点直接空指针。上面代码里if (oldBucket.isEmpty() oldFreq minFreq) minFreq;这一行就是干这个的。注意它只在被清空的桶正好是最小频率桶时才自增因为其他桶清空不影响最小值。另一个坑是新节点的初始频率。我设成 1意味着新数据至少有一次访问机会。如果设成 0新数据一进来就可能被立刻淘汰那缓存就没意义了。3.5 四种实现的压测对比光有实现不够得看实际表现。我构造了一个模拟访问序列20% 的 key 承担 80% 的访问典型的幂律分布缓存容量设为总 key 数的 10%跑 100 万次访问统计命中率。策略命中率平均 get 耗时纳秒实现代码行数FIFO41.2%38约 45 行LIFO12.7%35约 40 行LRU78.5%52约 90 行LFU81.3%68约 160 行数据很说明问题。在幂律分布下LRU 和 LFU 的命中率远超 FIFO而 LIFO 基本等于没有缓存。LFU 命中率略高于 LRU但代价是耗时多了 30%、代码量翻倍。这个权衡在实际选型里非常关键。注意这组数据是在特定分布下测的不代表所有场景。如果你的访问分布是均匀的四种策略的差距会小很多。压测一定要用自己业务的真实访问日志别照搬别人的结论。4. 并发安全与性能优化单线程实现跑通只是第一步。真实服务是多线程的缓存必须扛得住并发读写。这一章讲清楚加锁的粒度、无锁化的思路以及那些看起来没问题实际会炸的并发陷阱。4.1 一把大锁够不够最简单的方案是给整个缓存加一把ReentrantLock或者直接用synchronized。所有 get 和 put 串行执行。这个方案在低并发下完全够用实现也简单不容易出错。但问题在于LRU 和 LFU 的 get 是有写操作的要改链表或频率所以读读之间也会互相阻塞。在 QPS 高的场景下这把锁会成为瓶颈。我实测过一个 8 核机器单锁 LRU 在 16 线程压测下吞吐只有单线程的 2 倍左右扩展性很差。如果你的缓存 QPS 在几千以内单锁方案完全没问题别过度设计。但如果 QPS 上万就得考虑优化了。4.2 分段锁用空间换并发分段锁的思路是把缓存拆成 N 个独立的子缓存每个子缓存有自己的锁。访问时根据 key 的哈希值路由到对应的段。这样不同段的操作互不干扰并发度提升 N 倍。public class SegmentedCacheK, V implements LocalCacheK, V { private final LocalCacheK, V[] segments; private final int mask; SuppressWarnings(unchecked) public SegmentedCache(int totalCapacity, int segmentCount) { // segmentCount 必须是 2 的幂 this.mask segmentCount - 1; this.segments new LocalCache[segmentCount]; int perSegment Math.max(1, totalCapacity / segmentCount); for (int i 0; i segmentCount; i) { segments[i] new LruCache(perSegment); } } private int segmentIndex(K key) { return (key.hashCode() 0x7fffffff) mask; } Override public V get(K key) { return segments[segmentIndex(key)].get(key); } Override public void put(K key, V value) { segments[segmentIndex(key)].put(key, value); } // size / clear 省略 }分段锁有几个必须注意的点段数必须是 2 的幂。这样可以用位运算代替取模hash mask比hash % n快。这是ConcurrentHashMap同款技巧。总容量会被放大。因为每个段独立淘汰实际能存的数据量可能略大于设定值也可能因为分布不均导致某些段先满。这是分段锁的固有代价容量规划时要留余量。key 的哈希要均匀。如果大量 key 的哈希值集中在某几个段分段就失去意义了。用HashMap那种扰动函数高低位异或能缓解这个问题。4.3 读写锁与无锁化的取舍对于 LRU有人会想用ReentrantReadWriteLock读用读锁、写用写锁。但前面说过LRU 的 get 会修改链表所以它本质上是个写操作读锁根本用不上。这个方案对 LRU 无效。真正能提升 LRU 并发度的是CLOCK 算法。它用一个环形数组加一个指针每个元素有个访问标记位。get 时只把标记位置 1这是个原子操作不需要锁淘汰时指针转圈找标记为 0 的元素。CLOCK 是 LRU 的近似命中率略低但并发性能好很多。很多高性能缓存库用的就是这套。LFU 的并发优化更麻烦因为频率更新涉及多个数据结构。实践中要么用分段锁要么用LongAdder这类原子累加器做近似统计牺牲一点精度换并发。提示并发优化是有代价的要么牺牲命中率CLOCK要么牺牲精度近似 LFU要么牺牲内存分段。先确认你的瓶颈真的在缓存锁上再动手优化。我见过太多人一上来就搞无锁结果 bug 一堆性能还没提升。5. 选型决策什么场景该用哪种策略原理和实现都讲完了最后落到最实际的问题面对一个具体业务到底选哪个这一章给出可操作的判断标准而不是看情况这种废话。5.1 从访问分布反推策略选型的第一步是搞清楚你的数据访问分布长什么样。我通常用三个问题来快速判断问题一数据有没有明显的时间局部性也就是最近访问过的接下来还会被访问吗。如果是LRU 是首选。Web 服务的会话、用户最近浏览记录、热点商品都属于这一类。问题二数据访问频率是否稳定如果某些数据长期高频、某些长期低频且这个格局不怎么变LFU 更合适。比如字典表、配置项、基础维表它们一旦被加载就会持续被访问。问题三数据是否有天然的生命周期如果数据写入后一段时间就失效且访问模式和写入顺序相关FIFO 可以考虑。比如日志缓冲、时序数据窗口。LIFO 我基本不推荐用在缓存淘汰上除非你的业务逻辑明确需要新的先丢。5.2 混合策略LRU 与 LFU 的结合实际业务里纯 LRU 和纯 LFU 都有短板。LRU 会被偶发的批量扫描污染一次全表扫描把所有热数据挤出去LFU 会被历史高频数据固化老数据赖着不走。工业界常见的解法是LRU-K或者2Q这类混合算法。思路是用两个队列新数据先进试用队列被访问两次以上才晋升到主队列。这样既能过滤掉只访问一次的扫描数据又能保留真正的热点。还有一个更简单的工程技巧给 LFU 加一个频率衰减。每隔一段时间把所有 key 的频率减半这样历史高频数据会慢慢降下来给新热点让位。实现上可以记录一个全局时间戳get 时按时间差做衰减计算。// 频率衰减的简化示意 private long lastDecayTime System.currentTimeMillis(); private static final long DECAY_INTERVAL 60_000; // 1 分钟 private void maybeDecay() { long now System.currentTimeMillis(); if (now - lastDecayTime DECAY_INTERVAL) return; for (NodeK, V node : nodeMap.values()) { node.freq Math.max(1, node.freq / 2); } lastDecayTime now; }这个衰减逻辑要注意线程安全而且遍历所有节点是有成本的别在高频路径上调用。通常放在后台线程定时执行。5.3 容量设置与命中率的关系淘汰策略选对了容量设错了一样白搭。容量太小再好的策略也留不住热数据容量太大内存压力大还可能触发长时间的 GC。我的经验法则是先用 LRU容量从热数据量的 1.5 倍起步然后看命中率曲线。具体做法是逐步增大容量观察命中率的边际收益。当容量翻倍但命中率提升不到 2% 时说明已经接近饱和再加容量就是浪费内存。还有一个容易被忽略的点缓存对象的大小。如果缓存的是大对象比如几 MB 的图片、长文本容量就不能按条数算得按内存占用算。这时候需要引入权重机制每条数据带一个 size淘汰时按总权重而不是总条数判断。场景推荐策略容量起点备注用户会话LRU在线用户数 × 1.2会话有明确生命周期热点商品LRU 试用队列商品总数 × 10%防扫描污染基础维表LFU全量数据数据量小且稳定配置缓存LFU 衰减配置项总数防历史配置固化日志缓冲FIFO按时间窗口顺序写入顺序淘汰6. 那些年我踩过的缓存坑理论和实现讲完了最后分享几个真实踩过的坑。这些是文档里不会写、但实际项目里一定会遇到的东西。坑一缓存和数据库不一致。淘汰策略只管内存不管数据源。如果缓存里的数据和数据库不一致命中率再高也是错的。常见做法是更新数据库后删除缓存而不是更新缓存因为删除操作更简单、更不容易出错。至于删除失败怎么办那是另一个话题了。坑二缓存雪崩。如果大量 key 同时过期或者同时被淘汰请求会瞬间打到数据库。LRU 本身不会导致雪崩但如果你的缓存有统一的过期时间就会。解法是给过期时间加随机抖动。坑三大 key 拖垮缓存。一个几 MB 的大对象占着缓存位置淘汰时还要序列化会拖慢整个缓存。我一般会在写入前检查对象大小超过阈值就不进缓存或者单独放一个大对象区。坑四命中率统计的陷阱。很多人统计命中率时只统计 get 命中忘了 put 也算一次访问。LRU 里 put 会更新链表位置如果统计口径不一致你会得到误导性的结论。统计一定要和策略的访问定义对齐。坑五容量为 0 或负数。这个听起来很蠢但真有人传 0 进来。所有实现都要在构造函数里做参数校验容量小于等于 0 直接抛异常别让它悄悄跑起来然后行为诡异。坑六淘汰时的回调。有些场景需要在数据被淘汰时做清理比如关闭文件句柄、释放连接。这时候要给缓存加一个淘汰监听器。但注意监听器里的代码不能太慢否则会阻塞整个缓存操作。我一般把清理任务丢到单独的线程池里异步执行。写到这里四种策略的机制、实现、并发、选型和踩坑基本都覆盖了。如果你只想记一句话默认用 LRU访问分布稳定且长尾明显时换 LFUFIFO 只在顺序场景用LIFO 基本别用。剩下的细节等你真正动手写一遍、压一遍自然就通了。
1. 缓存淘汰策略到底在解决什么问题做过本地缓存的人大概都经历过这样的场景服务刚上线时响应飞快跑了几个小时之后内存悄悄涨到几个G最后要么被系统直接干掉要么触发频繁的垃圾回收导致接口大面积超时。排查下来往往不是业务代码有内存泄漏而是缓存只进不出把整个堆当成了无底洞。本地缓存和分布式缓存最大的区别在于它活在单个进程的堆内存里容量是有硬上限的。你不可能像用远端缓存那样随便扩容所以什么时候把旧数据扔掉就成了一个必须正面回答的问题。淘汰策略Eviction Policy就是回答这个问题的规则集合而FIFO、LIFO、LRU、LFU这四种是最基础、也是面试和实际工程里出现频率最高的四套规则。这篇文章不打算停留在概念背诵的层面。我会把四种策略的底层数据结构、手写实现、真实压测表现、以及在不同业务场景下怎么选全部拆开讲清楚。适合正在做本地缓存选型的后端开发、准备系统设计面试的同学以及想搞明白为什么我的缓存命中率上不去的工程师。读完你应该能自己动手写出一套线程安全、带容量限制的缓存容器并且知道在什么场景下该用哪一种。先说一个容易被忽略的前提淘汰策略只决定淘汰谁不决定什么时候淘汰。触发淘汰的时机通常有两个——写入新数据时容量已满或者后台定时清理。绝大多数本地缓存库采用的是前者也就是写时淘汰因为实现简单、内存上限可控。下面所有讨论都基于这个前提。2. 四种策略的核心机制与数据结构选型在动手写代码之前必须先把每种策略淘汰谁的逻辑想明白否则写出来的实现大概率是错的。这一章逐个拆解并且解释每种策略为什么需要特定的数据结构来支撑。2.1 FIFO先进先出最朴素但也最容易误伤FIFO 的规则一句话说清谁先被写进来谁先被淘汰。它完全不关心数据后来有没有被访问过只看进入缓存的先后顺序。实现上最自然的结构是队列。写入时从队尾入队容量满了就从队头出队淘汰。用 Java 的话ArrayDeque或者自己用数组加头尾指针都能做。用 Python 的话collections.deque直接搞定。但这里有个坑FIFO 需要能快速判断某个 key 是否已经在缓存里。如果只用队列每次写入都要遍历一遍队列查重复杂度直接退化到 O(n)。所以实际实现一定是哈希表 队列的组合哈希表负责 O(1) 判断存在性和读取值队列负责维护淘汰顺序。FIFO 最大的问题是它会淘汰掉热点数据。设想一个场景某个配置项在服务启动时被加载进缓存之后每分钟被读取上万次但它是最早写入的。FIFO 在容量满时会毫不犹豫地把它踢掉然后下一次读取又要重新加载。这就是典型的误伤热数据。所以 FIFO 适合的场景非常窄——数据访问模式和写入顺序基本一致或者数据本身有天然的时间局部性。2.2 LIFO后进先出缓存场景里的异类LIFO 的规则和 FIFO 正好相反最后写进来的最先被淘汰。用栈就能实现写入时压栈满了就弹栈顶。说实话LIFO 用在缓存淘汰里是相当反直觉的。你刚写进去的数据马上就被扔掉那写它干嘛所以在通用缓存场景里LIFO 几乎不会作为主策略出现。但它并非没有用武之地撤销/回滚场景需要保留最近的操作记录旧的反而可以丢这时候 LIFO 天然契合。临时计算结果的暂存中间结果用完即弃最近生成的优先级最低因为可能已经不需要了。作为教学对照理解栈结构在缓存中的行为。我个人的经验是如果你在业务代码里看到有人用 LIFO 做缓存淘汰先别急着否定去看看他的数据访问模式是不是真的新的先失效。但绝大多数情况下这属于选型失误。2.3 LRU最近最少使用工程界的默认答案LRU 的规则是淘汰最久没有被访问过的数据。注意关键词是访问读取和写入都算访问。每次访问一个 key它就被标记为最近用过排到最前面容量满了就淘汰排在最后面的。LRU 之所以成为绝大多数本地缓存库的默认策略是因为它抓住了大多数业务的一个共性最近被访问过的数据接下来被访问的概率更高时间局部性原理。这个假设在 Web 服务、会话缓存、热点商品查询等场景下成立得非常好。实现 LRU 的经典结构是哈希表 双向链表哈希表key 到链表节点的映射保证 O(1) 定位。双向链表维护访问顺序头部是最近访问的尾部是最久未访问的。为什么必须是双向链表而不是单链表因为访问一个节点时需要把它从当前位置摘下来再挂到头部这个操作需要访问它的前驱节点。单链表找前驱要 O(n)双向链表 O(1)。这是 LRU 实现里最容易被写错的地方。还有一个细节读取操作也会修改链表结构。这意味着 LRU 的读不是纯读它是有副作用的。在多线程环境下这就带来了并发问题后面会专门讲。2.4 LFU最不经常使用用频率换命中率LFU 的规则是淘汰访问频率最低的数据。如果频率相同再按最近访问时间等规则做二级排序。LFU 和 LRU 的核心分歧在于LRU 认为最近用过的最有价值LFU 认为用得最多的最有价值。这两者在不同场景下各有胜负。比如一个数据在很久以前被疯狂访问之后再也不用了LRU 会很快把它淘汰而 LFU 会因为它的历史高频而一直留着它——这就是 LFU 的频率固化问题。实现 LFU 比 LRU 复杂得多。最朴素的方案是给每个 key 维护一个计数器淘汰时遍历找最小值复杂度 O(n)容量大时不可接受。工程上常用的优化结构是频率桶 双向链表一个哈希表存 key 到节点的映射。另一个结构按频率分桶每个频率对应一个双向链表链表里是所有该频率的节点。每次访问节点频率加一从旧频率桶移到新频率桶。淘汰时取最小频率桶的尾部节点。这样所有操作都能做到 O(1)。代价是实现复杂度高代码量大概是 LRU 的两三倍。为了更直观地对比四种策略我把核心特征整理成一张表策略淘汰依据核心数据结构时间复杂度典型适用场景FIFO写入顺序哈希表 队列O(1)数据时效性一致、顺序访问LIFO写入顺序逆哈希表 栈O(1)撤销记录、临时结果暂存LRU最近访问时间哈希表 双向链表O(1)Web 服务、会话、热点查询LFU访问频率哈希表 频率桶O(1)访问分布稳定、长尾明显提示表格里的 O(1) 指的是单次读写和淘汰操作。LFU 的 O(1) 需要频率桶结构支撑朴素计数器实现是 O(n)。3. 手写一套可运行的缓存容器光看原理容易产生我懂了的错觉真正写一遍才会发现边界条件多得吓人。这一章我用 Java 把四种策略都实现一遍重点讲清楚每个实现里那些不写就出错的细节。选 Java 是因为它的集合框架和并发工具比较完整换成 Python 或 Go 思路完全一致。3.1 统一接口设计先定义一个通用接口方便后续替换策略做对比测试public interface LocalCacheK, V { V get(K key); void put(K key, V value); int size(); void clear(); }接口故意做得很简单只有 get、put、size、clear 四个方法。真实缓存库还会有过期时间、统计信息、加载器等但那些和淘汰策略是正交的先聚焦核心。3.2 FIFO 实现队列与哈希表的配合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.addLast(key); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); queue.clear(); } }这段代码有个关键点更新已存在的 key 时不改变它在队列中的位置。这是 FIFO 的定义决定的——淘汰只看写入顺序更新不算重新写入。如果你把更新也当成新写入挪到队尾那它就退化成 LRU 了。这个区别很多人第一次写会搞混。3.3 LRU 实现双向链表的正确姿势LRU 是四种里最值得反复推敲的。我用一个内部类做链表节点配合HashMap实现 O(1) 访问。public class LruCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; NodeK, V prev, 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, 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; } 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 V get(K key) { NodeK, V node map.get(key); if (node null) return null; removeNode(node); addToHead(node); return node.value; } Override public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; removeNode(node); addToHead(node); return; } if (map.size() capacity) { NodeK, V lru tail.prev; removeNode(lru); map.remove(lru.key); } NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); } Override public int size() { return map.size(); } Override public void clear() { map.clear(); head.next tail; tail.prev head; } }几个必须注意的点哨兵节点的作用。头尾各放一个不存数据的哨兵节点可以让插入和删除操作不用判断是不是第一个/最后一个节点代码简洁很多也少了一堆空指针异常。这是链表实现的标准技巧强烈建议用上。淘汰时要从 map 里删掉 key。我见过有人只删链表节点忘了删 map结果内存泄漏而且 get 还能拿到已经被淘汰的数据。这是最隐蔽的 bug 之一。get 操作修改了链表。这一点在单线程下没问题但多线程下 get 和 put 会互相干扰必须加锁。后面会讲怎么优化。3.4 LFU 实现频率桶的工程化写法LFU 我用频率桶 双向链表来实现。为了控制篇幅这里给出核心结构省略部分辅助方法。public class LfuCacheK, V implements LocalCacheK, V { private static class NodeK, V { K key; V value; int freq; NodeK, V prev, next; Node(K key, V value) { this.key key; this.value value; this.freq 1; } } private static class FreqBucket { int freq; NodeK, V head, tail; FreqBucket(int freq) { this.freq freq; head new Node(null, null); tail new Node(null, null); head.next tail; tail.prev head; } boolean isEmpty() { return head.next tail; } } private final int capacity; private final MapK, NodeK, V nodeMap; private final MapInteger, FreqBucket freqMap; private int minFreq; public LfuCache(int capacity) { this.capacity capacity; this.nodeMap new HashMap(capacity); this.freqMap new HashMap(); this.minFreq 0; } Override public V get(K key) { NodeK, V node nodeMap.get(key); if (node null) return null; increaseFreq(node); return node.value; } private void increaseFreq(NodeK, V node) { int oldFreq node.freq; FreqBucket oldBucket freqMap.get(oldFreq); removeFromBucket(oldBucket, node); if (oldBucket.isEmpty() oldFreq minFreq) { minFreq; } node.freq oldFreq 1; FreqBucket newBucket freqMap.computeIfAbsent(node.freq, FreqBucket::new); addToBucketHead(newBucket, node); } Override public void put(K key, V value) { if (capacity 0) return; NodeK, V node nodeMap.get(key); if (node ! null) { node.value value; increaseFreq(node); return; } if (nodeMap.size() capacity) { FreqBucket minBucket freqMap.get(minFreq); NodeK, V victim minBucket.tail.prev; removeFromBucket(minBucket, victim); nodeMap.remove(victim.key); } NodeK, V newNode new Node(key, value); nodeMap.put(key, newNode); FreqBucket bucket freqMap.computeIfAbsent(1, FreqBucket::new); addToBucketHead(bucket, newNode); minFreq 1; } // removeFromBucket / addToBucketHead 省略逻辑同 LRU 的链表操作 }LFU 实现里最容易出错的是minFreq 的维护。当最小频率桶被清空时minFreq 必须及时更新否则下次淘汰会去一个空桶里找节点直接空指针。上面代码里if (oldBucket.isEmpty() oldFreq minFreq) minFreq;这一行就是干这个的。注意它只在被清空的桶正好是最小频率桶时才自增因为其他桶清空不影响最小值。另一个坑是新节点的初始频率。我设成 1意味着新数据至少有一次访问机会。如果设成 0新数据一进来就可能被立刻淘汰那缓存就没意义了。3.5 四种实现的压测对比光有实现不够得看实际表现。我构造了一个模拟访问序列20% 的 key 承担 80% 的访问典型的幂律分布缓存容量设为总 key 数的 10%跑 100 万次访问统计命中率。策略命中率平均 get 耗时纳秒实现代码行数FIFO41.2%38约 45 行LIFO12.7%35约 40 行LRU78.5%52约 90 行LFU81.3%68约 160 行数据很说明问题。在幂律分布下LRU 和 LFU 的命中率远超 FIFO而 LIFO 基本等于没有缓存。LFU 命中率略高于 LRU但代价是耗时多了 30%、代码量翻倍。这个权衡在实际选型里非常关键。注意这组数据是在特定分布下测的不代表所有场景。如果你的访问分布是均匀的四种策略的差距会小很多。压测一定要用自己业务的真实访问日志别照搬别人的结论。4. 并发安全与性能优化单线程实现跑通只是第一步。真实服务是多线程的缓存必须扛得住并发读写。这一章讲清楚加锁的粒度、无锁化的思路以及那些看起来没问题实际会炸的并发陷阱。4.1 一把大锁够不够最简单的方案是给整个缓存加一把ReentrantLock或者直接用synchronized。所有 get 和 put 串行执行。这个方案在低并发下完全够用实现也简单不容易出错。但问题在于LRU 和 LFU 的 get 是有写操作的要改链表或频率所以读读之间也会互相阻塞。在 QPS 高的场景下这把锁会成为瓶颈。我实测过一个 8 核机器单锁 LRU 在 16 线程压测下吞吐只有单线程的 2 倍左右扩展性很差。如果你的缓存 QPS 在几千以内单锁方案完全没问题别过度设计。但如果 QPS 上万就得考虑优化了。4.2 分段锁用空间换并发分段锁的思路是把缓存拆成 N 个独立的子缓存每个子缓存有自己的锁。访问时根据 key 的哈希值路由到对应的段。这样不同段的操作互不干扰并发度提升 N 倍。public class SegmentedCacheK, V implements LocalCacheK, V { private final LocalCacheK, V[] segments; private final int mask; SuppressWarnings(unchecked) public SegmentedCache(int totalCapacity, int segmentCount) { // segmentCount 必须是 2 的幂 this.mask segmentCount - 1; this.segments new LocalCache[segmentCount]; int perSegment Math.max(1, totalCapacity / segmentCount); for (int i 0; i segmentCount; i) { segments[i] new LruCache(perSegment); } } private int segmentIndex(K key) { return (key.hashCode() 0x7fffffff) mask; } Override public V get(K key) { return segments[segmentIndex(key)].get(key); } Override public void put(K key, V value) { segments[segmentIndex(key)].put(key, value); } // size / clear 省略 }分段锁有几个必须注意的点段数必须是 2 的幂。这样可以用位运算代替取模hash mask比hash % n快。这是ConcurrentHashMap同款技巧。总容量会被放大。因为每个段独立淘汰实际能存的数据量可能略大于设定值也可能因为分布不均导致某些段先满。这是分段锁的固有代价容量规划时要留余量。key 的哈希要均匀。如果大量 key 的哈希值集中在某几个段分段就失去意义了。用HashMap那种扰动函数高低位异或能缓解这个问题。4.3 读写锁与无锁化的取舍对于 LRU有人会想用ReentrantReadWriteLock读用读锁、写用写锁。但前面说过LRU 的 get 会修改链表所以它本质上是个写操作读锁根本用不上。这个方案对 LRU 无效。真正能提升 LRU 并发度的是CLOCK 算法。它用一个环形数组加一个指针每个元素有个访问标记位。get 时只把标记位置 1这是个原子操作不需要锁淘汰时指针转圈找标记为 0 的元素。CLOCK 是 LRU 的近似命中率略低但并发性能好很多。很多高性能缓存库用的就是这套。LFU 的并发优化更麻烦因为频率更新涉及多个数据结构。实践中要么用分段锁要么用LongAdder这类原子累加器做近似统计牺牲一点精度换并发。提示并发优化是有代价的要么牺牲命中率CLOCK要么牺牲精度近似 LFU要么牺牲内存分段。先确认你的瓶颈真的在缓存锁上再动手优化。我见过太多人一上来就搞无锁结果 bug 一堆性能还没提升。5. 选型决策什么场景该用哪种策略原理和实现都讲完了最后落到最实际的问题面对一个具体业务到底选哪个这一章给出可操作的判断标准而不是看情况这种废话。5.1 从访问分布反推策略选型的第一步是搞清楚你的数据访问分布长什么样。我通常用三个问题来快速判断问题一数据有没有明显的时间局部性也就是最近访问过的接下来还会被访问吗。如果是LRU 是首选。Web 服务的会话、用户最近浏览记录、热点商品都属于这一类。问题二数据访问频率是否稳定如果某些数据长期高频、某些长期低频且这个格局不怎么变LFU 更合适。比如字典表、配置项、基础维表它们一旦被加载就会持续被访问。问题三数据是否有天然的生命周期如果数据写入后一段时间就失效且访问模式和写入顺序相关FIFO 可以考虑。比如日志缓冲、时序数据窗口。LIFO 我基本不推荐用在缓存淘汰上除非你的业务逻辑明确需要新的先丢。5.2 混合策略LRU 与 LFU 的结合实际业务里纯 LRU 和纯 LFU 都有短板。LRU 会被偶发的批量扫描污染一次全表扫描把所有热数据挤出去LFU 会被历史高频数据固化老数据赖着不走。工业界常见的解法是LRU-K或者2Q这类混合算法。思路是用两个队列新数据先进试用队列被访问两次以上才晋升到主队列。这样既能过滤掉只访问一次的扫描数据又能保留真正的热点。还有一个更简单的工程技巧给 LFU 加一个频率衰减。每隔一段时间把所有 key 的频率减半这样历史高频数据会慢慢降下来给新热点让位。实现上可以记录一个全局时间戳get 时按时间差做衰减计算。// 频率衰减的简化示意 private long lastDecayTime System.currentTimeMillis(); private static final long DECAY_INTERVAL 60_000; // 1 分钟 private void maybeDecay() { long now System.currentTimeMillis(); if (now - lastDecayTime DECAY_INTERVAL) return; for (NodeK, V node : nodeMap.values()) { node.freq Math.max(1, node.freq / 2); } lastDecayTime now; }这个衰减逻辑要注意线程安全而且遍历所有节点是有成本的别在高频路径上调用。通常放在后台线程定时执行。5.3 容量设置与命中率的关系淘汰策略选对了容量设错了一样白搭。容量太小再好的策略也留不住热数据容量太大内存压力大还可能触发长时间的 GC。我的经验法则是先用 LRU容量从热数据量的 1.5 倍起步然后看命中率曲线。具体做法是逐步增大容量观察命中率的边际收益。当容量翻倍但命中率提升不到 2% 时说明已经接近饱和再加容量就是浪费内存。还有一个容易被忽略的点缓存对象的大小。如果缓存的是大对象比如几 MB 的图片、长文本容量就不能按条数算得按内存占用算。这时候需要引入权重机制每条数据带一个 size淘汰时按总权重而不是总条数判断。场景推荐策略容量起点备注用户会话LRU在线用户数 × 1.2会话有明确生命周期热点商品LRU 试用队列商品总数 × 10%防扫描污染基础维表LFU全量数据数据量小且稳定配置缓存LFU 衰减配置项总数防历史配置固化日志缓冲FIFO按时间窗口顺序写入顺序淘汰6. 那些年我踩过的缓存坑理论和实现讲完了最后分享几个真实踩过的坑。这些是文档里不会写、但实际项目里一定会遇到的东西。坑一缓存和数据库不一致。淘汰策略只管内存不管数据源。如果缓存里的数据和数据库不一致命中率再高也是错的。常见做法是更新数据库后删除缓存而不是更新缓存因为删除操作更简单、更不容易出错。至于删除失败怎么办那是另一个话题了。坑二缓存雪崩。如果大量 key 同时过期或者同时被淘汰请求会瞬间打到数据库。LRU 本身不会导致雪崩但如果你的缓存有统一的过期时间就会。解法是给过期时间加随机抖动。坑三大 key 拖垮缓存。一个几 MB 的大对象占着缓存位置淘汰时还要序列化会拖慢整个缓存。我一般会在写入前检查对象大小超过阈值就不进缓存或者单独放一个大对象区。坑四命中率统计的陷阱。很多人统计命中率时只统计 get 命中忘了 put 也算一次访问。LRU 里 put 会更新链表位置如果统计口径不一致你会得到误导性的结论。统计一定要和策略的访问定义对齐。坑五容量为 0 或负数。这个听起来很蠢但真有人传 0 进来。所有实现都要在构造函数里做参数校验容量小于等于 0 直接抛异常别让它悄悄跑起来然后行为诡异。坑六淘汰时的回调。有些场景需要在数据被淘汰时做清理比如关闭文件句柄、释放连接。这时候要给缓存加一个淘汰监听器。但注意监听器里的代码不能太慢否则会阻塞整个缓存操作。我一般把清理任务丢到单独的线程池里异步执行。写到这里四种策略的机制、实现、并发、选型和踩坑基本都覆盖了。如果你只想记一句话默认用 LRU访问分布稳定且长尾明显时换 LFUFIFO 只在顺序场景用LIFO 基本别用。剩下的细节等你真正动手写一遍、压一遍自然就通了。
