Approximate Nearest Neighbors (HNSW / IVF): 解释十亿级索引的分片与路由。

Core Concept: 把索引分到多机（按向量/按簇/按哈希）；查询需'路由到相关分片'并'合并结果'；关键是减少需访问的分片数。

数学机理：<strong>十亿级索引的分片</strong>——单机内存无法容纳（1e9×768×4 字节 ≈ 3 TB），故需<strong>分片（sharding）</strong> 到多机。<strong>分片方式</strong>——(1) <strong>随机分片（random）</strong>——按文档 id 哈希分片；<strong>问题</strong>——查询时<strong>必须访问所有分片</strong>（因为不知道最近邻在哪个分片）→ <strong>扇出（fan-out）大</strong>（延迟 = 最慢分片 + 合并）；<strong>优点</strong>——简单、负载均衡。(2) <strong>按簇分片（cluster-based / IVF-style）</strong>——先做<strong>全局聚类</strong>（或用粗粒度量化），把相近的向量分到同一分片；查询时<strong>只访问'最近的若干簇'所在的分片</strong>；<strong>优点</strong>——扇出小（只查少数分片）；<strong>缺点</strong>——需维护全局的簇到分片的映射（且分片负载可能不均）。(3) <strong>按元数据分片</strong>——按类别/时间/地区分；<strong>优点</strong>——支持'过滤 + 路由'（只查相关分片）；<strong>缺点</strong>——分片粒度受限（元数据基数低）。(4) <strong>混合</strong>——先按元数据路由，再在子集内按簇路由。<strong>路由（routing）</strong>——决定查询发到哪些分片：(a) <strong>全扇出</strong>（随机分片）——延迟高（最慢分片决定）；(b) <strong>选择性路由</strong>（按簇/元数据）——只查相关分片（延迟低）；(c) <strong>两层路由</strong>——先用'路由索引'（小）定位到候选分片，再在分片内检索。<strong>合并（merge）</strong>——各分片返回本地 top-k，<strong>全局合并</strong>取 top-k；<strong>注意</strong>——(a) 每个分片需返回 <strong>k 个</strong>（而非 k/S）以保证全局正确；(b) 若用'分数'合并需分数可比（同空间）；(c) 若用'排名'可 RRF。<strong>关键指标</strong>——(a) <strong>扇出（fan-out）</strong>——访问的分片数（越小越好）；(b) <strong>延迟</strong>——由最慢分片决定（故需负载均衡 + 慢分片检测）；(c) <strong>召回率</strong>——分片 + 路由会引入额外损失（需测）；(d) <strong>负载均衡</strong>——热点分片会成为瓶颈。<strong>实践建议</strong>——(a) <strong>随机分片 + 全扇出</strong>（简单，适合分片数少，如 <10）；(b) <strong>按簇分片 + 选择性路由</strong>（分片多时必需）；(c) <strong>按元数据分片</strong>（支持过滤）；(d) <strong>每分片返回 k 个</strong>（保证全局正确）；(e) <strong>负载均衡 + 慢分片监控</strong>（延迟由最慢决定）；(f) <strong>测分片后的召回率</strong>（vs 单机）。<strong>度量</strong>——(a) 扇出数；(b) 延迟（P50/P99）；(c) 召回率；(d) 各分片的负载均衡度；(e) 成本。

深度剖析与工程权衡：① <strong>'随机分片必须全扇出'是关键约束</strong>——它使延迟由'最慢分片'决定；面试中能指出这一点是深度理解的标志。② <strong>'按簇分片减少扇出'</strong>——这是'用聚类换延迟'的思路；是十亿级的必需。③ <strong>'每分片返回 k 个'</strong>——易被忽略但必要（否则全局 top-k 不正确）。④ <strong>'延迟由最慢分片决定'</strong>——故需负载均衡 + 慢分片检测（尾延迟是分布式检索的核心问题）。⑤ <strong>'分片引入额外召回损失'</strong>——需测量（vs 单机基线）；这是'分布式'的代价。⑥ <strong>面试要点</strong>——被问'十亿级索引怎么分片'，应给出'<strong>随机（全扇出）/ 按簇（选择性路由）/ 按元数据 + 路由 + 合并（每分片返回 k）+ 负载均衡</strong>'与'<strong>扇出决定延迟</strong>'；能指出'延迟由最慢分片决定'是深度理解的标志。