缓存淘汰算法里，LFU 大概是最容易被误读的——很多人以为它只是简单数次数，但工程实现背后全是坑。说实话，我第一次自己写 LFU 的时候，两天后系统 OOM，查日志才发现计数器全溢出了。简直灾难。
频率的诅咒：当 LFU 遇上突发流量
LFU 的全称是 Least Frequently Used，核心逻辑简单到令人发指：记录每个对象的访问次数，淘汰那个次数最少的。你可能会想，这有啥难的？搞个 HashMap 存 key，里面套个计数器，访问一次 counter++，完事儿。但——天真。
想象一个图书馆。每本书被借一次，管理员就在卡片上画一道。一年后，你要根据这些卡片决定剔除哪些书。那本《C++从入门到放弃》去年借了 200 次，今年没人碰；而刚上架的《Rust 实战》只被借了 10 次，但最近一周就有 8 次。按 LFU 逻辑，你会扔掉《Rust 实战》，因为它的总次数少。这合理吗？显然不。这就是第一个致命伤：LFU 缺乏时间衰减，旧的高频数据会永久占据缓存，即使它们早已过气。
在真实系统中，比如一个电商网站，去年的爆款商品今年可能无人问津，但它的计数器值高得吓人。与此同时，刚刚上架的限时秒杀商品只有区区几次访问，却因频率低被瞬间淘汰。缓存命中率断崖式下跌，老板脸都绿了。更糟糕的是，如果有突发流量——比如某明星突然穿了你家 T 恤——瞬时访问暴涨，但这些新频率根本无法与沉淀了一年的老数据抗衡，新热门一个都进不来。
所以，纯 LFU 在现实世界基本是废的。你必须让频率「贬值」——随时间流逝而降低。怎么搞？经典做法是定时衰减，比如每隔 N 秒把所有计数器除以 2（指数衰减），或者用更高效的算法，比如 TinyLFU 里的概率衰减。这一下子就复杂了，咱们后面再聊。
数学之美与工程之痛：从 O(log n) 到 O(1) 的进化
就算你加上了衰减，还有一个更蛋疼的问题：优先级队列的复杂度。LFU 需要频繁找出最小频率的条目，你当然可以用最小堆，但每次访问更新计数器时，堆调整的成本是 O(log n)。对于高并发缓存，这几乎是不可接受的。Redis 的作者 Antirez 曾经尝试过纯 LFU，最后不得不引入近似算法——他在博客里吐槽说：「如果你想要精确的 LFU，你的服务器会慢得像拨号上网。」
那有没有办法搞到 O(1)？有，但得用巧妙的数据结构。1994 年有篇论文提出一个方案：用多个链表，每个链表对应一个频率值。访问一个元素时，把它从当前频率链表移到下一个频率链表。这样，每次移动都是 O(1)，淘汰时从最低频率链表随便拿一个。但问题来了——如果频率值无限膨胀，链表数量会炸掉。所以必须限制最大频率，并且搞衰减。
后来的 TinyLFU 走得更远：它根本不存完整的访问次数，而是用 Count-Min Sketch 这类概率数据结构来估算频率。只占极少内存，大约一个条目几个字节，就能维护数亿个 key 的近似频率，误差可控。雅虎在 HBase 里实验过，TinyLFU 的命中率比 LRU 高出 12%～18%，而内存开销只有 LFU 的十分之一。我在自己的压测里也复现过类似结果：10 万 QPS 的读密集型场景下，LRU 命中率 72%，纯 LFU 衰减后 79%，而 W-TinyLFU（Window-TinyLFU）稳稳停在 87% 左右。差距非常直观。
不过话说回来，概率计数也有代价——偶尔会高估低频条目的频率，导致个别冷数据赖着不走。但对绝大多数业务来说，这点误差完全可以接受，换来的是巨大的性能提升。
落地三坑：那些文档不会告诉你的血泪经验
理论很丰满，现实全是大坑。下面这三个是我亲身趟过的，每一个都差点搞挂生产环境。
坑一：计数器无限膨胀吃爆内存。 前面提过，单纯的计数器随时间只增不减，最终会让你 OOM。即使你用 64 位整数，百万级的 key 也占好几十 MB，这还不算数据结构本身的开销。解决方案：
- 概率计数器：使用 8 位的对数计数器，最大值 255 代表无限次，增长用概率递增（比如每访问一次，只有 1/(当前值) 的概率增加）。这样高频条目的计数器也绝不会溢出，内存用量极低。Caffeine 库就是这么干的。
- 全局衰减周期：设置定时任务统一把所有计数器衰减（如右移一位），但要注意避免触发 GC 雪崩，衰减操作最好异步或分批进行。
坑二：突发流量污染缓存。 系统本来跑得好好的，突然一波热点涌入，所有新 key 的频率都低，全给淘汰了，命中率瞬间跳水。你得给新数据一点「保护期」。解法：
- 分段缓存（Window LFU）：在 LFU 前面加一个小型 LRU 窗口（占比 1%），新数据先进入窗口，窗口内访问频次达到阈值后再进主缓存。这就滤掉了绝大多数的信噪。W-TinyLFU 就是这种设计，兼顾冷启动和突发流量。
- 准入策略：类似 Redis LFU 模式，它给每个 key 一个初始的衰减时间戳，访问时间离得近的 key 即使总频次低也更容易保留，相当于引入了时间维度。
坑三：并发锁竞争拖垮吞吐。 多线程访问缓存时，更新频率和淘汰操作都要加锁，如果用一把大锁，QPS 直接腰斩。在高并发下，锁竞争甚至比查找本身还慢。应对：
- 分段加锁：把缓存切成 N 个 segment，每个 segment 有自己的计数器堆和锁，类似 ConcurrentHashMap 的思路。只要设定合适的分段数，冲突率极低。
- 无锁近似：利用 LongAdder 这类原子累加器做频率统计，淘汰时使用快照或 lazy 重排序，容忍短暂的不精确。很多高性能缓存库（如 Caffeine）都已经无锁化。
最后说一句实在话：缓存算法这东西，没有银弹。LFU 在长期稳定访问模式中碾压 LRU，但遇到混合负载就可能翻车。看完文章别急着开干，自己压测一把，拿数据说话。这种工程美学，只有踩过坑才会懂。
