离线缓存

概述

离线缓存问题是缓存替换的经典理论模型：给定缓存容量 $k$ 和完整的请求序列 $\sigma$（预先已知），求使缓存未命中次数最少的替换策略。该问题的最优解是 furthest-in-future（Belady）算法——每次替换最远将来才会被请求的缓存项。离线缓存是在线缓存（如LRU）的理论上界。

定义

离线缓存问题（Offline Caching / Paging）

输入：

• 缓存容量 $k$（缓存中最多存放 $k$ 个不同的项）
• 请求序列 $\sigma =⟨{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n⟩$（完整序列预先已知）

输出：一个缓存替换策略，使得处理整个请求序列时的缓存未命中（cache miss）次数最少。

Furthest-in-Future 策略：当缓存已满且需要加载新项时，替换缓存中最远将来才会被再次请求的项（若某项不再被请求，则优先替换它）。

核心性质

1. Furthest-in-Future 算法

FURTHEST-IN-FUTURE(σ, k):
    初始化缓存 S 为空
    for i = 1 to n:
        if σ_i ∈ S:
            缓存命中，不做操作
        else:
            缓存未命中
            if |S| < k:
                将 σ_i 加入 S
            else:
                找到 S 中在 σ_{i+1}, σ_{i+2}, ..., σ_n 中最晚出现的项 e
                S = S \ {e} ∪ {σ_i}

2. 最优性证明（Theorem 15.5）

Theorem 15.5：Furthest-in-Future 策略产生最少的缓存未命中次数。

证明（四性质归纳构造）：

证明思路：将 FF 策略的执行过程与任意最优策略 OPT 的执行过程逐步对齐，证明 FF 的未命中次数不超过 OPT。

定义四个性质，在归纳过程中保持不变：

1. (P1)：FF 和 OPT 的缓存中包含相同的项数
2. (P2)：FF 的缓存是 OPT 缓存的子集（$S_{FF}\subseteq S_{OPT}$）
3. (P3)：FF 缓存中不在 OPT 缓存中的项，其下次请求时间不早于 OPT 缓存中不在 FF 缓存中的项
4. (P4)：FF 的累计未命中次数不超过 OPT 的累计未命中次数

归纳步骤：对于每个请求 ${\sigma }_i$：

• 若两者都命中或都未命中，性质容易保持
• 若 FF 命中而 OPT 未命中：FF 的未命中数更少，性质保持
• 若 FF 未命中而 OPT 命中：通过替换论证，将 OPT 的缓存调整为包含 FF 的选择，且不增加未命中次数

3. 与在线缓存的区别

特征	离线缓存	在线缓存
请求序列	完全预先已知	逐个到达，未来未知
最优策略	Furthest-in-Future	无绝对最优
分析方法	精确最优性	竞争比（competitive ratio）
代表策略	Belady (FF)	LRU, FIFO, LFU

竞争比：在线策略 $A$ 的竞争比定义为 ${\sup }_{\sigma }\frac{{\text{misses}}_A(\sigma )}{{\text{misses}}_{OPT}(\sigma )}$。

在线策略	竞争比
LRU	$k$
FIFO	$k$
LFU	不保证有界竞争比
下界	$k$（任何确定性在线策略的竞争比至少为 $k$）

4. Belady 异常（FIFO 的非单调性）

一个有趣的现象：增加缓存容量可能导致 FIFO 策略的未命中次数增加。这被称为 Belady 异常，说明 FIFO 不是最优的在线策略。而 Furthest-in-Future 和 LRU 都不会出现这种现象。

5. 实际应用中的启发式

虽然 Furthest-in-Future 需要预知未来请求序列（实际中不可行），但它为在线策略提供了理论指导：

• LRU（Least Recently Used）：替换最久未使用的项，是 FF 的在线近似
• LFU（Least Frequently Used）：替换使用频率最低的项
• ARC（Adaptive Replacement Cache）：自适应地在 LRU 和 LFU 之间切换

复杂度分析

指标	值
时间复杂度（朴素实现）	$O(kn)$（每次未命中时扫描缓存）
时间复杂度（优先队列实现）	$O(n\log k)$
空间复杂度	$O(k)$

章节扩展

• 15.4 离线缓存 — 离线缓存问题的完整求解过程
• 贪心算法 — 贪心算法完整方法论
• 替换论证 — 证明贪心最优性的核心技术

参见

• 活动选择问题 — 另一个经典贪心问题
• 哈夫曼编码 — 贪心算法的另一个应用
• 贪心选择性质 — 贪心选择性质的详细说明