DIP/BIP 插入策略:缓存动态插入如何在扫描负载下保住 LRU 的命中率
承 cache-replacement-policies-lru 对 LRU 家族的介绍,以及 cache-pseudo-lru-tree 对硬件友好近似算法的拆解。LRU 的问题不在「最近最少使用」这个直觉本身,而在它无条件地信任每一次访问——一行刚被填进来就被推到 MRU(Most Recently Used,最近最多使用)位置,哪怕它这辈子只被读一次。DIP/BIP 插入策略要修的正是这个「插入端无条件抬升」的口子:新行先蹲在 LRU 端,证明自己有价值再往上爬。
本文要回答的问题
- DIP/BIP 插入策略相对 LRU 改了哪一步?为什么只动插入不动提升就能抗扫描?
- 扫描型负载(一次性流式访问)为什么能把 LRU 的命中率打到接近零?
- SDIP(Set Dueling Insertion Policy,组对决插入策略)怎么用少量组在线判定该用哪种策略?
- 什么时候该怀疑自己的负载正在被插入策略坑?能用什么手段验证?
一、LRU 的死穴:插入即 MRU
先回忆经典组相联缓存的完整替换流程:miss 发生时选一个牺牲行(LRU 端),新行填入,然后新行直接放到 MRU 位置。后续每次命中也把该行提升到 MRU。「提升」这步没问题,问题出在「插入」——硬件在填入那一刻对该行的未来一无所知,却给了它组内最长的居留许可。
用数字感受下这个偏袒有多离谱。假设 LLC 某路工作集是 8 行,刚好填满一个 8 路组,LRU 下命中率接近 100%。现在混入一个流式扫描线程,顺序读一块 1 GB 的数组,每行只读一次。扫描行一个接一个地填进来,每个都坐上 MRU 宝座,把真正的 8 行工作集一路挤向 LRU 端并逐出。等下一轮循环再访问工作集时,8 行全没了——命中率从 100% 跌到接近 0,而扫描行自己贡献了 0 次命中(它们不会再被访问)。这就是经典的缓存抖动(thrashing):复用距离大于组容量的访问模式,LRU 一行都留不住。
更隐蔽的是介于两者之间的情况:工作集略大于容量,比如 9 行挤 8 路组。LRU 下每次访问都恰好踢掉下一个要用的行,命中率是刺眼的 0%;而随机替换反而能蒙中约 1/9。这类「LRU 比随机还差」的反直觉案例,在 cache-replacement-policies-lru 里有完整的访问序列推演。
二、BIP:新行先蹲 LRU 端
双峰插入策略(Bimodal Insertion Policy)的修改极小但精准:插入时不再无条件放 MRU,而是以大概率(比如 31/32)放到 LRU 端,以小概率(1/32)仍放 MRU——这就是「双峰」的来历,插入位置只在两个极端之间掷硬币,没有中间态。
direction: down
fill: "miss 发生\n新行填入"
lru: "LRU 策略\n插入即 MRU"
bip: "BIP 策略\n31/32 插 LRU 端"
bip_rare: "1/32 插 MRU\n(防新行全被秒杀)"
promote: "命中行提升到 MRU\n(两种策略相同)"
survive: "工作集行\n靠命中爬回 MRU"
evict: "一次性扫描行\n下次 miss 即被踢"
fill -> lru
fill -> bip
bip -> bip_rare: 小概率
lru -> promote
bip -> promote
promote -> survive: 有复用的行
bip -> evict: 无复用的行
fill.style: { fill: "#EAF2FE"; stroke: "#3B6FD4" }
lru.style: { fill: "#FDECEC"; stroke: "#D9534F" }
bip.style: { fill: "#E9F8F0"; stroke: "#2E9E6B" }
bip_rare.style: { fill: "#F4F6FA"; stroke: "#5B6B8C" }
promote.style: { fill: "#EAF2FE"; stroke: "#3B6FD4" }
survive.style: { fill: "#E9F8F0"; stroke: "#2E9E6B" }
evict.style: { fill: "#FDECEC"; stroke: "#D9534F" }上图的关键对照在下半截:提升机制两策略完全一致,差别全在插入位置。一行扫描数据在 BIP 下被插到 LRU 端,下一次 miss 需要牺牲行时它就是第一个候选——它在组里只占一个位置、只挡一次路,而不是像 LRU 那样一路从 MRU 慢慢沉底、沿途把所有正经行都顶出去。8 路组里 LRU 下一个扫描行能「祸害」8 次替换决策,BIP 下只祸害 1 次。同时保留 1/32 的 MRU 插入是防止矫枉过正:如果新行其实有复用价值,总得给它一条活路,靠后续命中提升回来也行,但纯 LRU 端插入会让「首次填充后立刻又被访问」的短间隔复用白白 miss 一次。
效果有多明显?Qureshi 等人 2007 年提出 DIP 的原论文(ISCA'07,《Adaptive Insertion Policies for High Performance Caching》)里,对 scan 主导负载,LIP(LRU Insertion Policy,BIP 退掉随机性的纯形态)相对 LRU 能把 miss 数砍掉一半以上;在 2 MB LLC、流式混部场景下,非流式应用的 IPC 提升常见 20% 量级。代价几乎为零:改动只在替换状态更新逻辑,不加存储、不加查找路径。
三、DIP/SDIP:让硬件自己投票
BIP 治好了扫描,但反过来问:如果负载根本没有扫描、就是规规矩矩的小工作集循环呢?这时 LRU 的插入即 MRU 反而是对的,BIP 会白送掉「插入后马上复用」的那批命中。谁也没法在硬件出厂时预判负载——所以有了动态插入策略(Dynamic Insertion Policy):在 LRU 与 BIP/LIP 两种插入方式之间运行时切换。
切换的依据来自 SDIP 的「组对决(set dueling)」机制,思路朴素得像 A/B 测试:
机制的要点是只花 64 个组的代价做全缓存的探测:按组索引的低位挑两小撮 follower set,各钉死一种策略;哪边的 follower 老在 miss,说明哪种策略不适合当前负载,就往 10 位饱和计数器 PSEL(Policy Selector)上记一笔反向票。主力组看 PSEL 的符号位站队,负载相位一换(比如从循环计算切到日志刷盘),几千次 miss 之后投票就翻过来了。因为 follower 与主力组经历的是同一份地址流的哈希,它们的 miss 率对比对全缓存有足够代表性——这是「对决」成立的统计学前提。
四、三种策略的行为对比
| 维度 | LRU | BIP | DIP/SDIP |
|---|---|---|---|
| 插入位置 | 恒 MRU | 31/32 LRU 端 + 1/32 MRU | 运行时二选一 |
| 扫描负载命中率 | 接近 0 | 接近工作集上限 | 接近工作集上限 |
| 小工作集循环 | 最优 | 略损(白送首次复用 miss) | 自动退回 LRU |
| 额外存储 | 无 | 一个 5 位随机数 | 64 组标记 + 10 位 PSEL |
| 相位切换适应 | 不适用 | 不适用 | 数千次 miss 内翻转 |
| 现实芯片采用 | 罕见(成本) | 作为组件 | Intel 自 Sandy Bridge 起 LLC 采用类 SDIP 自适应策略 |
表里最后一行值得展开:Intel 从不公开 LLC 替换策略的细节,但大量逆向研究(通过精心构造的驱逐集与访问序列测 miss 行为)表明,Sandy Bridge 之后的服务器 LLC 既不是纯 LRU 也不是纯随机,而是带自适应插入的近似策略,行为特征与 SDIP 高度吻合——扫描负载下新行被快速踢出、工作集行岿然不动。换句话说,你今天跑的至强服务器里,DIP/BIP 插入策略的思想就在 LLC 里默默值班。
五、什么负载受益,什么时候怀疑它
受益最明显的是混部与多相位负载:一个内存流式任务(视频转码、日志扫描、大表全扫)和延迟敏感任务共享 LLC 时,DIP 能把后者的命中率从「被拖下水」救回接近独享水平。纯流式的 spec mcf、libquantum 一类负载也是传统重灾区。
反过来,单线程小工作集的 HPC 内层循环基本无感——工作集装得下,插入策略无所谓。还有一种情况 DIP 也救不了:工作集本身就大于 LLC 且复用距离均匀,比如大规模随机哈希表探测,这时任何插入策略的命中率都贴着容量上限,只能靠 cache-partitioning-cat 这类路级划分做硬隔离。
想验证自己的机器是不是「类 DIP」行为,有个简单的实验套路:写一个指针追踪(pointer chasing)循环,工作集设为 LLC 的 2 倍,先纯跑测一次 miss 率基线;再并发一个 4 倍 LLC 大小的顺序扫描线程,重测。如果目标循环的 miss 率几乎不动,说明新行被插到了 LRU 端、硬件在做某种 BIP;如果 miss 率翻倍以上,则是插入即 MRU 的行为。配合 hardware-prefetcher-stride-stream 里介绍的预取器干扰一并观测,还能区分「替换策略踢的」与「预取顶掉的」两种污染来源。此外像 streaming-nt-load-store 的非临时访存指令(movnt 系列)本质上是软件侧对同一问题的回答:明知数据只写一次,就绕过缓存直接进内存,连插入的机会都不给它。
这一篇在知识体系里的位置
本篇是 LRU 家族讨论的延伸:基础算法见 cache-replacement-policies-lru,硬件近似实现见 cache-pseudo-lru-tree,DIP/BIP 插入策略回答的是「替换位置选定之后,新行该从哪端进场」这另一半问题。与之互补的隔离手段见 cache-partitioning-cat,软件侧绕开手段见 streaming-nt-load-store。
总结
DIP/BIP 插入策略的核心洞察是「LRU 的错不在替换而在插入」:BIP 让新行以 31/32 的概率从 LRU 端进场,把一次性扫描行的破坏半径从整个组压到一个位置;DIP/SDIP 再用 64 个 follower set 加一枚 10 位投票计数器做在线 A/B 测试,让缓存在 LRU 与 BIP 之间自动站队——这套思想正是现代服务器 LLC 在混部负载下不被流式扫描打穿的底层原因。