vLLM 与 SGLang 的前缀复用：Block Hash Chain vs Radix Tree

vLLM 和 SGLang 都支持共享前缀复用，但还是有很多人不知道二者的区别，今天我将会从源码的角度分析。

	vLLM	SGLang
核心数据结构	Block Hash + 哈希表	Radix Tree
前缀表示	prefix 被切成 KV Block 后逐块哈希	RadixKey 直接组织成树路径
上下文关系	当前 block hash 包含 parent block hash	父子节点天然表示前缀关系
匹配粒度	本文配置下为 16 token/block	由 page_size 决定；page_size=1 时可精确到 token
分叉方式	在 block 边界停止命中	可在一条边中间 _split_node()

---

1 vLLM： Block Hash Chain

源码 vllm/v1/core/kv_cache_utils.py：

def hash_block_tokens(hash_function, parent_block_hash,
                      curr_block_token_ids, extra_keys=None) -> BlockHash:
    """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
    return BlockHash(
        hash_function((parent_block_hash, tuple(curr_block_token_ids), extra_keys))
    )

其中 hash 的输入是：parent_block_hash，tuple(curr_block_token_ids)，extra_keys。这代表一个 KV Block 的身份不仅仅是当前 block 的 token，还包括前一个 block 的 hash 以及额外信息。

于是连续三个 block 会形成一条 hash chain：

H1 = hash(B1)

H2 = hash(H1, B2)

H3 = hash(H2, B3)

vLLM 官方设计文档同样把 block hash 描述为 parent hash + block tokens + extra hashes。

为什么要带 parent_block_hash？

因为 KV Cache 和上下文有关， 即使当前 block 的 token 完全相同，只要前面的上下文不同，该 block 对应的 KV Cache 也可能不同。如果只记录相同 block 的 hash，就可能把两个实际上不能复用的 KV Block 当成同一个。

例如：

seq1：CCBB | AAA
seq2：CCBC | AAA

只看hash("AAA") = hash("AAA")的话， 就可能把两个实际上不能复用的AAAblock 误判为同一个缓存块。加入父哈希后：

hash(hash("CCBB"), "AAA") != hash(hash("CCBC"), "AAA")

因此parent_block_hash 实际上是此前整个 prefix 的压缩表示。这也是 vLLM 能用一个 block hash 描述“ the tokens in the block and the tokens in the prefix before the block ”的原因。

extra_keys 是什么？

除了文本 token，vLLM 还会把一些额外信息加入 block hash，例如： LoRA 标识、multimodal input 信息、cache salt、prompt embeddings hash 等。这是因为仅仅 token 相同，不一定代表 KV Cache 可以复用。

例如 VLM 中两个请求都可能包含相同的 <image> placeholder，但传入的实际图片不同。

因此对于多模态请求，还需要把图片等输入的 hash 加入 key：

block identity = parent hash + token ids + multimodal hash

否则不同图片可能错误命中同一份 KV Cache。vLLM 官方 APC 文档也明确将 multimodal input hash 列为 block hash 的组成部分。

vLLM 如何查找共享前缀？

假设有请求为B1 → B2 → B3 → B4，可以依次得到H1 → H2 → H3 → H4，然后去缓存表查询，例如：

H1 = hash(NONE_HASH, B1, extra1)  hit
 ↓
H2 = hash(H1, B2, extra2)  hit
 ↓
H3 = hash(H2, B3, extra3)  hit
 ↓
H4 = hash(H3, B4, extra4)  miss

那么最长可复用前缀就是B1 + B2 + B3，到第一个 miss 就可以停止。最长可复用前缀即从第一个 block 开始，连续命中的 block hash。vLLM 的设计文档也是按“从左到右检查 block，第一次 miss 时结束”来描述 prefix lookup。

---

2 SGLang：Radix Tree

源码sglang/srt/mem_cache/radix_cache.py：

核心数据结构是 TreeNode：

class TreeNode:
    def __init__(self, id=None, priority=0):
        self.children = defaultdict(TreeNode)
        self.parent: TreeNode = None

        self.key: RadixKey = None
        self.value = None

        self.lock_ref = 0
        self.last_access_time = time.monotonic()
        self.hit_count = 0
        self.priority = priority

其中self.key不是固定大小的 block，而是可以保存一段变长 token 序列。 严格来说，self.key是RadixKey，除 token 序列外还包含extra_key、cache_salt等 namespace 信息，本文主要关注其中 token prefix 的组织方式。

例如两条请求：

A B C D E F
A B C X Y Z

对应的 Radix Tree 可以表示为一段共享树路径：

           root
             │
          [A B C]
          /     \
     [D E F]   [X Y Z]

关键函数_match_prefix_helper()：

def _match_prefix_helper(self, node, key):
    access_time = time.monotonic()
    node.last_access_time = access_time

    child_key = key.child_key(self.page_size)
    value = []

    while len(key) > 0 and child_key in node.children.keys():
        child = node.children[child_key]

        prefix_len = child.key.match(
            key,
            page_size=self.page_size,
        )

        if prefix_len < len(child.key):
            new_node = self._split_node(
                child.key,
                child,
                prefix_len,
            )

            value.append(new_node.value)
            node = new_node
            break

        else:
            value.append(child.value)

            node = child
            key = key[prefix_len:]

            if len(key):
                child_key = key.child_key(self.page_size)

    return value, node

这段代码就是标准的 Longest Prefix Match。

child_key = key.child_key(self.page_size)先根据当前待匹配 prefix 的开头，找到可能的 child。

然后child = node.children[child_key]进入对应分支，通过prefix_len = child.key.match(key, page_size=self.page_size)进行 prefix 比较。

其中prefix_len就代表“当前请求和树中此边共享的 token 数“。

体现 Radix Tree 特性的_split_node()：

当两个请求在一条 Radix Tree 边的中间发生分叉时，SGLang 会把公共部分拆出来，变成新的共享节点。

if prefix_len < len(child.key):
    new_node = self._split_node(
        child.key,
        child,
        prefix_len,
    )

其中_split_node的源码为：

def _split_node(self, key, child, split_len):

    new_node = TreeNode(priority=child.priority)

    new_node.children = {
        key[split_len:].child_key(...): child
    }

    new_node.key = child.key[:split_len]

    child.key = child.key[split_len:]

    child.parent = new_node

    new_node.parent.children[
        key.child_key(...)
    ] = new_node

    return new_node

源码中_split_node()将child.key[:split_len]放入新节点，同时把原 child 缩成后半段。这就是 Radix Tree 能精确表达请求之间 prefix 关系的关键。

例如，原来的：

root
 └── ABCDEF

拆分变成：

root
 └── ABC
      └── DEF

之后新请求再插入，就可以形成：

           ABC
          /   \
       DEF     XYZ

page_size 决定最终匹配粒度：

SGLang 通过 page_size决定命中的 token 长度。

match_prefix()的源码说明明确写着“当 page_size > 1 时，key 会先截断到 page_size 的整数倍再进行匹配。”

因此page_size = 1，可以命中任意长度的共享前缀。若是page_size = 16， 匹配和分裂边界会向下对齐到 16 token 的整数倍。

---

三、从源码看，两种方案的差异

假设两条请求共享前 100 token：

seq1: [t0 ... t99] + A ...
seq2: [t0 ... t99] + B ...

vLLM

本文配置block_size = 16，因为：

100 = 16 × 6 + 4

所以能够命中的完整 block 为 6，缓存命中 96 tokens，剩下 4 token 重新计算。

SGLang

本文配置page_size = 1，Radix Tree 可以直接在t99之后发生分叉：

        [t0 ... t99]
          /      \
         A        B

所以可以命中 100 tokens

源码结构

	vLLM	SGLang
共享前缀	连续 Block Hash	公共树路径
查	hash table lookup	沿树向下 longest-prefix match
分叉	下一个 block hash miss	_split_node()
本文匹配粒度	16 token	1 token
100-token 前缀	96 token	100 token

但是vLLM对于前缀的部分浪费并不代表其会造成吞吐差异，当共享前缀有几千 token，例如我之前实验中的 6448 tokens，即使 vLLM 最坏浪费 15 tokens 也只占 0.23%，基本已经可以忽略。

因此，两者在“表示共享前缀”上存在明显差异，SGLang 的 Radix Tree 可以更精确地表达分叉位置，而 vLLM 的 Block Hash 设计则直接复用了自身的 KV Block abstraction。

至于这种数据结构差异什么时候会真正转化成延迟或吞吐差异，还需要单独 benchmark。

---

四、KV Pool 容量大小不等于索引结构开销

我在 RTX 3050 Ti Laptop 4GB 上做 smoke test 时，得到过：

	SGLang 0.5.20	vLLM 0.28.0
权重占用	约 2.23 GB	约 2.47 GiB
KV Pool	2302 tokens	25008 tokens
启动耗时	约 50.5 s	约 50 s

刚开始我以为 Radix Tree 会占大量的显存，但是读了源码才发现 SGLang 中，mem_fraction_static 决定了模型权重和 KV Cache Pool 能使用多少静态显存：

\text{KV Cache Budget} \approx \text{mem_fraction_static}\times\text{GPU Memory} -\text{Model Weights}

剩余的显存作为 slack / headroom，留给 activation、CUDA Graph 等运行时开销。slack 不是 KV Cache，但它会占用原本可以分配给 KV Cache 的显存预算：

mem_fraction_static 越小
→ slack 越大
→ 留给 KV Cache 的空间越少
→ max_total_num_tokens 越小

因此，实验首先反映的是两套框架默认显存预算策略的不同，不能直接说明 Radix Tree 比 Block Hash 更占显存。