Continuous batching、prefix cache 与 QoS：调度器到底在每一轮做什么

1. 这页在整条主线中的位置

模型架构决定一次迭代要做哪些算子，KV cache 决定请求要长期占多少内存，runtime 调度器则把这些约束变成每一轮具体的执行清单。向上，它接收 API 请求和租户 SLO；向下，它生成 token budget、sequence list、block table 和 collective 调用。调度器的错误不会改变模型数学，却会把同一台 GPU 从“延迟稳定”变成“队首阻塞、显存抖动、尾延迟失控”。

2. 前置概念：一次“迭代”不是一个“请求”

自回归模型的 prefill 可以一次处理 prompt 的许多 token；decode 通常每个活跃序列每轮只产生一个新 token。设本轮有 B_d 条 decode 序列，每条走 1 token，另有 prefill chunk 共 T_p 个 token，调度器需要限制本轮总 token、序列数、KV 新页和算子形状。HTTP 请求数并不能准确表示这些资源。

这里的 token budget 是计算预算，KV page budget 是内存预算；两者必须同时满足。只盯 batch size 会把 32 个短 decode 和 32 个 32K prefill 当成同一种负载，显然错误。

3. 请求生命周期：把每条序列看成状态机

一个实用状态机至少包含：WAITING、PREFILLING、DECODING、PREEMPTED、WAITING_TOOL、FINISHED。多轮 Agent 还会在一次用户请求内部反复经过 decode、工具等待、追加工具结果、增量 prefill、再次 decode。每次状态转移都要携带位置、block table、采样器状态、随机种子、prefix 节点和租户优先级。

4. Continuous batching 的完整机制

固定 batching 必须等最慢序列结束，空出来的 batch slot 不能及时接新请求。continuous batching 在每轮 decode 边界退休已完成序列，并立即把新请求或 prefill chunk 填进来。它仍然是 batch GEMM，只是 batch 成员每轮可变。

while service_is_running:
    collect_finished_sequences()
    release_or_cache_their_KV_pages()

    token_budget = max_batched_tokens
    memory_budget = free_KV_pages()

    schedule_latency_critical_decode_first()
    schedule_admitted_prefill_chunks(token_budget, memory_budget)
    maybe_preempt_low_priority_sequences()

    logits = execute_one_model_iteration(batch, block_tables)
    sample_and_append_tokens(logits)
    publish_cache_and_completion_events()

调度器每个 token iteration 都会做一次决策，而非等到整个请求结束。ORCA 在 OSDI 2022 系统化提出 iteration-level scheduling；到 2026 年，vLLM 与 SGLang 已将它同分页 KV、chunked prefill、prefix reuse 和 PD 分离结合。阅读资料时要区分基础技术提出的年份与当前实现版本。

5. 调度目标不是“把 batch 填满”

填满 token budget 通常提高吞吐，却可能让 decode 的 inter-token latency 超标。一个更准确的选择问题是：在计算、KV 和优先级约束下，选择本轮序列集合，使满足 TTFT 与 TPOT SLO 的 token 或请求最多。

生产实现不会每轮精确求整数规划，而会用启发式：decode-first、按等待时间老化、按 prefix 命中排序、按预计迭代时间限制 prefill chunk、按租户配额做 deficit round robin。重要的是把 heuristic 对应到显式目标，否则“优化吞吐”的改动很容易偷偷破坏尾延迟。

6. Prefill 与 decode 为什么会互相伤害

长 prefill 的大 GEMM 容易占据整轮 GPU 时间，正在流式输出的 decode 请求只能等待，于是 TPOT 出现尖峰；反过来，如果永远优先 decode，大量小 decode batch 会把 prefill 饿死，TTFT 变差。chunked prefill 把长 prompt 拆成多个 token chunk，在相邻 decode 轮之间插入。

2026 年的 load-aware prefill deflection 工作在 2P2D A100 实验中观察到：prefill 执行本身只占 P95 TTFT 的 2%–23%，其余主要是排队和 KV 传输。它把部分 prefill 以受 TBT 约束的 chunk 送到 decode 侧，报告 P95 TTFT 降低 81%、SLO attainment 提升 79%。这说明“加速 prefill kernel”不能替代排队与放置控制。

7. 分页 KV 与 prefix cache 怎样进入调度决策

PagedAttention 把逻辑连续的 KV 序列映射到固定大小物理 block，调度器因此可以按页分配、回收、复制和换出，不必为最大上下文预留一整段连续显存。prefix cache 再把已计算的 prompt block 挂到 trie 或 radix tree 上；新请求只需 prefill 未命中的后缀。

缓存 key 必须包括影响 KV 的全部输入：模型/adapter 版本、token 序列、位置编码语义、多模态编码结果及必要的采样前状态。仅按原始字符串或会话 ID 命中会产生错误复用。共享前缀还能降低显存，但共享页必须采用引用计数或 copy-on-write，避免一个请求追加 token 时污染其他请求。

8. 抢占：重算、换出还是迁移

当没有足够 KV 页接纳高优先级请求时，runtime 有三种基本动作。重算只保留 token，恢复时重新 prefill；换出把 KV 写到 CPU/SSD；迁移把 KV 和状态发给另一 worker。选择取决于剩余上下文长度、链路带宽、未来恢复概率和当前空闲计算。

FastServe 的原论文发表于 NSDI 2026：它在 token iteration 边界抢占，并结合 skip-join MLFQ 与 GPU/host 状态主动换出；论文报告相对 vLLM 最高 6.1× 吞吐。它在 MLFQ 基础上进一步处理了 LLM 特有的两个条件：请求剩余工作量未知，而且 KV 状态很大。

9. TTFT、TPOT、TBT 与 goodput

TTFT 是从到达到首 token；TPOT 是首 token 后平均每个输出 token 的时间；TBT 强调相邻 token 的间隔及其尾部；goodput 只统计同时满足规定 SLO 的请求或 token。只报 tokens/s 会掩盖排队和尾延迟。

同一个“2000 token/s”系统可能通过把大量请求塞进 batch 得到高总吞吐，却让单用户只看到 5 token/s。容量规划必须固定输入/输出长度分布、并发、SLO 和到达过程后比较 goodput。

10. 2026 的进一步变化：请求可以在任意 token 边界拆开

Libra（NSDI 2026）不把“整个请求固定在一个 worker”当不可变前提，而是把请求切成 micro-request，在任意 token 边界转移。全局层决定 split point 和 worker，局部层做 SLO-aware batching，并用 chunked KV transfer 降低迁移阻塞。论文报告 goodput 最高提升 1.91×/1.61×、容量提升 1.15–3.07×，混合负载提升 74.2%。

这让调度单位从“请求”进一步缩小到“请求的一段 token 生命周期”。代价是需要可迁移 block table、精确的状态一致性和对 KV 传输尾延迟的控制；如果网络不可预测，拆分本身会制造新的 TBT 尖峰。

11. Speculative decoding 使预算从 token 变成验证树

草稿模型或 MTP head 一次提出多个候选，主模型并行验证。调度器要预留验证 token、临时 KV 和分支元数据；实际接受长度又是随机变量。若简单按“每序列一个 token”估算，本轮显存和算子形状会失真。

GLM-5.2 的 2026 SGLang 官方优化报告使用 Spec V2 overlap 和 IndexShare，称 MTP 接受长度经常达到 5 个以上 token；复用 DSA indexer top-k 使长上下文草稿成本约降 1.9×。这是具体模型上的官方工程结果，不能外推成所有模型都能接受 5 个 token。

12. 2026 生产实现：vLLM、SGLang 与模型特化

vLLM 的 2026 当前仓库明确列出 continuous batching、PagedAttention、chunked prefill、prefix caching、speculative decoding 和 P/D 分离；这些机制来自多个年份的论文，但当前 runtime 已把它们组合成统一 scheduler。SGLang 则以 RadixAttention 为共享前缀核心，配合连续批处理、分布式并行与 disaggregation。

模型结构也会反推 runtime。DeepSeek-V4 的 2026 SGLang 报告使用 ShadowRadix、HiSparse、MTP 与混合稀疏 attention：10K token 请求只保留 128 个原始 SWA token，其余依赖压缩 KV；从 4K 到 900K context，官方测试的 B200 输出吞吐从 199 降至 180 token/s，H200 从 266 降至 240 token/s，下降小于 10%。这类稀疏 KV 改变了 admission 的“每 token 内存”估算，不能继续套 dense MHA 常数。

13. 具体例子：一轮怎样选择 3 个 decode 和 1 个长 prompt

假设本轮 token budget 为 1024，三条 decode 序列各需要 1 token，其中一条距离 P99 TBT deadline 仅剩 4 ms；队列头有一个 10K prompt，prefix 命中 6K，尚需 4K prefill；每个 KV block 容纳 16 token，只剩 70 个 block。

1. 先给三条 decode 各排 1 token，预算剩 1021；按所需新增 KV 分配/复用最后一个 block。
2. 4K 后缀不能整段进入；基于迭代时间模型选 1008-token chunk，使本轮总 token 为 1011，并保留若干页余量。
3. 执行后，三条 decode 追加 token，prefill 请求写入 63 个 block；prefix 共享的 6K block 只增加引用计数。
4. 若估计 1008-token prefill 会让本轮超过 4 ms slack，则进一步缩小 chunk，哪怕降低 GPU 利用率。

QoS 最终要落到每轮能接受多长的算子执行时间。仅给请求排一个抽象优先级，还不足以保证 deadline。

14. 实现与部署清单

• 将请求、sequence group、KV block 和模型 executor 分层；状态变更用单一所有者或版本号避免双重释放。
• 同时限制 max_num_seqs、max_batched_tokens、KV 水位和预计迭代时间。
• 用真实 prompt/output 分布离线拟合 iteration latency，而不是只用 FLOPs 估算。
• prefix 命中长度应在路由和 admission 前可见；跨 worker 时订阅 cache add/remove 事件。
• 按租户记录 TTFT/TBT 直方图、抢占原因、swap bytes、cache hit tokens 和 rejected requests。
• 为工具等待设置保留策略：短等待保 HBM，长等待转 CPU/SSD，低恢复概率允许丢弃后重算。
• 升级 runtime 时固定模型、量化、CUDA graph、采样器与到达 trace 做 A/B，否则吞吐差异不可归因。

15. 局限与常见错误

论文中的最高倍数来自特定模型、GPU、trace 和 SLO。部署时应读取完整评测设置；本页数字用于说明机制的量级，不是采购或容量承诺。

16. 最小复现实验

准备同一模型的三种 trace：短对话（1K/128）、长 prompt（64K/128）、Agent 多轮（80K 前缀、每轮追加 1K、工具等待 0.1–10 秒）。固定请求率扫描并发，比较 FCFS、decode-first、chunked prefill、prefix-aware 四种策略。

必须记录：
arrival_ts, admit_ts, first_token_ts, every_token_ts, finish_ts
scheduled_tokens/iteration, iteration_ms, KV_pages, swapped_bytes
prefix_hit_tokens, preemption_count, tenant, status

报告：P50/P95/P99 TTFT；P99 TBT；tokens/s；goodput；OOM/拒绝率；公平性

请求率上升时，需要定位 goodput 曲线的拐点，并确认原因是计算饱和、KV 水位还是 swap 带宽。若缺少这层分解，“scheduler 快了 X%”很难迁移到另一套集群。

17. 一手来源与年份边界