作者/机构: Ruoyu Qin, Zheming Li, Weiran He (Moonshot AI); Mingxing Zhang, Yongwei Wu, Weimin Zheng (Tsinghua University); Xinran Xu (Moonshot AI)

A1 主要贡献

本文介绍了Mooncake，一个为领先的LLM服务Kimi提供支持的服务平台。

核心问题：随着大型语言模型（LLM）在各种场景中的广泛应用，其服务工作负载变得日益多样化，这些工作负载在输入/输出长度、到达频率和分布上各不相同，并且对服务水平目标（SLO）有不同的要求。作为模型即服务（MaaS）提供商，其主要目标是在满足各种复杂约束（主要是与延迟相关的TTFT和TBT）的同时，最大化直接影响收入的整体有效吞吐量。此外，在GPU供应有限的背景下，MaaS提供商经常面临严重的过载问题，这给调度带来了现有研究未曾探讨过的独特挑战。

研究目标：为了解决上述问题，研究目标是设计一个能够充分利用GPU集群中各种可用资源（GPU、CPU、DRAM、SSD）的LLM服务架构。该架构旨在通过解耦和重组资源池来优化整体吞吐量，特别是在长上下文和高负载场景下，同时满足延迟相关的SLO。

核心贡献与创新点：
1. 提出Mooncake架构：一个以KVCache为中心的分解式架构，该架构分离了预填充（prefill）和解码（decoding）集群，并利用GPU集群中未被充分利用的CPU、DRAM和SSD资源实现了一个分解式的KVCache缓存池。
2. KVCache为中心的调度器：设计并实现了名为Conductor的全局调度器，它以KVCache为中心进行调度和优化，平衡了最大化缓存重用、实例负载和满足SLO之间的复杂关系。
3. 针对长上下文的优化：
* 分块流水线并行（CPP）：为处理长上下文输入，实现了跨多节点的分块流水线并行机制，与传统的序列并行（SP）相比，该机制减少了网络消耗并简化了对频繁弹性扩展的依赖。
* 逐层预填充（Layer-wise Prefill）：通过与计算重叠的KVCache流式传输，有效减少了VRAM占用成本和延迟。
4. 面向过载场景的调度策略：
* 基于预测的提前拒绝策略：针对MaaS服务中常见的过载问题，开发了一种独特的提前拒绝策略，以减少在过载情况下因请求最终无法完成而造成的计算资源浪费。
* 解决负载波动问题：识别并解决了由直接实施提前拒绝策略引起的预填充和解码实例之间的负载波动问题，并通过预测未来负载来缓解此问题。
5. 开源真实世界请求追踪：提供了一个包含真实工作负载请求时间、输入/输出长度和重映射缓存块哈希的追踪数据集，这是首个可用于真实世界KVCache重用分析的开源数据集。

实验结果表明，在长上下文场景中，Mooncake相比基线方法在满足SLO的同时，可在某些模拟场景下实现高达525%的吞吐量提升。在真实工作负载下，Mooncake使Kimi能够多处理75%的请求。

A2 背景知识与问题定义

Transformer架构与推理阶段：现代大型语言模型（LLM）基于Transformer架构，利用注意力机制和多层感知机（MLP）处理输入。像GPT【索引10，Language models are unsupervised multitask learners，2019，OpenAI blog】和LLaMA【索引11，Llama: Open and efficient foundation language models，2023】这类流行的模型采用仅解码器结构。每个推理请求在逻辑上分为两个阶段：预填充（prefill）阶段和解码（decoding）阶段。

预填充与解码阶段的计算特性：在预填充阶段，所有输入token被并行处理，生成第一个输出token，同时存储计算出的键（key）和值（value）的中间结果，即KVCache。解码阶段则利用此KVCache自回归地生成新token。预填充阶段的计算密集度高，其计算时间通常随输入长度超线性增长，因为注意力网络的计算复杂度与输入长度成二次方关系，而MLP的复杂度是线性的。相比之下，解码阶段由于自回归生成的限制，每次只处理一个token，因此是内存受限的，其计算时间随批大小次线性增长。

图2：对于伪LLaMA2-70B模型，预填充和解码阶段在不同序列长度或批大小下的归一化吞吐量和延迟。

解码阶段优化：在解码阶段，一个广泛使用的优化是连续批处理（continuous batching）【索引12，Orca: A distributed serving system for {Transformer-Based} generative models，2022，OSDI 22；索引13，Efficient memory management for large language model serving with pagedattention，2023，SOSP】。在每次迭代前，调度器检查所有请求的状态，将新到达的请求加入批处理的预填充阶段，同时移除已完成的请求。

服务水平目标（SLO）：由于预填充和解码阶段的特性不同，MaaS提供商设置了不同的指标来衡量它们各自的服务水平目标（SLO）。具体来说，预填充阶段主要关注从请求到达至生成第一个token之间的延迟，即首token时间（TTFT）。而解码阶段则关注同一请求连续生成token之间的延迟，即token间时间（TBT）。

MaaS提供商的优化目标：作为MaaS提供商，通过满足服务协议定义的SLO指标来确保服务质量至关重要。例如，一个指标TTFTP90 = 4x意味着90%的推理请求的TTFT不会超过在无干扰情况下相同条件下单个请求运行时间的四倍。在本文的端到端实验中（§8.1），我们设置TTFTP90 = 10x和TBTP90 = 5x。在实际部署中，我们设置固定的TTFT和TBT的SLO。如果监控检测到SLO未被满足，我们会增加推理资源或拒绝部分传入请求。

面向过载的调度问题：由于当前GPU供应紧张，弹性扩展推理集群通常不可行。因此，决定拒绝哪些请求成为面向过载调度的核心问题。我们的主要目标是在遵守SLO的同时最大化整体吞-吐量，这一概念在其他研究【索引8，Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving，2024；索引14，Loongserve: Efficiently serving long-context large language models with elastic sequence parallelism，2024】中被称为“goodput”。我们的方法不同之处在于，只有完全完成执行的请求才被计入goodput的衡量标准。否则，所有先前消耗/生成的token都不被计算，相应的资源被浪费。换言之，如果一个请求无法在SLO下完成其全部执行，就应尽早拒绝。实现这一目标不仅需要优化预填充和解码阶段的架构，还需要具备预测短期未来负载的能力。

A3 方法细节

Mooncake的分解式架构概览

整体架构设计：如图1所示，Mooncake采用了一种分解式架构，不仅将预填充（prefill）节点与解码（decoding）节点分离，还将GPU集群的CPU、DRAM、SSD和RDMA资源组合起来，实现了一个分解式的KVCache。这种分解式缓存利用了未被充分利用的资源，以提供充足的缓存容量和传输带宽，从而在无需额外成本的情况下实现了高效的近GPU前缀缓存。

KVCache的存储与传输：图3展示了KVCache块的存储和传输逻辑。在CPU内存中，KVCache以分页块的形式存储。根据请求模式，它可以使用如LRU（最近最少使用）、LFU（最不经常使用）或基于请求特性的算法等缓存淘汰算法。这些KVCache块在CPU和GPU之间的传输由一个独立的、基于（GPUDirect）RDMA的组件“Messenger”处理。这种架构也使我们能够向外部用户提供上下文缓存API，以实现更高的KVCache重用率。

图3：CPU内存中的KVCache池。每个块都附加一个由其自身哈希及其前缀共同决定的哈希值，用于去重。

全局调度器Conductor：为了调度所有这些分解式组件，Mooncake在其核心实现了一个名为Conductor的全局调度器。Conductor负责根据KVCache的当前分布和工作负载来分派请求。如果对未来的推理有利，它还会复制或交换某些KVCache块。

请求处理工作流：具体来说，图4展示了一个请求的典型工作流。一旦token化完成，Conductor会选择一对预填充节点和一个解码节点，并启动一个包含四个步骤的工作流：
1. KVCache重用：选定的预填充节点（组）接收一个请求，该请求包含原始输入、可重用的前缀缓存的块ID以及为该请求分配的完整缓存的块ID。它根据前缀缓存块ID将前缀缓存从远程CPU内存加载到GPU内存中以启动请求。如果不存在前缀缓存，则跳过此步骤。此选择平衡了三个目标：尽可能多地重用KVCache、平衡不同预填充节点的负载以及保证TTFT SLO。这导致了一种以KVCache为中心的调度，将在§6中进一步讨论。
2. 增量预填充：预填充节点（组）使用前缀缓存完成预填充阶段，并将新生成的增量KVCache存回CPU内存。如果未缓存的输入token数量超过某个阈值（prefill_chunk），预填充阶段将被分割成多个块并以流水线方式执行。该阈值被选择以充分利用相应GPU的计算能力，通常大于1000个token。使用分块但仍保持分解的预填充节点的原因在§5.1中解释。
3. KVCache传输：前述的Messenger服务部署在每个节点中，用于管理和传输这些缓存。每个Messenger作为其各自推理实例内的独立进程运行，接收信号以促进高速、跨机器的KVCache传输。此步骤是异步执行的，并与上述增量预填充步骤重叠，将每个模型层生成的KVCache流式传输到目标解码节点的CPU内存中，以减少等待时间。
4. 解码：在所有KVCache都到达解码节点的CPU DRAM后，请求以连续批处理的方式加入下一个批次。Conductor会根据当前负载预先选择解码节点，以确保其不违反TBT SLO。然而，这个SLO会由本地调度器进行双重检查，因为预期的负载可能在预填充阶段后发生了变化。这种双重检查可能导致请求被拒绝，此时相应的预填充成本就被浪费了。

图4：推理实例的工作流。(*) 对于预填充实例，KVCache层的加载和存储操作是逐层进行的，并与预填充计算并行，以减轻传输开销(见§5.2)。(†) 对于解码实例，异步加载与GPU解码并发执行，以防止GPU空闲。

预填充池的实现

维持分解式架构的必要性：尽管许多研究人员【索引7，Splitwise: Efficient generative llm inference using phase splitting，2023；索引8，Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving，2024；索引9，Inference without interference: Disaggregate llm inference for mixed downstream workloads，2024】与我们有同样的直觉，即使用分解式架构，但值得讨论的是，随着分块预填充（chunked prefill）【索引15，Taming throughput-latency tradeoff in llm inference with sarathi-serve，2024】的引入，这种分离是否仍然必要。分块预填充将输入token分成多个小块，加入连续批处理过程。这种方法有两个明显的好处：1）不分离时，所有节点被平等对待，使调度更容易；2）将分块预填充内联到解码批处理中可以提高解码批处理的计算强度，从而获得更好的MFU。

Mooncake的设计决策：经过仔细考虑，我们决定维持Mooncake的分解式架构。一个请求的预填充只有在可以不分块地转发且不损害TBT SLO的情况下，才会被内联到解码批处理中。这个决定主要有两个原因：1）预填充节点需要不同的跨节点并行设置来处理长上下文（§5.1）。2）它为节省VRAM提供了独特的机会（§5.2）。

多节点预填充

长上下文预填充的挑战：最近LLM的可用上下文长度正在迅速增加，从8k到128K甚至1M【索引16，Our next-generation model: Gemini 1.5，2024，Google】。通常，对于这类长上下文请求，输入token可能比输出token大10到100倍，使得优化TTFT至关重要。由于长上下文预填充中存在丰富的并行性，使用超过单个8x GPU节点来并行处理它们是可取的。然而，将张量并行（TP）扩展到多个节点需要在每层进行两次昂贵的基于RDMA的all-reduce操作，这会显著降低预填充节点的MFU。

序列并行（SP）的局限性：最近，许多工作提出了序列并行（SP）【索引17，Deepspeed ulysses: System optimizations for enabling training of extreme long sequence transformer models，2023；索引18，Ring attention with blockwise transformers for near-infinite context，2023；索引19，Striped attention: Faster ring attention for causal transformers，2023；索引20，Lightseq: Sequence level parallelism for distributed training of long context transformers，2023；索引21，Reducing activation recomputation in large transformer models，2023；索引22，Sequence parallelism: Long sequence training from system perspective，2023；索引23，Usp: A unified sequence parallelism approach for long context generative ai，2024】。SP将请求的输入序列在不同节点间划分以实现加速。这些SP方法利用了注意力算子的结合律，在实现Ring Attention【索引18】或Striped Attention【索引19】时，每层至少需要一次跨节点通信。这大大减少了网络消耗并提高了MFU。

采用SP的问题：然而，与仅使用单节点TP相比，采用SP仍然会导致较差的MFU。一种理想的部署方式是将预填充节点分为两组：一组仅使用TP，另一组使用SP。仅在为满足TTFT SLO所必需时，才将请求分派到SP组。这种进一步的分解导致了动态调整每组节点数量的问题，因为静态的并行设置可能导致整个集群的利用率低下。最近的研究【索引14，Loongserve: Efficiently serving long-context large language models with elastic sequence parallelism，2024】提出了弹性序列并行来动态扩展或缩减SP组。虽然可行，但这为我们的架构增加了复杂性。例如，它需要预先建立一个全局通信组，并在调整期间考虑缓存重用利用率和SLO需求违规等指标时，使Conductor的设计复杂化。这对于我们部署期间需要频繁即时扩展性的情况构成了挑战。此外，SP仍然需要频繁的跨节点通信，这降低了MFU并与跨节点传输KVCache的网络资源竞争。

分块流水线并行（CPP）：为了解决这个问题，Mooncake利用仅解码器transformer的自回归特性，为长上下文预填充实现了分块流水线并行（CPP）。我们将预填充集群中的每X个节点分组为一个流水线预填充节点组。对于每个请求，其输入token被划分为多个块，每个块的长度不超过prefill_chunk。同一请求的不同块可以由不同节点同时处理，从而实现处理的并行化并减少TTFT。

CPP的优势：CPP提供了两个主要好处：1）与训练中的流水线并行类似，它仅在每个流水线阶段的边界需要跨节点通信，这可以很容易地与计算重叠。这带来了更好的MFU和更少的与KVCache传输的网络资源竞争。2）它自然地适用于短上下文和长上下文，对短上下文预填充没有显著开销，并避免了节点分区的频繁动态调整。这种基于流水线的加速方法已在训练系统【索引24，Terapipe: Token-level pipeline parallelism for training large-scale language models，2021，ICML】中被探索过，但据我们所知，这是其在推理阶段的首次应用，因为长上下文推理直到最近才出现。

逐层预填充

VRAM占用成本：除了计算能力，VRAM的有限大小也是一种宝贵资源，我们的目标是最小化状态（主要是KVCache）对VRAM的占用。理论上，如果一个请求的KVCache大小为S，处理时间为T，其占用成本为S * T。如果一个请求被分块，并且每个块的处理与分块预填充中的其他解码请求内联处理，T将会增加，导致更大的占用成本。

通过重叠降低占用成本：此外，由于预填充是逐层处理且受计算限制，因此可以将KVCache的传输和转储与计算重叠，从而进一步降低其占用成本。在Mooncake中，KVCache的加载和存储通过启动和等待操作异步执行。在每层的注意力计算开始之前，模型等待该层KVCache的异步加载完成，并触发下一层KVCache的异步加载。注意力计算完成后，启动该层KVCache的异步存储。一旦所有层的计算完成，进程等待所有异步存储操作的完成。传输重叠使得预填充实例的执行时间大致等于KVCache加载时间或标准预填充时间，具体取决于前缀缓存相对于输入长度的比例。

实验验证：KVCache存储延迟的实验结果如图7所示，表明逐层预填充可以有效减少长上下文请求的延迟。

图7：存储不同请求长度的KVCache的延迟（逐层延迟指逐层预填充与不存储KVCache的预填充之间的延迟差）。

逐层预填充的主要优势：这种重叠效率的主要优势在于，它使我们能够在预填充调度中忽略可用的VRAM大小，只要它能容纳单个请求即可。如图1所示，预填充节点的调度仅考虑KVCache的分布和可用的DRAM大小。

未来探索：未来，我们打算探索这种空闲VRAM的更多用途。例如，OpenAI最近提出了使用批量API【索引25，Batch api，2024，OpenAI】，它允许用户以50%的更低成本发送异步请求组，但只有明确的24小时周转时间。这项服务非常适合处理不需要立即响应的作业。由于这些批量请求没有严格的TBT，如果VRAM空间足以容纳相应的KVCache，我们甚至可以将这些请求的解码阶段内联到预填充处理中，以获得更好的MFU。

以KVCache为中心的调度

本节我们主要讨论Conductor在正常情况下如何调度请求和KVCache块，关于过载场景的讨论留到下一节。

预填充全局调度

调度策略：先前关于LLM服务的研究通常使用负载均衡策略，根据分配的请求数量来评估每个实例的负载。然而，在Mooncake中，选择预填充实例时会考虑额外因素——不仅是负载，还有前缀缓存命中长度和可重用KVCache块的分布。虽然倾向于将请求路由到具有更长前缀缓存长度的预填充实例以降低计算成本，但将它们调度到其他节点可能更有利于确保整体系统平衡并满足TTFT SLO。为了解决这些复杂性，我们提出了一种缓存感知的全局调度算法，该算法同时考虑了由前缀缓存引起的预填充时间和与实例负载相关的排队时间。

算法细节：算法1详细说明了我们缓存感知预填充调度的机制。对于每个新请求，其输入token被分成几个块，并为每个块计算一个哈希键。这包括生成一个块中token的哈希键，并与前一个块（如果可用）的哈希键连接。然后将请求的块键与每个预填充实例的缓存键逐一比较，以确定前缀匹配长度（prefix_len）。vLLM中已经实现了类似的重用逻辑，但vLLM的开源版本仅支持本地KVCache缓存。

调度决策过程：有了这些匹配信息，Conductor会根据请求长度和prefix_len（因实例而异）估计相应的执行时间。然后，它将该请求的估计等待时间相加，以获得该实例上的TTFT。最后，Conductor将请求分配给TTFT最短的实例，并相应地更新该实例的缓存和队列时间。如果SLO无法实现，Conductor会直接向上层返回HTTP 429 Too Many Requests响应状态码。

工程实现：这个调度框架的骨干是直接的，但复杂性隐藏在各种组件的工程实现中。例如，为了预测一个请求的预填充阶段的计算时间，我们采用了一个从离线测试数据中导出的预测模型。该模型根据请求的长度和前缀缓存命中长度来估计预填充持续时间。由于Transformer的常规计算模式，只要有足够的离线数据，这个预测的误差范围很小。一个请求的排队时间是通过聚合所有排队请求的预填充时间来计算的。在实际实现中，TTFT是并行计算的，使得处理时间与推理时间相比可以忽略不计。

传输时间预测的难点：预测传输时间更具难度，因为它不仅取决于传输数据的大小，还取决于当前的网络状态，特别是发送节点是否处于拥塞状态。这也使得复制热点KVCache块变得必要，这将在下一节中讨论。

缓存负载均衡

缓存分布不均问题：在我们的Mooncake集群中，每台预填充机器管理自己的一组本地前缀缓存。这些缓存的使用频率差异很大。例如，系统提示几乎被每个请求访问，而存储本地长文档内容的缓存可能只被一个用户使用。如§6.1所讨论，Conductor的角色在实现缓存匹配和实例负载之间的最佳平衡中至关重要。因此，从分布式缓存系统的角度来看，负载均衡也扮演着重要角色。具体来说，它涉及到如何策略性地备份缓存，以确保全局预填充调度能够实现高缓存命中率和低负载。

启发式热点迁移方案：解决这个KVCache调度问题的一个初步方案可以是收集每个块的全局使用情况，使用预测模型来预测其未来使用情况，并据此做出调度决策。然而，与预填充时间的估计不同，工作负载是高度动态的，并且随时间显著变化。特别是对于一个用户群快速增长的MaaS提供商来说，准确预测未来使用情况是不可能的。因此，我们提出了一种基于启发式的自动化热点迁移方案来增强缓存负载均衡。

迁移策略：如前所述，由于实例负载高，请求可能不总是被导向具有最长前缀缓存长度的预填充实例。在这种情况下，如果估计的额外预填充时间短于传输时间，Conductor会将缓存的位置和请求转发到备用实例。该实例会主动从持有者那里检索KVCache并将其存储在本地。更重要的是，如果最佳远程前缀匹配长度不大于当前本地可重用前缀乘以一个阈值，我们更倾向于计算输入token。这两种策略不仅减少了请求的预填充时间，还促进了热点缓存的自动复制，使其能够在多台机器上更广泛地分布。

实验验证：为了验证我们策略的有效性，我们进行了一项调度实验，将随机调度和负载均衡调度与我们的策略进行比较。我们进一步比较了§6.1中描述的缓存感知调度和本节中描述的考虑缓存负载均衡的以KVCache为中心的调度。在随机调度中，为每个请求任意选择一个预填充实例。在负载均衡调度中，选择负载最轻的实例。为了评估，我们建立了一个由8个预填充实例和8个解码实例组成的Mooncake集群，利用夜间空闲机器，并重放了23,000个真实世界请求进行实验。我们使用平均TTFT和TTFT SLO达成率来评估每种调度算法的性能。实验结果如图8所示，表明缓存感知策略和缓存负载均衡策略都显著降低了请求的TTFT。我们的以KVCache为中心的调度算法在两个指标上都优于随机调度和负载均衡调度。更多实验结果可在§8中找到。

面向过载的调度

现实场景中的过载问题：大多数现有的LLM服务工作都假设所有请求都将被处理，并相应地优化吞吐量或请求的TTFT和TBT。然而，在现实场景中，处理每一个传入的请求既不经济也不现实。对于面临用户请求量快速增长的商业推理服务，集群推理资源的增长速度远慢于传入请求的增长。因此，过载是当前LLM服务中的一个普遍问题，尤其是在高峰时段。

Mooncake的应对策略：为了平衡成本和用户体验，系统应尽可能多地处理请求，直到系统负载达到预定阈值。此后，剩余的请求将被直接拒绝或推迟重试。Mooncake作为一个分解式推理系统，允许更灵活的调度策略，但也面临着非分解式系统中不存在且先前工作【索引7, Splitwise: Efficient generative llm inference using phase splitting, 2023; 索引8, Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving, 2024; 索引9, Inference without interference: Disaggregate llm inference for mixed downstream workloads, 2024】中未提及的独特调度挑战。

本节内容：在本节中，我们描述了一种专为分解式架构设计的提前拒绝策略，并解决了由该方法引起的负载波动问题。然后，我们探讨了预测生成长度对于缓解这些问题的必要性。

过载场景下的调度

定义系统负载：在系统发生过载的场景中，调度涉及根据系统负载决定是接受还是拒绝传入的请求。此过程的一个关键方面是定义什么构成“系统负载”，因为这个定义会影响拒绝请求的阈值。在传统的耦合系统中，由于预填充和解码阶段之间的干扰，TTFT和TBT的预测可能很复杂。因此，负载通常简单地通过正在处理的请求数与系统最大容量的比率来衡量。

Mooncake的负载度量：相比之下，Mooncake凭借其分解式架构，独立处理预填充和解码阶段。因此，我们使用SLO满意度作为直接的负载测量。具体来说，我们定义l_ttft和l_tbt分别为请求的TTFT和TBT SLO约束。然后，通过将实例上预测的最大TTFT和TBT与l_ttft和l_tbt进行比较来确定预填充和解码实例的负载。基于这两个标准，Mooncake的调度需要两个关键决策：首先，根据预填充实例的负载决定是否接受预填充阶段；其次，根据解码实例的负载决定是否继续进行解码阶段。

提前拒绝

资源浪费问题：在实践中，预填充或解码实例的单个负载并不能准确反映系统处理的实际请求数。这种差异是由于调度单个请求的预填充和解码实例之间存在时间差。如果一个请求在预填充阶段完成后因解码实例负载过高而被拒绝，那么在预填充阶段消耗的计算资源就被浪费了。因此，预填充期间成功处理的实际请求数少于负载指标所显示的。

提前拒绝策略：为了解决这个问题，很自然地将解码实例的负载评估提前到预填充阶段开始之前。我们将此策略称为提前拒绝（Early Rejection）。当请求到达时，Conductor根据预填充和解码池中较大的负载来评估是否接受该请求。提前拒绝显著减少了因被拒请求产生的无效计算，并增强了负载均衡。

提前拒绝引起的负载波动

新挑战：然而，提前拒绝引入了新的挑战。图9显示了在使用提前拒绝策略后，一个由20台机器组成的集群在20分钟内观察到的真实世界实例负载。它突显了预填充和解码机器之间显著的反相波动。这种现象在预填充机器较少的集群中以及预填充阶段耗时较长的场景中更为明显。

波动根源：经过进一步探索，我们发现这个负载波动问题根植于预测解码负载与其际执行之间的时间差。基于当前解码负载的调度具有固有的延迟性。这种延迟导致预填充和解码实例上的负载之间出现波动和相位交错，如图10a中描述的理论示例所示。绿色曲线代表预填充实例的负载（从0到1缩放），黄色曲线代表解码实例的负载。

波动过程：在阶段1，预填充和解码实例的负载都很低，因此Conductor接受大量请求，直到预填充实例的负载达到极限。在阶段2，由预填充实例处理的请求被调度到解码实例，导致解码实例的负载变高。因此，Conductor拒绝传入的请求，导致预填充实例的负载降低。在阶段3，没有新请求进入解码阶段，导致负载下降。此时，Conductor再次接受大量请求，直到预填充实例满载。在阶段4，随着解码实例负载的增加，Conductor拒绝请求，导致预填充实例的负载变低。预填充和解码实例之间负载的这种剧烈波动导致推理集群的资源利用率不佳。

基于预测的提前拒绝

解决方案框架：为了解决负载波动问题，我们提出了一个基于预测的提前拒绝（Early Rejection Based on Prediction）框架，以应对像Mooncake这样的分解式LLM服务系统在过载场景中的调度挑战。如图10b所示，该框架预测传入请求的预填充阶段结束后的解码负载，并使用此预测来决定是否接受请求，这有助于缓解波动问题。该策略的核心组成部分是准确预测后续时段的解码负载。我们为此引入了两种方法：

预测方法：
* 请求级别：先前的工作指出了预测LLM服务负载的一个重大挑战：每个请求的未知输出长度。如果我们能提前确定输出长度，就有可能更准确地估计TTFT和TBT。这反过来将有助于预测解码实例可以完成的请求数以及在指定时间后将添加的新请求数，从而获得那时的负载。然而，预测每个请求的输出长度具有挑战性，因为成本高【索引9】或准确性低，特别是在资源稀缺且需要准确预测的过载条件下，这使得请求级别的预测尤其困难。
* 系统级别：与请求级别的预测相反，系统级别的预测不试图预测单个请求的完成时间。相反，它们估计在指定时间后实例的总体批次数或TBT状态。这类预测是持续进行的，并且要求的精度较低，使其更适合过载场景。

Mooncake的当前实现：在Mooncake中，我们目前采用一种系统级别的预测策略：我们假设每个请求的解码阶段花费一个统一的时间t_d。首先，对于给定的时刻t，将可以在t时刻由预填充实例完成的请求添加到统一的解码实例中。接下来，将将在t时刻之前完成（即其执行时间超过t_d）的请求从解码实例中移除。最后，计算所有解码实例的平均TBT与l_tbt的比率来预测负载。请求级别预测的探索留作未来工作。

A4 实验

实验环境

硬件配置：实验在一个高性能计算节点集群上部署。每个节点配置为：8个NVIDIA A800-SXM4-80GB GPU（每个80GB HBM，通过NVLINK连接），配备支持节点间高达800 Gbps互连带宽的RDMA网卡。
软件配置：为了保护专有信息并促进可复现性，所有实验结果都基于一个与LLaMA2-70B架构相同的伪（dummy）模型。基线系统为vLLM。每个节点根据启动参数部署为预填充实例或解码实例。
数据集与工作负载：
- 公共数据集：ArXiv Summarization【索引26，A discourse-aware attention model for abstractive summarization of long documents，2018，NAACL-HLT】和L-Eval【索引27，L-eval: Instituting standardized evaluation for long context language models，2023】。
- 模拟数据：生成具有预定义长度和前缀缓存比例的模拟数据批次。
- 真实世界请求追踪：构建了一个包含23,000条真实请求追踪的数据集，每条都标注了到达时间戳。实验通过按实际到达时间重放这些请求进行。对于其他场景，使用泊松到达过程模拟请求，并通过RPS（每秒请求数）控制请求率。
  
  图5：请求追踪中的输入和输出长度分布。
  
  表2：端到端实验中使用的数据集。

实验结果

端到端性能

评估指标：实验关注在定义的SLO下各系统的吞吐量性能。我们测量不同RPS速率下的TTFT和TBT，更高的RPS表示更好的吞吐量。为评估大多数请求是否满足SLO，我们使用TTFT和TBT的第90百分位（P90）值作为最终指标。TTFT和TBT的阈值分别设置为最低RPS观测值的10倍和5倍。为了便于比较，所有TTFT和TBT值都相对于这些上限进行归一化，基线为1.0。

公共数据集实验
* 实验设置：一个由四个vLLM实例组成的集群（vLLM-[4M]）作为基线。Mooncake配置为两种设置：一个由三个预填充实例和一个解码实例组成的集群（Mooncake-[3P+1D]），另一个由两个预填充和两个解码实例组成（Mooncake-[2P+2D]）。
* 实验结果：如图11所示，在ArXiv Summarization和L-Eval数据集上，Mooncake-[3P+1D]在满足SLO的情况下，分别比vLLM-[4M]实现了20%和40%的吞吐量提升。在L-Eval数据集上，前缀缓存进一步增强了Mooncake的吞吐量。
* 分析：Mooncake-[2P+2D]由于预填充和解码实例之间的负载不平衡，在TTFT指标上表现不如Mooncake-[3P+1D]和vLLM-[4M]。

图11：Mooncake和vLLM在ArXiv Summarization和L-Eval数据集上的端到端实验。

模拟数据实验
* 实验设置：集群配置同上。模拟数据中的长上下文请求严重干扰了vLLM的解码阶段，因此vLLM采用单请求处理而非批处理。
* 实验结果：如图12所示，Mooncake的分解式设计有效减少了预填充对解码阶段的影响，从未违反TBT SLO。与vLLM相比，Mooncake在遵守相同的TTFT和TBT SLO约束下，吞吐量提升了50%至525%。

真实工作负载实验
* 实验设置：使用10个预填充实例和10个解码实例（Mooncake-[10P+10D]），以及20个vLLM实例（vLLM-[20M]），重放真实请求追踪。TTFT上限为30秒，TBT阈值为每token 0.1秒。
* 实验结果：如图13所示，两个系统的TTFT分布几乎相同，几乎100%的请求满足TTFT SLO。然而，Mooncake-[10P+10D]约100%的请求满足TBT SLO，而vLLM-[20M]只有57%的请求满足该标准。
* 结论：在此实验中，Mooncake在遵守SLO的情况下能多处理约75%的请求。

过载场景性能

实验设置：建立一个由8个预填充实例和8个解码实例组成的Mooncake集群，使用来自23,000个请求的真实追踪数据，并将重放速度提高到2倍以模拟过载场景。
策略对比：比较了三种策略：基线策略（在两个阶段开始前根据负载拒绝请求）、提前拒绝策略和基于预测的提前拒绝策略。
实验结果：如表3所示，基线策略拒绝了4,183个请求。相比之下，提前拒绝和基于预测的提前拒绝策略分别拒绝了3,771和3,589个请求。
结论：通过提前拒绝请求，Mooncake可以避免不必要的预填充计算，从而提高系统资源的有效利用率。此外，通过预测解码实例的负载，Mooncake可以缓解负载波动，增加请求处理能力。

表3：过载场景实验中系统拒绝的请求数。

A5 结论

本文介绍了Mooncake，一个以KVCache为中心的分解式架构，专为高效服务LLM而设计，尤其擅长处理长上下文和过载场景。我们讨论了在平衡最大化整体有效吞吐量目标与满足延迟相关SLO要求时所涉及的必要性、挑战和设计选择。

A6 未来工作

异构加速器与深度分解：将LLM服务的不同部分分解到专用资源池是Mooncake高资源利用率的关键。未来，我们计划探索这条路径上的更多机会，特别是异构加速器的潜在用途。当前旗舰加速器在计算能力、内存带宽和容量等多个指标间取得平衡，使其功能多样但并非在每个单一指标上都达到最优。例如，仅考虑每美元带宽或每瓦特带宽，当前的GDDR甚至LPDDR解决方案可能比旗舰加速器好一个数量级。我们对使用内存中处理【索引37-40】或混合键合【索引41-45】技术实现内存导向设备的新技术特别感兴趣，这些设备在不久的将来可能提供高带宽和高容量，非常适合降低解码阶段内存密集型操作的成本。此外，在包含计算导向和带宽导向加速器的异构加速器环境中，我们可以探索更先进的分解架构，例如将解码阶段的注意力算子与其他线性算子分离，以进一步提高资源利用率。

KVCache优化算法：作为一个正交方向，许多算法旨在减小KVCache的大小，这在两个重要方面对Mooncake有利：1）增加批处理大小以获得更好的利用率；2）提高KVCache缓存命中率以降低预填充成本。这是一个非常活跃的研究领域，包括压缩KVCache的不同方法【索引48-53】、通过各种指标选择重要token【索引54-60】、在不同层之间共享KVCache【索引61-63】或使用不使用KVCache的算子的混合架构【索引64-69】。

调度策略的演进：在调度方面，我们正在开发一种先进的策略，该策略考虑了不同的请求优先级和具有不同TTFT/TBT SLO的场景，旨在增强系统在多样化操作条件下的响应能力和效率。KVCache的有效管理，包括复制、迁移以及针对部分命中和过期场景的专门驱逐策略，对于优化缓存重用也至关重要。此外，我们计划动态平衡预填充和解码实例，并研究通过批处理导向的卸载任务来利用空闲资源的策略。这种方法将使我们能够在波动的工况下最大化资源利用率。

Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving