缓存淘汰算法的系统化认知：预读失效 + 缓存污染 + 冷热分离 + LFU / W-TinyLFU
预读失效和缓存污染是任何高速缓存系统（Page Cache、Redis、MySQL Buffer Pool）在追求极致性能时必然会遭遇的两大"致命内伤"。根源全在于传统的 LRU 算法过于天真——它认为"只要一个数据刚刚被访问过，它就是最重要的"。
第一层：预读失效（Read-Ahead Failure）
为什么会有"预读"——空间局部性原理
计算机观察到：你读了磁盘第 1 页，接下来高概率会接着读第 2 页、第 3 页。于是操作系统和数据库偷偷帮你提前加载相邻的数据页进 Cache，这就是预读机制。
什么是"预读失效"
那些被顺手捎带进来的第 2、3 页，直到在缓存里躺到过期被踢走，代码也从来没有真正读过它们一次。
为什么成了致命灾难
传统 LRU 的弱智表现：预读垃圾页一进缓存就被塞到了 LRU 链表头部（热端），把真正高频访问的热点数据硬生生挤出了缓存。缓存命中率瞬间暴跌，RT 飙升。
第二层：缓存污染（Cache Pollution）
什么是"缓存污染"
全表扫描、大文件批量拷贝、或者恶意刷榜攻击时，大批只会被访问一次的冷数据瞬间涌入缓存，把整个 Cache 塞满。
为什么传统 LRU 扛不住
它只看"近况"，不看"频率"：
- 变量 A：过去 1 年每天被访问 1 万次（大热点），但最近 5 秒没人理
- 变量 B：从未被访问过（极冷），但刚刚因为全表扫描被读了 1 次
传统 LRU 眼里，变量 B 的地位瞬间超越变量 A——B 被捧到链表头部，真正的热点 A 被踢出内存。全表扫描结束后，B 再也没人访问，而 A 却因为被踢回了磁盘，后续成千上万的业务请求不得不去慢吞吞地直连磁盘，系统性能大崩盘。
第三层：工业级终极解法一——冷热分离（MySQL Buffer Pool + Linux Page Cache）
传统的单链表 LRU 溃不成军。Linux 内核和 MySQL 统一签署了目前最高效的解法：将缓存链表物理切割为冷热两段。
MySQL Buffer Pool 的改进版 LRU
按大约 63:37 的黄金比例，把缓存链表切成两段：
┌──────────────────────────────┬──────────────────────┐
│ Young 区域 (63%) │ Old 区域 (37%) │
│ ⭐ 热点数据大本营 │ 冷数据停尸房 │
└──────────────────────────────┴──────────────────────┘
怎么秒杀"预读失效"？
无论是正常读取还是预读进来的数据，一律不准直接进 Young 区，全员老老实实先丢进 Old 区头部。如果预读数据真的失效了（代码不来读），它只是在 Old 区内部慢慢往后挪，最后从尾部悄悄溜走。热点数据安如泰山。
怎么秒杀"缓存污染"？
MySQL 加了一道极为严苛的 防刷时间审查线（参数 innodb_old_blocks_time，默认 1 秒）：
数据想从 Old 区升级到 Young 区 ⇒ 两次访问的时间间隔 > 1 秒
- 全表扫描的冷数据：1 毫秒内读完，后续再也没人理它。访问间隔远小于 1 秒，被死死扣在 Old 区，绝不放行
- 真正的热点数据：第 1 秒读了它，第 5 秒又读了它（间隔大于 1 秒），顺利通过审查，升级进入 Young 区
Linux Page Cache 的双链机制
Linux 内核的实现思路完全一致，但用了两条链表：
- active_list：存放热点页，存疑不轻易换出
- inactive_list：存放冷数据页，新数据先放这里
关键规则：页在 inactive_list 后被第二次访问，才升级到 active_list。一次性的冷数据永远卡在 inactive_list 里，不影响热点。
第三层补充：Clock 算法——不用链表的 LRU 替代品
在操作系统内核（如 Linux 早期版本）和一些嵌入式场景中，维护 LRU 链表代价太高。Clock 算法（又称 Second Chance）用环形缓冲区 + 一个标志位来近似 LRU。
┌───┐
┌───►│ 0 │◄───┐
│ ├───┤ │
│ │ 1 │ │
│ ├───┤ │
│ │ 0 │ │
│ ├───┤ │
│ │ 1 │ │
│ ├───┤ │
└────┤ 0 │────┘ ← 时针指针
└───┘
算法：时钟指针循环扫描每个页。如果标志位为 1（最近被访问过），置为 0 并跳过；如果标志位为 0，选中淘汰。
优劣：
- ✅ 不需要链表，内存开销小，适合内核
- ❌ 近似 LRU 而非精确 LRU，换出精准度不如真 LRU
第四层：工业级终极解法二——LFU 与 W-TinyLFU
面对缓存污染，一些系统甚至不再用 LRU，升级到了 LFU（Least Frequently Used）。
LFU 的降维打击：自带计数器
LFU 在每个 Entry 旁边带一个访问计数器：
| 数据 | 计数器 | 表现 |
|---|---|---|
| 刚扫进来的冷数据 | 1 | 内存满时闭眼扔掉 ✅ |
| 历史热点数据 | 9999 | 最近几秒没人读也稳稳留下 ✅ |
从根本上杜绝了缓存污染。
Redis 的 LFU：Morris Counter（对数计数器）
Redis 支持 volatile-lfu 和 allkeys-lfu 淘汰策略。但它的计数器不是普通的 int——如果直接存 int，数千个 Key 的内存开销太大了。
Redis 用 Morris Counter（近似计数器）：
普通计数器：每访问一次，+1 → 9999 需要 14 bit
Morris 计数器：以对数概率递增 → 极大的频率值只需要几个 bit
访问次数越多，+1 的概率越低
效果：用 8 bit（一个字节）就能覆盖到数百万级别的访问频率。精度有折损，但实际效果足够好。
Caffeine 的 W-TinyLFU：Count-Min Sketch
W-TinyLFU 是目前 Java 生态里公认的最强本地缓存算法（Caffeine 框架的核心）。
它动用了 Count-Min Sketch——一种类似于布隆过滤器的概率数据结构：
多个哈希函数同时写入
Key ──→ h1() ──→ 计数器矩阵 [0][i] += 1
├─→ h2() ──→ [1][j] += 1
└─→ h3() ──→ [2][k] += 1
特点：
- 用极小的内存（几个 bit）估算海量 Key 的访问频率
- 读频率时取多个哈希位置的最小值，近似精度极高
- 新数据如果频率 PK 不过老热点，连缓存的大门都进不来（准入策略）
Caffeine 还结合了 Window LRU（小块窗口区记录最近刚访问的数据，防止 LFU 对新数据过于苛刻），形成了 Window-TinyLFU 的完整闭环。
进阶讨论：OS Page Cache 与 MySQL Buffer Pool 的双缓冲问题
一个经典的大厂调优问题：MySQL 既用 OS Page Cache，又用自己的 Buffer Pool，会不会造成数据存两份？
双缓冲问题的由来
MySQL 进程
┌──────────────────────┐
│ Buffer Pool (LRU) │ ← 自己管理 4KB/16KB 页
└──────────┬───────────┘
│ read() / write() 系统调用
▼
┌──────────────────────┐
│ OS Page Cache (LRU) │ ← 内核自动缓存
└──────────┬───────────┘
│ 磁盘 I/O
▼
┌──────────────────────┐
│ 磁盘 │
└──────────────────────┘
一份数据在内存里存了两份，浪费内存。大厂优化方案：
O_DIRECT绕过 OS Page Cache（MySQL 可配置innodb_flush_method = O_DIRECT）：MySQL 自己管理缓存，不经过 OS Page Cache，节省一层内存- 但不全用：
O_DIRECT禁用后，OS 预读优化失效。大厂通常折中——数据文件用O_DIRECT，日志文件不用
🏁 你建立起的缓存淘汰系统化认知
- 预读失效：顺手捎带的垃圾抢占热点位置 → 解法：放冷端自生自灭
- 缓存污染：批量冷数据冲垮历史热点 → 解法：冷热物理隔离 + 访问间隔审查 / LFU 频率计数
- 冷热分离：MySQL 63:37 Young/Old +
innodb_old_blocks_time1 秒防线；Linux inactive/active 双链 - LFU 降维：Redis Morris Counter（8 bit 对数计数器）/ Caffeine W-TinyLFU（Count-Min Sketch + Window 窗口）
- Clock 算法：环形缓冲区 + 标志位近似 LRU，内核场景的轻量替代
- 双缓冲问题：MySQL Buffer Pool + OS Page Cache 可能存两份，
O_DIRECT绕过后节省内存但丢失 OS 预读
评论
发表评论