Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service

本文提出了 Kareto，一种针对大语言模型 KV 缓存的自适应多目标分层存储配置优化器，它通过利用收益递减剪枝策略高效搜索帕累托前沿，并结合细粒度自适应调优机制，在真实工作负载下实现了吞吐量、延迟或成本等指标相比固定配置显著更优的平衡。

要点

这篇论文介绍了一个名为 Kareto 的智能系统，它的任务是帮大语言模型（LLM，比如现在的各种 AI 聊天机器人）“省钱、提速、省内存”。

为了让你更容易理解，我们可以把运行一个大模型想象成经营一家超级繁忙的“知识餐厅”。

1. 核心难题：厨房太小，客人太多

• 现状：大模型在回答问题时，需要记住之前说过的话（这叫"KV Cache"）。这就像厨师在炒菜时，必须把之前的配料和步骤记在脑子里。
• 问题：
  • 昂贵的“大脑”（GPU 显存）：餐厅里有一个超级快但非常小的“超级大脑”（GPU 显存），用来处理当前的订单。但它太小了，一旦客人多、对话长，脑子就装不下了。
  • 便宜的“记事本”（硬盘/内存）：为了装下更多内容，我们可以在旁边放一些便宜的“记事本”（DRAM 内存或硬盘）。虽然它们便宜且容量大，但取东西很慢。
• 困境：如果全用“超级大脑”，太贵且装不下；如果全用“记事本”，取东西太慢，客人会等得不耐烦（延迟高）。现在的系统通常死板地分配多少空间给大脑、多少给记事本，不管客人是少还是多，也不管客人喜欢点什么菜。这导致要么浪费钱（买了太多用不上的空间），要么服务太慢（空间不够用）。

2. Kareto 的解决方案：聪明的“动态管家”

Kareto 就像一个拥有预知能力的超级管家，它不再死板地分配空间，而是根据客人的习惯（工作负载）来动态调整。它主要做了三件大事：

A. 寻找“完美平衡点”（帕累托前沿）

• 比喻：想象你在买一辆车，你想速度最快、油耗最低、价格最便宜。但这三个目标通常是矛盾的（跑得快通常费油且贵）。
• Kareto 的做法：它不会只给你一个固定的方案，而是画出一张“地图”，上面标出了所有**“最划算”的组合**。
  • 如果你想要速度最快，它告诉你：“用这么多内存，虽然贵点，但能省时间。”
  • 如果你想要最省钱，它告诉你：“少用点内存，虽然慢一点点，但能省下一大笔钱。”
  • 它帮你找到那个**“花最少的钱，办最多的事”**的甜蜜点。

B. 像“修剪树枝”一样搜索（自适应搜索）

• 比喻：要在成千上万种配置里找最佳方案，就像在森林里找一棵完美的树。如果一棵一棵地试，累死也找不完。
• Kareto 的做法：它很聪明，知道**“边际效应递减”**。
  • 比如，内存从 100GB 加到 200GB，速度提升巨大；但从 2000GB 加到 2100GB，速度几乎没变，但钱却花了不少。
  • Kareto 发现这种“加钱也没用”的区域后，就直接跳过，不再浪费时间去测试。它只把精力花在那些“稍微加点配置，效果就大不同”的关键区域。这让它找方案的速度快了很多。

C. 给不同的“客人”发不同的“通行证”（分组 TTL 策略）

• 比喻：在餐厅里，有些客人是常客（比如每天来点同一份套餐的），有些是一次性游客（只来一次）。
  • 以前的做法：给所有客人的“座位保留时间”（TTL，生存时间）都一样。结果，常客的座位被误删了，游客的座位却占着空位。
• Kareto 的做法：它观察客人的行为模式。
  • 对于高频重复的对话（比如系统提示词、固定开场白），它给它们永久保留或超长保留，因为反正马上又要用。
  • 对于一次性的对话，它快速清理，把宝贵的空间腾出来。
  • 这就好比给 VIP 客户发“终身会员卡”，给普通游客发“单次入场券”，极大地提高了空间利用率。

3. 效果如何？

研究人员用真实的餐厅数据（真实的大模型服务日志）来测试 Kareto，结果非常惊人：

• 提速：在同样的硬件下，处理速度提升了 9.3%（相当于餐厅上菜更快了）。
• 降延迟：客人等待第一口菜的时间减少了 58.3%（相当于不用等那么久就能开始吃）。
• 省钱：在保持同样速度的情况下，成本降低了 20.2%（相当于省下了 1/5 的房租和食材钱）。

总结

简单来说，Kareto 就是一个大模型服务的“智能调度员”。它不再让系统“一刀切”地分配资源，而是通过模拟演练和智能分析，根据每天不同的客流和菜单，动态调整“大脑”和“记事本”的比例，并给不同的数据贴上不同的“保质期”。

最终结果就是：花更少的钱，让 AI 跑得更快、更聪明。

技术摘要

这篇论文提出了一种名为 Kareto 的自适应多目标分层存储配置框架，旨在优化大语言模型（LLM）服务中的 KV Cache 管理。该研究解决了在 GPU 显存（HBM）容量受限的情况下，如何动态地在 GPU HBM、主机 DRAM 和磁盘等不同存储层级之间分配资源，以平衡成本、吞吐量和延迟的问题。

以下是该论文的详细技术总结：

1. 问题背景与挑战 (Problem & Challenges)

• KV Cache 的内存瓶颈：LLM 推理中的 KV Cache 机制虽然通过“以存换算”加速了生成过程，但其内存占用随并发请求数和序列长度线性增长，极易超出 GPU HBM 容量。
• 分层存储的局限性：现有的解决方案（如 vLLM, SGLang, Mooncake 等）通常采用分层存储（HBM -> DRAM -> 磁盘）来扩展容量，但大多基于静态配置（如固定分配 1TB DRAM）。
• 核心挑战：
  • 动态工作负载：LLM 服务的请求模式（并发度、序列长度、前缀共享率）具有显著的日内和周间波动，静态配置容易导致资源过度配置（浪费成本）或配置不足（性能下降）。
  • 多目标优化困难：需要在成本（OPEX）、吞吐量（Throughput）和延迟（Latency，如 TTFT）之间寻找平衡。这些目标函数是非解析的、非凸的，且变量之间存在复杂的耦合关系（如存储容量增加会提高命中率，但超过一定阈值后收益递减，而成本线性增加）。
  • 缺乏智能配置工具：现有的云存储配置依赖用户手动调整，缺乏能够自动分析多维权衡并找到最优解的工具。

2. 方法论 (Methodology)

Kareto 框架通过仿真驱动的方式，将 KV Cache 配置问题建模为多目标优化问题，寻找帕累托前沿（Pareto Frontier）。其核心组件包括：

2.1 高保真端到端仿真器 (High-Fidelity End-to-End Simulator)

• 功能：模拟完整的 LLM 推理流水线，包括预填充（Prefill）和解码（Decode）阶段。
• 特性：
  • 支持多层级存储（HBM, DRAM, 远程磁盘/Redis）。
  • 精确模拟 KV Cache 的数据放置、跨层级访问、基于 Radix-Tree 的前缀共享复用。
  • 集成云厂商的非线性定价模型（如 AWS EBS 的 IOPS 阶梯定价、带宽与容量的耦合关系）。
  • 通过离散事件模拟捕捉缓存命中率变化对 GPU 利用率和 I/O 阻塞的级联影响。

2.2 自适应帕累托搜索 (Adaptive Pareto Search)

• 问题：全量网格搜索配置空间（DRAM 容量 x 磁盘容量 x TTL）计算成本过高。
• 策略：利用边际收益递减（Diminishing Returns）的规律进行剪枝。
  • 粗粒度到细粒度：先进行粗网格搜索，识别性能或成本变化剧烈的区域。
  • 剪枝机制：当检测到增加资源带来的性能提升低于预设阈值（进入长尾低收益区）时，停止该维度的进一步探索。
  • 结果：在大幅减少仿真次数的同时，仍能准确覆盖帕累托前沿的关键区域。

2.3 基于访问模式的 ROI 感知组 TTL 配置 (ROI-Aware Group TTL)

• 问题：传统的固定 TTL（Time-To-Live）策略对所有 KV Block 一视同仁，无法区分不同前缀子树的复用特性。
• 策略：
  • 分组：利用前缀树（Prefix Tree）结构，将请求按前缀子树分组。识别出高频复用的子树（Top-K）和剩余子树。
  • 差异化 TTL：针对不同组别计算最优的 TTL 值。高频复用组设置较长 TTL 以最大化命中率，低频组设置较短 TTL 以节省存储成本。
  • 优化算法：将问题建模为在总存储预算约束下最大化总复用次数的非凸优化问题，使用 SLSQP（序列最小二乘规划）结合多起点策略求解。

3. 关键贡献 (Key Contributions)

1. 形式化定义：首次将 LLM 推理中的吞吐量 - 延迟 - 成本权衡形式化为一个无闭式解、非凸的帕累托优化问题，证明了基于仿真的优化的必要性。
2. 高保真仿真器：开发了一个能够精确模拟云环境定价结构和复杂 I/O 行为的端到端仿真器，支持任意配置下的工作负载分析。
3. 自适应搜索算法：提出了一种基于边际收益递减的剪枝搜索策略，有效解决了大规模配置空间的搜索效率问题。
4. 细粒度自适应调优：提出了基于前缀树分析的组特定 TTL 配置方法，显著提升了缓存效率和存储利用率，优于“一刀切”的策略。
5. 实证验证：在真实生产轨迹（Trace）上进行了全面评估，证明了 Kareto 能自动适应不同工作负载，无需专家干预即可找到优于静态基线的配置。

4. 实验结果 (Results)

实验基于真实生产轨迹（包括交互式聊天、API 调用、Agent 应用）和不同规模的集群（1 实例计算受限场景，4 实例计算充裕场景），对比了 Kareto 与固定 1024GB DRAM 的基线配置：

• 吞吐量提升：在计算受限场景下，Kareto 可将吞吐量提升最高 9.3%。
• 延迟降低：通过优化配置，平均首字延迟（TTFT）最高可降低 58.3%。
• 成本降低：在满足性能要求的前提下，最高可降低 20.2% 的总运营成本（包括 GPU 小时费和存储费）。
• 搜索效率：自适应搜索策略比均匀网格搜索所需的仿真次数更少，同时保持了帕累托前沿的高质量覆盖。
• 组 TTL 效果：在具有明显复用模式的轨迹（如 Trace B 和 C）上，组 TTL 策略显著提高了复用率，进而改善了吞吐量和成本；而在随机性较强的聊天场景（Trace A）或低延迟场景下提升较有限。
• 仿真精度：仿真器与真实 GPU 服务器实测数据的误差在可接受范围内（平均 TTFT 误差最大 19.2%，吞吐量误差 6.5%，命中率误差 2.0%）。

5. 意义与价值 (Significance)

• 范式转变：从静态资源分配转向弹性、工作负载感知的编排系统，解决了 LLM 服务中资源利用率低和成本高昂的痛点。
• 自动化运维：为云厂商和 LLM 服务提供商提供了一种自动化工具，能够根据历史负载自动推荐最优的存储配置，降低了对人工专家经验的依赖。
• 经济性与性能的平衡：证明了通过智能管理分层存储（特别是利用廉价磁盘存储冷数据），可以在不牺牲太多性能的前提下，大幅降低 LLM 推理的运营成本，对于大规模部署 LLM 服务具有重要的商业价值。
• 通用性：该框架不仅适用于当前的 LLM 服务，其多目标优化和自适应搜索的思路也可推广到其他具有复杂存储层级和动态工作负载的 AI 推理系统中。

总结来说，Kareto 通过结合高保真仿真、智能搜索算法和细粒度的缓存管理策略，成功解决了 LLM 服务中 KV Cache 分层存储配置的复杂优化问题，实现了成本、延迟和吞吐量的最佳平衡。