KVCache Cache in the Wild — 生产级 KV$ cache 的画像与 workload-aware 淘汰 #

1. TL;DR #

来自 ALIYUN 通义生产集群一周真实 trace 的首个系统性 KV$ 复用画像：理想命中率仅 62%/54%（远低于合成负载的 >80%），单轮请求贡献 to-B 负载 97% 的命中，KV$ 寿命极短（to-B P99=97s，90% 块 0.3s 内不再复用），因此中等容量缓存即够用。据此把 GDFS 改造成按类别复用概率排序的 workload-aware 淘汰策略，命中率 +1.5–3.9%、QTTFT 降 28.3–41.9%。

2. 三个核心问题 #

Q1 痛点：现有 KV$ cache 的设计假设都建立在合成负载上 #

生产 LLM 服务同时承载 to-C（chatbot、文件/多模态/搜索）与 to-B（OpenAI 兼容 API 调用）两类请求，请求又分单轮/多轮。缓存淘汰策略（LRU/FIFO/LFU）本应像传统数据缓存那样贴合 workload 的复用特征，但业界对生产负载的 KV$ 复用一无所知：不清楚复用量有多大、哪类请求贡献最多、复用时间/复用概率的分布形状、以及 KV$ 的寿命——后者直接决定该配多大缓存。已有研究（ShareGPT、Mooncake trace）要么缺请求提交时间、要么缺请求类型/用户/多轮信息，无法支撑真实命中率与随时间使用量的分析（见 §5 Table 1）。

Q2 方法：先画像、再把 workload 特征灌进淘汰优先级 #

分两步。第一步用两条脱敏生产 trace（Trace A=to-C、Trace B=to-B）刻画三件事：复用量与偏斜、按类别的复用时间/概率分布、KV$ 寿命与容量需求。脱敏用 SipHash 对每 4 个连续 token 加随机盐哈希（比单 token 哈希更细粒度且更安全）。第二步把画像结论落到淘汰策略：把经典 GDFS 优先级公式里的 Frequency × Cost/Size 换成"按请求类别拟合的指数分布查出的复用概率"，并用寿命(life)对该概率做正则、用前缀偏移(Offset)打破平局。

核心技术壁垒：真正难以复制的不是那条公式，而是"请求类别（type + 轮数）→ 复用时间指数分布"这一可离线拟合、跨天稳定的映射。它依赖只有云厂商才能拿到的、带提交时间戳 + 请求类型 + 用户 ID + 多轮父链的全字段生产 trace（Table 1 里只有本工作三项俱全）。没有这份数据，策略里的 ReuseProb_w 无从标定，退化回 LRU。

Q3 结果：小改缓存策略即得双位数尾延迟收益，且推翻两个直觉 #

命中率相对最优基线再 +1.5–3.9%（相对最差 +8.1–23.9%），QTTFT 降 28.3–41.9%，单次淘汰仅 79 µs（vLLM 调度开销的 1.2%）。两个反直觉结论：(1) to-B 负载里单轮请求（而非多轮）贡献 97% 命中；(2) 显式丢弃 GDFS/LFU 的 Frequency 项反而更好，因为短命但高频的块会污染缓存。

3. 架构与方法 #

3.1 KV$ 复用机制（画像的物理基础） #

Paper Figure 2（caption: "An illustration of: ❶ how KV\$ from a prefill request (Req#0) can be reused by the decoding of Req#0, and ❷ how KV\$ can be reused for the prefill of a future request (Req#1)."）

❶ 同一请求 prefill 阶段算出的 K/V 矩阵在 decode 阶段被反复复用（避免重算）；❷ 当 Req#1 与 Req#0 共享前缀（"A paper on"）时，其 K/V 相同，故 Req#0 结束后仍缓存其 KV$ 供 Req#1 的 prefill 命中，只需现算未共享部分（"AI is"），直接压低 TTFT。这就是全篇优化的对象——块级（vLLM 默认 16 token/块）的跨请求前缀复用。读者应注意：命中只发生在前缀相同处，这也是 §3.4 空间局部性"从头缓存最好"的根因。

3.2 系统数据流：从请求到缓存决策 #

本框架不改推理算法与缓存机制（GPU→CPU 分层、异步逐层换出、命中时逐层换入均沿用既有系统），只替换"淘汰谁"这一个决策点。请求生命周期与调度/内存管理器的关系如下：

调度粒度是块、按用户做前缀匹配；内存管理器与策略解耦——策略只在 HBM OOM 触发淘汰时被调用。关键工程点：不逐块算概率，而是利用"同一 workload 内块天然按最后访问时间有序（指数分布单调）"，每个 workload 维护一个 LRU 优先队列，只把各队头当候选，把复杂度从 O(N) 降到 O(W)（W=workload 数，通常几十）。

3.3 复用概率的计算方式 #

Paper Figure 23（caption: "An illustration of how to calculate the reuse probability of a KV\$ block given its workload (request category)."）

后台采样近一小时数据，对每个请求类别拟合复用时间的累积分布 $F$（蓝线=9:00–10:00 拟合，红线=真实，二者贴合）。某块自上次访问已过 $t$、预期寿命 $\text{life}$，则其未来窗口内被复用的概率为 $\text{ReuseProb}(t,\text{life}) = F(t+\text{life}) - F(t)$——即把"寿命"作为向前看的窗口宽度，避免长尾分布对久未访问块给出虚高概率。

4. 作者证明 #

无形式化定理证明——本篇是实证系统论文；但 §4.2 给出两条淘汰优先级公式，逐项解释其物理意义（框架论文的性能/优先级模型）。

4.1 记号表 #

4.2 两条公式与物理意义 #

基线 GDFS：

$$\text{Priority} = \text{Clock} + \text{Frequency} \times \frac{\text{Cost}}{\text{Size}}$$

本篇 workload-aware：

$$\text{Priority} = \left( \text{ReuseProb}_w(t, \text{life}),\ -\text{Offset} \right)$$

six 项检查：

1. 为何用 tuple + 字典序而非加权和：复用概率与前缀位置量纲不同、重要性不对等；用字典序保证"未来最可能被复用"绝对优先，仅在概率并列时才用 -Offset 决胜，避免人工调权重。最低优先级者先淘汰。
2. 为何 -Offset（负号）：Offset 越小越靠请求头部；空间局部性表明只有相同前缀才能共享 KV$（§3.2/§3.4），故头部块更可能被复用。取负使"小 offset→高优先级"，与字典序"大者留存"一致。
3. 为何删掉 Frequency（相对 GDFS）：KV$ 寿命极短（Figure 19），高频块可能早已"死亡"，Frequency 无法预测未来复用，保留它会让死块占位。这是与经典缓存智慧相反的取舍，由 §5 消融（去掉 life 正则后 +2.4% 来自此思路）支撑。
4. 为何删掉 Cost/Size：GDFS 里取回代价高≠更可能被复用；本场景要优先把"更可能被复用"的块留住，而复用概率已由 ReuseProb_w 显式给出，Cost/Size 冗余且误导。
5. life 正则的必要性（单调性修正）：不加 life 时，长尾分布会对久未访问的块持续返回较大概率，与"寿命短"矛盾；用 $F(t+\text{life})-F(t)$ 把概率限制在有限前瞻窗口内，随 $t$ 增大而单调衰减，恢复"越久未用越该淘汰"的单调性。
6. 一阶数值自洽：Trace B >99% 为单轮请求，类别信息稀薄，指数拟合退化为均匀 recency 排序——即策略自动回落到 LRU；这正解释了 §5 中"WA 在 Trace B 收益小"的实测（模型的边界行为与实验一致，而非事后拟合）。

5. 实验与数据 #

5.1 画像：复用量、偏斜与单轮支配 #



Paper Figure 4（caption: "An analysis of the ideal cache hit ratio of the KV\$ cache under real-world LLM serving workloads within a day..."）

无限容量下 Trace A/B 理想命中率仅 62%/54%，显著低于合成负载常报的 >80%——说明合成数据高估了 KV$ 收益。10% 的块贡献 77% 复用，Trace A 中 19%、Trace B 中 4% 的请求贡献了 >90% 命中，偏斜极强。



Paper Figure 5（内容：每种请求类型对命中的贡献及其多轮比例；原文未surfaced verbatim caption）

反直觉核心证据：Trace B（纯 API）多轮比例 <0.1%，但单轮请求贡献了 97% 命中。原因是程序把相同 system prompt 硬编码进请求、且高 QPS（>10）密集复用共享前缀。结论——优化单轮请求缓存与优化多轮同等重要。

5.2 复用时间的指数分布与寿命 #



Paper Figure 15（caption: "An empirical analysis of the reuse time probability distribution of KV\$ blocks..."）

三条观察：(1) 每个请求类别的复用时间都能被指数分布很好拟合；(2) 分布是 workload-aware 的，连同类型不同轮数（text-1 vs text-2）都不同；(3) 相似流量时段（白天 vs 白天）分布相似、跨天同时段相似（附录 Figure 29 佐证）。(1)+(3) 合起来意味着可用近期历史离线预测某类别分布——这是 ReuseProb_w 可标定的前提。



Paper Figure 19（caption: "The distribution of the lifespan of KV\$ blocks on both traces."）

寿命极短且两 trace 差五个数量级：Trace A 90% 块 612s 内不再复用，Trace B 仅 0.3s。这直接支撑"删 Frequency"与"用 life 正则"的设计，也解释为何 to-B 用小缓存即可。

5.3 容量需求 #



Paper Figure 22（caption: "An analysis of the KV\$ cache size required to achieve an ideal cache hit ratio on different models and traces."）

GQA 模型容量需求适中：Trace A 上 Llama3-70B 仅需 4× 可用 HBM（恰好匹配 8×A100 + 1TB CPU 内存的典型配置里每 GPU ≈128GB ≈ 4× 预留 HBM）；Trace B 甚至小于预留 HBM，纯 GPU 缓存即够——意味着 API 负载可省掉 CPU-RDMA-SSD 存储层级。MHA 模型因每 token KV 大仍需巨量缓存，故淘汰策略在受限容量下仍重要。

5.4 策略收益与消融 #



Paper Figure 25（caption: "An analysis of the cache hit ratio and QTTFT with respect to the CPU cache provisioned on Qwen2-7B."）

在 8×A800-80GB、NVLink 400GBps、PCIe Gen4 的 testbed 上，基于 vLLM 自实现 CPU-GPU 缓存（已校准到 CachedAttention 水平），trace 用保温度模式的方法缩放。WA 相对最差基线 +8.1–23.9% 命中、相对最优基线 +1.5–3.9%，QTTFT 降 28.3–41.9%。



Paper Figure 28（caption: "An ablation study on Qwen2-7B with #CPU Cache / HBM is 1."）

分布法（技术➀）+1% 命中；叠加 life 正则（技术➂）再 +2.4%；空间局部性➁对所有策略均施加故不单列。

5.5 何时赢、何时平 #

Workload regime	本框架 (WA)	基线	为何
to-C 多类型、含多轮、容量受限 (Trace A)	收益最大 (+3.9% vs best)	LRU/FIFO 忽略类别复用差异	类别信息丰富，指数拟合有区分度
to-B 纯 API、>99% 单轮 (Trace B)	收益最小，≈ LRU	LRU 已近最优	类别信息稀薄，WA 回落 LRU
缓存容量很大	收益递减	各策略趋同	大缓存容忍差策略
LFU 在任意 regime	优于 LFU	LFU 最差	高频短命块污染缓存

6. 论证链 #

#	命题	依据（篇内）
1	生产 KV$ 复用量中等（62%/54%）且高度偏斜（10% 块→77% 复用）	§3.2 Figure 4/7/8
2	to-B 命中由单轮请求（共享 system prompt + 高 QPS）主导，占 97%	§3.2 Figure 5
3	每个请求类别的复用时间服从指数分布，且跨相似时段/跨天稳定、可离线预测	§3.4 Figure 15；附录 Figure 29
4	KV$ 寿命极短（to-B 0.3s / to-A 612s @90%），故 Frequency 无预测力、需 life 正则	§3.5 Figure 19
5	由 3+4，把 GDFS 的 Freq×Cost/Size 换成 (ReuseProb_w(t,life), -Offset) 字典序优先级	§4.2 两公式 + Table 2
6	利用同 workload 内时间序，priority queue 使复杂度 O(N)→O(W)，开销 79µs（vLLM 的 1.2%）	§4.2 Figure 24
7	由 5+6，实测命中 +1.5–3.9%、QTTFT −28.3–41.9%；Trace B 因回落 LRU 收益小（自洽边界）	§5.1 Figure 25–28

7. 实现 cross-reference #

• 淘汰算法伪代码见 Figure 24（CurT=time.time()；for b in Bs: Priority=ReuseProb_{H(b.w)}(CurT-b.cached_t, Life)；按 PriorityChosenBlock.offset) 更新 victim；返回 ChosenBlock）——论文以图形式给出，未提供可运行仓库，此段之外 [实现未公开]。
• 集成到 vLLM [id 2309.06180]：CPU-GPU 分层缓存为自实现（原文称已校准到 CachedAttention 水平），全局 KV$ 调度器复刻 Mooncake [id 2407.00079]；WA 策略仅作用于单实例，全局层留待未来工作。
• 脱敏 trace 样本：github.com/alibaba-edu/qwen-bailian-usagetraces-anon（仅样本，非完整生产 trace）。

核心技术壁垒（展开）：可复制的门槛在数据而非算法。策略的每个 ReuseProb_w 都要按"类型×轮数"标定一条指数曲线，而标定所需的全字段带时间戳生产 trace 只有大云厂商拥有（Table 1 中唯一三项俱全者）。缺此数据，公式退化为 LRU——这也是 Trace B 上收益微弱的同一机理。

关键实现细节：

1. ReuseProb 用 $F(t+\text{life})-F(t)$ 而非 $1-F(t)$：把预期寿命当作有限前瞻窗口，否则长尾分布会对久未访问块给出虚高概率，与短寿命矛盾。
2. O(N)→O(W) 的前提是"同一 workload 内块按最后访问时间有序 ⇔ 指数分布单调"，故只需各 workload LRU 队头作候选；这条不成立时优化失效。