系列：那些值得深究的源码
难度：⭐⭐⭐⭐（1-5星）
本篇精读：SGLang · sgl-project/sglang^[1] · tag v0.5.9，commit bbe9c7eeb520b0a67e92d133dfc137a3688dc7f2
分析重点：沿着 RadixCache -> SchedulePolicy -> Scheduler -> ScheduleBatch 这条路径，分析 RadixAttention 怎样把前缀命中变成调度排序、batch 输入裁剪、KV index 生命周期和驱逐边界。
前置知识：能读 Python，了解 Transformer prefill、KV cache、continuous batching 和 serving 调度基础。

1. 术语表（前置阅读）

• • SGLang：面向大语言模型和多模态模型的 serving/runtime 框架。官方 README 和文档把 RadixAttention、continuous batching、paged attention、PD disaggregation 等作为主要 runtime 能力，见 sgl-project/sglang^[1] 和 SGLang Docs^[2]。
• • RadixAttention：SGLang 论文和官方博客提出的自动 KV cache 复用机制，用 radix tree 组织 token 前缀，让复杂 LLM 程序里的共享 prompt 片段可以被复用；背景可读 LMSYS 官方博客^[3] 和论文 SGLang: Efficient Execution of Structured Language Model Programs^[4]。
• • Radix tree / compressed trie：把连续 key 片段压缩到节点里的前缀树。SGLang 的节点 key 是 token id 序列加可选 extra_key，value 是对应 KV cache index。
• • prefix cache：跨请求复用相同前缀已经计算出的 KV cache。它不是普通 prompt hash cache，而会参与调度、batch 构造、allocator 和 eviction。
• • Req：SGLang scheduler 里的请求对象，保存原始输入、生成输出、prefix_indices、last_node、host/storage 命中统计等状态。
• • SchedulePolicy：等待队列排序策略。lpm、dfs-weight 等 cache-aware policy 会先做 prefix match，再按命中信息调整请求顺序。
• • ScheduleBatch：scheduler 选出一批请求后构造的 batch 对象，负责把请求级 prefix_indices 转成 batch 级 prefix_lens、input_ids、out_cache_loc 等 forward 输入。
• • lock_ref：RadixCache 节点被运行中请求引用的计数。lock_ref > 0 的节点不能被驱逐。
• • evictable leaf：没有被 lock 且位于 radix tree 叶子位置的缓存节点。SGLang 从叶子往上驱逐，避免误删共享前缀。
• • HiCache：SGLang 的层级 KV cache 能力，涉及 GPU、host、storage 不同层级的命中和预取。这里先看它和基础 prefix cache 接口的交界，背景可读官方 HiCache 文档^[5]。

2. 版本、范围和阅读边界

分析版本固定为 SGLang tag v0.5.9，commit bbe9c7eeb520b0a67e92d133dfc137a3688dc7f2。源码许可为 Apache-2.0；后面引用的源码片段均为该版本的短节选和删减。

SGLang 官方把它描述为面向大语言模型和多模态模型的高性能 serving 框架，重点能力包括 RadixAttention、prefix caching、continuous batching、paged attention、PD disaggregation、speculative decoding 等。官方 README^[1] 和 SGLang 文档首页^[2] 都把 RadixAttention 放在 runtime 能力的核心位置。早期的 LMSYS 官方博客《Fast and Expressive LLM Inference with RadixAttention and SGLang》^[3] 解释得更直接：复杂 LLM 程序里经常有 few-shot examples、chat history、tree-of-thought search history 这类共享前缀，如果每次都从头 prefill，就会重复消耗计算和 KV cache 显存。SGLang 论文 SGLang: Efficient Execution of Structured Language Model Programs^[4] 也把 RadixAttention 作为 runtime 侧的关键优化之一。

RadixAttention 如果只停在“radix tree 复用前缀”这一层，很容易漏掉它和调度器的互相牵制。沿着 v0.5.9 的真实源码往前走，几个问题会变得具体：前缀命中发生在哪里，命中结果怎么影响 waiting queue 的排序，KV cache 索引怎么从 Req 传到 forward batch，请求结束以后缓存怎么插回 radix tree，显存不够时哪些节点可以被驱逐。

接下来主要沿着这些源码走。

先看架构图。它把前缀缓存所有权、排队顺序、batch 构造和 forward 输入边界放在同一张图里。

图里的类比只对应源码对象本身：RadixCache 可以想成一棵共同开头的目录树，树上挂的是已经算好的 KV cache index；lock_ref 决定哪些目录页暂时不能被撕掉。源码里可确认的是 Req.prefix_indices、last_node、allocator 和 tree 节点之间的状态传递。

3. 先看运行路径

SGLang 的前缀缓存不是 attention backend 里临时做一次查表。它更像 runtime 的一条共享状态路径：请求进入 scheduler，调度策略先用 radix tree 做 prefix match，然后 scheduler 根据排序结果选出能跑的请求，ScheduleBatch.prepare_for_extend() 再把命中的 prefix 从本轮 prefill 输入里扣掉，只对剩余 token 分配 KV cache 和执行 forward。请求完成或被 chunked prefill 暂停时，再把已经产生的 KV cache 写回 tree。

RadixAttention 的共享发生在 scheduler 和 batch construction 阶段。kernel 最终看到的是已经整理好的 ForwardBatch；哪些 token 可以跳过 prefill，由 scheduler 之前的 cache matching 和 batch construction 决定。

4. RadixCache 的数据结构

RadixCache 继承自 BasePrefixCache。它维护一棵 radix tree，key 是 token id 序列加一个可选的 extra_key，value 是对应 token 的 KV cache index。节点上还维护 lock_ref、last_access_time、hit_count、priority、hash_value、host cache 相关字段等。

第一段代码是 RadixKey 和 TreeNode 的骨架。这里值得注意的是，extra_key 被放进 key 命名空间里，这意味着 LoRA、cache salt 或其他隔离条件可以让相同 token 序列不共享 KV cache。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class RadixKey:
    def __init__(
        self,
        token_ids: List[int],
        extra_key: Optional[str] = None,
        is_bigram: bool = False,
    ):
        self.token_ids = token_ids
        self.extra_key = extra_key
        self.is_bigram = is_bigram


class TreeNode:
    def __init__(self, id: Optional[int] = None, priority: int = 0):
        self.children = defaultdict(TreeNode)
        self.parent: TreeNode = None
        self.key: RadixKey = None
        self.value: Optional[torch.Tensor] = None
        self.lock_ref = 0
        self.last_access_time = time.monotonic()
        self.hit_count = 0
        self.host_ref_counter = 0
        self.host_value: Optional[torch.Tensor] = None
        self.hash_value: Optional[List[str]] = None
        self.priority = priority

源码位置：radix_cache.py^[6]。

它和普通 trie 的粒度不同。普通 trie 的每条边通常对应一个 token，radix tree 会把连续 token 压缩到一个节点的 key 里。这样节点数量更少，但也带来一次关键操作：如果一次 match 停在某个节点 key 的中间，就必须 split node，把公共前缀单独暴露出来。

可以把 radix tree 想成一套共享目录。普通 trie 像每个字都单独建一层文件夹，路径很长；radix tree 会把一段连续路径压成一个文件夹名，比如 system prompt + few-shot。当新请求只共享这个文件夹名的前半段时，SGLang 就把文件夹拆成“公共前半段”和“后续分支”。这个比喻只对应 TreeNode.key 和 _split_node()，不要扩展成文件系统语义；节点上的 value 是 KV cache index。

RadixAttention 依赖的正是这种数据结构：缓存条目不再是孤立的 prompt hash，而是一棵可被不断 refine 的前缀树。它能表达聊天历史、few-shot 样例、self-consistency 多分支等模式，也能处理完全相同 prompt 之外的部分共享。

5. match_prefix 返回 KV index 和 last node

match_prefix() 返回 MatchResult。其中 device_indices 是最长命中前缀对应的 KV cache index tensor，last_device_node 是命中路径的最后节点。后续请求会用这个节点做 lock ref，避免正在被请求使用的 KV cache 被驱逐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def match_prefix(self, params: MatchPrefixParams) -> MatchResult:
    key = params.key
    key, _ = self.maybe_bigram_convert(key)

    def empty_match_result():
        return MatchResult(
            device_indices=torch.empty((0,), dtype=torch.int64, device=self.device),
            last_device_node=self.root_node,
            last_host_node=self.root_node,
        )

    if self.disable or len(key) == 0:
        return empty_match_result()

    if self.page_size != 1:
        page_aligned_len = len(key) // self.page_size * self.page_size
        key = key[:page_aligned_len]

    value, last_node = self._match_prefix_helper(self.root_node, key)
    value = torch.cat(value) if value else torch.empty((0,), dtype=torch.int64, device=self.device)
    return MatchResult(device_indices=value, last_device_node=last_node, last_host_node=last_node)

源码位置：RadixCache.match_prefix^[10]。

page_size != 1 时，函数会把 key 截到 page 对齐长度。SGLang 的 KV cache 可能是 paged layout，缓存复用不能只看 token 语义上的最长公共前缀，还要看底层 KV 页面是否能完整复用。返回值保留 last_node，因为命中不仅影响这次输入裁剪，还影响后续 lock、evict、unfinished req caching。

match_prefix() 的返回值不能按一个布尔命中来理解。它更像图书管理员递给你两样东西：一摞已经找到的书页编号，也就是 device_indices；还有最后停在哪个书架，也就是 last_node。前者让 batch 构造知道哪些 token 不用重算，后者让 cache 生命周期知道哪些节点正在被请求保护。只返回命中长度，不够后面这些步骤使用。

树遍历落在 _match_prefix_helper()。如果命中停在节点中间，它会调用 _split_node()，让公共前缀变成独立节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def _match_prefix_helper(self, node: TreeNode, key: RadixKey):
    access_time = time.monotonic()
    node.last_access_time = access_time

    child_key = self.get_child_key_fn(key)
    value = []
    while len(key) > 0 and child_key in node.children.keys():
        child = node.children[child_key]
        child.last_access_time = access_time
        prefix_len = self.key_match_fn(child.key, key)
        if prefix_len < len(child.key):
            new_node = self._split_node(child.key, child, prefix_len)
            value.append(new_node.value)
            node = new_node
            break
        else:
            value.append(child.value)
            node = child
            key = key[prefix_len:]
            if len(key):
                child_key = self.get_child_key_fn(key)
    return value, node

源码位置：RadixCache._match_prefix_helper^[11]。这段实现有一个很好的判断：match 本身允许改变树结构。很多缓存实现会把 lookup 设计成只读操作，但 radix tree 的最优形态依赖访问模式，读的时候顺手 split，可以让后续共享边界更准确。

6. 调度策略：命中长度先改变排队顺序

如果只在 forward 前裁掉已经命中的 token，prefix cache 当然能省计算，但还不够。排队顺序也会影响整体命中率。SGLang 的 SchedulePolicy 定义了 cache-aware policy，包括 lpm 和 dfs-weight。lpm 是 longest prefix match，直觉上就是先跑缓存命中多的请求。

关键代码在 _compute_prefix_matches()：它遍历 waiting queue，对每个请求调用 tree_cache.match_prefix()，然后把结果写回 Req 对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def _compute_prefix_matches(
    self, waiting_queue: List[Req], policy: CacheAwarePolicy
) -> Set[int]:
    temporary_deprioritized: Set[int] = set()
    self.waiting_queue_radix_tree.reset()

    for r in waiting_queue:
        prefix_ids = r.origin_input_ids + r.output_ids
        extra_key = r.extra_key
        match_result = self.tree_cache.match_prefix(
            MatchPrefixParams(key=RadixKey(token_ids=prefix_ids, extra_key=extra_key))
        )
        (
            r.prefix_indices,
            r.last_node,
            r.last_host_node,
            r.host_hit_length,
        ) = (
            match_result.device_indices,
            match_result.last_device_node,
            match_result.last_host_node,
            match_result.host_hit_length,
        )

源码位置：SchedulePolicy._compute_prefix_matches^[12]。

这段代码说明一件事：prefix match 是调度输入，不是 batch 构造之后的附属结果。Req.prefix_indices 之后会一路进入 ScheduleBatch，Req.last_node 则是缓存生命周期管理的句柄。

lpm 的排序很直接：没有被临时降权的请求，按 len(r.prefix_indices) 从大到小排。这里还有一个 in-batch prefix caching 的小机制：如果请求对现有 tree 命中很少，但它们在 waiting queue 内部共享较长前缀，策略会临时降权后面的同前缀请求，倾向先跑一个，等它把 KV cache 插进 tree，后面的请求再利用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

if len(r.prefix_indices) <= IN_BATCH_PREFIX_CACHING_CHECK_THRESHOLD:
    match_result = self.waiting_queue_radix_tree.match_prefix(
        MatchPrefixParams(key=RadixKey(token_ids=prefix_ids, extra_key=extra_key))
    )
    in_batch_matching_prefixes = match_result.device_indices
    if len(in_batch_matching_prefixes) >= IN_BATCH_PREFIX_CACHING_DEPRIORITIZE_THRESHOLD:
        temporary_deprioritized.add(r.rid)
    else:
        self.waiting_queue_radix_tree.insert(
            InsertParams(
                key=RadixKey(token_ids=prefix_ids, extra_key=extra_key),
                value=torch.empty(len(prefix_ids), dtype=torch.bool),
            )
        )

这段逻辑服务于 serving 系统里的一个常见取舍：当前 batch 的最短排队时间，不一定等于后续几个 batch 的最高吞吐。SGLang 在这里用很轻的 simulated radix tree 捕捉 waiting queue 内部的潜在共享，不需要真的分配 KV cache。

可以把这段调度想成拼车排队。FCFS 是谁先到谁先上车；LPM 会优先让路线重合更长的人上车，因为一辆车能顺路带更多人。in-batch prefix caching 则更细一点：如果队伍里有几个人路线很像，但第一位还没把路线变成系统里的可复用缓存，后面几位可以稍微等一等，让第一位先跑完，把公共路线登记进 tree。这个比喻只对应等待队列排序，不表示 SGLang 会牺牲所有公平性；源码里仍保留多种 policy 和降权阈值。

7. Scheduler 把 cache-aware policy 接进 prefill batch

Scheduler._get_new_batch_prefill_raw() 是 prefill batch 的主路径。它先让 policy 计算优先级，然后创建 PrefillAdder。PrefillAdder 拿到 tree_cache、KV allocator、running batch、prefill token budget 等信息，逐个尝试把 waiting queue 里的请求加进本轮 prefill。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

self.policy.calc_priority(self.waiting_queue, self.running_batch)

adder = PrefillAdder(
    self.page_size,
    self.tree_cache,
    self.token_to_kv_pool_allocator,
    self.running_batch,
    self.new_token_ratio,
    self.max_prefill_tokens,
    chunked_prefill_size,
    running_bs if self.is_mixed_chunk else 0,
    self.priority_scheduling_preemption_threshold,
    prefill_max_requests=self.server_args.prefill_max_requests,
    prefill_delayer_single_pass=prefill_delayer_single_pass,
    dllm_config=self.dllm_config,
)

源码位置：Scheduler._get_new_batch_prefill_raw^[13]。之后 scheduler 会对 waiting queue 做主循环，在每个请求进入 adder.add_one_req() 前调用 req.init_next_round_input(self.tree_cache)。

1
2
3
4
5
6
7
8
9
10
11
12
13

for req in self.waiting_queue:
    if self.enable_hicache_storage:
        prefetch_done = self.tree_cache.check_prefetch_progress(req.rid)
        if not prefetch_done:
            continue
        req.storage_hit_length = self.tree_cache.pop_prefetch_loaded_tokens(req.rid)

    req.init_next_round_input(self.tree_cache)
    res = adder.add_one_req(
        req,
        has_chunked_req=(self.chunked_req is not None),
        truncation_align_size=self.truncation_align_size,
    )

这段代码把普通 GPU resident prefix cache 和 HiCache 这类层级缓存扩展放在同一个调度入口前后。SGLang 把 host/storage 命中的加载进度也纳入 scheduler，复用条件不只限于显存命中。v0.5.9 的基础 RadixCache.match_prefix() 仍然返回 device 命中，但 BasePrefixCache.MatchResult 已经包含 last_host_node、host_hit_length 这类字段，为层级 KV cache 留了统一接口。SGLang 官方文档里的 HiCache 页面^[5] 也把这个方向作为高级功能单独展开。

当 can_run_list 非空后，scheduler 创建 ScheduleBatch 并调用 prepare_for_extend()。这一步把命中的 prefix 转成 batch 里的 suffix 输入。

1
2
3
4
5
6
7
8
9
10
11
12

new_batch = ScheduleBatch.init_new(
    can_run_list,
    self.req_to_token_pool,
    self.token_to_kv_pool_allocator,
    self.tree_cache,
    self.model_config,
    self.enable_overlap,
    self.spec_algorithm,
    chunked_req=self.chunked_req,
)

new_batch.prepare_for_extend()

8. ScheduleBatch 把 prefix_indices 变成 forward 输入

在 prepare_for_extend() 里，SGLang 对每个请求做了一个很关键的切片：

1
2
3
4
5

input_ids = [r.fill_ids[len(r.prefix_indices) :] for r in reqs]
extend_num_tokens = sum(len(ids) for ids in input_ids)
seq_lens = [len(r.fill_ids) for r in reqs]
prefix_lens = [len(r.prefix_indices) for r in reqs]
extend_lens = [r.extend_input_len for r in reqs]

源码位置：ScheduleBatch.prepare_for_extend^[14]。这四行是 RadixAttention 在 batch 构造层面的落点。

fill_ids 表示这轮请求需要覆盖的完整 token 序列，prefix_indices 表示已有 KV cache 的 token 索引。于是本轮送进模型的 input_ids 是从 len(prefix_indices) 之后开始的 suffix。与此同时，prefix_lens 会传到后续 model worker batch，让 attention backend 知道每条序列已有多长的 prefix。

这一段可以想成快递分拣：fill_ids 是整张订单，prefix_indices 是仓库里已经打包好的前半箱，input_ids 只剩还没打包的后半箱。prepare_for_extend() 直接把本轮要处理的货量缩小，只把 suffix 交给 extend forward。这个比喻的边界也很清楚：缓存保存的是这些 token 对应的 KV cache 位置，不是 token 文本。

后面 alloc_for_extend(self) 会按 extend_num_tokens 分配本轮新 token 的 KV cache 位置。也就是说，prefix cache 不只是省 attention 计算，它还改变 KV cache allocator 看到的需求规模。

同一个函数还会更新请求级统计字段：

1
2
3
4
5
6
7
8
9
10
11
12
13

new_cached = pre_len - req.already_computed
req.cached_tokens += new_cached

if not req._cache_breakdown_computed:
    host_total = req.host_hit_length
    storage_portion = min(host_total, req.storage_hit_length)
    host_portion = host_total - storage_portion
    device_portion = max(0, len(req.prefix_indices) - host_total)

    req.cached_tokens_device = device_portion
    req.cached_tokens_host = host_portion
    req.cached_tokens_storage = storage_portion
    req._cache_breakdown_computed = True

这说明 SGLang 不只是做内部优化，还把缓存命中拆成 device、host、storage 三类统计。对生产 serving 来说，这类指标很重要。没有它，大家只能看到吞吐变快或变慢，却不知道是 GPU prefix 命中、host cache 命中、storage prefetch，还是调度排序改变了请求形态。

9. 请求结束后缓存插回树，重复部分释放

请求完成后，cache_finished_req() 会把已提交的 KV cache 插回 radix tree。容易漏掉的内存管理细节在重复前缀上：如果新请求的前缀已经在 tree 里存在，那么插入返回的 prefix_len 表示重复部分长度，SGLang 会释放当前请求中重复那段 KV index，只保留新增的 cache。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def cache_finished_req(self, req: Req, is_insert: bool = True):
    kv_committed_len = req.pop_committed_kv_cache()
    token_ids = (req.origin_input_ids + req.output_ids)[:kv_committed_len]
    kv_indices = self.req_to_token_pool.req_to_token[
        req.req_pool_idx, : len(token_ids)
    ]

    keys = convert_to_bigram_key(token_ids) if self.is_eagle else token_ids
    keys = self._page_align_keys(keys)
    values = kv_indices[: len(keys)].to(dtype=torch.int64, copy=True)
    radix_key = RadixKey(keys, req.extra_key, is_bigram=self.is_eagle)

    if is_insert:
        result = self.insert(InsertParams(key=radix_key, value=values, priority=priority))
        new_prefix_len = result.prefix_len
        self.token_to_kv_pool_allocator.free(
            kv_indices[req.cache_protected_len : new_prefix_len]
        )

    self.token_to_kv_pool_allocator.free(kv_indices[len(keys) :])
    self.dec_lock_ref(req.last_node)

源码位置：RadixCache.cache_finished_req^[15]。这段代码把三个动作放在一起：把请求结果变成可复用缓存，释放重复 KV cache，释放请求对旧命中节点的 lock。

insert() 的内部也体现了 radix tree 的压缩特性。它一路比较 key，如果公共前缀停在节点中间就 split，如果剩余 key 非空就新建节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

while len(key) > 0 and child_key in node.children.keys():
    node = node.children[child_key]
    node.last_access_time = access_time
    prefix_len = self.key_match_fn(node.key, key)
    total_prefix_length += prefix_len
    key = key[prefix_len:]
    value = value[prefix_len:]

    if prefix_len < len(node.key):
        new_node = self._split_node(node.key, node, prefix_len)
        new_node.priority = max(new_node.priority, priority)
        node = new_node
    else:
        node.priority = max(node.priority, priority)

if len(key):
    new_node = TreeNode(priority=priority)
    new_node.parent = node
    new_node.key = key
    new_node.value = value.clone()
    node.children[child_key] = new_node
    self.evictable_size_ += len(key)

源码位置：RadixCache._insert_helper^[16]。这段实现没有复杂的外部索引，树本身就是 key 到 KV cache index 的索引。它的代价是每次插入和匹配都要维护 node split、访问时间、lock ref、evictable leaf 等状态。SGLang 选择把这些状态集中在 RadixCache 内，避免它们散落在 scheduler、allocator 和 backend 里。

10. 显存不够时只驱逐没有 lock 的叶子

缓存系统如果只会插入，不会驱逐，很快就会变成内存泄漏。SGLang 的 RadixCache 维护 evictable_leaves，并通过 lock_ref 区分正在被请求引用的节点和可以被释放的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def evict(self, params: EvictParams) -> EvictResult:
    num_tokens = params.num_tokens
    leaves = list(self.evictable_leaves)
    eviction_heap = [
        (self.eviction_strategy.get_priority(node), node) for node in leaves
    ]
    heapq.heapify(eviction_heap)

    num_evicted = 0
    while num_evicted < num_tokens and len(eviction_heap):
        _priority, x = heapq.heappop(eviction_heap)

        self.token_to_kv_pool_allocator.free(x.value)
        num_evicted += len(x.value)
        self._delete_leaf(x)

        if len(x.parent.children) == 0 and x.parent.lock_ref == 0:
            new_priority = self.eviction_strategy.get_priority(x.parent)
            heapq.heappush(eviction_heap, (new_priority, x.parent))

    return EvictResult(num_tokens_evicted=num_evicted)

源码位置：RadixCache.evict^[17]。

这里的策略是“从叶子往上删”。如果删掉一个叶子以后，父节点也变成没有子节点且没有 lock，就把父节点重新放回候选堆。这符合 radix tree 的共享语义：中间节点往往代表多个请求共享的公共前缀，不能随便删；叶子更可能是某条分支独有的后缀。

驱逐叶子可以类比成修剪树枝：先剪掉没有人正在使用的末端枝条，不能一上来砍树干。树干往往代表许多请求共享的公共 prompt，一刀砍掉会让多个后续请求都失去复用机会；叶子更像某次对话独有的后缀，收益小、风险低。源码里的 lock_ref 就是“这段枝条上还有人站着”的标记，有人站着就不能剪。

inc_lock_ref() 和 dec_lock_ref() 负责在请求使用某个命中节点时保护沿途节点。一个节点从 lock_ref == 0 变成被引用时，会从 evictable size 转到 protected size；引用释放后再转回可驱逐集合。

prefix cache 和 serving scheduler 在这里耦合起来。scheduler 决定哪个请求进入 batch，进入 batch 的请求必须保护自己的 prefix 节点；请求完成或被释放时，cache 才能重新参与驱逐。

11. 和 vLLM 的差异：SGLang 多了一层程序前缀视角

SGLang 官方博客明确提到 RadixAttention compatible with continuous batching and paged attention，并把 KV cache tensor 存在 paged layout 里，原文在 Backend: Automatic KV Cache Reuse with RadixAttention 一节^[3]。从源码看，SGLang 在分页 KV cache 之上加了一层按 token sequence 组织的 runtime index。

vLLM 的 PagedAttention 更像把显存页变成可调度资源，主要处理 block table、allocation、preemption 和 continuous batching。SGLang 的 RadixAttention 则额外关心“不同请求之间的 token 前缀关系”。这两个问题并不冲突：底层仍要高效管理 KV cache 页，上层还要判断哪些页可以被多个请求共享。

PagedAttention 让 KV cache 不必连续，RadixAttention 让 KV cache 不必只属于单个请求。前者解决物理布局，后者解决跨请求复用。SGLang 的代码把这两个问题接在一起：RadixCache 只保存 KV index，KV tensor 仍在 memory pool 和 allocator 管理之下。

12. 这套设计的代价

RadixAttention 的好处很明显：复杂 LLM 程序里的重复 prompt 片段可以自动复用，用户不需要手动声明哪些 prompt 可以共享。SGLang 官方博客举了 few-shot、self-consistency、multi-turn chat、tree-of-thought 等模式，这些模式也是最适合 prefix cache 的负载^[3]。但源码也能看到几个代价。

调度不再只是 FCFS。cache-aware policy 会为了命中率改变 waiting queue 顺序。这通常能提升吞吐，但也会让请求延迟的分布更复杂，所以代码里仍保留 FCFS、LOF、RANDOM、routing-key、priority scheduling 等多种策略。

lookup 可能修改树。match_prefix() 会 split node，这让后续命中更准，但意味着缓存读路径也要维护结构一致性。并发和多 worker 场景下，这类状态必须被严格限定在 scheduler 管理范围内。

缓存命中需要和 page size 对齐。语义上的最长公共 token 前缀不一定等于可复用的 KV page 前缀。源码中 _page_align_keys() 和 page_aligned_len 就是在处理这个边界。

prefix cache 对不同 workload 的收益不均匀。如果请求之间几乎没有共享前缀，RadixCache 仍有 match、排序、维护访问时间的成本。SGLang 官方博客提到其 ablation 显示无 cache hit 时没有明显 overhead，但在真实业务里，cache-aware 调度是否值得打开，仍然要看请求形态和指标。

13. 可迁移判断清单

• • 缓存要进入 runtime 状态，不能停在某个函数里的 memoization。SGLang 的 prefix cache 会影响调度、batch 构造、allocator、统计和 eviction。它是一条系统路径，不只是一个 map。
• • 缓存命中结果要携带可执行信息。match_prefix() 返回 KV indices 和 last node，单独返回长度数字不够后续构造 input_ids、保护节点、释放重复 KV cache。
• • 读路径可以维护索引形态。radix tree 的 split 发生在 match 和 insert 里，这让数据结构随着真实访问逐渐变得适合 workload。
• • 复用必须和隔离一起设计。extra_key、LoRA、cache salt、host/storage 命中拆分，都说明“能共享”不能只看 token 一样，还要看上下文是否允许共享。
• • 好的 serving 代码会把优化收益变成指标。cached_tokens_device、cached_tokens_host、cached_tokens_storage 这类字段看起来琐碎，但它们决定了线上问题能不能解释清楚。

14. AI 协作时可以用它否掉哪些代码

让 AI 生成一个 prefix cache for LLM serving，它很容易写成一个 prompt hash 到 KV tensor 的字典：完全相同 prompt 就复用，不同 prompt 就重算，显存不够就随机删一项。这个版本在 demo 里可能看起来能省一次 prefill，但它没有进入 serving runtime 的真实约束。

读完 SGLang 这部分源码，再看到类似实现，可以用几件事校验它：它是否只做完全匹配，还是能表达部分前缀共享；命中结果是否接进 batch 构造和 KV allocator；正在被请求引用的 prefix 节点是否有 lock ref 和 eviction 边界。如果这些问题答不上来，代码看起来再完整，也很可能只是演示缓存，离可服务真实负载的 runtime 组件还差一层。

15. 参考资料与延伸阅读

• • SGLang 官方仓库：sgl-project/sglang tag v0.5.9^[1]。
• • SGLang 官方文档：SGLang Documentation^[2]。
• • LMSYS 官方博客：Fast and Expressive LLM Inference with RadixAttention and SGLang^[3]。
• • SGLang 论文：SGLang: Efficient Execution of Structured Language Model Programs^[4]。
• • SGLang 源码：python/sglang/srt/mem_cache/radix_cache.py^[6]。
• • SGLang 源码：python/sglang/srt/managers/schedule_policy.py^[7]。
• • SGLang 源码：python/sglang/srt/managers/scheduler.py^[8]。
• • SGLang 源码：python/sglang/srt/managers/schedule_batch.py^[9]。
• • SGLang 文档：HiCache^[5]。

当前文章：第 02 篇《SGLang源码分析：RadixAttention与前缀缓存调度》。
下一篇预告：第 03 篇《llama.cpp源码分析：GGUF、量化与ggml执行图》，继续看本地推理 runtime 如何把模型格式、量化和多后端执行拆开。
更新时间：2026 年 7 月 24 日

引用链接

[1] `sgl-project/sglang`: https://github.com/sgl-project/sglang/tree/v0.5.9
[2] SGLang Docs: https://docs.sglang.io/
[3] LMSYS 官方博客: https://lmsys.org/blog/2024-01-17-sglang/#backend-automatic-kv-cache-reuse-with-radixattention
[4] SGLang: Efficient Execution of Structured Language Model Programs: https://arxiv.org/abs/2312.07104
[5] HiCache 文档: https://docs.sglang.io/docs/advanced_features/hicache.md
[6] `python/sglang/srt/mem_cache/radix_cache.py`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py
[7] `python/sglang/srt/managers/schedule_policy.py`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/schedule_policy.py
[8] `python/sglang/srt/managers/scheduler.py`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/scheduler.py
[9] `python/sglang/srt/managers/schedule_batch.py`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/schedule_batch.py
[10] `RadixCache.match_prefix`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py#L352
[11] `RadixCache._match_prefix_helper`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py#L648
[12] `SchedulePolicy._compute_prefix_matches`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/schedule_policy.py#L169
[13] `Scheduler._get_new_batch_prefill_raw`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/scheduler.py#L1977
[14] `ScheduleBatch.prepare_for_extend`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/managers/schedule_batch.py#L1429
[15] `RadixCache.cache_finished_req`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py#L446
[16] `RadixCache._insert_helper`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py#L698
[17] `RadixCache.evict`: https://github.com/sgl-project/sglang/blob/v0.5.9/python/sglang/srt/mem_cache/radix_cache.py#L565