Month 3 · 调度器与 Continuous Batching
这是把"显存优化"变成"吞吐优化"的关键一步。
Month 2 学完后你已经知道显存怎么省。但 GPU 算力本身怎么榨干？ 传统做法 batching 是 "等到 32 个请求凑齐再一起跑"——延迟高、长短不一时浪费。 Orca 和 vLLM 的答案叫 continuous batching：每一步都重组 batch。 这一节学这套机制。
驱动问题
100 个请求同时进来，prompt 长度在 10-2000 之间随机，期望输出 50-500 token 随机。
你只有一张 A100。怎么 batch 它们能让总吞吐最高？
三种朴素策略 + 它们的问题
策略 A · 静态 batching：等 32 个请求齐了，一起 forward 直到全部结束。
问题：先做完的请求要等最慢的（trailing decode 浪费算力）；新请求要等下一 batch（高 TTFT）。
策略 B · 一个一个跑：每个请求独占 GPU 跑完。
问题：GPU 利用率极低，prefill 算力浪费严重。
策略 C · 动态 batching（continuous batching）：每个 token step 都重新决定 batch 成员。
新请求随时插入、完成的随时退出、显存不够时挤掉低优先级的。
问题：复杂、需要 scheduler 配合内存管理。但这是 vLLM 选的路。
01前置：prefill vs decode
LLM 推理分两阶段，节奏天差地别。读 scheduler 前必须先理解这个：
| Prefill | Decode | |
|---|---|---|
| 触发 | 请求刚到，处理 prompt | 已开始生成，每出一个 token 一步 |
| 输入长度 | 整个 prompt（100-10000 tokens） | 1 个 token（上次的输出） |
| 瓶颈 | compute-bound（FLOPs 多） | memory-bound（搬 KV 多于算） |
| 耗时 | 几十 ms ~ 几秒 | 几 ms 一步，连续做几百步 |
| 显存增量 | 分配 N 个 KV block | 每 16 tokens 加 1 个 block |
把两类混 batch 的核心问题：prefill 一来，整个 batch 的 decode 速度被拖慢—— 你为了照顾一个"重活"，让 31 个"轻活"也卡住。 这就是 Sarathi-Serve 论文要解的（chunked prefill）。
02Continuous Batching · 直觉图
朴素 batching 必须等齐再切换；continuous batching 每步动态重组，请求随到随插。
"每步重组 batch" 听起来简单，难在每一步要同时回答 4 个问题：
- 这一步谁参与？(scheduler)
- 每个参与者要算 prefill 还是 decode？要算多少 token？(scheduler)
- 能不能腾出显存？要不要抢占别人？(scheduler + block manager)
- 怎么把异构请求打包给 kernel？(model runner + attention)
03OS 调度器：你已经会的部分
OS 进程调度跟这里结构上同构，但具体策略 vLLM 选了不同的解。
| 问题 | OS 解法 | vLLM 解法 |
|---|---|---|
| 谁先跑 | MLFQ / CFS：按 vruntime 公平排 | FCFS（先来先服务）+ priority |
| 跑多久 | time slice (~10ms) | 1 个 token step |
| 切换代价 | context switch ~µs | 0（每 step 都重排） |
| 满了怎么办 | swap-out 整个进程 | preempt + recompute 或 swap-out KV blocks |
| 饥饿 | aging（等久了优先级上升） | FIFO 天然不饿 |
| 实时 | RT scheduling class | (暂无强保证，靠 priority hint) |
关键差别：
- OS 调度器要在 µs 级别决策（每秒上千次）；vLLM 在 ms 级（每 token step 一次）。所以 vLLM 可以承受更复杂的算法。
- OS 切换代价高，所以倾向长 time slice + 公平；vLLM 切换代价 ≈ 0，所以可以每步都重排。
- vLLM 不能用 CFS 那种公平模型，因为 LLM 请求长度差异极大（10 vs 2000 token），公平等于浪费。FCFS + admission control 才合理。
面试常问
"vLLM 的 scheduler 为什么不用 CFS？" 用上面的差别表答，能讲出"切换代价 + 请求长度方差"两点就过关。
04vLLM scheduler 的状态机
每次 schedule() 决定状态迁移。preempt 是 vLLM 区别于 OS 的核心动作之一。
Preemption 两种实现
- Recompute：丢弃被抢者的 KV，把它放回 waiting 队列。下次轮到时重新 prefill。
优点：实现简单、显存彻底释放。
缺点：浪费 prefill 算力（如果它已经生成了 100 个 token，全废）。
适合：短请求。 - Swap-out：把被抢者的 KV blocks 拷到 CPU host RAM 暂存。下次调入时拷回来继续 decode。
优点：不重算。
缺点：PCIe 拷贝有时延（GB 级），swap 池要预留 host 内存。
适合：长请求、显存压力是阵发的。
vLLM 默认 recompute（更简单），但有 swap 选项。选哪个 = 工程 trade-off，论文里讨论过。
05读源码 · scheduler
读 ① · 2-3 小时 · 主体
V1 scheduler 主体。重点看 schedule() 方法。不要试图一次看懂全部——先看顶层流程：
- 遍历 waiting → 试图招进 running
- 遍历 running → 看每个的 KV 是否够
- 放不下时选谁 preempt
这一步的 "token budget" 是怎么算的？它限制了什么？
读 ② · 1 小时 · 输出结构
同上 ·
scheduler 不直接调 model；它返回一个计划。看这个 dataclass 有哪些字段，每个对应 worker 端做什么。
SchedulerOutput dataclass如果我想加一个新的调度策略，最少要改这个文件的哪几个函数？
读 ③ · 1 小时 · Chunked prefill
同上文件，搜
vLLM 支持 Sarathi-Serve 风格的 chunked prefill：把一个大 prefill 切成若干小段，跟 decode 混在同一个 step 里。
chunked_prefill 或 num_computed_tokens为什么这能解决"prefill 拖慢 decode" 的问题？
读 ④ · 30 分钟 · Preemption
搜
抢占的具体动作。看它如何决定抢谁（通常是 running 队列尾部，最年轻的）。
_preempt 或 preempted_reqs为什么不抢"剩余 token 数最大"的那个？("惩罚已投入"是个反模式，但有时也是对的)
06动手 · 写一个 mini scheduler
本月最重的作业。不要在真 GPU 上——用假数据跑通逻辑。
规格
- 纯 Python，单文件 < 300 行。
- 模拟 100 个请求随机到达、prompt 10-500、output 50-500。
- 实现：FCFS + token budget + recompute preempt。
- 跑完输出：throughput、avg TTFT、avg latency。
# 伪代码骨架
class Request:
id: int
prompt_len: int
output_len: int
generated: int = 0
state: Literal["WAITING", "RUNNING", "FINISHED", "PREEMPTED"]
arrival_time: float
first_token_time: float | None = None
class Scheduler:
def __init__(self, kv_capacity_blocks=1000, block_size=16):
self.waiting = deque()
self.running = []
self.kv_free = kv_capacity_blocks
def step(self, now) -> List[Request]:
# 1) admit from waiting
# 2) for each running, see if needs new KV block
# 3) preempt if full
# 4) return batch for "execution"
...
# main loop
sched = Scheduler()
for t in range(0, 10000): # 10000 ms simulation
for r in arrivals_at(t): sched.waiting.append(r)
batch = sched.step(t)
for r in batch:
r.generated += 1
if r.generated == r.output_len:
r.state = "FINISHED"
# log metrics
✓ 评估你的 mini scheduler
跑完应该能回答：
- 把
kv_capacity减一半，throughput 掉多少？preempt 次数升多少？ - 把 token budget 加倍，TTFT 怎么变？(batch 变大、TTFT 升、throughput 也升)
- 给 prompt 长度方差加大，平均延迟怎么变？
07本月 PR 候选
- 给 scheduler 加一个 metric：每 step 的 batch size 分布、preempt 次数、token throughput。
- 修一个 preemption 边界 bug（比如"被抢的请求重新调入时，prefix cache 没复用"——这类 issue 历史上有过）。
- 实现一个新的 priority 算法（比如"按剩余 token 数排"）作为实验性选项。
- 给 chunked prefill 写一个新测试覆盖某 corner case。
💡 找 issue 的诀窍
vLLM 的 RFC / proposal issue 里经常埋着 "scheduler 应该 X 但还没做"——
搜 label:scheduler + 按 oldest 排序，前几页通常有真东西。