vLLM Deep Dive Part 3: The Scheduler - Brain of vLLM

Posted on 2026-04-13 Edited on 2026-05-06 In AI/ML

第三部分：Scheduler——vLLM 的大脑

简介

Scheduler 是 vLLM 的核心调度器。在每个微秒级的时间窗口内，它都要做出关键决策：处理哪些 request、计算多少个 token、何时 preempt request，以及如何最大化 GPU 利用率。本文将深入探讨 Scheduler 的算法与实现。

调度挑战

问题空间

在任意时刻，Scheduler 必须处理：

等待中的 request：等待处理的新 prompt
运行中的 request：正处于 decode 阶段的持续生成任务
资源限制：有限的 GPU 内存和计算预算
目标冲突：最小化延迟 vs. 最大化吞吐量
动态负载：request 异步到达和完成

没有简单的解决方案

与传统批处理不同，LLM 推理服务面临独特挑战：

请求长度不固定：无法预测完成时间
内存随序列长度增长：不仅仅受计算限制
prefill 与 decode 的不对称性：prefill 每个 token 耗时约为 decode 的 100 倍
共享 KV cache：内存决策影响所有 request

Continuous Batching

vLLM 的核心创新：continuous batching（又称迭代级批处理）。

传统静态批处理

# Static batching - wait for batch to fill
batch = []
while len(batch) < batch_size:
    batch.append(wait_for_request())

# Process entire batch
outputs = model.forward(batch)

# Wait for ALL requests to finish
while any_request_incomplete(batch):
    outputs = model.forward(batch)

# All done - start next batch

问题：

队头阻塞：快速 request 需等待慢速 request
低 GPU 利用率：随着 request 完成，batch 规模不断缩小
高延迟：必须等待 batch 填满

Continuous Batching

# Continuous batching - add/remove every iteration
running = []

while True:
    # Remove finished requests
    running = [r for r in running if not r.finished]

    # Add new requests if there's capacity
    while can_fit_new_request() and waiting_requests:
        running.append(waiting_requests.pop())

    # Process current batch
    outputs = model.forward(running)

    # Immediately continue - no waiting!

优点：

无队头阻塞：request 完成后立即离队
持续高 GPU 利用率：始终维持最大 batch 大小
更低延迟：新 request 可立即开始处理

Scheduler 架构

文件位置：vllm/v1/core/sched/scheduler.py

核心数据结构

Scheduler 维护 requests、waiting、running 和 skipped_waiting，并持有 KVCacheManager / EncoderCacheManager 等资源管理器。其中 max_num_scheduled_tokens 的来源是：

self.max_num_scheduled_tokens = (
    self.scheduler_config.max_num_scheduled_tokens
    if self.scheduler_config.max_num_scheduled_tokens
    else self.scheduler_config.max_num_batched_tokens
)

也就是说，max_num_batched_tokens 现在是 fallback，而不是唯一来源。

Request 状态

当前 V1 的 request 状态比“WAITING → RUNNING → FINISHED”更细：

WAITING
WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR
WAITING_FOR_REMOTE_KVS
WAITING_FOR_STREAMING_REQ
RUNNING
PREEMPTED
多个 finished 子状态：FINISHED_STOPPED、FINISHED_LENGTH_CAPPED、FINISHED_ABORTED、FINISHED_IGNORED、FINISHED_ERROR、FINISHED_REPETITION

因此，更准确的流转应理解为：

新请求通常从 WAITING 进入 RUNNING
被抢占的请求会变成 PREEMPTED 并重新入队
恢复执行时是 PREEMPTED → RUNNING
结束时会进入某个具体的 finished 子状态，而不是单一的 FINISHED

Request 队列

当前 RequestQueue 的核心 API 是：

queue.add_request(request)
request = queue.pop_request()
request = queue.peek_request()
queue.prepend_request(request)

如果启用 priority 策略，优先级大小规律也与很多直觉相反：数值越小，优先级越高。PriorityRequestQueue 直接依赖 Request.__lt__，比较顺序是：

priority（更小者优先）
arrival_time（更早者优先）
request_id

调度算法

整体流程

schedule() 的核心思路仍然是“先处理 running，再在条件允许时接纳 waiting”。SchedulerOutput 会分别携带：

scheduled_new_reqs
scheduled_cached_reqs
num_scheduled_tokens: dict[str, int]
total_num_scheduled_tokens
scheduled_spec_decode_tokens
scheduled_encoder_inputs
finished_req_ids
preempted_req_ids
以及 prefix / encoder / connector 相关的附加信息

可以把主循环简化理解为：

def schedule(self) -> SchedulerOutput:
    token_budget = self.max_num_scheduled_tokens

    # 1. 先调度 running request
    # 2. 必要时执行 preemption
    # 3. 仅在本轮没有 preempt 时尝试接纳 waiting request
    # 4. 构造包含 per-request token 预算、spec decode、
    #    encoder inputs 和 finished/preempted IDs 的 SchedulerOutput

第一步：Token Budget

token budget 的概念没有变化：它仍然是当前迭代最重要的“算力 / latency / activation memory”上限之一。当前实现用 self.max_num_scheduled_tokens 作为每轮 budget，并在 chunked prefill、running request 续跑、spec decode 等路径上共享这份预算。

第二步：调度运行中的 Request

当前 scheduler 不再显式维护“prefill phase / decode phase”两套完全独立的 API。更准确的做法是根据：

request.num_computed_tokens
request.num_tokens_with_spec
request.num_output_placeholders

之间的差值来决定本轮还需要为该 request 安排多少 token。

对 running request 来说，scheduler 主要会：

计算本轮 num_new_tokens
结合 long_prefill_token_threshold 等配置裁剪超长 prefill
为已命中的 prefix cache / 外部 KV transfer / speculative lookahead 计算额外上下文
调用 allocate_slots() 尝试拿到新 slot
若拿不到 slot，则按当前策略 preempt 其他 request 或 preempt 当前 request

因此，比起“给 request 写回 request.num_scheduled_tokens = ...”，当前实现更准确的说法是：每轮调度数量被记录在 SchedulerOutput.num_scheduled_tokens[request_id] 中。

第三步：调度等待中的 Request

一个新 request 要进入本轮 batch，通常会经历这些检查：

从 waiting 或 skipped_waiting 中选择可调度的队列
处理 structured output grammar、remote KV、streaming 等阻塞状态
先调用 get_computed_blocks() 查找 prefix cache 命中
再用 can_fit_full_sequence() 判断完整序列是否可以被系统接纳
通过 allocate_slots() 为本轮真正需要的 token 分配 slot

这里有两个关键点：

scheduler 维护的是 waiting + skipped_waiting 两条队列，而不是单一 waiting queue
只有当本轮没有发生 preemption 时，scheduler 才会继续接纳 waiting request

第四步：处理 Preemption

preemption 通过 _preempt_request() 完成，流程更接近：

def _preempt_request(self, request, timestamp):
    self.kv_cache_manager.free(request)
    self.encoder_cache_manager.free(request)
    request.status = RequestStatus.PREEMPTED
    request.num_preemptions += 1
    self.waiting.prepend_request(request)

需要注意：

request 会以 PREEMPTED 状态重新入队，而不是简单地回到 WAITING
preemption 后确实需要重新调度，但如果 prefix cache 还能命中完整 block，后续恢复执行时不一定要“从零开始重算”
victim 选择也不是固定的“进度最少者优先”：在 priority 模式下，会先牺牲较差优先级的 running request；FCFS 模式下则更接近按当前运行队列尾部顺序处理

高级调度策略

Chunked Prefill

chunked prefill 仍然存在，但当前实现不是 self.chunk_size 这种字段驱动。更贴近源码的配置包括：

enable_chunked_prefill
long_prefill_token_threshold
max_num_partial_prefills
max_long_partial_prefills

因此，当前行为更像是：

对超长 prefill request 截断本轮 num_new_tokens
在 token budget 内把长 prompt 分摊到多轮
让长 prompt 不至于一次耗尽整个 batch 配额

优先级调度

当前 vLLM 只支持两种调度策略：

fcfs
priority

priority 模式下数字越小越先执行。可以这样理解：

1
2
3

# Lower numeric value = higher scheduling priority
priority = 0   # interactive / urgent
priority = 10  # background

支持 Speculative Decoding

当前 scheduler 对 speculative decoding 的感知体现在：

request 上的 spec_token_ids
SchedulerOutput.scheduled_spec_decode_tokens
num_lookahead_tokens
输出更新阶段对 draft token 的接受 / 拒绝处理

因此，比起 main_model.verify(draft_tokens) 这种直观伪代码，更准确的描述是：scheduler 会为 lookahead / draft token 预留 slot，并通过 scheduled_spec_decode_tokens 把本轮 spec decode 信息传给后续执行与输出更新路径。

Request 重排序

当前本地源码里并没有一个按“预估 prefix cache 命中率”对 waiting requests 进行重排序的 reorder_for_cache_hits() 实现。waiting 请求的顺序主要由 FCFS / priority queue 决定，再叠加 skipped_waiting 的恢复逻辑。

资源管理

KV Cache 分配

更贴近源码的准入流程是：

computed_blocks, num_cached_tokens = kv_cache_manager.get_computed_blocks(request)

if kv_cache_manager.can_fit_full_sequence(
    request,
    num_new_computed_tokens=num_cached_tokens,
    new_computed_blocks=computed_blocks,
):
    new_blocks = kv_cache_manager.allocate_slots(
        request,
        num_new_tokens,
        num_new_computed_tokens=num_cached_tokens,
        new_computed_blocks=computed_blocks,
    )

当存在 sliding window、external KV transfer、spec decode 或 encoder-decoder cross-attention 时，allocate_slots() 还会综合这些上下文一起计算需要分配的 block 数量。

内存压力处理

当前 scheduler 的内存压力处理更接近“尝试为 running request 分配 slot，失败时根据当前策略 preempt”。prefix cache 的显式淘汰接口是 kv_cache_manager.evict_blocks(block_ids)，它按 block id 清理缓存索引。

Encoder Cache 管理

多模态 / encoder-decoder 场景下，当前 request 并不是暴露 encoder_input_ids 这个简化字段。scheduler 会通过 request.mm_features、_try_schedule_encoder_inputs()，以及 EncoderCacheManager.can_allocate() / allocate() / check_and_update_cache() 来判断 encoder side 是否有容量。

性能指标

Scheduler 统计信息

SchedulerStats 的重点字段包括：

num_running_reqs
num_waiting_reqs
kv_cache_usage
encoder_cache_usage
prefix_cache_stats
connector_prefix_cache_stats
kv_cache_eviction_events
spec_decoding_stats
perf_stats

而“本轮 preempt 了多少 request”这类信息，当前是放在 IterationStats.num_preempted_reqs 里，而不是 SchedulerStats.num_preempted。

优化目标

因此，当前 scheduler 更像是在平衡这些目标：

最大化吞吐量：尽可能在 token budget 内安排更多有效计算
最小化延迟：优先保持 running request 的连续推进
控制长 prompt 影响：通过 chunked prefill / long prefill threshold 避免大 prompt 独占
减少无谓 preemption：让 KV cache 与 encoder cache 的压力保持可控
尽可能利用 prefix cache / external KV：减少重复 prefill 计算

示例：调度时间线

下面给出一个更接近当前实现语义的简化时间线。注意这里使用的是 scheduler_output.num_scheduled_tokens[req_id] 这个“每轮输出”，而不是给 request 对象写回一个持久字段。

初始状态

1
2
3

waiting = [A(prompt=100), B(prompt=50)]
running = []
token_budget = 200

迭代 1

A 和 B 都还是新请求
scheduler 分别检查 prefix cache 命中、完整序列准入与 KV slot 分配
若两者都能被接纳，则输出里会类似地记录：

scheduler_output.num_scheduled_tokens = {
  "A": 100,
  "B": 50,
}

迭代 2

A、B 进入 running 集合
若此时到来一个超长请求 C，scheduler 会先为 running request 预留预算，再根据 long_prefill_token_threshold 与剩余 budget 决定 C 这一轮最多能推进多少 token
如果本轮发生了 preemption，则 waiting request 的接纳会被延后到下一轮

后续迭代

request 的自然完成不是在 schedule() 里直接调用某个 finish_request() helper，而是要等 model output 返回后，由 scheduler.update_from_output(...) 更新状态并判断 stop / length cap / error 等 finished 原因
若 B 被 preempt，scheduler 会把它以 PREEMPTED 状态重新入队；等资源恢复后，它会再次进入 RUNNING

调度策略

当前 vLLM 暴露的调度策略只有两种：

FCFS（先到先服务）

队列类型：FCFSRequestQueue
主要接口：add_request() / pop_request() / peek_request()
优点：简单、可预测
缺点：长 request 更容易拖慢后续 waiting request 的进入时机

基于优先级

队列类型：PriorityRequestQueue
排序规则：priority 数值越小越先执行；若相同则按 arrival_time，再按 request_id
优点：可以显式优先保障交互式 / 重要流量
缺点：如果优先级设计不当，低优先级 request 可能长期等待

排查 Scheduler 问题

高 Preemption 率

更贴近当前指标的观察方式是关注：

IterationStats.num_preempted_reqs
SchedulerStats.kv_cache_usage
SchedulerStats.encoder_cache_usage

如果 preemption 频繁发生，通常优先检查：

KV cache 是否过小
max_num_seqs 是否过高
是否启用了 chunked prefill，以及 long_prefill_token_threshold 是否合理

等待队列持续增长

如果 SchedulerStats.num_waiting_reqs 长时间偏高，通常意味着：

token budget 太保守
长 prompt 占用了过多 budget
priority / FCFS 策略与业务流量类型不匹配

高延迟

如果 TTFT 偏高，通常优先检查：

是否启用 chunked prefill
max_num_scheduled_tokens 是否过大
prefix cache / external KV 是否发挥作用
高优先级交互流量是否需要单独的 priority 策略

关键要点

Continuous batching 通过每次迭代动态增减 request，消除了队头阻塞
Token budget 控制 batch 大小，平衡延迟与吞吐量的权衡
运行中的 request 拥有优先权，以最小化 decode 延迟
Preemption 是内存紧张时的最后手段：它会中断当前运行进度，但后续恢复时仍可能重新命中 prefix cache
Chunked prefill 在处理长 prompt 与交互式 request 之间取得平衡
当前的 SchedulerOutput 是结构化输出，会同时携带 per-request token 分配、spec decode、encoder 输入与 finished/preempted request 信息

下一步

在第四部分中，我们将探索 Request Processing——request 如何从 tokenization 到流式输出在系统中流转，以及跨迭代的状态管理机制。

参考资料

Scheduler 是 vLLM 的大脑，每秒钟要做出成千上万个瞬间决策，在满足延迟 SLA 的同时最大化 GPU 利用率。接下来，我们将看到 request 如何在系统中端到端地流转。