Nano-vLLM 源码解读 - 9. 抢占机制

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

L07 第 5 节讲过schedule()的 decode 分支大致结构,其中提到一句:“decode 在块边界处可能装不下,装不下就走preempt”,当时把细节明确推迟到本节。

那段代码不到 10 行,却同时回答三个问题:decode 在什么时刻会装不下?装不下时谁先被释放?被释放的 seq 接下来去哪里?

第一个问题落在block_manager.can_append——它的判定写成一行表达式,左边是空闲块数、右边是一个布尔比较的结果,合起来表达"何时需要新块,以及池子里是否真有"。第二个和第三个问题落在schedule()decode 分支内的while-else控制流,以及preempt函数的四个动作。

读完本节,读者可以:

• 解释can_append那一行表达式右边为什么是一个布尔比较(len(seq) % self.block_size == 1),并判断它在len的不同取值下分别返回什么
• 在给定 running 队列与 free_block_ids 数量时,列出"不抢 / 抢队尾 / 抢自己"三种情形分别在什么条件下被触发
• 解释 Pythonwhile-else在 decode 分支里如何让"被抢自己"的 seq 不进入本轮scheduled_seqs
• 说出preempt把被抢 seq 放到 waiting 队列的哪一端、为什么这样选
• 解释被抢 seq 下一轮 prefill 时不必从零重算的条件——L05 的 prefix cache 在什么场景下能恢复一部分块

1. decode 在块边界处装不下时怎么办

L03 讲过 nano-vllm 的 KV cache 不连续:每条 seq 的block_table列出它持有的若干物理块编号,每块固定容纳block_size个 token 的 KV(默认 256)。

decode 阶段每个 step 给 seq 追加 1 个新 token。这个 token 的 KV 要写到哪一块?分两种情况:

• 当前块还没写满:新 token 继续写当前块的下一个空位,block_table不变,不需要新块。
• 当前块刚好写满:新 token 装不进当前块,必须写入一个新块,需要从free_block_ids取一块追加到block_table末尾。

第二种情况就是"块边界"。一条 seq 的 decode 沿块边界走时,每block_size个 step 才需要 1 个新块;其余block_size − 1个 step 都在已有块内继续写,不需要新块。

但只要 KV cache 池(由 L06 的显存预算确定)被 running 全员占满,free_block_ids为空,某条 seq 走到块边界时就装不下。这时系统不能凭空多造一块,只能从别的 seq 持有的块中取——这就是抢占。

扩容不行——KV cache 池大小由 L06 的显存预算定死,运行期不能再多分配显存;凭空取块也不行——物理块是有限的。剩下唯一的做法是让别的 seq 释放它持有的块。代价是被释放的 seq 已经计算过的 KV 必须被丢弃,下次再被调度时要重新算一遍。

问题在于:系统怎么知道某条 seq 此刻正好处在块边界、需要新块?答案就在 can_append 这一行表达式里。

2.can_append:只在块边界时查池子

判定块边界与池子状态的逻辑写在block_manager.py里。最自然的写法是分两步——先判要不要新块,再判有没有空闲块:

# 朴素写法(并非 nano-vllm 实际代码)defcan_append(self,seq:Sequence)->bool:iflen(seq)%self.block_size==1:returnlen(self.free_block_ids)>=1else:returnTrue

这种写法每个 decode step 都要执行一段判断。nano-vllm 把两件事合并为一行,利用了 Python 布尔可强转为整型的特性——下面拆开看为什么这样写避免了大多数 step 的检查:

# block_manager.pydefcan_append(self,seq:Sequence)->bool:returnlen(self.free_block_ids)>=(len(seq)%self.block_size==1)

一行表达式把两件事合并为一个比较。先单独解析两边:

右边len(seq) % self.block_size == 1是一个布尔表达式。len(seq)是 seq 当前的 token 总数(prompt 长度加上已 decode 出的部分),block_size是每块容量。%取余,==判等。整个表达式只在余数恰好为 1 时为True,其他取值都为False。

这个 1 来自can_append的调用时机。L07 第 1 节讲过:每个 step 末尾postprocess调用seq.append_token(new_token),把新 token 追加到token_ids,len(seq)因此加 1。

按这个时序,一次 decode step 的时间线是:① 上一轮 forward 写完当前块的最末位置 → ②postprocess让len(seq)加 1(对应 seq 内部num_tokens字段;token 已存在于 seq,但它的 KV 还没有任何物理块容纳)→ ③ 本轮 schedule 看到len % block_size == 1,触发分配新块。

• 假设block_size = 16,seq 的block_table = [b0],b0 已写满 16 个 token。len(seq) = 16意味着 16 个 token 全部落在 b0(刚好写满),还没有第 17 个 token。下一轮 forward 会算出第 17 个 token,但 schedule 在此刻读到的len还是 16,余数为 0,不要新块。
• 上一个 decode step 跑完之后,postprocess把第 17 个 token 追加到token_ids,len由 16 变 17,本轮 schedule 看到len = 17。这个 token 的 KV 还没被任何块容纳——下一轮 forward 才会写。所以len = 17是"token 已经存在、但 KV 还没落块"的瞬间,必须为它准备一块。

所以len % block_size == 1表达的物理含义是:“当前 seq 的最末 1 个 token 已经处在新块的第 1 个位置,但还没有任何物理块容纳它”。这个时刻必须有空闲块。其他取值都对应当前块还能继续写,不需要新块。

左边len(self.free_block_ids)是空闲块数,整数。两边通过>=比较。Python 在做整型>=比较时会把布尔值强转为整型(True→ 1,False→ 0)。两种取值组合如下:

第二行是唯一可能返回False的情形。其他block_size − 1种余数全部返回True且不查池子——因为>= 0永远成立。

这里有一个反直觉的地方:绝大多数 decode step,can_append不做"是否有空闲块"的判定。按默认block_size = 256,255 / 256 ≈ 99.6%的 decode step 直接返回True、无需触发抢占检查;只有1 / 256 ≈ 0.4%的 step 真正执行>= 1的判定。一行>= (布尔)表达式把"何时需要检查"与"是否真有"合并为单次整型比较,避免了在大多数 step 显式判if (need_block): ...。

补一个收尾:can_append只判断"够不够",真正分配新块的是may_append,条件正好与can_append右边对齐:

# block_manager.pydefmay_append(self,seq:Sequence):iflen(seq)%self.block_size==1:seq.block_table.append(self._allocate_block())

schedule()在确认can_append通过、决定调度该 seq 后立刻调may_append(见 scheduler.py:69)。两者的条件一致:can_append判断"需不需要 + 有没有",may_append在两者都成立后取一块写入block_table。

何时触发已经清楚,接下来看触发后怎么办。

3. 三种调度结果与while-else控制流

这段代码要解决的事:遍历 running 队列,把每条 seq 加入本轮调度;遇到装不下的 seq 时,先抢队尾,实在不行抢自己。decode 分支的处置逻辑写在一段双层 while 里,外层遍历 running,内层处理can_append失败的情形。先看完整代码,再拆解控制流。

# scheduler.py:schedule() decode 分支whileself.runningandlen(scheduled_seqs)<self.max_num_seqs:seq=self.running.popleft()# 取出队首,逐条尝试调度whilenotself.block_manager.can_append(seq):# 装不下时进入抢占循环ifself.running:self.preempt(self.running.pop())# 抢队尾(最近加入的 seq)else:self.preempt(seq)# 队尾已抢光 → 抢自己break# break 退出,下面 else 不执行else:# ← 本节焦点:while 自然退出才走 elseseq.num_scheduled_tokens=1seq.is_prefill=Falseself.block_manager.may_append(seq)# 边界态(% == 1)分配新块scheduled_seqs.append(seq)# 调度成功,加入本轮assertscheduled_seqs# 不变式:每轮至少调度 1 条self.running.extendleft(reversed(scheduled_seqs))# 保持原顺序放回 running 队首returnscheduled_seqs,False

外层while从self.running队首逐条取 seq,加入本轮调度。内层while not can_append(seq)处理can_append失败的情形。

为什么抢的是队尾

self.running.pop()取的是 deque 的右端——即 running 队列的队尾,也就是最近 append 进来的 seq。直觉上 FIFO 是"先来先服务、先来先走",但抢占恰好反过来:先释放最近加入的那一条。

为什么?running 里每条 seq 都已经在过去若干 step 中算过 KV、累积了上下文。被抢者的全部 KV 会被释放(下一节preempt详解),加入 waiting 后需要重新 prefill 才能续上。被抢者最近加入,累积的 KV 越少,重算成本越低;加入早的,重算成本越高。所以"抢队尾"是用"已投入算力最少"的标准选取被抢对象。

while-else如何让"自抢"的 seq 自动出局

看懂内层 while 的三种结局,需要先讲清楚 Python 的while-else语义,因为内层while ... else的else才是"调度成功"那一支。

Pythonwhile-else语义:while 条件: ... else: ...是 Python 控制流的一个少见结构。else块只在while因条件失败而自然退出时执行,因break中断退出时不执行。

用类比理解:循环顺利跑完才走 else 分支;break 中途打断,跳过 else。在 decode 分支里,自然退出 =can_append转 True = 装得下。

把这条语义套回 decode 分支:

• while not can_append(seq)表示"只要装不下就继续触发抢占";退出条件是"can_append(seq)变 True",即装得下了。
• 自然退出 → 装得下 →else分支执行 → 把 seq 加入scheduled_seqs。
• break退出 → 抢光也装不下、只能放弃自己 →else不执行 → seq 不加入scheduled_seqs。

nano-vllm 在这里用while-else处理"自抢"情形:第三种结局里,seq 被preempt(seq)后立刻break出内层。break跳过else分支,意味着scheduled_seqs.append(seq)这一句不执行——seq 不进入本轮被调度的列表。

这与"自抢"语义对齐:seq 已经被preempt置为 WAITING、加入 waiting 队首,本轮 forward 它就不该参加。else分支天然把它排除,无需在break之后额外加if not preempted_self: ...判断。Pythonwhile-else的设计在这里恰好作为"自然退出执行主路径、异常退出执行旁路"的开关使用。

三种结局汇总。内层while加上if / else内分支,组合出三种结局。下表把进入内层while时的状态对应到结局:

三种结局对应"不抢 / 抢队尾 / 抢自己"。

上面把preempt(seq)当作单步操作处理;它内部其实做了四件事,每一件都对应一个状态变化。

4.preempt的四个动作与 prefix cache 的部分恢复机制

被抢者在 preempt 内部经历了什么、被抢之后是否真的全部丢失,需要拆开 preempt 函数看。preempt函数本身只有四行:

# scheduler.pydefpreempt(self,seq:Sequence):seq.status=SequenceStatus.WAITING seq.is_prefill=Trueself.block_manager.deallocate(seq)self.waiting.appendleft(seq)

四个动作各对应一个语义层面的状态变化。下面逐条看:

动作 1:status = WAITING

L07 第 1 节讲过 SequenceStatus 的三态机:WAITING → RUNNING → FINISHED。preempt 对应这个三态机上的反向转换——从 RUNNING 退回 WAITING。这一行的物理含义是:seq 从"正在被推进的活跃序列"变回"等待被调度的候选序列"。

动作 2:is_prefill = True

is_prefill是 L07 第 1 节讲过的"该 seq 下次被调度时走 prefill 路径还是 decode 路径"的指示位。preempt 把它重置为True,意味着 seq 下次被调度时必须走 prefill 路径。

为什么必须走 prefill 而不能直接续 decode?第 3 个动作给出答案。

动作 3:deallocate(seq)

deallocate要做两件事:把 seq 持有的每块的引用计数减 1(降到 0 才真正归还);清空 seq 自己对这些块的索引(block_table与num_cached_tokens)。L04 讲过细节,这里只回顾要点。

# block_manager.pydefdeallocate(self,seq:Sequence):forblock_idinreversed(seq.block_table):block=self.blocks[block_id]block.ref_count-=1ifblock.ref_count==0:self._deallocate_block(block_id)seq.num_cached_tokens=0seq.block_table.clear()

L04 已讲过deallocate的内部机制:把block_table中每一块的ref_count减 1,降到 0 的块由_deallocate_block真正放回free_block_ids。然后num_cached_tokens清零、block_table清空。

物理含义是:被抢者持有的全部物理块归还(或释放引用),被抢者已经计算的 KV 在物理上仍可能留在块内,但被抢者已失去对它们的引用——block_table.clear()之后,该 seq 与那些块之间的关联断了。

这同时回答了动作 2 的问题:被抢者的block_table已清空,下次被调度时没有任何块可"续",只能从头按 prefill 路径重新分配块、重新计算 KV。

动作 4:waiting.appendleft(seq)

一个反直觉的地方:被抢的 seq 不像新请求那样加入 waiting 队尾,而是置于队首。

普通 add 请求是waiting.append(放队尾);preempt 用appendleft(放队首)。两者的物理含义对照如下:

为什么 preempt 要把被抢者置于队首?原因是:被抢者已经投入过算力(算过 KV、推进过若干 step),把它再排到普通新请求之后会让"被抢→再次被调度"的延迟变得极长——这与"抢队尾"选取最近加入者的原则一致:preempt 让已投入算力最多的 seq 损失最小。appendleft让被抢者下一轮就优先重启,把"被抢→再次开始 prefill"的间隔降到最短。

这个选择还配合了 prefix cache 的部分恢复机制——把 hash 失效窗口降到最短。

prefix cache 的部分恢复机制

被抢者下一轮是从零开始还是能省一部分?答案取决于一个被 L04 与 L05 提到、但在抢占场景里至关重要的细节:deallocate不会立即清除hash_to_block_id字典中被抢者的 hash 条目。

先看理想情形:被抢者持有的块都已写满,且被抢→再次被调度之间没有别的 seq 取走这些块。这时被抢者下一轮 prefill 时,沿 token 序列重新算 hash,在字典里全部命中,所有满块的 KV 都不必重算。

但现实里有两个边界让这个"理想情形"不一定成立:

边界 1:末块未满。L05 讲过:hash_to_block_id 是一个字典,键是某块 16 个 token 序列的 hash,值是该 token 序列当前所在的 block_id;它是 prefix cache 找历史块的反向索引。L05 同时讲过:只有已写满的块才会被hash_blocks写入hash_to_block_id(hash_blocks只处理完整块)。被抢者最末那一块若未满,从未被 hash,不在恢复范围内——这部分 token 的 KV 必须重算。

边界 2:被抢→再次被调度之间发生了新分配。先看 L04 讲过的_allocate_block。_allocate_block在分配空闲块时,同时检查这块原来的所属 seq 是否仍持有它的引用(hash_to_block_id是否仍指向自己),只在"仍指向自己"时才删条目。下面是相关片段:

# block_manager.pydef_allocate_block(self)->int:block_id=self.free_block_ids.popleft()# 从 free pool 取一块block=self.blocks[block_id]assertblock.ref_count==0# 不变式:free 中的块 ref_count 必为 0ifblock.hash!=-1andself.hash_to_block_id.get(block.hash)==block_id:# 旧主的 hash 条目仍指向自己delself.hash_to_block_id[block.hash]# ← 本节焦点:覆写前清条目,旧主的恢复链断开block.reset()# ref_count=1, hash=-1, token_ids=[]...

hash_to_block_id中的条目只在该块真正被其他 seq 取走时才删除(且仅当 hash 字段仍指向自己——避免误删覆写情况)。preempt 调用的deallocate只动ref_count和block_table,不动hash_to_block_id。

这意味着:被抢者的 hash 条目在deallocate之后仍然存在;只要那些块没被其他 seq 取走、_allocate_block没触发过删除逻辑,它们就一直在字典里指向原来的 block_id。

下一轮被抢者作为 prefill 重新被调度时,L05 讲过can_allocate沿 seq 的完整块依次算 hash、查字典;命中则累加num_cached_blocks(不用重算的部分),并在合适时机扣减num_new_blocks:

# block_manager.py:can_allocate(seq)defcan_allocate(self,seq:Sequence)->int:h=-1num_cached_blocks=0num_new_blocks=seq.num_blocks# 上限:假设所有块都要新分配foriinrange(seq.num_blocks-1):# 只走前缀完整块,最末未满块跳过token_ids=seq.block(i)h=self.compute_hash(token_ids,h)# 沿前缀链算 hashblock_id=self.hash_to_block_id.get(h,-1)ifblock_id==-1orself.blocks[block_id].token_ids!=token_ids:break# 字典里没条目或内容不符 → 后续也不必再查num_cached_blocks+=1# 命中:这块 KV 不必重算ifblock_idinself.used_block_ids:num_new_blocks-=1# 命中且仍被占 → 共享,不需要新块iflen(self.free_block_ids)<num_new_blocks:# free pool 不够 → 整体分配失败return-1returnnum_cached_blocks# 返回命中数,后续 allocate 据此安排

num_new_blocks初值是seq.num_blocks——先按"所有块都要新分配"算上限。循环只遍历seq.num_blocks - 1个前缀完整块(最末未满块不入 hash 表,跳过)。对每个前缀块算 hash 查字典:命中且token_ids匹配 →num_cached_blocks += 1,表示这块 KV 不用重算;再判断该 block_id 是否仍在used_block_ids中,分两种情形扣减num_new_blocks:

• 命中且仍被占:其他 seq 也持有这块物理 block,本 seq 与之共享,num_new_blocks -= 1——不需要从free_block_ids取新块。
• 命中但已归还free_block_ids:这块物理 block 还在,但used_block_ids不含它,所以不扣减num_new_blocks——下面_allocate_block仍要从free_block_ids取一块,只不过取的就是这块命中的 block,语义上相当于"先归还、再领回"。

最后比较len(free_block_ids) >= num_new_blocks,不足则返回-1(不能分配),足够则返回num_cached_blocks。

被抢者部分恢复的物理基础就在于此:block 物理上还在,只是被抢者一度失去对它的引用;hash 表使被抢者重新定位到它之前持有的块。若被抢者之前的 hash 条目还在,且对应 block 的 token_ids 仍然匹配,就计入num_cached_blocks,命中的部分不需要重算 KV。

若被抢者的某些块在它再次被调度前已被其他 seq 通过_allocate_block取走,那条 hash 条目就被del了——这部分也丢失。在抢占场景中,A 触发抢占 → C 被抢出 → A 的may_append接着取一块,正好可能取走 C 刚释放的块。

这就是"prefix cache 部分恢复"的真实形态:是否能恢复、能恢复多少都不固定——取决于被抢者末块写满程度、以及被抢→再次被调度之间发生了多少新分配。最坏情况(全部块被复用)等价于从零重算;最好情况(无新分配介入)能省下整段 prompt 的 prefill 算力。

用一组具体数值跑一遍第 3、4 节描述的机制,可以直观确认三种处置情形如何依次触发、部分恢复机制如何起作用。

5. running=[A, B, C] 在块边界的一次调度

前四节给出规则,本节用一组具体数值端到端验证。

设定:block_size = 16(教学用值;默认 256,模式相同但表格冗长),max_num_seqs = 16,KV cache 池总容量 6 块。running 队列初始[A, B, C],free_block_ids 为空。三条 seq 的状态:

hash_to_block_id状态(L05 已讲:只有满块进字典):

b1、b3、b5 未满,不在字典中。free_block_ids = [],used_block_ids = {b0, b1, b2, b3, b4, b5}。

进入schedule()。waiting 为空,跳过 prefill 分支,直接进 decode 分支。

迭代 1:处理 A —— 抢队尾

seq = self.running.popleft()取出 A。self.running = [B, C]。

检查can_append(A):右边17 % 16 == 1为 True,布尔强转为 1;左边len(free) = 0;0 >= 1为 False。can_append返回 False,进入内层 while。

内层迭代:if self.running:为真(running 还有 B、C)→preempt(self.running.pop())=preempt(C)。

preempt(C)的四个动作:

1. C.status = WAITING
2. C.is_prefill = True
3. deallocate(C):遍历reversed([b4, b5])=[b5, b4]。
   • b5:ref_count -= 1= 0 →_deallocate_block(b5)→used_block_ids去掉 b5、free_block_ids.append(b5)。
   • b4:ref_count -= 1= 0 →_deallocate_block(b4)→free_block_ids.append(b4)。
   • 末尾C.num_cached_tokens = 0、C.block_table.clear()。
4. waiting.appendleft(C)→ waiting =[C]。

注意此时hash_to_block_id中 b4 的条目未删(deallocate不动 hash 字典)。deallocate的循环用reversed是为了从block_table末尾向前归还(实现细节,本节不关心);每归还一块就free_block_ids.append(...)加入队尾。所以 b5 先归还、先加入队尾;b4 后归还、加入更靠后的队尾。结果 deque 头到尾是[b5, b4]。

回到内层 while 重检can_append(A):17 % 16 == 1为 True(1);len(free) = 2;2 >= 1为 True。can_append返回 True,内层 while 条件失败,自然退出 → else 分支执行。

else 分支:

• A.num_scheduled_tokens = 1
• A.is_prefill = False
• may_append(A):17 % 16 == 1为真 →seq.block_table.append(self._allocate_block())。
  • _allocate_block:free_block_ids.popleft()取 b5(队首)。b5 的hash == -1(从未满过、从未写入 hash 字典)→ 跳过del。b5.reset()。used_block_ids.add(b5)。返回 b5。
  • A.block_table.append(b5)→[b0, b1, b5]。
• scheduled_seqs.append(A)→[A]。

末态:free_block_ids = [b4],used_block_ids = {b0, b1, b2, b3, b5}。hash_to_block_id仍含 b4 的旧条目。

迭代 2:处理 B —— 不抢

外层while继续。seq = self.running.popleft()取出 B。self.running = []。

检查can_append(B):右边18 % 16 == 2 == 1为 False(0);左边len(free) = 1;1 >= 0为 True。can_append返回 True,内层 while 一次都不进入,直接走 else 分支。

else 分支:

• B.num_scheduled_tokens = 1
• B.is_prefill = False
• may_append(B):18 % 16 == 2,不等于 1 →不分配新块。B.block_table仍为[b2, b3]。
• scheduled_seqs.append(B)→[A, B]。

末态不变:free_block_ids = [b4]。

迭代 3:running 空 —— 退出

外层while self.running条件[] and ...为假,退出外层 while。

assert scheduled_seqs检查[A, B]非空,通过。

self.running.extendleft(reversed([A, B]))=extendleft([B, A]),等价于先appendleft(B)再appendleft(A),结果self.running = [A, B],顺序保留。

return ([A, B], False),decode 分支返回。

末态汇总与下轮命中分析

C 当时持有的 b4(已满块)、b5(未满块):b5 被 A 的may_append取走、reset,b5 从未在 hash 字典里;b4 仍在free_block_ids中,hash 条目保留。

下一轮 schedule 走 prefill 分支处理 C 时,can_allocate(C)沿 C 的num_blocks - 1 = 1个完整块走 hash 比对:计算C.block(0)的 hash,在hash_to_block_id中查到 b4_id,且blocks[b4_id].token_ids与 C.block(0) 匹配 →num_cached_blocks += 1,b4 命中。

num_new_blocks初值是seq.num_blocks = 2(C 有 17 个 token,ceil(17/16) = 2块);b4 命中但不在used_block_ids(已归还free_block_ids),所以num_new_blocks不扣减,仍为 2。检查len(free_block_ids) = 1 < 2→can_allocate返回-1,C 本轮无法被调度——free_block_ids只剩 1 块,装不下 C 需要的 2 块。

但hash 条目并未失效:只要 b4 在 C 被再次调度前没被其他 seq 通过_allocate_block取走,hash_to_block_id中 b4 的条目就一直存在。等到free_block_ids恢复(例如后续某条 running seq 自然完成、释放它持有的块,或 A、B 又被抢出),can_allocate(C)再次被调用时仍会命中 b4,num_cached_blocks仍为 1——C 第 0 块直接复用 b4,无需重算,只有第 1 块(原 b5 的位置)需要重新分配并重算 KV。

这就是"prefix cache 部分恢复"在本例中的具体体现:hash 条目的存活与free_block_ids是否够用是两件事——前者决定"命中能省多少",后者决定"本轮能不能调度"。最理想情况(b4 hash 条目存活、free_block_ids足够)能省下 1 块的 prefill 算力,仅丢失最后那个未满块的 1 个 token 的 KV。

若 A 的may_append不是取走 b5 而是取走 b4(假设free_block_ids顺序相反),则 b4 的 hash 条目会被_allocate_block中的del删除,C 的部分恢复机制完全失效——这正是"恢复多少不固定"的具体含义。

下面这段视频把本节走查跑了一遍——running =[A, B, C],block_size = 16,free_block_ids为空。三次迭代依次触发"抢队尾"、“不抢”、“running 空退出”;末态汇总后再演示下一轮can_allocate(C)的命中判定与失效边界。状态面板(running / waiting / scheduled_seqs / free pool / hash_to_block_id)与判定面板随每一步同步变化:

6. 思考题

请先独立作答,再阅读下方提示。

1. 如果某个工程师把block_size改成 1(每块只能存 1 个 token),can_append表达式的右边会一直为 0 还是 1?抢占频率会怎么变化?为什么 nano-vllm 选择默认 256 而不是 1?

2. 若 running 队列只剩 1 条 seq A(len = 17,block_table = [b0, b1],边界态),KV cache 池只有 2 块、free_block_ids为空,schedule()调用如何走?最终会触发assert scheduled_seqs吗?走完执行轨迹后,主要回答:为什么 nano-vllm 在显存预算里留余量?

3. 把preempt的self.waiting.appendleft(seq)改成self.waiting.append(seq)(放队尾),其他不动。在长时间运行的场景下,被抢者会出现什么观测得到的现象?给出一个具体场景(可借用第 5 节的设定)说明改动前后调度结果的差异。

思考题参考答案

1. block_size = 1时,每个 token 都是块边界。len(seq) % 1 == 0永远成立,所以len(seq) % 1 == 1永远为False(转为 0)——这与直觉相反:不是"一直为 1",而是"一直为 0"。但这不意味着不抢占——block_size = 1意味着每个 decode token 都要单独占一块,所以实际每个 step 都需要新块。问题出在表达式本身:当block_size = 1时,len % block_size只能取 0,余数永远不会等于 1,can_append永远不查池子、永远返回 True;但may_append也用同一个条件len % block_size == 1,所以永远不分配新块——seq 持有的块不增,新 token 的 KV 没地方写,程序行为出错。换句话说,block_size = 1让整个% == 1的判定逻辑失效。nano-vllm 选 256 而非 1 的原因之二在性能层面:大块降低了block_table长度、降低了can_append触发的频率(每 256 个 step 才触发一次抢占检查)、也降低了 hash 表条目数;block_size = 1会让上述所有结构退化成 per-token 维护,完全失去块抽象的意义。

2. 会触发 assert,程序崩溃。执行轨迹:schedule()进 decode 分支(waiting 空、running 非空),外层 while 进入。seq = self.running.popleft()= A,self.running = []。内层while not can_append(A):17 % 16 == 1,布尔强转 1,len(free) = 0 >= 1为 False → 进入内层。if self.running:为假(空)→else分支 →preempt(A):A 状态置为 WAITING、deallocate A 的 2 块(b0、b1 都进 free,但此时 A 已经从 running 移出,running 没有别的 seq 可继续)→waiting.appendleft(A)→break。内层 break,else不执行,scheduled_seqs 不变(仍为空)。外层while self.running=[]为假,退出外层。assert scheduled_seqs检查空列表 → 触发AssertionError。该 assert 守护的不变式是"每一轮 schedule 必产出至少一条可推进的 seq";这是 forward 循环能继续的最低条件,违反这条不变式说明显存预算公式被违反,继续运行只会产生未定义行为。正常运行时num_kvcache_blocks由 L06 的显存预算公式留出余量,保证 running 中至少有 1 条 seq 可以装下;一旦余量被耗尽,系统直接崩溃而不返回空调度,避免下游 model_runner 收到无效输入。

3. 被抢者再次被调度延迟极长,prefix cache 的部分恢复机制容易失效。借用第 5 节设定:C 被抢后用append排到 waiting 队尾。假设上层连续接入 10 条新请求(都append到 waiting 队尾),则 waiting 变成[新1, 新2, ..., 新10, C]。下一轮 prefill 时,schedule()从waiting[0]开始处理,优先调度 10 条新请求中的一部分(取决于max_num_batched_tokens与max_num_seqs)。每调度一条新请求都会调_allocate_block取空闲块——这正是会触发del hash_to_block_id[block.hash]的路径。等轮到 C 时,它当时持有的 b4 的 hash 条目大概率已被某条新请求触发_allocate_block删除,部分恢复机制失效,C 必须从头 prefill。改用原来的appendleft,C 下一轮就是waiting[0],b4 的 hash 条目几乎不可能在这么短的时间内被覆写。appendleft与 prefix cache 部分恢复机制相互配合:把被抢者置于队首,就是为了把 hash 条目失效窗口降到最短。