Milvus 主键索引（Primary Key Index）设计解析：BBhash + Value Array 支撑十亿级跨 Segment 主键精确查找

Milvus 主键索引Primary Key Index设计解析BBhash Value Array 支撑十亿级跨 Segment 主键精确查找【免费下载链接】milvusMilvus is a high-performance, cloud-native vector database built for scalable vector ANN search项目地址: https://gitcode.com/GitHub_Trending/mi/milvusMilvus 作为云原生向量数据库其主键Primary Key, PK不仅是数据的唯一标识更承担着写入去重、点查、upsert部分更新与删除定位等关键职责。本篇文章以 Milvus 仓库中的主键索引设计文档 为核心脉络解析一套面向**跨多个 Segment、加载于 Delegator 并持久化在对象存储S3**的主键索引方案说明其两大核心组件 BBhash 与 Value Array 的工作原理、内存/性能模型并结合当前仓库中 Delegator 的 Bloom Filter Oracle 与 SegCore 按段 PK 索引实现帮助读者理解这一设计的动机、收益、适用边界与落地方向。一、设计动机从“Bloom Filter 集合”到“全局主键索引”在理解新方案之前有必要先回顾当前 Milvus 中主键检索的真实路径。写入的数据按 Segment 组织主键“落在哪个 Segment”这一问题由查询节点QueryNode中的Delegator回答。从源码看这一职责由internal/querynodev2/pkoracle包承担其中BloomFilterSet是Candidate接口的实现之一见 bloom_filter_set.go它在内存中持有每个 Segment 的PkStatistics内嵌统计布隆过滤器并通过MayPkExist做“PK 是否可能存在于该 Segment”的近似判定多个过滤器的判定结果再由 pk_oracle.go 汇总成候选 Segment 集合。这套基于 Bloom Filter 的方案的固有问题是近似性Bloom Filter 存在误判false positive返回“存在”并不代表 PK 一定在命中后仍需回到 Segment 内二次确认叠加放大Segment 数量越多需要顺序检查的过滤器越多累计的误判概率与查询时延随之上升删除/更新转发开销Delegator 在收到 Delete 或 Upsert 请求时需要把删除转发给所有“可能包含该 PK”的 Segment。过滤器越多、误判越高被无谓触达的 Segment 就越多。设计文档提出引入一套主键索引Primary Key Index系统它能够对字符串或整型主键做跨多个 Segment 的快速查找索引会被加载在 Delegator 中并持久化到 S3 存储以在节点重启/索引重建时快速恢复。二、目标与收益三大直接收益设计文档为该系统列出三个核心目标目标说明对应收益场景去重Deduplication写入过程中识别重复数据自动将其转换为 Insert Delete 操作高并发下相同主键的重复写入不必落到多份副本再靠合流去重加速部分更新Partial Updates提升部分 upsert 与点查point query性能PK 定位由“扫候选集”变成一次精确索引查找优化删除转发Delete Forwarding降低 Delegator 在 Delete 操作中做 Bloom Filter 检查的开销删除只需转发给真正持有该 PK 的 Segment可以看到这套索引的本质是把“用多个过滤器猜”升级为“用一张全局映射精确找”从而同时改善写入去重、查询与删除三类路径。三、总体设计两大核心组件系统由两个分工明确的组件组成BBhash一种空间高效的哈希结构用于把键集合无冲突地映射到一段连续的整数区间即最小完美哈希函数 MPHF。其 master 分支支持 Plain Old DataPOD类型文档特别注明“alltypes”分支可支持包括字符串在内的更多类型——这正是为字符串主键所做的扩展。Value Array值数组一个按主键存储“段位置信息”的数组。数组中每个条目记录该主键所在的 Segment ID可使用 BBhash 的映射结果直接下标访问从而获得O(1)的查询效率。值数组采用 **mmap内存映射**实现由操作系统按需加载、按需回收内存。两者的配合逻辑非常简洁BBhash 负责“把 PK 变成一个紧凑的整数下标”Value Array 负责“按下标取出 Segment 元信息”。由于映射是完美哈希同一主键在构建期内恒定对应同一下标因此无需在索引中保存原始字符串。3.1 BBhash 的设计细节对静态键集合构建最小完美哈希函数BBhash 能做到如下性质每个键被唯一映射到一个紧凑整数下标例如user123 → 0user456 → 1user789 → 2处理字符串主键时直接作用于原始字节序列不做类型转换支持变长字符串无需存储原始字符串——下标由哈希结构推导而非查表得到对完整内容哈希降低碰撞概率内存占用极低详见本文第五部分的内存模型。3.2 BBhash 的工作流程多层哈希BBhashBin Bloom Hash通过多级哈希函数完成“无冲突映射”这一任务其工作流程为第一级哈希先尝试把所有键映射到互不冲突的位置发生冲突的键改用下一级哈希函数重新映射迭代进行直到所有键都被无冲突地安置。这也解释了为什么它适合静态键集合构建完成后集合不再变化才能保证每一级哈希的“递归拆解”稳定成立。反过来一旦有大量新主键写入Segment 内数据持续增长就需要重新构建索引这是设计中需权衡的地方。四、Index 落点与 L1/L2 Segment 的分层策略设计文档将主键索引放到一个分层的存储语境中下图展示了 Shard-partition 下 L1/L2 层级、Segment、Bucket 以及 Compaction 之间的关系针对不同层级的 Segment设计采取了差异化策略L1 Segment活跃/近实时数据数据尚在频繁写入与合并不为其构建主键索引仍使用 Bloom Filter 做近似过滤容忍误判带来的少量二次确认L2 Segment已合并的稳定数据为每个 bucket 下的数据构建PK → Segment的精确映射也就是本文所述 BBhash Value Array 主键索引。需要特别指出的是即使对 L2 构建了 PK → Segment 映射“误报”依然可能残留其来源有二已被删除的数据索引记录的是构建时刻的 PK 分布之后发生的删除不会立刻反映到映射中BBhash 极小概率的哈希碰撞设计文档给出的量级约为1/2³² ≈ 2.3×10⁻¹⁰。也就是说该映射更准确的说法是“PK 一定不会出现在未映射的 Segment 中无漏报但可能指向已含被删数据的 Segment有极低误报”命中后仍需要结合删除位图等做最终裁决。五、核心代码原型构建与查询设计文档给出了 C 风格的伪代码原型清晰地展示了“构建 落盘 查询”三个阶段的骨架。下面是完整继承的代码并补充了逐行语义注释// 构建主键索引输入 PK 集合与其所在 Segment 信息 void buildPrimaryKeyIndex(const std::vectorstd::string keys, const std::vectorSegmentInfo segmentInfos) { // 1. 以全部键初始化 BBhash 完美哈希器对字符串键直接散列原始字节 bbhash::PerfectHasherstd::string hasher(keys); // 2. 初始化与键数量等长的 Value Array std::vectorSegmentInfo valueArray(keys.size()); // 3. 对每个键查询其无冲突下标把 Segment 信息放入对应槽位 for (size_t i 0; i keys.size(); i) { size_t index hasher.lookup(keys[i]); // 完美哈希无冲突 valueArray[index] segmentInfos[i]; } // 4. 持久化到存储哈希结构与值数组分别落盘 hasher.save(bbhash.idx); saveValueArray(valueArray, value_array.bin); } // 查询给定主键返回其所在的 Segment 信息 SegmentInfo lookupPrimaryKey(const std::string key) { // 从磁盘加载或使用缓存实例 bbhash::PerfectHasherstd::string hasher; hasher.load(bbhash.idx); // 值数组可选用内存映射加载mmap 实例交由 OS 管理换入换出 std::vectorSegmentInfo valueArray loadValueArray(value_array.bin); // 常数时间查找未命中返回空 Segment 信息 size_t index hasher.lookup(key); if (index ! bbhash::NOT_FOUND) { return valueArray[index]; } return SegmentInfo(); }这段代码的要点在于构建期完成一次性的“键 → 下标”学习查询期只做一次哈希求值与一次数组访问因此单次查找是确定性的O(1)。六、内存效率模型单键 4.5 字节如何支撑十亿级索引能承载多少数据取决于单键的内存开销。设计文档给出了明确的内存账本组成开销1B十亿键规模下的总量BBhash最小完美哈希约 2–4 bits/键250–500 MBValue ArraySegment ID约 4 bytes/键约 4 GB合计约 4.5 bytes/键约 4.5 GB加上 mmap 实现允许操作系统按需加载与回收内存即使面对十亿级数据集也无需一次性把整份索引驻留内存——这正是该设计声称“支持亿级乃至十亿级数据集”的内存基础。结合第六部分的语义可以推断上述 Value Array 开销4 bytes/键对应的正是一个 4 字节的 Segment ID 条目若未来为点查优化而附加偏移量offset甚至更多字段见本文“后续工作”一节单键内存会相应上升需要在索引收益与内存成本之间权衡。七、性能分析文档给出的构建与查询基准设计文档对索引构建与查询给出了量化的性能分析这些数据属于设计文档作者在其测试环境中的评估口径在此完整呈现并作解读7.1 索引构建性能单线程BBhash 为 1 亿个键构造最小完美哈希函数MPHF约需10 秒即约1000 万键/秒多线程扩展性使用 8 线程为 10 亿个键构建 MPHF 约需35 秒约2857 万键/秒体现出接近线性的扩展十亿级构建可行性在 32 核服务器上理论构建时间约为10–15 秒实测端到端含数据读取与索引构建约1 分钟构建期峰值内存不超过 16 GB。这组数据意味着为 L2 稳定 Segment 构建/重建主键索引的成本是可接受的甚至可以在 Compaction 产出新 Segment 后以分钟级窗口完成索引刷新。7.2 查询性能主键索引 vs. 多个 Bloom Filter文档对“单个主键索引”与“1 万个 Bloom Filter 顺序查询”做了对比指标Primary Key Index10,000 个 Bloom Filters顺序查询差距查询时延约 200 纳秒/次约 10,000 × 10 ns 0.1 毫秒主键索引快约500 倍吞吐量每节点约 1000–2000 万 QPS每节点约 1000 QPS高并发场景优势明显需要说明的是Bloom Filter 顺序查询的耗时与 Segment/过滤器数量线性相关因此上述差距会随着 Segment 数量的增长而进一步扩大主键索引则不受 Segment 数量影响始终是常数级查找。7.3 精确度对比BBhash实际实现仍有极小概率的哈希碰撞但远低于 Bloom Filter约 2.3×10⁻¹⁰ 量级Bloom Filter单个过滤器的误报率通常配置在0.1%当需要顺序查询 1 万个 Bloom Filter 时累计误报率趋近 100%——即“任一过滤器误报”几乎必然发生导致大量多余的 Segment 二次确认。精确度对比揭示了系统演进的深层动机Segment 规模越大Bloom Filter 组合方案的误报与查询成本越不可控而从“近似集合”走向“精确映射”的主键索引是自然的收敛方向。八、与仓库现有实现的呼应按段 PK 索引与 Delegator 层的当前状态主键索引并非全新概念——在 Milvus 当前源码中Segment 内部已经存在主键索引的工程实现可以作为理解跨 Segment 全局索引的参照SegCore 的ChunkedSegmentSealedImpl提供了PinPkIndex接口负责“钉住”某段的主键索引单元以进行查找见 ChunkedSegmentSealedImpl.cpp并在需要时通过BuildPkIndexSlot惰性构建见同文件 第 579–586 行其底层索引单元PkIndexCell由OffsetMapPK → 行内偏移与CompressedInt64PkArray行内偏移 → 压缩存储的整型 PK组成由PkIndexTranslator负责按需构建并接入缓存层见 SystemIndexTranslator.h。从源码结构可以推断这套实现解决的是“单个 Segment 内通过 PK 精确反查行偏移”的问题。而本文所述设计文档的核心创新在于把同样的“精确化”思想从段内推广到跨段在 Delegator 这一层当前由 pkoracle 的 Bloom Filter 组合充当“PK 分布在哪个段”的近似裁判引入 BBhash Value Array把对候选 Segment 的近似过滤升级为全局精确索引。二者形成互补段内PkIndexCell / OffsetMap 负责拿到候选段后精确定位行跨段BBhash 全局索引负责第一步就把查询/删除请求路由到真正的主键所在段从而把误报与转发开销压缩到极致。九、待解决问题与后续方向设计文档在末尾列出了若干尚未定论的问题这些也正是社区继续演进该方案的重点方向性能验证面需要开展更完整的性能验证含构建与查询并与 CMPH 等其他 MPHF 库做横向对比能否下沉到单 SegmentBBhash 是否也能取代单个 Segment 内的 Bloom Filter例如替代 Segment 级近似过滤尚待评估误报处理策略残留误报已删数据、极小概率碰撞如何处理——直接忽略还是在各 Segment 内二次校验需要明确策略值条目冗余设计Value Array 条目当前仅含 Segment ID未来为点查优化可考虑额外记录行内偏移offset乃至更多字段用适度内存换更高查询效率。其中第 4 点与第八节提到的段内OffsetMap实现存在潜在协同若 Value Array 直接记录“段 段内偏移”一次索引访问即可直达目标行可将 point query 简化到近乎零次额外 IO。十、总结Milvus 主键索引设计文档展示了一条清晰的演进路线以 BBhash 最小完美哈希 mmap Value Array 为核心在 Delegator 中构建一张“PK → Segment”的全局精确映射并持久化到 S3。它在内存端以约 4.5 bytes/键的代价换取了纳秒级单次查找与约 500 倍于多 Bloom Filter 组合的查询优势目标直指写入去重、部分更新加速与删除转发优化三大场景。该设计与仓库现有的段内 PkIndexCell 精确索引、Delegator 层 pkoracle Bloom Filter 集合形成“段内精查 跨段粗筛”的梯度组合而把“粗筛”也升级为“精查”正是这份文档留给后续工程化的核心命题。延伸阅读Primary Key Index 设计文档原文Delegator 层当前使用的 BloomFilterSet 实现PK Oracle 的候选段判定逻辑Delegator 的 Delta 转发实现SegCore 中按段 PK 索引单元与转换器定义ChunkedSegmentSealedImpl 中 PK 索引的构建与访问【免费下载链接】milvusMilvus is a high-performance, cloud-native vector database built for scalable vector ANN search项目地址: https://gitcode.com/GitHub_Trending/mi/milvus创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考