Reading Notes: “Preble: Efficient Distributed Prompt Scheduling for LLM Serving”

date
Oct 12, 2025
slug
preble
status
Published
tags
MLSys
summary
type
Post

Motivation

两个关于目前的 LLM 应用的观察：
  • 很多场景下，prompt 部分很长（比如指令模版，长序列理解，in context learning 的示例等等），而输出的部分比较短而且分布比较稳定
  • 很多情况下 prompt 可以在不同请求之间复用
这两个情况对于更早的系统来说主要的问题是没有利用 request 之间）的关系来做 KV Cache 的复用，每个请求独立维护 KV Cache 带来内存和计算的浪费。
最近的一些系统主要考虑了在单 GPU 层级处理这个问题，比如 vllm 通过 copy on write 来一定程度上前缀复用，sglang 通过 radix tree 管理 kv cache 来复用共享的前缀。
但是在多 GPU 做 distributed serving 的层面还缺少有效的方法，目前的 distributed serving 系统在负载均衡的时候主要考虑平衡 node 的负载，或者只简单考虑最大化前缀复用（这带来负载不均衡）。负载均衡在传统的软件系统中很常见，但是 LLM serving 相比于之前一般的应用系统相比更加计算密集，如果不考虑 KV Cache 的复用会造成很多计算上的浪费。
由此，我们需要一种多 GPU 层级的 prompt aware 的负载均衡策略，它可以和之前的单 GPU 层面的优化方法正交的使用，来实现集群效率的最大化。
对此，本文介绍了 Preble, 一个 distributed serving 系统，基于一个新提出的两级调度算法来达到上述的目标。

Approach

Preble 采用了一个两级的调度系统 E2，在多 GPU 之间通过一个 global scheduler 来把请求分配到具体某个 GPU，在单个 GPU 上用 local scheduler 来做执行的调度。在 global 层面调度时考虑 prompt aware 的负载均衡，在 local 层面综合考虑 prompt 复用以及公平性。
notion image

Global Scheduler

Global Data Structure

global scheduler 维护了一个全局的 radix tree，每个节点记录有多少个 token，在历史窗口 H 内每个 GPU 有多少请求复用了这个前缀，以及这个前缀 cache 在哪些 GPU. 这些信息在负载均衡策略中使用来做 prompt aware 的负载估计。

Load Balance Policy

Preble 的全局负载均衡采用 exploitation-exploration 的策略，文中称为 E2。总体的思路是：考虑 radix tree 里面最大的前缀匹配，如果复用 kv cache 带来的计算开销（cache 命中部分）约减大于重计算部分（cache miss 部分）的开销，那么就 exploit （也就是利用这个特点，绕过负载均衡，也就是图中的 if branch）；否则就 explore，选择负载小的（也就是图中的 else branch 的第二个 foreach 部分）。
notion image
对于一个 GPU 的负载估计的计算，preble 采用三个部分来建模：
  • 历史窗口 H 内的 GPU 负载 L: 分为 prefill 部分和 decode 部分，分别用关于 token 数量的线性模型建模
  • 为了放入当前请求而需要驱逐已有的 kv cache 带来的开销 M：通过估计这个被驱逐的部分带来的增益来计算，通过历史窗口 H 内的数据来计算，也就是这个部分 prefill 开销乘上缓存命中率
  • 放入当前请求带来的开销 P：当前请求中 Miss 部分的 prefill 开销
notion image

Prefill-decoding Balancing

Prefill 和 Decode 是两种具有不同计算特点的负载，前者是计算密集的，后者是访存密集的，在同一个 GPU 上配平两种负载可以更好地最大化硬件利用率（也就是Algorithm 1 中的 else branch 的第一个 foreach，因为新请求肯定要先 prefill，可以利用一下 decode heavy 的 GPU 富余的计算资源）

Post-assignment load adjustment

使用 algorithm 1 中提到的算法时，由于在条件满足时会总是去 exploit，某些情况下可能导致某个 GPU load 很重，比如某个非常 popular 的前缀。有两种应对策略：
  • rebalance：把 load 迁移到没什么负载的 GPU
  • replicate: 把不同子树分支 replicate 到新的 GPUs 上

Local Scheduler

在 local scheduler 的级别，用 local radix tree 来管理调度，把请求放到一个优先队列，优先级和 prefix hit rate 成正比。为了保证公平性，每次选择和优先级成比例数量的每个优先级的请求来执行，防止 starvation.
notion image
 

Result

下图展示了和 SGLang 的 avg latency 和 p99 latency 对比
notion image

© Lifan Sun 2023 - 2025