跳到主要内容

Cache-aware 调度

如何以 Prefix cache 命中率驱动请求路由，在命中率与负载均衡间取得平衡

核心要点：

  • 核心矛盾：最大化命中率 vs 维持负载均衡 vs 限制 cache 转移代价
  • Prefix 复用率：Kimi trace ~50%、L-Eval >80%、arXiv summarization 近 0%
  • Radix tree 索引：按 token id 序列压缩，O(prefix_len) 匹配；SGLang RadixAttention 代表
  • 跨节点索引：集中式 (Mooncake Conductor) vs 分布式 （SGLang 部分部署 + consistent hashing）
  • 四种主算法：SGLang RadixAttention （单节点） / Mooncake Conductor （cost function 三项） / Together CPD （长上下文） / STAR （decode 阶段再调度）
  • 公开收益：Mooncake +75% 请求；Together CPD +35-40% QPS; SGLang RadixAttention 多轮 / agent 数倍提升

本文只讨论调度算法层的设计：prefix 索引结构、跨节点命中检测、路由代价函数、动态再调度。具体系统的整体架构分别在 9.4 Mooncake 与 9.5 SGLang PD; KV cache 跨节点传输性能本身在 9.7 KV cache 跨节点传输瓶颈; PD 分离的基础调度模型在 9.2 Prefill/Decode 分离原理。

为什么要做 Cache-aware 调度​

核心问题：朴素负载均衡有多大代价？Prefix 复用率在不同场景下差多少？

朴素的负载均衡 (round-robin、least-loaded) 在 LLM 推理中代价显著：相同 prefix 的请求被路由到不同实例，每个实例都要把 prefix 重算一遍 prefill。命中率随请求结构变化极大：

场景Prefix 复用率来源
Kimi 真实在线 trace （chatbot 多轮 + system prompt）约 50%arXiv:2407.00079 §6.1
L-Eval （长上下文评测集，结构化）>80%arXiv:2407.00079 §6.1
arXiv summarization近 0%arXiv:2407.00079 §6.1
长上下文 100k+ token 服务高 （system prompt + RAG context 反复使用）Together AI CPD blog

@tbl-cache-aware-hit-rate 不同场景下 prefix 复用率

复用率 50%-80% 的工况意味着如果调度器能把请求送到"该 prefix 已驻留"的实例，prefill 算力直接减半到八折以上。但代价不是免费：

  • 索引同步开销：调度器需要实时知道每个实例上有哪些 prefix block，事件流必须低延迟
  • 负载倾斜风险：纯按命中率路由会让热门 prefix 所在实例过载
  • 跨节点 cache 转移代价：命中在"另一个实例上"时，把 KV cache 拉过来是否比直接重算更快

核心矛盾：最大化命中率 vs 维持负载均衡 vs 限制 cache 转移代价。后续各算法的差异基本都是这三项权重的不同取法。

关键技术机制有哪些​

核心问题：Radix tree 索引怎么工作？跨节点 hash 集中式 vs 分布式？共享 cache pool 怎么改变调度？

Prefix tree / Radix tree 索引​

把所有已驻留 KV cache block 按 token id 序列组成压缩前缀树。新请求来时按 token id 自上而下匹配，匹配深度即命中长度。SGLang RadixAttention 是该思路的代表实现[1]:

  • 节点：表示一段共享 token 序列对应的 KV cache block 引用
  • 匹配：O(prefix_len)，从根逐字符比对 (token-level)
  • 驱逐：LRU 策略，叶节点优先；命中的路径上所有节点引用计数 +1，防止被驱逐
  • 插入：新请求 decode 完成后，把新增 KV 作为新叶节点挂到匹配点下

Radix tree 相对 hash 表的优势是自然表达层级共享：一棵树覆盖 system prompt → 用户历史 → 当前 query 的整条 prefix 链，无需多级 hash。

跨节点 hash 与全局索引​

单节点 radix tree 解决"本实例命中"，跨节点调度还需要"哪些实例上有这个 prefix"。两种工程做法：

做法索引位置代表系统
集中式索引调度器维护全局 prefix → 实例列表的 hash 表，实例通过事件流 (如 ZMQ BlockStored / BlockRemoved) 汇报变化Mooncake Conductor
分布式索引每实例本地 radix tree，调度器只按某个 hash 函数 （如 consistent hashing） 把请求映射到"应该有"的实例部分 SGLang 部署

集中式索引命中精度高，但调度器是单点；分布式索引避免单点但牺牲命中精度 （hash 函数无法表达可变长度 prefix 的层级关系）。Mooncake Conductor 的方案是"集中式 + 按 block_hash 切分键空间"，把单点压力分摊到多个 Conductor 副本。

共享 cache pool​

如果 KV cache 不只在 GPU HBM 内、而是抽到跨节点 DRAM / CXL / SSD 池中 （Mooncake Store 模式），任意 prefill 实例都可以"现拉"已有 KV 而无需重算。这把"cache-aware 调度"的语义从"命中本地"拓展到"命中全局池"，调度算法相应变化：

  • 不再 strictly 选已有 prefix 的实例 — 任何空闲实例都可以拉 cache
  • 代价函数加上 transfer_time(p) = miss_block_count × block_size / link_bandwidth
  • 热门 block 主动复制到多节点 （hot-spot replication，避免单节点拉穿）

代价是池本身的协议栈复杂度，以及拉 cache 的时间是否真比重算快 — 这是 9.7 KV cache 跨节点传输瓶颈 讨论的"RTT-bound vs BW-bound"问题。

主要调度算法是什么​

核心问题：SGLang RadixAttention / Mooncake Conductor / Together CPD / STAR 各自怎么做？

SGLang RadixAttention 的 cache-aware scheduler​

SGLang 的调度对象是单节点内的请求队列。算法目标是在 batch 内最大化共享 prefix 长度，从而提高 KV cache reuse 和 batch 内 attention kernel 的效率。

  • 请求优先级：按"与当前 radix tree 上某节点的共享 prefix 长度"降序排
  • batch 组装：优先把 prefix 重合度高的请求合到同一 batch，使 attention 计算可以折叠 prefix
  • 驱逐协同：当显存不够时驱逐"最近最少使用 + 没被任何正在排队请求引用"的叶子节点，避免驱逐刚要被复用的 prefix

SGLang 报告在多轮聊天、agent tool-use、few-shot 场景下相对无 RadixAttention 的 baseline 取得吞吐数倍提升 （具体数字见原论文 §6）。

Mooncake Conductor 的 cache-aware + load-aware 调度​

Mooncake 调度对象是跨节点的 (prefill, decode) 实例对。Conductor 全局选实例，代价函数综合三项：

代价项含义估计方式
transfer_time(p)把缺失 block 拉到 p 实例的时间miss_block_count × block_size / 链路带宽
prefill_time(p)实际需要算的 prefill 时间f(prompt_len - hit_len(p))，论文用经验拟合曲线
queue_wait(p)p 上排队等待时间当前队列累积 prefill 时长

@tbl-cache-aware-mooncake-cost Mooncake Conductor 三项代价

选 argmin_p (transfer_time + prefill_time + queue_wait)。Decode 侧另外按 TBT SLO 估算选满足且负载最低的 d 实例。

Mooncake 在此基础上加两个机制：

  • Hot-spot replication：同一 prefix block 在短时间内被反复命中同一 p 时，主动把它复制到其它 p，分摊后续请求的 transfer + 排队压力
  • Prediction-based early rejection：在 prefill 前预测请求若被接到 decode 阶段是否会违反 TBT SLO，违反则直接拒绝，避免"做完 prefill 才发现 decode 队列满"的浪费

Together CPD (Cache-aware Prefill-Decode Disaggregation)​

Together AI 在 2026 年 3 月公布的 CPD 系统专门面向长上下文 (100k+ token) 工况。核心想法：

  • 传统 PD 分离把请求按"先到先服务"丢给 prefill 池，热门 prefix 命中只在请求所在实例本地起作用
  • CPD 引入 cache 感知的路由层，让请求直接送到"该实例上已有最长 prefix 命中"的 prefill 节点，再走标准 PD 流程

公开 blog 报告：

  • 在尾延迟敏感 SLA 下，相比传统 disaggregated 设计可持续 QPS 提升 35%-40%
  • 即使存在大量"冷 prompt" （不命中任何已有 prefix） 也能保持紧的 tail latency

CPD 与 Mooncake Conductor 的差异主要在适用场景假设：CPD 假设长上下文工况下 prefix 复用是显著优化项；Mooncake 把它作为整套架构的中心。在算法层面，CPD 公开材料未披露代价函数细节，但其"路由优先级 = prefix 命中长度"的描述与 SGLang 单节点策略的跨节点版相似。

STAR (decode-phase rescheduling + length prediction)​

arXiv:2510.13668 （Wang et al., 2025-10，南大） 提出的 STAR 是首个引入 decode 阶段再调度 的工作。其问题陈述与上述算法正交：

  • 之前的 cache-aware 调度都在 prefill 之前选实例。一旦请求进入 decode 实例，就固定在那里直到完成
  • 当请求 output length 方差极大 （如 reasoning model 的 CoT），decode 实例间会出现严重负载倾斜：先到的长 output 把某实例占住，新到的短 output 在另一实例排队空闲
  • STAR 允许在 decode 已开始后把请求迁移到其它 decode 实例，把当前 KV state 跨节点搬过去；同时通过 hidden states 预测剩余生成长度，作为迁移决策的输入

STAR 的算法做两件事：

决策触发条件
何时触发 rescheduling监控 decode instance 队列长度方差，超阈值触发
选哪个请求迁移优先迁移 KV 体积小、剩余 decode 步数多的请求 （迁移成本低、收益高）

@tbl-cache-aware-star-decisions STAR 两个调度决策

预测层 （按已生成 token 数估计剩余长度） 让算法能在"迁移收益"和"迁移代价"之间做实时权衡。这是把 cache-aware 思路从"请求入口"扩展到"请求生命周期内"的开创性工作。

收益和代价有多大​

核心问题：公开收益数据 + 5 类代价？

收益面 （公开数据）​

系统场景收益来源
MooncakeKimi trace 重放维持 SLO 下多处理 +75% 请求arXiv:2407.00079 §6
Mooncake16k-128k 长上下文模拟吞吐 +50% ~ +525% (vs vLLM 4M)arXiv:2407.00079 §6
Together CPD长上下文 + 尾延迟 SLA可持续 QPS +35%-40%together.ai blog
SGLang RadixAttention多轮 / agent / few-shot吞吐数倍提升 (vs no-RadixAttention baseline)arXiv:2312.07104 §6
STARdecode 不均工况论文表明显著降低 P99 TBT （具体数字见论文 §6）arXiv:2510.13668

@tbl-cache-aware-gains 公开收益数据汇总

代价面​

  • 索引同步开销：集中式 Conductor 是单点，需高可用副本 + 事件流低延迟。Mooncake 用 ZMQ 推送 BlockStored / BlockRemoved，事件量与请求量线性相关
  • 调度算力：全局代价函数对每个候选实例都要算 transfer + prefill + queue 三项，实例数 × prefix 长度的 cost 不可忽略，工程中常用近似 + 缓存历史命中数据
  • 倾斜风险：纯按命中率路由会让热点 prefix 所在实例排长队，必须配 hot-spot replication 或 load 权重
  • 跨节点拉 cache 的不确定性：是否比重算快取决于链路带宽与 KV 体积 (详见 9.7 KV cache 跨节点传输瓶颈)
  • 正确性约束：prefix 命中假设"前缀完全相同则 KV 复用合法"，但若模型有 stateful 行为 （特殊 token、位置编码偏移） 需在 block hash 中纳入相关 metadata，否则命中错误 KV 会导致结果不正确

Takeaway​

知识点核心结论
核心矛盾最大化命中率 vs 维持负载均衡 vs 限制 cache 转移代价
Prefix 复用率Kimi ~50%, L-Eval >80%, arXiv summarization ~0%；强依赖业务结构
Radix tree 优势O(prefix_len) 匹配，自然表达 system prompt → 用户历史 → query 层级
跨节点索引集中式 (Mooncake) 命中精度高有单点；分布式 (consistent hashing) 无单点但精度低
共享 cache pool把语义从"命中本地"扩到"命中全局池"，调度加 transfer_time 项
四种算法SGLang （单节点 batch 内复用） / Mooncake （三项 cost） / CPD （长上下文 prefix） / STAR （decode 再调度）
公开收益Mooncake +75% 请求；CPD +35-40% QPS; SGLang 多轮 / agent 数倍提升
5 类代价索引同步 / 调度算力 / 倾斜风险 / 拉 cache 不确定性 / 正确性约束

参考资料​

  1. SGLang: Efficient Execution of Structured Language Model Programs, arXiv:2312.07104. https://arxiv.org/abs/2312.07104