《大规模分布式计算深入解析》6.2 束搜索与多线程:efSearch、并发调度与结果一致

ef是图内搜索预算,线程数是执行调度;分片候选数不是归并比较次数,结果确定性还需同分规则和固定查询版本。

图搜索与任务并行是两层

单个HNSW查询维护前沿C、结果W和visited,ef控制保留预算,详见2.2。把整个索引分段后,每段可以独立执行搜索任务,任务数和线程数控制并发;它们不是同一个W。

高层通常用窄搜索定位,层零采用目标搜索预算。不能说“堆宽W,因此最多访问W个点”;邻接检查和已评估但未保留的点都可能更多。

本卷真实线程池路径

Beam.parallelMerge把分数数组按互斥区间划为threads段,向ExecutorService提交任务;每段排序并保留perShardK,再收集实际列表并调用带分数全局归并。测试记录真实worker名称,不再用一个忽略threads的全排序函数冒充多线程。

分数大值优先、并列按较小ID。真实距离路径可用负平方距离转换为该评分合同;不能把小值优先与大值优先的列表混放进同一归并器。

候选、比较与确定性

4段各返回64条,最多256条候选进入协调者。这不是“恰好256次比较”:排序、输入校验、堆操作、去重和提前停止都有自己的次数。多路归并只需逐步推进有希望的列表头,但本教学实现还会先遍历候选检查排序和副本分数一致性。

固定数据、参数、分片结果和并列规则后,归并顺序可确定;这不保证任意产品在并发写、动态路由、近似候选变化或浮点实现变化下永远返回同一序列。

失败处理

本模型任一Future失败会使调用失败并清理任务,不返回静默缺片的成功TopK。生产系统还需决定是否允许部分结果、如何标记、如何超时和取消、重试使用哪个快照。增加线程可能增加竞争和尾延迟,不能只按线程数线性外推吞吐。

架构与流程

flowchart TD
 Q["查询与固定分片输入"] --> EXEC["ExecutorService提交真实任务"]
 EXEC --> A["片A:本地评分与截断"]
 EXEC --> B["片B:本地评分与截断"]
 A --> JOIN["收集带ID和score的列表"]
 B --> JOIN
 JOIN --> MERGE["多路归并、去重、固定同分规则"]
 MERGE --> R["实际TopK"]
 EXEC --> ERR["任务失败:整体失败并取消/清理"]

实现与验证边界

真实ExecutorService分段、空段、最后一片最优、并列规则、非法线程数和候选不足均有用例。线程竞争、分布式RPC和产品内部并行度未实测。

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

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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