读 BasePrefixCache 与 radix_cache.py#

这章解决什么问题#

前面的调度与内存章节已经把 prefix match、cache_protected_len、host hit 和 load-back 讲得比较深了，但如果你真正打开源码，仍然会遇到一个很具体的问题：

prefix cache 这条主线到底该从哪两个文件开始读，怎样把“抽象 trait”和“真正的 radix tree 实现”接起来？

这条线最核心的两个入口其实是：

  • base_prefix_cache.py
  • radix_cache.py

这章的目标，就是把这两棵树收成一条稳定阅读路径。

为什么这两棵树必须配对读#

单读 base_prefix_cache.py，你会看到：

  • MatchPrefixParams
  • MatchResult
  • InsertParams
  • EvictParams
  • inc_lock_ref(...) / dec_lock_ref(...)

但你还不知道这些抽象在真实树结构里怎样落地。

单读 radix_cache.py，你会看到：

  • TreeNode
  • RadixKey
  • match_prefix(...)
  • _match_prefix_helper(...)
  • cache_unfinished_req(...)
  • cache_finished_req(...)

但你又容易在具体实现细节里迷路，看不清哪些是“prefix cache 家族通用接口”，哪些才是 radix tree 的特化行为。

所以更稳的方式是：

  • 先用 BasePrefixCache 建立抽象边界
  • 再用 RadixCache 看这套抽象怎样真正落地

一张图：prefix cache 这棵树为什么分成“抽象边界”和“具体实现”两层#

这张图解决的理解障碍是：很多读者会直接钻进 RadixCache.match_prefix(...)，结果一开始就被树节点和 split 细节淹没。

flowchart TD
    Base["BasePrefixCache\ntrait + params + results"] --> Ops["match / insert / evict / lock"]
    Ops --> Radix["RadixCache"]
    Radix --> Node["TreeNode / RadixKey"]
    Radix --> Reuse["cache_unfinished_req / cache_finished_req"]
    Radix --> Evict["evictable / protected / eviction policy"]

图比纯文字多解释的一点是：radix_cache.py 不是孤立大文件，它是在实现 BasePrefixCache 这一层统一语义。

第一层：为什么应该先读 BasePrefixCache#

base_prefix_cache.py 最值得先抓住的不是抽象方法列表，而是那几个 NamedTuple / dataclass：

  • MatchPrefixParams
  • MatchResult
  • InsertParams
  • EvictParams
  • IncLockRefResult
  • DecLockRefParams

这组类型非常有价值，因为它们本质上定义了 prefix cache 家族的问题边界：

  • 输入是什么
  • 输出是什么
  • cache match 需要回哪些信息
  • lock 与 eviction 语义怎样被统一表达

也就是说，它在替整本系统定义一套“prefix cache 的公共语言”。

MatchResult 为什么是这条线最重要的抽象#

如果你只记一个对象，最该记的其实是 MatchResult。因为它直接告诉你上游把“prefix 命中”理解成什么：

  • device_indices
  • last_device_node
  • last_host_node
  • host_hit_length
  • mamba_branching_seqlen
  • cache_protected_len

这组字段本身已经说明，prefix match 在 SGLang 里不是一个布尔查询，而是一份：

  • 当前可用前缀视图
  • 节点边界
  • 分层命中信息
  • 保护边界

的复合结果。

换句话说，MatchResult 本身就已经体现了整本书前两轮补过的那些关键观点。

第二层：RadixKey 为什么比看起来重要#

RadixKey 不只是 token ids 包一层。它还明确携带了：

  • extra_key
  • is_bigram

这说明 prefix cache 的逻辑命名空间并不只有“token 前缀”。在实际实现里，命名空间还会被：

  • LoRA / adapter id
  • cache salt
  • 其他不希望共享状态的额外维度

一起决定。

这是非常重要的系统设计点，因为它告诉你：

  • 相同 token 前缀不一定天然应该共享
  • prefix cache 的命名空间本身就是可扩展的

TreeNode 应该怎么理解#

技术书不必把 TreeNode 每个字段都讲成数据结构课，但有几个字段必须读清楚：

  • children
  • key
  • value
  • lock_ref
  • host_ref_counter
  • priority

这几个字段说明节点同时承担三层语义：

  1. 树结构本身
  2. 与 KV 索引值的绑定
  3. 可驱逐 / 被保护 / 主机侧引用的生命周期状态

也就是说，这不是一棵“纯索引树”，而是一棵带缓存所有权语义的树。

match_prefix(...) 为什么会主动 split node#

这是 radix_cache.py 里最值得读者停下来理解的一点。

当匹配结束在某个已存 segment 中间时，系统不会勉强复用模糊边界，而是：

  • 主动 split node
  • 把边界精确暴露出来

这说明 RadixCache 不是一个只查询不改树的结构。prefix match 自己也会让树更适合后续匹配。

这是一种很成熟的设计：

  • 当前多做一次结构细化
  • 后面换来更稳定的边界和更便宜的匹配

cache_unfinished_req(...) 为什么最该结合 ScheduleBatch 读#

这段逻辑和单纯的数据结构课差别非常大，因为它直接在服务运行时里改写：

  • req.prefix_indices
  • req.last_node
  • req.cache_protected_len

也就是说，RadixCache 不是只维护自己的树，它还会回写请求对象，让 scheduler 之后的预算和 extend 决策建立在新的前缀视图上。

这正是为什么本书前面反复说：

  • prefix cache 不是旁路优化
  • 它直接参与 batch 成形与请求推进

cache_finished_req(...) 为什么像“最终交账”#

unfinished 路径更像中途更新保护边界；finished 路径则更像最终结清：

  • 根据 committed KV 最终插树
  • free 重复部分
  • free 未对齐尾部
  • dec_lock_ref(req.last_node)

这说明 finished insertion 的重点并不只是“再写一次树”，而是把：

  • 请求
  • 树
  • allocator

三者之间的所有权关系最终结清。

这是一种很值得技术书专门说透的运行时语义。

inc_lock_ref(...) / dec_lock_ref(...) 为什么要回到 RadixCache 再看一遍#

前面的调度章节已经讲过它们会改：

  • evictable_size_
  • protected_size_

放回 radix_cache.py 再看一次，你会更清楚一点：

  • 这不是抽象 cache trait 的附属操作
  • 而是 radix tree 节点沿 parent 链逐层传播的真实保护逻辑

也就是说，lock 保护的并不只是当前叶子，而是整条被请求持有的前缀路径。

这能帮助你真正理解“为什么 eviction 不是简单地删一段 value”。

eviction policy 为什么值得在这章里提一句#

RadixCache 初始化时会根据配置选择：

  • LRU
  • LFU
  • FIFO
  • MRU
  • FILO
  • Priority
  • SLRU

这说明 radix tree 本身并不等于某种固定驱逐语义。树结构负责：

  • 表达前缀共享

而 eviction policy 决定：

  • 哪些叶子先被逐出

从系统阅读角度看，这有一个很重要的启发：

  • 不要把“是 radix tree”误读成“驱逐策略天然已经定了”

这棵树对排障有什么直接价值#

如果你遇到：

  • prefix reuse 看起来经常失效
  • protected_size_ 与 evictable_size_ 变化不合理
  • 节点似乎命中了，但后面还是多做了不少前向

那么 BasePrefixCache + RadixCache 这组文件就是最稳的第一落点。

因为你在这里能同时确认：

  • 抽象输出里到底承诺了什么
  • 具体树实现里到底做了什么

这比直接一头扎进 scheduler 或 allocator 更容易先把问题层级分清。

如果你要顺着源码读这条 cache 树，推荐顺序是什么#

建议按下面顺序：

  1. base_prefix_cache.py 里的 MatchResult / InsertParams / EvictParams
  2. radix_cache.py 里的 RadixKey
  3. TreeNode
  4. match_prefix(...)
  5. cache_unfinished_req(...)
  6. cache_finished_req(...)
  7. inc_lock_ref(...) / dec_lock_ref(...)
  8. 最后再回到 scheduler 或 ScheduleBatch 看这些结果如何被消费

这样读，你先有抽象边界，再进具体实现，最后再回主链，最不容易迷路。

这一层最容易出现的误判#

1. 以为 RadixCache 只是纯数据结构实现#

它同时承担了前缀所有权、保护和驱逐状态语义。

2. 以为 prefix match 的结果就是一段 token 索引#

真正重要的还包括节点边界、host hit、受保护长度等状态。

3. 以为 eviction 策略是树结构天然决定的#

在实现上，树结构和驱逐策略是分开的。

小结#

这一章真正要补齐的，是代码导读里 prefix cache 这棵树的正式源码入口：

  • BasePrefixCache 给了你一套公共语言
  • RadixCache 把这套语言真正落成树、节点、锁和驱逐逻辑
  • 两者配起来读，prefix reuse 这条主线才会从“概念理解”升级成“源码可读”

到这里，调度与内存章节里那条最难的 cache 主线，就终于有了一棵可以真正顺着去读的源码树。