RadixAttention

在 SGLang 中RadixAttention是其实现零开销Zero-overhead全局 KV Cache 复用的核心机制。传统 Prefix Caching 往往需要手动指定静态 Prefix或者仅支持简单的线性匹配而RadixAttention将运行过程中产生的所有 Token 序列及其对应的 KV Cache 页物理地址索引组织在一棵动态维护的基数树Radix Tree / Compact Trie中。这使得系统能够自动识别并复用任意跨请求、跨多轮对话甚至树状 Agent 分支的公共前缀。下面从数据结构设计、前缀匹配算法和LRU 换出机制三个维度进行深度拆解。一、 基数树Radix Tree数据结构设计Radix Tree 是对传统字典树Trie的优化它将没有分支的单向边节点进行合并压缩避免了深度过高带来的内存与遍历开销。在 SGLang 的 Python/C 运行时后端RadixCache中该结构的设计逻辑如下1. 节点TreeNode的核心字段key(Token 序列段)该节点存储的 Token ID 列表例如[101, 2053, 4012]。由于压缩了无分支边一个key可能包含任意长度的连续 Token 序列。value(KV Cache 页面映射索引)与key中每个 Token 一一对应的物理显存Paged Memory页面索引与 Page Offset 数组。children子节点映射字典或哈希表以首个分支 Token ID 为 Key 映射到子TreeNode。parent指向父节点的指针用于溯源和沿着树自底向上更新锁状态或回收节点。lock_ref(锁引用计数)最关键的状态控制量。表示当前正在被活跃请求In-flight Requests占用/引用的节点数。当lock_ref 0时该节点及其到根节点的路径绝对不可被换出/删除。last_access_time最新访问时间戳用于 LRU 算法选择淘汰候选者。2. 内存中的树形态示例假设系统陆续处理了三个请求Request 1:What is the capital of France?Request 2:What is the capital of Germany?Request 3:What is the weather today?Radix Tree 在内存中的呈现结构如下[ Root Node ] │ Key: [What, is, the] Value: [Page 0, Page 1...] │ ┌────────────┴────────────┐ ▼ ▼ Key: [capital, of] Key: [weather, today?] Value: [Page 2, Page 3] Value: [Page 6, Page 7] │ ┌────────┴────────┐ ▼ ▼ Key: [France?] Key: [Germany?] Value: [Page 4] Value: [Page 5]二、 前缀匹配与节点拆分算法Prefix Matching Insertion当新请求到达时SGLang 会在树上发起快速查询与增量插入。整个过程包含匹配Match、节点拆分Node Splitting和写回Insertion。1. Match前缀匹配流程输入新请求的 Token 数组TTT。从Root节点出发拿TTT的首 Token 检索当前节点的children。沿树向下遍历逐 Token 对比节点中的key与输入TTT。最长匹配终止直到到达叶子节点、或者TTT与节点的key在某一位出现不匹配或者匹配完整个TTT。状态锁定Inc Lock Ref将匹配成功路径上所有节点的lock_ref统一加 1inc_lock_ref。防止在 Prefill 执行期间这些 KV Cache 被并发调度线程换出。返回 KV Cache 索引将匹配到的物理页面索引直接传给 Attention Kernel如 FlashInfer。只有未命中的后缀 TokenDelta Tokens才需要真正送到 GPU 做 Prefill 计算。2. Node Splitting节点切分与 Insertion插入流程如果在匹配或插入过程中新请求与节点中的key部分重合但在中途发生分支Radix Tree 会自动执行节点切分切分场景假设节点存有key [capital, of, France]新请求的 Token 序列为[capital, of, Spain]。切分动作将原节点一分为二公共前缀部分切出作为父节点ParentKey [capital, of]。原节点的剩余部分变更其key为ChildKeyA [France]作为ParentKey的子节点。为新请求新建子节点ChildKeyB [Spain]挂载为ParentKey的另一个子节点。原有的物理 KV Cache 页面索引数组也按切分点Split Point进行精确的 Slice 截断与重映射。三、 LRU 缓存换出与内存回收机制Eviction Policy显存HBM容量是有限的。当系统显存不足以分配新的 Paged KV Cache Block 时RadixCache会触发内存回收。1. 基本原则自底向上与锁保护Leaf-first Lock-aware受保护节点Locked Nodes任何lock_ref 0的节点及其父路径绝对不可被移除。这确保了正在计算的 Request 显存安全。从叶子节点开始淘汰Leaf-first Eviction只有叶子节点Leaf Nodes才能被直接销毁。不能直接删除中间节点否则会损坏整棵树的联通性。2. LRU 算法的执行步骤[显存不足触发 Evict] │ ▼ 遍历所有叶子节点 (Leaf Nodes) │ ▼ 过滤掉 lock_ref 0 的节点 (仅保留锁引用为 0 的游离叶子) │ ▼ 按 last_access_time 排序找到最久未使用的叶子节点 (Oldest Leaf) │ ▼ 释放该叶子节点的 KV Cache 物理 Block 显存并将其从树中删除 │ ▼ 父节点是否变成新的无锁叶子节点 ├── 是 ── 递归将其加入 LRU 候选集继续淘汰 └── 否 ── 终止淘汰检查显存是否满足要求具体逻辑如下系统维护一个未锁定叶子节点的优先队列 / 堆基于last_access_time排序的 LRU 链表。当需要释放MMM个物理 Block 时弹出一系列lock_ref 0且last_access_time最早的叶子节点。释放这些叶子节点所持有的物理显存 Block 句柄归还给底层PageAllocator。剪枝Pruning与收缩当一个叶子节点被删掉后其父节点若不再拥有其他子节点且其自身的lock_ref 0则该父节点退化Degenerate为新的叶子节点。如果淘汰仍未满足显存需求系统会继续递归向上顺藤摸瓜地淘汰该父节点。节点合并Node Merging如果淘汰后某个节点仅剩下一个子节点且没有其他逻辑限制系统会将该节点与其唯一子节点进行重新合并合并key序列保持树结构的紧凑性。四、 总结RadixAttention 的核心工程优势自动前缀发现与零开销复用开发者不需要在应用层手写复杂的前缀 Hash 规则用户发送的所有请求在运行时自动进树完全透明地完成了最高精度的 Token 级 KV Cache 复用。完美契合 Complex Workflows在多轮对话Multi-turn、Few-shot Prompt、RAG 检索增强以及 Agent 分支推演Tree Search / Monte Carlo场景中树状结构能 100% 映射实际的 Context 拓扑结构将首字延迟TTFT降低数倍。细粒度与动态内存管理通过lock_ref机制 与基于 LRU 的自底向上叶子节点裁剪策略使得系统即使在极限高并发、显存极度紧张的情况下也能保证在吞吐量与缓存命中率Cache Hit Rate之间找到最优平衡点。