缓存淘汰算法

引言：“行李箱满载”问题

内存是昂贵的。你无法将所有内容都存入缓存（如 Redis、Memcached 或本地 RAM）。当你的“行李箱”满了，又有一个新项进来时，你必须决定扔掉哪个旧项。

缓存淘汰 (Cache Eviction) 就是做出这个决定的算法。一个好的算法会保留“热数据”（你很快就会用到的），并丢弃“冷数据”。

核心算法

1. LRU (最近最少使用)

• 逻辑： 扔掉那个最长时间没被访问过的项。
• 工作原理： 哈希表 + 双向链表。每次访问一个项，就把它移到链表头部。链表尾部的项就是待淘汰的牺牲品。
• 优点： 非常简单，适用于大多数基于“时间局部性”的场景。
• 缺点： 容易受“稀疏扫描”影响。如果一个脚本一次性读取了 100 万条旧数据，它会冲掉你原本频繁访问的所有热数据。

2. LFU (最不经常使用)

• 逻辑： 扔掉访问次数最少的项。
• 工作原理： 为每个项维护一个访问计数器。
• 优点： 适用于基于“频率”的场景（例如一个始终很受欢迎的静态首页）。
• 缺点： 实现 $O(1)$ 复杂度较难。而且，一个 1 小时前很火但现在已经没人看的项，可能会因为高计数而在缓存中“僵死”很久。

3. W-TinyLFU

• 逻辑： 一种混合方法，使用一个小型的“准入窗口”和一个类似布隆过滤器的 Sketch 来追蹤频率。
• 地位： 这是 Caffeine (Java) 和 Ristretto (Go) 使用的算法。它提供了接近完美的命中率，并且能有效抵抗稀疏扫描。

典型业务场景

• ✅ Session 存储： 使用 LRU。如果用户 30 分钟没动，淘汰他的 Session 是安全的。
• ✅ 商品目录： 使用 W-TinyLFU。有些商品是常青树（频率），有些则是当下的爆款（最近性）。
• ✅ 数据库缓冲池： MySQL 和 Postgres 使用改良版的 LRU（如 LRU-2），以防止全表扫描毁掉整个缓存。

性能与复杂度总结

• LRU： get 和 put 均为 $O(1)$。
• W-TinyLFU： 也是 $O(1)$，但需要更复杂的逻辑和频率估算器 (Count-Min Sketch)。

小结：一句话记住它

“LRU 是行业默认选择，因为它简单且快。但如果你的系统面临不可预测的流量激增或大范围扫描，请升级到 W-TinyLFU 以保持高缓存命中率。”