第3章 调度器：Token 的交通指挥

“Scheduling is about making choices, and every choice has consequences.” — Remzi H. Arpaci-Dusseau

3.1 LLM 推理调度的根本困境

在深入代码前，先理解为什么 LLM 推理调度特别难。传统 Web 服务的调度是”同质化”的——每个请求都走同样的代码路径、消耗差不多的 CPU。LLM 推理恰恰相反，一个请求在生命周期里会表现出两种截然不同的计算形态：

3.1.1 Prefill 与 Decode 的差异

一个推理请求（以 prompt_tokens=500, max_new_tokens=200 为例）的两个阶段：

预填充（Prefill）——处理用户输入的 500 个 Token。在单次 GPU kernel 调用里，500 个 Token 的 Query / Key / Value 一起算，attention 矩阵是 500×500 的三角矩阵。这一步compute-bound——GPU 的 TensorCore 满载，算力被吃完；FLOPs 需求正比于 prompt_len²；只产出 1 个输出 Token（prompt 末尾位置的采样结果）。

解码（Decode）——逐个生成后续 200 个 Token。每一步只算 1 个新 Token 的 Q，但要和前面 500 + 已生成数 个 Token 的 K/V 算 attention。这一步memory-bound——GPU 大部分时间在从 HBM 搬 KV Cache 进 SRAM，TensorCore 反而是闲的；FLOPs 需求正比于 current_len（线性增长）；每步产出 1 个 Token。

graph LR
    subgraph "Prefill 特征"
        P1["Compute-bound<br/>TensorCore 满载"]
        P2["一次算 N 个 Token<br/>FLOPs ∝ N²"]
        P3["高 GPU 利用率<br/>80-95%"]
        P4["决定 TTFT<br/>Time To First Token"]
    end

    subgraph "Decode 特征"
        D1["Memory-bound<br/>HBM 带宽打满"]
        D2["每步只算 1 Token<br/>FLOPs ∝ ctx_len"]
        D3["低 GPU 利用率<br/>15-40%"]
        D4["决定 TPOT<br/>Time Per Output Token"]
    end

    style P1 fill:#3b82f6,color:#fff,stroke:none
    style P2 fill:#3b82f6,color:#fff,stroke:none
    style P3 fill:#3b82f6,color:#fff,stroke:none
    style P4 fill:#3b82f6,color:#fff,stroke:none
    style D1 fill:#10b981,color:#fff,stroke:none
    style D2 fill:#10b981,color:#fff,stroke:none
    style D3 fill:#10b981,color:#fff,stroke:none
    style D4 fill:#10b981,color:#fff,stroke:none

两个观察：

(1) GPU 利用率形态完全不同。Prefill 时 GPU 是”吃撑”的，把请求排紧点没问题；Decode 时 GPU 是”饿”的，把 batch_size 加大是用不完的计算单元换更高的 KV Cache 搬运吞吐。这意味着一个好的调度器应该让这两种形态同时发生在一个 batch 里——Decode 请求填满计算空闲时间，Prefill 请求贡献高 GPU 利用率。这正是 V1 统一调度的起点。

(2) 两种指标口径分别。服务 SLA 通常关心两个数：首 Token 延迟 TTFT（从请求到达到第一个 Token 输出的时间）与每 Token 延迟 TPOT（生成每个后续 Token 的平均时间）。Prefill 决定 TTFT，Decode 决定 TPOT。调度策略的每一个取舍都会落在这两个指标的跷跷板上。

3.1.2 静态批处理的崩塌

在 LLM 推理被当成通用 DL 推理服务之前，大家的第一反应是 TF-Serving / TorchServe 式的静态批处理：攒一批请求、一起跑、出结果、下一批。理论上简单，实际上灾难性低效：

时间轴：静态批处理（batch size = 4）
        Req A (100 tokens)    ████████████░░░░░░░░░░░░░░  12ms
        Req B (250 tokens)    ███████████████████████░░░  23ms
        Req C (  5 tokens)    █░░░░░░░░░░░░░░░░░░░░░░░░░   1ms （早完成但干等 22ms）
        Req D ( 80 tokens)    ███████████░░░░░░░░░░░░░░░  11ms （早完成但干等 12ms）

短请求（C/D）早就完成了，但必须等整个 batch 里最长的请求（B）跑完，GPU 才能开始处理下一批。“座位”不释放——批次等效于一个”最慢请求”拉动的同步 barrier。在真实流量里这种浪费可能达到 50% 以上。

vLLM 采用连续批处理（Continuous Batching）：每一步结束后重新决定下一步参与计算的请求集合。一个请求完成了，立刻释放它的 KV 块和 batch 位置；一个新请求到了，如果有预算就立刻放进来。每一步都是一个”瞬时快照”，不存在”等别人”这回事。

但这就把问题推给了调度器——每一步都要做一次全局决策。做得好 GPU 100% 吃满，做得差抖来抖去。Scheduler 就是做这个决策的那个组件。

3.2 V1 的范式转移：统一 Token 调度

V0 时代的调度器代码（vllm/core/scheduler.py）相当复杂：Prefill 有一套路径，Decode 有一套路径，Chunked Prefill 是后来补丁进去的第三套路径，SequenceGroup（支持束搜索的组抽象）又是另一层。最终调度一个请求要走的分支数量，足以让新来的贡献者第一周只看懂主流程。

V1 做了一个核心的简化：调度器的输出本质上就是一个字典。

# vllm/v1/core/sched/output.py（概念性简化）
@dataclass
class SchedulerOutput:
    # 关键字段：每个请求本步要处理多少个 Token
    num_scheduled_tokens: dict[str, int]
    total_num_scheduled_tokens: int

    # 本步新入 RUNNING 的请求（需要给它们准备输入张量）
    scheduled_new_reqs: list[NewRequestData]

    # 本步继续 RUNNING 的请求（用之前已有的输入张量继续）
    scheduled_cached_reqs: list[CachedRequestData]

    # 本步完成 / 中止 / 抢占的请求
    finished_req_ids: set[str]
    preempted_req_ids: set[str]

    # KV 缓存分配：本步给哪些请求追加了哪些块
    scheduled_spec_decode_tokens: dict[str, list[int]]  # 投机解码（可选）

核心字段 num_scheduled_tokens: dict[str, int] 说明了一切：调度器不区分 Prefill 和 Decode，它只说”请求 A 这一步处理 128 个 Token，请求 B 这一步处理 1 个 Token”。128 可能是 A 的第一段 Prefill，也可能是 A 的中段 Prefill，也可能是 A 进了 decode 阶段第一次以 spec-decode 一次产 3-5 token——调度器不关心。

# 一次典型调度的输出可能长这样：
{
    "req-001": 128,   # A：可以是新请求的前 128 个 prompt token
    "req-002": 1,     # B：老请求解码 1 个 token
    "req-003": 64,    # C：另一个请求 prompt 的中间 64 个 token（chunked）
    "req-004": 4,     # D：spec-decode 阶段一次产 4 个 token
}

这种统一抽象带来了连锁优势：

1. Chunked Prefill 是天然的——把”Prefill 500 个 Token 必须一次做完”换成”可以分几拍做”，只需要在 budget 上限制每拍给出多少个 Token。没有特殊 codepath。

2. Prefill / Decode 混合批是天然的——SchedulerOutput 里既有 {A: 128} 也有 {B: 1}，Worker 拿到这个 dict 后把所有请求的 Token 拼接成一个大张量送进 attention kernel。现代的 FlashAttention-3 和 FlashInfer 原生支持 variable-length batches，不需要 padding，不需要 segment mask 之外的额外开销。

3. 调度代码短到能写明信片——整个 schedule() 主干不到 200 行，一读就懂。

4. 单元测试友好——输出是纯函数的 dict，给定输入状态能精确断言输出，没有隐式副作用要 mock。

V0 的 SequenceGroup 被拿掉了。它原本是为束搜索（beam search）设计的：一个请求在搜索空间里有多个候选分支，每个分支都是一个 Sequence，共享同一份 prompt KV。V1 的观察是：生产环境 99% 的流量是采样（sampling）或贪心（greedy），不用束搜索。把束搜索作为核心复杂性源头挂在路上，让每一个采样请求也交税——不划算。V1 把束搜索外化到 API 层（如果真要用，在 API Server 里展开成多个子请求），引擎核心保持纤细（截至当前版本，vllm/v1/ 下没有任何 beam_search 代码）。

3.2.1 统一抽象的核心不变式：num_tokens_with_spec

这个统一模型能自圆其说，靠的是 Request 类的一个单一标量字段。翻开 vllm/v1/request.py 第 110 行：

@property
def num_tokens_with_spec(self) -> int:
    return len(self._all_token_ids) + len(self.spec_token_ids)

加上 num_computed_tokens（已算过的 token 数），调度器的全部工作用一句话描述：每一拍，尽量让每个 RUNNING 请求的 num_computed_tokens 追平它的 num_tokens_with_spec。

这里 num_tokens_with_spec 包含三类 token：

1. prompt token（用户输入）
2. output token（已生成）
3. spec token（投机解码草稿模型提前预测的）

从调度器视角，这三者毫无区别——都是”等着被主模型 attention 一遍”的 token。这就是 Woosuk Kwon 在 scheduler.py line 138–147 写给后来贡献者的设计注释的精髓：

There’s no “decoding phase” nor “prefill phase” in the scheduler. Each request just has the num_computed_tokens and num_tokens_with_spec. … This is general enough to cover chunked prefills, prefix caching, speculative decoding, and the “jump decoding” optimization in the future.

把”算力要算多少 token”抽象成一个减法（num_new_tokens = num_tokens_with_spec - num_computed_tokens）之后，Chunked Prefill、Prefix Cache、投机解码、未来还要加的 Jump Decoding，全部变成对同一个 budget 的不同消费模式——不需要为每种新特性再拉一条新代码路径。这是 V1 之所以只有 200 行主干、却比 V0 功能更全的底层原因。后续第 12 章讲投机解码时会回到这个字段：草稿模型预测了 K 个 token 就把它们塞进 spec_token_ids，调度器自然地在下一拍分配 K+1 的预算（1 是给草稿 token 被拒后的回退 decode）给它——整条集成只动了 Request 的一个字段，没动调度器一行。

3.3 Scheduler.schedule()：逐阶段拆解

我们打开 vllm/v1/core/sched/scheduler.py，看 schedule() 方法。省略异常处理和日志后，它的主结构是：

def schedule(self) -> SchedulerOutput:
    # 1. 编列本步预算
    token_budget = self.max_num_scheduled_tokens  # 通常 = max_num_batched_tokens
    num_seqs_budget = self.max_num_seqs - len(self.running)

    # 2. 先续行 RUNNING 队列（每个老请求 decode 1 个 token）
    scheduled_running = self._schedule_running(token_budget)
    token_budget -= sum(scheduled_running.values())

    # 3. 再让 WAITING 队列入场（能吃多少预算吃多少）
    scheduled_new, scheduled_cached_prefill = self._schedule_waiting(
        token_budget, num_seqs_budget
    )

    # 4. 打包 SchedulerOutput
    return self._make_output(scheduled_running, scheduled_new, scheduled_cached_prefill)

看起来平平无奇的四步，每一步背后都有微妙的取舍。

3.3.1 阶段一：编列本步预算

预算由两个”旋钮”共同决定：

• max_num_batched_tokens——每步可以处理的最大 Token 数（Prefill + Decode 加起来）。这是直接约束 GPU 单次 kernel 规模的旋钮，典型值 2048~8192。
• max_num_seqs——同时 RUNNING 的最大请求数。这是约束 KV Cache 占用规模和 sampler 吞吐的旋钮，典型值 128~512。

两个旋钮相互独立：

graph TB
    subgraph "Budget 二维空间"
        A[max_num_batched_tokens=4096<br/>max_num_seqs=256<br/>balanced 在线服务]
        B[max_num_batched_tokens=16384<br/>max_num_seqs=1024<br/>高吞吐离线批]
        C[max_num_batched_tokens=2048<br/>max_num_seqs=64<br/>低延迟交互]
    end

    style A fill:#3b82f6,color:#fff,stroke:none
    style B fill:#10b981,color:#fff,stroke:none
    style C fill:#f59e0b,color:#fff,stroke:none

一个经验法则：max_num_batched_tokens 应该略大于你期待的”一次典型 Prefill 长度 × 同时能处理的 Prefill 请求数 + 当前 Decode 的请求数”。把它调小，可以让每步 GPU 计算时间短、单步延迟低——但连续批处理就”吃不饱”了。把它调大，吞吐上去了——但单步延迟上升，Decode 请求的 TPOT 抖动。

另一个约束我们之前没提：KV 池剩余块数。一个块装 16 个 Token（block_size=16）的 KV，剩 200 块就意味着本步最多还能放 3200 个 Token 的 KV 增量。Scheduler 会把 token_budget 再与 free_blocks * block_size 取 min。这个隐式约束会在下一节看到。

3.3.2 阶段二：续行 RUNNING 队列

_schedule_running 给每个已经在 RUNNING 状态的请求分配 1 个 Token（Decode 一步）。注意下面几个细节：

def _schedule_running(self, token_budget):
    scheduled = {}
    for req in self.running:
        if token_budget <= 0 or num_seqs_budget <= 0:
            # 预算耗尽 —— 抢占到 WAITING 队列
            self._preempt(req)
            continue

        # 每个 decode 步骤需要给请求追加 1 个 token 的 KV
        new_blocks_needed = self.kv_cache_manager.num_blocks_needed_for_append(req, 1)
        if self.kv_cache_manager.free_blocks < new_blocks_needed:
            # KV 池不够了 —— 抢占
            self._preempt(req)
            continue

        # 分配 KV 块（可能是 0 块，如果当前 block 还有空位）
        self.kv_cache_manager.append_slots(req, 1)
        scheduled[req.request_id] = 1
        token_budget -= 1

    return scheduled

优先续行已有请求、宁可抢占后来者。这个排序是有深意的：正在 decode 的请求最怕抖动——用户看到的”流式打字机”效果要求每 40-100ms 稳定出一个 token。一旦有一拍少给它 token，用户会立刻感到”卡”。相反，一个刚到的新请求延迟 200ms 才开始出 token，用户感知只是”稍微慢了”。所以延迟敏感度 decode >> prefill，调度器对 running 队列网开一面。

抢占被推到 RUNNING 队列里。如果一个正在 RUNNING 的请求拿不到 1 个 token 的 KV 块（池子满了），它会被 _preempt 回 WAITING。这个决策的一个副作用：抢占的受害者是最新加入 RUNNING 的那个还是最老的？V1 的默认策略是按入场时间从新到旧找受害者——新进来的刚吃了 Prefill 的预算，抢它损失最小；老请求已经生成了好多 token 了，抢它几乎是让用户白等。

3.3.3 阶段三：WAITING 队列入场

剩下的预算（token_budget 减去所有 RUNNING 请求吃掉的那 1 个）交给 WAITING 队列使用。这里要解决两类请求：

新请求（New Request）——刚从 API Server 收到 add_request 进入 WAITING。它需要做完整 Prefill（或在前缀缓存命中时跳过部分）。

被抢占后回到 WAITING 的请求——num_computed_tokens > 0 但 status == WAITING。它需要从断点继续 Prefill。

两类请求的处理逻辑是一样的——都是”给它多少个 Token 的预算，让它吞掉对应长度的 Prefill”：

def _schedule_waiting(self, token_budget, num_seqs_budget):
    scheduled_new = []
    scheduled_cached = []

    while self.waiting and token_budget > 0 and num_seqs_budget > 0:
        req = self.waiting[0]  # 取队首（FCFS）

        # 本次要吃掉多少 token？
        num_remaining = req.num_prompt_tokens - req.num_computed_tokens
        num_this_step = min(num_remaining, token_budget, self.max_chunk_size)

        # 先探查：前缀缓存能省多少？
        num_cached_blocks = self.kv_cache_manager.find_cache_hits(req)
        num_cached_tokens = num_cached_blocks * self.block_size
        num_new_compute = num_this_step - min(num_cached_tokens, num_this_step)

        # 需要新分配的 KV 块数
        new_blocks = ceil(num_new_compute / self.block_size)
        if self.kv_cache_manager.free_blocks < new_blocks:
            break  # KV 不够，后面的请求也别排了

        # 分配
        self.kv_cache_manager.allocate(req, num_cached_blocks, new_blocks)

        if req.num_computed_tokens == 0:
            scheduled_new.append(req)  # 第一次入场
        else:
            scheduled_cached.append(req)  # 被抢占后续跑

        req.num_computed_tokens += num_this_step
        if req.num_computed_tokens >= req.num_prompt_tokens:
            # Prefill 完了，移入 RUNNING
            self.waiting.popleft()
            self.running.append(req)
            req.status = RequestStatus.RUNNING

        token_budget -= num_new_compute  # 只扣"真的算了"的那部分
        num_seqs_budget -= 1 if req.status == RequestStatus.RUNNING else 0

几个关键点：

(1) 预算只扣”真的算了”的 Token 数。如果一个请求的前 256 个 Token 命中了前缀缓存，即使本步分给它的 num_this_step = 512，实际只有 256 Token 要进 GPU，token_budget 只扣 256。这是前缀缓存对调度的直接影响——命中率高的场景，单步能塞进更多请求。

(2) Chunked 切分由 max_chunk_size 控制。这个值默认等于 max_num_batched_tokens，也可以单独设置。它决定”一个长 prompt 最多一拍切多少”。设大了单步延迟尖峰大；设小了长 prompt 要跨很多拍才能 Prefill 完。

(3) 退出条件是保守的。一旦 free_blocks < new_blocks，整个 WAITING 扫描就退出——即使后面的请求可能小到足够 fit。这看起来次优，但 V1 的设计原则是”不因后面的请求调过前面的请求”，避免打破 FCFS 公平性。换句话说：调度的一个朴素正确性约束是不要出现”插队”。

3.3.4 阶段四：打包 SchedulerOutput

最后把三部分拼到一起：

def _make_output(self, running, new, cached_prefill) -> SchedulerOutput:
    num_scheduled_tokens = {}
    num_scheduled_tokens.update({r.request_id: 1 for r in running})
    # new 和 cached_prefill 里的 num_tokens 已经在 _schedule_waiting 里记下
    num_scheduled_tokens.update({r.request_id: r._this_step_tokens for r in new + cached_prefill})

    return SchedulerOutput(
        num_scheduled_tokens=num_scheduled_tokens,
        total_num_scheduled_tokens=sum(num_scheduled_tokens.values()),
        scheduled_new_reqs=[self._make_new_req_data(r) for r in new],
        scheduled_cached_reqs=[self._make_cached_req_data(r) for r in cached_prefill + running],
        finished_req_ids=self.finished_this_step,
        preempted_req_ids=self.preempted_this_step,
        ...
    )

这个 dict 就是交给 Executor 的全部指令。至此调度的一拍结束。

3.4 Chunked Prefill：把长 prompt 切开

Chunked Prefill 是 V1 的默认行为。它的动因不是”节省算力”——把 500 个 Token 的 Prefill 拆成 4×128 + 1×(128-12) 并不会减少总 FLOPs，反而略增（额外的 kernel 启动开销）。真正的动因是避免长 prompt 阻塞 Decode。

考虑一个场景：10 个 Decode 请求正在稳定跑（每步 1 Token），这时候来了个超长 prompt（8192 Token）。如果我们一次 Prefill 完它，这一拍的 GPU 时间可能是 200ms——10 个 Decode 请求要干等 200ms 再出下一个 Token，TPOT 从正常的 50ms 突刺到 200ms，用户感知到明显卡顿。

Chunked Prefill 的解法：把 8192 切成 8 拍 × 1024 Token，每拍 25ms。10 个 Decode 请求穿插进去：

gantt
    title 不启用 Chunked Prefill
    dateFormat X
    axisFormat %Lms

    section GPU
    Prefill 8192 tokens   :p1, 0, 200
    Decode 10 reqs        :d1, 200, 250

    section TPOT 感知
    10 decode 请求等待    :crit, w1, 0, 200

gantt
    title 启用 Chunked Prefill (chunk=1024)
    dateFormat X
    axisFormat %Lms

    section GPU
    P1 + 10 Decodes :p1, 0, 28
    P2 + 10 Decodes :p2, 28, 56
    P3 + 10 Decodes :p3, 56, 84
    P4 + 10 Decodes :p4, 84, 112
    P5 + 10 Decodes :p5, 112, 140
    P6 + 10 Decodes :p6, 140, 168
    P7 + 10 Decodes :p7, 168, 196
    P8 + 10 Decodes :p8, 196, 224

    section TPOT 感知
    smooth 25ms/token :smooth, 0, 224

代价：

1. 总墙钟时间略长（224ms vs 250ms 其实差不多，因为 Prefill 本来就是 compute-bound，和 Decode 一起跑两个都拿不到峰值算力；但多了 7 次 kernel 启动开销，约 1-2ms）。
2. 长 prompt 的 TTFT 稍微增加（第一个 Token 要到 Chunk 完全跑完才出）。
3. 调度逻辑复杂度上升——需要跟踪 num_computed_tokens。

收益：

1. Decode 的 TPOT 抖动从 ±200ms 压到 ±3ms 级别。
2. 系统的 p99 TPOT 与平均 TPOT 几乎重合（很重要的服务质量指标）。
3. 长 prompt 不再”霸占”整个引擎。

V1 把 Chunked Prefill 从 V0 时代的”opt-in 优化”升级为默认启用——因为几乎所有在线服务都应该用它。只有纯离线批处理（用户完全不关心 TPOT 抖动）才值得关掉。

3.5 前缀缓存对调度的影响

前缀缓存（Prefix Caching）是 vLLM 的另一个关键优化——相同 prompt 前缀的 KV Cache 块可以在请求间共享。具体机制在第 10 章详讲，这里只关注它对调度器行为的影响。

假设一个长对话的系统提示词是 1500 Token，用户发来的新消息前面这 1500 Token 每次都一样。第一个请求来的时候，调度器给它完整的 Prefill 预算；第二个请求来的时候，前缀缓存命中 1500 Token，实际只需要算用户消息那部分（比如 50 Token）。

对调度器意味着什么？

(1) num_computed_tokens 初始值不是 0。命中前缀缓存后，num_computed_tokens 被初始化为命中的 Token 数，调度器在后续 Prefill 时只看剩余部分。

(2) token_budget 消费是基于”真的算了多少”。如果本步给一个请求分配了 512 token 预算，但前 256 都命中缓存，实际 budget 只扣 256——剩下的 256 预算可以给别的请求用。这直接提升了单步吞吐。

(3) KV 块分配更轻量。命中的部分不需要新分配块（refcount+1 即可），只有没命中的部分要分配新块。这在 KV 池紧张时极其宝贵——命中率 90% 的场景，抢占频率降到 1/10。

graph TB
    subgraph "不命中缓存"
        A1[prompt: 1550 tokens] --> A2[分配: 97 blocks<br/>9700 token FLOPs]
        A2 --> A3[token_budget 扣 1550]
    end

    subgraph "命中 1500 tokens"
        B1[prompt: 1550 tokens] --> B2[分配: 4 new blocks<br/>+ refcount 93 blocks<br/>500 token FLOPs]
        B2 --> B3[token_budget 扣 50]
    end

    style A2 fill:#ef4444,color:#fff,stroke:none
    style B2 fill:#10b981,color:#fff,stroke:none

生产环境里，前缀缓存命中率是个重要的”便宜指标”——同一个 API Key 的连续请求、RAG 场景拼接的固定系统提示、编程助手里反复的工具定义——命中率上 70% 是常态。调度器会被这个命中率直接放大吞吐。

3.6 抢占（Preemption）：显存告急时的取舍

当 KV 池满了、新请求又来了，调度器必须抉择：放弃新请求？还是抢一些正在跑的请求？

V1 的策略是抢占。在 schedule() 主函数内联处理（vllm/v1/core/sched/scheduler.py line 221–237）：

# 当一个 RUNNING 请求申请不到 KV slot 时
new_blocks = self.kv_cache_manager.allocate_slots(
    request, num_new_tokens,
    num_lookahead_tokens=self.num_lookahead_tokens)
if new_blocks is None:
    # 抢占 running 队尾（最年轻）的请求
    preempted_req = self.running.pop()
    self.kv_cache_manager.free(preempted_req)
    preempted_req.status = RequestStatus.PREEMPTED
    preempted_req.num_computed_tokens = 0    # ← 关键：清零
    self.waiting.appendleft(preempted_req)   # 插回 WAITING 队首

这里有个容易误读的细节：num_computed_tokens 被清零，不是保留。所以字面意义上 V1 的抢占就是经典的 RECOMPUTE——被抢者下次入场要从 0 开始。那它凭什么比 V0 的 RECOMPUTE 成本低？

答案藏在重新入场那段代码（line 323–326）：被抢者回到 WAITING 队列后，下一次被 _schedule_waiting 取出时，第一步就是查前缀缓存：

computed_blocks, num_computed_tokens = \
    self.kv_cache_manager.get_computed_blocks(request)

如果该请求的 KV 块没被别的请求挤掉（通常被抢占后几秒内、前缀缓存 LRU 还没淘汰它），get_computed_blocks 会把 num_computed_tokens 重新填回到抢占前的值——对外表现就像”从断点续跑”，但架构上没有任何”保存断点”的专用机制。

这个设计把”抢占恢复”的责任完全外包给了前缀缓存：调度器本身无状态、抢占恢复不走特殊代码路径、KV 复用天然兜底。V0 时代需要维护 SWAP 缓冲、RECOMPUTE 特判两套分支，V1 用”num_computed_tokens=0 + 查前缀缓存”就涵盖了所有场景。这也是为什么 V1 敢砍掉 SWAP：当前缀缓存本来就要做、且命中率高时，SWAP 的那点 I/O 省略收益抵不过它带来的代码复杂度。

前缀缓存失效的情形——被抢者等的时间长、或者期间其他请求把它的 block 挤掉了——那就真的要从 0 重算。这时候 Chunked Prefill 发挥第二重作用：重算也是分块进行，不会在单拍里制造长尖峰。

stateDiagram-v2
    [*] --> WAITING
    WAITING --> RUNNING: schedule → 分配 KV
    RUNNING --> RUNNING: decode 1 token
    RUNNING --> WAITING: 被抢占 / KV 不足
    RUNNING --> FINISHED: stop / max_tokens / abort
    WAITING --> FINISHED: abort
    FINISHED --> [*]

    note right of WAITING
        num_computed_tokens 保留
        下次续跑
    end note

何时触发抢占？在 _schedule_running 阶段，如果一个 RUNNING 请求需要新 KV 块但池子空了——抢它。抢占策略的选择是”抢最年轻的”：self.running.pop()——从队尾（最新进 RUNNING 的）开始。这是基于”最年轻的请求投入最少”的推理：它生成的 Token 最少，被迫重走 Prefill 的浪费最小。

抢占的观测：Prometheus 指标 vllm_preempted_requests_total 是排查”为什么吞吐不稳”的第一信号。正常流量下它应该一段时间内平坦；如果它稳步上涨，说明 KV 池不够，要么加 GPU、要么降 max_num_seqs、要么压低 max_model_len。

3.7 update_from_output：一拍结束后的状态迁移

调度完 → 执行完 → Scheduler 还要收尾。这个收尾就是 update_from_output：

def update_from_output(
    self,
    scheduler_output: SchedulerOutput,
    model_output: ModelRunnerOutput,
) -> list[EngineCoreOutput]:
    engine_core_outputs = []
    for req_id, new_token_ids in model_output.sampled_token_ids.items():
        req = self.requests[req_id]

        # 1. 把新 token 追加到请求的 output list
        req.output_token_ids.extend(new_token_ids)
        req.num_computed_tokens += len(new_token_ids)

        # 2. 检查停止条件
        stop_reason = self._check_stop(req, new_token_ids)
        if stop_reason is not None:
            req.status = RequestStatus.FINISHED
            self.running.remove(req)
            self.kv_cache_manager.free(req)
            self.finished_this_step.add(req_id)

        # 3. 打包输出
        engine_core_outputs.append(EngineCoreOutput(
            request_id=req_id,
            new_token_ids=new_token_ids,
            finish_reason=stop_reason,
            stop_reason=req.sampling_params.stop_matched(new_token_ids),
            logprobs=model_output.logprobs.get(req_id),
        ))
    return engine_core_outputs

有两个设计点值得注意。

停止检查在下一拍开始前才完成。看上面伪代码，检查 stop 是在 update_from_output 里，也就是”本拍结束、下拍开始”的那一刻。但 V1 的异步流水线里，下一拍的 schedule() 可能已经在跑（CPU 在预测下一拍，GPU 在执行本拍）。这意味着：一个刚命中 stop 的请求，在发现 stop 之前可能已经被下一拍的 _schedule_running 安排了一个 decode 任务。这就是第 2 章提到的”overshoot 一个 token”——被浪费的那个 token 是这个异步流水线的必要代价。

GPU 拿回结果才做任何状态迁移。你可能以为 Scheduler 在 schedule() 里就应该”预测”某个请求会 stop，提前把它从 running 移除。V1 明确不这么做——所有状态迁移都基于”真的算完了什么”，避免推测性分支带来的一致性陷阱。简单、可预测、bug 更少。

3.8 策略细节：公平性、优先级、延迟因子

V1 Scheduler 除了 FCFS，还支持几个高级策略：

3.8.1 Priority（优先级）

通过 SamplingParams.priority 给请求加一个整数优先级。Scheduler 在 _schedule_waiting 里不是弹出队首，而是从 WAITING 队列里挑优先级最高的：

def _schedule_waiting(self, ...):
    # 原本：req = self.waiting[0]
    # 高优先级模式：req = max(self.waiting, key=lambda r: r.priority)

用途：服务内不同租户的请求用不同 priority；或者把”付费用户”的请求放 priority=1、“免费用户”放 priority=0。

3.8.2 LoRA 亲和性

max_loras 参数限制一拍里能用的 LoRA 适配器数量——因为每个 LoRA 都要占一份显存，同时使用太多会 OOM。Scheduler 在 _schedule_waiting 里会检查：如果加入这个请求会导致本拍 LoRA 数超过 max_loras，先跳过它。后续章节会详讲。

3.8.3 Delay Factor（少用）

delay_factor > 0 时，Scheduler 会在一拍里推迟新请求的入场：即使 token_budget 还有空，也不立刻让 WAITING 请求进来。这是一个给低延迟偏好场景的参数——让 running 请求先尽量多出几个 token，再处理新请求。生产中很少启用，因为绝大多数场景对新请求的 TTFT 也很敏感，不值得为 decode 的 TPOT 把 TTFT 推高。

3.8.4 long_prefill_token_threshold：对长 prompt 的二次节流

max_num_batched_tokens 决定的是”一拍的总预算”，并不限制单个请求能独占多大预算。当流量里混入一个 32K 的超长 prompt、而 max_num_batched_tokens=8192，那这一拍实际上就只服务这一个长请求了——其他 decode 请求全被挤掉。

SchedulerConfig.long_prefill_token_threshold 是 V1 为此加的第二重节流：给单个请求在单拍能吃的 Token 数再设一个上限。源码里两处都用到了它（scheduler.py line 181–184 和 342–345）：

if (0 < self.scheduler_config.long_prefill_token_threshold <
        num_new_tokens):
    num_new_tokens = (
        self.scheduler_config.long_prefill_token_threshold)

典型用法：max_num_batched_tokens=8192 + long_prefill_token_threshold=2048——这样任何一个请求每拍最多吃 2048 个 token 的 Prefill 预算，剩下 6144 必然被分配给其他请求（含 decode）。在线服务场景下这是保护 TPOT 稳定的第三重闸门（第一重是 Chunked Prefill、第二重是 prefill/decode 同拍混合、第三重是本参数）。

3.8.5 KVConnector：外挂 KV 缓存与 PD 分离部署

schedule() 里有一段容易被忽视的代码（line 328–335）：

num_external_tokens = (
    0 if self.connector is None else
    self.connector.get_num_new_matched_tokens(
        request, num_computed_tokens))
num_computed_tokens += num_external_tokens

KVConnector 是 V1 在 2025 年引入的扩展点，用于接外部 KV 缓存源——包括：

1. LMCache / MoonCake 等 NVMe 下沉：把冷的 KV 存到 NVMe SSD，热请求回来时从外部 store 拉回显存，避免重算。
2. PD Disaggregation（Prefill-Decode 分离）：prefill 节点做完 KV 后推给 decode 节点，两类节点异构部署。DistServe (OSDI ‘24)、MoonCake (MLSys ‘25) 两篇论文讨论的正是这个架构。
3. 跨节点 KV 复用：多机集群内共享前缀缓存。

对调度器而言，外部命中的 Token 和本地前缀缓存命中是等价的——都记入 num_computed_tokens 并按”不消耗 budget”处理。这种统一抽象让调度器代码不需要为 PD 分离写特殊分支，但对底层 get_num_new_matched_tokens 实现提出了要求：必须能快速（一般几百微秒内）判断远端命中情况，否则会阻塞调度拍频。

3.8.6 Cascade Attention 与共同前缀检测

schedule() 末尾（line 432–439）还有一段：

num_common_prefix_blocks = 0
if self.running:
    any_request = self.running[0]
    num_common_prefix_blocks = (
        self.kv_cache_manager.get_num_common_prefix_blocks(
            any_request, len(self.running)))

它计算 RUNNING 队列里所有请求共同前缀的块数，把这个数字附在 SchedulerOutput 上。底层 attention kernel 拿到后可以启用 Cascade Attention：共同前缀的 KV 只读一次，每个请求独有的尾段 KV 各读各的。在多用户共享系统提示词的场景（RAG、Agent），共同前缀往往是几千 token，Cascade Attention 能把这部分 memory-bound 的读取从 N 份请求 × 前缀长度压到 1 份前缀 + N 份尾段，decode 阶段带宽利用效率显著提升。

3.9 观测调度器：看懂 SchedulerStats

一个健康的生产 vLLM 引擎，调度器的指标应该是什么样的？

vllm_num_requests_running          稳定在 max_num_seqs 的 70-90%
vllm_num_requests_waiting          大部分时间 = 0，突发流量时短暂 > 0
vllm_kv_cache_usage_ratio          稳定在 40-80%
vllm_prompt_tokens_per_step        大 prompt 到达时高、decode 时低（抖动正常）
vllm_generation_tokens_per_step    ≈ num_requests_running（decode 一拍一个）
vllm_preempted_requests_total      长期平坦
vllm_prefix_cache_hit_ratio        RAG / 多轮场景 > 60%

不健康的信号：

• kv_cache_usage_ratio 持续 > 95% + preempted_requests_total 持续上涨 → KV 池饥饿，需要降 max_num_seqs 或加卡
• num_requests_waiting 长期 > 0 + num_requests_running == max_num_seqs → 吞吐被 max_num_seqs 卡住，可以尝试调大
• num_requests_waiting 长期 > 0 + kv_cache_usage_ratio 持续 < 50% → 奇怪，可能有 request leak，去看 abort 记录
• prompt_tokens_per_step 长期 = 0 → Prefill 队列空，但 num_requests_waiting > 0 → 可能有 LoRA 冲突或 priority 饿死

V1 的 SchedulerStats 每一步都产出，通过 EngineCore → API Server → Prometheus 的链路暴露。这些指标是生产调优的”仪表盘”——所有性能问题的第一线索都在这儿。

3.9.1 实测：Scheduler 是 1301 行的引擎、schedule() 是 374 行的主方法

把整个 V1 调度器子系统按文件实测——

文件	行	角色
vllm/v1/core/sched/scheduler.py	841	本章主角——Scheduler 类全部实现
vllm/v1/request.py	178	Request 数据类 + RequestStatus 枚举（FCFS / WAITING / RUNNING / FINISHED 等）
vllm/v1/core/sched/interface.py	134	SchedulerInterface ABC——给 V0/V1 双调度器的统一接口
vllm/v1/core/sched/output.py	126	3 个 dataclass：NewRequestData (line 20) + CachedRequestData (line 53) + SchedulerOutput (line 82)
vllm/v1/core/sched/utils.py	22	小工具
__init__.py	0	—
合计	1301	—

scheduler.py 内部方法分布（13 个 method）——

方法	起始行	估算行数	角色
schedule()	137	374	本章 §3.3 主角——三阶段编排：预算编列 → RUNNING 续行 → WAITING 入场 → 打包
update_from_output()	625	~130	本章 §3.7 主角——拿到 GPU 结果后状态迁移
_make_cached_request_data()	511	~30	helper
_try_schedule_encoder_inputs()	542	~80	encoder cache 试调度
add_request / finish_requests / _free_request / get_num_unfinished_requests / has_finished_requests / reset_prefix_cache / make_stats / make_spec_decoding_stats	759-840	余下	API 入口 + 统计

两条值得记住的物理事实——

1. schedule() 单方法 374 行 = 整个 scheduler.py 44%——是本子系统最大的单方法——本章 §3.3.1-3.3.4 拆出”四阶段”在源码里就是这 374 行的内部分段——印证 §3.2 标题”统一 Token 调度”——所有调度逻辑塞在一个方法里、不切成 _schedule_running / _schedule_waiting 几个子方法（V0 有这种切分、参见 ch11 §11.10.1 测得的 V0 _schedule_chunked_prefill 方法分散）——单方法包揽是为了避免子方法之间的 budget/state 同步
2. 整个 V1 调度器 1301 行 vs ch11 §11.10.1 实测 V0 scheduler.py 单文件 2060 行——少 37%——加上 V0 chunked_prefill_paged_decode.py 366 行 = 2426 行——V1 用 1301 行做了 V0 ~2426 行的事情、再加上原生支持的 prefill+decode 混合——印证 §3.2 “范式转移” 不是宣传词、是 -46% 代码量的实测

SchedulerOutput 仅 3 个 dataclass、126 行——是 §3.3.4 “打包”环节的全部数据契约——印证 vllm 在 ch01 §1.5 “四类跨边界 DTO” 设计纪律：调度器和 worker 之间的协议表面极薄（126 行），背后调度逻辑很厚（schedule() 374 行）。

串联 ch04 §4.9.1 v1/attention/ 3115 + ch05 §5.9.1 v1/core/ KV 子系统 1886 + 本节 sched/ 1301 + ch11 §11.10.1 V1 chunked prefill 14 行 + ch12 §12.8.1 v1/spec_decode/ 692 = ~7000 行 V1 调度+注意力+KV+优化的核心引擎——是 vllm V1 “memory-bound 推理优化” 的最小完整子集。

3.10 本章小结

调度器是 vLLM 性能优化的核心战场。一次好的调度决策能让 GPU 吃饱、让 decode 请求 TPOT 平稳、让长 prompt 不打断别人。V1 的核心设计：

• 统一 Token 调度——消除 Prefill / Decode 的代码路径差异，用 {req_id: num_tokens} 统一描述调度决策
• 三阶段 schedule()——预算编列 → 续行 RUNNING（每人 1 token）→ WAITING 入场（按 budget 吃 Prefill）→ 打包 SchedulerOutput
• 两个核心旋钮——max_num_batched_tokens 控制每拍 GPU kernel 规模，max_num_seqs 控制并发 KV 占用
• Chunked Prefill 默认开启——长 prompt 不再霸占引擎，Decode TPOT 抖动被压到 ±3ms 级别
• 前缀缓存直接提升 budget——命中的 token 不计入本拍预算，单步吞吐被命中率放大
• 抢占只做 RECOMPUTE——V1 砍掉 SWAP，配合前缀缓存把重算代价最小化；抢占最年轻的 RUNNING 请求
• 状态迁移基于真实结果——update_from_output 拿到 GPU 结果再决定 stop；stop 检查”晚一拍”是异步流水线的合理代价
• SchedulerStats——生产调优的仪表盘，kv_cache_usage / preempted_total / prefix_hit_ratio 是三个必看指标

物理事实：V1 sched/ 子系统 1301 行 vs V0 scheduler.py 单文件 2060 + chunked_prefill_paged_decode 366 = 2426 行——V1 用 -46% 代码量做了 V0 同等事情还原生支持 prefill+decode 混合；schedule() 单方法 374 行占 scheduler.py 44%——单方法包揽是为避免子方法间 budget/state 同步；SchedulerOutput 仅 126 行 3 dataclass 印证 ch01 §1.5’四类 DTO’数据契约表面薄、调度逻辑厚的纪律。

---

源码导航

• V1 Scheduler 主类：vllm/v1/core/sched/scheduler.py
• SchedulerOutput 定义：vllm/v1/core/sched/output.py
• Request 状态枚举：vllm/v1/request.py（RequestStatus）
• 预算与配置：vllm/config.py（SchedulerConfig）
• KV 分配配合点：vllm/v1/core/kv_cache_manager.py
• Metric 定义：vllm/v1/metrics/stats.py
• V0 Scheduler（历史对照）：vllm/core/scheduler.py