杨艺韬讲堂

Appearance

第10章 前缀缓存：零开销的加速 ​

"The fastest computation is the one you don't have to do."

本章要点

  • 理解前缀缓存的动机：为什么同一个系统提示不应该重复计算
  • 掌握哈希链（Hash Chain）的设计：如何唯一标识一个 KV Cache 块
  • 深入 BlockHash 的构造过程：父块哈希 + 当前 Token + 额外键
  • 理解零开销的实现原理：为什么 V1 能默认启用前缀缓存
  • 认识缓存命中率对吞吐量的定量影响

10.1 重复的代价 ​

在典型的 LLM 服务场景中，大量请求共享相同的前缀：

  • 系统提示（System Prompt）——所有请求都有相同的系统提示，可能长达数百甚至数千 Token
  • Few-shot 示例——RAG 应用中检索到的上下文片段经常重复
  • 多轮对话——同一个会话的前几轮对话是所有后续请求的公共前缀

没有前缀缓存时，每个请求都要独立计算这些重复部分的 KV Cache。100 个请求各有 500 Token 的系统提示，就要重复计算 100 × 500 = 50,000 Token 的注意力——其中 49,500 Token 是浪费的。

前缀缓存的思想很简单：如果一个 KV Cache 块的内容已经被计算过了，直接复用，不要重新计算。

10.2 哈希链：块的身份证 ​

前缀缓存的核心问题是如何识别两个块是否包含相同的 KV Cache。

vLLM 使用**哈希链（Hash Chain）**为每个块生成唯一标识。一个块的哈希不仅取决于它自身包含的 Token，还取决于它前面所有块的内容——因为 KV Cache 的值受到前面所有 Token 的影响（注意力机制的因果性）。

BlockHash 的构造公式定义在 vllm/v1/core/kv_cache_utils.py:392：

python
# vllm/v1/core/kv_cache_utils.py:392-420
def hash_block_tokens(
        hash_function: Callable,
        parent_block_hash: Optional[int],
        curr_block_token_ids: Sequence[int],
        extra_keys: Optional[tuple[Any, ...]] = None) -> BlockHashType:
    """Computes a hash value corresponding to the contents of a block
    and the contents of the preceding block(s)."""
    if not parent_block_hash:
        parent_block_hash = NONE_HASH  # 随机种子，防碰撞

    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHashType(
        hash_function(
            (parent_block_hash, curr_block_token_ids_tuple, extra_keys)),
        curr_block_token_ids_tuple, extra_keys)

BlockHashType 本身是一个 NamedTuple（kv_cache_utils.py:21），不仅包含哈希值，还保留了原始 token IDs 和 extra_keys 用于碰撞检测：

python
# vllm/v1/core/kv_cache_utils.py:21-32
class BlockHashType(NamedTuple):
    hash_value: int                      # 哈希值
    token_ids: tuple[int, ...]           # 原始 Token IDs（碰撞检测）
    extra_keys: Optional[Any] = None     # 额外键（LoRA/多模态/salt）

这个设计的精妙之处：即使使用 Python 内置 hash()（非密码学安全），通过同时比较 hash_value 和 token_ids，碰撞概率也极低。而 v0.8.5 还支持 SHA256 模式（caching_hash_algo="sha256"），碰撞概率可忽略不计。

为什么需要 extra_keys？ 因为相同的 Token 序列在不同条件下可能产生不同的 KV Cache：

  • 不同的 LoRA 适配器会改变注意力计算的权重
  • 不同的多模态输入（图片 embedding）会影响前面的 Token 表示
  • 用户可以通过 cache salt 强制隔离不同会话的缓存

缓存查找与命中 ​

当一个新请求到达时，KV Cache Manager 按块构造哈希链，依次在缓存中查找：

python
# vllm/v1/core/kv_cache_manager.py:93-155 (简化)
def get_computed_blocks(self, request):
    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

    # 特殊处理：prompt_logprobs 请求跳过缓存
    # 因为需要重新计算每个 token 的 logprob
    if request.sampling_params.prompt_logprobs is not None:
        return [], 0

    # 查找最长缓存命中
    computed_blocks = (
        self.specialized_manager.find_longest_cache_hit(block_hashes))

    # 统计命中率
    if self.log_stats:
        self.prefix_cache_stats.queries += len(block_hashes)
        self.prefix_cache_stats.hits += len(computed_blocks)

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

如果前 3 个块命中缓存，第 4 个块未命中，那么请求只需要从第 4 个块开始计算——前 3 个块的 KV Cache 直接复用，省去了 48 个 Token 的预填充计算。

10.3 零开销的秘密 ​

V0 的前缀缓存有明显的性能开销——大约 5-10% 的吞吐量下降，即使在 0% 缓存命中率的情况下。这是因为 V0 在每步调度时都要计算哈希、查找缓存、更新引用计数，这些 Python 操作在高 QPS 下成为瓶颈。

V1 通过几个优化将开销降到了 < 1%，使得前缀缓存可以默认启用：

优化一：极简的块对象。KVCacheBlock（kv_cache_utils.py:112）的设计极其精简——只有 5 个字段：

python
# vllm/v1/core/kv_cache_utils.py:112-145
class KVCacheBlock:
    """KV-cache block metadata."""
    block_id: int                                      # 块 ID
    ref_cnt: int = 0                                   # 引用计数
    _block_hash: Optional[BlockHashType] = None        # 哈希（惰性计算）
    prev_free_block: Optional["KVCacheBlock"] = None   # 双向链表-前驱
    next_free_block: Optional["KVCacheBlock"] = None   # 双向链表-后继

注意 prev_free_block 和 next_free_block——它们构成了一个侵入式双向链表（Intrusive Doubly Linked List）。与传统的 collections.deque 不同，侵入式链表不需要额外的包装节点，O(1) 删除任意节点。管理十万级别的块时，这个差异很明显。

优化二：BlockHashWithGroupId 打包。将块哈希和 KV Cache 组 ID 打包为单个 bytes 对象作为字典键，避免了元组键的哈希开销。

优化三：惰性哈希计算。块的哈希只在需要时才计算——如果一个块从未被释放（一直在使用中），就不需要计算哈希。

优化四：空闲链表复用。前缀缓存的 LRU 驱逐直接复用 BlockPool 的空闲链表，不需要额外的数据结构。

基准测试结果：在 0% 缓存命中率时，V1 的前缀缓存只带来 < 1% 的吞吐量下降。而在有缓存命中的场景（如共享系统提示），吞吐量提升可达 2-5 倍。

10.4 缓存命中率的定量影响 ​

前缀缓存的收益取决于工作负载中前缀共享度。让我们用具体数字感受：

场景：客服系统

  • 系统提示：800 Token（所有请求共享）
  • 用户输入：平均 200 Token（各不相同）
  • 总预填充：1000 Token/请求

没有前缀缓存：每个请求预填充 1000 Token。 有前缀缓存：第一个请求预填充 1000 Token，后续请求只预填充 200 Token（800 Token 的系统提示命中缓存）。

加速比：1000/200 = 5×。这意味着同样的 GPU 资源可以服务 5 倍的预填充请求，或者每个请求的首 Token 延迟降低到原来的 1/5。

场景：RAG 应用

  • 检索到的上下文：2000 Token（部分请求可能命中相同的文档片段）
  • 假设 30% 的请求共享至少一个文档片段
  • 共享部分平均 500 Token

平均加速：1 + 0.3 × 500/2200 ≈ 1.07×——只有 7%。RAG 场景的缓存命中率较低，因为检索结果的组合空间很大。

前缀缓存的最佳场景是：大量请求共享长前缀（系统提示、few-shot 示例）。最差场景是：每个请求的输入都完全不同。

10.5 缓存驱逐 ​

显存有限，不可能缓存所有历史块。当空闲块耗尽时，需要驱逐一些缓存块：

驱逐遵循 LRU 策略，但有一个细节：链尾块优先驱逐。

同一时间戳释放的块中，链越长的块（更靠近尾部的块）被驱逐的优先级越高。原因是：

  • 链头的块包含公共前缀（如系统提示），被未来请求复用的概率最高
  • 链尾的块包含个性化内容（如用户特定输入），被复用的概率最低

这个策略最大化了缓存的命中率。

10.6 本章小结 ​

前缀缓存是 vLLM 的"免费午餐"：

  • 动机——共享前缀的请求大量重复计算 KV Cache
  • 哈希链——每个块的身份由 (父块哈希 + 当前 Token + 额外键) 唯一确定
  • 零开销实现——__slots__、打包键、惰性哈希、链表复用，V1 默认启用
  • LRU 驱逐——链尾优先驱逐，保护高复用率的公共前缀块
  • 收益——0% 命中时 < 1% 开销，有命中时 2-5 倍吞吐提升

源码导航

  • BlockPool（含缓存逻辑）：vllm/v1/core/block_pool.py
  • BlockHash/KVCacheBlock：vllm/v1/core/kv_cache_utils.py
  • KVCacheManager.get_computed_blocks：vllm/v1/core/kv_cache_manager.py

基于 VitePress 构建

Copyright © 2024-present 杨艺韬