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)?
下一题: AWQ 激活感知缩放与 Group-Wise INT4 量化 →
💡

实战一句话记忆口诀

公共前缀挂基数树,半路分叉裂边节点,活跃加锁保不被删,闲置叶子按 LRU 清理

📐 核心数学公式与机理推导

PrefillTokens=∣P∣−LCP(P,Tradix)\text{PrefillTokens} = |P| - \mathrm{LCP}(P, \mathcal{T}_{\mathrm{radix}})
### 前缀复用树(Radix Tree)与 LRU 叶子回收
在 Agent 多轮工具调用、共享超长 System Prompt 或 Few-Shot 评测时,请求之间往往共享大量前缀 Token。若每次重新 Prefill 会浪费大量首字延迟(TTFT)。
SGLang 提出 RadixAttention:
1. 最长公共前缀匹配(LCP):沿压缩边逐段匹配已缓存 KV 节点,命中的前缀长度直接跳过 Prefill 计算;
2. 边分裂(Edge Split):当新请求只与已有节点共享前 kk 个 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 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: Continuous Batching 连续批处理调度器返回 Part I 与全部 105 题下一题: AWQ 激活感知缩放与 Group-Wise INT4 量化 →