prefix reuse 与 cache 命中#

很多人第一次读推理 runtime，会把前缀复用理解成一句很简单的话：如果两个请求前缀一样，就复用已有 KV。这个理解不算错，但远远不够。因为在真实运行时里，“命中了前缀缓存”并不自动等于“这一轮就更快”，也不自动等于“调度器就能更积极地接新请求”。

这一节只处理三件事：

  1. prefix reuse 在 SGLang 里是怎样被表达的；
  2. cache 命中的收益和调度推进是怎样互相影响的；
  3. 为什么前缀命中是 runtime 主能力，而不只是内存优化技巧。

一张图先看 prefix reuse 的位置#

flowchart LR
    A["Req / origin_input_ids"] --> B["tree_cache match"]
    B --> C["reuse committed KV"]
    C --> D["ScheduleBatch"]
    D --> E["ForwardBatch / ModelRunner"]

这张图最值得记住的一点是：prefix reuse 不发生在执行层末端，也不只是 cache 层内部动作。它在 scheduler 组织 batch 时就已经开始影响后续路径。

cache 命中不是一个布尔值，而是一条状态路径#

SGLang 在这一层真正依赖的是 tree_cache。而默认最重要的实现之一，就是 RadixCache 。

从 RadixCache 的初始化可以直接看出它背后的几件事：

  • 它拿到 req_to_token_pool
  • 它拿到 token_to_kv_pool_allocator
  • 它知道 page_size
  • 它有独立的 eviction policy

这说明“命中缓存”并不只是 dictionary lookup。它依赖的不是单个结构，而是一整套：

  • 请求到 token 位置的映射
  • token 到物理 KV 的映射
  • 树状前缀匹配结构
  • 驱逐策略

所以更准确的说法不是“缓存有没有命中”，而是“当前请求在多大程度上复用了已经 committed 的前缀状态”。

为什么命中前缀不自动等于更快#

这是这一节最容易讲浅的地方。前缀命中确实通常意味着：

  • 某些 token 不必重新 prefill；
  • 某些 KV 不必重新构造；
  • scheduler 手里的资源压力会下降一些。

但它不自动等于这轮一定更快，原因至少有三类：

  1. 调度时机
    命中了 cache，不代表这轮马上能进 batch。
  2. 资源状态
    即使前缀复用了，当前的 waiting queue、grammar、multimodal 或 running batch 状态仍然可能把新请求挡在外面。
  3. cache 策略本身
    命中的段有多长、是否被保护、是否很快又会被驱逐，这些都会改变收益。

也就是说，prefix reuse 的收益不是抽象收益，而是 runtime 当下状态下的局部收益。

ReqToTokenPool 和 prefix reuse 为什么绑得这么紧#

前缀复用之所以能成立，不只是因为树里能找到公共前缀，还因为系统必须知道这些前缀对应到哪些真实 KV 位置。这就是 ReqToTokenPool 的意义。

memory_pool.py 文件头已经把这层说得很明确：

SGLang has two levels of memory pool.
ReqToTokenPool maps a request to its token locations.
TokenToKVPoolAllocator manages the indices to kv cache data.

这意味着 prefix reuse 从来不是“只要字符串前缀一样就行”。真正可复用的是：前缀 token 已经对应到了稳定的 KV 位置，而这条映射仍然有效。

RadixCache 的三个核心操作#

RadixCache 的价值不在于”树结构比较高级”，而在于它把前缀复用的几个关键决策集中到了一层。理解它的三个操作——match_prefix、insert、evict——才能真正解释”前缀明明一样，但命中效果很奇怪”这类问题。

match_prefix：找最长可复用前缀#

match_prefix(token_ids) -> (matched_len, kv_indices)

匹配过程从根节点开始，沿树向下走：

  1. 在当前节点的子节点中，找到 key 与 token_ids 剩余部分共同前缀最长的那个；
  2. 如果找到，把 matched_len 向前推进，继续向下；
  3. 如果该子节点的 key 只部分匹配（比如 key 是 [A, B, C] 但 token_ids 只剩 [A, B]），停在这里——不拆节点，直接返回已匹配的部分；
  4. 返回时，matched_len 向下取整到 page_size 的倍数（见下文）。

返回结果是”可以安全复用的 token 数”以及”这些 token 对应的物理 KV slot 位置”。

insert：把新前缀写入树#

insert(token_ids, kv_indices)

插入过程先走 match_prefix 找到最长已有前缀，然后处理剩余部分：

  1. 如果剩余部分对应的子节点不存在，直接新建叶节点，key 为剩余 token_ids；
  2. 如果存在部分匹配的子节点（key 是 [A, B, C, D] 但新 token_ids 和它只共享 [A, B]），执行节点分裂：
    • 把该子节点 split 成两层：[A, B] 作为新内部节点，[C, D] 成为它的子节点；
    • 新 token_ids 的剩余部分 [C, ...] 作为另一个子节点挂在 [A, B] 下。

分裂操作保证了树中所有路径在分叉点之前都是公共前缀。

page_size 边界：为什么复用不总是精确的#

RadixCache 的匹配结果会对齐到 page_size（默认 16 tokens）的整数倍。原因是：

KV cache 的物理分配以 page 为单位。一个 page 需要该 page 内所有 token 的 KV 都已经写入才是”committed”的。如果一个请求写到第 20 个 token 时中止，第 17-20 号 token 所在的 page 只写了一部分，这个 page 的 KV 是不完整的，不能被其他请求安全复用。

所以即使你有公共前缀 25 tokens，match_prefix 最多返回 16（第一个完整 page）。第 17-25 个 token 需要重新 prefill。

实际影响：公共前缀越长，page_size 对齐的浪费比例越小。如果公共前缀只有 20 tokens，有 4 个 token（20%）被浪费；如果公共前缀有 1024 tokens，只有最后一个未满 page 最多浪费 15 tokens（约 1.5%）。

evict：谁最先被清掉#

驱逐只能发生在叶节点上（没有子节点、且没有被任何活跃请求引用的节点）。内部节点因为还被多个子节点共享，不能单独驱逐。

驱逐策略由 eviction_policy 控制，默认是 LRU：

  1. 维护一个按”最近访问时间”排序的叶节点列表；
  2. 当需要释放 N 个 pages 时，从最久未访问的叶节点开始驱逐；
  3. 驱逐一个叶节点后，它的父节点可能变成叶节点（如果父节点原来只有这一个子节点），父节点随即进入 evictable 集合。

这个逻辑解释了为什么 token_usage 接近 1.0 时 cache_hit_ratio 会下降：系统在不断驱逐最近没被复用的叶节点，而如果正好驱逐了下一批请求会用到的前缀，就产生了 cache miss。这是 LRU 在 prefix cache 场景下的天然劣势——它不知道未来的请求会用哪些前缀。

这意味着如果你看到”前缀明明一样，但命中效果很奇怪”，更稳的切入点通常不是先看 scheduler admission，而是先回到 tree_cache 这一层，确认节点是否还在树里、是否被驱逐策略清掉了。

prefix reuse 和 batch shaping 为什么必须一起理解#

从全书结构看，这一节之所以放在 5.1 后面，不是因为 cache 比 queue 更底层，而是因为它们回答的是同一件事的两个侧面：

  • 5.1 问的是：这一轮 batch 为什么这样组成；
  • 5.2 问的是：这一轮为什么可能少做一些 prefill。

把这两层拆开是必要的，但如果完全分开理解，又会重新出错。因为真正的 batch shaping，往往已经把 cache 状态算进去了；而 cache 命中的收益，也常常要靠 scheduler 下一轮的 admission 才能真正兑现。

调试 prefix reuse 时先看哪里#

如果你看到的现象是：

  • 请求前缀看起来相同，但性能没有明显改善；
  • cache 命中有时很好，有时又突然失效；
  • 某类请求一进来就把原本不错的复用效果冲掉；

更稳的顺序通常是：

  1. 先确认请求的 origin_input_ids 和前缀是否真的一致；
  2. 再看 tree_cache 是否还能命中这段前缀；
  3. 然后确认对应的 KV 位置是否仍然有效，没有被驱逐或保护策略改变；
  4. 最后再回头看 scheduler admission，是不是虽然命中前缀，但这轮依然没能及时进 batch。

这样排的好处是，你能把“没命中”和“命中了但收益没兑现”分开看。

小结#

这一节真正要建立的是三个判断：

  • prefix reuse 不是纯内存技巧，而是 runtime 主能力；
  • cache 命中不是简单布尔值，而是一条依赖映射、匹配和驱逐策略的状态路径；
  • 命中前缀不自动等于更快，收益还要看当下的 scheduler 状态和资源状态。

理解了这几点，后面再看 KV 生命周期和执行模型时，就不会把 cache 命中误读成“命中就一定省事”的简单条件。