vLLM 源码完全拆解（三）：Scheduler.schedule 如何分配 Token 预算与 KV Block

从引擎主循环进入真正的决策中心#

前两篇先建立了 vLLM 的整体模块地图，再沿着一次请求追踪了 LLM.generate()、EngineCore.step() 与输出处理的完整往返。在那条主链路里，核心事务被压缩成三步：schedule() 生成执行计划，Executor 执行模型，update_from_output() 提交结果。本篇停在第一步，只回答一个问题：一堆长短不一、到达时间不同、缓存命中情况不同的请求，怎样在一次 GPU 前向之前变成一个合法批次？

vLLM 源于 UC Berkeley 团队在 2023 年发表并收录于 SOSP 的 PagedAttention 工作；V1 引擎架构于 2024 年公开设计，2025 年开始成为项目主线。本文以 2026 年 9 月 26 日访问到的 vLLM main 分支提交 3b4566c5 为源码基线。这个日期很重要：Scheduler 是持续演进的热区，远程 KV、Mamba、异步调度等分支会变，但“请求欠多少计算、预算够不够、KV 槽位能不能兑现”这条主线相对稳定。

图源：vLLM 官方架构文档。图仍保留兼容性的宏观名称；在当前 V1 多进程架构中，调度器实际位于 Engine Core 进程，GPU Worker 只消费它生成的执行差量。

这里的 Scheduler 不是操作系统里负责线程时间片的 CPU 调度器。它更像一个每轮重新求解的小型资源分配器：输入是请求状态、KV Cache 状态和若干容量上限，输出是一份 SchedulerOutput。它不运行 Transformer，也不把 token 解码为文字，但它决定本轮 GPU 究竟算哪些位置，因此直接塑造吞吐、首 token 延迟、token 间延迟和抢占次数。

先建立状态账本：三条队列与两个计数#

阅读 schedule() 前，先认清它维护的状态。当前实现最关键的容器是：

1
self.requests: dict[str, Request] = {}
2
self.waiting = create_request_queue(self.policy)
3
self.skipped_waiting = create_request_queue(self.policy)
4
self.running: list[Request] = []

requests 是按 ID 查找请求的总表；running 保存已经接纳、持有执行状态的请求；waiting 保存尚未接纳或抢占后等待恢复的请求；skipped_waiting 保存暂时不满足外部依赖的请求，例如 grammar 尚未编译完成、远程 KV 尚未到达、流式会话还在等下一段输入。

把受阻请求放进单独队列，是为了避免队首阻塞。假设 FCFS 队首正在等待远端 KV，如果调度器每次只看它然后停止，后面所有本地可运行请求都会被拖住。当前源码会尝试提升受阻请求；条件仍不满足时，把它继续留在 skipped_waiting，转而检查别的请求。优先级模式则比较两个队列的队首，仍以全局优先级决定先看谁。

每个 Request 中最重要的不是“prefill 或 decode”标签，而是两类 token 计数：

• num_computed_tokens：已有有效计算结果、对应 KV 状态也应当存在的 token 数。
• num_tokens_with_spec：prompt token、已经生成的输出 token，以及当前投机草稿 token 的总数。

异步路径还会加入 output placeholder；它代表结果尚在流水线中、但调度时必须预留的位置。忽略少量高级分支后，请求 $i$ 在本轮开始时的计算欠账可以写成：

其中 $P_i$ 是 prompt token 数，$O_i$ 是已经生成并需要作为下一位置输入的输出 token 数，$S_i$ 是 speculative token 数，$H_i$ 是异步输出占位数，$C_i$ 是 num_computed_tokens。调度器的目标不是判断“当前属于哪个阶段”，而是在资源允许时让 $C_i$ 追上前四项之和。

这一个差值统一了四种看似不同的情况：

因此，源码注释明确说 Scheduler 内部没有独立的 decoding phase 与 prefill phase。这不是说 prefill 与 decode 的硬件特征相同，而是说调度状态不需要两套互斥状态机。两者最终都归约为“还有多少位置没计算”。

一轮调度不是排序，而是受约束的装箱#

若只看请求到达顺序，调度似乎就是从队列头部取若干项。实际至少有四类约束同时存在：

1. token 预算：一次模型前向最多安排多少 token，由 max_num_scheduled_tokens 与 max_num_batched_tokens 等配置共同约束。
2. KV 空间：新位置是否有物理 block 可写；有 token 预算不代表有显存槽位。
3. 请求槽位：max_num_active_reqs 或 max_num_seqs 限制 Worker 持有多少活跃请求状态。
4. 特性预算：多模态 encoder、LoRA、投机 lookahead、远程 KV 传输等各有附加约束。

对普通 decoder-only 模型，可先把问题简化为：

这里 $x_i$ 是本轮给请求 $i$ 安排的 token 数，$B_{token}$ 是 token budget，$B_{KV}^{free}$ 是可分配 KV 容量，$\Delta KV_i$ 是计算这 $x_i$ 个位置需要追加的缓存空间。第一个不等式控制一轮工作量，第二个不等式保证执行计划真的有地方落盘。

Scheduler 没有调用通用整数规划器，而是用面向在线服务的贪心扫描。主干可以压缩为下面的伪代码：

1
初始化 token、输入、encoder 等预算
2

3
遍历 running：
4
    计算每个请求的欠账
5
    用阈值和剩余预算裁剪本轮 token 数
6
    尝试分配新增 KV slots
7
    若失败，按策略抢占 victim 并重试
8

9
若本轮没有发生抢占：
10
    遍历 waiting / skipped_waiting：
11
        检查 grammar、远程 KV、LoRA 等接纳条件
12
        查询本地与远端前缀命中
13
        计算需要真正执行的 prompt 后缀
14
        尝试分配 KV slots
15
        成功后移入 running
16

17
构造 SchedulerOutput，只向 Worker 发送新增或变化的状态

顺序上的“先 running，后 waiting”非常关键。running 请求已经持有 KV 与 Worker 侧状态，优先推进它们通常能降低 token 间延迟，也避免频繁回收再重算。waiting 请求只有在剩余预算与容量都允许时才被接纳。当前官方优化文档把这一策略概括为优先安排 decode，再把剩余 token budget 给 prefill；源码实现比这句话更一般，因为 running 中也可能存在尚未完成的 prefill chunk。

第一段扫描：running 请求怎样获得本轮份额#

当前 schedule() 开头保留了一段极有价值的真实源码注释：

1
# There's no "decoding phase" nor "prefill phase" in the scheduler.
2
# Each request just has the num_computed_tokens and
3
# num_tokens_with_spec.
4
# At each step, the scheduler tries to assign tokens to the requests
5
# so that each request's num_computed_tokens can catch up its
6
# num_tokens_with_spec.

进入 while req_index < len(self.running) 后，每个请求大致经历五道门。

1
num_new_tokens = (
2
    request.num_tokens_with_spec
3
    + request.num_output_placeholders
4
    - request.num_computed_tokens
5
)
6
num_new_tokens = min(
7
    num_new_tokens,
8
    token_budget,
9
    input_budget - draft_slots,
10
)

1
new_blocks = self.kv_cache_manager.allocate_slots(
2
    request,
3
    num_new_tokens,
4
    num_lookahead_tokens=self.num_lookahead_tokens,
5
)

第二段扫描：waiting 请求如何被接纳#

只有本轮没有发生抢占且引擎未暂停时，Scheduler 才继续接纳 waiting 请求。这个规则避免一边因内存不足把旧请求赶走，一边又马上接纳新请求，让系统进入明显的 thrashing。

waiting 路径比 running 更复杂，因为新请求尚未建立完整的执行状态，必须先回答四个问题：

1. 请求的外部依赖是否已经就绪？
2. 它能复用多少本地或远端 KV？
3. 真正需要新计算多少 token？
4. KV、请求槽位与附加特性预算是否都够？

前缀缓存命中怎样改写调度起点#

前缀缓存不是模型执行结束后的附属优化，而是 waiting 接纳路径的一部分。新请求首次调度时，Scheduler 调用 KV Cache Manager 查询已计算 block：

1
(
2
    new_computed_blocks,
3
    num_new_local_computed_tokens,
4
    shared_prefix_boundary,
5
    hit_diverged,
6
) = self._get_local_prefix_cache_hit(request)

命中数会成为该请求的计算起点。若 3000-token prompt 命中前 2048 个 token，那么 num_computed_tokens 从 2048 起步，本轮只为余下 952 个 token 争取预算。缓存改变的是欠账，不改变生成结果。

图源：vLLM 官方 Automatic Prefix Caching 设计文档。Scheduler 负责查询与接纳，KV Cache Manager 协调 block pool、free queue、哈希索引和 request-to-block 映射。

vLLM 使用块哈希而不是逐 token 扫描所有历史请求。一个完整 block 的哈希包含父前缀哈希、该 block token 和必要的额外信息；因此只有内容与前缀链都一致时才能复用。缓存粒度通常受 block 或 prefix_match_unit 边界约束，不完整尾块不能被当成完整公共前缀随意共享。

图源：vLLM 官方前缀缓存示例 Time 1。示例 block size 为 4，总计 10 个 block；首个请求占用 4 个，其中前三个已满并可加入哈希缓存，最后一个仍是部分填充状态。

图源：vLLM 官方前缀缓存示例 Time 2/3 对应图。新请求虽与旧请求共享 10 个开头 token，但按 4-token block 匹配时只能直接命中前 8 个；第三块只匹配一部分，必须重算。

命中 block 后还不能立即执行。allocate_slots() 会先 touch 这些 block：增加引用计数，并在必要时从 free queue 中移走，防止它们在本轮被另一项分配淘汰；然后才为未命中的后缀取空闲 block。这个顺序维持一个关键不变量：执行计划引用的缓存块，在 GPU 消费计划前不能被重新分配。

“free” 与“cached”为什么不是反义词#

前缀缓存最容易误读的一点，是一个 block 可以同时处于“没有活跃请求引用”和“内容仍可复用”两种状态。请求结束后，引用计数降为零，block 进入 free queue；如果哈希仍在，它又是 cached block。之后：

• 新请求命中它时，touch 将其从 free queue 移除并增加引用计数；
• 新分配需要它作为空闲 block 时，系统从队首弹出并先清除旧哈希，相当于真正淘汰缓存内容。

图源：vLLM 官方前缀缓存设计文档。图中 free queue 同时承担空闲分配顺序和缓存淘汰顺序，避免再维护一套独立 LRU 节点。

这种设计把“可立即覆盖的物理空间”和“若尚未覆盖则可复用的旧内容”统一到同一个 block 对象中。它近似实现零额外容量的前缀缓存：缓存不永久霸占空闲空间，一旦新工作需要容量，队首 cached block 可以被驱逐。

远程 KV Connector 会让流程再多一层。Scheduler 先比较本地块对齐命中与远端命中；同步加载可在本轮形成执行计划，异步加载则先分配目标 block，把请求置为 WAITING_FOR_REMOTE_KVS，真正数据到达后再恢复。这里必须防止本地部分尾块与远端写入发生 copy-on-write 冲突，也要为传输中的 block 做容量预留。它仍然遵循同一原则：在数据有效且所有权清晰前，请求不能被当作普通 running 请求执行。

一个混合批次逐步推演#

设本轮 max_num_batched_tokens = 16，KV 还有足够 block，队列中有四个请求：

若没有额外阈值，扫描过程是：

1. A 获得 1 个 token，预算从 16 变为 15，并为必要位置确认 KV slot。
2. B 获得 1 个 token，预算变为 14。
3. C 的欠账是 20，但只获得 min(20, 14) = 14，预算归零。
4. D 本轮不进入 waiting 扫描，即使它只需新算 4 个 token，也要等下一轮。

下一轮 C 的欠账降为 6。若 A、B 各又欠 1，先占 2 个预算，C 占 6，余下 8；随后 D 查询到 8-token 前缀命中，只需 4 个 token，于是可被接纳，最终本轮安排 12 个 token。

现在把 KV 条件改成“C 追加位置时恰好需要一个新 block，但 free queue 为空”。Scheduler 会尝试抢占 victim。FCFS 下通常从 running 尾部选；如果 C 自己就是最后一个且释放后仍无法给它分配，那么 C 被转回 waiting，本轮不会再接纳 D。下一轮 C 可以借助刚释放或可命中的 block 恢复，但此前未缓存部分可能需要重算。

这个例子显示了三种常被混在一起的“优先级”：

• 扫描优先级：running 先于 waiting；
• 队列策略：FCFS 或显式 priority 决定同一集合中的顺序；
• 可行性优先：当前不可执行的高位请求可能被跳过，让可执行请求填满设备。

只有把这三层分开，才能解释为什么一次实际批次看起来没有严格按到达时间排列。

SchedulerOutput：计划必须足够小，也必须足够完整#

调度完成后，Scheduler 不把全部 Request 对象复制给 Worker，而是构造状态差量。关键内容包括：

• num_scheduled_tokens：每个请求本轮计算多少 token；
• scheduled_new_reqs：首次接纳请求的 prompt、采样参数、block IDs 等完整启动信息；
• scheduled_cached_reqs：已在 Worker 中存在的请求，只发送新增 token、block 与计数变化；
• scheduled_spec_decode_tokens：本轮参与验证的草稿 token；
• scheduled_encoder_inputs：多模态 encoder 本轮需要处理的输入；
• finished_req_ids 与 free_encoder_mm_hashes：通知 Worker 清理持久状态；
• KV Connector、copy-on-write 和新 block 清零所需元数据。

这种 new/cached 分流是 V1 的关键设计。假设 256 个 decode 请求每轮各推进 1 token，如果每一步都序列化完整 prompt、采样参数和全部 block table，CPU 与 IPC 开销会随历史长度反复增长。Worker 保留稳定状态后，Engine Core 只发送变化部分，热路径开销更接近本轮新增工作量。

但差量协议也带来一致性要求。Scheduler 认为请求已经有哪些 block、Worker 实际保存哪些 block table、异步 GPU 是否仍可能写旧 block，三者必须一致。源码里的 finished_req_ids、reset_preempted_req_ids、延迟 free 与 stale output 处理，都是在守住这个边界。调度器看似只做 Python 列表操作，实际上是在生成一份跨进程、跨 CPU/GPU 时间线的事务日志。

FCFS、priority 与公平性边界#

vLLM V1 支持 fcfs 与 priority 两种基础策略。FCFS 按到达时间排序；priority 先比较用户给定优先级，数值更小者更早，同优先级再按到达时间打破平局。

priority 不等于硬实时保证。高优先级请求仍然可能因为以下原因无法立即运行：

• KV block 不足，且正在执行的异步工作暂时不能安全释放；
• LoRA 并发上限已经用满；
• grammar、encoder 特征或远程 KV 尚未就绪；
• token budget 已被更早扫描的 running 请求耗尽；
• 流水并行或异步调度要求等待特定 step。

同样，FCFS 也不是绝对排他。源码在某些 num_new_tokens == 0 的分支明确使用 continue，允许后面的请求运行。严格阻塞式 FCFS 可以保持最纯粹的顺序，却可能因一个依赖未就绪的请求浪费整个 GPU；vLLM 选择工作保守性更低、设备利用率更高的做法。

公平性主要通过三种机制间接实现：队列顺序防止新请求无限插队；long prefill 阈值限制单个长请求的单轮份额；chunked prefill 给 decode 留出进入后续轮次的机会。它不是加权公平排队算法，也不会为每个租户维护长期服务份额。需要多租户配额、截止期或成本权重时，通常还要在网关或自定义 Scheduler 层补充策略。

高级分支应该怎样读，才不会淹没主线#

当前 scheduler.py 已超过三千行，因为同一个执行计划要兼容许多能力。第一次阅读不应逐个分支平铺，而应把它们放回四个问题。

调试 Scheduler：最有用的是记录决策差值#

直接打印整个 Request 或全部 block table 会严重扰动热循环。更有效的办法是先用单卡、短输出、确定性采样构造小负载，每轮只记录：

1
step=12 token_budget=4096 scheduled=1538
2
req=A state=RUNNING debt=1 grant=1 new_blocks=0
3
req=B state=RUNNING debt=2048 grant=1537 new_blocks=97
4
waiting=3 running=2 preempted=0 kv_usage=0.71

推荐断点顺序如下：

1. Scheduler.add_request()：确认请求进入 waiting 还是 skipped_waiting。
2. Scheduler.schedule() 入口：检查 token budget、running 与 waiting 长度。
3. running 循环中 num_new_tokens 计算之后：验证欠账和裁剪原因。
4. KVCacheManager.allocate_slots()：区分 token 预算不足与 KV 容量不足。
5. _preempt_request()：观察 victim、已计算长度和重算代价。
6. waiting 路径的 get_computed_blocks()：确认前缀命中数为何停在某个边界。
7. SchedulerOutput 构造处：核对 Worker 将收到哪些 new/cached 差量。

调试时应持续检查五个不变量：

• sum(num_scheduled_tokens.values()) 不超过本轮上限；
• token budget 与 input budget 永不为负；
• len(running) 不超过活跃请求上限；
• num_computed_tokens 指向的位置必须有有效 KV 或明确的远程加载状态；
• 被 SchedulerOutput 引用的 block 在 Worker 消费前不能回收到其他请求。

若 TTFT 高但没有抢占，先看长 prefill 是否被过小 budget 切成太多轮、队列是否持续有 decode；若 ITL 抖动，检查单轮 prefill chunk 是否过大；若日志频繁出现 preemption，优先看 KV Cache 容量、max_num_seqs 和 max_num_batched_tokens，而不是先怀疑 CUDA Kernel。官方优化文档也建议通过 Prometheus 指标或统计日志观察累计抢占次数。

配置旋钮背后的因果关系#

理解源码后，几个常用参数不再只是经验值：

参数之间存在耦合。增大 max_num_seqs 却不给更多 KV 空间，可能只会提高接纳后抢占概率；减小 max_num_batched_tokens 能改善已有 decode 的 ITL，却可能让新长 prompt 跨更多 step；打开前缀缓存能减少共享 prompt 的计算，但无法减少新生成 token 的逐步 decode 成本。调优应围绕实际负载的输入长度、输出长度、前缀重复率和延迟目标，而不是复制一组固定数字。

读完 schedule() 应该留下的源码地图#

V1 Scheduler 的核心不是“把 prefill 和 decode 分开排队”，而是统一维护每个请求的计算欠账，再用多重预算逐层裁剪。running 扫描优先保护已经在途的请求；waiting 扫描完成前缀查询与新请求接纳；allocate_slots() 是计划能否兑现的内存关口；抢占则在容量不足时用重算换空间。

最值得记住的五条关系是：

1. num_tokens_with_spec - num_computed_tokens 把 prefill、decode、chunked prefill 与投机验证统一成 token 欠账。
2. token budget 决定“本轮愿意算多少”，KV block 决定“这些结果有没有地方存”。
3. chunked prefill 是欠账被剩余预算裁剪后的自然结果，不需要第二套阶段状态机。
4. 前缀缓存先改变计算起点，再参与 block touch 与追加分配；命中与容量管理不可分开。
5. SchedulerOutput 是跨进程执行契约，调度正确性最终要由 Worker 状态、KV 所有权和异步时间线共同保证。

下一篇将沿本篇最关键的调用继续进入 KVCacheManager.allocate_slots()：拆解 block pool、free queue、哈希前缀索引、引用计数、touch/evict/free 顺序，以及一个逻辑请求的 block table 怎样增量交给 ModelRunner。

参考资料#

1. vLLM V1 Scheduler 源码（本文基线提交）
2. vLLM V1 SchedulerOutput 数据结构
3. vLLM KVCacheManager 源码
4. vLLM V1 用户指南
5. vLLM 官方架构总览
6. vLLM SchedulerConfig API 文档
7. vLLM Optimization and Tuning：Chunked Prefill 与抢占调优
8. vLLM Automatic Prefix Caching 设计文档
9. vLLM Automatic Prefix Caching 使用文档
10. vLLM Hybrid KV Cache Manager 设计文档
11. vLLM V1 Engine Architecture RFC
12. Efficient Memory Management for Large Language Model Serving with PagedAttention