算法不是纸上谈兵——LRU的致命假设
记得去年双十一，购物车服务突然疯了。Redis内存爆满，淘汰策略是allkeys-lru。当时我想，LRU嘛，最近最少使用，很合理。结果呢，大量活跃用户的购物车数据被踢了出去，瞬间缓存穿透，数据库差点跪了。为什么？因为LRU有个隐性前提：访问模式是时间局部性的。但双十一，用户操作是脉冲式的，前一小时没人，后一小时疯狂加购。LRU只看重最后一次访问时间，那些被用户反复观看但最后才决定购买的商品，反而因为“最近没动”而被优先淘汰。太冤了。
LRU实现很简单：哈希表+双向链表。每次访问，把节点移到链表头；淘汰时删掉链表尾。O(1)时间复杂度，工程上美得像诗。但它的性能退化曲线很陡——一旦工作集大于缓存容量，且访问模式不是那么“规矩”，命中率断崖式下跌。我们在预发环境里连续压测，模拟高峰流量，LRU命中率从稳定的90%骤降至62%，数据库QPS暴涨3倍。那一刻我真的冷汗直冒，用错误的方法优雅地自杀了。
LFU与他的变种——为什么复杂的往往是对的
后来转向LFU（Least Frequently Used），用频次计数。计数器记录每个键被访问了多少次，淘汰时踢掉计数最小的。听起来完美？呵呵，又踩坑。单纯的LFU存在缓存污染：一些历史热点，频次极高，但已经没人访问了，却赖在缓存里不走，新来的热点挤不进来。这就是冷启动问题，也是LFU的死穴。还有，频次累加是个越滚越大的数，内存开销不小。
我们实际压测：用Zipf分布（α=1.0）模拟真实负载，纯LFU命中率确实比LRU好，达到78%，但内存浪费严重——大量淘汰压根不发生，因为老热点挡路。之后尝试了LFU-Aging：定期将所有计数除以一个衰减因子。坦率说，这招设计得很tricky。我们设衰减周期10秒，除2，性能直接飞跃，命中率上了85%。但这依赖衰减间隔的精心调参，调不好就变成LRU或退化版LFU。
目前很多系统用W-TinyLFU，比如Caffeine。它维护一个Count-Min Sketch做频率计数，用一个小型LRU做“窗口”，解决LFU对新数据的歧视。说实话，这个Sketch方案特别精巧——用几个哈希函数映射到计数数组，取最小估计值避免溢出，空间开销极小。我们的测试显示，在热点频变的电商场景，W-TinyLFU比纯LFU命中率又提了5个百分点，达到90%左右，接近理论最优。但实现复杂度上去了，要考虑并发性能，尤其写多读多的场景，必须用无锁结构，比如环形缓冲队列+后台线程批处理。
三个让你半夜惊醒的实践陷阱
陷阱一：过期时间与淘汰策略的冲突。 很多人以为设置了key的TTL就万事大吉。错！当Redis内存到达maxmemory，它会先执行淘汰策略删除键，而不管这些键是否已过期。如果你用了noeviction，那更惨，直接OOM。我们曾把volatile-lru和主动过期叠用，结果频繁触发淘汰，但过期的键占了大量内存。解决办法：要么让淘汰策略和过期策略协同（比如用allkeys-*策略），要么自己写个脚本预删除临近过期的键，减少在淘汰路径上的竞争。
陷阱二：淘汰开销拖垮延迟。 纯LFU在键空间巨大时，选择淘汰键需要遍历所有键找最小计数，这是O(N)的操作，灾难！生产环境里不可能每次淘汰都遍历。除非你维护一个排序堆，但插入和更新的成本又会上升。Redis采用近似淘汰：随机采样N个键，挑其中最差的淘汰。N默认5，可以调到10。但采样随机性可能淘汰不那么差的键。我们的做法：结合采样和分桶，按计数范围分桶，采样时从一个桶里取，提高精度。压力测试表明，采样数从5提到10，命中率上升约2%，但CPU开销增加15%，需权衡。
陷阱三：多级缓存的一致性噩梦。 现在微服务架构，本地缓存+分布式缓存是标配。淘汰策略如何协调？本地淘汰不及时，会读到脏数据。我们起初用简单过期时间同步，结果一次网络抖动，本地缓存过期了，远端没更新，老数据又被加载回本地，循环污染。后来上了基于发布/订阅的失效机制：远端变更时广播失效消息，本地监听并标记删除。但消息可能丢失，所以加上定期全量校验和版本号。这中间的复杂性，真不是一篇文章能讲完的。
为什么说淘汰是门权衡的艺术
没有银弹。访问模式千变万化，你需要在命中率、内存开销、CPU成本、实现复杂度之间走钢丝。去年我们做过一次全面对比，用生产流量快照重放，结果如下：在QPS 10万、容量100万key的场景下，LRU命中率68%，CPU 5%；LFU命中率78%，CPU 9%；W-TinyLFU命中率91%，CPU 12%。但W-TinyLFU的代码维护成本高出两个数量级。所以，技术选型得看你的场景到底是不是真的需要那么高的命中率，以及团队能否hold住。千万別为了技术而技术。
好了，一口气说了这么多。缓存淘汰这件事，越是深入研究，越发现它像一门微妙的艺术，数字和直觉缺一不可。回想那次事故，如果早点理解这些，可能就不用熬夜背锅了——不过，谁不是在故障中成长的呢？
