CCACHE NOTES

CACHE SYSTEMS PAPER ROADMAP · 2015—2026

缓存策略综述

把这里当作 BFS Root：按问题找到研究分支，再沿时间线继续深挖。主线结论回到“缓存”页。

BFS RootWorkload 提供生产证据；五条主线覆盖通用替换、MRC、容量决策、推理 KV 与调度器。每张卡片只保留“问题—设计—适合—局限”；* 表示作者中有阿里云百炼团队成员。
35Papers 5Tracks

FIRST PRINCIPLES · BASELINES · WORKLOAD

先看：缓存问题、基础策略与阅读坐标

问题、基线与五条方法主线

1. 缓存的起点：用空间换掉重复工作

缓存命中的价值来自被省掉的后端读取、网络传输或重复计算，而不是来自“装得多”。读任何策略前先分清四个动作：

  • 准入： miss 得到的新对象是否值得进入？
  • 淘汰： 空间不足时谁先离开？
  • 维护： 命中时更新队列、计数和锁要付出多少成本？
  • 容量： 再增加一份空间能挽回多少高成本 miss？

2. 最小基线：FIFO、LRU 与 LFU

策略问题核心设计更适合局限
FIFO用最低维护成本管理有限空间按进入顺序淘汰，命中不改顺序对象生命周期接近、命中路径要轻看不到近期复用；S3-FIFO 需要额外队列才能过滤 one-hit object
LRU用最近性预测未来复用命中刷新顺序，淘汰最久未用对象短期局部性强、工作集稳定S3-FIFO 指出扫描污染；SIEVE 指出命中更新的并发成本
LFU保护长期高频对象记录频次，优先淘汰低频对象热点稳定、流行度差异明显KVCache Cache in the Wild* 表明短生命周期 KV 中累计频次会保护过时热点

3. workload 是算法选择器，不是附属指标

观察到的 workload真正的问题优先阅读验证重点
短时间反复访问同一工作集保住最近对象LRU、SIEVEmiss 与 hit-path CPU
大量对象只出现一次准入污染S3-FIFO、TinyLFU 路线one-hit ratio 与误拒绝
长扫描夹杂稳定热点扫描污染S3-FIFO、SIEVE 后续热点逐出与恢复时间
miss 很贵且 trace 稳定启发式不够精确LRB、3L-Cache、HALP模型开销是否小于 saved miss cost
对象大小或 miss 代价差异大普通 hit ratio 失真LHD、LA-Cache、FLOWSbyte / latency / compute-weighted benefit
对话或 workflow 暴露未来结构普通 recency 信号不足LPC、KVFlow预测错误与元数据依赖

4. 本页的五条研究线

  • 通用缓存替换： 普通对象应该赶走谁？
  • 在线 MRC： 不反复改容量，怎样预测不同容量的收益？
  • 容量决策： 拿到收益曲线后，分多少、何时调、怎样安全回收？
  • 推理 KV Cache： 哪份 Prefix KV 值得留在 HBM，哪些应该进入更慢层级？
  • Cache-aware 调度： 请求应该去哪个实例，才能兼顾 Prefix 复用与排队压力？

PRODUCTION TRACES · BURST · PREFIX REUSE

Workload：生产访问如何改变缓存需求

用生产 Trace 解释复用与压力怎样变化

缓存策略和容量曲线都由访问序列决定。下面三篇生产研究分别给出通用缓存、LLM 流量和 Prefix KV 复用的真实分布。

  • 通用缓存： 不同服务的对象大小、生命周期和访问模式不同，缓存引擎需要允许策略与层级组合。工作脉络： CacheLib；
  • LLM 流量： Burst、会话间隔和请求长度共同决定绝对 Prefill 压力。工作脉络： BurstGPT；
  • Prefix KV： 请求类别、Prefix 位置和生命周期共同决定复用概率。工作脉络： KVCache Cache in the Wild。
OSDI 通用生产

The CacheLib Caching Engine: Design and Experiences at Scale

  • 问题： 生产缓存由不同团队分别实现，单一合成 workload 无法代表 CDN、存储和应用数据缓存的共同需求。
  • 设计： 从 Facebook 多类缓存中提取共同能力，构建可组合的通用引擎，并用生产 workload 反推内存分配、淘汰和分层设计。
  • 适合： 理解为什么生产缓存需要按 workload 选择容量池、替换策略和存储层级。
  • 局限： 它总结的是普通对象缓存，不包含 Prefix 依赖、Prefill 重算成本或缓存 Autoscaler。
KDD LLM 流量

BurstGPT: A Real-World Workload Dataset to Optimize LLM Serving Systems

  • 问题： 稳态或泊松到达会隐藏真实服务中的请求 Burst、会话间隔、长度变化和失败高峰。
  • 设计： 发布 213 天、1,031 万条 Azure OpenAI 请求 Trace，从并发、会话、响应长度和失败四个维度描述流量变化。
  • 适合： 验证扩缩容能否在压力突变前完成，以及 Hit Rate 不变时绝对 Miss 计算量是否已经越过服务容量。
  • 局限： Trace 不包含 KV block 标识与实际命中，不能单独生成 Prefix Cache MRC。
ATC KV 复用

KVCache Cache in the Wild: Characterizing and Optimizing KVCache Cache at a Large Cloud Provider*

  • 问题： 合成对话 workload 难以代表生产 Prefix KV 的复用来源、时间尺度和容量需求。
  • 设计： 按请求类别估计复用概率与生命周期；优先淘汰复用概率低的 KV，同概率时优先保留更靠前的 Prefix block。
  • 适合： Prefix KV 的准入、淘汰和容量规划，也是通用 workload 研究迁移到当前问题的直接桥梁。
  • 局限： 结论来自单一云厂商和单实例 CPU–GPU 分层评估，不能直接覆盖多实例路由与共享池外部性。

对象缓存 · CDN · KV Cache

通用缓存替换策略

缓存满时，决定普通对象淘汰谁

这一类聚焦普通对象缓存、CDN、KV cache 和存储缓存。

主线分成：

  • 统计与解析模型： 用在线统计和代价公式估算对象未来收益，再选择最不值得占空间的对象。工作脉络： Hyperbolic Caching → LHD → LA-Cache → RFB；
  • 学习型： 从历史访问中预测未来复用或学习策略权重，后续工作持续压低训练和请求路径开销。工作脉络： LRB → CACHEUS / GL-Cache → 3L-Cache，以及 HALP → S4-FIFO；
  • 简单高性能与自适应： 用 FIFO、访问位和延迟晋升等轻量机制降低命中路径成本，同时适应扫描和 workload 漂移。工作脉络： S3-FIFO → SIEVE / Lazy Promotion → Merlin。
NSDI 统计 / 解析

LHD: Improving Cache Hit Rate by Maximizing Hit Density

  • 问题： recency / frequency 没有回答“每单位空间还能换来多少命中”。
  • 设计： 在线统计对象年龄与再次命中概率，淘汰 hit density 最低者。
  • 适合： 大小不一、希望直接优化单位容量命中的对象缓存。
  • 局限： 它优化统计期望而非 next reuse；后续 LRB 转向预测 relaxed Belady 距离。
NSDI 学习型

LRB: Learning Relaxed Belady for Content Distribution Network Caching

  • 问题： 启发式信号离“未来最晚复用者先走”的 Belady 仍很远。
  • 设计： 学习对象下次访问距离，只在候选集上近似执行 Belady。
  • 适合： CDN trace 稳定、miss 昂贵且能承担在线模型的场景。
  • 局限： 逐对象预测成本高；GL-Cache 因此改成 group-level learning。
SOSP 简单 / 自适应

FIFO Queues Are All You Need for Cache Eviction（S3-FIFO）

  • 问题： one-hit object 污染缓存，LRU 命中更新又增加并发成本。
  • 设计： 小 FIFO 试用、主 FIFO 保护、ghost 识别再次出现者。
  • 适合： 一次性对象多、并发高、希望保持简单数据面的缓存。
  • 局限： 静态队列比例不能适应所有 workload；S4-FIFO 因此学习少量全局参数。
NSDI 简单 / 自适应

SIEVE Is Simpler Than LRU

  • 问题： LRU 每次命中重排队列，多核下锁竞争明显。
  • 设计： 命中只设 visited 位，淘汰时再扫描并给对象第二次机会。
  • 适合： 高并发对象缓存，尤其重视 hit-path 吞吐时。
  • 局限： 单个 visited 位只表达“近期访问过”；原论文并不区分一次与多次复用强度。
PVLDB 简单 / 自适应

Demystifying and Improving Lazy Promotion in Cache Eviction

  • 问题： 大量 promotion 不改变最终 victim，却消耗同步与写入成本。
  • 设计： 延迟或省略晋升，并用对象年龄辅助淘汰。
  • 适合： promotion 成为 CPU 或并发瓶颈的缓存实现。
  • 局限： 论文主问题是 promotion；它不解决错误准入或容量分配。
OSDI 简单 / 自适应

Merlin: An Efficient Adaptive Cache Eviction Algorithm

  • 问题： 组合多个完整策略会状态干扰，固定策略又难适应 workload。
  • 设计： 直接刻画对象局部性与缓存大小关系，不再拼装专家策略。
  • 适合： workload 变化明显、又不希望运行学习模型的对象缓存。
  • 局限： 原论文针对普通对象局部性；迁移到前缀树需另行处理共享祖先。
OSDI 学习型

Learning-Augmented Heuristics（S4-FIFO）

  • 问题： 固定 S3-FIFO 参数不适应所有 workload，逐对象学习又太重。
  • 设计： 保留 FIFO 数据面，只让后台模型低频调整全局参数。
  • 适合： 请求路径必须简单，但 workload 会长期漂移的缓存。
  • 局限： 仍需要稳定反馈窗口训练控制面；它不直接估算容量的边际算力收益。

测量与建模 · 收益曲线 · 预测

在线缓存收益建模与 MRC：测量与建模

估算不同容量下的 miss 与收益

MRC（Miss Ratio Curve，未命中率曲线）描述“缓存容量 → 未命中比例”的关系：横轴是容量，纵轴是 miss ratio。它回答扩容或缩容会改变多少 miss，本身不是替换策略。

对 LRU，reuse distance 是两次访问同一对象之间出现过的不同对象数；首次访问算 cold miss。容量为 C 时，距离小于 C 会 hit，距离大于等于 C 会 miss。因此统计距离分布，就能一次推导所有容量下的 miss ratio；SHARDS 用哈希抽样近似这套分布。

这一层负责测量与建模。 它根据访问流构造“缓存容量 → miss、流量或延迟”的收益曲线，供容量控制使用。

后续工作沿三条并行分支推进：

  • 复用距离抽样： 抽样记录 LRU 栈距离，用少量状态近似“容量变化会带来多少 miss”。工作脉络： SHARDS；
  • 缩小版模拟： 运行多个缩小缓存直接模拟不同容量，因而也能覆盖无法由栈距离推导的策略。工作脉络： Miniature Simulations → Kosmo → LAShards；
  • 多维或价值加权曲线： 把单一 object-miss 曲线扩展到多层容量组合或 byte 权重，避免只优化对象命中数。工作脉络： eMRC / FLOWS。
FAST 复用距离

Efficient MRC Construction with SHARDS

  • 问题： 完整记录 reuse distance 的内存与计算开销过高。
  • 设计： 按 key 哈希采样，只用少量访问近似完整 LRU MRC。
  • 适合： LRU 类、需要在线观察容量收益的存储缓存。
  • 局限： 依赖 stack property；Miniature Simulations 用模拟补足 ARC、LIRS 等。
ATC 微型模拟

Cache Modeling and Optimization Using Miniature Simulations

  • 问题： 非栈策略没有可直接由 reuse distance 推导的 MRC。
  • 设计： 同时运行多个缩小版缓存，采样真实请求估计不同容量表现。
  • 适合： FIFO、ARC、LIRS 等需要黑盒建模的策略。
  • 局限： 每个容量点维护模拟器仍重；Kosmo 与 LAShards 都直接针对这项开销。
FAST 多维 / 加权

eMRC: Efficient Miss Ratio Approximation for Multi-Tier Caching

  • 问题： DRAM / SSD 多层缓存需要容量组合曲面，而不是一条 MRC。
  • 设计： 少量采样点加 cliff removal 与 convex hull，近似多维 miss-ratio surface。
  • 适合： 多层缓存配置搜索与多样 SLO。
  • 局限： 维度来自缓存层级，不包含 Prefix KV 的祖先依赖或 prefill 算力价值。
FAST 微型模拟

Kosmo: Efficient Online Miss Ratio Curve Generation

  • 问题： 非栈策略的多容量微型模拟仍占用大量状态。
  • 设计： 共享紧凑状态，一次生成 FIFO、LFU、2Q 等在线 MRC。
  • 适合： 需要低开销比较多种非栈替换策略的缓存。
  • 局限： 目标仍是 object miss ratio；FLOWS 表明变长对象还必须约束 byte-MRC 误差。
EuroSys 多维 / 加权

FLOWS: Balanced MRC Profiling for Heterogeneous Object-Size Cache

  • 问题： 变长对象下 object-MRC 准确，不代表 byte-MRC 也准确。
  • 设计： 平衡采样大小对象，同时约束对象与字节曲线误差。
  • 适合： CDN、KV store 等对象大小分布很宽的缓存。
  • 局限： byte 权重仍不等于 miss 的真实延迟或计算成本；算力 MRC 还需新的价值函数。
IEEE TC 微型模拟

LAShards: Low-Overhead and Self-Adaptive MRC Construction

  • 问题： 非栈式微型模拟既重，也难跟随 workload 漂移。
  • 设计： 利用局部性和 burst 缩小模拟规模，并在线调节采样。
  • 适合： workload 动态变化、需要持续在线 MRC 的缓存。
  • 局限： 它自适应的是 profiler 开销与误差，不负责把曲线转换成容量动作。

决策与执行 · 容量分配 · SLO

缓存容量分配与安全扩缩容：决策与执行

决定分多少、何时调、怎样安全回收

这一层负责决策与执行。 它接收 MRC、延迟、成本或 SLO 等信号，决定每个租户或服务应该分多少缓存、何时调整，并把决定落实为容量重新分配或安全回收。

后续工作沿三条分支推进：

  • 边际收益与多租户分配： 估计各租户多一份缓存能减少多少 miss 或 I/O，再把共享容量移向边际收益更高处。工作脉络： Cliffhanger → Memshare → OSCA → Cuki；
  • 尾延迟与 SLO 安全回收： 从“总 hit 最高”转向“尾延迟或 SLO 达标”，只回收不影响关键请求的容量。工作脉络： RobinHood → MDK；
  • 缓存与其他资源联动： 联合考虑内存、I/O 和网络，避免缩缓存只是把瓶颈推到下游。工作脉络： HARE。
NSDI 边际收益

Cliffhanger: Scaling Performance Cliffs in Web Memory Caches

  • 问题： performance cliff 使平均分配或粗粒度调整错过巨大边际收益。
  • 设计： shadow queue 测局部 hit-rate gradient，再迭代调整应用内外配额。
  • 适合： 多租户 Memcached、容量边界附近收益突变的 workload。
  • 局限： 目标仍是总体 hit rate；后续 RobinHood 证明尾延迟目标会给出不同分配。
ATC 边际收益

Memshare: A Dynamic Multi-tenant Key-value Cache

  • 问题： 静态分区让部分租户空置、部分租户缺容量。
  • 设计： 每租户保留保障额度，其余进入共享池并动态回收。
  • 适合： 多应用共享 DRAM KV cache，且需要最低容量保障。
  • 局限： 优化总 hit rate；RobinHood 表明高 hit 的快后端未必值得更多缓存。
OSDI SLO 安全

RobinHood: Tail Latency Aware Caching

  • 问题： 总 hit rate 无法表达哪个后端真正拖慢端到端 P99。
  • 设计： 从不影响尾延迟的后端收回容量，分给关键慢后端。
  • 适合： fan-out Web 服务、多个后端共同决定请求尾延迟。
  • 局限： 目标是端到端 tail latency；不直接生成容量–miss 曲线，也不建模缓存维护成本。
ATC 边际收益

OSCA: An Online-Model Based Cache Allocation Scheme

  • 问题： 多个存储节点共享缓存时，平均分配无法最小化后端 I/O。
  • 设计： 在线估计各节点 MRC，用动态规划求近优配置并重分配。
  • 适合： 云块存储节点共享同一缓存服务器。
  • 局限： MRC 构建仍是控制成本；后续 Cuki 以更轻的 / 结构驱动闭环。
ATC 边际收益

Adaptive Online Cache Capacity Optimization via Cuki

  • 问题： 完整 MRC 太贵，占用量又不能说明缓存该多大。
  • 设计： 轻量估计 WSS、IRR 与 MRC，直接驱动在线容量调整。
  • 适合： 可变大小文件缓存、需要生产闭环 autoscaling 的系统。
  • 局限： 只调缓存会把压力推向 I/O 和网络；后续 HARE 因此联合分配多种资源。
FAST 多资源

Cache-Centric Multi-Resource Allocation for Storage Services（HARE）

  • 问题： 缩缓存会增加 I/O 与网络，仅调内存会转移瓶颈。
  • 设计： 建模资源联动，用两阶段 harvest / redistribute 联合分配。
  • 适合： 缓存、I/O、网络共同限制吞吐的多租户存储服务。
  • 局限： 原论文优化存储吞吐与公平性；没有 Prefix KV 的 prefill 算力价值。
OSDI SLO 安全

MDK: Rethinking the Data Center Memory Reclamation Problem

  • 问题： 数据中心要在满足 SLO 时尽量回收内存，传统 MRC 问反了方向。
  • 设计： 提出离线最优策略、Memory Performance Curve 与快速生成方法。
  • 适合： 以 SLO 为约束、主动回收运行中任务内存的数据中心。
  • 局限： MPC 衡量性能损失与内存节省；Prefix KV 仍需把损失具体化为剩余 prefill 成本。

PREFIX EVICTION · TIERED KV CACHE

推理 KV Cache / Prefix Cache：本地淘汰与分层缓存

决定 Prefix 留在 HBM 还是进入更慢层级

这里的主问题是：多个推理请求之间，哪些前缀 KV 值得继续保留，以及它们应该留在 HBM 还是进入 DRAM、SSD 或远端缓存。

本地淘汰决定 HBM 满时删谁；分层缓存决定 KV 离开 HBM 后放到哪里，以及下次访问时加载还是重算。两者都改变有效缓存容量，但控制对象不同。

先看开源基线：当前系统实际在淘汰什么

系统管理层当前候选选择代码依据
vLLMHBM prefix block只淘汰 ref_cnt=0 的空闲 block，默认 block-LRU；同时间优先释放更深 suffixFreeKVCacheBlockQueue
SGLangHBM radix tree结构约束优先：只从未锁定叶子淘汰，默认 leaf-LRURadixCache.evict
RTP-LLMHBM prefix block动态缓存按 block-LRU 回收；标记为 resident 的 block 不参与淘汰BlockCache / ReuseCache
LMCache / MooncakeCPU、disk 或外部 KV storeLMCache 提供 LRU 等策略；Mooncake 先过滤 pin / lease，再按 lease timeout 回收LMCache policy / Mooncake eviction
kvcached引擎下方物理页沿用 vLLM / SGLang 原有候选顺序，增加物理页回收，不提供新的 workload-aware priorityintegration patches

前三篇 Prefix Cache 工作的直接基线是 vLLM block-LRU、SGLang leaf-LRU 与 RTP-LLM block-LRU。CachedAttention、Mooncake 与 LMCache 讨论 KV 离开引擎 HBM 后的分层保存与访问；kvcached 只负责物理页回收，不改变 Prefix victim 顺序。

  • 代价感知： 围绕 TTFT 阈值，优先回收即使下次重算也不会造成尾延迟违规的 KV。工作脉络： Tail-Optimized；
  • 会话语义： 根据会话是否还会继续估计未来复用，避免暂时空闲的对话 KV 被过早淘汰。工作脉络： LPC；
  • 工作流结构： 利用 Agent 执行图预测下一次复用距离，并据此协调淘汰与预取。工作脉络： KVFlow；
  • 分层缓存： 在 HBM、DRAM、SSD 和远端缓存之间放置 KV，并比较加载成本与重新 Prefill 成本。工作脉络： CachedAttention → Mooncake / LMCache。
NeurIPS 代价感知

Tail-Optimized Caching for LLM Inference

  • 问题： LRU 把短对话与长对话 miss 看成同样昂贵。
  • 设计： 先裁掉即使下次 miss 也不会越过 TTFT 阈值的“富余” block；仍不够时再按 LRU 淘汰，并以 作离线最优参照。
  • 适合： 会话长度差异大、目标是降低 TTFT 尾延迟的单层 Prefix Cache。
  • 局限： 原论文固定容量，并明确假设不同会话不共享前缀；不覆盖多租户共享物理容量。
NeurIPS 会话语义

Learned Prefix Caching for Efficient LLM Inference（LPC）

  • 问题： 对话暂时空闲不等于已经结束，纯 recency 会过早逐出。
  • 设计： 根据对话内容预测继续概率，再结合闲置时间排序。
  • 适合： 多轮聊天、能访问对话语义且 continuation 可预测的服务。
  • 局限： 原论文依赖语义模型与会话边界；不适用于没有稳定 conversation identity 的请求。
NeurIPS 工作流结构

KVFlow: Efficient Prefix Caching for Multi-Agent Workflows

  • 问题： Agent workflow 已暴露未来步骤，普通 LRU 却完全不用这些信息。
  • 设计： 根据执行图估计距下次使用的步数，联合指导淘汰与预取。缓存层 insight 与后来的 Pythia* 本质相同；Pythia* 再把预测用于调度和扩缩容。
  • 适合： 执行图显式、步骤复用稳定的 multi-agent workflow。
  • 局限： 原论文需要 workflow 结构；开放式请求没有执行图时，核心信号不存在。
arXiv 分层缓存

Cost-Efficient Large Language Model Serving for Multi-turn Conversations with CachedAttention

  • 问题： 多轮会话的历史 KV 超出 HBM 后，直接丢弃会重复 Prefill，临时加载又可能被慢介质拖住。
  • 设计： 用 GPU、主机内存和存储组成分层缓存，并通过逐层预取、异步保存和 scheduler-aware fetch / eviction 隐藏数据移动。
  • 适合： 会话身份明确、历史上下文会再次访问、允许把 KV 保存在慢层级的多轮服务。
  • 局限： 不改模型权重也不需要重训练，但会修改运行时 Attention / KV 位置处理；它不是完全透明的外部缓存插件。
ACM TOS 分层缓存

Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving

  • 问题： 单机 HBM 无法容纳长上下文与跨实例复用所需的 KV，而集群中的 DRAM、SSD 和网络资源没有被统一利用。
  • 设计： 建立全局分离式 KVCache，联合 CPU DRAM、SSD 与 NIC，并由 SLO-aware scheduler 决定 KV 的放置与请求执行位置。
  • 适合： 长上下文、P/D 分离、具有高速网络和全局元数据的大规模集群。
  • 局限： 不改模型结构或权重，但收益依赖传输带宽、全局索引与调度；全局存在某份 KV 不等于目标实例可以低成本使用。
arXiv 分层缓存

LMCache: An Efficient KV Cache Layer for Enterprise-Scale LLM Inference

  • 问题： 引擎本地 HBM 中的 KV 难以跨请求、跨引擎或跨 GPU 复用，直接外存又容易被数据移动开销抵消。
  • 设计： 通过 vLLM / SGLang Connector 抽取 KV，在 GPU、CPU、存储和网络层之间流水化保存与加载，并提供独立控制接口。
  • 适合： 需要外部 KV Offload、跨引擎 Prefix 复用或 P/D KV 传输的现有推理栈。
  • 局限： 不改模型结构或权重，但外部层的命中价值取决于加载与重算谁更快；它也不替代引擎内部的 HBM victim selection。

CACHE AFFINITY · LOAD BALANCING · AGENTS

Cache-aware 调度器：缓存局部性与实例负载

在缓存局部性与实例负载之间选择落点

调度器决定每个请求进入哪个实例。实例各自保存本地 Prefix KV 时，这个选择会直接改变命中、排队和后续访问序列。

  • 局部性与负载： 在已有 Prefix 与当前排队压力之间选择实例。工作脉络： Preble → LMetric*；
  • 会话与工作流： 利用 Session Affinity 或 Agent 执行结构保持后续复用。工作脉络： SMetric* / Pythia*；
  • 在线适应： 不固定手工公式，持续从实例状态与请求结果学习路由。工作脉络： Lodestar。
arXiv 局部性 / 负载

Preble: Efficient Distributed Prompt Scheduling for LLM Serving

  • 问题： 只按负载均衡会把共享 Prefix 分散到不同 GPU，只按缓存亲和又会把请求堆到热点实例。
  • 设计： 用分层调度同时估计 Prefix KV 复用与实例计算负载，在分布式副本间选择请求落点。
  • 适合： 多个实例各自持有本地 Prefix Cache、请求之间存在大量共享 Prompt 的服务。
  • 局限： 原文固定缓存机制和实例集合，只负责分布式调度，不估算扩缩容后的新容量收益。
OSDI 局部性 / 负载

Simple Is Better: Multiplication May Be All You Need for LLM Request Scheduling（LMetric）*

  • 问题： 只追求 KV 命中会形成热点，只追求负载均衡又会制造重复 Prefill；线性组合两者还需要按 workload 调参。
  • 设计： 对每个候选实例计算“新增 Prefill token × 当前 batch size”，把请求发给乘积最小的实例。
  • 适合： P/D colocated 服务：同一实例同时执行 Prefill 与 Decode，并持有本地 Prefix Cache。
  • 局限： 原文只决定路由，不负责 KV 准入、淘汰或容量；P/D 分离时还需要重新定义实例负载。
arXiv 会话 / 工作流

SMetric: Rethink LLM Scheduling for Serving Agents with Balanced Session-centric Scheduling*

  • 问题： 把多轮 Session 的每个请求独立调度，会让后续请求迁移并丢失已经形成的缓存亲和。
  • 设计： 首请求按负载选择实例，后续请求保持 Session Affinity，并用全局 KV 层承接跨实例访问。
  • 适合： Session 边界明确、后续轮次复用强、具备全局 KV 层的 Agent 服务。
  • 局限： 依赖全局 KV 层具有足够容量与带宽；它不决定各实例内部淘汰谁。
arXiv 会话 / 工作流

Pythia: Exploiting Workflow Predictability for Efficient Agent-Native LLM Serving*

  • 问题： 通用调度器把 Agent Workflow 当作无结构流量，无法利用未来步骤、长上下文复用和资源需求的可预测性。
  • 设计： 由应用暴露 Workflow 结构，在服务层预测后续步骤，并把预测用于缓存、调度和扩缩容协同。
  • 适合： 执行图稳定、能够提供工作流语义的多 Agent 或 Coding Agent 服务。
  • 局限： 依赖显式结构和可预测路径；开放式对话或临时工具调用会削弱预测价值。
arXiv 在线学习

Lodestar: An Online-Learning LLM Inference Router

  • 问题： 固定启发式难以同时覆盖 KV 复用、动态 Batch、长短请求与异构 GPU，且 workload 变化后需要重新调参。
  • 设计： 持续收集请求与实例状态，在线训练 Reward Predictor，并把请求发到预测目标最优的实例。
  • 适合： Workload 和硬件持续变化、能够承受在线学习与观测成本的分布式推理集群。
  • 局限： 需要探索和持续训练，决策可解释性弱；它学习当前实例集合内的路由，不直接回答应该扩多少缓存。

TAKEAWAY · SCALING · SCHEDULING · MULTI-TENANCY

Takeaway：回到问题

扩缩容、调度流控与多租户

问题边界

本节只讨论 P/D 分离服务中的 Prefill：Prefix KV 保存在各个 P 实例本地，没有可供调度器任意访问的 global KV。不同租户的 KV 内容彼此隔离，但共享 P 实例、物理容量与排队资源。当前调度基线是固定加权和，在预估 KV 命中与实例负载之间取舍。

三个核心问题

  1. 扩缩容： 当整体 RPM / TPM 看似稳定，而 KV 命中率持续下降时，怎样区分租户复用变化、调度迁移、容量淘汰和实例变化；又该在 KVS 或 Prefill 队列进入拐点前何时扩容、何时才可以安全缩容？
  2. 调度与流控： 在没有 global KV 的前提下，是否存在比固定加权和更合适的策略，同时兼顾本地 KV 命中、实例负载和 KVS 压力，并决定拥塞时哪些请求继续、等待、限流或清退？
  3. 多租户： 各租户 KV 内容隔离、却共享 P 实例的算力、KV 容量和排队资源时，怎样识别每个租户的真实需求与缓存收益，并处理容量分配、公平性和 SLO？

问题一：扩缩容——已有工作提供的部件

问题二：调度与流控——已有工作提供的部件

  • Preble 与 LMetric*： 在 Prefix 复用与实例负载之间选择落点；前者使用分层调度，后者用新增 Prefill token 与 batch size 的乘积消除固定权重。
  • SMetric* 与 Pythia*： 分别利用 Session Affinity 和 Agent Workflow 保持后续复用；前者依赖 global KV tier，后者依赖可见的工作流结构。
  • Lodestar： 用在线 Reward Predictor 跟随 workload 与硬件变化，但没有给出缓存容量分配或 SLO 安全回收保证。
  • Tail-Optimized 与 RobinHood： 说明拥塞时不能把所有 miss 或请求视为相同，它们对 TTFT 和尾延迟的影响不同。

问题三：多租户——已有工作提供的部件

  • Memshare： 给每个租户最低容量保障，同时让剩余容量进入共享池。
  • Cliffhanger、OSCA 与 Cuki： 用边际收益或在线需求估计，在租户之间动态调整缓存份额。
  • RobinHood、HARE 与 MDK： 把尾延迟、跨资源压力和 SLO 回收边界带入共享资源分配。
  • FLOWS： 说明按对象 hit 分配会忽略对象大小，多租户比较不能只看命中次数。

现有工作尚未一起回答的问题

  • 扩缩容： 现有工作没有直接回答 P/D 分离服务中，为什么 RPM / TPM 稳定时本地 KV 命中仍会缓慢下降，也没有覆盖 P 实例变化同时改动算力、KV 总容量、缓存分区和路由映射的场景。
  • 调度与流控： Preble / LMetric* 固定实例集合，SMetric* 依赖 global KV，Pythia* 依赖工作流结构，Lodestar 只学习当前状态下的路由；它们都没有直接覆盖本地 KV 场景下路由、扩缩容、限流和请求清退同时发生的问题。
  • 多租户： 现有多租户缓存工作主要衡量对象命中、I/O 或 SLO，没有直接覆盖 Prefix KV 的 Prefill 成本、租户隔离和实例本地副本同时存在的资源分配问题。