读论文：Distributed LLM Serving Scheduling

0. Background

• 不同工作负载 prompts/response token 数之比、共享前缀比例、共享一个前缀的 request 数量：

• 关键问题：实现最大 KV Cache 复用与 GPU 间负载均衡

Load balance ratio(CV) is: \[ CV = \frac{ \sqrt{ \frac{1}{n} \sum_{i=1}^{n}{\left( x_{i} - u \right) }^{2} } } {u} \] where, \(x_{i}\) denotes the number of pending prefill tokens on instance \(i\) , \(u = \sum_{i=1}^{n}{x_{i}}\) .

1. Preble: Efficient Distributed Prompt Scheduling for LLM Serving

1.1 Architecture

1.2 Global Scheduler

• Data Structures：global radix tree
  • 当有新 request 时，进行最大前缀匹配查找，然后进行 tree node split
  • 每个 node 保存以下信息：
    • 当前节点的 token 数量
    • 保存这个 tree node KV Cache 的 GPU 集合
    • 在历史窗口 \(H\) 内，每个 GPU 共享这个 tree node 的请求数量
  • 当一个树节点既没有缓存它的 GPU，且整个系统中在窗口 \(H\) 内也没有共享它的请求时，进行节点删除
• Per-request scheduling policy：
  • 前缀匹配 token 数量大于未匹配 token 数量时，选择“利用”，发送 request 给具有最长匹配且负载最小的 GPU 以复用 KV Cache
  • 反之（前缀匹配 token 数量小于未匹配 token 数量），选择“探索”。考虑三种 load（token 数量 + 模型与GPU 型号决定的线性回归函数），选择负载最小的 GPU：
    • 时间窗口内历史 request 总计算成本（prompts 未匹配 token 数量 + 历史平均 response token 数量）
    • 驱逐 KV Cache 导致的重计算成本（global scheduler 决定驱逐 radix tree 中哪些 node，计算这些 tree node 驱逐后导致的重计算成本之和。每个 node 驱逐后导致的重计算成本 = Prefill tree node token 数量 \(H\) 内共享该 node 的 request 比例）
    • 新 request Prefill 计算成本
  • GPU load cost 伪代码：
  • 
• Post-assignment load adjustment：对于热点 prefix，采取以下两个方法缓解负载不均衡：
  • 如果负载最大的 GPU 达到最小的 \(Th_{bal}\) 倍，直接将 request 发送给负载最小的 GPU
  • 当某个前缀时间窗口 \(H\) 内的平均排队时间翻倍时，进行 radix tree node split，可能导致某些 GPU KV Cache 驱逐以及重计算。
• Prefill-decoding balancing：
  • 在 explore 分支，如果某个 GPU 的 Decode 比例大于阈值，直接选择 Decode 比例最大的 GPU 执行 request。

Global Scheduler 完整算法流程：

1.3 Local Scheduler

• Local scheduler mechanism：类似于 vLLM 单个 GPU 的 scheduler
  • 当显存不够需要驱逐 KV Cache 时，进行 local 驱逐并异步通知 global scheduler
• Waiting queue request ordering：
  • 同时考虑排队时间与 KV Cache 复用减少重计算开销：划分 \(P\) 个队列，根据 prompts 前缀匹配比例将 request 划分到某个队列。选择 request 组成一个 batch 执行时，从匹配比例高的队列中选择较多的 request，按照匹配比例递减。

2. DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving

2.1 Overview

2.2 SLO-aware Request Routing

根据 request，基于两个哈希函数计算得到两个 instance，从中选择一个。

问题 1：

• 多长的 prefix token 作为 hash key？
  • 太长：KV cache reuse 概率降低
  • 太短：hash 冲突，导致负载不均衡
• Solution：自适应哈希前缀长度机制，动态调整每个 request 的前缀长度。
  • global scheduler 维护一个请求前缀热度树（request prefix hotness tree），每个节点记录前缀信息。哈希函数的输入（hash prefix）就是从根节点到叶子节点路径。
    • 当一个叶子节点变热时，增加子节点以扩展前缀。
    • 当一个父节点变冷时，删除子节点以缩短前缀长度。
  • 前缀热度（Prefix hotness）：通过滑动窗口实时监控每个前缀的流量占比 \(\rho\) 来追踪
    • \(\rho\) 定义为时间窗口内共享该 node 的请求占所有请求的比例。
    • \(\rho \gt \frac{2}{n}\) ：hot
    • \(\rho \gt \frac{2}{n}\) drops to \(\rho \lt \frac{1}{n}\) ：cold，删除子节点。

问题 2:

• 2 个 instance 如何选择？
• Baseline：
  • 符号：request 为 \(r\) , instance 为 \(i\)
  • \(T_{q}\left( r, i \right)\) 排队时间
  • \(T_{c}\left( r, i \right)\) 计算时间
  • \(TTFT\left(r, i \right) = T_{q}\left( r, i \right) + T_{c}\left( r, i \right)\)
  • 问题：可能导致频繁切换 instance
• Solution：SLO-Aware Strategy
  • The key idea is to maintain cache affinity whenever possible, and only trade it off when load imbalance threatens to breach SLO constraints.
  • 使用每个 instance 上排队的 prefill token 数量来估计 TTFT，当超过预定义的 TTFT SLO 时，切换到 load-balance 策略。

Corner case：

• 如果两个哈希函数映射到了同一个 instance_id，则取 \(instance\_id_{2} = \left( instance\_id_{1} + 1 \right) \ \mod \ \text{num\_instances}\) 。

2.3 Hotspot-Aware Rebalancing

问题：

• 由于实际的 request 分布倾斜，部分 instance 可能过载，导致尾部 TTFT 明显增长，而部分 instance 处于低负载。

Solution：

• 对于 request 映射到的两个 instance，如果其中一个负载过大，则将部分 request 重定向到另一个 instance
• 注意点：仅当目标 instance 负载较小，估计迁移 request 有收益时，才会执行该策略。
• 定义 request \(r\) 从 instance \(i\) 迁移到 instance \(j\) 的收益为：
• \(B_{r}^{\left(i \to j \right)} = TTFT_{r,i} - TTFT_{r,j} = (T_q(r, i) + T_c(r, i)) - (T_q(r, j) + T_c(r, j))\)
• 仅当 \(B_{r}^{\left(i \to j \right)}\) 为正数且 \(TTFT_{r,j} \lt TTFT_{SLO}\) 的 request 进行迁移。按照从大到小顺序迁移，直到过载 instance 上队列的 request 都可以满足 TTFT SLO。

2.4 Lightweight Dual-hash-ring Scaling

问题：

• 扩缩容
• Solution：
  • 一致性哈希

3、Conclusion

• 必要的 meta 信息维护，以进行 request route
  • Preble：Global Radix Tree
    • 需要较精确感知 cluster 内每个 instance KV Cache 信息（instance evict 后通知 global scheduler）
    • route 自由度更大
  • DualMap：LazyPrefixTable
    • 通过 LazyPrefixTable 和监控 prefix hotness 动态调整 hash prefix 长度，对 instance KV Cache 信息维护更轻量（不需要 instance 与 global scheduler 间通信，而是 global scheduler 模拟每个 instance 维护一个逻辑上的 KV Cache 使用情况，并进行前缀匹配查找/淘汰）
    • 只能 route 到 hash 函数映射到的两个 instance
  • trade-off
    • 实现复杂度
    • route 效果
• 识别热点 prefix，进行多 GPU 迁移
  • Preble：时间窗口内平均排队时间，TreeNode split
  • DualMap：Prefix Hotness，增加 Hash key Prefix 长度
  • trade-off
    • 及时性
    • 准确性