人工智能:理论、算法与系统 · 第30课
Continuous Batching 与请求级调度:吞吐、延迟与 KV 资源
2026年11月18日|第5周第2课|讲授约18分钟(自测另计)
上一课推导了 Prefill、Decode 和 KV Cache。今天回答:为什么几个请求同时到达,输出长度却不同,传统静态 Batch 会让短请求浪费时间?为什么迭代级调度能提高资源利用率,却还必须处理 KV 容量、排队、公平和长 Prompt 对流式输出的干扰?
目标: 理解 Static / Continuous Batching 的区别;用时间线计算调度收益;推导计算 Token 预算与 KV Block 约束;使用 TTFT、TPOT、Little 定律和双 SLO Goodput 评价调度。
一、Static Batching 的问题不只是 Padding
设服务端一次最多处理3条请求,A/B/C 在时刻0到达,后续需要生成的 Token 数分别是3、5、2;D 在第二轮结束后到达,需生成2 Token。为了突出调度机制,假设每轮 GPU 时间恒为1个抽象时间单位、Prefill不耗时、生成可以逐 Token 返回;这不是现实 GPU 的时间模型。
请求级静态批处理: A/B/C 被绑定为一批,直到最长的 B 在第5轮结束后才允许 D 加入。D 需第6、7轮。整体完工时间为7轮。
迭代级连续批处理: C 在第2轮结束时释放槽位,D 可在第3轮开始加入;A 第3轮结束,D 第4轮结束,B 第5轮结束。整体完工时间为5轮。
| 轮次 | 静态批处理(不接纳 D) | 连续批处理(可接纳 D) |
|---|---|---|
| 1 | A / B / C | A / B / C |
| 2 | A / B / C(C结束) | A / B / C(C结束) |
| 3 | A / B / 空槽(A结束) | A / B / D(A结束) |
| 4 | 空槽 / B / 空槽 | B / D / 空槽(D结束) |
| 5 | 空槽 / B / 空槽(B结束) | B / 空槽 / 空槽(B结束) |
| 6–7 | D(两轮) | 已全部结束 |
关键不是“不同请求可以并行生成未来所有 Token”,而是每一轮结束,服务端都能重新选择本轮活跃请求,并立即释放已完成请求的资源。实际 GPU 每轮耗时随 Batch、Context、Prefill 而变,本例中的7→5不能作为实测加速比。
二、Iteration-level Scheduling 怎样运行?
flowchart TD
A["等待队列 W:新到达请求"] --> C["Iteration-level Scheduler"]
B["运行集合 R:当前 KV 状态"] --> C
C --> D{"Token预算 / 序列上限 / KV块是否可行"}
D -->|可行| E["组装本轮 Batch:Decode + Prefill Chunks"]
D -->|不可行| F["排队 / 缩小Chunk / 必要时抢占"]
E --> G["GPU执行本轮 Forward"]
G --> H["流式返回输出,更新KV"]
H --> I["EOS/结束:释放状态,其他请求继续"]
I --> C
F --> C
每一轮可以安排:已经完成 Prefill 的请求各 Decode 一个新 Token,尚未完成 Prompt 的请求做一个连续的 Prefill Chunk,刚刚完成的请求退出。对同一个请求,Prefill/Decode 的因果顺序仍必须正确。
为什么 Attention 不像普通 GEMM 那样简单拼大 Batch? 不同请求的上下文长度不同,历史 KV 对应不同的块表,注意力需要处理不等长序列;线性层则较容易把本轮 Token 拼接为矩阵。Orca(OSDI 2022)将这称作 Iteration-level Scheduling 和 Selective Batching;现代系统还有更复杂的不等长 Attention Kernel。
三、调度要同时满足三个不同资源约束
设第 k 轮已在运行的请求集合为 R,新接纳的 Prefill 请求集合为 W’。对 Decode 请求 i 设 x_i∈{0,1}(本轮是否处理一个新 Token);对 Prefill j 设 c_j≥0(本轮计算的连续 Prompt Token 数,且不能超过其剩余长度)。
本轮新计算 Token 预算:
[ \boxed{\sum_{i\in R}x_i+\sum_{j\in W’}c_j\le K_{\mathrm{step}}.} ]
运行请求数量上限:
[ \boxed{|R_{\mathrm{next}}|\le S_{\max}.} ]
KV Block 池容量: 假设一个 KV Block 对每个请求存 g 个 Token;一个请求在本轮结束后缓存历史+新增长度 T_i,则在不共享、不分片的简化模型下:
[ \boxed{\sum_{i\in R_{\mathrm{next}}} \left\lceil\frac{T_i}{g}\right\rceil \le B_{\mathrm{KV}}.} ]
这里 T_i 是已经累计缓存的长度,不是本轮新增的 Token 数。实际 PagedAttention 可能涉及共享块、不同层结构、预留策略和临时缓冲;这些要单独计入。
三条约束各不相同:K_step 限制一次迭代的计算工作量,S_max 限制并发序列数,B_KV 限制跨迭代常驻的 KV 状态。调大 Token Budget 不会凭空增加 HBM。 此外,每个新 Token 的计算成本也随历史长度变化,Token Budget 并不直接等价于相同的 GPU 运行时间。
四、Chunked Prefill:长 Prompt 怎样不打断 Decode?
例如每轮最多调度64个新计算 Token;已有8条 Decode 请求,每条本轮消耗1个 Token。另有长度为140、尚未处理的 Prompt,若先保证这8个 Decode,本轮最多可处理:
[ 64-8=56\quad\text{个 Prefill Token}. ]
同样条件下,140 个 Prompt Token 可以拆成56、56、28三个 Chunk,分别在三轮执行。每个 Chunk 必须正确接续先前 Prefill 的注意力状态;不能把三个块视为互不相关的 Prompt。
这种策略的直觉是:让流式 Decode 不必被一次非常长的 Prefill 独占 GPU,剩余资源用于处理新请求。但若总把 Decode 排在前面,新的长 Prompt 可能等待更久,TTFT 变差;Chunk 本身也有额外调度和 Kernel 开销。
Sarathi-Serve(OSDI 2024)系统研究了 Chunked Prefill 与 Stall-free Batching。vLLM V1 的公开优化文档描述了可用时默认启用 Chunked Prefill、优先安排 Decode 再利用剩余 Token Budget 安排 Prefill 的策略。具体调度规则依赖实现和版本,不应把某一版本的默认值写成永久结论。
五、队列论:为什么高吞吐不代表低延迟?
在稳定的在线系统,设平均请求到达率为 (\lambda)(req/s),平均系统逗留时间为 (W)(s,含排队和服务),系统内平均请求数为 (\bar L),Little 定律给出:
[ \boxed{\bar L=\lambda W.} ]
例如长期每秒完成4个请求、平均端到端耗时1.5秒,则平均系统内请求数为6。注意这是稳态均值关系,不是每个时刻恰好6个请求;它本身也不能预测服务端最大容量。
在额外假设“泊松到达、指数服务、单服务器、FCFS、到达率低于服务率”的 M/M/1 模型中:
[ \rho=\frac{\lambda}{\mu},\qquad \mathbb E[W]=\frac1{\mu-\lambda}. ]
若服务率 (\mu=5) req/s,当 (\lambda=4) 时平均系统时间为1秒;(\lambda=4.5) 时变为2秒。这说明接近容量上限时排队可能急剧恶化。LLM Continuous Batching 并非真正的 M/M/1:其服务能力随 Batch/长度变化,故该式只能说明机制,不能直接拿来预测某个 GPU 的延迟。
六、TTFT、TPOT、Goodput:到底优化哪个目标?
令请求从到达到首 Token 到达的时间为 TTFT,包含排队、Prefill、首 Token 处理及必要传输;第 j 个和第 j−1 个输出之间为 ITL(Inter-Token Latency)。
若请求输出 G≥2 个 Token,常见定义:
[ \mathrm{TPOT}=\frac{t_{\mathrm{last}}-t_{\mathrm{first}}}{G-1}, \qquad \mathrm{E2E}\approx\mathrm{TTFT}+(G-1)\mathrm{TPOT}. ]
令用户 SLO 是 TTFT≤a 且 TPOT≤b。定义观测窗口 (\Delta t) 内的双 SLO Goodput:
[ \boxed{ \mathrm{Goodput}= \frac{#{i:\mathrm{TTFT}_i\le a\ \land\ \mathrm{TPOT}_i\le b}}{\Delta t} } \quad\text{(合格请求/s)}. ]
这个定义要求明确 G=1 请求的 TPOT 约定、超时和取消请求的统计规则。Goodput 与原始完成请求率、输出 Tokens/s 不同。
例如10个请求在2秒内完成,但只有8个同时满足 TTFT 和 TPOT 两项 SLO,则 Goodput 为4个合格请求/s;不能由总 Tokens/s 替代这个指标。真实服务还要记录 p50/p95/p99 TTFT 与 ITL,关注 tail latency。
flowchart LR
A["到达"] --> B["排队 Queue"]
B --> C["Prefill"]
C --> D["首 Token:TTFT"]
D --> E["Decode Token 2"]
E --> F["Decode Token 3 ... G"]
F --> G["完成:E2E"]
D -. "相邻输出间隔 ITL" .-> F
B -. "排队/Head-of-line Blocking" .-> D
七、FCFS、优先级、抢占与公平
FCFS(先到先服务)实现简单,但很长的 Prefill 或长输出可能使新请求延迟增大;它不是“绝对公平”,因为请求占用的 Token 与 KV 资源不同。
Decode-first 可以保护正在流式输出请求的 TPOT,但可能使新请求的 TTFT 恶化。应考虑每请求等待时长上限或为 Prefill 保留资源。
SJF/SRPT 类思路可能改善平均响应时间,但生成长度通常事先未知;估计偏差也会改变实际效果。高优先级请求若持续到达,低优先级请求可能饥饿,需要 Aging、额度或等待上限等措施。
KV 不足时的抢占:系统可以让请求等待、释放/换出 KV 或丢弃部分缓存并在恢复时重算。它们都可能增加时间与传输负担。在 vLLM V1 的公开文档中,常见抢占模式是 RECOMPUTE;不要把不同版本的 SWAP / RECOMPUTE 行为混为同一固定事实。
八、一个可复现的公平实验
比较:①静态请求级 Batch;②迭代级 FCFS;③Decode-first Chunked Prefill;④带等待保护的优先级调度。固定模型、Tokenizer、精度、GPU、Kernel、输出采样策略和请求数据;提前生成并固定到达时间、Prompt 长度、输出上限/终止条件,避免各策略使用不同负载。
分别扫描短/长 Prompt、短/长输出、稳态 Poisson 到达和突发到达,以及从富余到接近耗尽的 KV 容量。区分固定并发闭环压测与固定到达率开环压测:前者可能通过客户端等待把真实排队压力隐藏掉。
记录正确性、实际输出 Token 数、请求完成率、Goodput、有效输出 Tokens/s、排队时间、p50/p95/p99 TTFT/ITL/TPOT、GPU Step 耗时、KV Block 使用率、分页碎片、抢占次数与重算/换出成本。在每组负载下做 Warmup、多随机种子及足够长的采样窗口。
# 仅示意调度逻辑,非可直接执行的 vLLM API
while server_running:
release_completed_requests_and_kv()
budget = max_batched_tokens
chosen = []
for req in prioritized_running_decodes():
if budget >= 1 and kv_can_append(req, 1):
chosen.append((req, "decode", 1))
budget -= 1
for req in waiting_or_partly_prefilled():
n = min(req.remaining_prompt, budget, kv_available_for(req))
if n > 0 and active_seq_limit_allows(req):
chosen.append((req, "prefill", n))
budget -= n
if not chosen:
wait_or_preempt_with_accounting()
else:
execute_one_iteration(chosen)
stream_tokens_update_kv_and_metrics()
该伪代码省略了并发保护、调度公平、完整 Prefill 状态、优先级抢占、分片 KV 及具体内核调用,不是生产系统完整实现。
九、易错反例与理论/研究边界
| 常见误解 | 更准确的理解 |
|---|---|
| Continuous Batching 并行生成同一请求全部 Token | 它动态合并不同请求的当前计算,单请求自回归依赖仍存在 |
| 每轮 Token 数少就一定快 | 历史长度、Kernel、带宽和 Batch 也决定耗时 |
| 只限制 Batch Size 就能杜绝 OOM | 长请求的 KV 块持续增长,必须做容量管理 |
| Chunked Prefill 必然让所有 TTFT 和 TPOT 同时改善 | 可能提升 Decode 流畅性,却推迟新请求首 Token |
| 最高输出 Token/s 就是最优服务 | 仍需看 Goodput 与 p95/p99 TTFT、ITL |
| 抢占完全免费 | KV 状态迁移和重算存在额外成本 |
| M/M/1 的均值公式能准确预测 LLM GPU | 仅在其到达和服务假设下成立 |
经典理论: 请求排队、Little 定律、约束优化与因果自回归关系。已有系统研究: Orca 的迭代级调度、Sarathi-Serve 的分块 Prefill、vLLM 的现代调度与抢占实现。任何加速倍率都必须限定模型、硬件、负载和 SLO;不是数学常数。
参考资料:
- Orca(OSDI 2022):https://www.usenix.org/conference/osdi22/presentation/yu
- Sarathi-Serve(OSDI 2024):https://www.usenix.org/conference/osdi24/presentation/agrawal
- vLLM V1 架构与调度:https://docs.vllm.ai/en/stable/design/arch_overview/
- vLLM V1 性能与抢占:https://docs.vllm.ai/en/v0.17.0/configuration/optimization/
十、四级递进自测(总分100分)
首次授课不公布标准答案或解析。 Lv1(15分)、Lv2(20分)、Lv3(25分)客观判分;Lv4(40分)按推导和实验设计评分。提交后逐题解释:80分及以上继续;60–79分针对性补练;低于60分复习再练。
Lv1|机制辨析:静态批处理与连续批处理(15分|预计2分钟|单选)
某在线 LLM 服务同时处理输出长度不相同、随时到达的请求。关于 Static Batching 与 Continuous Batching 的机制,哪项最准确?
A. Static Batching 允许任何新请求在每一轮立即加入,而 Continuous Batching 必须等所有请求同时结束。
B. Continuous Batching 在生成迭代边界移出已完成请求并接纳新请求,但同一请求的自回归后续 token 仍具有因果依赖。
C. Continuous Batching 通过取消因果 Attention,使同一请求所有未知输出 token 在一次前向中生成。
D. 只要使用 Continuous Batching,就不需要管理 KV Cache 容量,也不会产生排队。
提示:区分“同一次迭代里并行处理多个请求”与“同一请求的连续 token 是否可并行预测”;思考何时释放运行槽位。
Lv2|Token Budget 与分块 Prefill 数值(20分|预计4分钟|数值)
某教学化 Chunked Prefill 调度器,每轮新计算 Token 预算为 256。始终有 20 条处于 Decode 的请求,每条每轮恰处理 1 个新 Token,且这 20 条在整个例子中都不结束。另有唯一一条等待请求,Prompt 还需 Prefill 600 个 Token。假设调度器始终先安排 20 个 Decode Token,再把剩余预算全部分配给该 Prefill;活跃请求数、KV 显存及其他开销均不构成限制。请问该 Prefill 在第 3 轮处理多少个 Token?(填写整数)
作答: 填写整数,单位 token。
提示:每轮先扣除 Decode 使用的 Token 数,再依次更新 Prompt 剩余量;不要把 256 全部留给 Prefill。
Lv3|多约束调度与 SLO 推理(25分|预计6分钟|多选)
考虑标准自回归 LLM 在线推理:调度器每轮限制新计算 Token 预算、运行请求数量和 KV Block 池容量,允许 Chunked Prefill。下列哪些结论正确?(多选)
A. Iteration-level Scheduling 可以在相邻迭代之间释放完成请求并加入等待请求,而不破坏同一请求的自回归顺序。
B. 只要启用 Chunked Prefill,每个请求的 TTFT 与 TPOT 都必然同时降低,不会存在调度额外开销。
C. 每轮 Token 预算不仅要计入运行请求的新 Decode Token,还应计入本轮调度的 Prefill Chunk Token。
D. 仅知道 max_num_batched_tokens 就能确定 KV 是否足够,无须考虑请求已缓存的历史长度。
E. KV 不足时发生的抢占可能引入重新计算或状态迁移开销,调度优先级还可能影响公平性。
F. 在给定 TTFT 与 TPOT 双重 SLO 时,只提高总 Tokens/s 就严格保证满足 SLO 的请求率提高。
提示:把 Token 计算预算、历史 KV 容量、排队/抢占成本和 SLO 分开判断;注意带“必然”“只要”的结论。
Lv4|调度器建模与系统实验(40分|预计15分钟|开放题)
为单节点 GPU 上的 Decoder-only LLM 设计一个支持 Continuous Batching 的推理服务调度器。 A(12 分):定义等待队列、运行集合、每轮 Prefill/Decode 决策变量,并写出 Token Budget、最大运行序列数以及 KV Block 容量约束。说明 Token Budget 与 KV 容量为什么不是同一个量。 B(10 分):用 TTFT、TPOT、E2E、Little 定律描述队列与尾延迟,定义同时满足 TTFT 和 TPOT 门限的 Goodput;说明吞吐与 Goodput 不等价。 C(10 分):比较静态批处理、Iteration-level FCFS、Decode-first Chunked Prefill,以及一种带公平/饥饿保护的优先级策略;解释 KV 不足时抢占、重计算/迁移的影响。 D(8 分):设计公平实验,覆盖短/长 Prompt、短/长输出、突发/稳态到达率和 KV 压力,列出正确性、吞吐、p95/p99 TTFT/ITL、抢占与峰值显存等指标。
作答: 按 A、B、C、D 四部分组织回答,公式、伪代码或实验表格均可。
提示:从每轮集合变化与三种不同资源约束出发;再分别分析排队、正在生成的请求、长 Prefill 和抢占。实验要保持模型、硬件、Tokenizer 与请求流一致。
十一、下一课预告
第31课|2026年11月19日|第5周第3课:PagedAttention、Prefix Caching 与 KV Cache 分配/驱逐。 将从物理块和引用计数出发,推导分页 KV 的内部碎片、共享前缀的正确性边界以及缓存命中、重算和公平调度的关系。