IRONMAN

vLLM 前缀缓存的命中流程：块哈希链、命中粒度与块的生命周期

前缀缓存要复用相同前缀的 KV，需要一层索引回答两个问题：这段前缀算过没有、它的 KV 在哪些块里。vLLM 的答案是一张平铺的字典，键是由块哈希串成的链；SGLang 的答案是 Radix Tree。

代码引用自 vLLM main 分支（2026-09-21 拉取）与 SGLang main 分支。

复用单位是块

vLLM 的缓存池由固定大小的块组成，默认每块 16 个 token：

# vllm/config/cache.py:71
DEFAULT_BLOCK_SIZE: ClassVar[int] = 16

块既是分配单位，也是复用单位。哈希粒度另由 prefix_match_unit 控制，默认取各缓存组块大小的最大公约数（vllm/v1/core/kv_cache_utils.py 中 hash_block_size = requested if requested is not None else math.gcd(*hashing_sizes)）。单组全注意力时它与块大小相等，都是 16。

分页与空闲队列是两层

分页机制解决按需分配：序列增长到需要新块时再申请，不必按最大长度预留连续显存。块表承担页表的角色，块对应页框。

空闲队列解决分配与回收顺序：下一个空闲块给谁、满了先回收谁。队列里的块正好是 ref_cnt 为 0 的那些。

  • 请求命中一个块，ref_cnt 加一，块移出空闲队列（BlockPool.touch，vllm/v1/core/block_pool.py:746）
  • 请求结束、ref_cnt 降到 0，块移回空闲队列（BlockPool.free_blocks，vllm/v1/core/block_pool.py:768）

块哈希是一条链

键的算法只有一个函数：

# vllm/v1/core/kv_cache_utils.py:649
def hash_block_tokens(hash_function, parent_block_hash, curr_block_token_ids, extra_keys=None):
    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_0 = Hash(Chunk_0) $$
$$ H_i = Hash(H_{i-1}, Chunk_i), \quad i > 0 $$

第 i 个块的键里嵌了第 i-1 个块的键，一路封到根。于是命中第 i 个键就等价于第 0 到第 i 个块全部命中。查找仍然从第 0 块起按顺序往后推进，差别在每一步只做一次字典查表，不比较 token。

索引结构是一张平铺字典：

# vllm/v1/core/block_pool.py:179
self.cached_block_hash_to_block: BlockHashToBlockMap = BlockHashToBlockMap()

字典的值是指向块的引用。键与键之间没有父子关系，只有内容上的包含关系。

只有满块才有键。Request.update_block_hashes 的文档字符串是 “Compute block hashes for any new full blocks and append them”（vllm/v1/request.py:281）。

一个 80 token 请求的完整流程

前提：这个 prompt 的前 30 个 token 与缓存中已有的某条链一致，后面 50 个不同。

第一步：请求创建时把 prompt 的键算完

Request.__init__ 末尾调用 update_block_hashes（vllm/v1/request.py:227）。80 除以 16 得 5 个满块，5 条键一次性算完，存进 request.block_hashes：

[h0, h1, h2, h3, h4]

“前 30 个 token 一致”这个信息在这一步用不上。切分按 16，第 1 块覆盖 token 16 到 31，其中 token 30、31 与缓存不同，整块内容就不同，键也不同。

P 阶段处理整个 prompt，D 阶段逐 token 生成。D 阶段每新增满 16 个 token 再追加一条，起点是：

# vllm/v1/core/kv_cache_utils.py:840
start_token_idx = len(request.block_hashes) * hash_block_size

P 阶段算出的这 5 条不重算。start_token_idx 以 len(request.block_hashes) 为起点，D 阶段按这个条数接着往后追加新满的块，不会回头重算 P 阶段的键。这个条数由请求自己记录，与查表无关。跨请求不复用：第二个请求哪怕 prompt 完全相同，也是新的请求对象，从空列表开始重算一遍。

第二步：逐块查表，首个未命中即停

KVCacheManager.get_computed_blocks（vllm/v1/core/kv_cache_manager.py:264）转到 find_longest_cache_hit（vllm/v1/core/single_type_kv_cache_manager.py:745）。循环体在同文件第 795 至 802 行：

for block_hash in itertools.islice(full_block_hashes, max_length // block_size):
    cached_block = block_pool.get_cached_block(block_hash, kv_cache_group_ids)
    if not cached_block:
        break
    ...
hit_length = len(computed_blocks[0]) * block_size

h0 命中，上一次那条链的第 0 块内容一致。h1 未命中，循环在这里 break，h2 到 h4 根本不去查。源码注释写着 “A missing block implies every later block misses too (chained hashes)”。

返回 hit_length = 1 * 16 = 16。默认配置下命中长度必然是 16 的倍数。

第三步：命中的块被取走，其余申请新块

allocate_slots（vllm/v1/core/kv_cache_manager.py:371）分两件事。

命中的块走 BlockPool.touch（vllm/v1/core/block_pool.py:746），文档字符串是 “This is used when a block is hit by another request with the same prefix”：ref_cnt 加一；如果它原先在空闲队列里，就把它摘出来。队列里的块 ref_cnt 都是 0，随时可能被淘汰，命中意味着它转成使用中。

剩下 80 – 16 = 64 个 token 需要 4 个块，走 get_new_blocks（同文件第 660 行），从空闲队列头部取。

登记结果形如 req_to_blocks[req_id] = [blk_0, blk_x, blk_y, blk_z, blk_w]，其中 blk_0 是命中复用的物理块，后四个是新分配的。这里的名字只用来表达顺序，实际槽号是整数，由空闲队列当时的状态决定。

第四步：P 阶段只算没命中的部分

num_computed_tokens 置为 16，前向计算从 token 16 开始。Attention 读 blk_0 里已有的 K/V 当作历史，只对后 64 个 token 计算新的 Q/K/V。

代价在这一步显形：token 16 到 29 这 14 个与缓存内容完全一致，却跟着一起重算。它们和内容不同的 token 挤在同一个块里，块边界卡在第 16 个 token，这 14 个没法单独拿出来复用。

第五步：D 阶段算出的 KV 写进新块

D 阶段每个 step 采样出新 token，这一步算出的 K/V 写进块表末尾的空槽。get_block_ids 给出这个请求的块表，长度等于逻辑块数 5，第 k 项是第 k 个逻辑块所在的缓存池槽号。token t 落在第 t // 16 项的第 t % 16 槽：token 16 落在第 1 项第 0 槽，token 79 落在第 4 项第 15 槽。

第 0 项是命中复用的 blk_0，后四项是本次新申请的块。槽号由分配那一刻空闲队列的状态决定，不同的机器上、同一个模型跑两次都会不同，这里只能给出形状。槽号本身与转换后的物理地址是两回事：kernel 拿它乘 kv_block_stride 算出数据指针，那个指针处于 GPU 虚拟地址空间，再由 GPU MMU 完成硬件地址翻译，两层映射见《PagedAttention：KV Cache 的分页、块表寻址与换页边界》。

第六步：每满 16 个 token 算一条键，新满的块用这条键注册

D 阶段每产出一个 token，append_output_token_ids 就调一次 update_block_hashes（vllm/v1/request.py:279、第 281 行）。token 数凑满 16 的倍数时追加一条新键，起点仍是 len(request.block_hashes) * hash_block_size，P 阶段那 5 条不重算。

这条键有两个用途，都在块填满这一步兑现：把新满的块登记进字典，让下一个请求能查到它；下一个请求在 P 阶段算出同一个键时，查表命中。

登记发生在下一个 step 的 allocate_slots 末尾（vllm/v1/core/kv_cache_manager.py:606）：

num_tokens_to_cache = min(total_computed_tokens + num_new_tokens, request.num_tokens)
self.coordinator.cache_blocks(request, num_tokens_to_cache)

这一步转到 BlockPool.cache_full_blocks（vllm/v1/core/block_pool.py:224）。键已经在请求侧算好，缓存管理器只是取现成的键写表。cache_full_blocks 的文档字符串写着 “The block hashes values are computed by the Request object immediately when it is created and when new tokens are appended.”

第七步：请求结束

KVCacheManager.free（vllm/v1/core/kv_cache_manager.py:610）转到 BlockPool.free_blocks（vllm/v1/core/block_pool.py:768）：ref_cnt 减一，归零的块放回空闲队列。哈希条目保留，这正是下一次同前缀请求能命中的原因。引用计数归零只表示块进入可淘汰集合，不表示立刻回收。

命中粒度的两个代价

尾部不满一块的前缀永远命中不了

80 token 恰好是 5 个整块，边界对齐。上面的例子里，与缓存一致的前缀有 30 个 token，只命中了 16 个，亏 14 个。

前缀长度落在 16 的倍数上时不亏；落在中间就亏掉一段。相同的前 5 个 token、后面不同，且分界不在第 16 个 token 上，这两段就完全不复用。

全部命中也要重算一个块

get_computed_blocks 里有一行（vllm/v1/core/kv_cache_manager.py:295）：

max_cache_hit_length = request.num_tokens - 1

注释解释：即使所有 token 都命中，也需要重算最后一个 token 才能拿到 logits。而 allocate_slots 要求 num_computed_tokens 按块对齐，于是这个“最后一个 token”会连带整个块一起重算。

80 token 的 prompt 全部命中时，79 // 16 = 4，最多命中 4 块，即 64 个 token，最后一块（token 64 到 79）重算。源码注释也承认这一点：“This can trigger recomputation of an entire block, rather than just the single last token.”

缓存里的块不会被覆写

引用计数

命中的块 ref_cnt 加一；空闲队列里只放 ref_cnt 为 0 的块。get_num_common_prefix_blocks（vllm/v1/core/single_type_kv_cache_manager.py:891）用 block.ref_cnt == len(self.req_to_blocks) 判断哪些块是所有请求共用的前缀，从第 0 块开始数，遇到第一个不满足的就停。

三类空闲块

  1. 从未使用过的块
  2. 淘汰过的块，哈希条目已经删掉
  3. 刚被结束的请求释放的块，哈希条目还在

第三类被 get_new_blocks 取走时，会先执行 _maybe_evict_cached_block（vllm/v1/core/block_pool.py:723）删掉它的哈希条目，然后才交给请求写。一个块离开空闲队列的那一刻，就不再是任何请求的命中目标。

于是本次算出的 KV 落进的物理块，在写入之前都已经从缓存条目中注销。旧链的第 1 到第 4 块要么已被淘汰，要么是另一条内容不同的链（键是另一组），不会被写。命中复用的 blk_0 全程只读。

物理位置可以复用，复用的前提是那个块的缓存身份已经注销，两件事绑在一起，不会出现“字典说有、内容已经被换掉”。

一个例外：继续往已登记的块里写

请求接着往一个已经登记进字典的块里写时（未满块按更细的哈希粒度登记的场景），move_block_hashes（vllm/v1/core/block_pool.py:642）把字典条目改指向一个私有副本，原块留给请求继续写。文档字符串：“the prefix cache holds a private copy (dst_block) under the same hashes instead”。

淘汰顺序与不可达条目

释放请求的块时按逆序放回空闲队列（vllm/v1/core/single_type_kv_cache_manager.py:585）：

# Free blocks in reverse order so that the tail blocks are freed first.
self.block_pool.free_blocks(reversed(self.pop_blocks_for_free(request_id)))

链尾排在队列前面，链头排在后面，淘汰从链尾开始。前缀被从后往前截断，命中长度逐渐变短，剩下的前缀一直可用。空闲队列本身按 LRU 组织（vllm/v1/core/kv_cache_utils.py:246 的类文档），被其他请求命中的块会从队列中摘出，释放时重新排到队尾。

“祖先的条目没了、后代的条目还在字典里”这种不可达条目，在正常的队列淘汰路径下不会出现，因为链尾先走。

BlockPool.evict_blocks（vllm/v1/core/block_pool.py:801）是 KV connector 使用的接口，文档字符串写着它“only evicts blocks that are currently cached (have a hash). blocks with ref_cnt > 0 are not freed from the block pool, only evicted from the prefix cache hash table”。它可以只摘掉任意一批块的条目，此时后代的条目会变成查不到的孤儿：新请求探到缺失的那一环就停，不会继续往下查。这类条目不会泄漏（那些块的 ref_cnt 为 0，本来就在空闲队列里，被分配时顺手删掉），但在被分配之前不产生任何命中。

与 Radix Tree 的对比

SGLang 的 RadixAttention 用树做索引，KV 仍然存在分页池里：token_to_kv_pool_allocator 负责分配，req_to_token_pool.req_to_token 是块表的等价物，radix_cache 里的 page_size、page_aligned 都来自这一层。默认 page_size = 1，即命中粒度精确到单个 token。树只是索引结构，与存储是否分页无关。

vLLM 块哈希链 SGLang Radix Tree
索引 平铺字典，键为链式块哈希 前缀树，节点为 token 段
命中粒度 block_size，默认 16 page_size，默认 1
祖先信息 嵌在键里 由父子指针表达
每步动作 查一次字典，不比较 token 先按子键查字典，再逐 token 比一段（child.key.match，radix_cache.py:729、第 739 行）
匹配终止 首个未命中即停 走到不匹配的那一层
边界处理 不涉及 命中落在节点中间时分裂节点（_split_node，radix_cache.py:755）
共享的显式表示 无，只体现为引用计数 节点自身共享
反向查询 给一个键枚举不出后代 遍历子树
淘汰 空闲队列 LRU，链尾先 叶子按 LRU 逐层向上（evict，radix_cache.py:643）

引用计数的语义两边一致，都在阻止正在被使用的缓存被回收。

SGLang 的 lock_ref 归零时只把 token 数从 protected_size_ 移回 evictable_size_（dec_lock_ref，radix_cache.py:688），节点留在树里；删除只发生在 evict(num_tokens)，触发条件是显存不足。进入 evictable_leaves 要求节点没有未淘汰的子节点（_update_leaf_status，radix_cache.py:871），所以淘汰同样叶先父后，不会留下不可达的节点。

取舍在于：哈希链让每个块自带祖先信息，查表代价与结构维护都很低，代价是粒度锁在块边界；Radix Tree 能在 token 粒度上精确表示最长公共前缀，代价是分裂、合并与节点管理。

参考资料

  • vLLM main 分支：vllm/config/cache.py、vllm/v1/request.py、vllm/v1/core/kv_cache_utils.py、vllm/v1/core/block_pool.py、vllm/v1/core/kv_cache_manager.py、vllm/v1/core/single_type_kv_cache_manager.py、vllm/v1/core/sched/scheduler.py
  • SGLang main 分支：python/sglang/srt/mem_cache/radix_cache.py
  • vLLM V1 前缀缓存文档
  • 站内：《PagedAttention：KV Cache 的分页、块表寻址与换页边界》