LLM 推理的请求优先级与公平调度工程 2026
把 preemption/copy-on-write/SLO 分层抽象为统一的请求运行时,在 GPU显存、KV cache 复用与公平性之间建立可形式化验证的调度内核,降低尾延迟并最大化吞吐。
约 20 分钟阅读5,837 字3 次阅读博主
把 preemption/copy-on-write/SLO 分层抽象为统一的请求运行时,在 GPU显存、KV cache 复用与公平性之间建立可形式化验证的调度内核,降低尾延迟并最大化吞吐。
过去两年，LLM 推理引擎经历了从 static batching 到 continuous batching、再到 in-flight batching 的三阶段跃迁。每一次跃迁都把"批"的概念从请求级（request-level）下沉到了 step 级（iteration-level），使得 GPU 利用率从 30% 区间被推到 70% 以上。但当单实例单卡已能在 4090 上稳定支撑 50-80 req/s 的 7B 模型推理、当 vLLM / SGLang / TensorRT-LLM 已经能通过 PagedAttention 把显存碎片化问题控制到 5% 以内时,新的瓶颈开始浮出水面：它不再是吞吐，而是调度公平性——具体地说，是当多个 SLO 等级（latency-critical / interactive / batch / best-effort）的请求共存时，如何在抢占、KV cache 复用、显存抢占成本和端到端尾延迟之间找到一个可形式化验证的运行时。
线上推理服务很少只有一种请求。生产集群里通常有四类请求共存：1) 在线对话补全，延迟上限 200-500 ms；2) Agent 工具调用，单回合 2-15 秒但用户可见；3) 长文档摘要与代码补全，秒级到十秒级；4) 离线回填与评估请求，分钟级可接受。这四类请求的"公平"显然不是 FIFO 公平，也不是加权轮询公平，而是SLO 公平——即每个请求应被调度器按照其 SLO 截止时间与剩余工作量的比例分配 GPU 时间片，且低优先级请求不能以高优先级请求的尾延迟为代价独占调度器。
现有的推理调度实现大多回避了这个问题的形式化，转而采用启发式：vLLM 的 chunked prefill 把 prefill 切到与 decode 同等粒度的 1k-token chunk，但调度顺序仍然是先到先服务；SGLang 的 RadixAttention 把 prompt 前缀的 KV 缓存做成可复用的基数树，但 preemption 触发时仍然按到达时间倒序驱逐；TensorRT-LLM 的 in-flight batching 把请求状态机做成了显式的转换，但调度策略对外是黑盒。本文要回答的核心问题是：能否把这四类请求共存下的调度问题抽象为一个统一的运行时内核，让 SLO 分层、preemption 决策、KV cache 复用与显存回收这四个看起来独立的能力在同一套数学语言下被设计与验证？如果答案是否定的，那么 LLM 推理服务的复杂度天花板将由调度器决定，而非由 GPU 硬件决定——这将是推理基础设施最大的瓶颈来源之一。
让我们从排队论的基本形式出发。一个 LLM 推理实例可以被建模为多类请求共享一组 GPU 资源的 M/G/c 队列变体。设第 k 类请求的到达率为 λₖ，服务时间分布为 Bₖ(t)（即 prefill 阶段 t₁ₖ + decode 阶段 Nₖ × t₂ₖ，其中 Nₖ 为输出长度随机变量），SLO 截止时间为 Dₖ。那么调度器的目标不是经典的平均延迟最小化，而是：
min Σₖ wₖ · P(Tₖ > Dₖ) + α · ΔKV + β · Δpreempt
其中 P(Tₖ > Dₖ) 是第 k 类请求的超 SLO 概率，ΔKV 是 KV cache 复用损失，Δpreempt 是 preemption 引起的重计算开销，wₖ/α/β 是超参数。在不抢占、零 KV cache 复用的极限情形下，这就是经典的 M/G/c 多类排队问题；当引入抢占和 KV cache 复用时，问题变成一个有状态依赖的随机调度问题，传统的 Gittins 索引策略不再直接适用。
实用主义的形式化更倾向把上述优化问题分解为三个子问题：(a) 优先级赋值问题——给每个请求分配一个动态优先级 p(t) ∈ {0,1,2,3}，对应四类 SLO 等级；(b) 准入控制问题——决定是否接受新请求进入调度队列；(c) preemption 决策问题——当显存不足时，按什么顺序驱逐已分配 KV cache 的请求。这三个子问题在生产系统里通常由独立的子系统处理，但若未在同一数学框架下设计，它们之间的接口会反复出现"优先级跳变"（priority inversion）与"调度颠簸"（scheduling thrashing）这两类典型 bug。
把三者统一的关键是引入SLO-aware 效用函数：
U(req) = max(0, 1 - elapsed(req) / D(req)) · priority(req) · state_penalty(req)
其中 state_penalty ∈ {1.0, 0.6, 0.3} 分别对应请求处于 running / preempted / evicted 状态。这样效用函数把"是否快超 SLO""优先级多高""是否已被抢占"压缩为一个标量，调度器每次只在 step 边界选择效用最高的请求继续推进——这等价于一个多类工作保存（work-conserving）的优先级队列，但效用函数的引入让"优先级"变成动态可计算的。
Preemption 是 LLM 推理调度里最被低估的能力。它不是简单的"显存不够 → 驱逐请求"，而是一个由触发器、决策器、执行器、回收器四个组件构成的状态机。状态转换的形式化如下：
running → (trigger: OOM imminent / SLO preemption) → preempting → (action: copy-on-write / swap-to-CPU / discard) → preempted → (recovery: swap-in / recompute) → running
触发器的常见信号有三类：(1) 显存水位线（VRAM watermark）越过阈值（典型值 85-92%）；(2) 高优先级请求到达且当前无 idle slot；(3) decode 迭代里某请求已逼近其 SLO 截止但被低优先级请求阻塞。三类触发器在 vLLM / SGLang 中的实现差异显著：vLLM 0.6+ 引入 watermark-based eviction，SGLang 走 prefix-cache-aware eviction，TensorRT-LLM 用 NVIDIA Triton 的 dynamic batching 内置策略。
决策器是 preemption 的真正难点。一个朴素的做法是按"剩余 KV cache 大小 × 已用时间"排序，驱逐"占用多但进展少"的请求，但这忽略了 KV cache 复用的价值——一个 4k prefix 的请求即使已生成 200 token，复用价值仍可能远高于一个 100 token 的冷请求。更合理的决策器需要维护一个三元组 (mem, progress, reuse_value)，并按 score = mem / (progress + ε) × reuse_value 的升序驱逐。回收器则要把被驱逐请求的 KV block 根据调度器的策略写入 CPU 内存（swap）或直接丢弃——这里的关键工程取舍是 swap 路径的开销与未来重计算开销的比较。生产数据表明，对于平均 500-token 输出的请求，swap-out + swap-in 的总开销约为 80-150 ms，而丢弃重计算的开销是 prefill 整段 prompt 的时间，前者通常优于后者。
形式上，我们把 preemption 决策器定义为一个线性规划问题：
min Σᵢ cᵢ · evict(i) s.t. Σⱼ alloc(j) ≤ VRAM_budget ∀j high_prio: alloc(j) = request(j)
其中 cᵢ 是请求 i 的驱逐代价（越大越不应驱逐），alloc(j) 是请求 j 的资源分配。线性规划的解在理论上最优，但实际工程中因为 LP 求解延迟（典型 5-20 ms）无法在 step 边界内完成，所以工程实现是 LP 的启发式近似——这正是 80% 推理引擎 bug 的来源。
传统观念把 KV cache 视为抢占的"成本"——被抢占的请求需要重建 KV cache，时间从 O(prefill_len) 起步。但当我们把 KV cache 视为可继承的资产后，抢占的逻辑会发生根本反转：被抢占的请求如果是另一新请求的 prefix 扩展，则 KV cache 复用可以让新请求"零成本"启动。这是 RadixAttention 提出的洞察，也是 SGLang 在生产集群里显存利用率比 vLLM 高 15-25% 的核心原因。
把 KV cache 形式化为基数树节点 + LRU-Eviction 策略后，prefix 匹配不再是字符串前缀比较，而是树上路径匹配。每个节点存储 (token_seq, kv_blocks, ref_count)，调度器在每次新请求到达时执行一次最长前缀匹配，把命中的 KV block 直接挂载到新请求的 slot，未命中的部分按 prefill 增量计算。这套机制在生产里带来三个隐性收益：(a) Agent 多步推理里同一 system prompt 的请求可以完全共用 KV cache，省掉 60-90% 的 system prompt 重新计算；(b) Few-shot 提示词模板在多用户共享时整体复用；(c) Multi-turn 对话的历史消息可以增量式挂载，不需要每轮重算整段 context。
但 KV cache 复用与公平调度之间存在张力：当一个高优先级请求到达但 GPU 显存已满，调度器需要驱逐一个低优先级请求腾出空间。如果低优先级请求的 KV block 恰好是高优先级请求的 prefix，单纯驱逐会损失复用价值——这就是**复用感知驱逐（reuse-aware eviction）**问题的起源。形式上，调度器需要在以下两个目标间做权衡：
(a) 严格 SLO 公平：高优先级请求立刻抢占显存，代价是丢失复用 (b) 复用最优：让高优先级请求等待低优先级请求自然完成，代价是 SLO 违约
生产系统的答案是条件抢占：当高优先级请求能在剩余显存 + 一次 LRU 驱逐内获得 80% 以上的所需 KV cache 时，立即抢占；否则让高优先级请求排队等待剩余请求完成。这一阈值的选取依赖于业务对 SLO 违约的容忍度——典型的在线对话场景阈值是 90%，离线评估场景可以是 50%。
KV cache 复用率的形式化度量通常用 prefix hit rate = 复用 token 数 / 总 token 数，业界生产系统的优秀水位是 65-85% 之间。低于 50% 说明 prefix 重叠度不足（用户请求多样化），高于 90% 通常意味着单一场景（评测回放），两种极端都提示调度器可能需要调整 batch 策略。
把推理服务的请求分成四个 SLO 等级（Tier 0/1/2/3）后，调度器不再是单一队列，而是四类工作负载的协奏：Tier 0（latency-critical，<200 ms）、Tier 1（interactive，<2 s）、Tier 2（batch，<30 s）、Tier 3（best-effort，分钟级）。每一类对应一个独立的 FIFO 队列，但队列之间共享 GPU 资源。这里的关键设计原则不是"先到先服务"，而是"按 SLO 紧迫度服务"——一个 Tier 0 请求即便到达时间晚于 Tier 2，也必须被优先推进；反之一个接近破窗的 Tier 2 请求必须被自动升级，避免占用 Tier 0 资源造成 P99 抖动。
核心设计是时间片切分与公平份额（fair share）：
Tier 0 请求保留 30% 的 GPU 时间片（基于 P50 延迟反推），Tier 1 保留 50%，Tier 2/3 共用剩余 20%。时间片分配在每 100 ms 重新计算，由一个 monitoring loop 反馈控制：当 Tier 0 P99 延迟超过阈值时，自动把 Tier 1 的份额降 10pp 并加到 Tier 0。这种反馈式调度在生产里非常有效，因为它不依赖精确的负载预测，而只依赖可观测的延迟信号。生产经验表明，反馈式调度的关键是控制环的稳定性——如果控制增益过高，会出现份额在 30%/50% 之间震荡，引发调度颠簸；如果过低，又无法在 5 分钟内对负载变化做出反应。实用做法是把控制环的更新频率限制在 5-10 Hz，并把份额变化限制在 ±10pp/step。
更精细的做法是引入**加权公平队列（WFQ）+ 优先级提升（priority boosting）**的组合：低优先级请求按 WFQ 调度，但当某个 Tier 2 请求的执行时间超过其 SLO 截止的 70% 时，自动提升到 Tier 1 队列。这种"自动升级"机制解决了多任务系统中的优先级反转问题——一个本来该早完成的长任务被低优先级队列阻塞，最终"破窗"反而占据 Tier 0 资源。WFQ 的权重设计：每类工作负载的权重不是固定的，而是基于"剩余 SLO 时间 / 估算剩余工作量"动态计算——这种动态权重让即将破窗的请求获得指数级增长的优先级，而新到的请求只能获得基础优先级。
工程实现上，这一机制通常以一个独立的"deadline watcher"协程实现，每 100 ms 扫描一次活跃请求的 (started_at, deadline) 对，把即将破窗的请求升级。这一机制在 vLLM 的 scheduler 里被命名为 priority_boost，在 SGLang 的 tokenizer manager 里被实现为 deadline_aware_queue。生产调参经验：deadline watcher 的扫描频率在 50-200 ms 之间选择，频率过低会导致破窗请求升级不及时，频率过高会引入调度抖动；阈值（破窗比例）通常取 70-85%，过低会让"快破窗"的请求过早升级，过高又会让已经破窗的请求错失升级机会。
把上述四节抽象到一个统一视角：推理调度器是一个反应式系统（reactive system），它的状态空间是 (active_requests, kv_cache_pool, gpu_util, time)，它的输入流是 (new_request, sso_signal, kv_eviction)，它的输出是 (next_step_batch, preemption_actions)。状态转移遵循一组由效用函数 U(req) 导出的规则。
形式化验证的关键是把状态空间离散化：把 GPU 时间划分为 100 ms 的 step，每个 step 内调度器必须给出 (batch, preemption) 二元决策。这样调度器的不变量（invariant）可以表达为：
(a) ∀req ∈ Tier 0: P99 latency(req) < D₀ (b) ∀t: Σᵢ mem(reqᵢ) ≤ VRAM_budget (c) ∀t: Σₖ share(t, Tierₖ) = 1.0
不变量 (a) 是 SLO 约束，(b) 是资源约束，(c) 是公平约束。三者同时成立的调度器称为"well-formed scheduler"。验证一个具体实现是否 well-formed，需要在测试集上覆盖：(i) 高负载下低优先级请求不能饿死 Tier 0 的 P99；(ii) KV cache 复用不能破坏 SLO；(iii) preemption 决策不能导致 ping-pong（同一请求在 1 秒内被抢占两次以上）。
模型检验（model checking）可以覆盖 10⁹ 状态以内的系统，对推理调度器而言基本够用——一个实例同时活跃的请求通常 ≤ 200，每请求状态数 ≤ 10，全局状态空间 ≤ 2000⁰⁰ ≈ 10⁴⁶⁰，这是 model checker 无法覆盖的。实用做法是用 statistical model checking（SMC）：在 10⁵ 模拟轨迹上验证不变量违反率 < 0.1%。生产中通常以"1 小时内 P99 < 1.1 × D₀"作为可接受阈值。
把上面的形式化框架落地到生产里，至少要跨过三道鸿沟。
第一道：形式化模型与硬件约束的耦合。上述讨论默认 KV cache 是一阶连续的内存资源，但实际 GPU 显存是分层的——HBM3 / HBM3e 的 3-5 TB/s 带宽、L2 cache 的 50 MB 容量、跨卡的 NVLink/NVSwitch 拓扑都会引入约束：跨卡的 KV cache 传输成本是同卡访问的 10-20 倍，所以调度器在做 preemption 决策时必须考虑 KV block 的物理位置。这要求把形式化模型从纯逻辑层下沉到拓扑感知层。
第二道：SLO 等级的颗粒度。四类工作负载的划分在论文里足够，生产里往往需要更细——例如同一 Tier 1 里既有 200 ms 的对话补全也有 1.5 s 的代码补全，后者实际接近 Tier 2。生产实践通常把 SLO 等级做成可配置的 6-8 级，每级有独立的 share、独立的 watermark，独立的 priority boost 阈值。
第三道：observability 与 SLA 反向归因。当一个用户的请求超 SLO，调度器需要回答：是被谁阻塞的？是优先级反 preemption？还是 KV cache 复用被错误驱逐？这要求每一次调度决策都记录完整的因果链：(req_id, decision, triggered_by, mem_pressure, sso_status, kv_reuse_hit)。这条因果链在生产里通常以 OpenTelemetry Span 的形式落地，span attribute 包含全部上述字段。Tracing 后端（如 Jaeger / Tempo）能在事故复盘时反向追溯："某 Tier 0 请求 P99=800 ms 由 X 引起，X 是一个 Tier 2 请求在 200 ms 前触发的低优先级抢占"。
让我们对比一下主流推理引擎的实际选择。vLLM 的 scheduler 在 0.6 之后引入了 chunked prefill + watermark-based preemption，调度策略以 FIFO + priority boost 为主，没有显式的 fair share 机制。SGLang 的 tokenizer manager 走的是 reuse-aware scheduling + RadixAttention，KV cache 复用做得好但 fair share 还在迭代。TensorRT-LLM 走的是 NVIDIA Triton 的 dynamic batching + in-flight batching，对 NVIDIA 硬件的拓扑感知最优但跨厂商的兼容性较弱。
从可观测性角度，vLLM 0.6+ 提供了 Prometheus 指标 exporter，核心 metrics 包括 vllm:num_requests_swapped、vllm:gpu_cache_usage_perc、vllm:cpu_cache_usage_perc；SGLang 则暴露 sglang:num_running_reqs、sglang:token_usage、sglang:gen_throughput 等更细粒度的运行时指标。TensorRT-LLM 通过 Triton Inference Server 的标准 metrics（nv-inference queue latency / compute latency）暴露调度信息，但缺乏 per-tier 的细分。真正能在生产里直接回答"我的 Tier 0 P99 是被谁阻塞的"的引擎目前还没有开源实现，这是一线厂商的核心竞争力。
从调度公平性角度，Anthropic 在 2024 年的工程博客里披露了一个细节：他们的内部调度器对不同 SLO 等级的工作负载使用独立的 GPU 配额（quota），而不是 share——quota 是硬上限，share 是软分配。Quota 机制下，Tier 0 的 30% 是预留（reservation），即便 Tier 0 空闲也不能被 Tier 1 借用；而 share 机制下，Tier 0 空闲时 Tier 1 可以临时占用。生产里 reservation 机制更可预测，但牺牲了 ~10-15% 的总吞吐利用率。这一取舍本质是"严格 SLO 优先"vs"最大化 GPU 利用"之间的权衡——前者适合 SLA 严格的 B2B 场景，后者适合内部业务或评估场景。
从演进路线角度，2025-2026 年的工程前沿是把抢占决策从集中式调度器下沉到 GPU kernel 自身——即让 kernel 知道 SLO 等级，并在 decode 阶段主动让出 SM 给更高优先级请求。这一思路在 NVIDIA Hopper 架构上首次成为可能：TMA（Tensor Memory Accelerator）+ DSMEM 机制允许 kernel 在 decode 中途主动 yield，而 AMD MI300 系列目前还做不到。预计 2026 下半年到 2027 上半年，开源推理引擎（vLLM / SGLang）会逐步吸收这一能力，届时"kernel-aware scheduling"会成为新一代推理引擎的标配。
本文提出的"四类 SLO 分层 + 效用函数驱动调度 + 复用感知 preemption"组合，在生产集群里实际是手工定制出来的——绝大多数线上服务都没有现成的开源实现。这反映了推理调度领域的一个特点：理论优美但工程复杂，开源实现通常只覆盖单类工作负载，跨类的统一调度在工业界是黑盒。这与本文作者在 2024-2025 年观测到的现象一致：大型 LLM 服务商（Anthropic / OpenAI / Google DeepMind）的内部推理调度系统都是私有的，且通常比开源版本领先 6-12 个月。
需要明确指出的是，这条路线在推理延迟 < 200 ms 的场景下仍然困难——它本质上受限于 prefill 的计算复杂度。对于极低延迟场景（如实时语音、即时翻译），更合适的方案是把 prefill 阶段彻底拆出，由专用的 prefill pool 处理，decode pool 单独跑生成任务，这就是 disaggregated inference 的思想——已在 Anthropic / DeepSeek 等生产系统里规模化使用。
把本文论述落成生产 checklist，至少需要以下 9 项能力：
一句话摘要：把请求优先级、preemption、KV cache 复用与 SLO 分层抽象为一个效用函数驱动的统一运行时内核，让 LLM 推理调度从黑盒启发式走向可形式化验证的反应式系统。
Conversation
0 条