第10章 前缀缓存：默认开启的零开销加速

最快的计算是不必做的计算。系统提示重复、多轮对话前缀延伸、RAG 片段部分重叠——前缀缓存要捡的就是这三类已经算过的 token。

10.1 为什么前缀缓存是"免费午餐"

LLM 推理的每一次 prefill 都要计算所有 prompt token 的 KV。但真实的生产流量里，大量 prompt 内容是重复的：

10.1.1 重复的三种来源

来源 1：系统提示（system prompt）。每个 ChatGPT-like 服务的每次请求前面都拼着几百到几千 token 的系统提示，指导模型的角色、语气、限制。同一个服务下，这段内容对所有请求都完全一样。

"你是一个专业的编程助手，回答要简洁清晰。遵循以下规则：1. ...
 2. ... 3. ... 4. ...（大约 800 tokens 的规则）"
 ──────────────────────────────────────
 用户本次问题："帮我写个 Python 快排"（~20 tokens）

系统提示占据了绝大多数 token。每个请求都从头算一遍这段规则的 KV，纯浪费。

来源 2：多轮对话的共同前缀。一段多轮对话的每一轮，都是前一轮的 "延长":

Round 1 = system_prompt + user_msg_1
Round 2 = system_prompt + user_msg_1 + assistant_reply_1 + user_msg_2
Round 3 = system_prompt + user_msg_1 + assistant_reply_1 + user_msg_2 + assistant_reply_2 + user_msg_3

Round 3 的前面一大段 token 和 Round 2 完全一样。如果重新全量 prefill 每次请求，每多一轮开销线性增加——N 轮对话总开销 $O(N^2)$，这就是"多轮对话越来越慢"的根源。

来源 3：RAG 的部分重叠。RAG 场景下每个请求前面拼着从知识库检索出来的上下文。同一个问题的多次重述、相邻问题、热门文档——都会让检索结果重合。

10.1.2 重复计算的惊人代价

假设系统提示 800 token，每个请求的用户输入 200 token，总 prompt 1000 token。

• 100 个请求：100 × 1000 = 100k token 的 prefill FLOPs
• 其中实际不同的只有 100 × 200 = 20k
• 80% FLOPs 是浪费

省掉的 FLOPs 会直接折算成 prefill 墙钟时间：第一个请求仍要完整算一遍系统提示，后续 99 个请求只需算各自 200 token 的增量部分。本专栏运行环境没有 GPU，不给具体毫秒数——真实收益取决于模型规模、batch 组合与 GPU 型号，读者应在自己的机器上用 benchmarks/benchmark_serving.py 实测。除了省时间，省下的重复 KV 还让 KV 池能服务更多并发。

10.1.3 前缀缓存为什么需要特殊设计

缓存听起来简单——hashmap 一个以 prompt token 为 key 的表，存 KV 就行？错。

挑战 1：KV Cache 有因果依赖。Transformer 的 attention 是因果的：第 k 个 token 的 KV 受它前面所有 token 影响。

看这个例子：

请求 A 的第 5 个 block = "...的专业的编程助手，回答要简..."
请求 B 的第 5 个 block = "...的专业的编程助手，回答要简..."

两个请求的第 5 个 block 里 token 完全相同。但如果请求 A 的第 0-4 个 block 和 B 不同，第 5 个 block 的 KV 就不同（因为计算它时要 attend 到前面的 KV，前面不一样，结果就不一样）。

单纯按 token 内容 hash 是错的。必须是"这些 token + 它们前面的上下文"一起 hash。

挑战 2：块粒度对齐。KV Cache 按 block（16 tokens）管理。前缀缓存也必须按 block 匹配。两个请求前 500 token 相同，但第 501 个开始不同——只有前 $\lfloor 500/16 \rfloor = 31$ 个 block 能命中。

挑战 3：查找性能的零容忍。每次有请求进来都要走这套 hash + 查找逻辑，而这套逻辑跑在调度器所在的 Python 主循环上。如果 CPU 开销抵消了 GPU 省下的计算，那就是负优化。这正是 V0 前缀缓存长期只能 opt-in 的原因——命中率为 0 时它仍然是纯开销。

10.2 链式哈希：每个 Block 的"身份证"

vLLM 的解决方案是链式哈希（Hash Chain）。

10.2.1 基本定义

每个 block 的 hash 由三部分决定：

$$\text{hash}(b_i) = H(\text{hash}(b_{i-1}), \text{tokens}(b_i), \text{extra\_keys}(b_i))$$

• 第 $i$ 个 block 的 hash = hash(父 block 的 hash + 本 block 的 token 序列 + extra_keys)
• 第 0 个 block 的"父 hash"用一个固定常量 NONE_HASH（防碰撞的随机种子）

递归地，第 $i$ 个 block 的 hash 其实"包含"了前面所有 block 的 hash——就像 Git commit hash 包含了父 commit 的 hash 一样。

graph LR
    N["NONE_HASH<br/>（种子）"] --> B0["Block 0<br/>hash = H(NONE_HASH, tokens[0:16], extra)"]
    B0 --> B1["Block 1<br/>hash = H(B0.hash, tokens[16:32], extra)"]
    B1 --> B2["Block 2<br/>hash = H(B1.hash, tokens[32:48], extra)"]
    B2 --> Bdots[...]
    style N fill:#94a3b8,color:#333,stroke:none
    style B0 fill:#2563eb,color:#fff,stroke:none
    style B1 fill:#7c3aed,color:#fff,stroke:none
    style B2 fill:#db2777,color:#fff,stroke:none

10.2.2 链式设计的两个好处

好处 1：O(1) 比较。两个 block 的 hash 一样 ⟺ 它们的 token 序列一样且前面的上下文也一样。不需要一个一个 token 比对。

好处 2：天然支持"最长公共前缀"匹配。

# 伪代码
for i, block_hash in enumerate(request_block_hashes):
    if block_hash in cache_table:
        # 命中，继续
        continue
    else:
        # 第 i 个 block 没命中，返回前 i 个作为可复用的
        return request_block_hashes[:i]

一旦有一个 block 不匹配，后面的都不用查了——链式结构保证了"前面不匹配就不可能匹配"。

10.2.3 BlockHashType：同时存 hash 和 tokens

vllm/v1/core/kv_cache_utils.py 里的 BlockHashType：

class BlockHashType(NamedTuple):
    hash_value: int                      # 整数 hash
    token_ids: tuple[int, ...]           # 原始 token 序列
    extra_keys: Optional[Any] = None     # 额外隔离键

为什么还要存原始 token_ids？ 因为 hash 有碰撞概率。虽然 Python 内置 hash() 对于整数 tuple 的碰撞概率极低，但不是 0。BlockHashType 整个元组就是 cached_block_hash_to_block 的键，NamedTuple 的相等判定会同时比较 hash_value、token_ids 和 extra_keys——三者都匹配才算命中。不过 token_ids 只能确认本块的内容，前面的上下文仍只由父块的 hash_value 这一个整数代表，前缀链上的碰撞它查不出来；所以源码 docstring 的说法是"降低"碰撞的可能（"to reduce the likelihood of hash collisions"），并紧接着指出换用 SHA256 才能让碰撞"practically impossible"。

如果用户极度在意碰撞概率（比如医疗、金融场景），可以在命令行传 --prefix-caching-hash-algo sha256（由 PR #15297 引入、随 v0.8.3 发布；只对 V1 有效，V0 引擎下设成 sha256 会直接报错，见 vllm/engine/arg_utils.py:1556）（对应 CacheConfig.prefix_caching_hash_algo，默认值是 "builtin"，见 vllm/config.py:1334 的 prefix_caching_hash_algo）。KVCacheManager.__init__ 里这个开关只是换一个函数：self.caching_hash_fn = sha256 if caching_hash_algo == "sha256" else hash（vllm/v1/core/kv_cache_manager.py:41）。SHA-256 是密码学哈希，工程上可以认为不会碰撞，代价是每个 block 都要先 pickle 序列化、再做一次真正的摘要运算（vllm/utils.py 的 sha256），而不是 CPython 内建的整数混合——比默认路径慢，具体倍数取决于 block_size 和机器，需自行实测。

10.2.4 extra_keys 的两种来源（v0.9.0 起有第三种）

同一段 token 序列在不同条件下会产生不同的 KV——extra_keys 把这些条件加到 hash 里以隔离：

v0.8.5 的 generate_block_hash_extra_keys（vllm/v1/core/kv_cache_utils.py:364）把两类来源拼在一起，没有其他项：

mm_extra_keys, new_start_mm_idx = _gen_mm_extra_hash_keys(
    request, start_token_idx, end_token_idx, start_mm_idx)
lora_extra_keys: list[int] = _gen_lora_extra_hash_keys(request)

extra_keys: list[Any] = lora_extra_keys + mm_extra_keys

if not extra_keys:
    return None, new_start_mm_idx

return tuple(extra_keys), new_start_mm_idx

LoRA 隔离：第 16 章会详讲。相同 prompt 在 LoRA-A 和 LoRA-B 下的 KV 不同，必须分开缓存。

多模态隔离：第 15 章会详讲。同样的文本 token "describe this:" 后面接不同图片，embedding 不同，KV 也不同。mm_hash 由模型 ID、该图片内容和 HF processor 参数一起哈希得到（vllm/multimodal/processing.py:1585），同一张图换模型或换预处理参数也不会误命中。

注意版本差异：社区后来还加了用户可指定的 cache_salt——比如多个客户共用同一个 model + LoRA，但不希望客户 A 的 prompt 通过缓存命中"泄漏"给客户 B，两边用不同 salt 即可隔离。但这个字段在本专栏锚定的 v0.8.5 里还不存在：在 v0.8.5 的源码里 grep cache_salt 一无所获，它是由 PR #17045「Prevent side-channel attacks via cache salting」 引入、随 v0.9.0 发布的。从这个 PR 标题也能看出它的真实动机——防侧信道：没有 salt 时，攻击者可以靠"我的请求是不是变快了"来推断别人缓存里有什么前缀。它恰好说明 extra_keys 这个设计是可扩展的——新的"隐含变量"只要塞进这个元组，链式哈希的核心逻辑一行都不用动。

10.2.5 链首的"虚拟父哈希"：NONE_HASH

链式哈希有个必须回答的工程问题——第一个 block 的"父哈希"是什么？如果写 parent = 0 或 parent = None，那两个 Python 进程跑同一段输入会得到相同的链首哈希——这在独立部署时没问题，但对"攻击者构造碰撞"防御为零：知道了哈希算法的人可以精心挑选 token 让两段不同内容落到同一个 block hash，污染别人的缓存。

vLLM 在 vllm/v1/core/kv_cache_utils.py:45 的解决是进程内随机、同源可重现：

NONE_HASH = int.from_bytes(os.urandom(32), byteorder="big") \
    if os.getenv('PYTHONHASHSEED') is None \
    else sha256(os.getenv('PYTHONHASHSEED'))

两种模式：

模式 A——PYTHONHASHSEED 未设置（生产默认）：进程启动时从 /dev/urandom 取 32 字节作链首。每个 vLLM 进程的链首哈希都不一样——攻击者无法预知链首，也就没法离线构造出能与别人前缀撞上的输入。

模式 B——PYTHONHASHSEED 已设置：用环境变量的 SHA256 作链首。同一个值的两个进程得到相同链首，方便一致性测试、以及多副本部署时希望多个进程算出同一条哈希链——源码注释里写的就是 "processes can share the seed if needed"。

这段代码上方的注释 # This is not performance critical as it is done one per process 交代了为什么这里能"奢侈"地用 urandom——整个进程生命周期只调用一次，不进热路径。hash_block_tokens 的热路径里只用传入的 hash_function，默认是 Python builtin hash()。这里有个容易想当然的点：CPython 的 PYTHONHASHSEED 随机化只作用于 str/bytes（以及 datetime），而纯文本请求喂给 hash_block_tokens 的是 (parent_hash, token_ids_tuple, None)——整数加 None，从 Python 3.12 起 hash(None) 也是常量（V0 ComputedBlocksTracker 的源码注释专门提到这一点），这样的元组 hash() 跨进程是确定的（多模态请求的 extra_keys 里含 mm_hash 字符串时例外）。所以链首的不可预测性主要由 NONE_HASH 那 32 字节 urandom 提供，而不是来自 builtin hash 本身。真正需要密码学强度（审计、多租户强隔离）时把 hash_function 换成 sha256 即可——一个参数替换，两种安全级别。

10.3 get_computed_blocks：查找命中的核心路径

一个新请求到达时，KVCacheManager 调用 get_computed_blocks 看能复用多少 block：

# vllm/v1/core/kv_cache_manager.py:92（概念性简化）
def get_computed_blocks(self, request) -> tuple[list[KVCacheBlock], int]:
    if not self.enable_caching:
        return [], 0

    # 1. 计算或读取请求的 block hash 链
    block_hashes = self.req_to_block_hashes.get(request.request_id)
    if not block_hashes:
        block_hashes = hash_request_tokens(self.caching_hash_fn,
                                           self.block_size, request)
        self.req_to_block_hashes[request.request_id] = block_hashes

    # 2. prompt_logprobs 请求走特殊路径（需要重算每个位置的 logprob）
    if request.sampling_params.prompt_logprobs is not None:
        return [], 0

    # 3. 若 prompt 长度恰好被 block_size 整除，摘掉最后一个 block hash，
    #    强制重算最后一个 block（否则没有 token 可以喂给下一步 forward）
    if len(block_hashes) * self.block_size == request.num_tokens:
        last_block_hash = block_hashes.pop()
    else:
        last_block_hash = None

    # 4. 在 BlockPool 里找最长匹配
    computed_blocks = self.specialized_manager.find_longest_cache_hit(block_hashes)

    # 5. 启用 EAGLE 且有命中时丢掉最后一个命中块，重算它以拿到 draft head 需要的 hidden states
    if self.use_eagle and len(computed_blocks) > 0:
        computed_blocks.pop()

    # 6. 统计（受 log_stats 开关保护）
    self.prefix_cache_stats.queries += len(block_hashes)
    self.prefix_cache_stats.hits += len(computed_blocks)

    if last_block_hash is not None:
        block_hashes.append(last_block_hash)   # 复原，因为链被缓存在 req_to_block_hashes

    num_computed_tokens = len(computed_blocks) * self.block_size
    return computed_blocks, num_computed_tokens

注意这里并不递增 refcount。get_computed_blocks 是一次纯查询，调度器拿到结果后决定要不要真的调度这个请求；只有随后的 allocate_slots 才会调用 self.block_pool.touch(new_computed_blocks) 把命中块的 ref_cnt 加一、并从空闲链表里拔出来（vllm/v1/core/block_pool.py:212）。"查"和"占"分离，是为了让调度器可以查完之后反悔。

flowchart TB
    New[新请求到达]
    Hash[hash_request_tokens<br/>构造 block hash 链]
    Check{prompt_logprobs?}
    SkipCache["跳过缓存<br/>返回 (空, 0)"]
    Find[find_longest_cache_hit<br/>在 BlockPool 哈希表里查]
    Return["返回 (命中块列表, 命中 token 数)"]
    Touch["allocate_slots 里才 touch<br/>refcount++<br/>从空闲链表里拔出"]
    New --> Hash --> Check
    Check -->|是| SkipCache
    Check -->|否| Find
    Find --> Return -.真正调度时.-> Touch
    style Find fill:#2563eb,color:#fff,stroke:none
    style Touch fill:#10b981,color:#333,stroke:none

10.3.1 三个工程细节

细节 1：req_to_block_hashes 缓存 hash 链本身。同一个请求被抢占后再调度时，它的 hash 链不需要重新算——已经缓存在 KVCacheManager 里（它是个 defaultdict(list)，所以第一次访问返回空 list 而不是抛 KeyError，代码里靠 if not block_hashes 判断"还没算过"）。请求真正结束时才由 free_block_hashes 清掉——注意源码注释特意强调：抢占时不能调它。这让抢占 + 恢复的开销降到极低。

细节 2：prompt_logprobs 特殊处理。如果用户请求要求返回 prompt 里每个 token 的 logprob（debug / 分析用），必须每个位置都真正算一遍——缓存无法提供这种信息。跳过缓存，保证语义正确。

细节 3：find_longest_cache_hit 在 block 级 O(1) 迭代。每个 block 查一次 hash 表，一旦 miss 就停。最多 $O(\text{num\_blocks\_per\_request})$ 次哈希表查询——典型请求也就几十次。

10.4 V0 → V1：把常驻开销削到"感觉不到"

V0 的前缀缓存功能可用，但长期是 opt-in 的：命中率为 0 时，那套簿记依然要照跑一遍，纯亏。本专栏没有 GPU，无法给出"损失百分之几"的实测，但可以做一件更扎实的事——把两代实现的数据结构摆在一起数一数每个 block 要付多少 Python 对象和多少次额外操作。

对照的两份源码是：V0 的 vllm/core/block/prefix_caching_block.py + vllm/core/evictor.py，V1 的 vllm/v1/core/kv_cache_utils.py + block_pool.py。两者在 v0.8.5 里同时存在（V0 代码尚未删除，只是不再是默认路径）。

10.4.1 每个 block 的元数据：从两个对象到一个 dataclass

V0 的 PrefixCachingBlock 在 __init__ 里挂了 _prev_block、_cached_content_hash、_cached_num_tokens_total、_allocator、_last_accessed、_computed、_extra_hash 等字段，并且内部再包一个 NaiveBlock 对象（self._block = NaiveBlock(...)）。V0 的 block 对象对应的是块表里的一项而不是物理块（多个对象可以指向同一个物理 block id），由 vllm/core/block/common.py 的 BlockPool 预分配 num_blocks * 4 个反复复用、不够时再扩容。也就是说，V0 每个 block 对象是两个 Python 对象，还额外持有指向前驱 block 对象的强引用。

V1 的 KVCacheBlock（vllm/v1/core/kv_cache_utils.py:111）是一个只有五个字段的 dataclass：

@dataclass
class KVCacheBlock:
    """KV-cache block metadata."""
    block_id: int
    ref_cnt: int = 0
    _block_hash: Optional[BlockHashType] = None
    # Used to construct a doubly linked list for free blocks.
    prev_free_block: Optional["KVCacheBlock"] = None
    next_free_block: Optional["KVCacheBlock"] = None

一个 block 一个对象，字段固定五个，其中两个还是空闲链表的指针（下一小节要用）。BlockPool.__init__ 一次性把它们全建出来（self.blocks = [KVCacheBlock(idx) for idx in range(num_gpu_blocks)]），之后运行期不再创建 block 对象——所有分配都是从空闲链表里摘节点。

10.4.2 哈希只在 block 填满时算，而且整条链按请求缓存

两代实现都不会给"半满"的 block 算 hash——一个 block 没填满，它的 hash 不稳定也没有复用价值。V0 用 PrefixCachingBlock.content_hash 属性里的 if not self.is_full: return None 做这件事，V1 则在 hash_request_tokens 的循环里直接 break：

for start in range(0, len(token_ids), block_size):
    end = start + block_size
    block_token_ids = token_ids[start:end]
    # Do not hash the block if it is not full.
    if len(block_token_ids) < block_size:
        break

decode 阶段并不走 hash_request_tokens：每 step 的 allocate_slots 都会调 BlockPool.cache_full_blocks，而 decode 每 step 只产一个 token，绝大多数时候尾块还没满，num_cached_blocks == num_full_blocks，函数开头就直接 return；只有尾块恰好填满的那一步才为这一块算一次 hash、写一次 dict（vllm/v1/core/block_pool.py:105-156）。

两代都有按请求缓存的哈希链，区别在生命周期：V1 的 KVCacheManager.req_to_block_hashes 是个 defaultdict(list)，一个请求算过一次的 block hash 链会一直留着，被抢占再恢复时一个 hash 都不用重算；只有请求真正结束才由 free_block_hashes 清掉（源码注释特意写明：抢占时不要调它）。V0 的 ComputedBlocksTracker._seq_id_to_blocks_hashes 也按序列增量缓存哈希，但重算式抢占会经 free() 连同它一起清掉（vllm/core/block_manager.py:266），恢复后要从头再算。

10.4.3 一个链表同时当空闲池、LRU 和驱逐候选池

V0 需要两套结构：PrefixCachingBlockAllocator._cached_blocks（hash → block id）负责查，vllm/core/evictor.py 里的 LRUEvictor 负责淘汰。LRUEvictor 自己就有 free_table: Dict[int, BlockMetaData] 加一个 priority_queue 堆，并且因为堆里会积累失效条目，还得靠 CLEANUP_THRESHOLD = 50 定期做一次全量重建。查和淘汰是两份状态，之间要同步。

V1 只有一条侵入式双向链表 FreeKVCacheBlockQueue——指针就长在 KVCacheBlock 自己身上（上面那两个 prev_free_block / next_free_block 字段）：

• 释放 block → free_block_queue.append(block)，进链尾
• 缓存命中 block → touch() 里 free_block_queue.remove(block)，从链表中间 O(1) 拔出
• 需要驱逐 → get_new_blocks 从链表头 popleft，天然就是最久没用的；取出的块若还挂着 hash，才由 _maybe_evict_cached_block 把它从 cached_block_hash_to_block 里删掉——释放时并不清 hash，驱逐是惰性的

一个数据结构同时扮演空闲池、LRU 和驱逐候选池，没有第二份状态，也就没有同步成本，更没有堆里的失效条目要清理。第 5 章的 FreeKVCacheBlockQueue 详细讲过。

10.4.4 查表结构：两级 dict，且刻意不去重

BlockPool.cached_block_hash_to_block 的类型是 dict[BlockHashType, dict[int, KVCacheBlock]]——两级：外层按 block hash，内层按 block id。为什么内层还要一层 dict？源码注释给了答案：

NOTE: We currently don't de-duplicate the blocks in the cache, meaning that if a block becomes full and is cached, we don't check if there is already an identical block in the cache. This is because we want to make sure the allocated block IDs won't change so that block tables are append-only.

也就是说 vLLM 故意允许内容相同的多个物理 block 共存。理由是 block table 必须是 append-only 的：一旦允许"发现重复就换成已有那块"，某个请求的 block table 中间那一项就得被改写，GPU 上的 block table 张量也要跟着更新。用一点点显存冗余换来"块表只追加不修改"，这是个非常典型的系统取舍。get_cached_block 命中时就取内层 dict 的第一个（next(iter(cached_blocks))）。

10.4.5 这些改动共同支撑的一句承诺

把上面四点加起来：每个物理 block 恰好一个对象、启动时一次建齐、半满块根本不进哈希路径、抢占恢复零重算、查与淘汰共用一条链表。命中率为 0 时，前缀缓存要付的固定成本就是"每满一个 block 算一次 hash + 写一次 dict"——这才是 V1 敢把它默认打开的工程依据。具体到百分之几的吞吐影响，取决于模型和负载，请用 benchmarks/benchmark_serving.py 在自己的机器上量。

10.5 Chain-aware LRU 驱逐

KV 池满时要驱逐缓存。朴素 LRU 是按时间顺序——但这在前缀缓存场景下有个微妙问题。

10.5.1 链式依赖下的驱逐陷阱

假设 block 0、1、2 是一段共同的系统提示前缀。三者同时进入空闲状态。朴素 LRU 按"最近访问时间"排序：

假设三个 block 最后访问时间都是 t=0:
  空闲链表头: [block 0 (link head), block 1 (link middle), block 2 (link tail), ...]

现在新请求进来要 1 个 block，LRU 驱逐链表头——block 0。但 block 0 是链头，未来所有请求都可能复用它（因为大家系统提示都一样）！应该驱逐 block 2 （链尾，最少被复用）。

10.5.2 V1 的 Chain-aware 策略

V1 在 block 释放时做倒序入链——把链尾（最具体的）先入空闲链表、链头（最通用的）后入。这个策略并非 V1 首创：V0 的 LRUEvictor 在堆里用 (last_accessed, -num_hashed_tokens, ...) 排序，时间相同时哈希 token 数多的（链尾）先驱逐（vllm/core/evictor.py:73-120）；V1 的 FreeKVCacheBlockQueue docstring 写的是同一条规则，只是改用释放顺序来实现：

vllm/v1/core/kv_cache_manager.py:296 的 free：

def free(self, request: Request) -> None:
    """When caching is enabled, we free the blocks in reverse order so that
    the tail blocks are evicted first."""
    blocks = self.req_to_blocks.pop(request.request_id, [])
    ordered_blocks: Iterable[KVCacheBlock] = blocks
    if self.enable_caching:
        ordered_blocks = reversed(blocks)
    self.block_pool.free_blocks(ordered_blocks)

BlockPool.free_blocks 的签名参数就叫 ordered_blocks，docstring 写死了契约："The blocks should be ordered by their eviction priority, where the first block will be evicted first." ——它自己不排序，排序责任在调用方。

这三块依次追加到空闲链表尾部，顺序变成 [..., block_2, block_1, block_0]——链尾 block_2 离 head 更近（最应该驱逐的），链头 block_0 排在最后（最应该保留的）。驱逐从 head 开始，轮到这三块时先驱逐链尾。

一行 reversed 就把 LRU 从"时间排序"升级到"价值感知的时间排序"。和 V0 的时间戳堆相比，整个实现零额外数据结构。

10.5.3 Chain-aware 为什么有收益

收益的来源可以纯逻辑地推出来，不需要 benchmark：链头 block 的潜在复用者是链尾 block 的超集。任何将来能复用 block $i$ 的请求，必然也复用了 block $0..i-1$；反过来不成立。所以在"必须扔掉一个"的时候，扔链尾严格不劣于扔链头。

代价是零：既不需要额外字段，也不需要额外扫描，就是把 blocks 换成 reversed(blocks)。

具体能提升多少命中率完全取决于负载的前缀结构（共享前缀越长、KV 池越紧张，差距越大），本专栏没有 GPU 环境，不给数字。想量化的读者可以对比开关 enable_caching 前后 benchmarks/benchmark_prefix_caching.py 的输出。

10.6 命中率与加速比的数学关系

为了让调优有依据，定量分析前缀缓存收益。

10.6.1 命中率定义

设请求平均 prompt 长度 $L$ token（= $L/B$ blocks，$B$ 是 block_size），其中命中缓存的部分是 $h \cdot L$ tokens（$h$ 是命中率）。

10.6.2 Prefill 加速

• 无缓存：prefill $L$ token，时间 $T_{\text{prefill}}(L)$
• 有缓存：只需 prefill $(1-h) L$ token

这里要小心一个常见的算错。Transformer 的 prefill 计算量不是单纯的 $L^2$：线性层（QKV 投影、attention 输出投影、FFN）是 $O(L)$，只有 attention 的 $QK^\top$ 和 $\text{softmax}\cdot V$ 是 $O(L^2)$。在今天常见的模型尺寸和 4k 以内的上下文里，线性层往往还占大头，所以整体更接近线性。

同时前缀缓存只省掉被跳过 token 自身的计算：剩下的 $(1-h)L$ 个 token 仍然要 attend 到全部 $L$ 个位置的 KV（那正是缓存里存着的东西）。于是 attention 部分的开销从 $O(L^2)$ 降到 $O((1-h)L \cdot L)$，也是省 $(1-h)$ 倍而不是 $(1-h)^2$ 倍。

$$\text{Prefill speedup} \approx \frac{1}{1-h}$$

• $h=0.3$ → 约 1.4×
• $h=0.5$ → 约 2×
• $h=0.7$ → 约 3.3×
• $h=0.9$ → 约 10×

这是一阶估计的上界：实际还要扣掉哈希、查表、以及最后那个被强制重算的尾块（见 §10.3 的 last_block_hash 分支）。任何声称"命中 90% 就快 100 倍"的说法都来自把节省当成平方项，不要信。

10.6.3 TTFT 对用户体感的意义

TTFT（首 token 延迟）在排队不严重时几乎等于 prefill 时间。对 chatbot 产品，用户感知"快"主要就是 TTFT 要短——而前缀缓存恰好只作用在 prefill 上，对 TPOT（每 token 输出延迟）基本没有影响。

换句话说：前缀缓存是一个专门优化 TTFT 的手段。如果你的 SLO 卡在 TPOT 上，别指望它；卡在 TTFT 上，它通常是投入产出比最高的一档。想知道自己场景的数字，用 benchmarks/benchmark_serving.py 分别在 --enable-prefix-caching 开关下跑一遍对比 TTFT 分位数。

10.6.4 五类场景的命中率估算

下表给的是定性排序，不是实测值——命中率完全由你自己的流量决定，任何脱离负载的百分比都没有意义：

场景	典型共享前缀	前缀在 prompt 中的占比	预期命中率
ChatGPT-like 开放对话（单轮为主）	系统提示	小	低
多轮对话（长会话）	历史对话全文	随轮数单调增长	随轮数上升，长会话可以很高
RAG 问答	检索到的文档片段	中到大，取决于文档命中重合度	中
客服 / 垂直助手	长系统提示 + 固定知识片段	大	高
Code Copilot	当前文件 / 仓库上下文	大，且相邻请求高度重叠	高

估算方法很简单：不必上 GPU，把线上真实 prompt 采样几千条，按 block_size 切块做一次链式哈希，统计"第 i 条 prompt 的前缀有多少块在前 i-1 条里出现过"，就能得到理论命中率上界。真实值会低一些——因为 KV 池有限，老块会被驱逐。

10.7 V1 为什么敢默认开启

默认开启这个决定看起来简单，但在工程上是重大举措。V0 时代这是 opt-in 的。落到代码上就是 vllm/engine/arg_utils.py 里 V1 分支的这两行：

if self.enable_prefix_caching is None:
    self.enable_prefix_caching = True

注意配置字段的默认值是 Optional[bool] = None 而不是 False——用三态区分"用户没表态"和"用户明确关掉"，V1 才能在用户没表态时替他打开，同时不覆盖显式的 --no-enable-prefix-caching。敢这样替用户做主，靠的是下面三条设计承诺。

10.7.1 0% 命中率的行为保证

第一条承诺：在工作负载完全不适合前缀缓存时（比如每个请求的 prompt 都独一无二），性能不应该比不启用更差。vLLM 官方 V1 alpha 博客（2025-01-27）给出的口径是：命中率为 0% 时，V1 前缀缓存带来的吞吐下降不到 1%，正因为开销近乎为零才默认开启。

上面 10.4 节的四项数据结构改动全是为了这一条——把缓存逻辑的固定开销压到"每满一个 block 一次 hash + 一次 dict 写入"，这样即使命中率是 0，用户也不会感到"启用前缀缓存反而慢了"。

10.7.2 自适应收益

只要有一点命中，就应该有可见收益。V1 的实现里 block 粒度的命中即使只命中 1 个 block（16 token），也能省下 16 token 的 prefill 计算——小收益累积起来也值得。

10.7.3 不需要用户思考

V0 的 opt-in 设计意味着用户需要：

• 知道前缀缓存是什么
• 评估自己的工作负载是否适合
• 知道有什么配置开关
• 决定要不要开

每一步都有摩擦。V1 的"默认开"意味着绝大多数用户不需要思考——默认配置就是合理配置。只有"我就是想关掉看裸性能"的用户需要显式关闭，而因为这个参数用的是 argparse.BooleanOptionalAction（vllm/engine/arg_utils.py:152），关闭它的写法是 --no-enable-prefix-caching，不是想当然的 --disable-prefix-caching。

这种"优秀的默认值"是 V1 贯穿的设计哲学。同样的思路还体现在 Chunked Prefill 默认开启（第 11 章）、CUDA Graph 默认捕获（第 8 章）等地方。好的系统让绝大多数用户什么都不配置就跑在合理路径上。

10.8 与其他系统的对比

前缀缓存不是 vLLM 独有的。横向对比：

系统	数据结构	匹配粒度	隐式/显式	特色
vLLM	哈希链 + HashMap	Block (16 token)	隐式	近零开销（官方：0% 命中时吞吐降 <1%）、默认开启；extra_keys 扩展
SGLang	Radix Tree	Token 级	隐式	自然支持分叉对话；tree 扩展操作原生
TensorRT-LLM	Radix 搜索树（节点为 block）	Block 级（只共享满块）	隐式	驱逐为带优先级（0–100）的 LRU
Anthropic API	服务端显式缓存	用户指定的断点	显式	用户打 cache_control 标签，缓存读写单独计费

10.8.1 vLLM 的哈希链 vs SGLang RadixAttention

SGLang 的 RadixAttention（Zheng et al., arXiv:2312.07104）用 Radix Tree（压缩前缀树）管理缓存。主要差异：

特性	vLLM 哈希链	SGLang Radix Tree
插入新请求	O(blocks) hash	O(tokens) radix 插入
查最长前缀	O(blocks) iter	O(tokens) tree 下降
分支/分叉支持	分叉前的满块经哈希共享，分叉点所在的未满块各算各的（V1 无 COW）	原生支持（tree 自然多叉）
内存开销	最少（每 block 1 hash）	中等（tree 节点开销）
实现复杂度	简单（HashMap）	中等（插入时要分裂节点）

什么时候哪个更好？

• vLLM 的哈希链简单高效，适合"大多数场景下前缀是线性延长的" —— chatbot、RAG
• SGLang 的 Radix Tree 原生支持分叉 —— 某些 beam search、tree-of-thoughts 场景更自然

两者的渐进复杂度都不高（一次前缀查找的代价都远小于一次 attention），公开可比的端到端 benchmark 又受各自引擎其余部分影响太大，本专栏不给"差距百分之几"的结论。取舍主要在于 与各自引擎架构的契合度：vLLM 的 block 表是 append-only 的定长块，天然适配定长哈希键；SGLang 的调度器本来就围绕程序结构（分叉、并行调用）设计，树结构是自然选择。

10.8.2 Anthropic Prompt Caching（显式）

Claude API 的做法是用户显式标记缓存边界：

{
  "system": [
    {"type": "text", "text": "你是一个助手...", "cache_control": {"type": "ephemeral"}}
  ],
  "messages": [
    {"role": "user", "content": "实际问题"}
  ]
}

显式方案的优点是语义清晰（用户知道哪些部分会被缓存）、计费明确（缓存读取按独立的、显著低于常规输入的单价计费，具体倍率以 Anthropic 官方定价文档为准）。缺点是用户心智负担。

vLLM 选择了隐式路线——让系统自动识别前缀。这符合 vLLM"作为开源推理引擎服务开发者"的定位——开发者希望"开箱即用、无需 SDK 改动"。Anthropic 作为"闭源 API 厂商"可以合理地要求用户适配它的缓存协议。两种路线都有道理，取决于你面对的受众。

10.9 监控与调优

生产部署前缀缓存后要持续监控两个指标：

vllm:gpu_prefix_cache_queries_total   # Counter：累计查询的 block 数
vllm:gpu_prefix_cache_hits_total      # Counter：累计命中的 block 数

这两个 Counter 定义在 vllm/v1/metrics/loggers.py:173-183（名字里带 gpu_，别漏；_total 后缀是 prometheus_client 给 Counter 自动加的）。

注意 "queries" 的单位是 block 不是请求——PrefixCacheStats 的字段注释（vllm/v1/metrics/stats.py:21-22）写得很清楚，原文折成两行，后半句是 "means the number of blocks that were queried from the cache."。

还要注意：滚动命中率不是 Prometheus 指标。PrefixCachingMetrics.hit_rate 只出现在 LoggingStatLogger 打的那行引擎日志里：

Engine 000: Avg prompt throughput: ... GPU KV cache usage: x%, Prefix cache hit rate: y%

要在 Prometheus 里画命中率曲线，得自己用两个 Counter 相除：rate(vllm:gpu_prefix_cache_hits_total[5m]) / rate(vllm:gpu_prefix_cache_queries_total[5m])。

10.9.1 健康曲线

好的系统前缀缓存命中率应该：

• 启动阶段：0（缓存冷启动，池子里一个 cached block 都没有）
• 预热期：随着相同前缀被反复命中而快速爬升
• 稳态：稳定在一个由你自己负载决定的水平
• 持续稳定：不应该剧烈上下跳动

具体数值没有"标准答案"——同一份代码在不同业务流量下的稳态命中率可以相差一个数量级。要判断健康与否，看的是形状（先爬升、后平稳），不是绝对值。

不健康的表现：

• 命中率持续极低还在跑 → 工作负载不适合前缀缓存，可以试着关掉对比一下（省下的只是哈希 + 查表那点固定开销，通常很小）
• 命中率剧烈波动 → 可能 KV 池太小导致缓存块刚建好就被驱逐，试着调高 --gpu-memory-utilization
• 命中率突然归零 → 可能有人在做性能测试，或 LoRA 切换频繁（每个 LoRA 破坏共享）

10.9.2 调优建议

Kvcache 预算分配：适当提高 gpu_memory_utilization（0.9 → 0.95）让 KV 池更大，能容纳更多缓存 block。

block_size：CUDA 平台上如果不显式指定，vllm/platforms/cuda.py:142-143 会填 16（MLA 模型走 FlashMLA 后端且硬件支持时是个例外，会被强制成 64，见同文件紧随其后的几行）。合法取值由 BlockSize = Literal[1, 8, 16, 32, 64, 128] 限定。调大它会让缓存匹配的粒度变粗（更容易在边界上"差几个 token 就整块不命中"），换来的是每次请求少几次哈希和查表——这个取舍只在极长共享前缀的场景下才值得试。

LoRA 影响评估：如果业务场景有多个 LoRA 并发，前缀缓存收益会被 extra_keys 分层（extra_keys 里带的是 lora_int_id）。考虑 API 路由让同 LoRA 请求走同副本（保留单副本内的命中率）。

10.9.3 累计 vs 滚动窗口——两个命中率不是同一件事

引擎日志里那行 Prefix cache hit rate: x% 不是"进程启动以来的累计命中率"，而是最近约 1000 个请求的滚动命中率。它和上面两个单调递增的 Counter 完全不是一回事，不区分就会在调优时犯错。实现在 vllm/v1/core/kv_cache_utils.py:49 的 PrefixCachingMetrics 类：

class PrefixCachingMetrics:
    def __init__(self, max_recent_requests: int = 1000):
        self.max_recent_requests = max_recent_requests
        self.aggregated_requests = 0
        self.aggregated_query_total = 0
        self.aggregated_query_hit = 0
        self.query_queue: deque[tuple[int, int, int]] = deque()

    def observe(self, stats):
        if stats.reset:
            self.reset()

        self.query_queue.append((stats.requests, stats.queries, stats.hits))
        self.aggregated_requests += stats.requests
        self.aggregated_query_total += stats.queries
        self.aggregated_query_hit += stats.hits

        # 老请求挤出队列
        if self.aggregated_requests > self.max_recent_requests:
            old_requests, old_queries, old_hits = self.query_queue.popleft()
            self.aggregated_requests -= old_requests
            self.aggregated_query_total -= old_queries
            self.aggregated_query_hit -= old_hits

    @property
    def hit_rate(self) -> float:
        if self.aggregated_query_total == 0:
            return 0.0
        return self.aggregated_query_hit / self.aggregated_query_total

算法是一个 FIFO deque——每来一批请求的统计就入队；队里累计请求数超过 1000 时，队首的最老批次出队。hit_rate 就是当前队里 hit / query 的比值。

这带来几个运维上的反直觉行为：

1. 流量骤变时命中率会"装作慢慢变"——流量结构突然变化时，新请求里很多是没 warm 的；但 hit_rate 的分母里还保留着旧流量贡献的那部分老批次。你会看到 hit_rate "缓慢滑落"而不是断崖式下跌。滞后时长 ≈ 1000 / QPS，低 QPS 部署上可以相当可观——凭这条曲线判断"工作负载变了"一定会比实际晚，排障时要心中有数。

2. reset_prefix_cache 会清窗口，但不会清 Counter——管理员调 reset_prefix_cache 后 KV 缓存全空，observe 开头的 if stats.reset: self.reset() 会把 deque 和三个累加值一起清零，所以日志里的 hit_rate 从零重新爬。但 vllm:gpu_prefix_cache_hits_total / _queries_total 这两个 Counter 是单调递增的，不会被 reset 影响。用这两个 Counter 做除法画曲线的人要记得看的是 rate() 而不是累计比值，否则清空的效果会被历史彻底摊平。

3. 两套口径不一致是正常的——vllm:gpu_prefix_cache_hits_total 和 vllm:gpu_prefix_cache_queries_total 是无窗口累计，从进程启动起单调递增；日志里的 hit_rate 是滚动。进程跑了一天、累计比值很高，而当前业务正在频繁切 LoRA、最近千把个请求的 hit_rate 掉到很低——这两件事同时成立完全正常。调优时看滚动值或 rate()，不要看累计比值。

max_recent_requests=1000 是构造函数的默认值。对 QPS 不高的部署，这个窗口会覆盖很长一段时间，场景切换的响应速度就偏慢。v0.8.5 里没有 CLI 参数能调它——PrefixCachingMetrics() 是在 vllm/v1/metrics/loggers.py 的 LoggingStatLogger 里不带参数构造的，想改只能改代码。这是个"默认值对绝大多数部署合理、少数场景需要改源码"的取舍。

10.9.4 实测：前缀缓存的两个核心算法都极短

§10.3 用一节讨论 get_computed_blocks、§10.5 讨论 chain-aware LRU——把这两个算法在源码里实测——

get_computed_blocks（kv_cache_manager.py:92）核心路径——

def get_computed_blocks(self, request: Request) -> tuple[list[KVCacheBlock], int]:
    if not self.enable_caching:
        return [], 0
    block_hashes = self.req_to_block_hashes[request.request_id]
    if not block_hashes:
        block_hashes = hash_request_tokens(self.caching_hash_fn, self.block_size, request)
        self.req_to_block_hashes[request.request_id] = block_hashes
    # ... prefix cache stats 累加
    # 如果 request 要 prompt_logprobs 则 skip prefix caching
    computed_blocks = self.specialized_manager.find_longest_cache_hit(block_hashes)
    # ...

整个函数占 vllm/v1/core/kv_cache_manager.py:92-162 共 71 行，其中 docstring 和注释占了大半——去掉空行、注释和 docstring 后只有 28 行，而且真正的匹配工作全部委托给 specialized_manager.find_longest_cache_hit。

FullAttentionManager.find_longest_cache_hit（specialized_manager.py:71-82）的"最长匹配"实测仅 12 行（去掉注释 9 行）——

def find_longest_cache_hit(
        self, block_hashes: list[BlockHashType]) -> list[KVCacheBlock]:
    computed_blocks: list[KVCacheBlock] = []
    for block_hash in block_hashes:
        # block_hashes is a chain of block hashes. If a block hash is not
        # in the cached_block_hash_to_id, the following block hashes are
        # not computed yet for sure.
        if cached_block := self.block_pool.get_cached_block(block_hash):
            computed_blocks.append(cached_block)
        else:
            break
    return computed_blocks

§10.3 整一节讨论的"最长匹配"算法在源码里就是这几行——for 一次、命中就 append、未命中就 break——完全线性扫描、不需要任何复杂数据结构。源码里那三行注释说的正是 §10.2.2 的结论："block_hashes is a chain of block hashes. If a block hash is not in the cached_block_hash_to_id, the following block hashes are not computed yet for sure." 一旦某个 hash 没命中，链上后续的所有 hash 也必然不会命中（它们的哈希输入里包含了未命中的前序）——所以 break 而不是 continue 是算法正确性的直接推论，而不是一个优化技巧。

两条值得记住的物理事实——

1. 最长匹配只用 for + dict.get + break——零额外数据结构——前缀缓存的 "O(L) 而 L 是 block 数（不是 token 数）" 性能特征就来自这几行。一个 4096 token 的 prompt 按 16 token/block 切分是 256 块，命中检查的成本上限就是 256 次 dict 查找（miss 时通常远少于此，因为第一个 miss 就 break 了）。这正是 §10.7.1 "0% 命中率的行为保证"的底气所在——不是一句承诺，而是一个能写出上界的数量级
2. SlidingWindowManager 在同一个文件里另有实现（specialized_manager.py 全文 161 行，两个子类都在里面）——给滑动窗口 attention 用（v0.8.5 只支持一个 KV cache group，全注意力层与滑动窗口层并存时后者都被改成 FullAttentionSpec，只有全部层都是滑动窗口时才会用到它）。它的 find_longest_cache_hit 不能简单 break：基类 docstring 写明返回值里"skipped blocks"要用 null block 占位（"sliding window manager should return a list like [NULL, NULL, KVCacheBlock(7), KVCacheBlock(8)] for block size 4 and sliding window 8"），因为窗口外的旧块本来就不需要命中。vLLM 用 SpecializedManager 这个 ABC（另一个抽象方法是 remove_skipped_blocks）加子类多态隔离两种 attention 的差异

和 §11.11 串起来看——chunked prefill 的核心截断逻辑在 vllm/v1/core/sched/scheduler.py:179-191 大约十来行，本节的最长匹配也是十来行。V1 两大优化的核心算法加起来不到三十行，剩下成千上万行都是配套基础设施（hash 链构造、block pool 管理、specialized manager 多态、metrics）——再次印证第 11 章 §11.11 的结论："V1 不是没有复杂度，而是把复杂度压进了统一调度协议"。

10.10 本章小结

前缀缓存是 V1 设计哲学"优秀的默认值"的最佳例证：

• 三种重复来源：系统提示、多轮对话延伸、RAG 检索片段——占比高低完全由业务流量决定
• 因果依赖：KV 是有向因果的，必须用链式哈希而不是简单内容哈希
• BlockHashType：hash + token_ids + extra_keys 三者同时参与相等判定，降低碰撞误命中；要密码学强度用 --prefix-caching-hash-algo sha256
• extra_keys：v0.8.5 只有 LoRA 与多模态两类（cache_salt 是 v0.9.0 才加的），设计上可扩展
• 查找路径：hash 链构造 → 最长匹配 → 返回命中块；refcount++ 在随后 allocate_slots 的 touch 里
• V0→V1 的四处数据结构收敛：每 block 一个 5 字段 dataclass（不是 __slots__）、半满块不进哈希路径、哈希链按请求缓存、空闲池即 LRU 即驱逐候选池
• Chain-aware LRU：倒序入链让链尾先驱逐，KVCacheManager.free 里的一个 reversed(blocks)；free_blocks 的契约把排序责任交给调用方
• 命中率-加速比：prefill 加速上界 ≈ 1/(1−h)，不是 1/(1−h)²——缓存只省被跳过 token 自身的计算
• 默认开启：enable_prefix_caching 用 Optional[bool] 三态，V1 分支在用户没表态时置 True；关闭要写 --no-enable-prefix-caching
• 横向对比：vLLM 哈希链（简单、贴合 append-only 块表）、SGLang Radix Tree（分叉友好）、Anthropic 显式（语义与计费清晰）
• 生产监控：Prometheus 只有 vllm:gpu_prefix_cache_{hits,queries}_total 两个 Counter，滚动命中率只出现在引擎日志里

源码实测：specialized_manager.py 全文 161 行，FullAttentionManager.find_longest_cache_hit 在 71-82 行（去掉注释 9 行，就是 for + dict 查找 + break）；get_computed_blocks 在 vllm/v1/core/kv_cache_manager.py:92-162，去掉空行、注释和 docstring 28 行，且不递增 refcount（touch 在 allocate_slots 里）；break 是链式哈希因果性的直接推论（§10.2.2），不是优化技巧。

---

源码导航

• 哈希链定义：vllm/v1/core/kv_cache_utils.py（BlockHashType、hash_block_tokens、hash_request_tokens）
• BlockPool 缓存机制：vllm/v1/core/block_pool.py
• KVCacheManager 查找入口：vllm/v1/core/kv_cache_manager.py（get_computed_blocks）
• Specialized 管理器（按 attention 类型选最长匹配策略）：vllm/v1/core/specialized_manager.py（161 行，FullAttentionManager / SlidingWindowManager）
• 指标数据结构：vllm/v1/metrics/stats.py（PrefixCacheStats）；Counter 与日志：vllm/v1/metrics/loggers.py

论文

• Zheng et al., "SGLang: Efficient Execution of Structured Language Model Programs", arXiv:2312.07104（2023 年 12 月首版，后发表于 NeurIPS 2024）— RadixAttention 一节
• Anthropic 官方文档 "Prompt caching"（docs.anthropic.com）— cache_control 语义与计费口径