June 4, 2026 中 #LLM Inference #Scheduling #Model Serving

Llumnix：大语言模型推理服务的动态调度系统

笔记日期： 2026-06-04 笔记作者： Zhongzhu Zhou 论文标题： Llumnix: Dynamic Scheduling for Large Language Model Serving 作者： Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, Wei Lin arXiv： 2406.03243v1, 2024-06-05 状态/Venue： OSDI ‘24，阿里巴巴集团 / 阿里云 PAI-EAS

一句话总结

Llumnix 把操作系统中”进程上下文切换”的思路搬进了 LLM 推理服务领域，实现了”请求在多个 GPU 实例之间在线迁移”的能力，借此解决了静态调度无法应对的三大问题：请求抢占（preemption）、批内干扰（interference）、集群碎片（fragmentation）。核心贡献是一个近零停机时间的预拷贝（pre-copy）迁移机制，以及一个把五种调度目标统一为一个变量的**虚拟用量（virtual usage）**抽象，最终在 16 卡集群上将 P99 TTFT 降低了 15 倍。

1. 前置知识

1.1 LLM 推理的两阶段生命周期

要理解 Llumnix 为什么需要”迁移请求”，首先要明白 LLM 推理的基本流程和它的难点在哪里。

Prefill（预填充）阶段：用户发来的 prompt，连同所有 token，同时通过模型所有层，一次性生成第一个输出 token。这个阶段是计算密集型（compute-bound），可以充分利用 GPU 的并行能力。

Decode（解码）阶段：每次只生成一个新 token，需要把当前 token 和之前所有 token 的 key/value 张量一起喂给模型，输出下一个 token，如此循环，直到生成 <EOS> 停止。这个阶段是内存带宽瓶颈（memory-bandwidth-bound），因为每步都要读一遍缓存好的 KV 张量。

从用户视角出发，有两个核心的延迟指标：

TTFT（Time-to-First-Token）：从发请求到收到第一个 token 的时间——取决于排队等待时间 + prefill 时间
TBT（Time-Between-Tokens）：连续两个输出 token 之间的间隔——取决于每次 decode step 的耗时

关键困难：在用户发出请求的那一刻，模型并不知道会输出多少 token（因为终止是靠模型自己生成 <EOS> 判断的）。这意味着一个请求的显存占用是动态增长且不可预知的，直到它结束之前都无法释放。

1.2 KV 缓存：动态显存的根源

Transformer 的 Attention 机制：

\text{Attention}(Q, K, V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_h}}\right) V

在自回归解码中，第 $t$ 步生成 token 时，需要用到所有之前 $t-1$ 步的 $K, V$ 。为了避免每步都重新计算，模型会把每一步生成的 $K, V$ 张量缓存起来，这就是 KV Cache。

KV Cache 的显存开销公式：

M_{\text{KV}}(n) = 2 \times n \times L \times H \times d_h \times \text{bytes\_per\_element}

各参数含义：

$2$ ：Key 和 Value 各一份
$n$ ：当前序列长度（输入 + 已输出 token 数）
$L$ ：Transformer 层数
$H$ ：注意力头数
$d_h$ ：每个头的维度
bytes_per_element：fp16 为 2 字节，bf16 也是 2 字节

具体例子（LLaMA-2-13B）： $L=40$ , $H=40$ , $d_h=128$ ，使用 fp16。

M_{\text{KV}}(4096) = 2 \times 4096 \times 40 \times 40 \times 128 \times 2 = 3.3 \text{ GB}

这相当于 LLaMA-2-13B 模型权重（约 26 GB）的 12.7%，而且随着输出 token 的增加，这个数字还会继续增长。更重要的是，在请求到达时，我们完全不知道最终会生成多少 token，也就无法提前预留精确的显存。

不同模型的 KV Cache 大小对比（序列长度 4096，fp16）：

模型名        参数量  层数L  头数H  维度d_h  KV Cache@4096 tokens
─────────────────────────────────────────────────────────────
LLaMA-7B     7B      32     32     128      1.6 GB
LLaMA-13B    13B     40     40     128      3.3 GB
LLaMA-30B    30B     60     52     128      6.4 GB
LLaMA-65B    65B     80     64     128      13.1 GB

从这个表格可以看出，对于 30B 以上的大模型，4096 token 的 KV Cache 就超过了 6 GB——一张 A100 40GB 的大部分显存（模型权重 +KV Cache）可能只够放 2-3 个并发请求。这正是为什么多实例集群级别的调度对生产部署如此重要。

1.3 PagedAttention 和连续批处理

连续批处理（Continuous Batching）（ORCA/vLLM 引入）：传统推理系统等一整批请求都完成才开始下一批。连续批处理允许请求随时加入或离开 batch——某个请求完成后，立即补充新请求进来，GPU 利用率大幅提升。

PagedAttention（vLLM 引入）：把 KV Cache 切分成固定大小的”块（page）“，按需动态分配，类似操作系统中的虚拟内存分页机制。

物理显存布局（PagedAttention 视角）：
+-------+-------+-------+-------+-------+-------+-------+
| 块 0  | 块 1  | 块 2  | 块 3  | 块 4  | 块 5  | 块 6  |
|请求 A |请求 A |请求 B |请求 A |  空闲 |请求 C |  空闲 |
+-------+-------+-------+-------+-------+-------+-------+
         （不连续的块通过页表关联，无需物理连续）

PagedAttention 消除了内部碎片（单个请求内部浪费的空间），但并不能解决外部碎片——多个请求分布在多个实例上后，空闲显存可能散布在各处，导致新的长序列请求找不到足够连续的空间。这正是 Llumnix 需要解决的问题之一。

1.4 SLO 与尾延迟：为什么 P99 比均值重要

服务等级目标（SLO，Service Level Objective）定义了服务提供商对用户的延迟承诺，例如：

TTFT 的 P99 ≤ 2秒（99% 的请求在 2 秒内收到第一个 token）
TBT 的 P99 ≤ 50ms（99% 的 token 间隔不超过 50ms）

为什么 P99 比均值难控制？ 因为即使只有 1% 的请求出现严重延迟（例如被抢占重算了一次，增加了 50 秒），这 1% 就足以违反 P99 SLO，直接影响用户体验。Llumnix 的核心目标之一就是大幅压低尾延迟。

1.5 多实例 LLM 服务系统

生产环境中，一个 LLM 服务通常运行在一组 GPU 实例（模型副本）上。前端调度器（scheduler）把用户请求分发给某一个实例，该实例负责完成这个请求的整个 prefill + decode 过程。

常见的调度策略：

轮询（Round-robin）：简单但忽略负载差异
最小负载（Least-loaded）：按队列长度或显存用量选最轻的实例
随机：简单，但容易造成负载不均

这些策略都是”一次性派发”：请求被派给某个实例后，就永远在那个实例上运行直到完成，中间不能移动。Llumnix 的根本性突破就是打破这个限制。

2. 问题：静态派发的三大失效场景

Llumnix 的 motivation 部分非常扎实，通过实验量化了三类问题。

2.1 问题一：显存抢占带来的尾延迟崩塌

由于每个请求的 KV Cache 增长是不可预测的，单个实例在运行过程中可能耗尽显存。这时引擎不得不抢占（preempt）某些正在运行的请求——把它们的 KV Cache 换出到 CPU 内存，或者直接丢弃并标记为”稍后重算”。

抢占的代价极高：

重算方式：重新执行整个 prefill，代价 $\propto n_{in}$ （序列越长越贵）
换出方式：通过 PCIe 把 KV Cache 写入 CPU，速度受限于 PCIe 带宽（32 GB/s），3.3 GB 的 KV Cache 需要约 103ms

论文实验数据（LLaMA-7B，A10 GPU，2000个请求，平均显存负载 62%）：

延迟百分位数分析：
                P50      P75      P90      P99
每 token 解码时间  12ms     18ms     25ms     46ms
其中：抢占损失      0ms      0ms      6ms      32ms  (占 P99 的 70%!)
────────────────────────────────────────────────
总时间            12ms     18ms     31ms     46ms

P99 比 P50 慢了 3.8 倍，其中 70% 的额外延迟来自抢占。论文还观测到一个 P99 请求因为被抢占两次，累计损失了 50 秒。

根本原因：请求一旦被派发到实例，就无法移走。当该实例显存不够时，除了抢占别无选择。

2.2 问题二：批内干扰导致 P99 TBT 恶化

同一个 batch 中的多个请求共用 GPU 计算资源和 HBM 带宽，相互之间会产生干扰：batch 中 token 越多，每步的解码时间越长。

论文实验数据（LLaMA-7B，不同 batch 大小）：

batch 中 token 总数 | 每步解码时间 | 相对减速
───────────────────|────────────|─────────
64                |  8ms       | 1×
256               | 12ms       | 1.5×
512               | 17ms       | 2.1×
1024              | 21ms       | 2.6×

高优先级请求（例如在线聊天）被分配到一个繁忙实例上后，每步解码都会被其他请求干扰，导致 TBT 显著拉长，即使从未被抢占也会违反 SLO。

2.3 问题三：集群级显存碎片与调度矛盾

静态派发系统面临一个无法同时满足的矛盾：

为了减少抢占和干扰：把请求分散到多个实例（负载均衡），每个实例显存压力小
但分散后：每个实例都持有一些请求，空闲显存分布在各实例上，呈碎片化状态

实验场景（4个 LLaMA-7B 实例，各 10 GB KV 配额）：
负载均衡策略后的状态：
  实例 0: [已用 6GB] [空闲 4GB]
  实例 1: [已用 5GB] [空闲 5GB]
  实例 2: [已用 4GB] [空闲 6GB]
  实例 3: [已用 3GB] [空闲 7GB]

此时来了一个 8192 token 的长输入请求，需要 6.6 GB KV Cache：
  → 只有实例 3 空闲 7GB 够用
  → 但后续请求继续派到实例 3，它很快也满了
  → P99 TTFT 被长队列拖慢 3-5 倍

这是一个典型的外部碎片问题：集群总空闲显存充足（4+5+6+7=22 GB），但没有单个实例有足够大的连续空间服务大请求。而如果用”贪心集中”策略（把请求尽量堆在少数实例），抢占频率又会上升 4 倍。

2.4 问题四：无法差异化服务优先级

现有 LLM 推理引擎把所有请求一视同仁。商业服务通常有多个服务等级（如 ChatGPT Plus vs 免费版），但没有机制在不单独配置专用 GPU 实例的情况下实现 SLO 差异化——代价高昂且资源浪费。

3. Llumnix 的核心设计理念：运行时请求重调度

3.1 操作系统类比

Llumnix 的设计灵感来自操作系统的进程调度。这个类比不是比喻——它直接指导了技术选择：

操作系统进程调度         Llumnix 请求调度
───────────────         ─────────────────
进程                ←→  LLM 请求
进程工作集（内存页）   ←→  KV Cache（显存块）
CPU 核心            ←→  GPU 模型实例
上下文切换           ←→  KV Cache 迁移
MLFQ/CFS 调度器     ←→  虚拟用量调度器
进程优先级           ←→  请求 SLO 优先级

操作系统的革命性发现：进程不必被钉在一个 CPU 核心上直到完成——可以随时迁移到另一个核心，从而实现负载均衡、优先级保证和资源复用。Llumnix 把同样的思想应用到 LLM 请求上。

3.2 重调度场景分类

graph TD
    A[新请求到达] --> B[LlumSched 初始派发]
    B --> C{最佳实例?}
    C -->|虚拟用量最低| D[实例A：运行中]
    C -->|有足够空闲显存| E[实例B：运行中]

    D --> F{运行时监控}
    E --> F

    F -->|负载不均| G[从重载→轻载实例迁移]
    F -->|显存碎片| H[整合请求，释放连续空间]
    F -->|高优先级请求| I[将低优先级请求迁走，腾出隔离空间]
    F -->|弹性扩容| J[将请求迁到新实例，快速热身]
    F -->|缩容下线| K[将请求全部迁走，安全关机]

    G --> L[LlumSched：持续重调度]
    H --> L
    I --> L
    J --> L
    K --> L

图1：五种重调度场景。 无论哪种场景，底层机制都是一样的：把请求连同它的 KV Cache 从一个实例迁移到另一个实例。

4. 在线迁移机制：近零停机时间的预拷贝

4.1 朴素迁移方案及其问题

最直接的迁移思路：

朴素迁移流程：
1. 停止请求（source 暂停解码）
2. 把所有 KV Cache 块从 source 传到 destination
3. 在 destination 重启请求，继续解码

停机时间 = 传输时间 $T_{\text{transfer}}(n)$ ，正比于序列长度 $n$ ：

T_{\text{naive}} = T_{\text{stop}} + \frac{M_{\text{KV}}(n)}{B} + T_{\text{restart}} \approx \frac{M_{\text{KV}}(n)}{B}

其中 $B$ 是 GPU 间传输带宽。

具体数值（LLaMA-13B， $n=4096$ ，NVLink 600 GB/s）：

T_{\text{naive}} \approx \frac{3.3\text{ GB}}{600\text{ GB/s}} \approx 5.5\text{ ms}

跨节点（PCIe 4.0，32 GB/s）：

T_{\text{naive}} \approx \frac{3.3\text{ GB}}{32\text{ GB/s}} \approx 103\text{ ms}

对于 TBT SLO 为 50ms 的服务，即使 NVLink 传输也是不可接受的，且停机时间随序列长度线性增长——越需要迁移的请求（序列越长、显存越大）迁移代价越高。

4.2 预拷贝方案：把传输时间藏进计算时间

Llumnix 借鉴虚拟机热迁移（VM live migration）中的**预拷贝（pre-copy）**技术：

核心思想：在 source 实例继续运行的同时，后台把已有的 KV Cache 块传过去；等大部分数据传完，只需要停机传输”增量”（新生成的少量块），增量大小是常数，与序列长度无关。

详细流程：

预拷贝迁移时间线：

Source:  [decode step t][decode step t+1][decode step t+2][ STOP ]
          └──── 后台传输已有 KV 块 ────┘                 └─Δ─┘
                                                          ↑    ↑
                                               传增量 Δ      在 dest 重启

Dest:    接收后台传来的块 .............................  [接收 Δ][ resume ]

请求停机时间 = T_stop + T_transfer(Δ) + T_restart ≈ O(1) 常数

“增量 Δ”只有在后台传输进行期间（通常 3-5 个 decode step）新生成的 KV 块，大小非常小，传输时间是常数，与序列总长度 $n$ 无关。

4.3 迁移算法伪代码

算法 1：Llumnix 预拷贝请求迁移
输入：请求 r，源实例 S，目标实例 D
输出：r 在 D 上继续解码，停机时间近零

// 阶段一：后台预拷贝（与 S 上的解码并行进行）
1:  pre_copy_done ← False
2:  启动后台线程：
3:      for 每个 KV Cache 块 b in r.kv_cache:
4:          transfer_block(b, from=S, to=D)    // 带宽限速，不影响解码
5:      pre_copy_done ← True

// 阶段二：S 继续运行，同时累积增量
6:  while not pre_copy_done:
7:      S.run_decode_step(r)                   // 继续生成 token
8:      new_blocks.append(S.get_latest_block(r)) // 记录新块

// 阶段三：停机，传输增量
9:  S.suspend_request(r)                       // 暂停，O(1) 时间
10: for 每个增量块 b in new_blocks:
11:     transfer_block(b, from=S, to=D)        // 增量小，O(1) 时间

// 阶段四：在 D 上恢复
12: D.resume_request(r)                        // D 已有所有 KV Cache 块
13: S.free_kv_cache(r)                        // 释放 S 上的显存

为什么停机时间是常数：new_blocks 的数量等于预拷贝期间执行的 decode step 数（通常 3-5 步），每步生成一个 KV 块（大约 0.5-1 MB），传输时间约 0.5ms，与序列总长度 $n$ 无关。

关键实现细节：迁移在解码步骤边界发生，不在步骤中间打断。这保证了 KV Cache 处于一致状态（所有已生成 token 的 K、V 都完整存储）。

4.4 迁移带宽限制

同时进行多个迁移会占满 GPU 间互联带宽，影响正在进行的解码操作。Llumnix 对迁移带宽做限速：

节点内（NVLink）：限制为 NVLink 带宽的可配置比例（如 20%）
跨节点（RDMA/PCIe）：限制为网络带宽的可配置比例

这确保迁移不会反而把它试图改善的延迟搞得更差。

5. 虚拟用量：五合一的统一调度策略

5.1 核心洞察：一个变量搞定五种场景

Llumnix 面对五种调度场景（负载均衡、去碎片化、优先级、扩容、缩容），最”工程直觉”的做法是给每种场景写一个独立的策略模块。但 Llumnix 选择了更优雅的方案：虚拟用量（virtual usage）。

每个请求 $r$ 有一个虚拟用量 $u_{\text{virtual}}(r)$ ：

u_{\text{virtual}}(r) = u_{\text{real}}(r) + \delta(r, \text{场景})

其中 $u_{\text{real}}(r)$ 是该请求当前实际占用的 KV Cache 显存大小（真实的、可测量的）， $\delta$ 是根据当前调度目标施加的一个”虚拟加分”。

唯一的调度规则：把总虚拟用量最高的实例上的请求，迁移到总虚拟用量最低的实例。

graph TD
    VS[虚拟用量调度器]
    VS --> R1[计算每个请求的虚拟用量]
    R1 --> R2[汇总每个实例的总虚拟用量]
    R2 --> R3[识别最重实例 src 和最轻实例 dst]
    R3 --> R4{src - dst > 阈值?}
    R4 -->|是| R5[从 src 选一个候选请求迁到 dst]
    R4 -->|否| R6[不迁移]
    R5 --> VS
    R6 --> VS

图2：虚拟用量调度循环。 所有五种场景都通过调整 $\delta$ 参数来表达，核心调度逻辑完全统一。

5.2 各场景的 $\delta$ 设计

┌──────────────────────────────────────────────────────────────────────┐
│ 场景          │ δ(r) 设置              │ 效果                       │
├──────────────┼────────────────────────┼────────────────────────────┤
│ 负载均衡      │ δ = 0（用真实显存）     │ 重→轻迁移，减少抢占         │
├──────────────┼────────────────────────┼────────────────────────────┤
│ 去碎片化      │ 对待调度的长请求，把它  │ 目标实例上的请求"看起来很贵" │
│              │ 的虚拟需求计入目标实例  │ → 被迁走 → 腾出连续空间     │
├──────────────┼────────────────────────┼────────────────────────────┤
│ 优先级        │ 低优先级请求：δ = +大数 │ 低优先级请求"虚拟用量高" →  │
│              │                        │ 被迁离高优先级请求所在实例   │
├──────────────┼────────────────────────┼────────────────────────────┤
│ 弹性扩容      │ 新实例上：δ = -大数    │ 新实例"虚拟负载最低" →      │
│              │                        │ 请求涌入新实例，快速热身     │
├──────────────┼────────────────────────┼────────────────────────────┤
│ 缩容下线      │ 待下线实例：δ = +∞     │ 该实例所有请求"极度昂贵" →  │
│              │                        │ 全部迁走 → 实例清空关机     │
└──────────────┴────────────────────────┴────────────────────────────┘

图3：五种场景的 $\delta$ 设计表。 新增场景只需添加 $\delta$ 规则，核心调度循环不变。

5.3 调度算法伪代码

算法 2：Llumnix 虚拟用量调度器
输入：集群状态（各实例的真实用量、请求队列、优先级信息）
输出：迁移决策

// 由 Llumlet 的负载变化事件触发（请求完成、新请求入队等）

过程 UPDATE_VIRTUAL_USAGES(state)：
1:   for 集群中的每个请求 r:
2:       u_virt[r] ← u_real[r]                      // 基础值 = 真实用量
3:       if r.priority == LOW:
4:           u_virt[r] += PRIORITY_BONUS             // 低优先级请求加权
5:       if r.instance in draining_list:
6:           u_virt[r] += DRAIN_BONUS                // 下线中的实例请求加权
7:       if r.instance in scaling_out_list:
8:           u_virt[r] -= SCALE_OUT_DISCOUNT         // 扩容目标实例减权
9:   for 每个待调度的大输入请求 p（需要 p.need_space 显存）:
10:      target ← find_fittest_instance(p.need_space)
11:      V_pending[target] += DEFRAG_BONUS           // 预留空间标记
12:  for 每个实例 i:
13:      V_total[i] ← Σ u_virt[r for r on i] + V_pending[i]

过程 RESCHEDULE(event)：
14: UPDATE_VIRTUAL_USAGES(cluster_state)
15: src ← argmax_i(V_total[i])              // 总虚拟用量最高的实例
16: dst ← argmin_i(V_total[i])              // 总虚拟用量最低的实例
17: if V_total[src] - V_total[dst] > THRESHOLD:
18:     r ← SELECT_CANDIDATE(src)
19:     ENQUEUE_MIGRATION(r, src, dst)

过程 SELECT_CANDIDATE(src_instance)：
20: candidates ← src_instance.running_requests
21: // 优先选：优先级最低 × KV Cache 最大（虚拟用量减少最多）
22: return argmax_{r ∈ candidates}(priority_inv(r) × kv_size(r))

6. 系统架构

6.1 组件全景

graph TB
    subgraph "客户端层"
        C1[用户请求 A]
        C2[用户请求 B]
        C3[用户请求 C]
    end

    subgraph "网关层 Gateway"
        GW[网关<br/>- Tokenizer<br/>- 请求路由<br/>- 流量分割/镜像]
    end

    subgraph "调度层"
        LS[LlumSched<br/>- 初始派发<br/>- 持续重调度<br/>- 虚拟用量策略]
        CMS[集群元数据存储 CMS<br/>- 各实例实时 KV 用量<br/>- 运行中/等待中请求数]
    end

    subgraph "实例层"
        LL0[Llumlet 0<br/>状态上报 + 迁移协调]
        LL1[Llumlet 1]
        LL2[Llumlet 2]
        E0[Engine 0<br/>vLLM]
        E1[Engine 1<br/>vLLM]
        E2[Engine 2<br/>vLLM]
    end

    C1 --> GW
    C2 --> GW
    C3 --> GW
    GW --> LS
    LS <--> CMS
    LS --> LL0
    LS --> LL1
    LS --> LL2
    LL0 --> E0
    LL1 --> E1
    LL2 --> E2
    LL0 <--> CMS
    LL1 <--> CMS
    LL2 <--> CMS
    E0 <-.->|KV Cache 迁移| E1
    E1 <-.->|KV Cache 迁移| E2

图4：Llumnix 系统架构全景图。 四层结构：客户端层、网关层、调度层、实例层。

6.2 LlumSched：调度大脑

LlumSched 是中心调度器，承担两个角色：

初始派发（Scheduler）：新请求到来时，LlumSched 依据当前虚拟用量状态，选择最合适的目标实例——显存够用、虚拟负载最低。

持续重调度（Rescheduler）：后台持续运行，监听来自各 Llumlet 的负载变化事件。每次事件触发后，运行虚拟用量调度器，决定是否发起迁移。

LlumSched 是一个单一的 Ray Actor，调度逻辑是 $O(N)$ 的（ $N$ 为实例数），迁移指令是异步下发的，不阻塞新的调度决策。

6.3 Llumlet：实例侧代理

每个模型实例旁运行一个 Llumlet 进程，是 LlumSched 和 vLLM Engine 之间的桥梁：

状态上报：每次负载变化事件（请求完成、新请求入队、KV Cache 用量变化）后，更新 CMS 中该实例的状态
迁移协调：接到迁移指令后，与对端 Llumlet 协调 KV Cache 传输（源侧：序列化 KV 块；目标侧：反序列化并安装）
Engine 插桩：在 vLLM 上加 hook，支持 suspend/resume 操作

全白盒模式 vs 轻量黑盒模式：

全模式（full mode）：Llumlet 直接访问 vLLM 内部状态（KV 块表、请求队列等），调度质量最佳
轻量模式（lite mode）：只观测 vLLM 的外部 API 指标，适合未修改的推理引擎

6.4 集群元数据存储（CMS）

CMS 是一个共享的键值存储（原版用 Ray 实现），维护每个实例的实时状态：

CMS 数据结构（每个实例一条记录）：
{
  instance_id: "gpu-0",
  kv_used_bytes: 8.2e9,       // 当前 KV Cache 用量
  kv_free_bytes: 1.8e9,       // 当前空闲显存
  running_requests: [...],     // 正在解码的请求列表
  pending_requests: 3,         // 队列中的待处理请求数
  utilization: 0.82            // GPU 利用率
}

Llumlet 在每次负载变化后写入 CMS（事件驱动，非周期轮询），LlumSched 在每次调度决策前读取 CMS。

6.5 迁移数据流

sequenceDiagram
    participant LS as LlumSched
    participant LL_S as Llumlet_src
    participant E_S as Engine_src (vLLM)
    participant E_D as Engine_dst (vLLM)
    participant LL_D as Llumlet_dst

    LS->>LL_S: migrate(request_r, dst=实例D)
    LL_S->>E_S: start_pre_copy(r, dst=E_D)
    E_S-->>E_D: 后台传输 KV 块（限速，并行于解码）
    E_S->>E_S: 继续为请求 r 运行 decode step
    E_S->>LL_S: pre_copy_done()
    LL_S->>E_S: suspend_request(r)
    E_S-->>E_D: 传输增量 Δ（少量新块，O(1) 时间）
    LL_S->>LL_D: 通知：请求 r 传输完成
    LL_D->>E_D: resume_request(r)
    E_D->>E_D: 继续解码 r
    LL_S->>CMS: 更新实例状态
    LL_D->>CMS: 更新实例状态

图5：迁移完整时序图。 虚线表示异步 KV Cache 传输，是关键路径外的操作。请求停机时间仅为”传增量 + suspend/resume”。

7. 实验与结果

7.1 实验配置

集群：     16 张 A100 40GB GPU，2 个节点，每节点 8 GPU
           节点间：25 Gbps 以太网
           节点内：NVLink
模型：     LLaMA-7B（1 GPU/实例）和 LLaMA-30B（4 GPU/实例）
负载：     ShareGPT 轨迹 + 合成 Poisson 到达
           输入长度：幂律分布，均值 256 token
           输出长度：幂律分布，均值 256 token
对比基线：  INFaaS（业界常用的负载感知调度器）、DeepSpeed-MII、随机派发
指标：     P50/P99 TTFT；P50/P99 每 token 解码时间（每解码步）

7.2 尾延迟对比

图6：P99 延迟对比表（LLaMA-7B，16 GPU，中等负载）：

                    TTFT P99        每 token 解码 P99
───────────────────────────────────────────────────
随机派发             ≈180s           ≈600ms
INFaaS              ≈120s           ≈485ms
DeepSpeed-MII       ≈95s            ≈420ms
Llumnix             ≈8s  (15× ↓)   ≈240ms (2× ↓)

观察：TTFT 的改善远大于 TBT 的改善。这符合预期：

TTFT 主要被排队等待时间拖累，而等待的根本原因是碎片化——Llumnix 的去碎片化迁移直接解决了这个问题
TBT 主要被抢占和批内干扰拖累，Llumnix 通过负载均衡减少了这两者，但改善幅度相对有限（2× vs 15×）

P50 延迟的改善较小（1.2–1.5×）——绝大部分请求本身就不受碎片化影响，Llumnix 主要改善了”坏运气的请求”。

7.3 优先级分离实验

负载中 50% 是高优先级（在线聊天，TTFT SLO 严格），50% 是低优先级（批量评估，SLO 宽松）：

                   高优先级 TTFT P99    低优先级 TTFT P99
─────────────────────────────────────────────────────
无 Llumnix：          120s               130s（两类一样慢）
有 Llumnix：          80s (1.5× 加速)   180s（降级，有意为之）

高优先级请求通过虚拟用量膨胀机制被保护：低优先级请求被迁离”高优先级区域”，高优先级请求获得更多隔离和显存。这正是优先级 SLO 差异化服务的理想行为——以低优先级流量的尾延迟为代价，保证高优先级流量的 SLO。

7.4 成本节省实验

问题：用更少的 GPU 跑出和基线相同的 P99 尾延迟，能省多少 GPU？

目标：和基线（INFaaS + 16 GPU）相同的 P99 TTFT ≈ 120s
Llumnix 实现相同 P99 TTFT 需要：11 GPU（节省 5 GPU，即 36%）

原理：Llumnix 消除了碎片化导致的空转和抢占导致的重算，使每块 GPU 的有效利用率更高，因此同样的服务质量只需更少的硬件。

7.5 迁移开销微基准

对 LLaMA-7B 的 4096 token 请求（KV Cache 约 3.3 GB），在 NVLink（有效带宽 600 GB/s）下：

预拷贝阶段：   5.5ms（后台传输，不阻塞请求，约覆盖 3-4 个 decode step）
增量传输：     0.5ms（后台传输期间新生成约 1 个 KV 块，约 0.5 MB）
暂停 + 重启：  1.0ms
─────────────────────────────────────────────────────
请求停机时间：  1.5ms  （vs. 朴素方案的 5.5ms，减少 3.7×）

关键：停机时间对序列长度不敏感——100 token 的请求和 4000 token 的请求都是约 1.5ms 的停机，因为增量 Δ 的大小只取决于预拷贝期间的 decode step 数（3-4 步），而不是序列总长度。

8. 与同期工作的对比定位

graph LR
    A["vLLM 2023<br/>PagedAttention"] -->|优化| B["单实例显存管理"]
    C["ORCA/TGI<br/>连续批处理"] -->|优化| D["单实例 GPU 利用率"]
    E["DistServe 2024<br/>Prefill-Decode 分离"] -->|优化| F["跨角色资源分配"]
    G["Mooncake 2024<br/>KV Cache 中心化"] -->|优化| H["KV Cache 存算分离"]
    I["Llumnix 2024<br/>动态调度迁移"] -->|优化| J["跨实例运行时重调度<br/>负载均衡/优先级/去碎片"]

    B --> K[单实例 层面]
    D --> K
    F --> L[跨角色 层面]
    H --> L
    J --> M[跨实例 调度层面]

图7：Llumnix 与同期系统的定位对比。 Llumnix 工作在不同的抽象层：它不替代 vLLM 或 DistServe，而是作为一个调度层部署在它们之上。你完全可以在 DistServe 的 P/D 分离部署中再叠加 Llumnix 的跨实例调度——两者互补，不冲突。

9. 批判性分析：不足与可改进之处

9.1 不好的地方（Weaknesses）

W1 — 只评估了 vLLM 一个后端。 迁移机制要求对引擎做侵入式改造（挂 hook、支持 suspend/resume、KV 块序列化）。论文声称架构可以适配其他引擎，但评估中只用了 vLLM。TensorRT-LLM（NVIDIA NIM 生产标配）、SGLang（以 RadixAttention 著称）的内存管理机制都与 vLLM 不同，迁移机制是否能低代价适配，完全未经验证。

W2 — 负载模型过于理想化。 全部实验都用 Poisson 到达 + 幂律长度分布。真实的 LLM API 服务有：

昼夜波动：高峰期请求量可能是低峰的 10-20 倍
请求相关性：同一系统提示的变体请求大量共现（prefix cache 命中率高）
突发流量：爆款事件触发的阵发性高峰

在这些场景下，Llumnix 是否会触发”迁移风暴”（大量同时迁移、带宽被打满）？论文完全没有讨论。

W3 — 未考虑 Prefix Cache 的交互。 vLLM 和 SGLang 均实现了共享前缀缓存（RadixAttention）：多个请求共用相同系统提示时，KV Cache 块被共享。把一个请求从持有共享块的实例迁走，意味着：

要么把共享块也传过去（会让其他请求无法共用，浪费显存）
要么在目标实例重计算这些块（增加 prefill 延迟）

论文完全回避了这个问题——而这在实际生产中极为常见（大量 chatbot 应用共享同一系统提示）。

W4 — 长上下文场景未测试。 GPT-4 Turbo（128K token）、Qwen2-128K、Llama-3 (128K) 的 KV Cache 最大可达数十 GB。这种场景下：

迁移的”增量 Δ”本身就可能很大（长序列每步生成的 KV 块更大）
NVLink 的传输时间不再可忽略

论文只测了均值 256 token 的短请求负载，最大序列长度约 4096。

W5 — 对比基线偏弱。 INFaaS（2021 年发布）是一个通用模型服务框架，并非专为 LLM 优化。2024 年已有多个 LLM 专用多实例调度器（如 FairServe、SpotServe 等），论文没有与这些更具竞争力的 baseline 对比。

9.2 作者淡化或回避的局限

L1 — 中心化 LlumSched 的可扩展性天花板。 LlumSched 是单一 Ray Actor，高并发场景下会成为调度瓶颈。论文中的可扩展性实验只有调度延迟的微基准，没有在高请求率（>1000 req/s）或大规模集群（>100 实例）的端到端实验。

L2 — CMS 信息滞后问题未量化。 LlumSched 的调度决策基于 CMS 中的状态，而 CMS 在 Llumlet 推送更新之前可能已经过时。高请求吞吐量下，CMS 的滞后会导致调度决策基于过期信息，可能引发多个请求同时被迁往同一”看起来空闲”的实例，造成目标实例过载。论文提到了这一问题（称为”information lag”），但没有量化其发生频率及对 SLO 的实际影响。

L3 — 优先级反转的边界条件。 把低优先级请求迁走后，目标实例可能已经很重，低优先级请求在目标实例被抢占。抢占的代价（重算 prefill）可能远高于迁移本身的代价。论文描述了这个场景的存在，但没有分析在什么条件下迁移→抢占的链路会比不迁移更差。

L4 — 弹性伸缩场景评估不完整。 论文在主要评估中对 scale-out/scale-in 场景只做了微基准，而没有在端到端实验中测试完整的弹性伸缩流程（包括新实例冷启动，LLaMA-7B 约需 30 秒加载模型权重）。

9.3 可以改进的地方（Concrete Improvements）

I1 — 支持 SGLang 和 TensorRT-LLM 后端。 设计一个引擎无关的迁移 API（serialize_kv_state(request_id) / deserialize_kv_state(blob)），用 SGLang 和 TRT-LLM 实现，在主评估中添加多后端对比实验。

I2 — 前缀缓存感知的迁移策略。 引入一个”迁移代价模型”：

\text{cost}(r, \text{src} \to \text{dst}) = T_{\text{transfer}} + P_{\text{cache\_miss}} \times T_{\text{re-prefill}}

当目标实例已有待迁移请求的前缀缓存时， $P_{\text{cache\_miss}}=0$ ；当前缀缓存会丢失时， $T_{\text{re-prefill}}$ 会很高，抑制迁移。

I3 — 显式测试跨节点迁移的实际代价。 在 10Gbps 和 25Gbps 以太网环境下测量不同序列长度的迁移代价，导出一个”是否值得跨节点迁移”的决策阈值公式，给工程部署提供实操指导。

I4 — 引入突发负载测试。 使用 BurstGPT 合成轨迹或真实 Azure LLM 服务轨迹（如果公开可用）测试 Llumnix 在突发流量下的行为——特别是同时触发大量迁移时，带宽竞争是否会导致迁移延迟超过其预期收益。

I5 — 分层调度架构。 当集群规模超过 50 个实例时，引入”机架内本地调度器 + 跨机架全局协调器”的两级架构：机架内迁移（NVLink，代价极低）由本地调度器处理；跨机架迁移（以太网，代价较高）由全局协调器把关，只在极度不均衡时发起。

10. 深入分析：虚拟用量为何在理论上站得住脚

10.1 从势函数角度理解虚拟用量调度

虚拟用量调度看起来像一个直觉性的启发式策略，但它实际上对应了一个经典的负载均衡理论框架。

定义集群在 $t$ 时刻的”不均衡势函数”：

\Phi(t) = \sum_{i=1}^{N} \left( V_i^{\text{total}}(t) \right)^2

即各实例总虚拟用量的平方和——这是负载均衡理论中常用的不均衡度量（“最小化最大负载”的平滑版本）。

将请求 $r$ （虚拟用量 $v_r$ ）从 $V_{src}$ 最高的实例迁移到 $V_{dst}$ 最低的实例，势函数变化为：

\Delta\Phi = (V_{src} - v_r)^2 + (V_{dst} + v_r)^2 - V_{src}^2 - V_{dst}^2

= -2v_r(V_{src} - V_{dst}) + 2v_r^2

当 $V_{src} - V_{dst} > v_r$ 时， $\Delta\Phi < 0$ ，迁移严格减少不均衡势——这正是算法第 5 行的判断条件。

关键结论：Llumnix 的调度器在做有理论保证的贪心势函数下降，而不是盲目启发式。当没有任何单次迁移能降低势函数时，集群进入局部均衡态。此时的配置满足：对所有实例对 $(i, j)$ ， $|V_i - V_j| \leq \min_r v_r$ ，即最大-最小虚拟负载之差不超过最小请求的虚拟用量——这是连续负载均衡的最优条件。

10.2 预拷贝迁移停机时间的精确推导

设：

$b_s$ ：每个 KV 块的大小（字节）
$B_{\text{pre}}$ ：预拷贝带宽（字节/秒，受限速管控）
$\tau_d$ ：每个 decode step 耗时（秒）
$n_0$ ：迁移开始时的序列长度（块数）
$k$ ：预拷贝阶段产生的新块数

预拷贝阶段时间：

T_{\text{pre-copy}} = \frac{n_0 \cdot b_s}{B_{\text{pre}}}

期间产生的新块数：

k = \left\lfloor \frac{T_{\text{pre-copy}}}{\tau_d} \right\rfloor = \left\lfloor \frac{n_0 \cdot b_s}{B_{\text{pre}} \cdot \tau_d} \right\rfloor

停机阶段只需传输 $k$ 个增量块：

T_{\text{down}} = \frac{k \cdot b_s}{B_{\text{stop}}} \approx \frac{k \cdot b_s}{B_{\text{pre}}}

代入 $k$ 的表达式：

T_{\text{down}} \approx \frac{n_0 \cdot b_s^2}{B_{\text{pre}}^2 \cdot \tau_d}

这看起来仍与 $n_0$ 有关——但关键在于带宽与解码速度之比。

数值代入（LLaMA-7B，NVLink，20% 限速）：

$b_s \approx 0.5$ MB/块（每个 token 在所有层的 KV 张量大小）
$B_{\text{pre}} = 120$ GB/s（NVLink 600 GB/s × 20%）
$\tau_d \approx 10$ ms/step

对于 $n_0 = 256$ 块（4096 tokens）：

T_{\text{pre-copy}} = \frac{256 \times 0.5\text{MB}}{120\text{GB/s}} = \frac{128\text{MB}}{120\text{GB/s}} = 1.07\text{ms}

k = \left\lfloor \frac{1.07\text{ms}}{10\text{ms}} \right\rfloor = 0 \text{ 或 } 1

即预拷贝阶段只产生约 1 个新块，停机时间：

T_{\text{down}} = \frac{1 \times 0.5\text{MB}}{120\text{GB/s}} = 4.2\mu s

加上 suspend/resume 开销（约 1ms），总停机时间约 1.0ms——确实与 $n_0$ 无关（因为 $k \in \{0, 1\}$ 对所有合理的序列长度都成立）。

设计准则：要保持 $k$ 为常数，需要：

\frac{b_s}{B_{\text{pre}} \cdot \tau_d} \ll 1 \quad \Rightarrow \quad B_{\text{pre}} \gg \frac{b_s}{\tau_d}

即预拷贝带宽必须远大于”每步产生的 KV 数据速率”。这个条件在 NVLink 环境下很容易满足；但在跨节点（以太网 10-25 Gbps）场景下， $B_{\text{pre}}$ 下降 5-12 倍，可能使 $k$ 变大，停机时间增长。这也是为什么跨节点迁移需要更谨慎地设置阈值。

11. 工程实践建议

11.1 什么时候该开 Llumnix？

明显有收益的场景：

平均 KV Cache 内存利用率 > 60%（高负载下抢占频发）
请求长度方差大（长度标准差 > 均值），碎片化严重
需要 SLO 分级（在线聊天 vs 批量评估混跑）
云上弹性伸缩部署（新实例冷启动期间的快速热身）

开了反而有害的场景：

平均利用率 < 30%（显存充裕，迁移只增加开销）
请求长度均匀（无碎片，无需去碎片化迁移）
单卡部署（没有别的实例可以迁移到）

11.2 迁移阈值的调参指导

算法 2 中的 MIGRATION_THRESHOLD 是最重要的调参变量：

过小：迁移频率过高，带宽被消耗，TBT 方差增大
过大：迁移很少触发，碎片化和负载不均无法被纠正

推荐初始值： $\text{THRESHOLD} = \bar{u} \times N$ ，其中 $\bar{u}$ 是平均请求 KV 用量， $N$ 是实例数。然后根据观测到的迁移率 vs SLO 违约率调整：迁移率高但 SLO 未改善 → 增大阈值；SLO 仍有尾延迟突出 → 减小阈值。

12. 笔记总结：这篇论文值得学什么

Llumnix 给我最深刻的启发不是具体的技术细节，而是如何从第一原理出发选择抽象层。

作者观察到 LLM 请求本质上像”有动态工作集的进程”后，没有去设计一个针对 preemption 的补丁、一个针对 fragmentation 的补丁、一个针对 priority 的补丁，而是直接问：“操作系统是怎么解决这些问题的？“答案是：context switch。然后把 context switch 搬进来，用预拷贝解决停机问题，用虚拟用量统一所有场景。

这种”借用已有抽象”的方法之所以有效，是因为类比足够精确：请求的 KV Cache 确实很像进程的工作集，GPU 实例确实很像 CPU 核心，连续批处理确实很像多任务调度。当类比精确时，借用成熟抽象可以一次性解决多个问题；当类比不精确时（例如把 LLM token 当成数据库查询处理），则会产生错误的直觉。

读到这篇论文之后，我对 LLM serving 基础设施有了一个新的心智模型：

单实例层（vLLM, SGLang）
  ↓ PagedAttention：消除内部碎片
  ↓ 连续批处理：提升 GPU 利用率

跨角色层（DistServe, Mooncake）
  ↓ Prefill/Decode 分离：针对计算特性配置资源
  ↓ KV Cache 中心化存储：解耦计算和存储

跨实例调度层（Llumnix）  ← 新增的这一层
  ↓ 运行时请求重调度：动态均衡、去碎片、优先级
  ↓ 预拷贝迁移：使在线迁移代价可接受

Llumnix 填补了”跨实例动态调度”这个空缺，与其他层正交互补。

技术可复用性：

预拷贝迁移机制可以推广到任何”需要在节点间迁移有状态计算”的场景，不局限于 LLM
虚拟用量的”隐式策略编码”思路可以推广到其他需要多目标调度的分布式系统（Kubernetes Pod 调度、数据库连接调度等）
LlumSched + Llumlet 的”中心调度 + 本地代理”架构在分布式系统中是经典模式，值得作为范例学习
势函数下降的理论框架说明了为什么简单的”高虚拟用量迁到低虚拟用量”规则可以收敛到良好的均衡态

对 LLM Serving 基础设施的系统性理解：Llumnix 让我意识到，解决 LLM serving 的难题需要在三个层面分别下功夫，它们互相正交、可以叠加：

第一层：单实例内部（vLLM, SGLang, TRT-LLM）
  → PagedAttention 消除内部 KV 碎片
  → 连续批处理提升 GPU 解码利用率
  → FlashAttention 加速 Attention 计算

第二层：Prefill / Decode 角色间（DistServe, Mooncake, Sarathi-Serve）
  → Prefill/Decode 分离，按计算特性配置资源
  → KV Cache 中心化存储，解耦计算与存储
  → 分块 Prefill 控制批内干扰

第三层：跨实例运行时调度（Llumnix）  ← 这一层之前几乎是空白
  → 动态请求重调度（负载均衡 + 去碎片化 + 优先级 + 弹性伸缩）
  → 预拷贝在线迁移（使第三层的"上下文切换"代价可接受）
  → 虚拟用量统一调度策略（优雅地把五个目标收归一个数值）

Llumnix 的最大价值是填补了第三层的空白——在它之前，工业界的普遍做法就是”派了就不管”，所有的调度灵活性都停留在派发阶段的静态决策。

标签: LLM Serving, LLM Inference, KV Cache, Operating Systems