LMCache Blend Index 深度解析基于 Key Directory 派生的全舰队 CacheBlend 片段查找索引【免费下载链接】LMCacheLMCache: Supercharge Your LLM with the Fastest KV Cache Layer项目地址: https://gitcode.com/GitHub_Trending/lm/LMCache本文档完整讲解 LMCache MP Coordinator 中blend_index模块的设计与实现。它以 Key Directory 的 token 绑定为唯一数据源用滚动哈希 占用过滤器 token 级验证回答给定一段请求 token其中包含哪些已缓存的 chunk、各自位于何处这一问题支撑全舰队fleet-wideCacheBlend 复用。读完本文你将掌握该索引的启用条件、命名空间隔离模型、数据结构与匹配流程、生命周期管理、HTTP 接口契约及其边界条件。一、Blend Index 是什么片段查找的派生视图在 LMCache 的 MP多进程协调器架构中Key Directory键目录见 key_directory.md维护着哪个 ObjectKey 被哪个实例存放在了哪个层级/后端的全舰队视图。它提供的前缀查找prefix lookup只能回答从位置 0 开始、与请求前缀完全一致的内容缓存于何处。而blend_indexblend index混合缓存索引是前缀查找的片段fragment对应物目录文档中将其称为fragment tokens → keys。它回答的问题是给定一个请求的 token 序列其中包含哪些已缓存的 chunk以及这些 chunk 分别位于序列的什么位置这正是全舰队 CacheBlend 复用背后的查询需求——当请求由分布在舰队任意节点上的文档片段拼装而成时必须在任意偏移处发现这些缓存。1.1 核心定位派生视图而非第二数据源blend index 是目录 token 绑定的派生视图derived view而不是第二个事实来源绑定binding由缓存事件流cache-event stream创建和销毁索引只是跟随这些事件更新没有任何东西直接向索引发布数据实现上它位于 blend_index.py而模块 docstring 明确指出它answers the blend-style fragment lookup并引用了本文档作为设计依据。1.2 关键开关--enable-blend-lookupblend index默认关闭。只有以--enable-blend-lookup启动协调器时才会启用此时启动流程调用KeyDirectory.enable_blend_lookup见 key_directory.py。在此之前不对任何 chunk 内容做哈希blend_match返回空结果不运行 CacheBlend 的舰队不为此付出任何代价零开销设计启用前已存储的 chunk不会被追溯索引不回溯建索引。1.3UNKNOWN_TOKEN_OFFSET无存储位置则不入索引一个token_offset为UNKNOWN_TOKEN_OFFSET在 api.py 中定义为-1与真实位置 0 严格区分的条目会填充其绑定的内容但不会被索引没有存储位置匹配结果就无法告诉调用方从哪个位置做 re-RoPE重旋转位置编码错误的位置会产出错误的 KV而不是一次 miss——因此宁可不匹配。注意UNKNOWN_TOKEN_OFFSET -1与 0 的区别是有意为之——0 是真实位置chunk 位于序列开头。若把未上报的位置当作 0会把每个 chunk 都置于序列起点从而从错误的源位置 re-RoPE 复用 KV。二、为什么它取代独立的 blend 目录standalone blend directory旧设计blend_directory.pyPOST /blend/fingerprints从独立的发布路径维护一张全舰队表blend 服务器在每次 store 时驱动发布。该表每个 chunk 只保存一个 64 位指纹这迫使旧设计在三方面妥协而新的 key directory 恰好消除了它们维度独立指纹表blend index数据来源每个 blend store 各自发布 RPC同一条缓存事件流匹配依据信任 64 位哈希哈希只用于发现token 用于验证碰撞后果浪费一次预取prefetch候选被跳过零代价淘汰惰性墓碑容忍陈旧条目精确与绑定同生命周期放置信息未知预取是盲目的已知peer L1 与共享 L2身份一个 chunk 哈希无命名空间概念每个 chunk 上按命名空间记录声明代价是协调器内存验证需要 token 常驻内存复杂度为O(m)而非O(m/C)m 为存储 token 数C 为 chunk 大小。关于使这一代价可负担的表示方式见 key_directory.md 的 Token index 一节token 以只读uint32numpy 数组保存每个 256-token chunk 约 1 KB对比tuple[int, ...]装箱整数约 10 KB 的开销。三、身份与作用域内容为键身份随占用者occupants而行3.1 仅以内容指纹为键条目只以内容指纹为键——单个 chunk token 的 64 位多项式哈希POLY_BASE舰队常量见 blend_index.pynp.uint64(0x9E3779B97F4A7C15)。键中无前缀概念。chunk_hash是前缀链接prefix-chained的因此同一段文本在不同前缀之后存储会得到两个不同的 chunk两个 chunk 都挂载到同一个内容条目上各自带自己的token_offset所以淘汰其中一个另一个仍然可被发现。每个占用者携带其命名空间。一个chunk_hash只命名内容与前缀——决定这是谁的 KV的所有信息都位于其旁的ObjectKey上。因此每个占用者都记录存储它的所有BlendNamespace匹配结果只提供给属于其中一个命名空间的请求方。测试 test_blend_index.py 中的test_identical_content_under_two_prefixes_survives_one_eviction第 165 行起验证了这一行为相同内容以两个 chunk hashA、B存储后移除 A 的声明B 依然可匹配。3.2 命名空间BlendNamespaceBlendNamespace定义于 api.py是三元组BlendNamespace (model_name, cache_salt, world_size)这正是ipc_key_to_object_keys读取、用于把chunk_hash展开为ObjectKey的三个字段model_nameKV 所属模型cache_salt应用于 key 的按租户隔离盐world_size并行世界大小TP × PP决定 rank 扇出fan-out。在存储侧命名空间直接从 key 本身推导world_size取自打包在kv_rank顶字节的ComputeKVRankBlendNamespace.from_object_key通过ObjectKey.WorldSizeFromKVRank解析在查询侧它随请求到达。object_group_id被刻意排除在外对象组object groups划分的是服务器自身的布局而非舰队因此 blend 服务器绝不能启用--separate-object-groups源码 api.py 明确注释了这一约束。3.3 作用域不损失合法复用命名空间的每个维度本来都是请求方自身 key 展开时会 miss 的维度另一个模型的 KV 不可互换另一个租户的 salt 按设计隔离另一种并行配置对 head 的分片不同。作用域移除的是无命名空间表的两个真实缺陷缺陷无命名空间表带声明claims匹配到任何请求方 key 都够不着的内容照样返回预取时确认 miss烧掉一个 blend 槽位永不提供请求方自己的 chunk 被另一个命名空间的遮挡丢失命中——每个内容只返回一个占用者而它可能是别人的找到遍历时跳过本命名空间不持有的占用者第二个缺陷消耗的是复用率而非工作量同一文档在不同前缀下缓存是不同的chunk_hash即第二个占用者若只返回第一个会静默丢弃它。旧设计曾以首个存储者的租户会被钉死其他人永远无法匹配自己的副本为由拒绝过滤。这源于把内容条目当作单租户的假设——内容条目天然是多租户的。正确做法是按成员关系membership过滤——即所有存储过该 chunk 的命名空间——而非按首个写入者身份过滤。3.4 残留问题Residual单个命名空间内的 rank 与对象组不会被单独跟踪一个仅由某 world size 的部分 rank 存储的 chunk仍会匹配并在 key 展开时确认与旧行为一致。四、数据结构与召回recall特性4.1 两层结构_contents : dict[fingerprint - _Entry { token_ids, occupants{} }] # 权威层 _slots : uint8[2^k] 占用过滤器任何指纹落入的槽位置 1occupants把chunk_hash映射到{ token_offset, namespaces }按首次索引顺序排列——通常恰好一个 chunk、由一个命名空间声明。两个租户在完全相同的前缀下存储的 chunk 是一个占用者带两个声明claims因此 token 只保存一份。代价是每个(chunk, namespace)对一个小元组在stats()中报告为num_claims。4.2 匹配流程先过滤、再解析、最后验证一次匹配的执行顺序对应BlendIndex.matchblend_index.py在查询上滚动一个chunk_size窗口的哈希rolling_hash_windows_numba每probe_stride个位置做一次向量化 gather查询_slots占用过滤器少数存活者survivors通过_contents精确解析对每个存活者选出请求方命名空间声明的占用者只有在此时才把查询窗口与entry.token_ids做逐 token 验证np.array_equal验证通过才接受。这个顺序对成本至关重要集合成员测试远比比较整个窗口便宜因此请求方取不到的内容在比较之前就被丢弃而不是之后——在一个租户大多缓存不同文档的舰队上这正是最常见的情况。文档记录了一个量化案例在 50 租户、内容与请求方完全不相交的索引上这种重排把窗口比较从 100 次降到 1 次得到相同结果。seen已见集合只在验证之后标记因此指纹碰撞不会消耗一个 chunk 的一次匹配机会。4.3 两种删除作用于不同层级remove_claim删除一个持有者chunk 为其余持有者继续存活DELETE路径remove_chunk在一次锁获取内删除 chunk 及其全部声明re-store 换内容路径。若改为按命名空间退役会出现一个窗口期match只持有索引锁可能在某个尚未移除的命名空间下仍找到该 chunk而此时其内容已经变化导致把新内容的 KV re-RoPE 到旧内容的位置上。4.4 过滤器刻意不携带身份——这是召回完整的原因过滤器_slots刻意不存储身份——只有这里落有东西。这正是召回完整的关键两个指纹共享一个槽位时两者都通过过滤器字典分别正确解析而直地址表slot → entry本地 matcher 与旧 blend 目录采用的方式会让后写入者把先写入者从槽位中驱逐使后者永不可匹配。文档给出了该设计自身增长阈值下的量化数据负载因子处于 12.5%–25% 时6%–12% 的被索引 chunk 静默不可匹配——在 60 条目的表上实测丢失 121 个参考匹配中的 7 个。既然召回即复用recall is reuse过滤器设计用一次罕见的多余字典查找换来了全部复用。因此负载因子只是误报率_TABLE_GROWTH16把它控制在约 6% 以下每个被索引 chunk 约花费 16 字节每槽一字节。4.5 验证使一切安全指纹碰撞意味着第二个内容永远不会被添加因此它保持不可发现——绝不会被错误匹配测试test_near_miss_content_is_rejected验证了一个 token 不同的近邻窗口被拒绝。五、生命周期完全由 Key Directory 的绑定生命周期驱动目录事件索引动作带token_ids的STOREadd(tokens, chunk_hash, token_offset, ns)首次填充绑定内容的STORE对绑定上的每个命名空间执行add不同内容的重复STOREremove_chunk然后按命名空间重新add某命名空间最后一个 key 被DELETEremove_claim(tokens, chunk_hash, ns)chunk 全部放置被DELETE最后一次remove_claim顺带删除占用者fence_instance重启 / 注销对每个被丢弃的 chunk 执行remove_claim命名空间来自事件携带的 key因此无需发布任何新内容。稳态存储路径每个条目只为一个命名空间声明只有两行内容变更会遍历绑定的 keys因此按 rank 的存储不会每个 rank 都重新哈希内容。关键源码佐证key_directory.py_claim_binding当 blend lookup 关闭、绑定尚无内容、或没有存储位置UNKNOWN_TOKEN_OFFSET时是 no-op内容长度非舰队chunk_size的也不入索引blend_index.py 对此记录 warning 并返回。5.1 无 token 的 STORE 与已知内容的 key一个STORE未携带 tokenemitter 的受限缓存已淘汰该 chunk不索引——一次查找 miss由该 chunk 下一次带戳的 store 修复一个key到达、未带 token但其 chunk 内容已知立即为它的命名空间声明该 chunk——因此第二个租户存储舰队已持有的内容时无需等待重新 store 即可匹配内容长度不等于舰队chunk_size的同样不入索引它永远无法填满一个chunk_size匹配窗口。上述两者都只记日志绝不视为错误。5.2 锁顺序索引持有自己的锁且绝不回调目录因此唯一的锁顺序是directory → index。match单独持有索引锁——片段查询处于服务路径serving path上与目录其余部分不同因此不会在事件应用之后串行排队。六、HTTP 接口POST /directory/blend-lookup端点定义于 directory_api.py请求模型见 schemas.py。6.1 请求POST /directory/blend-lookup接收tokens_b64base64 编码的小端uint32token 数组——比 JSON 列表小约 1.4 倍且一次np.frombuffer即可解码encode_tokens/decode_tokensschemas.py调用方的model_name、world_size、cache_salt。这三字段与/directory/lookup的 token 形式携带的字段相同但原因不同前缀查找用它们构建要查询的 keys片段匹配已直接命名一个存储的chunk_hash用它们保持在调用方可检索的命名空间内。两种 token 编码目前刻意不同——片段查询是请求的完整序列紧凑形式物有所值——两个端点未来可自由趋同。6.2 响应返回匹配列表(chunk_hash, old_st, cur_st)old_st——chunk 在其存储时所属序列中的位置re-RoPE 的源cur_st——其内容在查询中被发现的位置re-RoPE 的目标。匹配按cur_st升序排列每个 chunk 至多一个匹配。它们可能在查询中重叠——去重是按 chunk 而非按查询区间——两个覆盖相同 token 的匹配不能同时 scatter散射因此调用方自行应用重叠消解blend 使用最左贪心leftmost-greedy。滚动哈希遍历整个查询因此处理器把它放进线程asyncio.to_thread运行而不是占用事件循环。6.3 客户端BlendCoordinatorClientMP 服务器侧客户端位于 blend_client.py只查询不发布——协调器匹配的 chunk 来自舰队缓存事件流客户端无发布路径采用 submit-once / poll-on-recall 模式submit_match/poll_match/take_match后台守护线程 线程池并发执行往返match_concurrency默认 8request_timeout与match_budget_s默认 2.0 秒maybe_create空 URL 返回Noneblend 模块退化为纯本地匹配任何异常按 best-effort 处理查询失败退化为 local-only空结果。七、匹配结果如何接入 CacheBlend 统一查找片段查找在 MP 服务器侧的消费流程cb_unified_lookup见 lookup.py首次调用同时运行本地 matcher 与提交协调器查询请求 token并启动每次查找的墙钟截止时间match_budget_s来自 MP 服务器的--coordinator-blend-timeout前缀解析后、稀疏预取前轮询协调器pending 则 defer截止时间到则放弃该次查找仅本地合并两路结果保留前缀覆盖之外的匹配做最左贪心重叠去重_non_overlapping_after_prefixlookup.py——先过滤前缀覆盖再按cur_st排序、重叠时早者胜提交一次稀疏预取分类、检索、re-RoPE。为什么叠加而非仅舰队舰队索引不是本地表的保证超集——它由 best-effort 缓存事件驱动一次被丢弃的 flush 或 emitter 受限缓存中淘汰的 token 绑定都会让本服务器持有的 chunk在全舰队不可匹配。两者并行使召回成为并集绝不差于任何一方单独运行。协调器匹配被转换为CBMatchResult_build_global_segmentslookup.py——hash即协调器的chunk_hash因此它们走与本地匹配完全相同的稀疏预取 分类 检索 re-RoPE 路径出现在CBUnifiedLookupResult.non_prefix_segments中无独立global_segments字段、无协议变更。获取来源稀疏预取扇出到每个已注册的 L2 适配器P2P peer 适配器也包括在内——匹配的 chunk 从持有它的任一层级加载共享 L2或经 RDMA 的 peer L1。peer 的p2p_lookup_and_lock锁定稀疏 key 集合允许间隙服务端从不在自己的 L2 递归skip_l2对稀疏查找同样成立。由于 chunk 无论是否 L2 卸载都随 store 事件到达目录仅驻留在存储者 L1 的 chunk 全舰队可匹配。7.1 启用门槛Gating舰队匹配要求同时满足--coordinator-url或LMCACHE_COORDINATOR_URL且--coordinator-event-reporting或LMCACHE_COORDINATOR_EVENT_REPORTING默认关闭。有 URL 但无事件上报时协调器没有可匹配的缓存状态每次查询都返回空——server.py 启动时将其视为未配置并记录警告而不是为每次查找白付一次往返。由于匹配是叠加的此情况下 blend 仍可本地工作——只是缺少舰队支路。八、刻意排除的范围Out of scope亚 chunk 粒度复用是整 chunk 的且仅当内容 chunk 相位对齐时发生——与 blend 今日使用的算法一致。块级与 token 级细化minimizer 锚点、seed-and-extend以协调器内存换取更细、偏移鲁棒的复用演进对比表见 blend 设计笔记。放置感知排序匹配尚不优先选择在 L1 持有 chunk 的 peer 而非共享 L2 副本尽管目录两者都知道。超越绑定的活性声明只说明某实例在该命名空间存储过该 chunk不代表字节此刻可达——目录是最终一致的匹配仍是持有者需要验证的提示。基于放置过滤可收紧这一点代价是服务路径上获取目录锁。九、源码与测试导航设计文档blend_index.md本文主题、blend_lookup.md端到端能力与演进、views/key_directory.mdToken index 一节核心实现blend_index.pyBlendIndex、blend_client.pyBlendCoordinatorClient目录集成views/key_directory.pyenable_blend_lookup、_claim_binding、_remove_token_binding、blend_matchHTTP 层http_apis/directory_api.py/directory/blend-lookup、schemas.pyBlendLookupRequest、BlendMatchModel、token 编解码契约词汇api.pyBlendNamespace、BlendMatch、UNKNOWN_TOKEN_OFFSET配置config.pyenable_blend_lookup默认False、blend_probe_stride默认1、chunk_size默认256匹配消费multiprocess/modules/blend/lookup.pycb_unified_lookup、_non_overlapping_after_prefix、_build_global_segments测试test_blend_index.py发现、验证、命名空间作用域、召回与淘汰契约、test_blend_client.py、test_directory_api.pyHTTP 端点、test_key_directory.pyCLI 侧--enable-blend-lookup开关的解析由 tests/cli/commands/test_coordinator.py 覆盖验证。十、小结Blend index 是 LMCache 协调器在控制面目录之上构建的、面向服务路径的片段查找能力一份数据流缓存事件同时喂养放置目录与内容指纹索引匹配走占用过滤器 → 字典解析 → 命名空间裁剪 → token 精确验证的四级流水线以约 16 字节/chunk 与 ~6% 误报率换回完整召回声明式命名空间隔离让一个索引服务整个舰队而不错配租户关闭开关即零成本。它是理解 LMCache 全舰队 CacheBlend 复用链路store → 事件流 → 目录 → 指纹索引 → 统一查找 → 稀疏预取 → re-RoPE的关键一环。【免费下载链接】LMCacheLMCache: Supercharge Your LLM with the Fastest KV Cache Layer项目地址: https://gitcode.com/GitHub_Trending/lm/LMCache创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LMCache Blend Index 深度解析基于 Key Directory 派生的全舰队 CacheBlend 片段查找索引【免费下载链接】LMCacheLMCache: Supercharge Your LLM with the Fastest KV Cache Layer项目地址: https://gitcode.com/GitHub_Trending/lm/LMCache本文档完整讲解 LMCache MP Coordinator 中blend_index模块的设计与实现。它以 Key Directory 的 token 绑定为唯一数据源用滚动哈希 占用过滤器 token 级验证回答给定一段请求 token其中包含哪些已缓存的 chunk、各自位于何处这一问题支撑全舰队fleet-wideCacheBlend 复用。读完本文你将掌握该索引的启用条件、命名空间隔离模型、数据结构与匹配流程、生命周期管理、HTTP 接口契约及其边界条件。一、Blend Index 是什么片段查找的派生视图在 LMCache 的 MP多进程协调器架构中Key Directory键目录见 key_directory.md维护着哪个 ObjectKey 被哪个实例存放在了哪个层级/后端的全舰队视图。它提供的前缀查找prefix lookup只能回答从位置 0 开始、与请求前缀完全一致的内容缓存于何处。而blend_indexblend index混合缓存索引是前缀查找的片段fragment对应物目录文档中将其称为fragment tokens → keys。它回答的问题是给定一个请求的 token 序列其中包含哪些已缓存的 chunk以及这些 chunk 分别位于序列的什么位置这正是全舰队 CacheBlend 复用背后的查询需求——当请求由分布在舰队任意节点上的文档片段拼装而成时必须在任意偏移处发现这些缓存。1.1 核心定位派生视图而非第二数据源blend index 是目录 token 绑定的派生视图derived view而不是第二个事实来源绑定binding由缓存事件流cache-event stream创建和销毁索引只是跟随这些事件更新没有任何东西直接向索引发布数据实现上它位于 blend_index.py而模块 docstring 明确指出它answers the blend-style fragment lookup并引用了本文档作为设计依据。1.2 关键开关--enable-blend-lookupblend index默认关闭。只有以--enable-blend-lookup启动协调器时才会启用此时启动流程调用KeyDirectory.enable_blend_lookup见 key_directory.py。在此之前不对任何 chunk 内容做哈希blend_match返回空结果不运行 CacheBlend 的舰队不为此付出任何代价零开销设计启用前已存储的 chunk不会被追溯索引不回溯建索引。1.3UNKNOWN_TOKEN_OFFSET无存储位置则不入索引一个token_offset为UNKNOWN_TOKEN_OFFSET在 api.py 中定义为-1与真实位置 0 严格区分的条目会填充其绑定的内容但不会被索引没有存储位置匹配结果就无法告诉调用方从哪个位置做 re-RoPE重旋转位置编码错误的位置会产出错误的 KV而不是一次 miss——因此宁可不匹配。注意UNKNOWN_TOKEN_OFFSET -1与 0 的区别是有意为之——0 是真实位置chunk 位于序列开头。若把未上报的位置当作 0会把每个 chunk 都置于序列起点从而从错误的源位置 re-RoPE 复用 KV。二、为什么它取代独立的 blend 目录standalone blend directory旧设计blend_directory.pyPOST /blend/fingerprints从独立的发布路径维护一张全舰队表blend 服务器在每次 store 时驱动发布。该表每个 chunk 只保存一个 64 位指纹这迫使旧设计在三方面妥协而新的 key directory 恰好消除了它们维度独立指纹表blend index数据来源每个 blend store 各自发布 RPC同一条缓存事件流匹配依据信任 64 位哈希哈希只用于发现token 用于验证碰撞后果浪费一次预取prefetch候选被跳过零代价淘汰惰性墓碑容忍陈旧条目精确与绑定同生命周期放置信息未知预取是盲目的已知peer L1 与共享 L2身份一个 chunk 哈希无命名空间概念每个 chunk 上按命名空间记录声明代价是协调器内存验证需要 token 常驻内存复杂度为O(m)而非O(m/C)m 为存储 token 数C 为 chunk 大小。关于使这一代价可负担的表示方式见 key_directory.md 的 Token index 一节token 以只读uint32numpy 数组保存每个 256-token chunk 约 1 KB对比tuple[int, ...]装箱整数约 10 KB 的开销。三、身份与作用域内容为键身份随占用者occupants而行3.1 仅以内容指纹为键条目只以内容指纹为键——单个 chunk token 的 64 位多项式哈希POLY_BASE舰队常量见 blend_index.pynp.uint64(0x9E3779B97F4A7C15)。键中无前缀概念。chunk_hash是前缀链接prefix-chained的因此同一段文本在不同前缀之后存储会得到两个不同的 chunk两个 chunk 都挂载到同一个内容条目上各自带自己的token_offset所以淘汰其中一个另一个仍然可被发现。每个占用者携带其命名空间。一个chunk_hash只命名内容与前缀——决定这是谁的 KV的所有信息都位于其旁的ObjectKey上。因此每个占用者都记录存储它的所有BlendNamespace匹配结果只提供给属于其中一个命名空间的请求方。测试 test_blend_index.py 中的test_identical_content_under_two_prefixes_survives_one_eviction第 165 行起验证了这一行为相同内容以两个 chunk hashA、B存储后移除 A 的声明B 依然可匹配。3.2 命名空间BlendNamespaceBlendNamespace定义于 api.py是三元组BlendNamespace (model_name, cache_salt, world_size)这正是ipc_key_to_object_keys读取、用于把chunk_hash展开为ObjectKey的三个字段model_nameKV 所属模型cache_salt应用于 key 的按租户隔离盐world_size并行世界大小TP × PP决定 rank 扇出fan-out。在存储侧命名空间直接从 key 本身推导world_size取自打包在kv_rank顶字节的ComputeKVRankBlendNamespace.from_object_key通过ObjectKey.WorldSizeFromKVRank解析在查询侧它随请求到达。object_group_id被刻意排除在外对象组object groups划分的是服务器自身的布局而非舰队因此 blend 服务器绝不能启用--separate-object-groups源码 api.py 明确注释了这一约束。3.3 作用域不损失合法复用命名空间的每个维度本来都是请求方自身 key 展开时会 miss 的维度另一个模型的 KV 不可互换另一个租户的 salt 按设计隔离另一种并行配置对 head 的分片不同。作用域移除的是无命名空间表的两个真实缺陷缺陷无命名空间表带声明claims匹配到任何请求方 key 都够不着的内容照样返回预取时确认 miss烧掉一个 blend 槽位永不提供请求方自己的 chunk 被另一个命名空间的遮挡丢失命中——每个内容只返回一个占用者而它可能是别人的找到遍历时跳过本命名空间不持有的占用者第二个缺陷消耗的是复用率而非工作量同一文档在不同前缀下缓存是不同的chunk_hash即第二个占用者若只返回第一个会静默丢弃它。旧设计曾以首个存储者的租户会被钉死其他人永远无法匹配自己的副本为由拒绝过滤。这源于把内容条目当作单租户的假设——内容条目天然是多租户的。正确做法是按成员关系membership过滤——即所有存储过该 chunk 的命名空间——而非按首个写入者身份过滤。3.4 残留问题Residual单个命名空间内的 rank 与对象组不会被单独跟踪一个仅由某 world size 的部分 rank 存储的 chunk仍会匹配并在 key 展开时确认与旧行为一致。四、数据结构与召回recall特性4.1 两层结构_contents : dict[fingerprint - _Entry { token_ids, occupants{} }] # 权威层 _slots : uint8[2^k] 占用过滤器任何指纹落入的槽位置 1occupants把chunk_hash映射到{ token_offset, namespaces }按首次索引顺序排列——通常恰好一个 chunk、由一个命名空间声明。两个租户在完全相同的前缀下存储的 chunk 是一个占用者带两个声明claims因此 token 只保存一份。代价是每个(chunk, namespace)对一个小元组在stats()中报告为num_claims。4.2 匹配流程先过滤、再解析、最后验证一次匹配的执行顺序对应BlendIndex.matchblend_index.py在查询上滚动一个chunk_size窗口的哈希rolling_hash_windows_numba每probe_stride个位置做一次向量化 gather查询_slots占用过滤器少数存活者survivors通过_contents精确解析对每个存活者选出请求方命名空间声明的占用者只有在此时才把查询窗口与entry.token_ids做逐 token 验证np.array_equal验证通过才接受。这个顺序对成本至关重要集合成员测试远比比较整个窗口便宜因此请求方取不到的内容在比较之前就被丢弃而不是之后——在一个租户大多缓存不同文档的舰队上这正是最常见的情况。文档记录了一个量化案例在 50 租户、内容与请求方完全不相交的索引上这种重排把窗口比较从 100 次降到 1 次得到相同结果。seen已见集合只在验证之后标记因此指纹碰撞不会消耗一个 chunk 的一次匹配机会。4.3 两种删除作用于不同层级remove_claim删除一个持有者chunk 为其余持有者继续存活DELETE路径remove_chunk在一次锁获取内删除 chunk 及其全部声明re-store 换内容路径。若改为按命名空间退役会出现一个窗口期match只持有索引锁可能在某个尚未移除的命名空间下仍找到该 chunk而此时其内容已经变化导致把新内容的 KV re-RoPE 到旧内容的位置上。4.4 过滤器刻意不携带身份——这是召回完整的原因过滤器_slots刻意不存储身份——只有这里落有东西。这正是召回完整的关键两个指纹共享一个槽位时两者都通过过滤器字典分别正确解析而直地址表slot → entry本地 matcher 与旧 blend 目录采用的方式会让后写入者把先写入者从槽位中驱逐使后者永不可匹配。文档给出了该设计自身增长阈值下的量化数据负载因子处于 12.5%–25% 时6%–12% 的被索引 chunk 静默不可匹配——在 60 条目的表上实测丢失 121 个参考匹配中的 7 个。既然召回即复用recall is reuse过滤器设计用一次罕见的多余字典查找换来了全部复用。因此负载因子只是误报率_TABLE_GROWTH16把它控制在约 6% 以下每个被索引 chunk 约花费 16 字节每槽一字节。4.5 验证使一切安全指纹碰撞意味着第二个内容永远不会被添加因此它保持不可发现——绝不会被错误匹配测试test_near_miss_content_is_rejected验证了一个 token 不同的近邻窗口被拒绝。五、生命周期完全由 Key Directory 的绑定生命周期驱动目录事件索引动作带token_ids的STOREadd(tokens, chunk_hash, token_offset, ns)首次填充绑定内容的STORE对绑定上的每个命名空间执行add不同内容的重复STOREremove_chunk然后按命名空间重新add某命名空间最后一个 key 被DELETEremove_claim(tokens, chunk_hash, ns)chunk 全部放置被DELETE最后一次remove_claim顺带删除占用者fence_instance重启 / 注销对每个被丢弃的 chunk 执行remove_claim命名空间来自事件携带的 key因此无需发布任何新内容。稳态存储路径每个条目只为一个命名空间声明只有两行内容变更会遍历绑定的 keys因此按 rank 的存储不会每个 rank 都重新哈希内容。关键源码佐证key_directory.py_claim_binding当 blend lookup 关闭、绑定尚无内容、或没有存储位置UNKNOWN_TOKEN_OFFSET时是 no-op内容长度非舰队chunk_size的也不入索引blend_index.py 对此记录 warning 并返回。5.1 无 token 的 STORE 与已知内容的 key一个STORE未携带 tokenemitter 的受限缓存已淘汰该 chunk不索引——一次查找 miss由该 chunk 下一次带戳的 store 修复一个key到达、未带 token但其 chunk 内容已知立即为它的命名空间声明该 chunk——因此第二个租户存储舰队已持有的内容时无需等待重新 store 即可匹配内容长度不等于舰队chunk_size的同样不入索引它永远无法填满一个chunk_size匹配窗口。上述两者都只记日志绝不视为错误。5.2 锁顺序索引持有自己的锁且绝不回调目录因此唯一的锁顺序是directory → index。match单独持有索引锁——片段查询处于服务路径serving path上与目录其余部分不同因此不会在事件应用之后串行排队。六、HTTP 接口POST /directory/blend-lookup端点定义于 directory_api.py请求模型见 schemas.py。6.1 请求POST /directory/blend-lookup接收tokens_b64base64 编码的小端uint32token 数组——比 JSON 列表小约 1.4 倍且一次np.frombuffer即可解码encode_tokens/decode_tokensschemas.py调用方的model_name、world_size、cache_salt。这三字段与/directory/lookup的 token 形式携带的字段相同但原因不同前缀查找用它们构建要查询的 keys片段匹配已直接命名一个存储的chunk_hash用它们保持在调用方可检索的命名空间内。两种 token 编码目前刻意不同——片段查询是请求的完整序列紧凑形式物有所值——两个端点未来可自由趋同。6.2 响应返回匹配列表(chunk_hash, old_st, cur_st)old_st——chunk 在其存储时所属序列中的位置re-RoPE 的源cur_st——其内容在查询中被发现的位置re-RoPE 的目标。匹配按cur_st升序排列每个 chunk 至多一个匹配。它们可能在查询中重叠——去重是按 chunk 而非按查询区间——两个覆盖相同 token 的匹配不能同时 scatter散射因此调用方自行应用重叠消解blend 使用最左贪心leftmost-greedy。滚动哈希遍历整个查询因此处理器把它放进线程asyncio.to_thread运行而不是占用事件循环。6.3 客户端BlendCoordinatorClientMP 服务器侧客户端位于 blend_client.py只查询不发布——协调器匹配的 chunk 来自舰队缓存事件流客户端无发布路径采用 submit-once / poll-on-recall 模式submit_match/poll_match/take_match后台守护线程 线程池并发执行往返match_concurrency默认 8request_timeout与match_budget_s默认 2.0 秒maybe_create空 URL 返回Noneblend 模块退化为纯本地匹配任何异常按 best-effort 处理查询失败退化为 local-only空结果。七、匹配结果如何接入 CacheBlend 统一查找片段查找在 MP 服务器侧的消费流程cb_unified_lookup见 lookup.py首次调用同时运行本地 matcher 与提交协调器查询请求 token并启动每次查找的墙钟截止时间match_budget_s来自 MP 服务器的--coordinator-blend-timeout前缀解析后、稀疏预取前轮询协调器pending 则 defer截止时间到则放弃该次查找仅本地合并两路结果保留前缀覆盖之外的匹配做最左贪心重叠去重_non_overlapping_after_prefixlookup.py——先过滤前缀覆盖再按cur_st排序、重叠时早者胜提交一次稀疏预取分类、检索、re-RoPE。为什么叠加而非仅舰队舰队索引不是本地表的保证超集——它由 best-effort 缓存事件驱动一次被丢弃的 flush 或 emitter 受限缓存中淘汰的 token 绑定都会让本服务器持有的 chunk在全舰队不可匹配。两者并行使召回成为并集绝不差于任何一方单独运行。协调器匹配被转换为CBMatchResult_build_global_segmentslookup.py——hash即协调器的chunk_hash因此它们走与本地匹配完全相同的稀疏预取 分类 检索 re-RoPE 路径出现在CBUnifiedLookupResult.non_prefix_segments中无独立global_segments字段、无协议变更。获取来源稀疏预取扇出到每个已注册的 L2 适配器P2P peer 适配器也包括在内——匹配的 chunk 从持有它的任一层级加载共享 L2或经 RDMA 的 peer L1。peer 的p2p_lookup_and_lock锁定稀疏 key 集合允许间隙服务端从不在自己的 L2 递归skip_l2对稀疏查找同样成立。由于 chunk 无论是否 L2 卸载都随 store 事件到达目录仅驻留在存储者 L1 的 chunk 全舰队可匹配。7.1 启用门槛Gating舰队匹配要求同时满足--coordinator-url或LMCACHE_COORDINATOR_URL且--coordinator-event-reporting或LMCACHE_COORDINATOR_EVENT_REPORTING默认关闭。有 URL 但无事件上报时协调器没有可匹配的缓存状态每次查询都返回空——server.py 启动时将其视为未配置并记录警告而不是为每次查找白付一次往返。由于匹配是叠加的此情况下 blend 仍可本地工作——只是缺少舰队支路。八、刻意排除的范围Out of scope亚 chunk 粒度复用是整 chunk 的且仅当内容 chunk 相位对齐时发生——与 blend 今日使用的算法一致。块级与 token 级细化minimizer 锚点、seed-and-extend以协调器内存换取更细、偏移鲁棒的复用演进对比表见 blend 设计笔记。放置感知排序匹配尚不优先选择在 L1 持有 chunk 的 peer 而非共享 L2 副本尽管目录两者都知道。超越绑定的活性声明只说明某实例在该命名空间存储过该 chunk不代表字节此刻可达——目录是最终一致的匹配仍是持有者需要验证的提示。基于放置过滤可收紧这一点代价是服务路径上获取目录锁。九、源码与测试导航设计文档blend_index.md本文主题、blend_lookup.md端到端能力与演进、views/key_directory.mdToken index 一节核心实现blend_index.pyBlendIndex、blend_client.pyBlendCoordinatorClient目录集成views/key_directory.pyenable_blend_lookup、_claim_binding、_remove_token_binding、blend_matchHTTP 层http_apis/directory_api.py/directory/blend-lookup、schemas.pyBlendLookupRequest、BlendMatchModel、token 编解码契约词汇api.pyBlendNamespace、BlendMatch、UNKNOWN_TOKEN_OFFSET配置config.pyenable_blend_lookup默认False、blend_probe_stride默认1、chunk_size默认256匹配消费multiprocess/modules/blend/lookup.pycb_unified_lookup、_non_overlapping_after_prefix、_build_global_segments测试test_blend_index.py发现、验证、命名空间作用域、召回与淘汰契约、test_blend_client.py、test_directory_api.pyHTTP 端点、test_key_directory.pyCLI 侧--enable-blend-lookup开关的解析由 tests/cli/commands/test_coordinator.py 覆盖验证。十、小结Blend index 是 LMCache 协调器在控制面目录之上构建的、面向服务路径的片段查找能力一份数据流缓存事件同时喂养放置目录与内容指纹索引匹配走占用过滤器 → 字典解析 → 命名空间裁剪 → token 精确验证的四级流水线以约 16 字节/chunk 与 ~6% 误报率换回完整召回声明式命名空间隔离让一个索引服务整个舰队而不错配租户关闭开关即零成本。它是理解 LMCache 全舰队 CacheBlend 复用链路store → 事件流 → 目录 → 指纹索引 → 统一查找 → 稀疏预取 → re-RoPE的关键一环。【免费下载链接】LMCacheLMCache: Supercharge Your LLM with the Fastest KV Cache Layer项目地址: https://gitcode.com/GitHub_Trending/lm/LMCache创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
并仿真+模型导入+SUBCKT (子电路)绘制与使用+特殊器件绘制)
