Cache-aware Scheduling：让命中长的请求先跑

谁该读这一篇？ 已经看过 RadixAttention，想搞清"前缀缓存和调度怎么咬合"的工程师；准备解决"为什么我业务里 cache hit rate 这么低"的运维。 前置阅读： 01-radix-attention.md、03-code-walkthrough/03-scheduler.md §5 至少看过。 耗时： 35 分钟 学完能： 1. 解释 cache-aware 与 FCFS 在算法层的区别； 2. 把 PrefillAdder.add_one_req 的主要逻辑画成流程图； 3. 看到一个具体的等待队列，能用纸笔算出 SGLang 会选哪个请求先跑； 4. 区分 CacheAwarePolicy 和 CacheAgnosticPolicy，知道什么场景下用哪个； 5. 排查"命中率高但调度还是不快"的场景。

1. 问题陈述

朴素 FCFS（先到先服务）的盲点：

等待队列:
  T=0  req-A: prompt=4000 token, prefix 命中 0
  T=1  req-B: prompt=4000 token, prefix 命中 3800   ← 几乎不用 prefill
  T=2  req-C: prompt=4000 token, prefix 命中 0

FCFS 会先跑 A（最早到），把 8000 token 的 prefill 算力消耗掉；B 只能等。但事实是 B 几乎"免费"：3800 token 已经在 cache 里，只需算最后 200 token 的 prefill。

更聪明的策略：先跑 B——既不延迟 B（甚至 SLO 还好），又能让 A 和 C 错开 prefill 算力。

这就是 SGLang 默认 cache-aware policy 的直觉。

2. 策略类型

源码：schedule_policy.py:125。

class CacheAwarePolicy(Enum):
    LPM = "lpm"                    # Longest Prefix Match
    DFS_WEIGHT = "dfs-weight"      # DFS 权重排序（默认）
    PRIORITY = "priority"          # 优先级（业务方传）

class CacheAgnosticPolicy(Enum):
    FCFS = "fcfs"
    LOF = "lof"                    # Longest Output First
    RANDOM = "random"

LPM：直接按"命中长度"降序排队。直觉但对长尾请求不友好。
DFS_WEIGHT：把所有请求映射到 RadixTree 的节点，按"同节点请求成组"先后调度，避免同 prefix 的多请求被打散。
PRIORITY：业务带 priority 字段时按业务给的排序，cache-aware 作为打平时的 tiebreaker。
FCFS / LOF / RANDOM：传统策略，cache-aware 关闭时用。

默认是 DFS_WEIGHT，因为它在多种 workload 下的平均表现最稳。

3. `PrefillAdder.add_one_req`：调度的最内层（813+）

源码：schedule_policy.py:813。

调用栈：

Scheduler.get_next_batch_to_run        (scheduler.py:2348)
  └── Scheduler.get_new_batch_prefill
        └── SchedulePolicy.calc_priority         ← 算每个请求的权重
              └── match_prefix_for_req            ← 算每个请求的命中长度
        └── for req in sorted:
              PrefillAdder.add_one_req(req)       ← 尝试把请求塞进本步 batch
                  return ADDED / FULL / SKIP

add_one_req 的核心逻辑（简化伪代码）：

def add_one_req(self, req):
    # 1. 这个请求需要多少 token 的 prefill？
    new_tokens = req.extend_input_len               # = prompt_len - prefix_cache_hit_len

    # 2. 还剩多少 token budget？
    remaining_budget = self.rem_input_tokens - new_tokens
    if remaining_budget < 0:
        return AddReqResult.NO_TOKEN                # batch 装不下

    # 3. 还剩多少请求槽位？
    if len(self.cur_batch) >= self.max_running_requests:
        return AddReqResult.OTHER

    # 4. KV pool 还有多少 slot？
    if self.token_to_kv_pool_allocator.available_size() < new_tokens + req.max_new_tokens:
        return AddReqResult.OTHER                   # 显存不够

    # 5. 锁住命中的 prefix 节点（避免被并发 evict）
    self.tree_cache.inc_lock_ref(req.last_node)

    # 6. 真正把请求加入 batch
    self.cur_batch.append(req)
    self.rem_input_tokens -= new_tokens
    return AddReqResult.CONTINUE

关键不变量：

lock_ref 在调度时增：避免命中的节点在请求开始 prefill 之前被淘汰。
token budget 单调递减：每一轮所有加入 batch 的请求总 token 不超过 max_prefill_tokens。
slot 检查：把"KV pool 是否够装最大输出"也算进去，避免请求半路 OOM。

4. `calc_priority`：怎么算分数（162+）

schedule_policy.py:162。

对每个请求计算一个权重（数字越小越优先）：

def calc_priority(self, policy: str, waiting_queue: List[Req]):
    if policy == "lpm":
        # 直接按 -prefix_len 排序
        waiting_queue.sort(key=lambda r: -r.prefix_indices.shape[0])
    elif policy == "dfs-weight":
        # 按 RadixTree 的 DFS 序：同 prefix 子树请求成簇
        ...
    elif policy == "priority":
        waiting_queue.sort(key=lambda r: (r.priority, -r.prefix_indices.shape[0]))
    ...

DFS_WEIGHT 思路：

RadixTree:
                root
               /    \
            [P1]    [P2]
            / \      |
          [A] [B]   [C]

waiting queue 里有: A, C, B
DFS 序: P1-A, P1-B, P2-C → 排序后: A, B, C

这样 A 和 B 紧邻被调度，attention kernel 可以一次性吃下"shared P1 prefix"做 cascade，比把 A、C、B 错开调度高效。

5. 一次完整的调度循环（举例）

设定：

max_prefill_tokens = 4096
max_running_requests = 16
KV pool 剩 50000 token slot
等待队列（按到达顺序）：
A: prompt=2000, hit=1900（净 100）
B: prompt=4000, hit=0（净 4000）
C: prompt=2000, hit=1800（净 200）

FCFS 调度：

加 A：budget 4096-100=3996 ✓
加 B：budget 3996-4000<0，装不下 → 留到下一步
加 C：budget 3996-200=3796 ✓
本步 batch: [A, C]，token=300

但 B 在下一步还是要等。

Cache-aware (LPM)：排序按命中：A(1900) > C(1800) > B(0)

加 A：budget 3996 ✓
加 C：budget 3796 ✓
加 B：budget < 0 → 装不下
本步 batch: [A, C]，token=300

这一轮看起来一样，但收益体现在多轮平均：cache-aware 让 A、C 这种"prefill 几乎不花钱"的请求始终能优先吃上算力，B 这种"prefill 很重"的请求被推迟到 chunked prefill 模式去切片处理。

6. 病态情况：什么时候 cache-aware 反而不好

6.1 长尾队首

waiting queue:
  X: hit=10000 token  ← 命中超长，运行时一直让 X 占算力
  Y: hit=0
  Z: hit=0

X 调度后会一直跑（直到完成），新到的 Y、Z 等很久。这就是"长尾 starvation"。 SGLang 通过 _abort_on_waiting_timeout + 最大等待时间限制来兜底，但仍要监控。

6.2 命中评估错误

如果 RadixCache 因为显存压力评估命中长度时已经把节点 evict 了（罕见），调度算的命中和真实命中不一致。源码里 inc_lock_ref 就是为了避免这个 race；但极端并发下还是要注意。

6.3 短 prompt + 高命中

所有请求 prompt = 100, hit = 90

命中长度都一样，cache-aware 退化为 FCFS。这种 workload 不需要 cache-aware。

6.4 突发新业务上线

新业务的 system prompt 还没沉淀进 RadixCache，最初 N 个请求命中全是 0。按理说应该先让前几个请求"热"起来 cache，但 cache-aware 偏把这些请求排到后面，新业务延迟一上线就飙高。对策：业务上线时用 warmup 脚本先发几个 dummy 请求把缓存"热"一下（见 07-hands-on/01-setup.md）。

7. 与 chunked prefill 的协同

记得 03-code-walkthrough/03-scheduler.md §5 提到 token budget：一步喂进 GPU 的总 token 受限。 cache-aware 的副作用：长 prompt 低命中请求（B）总是被排到队尾。解决：chunked prefill 把 B 切成多个 4096 token 的 chunk，每轮喂一段，穿插在高命中请求之间。

轮 1: A (100) + C (200) + B[0:4096]    总=4396 ≤ budget   ✓
轮 2: D (50)  + B[4096:8192]           总=4146           ✓
轮 3: B[8192:12288]                   总=4096            ✓

实现细节：调度器维护 chunked_req 状态，每轮看 budget 还剩多少切 B 的下一片。

8. 性能监控指标

指标	含义	健康范围
`cache_hit_rate`	整体命中率	> 30% 业务正常，否则 cache-aware 没意义
`waiting_queue_size`	等待队列长度	持续涨 → 容量不够
`waiting_time_p99`	队尾请求等多久	< 1s 通常 OK
`prefill_tokens_per_iter`	每轮平均 prefill token	接近 max_prefill_tokens 说明 budget 饱和
`time_to_first_token_p99`	TTFT p99	SLO 决定

这些都在 /metrics 暴露，配 Grafana 看趋势。

9. 调优 cheatsheet

现象	调什么
cache_hit_rate < 10%	业务前缀复用度低；考虑改业务（统一 system prompt）或换 FCFS
TTFT 突增、waiting_queue 涨	增 `max_prefill_tokens` 或加副本
长尾请求一直 starve	减 `max_running_requests`、用 priority 策略
大量 chunked prefill 切片	检查长 prompt 占比；可能要分流量
evict 频繁	KV pool 太小；增 `mem-fraction-static`

10. 切换策略的方法

python -m sglang.launch_server \
    --model-path ... \
    --schedule-policy fcfs              # 关 cache-aware
# 或
    --schedule-policy lpm               # 直接 LPM

完整选项见 server_args.py 里 schedule_policy 字段的注释。

11. 小结

Cache-aware scheduling 在等待队列里把"命中长度"作为权重，优先跑命中多的请求。
默认 dfs-weight：把同 prefix 子树的请求成簇调度，配合 Cascade attention。
关键源码：schedule_policy.py 的 calc_priority 和 PrefillAdder.add_one_req。
病态：长尾 starvation、新业务冷启动、短 prompt 全命中等。
监控：cache_hit_rate + waiting_queue_size + TTFT p99。

12. 自检

cache-aware 与 FCFS 的核心算法差异？什么时候 cache-aware 退化为 FCFS？

答案

FCFS：按到达时间排序，无视 cache 状态。 cache-aware：按"命中长度"（LPM）或"radix tree DFS 序"（DFS_WEIGHT）排序，命中多的优先；DFS_WEIGHT 额外把"同 prefix 子树"成簇调度（配合 Cascade attention）。退化条件：所有请求命中长度相同（都是 0 或都是相同值）→ 排序 tie，按入队顺序退化为 FCFS。短 prompt 全无前缀复用的场景就这样。

dfs-weight 为什么比 lpm 在平均场景下更稳？

答案

LPM 只看单请求的命中长度，可能把"prefix A 子树的请求"和"prefix B 子树的请求"交错调度，cascade attention 没法合批。 DFS_WEIGHT 按 radix tree DFS 序排，**同一 prefix 子树的请求一定相邻调度**，FlashInfer 的 MultiLevelCascade wrapper 能一次性算这一簇请求的 shared prefix attention。平均场景下两者的"命中长度"分布差不多，但 DFS_WEIGHT 把 cascade kernel 收益最大化，所以更稳。

add_one_req 里有 5 个失败原因（NO_TOKEN / OTHER 等），分别对应什么？

答案

主要返回值（[`schedule_policy.py`](../sglang/python/sglang/srt/managers/schedule_policy.py) `AddReqResult`）： - `CONTINUE`：成功加入 batch。 - `NO_TOKEN`：本步 token budget（max_prefill_tokens）剩余不足。 - `OTHER`：max_running_requests 满 / KV pool slot 不够 / chunk prefill 状态不允许加入。还有针对 chunked prefill 的特殊状态（要让正在切分的请求继续而不接新请求）。每个返回值对应不同的后续逻辑：`NO_TOKEN` 等下一轮、`OTHER` 通常意味着要等更多请求完成。

cache_hit_rate = 5% 时还应该开 cache-aware 吗？为什么？

答案

可以开但收益小。开的代价基本可忽略（排序 + 一次 hash 表查），收益是那 5% 命中的请求能被优先调度。但如果命中长度方差大（少数请求命中长，多数 0），cache-aware 仍能让那少数命中长的请求"白嫖"——所以不要光看 hit_rate，要看命中长度分布。只在确认"命中分布几乎全 0"时考虑切 FCFS（极简部署、调试基准）。

新业务上线时怎么避免命中率突增带来的延迟？

答案

两条路： (a) **Warmup**：上线前用 dummy 请求把高频 system prompt 喂一遍，让 RadixCache 沉淀。具体见 [`07-hands-on/01-setup.md`](../07-hands-on/01-setup.md) §8。 (b) **流量灰度**：先放 1-5% 流量进新业务，让 cache 自然建立，再逐步加大。不做的话：前 N 个请求命中都是 0，但 cache-aware 把它们排到后面（因为有老业务命中长的），新业务延迟突增；老业务也因为新业务突发 prefill 抢算力跟着抖。

13. 下一步

04-compressed-fsm.md — 另一个核心优化。
03-code-walkthrough/03-scheduler.md — 调度主循环源码精读。
07-hands-on/03-debug-scheduler.md — 给调度加 print 看现象。
源码：schedule_policy.py、schedule_batch.py。

上游源码：sglang/python/sglang/srt/managers/schedule_policy.py。