《大规模分布式计算深入解析》8.3 全局与本地索引:两阶段召回与 routing

全局TopK需要每片实际有序ID与分数,多路归并不能截掉后片;局部预算、去重和路由遗漏分别影响召回。

输入合同先明确

每个参与分片返回同一度量、分数方向和查询版本下的有序(id,score)列表。协调者维护各列表头,用小/大优先关系取当前最优项,推进该片下一个元素。只接收一串主键、保留前perShardK项再截全局K不是归并。

本模型统一大分数优先、同分小ID优先;距离小值优先可以显式转换。重复副本的同ID同分只占一个最终名额,同ID异分被拒绝,提示数据/评分版本不一致,而不是静默选择一个值。

最优项全在最后一片

两片分数[1,2,3]与[100,101,102],各返回3条,全局Top3为最后一片ID5/4/3。旧函数只看第一段时会完全错过;新增用例直接用此反例验证。

如果每片只返回1条,则只能合成两个候选5/2,真Top3中的4/3已被局部截断。协调者不能通过“再排一次”恢复它们。对互斥分片、同一精确顺序、无去重等简化前提,每片至少K可覆盖全局精确TopK;近似局部搜索仍可能漏召回。

全局路由与本地索引

所有分片各有本地索引时,可以全扇出;若用额外粗中心/全局目录选少数分片,则减少RPC但引入路由遗漏风险。全局索引不天然保证近邻所在片都被选中,需要质量评估和可能的扩展探测。

4片每片10条是最多40候选;只路由2片是最多20。候选减少不等于召回保持,归并比较数也不必等于候选总数。

超时和快照

若一片失败,应按产品合同整体失败、重试或显式标记部分结果。不能把缺片TopK静默标成完整成功。迁移期间的双路由和副本结果还需去重及路由版本,以免重复计入或漏数据。

架构与流程

flowchart TD
 A["片A有序id/score"] --> H["每片列表头优先队列"]
 B["片B有序id/score"] --> H
 C["最后一片也必须参与"] --> H
 H --> TAKE["取最优;推进该片头"]
 TAKE --> DUP{"重复ID且同分?"}
 DUP -->|是| SKIP["不占新名额"]
 DUP -->|否且一致| OUT["加入全局结果"]
 OUT --> MORE{"已够K或耗尽?"}
 MORE -->|否| H
 MORE -->|是| DONE["返回实际条数"]

实现与验证边界

真实多路带分数归并、最后片最优、空片、局部不足、重复与同分均有测试。没有实现多节点路由或全局聚类索引;单机Milvus手工分区不能代签分片调度。

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

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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