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），用于：

• 根据用户上下文（而非仅仅是请求元数据）分配优先级
• 实施分层限流，以防止优先级通胀
• 对来自同一用户的重复请求降低优先级（第一个请求：优先级 0，后续：1, 2, 3...），以防止单个用户霸占队列

关键的设计洞察：保持后端队列简短。目标是推理引擎内部队列中的待处理请求少于 3 个。你的准入控制器应该在你可以完全控制排序的上游队列中持有请求，而不是将它们推送到难以或无法重新排序的后端。

准入控制：你的系统所缺失的阀门

大多数生产级 LLM 部署都有负载均衡器和推理引擎。它们缺失的是准入控制器 —— 这个组件位于两者之间，负责回答：“这个请求现在应该进入系统，还是应该等待？”

如果没有准入控制，你会遇到一种直到灾难发生时才被察觉的故障模式。随着负载增加，推理引擎接受所有传入请求，KV 缓存内存填满，系统开始逐出并重新计算缓存状态，吞吐量下降，延迟飙升，系统进入一种死循环（death spiral），即它在缓存管理上花费的时间比实际推理还要多。

有效的 LLM 推理准入控制监控两个信号：

Token 生成速度：如果后端每个序列每秒生成的 token 少于 7 个（大约每个 token 150ms），则停止接纳新请求。这是系统过载最可靠的单一指标。

后端队列深度：从推理引擎的指标端点（例如 vLLM 的 Prometheus /metrics）获取此数据。当它超过你的目标值（通常为 2-3 个请求）时，在准入控制器的队列中截留新到达的请求。

反馈循环如下：

1. 请求到达准入控制器
2. 检查后端队列深度和 token 生成速度
3. 如果两者都在阈值内，则转发给推理引擎
4. 如果其中之一超过阈值，则在上游队列中持有
5. 持续轮询后端指标，并在容量释放时释放持有的请求

对于多租户系统，在准入控制器级别增加按租户的公平队列。跨租户队列的轮询（Round-robin）可确保没有单个租户能够垄断推理能力，即使他们的请求速率是其他人的 10 倍。

容量规划：防止意外的数学计算

这是大多数团队都会跳过的容量规划计算：

第一步 — 估算每日 token 消耗量：

• 每日请求数 × 每个请求的平均 token 数（输入 + 输出）
• 示例：100K 请求/天 × 1,500 平均 tokens = 1.5 亿 tokens/天

第二步 — 转换为 GPU 秒：

• 测量系统在实际负载下（而非基准测试条件下）持续的每秒每 GPU 的 token 产出
• 示例：200 tokens/秒/GPU → 1.5 亿 / 200 = 750,000 GPU 秒 = 约 208 GPU 小时/天

第三步 — 应用突发性乘数：

• 流量永远不是均匀的。高峰时段的负载通常是平均负载的 3-5 倍。
• 如果你按平均负载进行配置，在高峰期你将不得不排队（或丢弃）请求。
• 乘以你的峰均比：208 × 4 = 需要 832 GPU 小时的峰值容量

第四步 — 加计 KV 缓存税：

• 每个并发序列持有的 KV 缓存内存与（层数 × 隐藏维度 × 序列长度）成正比
• 对于一个拥有 80 层的 70B 参数模型，每个上下文长度为 2K 的活动序列大约消耗 2.5 GB 的 KV 缓存
• 如果你的 GPU 有 80GB，仅 KV 缓存就将你限制在约 30 个并发序列 —— 无论计算能力是否充足

KV 缓存约束使得 LLM 容量规划与受 CPU 限制的服务有着本质区别。你不能简单地“增加更多计算能力”。内存是瓶颈，并且它随着并发量 × 序列长度线性扩展。

教科书没告诉你的事

经典的排队论假设你知道（或可以估计）服务时间的分布。LLM 推理打破了这一假设：在请求完成之前，你无法真正知道它会生成多少个 token。输出长度的分布取决于提示词（prompt）、采样参数、系统提示词以及随机采样（temperature > 0）。

这意味着像“短作业优先（SJF）能最小化平均等待时间”这样的标准结论仅部分适用。你可以通过优先处理输入提示词较短的请求来近似实现 SJF（因为较短的提示词与较短的输出之间存在弱相关性），但预测误差非常大，以至于你经常会调度一个“短”任务，结果它却变成了一个 4,000 token 的生成任务。

更实用的方法承认了这种不确定性：

• 投机性准入 (Speculative admission)：假设平均输出长度来接纳请求，但为可能出现的更长输出预留容量。如果 KV 缓存压力超过阈值，则抢占运行时间最长的序列。
• 输出长度提示 (Output-length hints)：允许 API 调用者指定 max_tokens 作为调度暗示。即使他们设置的值高于实际需求，它也能为容量规划提供一个上限。
• 经验服务时间分布 (Empirical service time distributions)：根据生产流量，为每个端点、每个模型构建实际输出长度的直方图。使用这些分布（而非假设）作为排队模型的参数。

做得出色的团队会将他们的推理基础设施视为分组交换网络（packet-switched network），而不是传统的 Web 服务。Token 就是数据包，GPU 迭代就是时隙，KV 缓存就是缓冲区内存。就像在网络领域一样，有趣的问题不在于稳态，而在于当你对流量模式的假设不再成立时会发生什么。

开始行动

如果你正在生产环境中运行 LLM 推理，却还没考虑过排队论，以下是最小可行性改进方案：

1. 测量 token 吞吐量，而非请求吞吐量。将你的主要容量指标从每秒请求数（RPS）更改为每秒 token 数（TPS）。这一改变将揭示你当前监控中忽略的不平衡问题。

2. 添加上游队列。不要直接将请求推送到推理引擎。将它们保存在你控制的队列中，并根据后端的健康信号释放它们。

3. 启用分块预填充 (Chunked prefill)。如果你的推理框架支持（如 vLLM、TensorRT-LLM），请开启它。通过混合预填充和解码 token 带来的吞吐量提升通常在 30-50% 之间。

4. 按 token 路由，而非按请求路由。更新你的负载均衡器，根据预估的 token 数量而非请求数量来加权路由决策。

这四项改变不会让你成为排队论专家，但它们能防止最常见的失效模式：即系统在请求层面看起来很健康，但在 token 层面却在悄悄恶化。