前言

最近在项目中用到了 Caffeine 本地缓存，虽然用起来很简单，但一直没搞懂它底层的 W-TinyLFU 淘汰机制到底是怎么工作的。网上看了很多文章，有的讲得太深奥，有的又太简略。经过一番学习和实践，我把自己踩过的坑和理解的过程整理出来，希望对大家有帮助。

特别说明：这篇文章会把我理解错的地方也写出来，因为我觉得错误的理解过程反而能帮助加深印象。

---

一、为什么需要 W-TinyLFU？

传统淘汰算法的缺陷

LRU（最近最少使用）的问题：

text

场景：偶尔批量查询历史数据
- 大量历史数据一次性涌入缓存
- 真正高频访问的热点数据被挤出去了
- 缓存命中率骤降

LFU（最不经常使用）的问题：

text

场景：双11活动商品
- 商品A：昨天被访问100万次（频率100万）
- 商品B：今天新上架（频率1）
- 用LFU：B永远进不来，因为A频率太高
- 问题：昨天的热点今天可能已经过时了

W-TinyLFU 就是为了解决这些问题而生的。

---

二、我一开始的理解（错误版本）

学习初期，我是这样理解 W-TinyLFU 的：

❌ 错误理解1：Window 区满了，淘汰访问频率最低的数据

❌ 错误理解2：频率超过阈值进入 Protected 区，把频率低的退回 Probation

相信很多初学者也会有同样的误解，后面我会纠正。

---

三、W-TinyLFU 的核心架构

名称拆解

部分	含义	作用
LFU	Least Frequently Used	淘汰低频数据
Tiny	Tiny memory	用极小内存统计频率
W	Window	窗口区，解决历史数据污染

三区架构（用停车场比喻）

把缓存想象成一个停车场：

text

┌─────────────────────────────────────────┐
│                停车场                    │
├─────────────────────────────────────────┤
│  [新车区]    [普通区]     [VIP区]        │
│  Window     Probation    Protected      │
│   10%         80%          10%          │
│                                         │
│  新车先停这   普通车位     高频车专属     │
└─────────────────────────────────────────┘

---

四、正确的数据流转过程

流程图

text

新数据到来
    ↓
┌────────────────────────────────────┐
│ 1. 进入 Window 区                   │
│    (新数据都先来这里)                │
└────────────────────────────────────┘
    ↓
┌────────────────────────────────────┐
│ Window 区满了？                     │
└────────────────────────────────────┘
    ↓ 是
┌────────────────────────────────────┐
│ 2. 淘汰 Window 区【最旧】的数据      │
│    ⚠️ 注意：不是频率最低！           │
│    被淘汰的数据 → 进入 Probation    │
└────────────────────────────────────┘
    ↓
┌────────────────────────────────────┐
│ 3. Probation 区满了？               │
└────────────────────────────────────┘
    ↓ 是
┌────────────────────────────────────┐
│ 4. 从 Probation 选出【频率最低】的   │
│    作为受害者(victim)               │
└────────────────────────────────────┘
    ↓
┌────────────────────────────────────┐
│ 5. 比较：新数据 vs 受害者            │
│    谁频率高谁留下                   │
│    频率低的【彻底淘汰】              │
└────────────────────────────────────┘
    ↓
┌────────────────────────────────────┐
│ 6. 晋升机制（访问时触发）            │
│    频率超阈值 → 进 Protected        │
│    Protected满 → 踢最低频回Probation│
└────────────────────────────────────┘

关键纠正

我的错误理解	正确逻辑
Window 区淘汰频率最低的	Window 区淘汰最旧的（FIFO）
Protected 区主动淘汰低频	Protected 区满了才踢人

---

五、详细示例演示

假设配置：总容量14，Window=2，Probation=10，Protected=2

步骤1：新数据进入 Window

text

新数据 A,B 到来
Window:  [A, B]     ← A最老，B最新
Probation: 空
Protected: 空

步骤2：Window 满，触发 FIFO 淘汰

text

新数据 C 到来，Window已满

1. 淘汰 Window 最老的 A（不是比频率！）
2. A 进入 Probation
3. C 进入 Window

Window:  [B, C]
Probation: [A]

步骤3：Probation 满，触发频率淘汰

假设 Probation 已满（10个位置）：

text

Probation: [A, D, E, F, G, H, I, J, K, L]

新数据 M 触发淘汰：
1. M 先占 Window，把最老的 X 挤到 Probation
2. Probation 满，需要腾位置
3. 从 Probation 选出频率最低的（假设 L 频率=2）
4. 比较 X(频率=1) vs L(频率=2)
   → X 频率低，X 被淘汰出缓存
   → L 留下

结果：L 幸存，X 彻底没了

步骤4：晋升到 Protected

text

数据 A 被频繁访问，频率达到阈值

Protected 区未满（有空位）：
→ A 直接进入 Protected ✅

Protected 区已满（2个位置）：
Protected: [A(100次), B(80次)]
数据 C(90次) 要晋升：
→ 比较频率，B(80)最低
→ B 被踢回 Probation
→ C 进入 Protected
Protected: [A(100), C(90)]

---

六、为什么 Window 区用 FIFO 而不是频率？

这是我踩过最大的坑，想明白后豁然开朗：

text

场景：秒杀活动
- 商品 A：昨天被访问100万次（频率超高）
- 商品 B：今天新上架（频率=1）

如果用频率淘汰：
B(频率1) vs Window 里任意数据(频率>1)
→ B 永远进不来！新数据没机会

用 FIFO：
B 直接进入 Window，老数据被挤出去
→ 新数据至少有机会展示自己

结论：Window 区存在的意义就是给新数据"试错机会"，所以用 FIFO。

---

七、为什么 Protected 区满了才踢人？

这是为了保护真正的高频数据：

text

Protected 区的作用：保护高频数据不被频繁干扰

如果没满：
    新晋升的数据直接进入，不用踢任何人

如果满了：
    必须踢一个最低频的，但被踢的数据回 Probation
    还有机会再回来（不像被淘汰就没了）

---

八、CountMin Sketch 频率统计

为什么不用 HashMap 存频率？

方案	内存占用	精度
HashMap<Key, Integer>	巨大（每个key都要存）	100%
CountMin Sketch	固定大小（几KB）	约99%

工作原理（简化版）

text

4个哈希函数，8个计数器：

添加 "user:1" 的访问：
h1 → 位置1: +1
h2 → 位置3: +1
h3 → 位置5: +1
h4 → 位置7: +1

查询 "user:1" 的频率：
取 min(位置1, 位置3, 位置5, 位置7)

特点：
✅ 固定内存
✅ O(1) 时间
✅ 可能高估，不会低估（影响可接受）

频率衰减机制

text

频率会定期减半，防止历史数据永久占位：

时间1: X 频率 = 1,000,000
时间2: 所有频率 ÷ 2 → X = 500,000
时间3: 所有频率 ÷ 2 → X = 250,000

只要 X 不再被访问，频率会不断衰减
新数据 Y 很容易超过 X

---

九、三区对比总结

区域	淘汰/踢出策略	进入条件	离开条件
Window	FIFO（淘汰最旧）	新数据	被挤出到 Probation
Probation	比频率（淘汰低频）	从 Window 来 / 从 Protected 被踢	被淘汰 / 晋升到 Protected
Protected	满了才踢最低频	从 Probation 晋升	被踢回 Probation

---

十、一句话记忆法

Window FIFO 往外挤，Probation 比频率淘汰，Protected 满了才踢人

---

十一、面试回答模板

如果面试官问 W-TinyLFU，我会这样回答：

"W-TinyLFU 是 Caffeine 的核心淘汰算法，把缓存分成三个区：Window、Probation、Protected。

新数据先进入 Window 区，Window 区满了按 FIFO 淘汰最老的数据到 Probation 区。

Probation 区满了需要腾位置时，从 Probation 选出频率最低的数据作为受害者，和新数据比较频率，低的被淘汰。

数据被频繁访问，频率超过阈值时晋升到 Protected 区。Protected 区只有满了才触发踢人，把最低频的踢回 Probation。

Window 用 FIFO 是为了给新数据试错机会，Protected 满了才踢是为了保护高频数据不被频繁干扰。频率统计用 CountMin Sketch，固定内存且会定期衰减，解决历史数据污染问题。"

---

十二、写在最后

学习 W-TinyLFU 的过程中，我发现自己一开始的理解有好几处错误：

• 以为 Window 区也按频率淘汰

• 以为 Protected 区会主动淘汰

这些错误理解反而让我对正确逻辑的印象更深刻。如果你也在学习这个算法，不妨先按自己的理解推演一遍，遇到矛盾再纠正，这样记忆会更牢固。

核心要点：

1. Window 区：FIFO，不是频率

2. Probation 区：比频率淘汰

3. Protected 区：满了才踢人

4. 频率用 CountMin Sketch 统计，会衰减

希望这篇文章能帮你少走弯路！