DejaVu: KV-Cache Streaming for Fast, Fault-Tolerant Generative LLM Serving

发表时间: 2024-03 · arXiv:2403.01876 (ICML 2024)

原文: https://arxiv.org/abs/2403.01876

作者/机构：Foteini Strati 1 2, Sara Mcallister 1 3, Amar Phanishayee 4, Jakub Tarnawski 4, Ana Klimovic 2

速读

一句话结论 DejaVu 提出了一个基于高效 KV Cache 流式传输的分布式大语言模型推理系统，通过将提示词处理与词元生成物理分离、引入微批次级别的显存交换以及状态复制机制，在流水线并行场景下将系统吞吐量提升了最高 2 倍，并大幅降低了节点故障带来的恢复延迟。

要解决什么问题 现有的分布式大语言模型推理系统在流水线并行部署时面临三个严重的效率卡点。首先是提示词处理与词元（Token）生成阶段的延迟呈现双峰分布：提示词处理是计算密集型，耗时长；而词元生成是显存带宽密集型，单步耗时极短（相差可达 106 倍）。将这两个阶段放在同一流水线中混合执行，会导致严重的流水线气泡，使得 GPU 大量闲置，尤其是在请求提前结束并引入新请求时气泡会被进一步放大。其次是显存的严重过度配置，现有系统通常会按照模型支持的最大序列长度为所有微批次预先分配好 KV Cache 显存，但在流水线并行中，每个阶段同一时刻只有一个微批次在使用显存，导致大量显存被无效占用。最后是状态丢失导致的容错成本极高，由于 KV Cache 使得推理过程变为有状态的，一旦集群中某个 GPU 发生故障，现有的系统只能让整个请求从头开始重新计算，这种重新计算提示词和已生成词元的冗余操作会使端到端延迟急剧增加。

怎么做的 系统的内核是一个名为 DejaVuLib 的高效 KV Cache 流式传输底层库，它通过显存内缓冲聚合小块拷贝、逐层传输与计算流水线化等设计，将传输开销降到了极低。基于该库，系统设计了三个核心机制来绕开上述卡点。第一是提示词与词元生成解耦，系统将计算节点划分为专门处理提示词的机器和专门生成词元的机器，通过网络将提示词的 KV Cache 传输给生成节点，从而彻底消除了两阶段混合带来的流水线气泡。为了最大化吞吐量，系统内置了一个资源分配规划器，其核心逻辑是确保解耦后的吞吐量优于基线，即满足以下条件时才进行解耦并计算最佳机器配比：

$$ \frac{Y}{t} > \frac{D-1}{D \cdot (2-m) - 1} $$


其中 $Y$ 是提示词处理耗时，$t$ 是单步词元生成耗时，$D$ 是机器总数，$m$ 是流式传输的额外开销系数。第二是微批次交换，系统将所有正在处理的微批次的 KV Cache 存放在 CPU 内存中，只有当某个微批次轮到当前 GPU 处理时，才将其对应的 KV Cache 预取到 GPU 显存中，计算完成后再将更新的部分写回 CPU。这种按需加载机制打破了显存容量瓶颈，使得系统能够容纳更大的批处理大小。第三是用于容错的状态复制，在词元生成的同时，系统会异步地将每个微批次的 KV Cache 增量流式传输并复制到流水线下一个节点的 CPU 内存中。当中心控制器检测到某个节点宕机时，会直接从相邻节点拉取丢失的 KV Cache 副本，并准确定位到故障发生的微批次和具体步数，直接从断点处恢复生成，完全避免了重新计算提示词的开销。

效果如何 实验在配备 A100-80GB 和 V100-16GB GPU 的集群上进行，评测了 GPT2、OPT（最高 66B）和 BLOOM（176B）模型，请求数据采样自真实的 LMSys 对话数据集。对比的基线方法是 FasterTransformer，它代表了当前支持流水线并行的最先进路线（作者对其进行了修改以支持微批次级别的调度）。在无故障的常规流水线并行设置下，由于有效消除了气泡，该方法在 OPT-66B 和 BLOOM-176B 模型上的吞吐量分别比 FasterTransformer 提升了 1.88 倍和 2 倍。在显存优化方面，微批次交换机制成功支撑了 2 倍的批处理大小，使吞吐量进一步提升了最高 1.8 倍。在注入节点故障的测试中，基线方法因需要从头重算导致微批次延迟增加了 1.91 倍，而该方法凭借状态复制机制仅增加了 1.24 倍，整体恢复运行时间缩短了 1.16 倍。作者也指出了该方法的局限性与失效场景：微批次交换的收益高度依赖于 CPU 与 GPU 之间的 PCIe 带宽，当生成的序列长度过长或批处理大小过大时，将 KV Cache 重新搬运回 GPU 的耗时会显著增加，此时交换机制带来的开销将超过其扩大批处理大小所带来的吞吐量收益。

主要贡献

当前分布式大语言模型（LLM）的推理服务成本高昂，且由于面临三大关键挑战，通常会导致硬件加速器的利用率不足：
1. 流水线气泡问题：由于提示词（prompt）处理和token生成的双峰延迟（bimodal latency）差异，在流水线并行部署中会产生大量气泡（计算空闲）。
2. GPU内存过度配置：为了容纳请求的上下文，系统通常会过度分配GPU内存。
3. 故障恢复时间长：在发生故障时，系统状态丢失会导致漫长的恢复时间。

为了解决这些挑战，本文提出了 DejaVu 系统。该系统的核心目标是通过一个多功能且高效的KV缓存流式传输库（DejaVuLib）来应对上述问题。
本文的核心创新点包括：
* DejaVuLib：设计并实现了一个高效的KV缓存流式处理库。
* 提示词-Token分离（Prompt-token disaggregation）：通过物理分离提示词处理和token生成阶段，有效减少流水线气泡。
* 微批次交换（Microbatch swapping）：实现高效的GPU内存管理，提升内存利用率。
* 状态复制（State replication）：实现低开销的容错机制。
作者在云部署的各种大型模型上验证了这些解决方案的有效性。

图1 各种LLM在2K序列长度（输入+生成token）和半精度（fp16）下的内存占用
图1 各种LLM在2K序列长度（输入+生成token）和半精度（fp16）下的内存占用

背景知识与动机

生成式LLM推理机制。生成式LLM推理包含两个阶段：提示词处理（prompt processing）和自回归token生成（autoregessive token generation）。在提示词处理阶段，模型处理用户定义的输入句子并生成一个新token，此阶段计算密集（compute-bound）。在自回归token生成阶段，模型基于先前生成的token逐个生成新token，此阶段受限于内存带宽（memory bandwidth-bound）。为了避免在每一步重复计算已处理token的键（key）和值（value）向量，推理框架将其存储在KV缓存（KV Cache）中。KV缓存的大小取决于模型层数、隐藏单元数、精度、批次大小和序列长度。由于内存占用巨大（达数百GB），LLM推理通常需要跨多个GPU进行张量并行（单节点内）和流水线并行（跨节点）。

LLM服务面临的挑战。分布式LLM推理面临三个重要挑战：
第一，提示词与Token生成延迟的双峰性。由于提示词处理的token数量等于输入序列长度，该阶段耗时通常比单token生成阶段高出1到2个数量级（本文研究中高出$1.4\times$到$106\times$）。在流水线并行中，这种执行时间的差异会导致流水线气泡，使得某些阶段在等待其他阶段完成时处于空闲状态。特别是当某些请求提前结束（early stopping）并引入新微批次时，气泡问题会进一步恶化。

图2 A100 GPU上使用FasterTransformer（批次大小8，提示词长度1000）的提示词处理和平均单token生成时间。Y轴为对数刻度。
图2 A100 GPU上使用FasterTransformer（批次大小8，提示词长度1000）的提示词处理和平均单token生成时间。Y轴为对数刻度。

第二，GPU内存使用效率低下。在流水线并行设置中，多个微批次（microbatches）需要被不同阶段并发处理以保持各阶段忙碌。现有的框架（如FasterTransformer）为了提高性能，会预先在GPU内存中为所有微批次分配KV缓存。然而，由于每个阶段一次只能顺序处理一个微批次，这就导致了严重的内存过度配置。

第三，状态依赖与故障处理。在分布式集群中，硬件或软件故障是不可避免的。由于流水线并行阶段之间存在数据依赖，一个阶段的故障会导致所有剩余阶段空闲，甚至引发级联故障。更严重的是，由于KV缓存存储在GPU内存中，加速器故障会导致推理请求的缓存数据丢失。现有系统缺乏容错机制，只能从头开始重新处理请求（重新填充KV缓存），这导致端到端请求延迟大幅增加（如图4中示例，延迟增加了$1.89\times$）。

图4 GPT2-1.5B模型在现有系统中发生故障时对推理请求累积延迟的影响
图4 GPT2-1.5B模型在现有系统中发生故障时对推理请求累积延迟的影响

方法细节

缓解流水线气泡的架构设计。为了减轻流水线气泡，作者提出将提示词处理与token生成解耦，通过为每个任务分配独立的机器来实现。通过避免混合提示词和token任务，解耦有助于减少流水线气泡并提高吞吐量。然而，解耦的有效性依赖于提示词KV缓存的快速传输，这可能成为一个瓶颈，特别是在用户提交的提示词尺寸不断增长的情况下，这就强调了对高效KV缓存流式传输机制的需求。此外，一个关键挑战是如何将可用资源划分为提示词处理和token生成以优化系统吞吐量，为此作者采用了一种基于原则的方法来优化资源分配。

优化GPU内存使用的交换机制。为了有效利用GPU内存容量，作者提出在微批次（microbatch）级别在GPU和CPU之间交换KV缓存。所有运行中微批次的KV缓存都存储在CPU中，只有在处理相应的微批次时才将其传输到GPU。这极大地降低了GPU内存需求，允许更大的批次大小，并促进了在有限硬件下的LLM服务。但是，通过带宽有限的PCIe进行CPU-GPU传输可能成为瓶颈，因此需要一种高效的机制来将KV缓存换入和换出GPU。

实现容错的状态复制。对于容错，作者提出将KV缓存复制到持久化存储或远程CPU内存中。在发生故障时，DejaVu将最近计算的值恢复到故障的GPU上，允许推理从最后一个生成的token恢复，从而减少了与其他LLM服务系统相比的恢复时间。在实践中，需要最小化KV缓存流式传输到存储或远程内存的开销，并确保能够快速检测和缓解故障以最小化恢复时间。

DejaVu系统架构概述。DejaVu系统依赖于一个集中式控制器（Controller）来协调推理（Fig 5）。工作节点（Workers）在控制器注册以服务请求，客户端连接到控制器提交请求。随着token的生成，工作节点将token发送给控制器。每个DejaVu Worker都有一个缓存管理器（cache manager），负责处理KV缓存流式传输。缓存管理器了解流水线配置（如流水线深度、提示词或token处理、批次大小等）。当Worker需要将KV缓存流出或流入GPU时，缓存管理器会调用适当的DejaVuLib原语。

图5 完整的DejaVu系统图。启用解耦后，worker仅执行提示词处理（P-worker）或token生成（T-worker）。蓝色箭头代表提示词-token缓存交换，红色箭头代表缓存复制，橙色箭头代表缓存交换。
图5 完整的DejaVu系统图。启用解耦后，worker仅执行提示词处理（P-worker）或token生成（T-worker）。蓝色箭头代表提示词-token缓存交换，红色箭头代表缓存复制，橙色箭头代表缓存交换。

DejaVuLib底层实现。DejaVu建立在FasterTransformer框架之上 [引用文献：Nvidia fastertransformer/https://github.com/NVIDIA/FasterTransformer/2023/NVIDIA]，支持张量和流水线并行。FasterTransformer基于最大序列长度预分配GPU内存作为KV缓存。在处理提示词后，token逐个生成，每次生成仅更新Key缓存中一个小的、非连续的部分 （Fig 6）。由于复制大量非连续的小内存区域会导致显著开销，作者实施了三项关键优化：

图6 简化版的2D Key缓存及在提示词处理和token生成期间更新的部分
图6 简化版的2D Key缓存及在提示词处理和token生成期间更新的部分

缓冲复制（Buffered copies）。第一项优化针对单个token生成导致的KV缓存中多个非连续小更新。作者没有使用多个cudaMemcpy调用来复制这些块，而是利用GPU DRAM的高带宽，将所有更新聚合到GPU内存中的一个临时缓冲区（Fig 7a）。一旦临时缓冲区被填满，就将其复制到适当的目的地。由于这些缓冲区被重复使用，GPU内存容量的开销可以忽略不计。

图7a 缓冲复制：我们将小更新聚合到GPU中的连续缓冲区中，然后将该缓冲区复制出去。
图7a 缓冲复制：我们将小更新聚合到GPU中的连续缓冲区中，然后将该缓冲区复制出去。

逐层提示词缓存流式传输（Layer-by-layer prompt cache streaming）。第二项优化考虑到提示词处理是逐层进行的，因此作者也逐层流式传输提示词缓存（Fig 7b）。这类似于分布式ML训练中的无等待反向传播 [引用文献：Poseidon: An efficient communication architecture for distributed deep learning on GPU clusters/https://www.usenix.org/conference/atc17/technical-sessions/presentation/zhang/2017/USENIX ATC 17]。在流水线并行设置中，作者进一步将微批次$i$的提示词流式传输与微批次$i+1$的计算并行化。

图7b 提示词KV缓存流式传输与计算的逐层流水线化。
图7b 提示词KV缓存流式传输与计算的逐层流水线化。

Token计算与流式传输并行化（Token computation and streaming parallelization）。第三项优化针对多步的token生成。在单机设置中，作者在步骤$i+1$进行时，流式传输步骤$i$的KV缓存。在流水线并行设置中，作者将微批次$i$步骤$j$的缓存流式传输与微批次$i+1$步骤$j$的计算并行化（Fig 7c）。作者使用一个后台CPU线程负责缓存流式传输，并使用CUDA流 [引用文献：Cuda c/c++ streams and concurrency/https://developer.download.nvidia.com/CUDA/training/StreamsAndConcurrencyWebinar.pdf/2015/NVIDIA] 将GPU上的KV缓存流式传输与计算并行化。

图7c Token流式传输与计算的流水线化。我们还将微批次$i$的流式传输与微批次$i+1$的提示词处理流水线化。
图7c Token流式传输与计算的流水线化。我们还将微批次$i$的流式传输与微批次$i+1$的提示词处理流水线化。

DejaVuLib原语设计。DejaVuLib被构建为一个多功能库，旨在处理需要KV缓存流式传输的各种配置。由于源、目标、数据量和传输方法取决于流水线设置和网络拓扑，DejaVuLib提供了不同抽象级别的原语（表1）。例如，flush和fetch处理本地或远程主机上的连续块复制（支持CUDA、NCCL [引用文献：Nvidia collective communications library (nccl)/https://developer.nvidia.com/nccl/2023/NVIDIA] 、MPI [引用文献：Open mpi: Open source high performance computing/https://www.open-mpi.org//2023/OpenMPI] 或 Boost [引用文献：Boost.asio/https://www.boost.org/doc/libs/1_78_0/doc/html/boost_asio.html/2021/Boost]） ；scatter和gather负责将非连续区域分块并编排移动；最高层的stream_out和stream_in则根据推理设置（worker数量、流水线深度、批次大小）在源端拆分或在目标端合并缓存。

原语 功能描述
stream_out, stream_in 给定源（或目标）worker、KV缓存及推理设置，为KV缓存的不同块找到合适的目标（或源）。这可能涉及在源端拆分缓存或在目标端合并缓存块。
scatter, gather 给定KV缓存的非连续区域和本地或远程目标（或源），将该区域分块为连续传输并编排移动。
flush, fetch 复制同一主机或远程主机上的连续KV缓存块。支持使用CUDA进行本地复制，使用NCCL、MPI或Boost进行远程复制。

表1 DejaVuLib原语说明

基于原则的资源分配规划器。在提示词-Token分离架构中，为了最大化系统吞吐量并满足GPU内存约束，作者开发了一个资源分配规划器。假设有$D$台机器，每台机器聚合GPU内存为$M$ GB，模型有$L$层。注意力层参数内存需求为$W_i$，单层提示词KV缓存为$C_i$，单层token KV缓存为$K_i$。对于提示词流水线，深度$D_p$需满足：$D_p \geq \lceil \frac{L \cdot (C_0 + W_0)}{M} \rceil$。对于Token生成流水线，深度$D_t$需满足：$D_t \geq \frac{L \cdot W_0}{M - L \cdot (C_0 + K_0)}$。为了使分离后的系统吞吐量最大化，规划器计算逆吞吐量（Inverse throughput, $I$）。基线（未解耦）的逆吞吐量为：$I_c = \frac{(D-1)(Y-t)}{D} + Y + N \cdot t$（其中$Y$为提示词处理时间，$t$为单token生成时间，$N$为生成的token数）。解耦系统的性能$I_{dis} = \max(I_t, I_p)$，当$I_t = I_p$时达到最优，推导出分配公式：$D_t = \frac{D \cdot N \cdot t}{m \cdot Y + N \cdot t}$ 且 $D_p = \frac{D \cdot m \cdot Y}{m \cdot Y + N \cdot t}$（$m$为缓存流式传输的额外开销因子）。只有当 $\frac{Y}{t} > \frac{D-1}{D \cdot (2-m) - 1}$ 且 $m \in [1, 2)$ 时，解耦系统才比基线更有利。

快速提示词KV缓存传输过程。系统利用前述优化（1）和（2）将逐层提示词KV缓存流式传输与提示词处理流水线化。为了避免GPU内存过载，系统先将KV缓存传输到本地CPU内存，然后再传输到token机器的CPU内存。缓存管理器调用stream_out原语，根据流水线深度和批次大小调用底层原语来拆分或合并缓存。Token机器会检查其本地CPU内存中是否有可用的提示词KV缓存，一旦可用，就将其加载到GPU内存并开始token生成。

微批次交换（Microbatch Swapping）工作流。为了以最小开销促进微批次交换，系统利用了所有三项流式传输优化。对于深度为$D$的流水线，每个微批次需要$M$ GB内存，系统在CPU内存中分配$D \cdot M$ GB，在GPU内存中仅分配$2 \cdot M$ GB。在微批次$x$的token生成步骤$t$开始之前，DejaVu将其KV缓存从CPU预取到GPU（swap in）。步骤$t$完成后，缓存管理器将微批次$x$对应于步骤$t$的KV缓存更新部分传输回CPU（swap out）。具体而言（Fig 9），当流水线中第4阶段正在生成微批次1的token时，它会并行将微批次2换入；当微批次1处理完成后，其新增内容被换出。对于$N$阶段流水线，当处理微批次$x$时，微批次$(x+1)\%N$被换入，微批次$(x-1)\%N$被换出。

图9 4阶段token生成流水线随时间推移的微批次KV缓存交换。我们展示了阶段4的微批次交换，但所有其他阶段遵循类似的模式。
图9 4阶段token生成流水线随时间推移的微批次KV缓存交换。我们展示了阶段4的微批次交换，但所有其他阶段遵循类似的模式。

故障检测与四步恢复机制。DejaVu控制器负责检测故障，工作节点定期向控制器发送心跳。如果控制器在规定时间内未收到心跳，则判定该节点故障，并通知其他节点停止服务。在正常运行期间，每个工作节点$x$将其KV缓存异步增量地流式传输到节点$(x+1)\%N$作为副本。当收到微批次$j$和步骤$t$的更新时，节点发送确认消息$(x, j, t)$给控制器。当节点$x$发生故障时，遵循以下四个步骤进行恢复（Fig 10）：首先，节点$(x+1)\%N$将其托管的副本发送回新拉起的节点$x$（恢复$x$丢失的自身缓存）；接着，节点$(x-1)\%N$将其缓存发送给节点$x$（恢复$x$上丢失的副本）；然后，控制器根据确认消息确定需要重新执行的微批次$j$和步骤$t$；最后，由于阶段$x$需要前置阶段的输入，控制器将$(j, t)$广播给所有节点，流水线从阶段1的微批次$j$和步骤$t$恢复推理。

图10 流水线故障和恢复示例。Token阶段2发生故障（F），被DejaVu控制器检测到（D）。流水线被修复（R），包括适当地在各处复制KV缓存。修复完成后，推理继续进行。
图10 流水线故障和恢复示例。Token阶段2发生故障（F），被DejaVu控制器检测到（D）。流水线被修复（R），包括适当地在各处复制KV缓存。修复完成后，推理继续进行。

方法细节引用汇总

  • [引用文献：Nvidia fastertransformer/https://github.com/NVIDIA/FasterTransformer/2023/NVIDIA]：在描述DejaVuLib底层实现时引用，指明系统构建在FasterTransformer框架之上。
  • [引用文献：Poseidon: An efficient communication architecture for distributed deep learning on GPU clusters/https://www.usenix.org/conference/atc17/technical-sessions/presentation/zhang/2017/USENIX ATC 17]：在描述逐层提示词缓存流式传输优化时引用，类比了分布式训练中的无等待反向传播技术。
  • [引用文献：Cuda c/c++ streams and concurrency/https://developer.download.nvidia.com/CUDA/training/StreamsAndConcurrencyWebinar.pdf/2015/NVIDIA]：在描述计算与传输并行化时引用，说明使用CUDA流来掩盖传输开销。
  • [引用文献：Nvidia collective communications library (nccl)/https://developer.nvidia.com/nccl/2023/NVIDIA]：在描述DejaVuLib原语时引用，作为支持的远程内存复制底层库之一。
  • [引用文献：Open mpi: Open source high performance computing/https://www.open-mpi.org//2023/OpenMPI]：在描述DejaVuLib原语时引用，作为支持的远程内存复制底层库之一。
  • [引用文献：Boost.asio/https://www.boost.org/doc/libs/1_78_0/doc/html/boost_asio.html/2021/Boost]：在描述DejaVuLib原语时引用，作为支持的远程内存复制底层库之一。

实验环境

  • 硬件配置：使用了两种虚拟机。一种配备 2块 A100-80GB GPU，虚拟机间网络带宽为 40 Gbps；另一种配备 V100-16GB GPU，虚拟机间网络带宽为 32 Gbps。
  • 模型配置：使用了HuggingFace版本的 GPT2 (1.5B), OPT (13B, 30B, 66B) 和 BLOOM (176B) 模型，并适配了 FasterTransformer。所有模型均使用半精度（fp16）。
  • 数据集：使用了 LMSys 数据集（Zheng et al., 2023）中的请求来采样生成的token数量。
  • 软件与基线配置：代码基于 FasterTransformer 实现。由于原版 FasterTransformer 不允许批次中的请求提前结束，作者对其进行了修改，允许在微批次级别进行调度（即当任何阶段的微批次完成时，可被下一个可用微批次替换）作为对比基线。

实验结果

DejaVuLib 微基准测试（5.1节）
* 实验内容：评估DejaVuLib流式传输机制的开销。使用提示词大小500、生成500个新token的请求，测量流式传输到本地SSD和远程CPU内存的延迟。
* 实验结果：与不进行流式传输相比，流式传输到本地SSD和远程CPU内存的延迟减速始终在 $2\%$ 以内。
* 分析结论：DejaVuLib的开销极低。细分优化显示（图11），“缓冲复制”相比朴素传输提升了 $95\times$ 的性能，而另外两项优化进一步提高了 $1.4\times$ 的性能。
* 图表引用：Fig 11。

图11 逐步应用DejaVuLib提出的优化时，流式传输KV到远程CPU内存引起的单批次延迟减速。
图11 逐步应用DejaVuLib提出的优化时，流式传输KV到远程CPU内存引起的单批次延迟减速。

无故障情况下的端到端性能（5.2.1节）
* 实验内容：评估提示词-Token分离架构相比于不分离基线的性能。固定提示词大小为1000，使用LMSys数据集采样生成token数。采用泊松分布开环提交请求。
* 实验结果：对于OPT-66B和BLOOM-176B模型，DejaVu在保持低延迟的同时，吞吐量分别比FasterTransformer基线高出最多 $1.88\times$ 和 $2\times$。
* 分析结论：基线系统中由于请求提前结束引入新提示词，导致严重的气泡问题。DejaVu通过分离流水线并由规划器最优分配机器，消除了等待气泡。提示词越大，解耦优势越明显。
* 图表引用：Fig 12。

图12 LMSys数据集中OPT-66B和BLOOM-176B模型的端到端性能。Baseline-X表示流水线使用了X台机器。DejaVu-X-Y表示X台机器用于提示词处理，Y台用于token生成。
图12 LMSys数据集中OPT-66B和BLOOM-176B模型的端到端性能。Baseline-X表示流水线使用了X台机器。DejaVu-X-Y表示X台机器用于提示词处理，Y台用于token生成。

微批次交换的性能（5.2.2节）
* 实验内容：对比在给定GPU集合下，不使用交换的最大可行批次大小 $B$ 与启用交换后批次大小为 $2 \cdot B$ 的系统吞吐量。
* 实验结果：通过容纳更大的批次大小，吞吐量提升了最多 $1.8\times$。
* 分析结论：交换机制显著降低了KV缓存的GPU内存需求，允许更大的批次大小。其主要瓶颈是将缓存带回GPU的时间，这取决于PCIe带宽。
* 图表引用：Fig 13。

图13 微批次交换的益处
图13 微批次交换的益处

存在故障情况下的性能（5.2.3节）
* 实验内容：在4节点集群（4阶段流水线）上服务OPT-66B模型。在token生成步骤1200人为注入流水线阶段故障。
* 实验结果：在基线系统中，单次故障导致一组微批次的延迟增加了 $1.91\times$。相比之下，DejaVu的延迟仅增加了 $1.24\times$。在连续注入多次故障的实验中，DejaVu的运行时间比基线短 $1.16\times$。
* 分析结论：基线系统在故障后需要从头开始处理活跃的微批次；而DejaVu凭借轻量级缓存流式传输协议，仅需从最新复制的步骤重新启动token生成，大幅减少了冗余计算。
* 图表引用：Fig 14，Fig 15。

图14 在token生成步骤1200发生故障时对单个微批次累积延迟的影响。
图15 随时间推移的请求完成情况。我们在600、1200和1800秒后引入故障（用黑色X标记）。

相关工作

LLM服务系统。随着LLM的广泛采用，出现了如FasterTransformer、TensorRT-LLM和DeepSpeed Inference等服务系统。Orca引入了迭代级调度，但忽视了提示词与token生成时间差异带来的负面影响。vLLM通过PagedAttention减少内存过度配置，并在内存压力下将请求换出到CPU。FlexGen提出利用CPU内存和磁盘交换来在有限显存下服务LLM。与这些工作不同，DejaVu专注于流水线并行推理，并在微批次级别进行交换。此外，H2O和LESS等利用缓存稀疏性驱逐KV缓存条目的工作与DejaVu是正交互补的。

提示词和Token处理的差异。与DejaVu同时期的一些工作也关注了这一差异。Sarathi提出将预填充请求分割成较小的块并与解码合并。Splitwise和DistServe提出分离提示词和token处理。Splitwise主要基于模拟，旨在异构GPU上降低功耗和成本，不支持近期大模型所需的流水线并行。DistServe基于模型特征采用不同的批处理和并行策略。DejaVu则使用解耦来最小化流水线并行设置中的气泡，并优化资源规划以最大化吞吐量。

抢占式资源上的LLM服务。SpotServe是一个在现货云资源上服务LLM的框架，它利用VM被抢占前的宽限期（如AWS中的30秒）迁移KV缓存。然而，这种方法无法防止突然故障。相比之下，DejaVu使用开销极小的token级KV缓存复制策略，提供持续的容错和无缝恢复。

结论

DejaVu是一个用于大规模高效、容错LLM服务的系统。它将提示词处理与token生成解耦，以缓解由两者执行时间差异引起的流水线气泡。此外，它通过实现与CPU内存之间的微批次级别交换，优化了流水线并行设置中的内存利用率。最后，它采用了缓存复制和故障处理机制，以提供无缝恢复并最大程度减少故障发生时的冗余工作。DejaVu依赖于DejaVuLib这一模块化库，该库允许在各种设置下以极小开销进行KV缓存流式传输。与最先进的系统相比，DejaVu将LLM服务吞吐量提高了最高 $2\times$。

附录

A. 提示词处理与Token生成时间对比
作者在附录A中展示了不同模型（OPT-13B, OPT-66B, BLOOM-176B）在不同批次大小和提示词长度下的处理时间。结果表明，生成第一个token（即提示词处理）的时间远高于后续token的生成时间。提示词处理时间几乎随批次大小和提示词长度线性扩展，并且比单token生成延迟高出最高 $106\times$。
相关图表：Fig 16, Fig 17, Fig 18, Fig 19。

图16 批次大小为8的OPT-13B和OPT-66B服务的提示词处理和token生成时间
图17 OPT-13B模型的提示词处理和token生成时间
图18 OPT-66B模型的提示词处理和token生成时间
图19 BLOOM-176B模型的提示词处理和token生成时间

B. DejaVu规划器深入评估
作者在附录B中使用模拟器评估了资源分离在不同场景下的表现。模拟了三种策略：基线（张量并行+流水线并行）、基线-DP（增加数据并行）和DejaVu（解耦流水线）。
可扩展性与提前结束的影响。基线策略在机器数量增加时完工时间（Makespan）会缩短，但其可扩展性会随着流水线深度增加而下降（成本上升）。此外，在真实轨迹（如LMSys）中，由于请求提前结束（early stops），基线系统的完工时间会出现波动（Fig 24）。虽然增加微批次大小可以减少完工时间，但这也会按比例增加提示词计算时间，从而在请求提前退出时放大流水线气泡，因此更大的微批次并不总是有益的（Fig 25）。
解耦的优势。引入数据并行（基线-DP）虽然优于纯基线，但不同流水线间会因生成的token数量不均而导致负载不平衡。DejaVu通过解耦彻底消除了提前结束带来的气泡影响。在分配相同机器数量时，DejaVu的完工时间比基线和基线-DP分别缩短了 $4.2\times$ 和 $2.22\times$。
相关图表：Fig 20, Fig 21, Fig 22, Fig 23, Fig 24, Fig 25。

图20 OPT-66B模型在2-A100-80GB机器上使用不同策略找到的最佳配置的完工时间和成本。每种用例的最佳配置见表2
图21 OPT-66B模型在4-A100-80GB机器上使用不同策略找到的最佳配置的完工时间和成本。每种用例的最佳配置见表3
图22 OPT-30B模型在4-V100-16GB机器上使用不同策略找到的最佳配置的完工时间和成本。每种用例的最佳配置见表4
图23 BLOOM-176B模型在4-A100-80GB机器上使用不同策略找到的最佳配置的完工时间和成本。每种用例的最佳配置见表5
图24 BLOOM-176B在改变可用机器数量时有无提前停止的完工时间。我们保持微批次大小恒定为16个请求。
图25 BLOOM-176B在8台机器上，改变微批次大小时有无提前停止的完工时间。

C. 解耦的执行轨迹对比
附录C通过执行轨迹图（Fig 26）直观展示了基线（混合提示词和token处理）与解耦架构的对比。在提示词延迟比token延迟高10倍的情况下，解耦架构能有效消除空闲气泡。

图26 (a) 提示词处理和token生成在同一流水线。
图26 (b) 使用不同的流水线进行提示词处理和token生成。对比将4台机器同时用于提示词和token，与使用2台机器处理提示词、2台机器生成token的情况。

D. 流式传输微基准测试
附录D进一步展示了DejaVuLib在单批次（无流水线并行）下的流式传输减速情况（Fig 27）。流式传输到远程CPU或本地SSD的减速始终在 $2\%$ 以内，证明了该库极低的开销。

图27 DejaVu KV缓存流式传输的单批次减速
图27 DejaVu KV缓存流式传输的单批次减速

E. 理解微批次交换的益处
理论形式化分析。微批次交换的性能很大程度上取决于将KV缓存换回GPU所需的时间。假设在不交换时最大批次为 $B$，启用交换后为 $2 \cdot B$。提示词处理时间分别为 $P$ 和 $2 \cdot P$，单token生成时间 $t$ 保持恒定。微批次交换带来更好吞吐量的条件是：

$$2 \cdot N \cdot t \geq \sum_{i=p}^{i=N+p} \max(t, transf_i)$$


其中 $transf_i = \frac{i \cdot B \cdot C_i}{pciebw}$ 是从主机内存将KV缓存传回GPU的时间（$C_i$为单token单请求缓存大小，$pciebw$为PCIe带宽）。
实验分析。对于给定模型，影响交换性能的主要因素是批次大小和生成的token数量。实验表明（Fig 28-31），当批次大小或序列长度过大时，缓存换入的开销变得非常高，以至于交换不再有益。这为系统在实际部署中是否启用交换提供了决策依据。

图28 改变序列长度时有无交换的吞吐量
图29 OPT-30B, 6 V100-16GB的吞吐量
图30 OPT-66B, 2 A100-80GB的吞吐量
图31 BLOOM-176B, 5 A100-80GB的吞吐量