1 / 4概念
Replacement and Write Policy
组满之后必须有人离开,写操作则必须在缓存与下级之间选一条路径。替换策略决定“谁走”,写策略决定“走之前要不要先写下去”。两个选择共同决定未命中率、下级写流量与一致性协议的复杂度。
1 概念
1.1 一句话定义
替换策略在组内所有路都被占用时选择淘汰哪一路。写策略规定写命中与写未命中时,数据写入缓存、写入下级,还是两者都写。
1.2 它解决什么问题
- 空间有限:组数固定,新块进来必须有旧块出去。
- 保存近期性:留下更可能被再次访问的块,减少容量与冲突未命中。
- 控制写流量:写回把多次写合并成一次回写,直写则每次下发。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 相联度、组索引、行大小 | hw-cache-organization |
| 未命中分类、预取、非阻塞 | hw-misses-prefetch-blocking |
| 多级之间的包含与互斥 | hw-multilevel-inclusion |
| 一致性协议与内存序 | hw-cache-coherence、hw-memory-consistency |
| 虚拟内存的页替换策略 | Systems → Operating Systems |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| LRU | 淘汰最久未使用的块 | 不是“最少使用次数” |
| 树形伪 LRU | 用二叉树位近似近期性 | 不是真 LRU |
| RRIP | 用重引用预测值分级 | 不是 LRU 变体 |
| 脏位 | 标记块与下级不一致 | 不是有效位 |
| 写回 | 只在淘汰时写下级 | 不是“延迟写” |
| 写分配 | 写未命中先取块再写 | 不是“预取” |
2 机制
2.1 心智模型
替换策略回答“谁走”,写策略回答“走之前要不要先写下去”。 真 LRU 需要记录完整顺序,硬件代价高,所以主流实现用近似;写回省下级带宽但要求脏位,直写简单但放大写流量。
2.2 机制拆解
- 真 LRU:为每路维护访问顺序,N 路需要
log2(N!)位,8 路约 16 位,且每次命中都要更新。 - 树形伪 LRU:用 N-1 位记录二叉树方向,命中时翻转路径上的位,代价低且接近 LRU。
- NRU 与时钟:每路一位,定期清零,淘汰时从指针处扫描第一个未访问的块。
- 随机与 RRIP:随机不需要状态位;RRIP 每路两位,插入时设为最远、命中时清零,能抵抗一次性扫描。
- 写回:写命中只改缓存并置脏位,淘汰或失效时才写下级,多次写合并成一次回写。
- 直写:每次写都下发,用写缓冲吸收延迟。实现简单,但写流量与下级带宽成正比。
- 写分配:写未命中先取整块再改,配合写回使用;非写分配直接下发,适合整块写。
- 写合并与脏状态:把同一行的多次部分写合成一次传输;脏块在失效时必须写回或转交,这进入一致性协议的 M 状态。
2.3 完整枚举
| 替换策略 | 状态位 | 抗扫描 | 命中率 | 硬件代价 | 典型用途 |
|---|---|---|---|---|---|
| 真 LRU | log2(N!) 位 | 中 | 最高 | 高 | 小相联度、教学 |
| 树形伪 LRU | N-1 位 | 中 | 接近 LRU | 低 | 主流 L1、L2 |
| NRU 与时钟 | 每路 1 位 | 低 | 中 | 最低 | 早期处理器 |
| 随机 | 0 位 | 中 | 中 | 最低 | 末级缓存 |
| RRIP | 每路 2 位 | 高 | 接近 LRU | 低 | 大容量末级 |
| FIFO | 指针 | 无 | 较低 | 最低 | 简单控制器 |
| 写组合 | 写未命中 | 下级写流量 | 一致性复杂度 | 适用 |
|---|---|---|---|---|
| 写回加写分配 | 先取块再写 | 低 | 高 | 通用 L1 到 L3 |
| 写回加非写分配 | 直接下发 | 中 | 中 | 写少读多 |
| 直写加写分配 | 先取块再写 | 高 | 低 | 小容量一级缓存 |
| 直写加非写分配 | 直接下发 | 最高 | 最低 | 简单或共享结构 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 8 路真 LRU 状态 | 约 16 位 | 等于 log2(8!) |
| 8 路伪 LRU 状态 | 7 位 | 每级一个方向位 |
| 一次脏块回写 | 64 B | 等于一条缓存行 |
| 写缓冲深度 | 4–16 项 | 吸收突发写 |
| 直写写流量 | 约 2 倍 | 相对写回 |
| 抖动条件 | 工作集等于路数加一 | 循环访问时最明显 |
3 实践
3.1 最小示例
# LRU 有栈性质,FIFO 没有:同一条引用串,路数增加时 FIFO 反而更差。
refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
def misses(refs, ways, policy):
frames, faults = [], 0
for r in refs:
if r in frames:
if policy == 'lru':
frames.remove(r)
frames.append(r)
else:
faults += 1
if len(frames) == ways:
frames.pop(0)
frames.append(r)
return faults
print(misses(refs, 3, 'lru'), misses(refs, 4, 'lru')) # 10 与 8
print(misses(refs, 3, 'fifo'), misses(refs, 4, 'fifo')) # 9 与 10
LRU 增加一路不会让未命中变多,这是栈性质。FIFO 出现 9 到 10 的反常,说明“更多容量一定更好”只对栈算法成立。
3.2 常用操作与参数
| 操作 | 命令 | 说明 |
|---|---|---|
| 看写未命中 | perf stat -e LLC-stores,LLC-store-misses | 写路径的下级流量 |
| 看读写比例 | perf stat -e mem_inst_retired.all_stores | 判断写是否主导 |
| 逐访存归因 | perf mem report | 区分加载与存储 |
| 持久化顺序 | clwb 加 sfence | 保证掉电一致性 |
| 非临时写 | movntdq、__builtin_nontemporal_store | 绕过缓存减少污染 |
3.3 标准流程
- 先用
perf stat判断热点是读为主还是写为主。 - 看写未命中与回写量,判断直写还是写回更合适。
- 检查工作集是否等于相联度加一,排除抖动。
- 选定策略后只改一个变量,复测未命中与写流量。
3.4 与相邻技术的组合
- 一致性:写回产生脏块,失效时必须写回或转交,M 状态由此而来。
- 持久内存:写回缓存加
clwb与sfence才能保证掉电后的顺序。 - 存储:写合并与顺序写能显著减少 SSD 的写放大。
3.5 选型维度
| 负载 | 替换策略 | 写策略 | 原因 |
|---|---|---|---|
| 通用服务 | 伪 LRU | 写回加写分配 | 命中率与带宽折中 |
| 流式扫描 | RRIP 或随机 | 写回加非写分配 | 抗污染,减少读改写 |
| 写密集日志 | 伪 LRU | 写回加写合并 | 合并部分写 |
| 掉电敏感 | 伪 LRU | 写回加显式刷新 | 顺序可验证 |
3.6 决策规则
- 通用缓存宜用伪 LRU 加写回加写分配。
- 一次性扫描占主导时,宜用 RRIP 或随机替换,保护常用块。
- 写流量已经是瓶颈时,应改直写为写回,或加写合并。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 真 LRU | 命中率最高 | 状态位与更新开销 | 小相联度 |
| 伪 LRU | 接近 LRU、便宜 | 近似误差 | 主流缓存 |
| 写回 | 下级写流量低 | 脏位与回写路径 | 通用 |
| 直写 | 实现简单 | 写流量翻倍 | 小缓存、共享结构 |
3.8 何时不该用
- 工作集远小于缓存且无冲突时,替换策略几乎不影响结果。
- 需要强持久性时,不要依赖缓存层的写回,必须显式刷新。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 写带宽突然翻倍 | 直写遇到写密集负载 | 改写回或加写合并 |
| 循环访问性能骤降 | 工作集等于路数加一 | 改分块或加相联 |
| 大数组扫描后命中率崩 | 缓存被一次性数据冲刷 | 用 RRIP 或非临时写 |
| 掉电后数据不一致 | 未刷新缓存或未屏障 | 补 clwb 与 sfence |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 用直写跑写密集负载 | 下级带宽被写满 | 写回加写合并 |
| 循环上界取相联度加一 | 每次访问都未命中 | 分块、改步长 |
| 持久化只写不刷新 | 掉电顺序不成立 | 刷新加屏障 |
4.3 可观测信号
perf stat 的 LLC-stores 与 LLC-store-misses;perf mem report 的存储指令归因;perf c2c 的伪共享与失效;cachegrind 的写未命中模拟;持久化路径上 clwb 的次数与延迟。
4.4 安全 / 性能 / 一致性边界
- 掉电一致性:写回缓存让“已写”不等于“已持久”,必须显式刷新。
- 数据残留:被替换的脏块仍留在缓存中,进程隔离依赖刷新与清零。
- 性能悬崖:抖动与扫描污染会让未命中率阶跃上升,而不是缓慢变差。