离线缓存
概述
离线缓存（Offline Caching）是在已知完整请求序列的前提下，研究最优缓存淘汰策略的问题。它是分析在线缓存算法竞争比的理论基准，其最优解通过 Belady 策略实现。
定义
形式化定义
缓存问题（caching/paging problem）：
- 一个容量为 的高速缓存（cache），可存放 个页面
- 一个慢速存储（slow memory），包含 个页面
- 给定一个请求序列 ，每个 是一个页面
- 当请求的页面不在缓存中时，发生缓存未命中（cache miss），需要将该页面调入缓存；若缓存已满，必须淘汰（evict）一个页面
离线缓存：已知完整的请求序列 （即可以”预见未来”），目标是找到使缓存未命中次数最少的淘汰策略。
Belady 最优策略
Belady's Optimal Algorithm (Bélády, 1966)
在离线缓存问题中，最优策略为： 当缓存满且发生未命中时，淘汰在将来最晚被请求的页面（或永远不再被请求的页面）。
该策略也称为 MIN 策略或 OPT 策略。
直觉理解
淘汰”将来最晚使用”的页面等价于”尽量保留将来最需要”的页面。这就像收拾行李时，优先带上最近会用到的东西。
最优性证明（交换论证）
交换论证（Exchange Argument）
设 OPT 为 Belady 策略，ALG 为任意确定性策略。
证明思路：对请求序列 的长度 进行归纳，证明在每一步之后，都可以将 ALG 的缓存状态转化为与 OPT “至少一样好”的状态。
关键引理：考虑第 次请求 ：
- 若 OPT 和 ALG 都命中，无需操作
- 若 OPT 命中而 ALG 未命中：ALG 多了一次未命中，ALG 的状态变差
- 若 OPT 未命中而 ALG 命中：OPT 淘汰了将来最晚使用的页面 ，ALG 缓存中可能包含某个页面 。若 比 更早被请求，则可以”交换”——将 ALG 缓存中的 替换为 ，不会增加 ALG 的未来未命中次数
因此，OPT 的未命中次数不超过任何确定性策略。
核心性质
- 离线最优：Belady 策略在已知完整请求序列时产生最少的缓存未命中次数
- 在线不可达：实际系统无法预知未来请求，因此 Belady 策略不能直接用于在线场景
- 竞争比基准：Belady 策略的未命中次数 是衡量在线算法性能的下界基准
在线缓存算法的竞争比
| 在线算法 | 竞争比 | 说明 |
|---|---|---|
| LRU（最近最少使用） | 竞争比为 ，实际表现接近最优 | |
| FIFO（先进先出） | 竞争比为 | |
| LFU（最不经常使用） | 竞争比为 | |
| 下界 | 任何确定性在线算法的竞争比至少为 | |
| 随机化标记算法 | 为第 个调和数 |
应用场景
- 虚拟内存管理：操作系统的页面置换策略以 Belady 策略为理论最优基准，LRU 是最常用的近似策略
- 磁盘缓存：数据库缓冲池管理、文件系统缓存
- Web 缓存：代理服务器和 CDN 的缓存策略设计
- CPU 缓存：L1/L2/L3 缓存替换策略的理论分析