尧图网站建设 
Garnet 向量过滤搜索Filtered Vector Search端到端设计解析从内联过滤到零分配 FFI 回调【免费下载链接】garnetGarnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.项目地址: https://gitcode.com/GitHub_Trending/garnet4/garnet导读本文基于 Garnet 仓库中的 filtered-search-design.md 设计文档结合 libs/server/Resp/Vector 下的实际实现代码系统讲解 Garnet 如何在 DiskANN 图索引的相似性搜索VSIM命令族中实现内联元数据过滤在图的遍历过程中实时求值过滤谓词避免先取 K 个再丢弃的后置过滤post-filtering方案带来的过度拉取overfetch与召回损失。读完本文你将掌握过滤表达式如何在 C# 侧被编译成零分配的指令流、二进制属性存储如何把 JSON 解析成本从查询期转移到写入期、RustDiskANN与 C# 之间的 FFI 回调协议如何按候选节点per-candidate工作以及FILTER-EF等调优参数的真实语义与取值范围。1. 动机为什么不能做简单的后置过滤Garnet 的向量搜索通过VSIM命令族在 DiskANN 图索引上执行相似度搜索。实际业务中用户常常需要把相似度搜索与元数据过滤组合起来使用例如找到 10 张最近的图片要求year 2020 AND genre IN [action, comedy]最朴素的实现是后置过滤先取 K 个最近邻结果再丢弃不满足条件的。设计文档明确指出这一方案有两个致命问题过度拉取Overfetch waste要返回 K 个满足过滤条件的结果必须拉取 K×(1/selectivity) 个候选。当选择率selectivity只有 1% 时意味着 100 倍的过度拉取。召回损失Recall loss即使过度拉取最终结果集仍可能少于 K 条或者因为更近的匹配项在应用过滤前就被剪枝pruned而丢失。解决方案是内联过滤Inline Filtering在图的遍历过程中就求值过滤谓词使不匹配的候选节点永远不会占用结果槽位。这样既消除了过度拉取又提升了低选择率下的召回率。这一方案需要同时在两端改造——Garnet 侧的属性存储设计以及 DiskANN 库侧的搜索算法。2. Garnet 侧为内联过滤设计的属性存储2.1 既有属性存储的局限Garnet 既有的属性存储是面向通用键值访问设计的属性以原始 JSON 形式、按外部用户可见ID 为键存储。这是键值存储的自然选择——用户以键doc:42插入向量同时写入属性{year: 2021, genre: action}属性就存于该键下。此存储服务于 RESP 命令操作如VGETATTR保持不变。然而这与 DiskANN 图遍历的工作方式存在错配DiskANN 完全运行在内部 ID 空间——每个候选节点都是一个uint32内部 ID。若只依赖既有存储求值过滤的回调必须做读ExternalIdMap[internal_id]把内部 ID 翻译成外部键第一次 Garnet 存储读读Attributes[external_key]取回原始 JSON 负载第二次 Garnet 存储读查询时解析 JSON——ExtractFields()用 JSON tokenizer 定位并解析过滤表达式引用的字段。在内联过滤下这个回调对图遍历考虑到的每一个候选节点都要执行单次查询可能数千次两次存储读加上逐候选的 JSON 解析成为热路径上的主导成本。2.2 方案把二进制属性存在向量数据之后设计文档给出的方案是不再存原始 JSON 块而是把属性序列化为优化的二进制块紧跟在最常用的向量数据之后存储未量化索引中是完整向量 full vector量化索引中是量化向量 quant vector。为什么与向量放在一起向量数据是定长的因此紧随其后的过滤属性很容易定位。一次读取即可同时完成距离计算与过滤求值省掉额外的键访问。为什么用二进制格式原始 JSON 迫使查询期对每个候选节点都做解析。例如提取数字字段.year需要扫描键名、跳过空白、再把数字字符串解析成 double——这个工作在每次查询的每个候选节点上完全相同地重复而 JSON 结构在查询之间根本不变纯属浪费。二进制存储把 JSON 解析成本从查询期转移到写入期写入期向量插入/更新JSON 只解析一次经ConvertJsonToBinary()转换为二进制。二进制格式为[0xFF marker][field count][per-field: name_len, name, type_tag, value_len, value_bytes]数字预先转成 8 字节小端 f64。这是一次性成本写入新存储的同时也保留既有 JSON 存储。查询期每个候选节点ExtractFieldsBinary()直接扫描长度前缀字段。无需 JSON tokenizer字段名以原始字节区间比较数字直接读成 f64——无需字符串解析比 JSON 提取快约 10 倍。由于每个向量只插入一次、却可能在成千上万次查询中被作为候选节点求值这个写入多付一点、读取少付一点的权衡对读多写少的相似性搜索负载是正确的。2.3 逐候选回调对比不使用二进制属性存储每个候选节点 2 次存储读 JSON 解析 1. 读 ExternalIdMap[internal_id] → 外部键 ← ID 翻译 2. 读 Attributes[external_key] → JSON 字节 ← 既有 JSON 存储 3. ExtractFields(json, selectors) → 字段值 ← 查询期 JSON 解析 4. ExprRunner.Run(program) → bool 使用二进制属性存储每个候选节点 1 次存储读 二进制扫描 1. 读 BinaryAttributes[internal_id] → 二进制字节 ← 新存储直接查找 2. ExtractFieldsBinary(binary, selectors) → 字段值 ← 预解析约快 10 倍 3. ExprRunner.Run(program) → bool2.4 内联过滤逐候选成本汇总维度仅外部 ID 键控 JSON 属性存储本次改动内部 ID 键控二进制属性进一步优化二进制属性与向量数据共存每候选存储读2ExternalIdMap Attributes1仅 Attributes0遍历中已可访问ID 翻译必需内部 → 外部消除按内部 ID 键控消除字段提取查询期 JSON 解析二进制扫描约快 10 倍二进制扫描约快 10 倍解析成本支付时机查询期每候选、每查询写入期每次插入一次写入期每次插入一次每候选总开销2 读 JSON 解析 求值1 读 二进制扫描 求值二进制扫描 求值2.5 进一步优化一属性与向量数据共置Co-locate本次改动仍要求每个候选节点一次 Garnet 存储读来获取二进制属性。更进一步的优化是把二进制属性负载直接追加在同一个 Garnet 记录的向量数据之后图遍历时 DiskANN 已经为每个候选节点访问过向量记录来计算距离。若二进制属性作为同一条记录的尾部字节存储回调可以直接从 DiskANN 已持有的数据引用中读取——不再需要额外的存储读。本次改动每候选 1 次存储读 1. 读 Attributes[internal_id] → 二进制字节 ← 仍是一次独立读取 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(program) → bool 共置后每候选 0 次额外存储读 1. 从 vector record[internal_id] 读尾部字节 ← 遍历中已可访问 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(program) → bool这会把每候选成本降到零额外存储读——剩余开销只有二进制字段扫描与表达式求值。2.6 进一步优化二预构建属性索引若存在属性索引例如基于属性值构建的倒排索引或 roaring bitmap过滤谓词可以在查询规划期求值而不是图遍历期逐候选求值。索引会产生一个预计算的匹配内部 ID 集合如一个 bitmap直接作为GarnetFilter::Bitmap喂给 DiskANN——完全取代逐候选 FFI 回调DiskANN 用一次位查找代替读取属性并运行表达式求值器。这会把过滤成本从 O(访问候选数) 次回调调用降为查询开始时一次 O(匹配向量数) 的 bitmap 构建彻底消除逐候选的属性读取与表达式求值。3. DiskANN 侧过滤搜索算法DiskANN 库提供多种过滤查询搜索算法都接收一个过滤谓词区别在于如何把过滤集成到图遍历中。3.1 算法对比维度Inline自适应 LBetaFilter过滤集成方式搜索过程中求值过滤按采样选择率缩放 Lsearch用 beta 因子缩放不匹配节点的距离数据结构NeighborPriorityQueue有序数组包装任意搜索策略低选择率下的探索广度受自适应 Lsearch 约束中等——不匹配节点显得更远但仍参与竞争收敛性标准贪心收敛标准贪心收敛自适应预算有无性能对比TBD在 100K YFCC 数据集上的召回率与延迟基准结果待定选择内联 自适应 L 的依据来自 DiskANN 在内存内 provider 上、跨一系列选择率与数据集的基准测试。3.2 内联 自适应 L 算法当前选择算法描述见 DiskANN 库本身请参考 storage/Tsavorite/README.md 下的依赖说明算法细节位于 DiskANN 源码中。3.3 过滤模式分发Rust文件DiskANN/diskann-garnet/src/provider.rs、dyn_index.rsRust 侧实现不在本仓库中C# 提供一个过滤回调DiskANN 在检查向量是否匹配过滤表达式时调用它。4. 架构总览┌──────────────────────────────────────────────────────┐ │ Client (RESP) │ │ VSIM key 10 VALUES vec... FILTER .year 2020 │ │ FILTER-EF 32 │ └──────────┬───────────────────────────────────────────┘ │ ▼ ┌──────────────────────────────────────────────────────┐ │ Garnet Server (C#) │ │ │ │ VectorManager.ValueSimilarity() │ │ ├─ ExprCompiler.TryCompile(filter) → postfix pgm │ │ ├─ Pin scratch buffers, set t_inlineFilterState │ │ └─ DiskANNService.SearchVector( │ │ ..., filterData, filterLen, maxFilterEffort) │ └──────────┬───────────────────────────────────────────┘ │ P/Invoke (FFI) ▼ ┌──────────────────────────────────────────────────────┐ │ DiskANN (Rust, diskann-garnet) │ │ │ │ search_vector() │ │ │ For each candidate node: │ │ │ ├─ Call filterCallback(ctx, internal_id)──┐ │ │ │ │ ┌────────────────────┘ │ │ │ │ ▼ │ │ │ │ ┌─────────────────────────────────────┐ │ │ │ │ │ C# InlineFilterCandidateCallback │ │ │ │ │ │ ├─ Read BinaryAttrs[internal_id] │ │ │ │ │ │ ├─ ExtractFieldsBinary(selectors) │ │ │ │ │ │ └─ ExprRunner.Run(program)→0/1 │ │ │ │ │ └─────────────────────────────────────┘ │ │ │ │ │ │ └─ Return top-K │ └──────────────────────────────────────────────────────┘5. 过滤表达式编译C#文件VectorManager.Filter.cs5.1 表达式语言支持对 JSON 属性的布尔表达式.year 2020 AND .genre IN [action, comedy] AND NOT .archived运算符、!、、、、、IN、NOT IN、AND、OR、NOT命令文档 vector-sets.md 进一步明确了完整的语法面字段访问用点号.year、.rating、.tags算术运算含、-、*、/、%、**逻辑运算and/or/not也支持、||、!均为小写敏感in支持三种语义——元组成员.director in [Spielberg, Nolan]、JSON 数组成员classic in .tags、以及子串act in .genre支持括号分组与整数、浮点、单/双引号字符串含\转义、true/false/null字面量。5.2 编译管线Tokenize——提取字段选择器.field、运算符、字面量Shunting-yard——通过ExprCompiler.TryCompile把中缀表达式转为后缀输出——ExprToken数组指令流 选择器范围表达式中引用的唯一字段名。ExprCompiler.cs 的实现显示编译器分两阶段工作第一阶段把表达式 token 化进tokensBuf数字、字符串字面量以 (offset, length) 字节区间直接引用原始过滤表达式字节零字符串分配元组字面量[1, foo, 42]的成员平铺进 tuple pool第二阶段用调度场算法shunting-yard产出后缀指令流。运算符优先级表OpTable与 Redis 的expr.c ExprOptable[]保持一致见 VectorFilterExpression.cs。编译产物是ExprProgram——一个零分配的 ref struct其中Instructions是后缀指令序列。例如.year 2000 and .rating 7被编译为[SEL:year] [NUM:2000] [OP:Gte] [SEL:rating] [NUM:7] [OP:Gt] [OP:And]执行时 ExprRunner.cs 的栈式 VM 从左到右遍历指令值 tokenNum/Str/Tuple/Null压栈Selectortoken 触发字段提取后压栈Optoken 弹出 12 个操作数、计算结果并压回全部指令处理完后以栈顶值的真值性产生最终布尔结果。所有字符串比较都在原始 UTF-8 字节区间上进行并支持转义感知的相等比较UnescapedEquals。5.3 零分配设计所有编译与求值缓冲区都来自会话局部的ScratchBufferBuilder采用固定的约 9 KB 布局实际字节数因注释版本而异见下表ExprToken为 16 字节 blittable 结构因此 560 个 token × 16 8960 字节 32 个选择器 × 8 256 字节合计约 9216 字节缓冲区大小用途instrBuf2048 B编译后的指令tuplePoolBuf2048 B元组字面量存储tokensBuf1024 BTokenizer 工作区opsStackBuf512 B调度场运算符栈runtimePoolBuf1024 BIN 运算符的数组展开extractedFields1024 B字段提取输出stackBuf1024 B表达式求值栈从 VectorManager.Filter.cs 的源码注释与常量定义可以看到这套布局的实际形态MaxInstructions 128约支持 18 个 AND/OR 子句、MaxTuplePool 64、MaxRuntimePool 64、MaxSelectors 32、StackCapacity 16共 560 个ExprToken。缓冲区来自会话级 pinnedbyte[]scratch buffer——第一次VSIM FILTER查询后即已扩容到位后续调用零分配成本缓冲在finally块中以 LIFO 顺序通过RewindScratchBuffer归还。过滤编译与求值全程无堆分配。重要行为语义若任一上限被突破过滤要么编译失败返回 0 无结果通过要么该候选节点被优雅排除。命令文档 vector-sets.md 中的Limits表与此一一对应最大 token 128、最大元组元素 64、每候选最大运行期数组元素 64、最大唯一选择器 32、最大求值栈深 16、最大括号嵌套 128受 token 缓冲区约束。属性缺失会使该候选的过滤结果为 false编译错误返回空结果集而非服务端错误。6. FFI 回调协议6.1 注册在索引创建CreateIndex/RecreateIndex时C# 把InlineFilterCallbackPtr传给 Rust见 DiskANNService.cs 中create_index的filterCallback参数与 VectorManager.Callbacks.cs 中的InlineFilterCallbackPtr定义delegate* unmanaged[Cdecl]ulong, uint, byte InlineFilterCallbackPtr InlineFilterCandidateCallbackImpl;Rust 将其存入自己的Callbacks结构与 read/write/delete 回调并列。6.2 每次搜索的设置C# 侧每次 FFI 搜索调用前编译过滤表达式pin 所有 scratch 缓冲区用指向以下内容的指针填充[ThreadStatic] t_inlineFilterState编译后的指令元组池选择器范围过滤字节Garnet 存储上下文以filter_data、filter_len、max_filtering_effort调用Service.SearchVector(...)。在 VectorManager.cs 的ValueSimilarity内联过滤路径中可以看到这套流程的完整代码从 scratch buffer 借出 token 与选择器区间、ExprCompiler.TryCompile编译、GetSelectorRanges收集唯一选择器、构造栈上的InlineFilterStateref struct 并保存指针到InlineFilterStatePtr随后调用Service.SearchVector(...)最后在finally中RewindScratchBuffer并清空InlineFilterStatePtr。由于InlineFilterState是 ref struct它留在调用栈上在SearchVector调用期间保持有效。6.3 逐候选回调Rust → C#Rust 调用: filterCallback(context: u64, internal_id: u32) → u8 └─ 1 通过, 0 拒绝 C# InlineFilterCandidateCallbackImpl: 1. 读 BinaryAttributes[internal_id] → 二进制字节经 ReadSizeUnknown 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(instructions, fields) → bool 4. 返回 1 或 0VectorManager.Filter.cs 中的EvaluateCandidateFilter展示了当前实现的回调体先经ExternalIdMap读出外部 ID读不到则排除再按外部 ID 读属性读不到则排除随后从线程静态状态重建ExprProgram、ResetRuntimePool()、ExtractFields提取字段、ExprRunner.Run求值并返回 1/0。当前实现采用的是 2.3 节描述的2 次存储读 查询期 JSON 提取路径设计文档中的二进制属性存储与共置优化即在此基础上演进。6.4 线程安全DiskANN 搜索每个查询单线程执行[ThreadStatic]状态保证跨查询无相互干扰ActiveThreadSession在 FFI 前设置、在锁释放时清除见 VectorManager.Callbacks.cs 中的ActiveThreadSession注释只要 DiskANN 保持单线程该方案即可工作。7. 属性提取文件AttributeExtractor.cs支持两种存储格式7.1 JSON 格式既有外部 ID 键控存储的默认格式。属性以原始 JSON 存储如{year: 2021, genre: action}。ExtractFields()单遍扫描把字段名与选择器匹配把值解析为ExprToken。实现上是一个超轻量的顶层 JSON 字段提取器所有字符串值都是指向源 JSON span 的零拷贝字节区间引用Utf8Start、Utf8Length不产生字符串分配布尔true/false解析为数字 1/0null解析为Nulltoken数组在解析成员超过 64 个上限时优雅跳过并返回 null。7.2 二进制格式新的内部 ID 键控存储使用的格式。预提取二进制布局[0xFF marker][field count][per-field: name_len, name, type_tag, value_len, value_bytes]。数字以 8 字节小端 f64 存储。ExtractFieldsBinary()比 JSON 提取约快 10 倍由ConvertJsonToBinary()负责转换。源码中的类型标签为0字符串、1数字、2bool_true、3bool_false、4null字段名字符串要求无转义字符串值会做转义展开\n、\r、\t等嵌套对象/数组在二进制格式中不支持转换时返回 -1。两条路径都是零分配操作在ReadOnlySpanbyte上进行。8. 端到端数据流1. VSIM 命令解析 → 提取过滤字节 maxFilteringEffort 2. VectorManager.ValueSimilarity() ├─ filter 非空 → 内联过滤路径 ├─ ExprCompiler.TryCompile(filter) → 后缀程序 ├─ Pin 缓冲区, 填充 t_inlineFilterState └─ DiskANNService.SearchVector(query, k, ef, filterData, filterLen, maxEffort) 3. P/Invoke → Rust search_vector() ├─ 检测 GarnetFilter::Callback ├─ 创建 TwoQueueSearch GarnetFilterProvider └─ 运行 two-queue 算法: 对每个候选节点: ├─ 计算距离 ├─ 插入 candidates 最小堆 ├─ FFI 回调 → C# 求值过滤 → 接受/拒绝 └─ 若接受 → 插入 filtered_results 最大堆 4. 返回 top-K 内部 ID 距离仅匹配候选 5. 回到 C# VectorManager: ├─ 经 ExternalIdMap 把内部 ID 映射为外部键 ├─ 可选地为结果拉取属性 └─ 序列化 RESP 响应给客户端命令解析端在 RespServerSessionVectors.cs 的VSIM处理器中实现解析FILTER expr与FILTER-EF n选项其中FILTER-EF必须为 4 到VectorManager.MaxFilteringScaleFactor即 256之间的整数重复指定会报错未指定时默认 16随后把过滤字节与maxFilteringEffort一并传入VectorSetValueSimilarity/VectorSetElementSimilarity。EF n搜索期探索因子的默认值为 100且实际生效值为Math.Max(searchExplorationFactor, count)见 VectorManager.cs 的ValueSimilarity。9. 性能特征9.1 与后置过滤对比维度后置过滤内联 自适应 L是否需要过度拉取是K/selectivity否低选择率下的召回差错过邻近匹配高广泛探索每候选成本仅距离计算距离 FFI 回调 属性读取 过滤求值内存大结果缓冲区固定大小堆9.2 调优用FILTER-EF控制低选择率时 Lsearch 的缩放幅度默认 16取值范围[4, 256]。它决定了自适应内联过滤搜索中 EF 基于选择率的缩放上限见 vector-sets.md 中FILTER-EF n的说明。EF n搜索期探索因子默认 100控制候选列表大小越大越广的探索通常对应越高召回与更高延迟。9.3 与既有命令文档的关系过滤表达式的能力与限制在 vector-sets.md 的 Filter Expressions 一节有完整的用户视角文档语法、运算符优先级表、limits 表、缺失属性语义、编译错误语义与本文设计文档互为印证设计文档阐述为什么这样实现零分配、二进制存储、内联回调命令文档阐述用户如何使用。两者结合阅读可以完整理解 Garnet 向量过滤搜索从命令入口到图遍历求值的全部链路。参考实现与测试入口设计文档filtered-search-design.md用户命令文档vector-sets.md过滤编译与内联回调状态VectorManager.Filter.cs属性提取JSON/二进制双格式AttributeExtractor.cs编译管线调度场算法ExprCompiler.cs执行引擎栈式 VMExprRunner.cs表达式 token 与运算符表VectorFilterExpression.csFFI 边界create_index/search_vector声明DiskANNService.csFFI 回调FilterCallbackUnmanaged、ActiveThreadSessionVectorManager.Callbacks.cs搜索入口ValueSimilarityVectorManager.csVSIM 命令解析FILTER/FILTER-EF选项RespServerSessionVectors.cs【免费下载链接】garnetGarnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.项目地址: https://gitcode.com/GitHub_Trending/garnet4/garnet创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Garnet 向量过滤搜索（Filtered Vector Search）端到端设计解析：从内联过滤到零分配 FFI 回调
Garnet 向量过滤搜索Filtered Vector Search端到端设计解析从内联过滤到零分配 FFI 回调【免费下载链接】garnetGarnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.项目地址: https://gitcode.com/GitHub_Trending/garnet4/garnet导读本文基于 Garnet 仓库中的 filtered-search-design.md 设计文档结合 libs/server/Resp/Vector 下的实际实现代码系统讲解 Garnet 如何在 DiskANN 图索引的相似性搜索VSIM命令族中实现内联元数据过滤在图的遍历过程中实时求值过滤谓词避免先取 K 个再丢弃的后置过滤post-filtering方案带来的过度拉取overfetch与召回损失。读完本文你将掌握过滤表达式如何在 C# 侧被编译成零分配的指令流、二进制属性存储如何把 JSON 解析成本从查询期转移到写入期、RustDiskANN与 C# 之间的 FFI 回调协议如何按候选节点per-candidate工作以及FILTER-EF等调优参数的真实语义与取值范围。1. 动机为什么不能做简单的后置过滤Garnet 的向量搜索通过VSIM命令族在 DiskANN 图索引上执行相似度搜索。实际业务中用户常常需要把相似度搜索与元数据过滤组合起来使用例如找到 10 张最近的图片要求year 2020 AND genre IN [action, comedy]最朴素的实现是后置过滤先取 K 个最近邻结果再丢弃不满足条件的。设计文档明确指出这一方案有两个致命问题过度拉取Overfetch waste要返回 K 个满足过滤条件的结果必须拉取 K×(1/selectivity) 个候选。当选择率selectivity只有 1% 时意味着 100 倍的过度拉取。召回损失Recall loss即使过度拉取最终结果集仍可能少于 K 条或者因为更近的匹配项在应用过滤前就被剪枝pruned而丢失。解决方案是内联过滤Inline Filtering在图的遍历过程中就求值过滤谓词使不匹配的候选节点永远不会占用结果槽位。这样既消除了过度拉取又提升了低选择率下的召回率。这一方案需要同时在两端改造——Garnet 侧的属性存储设计以及 DiskANN 库侧的搜索算法。2. Garnet 侧为内联过滤设计的属性存储2.1 既有属性存储的局限Garnet 既有的属性存储是面向通用键值访问设计的属性以原始 JSON 形式、按外部用户可见ID 为键存储。这是键值存储的自然选择——用户以键doc:42插入向量同时写入属性{year: 2021, genre: action}属性就存于该键下。此存储服务于 RESP 命令操作如VGETATTR保持不变。然而这与 DiskANN 图遍历的工作方式存在错配DiskANN 完全运行在内部 ID 空间——每个候选节点都是一个uint32内部 ID。若只依赖既有存储求值过滤的回调必须做读ExternalIdMap[internal_id]把内部 ID 翻译成外部键第一次 Garnet 存储读读Attributes[external_key]取回原始 JSON 负载第二次 Garnet 存储读查询时解析 JSON——ExtractFields()用 JSON tokenizer 定位并解析过滤表达式引用的字段。在内联过滤下这个回调对图遍历考虑到的每一个候选节点都要执行单次查询可能数千次两次存储读加上逐候选的 JSON 解析成为热路径上的主导成本。2.2 方案把二进制属性存在向量数据之后设计文档给出的方案是不再存原始 JSON 块而是把属性序列化为优化的二进制块紧跟在最常用的向量数据之后存储未量化索引中是完整向量 full vector量化索引中是量化向量 quant vector。为什么与向量放在一起向量数据是定长的因此紧随其后的过滤属性很容易定位。一次读取即可同时完成距离计算与过滤求值省掉额外的键访问。为什么用二进制格式原始 JSON 迫使查询期对每个候选节点都做解析。例如提取数字字段.year需要扫描键名、跳过空白、再把数字字符串解析成 double——这个工作在每次查询的每个候选节点上完全相同地重复而 JSON 结构在查询之间根本不变纯属浪费。二进制存储把 JSON 解析成本从查询期转移到写入期写入期向量插入/更新JSON 只解析一次经ConvertJsonToBinary()转换为二进制。二进制格式为[0xFF marker][field count][per-field: name_len, name, type_tag, value_len, value_bytes]数字预先转成 8 字节小端 f64。这是一次性成本写入新存储的同时也保留既有 JSON 存储。查询期每个候选节点ExtractFieldsBinary()直接扫描长度前缀字段。无需 JSON tokenizer字段名以原始字节区间比较数字直接读成 f64——无需字符串解析比 JSON 提取快约 10 倍。由于每个向量只插入一次、却可能在成千上万次查询中被作为候选节点求值这个写入多付一点、读取少付一点的权衡对读多写少的相似性搜索负载是正确的。2.3 逐候选回调对比不使用二进制属性存储每个候选节点 2 次存储读 JSON 解析 1. 读 ExternalIdMap[internal_id] → 外部键 ← ID 翻译 2. 读 Attributes[external_key] → JSON 字节 ← 既有 JSON 存储 3. ExtractFields(json, selectors) → 字段值 ← 查询期 JSON 解析 4. ExprRunner.Run(program) → bool 使用二进制属性存储每个候选节点 1 次存储读 二进制扫描 1. 读 BinaryAttributes[internal_id] → 二进制字节 ← 新存储直接查找 2. ExtractFieldsBinary(binary, selectors) → 字段值 ← 预解析约快 10 倍 3. ExprRunner.Run(program) → bool2.4 内联过滤逐候选成本汇总维度仅外部 ID 键控 JSON 属性存储本次改动内部 ID 键控二进制属性进一步优化二进制属性与向量数据共存每候选存储读2ExternalIdMap Attributes1仅 Attributes0遍历中已可访问ID 翻译必需内部 → 外部消除按内部 ID 键控消除字段提取查询期 JSON 解析二进制扫描约快 10 倍二进制扫描约快 10 倍解析成本支付时机查询期每候选、每查询写入期每次插入一次写入期每次插入一次每候选总开销2 读 JSON 解析 求值1 读 二进制扫描 求值二进制扫描 求值2.5 进一步优化一属性与向量数据共置Co-locate本次改动仍要求每个候选节点一次 Garnet 存储读来获取二进制属性。更进一步的优化是把二进制属性负载直接追加在同一个 Garnet 记录的向量数据之后图遍历时 DiskANN 已经为每个候选节点访问过向量记录来计算距离。若二进制属性作为同一条记录的尾部字节存储回调可以直接从 DiskANN 已持有的数据引用中读取——不再需要额外的存储读。本次改动每候选 1 次存储读 1. 读 Attributes[internal_id] → 二进制字节 ← 仍是一次独立读取 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(program) → bool 共置后每候选 0 次额外存储读 1. 从 vector record[internal_id] 读尾部字节 ← 遍历中已可访问 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(program) → bool这会把每候选成本降到零额外存储读——剩余开销只有二进制字段扫描与表达式求值。2.6 进一步优化二预构建属性索引若存在属性索引例如基于属性值构建的倒排索引或 roaring bitmap过滤谓词可以在查询规划期求值而不是图遍历期逐候选求值。索引会产生一个预计算的匹配内部 ID 集合如一个 bitmap直接作为GarnetFilter::Bitmap喂给 DiskANN——完全取代逐候选 FFI 回调DiskANN 用一次位查找代替读取属性并运行表达式求值器。这会把过滤成本从 O(访问候选数) 次回调调用降为查询开始时一次 O(匹配向量数) 的 bitmap 构建彻底消除逐候选的属性读取与表达式求值。3. DiskANN 侧过滤搜索算法DiskANN 库提供多种过滤查询搜索算法都接收一个过滤谓词区别在于如何把过滤集成到图遍历中。3.1 算法对比维度Inline自适应 LBetaFilter过滤集成方式搜索过程中求值过滤按采样选择率缩放 Lsearch用 beta 因子缩放不匹配节点的距离数据结构NeighborPriorityQueue有序数组包装任意搜索策略低选择率下的探索广度受自适应 Lsearch 约束中等——不匹配节点显得更远但仍参与竞争收敛性标准贪心收敛标准贪心收敛自适应预算有无性能对比TBD在 100K YFCC 数据集上的召回率与延迟基准结果待定选择内联 自适应 L 的依据来自 DiskANN 在内存内 provider 上、跨一系列选择率与数据集的基准测试。3.2 内联 自适应 L 算法当前选择算法描述见 DiskANN 库本身请参考 storage/Tsavorite/README.md 下的依赖说明算法细节位于 DiskANN 源码中。3.3 过滤模式分发Rust文件DiskANN/diskann-garnet/src/provider.rs、dyn_index.rsRust 侧实现不在本仓库中C# 提供一个过滤回调DiskANN 在检查向量是否匹配过滤表达式时调用它。4. 架构总览┌──────────────────────────────────────────────────────┐ │ Client (RESP) │ │ VSIM key 10 VALUES vec... FILTER .year 2020 │ │ FILTER-EF 32 │ └──────────┬───────────────────────────────────────────┘ │ ▼ ┌──────────────────────────────────────────────────────┐ │ Garnet Server (C#) │ │ │ │ VectorManager.ValueSimilarity() │ │ ├─ ExprCompiler.TryCompile(filter) → postfix pgm │ │ ├─ Pin scratch buffers, set t_inlineFilterState │ │ └─ DiskANNService.SearchVector( │ │ ..., filterData, filterLen, maxFilterEffort) │ └──────────┬───────────────────────────────────────────┘ │ P/Invoke (FFI) ▼ ┌──────────────────────────────────────────────────────┐ │ DiskANN (Rust, diskann-garnet) │ │ │ │ search_vector() │ │ │ For each candidate node: │ │ │ ├─ Call filterCallback(ctx, internal_id)──┐ │ │ │ │ ┌────────────────────┘ │ │ │ │ ▼ │ │ │ │ ┌─────────────────────────────────────┐ │ │ │ │ │ C# InlineFilterCandidateCallback │ │ │ │ │ │ ├─ Read BinaryAttrs[internal_id] │ │ │ │ │ │ ├─ ExtractFieldsBinary(selectors) │ │ │ │ │ │ └─ ExprRunner.Run(program)→0/1 │ │ │ │ │ └─────────────────────────────────────┘ │ │ │ │ │ │ └─ Return top-K │ └──────────────────────────────────────────────────────┘5. 过滤表达式编译C#文件VectorManager.Filter.cs5.1 表达式语言支持对 JSON 属性的布尔表达式.year 2020 AND .genre IN [action, comedy] AND NOT .archived运算符、!、、、、、IN、NOT IN、AND、OR、NOT命令文档 vector-sets.md 进一步明确了完整的语法面字段访问用点号.year、.rating、.tags算术运算含、-、*、/、%、**逻辑运算and/or/not也支持、||、!均为小写敏感in支持三种语义——元组成员.director in [Spielberg, Nolan]、JSON 数组成员classic in .tags、以及子串act in .genre支持括号分组与整数、浮点、单/双引号字符串含\转义、true/false/null字面量。5.2 编译管线Tokenize——提取字段选择器.field、运算符、字面量Shunting-yard——通过ExprCompiler.TryCompile把中缀表达式转为后缀输出——ExprToken数组指令流 选择器范围表达式中引用的唯一字段名。ExprCompiler.cs 的实现显示编译器分两阶段工作第一阶段把表达式 token 化进tokensBuf数字、字符串字面量以 (offset, length) 字节区间直接引用原始过滤表达式字节零字符串分配元组字面量[1, foo, 42]的成员平铺进 tuple pool第二阶段用调度场算法shunting-yard产出后缀指令流。运算符优先级表OpTable与 Redis 的expr.c ExprOptable[]保持一致见 VectorFilterExpression.cs。编译产物是ExprProgram——一个零分配的 ref struct其中Instructions是后缀指令序列。例如.year 2000 and .rating 7被编译为[SEL:year] [NUM:2000] [OP:Gte] [SEL:rating] [NUM:7] [OP:Gt] [OP:And]执行时 ExprRunner.cs 的栈式 VM 从左到右遍历指令值 tokenNum/Str/Tuple/Null压栈Selectortoken 触发字段提取后压栈Optoken 弹出 12 个操作数、计算结果并压回全部指令处理完后以栈顶值的真值性产生最终布尔结果。所有字符串比较都在原始 UTF-8 字节区间上进行并支持转义感知的相等比较UnescapedEquals。5.3 零分配设计所有编译与求值缓冲区都来自会话局部的ScratchBufferBuilder采用固定的约 9 KB 布局实际字节数因注释版本而异见下表ExprToken为 16 字节 blittable 结构因此 560 个 token × 16 8960 字节 32 个选择器 × 8 256 字节合计约 9216 字节缓冲区大小用途instrBuf2048 B编译后的指令tuplePoolBuf2048 B元组字面量存储tokensBuf1024 BTokenizer 工作区opsStackBuf512 B调度场运算符栈runtimePoolBuf1024 BIN 运算符的数组展开extractedFields1024 B字段提取输出stackBuf1024 B表达式求值栈从 VectorManager.Filter.cs 的源码注释与常量定义可以看到这套布局的实际形态MaxInstructions 128约支持 18 个 AND/OR 子句、MaxTuplePool 64、MaxRuntimePool 64、MaxSelectors 32、StackCapacity 16共 560 个ExprToken。缓冲区来自会话级 pinnedbyte[]scratch buffer——第一次VSIM FILTER查询后即已扩容到位后续调用零分配成本缓冲在finally块中以 LIFO 顺序通过RewindScratchBuffer归还。过滤编译与求值全程无堆分配。重要行为语义若任一上限被突破过滤要么编译失败返回 0 无结果通过要么该候选节点被优雅排除。命令文档 vector-sets.md 中的Limits表与此一一对应最大 token 128、最大元组元素 64、每候选最大运行期数组元素 64、最大唯一选择器 32、最大求值栈深 16、最大括号嵌套 128受 token 缓冲区约束。属性缺失会使该候选的过滤结果为 false编译错误返回空结果集而非服务端错误。6. FFI 回调协议6.1 注册在索引创建CreateIndex/RecreateIndex时C# 把InlineFilterCallbackPtr传给 Rust见 DiskANNService.cs 中create_index的filterCallback参数与 VectorManager.Callbacks.cs 中的InlineFilterCallbackPtr定义delegate* unmanaged[Cdecl]ulong, uint, byte InlineFilterCallbackPtr InlineFilterCandidateCallbackImpl;Rust 将其存入自己的Callbacks结构与 read/write/delete 回调并列。6.2 每次搜索的设置C# 侧每次 FFI 搜索调用前编译过滤表达式pin 所有 scratch 缓冲区用指向以下内容的指针填充[ThreadStatic] t_inlineFilterState编译后的指令元组池选择器范围过滤字节Garnet 存储上下文以filter_data、filter_len、max_filtering_effort调用Service.SearchVector(...)。在 VectorManager.cs 的ValueSimilarity内联过滤路径中可以看到这套流程的完整代码从 scratch buffer 借出 token 与选择器区间、ExprCompiler.TryCompile编译、GetSelectorRanges收集唯一选择器、构造栈上的InlineFilterStateref struct 并保存指针到InlineFilterStatePtr随后调用Service.SearchVector(...)最后在finally中RewindScratchBuffer并清空InlineFilterStatePtr。由于InlineFilterState是 ref struct它留在调用栈上在SearchVector调用期间保持有效。6.3 逐候选回调Rust → C#Rust 调用: filterCallback(context: u64, internal_id: u32) → u8 └─ 1 通过, 0 拒绝 C# InlineFilterCandidateCallbackImpl: 1. 读 BinaryAttributes[internal_id] → 二进制字节经 ReadSizeUnknown 2. ExtractFieldsBinary(binary, selectors) → 字段值 3. ExprRunner.Run(instructions, fields) → bool 4. 返回 1 或 0VectorManager.Filter.cs 中的EvaluateCandidateFilter展示了当前实现的回调体先经ExternalIdMap读出外部 ID读不到则排除再按外部 ID 读属性读不到则排除随后从线程静态状态重建ExprProgram、ResetRuntimePool()、ExtractFields提取字段、ExprRunner.Run求值并返回 1/0。当前实现采用的是 2.3 节描述的2 次存储读 查询期 JSON 提取路径设计文档中的二进制属性存储与共置优化即在此基础上演进。6.4 线程安全DiskANN 搜索每个查询单线程执行[ThreadStatic]状态保证跨查询无相互干扰ActiveThreadSession在 FFI 前设置、在锁释放时清除见 VectorManager.Callbacks.cs 中的ActiveThreadSession注释只要 DiskANN 保持单线程该方案即可工作。7. 属性提取文件AttributeExtractor.cs支持两种存储格式7.1 JSON 格式既有外部 ID 键控存储的默认格式。属性以原始 JSON 存储如{year: 2021, genre: action}。ExtractFields()单遍扫描把字段名与选择器匹配把值解析为ExprToken。实现上是一个超轻量的顶层 JSON 字段提取器所有字符串值都是指向源 JSON span 的零拷贝字节区间引用Utf8Start、Utf8Length不产生字符串分配布尔true/false解析为数字 1/0null解析为Nulltoken数组在解析成员超过 64 个上限时优雅跳过并返回 null。7.2 二进制格式新的内部 ID 键控存储使用的格式。预提取二进制布局[0xFF marker][field count][per-field: name_len, name, type_tag, value_len, value_bytes]。数字以 8 字节小端 f64 存储。ExtractFieldsBinary()比 JSON 提取约快 10 倍由ConvertJsonToBinary()负责转换。源码中的类型标签为0字符串、1数字、2bool_true、3bool_false、4null字段名字符串要求无转义字符串值会做转义展开\n、\r、\t等嵌套对象/数组在二进制格式中不支持转换时返回 -1。两条路径都是零分配操作在ReadOnlySpanbyte上进行。8. 端到端数据流1. VSIM 命令解析 → 提取过滤字节 maxFilteringEffort 2. VectorManager.ValueSimilarity() ├─ filter 非空 → 内联过滤路径 ├─ ExprCompiler.TryCompile(filter) → 后缀程序 ├─ Pin 缓冲区, 填充 t_inlineFilterState └─ DiskANNService.SearchVector(query, k, ef, filterData, filterLen, maxEffort) 3. P/Invoke → Rust search_vector() ├─ 检测 GarnetFilter::Callback ├─ 创建 TwoQueueSearch GarnetFilterProvider └─ 运行 two-queue 算法: 对每个候选节点: ├─ 计算距离 ├─ 插入 candidates 最小堆 ├─ FFI 回调 → C# 求值过滤 → 接受/拒绝 └─ 若接受 → 插入 filtered_results 最大堆 4. 返回 top-K 内部 ID 距离仅匹配候选 5. 回到 C# VectorManager: ├─ 经 ExternalIdMap 把内部 ID 映射为外部键 ├─ 可选地为结果拉取属性 └─ 序列化 RESP 响应给客户端命令解析端在 RespServerSessionVectors.cs 的VSIM处理器中实现解析FILTER expr与FILTER-EF n选项其中FILTER-EF必须为 4 到VectorManager.MaxFilteringScaleFactor即 256之间的整数重复指定会报错未指定时默认 16随后把过滤字节与maxFilteringEffort一并传入VectorSetValueSimilarity/VectorSetElementSimilarity。EF n搜索期探索因子的默认值为 100且实际生效值为Math.Max(searchExplorationFactor, count)见 VectorManager.cs 的ValueSimilarity。9. 性能特征9.1 与后置过滤对比维度后置过滤内联 自适应 L是否需要过度拉取是K/selectivity否低选择率下的召回差错过邻近匹配高广泛探索每候选成本仅距离计算距离 FFI 回调 属性读取 过滤求值内存大结果缓冲区固定大小堆9.2 调优用FILTER-EF控制低选择率时 Lsearch 的缩放幅度默认 16取值范围[4, 256]。它决定了自适应内联过滤搜索中 EF 基于选择率的缩放上限见 vector-sets.md 中FILTER-EF n的说明。EF n搜索期探索因子默认 100控制候选列表大小越大越广的探索通常对应越高召回与更高延迟。9.3 与既有命令文档的关系过滤表达式的能力与限制在 vector-sets.md 的 Filter Expressions 一节有完整的用户视角文档语法、运算符优先级表、limits 表、缺失属性语义、编译错误语义与本文设计文档互为印证设计文档阐述为什么这样实现零分配、二进制存储、内联回调命令文档阐述用户如何使用。两者结合阅读可以完整理解 Garnet 向量过滤搜索从命令入口到图遍历求值的全部链路。参考实现与测试入口设计文档filtered-search-design.md用户命令文档vector-sets.md过滤编译与内联回调状态VectorManager.Filter.cs属性提取JSON/二进制双格式AttributeExtractor.cs编译管线调度场算法ExprCompiler.cs执行引擎栈式 VMExprRunner.cs表达式 token 与运算符表VectorFilterExpression.csFFI 边界create_index/search_vector声明DiskANNService.csFFI 回调FilterCallbackUnmanaged、ActiveThreadSessionVectorManager.Callbacks.cs搜索入口ValueSimilarityVectorManager.csVSIM 命令解析FILTER/FILTER-EF选项RespServerSessionVectors.cs【免费下载链接】garnetGarnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.项目地址: https://gitcode.com/GitHub_Trending/garnet4/garnet创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考