调度器
每一步调度器都要决定哪些请求能跑。公平性、延迟 SLO、显存不足后的恢复策略，都在这里。
- 等待/运行队列
- token 预算
- 抢占
- 换出 vs 重算
- 准入控制
为什么重要
问题
S09 结尾出现了 while self.can_admit()，一个我们从没写过的函数。它必须每秒回答几百次这样的问题：
- 这一步应该运行多少个请求？
- 该不该启动一个新的 8000 token prefill，还是把整步都留给已经在流式输出的四十个请求？
- KV block 用光了，而一个运行中的请求还要再来一块。谁该失去自己的缓存？
- 有个请求已经卡在一个长 prompt 后面排了九秒。这可以接受吗？
这些问题没有放之四海皆准的答案，你能拿出的只是一套策略；而这套策略就是你的引擎对外可见的行为。
核心思路
解法
一个带两个队列、两种预算和一条抢占路径的调度器。结构短到可以完整读完：
def schedule(self) -> Batch:
budget = self.max_num_batched_tokens
scheduled = []
# --- 1. running decodes first: a started request should finish ---
for req in self.running:
if budget < 1:
break
if not self.blocks.can_append(req):
victim = self.pick_victim() # last admitted, usually
self.preempt(victim)
if victim is req:
continue
self.blocks.append(req)
scheduled.append(req)
budget -= 1
# --- 2. spend what is left admitting new prefills ---------------
while self.waiting and budget > 0:
req = self.waiting[0]
if req.prompt_len > budget:
break # cannot fit this step
if not self.blocks.can_allocate(req, watermark=0.01):
break # keep headroom for growth
self.waiting.popleft()
self.blocks.allocate(req)
scheduled.append(req)
budget -= req.prompt_len
return Batch(scheduled)「decode 优先」不是随便定的
工作原理
工作原理
两种预算是两种不同的约束
- token 预算（
max_num_batched_tokens）限制每步的算力。它给一次前向的耗时设了上限，也就给 batch 中所有人的 token 间延迟设了上限。 - 显存水位线限制 KV block。一直准入到池子 100% 占满，必然死锁：每个运行中的请求最终都还要再来一块，而一块都没有了。真实引擎会留出百分之几的余量。
调高 token 预算，吞吐变好、每步延迟变差；调低则相反。不存在对两者都最优的设置；这正是 SLO 的意义所在。
抢占：重算还是换出
显存耗尽时，某个运行中的请求必须交出它的缓存。把它取回来有两条路，两者的交叉点很清晰：
- 重算 —— 扔掉 KV，等它被重新调度时把整个请求重新 prefill 一遍。代价是
(prompt + 已生成)个 token 的 prefill：受算力限制，也相当快。 - 换出 —— 把 KV block 拷到主机内存再拷回来。代价是缓存大小的两倍经由 PCIe：字节很多，算术为零。
短上下文下，重算轻松取胜。极长上下文下 prefill 成本上升，换出开始有竞争力。vLLM 默认重算；有了分块和前缀缓存之后，prefill 已经便宜了很多。
公平性，以及纯 FCFS 的问题
严格先到先服务简单、且不会饿死任何人，但它有一个糟糕的失效模式：队首阻塞。队首那个 32000 token 的 prompt 在整份预算腾出来之前无法被调度，而在它等待期间，它后面的一切也都不动。
短 prompt 优先能改善小请求的尾延迟，却会饿死大请求。优先级队列让你能表达业务规则，也逼你必须先有业务规则。调度策略属于运维者，所以把它做成可插拔的，并且同时测量 P50 和 P99。一个改善均值却毁掉尾部的策略，在仪表盘上很好看，在用户那里很难受。
动手观察
动手试试
- 已完成
- 0/20
- 平均 TTFT
- 0.0 步
- p95 TTFT
- 0 步
- 抢占次数
- 0
- r11873 prompt
- r12140 prompt
- r171324 prompt
- r681 prompt
- r1464 prompt
- r11114 prompt
- r1669 prompt
- r131109 prompt
- r18194 prompt
- r01461 prompt
- r19146 prompt
- r8182 prompt
- r10929 prompt
- r15219 prompt
- r3136 prompt
- r7156 prompt
- r980 prompt
- r244 prompt
- r493 prompt
- r5228 prompt
比 token 预算还长的 prompt 永远排不上，只会被无限饿死。把预算降到 128，看着长 prompt 永久堆积。解决它的是 S11。
- 当前没有运行中的请求
decode 的调度优先于 prefill。已经开始的请求应该尽快结束，否则它的 KV 缓存一直占着，对其他所有人都更糟。
- 已用 block
- 0/180
- prefill token
- 0
- decode token
- 0
- 重算的 token
- 0
紫色尖峰是 prefill。一个长 prompt 就能吃掉整步预算，排在它后面的 decode 全部干等：对每个正在流式输出的用户，这都是一次看得见的延迟毛刺，也正是分块 prefill 要解决的问题。
三个实验，每一个都能复现一次真实的生产事故：
- 把 token 预算设成 128。长 prompt 永远无法被调度，只能一直排队，这就是永久饥饿；而引擎自始至终看起来都很健康。FCFS 队首那个排不上的请求还会挡住它后面的所有人，于是少数几个超长 prompt 就能拖住大部分流量。
- 把 KV 池缩到 60 个 block。抢占次数飙升，同样的 token 被反复重算，这就是抖动：吞吐塌陷，而 GPU 利用率显示 100%。
- 在持续负载下切到短 prompt 优先。中位数大幅改善，长 prompt 则差得多。如果队列有限且能排空，最短优先会全面胜出；只有当短请求源源不断地到来、可以不断插队时，饥饿才会出现。
亲手实现
实现
def preempt(self, req: Request):
"""Give a running request's KV memory back to the pool."""
self.blocks.free(req)
req.preemption_count += 1
if self.preemption_mode == "recompute":
# Cheapest for short contexts: forget everything, re-prefill later.
req.computed = 0
req.kv_blocks = []
else:
# Cheapest for long contexts: park the blocks in host memory.
req.swapped_blocks = self.blocks.swap_out(req)
self.waiting.appendleft(req) # front of the queue — do not restart it last被抢占的请求要插到队列的最前面
$ python code/s10_scheduler.py只需要 NumPy — 查看环境准备.
生产实践
在生产环境中
- vLLM ——
Scheduler.schedule()，带max_num_batched_tokens、max_num_seqs、GPU 水位线，以及默认使用重算的抢占。抢占率过高时它会打一条警告，那条警告就是你的抖动信号。 - SGLang —— 缓存感知调度，优先选择前缀已经驻留的请求，把 S07 的缓存变成了一个调度输入。
- Kubernetes 规模的部署 —— 在这个调度器之上还有第二层调度器，在副本之间路由请求，理想情况下是前缀感知的，以免轮询负载均衡把缓存命中全毁掉。
练习
- 1实现一个带老化的优先级队列：请求等得越久优先级越高，这样短优先也饿不死任何人。演示改造前后的饥饿情况。
- 2加一个 SLO 感知的准入控制器：当队列意味着 TTFT 会超过目标时，直接拒绝新请求。早点拒绝，通常是比先接受再超时更像样的服务。
- 3给抢占抖动加上度量：记录「重算 token 数 / 新生成 token 数」的比值，超过 20% 时触发背压信号。
继续学习
接下来
模拟器暴露了缺陷：一次长 prefill 吃掉整整一步，每个流式用户都感到卡顿。S11 把 prefill 切成小块，混进 decode 批次。尖峰因此消失，吞吐并不受损。
自测
习题
先作答，再看解析。答错比答对更有价值，因为解析会指出你该回头重读哪一部分。
调度器为什么要先跑完所有待处理的 decode，再准入任何新的 prefill？