作者/机构: Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, Yiying Zhang (University of California, San Diego)

A1 主要贡献

本文旨在解决大型语言模型（LLM）服务中，由长且部分共享的提示（prompt）带来的新挑战。

核心问题:
随着LLM应用的发展，提示变得越来越长且复杂，例如包含领域特定指令、工具使用说明或长篇上下文（如教科书章节）。这导致许多请求之间的提示存在重复部分，其注意力计算结果（键值，即KV）可以被重用。然而，现有的LLM服务系统（如vLLM）将每个请求视为独立的计算单元，完全重新计算每个提示，即使部分内容之前已被计算过，从而错失了计算重用的机会。

研究目标:
设计并实现首个针对提示共享进行优化的分布式LLM服务平台，以在长且共享提示的工作负载下，提供高吞吐量和低平均/尾部延迟。

创新与贡献:
1. 首次对长共享提示的LLM工作负载进行系统性研究:
* 分析了五个真实LLM工作负载（工具使用、具身智能体、代码生成、视频问答、长文档问答）和一个数据中心LLM请求追踪。
* 研究发现：提示长度平均比生成序列长37至2494倍；提示中85%至97%的token与其他提示共享；大多数请求中存在一个比其前缀更长且共享特性不同的“关键部分”（key portion）。

  1. 识别了LLM服务中分布式状态管理的三个新挑战:

    • 计算与状态耦合: LLM推理要求注意力计算直接访问同一GPU上的状态（KV缓存），限制了计算和状态的独立放置。
    • 前缀约束: 只有匹配的前缀（prefix）才能被共享和缓存，且整个前缀必须位于同一GPU上。
    • 动态负载平衡: LLM的前缀树结构和各节点的负载随请求动态变化，使得静态分区变得困难且低效，该问题本质上是NP难的图分区问题。

  2. 提出了E2（Exploitation + Exploration）分布式调度算法:

    • 核心思想: 根据GPU负载和提示共享特性，动态地在“利用”（Exploitation）现有缓存和“探索”（Exploration）新GPU之间做出决策。
    • 利用策略: 当可节省的重计算量（共享前缀长度）大于新计算量（非共享部分长度）时，将请求发送到缓存了其“关键部分”的GPU上，以重用计算结果。
    • 探索策略: 当共享前缀较短时，为避免局部过载并实现长期负载均衡，算法会计算集群中所有GPU的“负载成本”，并将请求发送到成本最低的GPU。该成本综合考虑了GPU的预期负载、为新请求腾出空间所需驱逐内容的重计算成本，以及运行当前请求的成本。

  3. 构建了Preble，首个面向长共享提示的分布式LLM服务系统:

    • 双层调度架构: 包含一个全局的请求级调度器和一个每GPU的迭代级调度器。
    • 动态负载调整: Preble通过请求重定向和“关键部分”复制（自动扩缩）来缓解负载不均和热点问题。
    • 感知预填充-解码不平衡: 创新地将缓存命中（hit）的请求视为“解码型”计算，未命中（miss）的请求视为“预填充型”计算，并优先将后者调度到前者所在的GPU上，以平衡计算资源需求。
    • 公平性调度: 在本地等待队列中，采用基于前缀缓存命中率的优先级分组调度策略，以避免饥饿问题，兼顾了共享效率与公平性。

  4. 全面的实验评估:

    • 在两个GPU集群（4x A6000, 8x H100）上，使用两种开源LLM（Mistral 7B, Llama-3 70B）和五个真实工作负载进行了评估。
    • 结果表明，与当前最先进的支持前缀共享的单机系统SGLang的数据并行版本相比，Preble将平均延迟降低了1.5至14.5倍，p99尾部延迟降低了2至10倍。

A3 背景知识/关键Observation/设计原则

2. 背景与相关工作

2.1 LLM推理背景

LLM模型结构与推理阶段：当今的LLM由堆叠的Transformer块构成，每个块包含一个内存密集型的自注意力操作和一个计算密集型的线性操作。LLM推理包括两个阶段：预填充（prefill）和解码（decoding）。预填充阶段处理用户提示的所有token，计算出中间结果，即键（keys）和值（values），简称KV。解码阶段以自回归方式逐个生成输出token，每次生成（一个迭代）都会利用之前所有步骤计算出的KV状态。

预填充与解码的性能特征：预填充和解码阶段表现出不同的计算行为，前者是计算密集型，后者是内存带宽密集型。为了量化这些行为以供E2算法使用，我们对Mistral 7B在A6000 GPU上进行了性能剖析。图1显示，预填充时间随着提示长度的增加而增加，且由于线性层在预填充阶段占主导地位，预填充时间与提示长度大致呈线性关系。这表明前缀共享带来的节省与共享长度成正比。图2显示，单个请求的解码性能也与上下文长度（提示+已生成序列）呈类似的线性关系。总的来说，这些剖析结果表明注意力计算是规律的，因此可以用token长度和一个通过剖析得到的回归函数来估计计算时间。

图1：预填充时间分解
图1：预填充时间分解

图2：解码时间分解
图2：解码时间分解

2.2 以解码为中心的LLM服务

传统LLM服务系统的局限性：上一代LLM服务系统（如【59，Orca: A Distributed Serving System for Transformer-Based Generative Models，OSDI 2022】、【21，Efficient Memory Management for Large Language Model Serving with PagedAttention，SOSP 2023】）主要关注解码阶段，因为早期的LLM应用通常输出比提示长。例如，Orca【59】引入了迭代式调度，vLLM【21】提出了PagedAttention以减少GPU内存碎片。这些系统通常采用数据并行或模型并行来利用多GPU，但它们没有优化预填充阶段，也未利用提示共享，因此不适合处理长共享提示的工作负载。

2.3 感知提示的LLM服务

近期研究进展：随着LLM使用场景向提示密集型转变，近期工作【2，Taming throughput-latency tradeoff in llm inference with sarathi-serve，OSDI 2024】、【3，Sarathi: Efficient llm inference by piggybacking decodes with chunked prefills，arXiv 2023】、【65，Distllm: Disaggregating prefill and decoding for goodput-optimized large language model serving，OSDI 2024】识别了预填充和解码阶段的不同计算需求。预填充的计算与内存访问比率更高，当与解码请求批处理时，会导致解码请求等待，降低GPU效率。为解决此问题，提出了两种方法：分块预填充（chunked prefill）【2, 3】和将预填充与解码分离到不同GPU【65】。这些方案虽针对长提示，但未考虑提示共享。Preble在分块预填充的基础上，结合了一种新颖的基于共享的方案来解决该问题。

与单机前缀共享系统的对比：近期工作SGLang【64，Efficiently programming large language models using sglang，arXiv 2023】提出了使用前缀树在单GPU上共享请求前缀。但SGLang是单GPU方案，在分布式集群上运行时，若简单地在其上层添加数据或模型并行，会忽略跨GPU的集群级前缀共享机会。Preble除了提供对长共享提示的分布式支持外，还通过更优的驱逐机制和等待队列排序策略，提高了内存效率和公平性。另一项工作Prompt Cache【10，Prompt cache: Modular attention reuse for low-latency inference，MLSys 2024】允许共享任意子序列，但这是有损的，可能影响生成质量，且同样是单GPU方案。Hydragen【18，Hydragen: High-throughput llm inference with shared prefixes，arXiv 2024】则提出了一种高效的共享前缀注意力操作实现，与Preble的设计是正交的，Preble可以支持任何底层的注意力核。

2.4 传统的分布式有状态系统

与传统系统的区别：虽然Preble与传统的分布式有状态系统（如分布式文件系统、数据库、缓存层）有相似的目标（负载均衡、提升性能），但存在关键差异，使得传统方案不适用于LLM服务。
1. 状态与计算的耦合：传统系统通常将状态层与计算层分离。而LLM推理要求状态（KV缓存）和计算必须在同一GPU上才能高效执行，因此Preble必须协同管理计算负载和状态。
2. 状态的不变性与共享状态的动态性：LLM推理中，一旦序列的KV被计算，其值不会改变。但共享状态是动态的，一个已计算序列的某部分可能被未来的请求匹配为前缀，从而变为共享状态。
3. 前缀共享的特殊性：与传统系统可以缓存任意数据块不同，LLM服务中只有前缀共享才是有用的。
4. 计算模式的规律性：LLM的Transformer计算是规律的，其计算和内存消耗可由模型大小、提示长度和输出长度确定。这种规律性为预先确定负载提供了机会，但也带来了如预填充-解码平衡等新挑战。

3. LLM提示的（系统性）研究

我们研究了五种新兴的LLM使用场景：工具使用、具身智能体、程序生成、视频问答和长文档问答（如图3所示），并分析了它们的系统特性。

图3：工作负载演示。绿色框代表共享前缀。灰色框是非共享提示。白色框是输出生成。黄色星形代表固定位置出现的关键部分；粉色星形代表非固定位置。蓝色云代表如果知道先验信息，可用于分发前缀的部分。
图3：工作负载演示。绿色框代表共享前缀。灰色框是非共享提示。白色框是输出生成。黄色星形代表固定位置出现的关键部分；粉色星形代表非固定位置。蓝色云代表如果知道先验信息，可用于分发前缀的部分。

关键部分（Key Portion）定义：一个请求路径中，其token数量超过其所有前驱节点token数量总和的最深节点。

表1和图4总结了研究结果。

表1：LLM提示属性。除请求数量外，每个单元格显示（均值，标准差）。长度以token数量表示。“KeyPort.”代表关键部分。
表1：LLM提示属性。除请求数量外，每个单元格显示（均值，标准差）。长度以token数量表示。“KeyPort.”代表关键部分。

图4：关键指标的CDF图。显示了所有五个工作负载在提示-解码比率、共享前缀方面的CDF。
图4：关键指标的CDF图。显示了所有五个工作负载在提示-解码比率、共享前缀方面的CDF。

3.1 工具使用

工作负载特性：使用Toolbench数据集【11，Stabletoolbench: Towards stable large-scale benchmarking on tool learning of large language models，arXiv 2024】。每个查询包含共享的系统提示、工具特定指令和用户问题。共享主要来自使用相同工具的查询，这些指令的长度可能是输出长度的43倍。

3.2 具身智能体

工作负载特性：使用ALFWorld数据集【45，Alfworld: Aligning text and embodied environments for interactive learning，arXiv 2021】。提示包含环境描述、任务、解决步骤演示。模型通过规划-行动循环与环境交互，每一步都重用之前步骤的上下文，形成链式共享。由于步数由LLM生成决定，共享模式不可预测。提示长度是输出token的157倍。

3.3 程序生成

工作负载特性：使用APPS编程竞赛数据集【14，Measuring coding challenge competence with apps，NeurIPS Datasets and Benchmarks 2021】。为提升生成质量，在用户问题前添加了通用的代码示例作为系统提示。该系统提示在所有请求间共享。之后，并行调用LLM多次生成候选程序，这些并行调用共享相同的问题描述。提示与输出比率相对较低（20倍）。

3.4 视频问答

工作负载特性：使用NExT-QA基准【56，Next-qa: Next phase of question-answering to explaining temporal actions，CVPR 2021】。提示由一个token化的视频片段和一个多项选择题组成。由于输出是选择题答案，通常只有几个token。长视频token和短输出导致了极高的提示-解码token比率，接近2500倍。

3.5 长文档问答

工作负载特性：使用LooGLE数据集【22，Loogle: Can long-context language models understand long contexts?，arXiv 2023】。一个或多个用户通常会对同一长文档提出多个问题，导致大量token共享。答案通常很短，这同样导致了高提示-解码比率和高共享率。

3.6 真实世界LLM使用情况

Azure LLM推理追踪分析：我们分析了最近发布的Azure LLM推理追踪数据【40，Splitwise: Efficient generative llm inference using phase splitting，ISCA 2024】，包含代码生成和聊天对话两种用途。图5的CDF图显示，聊天请求的平均到达间隔为118毫秒，编程请求为63毫秒。编程任务的平均提示-解码比率为92，与我们评估的工作负载范围一致。聊天对话中，最长的20%提示的平均提示-解码比率为175，也证实了我们的观察。

图5：Azure LLM追踪分析结果。
图5：Azure LLM追踪分析结果。

3.7 总结性见解

  1. 洞见1: 提示显著长于输出。启示1: 优化预填充计算能极大提升应用性能，且需考虑预填充与解码的计算不平衡性。
  2. 洞见2: 提示共享普遍且量大。启示2: 跨共享前缀重用计算能显著提升真实工作负载的性能。
  3. 洞见3: 大多数请求存在“关键部分”，占提示的大部分并被大量请求共享。启示3: 识别并根据关键部分优化请求放置，是降低调度复杂性同时获得良好性能的可行方法。
  4. 洞见4: 真实世界LLM使用负载强度和提示-解码比率各不相同。启示4: 高效的LLM服务系统应考虑复杂、混合的场景，并计入负载和提示共享的变化。

A2 方法细节

4. Preble 设计

本节介绍E2算法及Preble系统设计。Preble主要针对长共享提示和相对短输出的场景，但在无共享且长输出的最坏情况下，其性能与vLLM【21】等传统系统相当，因为E2策略会退化为常规的负载均衡器。

4.1 整体系统架构

双层调度系统：Preble是一个分布式的GPU LLM服务系统，采用双层调度架构。一个全局调度器执行请求级调度决策并协调跨GPU的负载均衡，而每个模型实例对应一个本地调度器，执行分配到该GPU上的请求的迭代级调度。全局调度器可部署在单独的服务器或与GPU在同一服务器上。本地调度器运行在与GPU相同的服务器的CPU上。

请求处理流程：新请求到达后，首先由并行的分词器层进行分词。然后，全局调度器使用E2算法选择一个GPU分配给它。目标GPU所在的服务器将请求插入该GPU的等待队列。对于每个GPU，本地调度器在每次模型前向传播（即一次迭代）后，通过组合请求形成一个批次，进行迭代级调度。图6展示了Preble的整体架构。

图6：Preble架构。
图6：Preble架构。

设计优点：
1. 通过全局调度器集中处理所有请求，便于维护全局信息和每个GPU的请求级信息，这对E2至关重要。
2. 执行粗粒度的请求级调度，使得单个全局调度器可以扩展到更多GPU，避免了维护分布式全局控制平面的复杂性。
3. 本地调度器执行细粒度的迭代级调度，能快速适应GPU资源和请求可用性的变化，做出更精确的决策。
4. 在执行中途跨GPU迁移请求的开销相对较高，因此全局调度器无需在迭代级别进行调度或迁移。

4.2 E2 全局调度器

全局调度器数据结构：全局调度器维护全局前缀树（以基数树实现）作为主要数据结构。每个树节点代表一个具有相同共享属性的token序列。当插入新请求时，从根节点开始匹配前缀，直到无匹配为止，并将剩余部分作为新叶节点插入。每个树节点记录三类信息：该节点的token数量、缓存该节点的GPU集合，以及在一个历史窗口W内每个GPU上共享该节点的请求数量。当一个树节点没有被任何GPU缓存且在窗口W内系统中没有请求共享它时，该节点将被从树中移除。

算法1：E2调度算法伪代码
算法1：E2调度算法伪代码

单请求调度策略：全局调度器使用E2调度算法（如算法1所示）来调度请求。它首先在全局前缀树中匹配请求的提示。当节省的重计算量（匹配前缀的token数）大于新计算量（未匹配的剩余提示token数）时，我们倾向于“利用”而非“探索”。E2采用贪心策略，将请求分配给缓存了匹配前缀中“关键部分”（即token最长的树节点）的GPU。如果存在多个这样的GPU，则选择请求负载最轻的一个。

探索阶段的负载成本计算：如果匹配的前缀较短，E2会“探索”最佳GPU来运行该请求。探索阶段会找到“负载成本”最低的GPU。与传统计算不同，LLM的计算模式是规律的，预填充和解码的计算量与token数成正比。基于此，E2在计算每个GPU的成本时统一了三类成本，如算法2所示。

算法2：负载成本计算伪代码
算法2：负载成本计算伪代码

  1. GPU的总体负载 $L_i$：我们不使用GPU $i$的瞬时负载，而是通过最近路由到该GPU的 $H$ 个请求的历史来捕捉近期负载。对历史中的每个请求 $r$，我们使用回归函数根据其在GPU $i$上未匹配前缀的token数量估算其预填充时间 $P T_r$，并使用在窗口 $H$ 内观察到的平均请求解码时间估算其解码时间 $D T_r$。因此，$L_i = \sum_{r \in W} (P T_r + D T_r)$。
  2. 内存成本 $M_i$：这是为当前请求 $k$ 释放GPU内存可能产生的成本，量化为需要被驱逐并在其他GPU上重计算的token负载。我们使用驱逐算法（见4.3节）找到将被驱逐的树节点。对每个被驱逐的树节点 $j$，其驱逐成本是当前所有共享该节点的请求重计算这些token的时间。因此，$M_i = \sum P T_j \times N_j$，其中 $N_j$ 是共享树节点 $j$ 的请求数。
  3. 当前请求的运行成本 $R_i$：这是在GPU $i$上运行当前请求 $k$ 的实际成本，即请求 $k$ 中未命中部分的预填充时间。

分配当前请求到GPU $i$的总成本是 $L_i + M_i + R_i$，我们选择总成本最低的GPU。

分配后的负载调整：E2的贪心策略在负载相对稳定且关键部分不变的情况下工作良好。为应对负载或关键部分变化的情况，我们设计了两种分配后调整机制。第一种是负载转移：如果最重负载GPU的负载超过最轻负载GPU的 $T_{hbal}$ 倍，全局调度器会将未来的请求从重载GPU重定向到轻载GPU，直到负载差异低于阈值。第二种是自动扩缩：如果经过重平衡后，某个前缀的请求负载仍然过高（例如平均排队时间在窗口 $H$ 内翻倍），我们会复制该前缀及其子树，并按负载将其拆分到多个GPU上。

预填充-解码平衡：我们提出一种新的方法解决预填充-解码不平衡问题。我们的洞见是：一个其整个提示都被共享并缓存的请求，只执行解码阶段，可视为一个“解码阶段计算单元”；而一个长提示未被缓存且输出短的请求，可视为一个“预填充阶段计算单元”。因此，我们可以通过组合具有不同共享程度的请求来平衡预填充-解码。具体来说，当一个请求将要被“探索”时，如果某个GPU上重度负载着“解码阶段计算单元”，全局调度器会优先将当前请求（被视为“预填充阶段单元”）导向该GPU，因为该GPU有未被充分利用的计算能力。只有当所有GPU的预填充-解码负载相对平衡时，才进行负载成本比较。

全局调度器可扩展性：全局调度器采用多种技术提升其可扩展性。包括：使用并行的分词层；为处理和调度请求生成异步请求处理器；对全局基数树的访问是无锁的，因为大多数操作是只读的，写操作（如更新GPU分配和增加请求计数）可通过原子指令完成；以及使用后台线程运行重平衡和驱逐记账等非请求调度任务。

4.3 本地调度器

本地调度器机制：本地调度器负责调度全局调度器分配给其管理的GPU的请求。与现有系统类似，我们为每个GPU运行一个本地调度器，在迭代级别进行调度。每个本地调度器维护一个请求等待队列、一个前缀基数树，以及共享每个前缀树节点的活跃请求数。当新请求到来时，它会与本地前缀树匹配并相应更新树，然后请求被插入等待队列。每次模型迭代后，本地调度器使用基于优先级的算法选择等待的请求来组成下一个批次。如果选中的请求有长且未共享的提示，我们会像Sarathi【3】一样对提示进行分块。如果GPU内存不足以运行该批次，本地调度器会根据请求访问时间（LRU）选择一个或多个树节点进行驱逐，并通知全局调度器。

等待队列请求排序：现有的LLM服务系统通常按FCFS（先到先服务）或最大共享量优先的策略调度等待队列中的请求。前者忽略了提示共享，后者则可能导致饥饿问题【54，Fast distributed inference serving for large language models，arXiv 2023】。我们提出一种基于优先级的等待队列调度策略，同时考虑前缀共享和公平性。具体地，我们创建 $P$ 个（可配置参数）优先级组，并根据请求的缓存token百分比将其分配到对应的优先级组。例如，一个100-token提示中有63个token被缓存，且 $P=10$，则该请求被分配到优先级6。在选择请求组成下一批次时，调度器按比例从每个优先级组中选择请求，高优先级组被选中的请求更多。

A4 实验环境

  • 数据集:
    • 使用了第3节中分析的五个工作负载：Toolbench（工具使用）、ALFWorld（具身智能体）、APPS（程序生成）、NExT-QA（视频问答）、LooGLE（长文档问答）。
    • 请求到达模式：对于大多数实验，使用泊松分布生成请求的到达间隔时间；在混合工作负载实验中，使用了Azure LLM Inference Trace的真实请求到达时间模式。
  • 模型架构:
    • Mistral 7B：一个70亿参数的开源模型。
    • Llama-3 70B：一个700亿参数的开源模型。
  • 硬件配置:
    • GPU平台1: 一个包含4块NVIDIA A6000 GPU的集群。
    • GPU平台2: 一个包含8块NVIDIA H100 GPU的集群。
    • CPU: Intel(R) Xeon(R) Gold 5218。
    • 连接关系: 调度器运行在与GPU相同的节点上。对于Llama-3 70B的实验，使用了4路张量并行（Tensor Parallelism）加上数据并行（Data Parallelism）的配置。
  • 软件配置:
    • 实现: Preble作为一个独立的调度层实现，代码量约911行。
    • 后端: 支持vLLM【21】和SGLang【64】作为后端。对SGLang的修改仅约50行代码，用于增加基于优先级的等待队列管理。
    • 基线系统1 (SGLang/vLLM): 使用轮询（Round-Robin）负载均衡器将请求分发到多个独立的SGLang或vLLM实例上，模拟一个仅在单机内部进行前缀共享的分布式数据并行系统。
    • 基线系统2 (Oracle partition): 一个理想化的基线。在离线状态下，将工作负载的所有请求构建成一个完整的前缀树，然后手动选择一个“关键部分”层，并均匀地将该层的子树静态地划分到各个GPU上。

A4 实验结果

5.3 端到端工作负载性能

  • 单一工作负载结果 (图 7):
    • 实验内容: 在五个独立的工作负载、两种LLM和两个GPU集群上，对比Preble、SGLang（数据并行）和Oracle分区基线的性能。
    • 实验结果: Preble在所有配置下均显著优于SGLang基线，平均延迟降低1.5倍至14.5倍，p99延迟降低2倍至10倍。Preble的性能优于或持平于理想化的Oracle分区基线。
    • 分析结论:
      • Preble的动态调度能力（E2算法）能够有效利用跨GPU的共享机会，远胜于仅在单GPU内共享的轮询方案。
      • Oracle分区的静态策略无法适应动态变化的请求负载和不清晰的“关键部分”层，因此性能不如Preble的动态策略。
      • 在编程工作负载上，由于解码时间占比较高且存在一个所有请求共享的长系统提示（这有利于轮询基线），Preble的优势相对较小，但仍有1.56倍至1.8倍的平均延迟和3至4倍的p99延迟提升。在其他四个提示更长、输出更短的工作负载上，Preble的优势更为明显。
      • Preble表现出良好的可扩展性，从2个GPU扩展到4个A6000 GPU时，吞吐量近乎翻倍。在更强大的H100集群和更大的Llama-3 70B模型上，Preble同样保持了显著的性能优势。

图7：端到端工作负载性能。顶行和中行在2个和4个A6000 GPU上运行Mistral 7B模型。底行在8个H100 GPU上运行Llama-3 70B模型（4路张量并行+数据并行）。
图7：端到端工作负载性能。顶行和中行在2个和4个A6000 GPU上运行Mistral 7B模型。底行在8个H100 GPU上运行Llama-3 70B模型（4路张量并行+数据并行）。

  • Azure追踪和混合工作负载 (图 8):
    • 实验内容: 使用Azure LLM推理追踪的真实请求到达模式，混合了Tool和VideoQA两个工作负载，模拟真实世界场景。
    • 实验结果: Preble在平均请求延迟、p99请求延迟、TPOT（每输出token时间）和TTFT（首token时间）所有四个指标上均优于SGLang。
    • 分析结论: Preble的有效性在潜在的真实世界、混合工作负载场景下得到了验证。

图8：使用Azure追踪的混合工作负载。在4个GPU上运行Tool和Video工作负载时Preble和SGLang的性能。
图8：使用Azure追踪的混合工作负载。在4个GPU上运行Tool和Video工作负载时Preble和SGLang的性能。

  • vLLM后端结果 (图 9):
    • 实验内容: 将Preble的后端替换为vLLM，并在VideoQA工作负载上进行评估，以展示其通用性。
    • 实验结果: 与使用SGLang作为后端相比，使用vLLM作为后端时Preble的相对性能提升较小。
    • 分析结论: 尽管性能提升幅度较小，但Preble仍然优于原生的vLLM和Oracle分区基线。这表明Preble的设计是通用的，可以与不同的LLM服务后端集成。性能提升较小的原因包括vLLM的前缀缓存功能尚处于beta阶段且性能不如SGLang，以及vLLM不支持将分块预填充与前缀缓存同时使用。

图9：vLLM后端性能。在2个GPU上使用Mistral 7B模型评估Video QA工作负载。
图9：vLLM后端性能。在2个GPU上使用Mistral 7B模型评估Video QA工作负载。

A7 补充细节

5.4 深入分析

消融研究

实验设置: 为了理解Preble各项技术带来的收益，我们进行了一项消融研究。我们使用带有Zipf(1.1)分布的Tool工作负载，以模拟现实生活中工具使用的倾斜流行度。我们从Oracle分区基线开始，逐步增加Preble的特性。

结果分析 (图 10):
1. 首先，在Oracle分区的基础上添加单请求E2策略（§4.2），平均和p99请求延迟均得到改善，因为E2的动态负载划分对于倾斜工作负载更有利。
2. 接着，添加分配后的全局重平衡和自动扩缩，这成功地进一步平衡了负载，导致性能进一步提升，尤其是在p99延迟上。
3. 然后，添加感知预填充/解码的处理，这使得平均和p99延迟都得到更多改善，因为它考虑了当前批次的构成，能更好地利用GPU资源。
4. 最后，添加本地调度器的基于优先级的等待队列调度（§4.3）。正如预期的那样，这项技术改善了p99延迟（因为它旨在提高公平性），但对平均延迟没有影响。

图10：ToolBench（Zipf 1.1分布）性能，4xA6000
图10：ToolBench（Zipf 1.1分布）性能，4xA6000

全局调度器性能与可扩展性

吞吐量测试: 我们测量了系统在Toolbench数据集上的最大吞吐量，发现在工具数量为200和1500（整个数据集）的情况下，性能分别为每秒634和245个请求。在树结构更简单的VideoQA数据集上，我们测量到性能为每秒2931个请求。这表明，对于与我们研究相似的工作负载，在峰值RPS下，我们的全局调度器至少可以管理数百到数千个GPU。

A5 结论

本文识别了面向长共享提示的分布式服务问题。为解决该问题，我们对五个LLM工作负载和一个真实的LLM追踪数据进行了研究。我们提出了E2，一个针对具有长共享提示的LLM使用场景的分布式LLM请求调度算法。我们基于E2算法构建了分布式LLM服务系统Preble。我们的评估结果表明，与当前最先进的服务系统相比，Preble显著提升了LLM服务的性能。

4. 方法细节中的引用汇总

  • 段落: §1 Introduction, 引用[9]
    • 原文描述: "Solving the above challenges perfectly is equivalent to a multi-constrained graph partitioning problem, which is NP hard [9]."
    • 引用文献: 【9，M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1976.】
  • 段落: §4.3 Local Scheduler, 引用[3]
    • 原文描述: "If a selected request has a long and nonshared prompt, we chunk the prompt similar to Sarathi [3]."
    • 引用文献: 【3，Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee. Sarathi: Efficient llm inference by piggybacking decodes with chunked prefills. arXiv preprint arXiv:2308.16369, August 2023.】
  • 段落: §4.3 Local Scheduler, 引用[54]
    • 原文描述: "The former ignores prompt sharing and results in more recomputation; the latter ignores fairness and could result in starvation [54]."
    • 引用文献: 【54，Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast distributed inference serving for large language models. arXiv preprint arXiv:2305.05920, May 2023.】