W-TinyLFU 与 Caffeine 深度实战：从 LRU 的扫描免疫性缺陷到频率草图准入的在线替换工程
执行摘要：大多数团队把缓存命中率问题当作"调容量"问题，实际上它是一个在线替换决策问题。LRU 用"最近最久未用"这一个比特的瞬时信息做决策，被一次全表扫描就能冲垮；LFU 用历史频率做决策，却又被"一次性热点"永久占据。W-TinyLFU 的解法很反直觉：频率不用来挑选淘汰谁，而是用来决定"新来的有没有资格进来"——用一个 4-bit 的 Count-Min Sketch 做准入法官，配一个只占 1% 的小 LRU 窗口承接突发。本文拆解 TinyLFU 的草图数学、W-TinyLFU 的三段式结构、Hill Climbing 自适应，以及 Caffeine 如何用 striped ring buffer 和分层时间轮把这些理论变成纳秒级无锁实现，并给出可运行的代码。
一、先说清楚 LRU 到底错在哪
LRU 的问题不是一个，是三个，而且互相叠加。
第一，扫描免疫性（scan resistance）缺失。 一个 10000 条目的缓存，跑一次 20000 行的批量导出，缓存里剩下的全是导出数据，真正的热数据被全部挤走。LRU 认为"刚被访问过 = 有价值"，但批量扫描的每次访问都是一次性访问，这个假设在扫描负载下完全失效。
第二，只用了 1 比特信息。 LRU 的排序键是"上次访问时间"，一个连续量被压缩成了顺序；它完全丢弃了"这个 key 被访问过多少次"。理论上 LRU 是 LRU-2（用倒数第二次访问时间排序）的劣质近似，而 LRU-2 又只是 LFU 的近似。
第三，无法区分长尾。 在 Zipf 分布（绝大多数真实业务访问的分布形态）下，LRU 的命中率随容量增长曲线非常平缓，而 LFU 类策略能逼近 Belady 最优（淘汰未来最远才用到的）的 90% 以上。
那 LFU 是不是答案？也不是。经典 LFU 有两个硬伤：一是历史污染——去年双十一爆过的 key，今年还在缓存里占位，因为它的计数器永远很高；二是实现代价——精确 LFU 需要按频率排序的堆，每次访问 O(log n)，在百万 QPS 的缓存里完全不可接受。
二、TinyLFU：用 4-bit 草图换一个"够用"的频率
TinyLFU 的核心洞察是：准入决策不需要精确频率，只需要"谁更频繁"的相对判断。于是可以用概率数据结构把频率估计压到极致。
2.1 Count-Min Sketch 与它的 4-bit 计数器
TinyLFU 用 Count-Min Sketch（CMS）：一个 width × depth（如 4 × 行数）的二维数组，每行一个独立哈希。增加时 4 个位置各加一，查询时取 4 个位置的最小值——这是 CMS 的关键，取最小值能把哈希碰撞带来的高估压到可控范围。
真正让它"tiny"的是每个计数器只有 4 bit（最大值 15）。这带来两个必须处理的工程细节：
import hashlib
class FourBitCMS:
"""TinyLFU 频率草图：4-bit 计数器 + 定期 halving 的近似 LFU"""
MAX = 15
def __init__(self, width: int, depth: int = 4, seed: int = 0):
self.w, self.d = width, depth
self.seed = seed
self.table = bytearray(width * depth) # 每个 byte 存两个 4-bit 计数器
self.size = 0 # 已累加的条目数，用于触发 reset
self.sample_size = 10 * width # 采样/重置阈值
def _index(self, row: int, key: bytes) -> int:
h = hashlib.sha1(bytes([row, self.seed]) + key).digest()
return int.from_bytes(h[:8], "big") % self.w
def _get(self, row: int, idx: int) -> int:
b = self.table[row * self.w + idx]
return b >> 4 if idx & 1 else b & 0x0F
def _add(self, row: int, idx: int, delta: int):
off = row * self.w + (idx >> 1)
b = self.table[off]
if idx & 1:
v = min(self.MAX, (b >> 4) + delta)
self.table[off] = (b & 0x0F) | (v << 4)
else:
v = min(self.MAX, (b & 0x0F) + delta)
self.table[off] = (b & 0xF0) | v
def increment(self, key: bytes):
self.size += 1
for r in range(self.d):
self._add(r, self._index(r, key), 1)
if self.size >= self.sample_size:
self.reset()
def estimate(self, key: bytes) -> int:
return min(self._get(r, self._index(r, key)) for r in range(self.d))
def reset(self):
"""老化：全表减半，size 也减半。这是频率'遗忘'的唯一机制"""
for i in range(len(self.table)):
b = self.table[i]
self.table[i] = ((min(15, (b >> 4) >> 1)) << 4) | (min(15, (b & 0x0F)) >> 1)
self.size >>= 14-bit 上限的处理是 saturate 而不是 wrap。 计数到 15 就停住，靠 reset() 做老化：每当累加次数达到 10 × width 次，整个草图所有计数器减半（右移一位）。这就是频率的指数衰减——一个曾经爆热但现在冷掉的 key，经过几次 halving 后计数归零，自动让位。没有这个 reset，TinyLFU 就退化成带噪声的 LFU，历史污染问题原样回归。
宽度怎么定？ 经验公式是 width ≈ 预计缓存条目数 × 10，但更实用的做法是反推：CMS 的误差界是 ε = e/width，命中率损失大约与 1/width 同阶。Caffeine 的默认策略是让 sketch 占用约为缓存容量的内存开销，通常几十 KB 就能支撑百万级条目，误差带来的命中率损失 < 1%。
Doorkeeper：一个前置 Bloom filter。 Caffeine 在 CMS 前面加了一层 Bloom filter，只有已经出现过至少一次的 key 才会被写进 CMS。原因很实际：大量 key 只出现一次（one-hit wonder），把它们写进 CMS 会白白消耗计数器预算、放大碰撞噪声。Doorkeeper 用 1 bit/entry 拦掉这批"首次访问"，CMS 只记录"至少见过两次"的 key，命中率估计的信噪比大幅提升。
三、W-TinyLFU：让频率做"准入官"，而不是"刽子手"
这是整个设计里最精妙的一步。直觉上大家会想：用频率决定淘汰谁。但 W-TinyLFU 反过来——淘汰仍由 LRU 家族负责，频率只决定"新候选者能不能进来"。
结构分三段：
┌─────────────┐
新访问 ──────▶ │ Window LRU │ ~1% 容量，纯 LRU，承接突发流量
└──────┬──────┘
│ 被 Window 淘汰的候选者
▼
┌────────────────────┐
│ TinyLFU 准入判定 │ est(new) vs est(victim)
└─────────┬──────────┘
│ 新条目胜出才准入
┌───────────────┴───────────────┐
▼ ▼
┌─────────────┐ ┌─────────────┐
│ Probation │ ~20% │ Protected │ ~80%
│ (SLRU) │ ──再次命中────▶ │ (SLRU) │
└─────────────┘ ◀──被淘汰────── └─────────────┘- Window（窗口区，约 1%）：一个极小的纯 LRU。所有新 key 先落这里。它的作用是给突发流量一个短期避风港——一个新热点刚出现时频率计数还是 0，如果直接跟老条目比频率必输；Window 给它几次"免费访问"的机会把计数刷上来。
- Main（主区，约 99%）：SLRU（Segmented LRU）结构，分 Protected（80%）和 Probation（20%）。Probation 里的条目再被命中一次就晋升到 Protected；Protected 满了就把最老的降回 Probation 尾部。SLRU 保证一个"周期性但不频繁"的 key 不会挤掉"持续高频"的 key。
- TinyLFU 判定：Window 淘汰出的候选者 vs Main 的淘汰候选者（Probation 尾部），比较
estimate()频率，胜者留下。注意这个比较是概率性的——Caffeine 在频率相等时会用随机化打破平局，避免草图噪声造成的系统性偏差。
def admit(candidate_key, victim_key, sketch) -> bool:
"""W-TinyLFU 准入判定：频率比较 + 平局随机化"""
c, v = sketch.estimate(candidate_key), sketch.estimate(victim_key)
if c > v:
return True
if c < v:
return False
return random.random() < 0.5 # 抗草图噪声3.1 Hill Climbing：window 大小不该是常量
1% 还是 20%？这取决于负载形态：Zipf 分布越陡（如 CDN、商品详情），窗口应该越小，因为频率信号很可靠；分布越平坦（如社交 timeline、搜索），窗口应该越大，因为"新近性"才是主要信号。
Hill Climbing 的做法是把 window/max 比例当成待优化参数：每隔一定采样量（如 10000 次访问）统计一次命中率，若命中率上升则沿当前方向继续调整 window（并加大步长），若下降则反向（并减小步长）。这是一个不需要人工调参、能随负载漂移自适应的一维爬山。生产上很实用：大促期间负载形态突变，缓存策略能自己跟着变。
四、Caffeine：把理论做成纳秒级无锁的 Java 实现
Caffeine（Java 8+ 的高性能缓存库，Spring Boot 默认）是 W-TinyLFU 的生产级实现，也是它真正"落地"的原因。几个关键工程决策值得单独说：
1）读写用 striped ring buffer 削峰。 如果每次 get() 都直接更新 CMS（4 次哈希 + 4 次写），热点 key 上会产生严重的 cache line 争用。Caffeine 的做法是：读操作只往一个 striped ring buffer（默认 128 字节 × N 条带）里追加一条记录，写操作往另一个 buffer 里追加，由后台（或触发阈值的那个线程）异步批量 drain 到 CMS。这把随机写变成了顺序 append，多核扩展性从"锁竞争"变成"几乎无竞争"。代价是频率估计有短暂延迟——一个刚爆发的 key 可能在几十毫秒内频率还没刷上来，这正是 Window LRU 存在的意义，两者互补。
2）过期用分层时间轮，不是优先队列。 expireAfterWrite / expireAfterAccess 如果用 PriorityQueue，每次访问都要 O(log n) 调整。Caffeine 用 TimerWheel（分层哈希时间轮）：按 1.07s / 1.1min / 1.7h / 1.2day / 1.7year 分五层，每层若干桶，条目按过期时间挂桶，推进时 O(1) 摘桶。配合惰性清理（在读写路径上顺手检查）+ 定期推进，实际开销接近零。
3）淘汰与过期异步化。 淘汰动作（写 CMS、调 eviction listener、可能触发 CacheLoader 回调）全部丢给 ForkJoinPool.commonPool() 或配置的 executor，不阻塞调用线程。这也是为什么 Caffeine 的 hit rate 在高并发下几乎不掉。
4）CaffeineSpec 字符串配置 + recordStats。 生产上建议始终打开统计并接入监控：
Cache<String, Order> cache = Caffeine.newBuilder()
.maximumSize(500_000) // 触发 W-TinyLFU 的容量约束
.expireAfterWrite(Duration.ofMinutes(10))
.refreshAfterWrite(Duration.ofMinutes(1)) // 异步刷新，避免雪崩
.recordStats() // 命中率/加载时间/淘汰数
.executor(ThreadPoolTaskExecutor 或专用 executor)
.removalListener((k, v, cause) -> metrics.inc("cache.evict." + cause))
.build(key -> orderRepo.load(key));
// 观测：命中率低于 0.8 通常意味着容量不足或负载形态已变
double hitRate = cache.stats().hitRate();5）用 refreshAfterWrite 而不是全靠 expireAfterWrite。 前者在条目过期后仍返回旧值、异步触发 reload，避免缓存击穿；后者会把请求打到 DB。对允许短暂陈旧的数据（商品库存以外的多数读场景），这是硬要求。
五、对照与边界：什么时候别用 W-TinyLFU
- 对比 Redis：Redis 的
maxmemory-policy里allkeys-lru是采样 LRU（默认取 5 个样本，3.0+ 有 16 样本候选池），allkeys-lfu用 24-bit 中的 16-bit 存频率并带对数衰减（LFUDecayAndFetch）。它是近似实现，且淘汰池是全局共享的——单实例热点 key 的治理能力远弱于进程内 Caffeine。 - 对比 Linux MGLRU：页缓存面对的是"文件页 + 匿名页"的多代回收，用 generation + tier 扫描，解决的是 LRU 链表在 TB 级内存下的扫描成本问题，动机与 TinyLFU 不同但殊途同归——都是用更粗粒度的近似换可扩展性。
- 对比 ARC / LIRS：ARC（Adaptive Replacement Cache）用双队列自适应平衡 recency/frequency，命中率优秀但有专利历史、实现复杂；LIRS 用 IRR/HIR 双栈，命中率常优于 ARC。W-TinyLFU 的优势是内存开销与实现复杂度都更低，且有高质量开源实现。
W-TinyLFU 不适合的场景：缓存条目极小（< 100 条），此时 LRU 已经够用，草图的固定开销反而不划算；负载完全随机均匀（无局部性），任何策略都救不了；以及对过期精度要求到毫秒级的场景——时间轮的粒度是秒级的。
六、生产落地检查清单
- 先量化再优化：接
recordStats()，把hitRate、evictionCount、averageLoadPenalty打到 Prometheus。没有基线就调参是盲调。 - 容量按"工作集"而非"数据总量"设定：用 Zipf 估算，缓存 95% 命中率通常只需要覆盖工作集的 20%~30%。
- 警惕启动预热污染：JIT 未warm-up、冷启动批量加载会灌进大量一次性 key。解决方式是加载时走
getAll批量接口、或临时提高 window 比例。 - key 设计影响草图精度：过长的 key 会增加哈希成本，建议固定长度哈希后的摘要作为缓存 key。
- 分层缓存要有"准入差异"：L1（进程内 Caffeine）用 W-TinyLFU，L2（Redis）用 LFU，两层策略刻意错开，避免同样的淘汰逻辑造成"同频共振"式雪崩。
七、结语
缓存替换算法的演进，本质上是一场用有损近似换取可扩展性的工程实践：从精确 LRU 链表（O(1) 但无扫描免疫），到采样 LRU（可扩展但更不准），到 TinyLFU 用 4-bit 草图把频率压缩到每条目几个 bit，再到 W-TinyLFU 用"频率判准入 + LRU 判淘汰"的分工把两者的优点拼起来。
真正值得带走的不是某个参数，而是这个思路：当一个信号不可靠时，不要用它做最终决策，用它做准入筛选。 频率估计是概率性的、会错的，那就不让它直接淘汰谁，而只让它否决"明显不该进来的"。这个设计哲学，在限流、调度、甚至模型路由里都能看到同样的影子。
发表评论 取消回复