返回文章列表
Go / Cache精选
W-TinyLFU 缓存淘汰算法详解
深入解析 W-TinyLFU 准入策略的数学原理与工程实现，包含布隆过滤器、SLFU 和 LRU 的协同工作机制。
2026-05-0815 min
文章定位
面向生产环境的实战经验沉淀，适合拿来做方案评审、复盘和升级前检查。
阅读建议
先看标题和列表，再回到关键段落。技术文章更适合跳读和回查的阅读节奏。
适合场景
云原生、后端工程、系统设计、性能优化、故障处理和团队知识沉淀。
背景#
在缓存系统中，如何高效地淘汰低价值数据、保留热点数据是一个核心问题。W-TinyLFU（Window TinyLFU）是一种结合了 Least Recently Used（最近最少使用）和 Frequency Least Frequently Used（最不频繁使用）优点的准入策略。
核心公式#
1. 布隆过滤器（Bloom Filter）#
布隆过滤器用于快速判断一个 key 是否曾经被访问过。其假阳性率（False Positive Rate）为：
其中：
- — 已插入元素数量
- — 位数组长度
- — 哈希函数数量
最优哈希函数数量为：
k_\bgroup opt\egroup = \frac\bgroup m\egroup\bgroup n\egroup \ln 22. 频率计数（Frequency Counter）#
TinyLFU 使用 Count-Min Sketch 来估计访问频率：
f_\bgroup ij\egroup = f_\bgroup ij\egroup + 1 \quad \text\bgroup for all \egroup j \in h_i(x)其中 是 key 的第 个哈希值对应的计数器位置。
3. W-TinyLFU 窗口#
W-TinyLFU 将缓存分为两个区域：
- Window Cache：大小为总容量的
- Main Cache：剩余
4. 准入评分（Admission Score）#
当一个新 entry 需要进入 Main Cache 时，计算其准入评分：
S_\bgroup new\egroup = \frac\bgroup f_\bgroup new\egroup \egroup\bgroup \max_\bgroup old \in victim\egroup \egroup如果 ，则新 entry 准入，得分最低的 entry 被淘汰。
算法流程#
CODE
func (w *W TinyLFU) Admit(key string) bool {
// 1. 计算新 key 的频率
freq := w sketch.Estimate(key)
// 2. 找到 Main Cache 中得分最低的 entry
victim, victimScore := w.mainCache.EvictCandidate()
// 3. 比较准入评分
if freq > victimScore {
w.mainCache.Put(key)
return true
}
return false
}
性能分析#
W-TinyLFU 在 Stack Exchange 的 benchmark 中表现优异：
| 数据集 | 命中率 | 内存效率 |
|---|---|---|
| Zipf 0.99 | ||
| Zipf 0.95 | ||
| Uniform |
总结#
W-TinyLFU 通过布隆过滤器 + Count-Min Sketch 的组合，实现了 时间复杂度的频率估计，同时通过滑动窗口机制保护了短期热点数据。
\boxed\bgroup \text\bgroup Hit Rate\egroup \approx 1 - \frac\bgroup 1\egroup\bgroup 1 + \alpha \cdot \text\bgroup Zipf\egroup_\bgroup \lambda\egroup \egroup \egroup