Inference LLM Scheduling

基于调度的推理优化

负载均衡与公平性的处理

Posted by Sirin on November 28, 2025

关于调度：我们在做什么

​ 在前面的博客中，我们讲解了关于推理优化的一些技术和文章。本文将继续针对调度这一专题，介绍相关的工作内容。对于LLM的推理服务中，调度主要关心的目标有两个，一个是负载均衡，即公平性；一个是缓存复用/降低延迟，即局部性/效率性。Virtual Token Counter这一技术，就是公平性一极的工作；SGLang提出的Prefix Longest Match，就是局部性一极的工作。Preble和DLPM这两篇文章，就是为了权衡公平性和局部性而提出的调度框架，Preble对于公平性的衡量，是保证不同复用程度的请求能够得到相应比例的服务；而DLPM则是从每个客户端所能获取的服务量角度来衡量公平性，并使用一个超参数来控制在公平性和局部性的权衡程度。

​ 下面将讲解几个同样是基于调度来提升LLM推理服务性能的文章：

  • 《Fast Distributed Inference Serving for Large Language Models》：提出的FastServe系统旨在通过调度来优化请求的排队延迟，弥补FCFS排队的不足。
  • 《Llumnix: Dynamic Scheduling for Large Language Model Serving》：提出的Llumnix系统旨在服务运行时引入请求重调度机制，即将请求从一个模型实例转移到另一个实例进行处理。
  • 《Efficient LLM Scheduling by Learning to Rank》：通过输出长度的相对排名来预测负载水平从而实现短工作优先，降低延迟
  • 《Don’t Stop Me Now: Embedding Based Scheduling for LLMs》: 基于嵌入进行输出长度预测的Shortes-Job-First调度策略。
  • 《Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs》：在内存受限的场景下，如何提高GPU利用率并实现负载均衡？

FastServe系统

​ 在真实负载（如ShareGPT, Alpaca）中，任务的输入/输出长度分布是长尾的，即大部分任务较短，但少数任务非常长。在这种负载下，排队延迟占据了总延迟的90%。因此，优化执行时间收效甚微，优化排队延迟才是关键。FastServe系统的提出，就是旨在解决推理服务中的两个核心挑战：

  1. 调度挑战：如何在不知道任务总大小（输出长度）的情况下，设计一个抢占式调度器来最小化平均延迟和尾延迟，同时避免队头阻塞和饥饿问题？
  2. 内存挑战：抢占式调度会引入大量中间状态（KV缓存），如何在不超出有限GPU内存的前提下，高效管理这些状态，避免其成为新的性能瓶颈？

该方法的核心思想是在每次生成一个token后就进行抢占决策，主要包括三个组件：

1. Skip-Join Multi-Level Feedback Queue

传统的MLFQ用于解决队头阻塞的问题，所有的新任务都是先加入最高优先级队列，如果任务在分配的时间片内未完成，则降级到低优先级队列。但对于LLM来说，推理时第一次迭代(Prefill)的计算量是远大于后续迭代(Decode)的，对于一个长Prompt请求，很有可能第一次迭代就用完了时间片。如果此时抢占该请求，就会导致KV Cache的浪费；如果不抢占，就违背了MLFQ的初衷，造成队头阻塞。

传统MLFQ的问题在于假设任务信息是未知的，于是FastServe的设计中，考虑了输入长处(这决定了第一次迭代的时间)：

  1. 跳过加入：当一个新任务到达时，系统根据其预分析的第一次迭代时间，直接将其分配到一个合适的优先级队列中。这个队列的时间片 q_i 需要满足 q_i >= t_init（第一次迭代时间）。这样，任务在第一次迭代中就不会因为时间片用完而被抢占。
  2. 降级：在后续的Decode迭代中，如果一个任务用完了当前队列的时间片，则根据其下一次迭代的预估时间，被降级到更低的优先级队列。
  3. 防饥饿：为了防止长任务永远得不到执行，调度器会定期检查等待时间过长的任务，并将其提升到最高优先级队列。

这种设计使得短任务（输入和输出都短）能够快速得到服务，长任务也不会过度阻塞系统，从而在平均延迟和公平性之间取得了良好平衡。

2. Proactive KV Cache Management

抢占式调度会导致很多已开始但未完成的任务的KV缓存保留在GPU内存中，如果这类任务过多，就会导致显存耗尽。朴素方案要么推迟新任务(退化为FCFS出现队头阻塞)，要么杀死低优先级任务(计算浪费)。FastServe针对于此提出了主动交换的解决方案：

  1. 扩展内存空间：将KV缓存的管理空间从GPU内存扩展到主机内存。
  2. 主动而非被动：不是等需要内存时才去交换，而是提前预测哪些任务的KV缓存即将被使用，哪些可以被换出。
  3. 关键创新：重叠计算与通信：
    • 系统在GPU正在执行当前一批任务的同时，在后台将下一批可能需要任务的KV缓存从主机内存换入GPU，并将当前不急需任务的KV缓存换出到主机内存。
    • 这样，数据传输的延迟就被隐藏在了计算时间之下，对用户感知的延迟影响极小。
  4. 交换顺序：使用预估下次调度时间（ENST） 来决定交换顺序。ENST综合考虑了任务的优先级(更高优先级任务所消耗的时间)和防饥饿机制(还有多长时间就会被Promote)，确保最快要被调度的任务其KV缓存优先留在GPU内存中。
  5. 应对突发任务：为应对突发的高优先级新任务，系统会预留一部分空闲的KV缓存槽位，确保它们能立即被执行，而无需等待交换。

LLumnix系统

对于生产级别的LLM服务，通常由多个模型实例来共同承担，传统的服务调度策略无法解决在多个实例之间进行请求调度的问题。

  • 问题来源：负载的异构性和不可预知性

    不同应用场景导致请求的输入输出长度和预期延迟差异巨大，且一个请求要生成的内容量也是事前未可知的。

  • 导致的问题：隔离性差；内存碎片化；缺乏优先级支持 由于不可预知性，某些请求可能会抢占同批次其他请求的资源，导致性能下降；负载均衡下的调度会引发内存碎片问题；现有的调度系统无法满足多样化的服务等级目标SLO

  • 根本局限性：一次调度，终身绑定 一个请求被调度到负载上运行时，就无法再调整，使得系统无法在运行时对上述问题进行处理。

Llumnix的核心思想是借鉴操作系统在多核CPU上进行进程上下文切换的理念，为LLM服务引入运行时请求重调度机制。简单来说，就是允许将一个正在执行的请求及其状态（KV缓存）从一个模型实例迁移到另一个实例。

1. Live Migration of LLM requests

Live Migration的最大挑战在于如何高效转移巨大的KV缓存状态，而不造成长时间的服务停顿。解决这一问题依赖于KV Cache的关键特性：KV缓存是append-only的。一旦一个token的KV值被计算并存储，在后续生成中就不会再被修改。

Llumnix采用了一种多阶段、pipeline化的机制来重叠计算和通信，其迁移流程如下：

  1. Stage 0：source instance开始将目前已生成的KV缓存块拷贝到destination instance，同时继续正常执行该请求，生成新的token。
  2. 阶段1：当阶段0的拷贝完成后，source instance将在阶段0期间新生成的KV缓存块拷贝到destination，同时继续执行生成后续token。
  3. 重复此过程，直到需要拷贝的“增量”KV缓存块数量变得很少。
  4. 最后阶段：source instance暂停该请求的计算，将最后剩余的少量KV缓存块拷贝到destination instance。这个短暂的暂停期就是请求的停机时间。迁移完成后，请求恢复执行。

为了保证在异步并发环境下的正确性，Llumnix在source instance和destination instance之间设计了相应的handshake协议，用于在每阶段前检查destination instance的内存是否充足、请求是否已完成或被抢占等，确保迁移安全。

2. 分布式调度架构

Llumnix采用两级分布式架构：

  1. 全局调度器 负责集群级别的决策，不关注单个请求，只关注由局部调度器上报的实例内存负载信息，基于负载信息进行三种决策：分发新请求；触发实例之间的迁移(只指定source&distination，不指定请求)；控制实例进行auto-scaling
  2. 局部调度器Llumlet 每个模型实例都有一个相应的Llumlet，管理本地的请求队列和批处理任务，根据调度策略来计算相应的Vitural Usage。当被全局调度器设置为source instance时，执行迁移操作。

3. 同一动态调度策略: Virtual Usage

将不同的调度目标（负载均衡、去碎片化、优先级、Auto-Scaling）统一到一个简单的负载均衡框架中。其核心思想是为队列中的请求赋予一个虚拟用量，用这一指标来指导负载均衡器采用何种policy。

Virtual Usage是根据请求所处的状态和系统的调度Policy，来计算获取的一项指标数据，其计算规则如下：

  • 普通情况：虚拟用量 = 物理内存用量。目标是常规的负载均衡。
  • 排队中的请求：虚拟用量 = 该请求启动时的内存需求。这使得该实例看起来负载很重，从而触发迁移（将其他请求移走），为这个排队请求腾出空间，实现去碎片化。
  • 高优先级请求：虚拟用量 = 请求启动时的物理内存用量 + 预留空间。这使得实例看起来负载更重，从而促使负载均衡器将其他普通请求迁移走，为高优先级请求保留资源，减少干扰，实现优先级隔离。
  • 缩容中的实例：加入一个虚拟用量无穷大的空请求。这使得该实例看起来极度过载，从而触发所有请求被迅速迁移走，实现快速排空。

基于Vitural Usage的调度决策有：

  • 分发：将新请求发给空闲度最高的实例。空闲度 = (实例总内存 - 所有请求Virtual Usage之和) / Batch_Size。
  • 迁移：周期性检查，将空闲度最低的实例作为源，空闲度最高的实例作为目标，配对触发迁移。
  • 自动扩缩容：根据集群平均空闲度结合相应的人工设定的阈值来决定是否增加或终止实例。

LTR方法

本文针对的问题仍然是在LLM推理服务中的队头阻塞问题，即长请求可能会阻塞短请求。理论上Shortest-Job-First或者Shortest-Remaining-Time-First能够有效解决这一问题，但由于请求负载的不可预知性，这些算法难以应用。

本文的Insight在于：虽然准确预测每个请求的生成长度很困难，但预测一批请求中生成长度的相对顺序是可行的。从而可以实现近似SJF/SRTF的调度方式。

LTR方法中训练了一个轻量级的OPT模型并在最后增加了一个线性层用于输出排序分数，分数越大则表示输出长度越长。每个Prompt的真实标签被设置为其输出在所有Batch中的长度排序，通过ListMLE列表排序损失来最大化真实排名的似然，使得分数的相对顺序符合真实生成长度的排序。

此外，LTR还额外设计了优先级机制来防止饥饿，这借鉴了MLFQ的设计。请求的优先级由两部分组成，首先是最基本的优先级队列，每次构建Running Batch时会先处理高优先级的请求。对于优先级相同的请求，再按照预测分数进行排序。每次请求未被选中时，其饥饿计数器会增加，达到阈值后，会提升其优先级并获得执行时间片。请求被选中时，则会消耗其执行时间片并清空饥饿计数。当优先级时间片消耗完之后，请求的优先级会降级。具体的伪代码如下：

B = []  # 当前执行批次

for r in S:
    if not BatchIsFull(B):  # 批次未满（内存/批量限制）
        B.append(r)  # 加入执行批次
        r.StarvationCount = 0  # 重置饥饿计数（因为被选中执行）
        r.Quantum -= 1  # 消耗优先级时间片
    else:
        # 批次已满，该请求本次无法执行
        r.StarvationCount += 1  # 增加饥饿计数
        
        # 检查是否达到饥饿阈值
        if r.StarvationCount >= StarvationThreshold:
            Promote(r.Priority)  # 提升优先级
            r.StarvationCount = 0  # 重置饥饿计数
            r.Quantum = PriorityQuantum  # 分配新的时间片
            
    # 检查优先级时间片是否用完
    if r.Priority > 0 and r.Quantum <= 0:
        Demote(r.Priority)  # 降低优先级

Trail方法

对于LLM推理服务系统，其核心目标是通过降低请求的平均延迟和首token时间，从而提升用户体验。目前方法的矛盾在于：

  • 理想的调度策略（例如最短剩余处理时间SRPT）需要知道请求的大小，但请求的输出长度在请求完成之前是未知的。
  • 抢占调度的内存开销巨大，一旦请求被抢占，其KV缓存需要保留在GPU内存中，直到被再次调度。

本文的研究问题如下：

  1. 如何实现低开销、高精度的输出长度预测？
  2. 如何在考虑内存开销的前提下，实现有效的抢占式调度？

Trail方法的核心在于，其发现了LLM内部Transformer层的隐藏状态(Embeddings)不仅包含生成当前令牌的信息，还隐含地编码了序列的未来信息，包括其可能的长度。因此，可以“回收”这些本已计算好的Embeddings，用于预测任务。

1. 基于Embedding的迭代级输出长度预测

a) 问题建模

将输出长度预测建模为一个分类问题。将可能的剩余tokens数量划分为 k 个区间（bin）。例如，论文中将0-512划分为10个等宽区间。任务就是：给定一个嵌入向量，预测剩余tokens数量落在哪个区间。

b) 预测器训练

  1. 数据收集：选择一个目标LLM（如LLaMA-3-8B）和一个数据集（如Alpaca）。在模型推理（包括预填充和解码）时，从所有Transformer层提取每个token的embedding。同时记录每个时间点的真实剩余tokens数。这样就构成了训练数据对：(embedding向量, 剩余token数所属的区间)。
  2. 层选择：论文发现，并非所有层对长度预测都同样有效。通过实验发现中间层的预测准确率最高。因此，后续工作聚焦于从单一最佳层提取嵌入，以简化系统设计。使用一个FC+ReLu+FC的轻量级MLP分类器来预测输出长度的概率分布。

c) 在线推理与动态精炼

  1. 初始预测：在Prefill完成后，对输入的所有token embedding进行平均池化，得到一个综合的提示嵌入并输入输入预测器，得到初始的输出长度预测 r。
  2. 迭代精炼：Decode阶段，每生成一个新的token，就从选定的中间层提取该token的embedding输入预测器，得到一个新的、基于当前上下文的对剩余长度的预测。由于单步预测可能存在波动，Trail采用贝叶斯平滑：维护一个当前对剩余长度分布的先验，每得到一个新的预测，就根据贝叶斯规则更新后验。此外，还引入了一个状态转移矩阵，其假设是剩余长度只会随着生成的进行而减少（即只能从一个bin转移到相邻的更小的bin），这使得预测随着生成的进行越来越平滑和准确。

2. 有限抢占的调度策略

Trail的调度策略核心是Shortest Predicted Remaining Processing Time with Limited Preemption，即调度器始终优先执行预测剩余处理时间最短的请求。

具体的是线上，Trail调度器为每个请求设定一个抢占窗口。

  • 定义一个参数 c（例如0.8）
  • 对于一个初始预测长度为 r 的请求，只有在它已经生成的令牌数 a 小于 c * r 时，才允许被其他请求抢占。
  • 一旦 a >= c * r，该请求就变为不可抢占，必须一直执行直到完成。

这种策略的目的就是为了缓解抢占调度会导致的KV缓存占用情况。

早期：一个请求刚执行时，其KV缓存很小，即使被抢占，占用的内存也很少。此时允许抢占，可以让短请求快速插队，显著降低平均延迟。

后期：一个请求已经生成了很多令牌，其KV缓存已经很大。如果此时被抢占，它会长期占用大量内存，可能导致内存溢出，或阻止新请求进入。此时禁止抢占，让它尽快完成并释放内存，从系统整体来看是更优的。

因此，整个Trail调度方法的步骤可以总结如下：

  1. 接收与初始化：用户请求进入请求池。系统使用一个轻量级BERT模型，仅基于输入提示对请求的输出长度进行初始预测，并据此进行初步排序。
  2. 调度与执行：调度器使用有限抢占的SPRPT策略，从请求池中选择一批预测剩余时间最短的请求，送入GPU执行一个Decode步骤(生成一个token)。执行请求的数量受GPU内存限制。
  3. 预测精炼：每生成一个token后，系统从LLM的指定中间层回收其embedding表示，并将其送入轻量级预测器，更新该请求的剩余长度预测。
  4. 反馈与再调度：更新后的预测立即反馈给调度器。调度器根据最新的预测结果，重新评估所有请求的优先级，并决定在下一个迭代中是继续执行当前请求，还是抢占它并换上一个预测更短的请求。

LARRY and SAL方法

本文主要针对队头阻塞问题和KV缓存引发的内存溢出问题进行调度策略的设计，从两大角度来研究

  1. 引擎级调度：何时分发请求进行执行？何时抢占请求？如何管理KV Cache?
  2. 负载均衡调度：如何将请求分配到多个服务器（数据并行）？如何考虑不同请求的资源需求？

前者的目标是在内存受限的条件下，最大化GPU利用率，降低延迟；后者的目标是在多服务器环境下平衡负载。一个是效率性，一个是公平性。

1. LARRY引擎级调度

该方法的核心思想是在内存压力大的时候，优先调度内存需求小的请求；同时避免长请求饥饿，考虑等待时间。其核心就是一条公式： \(score(request) = \alpha \times waitTime(request)-queueLen\times memoryCost(request)\) 其中，$\alpha$是一个权重超参数，用于控制等待时间和内存需求的权衡；$waitTime$代表请求入队后的等待时间；$queueLen$表示当前队列长度；$memoryCost$表示基于Prompt长度预估的请求的内存消耗。评分越低，表示请求的优先级越低。

$\alpha$设置的越大，能够有效减少长请求的尾延迟；$\alpha$设置的越小，系统越倾向于处于短请求。

2. SAL均衡负载器

该方法的核心思想就是在对请求进行路由时，同时考虑服务器的内存余量和排队token数，避免将大请求发送到资源紧张的服务器。其核心公式是 \(load(s, r)=max(\beta \times (memeryCost(r)-freeMem(s)),\frac{queuedTokens(s,r)}{maxTokensPerBatch})\) 前一部分表示服务器$s$需要经过多长时间才能为请求$r$保留足够的内存，如果括号内的项计算出来为0或者负数，则表示预留空间足够，无需等待。$\beta$为根据历史输入输出估计的内存释放速率，假设历史平均输入输出的tokens数分别为$\mu_{in}, \mu_{out}$，则$\beta = \frac{\mu_{in}+\mu_{out}}{\mu_{out}}$，其中分子近似代表一个请求的平均总序列长度，分母则表示请求在Decode阶段的平均序列长度。

第二部分估计的是 请求$r$要等待多少个批次(按每个批次的平均处理时间映射为等待时间)，服务器$s$才能处理完其Prefill请求。其中$queuedTokens(s,r)$表示服务器 $s$上当前排队的所有请求的Prefill token总数加上新请求$r$自身的Prefill token数。

最终取max是基于短板效应，因为一个请求的启动，需要同时满足两个约束条件：

  1. 内存约束：服务器必须有足够的内存来放置其KV Cache(第一部分)
  2. 队列约束：必须排队完成后，GPU才能开始计算其Prefill

最终SAL将请求路由到$load(s, r)$最小的服务器上。

 Limitations分析

FastServe方法缺陷

FastServe没有对于抢占进行限制，采用主动交换KV Cache的方法会引起带宽竞争问题。此外，FastServe这种主动控制KV Cache交换的操作需要大量额外的实现才能适配到vLLM, SGLang等推理框架中。无法作为一个drop-in replacement去使用。

LLumnix方法缺陷

Llumnix的缺陷与FastServe同样，其迁移和实现的成本过高。

LTR方法缺陷

普适性有问题，因为需要预先按照特定数据集来训练，无法适应现实场景下的分布偏移，容易出现预测准度偏差，需要周期性重训练。

Trail方法缺陷

  1. 普适性问题：仅对于LLaMA-3-8B与Alpaca进行了分析，其参数设置缺乏理论指导，不具有普适性意义。
  2. 脆弱性问题：整个调度策略高度依赖于这一预测，随着请求模式的变化，轻量模型无法适应，预测的失准问题会导致策略失效。
  3. 公平性问题：短请求的持续到达会导致较长的请求始终排队等待。
  4. 权限问题：很多情况下，模型中间层的embedding是无法获取的。

LARRY and SAL方法

该方法只基于了vLLM框架进行了实现，并没有考虑到SGLang这种基于局部性复用的调度思想。

CATALOG
    FEATURED TAGS
    Tools Lecture CV DL Go LeetCode LLM projectDesign Inference Linux