FreeToken 前缀缓存差分测试套件:radix cache 三兄弟类的参照模型与变异验证
FreeToken 前缀缓存差分测试套件:radix cache 三兄弟类的参照模型与变异验证
导读
FreeToken 的 KV 前缀缓存家族包含三个同源实现——纯 KV 的 RadixPrefixCache、滑动窗口的 SWARadixCache 和 GDN 状态快照的 HybridRadixCache。它们共享同一棵 RadixTreeNode 树与 split_at 分裂语义,却在匹配、插入、加锁、驱逐上各有迥异的“第二币种”规则,任何一处边界条件的偏差都可能导致静默的多余预填充或 KV 泄漏。本指南以 tests/kvcache/radix/README.md 为主干,拆解这套以按页键控的独立参照模型 + 每操作全量不变量电池 + 变异注入评分为核心的测试方法论:读完你将理解这三个缓存的真实差异点、harness 如何做到“期望绝不来自实现自身的账本”,以及为什么 17 个注入回归全部被捕获、8 个按缺陷类别设的门禁全数通过。
三兄弟类:共享一棵树,各持一种“第二币种”
套件覆盖的三种缓存类分别位于三个模块,它们是兄弟类而非继承层级——唯一共享的代码是 RadixTreeNode 与 split_at:
| 类 | 第二币种 | 测试模块(相对仓库根) |
|---|---|---|
RadixPrefixCache |
无(单币种全 KV) | test_plain_radix.py |
SWARadixCache |
滑动窗口(tombstone 标记) | test_swa_radix.py |
HybridRadixCache |
GDN 状态快照(mamba 槽位) | test_hybrid_radix.py |
凡不属于任何单一类的部分统一收在 test_tree_and_harness.py:共享树机制(split_at 的身份语义、key_fn、get_match_len、align_down)只测一次;以及一个 harness 自检——把一个真实缓存包进一个故意损坏的代理,证明不变量电池与参照模型确实会开火(“一个永远不会失败的模型只是装饰品”)。
以源码佐证,节点 RadixTreeNode 正是为三种语义而设计的:除全 KV 的 ref_count 外,mamba_value/mamba_ref_count 承载 GDN 快照币种,swa_tombstone/swa_ref_count/swa_uuid 承载滑动窗口币种,见 python/freetoken/kvcache/radix_cache.py#L17-L46。三种实现各用各的模块:radix_cache.py、swa_radix_cache.py、hybrid_radix_cache.py。
共享树机制:一次测透,三个类共用
split_at 是身份契约,不是结构契约
调用方在分裂前就持有句柄(锁目标、MatchResult 节点、子节点)。因此 split_at 的实现策略是:新建一个节点充当根侧的 prefix,原地把原对象改造成 suffix,这样所有先前发出的句柄——包括树更深处节点的句柄——依然解析到同一批槽位。见 test_tree_and_harness.py#L60-L115 与实现 python/freetoken/kvcache/radix_cache.py#L87-L106。
每个兄弟类存在节点上的字段都有各自的 split 规则,且全部在这一个测试中固定下来:
- 全量锁
ref_count复制到两半(锁覆盖整个节点); - SWA 锁
swa_ref_count复制到两半(窗口覆盖两半),tombstone 复制到两半(“tombstone 覆盖节点全部 token”); - 窗口边界句柄
swa_uuid迁移到根侧 prefix,suffix 置空; - GDN 快照
mamba_value不复制——快照不能分裂,它留在 suffix(其 end boundary 未变); - LRU 时间戳
timestamp由 prefix 继承; - 分裂点必须严格落在节点内部(
0 < pos < length),越界即断言失败。
该测试还验证了重挂接:root -> prefix -> suffix,每一层都以其首页键注册在父节点的 children 映射中。
key_fn:整页做桶,不是按 token
_get_key_fn 是“参照模型按页键控”的根本原因:子节点只注册在其首页下,查询被切到该页为止。page_size = 1 时键是标量,page_size > 1 时键是整页 tuple;尾部 token 一律忽略。由此推出关键后果:两页共享前导 token 也不共享任何树边——按 token 建树会预言一种实际不会发生的共享(并给出错误页的索引)。见 test_tree_and_harness.py#L117-L151,以及 page_blocks 特意构造“共享前导 token 的整页字母表”(driver.py#L84-L90)。
get_match_len 数 token,复用只到整页
get_match_len 统计相等 token 数;而三类的每次树游走都是 align_down(child.get_match_len(...), page_size)——页内一旦分歧,整页作废。page_size 在 {1, 4, 128} 上参数化验证:截断后的 cached_len 恒等于 align_down 的结果(test_tree_and_harness.py#L154-L182)。
Harness 四件套:期望绝不来自实现自身的账本
整个套件最核心的设计原则:没有任何一处用缓存的簿记来决定期望值。四个模块各司其职:
model.py——按页键控的参照模型
参照模型是三个缓存在页粒度上的完整独立重实现。它从不读取实现的计数器或它要预测的节点字段;它从实现那里学到的只有两样:不透明句柄(SWA 的 swa_uuid)和多个等龄 LRU 候选被选中了哪一个(平局是固有的)。
PageTrie用绝对页路径做键:分裂节点不会重命名任何页,只是改变分组,这让页键控既廉价又忠实(model.py#L115-L213);RefModel是单币种RadixPrefixCache,SWAModel增加每节点tomb位(窗口币种不持自有槽位,其 KV 复用整页索引),HybridModel增加每节点可选 GDN 快照槽(model.py#L241-L271 及各子类);- 模型还维护一套分支覆盖率计数器(如
insert.revive_whole、match.windowed_truncation、trim.tombstone),场景测试可以断言自己真的走到了声称要测的分支,例如assert events["insert.revive_whole"] == 1。
adapters.py——协议归一化 + 每操作后的不变量电池
三个缓存的公开 API 在名称、参数列表、返回值形状上各不相同,适配器把它们归一到一个操作词表:match / insert / inc_lock / dec_lock / evict_full / evict_second / trim_head_swa,边界上只流通 list<a href="https://link.gitcode.com/i/e287fc3a406629475ba44f8a355c8ab0" target="_blank">int],张量从不漏进模型。每个操作之后都要跑整套电池([adapters.py#L286-L367):
- 计数器模型:维护中的运行尺寸 vs 从原始节点字段重算的尺寸(
recompute而非维护正是关键——任一侧的增量计数器 bug 都无处藏身); - 槽位守恒:{树中存活} + {已归还} == {已发出},且任何槽位不得同时出现在两个位置——
SlotLedger对双重释放直接抛conservation.*; - 前缀闭包:父链接、首页键注册、页对齐、key/value 长度一致;
- 类自身的
check_integrity; - 与参照模型的逐节点逐字段一致(
model.structure/model.node/model.counters)——回归真正死在这里,(a)–(d) 是更早开火、更快定位的廉价绊线。
driver.py——几何矩阵与 Session
ALL_SPECS 定义 (类 × page_size) 矩阵(driver.py#L77-L81):
- plain:p1 / p4 / p128;
- swa:p1-w4、p4-w8、p128-w128(最后是 DSV4 形态——一页即一窗口,窗口数学退化);
- hybrid:p1 / p4 / p128(p128 被类自身以
CHUNK_SIZE % page_size == 0拒绝,夹具跳过而非静默丢弃,见 hybrid_radix_cache.py#L57-L61)。
Session 把同一操作同时问给缓存与参照模型,逐字段比对,再跑整套电池。do_request 还原真实请求生命周期:match → lock → 扩展+提交 → unlock,这是 harness 产生 reused_len > 0 插入的唯一途径,并守住调度器契约:<a href="https://link.gitcode.com/i/6437dfd247d7e7b31112c3ef954cbe69" target="_blank">0, reused_len) 的槽位本来就是树自己的,缓存既不能释放也不能重新拥有它们([driver.py#L194-L204)。
conftest.py——确定性时钟
任何排序断言都必须使用确定性时钟。 _tree_walk 每次调用只取一次 time.monotonic_ns(),用它给触碰到的每个节点盖章——因此一次调用内的节点天然并列;而真实时钟的精度比一次树游走更粗,会在调用之间也引入并列,使任何 LRU / 驱逐顺序断言在负载机器上变脆弱。确定性时钟把 monotonic_ns 替换为严格递增计数器(从 1_000_000_001 起),并以 autouse 夹具作用域应用于整个包(conftest.py、driver.py#L23-L36)。
每操作后的失败信号:带稳定 tag 的 HarnessFailure
任何 harness 失败都抛 HarnessFailure,携带稳定 tag 指明开火的检查(match.cached_len、conservation.kv、model.evict、insert.matched_len……)以及比较的双方。这让调用方可以区分“同一个 bug”与“别的 bug”;test_tree_and_harness.py 里的四个损坏代理(忘记增长 evictable_size 的插入、漏回收一个叶子 KV 的驱逐、LRU 反转的驱逐、提前一个节点停下的匹配)各自必须以名字与之相符的 tag 被抓,而不是被下游雪崩误抓(test_tree_and_harness.py#L246-L282)。
变异评分:17 个注入回归,17 个被捕获
套件构建时向三个实现逐一注入了 17 个看似合理的回归,结果 17 个全被捕获。其中由命名测试单独承载的 8 变异门禁——按实现缺陷类别各设一个:匹配与插入时的页对齐、索引别名、加锁时的两处尺寸转移、两处窗口安全的边界提交、快照去重——达成 8/8。
最后一个倒下的:>= 与 > 的边界
最后一个被击落的变异是 swa_radix_cache.py:108 处把 match_since_tomb >= sliding_window_size 改成 >(python/freetoken/kvcache/swa_radix_cache.py#L108)。约 8500 次随机运行从未产生反例,曾在此被判定“大概等价”——那是错的。随机化轨迹善于探索交错,却很少精确落在数值边界上;这个 bug 需要恰好一个窗口夹在两个 tombstone 之间的活体运行。
要到达这个形状,两条 tombstone 路径缺一不可,因为任何一条单独都到不了:_stamp_path 会重新盖戳祖先,LRU 永远无法把根侧节点老化到其自身后代之下(头部的 tombstone 只能来自 trim_head_swa);而 evict_swa 直接摘除空闲叶子而非打 tombstone,所以第二个 tombstone 必须是内部节点且其下还有一个活节点。
在 > 语义下,整个匹配塌缩为 0——这是静默的多余预填充,而非错误答案,所以其他测试毫无察觉。test_a_live_run_of_exactly_one_window_between_two_tombstones_is_reusable 将其钉死(test_swa_radix.py#L312-L342);第 129 行的兄弟比较则被 14 个测试共同覆盖。
该测试是回归门禁而非语义的独立证据:参照模型做同样的 >= 选择(run >= self.W),如果规范是 >,两边会同时同意且同时错误。语义来自别处——sglang 逐字节相同的 _match_prefix_helper(其 docstring 把契约写作“大于或等于滑动窗口大小”),以及“恰好 W 的活体运行覆盖一个窗口 W”这一算术事实。另有三处变异在套件构建期被判定为等价:inc_lock 的 not cur.swa_tombstone、evict_swa 的叶子 ref_count == 0、_free_node_mamba 的 mamba_ref_count == 0——它们守卫的状态无法通过公开 API 到达。
场景测试为什么都这么短
每个测试都是命名场景,正文很短是因为检查交给了 harness:每个操作同时问缓存与参照模型、逐字段比对,且 Session.check() 会重跑整套不变量电池。测试自身只额外钉住电池无法表述的类特有契约——例如 plain 类中“分裂不改变 protected 总量”“锁沿根路径向上计数”“驱逐先摘叶子再级联新近暴露的父节点”,以及 insert_prefix 必须复制其存储的索引(调用方复用暂存缓冲区,切片视图会在写入后污染树,见 test_plain_radix.py#L426-L440)。
槽位 id 全局唯一且永不重用,因此每个返回的张量都能回溯到 (path, page),参照模型仅凭公开输出即可维护——这是“期望不读实现账本”得以成立的前提。
运行方式
测试位于 tests/kvcache/radix/ 目录,直接以 pytest 运行即可:
pytest tests/kvcache/radix/ -q
- 单跑某一兄弟类:
pytest tests/kvcache/radix/test_plain_radix.py -q; - 只跑共享机制与 harness 自检:
pytest tests/kvcache/radix/test_tree_and_harness.py -q; - 跑某个几何形状:夹具 id 形如
swa-p4-w8、hybrid-p128,可用-k筛选,例如pytest tests/kvcache/radix/test_swa_radix.py -k "p4"。
hybrid 在 page_size=128 时会被夹具以 CHUNK_SIZE % page_size == 0 不满足为由 skip(快照落在 CHUNK_SIZE=64 边界上),这是类的真实约束而非套件缺陷。
小结
这套测试的价值不在“覆盖了多少行”,而在期望的独立性:参照模型与实现是两个独立产生、逐字段对拍的账本,加上从原始字段重算的计数器、槽位守恒账本与分支覆盖计数器,任何单点增量式簿记 bug 都无处可藏。变异评分进一步证明电池具备失败能力——17/17 的捕获率、8/8 的缺陷类别门禁,以及那个需要精确窗口长度、双 tombstone 路径才能暴露的 >=/> 边界,共同构成了 FreeToken 三个前缀缓存实现的可信护栏。若要继续深入,可从 tests/kvcache/radix/model.py(参照模型)与 tests/kvcache/radix/adapters.py(不变量电池)读起,再对照三个实现模块逐项印证。