SGLang 内幕：RadixAttention、超售调度与期货流水线的源码深读

vLLM 的招牌是 PagedAttention，SGLang 的招牌是 RadixAttention——但如果你打开 SGLang 的源码，会发现 radix_cache.py 里没有一行 CUDA，它本质上是一个给显存记账的前缀树。真正让 SGLang 快的，是三本互相咬合的账：前缀树的复用账、调度器的超售账、FutureMap 的期货账。这篇把三本账的源码逐页翻给你看。

本文所有结论来自 SGLang 主干源码 commit b20c375（2026-08-11 合入，克隆于 2026-08-12） 的静态阅读，函数名、默认常量、环境变量均照抄原文；行号会随版本漂移，函数名可长期检索。这是《LiteLLM 路由内幕》之后源码深读系列的第二篇：那篇看网关层怎么”选哪台机器”，这篇下潜一层，看推理引擎拿到请求后怎么”榨干这台机器”。

阅读地基：如果你还没有 KV cache 的直觉，先看《KV Cache 的显存账》；PagedAttention 的分页思想在《从 Attention 到 PagedAttention》；把推理引擎当操作系统看的心智模型在《LLM 推理即操作系统》——SGLang 是这三篇概念的一个工业级具象。

全景：三个进程、两级页表、三本账

进程拓扑

SGLang 服务端（sglang.srt，Serving RunTime）不是单进程。entrypoints/engine.py 的 _launch_subprocesses 用 multiprocessing 拉起三段流水线，进程间走 ZMQ：

1. TokenizerManager（入口进程）：文本 → token ids，转发请求；
2. Scheduler（每个 TP rank 一个独立进程，run_scheduler_process）：本文主角，持有 event_loop，管批组装、显存、radix tree、GPU forward；
3. DetokenizerManager（独立进程，run_detokenizer_process）：token → 增量文本，流式回传给 TokenizerManager。

把 tokenize/detokenize 从调度进程剥出去，是因为它们是纯 CPU 串行工作，放在调度循环里会偷走 GPU 的喂食时间——这个动机在下文”期货流水线”一节会反复出现。

两级页表

Scheduler 进程里管显存的是两个池子（mem_cache/memory_pool.py 与 mem_cache/allocator/token.py）：

• ReqToTokenPool：一张 (max_requests+1, max_context_len) 的 int32 矩阵 req_to_token，第 r 行第 i 列 = 请求 r 的第 i 个 token 的 KV 存在哪个槽位。多出来的第 0 行是 CUDA Graph padding 的垃圾桶：被 padding 的假请求默认 req_pool_idx=0，读写都落在这行，无害。
• TokenToKVPoolAllocator：管理槽位的自由链表 free_pages = arange(1, size+1)（0 号槽同样留给 padding 写垃圾），槽位指向每层真正的 K/V 张量。

这就是一张两级页表：请求号 → 槽位号 → 物理 K/V。和 vLLM（PagedAttention, arXiv:2309.06180）的 block table 同构，但 SGLang 的默认页大小是 page_size=1（arg_groups/overrides.py 的 _page_size_default，仅 MUSA 平台和 ROCm 的 vectorized_5d 布局默认 64）——token 粒度的页表让前缀可以精确到单个 token 复用，代价是索引更长。页表解决”KV 放哪”，接下来三本账解决”怎么不浪费”。

三本账（本文主线）

浪费形态	数据结构	源码位置
算力浪费：跨请求重复 prefill 相同前缀	RadixCache 前缀树	mem_cache/radix_cache.py
显存浪费：按 max_new_tokens 足额预留但多数请求提前结束	new_token_ratio 超售账本	managers/schedule_policy.py + scheduler_components/new_token_ratio_tracker.py
时间浪费：CPU 调度与 GPU 计算互相等待	FutureMap 期货账本	managers/overlap_utils.py

第一幕 · RadixCache：把别人算过的 prefill 变成你的免费午餐

为什么是 radix tree 而不是哈希表

SGLang 论文（arXiv:2312.07104，NeurIPS 2024）里 RadixAttention 的核心主张：请求结束后不丢 KV cache，把它按 token 序列组织进一棵 radix tree（压缩前缀树），后来的请求做最长前缀匹配，命中多少就少算多少。哈希表只能匹配”完全相同的键”，radix tree 能匹配”任意长度的公共前缀”——而 LLM 负载里的共享恰恰是前缀形态的：系统提示词、few-shot 例子、多轮对话的历史、self-consistency 的公共题干。

省多少？拿多轮对话手算一笔（我自己设的场景，算式可复现）：系统提示 1000 token，5 轮对话每轮用户 100 token、助手回 300 token。无前缀缓存时每轮都要 prefill 全部历史，5 轮合计 9500 个 token 的 prefill；有 radix cache 时每轮只 prefill 新增的 100 token，合计 500——19 倍的算力差距。这就是”免费午餐”的规模。

树长什么样：TreeNode 与 RadixKey

树节点 TreeNode 的关键字段（radix_cache.py）：

• key: RadixKey——这段边上的 token 序列；value: torch.Tensor——对应的 KV 槽位索引（就是两级页表里的槽位号）；
• lock_ref——引用计数，>0 表示有在飞请求正依赖这段前缀，不可驱逐；
• last_access_time / creation_time / hit_count / priority——四个驱逐策略原料；
• host_value / hash_value——分层缓存（HiRadixCache，KV 下沉到 CPU 内存/磁盘）的钩子，本文不展开。

RadixKey 比”token 数组”多两个心眼：

1. extra_key 命名空间：LoRA adapter ID、cache salt 等会拼进键里。两条 token 序列相同但 LoRA 不同的请求故意不共享前缀——KV 是被 adapter 权重污染过的，混用会出错。源码 docstring 把这类场景列得很全：不同采样盐、缓存版本、检索增强上下文。
2. is_bigram 模式：给 EAGLE 类投机解码用（EAGLE, arXiv:2401.15077；投机解码入门见《Medusa 深读》）。草稿模型的 KV 与 (t_i, t_{i+1}) 二元组对齐，N 个 token 只有 N-1 份 KV。实现上不物化二元组列表，只翻一个布尔标志位（maybe_to_bigram_view，注释明写 O(1)），迭代器按需产出相邻对。

匹配为什么快：疾驰 + 二分，370 倍

最长前缀匹配的朴素写法是逐 token 比较——Python 循环在万级 token 的共享前缀上是灾难。RadixKey.match 用了指数疾驰（galloping）+ 二分：先用 1、2、4、8……倍增的窗口做切片比较（t0[lo:hi] != t1[lo:hi] 是 C 层面的一次比较，不进 Python 循环），撞到第一个不等的窗口后，在窗口内二分定位分叉点。

我用源码同款算法验算：两条序列共享 10000 token 前缀，逐 token 要 10001 次比较，疾驰+二分只要 27 次切片比较（14 次疾驰 + 13 次二分）——约 370 倍的操作数差距。这是”长共享前缀”负载下匹配开销可以忽略的原因。

树的三种手术：分裂、插入去重、锁引用

分裂（_split_node）：匹配终止在某条边的中间时（比如树里存着 [1,2,3,4,5]，新请求是 [1,2,3,9]），把这条边一分为二，公共段成为新的父节点。分裂只拷贝索引张量，不动 KV 本体。

插入即去重（cache_finished_req / cache_unfinished_req）：请求结束（或 chunked prefill 每段结束）时把自己的 KV 索引插进树。微妙之处：insert 返回 prefix_len——树里已经有的前缀长度。如果两条同前缀请求并发各算了一份 KV，后插的那份重复段会被立刻 free_segments 释放，然后 cache_unfinished_req 重新 match_prefix、把请求自己的 req_to_token 行改写指向共享段。写入的同时完成去重，显存里同一前缀永远只有一份。

锁引用（inc_lock_ref / dec_lock_ref）：从节点走到根，路径上每个节点 lock_ref±1，并把节点大小在两本尺寸账（evictable_size_ / protected_size_）之间搬运。调度器看到的”可用显存”永远是 available + evictable——被锁的前缀不算。

驱逐：策略可插拔的堆

显存吃紧时 evict(num_tokens) 干活：把所有可驱逐叶子（evictable_leaves 集合，无锁、无未驱逐子节点）按策略打分建最小堆，逐个弹出、释放 KV 槽位、删叶子；父节点变成裸叶子后再入堆。只从叶子剪，保证树永远是”完整前缀”的形态。

策略在 evict_policy.py，全部是给 TreeNode 打分的一行函数：

策略	打分	语义
LRU（默认）	last_access_time	最久没用先走
LFU	(hit_count, last_access_time)	命中少先走
SLRU	(是否进保护段, last_access_time)	命中 ≥2 次进保护段，试用段先走
Priority	(priority, last_access_time)	低优先级先走
FIFO / FILO / MRU	±creation_time / -last_access_time	实验用

--radix-eviction-policy 默认 lru。一个防自嗨细节：chunked prefill 的请求分多段插树，_inc_hit_count 对 chunked 插入跳过计数——否则一条长请求自己给自己刷 hit_count，LFU 就被污染了。

第二幕 · 调度策略：谁先上车

event_loop 每一圈调 get_next_batch_to_run（scheduler.py），它做三件事：把上一圈的 prefill 批合并进 running_batch、尝试组装新 prefill 批、组不出来就跑 decode。prefill 优先——新请求尽快进场能提高批规模，也让它的前缀尽快进树被后来者复用。

组 prefill 批之前先给 waiting_queue 排序（SchedulePolicy.calc_priority，schedule_policy.py）：

• fcfs（当前默认值，server_args.py 的 schedule_policy 字段）：先来先服务；
• lpm（longest prefix match，论文里的 cache-aware 调度）：对每个等待请求跑一次 match_prefix，按命中长度降序——命中多的先上车，因为它们”便宜”；防饿死的边界是队列长于 128 时自动退化为 FCFS（_determine_active_policy，注释直言前缀匹配+排序太贵）；
• dfs-weight / lof / random / priority / routing-key：按树的 DFS 权重 / 按最长输出 / 随机 / 按请求优先级 / 按路由键在运行批中的频率。

队内去重是 LPM 里最聪明的一小段（_compute_prefix_matches）：同一波进来 50 条共享长前缀的请求（比如批量评测），第一条对树的命中是 0，剩下 49 条彼此相似但树里也还没有。SGLang 维护一棵模拟 radix tree（waiting_queue_radix_tree，只存 token 不存 KV）：对树命中 ≤32 token（IN_BATCH_PREFIX_CACHING_CHECK_THRESHOLD）的请求再对模拟树匹配一次，若和队友的共享前缀 ≥32 token（IN_BATCH_PREFIX_CACHING_DEPRIORITIZE_THRESHOLD），就临时降权（排序键直接设 float("inf")）。效果：50 条里只放 1 条代表先上车，等它把前缀算进真树，其余 49 条下一波全程命中。故意的不公平换来全局的少算。

第三幕 · PrefillAdder：显存超售的审批柜台

排好序的请求逐个过 PrefillAdder.add_one_req 审批。这里藏着 SGLang 调度最有味道的设计——像航空公司一样超售显存。

超售比：new_token_ratio

一个请求声称 max_new_tokens=4096，审批时该给它预留多少 decode 显存？足额预留最安全，但绝大多数请求提前遇到 EOS，足额意味着显存大量空置、批规模上不去。SGLang 的答案（new_token_ratio_tracker.py，默认值都在 environ.py）：

$\text{预留} = \text{max\_new\_tokens} \times \text{new\_token\_ratio}$

• 初始比率 SGLANG_INIT_NEW_TOKEN_RATIO = 0.7（乘以 --schedule-conservativeness，默认 1.0）；
• 每平安度过一步 decode，比率线性衰减 (0.7 − 0.098)/600 ≈ 0.001（decay_step），最低到 0.7 × 0.14 = 0.098；
• 一旦发生撤退（下一幕），比率按公式跳回保守值。

手算感受一下（脚本验算过）：max_new_tokens=4096 的请求，初始预留 0.7 × 4096 ≈ 2867 token；引擎连续平稳运行 600 步后，同样的请求只预留 0.098 × 4096 ≈ 401 token——7 倍的口径差。系统越”没出过事”，审批越激进，批越大。另外估算还有个截断：CLIP_MAX_NEW_TOKENS = 4096（环境变量可调），声称要生成十万 token 的请求在估算里只按 4096 算，防止一条贪婪声明吓退整个批——注意只截估算，不截真实生成。

审批的门

add_one_req 的预算检查用的余额是 rem_total_tokens = 可用槽位 + 可驱逐树节点 − 在飞请求的预留和——树里没上锁的部分被当作”可透支的存款”。通过后有个二次确认：_lock_node 上下文管理器先把命中前缀锁住（防止审批过程中被驱逐），锁完再查一遍余额（注释：self.rem_total_tokens may decrease after the lock acquisition）。

chunked prefill：长请求切片进场

一条 100K token 的 prefill 会把整张 GPU 独占几秒，期间所有 decode 停摆。SGLang 默认启用 chunked prefill（思想源自 SARATHI, arXiv:2308.16369）：预算里的 rem_chunk_tokens（--chunked-prefill-size）限制单批 prefill 量，超长请求被截断成 new_chunked_req，下一圈优先续传（add_chunked_req 排在所有新请求之前）。配合 is_mixed_chunk 选项还能把 running_batch 的 decode 混进 prefill 批（mix_with_running）——正是 SARATHI 的 decode-maximal batching：prefill 吃满算力，decode 顺风车搭走。

第四幕 · 撤退：超售翻车后的乘客降舱

超售总有翻车的一天：decode 批的下一步需要 N 个新槽位，池子不够了。update_running_batch 的处理链（scheduler.py）：

1. check_decode_mem：先驱逐树里可驱逐的节点补缺口，够了就继续——牺牲缓存保在飞请求；
2. 还不够，retract_decode（schedule_batch.py）开始”降舱”：按 (len(output_ids), -len(origin_input_ids)) 排序，已生成最少、输入最长的请求先被撤退——沉没成本最小（重算 decode 步数少），释放显存最多（输入长）。server_args.py 对 retraction_policy="length" 的帮助文本原话就是 “retracts short-output, long-input requests first”；
3. 被撤退的请求释放显存（注释明说不插树——“we need the space instantly”），回到 waiting_queue 队首待重跑；至少保留一条请求，如果连最后一条都放不下，优雅 abort 而不是崩掉调度器；
4. 撤退后 new_token_ratio 跳回保守值：(已生成总数 + 20×请求数) / (max_new 总和 + 1)（SGLANG_RETRACT_DECODE_STEPS=20，语义是”至少再撑 20 步 decode”）。跳完从头开始衰减。

这是一个完整的负反馈回路：激进 → 翻车 → 保守 → 缓慢再激进。和 TCP 拥塞控制的 AIMD 形态神似（此为我的类比，非源码注释）：线性降压（decay_step 是加性的），乘性回撤（撤退后比率断崖式回跳）。

第五幕 · 期货流水线：CPU 和 GPU 不再互等

问题：一半时间在等 CPU

朴素事件循环（event_loop_normal，源码里保留着）是串行的：收请求 → 组批 → GPU forward → 等结果 → 处理结果 → 下一圈。GPU 算的时候 CPU 闲着，CPU 组批/detokenize/插树的时候 GPU 闲着。官方 v0.4 博客称未优化的引擎最多一半时间耗在 CPU 上，且明说重叠调度的想法来自 NanoFlow（arXiv:2408.12757）。

解法：晚一拍处理 + 期货 token

event_loop_overlap（当前默认）把循环改成流水线：

sequenceDiagram
    participant CPU as CPU 调度流
    participant FM as FutureMap
    participant GPU as GPU forward 流
    Note over CPU: 迭代 N 开始
    CPU->>GPU: 提交批 N 的 forward
    Note over GPU: 批 N 计算中
    CPU->>CPU: 处理批 N-1 的结果<br>树插入与流式输出
    CPU->>CPU: 组装批 N+1<br>decode 输入填期货引用
    GPU->>FM: 批 N 采样结果写入<br>output_tokens_buf
    Note over GPU: 批 N+1 forward 开头<br>gather 期货成真实 token

CPU 提交批 N 后不等结果，把 (batch, result) 塞进 result_queue，转头处理批 N−1 的结果、组装批 N+1。但这有个死结：组装批 N+1 的 decode 输入需要批 N 采样出的 token，而批 N 还没算完。

解结的是 FutureMap（overlap_utils.py）——一个按 req_pool_idx 索引的 GPU 常驻账本 output_tokens_buf。CPU 组批时不填真 token，填的是”期货引用”；批 N 的采样核在 GPU 上直接把结果写进账本对应行；批 N+1 的 forward 入口处（resolve_forward_inputs）在 GPU 流上 gather 一把，期货交割成真实 token：

batch.input_ids = future_map.output_tokens_buf[batch.req_pool_indices]

整条依赖链在 GPU 流内部闭合，CPU 全程不碰 token 值、不做同步。CI 模式下账本用 −1 毒化初始化 + 融合断言核（_assert_nonneg_and_invalidate），抓”没写先读”的时序 bug。

两处刻意关掉重叠的地方值得记：连续两个 prefill 批之间可关重叠（环境变量 SGLANG_DISABLE_CONSECUTIVE_PREFILL_OVERLAP，牺牲一点吞吐换第一批的 TTFT）；带语法约束的 decode 需要在下一批的位掩码生成前同步推进 FSM 状态（need_grammar_sync）——引出最后一幕。

第六幕 · 约束解码：语法怎么挤进流水线

SGLang 默认语法后端是 xgrammar（_handle_grammar_backend；XGrammar, arXiv:2411.15100）。约束解码的位置在采样前：语法对象按当前 FSM 状态生成 vocab 大小的位掩码（allocate_vocab_mask / fill_vocab_mask / apply_vocab_mask，聚合在 sampling_batch_info.update_regex_vocab_mask），非法 token 的 logit 置 −∞。结构化输出的分层全景见《结构化输出的五层实现》。

两个工程细节：

1. 编译异步化：语法（JSON schema → FSM）编译很贵，请求先进 grammar_manager 的编译队列，调度器每圈开头查”编译好了没”（_get_new_batch_prefill_raw 第一段），编译完成的请求才回到 waiting_queue。编译不阻塞调度循环。
2. 与重叠调度的咬合：FSM 推进依赖上一步实际采样的 token，而重叠模式下结果处理是滞后的。_advance_pending_grammar 做”语法屏障”——在生成下一批位掩码之前，把 result_queue 里还没处理的 decode 结果的 FSM 先行推进，让 CPU 的 FSM 推进与 GPU 的 verify forward 重叠。

jump-forward 的现状（诚实标注）：论文的压缩 FSM 招式——当语法从当前状态出发只有唯一路径时（如 JSON 的 {"name": " 这类固定骨架），一次性跳过多个 token 不做 forward——接口仍在源码里（base_grammar_backend.py 的 try_jump_forward / jump_forward_str_state，xgrammar 后端调 matcher.find_jump_forward_string()，outlines_jump_forward.py 还保留着完整的压缩 FSM 实现和 LMSYS 博客引用）。但我在当前主干的调度器路径里没有找到这些接口的调用点（全仓检索 try_jump_forward 只在 constrained/ 目录内部出现）——我的推测（未验证）：重叠调度 + 投机解码时代，跳跃会打乱批内对齐与期货账本，主路径改为纯位掩码，jump-forward 处于接口保留但未接线状态。读者若考证出确切结论，欢迎指正。

尾声 · 一张总表与一条元规律

机制	消灭的浪费	核心数据结构	关键函数	反直觉细节
RadixAttention	跨请求重复 prefill	radix tree（KV 索引缓存）	match_prefix / _split_node / evict	匹配用疾驰+二分，万 token 前缀 27 次比较；插入即去重
缓存感知调度	队列顺序导致的缓存踩踏	模拟 radix tree（只存 token）	calc_priority / _compute_prefix_matches	同前缀队友被故意降权，放一条代表先跑
超售调度	足额预留的显存空置	new_token_ratio 标量账本	add_one_req / budget_state	0.7 起步 600 步衰减到 0.098，7 倍口径差
撤退机制	超售翻车	排序牺牲者名单	retract_decode / check_decode_mem	先驱逐缓存再撤请求；撤退者不插树
重叠调度	CPU-GPU 互等	FutureMap 期货账本	event_loop_overlap / resolve_forward_inputs	期货在 GPU 流内交割，CPU 不碰 token 值
约束解码	非法 token 的采样空间	vocab 位掩码	update_regex_vocab_mask	编译异步化 + 语法屏障与 forward 重叠

元规律（我的提炼，非源码或论文原话）：浪费在哪，数据结构就长在哪。吞吐引擎的每一个核心数据结构，都是为消灭一种特定形态的浪费而生——算力浪费长出前缀树，显存浪费长出超售账本，时延浪费长出期货账本，采样浪费长出位掩码。反过来这也是读任何推理引擎源码的导航图：先问”它在消灭哪种浪费”，再找”为此发明了什么账本”。这与《一把 Key 背后》的元数据分界定律拼成完整图景：只需请求级元数据的优化浮到网关层，要碰 KV/logits 的优化沉到引擎层——本文六个机制全部在引擎侧，因为它们每一个都在直接搬弄 KV 槽位和 logits。

诚实的提醒

• 本文是静态源码阅读，未在 GPU 上运行过 SGLang，也未复现任何官方基准数字（6.4x 吞吐、1.1x 零开销加速等均转述自论文与官方博客，正文已带链接）。
• 主干 commit b20c375 与你安装的发行版可能有差异；SGLang 演进极快（本文读到的调度器已有 5000+ 行，含大量本文略过的 PD 分离、DP attention、Mamba 混合池逻辑）。
• “jump-forward 未接线”是基于全仓检索的推断，可能存在我没找到的动态分发路径。
• 三个手算数字（19x 前缀节省、27 次 vs 10001 次比较、0.7→0.098 超售衰减）全部用脚本验算过，但场景是我构造的，不代表你的负载。

成本最低的亲手验证实验：radix_cache.py 文件末尾自带 __main__ 块，RadixCache.create_simulated() 不需要 GPU——装好 torch 后直接 python -m sglang.srt.mem_cache.radix_cache，就能看到插入 [1,2,3]、[1,2,4,5] 等序列后 pretty_print 打出的树形结构与每个节点的 lock_ref。想再进一步，改这段代码插入两条共享 5000 token 前缀的序列，用 time.perf_counter 对比 match_prefix 与逐 token 循环的耗时，亲手复现疾驰匹配的数量级差距。

参考来源

工程实践

• SGLang GitHub 仓库（本文源码基线 commit b20c375）
• SGLang v0.4：零开销批调度器（LMSYS 官方博客）
• 压缩 FSM 加速约束解码（LMSYS 官方博客，源码注释中引用）

arXiv 论文（均于 2026-08-12 检索核实）

• SGLang: Efficient Execution of Structured Language Model Programs — arXiv:2312.07104（NeurIPS 2024）
• Efficient Memory Management for LLM Serving with PagedAttention — arXiv:2309.06180（SOSP’23）
• NanoFlow: Towards Optimal Large Language Model Serving Throughput — arXiv:2408.12757（OSDI’25，重叠调度思想来源）
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills — arXiv:2308.16369
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty — arXiv:2401.15077
• XGrammar: Flexible and Efficient Structured Generation Engine — arXiv:2411.15100

另：Orca（OSDI’22）提出的 continuous batching 是本文一切调度讨论的前提（每次迭代重组批而非等整批完成），无 arXiv 版本，见 USENIX 会议页。