缓存替换策略
更新时间：2026-10-24。缓存满了要踢掉一行，替换策略直接决定命中率；它在 相联映射 之上发挥作用——组相联缓存里，一路空位都没有时才轮得到替换策略出场。
本篇是缓存簇里讲「缓存满了怎么办」的一篇。同簇的 MESI 讲多核之间副本怎么保持一致，本篇讲单核（或共享 LLC）内部空间有限时怎么取舍；写完一行之后脏数据怎么办，见 写策略 write-back。
本文要回答的问题
- LRU 不是最优吗，为什么真实硬件很少用真 LRU？
- 伪 LRU（树位/CLOCK）是怎么用几个比特近似出 LRU 效果的？
- 扫描/流式访问为什么能让 LRU 完全失效？
- RRIP、ARC 这类现代策略解决了什么问题？
- 怎么实测命中率来给自己的负载选策略？
一、替换策略管什么：组相联里的「踢谁」问题
先回忆一下场景。一个 4 路组相联缓存，每组 4 个 way，每路一条 64B 的缓存行。某个新地址映射到组 3，而组 3 的 4 路全满——这时缓存控制器必须做一个决定：踢掉哪一路，给新行腾位置。这个决定就是替换策略（replacement policy）。
读这张图只要盯住一件事：替换决策发生在组内，候选永远只有本组的 N 路（这里是 4 个），不是在整个缓存里挑。所以「踢谁」的信息量其实很小——4 路里选 1 路，理论上 2 比特就够编码一次决策；难的是「怎么知道谁最久没用」这件需要持续记账的事。
踢错代价很直接：被踢的行如果马上又要用，就是一次本可避免的缓存缺失（miss），代价是从 L2/LLC/内存重新取一行，几十到几百个周期。替换策略的全部意义，就是用尽量便宜的硬件，把「踢错」的概率压到尽量低。
二、真 LRU：直觉最优，硬件最贵
LRU（Least Recently Used，最近最少使用）踢掉组内最久没被访问的那一路。它的直觉依据是时间局部性：最近用过的很可能马上再用，最久没用的多半也不会再用了。
问题是硬件实现。N 路组相联要维护一个「使用顺序」，每次命中都要把被命中的路提到「最新」位置：
| 路数 N | 每组的排序状态数 | 精确 LRU 所需位数 |
|---|---|---|
| 2 | 2 | 1 bit |
| 4 | 24 | 5 bit |
| 8 | 40320 | 15 bit |
| 16 | 约 2×10¹³ | 44 bit |
这张表说明为什么真 LRU 在 8 路以上基本绝迹：16 路每组要 44 比特的排序状态，而且每次访问都要组合逻辑重排——面积大、延迟高，还高频率触发。L1 常为 4-8 路、LLC 动辄 12-16 路，真 LRU 在 LLC 上完全不可行。所以真实处理器里，「LRU」两个字几乎总是某种近似。
三、工程近似：伪 LRU、CLOCK 与随机
树位伪 LRU（tree-based pseudo-LRU）
伪 LRU 不记完整顺序，只记一棵二叉树上的「方向位」。4 路时把 4 个 way 排成一棵 3 节点二叉树，每个节点 1 bit，记录「左右两边哪边最近用过」。每次命中更新路径上的 3 个位；替换时从树根沿「较久未用」方向一路走到叶子，就是牺牲者。4 路只用 3 bit 而不是真 LRU 的 5 bit，8 路只用 7 bit 而不是 15 bit，而且更新是固定位翻转，不需要排序逻辑。
这张图按「位指旧」的约定读：根节点位 0 说左边子树较旧，于是往左走；位 1 说左子树里左边较旧，继续往左……最终落在 way 1。注意伪 LRU 不保证选中真正的最久未用者——它只能保证选中「某个比较旧的」。绝大多数负载下这个近似和真 LRU 的命中率差距在噪声范围内，这正是它被广泛采用的原因。
CLOCK（时钟算法）
CLOCK 给每路一个「引用位」：命中时置 1；替换时指针扫过组内各 way，遇到 1 就清 0 并跳过，遇到 0 就踢掉。本质是「给第二次机会」的 FIFO，每路只要 1 bit，硬件极简，OS 的页面置换也用它。
随机替换
干脆不记账，踢谁掷骰子。听起来离谱，但有两个实打实的优点：一是零状态、验证简单；二是没有最坏情况——任何确定性的策略都存在能把它打成 0% 命中率的对抗性访问序列，而随机策略的期望命中率只取决于工作集大小。部分 ARM 处理器的 LLC 就用随机或近似随机替换。
四、LRU 的命门：扫描与颠簸
LRU 一族（包括伪 LRU）有个结构性弱点：一次性扫描（scan）大于缓存的数组。
假设 LLC 8MB，程序顺序读一个 16MB 数组、每个元素只用一次。LRU 看到的行为是：每个新行都「刚刚被用过」，于是老老实实把它们全请进缓存，把原来驻留的、真正有复用价值的热行全部挤走。扫描结束后，缓存里躺着 8MB 再也不会被碰的扫描数据，热行却要重新从内存取——这就是缓存颠簸（thrash）的典型一幕。
图里的死结在于：LRU 只看「最近」，而扫描数据恰恰是「最近」的——它无法区分「最近用过且还会再用」与「最近用过但仅此一次」。数据库顺序扫描、大文件拷贝、视频流处理都是这类负载。
五、现代解法：RRIP 与自适应
针对这个命门，研究界和工业界各走了一条路：
- RRIP（Re-Reference Interval Prediction，再引用间隔预测）：给每行存一个 2-3 bit 的「再引用期望」。装入时默认标为「很久后才会再用」（远间隔），命中时才提升为「近期会再用」。替换时优先踢期望最低的行；扫描数据因为从不二次命中，期望始终最低，装进缓存后立刻成为头号牺牲品，热行因此安然无恙。Intel 的服务器 LLC 采用了 SRRIP/DRRIP 家族思路的变种。
- ARC（Adaptive Replacement Cache，自适应替换缓存）：同时维护「最近」和「频率」两个列表，外加两个 ghost 列表记录最近被踢走的行的地址——如果 ghost 列表频繁命中，说明踢错了，就动态调整两个列表的配比。不用调参、对扫描和突发都有韧性，ZFS 的缓存层是它的知名用户。
各策略横向对比：
| 策略 | 每组状态 | 抗扫描 | 最坏情况 | 典型应用 |
|---|---|---|---|---|
| 真 LRU | 多（随 N 阶乘涨） | 差 | 被对抗序列打穿 | 2-4 路低相联缓存 |
| 树位伪 LRU | 少（N-1 bit） | 差 | 同上 | L1/L2 |
| CLOCK | 1 bit/路 | 一般 | 同上 | 页面置换、简单缓存 |
| 随机 | 0 | 一般 | 无对抗序列 | 部分 LLC |
| RRIP 系 | 2-3 bit/路 | 好 | 较好 | Intel 服务器 LLC |
| ARC | 两列表+ghost | 好 | 自适应 | ZFS、数据库缓存 |
读这张表抓住一条主线：状态越省越便宜，但对「最近 vs 会再用」的区分能力越弱。从真 LRU 到 ARC 的演化，本质就是在「记账成本」和「识别扫描/复用结构的能力」之间找新的平衡点。
六、怎么给自己的负载选/验证策略
硬件替换策略焊死在芯片里，应用层改不了；但理解它能帮你做两件事：
- 解释性能数据：数据库做全表扫描后 OLTP 查询变慢，八成是扫描把热行挤出了 LLC；给扫描型任务用
madvise(MADV_DONTNEED)式的流式提示、或拆小批次处理，都是绕过替换策略弱点的工程手段。 - 自建缓存时选型：应用内缓存（页面缓存、对象缓存、CDN 边缘缓存）的替换策略是你自己写的——这时候上面的对比表就是选型表。有扫描负载就别用裸 LRU，上 CLOCK-Pro、ARC 或 2Q。
验证手段也很直接：perf stat -e cache-misses,cache-references 看命中率，改造前后各跑一次对照；命中率涨了、IPC 跟着涨，才算策略选对。
七、常见坑
- 以为所有缓存都用真 LRU。恰恰相反，真 LRU 只活在教科书和 2 路缓存里，LLC 里跑的是伪 LRU、随机或 RRIP 类近似。
- 忽略扫描型负载让 LRU 退化。一次全表扫描可能抹掉半小时积累的热缓存，事后「系统怎么突然慢了」的根因就在这。
- 脱离工作负载谈替换策略优劣。随机策略在对抗序列下吊打 LRU，LRU 在正常局部性负载下又优于随机——没有负载谈策略都是空对空。
这一篇在知识体系里的位置
本篇上接 相联映射（way 的概念从哪来）、缓存组织，下接 写策略 write-back（被踢出的脏行往哪写）。被替换策略踢出的行在多核场景还要经过 MESI 的一致性处理；应用层如何利用这些知识写出缓存友好的代码，见 cache-friendly-code。
总结
缓存满了踢谁直接决定命中率：理想 LRU 虽然直觉最优，但高相联下为每行维护顺序的硬件代价太贵，真实 LLC 多用伪 LRU（树位/CLOCK）或随机近似；而 LRU 一族对一次性扫描大数组会把有用行全部挤出（thrash），RRIP、ARC 等策略按「再引用期望」或自适应地保护复用行——没有脱离负载的最优策略，硬件策略焊死改不了，自建缓存则务必用自己工作集下的命中率实测来选型。