Nano-vLLM 源码解读 - 5. Prefix Cache

nano-vllm 用千行代码拆解 vLLM 核心,是读懂大模型推理最快的捷径。

L4 给 BlockManager 留下了三个问题。hash_to_block_id 是块级复用的反向索引,但块的 hash 到底是怎么算出来的、为什么算出来的 hash 能保证"前缀相同则 hash 相同"——这个 hash 函数具体怎么实现,L4 没说;can_allocate 返回 num_cached_blocks、allocate 真正把命中的物理块写入 seq.block_table 并对每块 ref_count += 1,中间的流程怎么走,L4 也没说;L4 第 6 节解释了 reversed(seq.block_table) + deque popleft 让前缀块排到队尾,但这套方向性是否就是 LRU?prefix cache 还需不需要专门的 LRU 数据结构?

三个问题指向同一件事:两条请求共享同一段前缀时,BlockManager 内部从入场判定到状态登记到 LRU 时间序,完整地走了哪几步?核心新概念是 compute_hash(token_ids, prev_hash) 的链式构造,其余流程围绕它收束。

读完你能:

• • 解释为什么 compute_hash 必须把上一块的 hash 作为种子,而不是只算当前块的 token 序列
• • 在给定 block_size=4、两条请求前 8 个 token 相同的设定下,手动追出 can_allocate / allocate / hash_blocks 各自对四个数据结构(blocks / free_block_ids / used_block_ids / hash_to_block_id)的修改顺序
• • 说明 hash_blocks 为什么只对"本步刚写满"的块注册,而跳过半满尾块
• • 解释 prefix cache 没有专门的 LRU 数据结构这一事实:L4 第 6 节的 deque 时间序已经够用,没有额外引入任何 LRU 机制

1. 系统位置

既然 prefix cache 不引入新模块,这三个问题到底对应 BlockManager 的哪几行?

图里浅黄色的 BlockManager 主体框、四个数据结构、5 个公开 API 名称都来自 L4 第 3-4 节;橙色高亮的四块(三个 API + 中央的 compute_hash 辅助函数)是 L4 略过、需要补齐的位置;hash_to_block_id 也用橙色边框强调,因为它是块级复用反向索引的核心入口,四个补齐点都要读写这张表。灰色虚线框对应 L4 已讲、与 prefix cache 不直接相关的其他 API(can_append / may_append / deallocate),只占位以保持结构完整。

四块高亮内容:

• • compute_hash:链式 hash 函数本身。
• • can_allocate 里的 hash 表查找循环:数出本条 seq 前缀可复用几块。
• • allocate 里的复用/新申请分支:对每一块要么 ref_count += 1 复用、要么 _allocate_block 全新申请。
• • hash_blocks 的注册时机:prefill 结束、刚写满的块注册到 hash_to_block_id。

四块共用同一个 hash 函数和同一张反向索引:compute_hash 给每块算指纹,can_allocate 用指纹数命中块数,allocate 用同一指纹把命中的物理块写入 seq.block_table、把未命中的位置补齐,hash_blocks 在 prefill 结束时把刚写满的块注册到索引,供下一条请求复用。

2. 链式 hash 的构造

L4 的 hash_to_block_id 用 hash 做反查键,但这个 hash 到底是怎么算的、为什么前缀相同就能算出相同 hash?直接拿 token 序列做指纹够吗?

2.1 是什么

compute_hash 是把"一块 token 序列"映射成 64 位指纹的函数。它额外接受一个参数 prev_hash,把上一块的指纹也作为输入,充当本块指纹的种子。

@classmethoddefcompute_hash(cls, token_ids: list[int], prefix: int = -1):    h = xxhash.xxh64()if prefix != -1:                          # prefix == -1 表示这是第 0 块,没有前驱        h.update(prefix.to_bytes(8, "little"))    h.update(np.array(token_ids).tobytes())return h.intdigest()

记 h_i 为第 i 块的 hash,tokens_i 为第 i 块的 token 序列,则:

• • h_0 = xxhash(tokens_0)
• • h_i = xxhash(h_{i-1} || tokens_i),|| 是字节拼接

h_0 是首块,没有前驱,所以 prev_hash 默认值 -1 触发 if prefix != -1 短路,只 hash 当前块 token;h_i (i ≥ 1) 先把前一块指纹的 8 字节写入 xxhash 状态、再把当前块 token 写入,等价于把两段字节拼接后整体 hash。递归展开后 h_i 实质上是从第 0 块到第 i 块整段前缀的指纹:任一前驱块内容变化都会让本块及之后所有块的 hash 偏移。

这条链让指纹不只刻画"当前块这段 token",还刻画"这段 token 之前的整段前缀",正是 prefix cache 反查表的判等需求——只有前缀完全相同,才允许共享同一物理块的 KV。

图分上下两部分。上半是链式构造:每个 hash 块上方既有当前块的 token,又有上一块的 hash 输出;箭头从前一块的输出指向后一块的输入,直观表达"递归依赖";块中央的虚线分隔上下两部分,上半是输入(tokens),下半是 hash 函数与输出指纹;右侧"递归展开:h_i 实际刻画整段前缀"是对链式作用的简短总结;第三块标记为 A_i tokens 加省略号,用泛化下标表示链向第 i 块推广,A0 与 A_i 之间可以有任意多块。下半是反例,与 第 2.2 节的论证对应。

2.2 为什么必须链式

直觉上,要给一段 token 序列算指纹,只 hash 这段 token 本身就够了。但 prefix cache 这里必须把上一块的 hash 也作为输入,原因是单看 token 序列的指纹无法区分"前缀不同的两块",会发生下面这种错误命中。

• • 请求 A 的 prompt:[I, like, cats, ., I, dislike, dogs, .],block_size = 4,切成两块——A0 = [I, like, cats, .]、A1 = [I, dislike, dogs, .]。
• • 请求 B 的 prompt:[I, dislike, dogs, .](只有一块),记为 B0。

反例(非链式 h_i = xxhash(tokens_i)):A1 与 B0 的 token 序列完全相同,因此 hash(A1) == hash(B0)。当请求 B 到达、对 B0 算 hash 去 hash_to_block_id 查表时,会命中 A1 这个物理块。但 A1 与 B0 的 K/V 内容完全不同——根源在 attention 的加权聚合过程。

上图以两条请求最后一个 token "." 为例,展示 attention 怎么把前缀的 v 拉进当前 token 的输出。

• • 上半蓝色:请求 A 算 A1 最后一个 "." 的 attention 时,因果掩码让它能看到 A0 的全部 4 个 v(浅灰)以及 A1 自己前面 3 个 v(蓝色),共 7 项加权和。A0 的 v(I)、v(like)、v(cats)、v(.) 真实出现在 A1 的 attention output 公式里。
• • 下半紫色:请求 B 算 B0 最后一个 "." 的 attention 时,B0 是首块、没有任何前缀,前缀位置(虚线框)里是空集 ∅,只能聚合 B0 自己前面 3 个 v(紫色),共 3 项加权和。
• • 底部红色:7 项加权和 ≠ 3 项加权和。这个 attention output 进入 transformer 下一层,作为算下一层 K/V 的输入。所以 A1 下一层的 K/V 携带 A0 的注意力痕迹,B0 下一层的 K/V 不含任何前缀信息——两条请求虽然 token 相同,从第二层开始 K/V 就一直不同。

KV cache 按层缓存每一层的 K/V。若 B 错误复用 A1 的物理块,B 后续 decode 读到的是 A 受 A0 影响的 K/V,输出彻底错位。反例错在这里:hash 只刻画"这一块的 token 序列",无法表达"这一块之前的前缀"。

正例(链式 h_i = xxhash(h_{i-1} || tokens_i)):A1 的 hash 是 xxhash(h_A0 || A1.tokens),B0 是首块,h_B0 = xxhash(B0.tokens)(无前驱)。两式的输入字节构成完全不同,xxhash 不会算出相同结果,B 查表 miss,不会错误命中。

上图下半部分把这次错误共享画了出来:左侧"请求 A(两块)"框内的 A0、A1 与右侧"请求 B(单块)"框内的 B0 都用红色实线框圈出,表示它们都是非链式 hash 下被错误等价的对象;A1 与 B0 之间那条红色虚线弧表示这两块在非链式 hash 下算出相同结果、发生错误命中;图底部灰色小字"链式 hash 下:h_A1 = … 形式不同,不会碰撞"是对正例的总结——同一组输入在链式下不会复现这条弧。

链式 hash 让"前缀完全相同则 hash 相同"成立——任一前缀位置 token 不同,本块 hash 就不同;前缀完全相同时,hash 才一致。

你可能以为反过来也成立:"hash 相同则前缀完全相同"。但 64 位指纹仍有 2^-64 量级的碰撞概率,极小但非零——一旦碰撞,两条逻辑上不同的前缀会算出同一 hash。为此 nano-vllm 在 hash 命中后还会做一次完整的 token_ids 比较,比较失败则退回到全新申请分支。这一次完整比较在 L4 第 4.1 节已经介绍,后续流程会用到。

3. 两条请求共享前 8 个 token 的完整状态变迁

hash 函数本身已经清楚。真到一条新请求进来时,这条链怎么一步步把四个数据结构改写?

3.1 场景设定

• • block_size = 4,初始 free_block_ids = deque([0, 1, 2, 3, 4, 5]),used_block_ids = set(),hash_to_block_id = {}。
• • 请求 A 的 prompt 长 12 个 token,切成 3 块:A0、A1、A2。
• • 请求 B 的 prompt 长 10 个 token,前 8 个 token 与 A 完全相同(B0 == A0,B1 == A1),后 2 个 token 不同(B2 仅含 2 个 token,半满)。

两条请求共享前 2 块(共 8 个 token)。四个时间点 t1-t4 聚焦"块对齐"的主复用路径;半满块 B2 在 t4 只占一个位置不影响判定,关于它的特殊处理放到 第 4 节。

图中横向自左向右的紫色箭头表示时间从 t1 推进到 t4。标注的"行"中,前四行(free_block_ids / used_block_ids / blocks ref_count / hash_to_block_id)正是 BlockManager 内部的四个数据结构;最末一行 seq.block_table 是 BlockManager 写到 seq 上的产物,与四个数据结构同步显示便于对照阅读。free_block_ids 行 t1 列底部"队头 → ← 队尾"标注 deque 的两端方向,提醒分配从队头 popleft、归还从队尾 append(L4 第 6 节已介绍)。

3.2 时间点 t1:请求 A 进入 can_allocate

can_allocate 逐块算 hash 去 hash_to_block_id 里查,数能复用几块;它是只查不改的纯函数。

defcan_allocate(self, seq) -> int:    h = -1    num_cached_blocks = 0    num_new_blocks = seq.num_blocksfor i inrange(seq.num_blocks - 1):           # 末块通常半满,不查        token_ids = seq.block(i)        h = self.compute_hash(token_ids, h)        # 链式:把上一块的 h 作为种子传入        block_id = self.hash_to_block_id.get(h, -1)if block_id == -1orself.blocks[block_id].token_ids != token_ids:break# 链断了,后面就不必再查        num_cached_blocks += 1if block_id inself.used_block_ids:            num_new_blocks -= 1iflen(self.free_block_ids) < num_new_blocks:return -1# 装不下,留给 Scheduler 触发抢占return num_cached_blocks

请求 A 是系统中的首条请求,hash_to_block_id 为空,第 0 块查表立即 miss,循环 break,返回 num_cached_blocks = 0。num_new_blocks 保持 3,与 free_block_ids 的 6 个空闲块相比足够,通过容量校验。

四个数据结构在 t1 都未变化:hash_to_block_id 仍为空,free_block_ids 仍为 [0,1,2,3,4,5],used_block_ids 仍为空,blocks 里每个 Block 的 ref_count 仍为 0。

注意循环边界 for i in range(seq.num_blocks - 1) 而不是 range(seq.num_blocks)——遍历范围只覆盖前 num_blocks-1 块,末块跳过。物理含义是:末块通常未写满,半满块的 hash 在它写满前不会被 hash_blocks 注册到反向索引(第 4 节中的注册时机),查也是 miss,直接跳过,略过一次 hash 计算。

3.3 时间点 t2:请求 A 进入 allocate

allocate 拿到can_allocate返回的num_cached_blocks后,前num_cached_blocks块走复用分支,其余块走全新申请。复用分支内部又分两种情况:命中块仍被某条 seq 持有(在used_block_ids里),则ref_count += 1;命中块已被释放(在free_block_ids里、ref_count == 0、但 hash 与反向索引仍有效),则从free_block_ids取出、ref_count置 1、加入used_block_ids。

defallocate(self, seq, num_cached_blocks):assertnot seq.block_table    h = -1for i inrange(num_cached_blocks):             # 前 num_cached 块走复用分支        token_ids = seq.block(i)        h = self.compute_hash(token_ids, h)        block_id = self.hash_to_block_id[h]        block = self.blocks[block_id]if block_id inself.used_block_ids:            block.ref_count += 1# 仍在用 → 引用计数加一else:            block.ref_count = 1# 已释放但 hash 未失效 → 取回再用self.free_block_ids.remove(block_id)self.used_block_ids.add(block_id)        seq.block_table.append(block_id)for i inrange(num_cached_blocks, seq.num_blocks):  # 剩余块走全新申请        seq.block_table.append(self._allocate_block())    seq.num_cached_tokens = num_cached_blocks * self.block_size

对请求 A,num_cached_blocks = 0,第一个 for 循环不执行;第二个 for 循环把全部 3 块走 _allocate_block,从 free_block_ids 队头依次 popleft 出 0、1、2,得到 A.block_table = [0, 1, 2]。

t2 结束时:

• • free_block_ids:[3, 4, 5]
• • used_block_ids:{0, 1, 2}
• • blocks[0/1/2].ref_count:都为 1
• • hash_to_block_id:仍为空——_allocate_block 不算 hash,hash 计算与注册要等 prefill 算完才发生
• • A.num_cached_tokens = 0

allocate 只把"准备好接收 KV 的物理块" 对应的 block_id 写入 seq.block_table;hash 注册由 hash_blocks 负责。

3.4 时间点 t3:请求 A prefill 完成、hash_blocks 把写满的块注册到索引

A 的 prefill 把 12 个 token 的 K/V 算好写入物理块 0、1、2。3 块都正好写满(12 = 3 × 4),hash_blocks 在 postprocess 阶段把这 3 块逐个注册到反向索引。

defhash_blocks(self, seq):    start = seq.num_cached_tokens // self.block_size    end = (seq.num_cached_tokens + seq.num_scheduled_tokens) // self.block_sizeif start == end: return    h = self.blocks[seq.block_table[start - 1]].hashif start > 0else -1for i inrange(start, end):        block = self.blocks[seq.block_table[i]]        token_ids = seq.block(i)        h = self.compute_hash(token_ids, h)        block.update(h, token_ids)self.hash_to_block_id[h] = block.block_id

start 是本步开始前 seq 已经 hash 注册过的块数边界——num_cached_tokens 是已经被 cache 命中或上一段 prefill 写满的 token 数,除以 block_size 得到"上一次 hash 截止到第几块"。end 是本步结束时累计写满的块数边界——num_cached_tokens + num_scheduled_tokens 是 prefill 结束时这条 seq 已经覆盖的 token 总数,除以 block_size 取整得到"本步累计写满到第几块"。两者之差即本步新写满的块数,循环范围 range(start, end) 就是本步要算 hash 的块。

if start == end: return 表示本步没有任何新块被写满——例如 chunked prefill 还在前一块的中段,没越过块边界,就不必算 hash。

循环体里 block.update(h, token_ids) 把本块的 hash 与 token 序列写回 Block 对象。后续即便这块被释放回 free_block_ids,只要 _allocate_block 还没把它 popleft 出来覆写,Block.hash 与 Block.token_ids 都还在原位——第 3.6 节的 else 复用分支正是靠这两个字段才能取回再用,L4 第 4.1 节介绍的内容碰撞防护也靠 token_ids 做最后比对。

链式延续靠这一行:h = self.blocks[seq.block_table[start - 1]].hash if start > 0 else -1。start > 0表示前面已有 hash 链,从start - 1这块的Block.hash取出作为本段种子——Block.hash字段就是block.update(h, token_ids)写入的,deallocate不会清除它,所以即便上一段是几个 step 前完成的,这块的Block.hash仍可直接读到;start == 0表示这是 prefill 第一段,没有前驱,从-1起步,与can_allocate首次进入时的种子保持一致。chunked prefill(一个 prefill 被切成多个 step)反复进入hash_blocks,多段拼起来,最终算出的 hash 与单段一次性 prefill 完全相同,确保后续请求查表能命中。chunked prefill 的具体调度规则不在本讲范围。

对请求 A 首次 prefill,start = 0、end = 3,链式 hash 从 h = -1 起步:

• • 块 0:h_0 = compute_hash(A0_tokens, -1),blocks[0].hash = h_0,hash_to_block_id[h_0] = 0
• • 块 1:h_1 = compute_hash(A1_tokens, h_0),blocks[1].hash = h_1,hash_to_block_id[h_1] = 1
• • 块 2:h_2 = compute_hash(A2_tokens, h_1),blocks[2].hash = h_2,hash_to_block_id[h_2] = 2

t3 结束时:

• • hash_to_block_id:{h_0: 0, h_1: 1, h_2: 2}
• • 其余三个结构与 t2 相同

请求 A 的前 12 个 token 现在既在 KV pool 里物理存在,也通过 hash 链注册到反向索引中。

3.5 时间点 t4:请求 B 到达,前 8 个 token 命中复用

can_allocate 对 B 逐块算 hash:

• • 块 0:B0_tokens == A0_tokens,所以 compute_hash(B0_tokens, -1) == h_0,hash_to_block_id[h_0] = 0 命中。blocks[0].token_ids 与 B0_tokens 比对相等(同一段 token 算出同一 hash 是正常情况,这一步排除 64 位指纹的极少数碰撞),num_cached_blocks 加到 1。blocks[0] 在 used_block_ids 中(仍被 A 持有),所以 num_new_blocks 减 1。
• • 块 1:B1_tokens == A1_tokens 且本次 h = h_0(链式延续),所以 compute_hash(B1_tokens, h_0) == h_1,命中 blocks[1],token 比对通过,num_cached_blocks 加到 2,num_new_blocks 再减 1。
• • 末块(块 2)循环不查:can_allocate 的循环到 num_blocks - 1 就停(第 3.2 节的循环边界设计——末块通常半满,半满块的 hash 没注册到反向索引,查也是 miss)。这里 B 的末块 B2 正好半满,跳过对计数没影响。

num_cached_blocks = 2,num_new_blocks = 3 - 2 = 1,free_block_ids 还剩 3 个,通过校验,can_allocate 返回 2。

allocate(B, 2):

• • 前 2 块走复用分支。blocks[0].ref_count 从 1 加到 2(A 和 B 同时持有),blocks[1].ref_count 从 1 加到 2。两块都在 used_block_ids 中,因此走 block.ref_count += 1 一行,不动 free_block_ids、不动 used_block_ids。B.block_table 前两位填上 0、1。
• • 剩 1 块走 _allocate_block,从队头 popleft 出 3,得到 B.block_table = [0, 1, 3]。

t4 结束时:

• • free_block_ids:[4, 5]
• • used_block_ids:{0, 1, 2, 3}
• • blocks[0/1].ref_count:都为 2(共享块)
• • blocks[2].ref_count:1(A 独占)
• • blocks[3].ref_count:1(B 独占,等待 prefill 写入)
• • hash_to_block_id:仍为 {h_0: 0, h_1: 1, h_2: 2},本次复用不动这个表
• • B.num_cached_tokens = 8——本条 seq 已经命中 8 个 token,prefill 时只需算后 2 个

"两条请求共享前 8 个 token"在 BlockManager 内部的完整状态变迁就是这样:没有新增任何数据结构,只是在 _allocate_block 之外多走了一条复用分支,把已命中物理块的 ref_count 加一。

3.6 复用分支的另一条路径

t1-t4 的场景里,A 在 B 到达时仍持有共享块,所以复用分支只走了 ref_count += 1 一条路径(命中块在 used_block_ids 中)。第 3.3 节代码里 if/else 还有另一条路径:命中块当前在 free_block_ids 中、ref_count == 0,从队列取出、ref_count 置 1、加入 used_block_ids。这条路径在 A 已经执行完 prefill+decode、被 deallocate 释放、B 才到达的场景下触发。

你可能以为请求结束、deallocate 时应该把这些块的 hash 和hash_to_block_identry 一并清掉——既然块都释放了,KV 也算"过期"了,索引留着只占内存。但 nano-vllm 的做法是deallocate既不清Block.hash也不删hash_to_block_id里的 entry(L4 第 3 节介绍_allocate_block里那行清除旧 hash 的安全守卫时就铺垫过这一点)——原因是物理块的ref_count归零、回到free_block_ids队尾后,只要它还没被_allocate_blockpopleft 出去覆写,KV 数据物理上仍在 KV pool 里,反向索引里的 entry 仍指向这个 block_id。A 释放后,B 一旦带相同前缀到达,就能通过 第 3.3 节代码里 else 分支把它从free_block_ids 取回再用,KV 数据不必重算。

结合 L4 第 6 节介绍过的 deallocate 倒序释放让前缀块排到 free_block_ids 队尾:前缀块释放后会在 free 队列里待得最久,期间它的 hash 反查仍然有效,任何带相同前缀的新请求都能命中并取回再用——这是 prefix cache 跨请求复用的另一条关键路径。

3.7 这一切节省了什么

t4 之后 B 进入 prefill。如果 prefix cache 不存在,B 要把全部 10 个 token 都走一遍 prefill。现在 B.num_cached_tokens = 8,B 的本步 prefill 只算后 2 个 token——前 8 个 token 不再进入本步前向计算,只是 attention 时仍需读取它们对应的 KV(那部分 KV 已经在 KV pool 里,由块 0、1 提供)。

prefix cache 在 GPU 端如何读已 cached 的 KV、本步新 token 的 KV 如何写入剩余 slot,与 BlockManager 解耦,不在本讲范围。所有效果都体现在 B.num_cached_tokens = 8 这一个整数上:从 BlockManager 的视角看,prefix cache 命中就是把这个整数从 0 改写成 8。

4. hash_blocks 的注册时机

第 3.4 节已贴出 hash_blocks 的实现,其中"跳过半满尾块"这一行写得不显眼,但它是 prefix cache 唯一的自动维护动作。为什么必须跳过半满块?这一块的 hash 在它写满前为什么不能注册到索引?

4.1 触发位置

hash_blocks 由 Scheduler 在 prefill 的 postprocess 阶段调用,处理本步刚写入 KV 的所有 seq。它不修改 seq.block_table,只把"本步内已被写满"的块注册到 hash_to_block_id。

4.2 哪些块算"本步刚写满"

start 与 end 这两行界定本步处理范围:

• • start = num_cached_tokens // block_size——本步开始前已 cached 的 token 折算成块数,即"上一次 hash 截止到第几块"。首次 prefill 这值为 0;chunked prefill 续算时是上一段的累计块数。
• • end = (num_cached_tokens + num_scheduled_tokens) // block_size——本步结束时累计已算 token 数折算成块数,即"这次累计能写满第几块"。

整数除法的语义是"向下取整",end 自然只数已写满的块,半满的尾块对应的余数被舍去,不进入循环范围。举一个具体例子:假设这是首次 prefill,num_cached_tokens = 0、本步要算的 token 数 num_scheduled_tokens = 10、block_size = 4,则 start = 0 // 4 = 0、end = 10 // 4 = 2——本步写入 10 个 token,前 8 个写满了块 0、1,第 9-10 个写在块 2 的前两个 slot,块 2 半满。循环范围 range(0, 2) 只算块 0、1 的 hash,块 2 跳过。

图分左右两个场景。左场景 num_scheduled_tokens = 10、block_size = 4:绿色实线框表示本步写满、需要算 hash 并注册到索引的块(块 0、1),红色虚线框表示半满块(块 2),它对应的 slot 中后两格用灰色填充表示尚未写入 token,被整除截断舍去,不进入循环范围,hash_to_block_id 只新增 2 个 entry。右场景 num_scheduled_tokens = 12:块 0、1、2 都正好写满,三块都被绿色实线框圈出,hash_to_block_id 新增 3 个 entry。每块内部的 t₀…t₁₁ 是 token 槽位编号,从左到右标注本块占据的 token 在整段 seq 中的位置,不是时间步。

4.3 半满尾块跳过的原因

你可能以为块一被分配就该立刻注册到反向索引、越早注册越早可被复用,但 nano-vllm 的做法是等写满才注册。原因是半满块还要继续被追加 token——下一个 step 的 decode 会往这块的剩余 slot 写新 K/V,块的 token 序列在变,基于这段 token 算出的 hash 也在变。如果半满时就把 (h_partial → block_id) 注册进反向索引,后果是双向的:

• • 二义性:同一物理块号在 hash_to_block_id 里有可能挂两个 entry——半满时的 h_partial 和将来写满后的 h_full。后续请求查 h_partial 会命中,但命中的物理块此刻的 token 序列已经不一样了,在 L4 第 4.1 节介绍的"内容碰撞防护"那一行会判定失败、退回全新申请——多做一次无效查找。
• • 失效成本:半满块每追加一个 token 就要把上一条 entry 从 hash_to_block_id 里删掉、重新注册。频繁删插会让这张表的命中率随 decode 推进无规律抖动。

对照正例(现状)的设计:只在块写满、内容确定下来后做一次注册,这条 entry 在被覆写前始终有效——只在 _allocate_block 把这个 block_id popleft 出来准备覆写时,被 L4 第 3 节介绍的清除旧 hash 的安全守卫清掉。一次注册对应一段固定内容,不会随 decode 推进抖动,也不会让同一物理块同时挂多个 entry。

5. LRU 不需要专门数据结构

L4 第 6 节介绍过 deque + 倒序释放怎么形成 LRU——前缀块在 deallocate 时倒序排到 free_block_ids 队尾,下次 _allocate_block 从队头 popleft,前缀块最迟才会被覆写。L4 没有展开的另一个问题:prefix cache 在复用流程里有没有额外引入什么 LRU 数据结构?

5.1 反直觉点

你可能会以为,prefix cache 这种"哪些块更可能被复用、就更晚被驱逐"的策略,需要一个专门的 LRU 队列或链表来记录访问时间。实际上 nano-vllm 没有这种结构——完整的 LRU 语义靠 deque 的方向性 + L4 第 6 节倒序释放自然形成。整个 engine/block_manager.py 里找不到任何"上一次被命中的时间戳"或"最近访问次数"——Block 类只有 block_id、ref_count、hash、token_ids 四个字段,没有时间相关字段;BlockManager 只有 4 个数据结构,没有专门的 LRU 表。

prefix cache 的 LRU 行为完全由 L4 第 6 节那套机制自然形成,没有任何独立实现:

• • deallocate 时倒序遍历 seq.block_table,前缀块最后进 free_block_ids 队尾,最久不会被覆写
• • _allocate_block 从队头 popleft,优先取最久未用的块
• • 一旦某块被 _allocate_block 选中,L4 第 3 节的安全守卫会清掉它在 hash_to_block_id 中的旧 entry,这块的复用机会自然终止

三步合起来:最有复用价值的前缀块,在 free deque 队列里待得最久——这恰好就是 LRU 的语义。

5.2 为什么 deque 方向性已经够用

LRU 的本质是"按上次使用时间排序,驱逐最久未用的"。nano-vllm 的 deque 借两个事实自然实现了这种排序:

• • 入队方向恒定:_deallocate_block 永远 append 到队尾,所有释放过的块按归还时间排队。
• • 出队方向恒定:_allocate_block 永远从队头 popleft,每次取出的就是队列里待最久的。

这两个事实结合 L4 第 6 节的"倒序释放"让前缀块排到队尾,合起来等价于"按 (归还时间 - 前缀深度) 排序"——归还时间 是该块进入 free_block_ids 队尾的时刻,前缀深度 指它在 seq.block_table 中的下标。减号物理上对应:同一次 deallocate 内,下标越小(前缀越靠前)的块归还得越晚 append 进队尾,等效于让它在队列里排得更靠后,前缀越靠前的块越晚被覆写,与 LRU 的目标一致。

为什么"LRU 的目标"是让前缀靠前的块晚被覆写?因为前缀越靠前,被多条请求共享的概率越高,保留它们换来的复用收益越大。

上图列了 6 条典型的线上请求:同色块表示 token 序列相同(同一物理块可复用),异色块表示内容不同。块 0 是 SYS prompt,被 6 条中的 5 条共用(命中率 83%);块 1 是 few-shot 模板,4 条共用(67%);块 2、块 3 是各条请求各自的用户输入与模型输出,几乎独占(17%)。底部黄框给出物理结论:LRU 让块 0、块 1 在 free 队列里待最久——它们被覆写一次会让后续每条带相同前缀的请求都重做 prefill;块 2、块 3 即使被覆写,本来就没有其他请求会复用,损失为零。

代价是这种 LRU 没有"在用户层主动提升优先级"的能力——例如某条共享块当前 ref_count > 1,正在被 attention 读,但它在 deque 里的位置由它首次释放的时刻决定,被读取时不会更新这块在 deque 中的位置。但对 prefix cache 来说,这个能力不是必须的:ref_count > 1 的块根本不在 free_block_ids 队列里,谈不上被覆写;一旦最后一条持有它的 seq deallocate,这块才进队尾,此时它的 hash 仍然有效,接下来任何一条带相同前缀的请求都能直接命中(走 第 3.6 节介绍的 else 分支取回再用),无需经过队列遍历。

5.3 整套 prefix cache 的代码范围

L4 用"hash_to_block_id + 释放时不清 hash"完成了块级复用的入口和持久化;compute_hash 链式、can_allocate / allocate 复用分支、hash_blocks 注册时机这三个细节合起来构成 prefix cache 的复用流程;LRU 行为没有添加任何新结构。整套 prefix cache 总共增加的代码就是 compute_hash、can_allocate 的 hash 查找循环、allocate 的复用分支、hash_blocks 这四处,未超出 4 个数据结构、5 个公开 API 的范围。

6. 思考题

先合上教程自己答一遍,再看参考答案。

问题 1(链式 hash 的必要性):假设把 compute_hash 改成只算当前块的 token 序列(去掉 prev_hash 参数)。给出一个具体的、block_size = 4 的 prompt 例子,说明在这种实现下会出现什么样的"错误共享 KV"。说明你的例子里链式 hash 为什么不会出这个问题。

问题 2(状态变迁追踪):block_size = 4,初始 free_block_ids = deque([0,1,2,3,4])、used_block_ids = {}、hash_to_block_id = {}。请求 A 长 12 个 token,先进入并依次执行 can_allocate / allocate / hash_blocks;然后请求 A 完成、调用 deallocate(此时 ref_count 都降到 0);然后请求 B 长 8 个 token,前 8 个 token 与 A 相同。请按时间顺序列出 t1(A 进入后)、t2(A deallocate 后)、t3(B allocate 后)三个时刻 free_block_ids 的内容和 hash_to_block_id 的 entry 数量。

问题 3(LRU 机制预测):如果把 L4 §6 介绍的 deallocate 中 reversed(seq.block_table) 去掉,改成按下标顺序释放,这条 seq 的前缀靠前块在 free_block_ids 里会排在哪一端?下一次 _allocate_block 会优先覆写哪些块?LRU 行为是否还成立?

问题 1:block_size = 4,prompt A = [I, like, cats, ., I, dislike, dogs, .],prompt B = [I, dislike, dogs, .]。非链式 hash 下,A 的第 1 块 [I, dislike, dogs, .] 与 B 的第 0 块 [I, dislike, dogs, .] 算出相同 hash,B 查表会命中 A 的第 1 块。但 A 的第 1 块 KV 是模型在看过 [I, like, cats, .] 这段前缀后生成的,与 B 从空前缀开始生成的 KV 完全不同。B 复用这份 KV 后,decode 时 attention 读到的是 A 带 [I, like, cats, .] 注意力痕迹的 K/V,模型据此推断"前面有人在说喜欢猫",基于这个错误上下文预测下一个 token——B 本应基于"我不喜欢狗"续写的内容,会被"我喜欢猫"语境干扰,输出可能转回猫的话题或给出与狗的负面态度相反的延续,与 B 的实际意图完全不符。链式 hash 下,A 的第 1 块 hash 是 xxhash(h(A0) || A1_tokens),B 的第 0 块 hash 是 xxhash(B0_tokens)(无前驱),两式形式不同,不会算出相同 hash。

问题 2:

• • t1(A 进入后):can_allocate 返回 0,allocate 从队头 popleft 出 0、1、2 给 A,A.block_table = [0, 1, 2]。hash_blocks 把 3 块都注册到索引(12 = 3×4 都写满)。free_block_ids = [3, 4],hash_to_block_id 有 3 个 entry。
• • t2(A deallocate 后):倒序遍历 [2, 1, 0],每块 ref_count 从 1 减到 0,逐一 append 到队尾。free_block_ids = [3, 4, 2, 1, 0]。hash_to_block_id 仍有 3 个 entry——deallocate 不清 hash。
• • t3(B allocate 后):can_allocate 链式算 hash 命中前 2 块(块 0、块 1),num_cached_blocks = 2。前 2 块走复用分支:块 0 与块 1 都在 free_block_ids 中(非 used_block_ids),走的是 第 3.6 节介绍的另一条路径——ref_count = 1、从 free_block_ids 中 remove(0) 和 remove(1)、add 到 used_block_ids。剩余 1 块从队头 popleft 出 3(因为前两次 remove 不动队头)。free_block_ids = [4, 2],B.block_table = [0, 1, 3]。hash_to_block_id 仍有 3 个 entry,本次复用不动这张表。

问题 3:顺序释放下,前缀靠前的块先 append 到 free_block_ids,落在队头(后释放的块反而在队尾)。下一次 _allocate_block 从队头 popleft,优先覆写前缀靠前的块——本应被保留的高命中率块(SYS prompt、few-shot 模板)最先被覆写,LRU 行为反转。prefix cache 命中率显著下降:后到的同前缀请求查表 miss,重做完整 prefill。reversed 这一行就是把释放顺序翻过来,让前缀块排到队尾。

7. 总结

• • compute_hash(token_ids, prev_hash) 的链式构造让块的指纹刻画从第 0 块到当前块的整段前缀。不变式:前缀完全相同 ↔ hash 完全相同;任一前缀位置变化,本块及之后的 hash 全部偏移。
• • 复用流程只动 L4 已有的 4 个数据结构、5 个 API:can_allocate 数命中,allocate 走 ref_count += 1 或从 free_block_ids 取回再用,hash_blocks 在 prefill 收尾注册新写满的块。没有新增数据结构,也没有新模块。
• • deallocate 不清 Block.hash、不删 hash_to_block_id 的 entry——这是前缀块释放后仍能被新请求查表命中、取回再用的物理基础。
• • LRU 不需要专门结构:reversed(seq.block_table) 让前缀靠前的块排到 deque 队尾,_allocate_block 从队头覆写,前缀越靠前的块越晚被覆写。前缀越靠前共享越广,LRU 优先保留它们正好对应"覆写损失最大"的块。

下面这段视频把两条请求 A、B 共享前 8 个 token 的完整流程跑了一遍——从 A 到达 can_allocate、到 allocate popleft 三块、到 hash_blocks 链式注册,再到 B 命中复用、ref_count++ 变共享块,完整可追踪: