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_size1: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_size1)一行表达式把两件事合并为一个比较。先单独解析两边:右边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)。两种取值组合如下:len(seq) % block_size右边布尔表达式比较条件can_append返回值物理含义0False(转为 0)len(free) 0永真True上一轮 token 写入当前块的最末 1 个位置,本轮还不需要新块1True(转为 1)len(free) 1,需至少 1 块取决于池子本轮即将写新块,必须有空闲块2 到block_size − 1False(转为 0)len(free) 0永真True当前块还没写满,继续写第二行是唯一可能返回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_size1: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:seqself.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_tokens1seq.is_prefillFalseself.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中断退出时不执行。while退出方式else是否执行条件由 True 变 False,自然退出是循环体内执行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时的状态对应到结局:进入内层时的状态内层while行为退出方式else是否执行当前 seq 命运can_append(seq)第一次就True循环体一次都不执行条件由 True 变 False(指not can_append由 True 变 False)是调度成功,加入scheduled_seqscan_append(seq)失败,self.running非空preempt(self.running.pop())抢队尾,然后重检can_append抢一条或多条队尾后,池子有空块、can_append转 True,条件失败退出是调度成功can_append(seq)失败,self.running空preempt(seq)抢自己,然后breakbreak否不加入scheduled_seqs,seq 状态置为 WAITING,加入 waiting 队首三种结局对应不抢 / 抢队尾 / 抢自己。上面把preempt(seq)当作单步操作处理;它内部其实做了四件事,每一件都对应一个状态变化。4.preempt的四个动作与 prefix cache 的部分恢复机制被抢者在 preempt 内部经历了什么、被抢之后是否真的全部丢失,需要拆开 preempt 函数看。preempt函数本身只有四行:# scheduler.pydefpreempt(self,seq:Sequence):seq.statusSequenceStatus.WAITING seq.is_prefillTrueself.block_manager.deallocate(seq)self.waiting.appendleft(seq)四个动作各对应一个语义层面的状态变化。下面逐条看:动作 1:status WAITINGL07 第 1 节讲过 SequenceStatus 的三态机:WAITING → RUNNING → FINISHED。preempt 对应这个三态机上的反向转换——从 RUNNING 退回 WAITING。这一行的物理含义是:seq 从正在被推进的活跃序列变回等待被调度的候选序列。动作 2:is_prefill Trueis_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):blockself.blocks[block_id]block.ref_count-1ifblock.ref_count0:self._deallocate_block(block_id)seq.num_cached_tokens0seq.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(放队首)。两者的物理含义对照如下:操作用途seq 在 waiting 中的位置waiting.append(seq)上层接入的新请求队尾(等队列里所有比它先来的都进了 running 再轮到自己)waiting.appendleft(seq)preempt 把被抢者加入 waiting队首(下次schedule()进 prefill 分支第一个就是它)为什么 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_idself.free_block_ids.popleft()# 从 free pool 取一块blockself.blocks[block_id]assertblock.ref_count0# 不变式: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_count1, 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_blocks0num_new_blocksseq.num_blocks# 上限:假设所有块都要新分配foriinrange(seq.num_blocks-1):# 只走前缀完整块,最末未满块跳过token_idsseq.block(i)hself.compute_hash(token_ids,h)# 沿前缀链算 hashblock_idself.hash_to_block_id.get(h,-1)ifblock_id-1orself.blocks[block_id].token_ids!token_ids:break# 字典里没条目或内容不符 → 后续也不必再查num_cached_blocks1# 命中:这块 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 的状态:seqlen(seq)block_tablelen % block_size是否边界态说明A17[b0, b1]1是b0 已满 16 token,b1 已写 1 token,本轮需要新块B18[b2, b3]2否b3 已写 2 token,本轮在 b3 继续写C17[b4, b5]1是b4 已满,b5 已写 1 token,本轮需要新块hash_to_block_id状态(L05 已讲:只有满块进字典):满块字典条目b0hash(A 第 0 块的 16 token)→ b0b2hash(B 第 0 块的 16 token)→ b2b4hash(C 第 0 块的 16 token)→ b4b1、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)的四个动作:C.status WAITINGC.is_prefill Truedeallocate(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()。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 1A.is_prefill Falsemay_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 1B.is_prefill Falsemay_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 分支返回。末态汇总与下轮命中分析字段末态running[A, B]waiting[C]scheduled_seqs[A, B](本轮 forward 处理)A.block_table[b0, b1, b5]B.block_table[b2, b3]C.block_table[]free_block_ids[b4]hash_to_block_id{hash(b0): b0, hash(b2): b2, hash(b4): b4}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)与判定面板随每一步同步变化:preempt-flow6. 思考题请先独立作答,再阅读下方提示。如果某个工程师把block_size改成 1(每块只能存 1 个 token),can_append表达式的右边会一直为 0 还是 1?抢占频率会怎么变化?为什么 nano-vllm 选择默认 256 而不是 1?若 running 队列只剩 1 条 seq A(len 17,block_table [b0, b1],边界态),KV cache 池只有 2 块、free_block_ids为空,schedule()调用如何走?最终会触发assert scheduled_seqs吗?走完执行轨迹后,主要回答:为什么 nano-vllm 在显存预算里留余量?把preempt的self.waiting.appendleft(seq)改成self.waiting.append(seq)(放队尾),其他不动。在长时间运行的场景下,被抢者会出现什么观测得到的现象?给出一个具体场景(可借用第 5 节的设定)说明改动前后调度结果的差异。思考题参考答案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 维护,完全失去块抽象的意义。会触发 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 收到无效输入。被抢者再次被调度延迟极长,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 条目失效窗口降到最短。
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_size1: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_size1)一行表达式把两件事合并为一个比较。先单独解析两边:右边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)。两种取值组合如下:len(seq) % block_size右边布尔表达式比较条件can_append返回值物理含义0False(转为 0)len(free) 0永真True上一轮 token 写入当前块的最末 1 个位置,本轮还不需要新块1True(转为 1)len(free) 1,需至少 1 块取决于池子本轮即将写新块,必须有空闲块2 到block_size − 1False(转为 0)len(free) 0永真True当前块还没写满,继续写第二行是唯一可能返回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_size1: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:seqself.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_tokens1seq.is_prefillFalseself.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中断退出时不执行。while退出方式else是否执行条件由 True 变 False,自然退出是循环体内执行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时的状态对应到结局:进入内层时的状态内层while行为退出方式else是否执行当前 seq 命运can_append(seq)第一次就True循环体一次都不执行条件由 True 变 False(指not can_append由 True 变 False)是调度成功,加入scheduled_seqscan_append(seq)失败,self.running非空preempt(self.running.pop())抢队尾,然后重检can_append抢一条或多条队尾后,池子有空块、can_append转 True,条件失败退出是调度成功can_append(seq)失败,self.running空preempt(seq)抢自己,然后breakbreak否不加入scheduled_seqs,seq 状态置为 WAITING,加入 waiting 队首三种结局对应不抢 / 抢队尾 / 抢自己。上面把preempt(seq)当作单步操作处理;它内部其实做了四件事,每一件都对应一个状态变化。4.preempt的四个动作与 prefix cache 的部分恢复机制被抢者在 preempt 内部经历了什么、被抢之后是否真的全部丢失,需要拆开 preempt 函数看。preempt函数本身只有四行:# scheduler.pydefpreempt(self,seq:Sequence):seq.statusSequenceStatus.WAITING seq.is_prefillTrueself.block_manager.deallocate(seq)self.waiting.appendleft(seq)四个动作各对应一个语义层面的状态变化。下面逐条看:动作 1:status WAITINGL07 第 1 节讲过 SequenceStatus 的三态机:WAITING → RUNNING → FINISHED。preempt 对应这个三态机上的反向转换——从 RUNNING 退回 WAITING。这一行的物理含义是:seq 从正在被推进的活跃序列变回等待被调度的候选序列。动作 2:is_prefill Trueis_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):blockself.blocks[block_id]block.ref_count-1ifblock.ref_count0:self._deallocate_block(block_id)seq.num_cached_tokens0seq.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(放队首)。两者的物理含义对照如下:操作用途seq 在 waiting 中的位置waiting.append(seq)上层接入的新请求队尾(等队列里所有比它先来的都进了 running 再轮到自己)waiting.appendleft(seq)preempt 把被抢者加入 waiting队首(下次schedule()进 prefill 分支第一个就是它)为什么 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_idself.free_block_ids.popleft()# 从 free pool 取一块blockself.blocks[block_id]assertblock.ref_count0# 不变式: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_count1, 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_blocks0num_new_blocksseq.num_blocks# 上限:假设所有块都要新分配foriinrange(seq.num_blocks-1):# 只走前缀完整块,最末未满块跳过token_idsseq.block(i)hself.compute_hash(token_ids,h)# 沿前缀链算 hashblock_idself.hash_to_block_id.get(h,-1)ifblock_id-1orself.blocks[block_id].token_ids!token_ids:break# 字典里没条目或内容不符 → 后续也不必再查num_cached_blocks1# 命中:这块 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 的状态:seqlen(seq)block_tablelen % block_size是否边界态说明A17[b0, b1]1是b0 已满 16 token,b1 已写 1 token,本轮需要新块B18[b2, b3]2否b3 已写 2 token,本轮在 b3 继续写C17[b4, b5]1是b4 已满,b5 已写 1 token,本轮需要新块hash_to_block_id状态(L05 已讲:只有满块进字典):满块字典条目b0hash(A 第 0 块的 16 token)→ b0b2hash(B 第 0 块的 16 token)→ b2b4hash(C 第 0 块的 16 token)→ b4b1、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)的四个动作:C.status WAITINGC.is_prefill Truedeallocate(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()。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 1A.is_prefill Falsemay_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 1B.is_prefill Falsemay_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 分支返回。末态汇总与下轮命中分析字段末态running[A, B]waiting[C]scheduled_seqs[A, B](本轮 forward 处理)A.block_table[b0, b1, b5]B.block_table[b2, b3]C.block_table[]free_block_ids[b4]hash_to_block_id{hash(b0): b0, hash(b2): b2, hash(b4): b4}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)与判定面板随每一步同步变化:preempt-flow6. 思考题请先独立作答,再阅读下方提示。如果某个工程师把block_size改成 1(每块只能存 1 个 token),can_append表达式的右边会一直为 0 还是 1?抢占频率会怎么变化?为什么 nano-vllm 选择默认 256 而不是 1?若 running 队列只剩 1 条 seq A(len 17,block_table [b0, b1],边界态),KV cache 池只有 2 块、free_block_ids为空,schedule()调用如何走?最终会触发assert scheduled_seqs吗?走完执行轨迹后,主要回答:为什么 nano-vllm 在显存预算里留余量?把preempt的self.waiting.appendleft(seq)改成self.waiting.append(seq)(放队尾),其他不动。在长时间运行的场景下,被抢者会出现什么观测得到的现象?给出一个具体场景(可借用第 5 节的设定)说明改动前后调度结果的差异。思考题参考答案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 维护,完全失去块抽象的意义。会触发 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 收到无效输入。被抢者再次被调度延迟极长,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 条目失效窗口降到最短。
