LLM 排队论：为什么你的负载均衡器按请求思考，而你的 GPU 按 Token 思考

你的负载均衡器将请求均匀地分配到你的 GPU 集群中。每个实例接收到的并发请求数量大致相同。一切看起来都很均衡。然而，一个实例的运行速度缓慢，仅为每秒 40 个 token，而另一个实例却能稳定在 200 个。仪表板显示请求数相等，但你的用户体验到的延迟却天差地别。

问题的根源在于：传统的负载均衡在请求层面运行，但 LLM 推理成本是随 token 数量扩展的。一个要求生成 4,000 个 token 文章的请求所消耗的 GPU 时间，是一个生成 80 个 token 分类结果请求的 50 倍。将它们视为同等单位，就像高速公路收费站只计算车辆数量而不区分摩托车和 18 轮大卡车一样。

这种请求层面的思维与 token 层面的现实之间的不匹配，正是古典排队论面临的最有趣的现代挑战。

利特尔法则不在乎你的 Token（直到它开始在乎）

利特尔法则 (Little's Law) —— L = λW，即平均队列长度等于到达率乘以平均等待时间 —— 是排队论的基石。无论到达分布或服务策略如何，它对任何稳定系统都适用。但将其应用于 LLM 推理需要重新定义你实际测量的对象。

在传统的 Web 服务中，“工作单位”是一个请求。服务时间大致是可预测的：数据库查询需要 5-50 毫秒，API 调用需要 100-500 毫秒。你可以将容量建模为每秒请求数，并据此进行规划。

LLM 推理通过以下三种方式打破了这一假设：

• 双峰处理 (Bimodal processing)：每个请求都有一个 prefill 阶段（处理输入 prompt，可并行化）和一个 decode 阶段（按顺序生成 token，每次前向传递生成一个）。这两者具有截然不同的计算特性。
• 可变的输出长度：当请求到达时，你不知道它的服务时间。一个请求可能生成 10 个 token，也可能生成 4,000 个。服务时间的差异可能跨越两个数量级。
• 内存受限的扩展：每个活动请求都持有一个键值 (KV) 缓存，该缓存随生成的每个 token 而增长。GPU 内存（而非计算能力）往往成为核心限制因素。

实际意义在于：你需要将利特尔法则应用于 token 层面，而不是请求层面。系统的吞吐量容量是以每秒 token 数来衡量的，你需要管理的“队列”是总的 token 工作负载 —— 包括等待 prefill 的输入 token 以及所有活动序列中正在生成的输出 token。

当研究人员将 LLM 推理建模为一个离散时间排队系统，且每个时间槽对应一次 GPU 前向传递时，其稳定性条件变为：

λ(m_prefill + m_decode) < B / t_step

其中 λ 是请求到达率，m_prefill 和 m_decode 是平均 token 计数，B 是每步 token 预算，t_step 是每次前向传递的时间。一旦超过这个阈值，你的队列就会无限增长 —— 无论你的调度器有多聪明。

为什么请求层面的负载均衡会失败

考虑一个 GPU 实例，每次前向传递的 token 预算为 512。以下是两个请求数完全相同的场景：

场景 A：10 个并发请求，每个生成约 50 个 token。每步总的活动 decode token 数：约 10。Prefill 很快，decode 步骤很轻量。GPU 利用率不足。

场景 B：10 个并发请求，每个生成约 2,000 个 token。所有序列的 KV 缓存：巨大。GPU 在处理到 6 个并发序列时内存耗尽，迫使 4 个请求进入等待队列。有效吞吐量骤降。

请求层面的负载均衡器在两种情况下都看到“10 个请求”，并认为它们是平衡的。而感知 token 的系统会看到实际 GPU 工作负载存在 40 倍的差异。

这就是为什么 N+1 查询问题在 LLM 服务中也有类似的情况：负载均衡器在不知道每个决策实际成本的情况下做出了 N 个路由决策。它所需要的信息 —— 输出 token 计数 —— 在做出路由决策时还不存在。

实际的解决办法包括：

• 基于 Prompt 长度加权的路由：使用输入 token 计数作为总成本的代理。虽然不完全准确，但较长的 prompt 通常与较长的输出相关。
• 基于活动 Token 计数的路由：将路由指向处理中总 token 数（prefill + decode）最少的实例，而不是请求数最少的实例。
• 感知 KV 缓存的路由：根据可用 GPU 内存而非请求数进行路由。一些系统（如 NVIDIA Dynamo）通过将内存利用率暴露为路由信号来实现这一点。

这些方法都不能完全解决预测问题，但它们将差异从 100 倍降低到大约 3-5 倍 —— 足以让尾部延迟保持在可控范围内。

真正至关重要的调度策略

古典排队论提供了一系列调度策略：FIFO（先进先出）、SJF（短作业优先）、优先级队列、公平队列。对于 LLM 推理，最重要的选择不是下一个服务哪个 请求 —— 而是如何用 token 填满每个 GPU 迭代。

最近的研究将此形式化为“工作守恒 (work-conserving)”属性：如果调度器在有足够 token 可用时，总能将每次迭代的 token 预算填满，那么它就是工作守恒的。核心见解是：在同一个 batch 中混合 prefill 和 decode token 对于实现吞吐量最优至关重要。

原因如下。在一个仅包含 decode 的 batch 中，你可能有 8 个活动序列，每个序列每步贡献 1 个 token = 每次前向传递处理 8 个 token，而预算是 512。这只有 1.5% 的利用率。工作守恒调度器会将等待请求中的 prefill token 填充到剩余的 504 个 token 槽中，从而显著提高每步的 GPU 利用率。

实际验证结果非常显著：

• Sarathi-Serve 和 Orca：经证明是吞吐量最优的。两者都通过分块 prefill (chunked prefill) 在同一个 batch 中混合 prefill 和 decode token。
• FasterTransformer：并非吞吐量最优。它将 prefill 和 decode 分离到不同的 batch 中，导致 GPU 周期被浪费。
• 原生 vLLM (在支持 chunked prefill 之前)：在其原始形式下并非吞吐量最优。没有混合的 prefill 优先调度可能会在某些到达模式下导致 decode token 饥饿。

结论：如果你的服务基础设施将 prefill 和 decode 分离为无法共享 batch 的不同阶段，那么你将白白浪费 30-70% 的 GPU 吞吐量。支持 chunked prefill 的持续批处理 (Continuous batching) 不仅仅是一项优化 —— 它是高负载下稳定服务的正确性要求。

优先级队列：三层模式

并非所有推理请求都值得同等对待。在生产系统中出现的标准模式使用三个优先级层级：

第一层 — 交互式（延迟敏感）：聊天回复、实时补全、流式 UI。目标：首个 token 生成时间（TTFT）在 500ms 以下。这些请求应抢占低优先级任务。

第二层 — 标准（平衡）：具有合理 SLA 的 API 调用、后台功能生成、搜索增强。目标：端到端完成时间在 10 秒以内。可以容忍短暂排队。

第三层 — 批处理（吞吐量优化）：批量分类、数据集标注、离线摘要。目标：最大化单位成本的 token 产出。可以等待几分钟或几小时。

实现的挑战在于抢占（preemption）。当第一层请求到达且 GPU 正全力处理第三层任务时，你需要逐出（evict）低优先级的序列。这意味着保存它们的 KV 缓存状态（存入 CPU 内存或丢弃以供稍后重新计算），并立即开始高优先级的预填充（prefill）。

vLLM 0.9+ 支持连续优先级编号，高优先级请求可以抢占活动批次中的低优先级请求。但仅靠调度系统是不够的 —— 你还需要一个外部准入控制器（admission controller），用于：

加载中…