大规模语言模型（LLMs）的推理服务 是释放其在人们日常生活中潜力的关键。然而，当前的LLM服务在效率上仍面临严峻挑战，因为请求的资源需求和延迟要求本质上具有异构性和不可预测性——这源于LLM应用的多样性及其动态执行特性。现有系统在处理这些特征时存在根本性局限，导致严重的排队延迟、尾延迟恶化以及服务级别目标（SLO）违规等问题。

为此，我们提出了Llumnix ——一种针对LLM服务的系统，它通过跨多个模型实例的运行时动态重调度 来应对异构且不可预测的请求。与现代操作系统中跨CPU核心的上下文切换类似，Llumnix通过重调度优化负载均衡与隔离性，缓解资源碎片化，并差异化处理请求优先级与SLO。Llumnix通过一种高效且可扩展的请求实时迁移机制 实现重调度，该机制能够迁移请求及其内存状态，并在动态调度策略中统一处理多种重调度场景。评估表明，与现有最先进的LLM服务系统相比，Llumnix将尾延迟降低了一个数量级，高优先级请求加速达1.5倍，且在保持相似尾延迟的情况下实现高达36%的成本节约。Llumnix已开源，项目地址：https://github.com/AlibabaPAI/llumnix。

1 引言

以GPT系列为代表的大规模语言模型（LLMs）正将生成式人工智能推向前所未有的高度。这些模型展现出 人类水平的生成能力 ，正被快速应用于广泛领域，不断激发对未来应用的丰富想象，并有望深刻改变人们的日常生活和工作方式。
LLM的推理服务是LLM驱动型服务的核心，已成为数据中心的关键负载。此类服务通常由部署在GPU集群上的多个LLM实例支撑。系统包含调度器和推理引擎两部分：请求首先由调度器分配至某个模型服务实例，随后在该实例内部的推理引擎中执行。为了提高吞吐量和成本效益，请求通常会在每个实例中以**批处理（batch）**形式执行。

我们观察到LLM的独特特性，这要求其服务基础设施采用全新的设计哲学。首先是工作负载异构性。LLM通过尽可能学习多领域知识而具备通用性，人们可以在完全不同的场景中查询同一LLM，甚至基于LLM构建定制化应用以满足多样化需求——所有这些仅需提供特定上下文的输入（即提示词prompt）[15]。这种通用性与应用多样性导致推理请求在输入长度、输出长度、预期延迟等方面呈现显著异构性。例如，长文本摘要任务可能涉及极长的输入长度，而快速返回首个token（单词）的延迟对用户体验至关重要[38]。
要在多个实例上处理异构且不可预测的工作负载。这种行为与传统深度神经网络（DNN）模型存在根本性差异——传统DNN的请求通常是同构的，执行过程为单次、无状态且确定性。相比之下，我们发现LLM更类似于现代操作系统，需在多个核心上管理具有动态工作集和不同优先级的进程。此类系统的管理目标复杂多样，远超现有推理服务系统的设计范畴。

尽管已有针对LLM优化的推理引擎（如提高单实例吞吐量）[34,46,67]，但跨实例的请求调度 却鲜有关注。当前的通用做法仍是沿用传统DNN时代遗留的调度系统或策略[4,28,35,47,53]。这种明显的差距导致在以下关键方面面临挑战，而这些挑战对多租户环境和在线服务至关重要：
隔离性 ：由于请求的内存消耗不可预测，系统难以实现性能隔离。内存争用会导致性能干扰，甚至引发批次中某些请求被抢占[34]，造成尾延迟剧烈波动和服务级别目标（SLO）违规，显著损害用户体验。
碎片化 ：请求长度与内存需求的差异必然导致实例间的内存碎片化，这会引发调度目标的冲突。运行中的请求倾向于通过负载均衡减少抢占和干扰，但负载均衡同时会加剧实例间空闲内存的碎片化。这种碎片化会导致新请求因需要单实例大块内存（如长输入序列）而长时间排队。面对请求到达时间和长度的不可预测性，调度器难以调和此类冲突。
优先级 ：不同应用场景的请求天然存在延迟目标差异。在线聊天机器人[6,8]等交互式应用对SLO要求严格，而离线任务（如评估[51]、评分[36]、数据处理[43]）对延迟不敏感。这种差异也源于商业需求——通过分级服务（如ChatGPT Plus[2]）提升LLM盈利空间。然而，现有LLM推理系统[34,67]通常平等对待所有请求，无法区分优先级，难以满足不同延迟目标。

为此，我们提出Llumnix ——一种通过跨模型实例的运行时重调度 解决上述挑战的LLM调度系统。类比操作系统中CPU核心间的进程上下文切换，Llumnix通过动态重调度应对工作负载的不可预测性，而非依赖一次性请求分发解决所有复杂调度权衡。Llumnix的重调度机制服务于多重目标（图1）：

负载均衡 ：减少请求抢占与干扰；
去碎片化 ：缓解长输入请求的排队延迟；
优先级调度 ：通过增强隔离性加速高优先级请求；
弹性伸缩 ：快速填充或释放实例资源。
Llumnix通过一种高效且可扩展的实时迁移机制实现请求重调度，该机制能够在实例间迁移请求及其GPU内存状态（如图1所示）。直接重调度方法可能对被迁移的请求造成显著停机时间，尤其是处理长序列时。相比之下，Llumnix通过精心协调计算与内存传输，将停机时间降至接近零，且与序列长度无关，从而隐藏迁移开销。

为充分利用迁移带来的调度灵活性，Llumnix采用分布式调度架构，支持高可扩展的持续重调度。在此架构下，Llumnix进一步设计了一种动态调度策略，以统一方式优雅处理不同目标的重调度场景。这种统一性通过“虚拟使用量”（virtual usage）概念实现：Llumnix只需为不同场景下的请求定义GPU内存虚拟使用量的规则，随后基于虚拟使用量实施简单负载均衡策略即可。

实现与评估
我们已将Llumnix实现为推理引擎之上的调度层，目前支持以vLLM[34]为代表的底层引擎。在16-GPU集群上的真实负载测试表明，与现有先进调度器INFaaS[53]相比，Llumnix将P99首token延迟提升高达15倍，P99单token生成延迟提升达2倍。同时，Llumnix使高优先级请求加速1.5倍，并在保持相似尾延迟的情况下实现36%的成本节约。

本文贡献总结
• 揭示了LLM服务的独特特性与调度挑战，提出隔离性、去碎片化和优先级等新调度目标。
• 提出请求重调度作为核心手段，并通过高效的请求及其GPU内存状态迁移机制实现目标。
• 设计分布式调度架构与动态策略，利用迁移统一实现多目标调度。
• 实现并评估Llumnix，验证其相对于现有推理服务系统的优势。

2 背景

LLM的应用多样性。近期LLM正逐渐演变为任务无关型（task-agnostic），即同一模型可通过提供特定上下文的输入（即“提示词”）适应各类任务。这一特性源于模型与数据集规模的持续扩大，以及少样本学习（few-shot learning）[14]等先进预训练方法。任务无关型模型催生了多样化应用，包括聊天机器人、搜索引擎、摘要生成、代码编写、AI助手及AI代理等。

这些多样化应用导致服务请求的需求差异显著。一个重要维度是序列长度。LLM正竞相支持更长的序列长度——例如，2023年3月至11月期间，GPT系列的最大序列长度从32k（GPT-4[49]）扩展至128k（GPT-4 Turbo[50]）。我们预计这一趋势将持续，因更广泛的应用需依赖长序列支持。以直观任务为例：文章摘要需足够长的输入长度，而文章生成则需要长输出长度。

另一维度是预期延迟。实际案例中，OpenAI推出订阅计划ChatGPT Plus[2]，以提供更快的标准ChatGPT服务响应。通常，不同应用与场景天然存在紧迫性差异。例如，个人助手等高交互性应用对延迟的要求，远高于文章摘要等任务。

自回归生成。当前LLM的推理过程是自回归的：模型迭代接受输入序列及所有已生成的输出token，逐次生成下一个token，直至生成“序列结束”（EOS）标记。生成首个token的阶段与后续生成新token的阶段通常称为预填充（prefill）和解码（decode）。LLM服务通常以流式（streaming）方式返回生成结果，因此预填充延迟与解码延迟均直接影响用户体验。

• 预填充延迟决定用户开始接收响应的等待时间，可能主要受排队延迟主导。
• 解码延迟决定后续token的连续接收速度。

在自回归过程中，每个token的中间结果（注意力操作[59]中使用的键值张量）会被后续所有token的生成过程复用。因此，推理引擎通常将这些状态存储于GPU内存中，称为KV缓存[52]。
批处理与内存管理
当前先进的推理引擎采用连续批处理技术（continuous batching）[34,67]，以应对请求序列长度差异大和动态到达的挑战。具体而言，新请求或已完成的请求可立即加入或退出当前运行批次，无需等待所有运行中的请求完成。然而，批处理也引发了对KV缓存内存管理的关注。由于KV缓存的内存需求无法提前预知，若预先为最大可能长度保留内存，将显著限制批处理规模及其收益。例如，LLaMA-2-13B[58]模型支持最长4k的序列长度，单个请求对应的KV缓存占用达3.2GB；而当前GPU的内存容量仅为数十GB，更不用说还需存储模型权重（如LLaMA-2-13B需26GB）。因此，近期研究（vLLM[34]）提出通过动态内存分配管理KV缓存以提升批处理规模和吞吐量，其核心技术为分页式注意力机制（PagedAttention）：KV缓存张量按需动态分配块（block）存储，随缓存增长灵活扩展。

图2展示了使用连续批处理与动态内存分配的示例。系统根据空闲内存块选择运行中的请求，因此在迭代N时，因内存不足存在一个排队请求（灰色）。下一迭代中，系统无法为运行中请求的新块分配内存，故需抢占某些正在运行的请求（蓝色请求），将其重新放回队列。

3 动机

我们通过LLM服务的以下关键特性，阐述Llumnix的设计动机。

不可预测的内存需求与抢占
采用动态内存分配时，由于内存需求不可预测，请求抢占（preemption）不可避免，这会显著增加被抢占请求的延迟。图3展示了在A10 GPU上使用vLLM服务LLaMA-7B模型的实验结果，负载为2,000个请求（基于泊松分布生成）。输入和输出长度遵循幂律分布，均值为256个token（细节见第6节）。我们控制请求速率（0.42请求/秒）以模拟中等内存负载（平均62%），同时因序列长度差异存在内存峰值。即使在该负载下，仍有8%的请求被抢占。

我们通过测量抢占导致的延迟惩罚（包括额外排队时间和重计算KV缓存的开销）量化抢占损失。图中展示了不同分位数的单token解码延迟（取请求所有解码迭代的平均值）。未使用端到端延迟，因其依赖迭代次数。观察发现：

• P99单token解码延迟显著劣于P50（3.8倍差距）；
• P99请求的抢占损失占比达70%；
• P99请求因两次抢占导致总损失达50秒，表明抢占会引发严重的服务停滞和用户体验下降。
  
  

请求间的性能干扰
我们还观察到，批次内的请求因GPU计算资源和内存带宽竞争而相互干扰。图4展示了LLaMA-7B（单GPU）和LLaMA-30B（4-GPU）在不同序列长度和批次大小下的单步解码耗时（X轴表示每个数据点的批次总token数）。解码速度随请求数量增加和干扰加剧而下降，相同序列长度下的性能差距最高达2.6倍。

内存碎片化
考虑到上述问题，将请求分散到多个实例上可减少抢占和干扰。然而，这种分散会导致集群的可用内存在实例间碎片化。此处的碎片化指外部碎片（即实例上未分配的内存）。动态分配技术（如PagedAttention[34]）通过逐块分配内存，可在解码阶段消除外部碎片。但预填充阶段仍面临显著外部碎片问题，因其需在单次分配中占用实例上的大量内存块，以容纳输入所有token的KV缓存。因此，外部碎片会导致新请求（尤其是长输入请求）的长时间排队延迟。

图5展示了四实例LLaMA-7B的实验结果，负载采用均值为256的输入/输出长度分布及速率为1.9请求/秒的泊松分布。我们实现了一种分散调度策略（将新请求分发至内存负载最低的实例以实现负载均衡）。通过展示集群总空闲内存块与各实例队列头部请求的内存需求对比，可体现碎片化问题。在大多数时间段内，集群总空闲内存足以容纳至少三个实例（有时全部）的排队请求，但请求仍因单实例空闲空间不足而排队，这既揭示了碎片化现象，也表明去碎片化对减少排队延迟的潜力。
请求的不同紧急程度与优先级
随着ChatGPT Plus等产品需求及LLM应用场景的多样化，我们预见更多具有差异化延迟敏感度的应用将涌现。然而，现有系统通常平等对待所有请求，导致延迟敏感型请求易受其他普通请求干扰（例如过度排队延迟或性能干扰）。这要求一种系统化方法，以区分LLM请求的优先级，从而满足各自的延迟目标。

机会：跨实例请求重调度
本文探索了当前LLM服务系统缺失的新维度：部署的多实例及其交互。一个直观思路是，当某一实例出现前述问题时，整个集群可能仍存在足够资源，可避免请求抢占、容纳新请求或缓解干扰。这是请求长度与内存负载在实例间差异化的自然结果。然而，现有系统无法利用其他实例的空闲空间，因为请求一旦被调度，在自回归执行期间会被绑定至同一实例。Llumnix通过统一请求调度组件与模型推理引擎，挖掘实例间细粒度协同的潜力。4 Llumnix设计

4.1 概述

Llumnix基于运行时跨模型实例重调度LLM推理请求的核心思想构建。Llumnix继承了现有先进系统中的连续批处理[67]和动态内存分配[34]技术以实现高吞吐量。除此之外，Llumnix通过请求重调度应对不可预测的工作负载动态，满足不同场景下的调度目标（如图1所示）。

首个目标是负载均衡（图1-a），旨在减少高负载实例上的请求抢占与干扰。尽管初始调度可考虑内存使用负载均衡，但由于输出长度不可预测，请求的最终内存需求在到达时未知，可能导致次优结果。重调度通过响应请求实际内存增长，补充了初始调度的不足。然而，如前所述，负载均衡可能加剧内存碎片化，并导致长输入请求的排队延迟增加。因此，Llumnix还通过重调度实现去碎片化（图1-b），即通过将请求迁移至其他实例，为当前实例腾出连续内存空间。尽管这两个目标存在权衡，但Llumnix通过重调度获得了更大的平衡空间。

另一目标是优先级调度（图1-c），即通过迁移共置请求以降低负载并避免干扰，从而为高优先级请求动态提供“专用”资源，而无需静态预留机器。最后，Llumnix在弹性伸缩期间重调度请求，例如排空待终止实例（图1-d）或快速填充新实例。

实现高动态重调度的挑战
考虑到请求上下文状态（即KV缓存）规模庞大，高效实现此类高动态重调度极具挑战。直接方案包括重新计算或复制被迁移请求的KV缓存，但这会导致高计算停滞和停机时间（解码成本的50倍以上，见§6.2）。此外，KV缓存状态随序列长度增长而扩大[50]，在上下文长度增长趋势下进一步限制调度灵活性。生成下一个token的高推理延迟会严重损害LLM服务的用户体验，从而阻碍请求重调度。

Llumnix通过实时迁移机制解决这一挑战：通过流水线化协调KV缓存复制与token生成计算，将停机时间降至可忽略水平（§4.2）。

架构与策略
为充分发挥迁移优势，Llumnix采用可扩展架构，结合全局与本地调度以分散调度决策和迁移操作，支持大规模持续重调度（§4.3）。在此架构下，我们进一步设计了一种基于虚拟使用量（virtual usage）概念的高效启发式调度策略，以统一方式抽象不同调度目标的需求（§4.4）。

4.2 LLM请求的实时迁移

请求的键值缓存（KV Cache）状态可能在重调度过程中引入显著的资源开销和服务停顿。Llumnix通过利用LLM推理的一个关键特性解决了这一挑战：KV缓存是仅追加的（append-only）。

LLM推理通过迭代拼接当前迭代的输出token与输入token，并将其作为下一次迭代的输入。在此过程中，推理引擎会将当前迭代计算的KV状态持续追加到缓存参数中，而先前迭代生成的参数始终保持不变。

Llumnix的实时迁移机制利用KV缓存的仅追加特性，将KV缓存的复制与解码计算流水线化。由于已生成的KV缓存不会被后续迭代修改，Llumnix能够安全地并行复制历史缓存块与新token的计算，从而实现重调度请求的近零停机时间，且停机时间恒定。如图6所示：

1. 阶段0：迁移启动时，源实例开始复制已完成迭代的KV缓存块，同时继续执行新迭代的计算。
2. 阶段1：当历史缓存复制完成后，源实例继续计算少量新迭代（即图6中的新增块），随后复制这些新生成的缓存。
3. 阶段N：最终，仅需为最后一次迭代的缓存复制暂停计算。此时，请求会从当前批次中移出（drain out），并复制剩余缓存块，此过程即为请求的停机时间。
   

由于复制速度远快于计算速度，新增缓存块数量通常极少，可在极短时间内完成复制。因此，请求的总停机时间仅取决于单次迭代缓存的复制耗时，与序列总长度无关，几乎可忽略不计。迁移完成后，请求在目标实例上恢复执行。

4.3 Llumnix的请求迁移机制

Llumnix的请求迁移方法借鉴了虚拟机（VM）实时迁移[17]的核心思想，即逐步缩减工作集以最小化停机时间。但与VM迁移不同，LLM服务无需追踪“脏页”（dirty page），因为其工作集（即KV缓存）是仅追加的，且在迁移过程中不会被修改。然而，LLM服务还面临额外挑战：
5. 内存不足风险：源实例和目标实例均持续处理请求，迁移过程中可能出现内存不足；
6. 请求提前完成：由于生成过程不可预测（如提前生成结束符EOS token）和持续批处理[67]，请求可能在迁移中途完成。

为应对这些异常情况并确保异步计算与内存复制的正确性，Llumnix通过细粒度的握手协作机制协调参与迁移的实例（图7）：

• 阶段前预分配：源实例在每阶段开始前，向目标实例发送预分配请求（含需迁移的块数量），确保目标实例有足够空间。若目标实例成功预留空间，则通知源实例继续；若失败，则中止迁移并清理状态。
• 阶段后校验：每阶段结束后，源实例检查被迁移请求是否已完成或被抢占。若已完成，则通知目标实例中止迁移并释放预留块；否则进入下一阶段。
• 异常处理：若源实例或目标实例在迁移过程中失效，另一方将主动中止迁移。
• 最终提交：所有阶段完成后，源实例释放本地块，并通知目标实例提交迁移结果、恢复请求执行。

4.3 分布式调度架构

实时迁移机制为LLM推理请求的运行时重调度提供了基础。然而，由于调度压力远高于传统调度器，实现完全动态调度仍非易事。具体而言，Llumnix需要持续跟踪并重调度集群中每一个运行中的请求，而非仅一次性分发新请求或仅管理单个实例上的运行请求。这意味着调度器每轮需处理更高的调度频率以及更大规模的待跟踪和调度请求。

Llumnix设计了一种可扩展架构，结合集群级全局调度器与分布式实例级调度器（命名为llumlets），以高效实现持续重调度（图8）。Llumnix通过窄接口在两级调度器之间明确划分职责：

• 全局调度器不直接跟踪或调度运行中的请求，而是基于实例的内存负载制定面向实例的调度决策。
• 该设计使全局调度器的复杂度与运行请求无关，从而保持与无动态调度能力的调度器相近的可扩展性。
• 实例负载由llumlets根据请求状态和Llumnix调度策略定期上报。
  

全局调度器利用负载信息完成以下任务：

1. 分发新请求；
2. 触发跨实例迁移；
3. 控制实例自动扩缩容。
   特别地，对于迁移决策，全局调度器不针对具体请求，仅根据负载状态配对源实例与目标实例，并标记其状态以触发迁移。llumlets负责自动选择待迁移请求并执行迁移。

每个实例的llumlet包含本地调度器与迁移协调器：

• 本地调度器：
  • 除传统功能（如排队、批处理、块管理）外，新增核心任务为计算实例内存负载。该负载并非物理内存占用，而是请求的虚拟使用量（定义见第4.4节）之和。
  • 在触发迁移时，负责选择待迁移的请求。
• 迁移协调器：
  • 根据选定的请求，协调本地调度器与目标实例，指挥模型执行器完成内存拷贝（如前文所述）。

4.4 动态调度策略

4.4.1 目标与定义

Llumnix的调度策略设计包含以下目标。首要目标是通过减少排队延迟、抢占和干扰，优化预填充（prefill）与解码（decode）延迟。第二目标是实现负载适应性，以应对集群负载波动并提升成本效益。我们注意到，重调度的收益与集群负载相关：负载过高或过低时收益可能受限。为此，Llumnix引入实例自动扩缩容机制，以维持适当的集群负载，既节省成本又最大化重调度收益。

除上述与现有系统相似的目标外，Llumnix新增了请求优先级这一核心目标，源于LLM的新需求。优先级为同一LLM服务提供了一种系统性方法，以优先处理高紧急程度的请求（例如来自ChatGPT Plus或高交互性应用的请求）。Llumnix为应用提供接口，允许指定请求优先级以满足不同服务级别目标（SLO），具体分为调度优先级和执行优先级：

• 调度优先级：高优先级请求会被更早调度以减少排队延迟。
• 执行优先级：高优先级请求会被分配到负载较低的实例，从而减少干扰以加速执行。

目前，Llumnix支持**高（high）和普通（normal）**两类优先级，以验证系统对高优先级请求的优先处理能力，但设计可扩展至更多优先级。

4.4.2 虚拟使用量

为在分布式调度架构下实现上述多重目标，Llumnix需要一种调度策略，能够通过简单的实例级指标表达这些目标，以提升全局调度器的效率与可扩展性。为此，Llumnix提出虚拟使用量抽象，将不同甚至冲突的目标统一为实例的负载指标。关键观察在于：前述重调度场景可分为两类——负载均衡和在实例上腾出空闲空间（去碎片化、优先级调度、实例缩容）。通过假设实例的虚拟负载，两类场景可被统一为负载均衡问题：若需在实例上腾出空间，只需设置部分请求的虚拟使用量使实例看似“过载”，则负载均衡策略将被触发，将请求迁移至其他实例。

基于这一观察，Llumnix采用以负载均衡为核心的简单启发式策略，结合一套针对不同场景设置请求虚拟使用量的规则。算法1中的函数CalcVirtualUsage总结了这些规则，图9展示了示例场景。在常规情况下，请求的虚拟使用量等于其物理内存占用，以支持常规负载均衡（图9(a)）。其他场景的规则如下：

排队请求：
对于实例上的队首排队请求（尚未分配资源），尽管其物理内存占用为0，我们仍为其分配一个正虚拟使用量，以反映其所需的内存资源。此时，排队请求会增加实例的总虚拟使用量，从而触发负载均衡迁移（实际效果为排队请求的去碎片化，如图9(b)）。设置虚拟使用量的启发式规则可灵活调整，例如逐步增加排队请求的虚拟使用量直至达到实际需求，以平衡减少排队延迟与负载均衡的权衡。Llumnix当前采用简单规则：直接使用请求的实际内存需求（算法1第4行），优先减少排队延迟。此规则基于我们的观察：排队延迟可能主导端到端延迟，值得优先处理。评估表明，由于迁移的高度灵活性，此规则仍能保留负载均衡的收益。
执行优先级：
对于高执行优先级请求，Llumnix通过为其预留内存空间（即“预留空间”）防止所在实例的实际负载超过给定阈值（图9©）。具体方法是将预留空间加到高优先级请求的物理内存占用上，得到其虚拟使用量（算法1第8行）。若实例上有多个高优先级请求，该预留空间会在这些请求间分配（算法1第10行）。当前，高优先级请求的预留空间定义为“维持理想解码速度（即无干扰）所需的内存”，其值通过性能分析确定。普通请求的预留空间为0。通过指定不同预留空间大小，Llumnix还可支持更多层级的执行优先级。当高优先级请求的预留空间不足时，其他普通请求会因实例总虚拟使用量过载而被负载均衡策略迁移。

自动扩缩容：
当新实例启动时，Llumnix的负载均衡策略会自动将其他实例的请求迁移至此以填充新实例。当实例需终止时，Llumnix会人为添加一个虚拟使用量为无穷大的假请求（算法1第7行），迫使剩余请求迁移至其他实例（图9(d)）。

以下是 Algorithm 1 的逐步解释，该算法用于计算请求（req）在实例（instance）中的 虚拟使用量（Virtual Usage） 和实例的 空闲度（Freeness），以支持动态调度决策：

---

1. 函数 CalcVirtualUsage(req, instance)

功能：计算单个请求在实例中的虚拟资源占用量，综合考虑请求状态、优先级和实际资源使用。

逻辑流程：

1. 排队请求（isQueuing）：

   • 如果请求处于排队状态：
     • 若该请求是队列头部（isHeadOfLine），返回其资源需求（demand）。
     • 否则返回 0，表示非头部排队请求暂时不占用资源。
   • 目的：仅对即将执行的头部请求分配资源，避免过度预留。

2. 假请求（isFake）：

   • 若请求是“假请求”（可能用于标记终止实例），返回无穷大（∞）。
   • 目的：阻止新请求分配到即将终止的实例。

3. 运行中请求：

   • 返回 physicalUsage（实际物理资源占用） + GetHeadroom(priority)（优先级预留资源）。
   • 目的：为高优先级请求预留额外资源，确保其性能。

---

2. 函数 GetHeadroom(p, instance)

功能：根据优先级 p，计算实例中每个请求的平均预留资源。

公式：

$
\text{Headroom} = \frac{\text{headroomForPriority}[p]}{\text{instance.numRequests}[p]}
$

• headroomForPriority[p]：为优先级 p 预留的总资源。
• instance.numRequests[p]：实例中优先级为 p 的请求数量。
• 目的：确保高优先级请求获得更高资源保障。

---

3. 函数 CalcFreeness(instance)

功能：计算实例的剩余资源容量（空闲度），用于指导调度决策。

逻辑流程：

1. 终止中的实例：

   • 若实例正在终止（isTerminating），添加一个“假请求”（防止新请求分配到此实例）。

2. 计算总虚拟使用量：

   • 遍历实例中所有请求，累加它们的 CalcVirtualUsage 值。

3. 空闲度公式：
   $\text{freeness}=\frac{\text{instance.M}-\text{totalVirtualUsages}}{\text{instance.B}}$

   • instance.M：实例的总资源容量。
   • totalVirtualUsages：所有请求的虚拟使用量总和。
   • instance.B：归一化因子（如 GPU 显存块大小）。
   • 目的：空闲度越高，实例可接收的新请求越多。

---

关键设计思想

1. 动态资源预留：

   • 通过 GetHeadroom 为高优先级请求预留资源，避免低优先级请求占用关键资源。

2. 排队优化：

   • 仅对队列头部请求分配资源，减少资源浪费。

3. 实例终止保护：

   • 通过“假请求”阻止新请求分配到即将终止的实例，提升系统鲁棒性。

4. 归一化空闲度：

   • 通过 instance.B 将空闲度标准化，便于跨实例比较（例如选择空闲度最高的实例分配请求）。

---

应用场景

• 负载均衡：根据空闲度选择最合适的实例分配新请求。
• 优先级调度：高优先级请求通过预留资源获得更低延迟。
• 碎片化缓解：动态调整资源分配，减少内存碎片。
• 弹性伸缩：快速判断实例是否可终止或需要扩容。

如果需要进一步探讨具体细节（如 headroomForPriority 的设定），请随时提问！

调度（Dispatching）
Llumnix 优先调度具有更高调度优先级的新请求。在相同优先级内，采用简单的先到先服务（first-come-first-serve）顺序。在每个实例中，请求按相同顺序被调度。Llumnix 使用一种负载均衡策略，将每个请求分发到空闲度（freeness）最高的实例。我们引入了一个衡量实例空闲度的指标，定义为：

其中，(M) 是实例的总内存，(V) 是每个请求的虚拟使用量，(B) 是批处理大小。尽管 $(M-\sum V)$ 已能衡量剩余内存空间，但除以批处理大小 (B) 是因为它决定了资源消耗速度（即每次迭代生成的新 token 数量）。因此，该指标表示当前批次还能运行多少次迭代。随后，Llumnix 将每个新请求分发到空闲度最高的实例。由于请求的虚拟使用量可能大于实际物理使用量，空闲度 (F) 可能为负值（例如存在排队请求或高优先级请求时）。此类负值帮助 Llumnix 自动将实例标记为过载状态，并优先将请求分发到其他实例。空闲度指标还指导迁移和自动扩缩容（如后文所述）。

迁移（Migration）
Llumnix 周期性触发迁移策略。每轮中，Llumnix 通过选择空闲度低于或高于给定阈值的实例，分别组成源实例（source）和目标实例（destination）的候选集合。Llumnix 通过反复选择空闲度最低的源实例和空闲度最高的目标实例进行配对，并将它们置入对应状态。每个源实例的 llumlet 组件随后开始持续将请求迁移到目标实例，直到该实例不再处于源状态。在选择迁移请求时，llumlet 优先选择优先级较低且序列长度较短的请求。在下一轮中，若处于迁移状态的实例的空闲度不再超出阈值，Llumnix 将取消其迁移状态并停止迁移。

自动扩缩容（Auto-scaling）
Llumnix 根据集群中普通优先级请求的平均空闲度调整实例数量。该策略将平均空闲度维持在范围 ([x, y]) 内：若空闲度持续低于 (x) 则扩容实例，高于 (y) 则终止实例。Llumnix 选择运行请求数量最少的实例进行终止。

5 实现

Llumnix 使用3,300行Python代码实现。Llumnix是一个独立库，包含其自身组件及与后端推理引擎集成和通信的接口。此架构使Llumnix对不同后端非侵入且可扩展。Llumnix目前支持vLLM作为后端，这是一个开源的先进推理引擎，具备连续批处理、PagedAttention和张量并行分布式推理功能。

多实例服务
Llumnix将后端的多个实例与其他组件实例化为Ray参与者。Ray的原生Python分布式运行时能以简洁高效的方式实现这些参与者间的细粒度协调。Llumnix还启动一组请求前端参与者，暴露OpenAI风格的API端点。尽管请求可在后端实例间迁移，但生成的token会被转发至前端并返回给终端用户，确保API服务的稳定性。

KV缓存传输
迁移期间，我们使用Gloo集体通信库（Send/Recv原语）进行KV缓存传输。潜在替代方案是NCCL，其在GPU上通常比Gloo更快，但已被用于分布式推理通信。然而，Llumnix需在推理过程中并行迁移请求以最小化停机时间，但NCCL的并发调用存在不安全性。流水线式迁移设计使我们能在保持可忽略停机时间的同时使用Gloo。使用Gloo需在CPU与GPU内存间复制KV缓存，此操作在另一CUDA流中完成以避免阻塞推理计算。在典型部署中，通信密集型张量并行性局限于单机以实现高速传输。此时，实例（机器）间的迁移不会干扰张量并行推理。

块融合
vLLM以动态分配的非连续小块存储KV缓存。例如，16位LLaMA-7B模型的块大小为128KB（每层16个token的键或值张量），1k token的序列对应4k个块（32层）。为避免大量小消息传输的开销，我们通过将块从GPU内存复制到连续的CPU内存缓冲区并整体发送，从而提升传输效率。

容错能力
Llumnix为各组件提供容错能力以确保高服务可用性。当全局调度器故障时，Llumnix临时回退到绕过调度器模式，不影响服务可用性：请求前端使用简单规则直接分发请求至特定实例，且迁移被禁用。当实例（或同节点的llumlet）故障时，其上运行的请求将被终止。特别是，故障实例上的迁移操作也会终止（被迁移请求是否终止取决于源实例是否健康），此过程由握手协议处理。这些故障参与者将被Ray自动重启，随后服务恢复正常状态。

6 评估

我们在一个16-GPU集群上使用真实模型和多样化工作负载对Llumnix进行评估。总体而言，我们的主要发现包括：
• Llumnix对迁移中的请求引入了接近零的停机时间，对其他运行中的请求引入了接近零的额外开销。
• 通过碎片整理，Llumnix在16个LLaMA-7B实例上，将预填充延迟（P99/平均值）最高提升了15倍/7.7倍，优于INFaaS。通过减少抢占，Llumnix还将P99解码延迟最高降低了2倍。
• Llumnix通过减少高优先级请求的排队延迟并加速其执行，将其延迟最高降低1.5倍，同时保持普通请求的性能相似。
• Llumnix通过高效自动扩缩容，在保持相似P99延迟的同时，实现了最高36%的成本节省。

6.1 实验设置

测试平台。我们使用阿里云上的16-GPU集群（包含4个GPU虚拟机，类型为ecs.gn7i-c32g1.32xlarge）。每台虚拟机配备4个NVIDIA A10（24 GB）GPU（通过PCI-e 4.0连接）、128个vCPU、752 GB内存和64 Gb/s网络带宽。
模型。我们以流行的LLaMA模型族[57]为实验对象。测试两种规格：LLaMA-7B（单GPU运行）和LLaMA-30B（通过张量并行在单机4个GPU上运行）。模型采用常见的16位精度。我们基于的vLLM版本仅支持原始LLaMA（最大序列长度2k），但近期已有支持更长序列长度（4k至256k）的LLaMA变体[3,7,58,65]。由于这些变体的模型架构和推理性能与LLaMA基本相似，我们认为从系统角度而言，我们的结果能代表更多模型类型和更长序列长度范围。

请求轨迹。与先前工作[34, 35, 67]类似，我们通过合成请求轨迹评估Llumnix的在线服务性能。

分布	平均值	P50	P80	P95	P99
真实
ShareGPT 输入	306	74	348	1484	3388
输出	500	487	781	988	1234
BurstGPT 输入	830	582	1427	2345	3549
输出	271	243	434	669	964
生成
短（S）	128	38	113	413	1464
中（M）	256	32	173	1288	4208
长（L）	512	55	582	3113	5166
表1：评估中使用的序列长度（token数量）真实分布与生成分布。真实分布包含输入（“In”）和输出（“Out”）的长度。我们使用不同请求率（每秒请求数）的泊松分布和伽马分布生成请求到达时间。对于伽马分布，我们调整变异系数（CV）以控制请求的突发性。每个轨迹包含10,000个请求。我们选择合适的请求率或CV范围，使负载保持在合理区间：使用Llumnix时，P50请求几乎无排队延迟和抢占，P99请求的排队延迟在几十秒内。

对于请求的输入/输出长度，我们使用两个公开的ChatGPT-4对话数据集——ShareGPT (GPT4)[10]和BurstGPT (GPT4-Conversation)[62]——评估真实工作负载。考虑到Llumnix面向更多样化的应用场景，我们还使用生成的幂律长度分布模拟长尾工作负载，混合高频短序列（如聊天机器人、个人助手等交互式应用）和低频长序列（如摘要或文章生成）。我们生成多个不同长尾程度和平均长度（128、256、512）的分布，如表1中的短（S）、中（M）、长（L）分布。这些分布的最大长度为6k，因此请求的总序列长度（输入+输出）在运行LLaMA-7B时不会超过A10 GPU的容量（13,616 tokens）。为观察不同工作负载特征的性能，我们通过组合输入和输出的长度分布构建轨迹，包括S-S、M-M、L-L、S-L和L-S。

基线。我们将Llumnix与以下调度器对比。所有基线和Llumnix均使用vLLM作为底层推理引擎，以聚焦实例间请求调度的对比。
• 轮询调度：一种均衡分发请求的简单策略，是生产级服务系统的典型行为[4, 9, 47]。
• INFaaS++：优化版的INFaaS[53]，一种先进的多实例服务调度器。我们评估其负载均衡调度和负载感知自动扩缩容策略。我们通过使其专注于LLM服务中的主导资源——GPU内存（包括排队请求占用的内存以反映队列压力）对其进行改进。
• Llumnix-base：Llumnix的基础版本，不区分优先级（所有请求视为同优先级），但启用迁移等其他功能。

关键指标。我们重点关注请求延迟，包括端到端延迟、预填充延迟（首个生成token的延迟）和解码延迟（自首个生成token至最后一个的平均延迟）。我们报告平均值和P99值。

6.2 迁移效率

我们首先评估Llumnix迁移机制的性能，包括对迁移请求引入的停机时间和对运行中请求的额外开销。我们测试了1-GPU的LLaMA-7B和4-GPU的LLaMA-30B模型。针对每种模型，我们在两台不同机器上部署两个实例。使用不同序列长度时，我们分别在两个实例上运行总长度为8k的同一批请求。随后将其中一个实例上的请求迁移至另一实例，并测量其停机时间及迁移期间两个实例上运行批次的解码速度。

我们比较了迁移期间的停机时间与两种简单方法：重新计算和使用Gloo阻塞式拷贝KV缓存（其他请求非阻塞）。如图10（左）所示，迁移的停机时间随序列长度增加几乎保持恒定（约20-30毫秒），甚至短于单次解码步骤。相比之下，基线方法的停机时间随序列长度增加而增长，最高达到迁移的111倍。例如，对LLaMA-30B重新计算8k序列需3.5秒，相当于54个解码步骤的服务停滞。我们还观察到，所有序列长度的迁移仅需两个阶段，这是最小值。这是因为数据拷贝速度足够快，且第一阶段生成的新token数量较少。

图10（右）进一步比较了源实例在迁移期间与正常执行时的单步解码时间（目标实例结果类似）。对于LLaMA-7B和LLaMA-30B，性能差异均不超过1%，表明迁移额外开销可忽略不计。此外，此类额外开销仅在实例上有请求被迁移（入或出）时存在。我们发现，在后续所有服务实验中，每个实例上正在进行迁移的时间跨度平均占比仅为约10%。这意味着实际额外开销更小，而迁移带来的调度收益显著，这一权衡是值得的。

6.3 服务性能

我们评估Llumnix在在线服务中的调度性能，使用16个LLaMA-7B实例（自动扩缩容功能仅在§6.5实验中启用）。
真实数据集。我们首先使用ShareGPT和BurstGPT轨迹（图11的前两行），比较Llumnix与轮询及INFaaS++的性能。Llumnix在端到端请求延迟上显著优于基线方法，平均延迟最高提升2倍，P99延迟最高提升2.9倍。尤其值得注意的是，轮询策略的性能始终远低于INFaaS++和Llumnix：由于序列长度方差较大，单纯均匀分发请求仍会导致负载不均衡，从而影响预填充和解码延迟。

Llumnix在预填充延迟上相比轮询实现显著提升，平均延迟最高达26.6倍，P99延迟最高达34.4倍。这是由于轮询可能将新请求分发至过载实例，导致较长的排队延迟。通过负载均衡减少抢占，Llumnix将P99解码延迟最高降低2倍。由于抢占导致的延迟惩罚被所有生成token分摊，这一提升幅度看似较小。然而，每次抢占发生时，都会造成突发性服务停滞，影响用户体验。图11（最右侧列）报告了抢占损失（所有请求的额外排队和重计算时间均值）。Llumnix相比轮询平均减少84%的抢占损失。这些结果凸显了负载均衡在LLM服务中的重要性。在后续使用更高方差生成分布的实验中，轮询的延迟表现恶化至基线的两个数量级。因此，为保持图表清晰，后续实验将省略轮询，仅对比INFaaS++与Llumnix。