《大规模分布式计算深入解析》3.1 IVF:聚类、倒排桶与 nprobe 路由

IVFFlat的粗中心路由与桶内扫描分开记账;N8000/nlist64/nprobe8的总算距为1064,不把固定中心分配称为完整训练。

IVF家族与IVFFlat

IVF把库向量分配给粗量化器的列表;IVFFlat在列表里保留原向量,IVFPQ则使用压缩码。只有IVFFlat可以直接描述为“所选桶内按原向量精确算距”,不能把该性质推广给所有IVF变体。

典型训练先学习nlist个中心。插入时找最近中心并记录桶归属;查询时对中心路由,选nprobe个列表,再扫描列表内数据。训练、赋桶和查询是三个阶段,不能把每次查询重算全库赋桶的成本藏在查询计数之外。

本卷实际实现了什么

Ivf.train执行有限轮Lloyd:确定性初始化,最近中心分配,成员均值更新;空桶保留原中心,达到迭代上限或中心不再变化便结束。它不保证全局最优,也没有生产级采样、k-means++、并行和重新训练策略。

Ivf.Flat构建时保存向量和中心副本、预先赋桶;查询先缓存每个中心的距离并排序,再对选定桶成员做精确TopK。中心距离不在排序比较器中重复计算。候选不足K返回实际条数。

均匀桶例子的三本账

N=8000、nlist64,每桶125条。穷举中心路由先算64次;nprobe8扫描1000条,合计1064次;nprobe16扫描2000条,合计2064次。若改用近似粗量化器,中心访问与误差又有不同合同。

桶不均匀时扫描量必须对实际桶成员数求和,不能只取nprobe/nlist乘N。选择的桶集合嵌套、距离和选择规则保持不变时,扩大精确扫描范围不会减少可获得的真近邻;复杂压缩、过滤和预算交互不能直接沿用这个简单结论。

更新与退化

数据分布漂移会让训练中心不再合适,单桶热点也会增加尾延迟。重新训练会改变赋桶,需重新编码或迁移数据并受控切换。nprobe=nlist对IVFFlat意味着全库扫描,可接近精确基线;对压缩IVFPQ仍有量化误差,除非另有精排。

架构与流程

flowchart TD
 TRAIN["有限Lloyd训练nlist中心"] --> BUILD["构建:预先赋桶并持有原向量"]
 Q["查询q"] --> C["计算并缓存nlist个中心距离"]
 C --> P["选择nprobe列表"]
 BUILD --> SCAN["扫描所选列表实际成员"]
 P --> SCAN
 SCAN --> R["精确桶内TopK;中心/成员计数分开"]

实现与验证边界

模型实际执行有限训练、赋桶和查询,验证中心/成员/总数与精确结果。Milvus产品IVF索引未实测;当前原生场景不以HNSW替代它。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 ivf.IvfSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路