I7Hard★ LLM Serving 前沿 · SGLang 核心Part I · 推理生成、解码与量化
RadixAttention 前缀树缓存匹配与 LRU 淘汰
用带边压缩的 Radix 树管理系统提示、多轮对话与 Few-Shot 公共 KV 前缀,支持局部切边分裂与引用计数 LRU 淘汰。
⏱️ 时间复杂度:
O(|Prompt|) 前缀匹配与插分边💾 空间复杂度:
O(CachedTokens) 基数树压缩节点🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
class RadixNode:
def __init__(self, tokens=()):
self.tokens = tuple(tokens)
self.children = {} # first_token -> RadixNode
self.parent = None
self.lock_ref = 0 # active running requests holding this prefix
self.last_access = 0
class RadixPrefixCache:
"""Prefix-sharing KV radix tree with ref-count protection and LRU leaf eviction."""
def __init__(self, capacity_tokens: int):
self.root = RadixNode()
self.capacity = capacity_tokens
self.cached_tokens = 0
self.tick = 0
def match_prefix(self, prompt_tokens: list) -> tuple:
self.tick += 1
node = self.root
matched_len = 0
path_nodes = [node]
while matched_len < len(prompt_tokens):
tok = prompt_tokens[matched_len]
if tok not in node.children:
break
child = node.children[tok]
# Compare compressed edge tokens
edge_match = 0
while (edge_match < len(child.tokens) and
matched_len + edge_match < len(prompt_tokens) and
child.tokens[edge_match] =
edge_match += 1
if edge_match < len(child.tokens):
# Partial edge hit stops at matched prefix length
matched_len += edge_match
break
node = child
node.last_access = self.tick
path_nodes.append(node)
matched_len += edge_match
return matched_len, path_nodes
def insert(self, tokens: list) -> RadixNode:
self.tick += 1
node = self.root
idx = 0
while idx < len(tokens):
tok = tokens[idx]
if tok not in node.children:
new_leaf = RadixNode(tokens[idx:])
new_leaf.parent = node
new_leaf.last_access = self.tick
node.children[tok] = new_leaf
self.cached_tokens += len(new_leaf.tokens)
self._evict_if_needed(exclude=new_leaf)
return new_leaf
child = node.children[tok]
k = 0
while k < len(child.tokens) and idx + k < len(tokens) and child.tokens[k] == tokens[idx + k]:
k += 1
if k < len(child.tokens):
# Split compressed edge
mid = RadixNode(child.tokens[:k])
mid.parent = node
mid.lock_ref = child.lock_ref
mid.last_access = self.tick
child.tokens = child.tokens[k:]
child.parent = mid
mid.children[child.tokens[0]] = child
node.children[tok] = mid
node = mid
idx += k
else:
child.last_access = self.tick
node = child
idx += k
return node
def _evict_if_needed(self, exclude=None):
while self.cached_tokens > self.capacity:
leaves = []
stack = [self.root]
while stack:
cur = stack.pop()
if not cur.children and cur is not self.root and cur is not exclude and cur.lock_ref == 0:
leaves.append(cur)
stack.extend(cur.children.values())
if not leaves:
break
victim =
del victim.parent.children[victim.tokens[0]]
self.cached_tokens -= len(victim.tokens)
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: RadixAttention 如何兼顾缓存命中率与调度吞吐(Cache-Aware Scheduling)?
💡
实战一句话记忆口诀
公共前缀挂基数树,半路分叉裂边节点,活跃加锁保不被删,闲置叶子按 LRU 清理
📐 核心数学公式与机理推导
### 前缀复用树(Radix Tree)与 LRU 叶子回收
在 Agent 多轮工具调用、共享超长 System Prompt 或 Few-Shot 评测时,请求之间往往共享大量前缀 Token。若每次重新 Prefill 会浪费大量首字延迟(TTFT)。
SGLang 提出 RadixAttention:
1. 最长公共前缀匹配(LCP):沿压缩边逐段匹配已缓存 KV 节点,命中的前缀长度直接跳过 Prefill 计算;
2. 边分裂(Edge Split):当新请求只与已有节点共享前 个 Token 时,在分叉点裂解出中间节点,原有分支保留物理 KV 映射;
3. 安全 LRU 淘汰:只允许从叶子节点且活跃引用计数 `lock_ref == 0` 的节点中,优先淘汰
在 Agent 多轮工具调用、共享超长 System Prompt 或 Few-Shot 评测时,请求之间往往共享大量前缀 Token。若每次重新 Prefill 会浪费大量首字延迟(TTFT)。
SGLang 提出 RadixAttention:
1. 最长公共前缀匹配(LCP):沿压缩边逐段匹配已缓存 KV 节点,命中的前缀长度直接跳过 Prefill 计算;
2. 边分裂(Edge Split):当新请求只与已有节点共享前 个 Token 时,在分叉点裂解出中间节点,原有分支保留物理 KV 映射;
3. 安全 LRU 淘汰:只允许从叶子节点且活跃引用计数 `lock_ref == 0` 的节点中,优先淘汰
last_access 最久远的分支。🔄 张量维度与形状流转说明
prompt_tokens -> RadixTree LCP 匹配命中的缓存前缀 -> 仅增量计算剩余后缀 KV -> 结束或超容时对无锁叶子节点按 LRU 淘汰
🛡️ 数值稳定性自检与边界要点
- 正在执行前向的请求必须锁定整条前缀路径的
lock_ref > 0,绝不能在计算途中被后台 LRU 淘汰 - 注意部分边命中(edge_match < len(child.tokens))时,不能直接删除子节点;插入新分支时需原地做 Edge Split
💻 完整参考代码实现
class RadixNode:
def __init__(self, tokens=()):
self.tokens = tuple(tokens)
self.children = {} # first_token -> RadixNode
self.parent = None
self.lock_ref = 0 # active running requests holding this prefix
self.last_access = 0
class RadixPrefixCache:
"""Prefix-sharing KV radix tree with ref-count protection and LRU leaf eviction."""
def __init__(self, capacity_tokens: int):
self.root = RadixNode()
self.capacity = capacity_tokens
self.cached_tokens = 0
self.tick = 0
def match_prefix(self, prompt_tokens: list) -> tuple:
self.tick += 1
node = self.root
matched_len = 0
path_nodes = [node]
while matched_len < len(prompt_tokens):
tok = prompt_tokens[matched_len]
if tok not in node.children:
break
child = node.children[tok]
# Compare compressed edge tokens
edge_match = 0
while (edge_match < len(child.tokens) and
matched_len + edge_match < len(prompt_tokens) and
child.tokens[edge_match] == prompt_tokens[matched_len + edge_match]):
edge_match += 1
if edge_match < len(child.tokens):
# Partial edge hit stops at matched prefix length
matched_len += edge_match
break
node = child
node.last_access = self.tick
path_nodes.append(node)
matched_len += edge_match
return matched_len, path_nodes
def insert(self, tokens: list) -> RadixNode:
self.tick += 1
node = self.root
idx = 0
while idx < len(tokens):
tok = tokens[idx]
if tok not in node.children:
new_leaf = RadixNode(tokens[idx:])
new_leaf.parent = node
new_leaf.last_access = self.tick
node.children[tok] = new_leaf
self.cached_tokens += len(new_leaf.tokens)
self._evict_if_needed(exclude=new_leaf)
return new_leaf
child = node.children[tok]
k = 0
while k < len(child.tokens) and idx + k < len(tokens) and child.tokens[k] == tokens[idx + k]:
k += 1
if k < len(child.tokens):
# Split compressed edge
mid = RadixNode(child.tokens[:k])
mid.parent = node
mid.lock_ref = child.lock_ref
mid.last_access = self.tick
child.tokens = child.tokens[k:]
child.parent = mid
mid.children[child.tokens[0]] = child
node.children[tok] = mid
node = mid
idx += k
else:
child.last_access = self.tick
node = child
idx += k
return node
def _evict_if_needed(self, exclude=None):
while self.cached_tokens > self.capacity:
leaves = []
stack = [self.root]
while stack:
cur = stack.pop()
if not cur.children and cur is not self.root and cur is not exclude and cur.lock_ref == 0:
leaves.append(cur)
stack.extend(cur.children.values())
if not leaves:
break
victim = min(leaves, key=lambda n: n.last_access)
del victim.parent.children[victim.tokens[0]]
self.cached_tokens -= len(victim.tokens)
🧪 本地测试与正确性断言
可直接复制到本地 Python / Jupyter 验证:
cache = RadixPrefixCache(capacity_tokens=10)
n1 = cache.insert([1, 2, 3, 4, 5, 6])
n1.lock_ref = 1 # 6 tokens pinned by active request
n_idle = cache.insert([10, 11, 12, 13]) # 4 idle tokens
assert cache.cached_tokens == 10
matched, _ = cache.match_prefix([1, 2, 3, 99, 100])
assert matched == 3, f"Expected LCP=3, got {matched}"
# Insert 4 new tokens: idle leaf [10..13] must be evicted while pinned [1..6] survives
n2 = cache.insert([20, 21, 22, 23])
assert cache.cached_tokens <= 10, f"Eviction must enforce capacity budget, got {cache.cached_tokens}"
matched_pinned, _ = cache.match_prefix([1, 2, 3, 4, 5, 6])
assert matched_pinned == 6, "Pinned active prefix must not be evicted"
matched_evicted, _ = cache.match_prefix([10, 11, 12, 13])
assert matched_evicted == 0, "Unpinned LRU leaf must be evicted"
print("✓ RadixAttention prefix tree cache assertion passed")🎯 核心工程追问与标准应答
Q1:RadixAttention 如何兼顾缓存命中率与调度吞吐(Cache-Aware Scheduling)?
如果按单纯 FIFO 队列随机分派请求,同一系统前缀的请求可能触发反复淘汰与重算。SGLang 调度器在准入等待队列时,会按“最长已缓存前缀匹配度”对等待请求重排,优先连续跑命中同一子树前缀的请求,最大化 KV 复用率。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!