LFU 缓存淘汰算法

定义

LFU(Least Frequently Used,最不经常使用)是一种缓存置换算法:为每个缓存条目维护访问计数,当空间不足时淘汰访问频率最低的条目。

原理

朴素实现用最小堆维护频率,操作复杂度为 O(log n);更优的做法是采用「频率桶 + 双向链表 + 哈希表」结构,将读写和淘汰都降到 O(1),同频条目之间再按 LRU 顺序打破平局。

优缺点

LFU 对访问频率分布稳定的场景(如热点内容长期热)命中率通常优于 LRU;但存在「缓存污染」问题——历史上被高频访问、如今已过气的数据因计数很高而迟迟不被淘汰,对突发流量和访问模式漂移适应差。常见改进包括对计数做时间衰减(aging)、以及 TinyLFU 等基于概率草图的近似方案。

应用

Redis 的 maxmemory 策略提供 allkeys-lfu 与 volatile-lfu(近似 LFU,采用对数计数器加衰减);操作系统、数据库缓冲池和 CDN 也常用其变体。