相同长文档为何每次都要重算?Automatic Prefix Caching 的块哈希与安全隔离
从重复 prefill 出发,手算块级最长前缀命中,追踪 KV 引用与淘汰,解释链式哈希、完整块粒度、多租户隔离及当前 vLLM 配置。
上一篇用 Speculative Decoding(投机解码)减少 target model 的串行 decode 轮数。但在长文档问答、固定 system prompt、few-shot 模板和多轮聊天里,另一个浪费更早发生:每个新请求都把相同前缀重新 prefill,生成一模一样的 Key/Value。
Automatic Prefix Caching(自动前缀缓存,APC)把已算好的前缀 KV blocks 留在缓存池。新请求若 token 前缀、模型环境与隔离域都匹配,就从最长命中边界继续计算。它不缓存答案,也不跳过新问题;它只复用因果注意力中确定的历史状态。
01 为什么只能复用“前缀”?#
Transformer 第 个位置的 Key/Value 由该位置 hidden state 产生,而 hidden state 已依赖此前全部可见 token:
即使两个请求中间都包含相同句子,只要它们之前的 token 不同,该句子的 hidden state 与 KV 通常也不同。安全的直接复用条件因此是从位置 0 开始的完整 token 前缀一致,而不是“找到任意相同子串”。
请求 A: [system][长文档 D][问题 1]
请求 B: [system][长文档 D][问题 2]
<------ 可复用 ------><- 重新 prefill ->
请求 C: [别的 system][长文档 D][问题 3]
前文不同,不能只因 D 的文本相同就复用其 KVtext02 一次命中省掉了哪些张量计算?#
设共享前缀长度为 ,模型有 层、KV heads 为 、head 维度为 。可复用状态的逻辑形状为
新请求不再对前 个 token 重做 embedding、每层 attention/MLP 以及 KV 写入;它把已有物理 blocks 加进自己的 block table,再从位置 继续 prefill。
命中不会减少后续 decode 每个 token 读取历史 KV 的成本,所以主要改善 Time To First Token(首 token 延迟,TTFT)与 prompt throughput,而不是长答案的 Time Per Output Token(逐 token 间隔,TPOT)。
03 为什么生产实现按块缓存?#
上一篇 PagedAttention 已把 KV Cache 划成固定 token 数的物理 blocks。APC 顺着这一布局建立索引:只有 full block(完整块)拥有稳定内容并可进入共享缓存。
假设 block size 为 4,两个请求的 token IDs 是:
A: [11,12,13,14] [21,22,23,24] [31,32,33]
B: [11,12,13,14] [21,22,23,24] [41,42]textB 可命中前 8 个 token。A 的第三块尚未填满,不能作为完整共享块;而且 B 在第 9 个 token 已分叉。
| 项目 | 数值 |
|---|---|
| 文本/token 共同前缀 | 8 |
| 完整命中块 | 2 |
| 直接复用 token | 8 |
| B 仍需 prefill | 2 |
块越大,哈希项和管理开销越少,但共同前缀末尾可能留下更多必须重算的 token;块越小,匹配更细,却增加元数据、哈希和 block table 压力。
04 为什么哈希必须包含父块?#
若只哈希当前块 token,出现在不同上下文中的 [21,22,23,24] 会得到同一个 key,但它们的 KV 已被不同前缀影响。
vLLM 的设计可抽象为链式哈希:
flowchart LR
B0[block 0<br/>token 0:4] --> H0[H0]
H0 --> B1[block 1<br/>token 4:8]
B1 --> H1[H1]
H1 --> B2[block 2<br/>token 8:12]
B2 --> H2[H2]
H1 -.请求在此分叉.-> N[新 block]mermaid查找从第一块顺序进行;一旦某块 miss,后续块即使局部 token 相同也不能越过缺口继续命中。
05 extras 为什么属于正确性,不只是元数据?#
相同 token IDs 不一定产生相同 KV。cache key 还要区分会改变前向结果的环境,例如:
- 模型与权重版本、KV dtype、位置编码配置;
- LoRA/adapter ID;
- 多模态 placeholder 对应的真实图像或音频 hash;
- prompt adapter 或其他改变 hidden state 的输入;
- 多租户的 cache salt(缓存盐)。
系统重启或模型热更新后,不能把旧权重算出的 KV 当成新权重状态。一个健壮的 key contract 必须可审计地列出所有语义输入。
06 手写一个最小链式块键#
下面只构造可复现 key,不存真正 KV:
from hashlib import sha256
import json
def block_key(
parent: str | None,
token_ids: list[int],
*,
model_revision: str,
adapter_id: str | None,
cache_salt: str,
) -> str:
payload = {
"parent": parent,
"tokens": token_ids,
"model_revision": model_revision,
"adapter_id": adapter_id,
"cache_salt": cache_salt,
}
raw = json.dumps(payload, sort_keys=True, separators=(",", ":")).encode()
return sha256(raw).hexdigest()
def prefix_keys(token_ids: list[int], block_size: int, **extras) -> list[str]:
parent = None
keys = []
full_end = len(token_ids) // block_size * block_size
for start in range(0, full_end, block_size):
parent = block_key(parent, token_ids[start:start + block_size], **extras)
keys.append(parent)
return keys
extras = dict(model_revision="m@abc123", adapter_id=None, cache_salt="tenant-7")
print(len(prefix_keys(list(range(10)), block_size=4, **extras))) # 2python输入 10 个 tokens、块大小 4,只得到 2 个完整块 key。换掉第一个 block 的任一 token,后续全部 key 都变化;只换 cache_salt,即使 tokens 相同也不会跨隔离域命中。
07 从请求到复用的数据流#
原始 messages
-> chat template + tokenizer
-> token_ids
-> 按 block_size 切完整块
-> 逐块计算 parent hash + extras
-> 查 cache map,得到最长连续命中 block IDs
-> ref_cnt++,从 free queue 移除正在使用的块
-> 为 miss 后缀分配新块并执行 prefill
-> 完整块计算完成后登记 hash
-> 请求结束:ref_cnt--,可留作缓存或被淘汰text这里有两类“空闲”:ref_cnt=0 表示当前请求不再引用,但该 block 仍可能携带可复用缓存;真正分配新空间时,缓存块可以从 free queue 头部被淘汰并重置。
08 引用计数怎样避免命中块被覆盖?#
设 block b7 已缓存且 ref_cnt=0。请求 B 命中它时:
- 把
ref_cnt从 0 加到 1; - 若它在可淘汰 free queue 中,先移出;
- 把
b7加入 B 的 block table; - B 结束后
ref_cnt回到 0,才重新成为淘汰候选。
如果只返回物理 block ID、没有原子地 touch(触碰)引用,另一个分配可能在模型 forward 前覆盖该 block,造成极难复现的错误输出。
批内共享还要求 Copy-on-Write(写时复制)语义:共享的完整前缀只读;各请求分叉后的新 token 写入自己的尾块,不能改坏其他请求引用的内容。
09 淘汰策略实际在优化什么?#
缓存和活跃请求争用同一个 KV block pool。保留太多冷前缀会减少新请求容量;淘汰过快又使高频 system prompt 反复 prefill。
基础 LRU(最近最少使用)可按 free queue 顺序淘汰。前缀树或 radix tree 实现还能感知共享层次,但任何策略都要回答:
- 命中节省了多少 prefill tokens/时间;
- 该前缀未来再次出现的概率;
- block 占用多久、是否阻塞活跃请求;
- 淘汰父前缀会让多少子路径失去可达性;
- 多副本服务中请求是否被路由到持有该缓存的 worker。
单机命中率很高并不代表集群收益高:若负载均衡随机打散同一会话,每个副本都只看到一次前缀。
10 Token 相同为何仍可能 miss?#
用户看到的文本相同,不保证 tokenizer 输入字节相同:
- chat template 版本、角色标记或 BOS/EOS 变化;
- JSON 字段顺序、空格、换行和 Unicode 规范化不同;
- 把动态时间戳、request ID 放在 system prompt 开头;
- 文档列表顺序不稳定;
- tokenizer 或词表版本变化。
调试时不要只 diff 原始字符串。应记录隐私安全的 token 长度、首个分叉索引、各块 key 与 extras 版本;在受控环境中再逐 token 对账。
把稳定内容放前、动态内容放后通常能增加共同前缀:
较差:[timestamp][request id][稳定 system prompt][长文档]
较好:[稳定 system prompt][长文档][timestamp/request id][用户问题]text但不能为了命中率改变提示语义或把本应隔离的数据挪进共享域。
11 多租户为何需要 Cache Salt?#
即使缓存只在 GPU 内、不直接返回给用户,命中造成的 TTFT 差异也可能形成 timing side channel(时间侧信道):攻击者反复提交候选前缀,从延迟推测另一个用户是否请求过某段内容。
当前 vLLM 支持 per-request cache_salt。盐进入首块及后续链式 hash,只有相同盐的请求才能复用。合理粒度可以是租户、组织或明确允许共享的信任域。
{
"messages": [
{ "role": "system", "content": "..." },
{ "role": "user", "content": "..." }
],
"cache_salt": "tenant-stable-secret-domain"
}jsonsalt 不应直接使用可猜的公开租户名;还需结合认证、日志脱敏、速率限制和恒定时间并不现实的侧信道评估。共享收益与隔离强度是显式策略,不能交给偶然相同的 prompt。
12 当前 vLLM 配置怎样核实?#
当前官方入口是:
vllm serve your-org/your-model \
--enable-prefix-caching \
--prefix-caching-hash-algo sha256bash官方 engine arguments 当前列出的 hash 算法包括 sha256、sha256_cbor、xxhash 与 xxhash_cbor;默认是 sha256。sha256_cbor 提供跨语言、规范序列化的可复现性;非加密 xxhash 速度更快,但文档明确提示碰撞与潜在信息泄漏风险。
默认值与混合 Mamba 模型的细粒度匹配选项会变化。部署时保存 vLLM 版本、完整解析配置、block size、模型 revision 和 tokenizer revision,并以对应版本官方文档为准。
13 性能实验怎样避免“暖缓存作弊”?#
至少拆成三组:
- cold:首次出现的长前缀;
- warm-hit:完整共享长前缀,只改变末尾问题;
- near-miss:在前缀靠前、中间、块内尾部各改一个 token。
记录:
cached tokens / prompt tokens
prefix cache hit blocks 与首个 miss block
prefill tokens/s、TTFT p50/p95/p99
KV utilization、evictions、preemptions
cache lookup/hash 时间
worker/replica ID 与会话路由命中text吞吐实验要包含真实复用率和 Zipf 型热点,而不是让所有请求复制同一 prompt。还要分别报告冷启动与稳态,否则第一次计算成本会被平均数藏掉。
14 正确性与隔离测试#
最强基础断言是 APC 开/关输出等价。在 greedy、固定模型与固定 dtype 下比较 token IDs;在随机模式比较目标分布,并确保 RNG 差异不会被误判为模型错误。
再构造这些边界:
- 共同前缀恰好为
block_size-1、block_size、block_size+1; - 第一块相同、第二块不同、第三块局部又相同;
- 同 tokens 不同 adapter/model revision;
- 同 tokens 不同
cache_salt; - 一个请求仍引用块时制造强制淘汰压力;
- 多模态 placeholder 相同但图片内容不同。
每个测试同时检查 computed_tokens、block IDs/ref counts、输出与是否发生越权命中。
15 常见错误与最短调试路径#
| 症状 | 常见原因 | 最短检查 |
|---|---|---|
| 看似相同 prompt 却 0 命中 | 模板/空白/tokenizer 版本不同 | 比较 token IDs 与首个分叉位置 |
| 命中后输出错误 | key 漏了父 hash、adapter 或多模态 hash | A/B 关闭 APC,并打印完整 key components |
| 高命中率但 TTFT 无改善 | 命中前缀太短或 lookup/路由开销大 | 报 cached tokens 而不只报 request hit |
| 缓存一开并发下降 | 冷 blocks 占据 KV pool,引发抢占 | 对齐 KV utilization、eviction 与 preemption |
| 多副本命中率低 | 会话被 round-robin 打散 | 按 worker 拆指标并测试 cache-aware routing |
| 跨租户出现延迟相关性 | 未设置隔离 salt | 用不同租户同 prompt 做黑盒时延测试 |
16 与相近缓存的边界#
普通单请求 KV Cache 避免同一请求 decode 时重算自己的历史;APC 让不同请求或同一会话的后续调用共享历史 blocks。Prompt Cache 这个名称有时也指客户端缓存文本、服务端缓存完整响应或提供商计费项,必须问清缓存的是 token、KV 还是答案。
RadixAttention 用 radix tree 管理多层共享前缀与调度;vLLM 当前设计以链式 block hash 查找缓存。二者数据结构不同,目标同样是让共同前缀 KV 可复用。外部 KV store/offload 可跨实例或跨时间延长缓存寿命,但引入传输、序列化、一致性与安全成本。
17 失败场景与局限#
- 请求几乎没有共同 token 前缀;
- 回答很长而 prompt 很短,decode 主导端到端耗时;
- 模板频繁变更或动态字段放在前缀开头;
- KV block pool 已被活跃长请求占满,没有缓存驻留空间;
- 多机路由缺少会话亲和或全局缓存目录;
- 混合注意力、滑动窗口或状态空间模型的可恢复边界比标准 Transformer 更复杂;
- 安全隔离要求使跨租户复用不可接受。
18 今天真正需要记住什么?#
- KV 只能在完整因果前缀一致时直接复用;任意相同子串不足以保证 hidden state 相同。
- 链式块哈希必须包含父 hash、当前 tokens 与所有影响前向结果的 extras。
- APC 主要减少重复 prefill,改善 TTFT 与 prompt throughput,不会直接加快长答案 decode。
- 命中、引用、淘汰、路由和租户 salt 是同一个系统问题;只打开一个布尔开关不等于获得稳定收益与安全隔离。
19 思考题与小练习#
- block size 为 4,两条请求共同前缀为 11 tokens。按“只缓存完整块”的规则最多复用多少 tokens?剩余多少需要重算?
- 修改
prefix_keys,让不同adapter_id的 key 必然不同;写测试证明第二块 token 相同但第一块不同也不会命中。 - 设计 3 个租户、4 个 worker 的实验,对比 round-robin、会话亲和和 cache-aware routing 的命中 tokens、TTFT 与负载不均衡。
相关工作#
- Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention ↗,提供块式 KV 管理基础。
- Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs ↗,提出 RadixAttention 管理可复用前缀。
- Gim et al., Prompt Cache: Modular Attention Reuse for Low-Latency Inference ↗,研究模块化 prompt 的注意力状态复用。
- Gao et al., CachedAttention: Memory-Aware KV Cache Management for LLM Inference ↗,讨论跨请求 KV 缓存管理。
- vLLM, Automatic Prefix Caching 设计文档 ↗,说明当前块哈希、引用、淘汰与 cache salt 机制。
20 下一篇预告#
前缀缓存减少了重复 prefill,但 prefill 与 decode 仍共享同一组 GPU 资源并互相干扰。下一篇将进入 Disaggregated Prefill/Decode(预填充—解码分离):两类阶段为何适合不同资源,以及 KV 跨节点传输何时会吞掉隔离收益。