请求不断到达时为何还要等整批结束？Continuous Batching 的逐轮调度

上一篇用 PagedAttention（分页注意力）让每条请求的 KV Cache 按块增长，避免为最大长度预留连续显存。但“能把更多请求放进显存”不等于“GPU 每一轮都在服务最有价值的请求”。若把 16 条请求组成固定批次，必须等最慢的一条生成结束才接纳下一批，早早结束的 15 个位置会一直空着。

Continuous Batching（连续批处理，也称 iteration-level scheduling，逐迭代调度）把批次边界从“整条请求”下移到“模型的一次前向”。每生成一轮，scheduler（调度器）都移走已完成请求，再从等待队列补入新请求。

01 静态批处理浪费的不是 Padding，而是空轮次#

设四条请求都已完成 prefill（提示词阶段），还需生成 [1, 2, 4, 4] 个 token。静态批处理锁住这四个位置直到最长请求结束：

decode 轮次       1    2    3    4
A: 还需 1         ●    -    -    -
B: 还需 2         ●    ●    -    -
C: 还需 4         ●    ●    ●    ●
D: 还需 4         ●    ●    ●    ●
有效槽位          4    3    2    2   => 11 / 16

text

这里的 - 不是输入张量里的 padding token，而是本可让新请求执行、却被批次边界闲置的 decode slot。若等待队列里还有 E、F，连续批处理能在下一轮立即补位。

02 调度器每一轮看见什么状态？#

一条生成请求至少携带：

prompt_tokens：尚未计算或已经写入 KV Cache 的输入 token；
generated_tokens：当前已经生成的输出；
max_new_tokens、EOS 与停止字符串：完成条件；
block_table：逻辑 token 到物理 KV blocks 的映射；
arrival_time 与 priority：排队次序；
sampling state：随机数、temperature、top-p 等采样状态。

调度器维护三个集合：

flowchart LR
  Q[waiting<br/>等待 admission] -->|KV 与 token 预算允许| R[running<br/>本轮执行]
  R -->|未结束，保留 KV| R
  R -->|EOS / 长度 / stop| F[finished<br/>释放 KV blocks]
  R -->|显存压力，抢占| Q

mermaid

一次 scheduler step 输出的不是永远固定的 [N,L] 批，而是一组本轮要计算的 token 与对应位置元数据。模型执行后，输出 token、KV 长度和完成状态再反馈给下一轮。

03 用四轮手算请求怎样被替换#

令最大并发序列数为 3，A/B/C 在 t=0 已进入 decode，所需输出分别为 1、3、2；D 在第 1 轮结束后到达。

轮次	轮前 running	本轮各算 1 token	轮后完成	补入请求
1	A, B, C	A₁, B₁, C₁	A	D
2	B, C, D	B₂, C₂, D₁	C	E
3	B, D, E	B₃, D₂, E₁	B	F
4	D, E, F	D₃, E₂, F₁	视停止条件	下一条

静态批会让 A 的位置闲置两轮，且 D 必须等 B、C 全结束；连续批让空位只存在于“本轮结束到下轮开始”的调度间隙。

04 Prefill 与 Decode 为何不能只按“请求数”计费？#

对 decoder-only Transformer：

Prefill（提示词预填充）一次计算 prompt 中很多 token，矩阵乘规模大，通常更偏 compute-bound（计算受限）；
Decode（逐 token 解码）每条请求每轮通常只新增 1 token，却读取全部历史 KV，常更偏 memory-bandwidth-bound（显存带宽受限）。

若本轮有 $n_d$ 条 decode 请求和若干 prefill token $p_i$ ，可把工作预算粗略写成

T_{\text{scheduled}}=n_d+\sum_i p_i.

它不是精确运行时间模型：一个 decode token 会读不同长度的 KV，一个 prefill token 的 attention 上下文也不同。但它比“本轮有多少条请求”更接近实际工作量，适合作为第一层容量阀门。

05 两个容量上限必须同时满足#

当前 vLLM 的 scheduler 公开两个核心限制：

N_{\text{seq}}\leq \texttt{max\_num\_seqs},

T_{\text{scheduled}}\leq \texttt{max\_num\_batched\_tokens}.

前者约束序列数及其 CPU 元数据、采样和 kernel batch 维度；后者约束单轮 token 工作量。除此之外还必须满足 KV Cache 可用 blocks，否则请求不能 admission（准入），或已有请求需要 preemption（抢占）。

waiting queue
    |
    v
[序列数上限] --不满足--> 等待
    |
    v
[本轮 token 预算] --不满足--> 等待/只取部分 prefill
    |
    v
[KV blocks 足够] --不满足--> 等待/抢占
    |
    v
本轮 model runner

text

06 一个透明的教学版逐轮调度器#

下面只模拟已完成 prefill 的 decode 请求。生产系统还要处理 KV blocks、prefill、sampling 和多 GPU 一致性。

from collections import deque
from dataclasses import dataclass

@dataclass
class Request:
    rid: str
    remaining: int

def continuous_decode(requests: list[Request], max_num_seqs: int):
    waiting = deque(requests)
    running: list[Request] = []
    timeline: list[list[str]] = []

    while waiting or running:
        while waiting and len(running) < max_num_seqs:
            running.append(waiting.popleft())

        # 一次 forward：每条 running 请求恰好新增一个 token
        timeline.append([r.rid for r in running])
        for r in running:
            r.remaining -= 1

        # 在迭代边界释放完成请求；下一轮才补入新请求
        running = [r for r in running if r.remaining > 0]

    return timeline

requests = [Request("A", 1), Request("B", 3), Request("C", 2), Request("D", 3)]
print(continuous_decode(requests, max_num_seqs=3))
# [['A', 'B', 'C'], ['B', 'C', 'D'], ['B', 'D'], ['D']]

python

输入是请求及剩余生成长度；输出是每轮真正参与 forward 的 request IDs。最重要的断言是：每条请求出现的轮数恰好等于其 remaining 初值，且完成后不再出现。

07 为什么吞吐与延迟可能同时改善？#

吞吐常以 output tokens/s 或 completed requests/s 衡量。连续补位提高 GPU 有效 batch，通常增加吞吐；短请求也不必等待同批长请求，可能同时降低排队时间。

但“延迟”至少拆成：

Time To First Token（首 token 延迟，TTFT）：到达至第一个输出；
Time Per Output Token（逐 token 间隔，TPOT）：开始输出后的平均间隔；
Inter-Token Latency（token 间延迟，ITL）：每两个流式 token 的具体时间间隔；
End-to-End Latency（端到端延迟，E2E）：到达至完成。

若为追求吞吐不断扩大 batch，每轮 kernel 更久，已在 decode 的请求反而要更久才等到下一 token，TPOT/P99 可能恶化。没有 arrival rate、prompt/output 长度分布和延迟分位数的单个 tokens/s 没有可比性。

08 FCFS、Priority 与公平性#

First-Come, First-Served（先到先服务，FCFS）容易解释，但超长 prompt 可能挡住短请求。Priority Scheduling（优先级调度）能为交互流量保留低延迟，却可能让低优先级请求 starvation（饥饿）。

工程上要明确：

priority 是否可由外部用户随意指定；
同优先级怎样按到达时间打破平局；
是否做 aging，让等待越久的请求逐渐提升权重；
租户级配额是否在单请求 priority 之前生效。

当前 vLLM 的 --scheduling-policy 支持 fcfs 与 priority。不要依赖内部 scheduler 类的私有字段；优先通过稳定 CLI/EngineArgs 配置，并锁定部署版本。

09 当前 vLLM 的可审计启动配置#

vllm serve your-org/your-model \
  --max-num-seqs 128 \
  --max-num-batched-tokens 4096 \
  --scheduling-policy fcfs

bash

这些数值只是实验起点，不是通用最佳值。记录模型、dtype、tensor parallel 大小、GPU、max_model_len、KV cache 容量与流量分布，再分别 sweep 两个上限。

一次完整实验至少输出：

offered_rps, admitted_rps, completed_rps
prompt_tokens/s, output_tokens/s
TTFT p50/p95/p99, TPOT p50/p95/p99
queue_time, running_sequences, waiting_sequences
KV usage, preemptions, OOM/rejection count

text

10 抢占为什么可能让系统越忙越慢？#

若调度器过度 admission，KV blocks 不够时必须暂停某些请求。被抢占请求可能需要 swap（换出）或稍后 recompute（重算）已有状态。两者都消耗带宽或算力，并拉长尾延迟。

一种危险反馈环是：

flowchart LR
  A[并发上限过高] --> B[KV 压力]
  B --> C[频繁抢占]
  C --> D[重算/换入开销]
  D --> E[每轮变慢、队列增长]
  E --> A

mermaid

因此 max_num_seqs 不能只调到 OOM 前一格。看见 preemption 增多时，应同时检查请求长度分布、KV block 水位、token budget 与 prefix sharing，而非只加队列长度。

11 正确性要验证哪些跨轮状态？#

连续替换 batch 后，最危险的错误是“张量位置变了，请求状态没有一起移动”。用确定性 greedy decoding 建立以下测试：

单请求离线生成作为 reference；
同一请求与不同到达时刻、不同输出长度的干扰请求混跑；
比较最终 token IDs，而非只比字符串；
在请求完成、取消、抢占、KV block 边界处记录 request ID；
断言每条序列的 position、block table、sampling state 始终配套。

对 stochastic sampling（随机采样），若 RNG 依赖 batch position，请求重排可能改变输出。可按 request ID 派生独立随机流，并把“批次组成变化不改变同请求随机序列”写成测试契约。

12 常见错误与最短调试路径#

症状	常见原因	最短检查
请求越多 tokens/s 反而下降	batch 已过饱和或抢占频繁	画吞吐、TPOT、preemption 随并发曲线
短请求 P99 很高	FCFS 前有长 prefill	分开统计 queue 与 prefill 时间
流式输出偶发长停顿	混入大 prefill 或单轮 token 预算过大	记录每轮 prefill/decode token 数和耗时
混批结果与单请求不同	KV/position/RNG 随 batch 重排错位	用两个请求在完成边界逐 token 对账
仍有显存却拒绝请求	KV blocks、序列上限或预留水位命中	同时打印三个准入条件
平均延迟好但用户仍投诉	尾延迟或不同租户被平均掩盖	按长度、租户与优先级看 p95/p99

13 它与 Dynamic Batching 有什么不同？#

Dynamic Batching（动态批处理）常在请求进入模型前等待一个短窗口，把同时到达的请求凑成一批；批次一旦开始仍可能锁到整条请求结束。Continuous Batching 会在每次模型迭代后重新组成批次。

PagedAttention 解决 KV 的物理存放；continuous batching 决定谁在本轮运行；chunked prefill 再决定长 prompt 是否能拆成多轮。三者分别对应 memory manager、request scheduler 与 token-level work partition。

14 今天真正需要记住什么？#

固定请求批次会在短请求结束后留下空轮次；逐迭代调度能立刻补入等待请求。
一轮能放多少工作同时受 sequence count、scheduled token budget 与 KV blocks 约束。
更大 batch 通常提高吞吐，却可能拉长每轮时间与 TPOT；必须联合测 TTFT、TPOT、吞吐和抢占。
调度改变 batch 位置时，KV、position、停止条件与 RNG 必须按 request ID 保持一致。

15 思考题与小练习#

三条请求还需生成 [2,4,1] 个 token，max_num_seqs=2。分别画静态批与连续批时间线，计算有效槽位比例。
本轮已有 80 条 decode 请求，token 预算为 512。若一个新 prompt 有 600 tokens，在不切 prefill 时为何无法进入？切分后第一轮最多取多少 prompt tokens？
扩展教学版调度器，加入 arrival step 与 priority；设计一个防止低优先级请求永久饥饿的 aging 规则。

16 下一篇预告#

连续批处理能在请求完成后立刻补位，但一个 32K prompt 若必须整段 prefill，单次迭代仍会很长，正在流式生成的请求会集体停顿。下一篇将把 prefill 切成 token chunks，手算 chunked prefill 如何用同一轮预算保护 TPOT。

01 静态批处理浪费的不是 Padding，而是空轮次#

02 调度器每一轮看见什么状态？#

03 用四轮手算请求怎样被替换#

04 Prefill 与 Decode 为何不能只按“请求数”计费？#

05 两个容量上限必须同时满足#

06 一个透明的教学版逐轮调度器#

07 为什么吞吐与延迟可能同时改善？#

08 FCFS、Priority 与公平性#

09 当前 vLLM 的可审计启动配置#

10 抢占为什么可能让系统越忙越慢？#

11 正确性要验证哪些跨轮状态？#

12 常见错误与最短调试路径#

13 它与 Dynamic Batching 有什么不同？#

14 今天真正需要记住什么？#

15 思考题与小练习#

相关工作#

16 下一篇预告#