前缀缓存驱逐策略:RadixAttention 树上的 LRU、频率与成本加权驱逐及多租户命中率模型
更新时间:2026-10-06。前缀缓存把「多个请求共享的 prompt 前缀」的 KV 只算一次、只存一份,是长 system prompt、多轮对话、RAG 场景里同时省算力和省显存的关键机制——站内 前缀缓存与 prompt 复用 讲了收益模型,SGLang Radix 前缀缓存 讲了树结构的组织方式。这篇回答一个随之而来的运维问题:缓存容量永远装不下所有前缀,谁去谁留。驱逐策略(eviction policy)听起来是缓存课的老话题,但前缀缓存是一棵树而不是平铺的键值表,树上的驱逐有它自己的规则、自己的坑,和一套可以定量估算的命中率模型。
本文要回答的问题
- RadixAttention 树上的驱逐和平铺缓存的驱逐有什么本质不同,为什么只能驱逐叶子?
- LRU、频率加权、成本加权三类策略各自的适用负载是什么?
- 多租户共享前缀时,公平性和命中率怎么两全?
- 给定流量特征,命中率能不能提前估算,容量该怎么配?
一、树结构给驱逐立的三条规矩
先回顾树结构本身:RadixAttention 把所有缓存的前缀组织成一棵基数树,每条从根到叶的路径是一段 token 序列,节点上挂着对应前缀段的 KV block 引用。请求到来时在树上做最长前缀匹配,命中部分直接复用,未命中部分算完后作为新分支挂回树上。
这棵树给驱逐立了三条平铺缓存没有的规矩。第一条:只能驱逐叶子。一个内部节点的子树里还有其他活跃分支,删了它等于删了所有后代前缀——「system prompt 前 2k token」这个节点可能是几百条分支的公共祖先,驱逐它的代价是整片子树。所以驱逐的基本单元是叶子节点,删叶子后如果父节点变成新叶子且也无引用,可以递归上卷。第二条:引用计数优先于任何策略。正在被进行中的请求引用的节点不可驱逐,策略只在「零引用的叶子」这个候选集里做选择——这意味着高并发下可驱逐的候选其实不多,策略的实际自由度比理论小。第三条:驱逐粒度是变长的。基数树的边代表变长 token 段,一个叶子可能挂 16 个 token 也可能挂 2k 个 token,「驱逐一个叶子」释放的显存和损失的前缀长度都不固定,策略的成本模型必须按字节和按 token 双重记账。
上图把三条规矩画在一棵具体的树上:绿色是唯一安全的驱逐候选,黄色被引用计数保护,中间那个内部节点谁都不敢动。看这张图就能理解为什么驱逐策略的论文式对比(LRU 对 LFU)在树上要做修正——候选集本身已经被结构筛掉了一大半。
二、三类驱逐策略:LRU、频率加权、成本加权
**LRU(最近最少使用)**是默认答案:维护零引用叶子的访问时间戳,空间不足时从最久未访问的开始删。优点是实现极简、对「时间局部性」强的负载(多轮对话连续追问)表现好——刚用过的前缀大概率马上再用。缺点是对「大而不热」的节点处理不当:一条 8k token 的 RAG 文档前缀如果被驱逐,重建成本是 recompute 8k token 的 prefill;LRU 只看时间不看成本,可能为了腾 8k 的空间删掉这个贵节点,留住一堆 32 token 的便宜小叶子。
**频率加权(LFU 族)**给每个节点记访问次数,驱逐次数最少的。它抓住的是「长期热度」——system prompt 这类被全体请求反复命中的前缀,频率计数天然高位,几乎不会被驱逐。纯 LFU 的老问题在树上同样存在:历史热度衰减不掉,一个昨天爆火今天过气的前缀会长期霸占空间,所以生产实现都带老化(计数定期减半)。
成本加权把「重建这个前缀要多少算力」放进驱逐代价:驱逐得分 = f(最近性, 频率) × 节点 token 数(重建成本)。直觉很直白——驱逐一个 8k 前缀的损失约等于驱逐 256 个 32 token 小前缀的损失之和,因为下一次命中失败时前者要重算 8k 的 prefill。SGLang 的生产实践和这个方向一致:在 LRU 的基础上对大节点给保护性权重。成本加权还可以再进一步,把「命中时省下的不只是 prefill 算力还有排队时间」算进去——高峰期的 prefill 算力比低谷期值钱,理论上驱逐代价应该随集群水位浮动,这个精细化目前多见于研究,工程上静态权重已够用。
| 策略 | 考虑因素 | 优势负载 | 主要缺陷 | 实现成本 |
|---|---|---|---|---|
| LRU | 最近性 | 多轮对话连续追问 | 无视重建成本 大前缀吃亏 | 极低 |
| LFU 加老化 | 长期频率 | 稳定 system prompt 高复用 | 热度突变响应慢 | 低 |
| 成本加权 | 最近性 频率 重建成本 | 混合长度 RAG 与 Agent | 参数要按负载标定 | 中 |
这张表可以直接当选型速查。多数团队的落地路径是从 LRU 起步(已经是引擎默认),在观测到「大前缀频繁重建」的埋点信号后升级成本加权——升级的收益和负载里长前缀的占比正相关,短前缀为主的负载升级了也看不出差别。
成本加权的具体打分公式值得再展开一步,因为它决定了标定时要调哪几个旋钮。一个工程上好用的形式是:得分 = α × 距上次访问的秒数 + β × 访问间隔的指数移动平均 − γ × log(节点 token 数)。前两项合起来是「最近性和频率」的混合,第三项是成本保护——token 数越大的节点得分被拉低,越不容易被驱逐。三个系数的标定顺序有讲究:先只开 α(退化为 LRU)拿到基线命中率,再加 γ 观察大前缀重建量的变化,最后引入 β 微调。一次只动一个旋钮,否则三个参数纠缠在一起,命中率变化归因不清。标定的目标函数建议直接用「驱逐后重建消耗的 prefill token 总量」,它比命中率更贴近成本,也能自然惩罚「驱逐大节点」的错误。
三、多租户共享:公平性与命中率的两难
共享前缀缓存进入多租户平台后,问题从「全局命中率最大化」变成「全局命中率和租户公平性的联合优化」。矛盾很具体:租户 A 的流量高度模板化(同一个长 system prompt),租户 B 的流量高度发散(每次 prompt 都不同)。全局最优策略会把全部缓存空间给 A 的前缀——B 的缓存条目命中率低,留着「浪费」。结果是 A 的 TTFT 越来越好,B 的 TTFT 没有改善,而 B 付的钱一分不少。
工程上有三档解法。配额隔离:给每个租户预留缓存空间下限,下限之内租户自己的驱逐策略说了算,下限之外的公共空间全局竞争。简单、可解释,代价是静态配额对流量结构变化不灵敏。加权驱逐:驱逐得分里乘上租户权重,权重按租户的历史命中率反向调节——命中率长期低于配额的租户,其条目获得驱逐保护。这是「结果公平」而非「空间公平」,更符合 SLO 导向的计费逻辑。优先级分层:付费档位直接映射驱逐优先级,高优租户的条目最后驱逐。最粗暴也最好卖,但要小心低优租户的体验塌方引发投诉——配合 请求优先级与抢占 的队列侧优先级一起设计才完整。
上图画出矛盾结构和三档解法的选择逻辑。还有一个和路由的联动必须提:前缀缓存的命中率高度依赖「同前缀的请求被路由到持有该前缀的实例」,驱逐策略和路由策略是一体两面——路由把流量粘到实例上创造了局部性,驱逐策略负责把局部性兑现成命中率,见 LLM 路由负载均衡。如果路由是随机的,跨实例的全局前缀池会让驱逐决策复杂一个量级,此时更务实的做法是每个实例独立管理自己的树。
四、命中率模型与容量规划
最后一个问题:给多少显存当前缀缓存,命中率能到多少?可以粗略建模。把前缀的总体想象成一个按访问频率排序的分布(生产上普遍接近 Zipf:少数前缀极热,大量前缀长尾),缓存能装下前 K 个最热门前缀时,命中率近似等于这 K 个前缀的频率质量之和。操作步骤:从日志提取所有请求的「可共享前缀段」,统计每个前缀段的命中次数和 token 长度,按频率排序画累计曲线——曲线的横轴是缓存容量(按 token 累计),纵轴是累计命中质量。这条曲线直接读出「给 X GB 缓存,命中率约 Y%」。
规划时三个经验锚点。其一,Zipf 分布的累计曲线是对数形的:容量翻倍,命中率只涨固定的一小段——前缀缓存存在明显的性价比拐点,过了拐点加容量的收益急剧递减,拐点位置由流量的前缀多样性决定,模板化负载拐点早(几十 MB 就够),开放域负载拐点晚。其二,驱逐策略改变的是曲线的「可达部分」:理想策略能逼近理论曲线的九成以上,糟糕的驱逐(比如不保护大节点的纯 LRU 遇上混合长度负载)可能只兑现六七成——实测命中率持续低于理论曲线时,问题在驱逐策略不在容量。其三,缓存容量和 KV 工作区是零和的:前缀缓存占的显存是从并发请求的 KV 空间里切出来的,容量规划要把两者放在同一张预算表上权衡,整体框架见 KV cache 管理方法学全景 和 服务容量规划。
把四张图和两个读图结论收成一张诊断速查表,值班时直接对照:
| 观测组合 | 诊断 | 处方 |
|---|---|---|
| 命中率尚可 被驱逐节点平均长度偏大 重建算力占比超 15% | 驱逐策略在杀大节点 | 上成本加权或加大 gamma |
| 命中率低 驱逐事件稀疏 被驱逐节点普遍很小 | 容量装不下工作集 | 加容量或缩准入 |
| 命中率缓慢爬升后长期横盘低于理论曲线两成以上 | 策略兑现率低 | 检查权重标定与路由粘性 |
| 模板改版后命中率迟迟不回升 | 死前缀清不出去 | 检查 LFU 老化机制 |
埋点清单收尾:缓存命中率(按请求数和按命中 token 数两个口径都要)、驱逐事件速率与被驱逐节点的 token 长度分布、驱逐后的重建 prefill 总量、分租户命中率。这四个指标一个周期跑下来,驱逐策略该不该换、容量该不该加,都是读图题而不是玄学题。
给两个典型的读图结论做示范。场景一:命中率尚可,但「驱逐节点的平均 token 长度」持续偏高、重建 prefill 总量占 prefill 池算力的比例超过 15%——这是驱逐策略在杀大节点的信号,上成本加权或加大 γ,容量本身没问题。场景二:命中率低、驱逐事件稀疏、被驱逐节点普遍很小——这是容量真不够,缓存连工作集都装不下,策略再聪明也只能在矮子里拔将军,该加容量或缩准入。两个场景的处方完全相反,靠拍脑袋区分不了,全靠这四张图。另外多提一句版本联动:system prompt 模板改版(产品侧常见操作)会让旧模板前缀一夜之间全部变成死重,驱逐策略要能在几个小时内把它们清出去——这是 LFU 不带老化时最典型的翻车现场,也是检验老化机制是否生效的天然实验。
这一篇在知识体系里的位置
本篇是前缀缓存专题的策略篇:机制与收益在 前缀缓存与 prompt 复用,树结构实现在 SGLang Radix 前缀缓存,同属「缓存内取舍」的 KV cache 驱逐 H2O 策略 处理的是单请求内部 token 的取舍(注意两者别混淆),路由侧联动在 LLM 路由负载均衡,全局容量框架在 KV cache 管理方法学全景。
总结
前缀缓存的驱逐在一棵基数树上进行,结构先立了三条规矩——只驱逐零引用叶子、引用计数优先于一切策略、驱逐粒度变长要按 token 双重记账;策略选型上 LRU 起步吃时间局部性、LFU 加老化吃长期热度、成本加权把重建 prefill 的算力代价计入驱逐得分,是混合长度 RAG 与 Agent 负载的正解;多租户共享时全局命中率和租户公平性冲突,按计费模式在配额隔离、加权驱逐、优先级分层三档里选;容量规划用「前缀频率排序的累计曲线」提前估算命中率,Zipf 形态决定了缓存存在性价比拐点,实测命中率持续低于理论曲线时该换的是驱逐策略而不是加容量。