课程 09 · 生产调度

预算、抢占、淘汰

同一个 schedule()，nano-vllm 用 50 行做到「能跑」，vLLM 用 3800 行做到「在几百张卡上跑不崩」。这一课只讲它多出来的三件事：token 预算、抢占策略、块淘汰。

约 60 分钟源码：v1/core/sched/scheduler.py · v1/core/kv_cache_manager.py · v1/core/block_pool.py 前置：08

2026-11-08 源码校正

本页已按本地固定commit修正相关描述。三框架对照 · 带行号的离线证据 · 核查与勘误详情。

1预算：三个数字同时约束

scheduler.py · L726–729token_budget = self.max_num_scheduled_tokens
spec = self.vllm_config.speculative_config
draft_slots = spec.max_num_new_slots_for_drafting if spec is not None else 0
input_budget = self.scheduler_config.max_num_batched_tokens

nano-vllm 只有一个 max_num_batched_tokens。vLLM 有三层：

预算	约束什么	为什么单独存在
`max_num_scheduled_tokens`	这轮总共算多少 token	硬上限，和显存/延迟目标挂钩
`max_num_batched_tokens`	这轮「输入」最多多少 token	每请求还需扣除drafting的额外预留
`draft_slots`	每请求drafting预留输入位	不能等同本轮已包含的draft验证数或KV块数

2顺序反了：vLLM 先 running

nano-vllm 是「先尽量 prefill，再 decode」。vLLM 反过来[scheduler.py L800–802]：

# First, schedule the RUNNING requests.
req_index = 0
while req_index < len(self.running) and token_budget > 0:
    ...

running优先让已经开始处理的请求继续推进；running中也可能有未完成的chunked prefill，不能全部等同decode。具体公平性、延迟与抢占率仍受策略和负载影响。

nano-vllm 的顺序在单机小模型上问题不大（一轮很快），但在生产里会造成 decode 饥饿：源源不断的新请求让 running 里的序列永远排不上队。vLLM 的取舍是：先保证在跑的请求向前推进，再用剩余预算接纳新请求。

面试点

先running保护已有进度并用剩余预算接纳waiting；这是一种策略选择，不能仅由顺序推导“抢占率最低”的性能结论。

3抢占：谁当牺牲品

scheduler.py · L938–945if self.policy == SchedulingPolicy.PRIORITY:
    preempted_req = max(self.running, key=lambda r: (r.priority, r.arrival_time))
else:
    preempted_req = self.running[-1]      # 默认：最后进来的

默认策略与 nano-vllm 完全一致——running[-1]，最新的先牺牲。但 vLLM 多了两件事：

优先级策略：max(priority, arrival_time) 选「优先级最低 + 最晚到」的那条。多租户场景下，可据业务策略赋不同优先级，但不能保证绝不抢占。
抢占后的清理[L1841]：num_computed_tokens = 0、清空 spec_token_ids、标记 in-flight 输出为 stale、num_preemptions += 1、把请求 prepend 回 waiting 队首。

和 nano-vllm 的 preempt() 对照，你会发现连「插回队首」都一样——不同的是 vLLM 要处理异步调度下「已经发出去但还没回来的 token」，所以有 drop_stale_output 这一层。

4前缀缓存：哈希在请求创建时就算好了

nano-vllm 在 hash_blocks() 里边算边登记；vLLM 反过来了——Request 一创建就计算好 block_hashes[request.py L235–240]，每追加 token 就增量更新。

kv_cache_manager.py · L296–307# 全部命中也要重算最后一个 token 才能拿 logits
max_cache_hit_length = request.get_max_cache_hit_length(max_cache_hit_length)
computed_blocks, num_new_computed_tokens, num_uncached = (
    self.coordinator.find_longest_cache_hit(request.block_hashes, max_cache_hit_length)
)

常规生成需要重新计算最后位置以取得hidden/logits，因此最大前缀命中长度要留出该位置；完整块对齐可能导致重算整个最后块，而不只是一个token。例如B=16、prompt=32时实际命中16，另16需计算。

如果没有这一行，一个「完全命中」的请求会拿不到 logits——这是实现前缀缓存时最经典的坑。

块的淘汰：双向链表而不是 deque

kv_cache_utils.py · L261–273class FreeKVCacheBlockQueue:
    """... doubly linked list of free blocks ...
    to support removing a block in the middle of the queue in O(1) time.
    ...
    1. The least recent used block is at the front (LRU)."""

nano-vllm的deque也能remove中间元素，但这是O(n)查找；vLLM的侵入式双向链表借已知节点可O(1)摘除。复杂度差别不是“deque完全不能移除中间元素”。

cached块的常规行为可用LRU理解，但无hash块优先放free队首，evict_first等路径可调整顺序。ref_cnt=0的块仍可能保有可命中的hash和KV。完整生命周期见28课。

5`allocate_slots`：一个函数塞进了所有场景

kv_cache_manager.py · L379–395def allocate_slots(
    self, request, num_new_tokens,
    num_new_computed_tokens=0,          # 刚命中的前缀 token 数
    new_computed_blocks=None,
    num_lookahead_tokens=0,             # 投机解码要预留的 token
    num_external_computed_tokens=0,     # KV connector 从别处搬来的
    delay_cache_blocks=False,           # PD 分离：块先占、稍后再写
    full_sequence_must_fit=False,       # 准入控制：当前已知序列需可容纳
    reserved_blocks=0,                  # 给在飞序列留的余量
    ...):

nano-vllm 的 allocate(seq, num_cached_blocks) 只有两个参数。vLLM 的十几个参数，每一个都对应一种真实场景：

参数	场景
`num_lookahead_tokens`	投机解码：draft token 的 KV 也要地方放
`num_external_computed_tokens`	PD 分离 / KV 复用：KV 从别的节点传过来
`delay_cache_blocks`	KV 还在传输中，块先占住但不能登记进前缀缓存
`full_sequence_must_fit`	准入控制：chunked prefill 只看第一块可能会超卖，检查当前已知序列的容量，不保证未知未来输出
`reserved_blocks`	给已经 in-flight 的序列留安全余量，避免它们被饿死

full_sequence_must_fit检查当前已知request.num_tokens所需容量；它不会保证全部未知未来输出也一定装下。块分配还受lookahead、group、reserved与watermark等约束。

6KV cache group：一个模型多种 KV

nano-vllm 假设所有层都是标准注意力，KV 形状统一。但现代模型不是：

滑动窗口注意力（SWA）：只保留最近 N 个 token 的 KV。
Mamba / 状态空间模型：没有 KV cache，只有固定大小的状态。
混合架构：一部分层用全注意力，一部分用 SWA。

vLLM 用 KV cache group 把它们分开管理：每个 group 有自己的块大小和分配策略，哈希键是 (block_hash, group_id) 的组合[block_pool.py L175–201]。

def get_cached_block(self, block_hash, kv_cache_group_ids):
    for group_id in kv_cache_group_ids:
        block = self.cached_block_hash_to_block.get_one_block(
            make_block_hash_with_group_id(block_hash, group_id))
        if not block:
            return None          # 任何一个 group 没命中，整体就算没命中

这解释了为什么 get_computed_blocks 会返回三个值——命中前缀、命中 token 数、以及某个 group 落后时的接缝位置（shared_prefix_boundary），后者用于保证跨请求复用不会把 Mamba 状态截断在错误的位置。

7和 nano-vllm 的对照表

问题	nano-vllm	vLLM v1
一轮跑什么	整轮 prefill 或整轮 decode	按token预算可混合，保留特殊分支
先调度谁	waiting 优先	running 优先
抢占策略	固定 LIFO	LIFO 或优先级
前缀哈希	postprocess 时增量登记	Request 创建时算好，块池统一管理
空闲块结构	deque（FIFO）	双向链表（LRU，O(1) 中间摘除）
KV 形状	单一	多 group（SWA / Mamba / 混合）
准入控制	prefill先分配当前全部块	可选检查当前已知序列

8练习 A · 算一次超卖

块大小 16，显存剩 100 个块。max_num_batched_tokens = 8192。现在涌入 40 条请求，每条 prompt 长 2048 token。如果只用「第一个 chunk 能装下就接」的准入策略，会发生什么？

展开：答案

每条请求至少需要 2048/16 = 128 个块才能跑完，但只剩 100 个块——一条都跑不完。

如果按 chunk 准入（只检查第一块），调度器可能一次接进 40 条，每条先分 1–2 个块开始 prefill；跑到一半块耗尽，只能不停抢占，吞吐崩到接近零，而且用户看到的是「所有请求都卡住」。

full_sequence_must_fit=True 的作用就是在这里：先算整条序列需要多少块，装不下就不接，让请求在 waiting 里排队，而不是接进来互相踩踏。

9练习 B · 闭卷测验

10面试复述卡

「vLLM 怎么决定这一轮跑哪些请求？」

展开：30 秒版本

「它维护一个 token 预算，先遍历 running 队列，给每条请求分配它「还差多少 token」；预算用完或显存不够就停。然后遍历 waiting 队列，用剩下的预算接纳新请求，同样是按块分配、按需切块。显存不够时从 running 尾部抢占——最新的请求先牺牲——释放它的块、清零已算 token 数、放回 waiting 队首。被抢占的请求之后要重新 prefill，除非前缀缓存还能命中一部分。」

可以问：「为什么 vLLM 不再支持 swap 抢占？」——v1 的设计取舍，值得单独聊十分钟，涉及 CPU 显存带宽和 PCIe 的现实。