前缀缓存：块哈希对基数树

主线位置：一个请求的一生里「调度 → 前缀命中」这一步：调度器决定这个请求有多少 token 可以跳过预填充。两个引擎都在调度器进程里做；vLLM 是 Python（块哈希在 EngineCore 收到请求时就算好），SGLang 的编排是 Python、树核心默认 Rust。

版本：vLLM v0.32.0、SGLang v0.5.22

结论先说：

• vLLM 的前缀缓存默认打开（enable_prefix_caching = True），按整块命中：每个满块一个链式哈希，查哈希表，遇到第一个不命中就停。
• SGLang 的 RadixAttention 默认打开，按 token 命中（page_size 默认 1）：沿基数树逐 token 比较。
• 差别有上界：同一份缓存内容，vLLM 每个请求最多比 SGLang 少命中 15 个 token。共享前缀短于一块（16 个 token）时，vLLM 一个都命中不了。
• 按两边源码规则写的 CPU 模拟里，共享 1000 个 token 系统提示的负载，命中率 82.4% 对 83.0%；多轮对话 90.5% 对 91.1%；显存紧时两者持平，SGLang 整叶驱逐反而多赶走一些 token。真实引擎的命中率和 TTFT 待实测（C3-3）。

vLLM：哈希怎么算

vllm/v1/core/kv_cache_utils.py

def hash_block_tokens(
    hash_function: Callable[[Any], bytes],
    parent_block_hash: BlockHash | None,
    curr_block_token_ids: Sequence[int],
    extra_keys: tuple[Any, ...] | None = None,
) -> BlockHash:
    # ...
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

一块的哈希 = H(前一块的哈希, 本块的 token, 额外键)。第一块的「前一块」是常量 NONE_HASH。因为带着前一块的哈希，第 i 块的哈希就代表了「从开头到第 i 块末尾的整个前缀」，查表时只要比这一个值。

flowchart LR
  none["NONE_HASH"] --> h0["h0 = H(NONE_HASH, 块0 的 16 个 token, 额外键)"]
  h0 --> h1["h1 = H(h0, 块1, 额外键)"]
  h1 --> h2["h2 = H(h1, 块2, 额外键)"]
  h2 --> tail["末尾不满 16 个的 token：不算哈希"]

几处细节：

• 只算满块。get_request_block_hasher 在请求创建和追加 token 时增量计算，不满一块就停。
• 算法：--prefix-caching-hash-algo 默认 sha256，先 pickle 再 SHA-256（cache.py、hashing.py）；可选 sha256_cbor（跨语言可复现）、xxhash、xxhash_cbor（快，非密码学）。
• NONE_HASH 的种子：设了 PYTHONHASHSEED 就用它；否则 SHA-256 用固定串 "vllm-none-hash"，xxhash 每个进程随机生成（resolve_none_hash_seed）。后果：用 xxhash 又不设 PYTHONHASHSEED，不同实例的块哈希对不上，跨实例的 KV 复用（连接器、KV 事件路由）就失效。
• KV cache 组：混合模型有多组 KV（比如全注意力层和滑动窗口层），查表的键是「块哈希 + 组号」（make_block_hash_with_group_id）。

额外键由 generate_block_hash_extra_keys 拼出来，四种：

多模态输入在 token 序列里是一串占位符，同一张图和另一张图的占位 token 完全一样；不把图的标识放进哈希，换一张图也会命中。

vLLM：怎么查，命中多少

vllm/v1/core/kv_cache_manager.py

        # NOTE: When all tokens hit the cache, we must recompute the last token
        # to obtain logits. Thus, set max_cache_hit_length to prompt_length - 1.
        # This can trigger recomputation of an entire block, rather than just
        # the single last token, because allocate_slots() requires
        # num_computed_tokens to be block-size aligned. ...
        max_cache_hit_length = request.num_tokens - 1
        computed_blocks, num_new_computed_tokens, num_uncached = (
            self.coordinator.find_longest_cache_hit(
                request.block_hashes, max_cache_hit_length
            )
        )

全注意力层的查找（FullAttentionManager.find_longest_cache_hit）从第 0 块往后逐个查哈希表，第一个不命中就停：链式哈希保证后面的也不会命中。命中长度 = 命中块数 × 16，且不超过 num_tokens - 1。

所以命中总是 16 的倍数。prompt 有 1000 个 token、前 1000 个都在缓存里时，vLLM 命中 ⌊999 / 16⌋ × 16 = 992 个，剩 8 个重算；SGLang 命中 999 个，只重算最后 1 个。

v0.32.0 有一个更细的命中单位 prefix_match_unit（cache.py），让命中可以停在块内部。它只在混合 Mamba 模型的 align 模式下生效（partial_hash_hits_enabled），普通模型仍按整块。

SGLang：没有哈希，键就是 token

基数树的子节点字典以 token（或一页 token）为键，匹配就是逐 token 比较，见 RadixAttention。节点上的 hash_value 只在开了分层存储或外部缓存连接时才算，用于跨层级、跨实例查找，不参与树内匹配。

vLLM 放进哈希的那些额外信息，SGLang 用别的办法表达：

两点值得留意。extra_key 和 lora_id 是直接字符串相加，中间没有分隔符，"ab" + "c" 和 "a" + "bc" 得到同一个命名空间；正常部署里 extra_key 由调用方控制，多数请求不带它。多模态占位值只取了哈希的 30 位，两张不同的图在同一位置、同样长度时，有约 2^-30 的概率得到同一串 token，从而共享 KV。两处都是读源码得到的推断，没有构造过实例验证。

驱逐谁先走

两边的 LRU 都把「共享的开头」留到最后：vLLM 靠倒序释放和引用计数，SGLang 靠只能删叶子。差别在粒度：vLLM 缺一块赶一块；SGLang 一次赶走一整片叶子，缺 10 个 token 也可能赶走 300 个。机制细节见 分页注意力 和 RadixAttention。

CPU 模拟：整块命中对 token 级命中

模拟是三个纯标准库的 Python 文件：vllm_blocks.py 实现 vLLM 的块池规则，radix_tree.py 实现 SGLang 的树规则，run.py 生成合成请求并驱动两边（python3 -I run.py 复现，--demo 打印上一页的两请求例子）。

规则与出处

简化了什么

• 请求入场时一次分配 prompt 加全部输出的空间；真实引擎随解码一块块（一个个槽位）分配。
• vLLM 输出 token 组成的满块，在请求结束时才登记进缓存；真实 vLLM 每步调度都登记刚写满的块。在下面的负载里，同一会话的下一轮总在上一轮结束后才开始，所以命中数不受影响。
• 同时最多 8 个请求持有 KV，先进先出地结束。没有分块预填充、抢占、投机解码；容量选得足够大，不会走到抢占。
• vLLM 的哈希表一个哈希只记一个块（真实实现允许多块同哈希）。这些负载里不出现并发重复计算，两者等价。
• SGLang 只建模 FULL 组件，不含分层缓存、会话缓存、EAGLE 的二元组键；page_size = 16 的变体只用在容量充足的负载上，因为分配器没有按页建模。
• token id 全局唯一，只有刻意共享的部分会命中。

关键代码

vLLM 一侧，入场时查前缀、取块、登记：

  def admit(self, rid, prompt, total_len, extra_keys=None):
    hashes = block_hashes(prompt, extra_keys)
    # KVCacheManager.get_computed_blocks: max hit = num_tokens - 1, and
    # FullAttentionManager.find_longest_cache_hit stops at the first miss.
    max_blocks = (len(prompt) - 1) // BLOCK_SIZE
    hit = []
    for h in hashes[:max_blocks]:
      b = self.pool.get_cached_block(h)
      if b is None:
        break
      hit.append(b)
    self.pool.touch(hit)
    # Simplification: allocate prompt + output slots at admission.
    need = -(-total_len // BLOCK_SIZE) - len(hit)
    blocks = hit + self.pool.get_new_blocks(need)
    # allocate_slots -> cache_blocks: prompt full blocks become hittable now.
    self.pool.cache_full_blocks(blocks, hashes, len(hit), len(hashes))
    self.reqs[rid] = (blocks, len(hashes), extra_keys)
    return len(hit) * BLOCK_SIZE

SGLang 一侧，入场时匹配、加锁、分配（不够就驱逐叶子）：

  def admit(self, rid, prompt, total_len):
    matched, node = self.match(prompt)
    # Req._compute_max_prefix_len: at most input_len - 1 tokens reused.
    hit = min(matched, len(prompt) - 1)
    self.lock(node, +1)
    self.alloc(total_len - hit)
    self.reqs[rid] = [node, hit]
    self._checkpoint(rid, prompt)  # checkpoint_kv_cache after prefill
    return hit

  def evict(self, need):
    heap = [n for n in self._leaves() if n.lock_ref == 0]
    heapq.heapify(heap)          # Node.__lt__ compares last_access
    freed = 0
    while freed < need and heap:
      leaf = heapq.heappop(heap)
      parent = leaf.parent
      del parent.children[self.child_key(leaf.key)]
      freed += len(leaf.key)
      # ...
      if parent is not self.root and not parent.children and parent.lock_ref == 0:
        heapq.heappush(heap, parent)
    self.free_slots += freed
    # ...

负载

• A / B：256 个请求，共享一段系统提示（A 为 1000 个 token，B 为 1008 = 63 × 16），后面各跟 20–400 个不重复的 token，输出 32–200 个。
• C：256 个请求，共享前缀只有 12 个 token，后缀 20–60，输出 16–64。代表短模板、短指令。
• D / E / F：32 个会话、每个 6 轮，共 192 个请求；共享 500 个 token 的系统提示；每轮的 prompt = 上一轮的 prompt + 上一轮的输出 + 30–200 个 token 的新消息，输出 50–300 个；会话随机交错。D 的 KV 空间足够大，E、F 分别只有 32768 和 24576 个 token（全部会话的不同 token 共约 5.6 万个）。

结果

（B 的基数树页 16 一行与页 1 相同，省略。驱逐次数的单位两边不同：vLLM 数块，SGLang 数节点。）

读这张表：

1. 差别全来自粒度。 基数树把页设成 16 后，A、C、D 三个负载的命中数和 vLLM 一个不差。
2. 差别有上界，通常不大。 A 里第一个请求之后，每个请求 vLLM 命中 992、SGLang 命中 1000，差 8 个 token，255 个请求共差 2040。系统提示恰好是 16 的倍数（B），两边相同。D 的多轮对话，每一轮上一轮的末尾不满一块，平均每个请求差约 7 个 token。
3. 共享前缀不到一块时，块哈希完全失效。 C 里 vLLM 命中 0，基数树每个请求命中 12 个，命中率 23.2%。
4. 显存紧时差别被驱逐策略抹平，甚至反过来。 F 里基数树命中略少（207317 对 207776），驱逐的 token 反而多（61030 对 59136）：它一次赶走整片叶子，多轮对话的叶子是一整轮的尾巴，缺几十个 token 也会赶走几百个。vLLM 按块驱逐，赶得刚好。

上一页的例子也出自这个模拟：两个请求共享 40 个 token 的系统提示，第二个请求在 vLLM 规则下命中 32 个（两块），在基数树规则下命中 40 个。

这些数只说明「规则本身」能复用多少 token。省下的预填充能换来多少 TTFT、真实的请求分布下命中率是多少，要在 GPU 上跑两个引擎才知道，待实测（C3-3）。

小结

• vLLM：块哈希 = H(前一块哈希, 本块 token, LoRA / 多模态 / cache_salt / embedding 额外键)，默认 SHA-256；只算满块，按块查，第一个不命中就停。
• SGLang：树里不用哈希，键就是 token；LoRA 和 cache_salt 作为第一层子节点键的命名空间，多模态把占位 token 换成由图像哈希得到的值。
• 命中粒度：vLLM 整块，每个请求最多少 15 个 token；共享前缀不到一块时命中为零。SGLang 默认逐 token，页设成 16 后与 vLLM 相同。
• 驱逐：两边都是 LRU，都把共享开头留到最后；vLLM 按块赶，SGLang 按整叶赶。
• 模拟里粒度带来的命中率差别在 0.4–0.6 个百分点（A、D、E），短前缀负载（C）除外；显存更紧时（F）差别消失。实测待 C3-3。