<aside> 🎯
多个请求共享前缀（system prompt、多轮对话历史、few-shot）的时候，前缀的 KV 只算一次、存一份，后面的请求直接拿来用。这是 SGLang 相对其它引擎最有名的设计。这一页我们先把 RadixAttention 用三个请求走一遍，再看 HiCache 怎么把它扩展到 CPU 内存和外部存储，最后下到代码里看树的插入、去重、对齐和淘汰。
</aside>
用一棵前缀树（Radix Tree）维护「token 序列 → KV 槽位」的映射。新请求到来时从根开始逐段匹配，命中的部分直接复用已有槽位（零拷贝），只对未命中的尾部做 prefill。
flowchart TD
ROOT["root"] --> SYS["system prompt<br>已缓存 KV"]
SYS --> U1["用户 A 的问题<br>已缓存 KV"]
SYS --> U2["用户 B 的问题<br>已缓存 KV"]
U1 --> A1["A 的回答 + 下一轮问题<br>新增节点"]
NEW["新请求 C<br>system prompt + 新问题"] -. "命中 system prompt<br>只需计算新问题部分" .-> SYS
节点会在匹配到一半时被分裂，这就是「radix」的含义：边上存的是一段 token 序列，而不是单个 token。被运行中请求引用的节点不能被淘汰，显存不足时只回收 lock_ref == 0 的叶子节点（下一节展开）。
拿它和 vLLM 的 Automatic Prefix Caching 比一下：思想类似，都是前缀复用，但 SGLang 的 Radix Tree 是调度器的一等公民，调度策略（LPM、DFS-weight、in-batch 去重）直接建立在它之上。vLLM 的 APC 是按固定大小的 block 做 hash，匹配粒度是 block；SGLang 在 page_size=1 时可以做到 token 粒度。（两个项目都在演进，面试前再对照最新实现确认。）
光看概念很容易记混，我们拿三个请求实际走一遍。假设系统里已经缓存了 A B 两个 token，它们的 KV 放在槽位 10、11。现在依次来了：
R1: A B C D
R2: A B C F
R3: A B G H
R1 进来先在树上 match_prefix，命中 A B，拿到槽位 [10, 11]，并把这条路径上的节点 lock_ref += 1。接着 prepare_for_extend 在 req_to_token 里给 R1 分一行，前两格填 10、11，再从分配器里申请 2 个新槽位给 C D（比如 12、20）。forward 时 attention backend 把 C、D 的 K/V 写进槽位 12、20，再用 Q=[C, D]、KV=[10, 11, 12, 20] 算 attention。算完之后，cache_unfinished_req 把 C D 插到树上。
等 R2 来的时候，树上已经有了 A B C D。R2 匹配到 A B C，于是 C D 这个节点被从中间分裂成 C 和 D 两个节点，R2 只需要算 F。R3 只匹配到 A B，要算 G H。最后三张表长这样：
| req_to_token | pos 0 | pos 1 | pos 2 | pos 3 | 含义 |
|---|---|---|---|---|---|
| R1 | 10 | 11 | 12 | 20 | 共享 A B C，私有 D |
| R2 | 10 | 11 | 12 | 25 | 共享 A B C，私有 F |
| R3 | 10 | 11 | 40 | 41 | 共享 A B，私有 G H |
flowchart TD
ROOT["root"] --> AB["A B → [10, 11]<br>lock_ref = 3"]
AB --> C["C → [12]<br>lock_ref = 2"]
AB --> GH["G H → [40, 41]<br>lock_ref = 1"]
C --> D["D → [20]<br>lock_ref = 1"]
C --> F["F → [25]<br>lock_ref = 1"]
这个例子里有三个值得想一想的地方。
第一，前缀命中是零拷贝的。 R2 和 R3 都没有复制 A、B 的 KV，只是在自己那一行里写了 10、11 这两个整数。attention kernel 通过这张表去挑 KV，物理上连不连续无所谓。
第二，写 KV 表和写 radix 树发生在不同时刻。 req_to_token 和槽位分配在 forward 之前（Pre Schedule）就做完了，而把新 token 插进 radix 树，在 forward 之后（process_batch_result）才做。为什么不一起做？因为如果在 forward 之前就插树，同一轮里另一个请求可能命中这段还没算出来的 KV，读到的是垃圾。只有确认 KV 已经写进显存，才能公开给别人用。
第三，lock_ref 是保护正在用的前缀不被淘汰的唯一机制。 一个请求引用了某个节点，就把从该节点到根的整条路径都加 1。请求每推进一次（比如 chunked prefill 的下一块），就把「旧的 last_node」解锁、「新的 last_node」加锁。淘汰时只看 lock_ref == 0 的叶子。
| 步骤 | cache_unfinished_req（chunk 算完、或 prefill 刚结束） |
cache_finished_req（请求结束） |
|---|---|---|
| 从 req_to_token 取出这个请求的槽位 | 是 | 是 |
insert 进 radix 树 |
是 | 是（开了 --strip-thinking-cache 时只插 prompt 部分） |
| 释放重复的槽位 | 是。如果插入时发现树上已经有一份（比如同一轮另一个请求先插了），自己这份就是多余的，归还分配器 | 是 |
| req_to_token 那一行 | 用新的前缀结果重写（指向树上那份） | 整行归还 |
| last_node 的 lock_ref | 旧的减 1，新的加 1 | 减 1，之后就可以被淘汰了 |
注意请求结束时 KV 并没有被释放，只是解除了引用，还安静地躺在树上。显存宽裕时，同一用户的下一轮对话来了就能整段命中；显存紧时，它们会在下一次分配不够时被 evict 按 LRU 一点点清掉。这也解释了为什么监控里 token usage 常常很高，却不代表并发高：大量容量被「可淘汰的缓存」占着，要看 kv_evictable_tokens 才知道真实余量。