本文深入剖析大语言模型推理优化中的 RadixAttention 技术详述其基于 Radix Tree基数树自动复用 KV Cache 的核心原理结合 SGLang 的落地实现解析其内存调度机制并与 vLLM 的 APC 方案进行全方位对比为大家在生产环境中提供性能评估与选型参考。1. 引言与背景本章将介绍 LLM 推理中的重复计算问题以及 RadixAttention 提出的解决方案。1.1 LLM 推理中的重复计算问题大语言模型LLM的推理过程分为两个阶段Prefill预填充和Decode解码。在 Prefill 阶段模型需要处理完整的输入序列并生成对应的 KV Cache。根据 [KV Cache 原理简介]中的分析由于 Transformer 的自注意力机制Prefill 阶段的计算复杂度为 其中 为输入序列长度。在实际的 LLM 应用中大量请求存在共享前缀的现象•System Prompt同一应用的所有请求使用相同的系统指令通常 2K-8K tokens。•多轮对话历史对话上下文在后续轮次中反复出现。•Few-shot Examples相同的示例在多个请求中复用。•RAG 场景检索到的文档片段被多个查询复用。根据生产环境的统计数据 [1,3]40%-80% 的 token 序列存在可复用的共享前缀。如果每次请求都从零开始计算这些重复前缀的 KV Cache将造成巨大的计算资源浪费。场景示例客服机器人请求 A: [System Prompt: 8K tokens] [用户问题 A: 256 tokens]请求 B: [System Prompt: 8K tokens] [用户问题 B: 128 tokens]请求 C: [System Prompt: 8K tokens] [用户问题 C: 512 tokens]→ System Prompt 被重复计算 3 次浪费约 95% 的 Prefill 计算量1.2 为什么需要 KV Cache 复用KV Cache 具有一个关键特性确定性。对于相同的输入 token 序列模型总是产生相同的 KKey和 VValue表征。这意味着相同的 token 序列 → 相同的 KV Cache → 只需计算一次后续直接复用这一特性使得 KV Cache 复用成为可能。通过缓存已计算的 KV Cache 并在后续请求中复用我们可以降低 TTFTTime-To-First-Token跳过前缀的 Prefill 计算。提升吞吐量节省的 GPU 算力可服务更多请求。降低成本减少单位请求的计算资源消耗。然而这带来了一个核心的技术挑战如何高效地管理和检索 KV Cache• 缓存的键Key是什么• 如何快速判断新请求是否命中缓存• 如何处理部分前缀匹配的情况• 如何在有限的显存中进行淘汰和替换1.3 现有方案的局限性在 RadixAttention 提出之前常见的 KV Cache 管理方案存在明显局限方案 1简单哈希表:将完整的 token 序列哈希后作为键KV Cache 作为值存入哈希表。# 初始化缓存字典cache {}# 将完整的 token 序列转换为元组后计算哈希值作为键key hash(tuple(token_ids))# 将生成的 KV Cache 存入哈希表cache[key] kv_cache问题无法支持前缀匹配。即使两个请求共享 99% 的前缀只要有一个 token 不同就无法复用任何缓存。方案 2静态前缀缓存:预先定义固定的 System Prompt为其计算并缓存 KV Cache。问题缺乏灵活性无法适应动态工作负载。多轮对话、用户特定上下文等场景无法受益。方案 3逐 Token 查找:将每个 token 的 KV Cache 单独存储按位置索引。问题管理开销巨大无法利用前缀的结构化特性进行高效查找。这些局限性促使 SGLang 团队提出了RadixAttention——一种基于 Radix Tree基数树的 KV Cache 管理方案能够自动、高效地识别和复用任意长度的共享前缀。2. RadixAttention 核心原理RadixAttention 的核心创新在于使用Radix Tree基数树这一数据结构来组织和管理 token 序列与 KV Cache 的映射关系。本章将深入介绍 Radix Tree 的原理及其在 KV Cache 管理中的应用。2.1 Radix Tree 数据结构本节将详细介绍 Radix Tree 数据结构的基本原理、核心特性以及时间复杂度分析。2.1.1 从 Trie 到 Radix TreeTrie前缀树是一种经典的树形数据结构用于高效存储和检索字符串集合。在 Trie 中每个节点代表一个字符从根到叶子的路径表示一个完整的字符串。Trie 存储 [hello, help, world] root / \ h w | | e o | | l r / \ | l p l | | o dTrie 的问题在于当存在长的非分支路径时会产生大量只有单个子节点的中间节点浪费内存且增加遍历深度。Radix Tree基数树也称为压缩前缀树Compressed Trie或Patricia Tree通过路径压缩解决了这一问题。它将连续的、没有分支的节点合并为一个节点存储整个字符串片段而非单个字符。Radix Tree 存储 [hello, help, world] root / \ hel world / \ lo p节点数5Trie 需要 11 个节点2.1.2 Radix Tree 的核心特性与传统 Trie 树相比Radix Tree 具有以下几个核心特性使其非常适合用于管理 KV Cache特性说明路径压缩连续非分支节点合并减少内存和遍历深度前缀共享相同前缀自动合并到同一路径动态更新支持高效的插入、删除和查找最长前缀匹配天然支持找到与查询序列匹配的最长前缀2.1.3 时间复杂度分析设 为查询/插入序列的长度 为字符集大小对于 token 序列 为词表大小操作时间复杂度说明查找与序列长度线性相关与树中总节点数无关插入最坏情况需要分裂现有节点删除可能触发节点合并最长前缀匹配遍历直到无法继续匹配2.2 Token 序列到 KV Cache 的映射在 RadixAttention 中Radix Tree 的每个节点不仅存储 token 序列片段还关联了对应的KV Cache Block。2.2.1 节点结构设计在 RadixAttention 的实现中每个 Radix Tree 节点都需要保存 token 信息以及关联的缓存块索引。以下是节点的典型结构设计class RadixNode: # 存储的 token 序列片段 tokens: List[int] # 对应的 KV Cache Block 列表每个 Block 固定大小如 16 tokens kv_cache_blocks: List[KVCacheBlock] # 子节点映射第一个 token - 子节点 children: Dict[int, RadixNode] # 引用计数当前有多少活跃请求使用此节点 ref_count: int # 最后访问时间用于 LRU 淘汰 last_access_time: float2.2.2 树的构建过程当新的 token 序列需要被缓存时RadixAttention 执行以下步骤从根节点开始匹配逐 token 比较沿着匹配的路径向下遍历处理分歧点• 如果在某个节点内部出现不匹配分裂该节点• 将公共部分保留不同部分创建新的子节点创建新路径对于完全不匹配的后缀创建新的节点链初始状态树中已有序列 hello world插入序列 hello vllm步骤 1: 匹配 hello (6 tokens) ✓步骤 2: 在 world 节点处发现不匹配w vs v步骤 3: 分裂节点创建分支结果 root | hello / \ world vllm2.2.3 前缀共享机制Radix Tree 的结构天然支持前缀共享所有具有相同前缀的序列都会经过相同的节点路径。这意味着• 相同前缀的 KV Cache 只存储一份。• 新序列插入时自动识别并复用已有前缀。• 无需显式的“注册”或“声明”共享关系。请求 A: [System Prompt] [Query A] → 缓存 System Prompt请求 B: [System Prompt] [Query B] → 自动复用 System Prompt 的 KV Cache请求 C: [System Prompt] [Query A] [Response A] [Query C] → 复用 System Prompt Query A 的全部 KV Cache2.3 前缀匹配与查找算法前缀匹配是 RadixAttention 的核心操作决定了能够复用多少已缓存的 KV Cache。本节介绍最长前缀匹配算法及其查找结果的处理方式。2.3.1 最长前缀匹配算法当新请求到达时RadixAttention 需要找到与请求 token 序列匹配的最长前缀以最大化 KV Cache 复用。def match_prefix(root: RadixNode, query_tokens: List[int]) - Tuple[int, List[KVCacheBlock]]: 查找与 query_tokens 匹配的最长前缀 返回(匹配长度, 对应的 KV Cache Block 列表) current root matched_length 0 matched_blocks [] query_pos 0 while query_pos len(query_tokens): # 查找匹配的子节点 first_token query_tokens[query_pos] if first_token not in current.children: break # 无匹配子节点停止 child current.children[first_token] # 在子节点内逐 token 匹配 node_pos 0 while node_pos len(child.tokens) and query_pos len(query_tokens): if child.tokens[node_pos] ! query_tokens[query_pos]: break # 节点内部不匹配停止 node_pos 1 query_pos 1 # 收集匹配的 KV Cache Blocks matched_length query_pos matched_blocks.extend(child.kv_cache_blocks[:node_pos // BLOCK_SIZE]) if node_pos len(child.tokens): break # 节点未完全匹配停止 current child # 继续向下遍历 return matched_length, matched_blocks2.3.2 查找结果的处理前缀匹配的结果决定了推理引擎的后续行为匹配情况处理方式完全匹配直接复用全部 KV Cache跳过 Prefill部分匹配复用匹配部分的 KV Cache仅对未匹配后缀执行 Prefill无匹配从头执行完整 Prefill并将结果缓存查询序列: [T0, T1, T2, T3, T4, T5, T6, T7]树中已有: [T0, T1, T2, T3] → KV Blocks [B0, B1]匹配结果: 长度4, Blocks[B0, B1]Prefill 执行:- 位置 0-3: 跳过计算加载 [B0, B1]- 位置 4-7: 执行 Prefill生成新的 KV Cache2.4 LRU 淘汰策略GPU 显存有限无法无限缓存 KV Cache。RadixAttention 采用LRULeast Recently Used策略进行缓存淘汰。2.4.1 引用计数机制为了避免淘汰正在被使用的 KV Cache每个节点维护一个引用计数• 当请求开始使用某节点的 KV Cache 时ref_count 1• 当请求完成生成结束或被取消时ref_count - 1•只有ref_count 0的节点才能被淘汰def acquire_node(node: RadixNode): 请求开始使用节点 node.ref_count 1 node.last_access_time time.time()def release_node(node: RadixNode): 请求释放节点 node.ref_count - 12.4.2 淘汰算法当显存不足时RadixAttention 从叶子节点开始按最后访问时间排序淘汰最久未使用的节点def evict_lru(root: RadixNode, target_free_blocks: int) - int: 淘汰最久未使用的节点释放指定数量的 KV Cache Blocks 返回实际释放的 Block 数量 freed_blocks 0 # 收集所有可淘汰的叶子节点ref_count 0 evictable_leaves collect_evictable_leaves(root) # 按最后访问时间排序 evictable_leaves.sort(keylambda n: n.last_access_time) for leaf in evictable_leaves: if freed_blocks target_free_blocks: break # 释放 KV Cache Blocks freed_blocks len(leaf.kv_cache_blocks) release_kv_blocks(leaf.kv_cache_blocks) # 从父节点移除 remove_from_parent(leaf) # 如果父节点只剩一个子节点合并路径 merge_single_child_nodes(leaf.parent) return freed_blocks2.4.3 淘汰的级联效应由于 Radix Tree 的前缀共享特性淘汰需要谨慎处理•只能从叶子节点开始淘汰中间节点被淘汰会导致所有后代节点失效。•淘汰后可能触发节点合并父节点只剩一个子节点时可以合并以保持压缩特性。淘汰前 hello / \ world vllm淘汰 vllm 后 hello | world进一步压缩 hello world3. SGLang 中的实现SGLangStructured Generation Language是由 UC Berkeley 团队开发的高效 LLM 推理系统RadixAttention 正是其核心优化技术之一。本章将分析 RadixAttention 在 SGLang 中的具体实现。3.1 SGLang 系统架构简介SGLang 的定位是结构化语言模型程序的高效执行引擎。它支持复杂的控制流如循环、分支、多次生成调用的复合任务并通过 RadixAttention 实现跨调用的 KV Cache 自动复用。SGLang 架构概览┌───────────────────────────────────────────────────────────┐│ SGLang Frontend ││ (Python DSL for structured LLM programs) │└───────────────────────────────────────────────────────────┘ │ ▼┌───────────────────────────────────────────────────────────┐│ SGLang Runtime ││ ┌─────────────┐ ┌─────────────────┐ ┌─────────────┐ ││ │ Scheduler │◄─┤ RadixCache ├─►│ Executor │ ││ │ │ │ (RadixAttention)│ │ │ ││ └─────────────┘ └─────────────────┘ └─────────────┘ │└───────────────────────────────────────────────────────────┘ │ ▼┌───────────────────────────────────────────────────────────┐│ Model Execution Backend ││ (CUDA Kernels, PagedAttention) │└───────────────────────────────────────────────────────────┘RadixAttention 位于 SGLang Runtime 的核心位置负责管理所有缓存的 token 序列与 KV Cache 的映射为每个请求提供前缀匹配查询协调 KV Cache Block 的分配与淘汰3.2 核心数据结构SGLang 中的 RadixAttention 实现涉及三个核心数据结构RadixCache 主类、TreeNode 节点结构以及内存池管理器。3.2.1 RadixCache 类RadixCache是 RadixAttention 的主类封装了 Radix Tree 及其操作class RadixCache: def __init__( self, req_to_token_pool, # Token Pool 管理器 token_to_kv_pool, # KV Cache Pool 管理器 disable: bool False, # 是否禁用缓存 ): self.root_node TreeNode() # Radix Tree 根节点 self.req_to_token_pool req_to_token_pool self.token_to_kv_pool token_to_kv_pool self.disable disable # 统计信息 self.total_cache_hit_tokens 0 self.total_cache_miss_tokens 0 def match_prefix(self, rid: int, key: List[int]) - Tuple[TreeNode, int]: 查找最长匹配前缀 ... def insert(self, node: TreeNode, key: List[int], value: List[int]): 插入新的 token 序列 ... def evict(self, num_tokens: int) - int: LRU 淘汰指定数量的 tokens ...3.2.2 TreeNode 结构每个TreeNode代表 Radix Tree 中的一个节点class TreeNode: def __init__(self): # 子节点映射token_id - TreeNode self.children: Dict[int, TreeNode] {} # 父节点引用 self.parent: Optional[TreeNode] None # 存储的 token 序列压缩后的路径 self.key: List[int] [] # 对应的 KV Cache Block 索引 self.value: List[int] [] # 引用计数 self.lock_ref: int 0 # 最后访问时间 self.last_access_time: float 0.03.2.3 内存池管理SGLang 使用专门的内存池管理 KV Cache Blocks•Token Pool管理 token 序列到物理位置的映射•KV Pool管理实际的 KV Cache 显存分配class TokenToKVPool: def __init__(self, size: int, dtype: torch.dtype): # 预分配的 KV Cache 显存 self.k_buffer torch.empty((size, ...), dtypedtype, devicecuda) self.v_buffer torch.empty((size, ...), dtypedtype, devicecuda) # 空闲 Block 列表 self.free_slots: List[int] list(range(size)) def alloc(self, num_blocks: int) - List[int]: 分配 KV Cache Blocks ... def free(self, block_ids: List[int]): 释放 KV Cache Blocks ...3.3 关键操作实现本节详细分析 RadixCache 的四个关键操作前缀匹配、插入、LRU 淘汰以及并发控制。3.3.1 前缀匹配match_prefix()前缀匹配是系统处理新请求时的首个操作。该方法通过遍历 Radix Tree找到与输入序列匹配的最长前缀路径def match_prefix(self, rid: int, key: List[int]) - Tuple[TreeNode, int]: 查找与 key 匹配的最长前缀 Args: rid: 请求 ID key: 输入的 token 序列 Returns: (last_node, prefix_len): 最后匹配的节点和前缀长度 if self.disable: return self.root_node, 0 current self.root_node prefix_len 0 key_len len(key) while prefix_len key_len: # 查找匹配的子节点 first_token key[prefix_len] if first_token not in current.children: break child current.children[first_token] child_key child.key child_len len(child_key) # 检查子节点的 key 是否完全匹配 match_len 0 while match_len child_len and prefix_len match_len key_len: if child_key[match_len] ! key[prefix_len match_len]: break match_len 1 prefix_len match_len if match_len child_len: # 部分匹配需要在返回前处理 break current child # 更新统计 self.total_cache_hit_tokens prefix_len self.total_cache_miss_tokens key_len - prefix_len return current, prefix_len3.3.2 插入操作insert()当处理完未命中的前缀并生成新的 KV Cache 后系统需要将这些新数据插入到 Radix Tree 中。插入过程可能涉及节点的分裂def insert(self, node: TreeNode, key: List[int], value: List[int]): 从指定节点开始插入新的 token 序列 Args: node: 起始节点通常是 match_prefix 返回的节点 key: 要插入的 token 序列未匹配部分 value: 对应的 KV Cache Block IDs if self.disable or len(key) 0: return current node key_pos 0 while key_pos len(key): first_token key[key_pos] if first_token in current.children: child current.children[first_token] child_key child.key # 找到公共前缀长度 common_len 0 while (common_len len(child_key) and key_pos common_len len(key) and child_key[common_len] key[key_pos common_len]): common_len 1 if common_len len(child_key): # 需要分裂节点 self._split_node(child, common_len) key_pos common_len current child else: # 创建新节点 new_node TreeNode() new_node.key key[key_pos:] new_node.value value[key_pos:] new_node.parent current current.children[first_token] new_node break current.last_access_time time.time()3.3.3 LRU 淘汰evict()当系统显存不足时将触发 LRU 淘汰机制。淘汰操作总是从最久未使用的叶子节点开始以释放 KV Cache 块def evict(self, num_tokens: int) - int: 淘汰至少 num_tokens 个 tokens 的缓存 Returns: 实际淘汰的 tokens 数量 if self.disable: return 0 evicted 0 # 收集所有叶子节点 leaves self._collect_leaves() # 按最后访问时间排序最旧的在前 leaves.sort(keylambda n: n.last_access_time) for leaf in leaves: if evicted num_tokens: break # 跳过被锁定的节点 if leaf.lock_ref 0: continue # 释放 KV Cache evicted len(leaf.value) self.token_to_kv_pool.free(leaf.value) # 从树中移除 self._remove_node(leaf) return evicted3.3.4 并发控制SGLang 使用节点级锁来支持并发访问def inc_lock_ref(self, node: TreeNode): 增加节点的引用计数请求开始使用 delta 0 while node is not None: if node.lock_ref 0: delta 1 node.lock_ref 1 node node.parent return deltadef dec_lock_ref(self, node: TreeNode): 减少节点的引用计数请求结束 delta 0 while node is not None: node.lock_ref - 1 if node.lock_ref 0: delta 1 node node.parent return delta3.4 与 PagedAttention 的集成RadixAttention 与 PagedAttention 紧密集成共同实现高效的 KV Cache 管理Block 粒度对齐RadixCache 中的 value 存储的是 Block ID 而非原始显存地址。统一的内存池KV Cache Blocks 由TokenToKVPool统一管理。Block Table 更新Prefill 完成后Block Table 自动更新以包含新生成的 KV Cache。请求处理流程1. match_prefix(tokens) → (node, prefix_len, block_ids)2. 将 block_ids 加载到 Block Table 的前 prefix_len 位置3. 仅对 tokens[prefix_len:] 执行 Prefill4. 将新生成的 KV Cache 存入新分配的 Blocks5. insert(node, tokens[prefix_len:], new_block_ids)4. vLLM 的 Automatic Prefix Caching (APC) 对比vLLM 从 v0.4.0 开始引入了 **[Automatic Prefix Caching (APC)]功能实现了类似 RadixAttention 的前缀缓存能力但采用了不同的技术方案。本章将对比分析两者的异同。4.1 vLLM 的技术选型Hash Table vs Radix TreevLLM 的 APC 与 SGLang 的 RadixAttention 在功能上相似但在底层数据结构上做出了不同的选择。本节分析 vLLM 选择哈希表的原因及其设计细节。4.1.1 为什么 vLLM 选择 Hash TablevLLM 没有采用 Radix Tree而是选择了基于哈希表的增量哈希链方案。主要考量包括与 Block Manager 的集成vLLM 的 PagedAttention 已经以 Block 为粒度管理 KV Cache哈希表可以直接以 Block Hash 为键。实现复杂度哈希表的实现比 Radix Tree 更简单易于维护。内存开销哈希表的额外内存开销通常低于树结构。4.1.2 增量哈希链设计vLLM 的 APC 使用增量哈希确保前缀依赖def hash_block_tokens( parent_block_hash: Optional[int], curr_block_token_ids: Tuple[int, ...]) - int: 计算 Block 的哈希值 return hash((parent_block_hash, curr_block_token_ids))这种设计保证了• 相同的前缀 → 相同的哈希链• 不同的前缀 → 不同的哈希值即使当前 Block 内容相同4.1.3 缓存查找流程vLLM 的缓存查找过程基于增量哈希链按 Block 粒度逐个匹配一旦遇到未命中的 Block 即可提前终止查找def find_cached_blocks(token_ids: List[int], block_size: int) - List[int]: 查找已缓存的 Blocks cached_blocks [] parent_hash None for i in range(0, len(token_ids), block_size): chunk tuple(token_ids[i:i block_size]) block_hash hash_block_tokens(parent_hash, chunk) if block_hash in block_cache: cached_blocks.append(block_cache[block_hash]) parent_hash block_hash else: break # 一旦未命中后续都无法复用 return cached_blocks4.2 两种方案的对比分析SGLang 的 RadixAttention 与 vLLM 的 APC 在设计理念和数据结构上各有侧重以下是这两种方案在多个维度上的详细对比维度RadixAttention (SGLang)APC (vLLM)数据结构Radix Tree压缩前缀树Hash Table哈希表索引粒度Token 级别Block 级别16-32 tokens查找方式树遍历天然支持最长前缀匹配逐 Block 哈希查找内存开销较高树节点、指针较低仅哈希表条目动态前缀任意位置分支灵活性高需 Block 对齐灵活性稍低实现复杂度较高节点分裂、合并较低标准哈希表操作并发支持需要细粒度锁通过引用计数管理4.2.1 适用场景对比根据两种方案的特性差异它们在不同的业务场景中各有优势。以下是它们的主要适用场景对比RadixAttention 更适合• 高度动态的工作负载前缀频繁变化• 需要细粒度token 级缓存控制的场景• 复杂的结构化生成程序SGLang 的核心用例vLLM APC 更适合• 前缀相对固定的场景如固定 System Prompt• 追求实现简洁性和与现有系统集成• Block 对齐不造成显著浪费的场景4.3 vLLM Router 中的 Radix Tree 应用有趣的是虽然 vLLM 的 KV Cache 管理使用哈希表但其路由组件vLLM Router却使用了 Radix Tree 来实现Cache Aware 路由策略。本节介绍该策略的原理和动态平衡机制。4.3.1 Cache Aware 策略概述在多实例部署场景中如何将请求路由到最可能已缓存其前缀的 Worker 节点是一个关键问题。vLLM Router 的 Cache Aware 策略为每个 Worker 维护一棵近似 Radix Tree追踪该 Worker 上已缓存的请求前缀。新请求到达时计算其与各 Worker Radix Tree 的前缀匹配率。优先将请求路由到匹配率最高的 Worker。Router 中的 Radix Tree 结构Worker A 的 Radix Tree: root - You are a helpful - assistant - for coding - chatbotWorker B 的 Radix Tree: root - You are a helpful - translator - Summarize the - following text新请求: You are a helpful assistant for Python→ 与 Worker A 匹配 You are a helpful assistant更长→ 路由到 Worker A4.3.2 动态平衡机制Cache Aware 策略并非总是选择匹配率最高的 Worker它还会考虑负载均衡def select_worker(request: Request, workers: List[Worker]) - Worker: # 计算各 Worker 的匹配率 match_rates [worker.radix_tree.match_rate(request.tokens) for worker in workers] # 获取当前负载 loads [worker.current_load for worker in workers] # 判断是否需要负载均衡 if max(loads) - min(loads) BALANCE_THRESHOLD: # 负载不均衡时优先考虑负载均衡 return workers[loads.index(min(loads))] else: # 负载均衡时优先考虑缓存命中 return workers[match_rates.index(max(match_rates))]5. 进阶主题本章探讨 RadixAttention 在生产环境中的进阶应用包括多租户与分布式场景下的扩展设计、与其他推理优化技术的协同以及非前缀复用场景的解决方案。5.1 多租户与分布式场景在实际生产环境中RadixAttention 需要支持多租户隔离和跨实例的 KV Cache 共享。本节讨论相关的扩展设计。5.1.1 多租户支持在多租户场景中不同租户或不同 Worker可能对同一前缀有不同的访问模式。RadixAttention 通过在节点中维护per-tenant 访问时间来支持细粒度的淘汰策略class TreeNode: # 每个租户的最后访问时间 tenant_last_access_time: Dict[str, float] {} def update_access(self, tenant_id: str): self.tenant_last_access_time[tenant_id] time.time()5.1.2 跨实例 KV Cache 共享在分布式推理系统中跨实例共享 KV Cache 是一个重要优化方向。主要挑战包括•一致性如何保证不同实例看到一致的缓存状态。•传输开销KV Cache 数据量大网络传输成本高。•索引同步Radix Tree 结构需要在多实例间同步。Mooncake 的方案• 使用全局 Conductor 管理 KV Cache 元数据。• KV Cache 存储在分布式存储池GPU VRAM CPU DRAM SSD。• 调度时考虑缓存命中率将请求路由到已缓存前缀的节点。LMCache 的方案• 支持 P2P 模式和集中式存储模式。• 使用 Cache Controller 维护全局索引。• 支持跨实例的 KV Cache 传输和复用。5.2 与其他优化技术的协同RadixAttention 可以与多种推理优化技术协同工作进一步提升系统性能。本节介绍三种典型的协同场景。5.2.1 Chunked PrefillChunked Prefill 将长 Prefill 拆分为多个小批次执行与 Decode 请求交替调度。RadixAttention 可以与 Chunked Prefill 协同• 缓存命中的 Chunk 完全跳过。• 仅对未命中的 Chunk 执行分块 Prefill。• 进一步降低长前缀场景的调度延迟。5.2.2 Prefill-Decode 分离架构Prefill-Decode 分离架构PD 分离通过将计算密集型的 Prefill 阶段和访存密集型的 Decode 阶段分配到不同的节点上执行从而提升系统整体吞吐量。在 PD 分离架构 中•Prefill 节点维护热门前缀的 RadixCache专注于 Prefill 计算。•Decode 节点接收 Prefill 节点传来的 KV Cache专注于 Decode 生成。RadixAttention 在此场景下的价值• Prefill 节点可以通过 RadixCache 快速判断是否需要计算。• 相同前缀的请求可以路由到同一 Prefill 节点最大化复用。5.2.3 Speculative Decoding推测执行需要为多个候选 token 序列准备 KV Cache。RadixAttention 可以• 缓存高概率分支的 KV Cache。• 在验证阶段快速复用已计算的 KV Cache。• 降低推测失败时的重算成本。5.3 非前缀复用场景标准的 Prefix Caching 要求从序列开头进行严格的前缀匹配但某些场景下存在非前缀的 KV Cache 复用需求。本节讨论相关挑战与解决方案。5.3.1 RAG 场景的挑战在 RAG检索增强生成场景中检索到的文档片段顺序可能不固定请求 A: [System Prompt] [Doc1] [Doc2] [Query]请求 B: [System Prompt] [Doc2] [Doc1] [Query]由于 Transformer 的因果注意力- Doc1 在位置 2 和位置 3 的 KV Cache 是不同的- 即使内容相同位置不同导致无法直接复用5.3.2 CacheBlend选择性重算LMCache 提出的 CacheBlend 技术提供了一种解决方案允许复用非前缀位置的 KV Cache存在位置不匹配。选择性重算关键位置的 Attention修正位置偏差。在复用率和计算开销之间动态平衡。CacheBlend 流程1. 检索已缓存的 Doc2 的 KV Cache位置 32. 将其加载到位置 23. 重算部分 Attention Scores 以修正位置编码偏差4. 得到近似但高效的结果6. 性能分析与最佳实践本章将从理论模型和实际测试两个方面分析 Prefix Caching 的性能表现并总结在生产环境中部署的最佳实践。6.1 理论性能分析本节从理论角度推导 Prefix Caching 的加速比并分析不同场景下的性能收益。6.1.1 加速比公式在评估 Prefix Caching 的性能时我们可以通过建立简化的数学模型来推导其理论加速比。假设• 前缀长度tokens• 用户查询长度tokens• Prefill 计算复杂度 其中无 Prefix Caching有 Prefix Caching完全命中加速比6.1.2 典型场景收益根据上述公式不同应用场景下 Prefix Caching 能够带来的理论加速比有显著差异具体如下表所示场景前缀长度 P查询长度 Q理论加速比短 System Prompt1K256~2.5x标准 System Prompt4K256~8.5x长 System Prompt8K256~16.5x多轮对话5轮2K128~8.5xRAG长文档16K512~16x6.2 实测数据本节汇总 SGLang 和 vLLM 在不同工作负载下的实测性能数据。6.2.1 SGLang 官方基准测试根据 SGLang 论文 [1] 和官方文档 [4] 的基准测试工作负载模型吞吐量提升TTFT 降低多轮对话Llama-2-7B2-3x60-80%Few-shot 学习Llama-2-7B3-5x70-85%结构化生成Llama-2-7B4-6x75-90%Tree of ThoughtsLlama-2-7B5-8x80-95%6.2.2 与 vLLM APC 的对比根据 SGLang 官方提供的测试数据 [4]在相同硬件和模型配置下RadixAttention 与 vLLM APC 的性能对比如下指标SGLang (RadixAttention)vLLM (APC)前缀命中率85-95%80-90%内存开销5-10%2-5%动态前缀支持优秀良好实现复杂度高中6.3 最佳实践基于理论分析和实测经验本节总结在生产环境中使用 Prefix Caching 的关键优化建议。6.3.1 System Prompt 设计为了最大化前缀缓存的命中率建议在设计 System Prompt 时遵循“稳定内容在前动态内容在后”的原则推荐结构┌─────────────────────────────────────┐│ [固定部分 - 放在最前面] ││ - 角色定义 ││ - 通用指令 ││ - 输出格式要求 │├─────────────────────────────────────┤│ [半动态部分 - 中间位置] ││ - Few-shot 示例按使用频率排序 ││ - 常用工具说明 │├─────────────────────────────────────┤│ [动态部分 - 放在最后] ││ - 用户名、时间戳 ││ - 会话特定上下文 ││ - RAG 检索结果 │└─────────────────────────────────────┘原则稳定内容在前动态内容在后6.3.2 Chunk Size 选择在使用哈希表方案如 vLLM APC时Chunk Size 的大小直接影响缓存的匹配粒度和管理开销。不同大小的优缺点对比如下Chunk Size优点缺点推荐场景64 tokens细粒度匹配哈希计算开销大高度动态前缀256 tokens平衡-通用推荐512 tokens低管理开销粒度粗浪费空间前缀非常稳定建议选择 vLLM Block Size 的整数倍如 256 16 × 16便于与 PagedAttention 对齐。6.3.3 缓存预热策略在服务启动或更新时可以通过预热高频使用的 System Prompt 或上下文来避免冷启动带来的首次请求延迟# 服务启动时预热常用前缀def warmup_cache(common_prompts: List[str]): for prompt in common_prompts: tokens tokenizer.encode(prompt) # 触发 Prefill 并缓存 model.generate(tokens, max_new_tokens1) print(fWarmed up: {len(tokens)} tokens)# 使用示例warmup_cache([ SYSTEM_PROMPT, SYSTEM_PROMPT FEW_SHOT_EXAMPLES, COMMON_RAG_CONTEXT,])7. 总结本章总结 RadixAttention 的核心价值、技术选型建议以及未来发展方向。7.1 RadixAttention 的核心价值RadixAttention 通过创新性地将 Radix Tree 数据结构应用于 KV Cache 管理实现了自动前缀识别无需手动声明系统自动发现和复用共享前缀。高效查找 时间复杂度的最长前缀匹配。细粒度管理支持任意位置的前缀分支和复用。动态适应通过 LRU 淘汰自动适应工作负载变化。7.2 技术选型建议针对不同的业务需求和系统架构我们建议在实际部署中采用以下技术选型方案场景推荐方案SGLang 用户RadixAttention内置vLLM 单实例、显存充足APC内置vLLM 单实例、需扩展缓存APC LMCache多实例部署、需跨实例共享LMCacheP2P 或 Server 模式生产级高可用LMCache Redis/Mooncake 后端学AI大模型的正确顺序千万不要搞错了2026年AI风口已来各行各业的AI渗透肉眼可见超多公司要么转型做AI相关产品要么高薪挖AI技术人才机遇直接摆在眼前有往AI方向发展或者本身有后端编程基础的朋友直接冲AI大模型应用开发转岗超合适就算暂时不打算转岗了解大模型、RAG、Prompt、Agent这些热门概念能上手做简单项目也绝对是求职加分王给大家整理了超全最新的AI大模型应用开发学习清单和资料手把手帮你快速入门学习路线:✅大模型基础认知—大模型核心原理、发展历程、主流模型GPT、文心一言等特点解析✅核心技术模块—RAG检索增强生成、Prompt工程实战、Agent智能体开发逻辑✅开发基础能力—Python进阶、API接口调用、大模型开发框架LangChain等实操✅应用场景开发—智能问答系统、企业知识库、AIGC内容生成工具、行业定制化大模型应用✅项目落地流程—需求拆解、技术选型、模型调优、测试上线、运维迭代✅面试求职冲刺—岗位JD解析、简历AI项目包装、高频面试题汇总、模拟面经以上6大模块看似清晰好上手实则每个部分都有扎实的核心内容需要吃透我把大模型的学习全流程已经整理好了抓住AI时代风口轻松解锁职业新可能希望大家都能把握机遇实现薪资/职业跃迁这份完整版的大模型 AI 学习资料已经上传CSDN朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费】
RadixAttention 技术详解：从原理到 SGLang 实践及 vLLM APC 对比
本文深入剖析大语言模型推理优化中的 RadixAttention 技术详述其基于 Radix Tree基数树自动复用 KV Cache 的核心原理结合 SGLang 的落地实现解析其内存调度机制并与 vLLM 的 APC 方案进行全方位对比为大家在生产环境中提供性能评估与选型参考。1. 引言与背景本章将介绍 LLM 推理中的重复计算问题以及 RadixAttention 提出的解决方案。1.1 LLM 推理中的重复计算问题大语言模型LLM的推理过程分为两个阶段Prefill预填充和Decode解码。在 Prefill 阶段模型需要处理完整的输入序列并生成对应的 KV Cache。根据 [KV Cache 原理简介]中的分析由于 Transformer 的自注意力机制Prefill 阶段的计算复杂度为 其中 为输入序列长度。在实际的 LLM 应用中大量请求存在共享前缀的现象•System Prompt同一应用的所有请求使用相同的系统指令通常 2K-8K tokens。•多轮对话历史对话上下文在后续轮次中反复出现。•Few-shot Examples相同的示例在多个请求中复用。•RAG 场景检索到的文档片段被多个查询复用。根据生产环境的统计数据 [1,3]40%-80% 的 token 序列存在可复用的共享前缀。如果每次请求都从零开始计算这些重复前缀的 KV Cache将造成巨大的计算资源浪费。场景示例客服机器人请求 A: [System Prompt: 8K tokens] [用户问题 A: 256 tokens]请求 B: [System Prompt: 8K tokens] [用户问题 B: 128 tokens]请求 C: [System Prompt: 8K tokens] [用户问题 C: 512 tokens]→ System Prompt 被重复计算 3 次浪费约 95% 的 Prefill 计算量1.2 为什么需要 KV Cache 复用KV Cache 具有一个关键特性确定性。对于相同的输入 token 序列模型总是产生相同的 KKey和 VValue表征。这意味着相同的 token 序列 → 相同的 KV Cache → 只需计算一次后续直接复用这一特性使得 KV Cache 复用成为可能。通过缓存已计算的 KV Cache 并在后续请求中复用我们可以降低 TTFTTime-To-First-Token跳过前缀的 Prefill 计算。提升吞吐量节省的 GPU 算力可服务更多请求。降低成本减少单位请求的计算资源消耗。然而这带来了一个核心的技术挑战如何高效地管理和检索 KV Cache• 缓存的键Key是什么• 如何快速判断新请求是否命中缓存• 如何处理部分前缀匹配的情况• 如何在有限的显存中进行淘汰和替换1.3 现有方案的局限性在 RadixAttention 提出之前常见的 KV Cache 管理方案存在明显局限方案 1简单哈希表:将完整的 token 序列哈希后作为键KV Cache 作为值存入哈希表。# 初始化缓存字典cache {}# 将完整的 token 序列转换为元组后计算哈希值作为键key hash(tuple(token_ids))# 将生成的 KV Cache 存入哈希表cache[key] kv_cache问题无法支持前缀匹配。即使两个请求共享 99% 的前缀只要有一个 token 不同就无法复用任何缓存。方案 2静态前缀缓存:预先定义固定的 System Prompt为其计算并缓存 KV Cache。问题缺乏灵活性无法适应动态工作负载。多轮对话、用户特定上下文等场景无法受益。方案 3逐 Token 查找:将每个 token 的 KV Cache 单独存储按位置索引。问题管理开销巨大无法利用前缀的结构化特性进行高效查找。这些局限性促使 SGLang 团队提出了RadixAttention——一种基于 Radix Tree基数树的 KV Cache 管理方案能够自动、高效地识别和复用任意长度的共享前缀。2. RadixAttention 核心原理RadixAttention 的核心创新在于使用Radix Tree基数树这一数据结构来组织和管理 token 序列与 KV Cache 的映射关系。本章将深入介绍 Radix Tree 的原理及其在 KV Cache 管理中的应用。2.1 Radix Tree 数据结构本节将详细介绍 Radix Tree 数据结构的基本原理、核心特性以及时间复杂度分析。2.1.1 从 Trie 到 Radix TreeTrie前缀树是一种经典的树形数据结构用于高效存储和检索字符串集合。在 Trie 中每个节点代表一个字符从根到叶子的路径表示一个完整的字符串。Trie 存储 [hello, help, world] root / \ h w | | e o | | l r / \ | l p l | | o dTrie 的问题在于当存在长的非分支路径时会产生大量只有单个子节点的中间节点浪费内存且增加遍历深度。Radix Tree基数树也称为压缩前缀树Compressed Trie或Patricia Tree通过路径压缩解决了这一问题。它将连续的、没有分支的节点合并为一个节点存储整个字符串片段而非单个字符。Radix Tree 存储 [hello, help, world] root / \ hel world / \ lo p节点数5Trie 需要 11 个节点2.1.2 Radix Tree 的核心特性与传统 Trie 树相比Radix Tree 具有以下几个核心特性使其非常适合用于管理 KV Cache特性说明路径压缩连续非分支节点合并减少内存和遍历深度前缀共享相同前缀自动合并到同一路径动态更新支持高效的插入、删除和查找最长前缀匹配天然支持找到与查询序列匹配的最长前缀2.1.3 时间复杂度分析设 为查询/插入序列的长度 为字符集大小对于 token 序列 为词表大小操作时间复杂度说明查找与序列长度线性相关与树中总节点数无关插入最坏情况需要分裂现有节点删除可能触发节点合并最长前缀匹配遍历直到无法继续匹配2.2 Token 序列到 KV Cache 的映射在 RadixAttention 中Radix Tree 的每个节点不仅存储 token 序列片段还关联了对应的KV Cache Block。2.2.1 节点结构设计在 RadixAttention 的实现中每个 Radix Tree 节点都需要保存 token 信息以及关联的缓存块索引。以下是节点的典型结构设计class RadixNode: # 存储的 token 序列片段 tokens: List[int] # 对应的 KV Cache Block 列表每个 Block 固定大小如 16 tokens kv_cache_blocks: List[KVCacheBlock] # 子节点映射第一个 token - 子节点 children: Dict[int, RadixNode] # 引用计数当前有多少活跃请求使用此节点 ref_count: int # 最后访问时间用于 LRU 淘汰 last_access_time: float2.2.2 树的构建过程当新的 token 序列需要被缓存时RadixAttention 执行以下步骤从根节点开始匹配逐 token 比较沿着匹配的路径向下遍历处理分歧点• 如果在某个节点内部出现不匹配分裂该节点• 将公共部分保留不同部分创建新的子节点创建新路径对于完全不匹配的后缀创建新的节点链初始状态树中已有序列 hello world插入序列 hello vllm步骤 1: 匹配 hello (6 tokens) ✓步骤 2: 在 world 节点处发现不匹配w vs v步骤 3: 分裂节点创建分支结果 root | hello / \ world vllm2.2.3 前缀共享机制Radix Tree 的结构天然支持前缀共享所有具有相同前缀的序列都会经过相同的节点路径。这意味着• 相同前缀的 KV Cache 只存储一份。• 新序列插入时自动识别并复用已有前缀。• 无需显式的“注册”或“声明”共享关系。请求 A: [System Prompt] [Query A] → 缓存 System Prompt请求 B: [System Prompt] [Query B] → 自动复用 System Prompt 的 KV Cache请求 C: [System Prompt] [Query A] [Response A] [Query C] → 复用 System Prompt Query A 的全部 KV Cache2.3 前缀匹配与查找算法前缀匹配是 RadixAttention 的核心操作决定了能够复用多少已缓存的 KV Cache。本节介绍最长前缀匹配算法及其查找结果的处理方式。2.3.1 最长前缀匹配算法当新请求到达时RadixAttention 需要找到与请求 token 序列匹配的最长前缀以最大化 KV Cache 复用。def match_prefix(root: RadixNode, query_tokens: List[int]) - Tuple[int, List[KVCacheBlock]]: 查找与 query_tokens 匹配的最长前缀 返回(匹配长度, 对应的 KV Cache Block 列表) current root matched_length 0 matched_blocks [] query_pos 0 while query_pos len(query_tokens): # 查找匹配的子节点 first_token query_tokens[query_pos] if first_token not in current.children: break # 无匹配子节点停止 child current.children[first_token] # 在子节点内逐 token 匹配 node_pos 0 while node_pos len(child.tokens) and query_pos len(query_tokens): if child.tokens[node_pos] ! query_tokens[query_pos]: break # 节点内部不匹配停止 node_pos 1 query_pos 1 # 收集匹配的 KV Cache Blocks matched_length query_pos matched_blocks.extend(child.kv_cache_blocks[:node_pos // BLOCK_SIZE]) if node_pos len(child.tokens): break # 节点未完全匹配停止 current child # 继续向下遍历 return matched_length, matched_blocks2.3.2 查找结果的处理前缀匹配的结果决定了推理引擎的后续行为匹配情况处理方式完全匹配直接复用全部 KV Cache跳过 Prefill部分匹配复用匹配部分的 KV Cache仅对未匹配后缀执行 Prefill无匹配从头执行完整 Prefill并将结果缓存查询序列: [T0, T1, T2, T3, T4, T5, T6, T7]树中已有: [T0, T1, T2, T3] → KV Blocks [B0, B1]匹配结果: 长度4, Blocks[B0, B1]Prefill 执行:- 位置 0-3: 跳过计算加载 [B0, B1]- 位置 4-7: 执行 Prefill生成新的 KV Cache2.4 LRU 淘汰策略GPU 显存有限无法无限缓存 KV Cache。RadixAttention 采用LRULeast Recently Used策略进行缓存淘汰。2.4.1 引用计数机制为了避免淘汰正在被使用的 KV Cache每个节点维护一个引用计数• 当请求开始使用某节点的 KV Cache 时ref_count 1• 当请求完成生成结束或被取消时ref_count - 1•只有ref_count 0的节点才能被淘汰def acquire_node(node: RadixNode): 请求开始使用节点 node.ref_count 1 node.last_access_time time.time()def release_node(node: RadixNode): 请求释放节点 node.ref_count - 12.4.2 淘汰算法当显存不足时RadixAttention 从叶子节点开始按最后访问时间排序淘汰最久未使用的节点def evict_lru(root: RadixNode, target_free_blocks: int) - int: 淘汰最久未使用的节点释放指定数量的 KV Cache Blocks 返回实际释放的 Block 数量 freed_blocks 0 # 收集所有可淘汰的叶子节点ref_count 0 evictable_leaves collect_evictable_leaves(root) # 按最后访问时间排序 evictable_leaves.sort(keylambda n: n.last_access_time) for leaf in evictable_leaves: if freed_blocks target_free_blocks: break # 释放 KV Cache Blocks freed_blocks len(leaf.kv_cache_blocks) release_kv_blocks(leaf.kv_cache_blocks) # 从父节点移除 remove_from_parent(leaf) # 如果父节点只剩一个子节点合并路径 merge_single_child_nodes(leaf.parent) return freed_blocks2.4.3 淘汰的级联效应由于 Radix Tree 的前缀共享特性淘汰需要谨慎处理•只能从叶子节点开始淘汰中间节点被淘汰会导致所有后代节点失效。•淘汰后可能触发节点合并父节点只剩一个子节点时可以合并以保持压缩特性。淘汰前 hello / \ world vllm淘汰 vllm 后 hello | world进一步压缩 hello world3. SGLang 中的实现SGLangStructured Generation Language是由 UC Berkeley 团队开发的高效 LLM 推理系统RadixAttention 正是其核心优化技术之一。本章将分析 RadixAttention 在 SGLang 中的具体实现。3.1 SGLang 系统架构简介SGLang 的定位是结构化语言模型程序的高效执行引擎。它支持复杂的控制流如循环、分支、多次生成调用的复合任务并通过 RadixAttention 实现跨调用的 KV Cache 自动复用。SGLang 架构概览┌───────────────────────────────────────────────────────────┐│ SGLang Frontend ││ (Python DSL for structured LLM programs) │└───────────────────────────────────────────────────────────┘ │ ▼┌───────────────────────────────────────────────────────────┐│ SGLang Runtime ││ ┌─────────────┐ ┌─────────────────┐ ┌─────────────┐ ││ │ Scheduler │◄─┤ RadixCache ├─►│ Executor │ ││ │ │ │ (RadixAttention)│ │ │ ││ └─────────────┘ └─────────────────┘ └─────────────┘ │└───────────────────────────────────────────────────────────┘ │ ▼┌───────────────────────────────────────────────────────────┐│ Model Execution Backend ││ (CUDA Kernels, PagedAttention) │└───────────────────────────────────────────────────────────┘RadixAttention 位于 SGLang Runtime 的核心位置负责管理所有缓存的 token 序列与 KV Cache 的映射为每个请求提供前缀匹配查询协调 KV Cache Block 的分配与淘汰3.2 核心数据结构SGLang 中的 RadixAttention 实现涉及三个核心数据结构RadixCache 主类、TreeNode 节点结构以及内存池管理器。3.2.1 RadixCache 类RadixCache是 RadixAttention 的主类封装了 Radix Tree 及其操作class RadixCache: def __init__( self, req_to_token_pool, # Token Pool 管理器 token_to_kv_pool, # KV Cache Pool 管理器 disable: bool False, # 是否禁用缓存 ): self.root_node TreeNode() # Radix Tree 根节点 self.req_to_token_pool req_to_token_pool self.token_to_kv_pool token_to_kv_pool self.disable disable # 统计信息 self.total_cache_hit_tokens 0 self.total_cache_miss_tokens 0 def match_prefix(self, rid: int, key: List[int]) - Tuple[TreeNode, int]: 查找最长匹配前缀 ... def insert(self, node: TreeNode, key: List[int], value: List[int]): 插入新的 token 序列 ... def evict(self, num_tokens: int) - int: LRU 淘汰指定数量的 tokens ...3.2.2 TreeNode 结构每个TreeNode代表 Radix Tree 中的一个节点class TreeNode: def __init__(self): # 子节点映射token_id - TreeNode self.children: Dict[int, TreeNode] {} # 父节点引用 self.parent: Optional[TreeNode] None # 存储的 token 序列压缩后的路径 self.key: List[int] [] # 对应的 KV Cache Block 索引 self.value: List[int] [] # 引用计数 self.lock_ref: int 0 # 最后访问时间 self.last_access_time: float 0.03.2.3 内存池管理SGLang 使用专门的内存池管理 KV Cache Blocks•Token Pool管理 token 序列到物理位置的映射•KV Pool管理实际的 KV Cache 显存分配class TokenToKVPool: def __init__(self, size: int, dtype: torch.dtype): # 预分配的 KV Cache 显存 self.k_buffer torch.empty((size, ...), dtypedtype, devicecuda) self.v_buffer torch.empty((size, ...), dtypedtype, devicecuda) # 空闲 Block 列表 self.free_slots: List[int] list(range(size)) def alloc(self, num_blocks: int) - List[int]: 分配 KV Cache Blocks ... def free(self, block_ids: List[int]): 释放 KV Cache Blocks ...3.3 关键操作实现本节详细分析 RadixCache 的四个关键操作前缀匹配、插入、LRU 淘汰以及并发控制。3.3.1 前缀匹配match_prefix()前缀匹配是系统处理新请求时的首个操作。该方法通过遍历 Radix Tree找到与输入序列匹配的最长前缀路径def match_prefix(self, rid: int, key: List[int]) - Tuple[TreeNode, int]: 查找与 key 匹配的最长前缀 Args: rid: 请求 ID key: 输入的 token 序列 Returns: (last_node, prefix_len): 最后匹配的节点和前缀长度 if self.disable: return self.root_node, 0 current self.root_node prefix_len 0 key_len len(key) while prefix_len key_len: # 查找匹配的子节点 first_token key[prefix_len] if first_token not in current.children: break child current.children[first_token] child_key child.key child_len len(child_key) # 检查子节点的 key 是否完全匹配 match_len 0 while match_len child_len and prefix_len match_len key_len: if child_key[match_len] ! key[prefix_len match_len]: break match_len 1 prefix_len match_len if match_len child_len: # 部分匹配需要在返回前处理 break current child # 更新统计 self.total_cache_hit_tokens prefix_len self.total_cache_miss_tokens key_len - prefix_len return current, prefix_len3.3.2 插入操作insert()当处理完未命中的前缀并生成新的 KV Cache 后系统需要将这些新数据插入到 Radix Tree 中。插入过程可能涉及节点的分裂def insert(self, node: TreeNode, key: List[int], value: List[int]): 从指定节点开始插入新的 token 序列 Args: node: 起始节点通常是 match_prefix 返回的节点 key: 要插入的 token 序列未匹配部分 value: 对应的 KV Cache Block IDs if self.disable or len(key) 0: return current node key_pos 0 while key_pos len(key): first_token key[key_pos] if first_token in current.children: child current.children[first_token] child_key child.key # 找到公共前缀长度 common_len 0 while (common_len len(child_key) and key_pos common_len len(key) and child_key[common_len] key[key_pos common_len]): common_len 1 if common_len len(child_key): # 需要分裂节点 self._split_node(child, common_len) key_pos common_len current child else: # 创建新节点 new_node TreeNode() new_node.key key[key_pos:] new_node.value value[key_pos:] new_node.parent current current.children[first_token] new_node break current.last_access_time time.time()3.3.3 LRU 淘汰evict()当系统显存不足时将触发 LRU 淘汰机制。淘汰操作总是从最久未使用的叶子节点开始以释放 KV Cache 块def evict(self, num_tokens: int) - int: 淘汰至少 num_tokens 个 tokens 的缓存 Returns: 实际淘汰的 tokens 数量 if self.disable: return 0 evicted 0 # 收集所有叶子节点 leaves self._collect_leaves() # 按最后访问时间排序最旧的在前 leaves.sort(keylambda n: n.last_access_time) for leaf in leaves: if evicted num_tokens: break # 跳过被锁定的节点 if leaf.lock_ref 0: continue # 释放 KV Cache evicted len(leaf.value) self.token_to_kv_pool.free(leaf.value) # 从树中移除 self._remove_node(leaf) return evicted3.3.4 并发控制SGLang 使用节点级锁来支持并发访问def inc_lock_ref(self, node: TreeNode): 增加节点的引用计数请求开始使用 delta 0 while node is not None: if node.lock_ref 0: delta 1 node.lock_ref 1 node node.parent return deltadef dec_lock_ref(self, node: TreeNode): 减少节点的引用计数请求结束 delta 0 while node is not None: node.lock_ref - 1 if node.lock_ref 0: delta 1 node node.parent return delta3.4 与 PagedAttention 的集成RadixAttention 与 PagedAttention 紧密集成共同实现高效的 KV Cache 管理Block 粒度对齐RadixCache 中的 value 存储的是 Block ID 而非原始显存地址。统一的内存池KV Cache Blocks 由TokenToKVPool统一管理。Block Table 更新Prefill 完成后Block Table 自动更新以包含新生成的 KV Cache。请求处理流程1. match_prefix(tokens) → (node, prefix_len, block_ids)2. 将 block_ids 加载到 Block Table 的前 prefix_len 位置3. 仅对 tokens[prefix_len:] 执行 Prefill4. 将新生成的 KV Cache 存入新分配的 Blocks5. insert(node, tokens[prefix_len:], new_block_ids)4. vLLM 的 Automatic Prefix Caching (APC) 对比vLLM 从 v0.4.0 开始引入了 **[Automatic Prefix Caching (APC)]功能实现了类似 RadixAttention 的前缀缓存能力但采用了不同的技术方案。本章将对比分析两者的异同。4.1 vLLM 的技术选型Hash Table vs Radix TreevLLM 的 APC 与 SGLang 的 RadixAttention 在功能上相似但在底层数据结构上做出了不同的选择。本节分析 vLLM 选择哈希表的原因及其设计细节。4.1.1 为什么 vLLM 选择 Hash TablevLLM 没有采用 Radix Tree而是选择了基于哈希表的增量哈希链方案。主要考量包括与 Block Manager 的集成vLLM 的 PagedAttention 已经以 Block 为粒度管理 KV Cache哈希表可以直接以 Block Hash 为键。实现复杂度哈希表的实现比 Radix Tree 更简单易于维护。内存开销哈希表的额外内存开销通常低于树结构。4.1.2 增量哈希链设计vLLM 的 APC 使用增量哈希确保前缀依赖def hash_block_tokens( parent_block_hash: Optional[int], curr_block_token_ids: Tuple[int, ...]) - int: 计算 Block 的哈希值 return hash((parent_block_hash, curr_block_token_ids))这种设计保证了• 相同的前缀 → 相同的哈希链• 不同的前缀 → 不同的哈希值即使当前 Block 内容相同4.1.3 缓存查找流程vLLM 的缓存查找过程基于增量哈希链按 Block 粒度逐个匹配一旦遇到未命中的 Block 即可提前终止查找def find_cached_blocks(token_ids: List[int], block_size: int) - List[int]: 查找已缓存的 Blocks cached_blocks [] parent_hash None for i in range(0, len(token_ids), block_size): chunk tuple(token_ids[i:i block_size]) block_hash hash_block_tokens(parent_hash, chunk) if block_hash in block_cache: cached_blocks.append(block_cache[block_hash]) parent_hash block_hash else: break # 一旦未命中后续都无法复用 return cached_blocks4.2 两种方案的对比分析SGLang 的 RadixAttention 与 vLLM 的 APC 在设计理念和数据结构上各有侧重以下是这两种方案在多个维度上的详细对比维度RadixAttention (SGLang)APC (vLLM)数据结构Radix Tree压缩前缀树Hash Table哈希表索引粒度Token 级别Block 级别16-32 tokens查找方式树遍历天然支持最长前缀匹配逐 Block 哈希查找内存开销较高树节点、指针较低仅哈希表条目动态前缀任意位置分支灵活性高需 Block 对齐灵活性稍低实现复杂度较高节点分裂、合并较低标准哈希表操作并发支持需要细粒度锁通过引用计数管理4.2.1 适用场景对比根据两种方案的特性差异它们在不同的业务场景中各有优势。以下是它们的主要适用场景对比RadixAttention 更适合• 高度动态的工作负载前缀频繁变化• 需要细粒度token 级缓存控制的场景• 复杂的结构化生成程序SGLang 的核心用例vLLM APC 更适合• 前缀相对固定的场景如固定 System Prompt• 追求实现简洁性和与现有系统集成• Block 对齐不造成显著浪费的场景4.3 vLLM Router 中的 Radix Tree 应用有趣的是虽然 vLLM 的 KV Cache 管理使用哈希表但其路由组件vLLM Router却使用了 Radix Tree 来实现Cache Aware 路由策略。本节介绍该策略的原理和动态平衡机制。4.3.1 Cache Aware 策略概述在多实例部署场景中如何将请求路由到最可能已缓存其前缀的 Worker 节点是一个关键问题。vLLM Router 的 Cache Aware 策略为每个 Worker 维护一棵近似 Radix Tree追踪该 Worker 上已缓存的请求前缀。新请求到达时计算其与各 Worker Radix Tree 的前缀匹配率。优先将请求路由到匹配率最高的 Worker。Router 中的 Radix Tree 结构Worker A 的 Radix Tree: root - You are a helpful - assistant - for coding - chatbotWorker B 的 Radix Tree: root - You are a helpful - translator - Summarize the - following text新请求: You are a helpful assistant for Python→ 与 Worker A 匹配 You are a helpful assistant更长→ 路由到 Worker A4.3.2 动态平衡机制Cache Aware 策略并非总是选择匹配率最高的 Worker它还会考虑负载均衡def select_worker(request: Request, workers: List[Worker]) - Worker: # 计算各 Worker 的匹配率 match_rates [worker.radix_tree.match_rate(request.tokens) for worker in workers] # 获取当前负载 loads [worker.current_load for worker in workers] # 判断是否需要负载均衡 if max(loads) - min(loads) BALANCE_THRESHOLD: # 负载不均衡时优先考虑负载均衡 return workers[loads.index(min(loads))] else: # 负载均衡时优先考虑缓存命中 return workers[match_rates.index(max(match_rates))]5. 进阶主题本章探讨 RadixAttention 在生产环境中的进阶应用包括多租户与分布式场景下的扩展设计、与其他推理优化技术的协同以及非前缀复用场景的解决方案。5.1 多租户与分布式场景在实际生产环境中RadixAttention 需要支持多租户隔离和跨实例的 KV Cache 共享。本节讨论相关的扩展设计。5.1.1 多租户支持在多租户场景中不同租户或不同 Worker可能对同一前缀有不同的访问模式。RadixAttention 通过在节点中维护per-tenant 访问时间来支持细粒度的淘汰策略class TreeNode: # 每个租户的最后访问时间 tenant_last_access_time: Dict[str, float] {} def update_access(self, tenant_id: str): self.tenant_last_access_time[tenant_id] time.time()5.1.2 跨实例 KV Cache 共享在分布式推理系统中跨实例共享 KV Cache 是一个重要优化方向。主要挑战包括•一致性如何保证不同实例看到一致的缓存状态。•传输开销KV Cache 数据量大网络传输成本高。•索引同步Radix Tree 结构需要在多实例间同步。Mooncake 的方案• 使用全局 Conductor 管理 KV Cache 元数据。• KV Cache 存储在分布式存储池GPU VRAM CPU DRAM SSD。• 调度时考虑缓存命中率将请求路由到已缓存前缀的节点。LMCache 的方案• 支持 P2P 模式和集中式存储模式。• 使用 Cache Controller 维护全局索引。• 支持跨实例的 KV Cache 传输和复用。5.2 与其他优化技术的协同RadixAttention 可以与多种推理优化技术协同工作进一步提升系统性能。本节介绍三种典型的协同场景。5.2.1 Chunked PrefillChunked Prefill 将长 Prefill 拆分为多个小批次执行与 Decode 请求交替调度。RadixAttention 可以与 Chunked Prefill 协同• 缓存命中的 Chunk 完全跳过。• 仅对未命中的 Chunk 执行分块 Prefill。• 进一步降低长前缀场景的调度延迟。5.2.2 Prefill-Decode 分离架构Prefill-Decode 分离架构PD 分离通过将计算密集型的 Prefill 阶段和访存密集型的 Decode 阶段分配到不同的节点上执行从而提升系统整体吞吐量。在 PD 分离架构 中•Prefill 节点维护热门前缀的 RadixCache专注于 Prefill 计算。•Decode 节点接收 Prefill 节点传来的 KV Cache专注于 Decode 生成。RadixAttention 在此场景下的价值• Prefill 节点可以通过 RadixCache 快速判断是否需要计算。• 相同前缀的请求可以路由到同一 Prefill 节点最大化复用。5.2.3 Speculative Decoding推测执行需要为多个候选 token 序列准备 KV Cache。RadixAttention 可以• 缓存高概率分支的 KV Cache。• 在验证阶段快速复用已计算的 KV Cache。• 降低推测失败时的重算成本。5.3 非前缀复用场景标准的 Prefix Caching 要求从序列开头进行严格的前缀匹配但某些场景下存在非前缀的 KV Cache 复用需求。本节讨论相关挑战与解决方案。5.3.1 RAG 场景的挑战在 RAG检索增强生成场景中检索到的文档片段顺序可能不固定请求 A: [System Prompt] [Doc1] [Doc2] [Query]请求 B: [System Prompt] [Doc2] [Doc1] [Query]由于 Transformer 的因果注意力- Doc1 在位置 2 和位置 3 的 KV Cache 是不同的- 即使内容相同位置不同导致无法直接复用5.3.2 CacheBlend选择性重算LMCache 提出的 CacheBlend 技术提供了一种解决方案允许复用非前缀位置的 KV Cache存在位置不匹配。选择性重算关键位置的 Attention修正位置偏差。在复用率和计算开销之间动态平衡。CacheBlend 流程1. 检索已缓存的 Doc2 的 KV Cache位置 32. 将其加载到位置 23. 重算部分 Attention Scores 以修正位置编码偏差4. 得到近似但高效的结果6. 性能分析与最佳实践本章将从理论模型和实际测试两个方面分析 Prefix Caching 的性能表现并总结在生产环境中部署的最佳实践。6.1 理论性能分析本节从理论角度推导 Prefix Caching 的加速比并分析不同场景下的性能收益。6.1.1 加速比公式在评估 Prefix Caching 的性能时我们可以通过建立简化的数学模型来推导其理论加速比。假设• 前缀长度tokens• 用户查询长度tokens• Prefill 计算复杂度 其中无 Prefix Caching有 Prefix Caching完全命中加速比6.1.2 典型场景收益根据上述公式不同应用场景下 Prefix Caching 能够带来的理论加速比有显著差异具体如下表所示场景前缀长度 P查询长度 Q理论加速比短 System Prompt1K256~2.5x标准 System Prompt4K256~8.5x长 System Prompt8K256~16.5x多轮对话5轮2K128~8.5xRAG长文档16K512~16x6.2 实测数据本节汇总 SGLang 和 vLLM 在不同工作负载下的实测性能数据。6.2.1 SGLang 官方基准测试根据 SGLang 论文 [1] 和官方文档 [4] 的基准测试工作负载模型吞吐量提升TTFT 降低多轮对话Llama-2-7B2-3x60-80%Few-shot 学习Llama-2-7B3-5x70-85%结构化生成Llama-2-7B4-6x75-90%Tree of ThoughtsLlama-2-7B5-8x80-95%6.2.2 与 vLLM APC 的对比根据 SGLang 官方提供的测试数据 [4]在相同硬件和模型配置下RadixAttention 与 vLLM APC 的性能对比如下指标SGLang (RadixAttention)vLLM (APC)前缀命中率85-95%80-90%内存开销5-10%2-5%动态前缀支持优秀良好实现复杂度高中6.3 最佳实践基于理论分析和实测经验本节总结在生产环境中使用 Prefix Caching 的关键优化建议。6.3.1 System Prompt 设计为了最大化前缀缓存的命中率建议在设计 System Prompt 时遵循“稳定内容在前动态内容在后”的原则推荐结构┌─────────────────────────────────────┐│ [固定部分 - 放在最前面] ││ - 角色定义 ││ - 通用指令 ││ - 输出格式要求 │├─────────────────────────────────────┤│ [半动态部分 - 中间位置] ││ - Few-shot 示例按使用频率排序 ││ - 常用工具说明 │├─────────────────────────────────────┤│ [动态部分 - 放在最后] ││ - 用户名、时间戳 ││ - 会话特定上下文 ││ - RAG 检索结果 │└─────────────────────────────────────┘原则稳定内容在前动态内容在后6.3.2 Chunk Size 选择在使用哈希表方案如 vLLM APC时Chunk Size 的大小直接影响缓存的匹配粒度和管理开销。不同大小的优缺点对比如下Chunk Size优点缺点推荐场景64 tokens细粒度匹配哈希计算开销大高度动态前缀256 tokens平衡-通用推荐512 tokens低管理开销粒度粗浪费空间前缀非常稳定建议选择 vLLM Block Size 的整数倍如 256 16 × 16便于与 PagedAttention 对齐。6.3.3 缓存预热策略在服务启动或更新时可以通过预热高频使用的 System Prompt 或上下文来避免冷启动带来的首次请求延迟# 服务启动时预热常用前缀def warmup_cache(common_prompts: List[str]): for prompt in common_prompts: tokens tokenizer.encode(prompt) # 触发 Prefill 并缓存 model.generate(tokens, max_new_tokens1) print(fWarmed up: {len(tokens)} tokens)# 使用示例warmup_cache([ SYSTEM_PROMPT, SYSTEM_PROMPT FEW_SHOT_EXAMPLES, COMMON_RAG_CONTEXT,])7. 总结本章总结 RadixAttention 的核心价值、技术选型建议以及未来发展方向。7.1 RadixAttention 的核心价值RadixAttention 通过创新性地将 Radix Tree 数据结构应用于 KV Cache 管理实现了自动前缀识别无需手动声明系统自动发现和复用共享前缀。高效查找 时间复杂度的最长前缀匹配。细粒度管理支持任意位置的前缀分支和复用。动态适应通过 LRU 淘汰自动适应工作负载变化。7.2 技术选型建议针对不同的业务需求和系统架构我们建议在实际部署中采用以下技术选型方案场景推荐方案SGLang 用户RadixAttention内置vLLM 单实例、显存充足APC内置vLLM 单实例、需扩展缓存APC LMCache多实例部署、需跨实例共享LMCacheP2P 或 Server 模式生产级高可用LMCache Redis/Mooncake 后端学AI大模型的正确顺序千万不要搞错了2026年AI风口已来各行各业的AI渗透肉眼可见超多公司要么转型做AI相关产品要么高薪挖AI技术人才机遇直接摆在眼前有往AI方向发展或者本身有后端编程基础的朋友直接冲AI大模型应用开发转岗超合适就算暂时不打算转岗了解大模型、RAG、Prompt、Agent这些热门概念能上手做简单项目也绝对是求职加分王给大家整理了超全最新的AI大模型应用开发学习清单和资料手把手帮你快速入门学习路线:✅大模型基础认知—大模型核心原理、发展历程、主流模型GPT、文心一言等特点解析✅核心技术模块—RAG检索增强生成、Prompt工程实战、Agent智能体开发逻辑✅开发基础能力—Python进阶、API接口调用、大模型开发框架LangChain等实操✅应用场景开发—智能问答系统、企业知识库、AIGC内容生成工具、行业定制化大模型应用✅项目落地流程—需求拆解、技术选型、模型调优、测试上线、运维迭代✅面试求职冲刺—岗位JD解析、简历AI项目包装、高频面试题汇总、模拟面经以上6大模块看似清晰好上手实则每个部分都有扎实的核心内容需要吃透我把大模型的学习全流程已经整理好了抓住AI时代风口轻松解锁职业新可能希望大家都能把握机遇实现薪资/职业跃迁这份完整版的大模型 AI 学习资料已经上传CSDN朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费】
