vespa 亿级向量索引方案 - 数据库

vespa 公司也是一个造向量数据库的，并且受欢迎的程度和 milvus 不相上下？这篇博客主要是对 vespa 的 billion vector 的方案进行解析 Billion-scale vector search using hybrid HNSW-IF。我看完了第一遍后，第一想法是没准真能行，这个方案有点 spann 的意思，但是比 spann 更加精炼。

# Spann

spann 这个算法我之前看过但是没有写博客，原因就是我觉得这玩意太啰嗦了，很难被工程化。我这里简单提一下这个算法：

层次 kmeans，进行质心的选取，质心用 SPTAG 建立索引。
非质心节点 assign 到对应的 post list（postlist 中包括了 id 和 vector）

spann 在这里做了两个优化：

$\begin{array}{r} \mathbf{x} \in \mathbf{X}_{i j} \Longleftrightarrow \operatorname{Dist}\left(\mathbf{x}, \mathbf{c}_{i j}\right) \leq\left(1+\epsilon_{1}\right) \times \operatorname{Dist}\left(\mathbf{x}, \mathbf{c}_{i 1}\right) \\ \operatorname{Dist}\left(\mathbf{x}, \mathbf{c}_{i 1}\right) \leq \operatorname{Dist}\left(\mathbf{x}, \mathbf{c}_{i 2}\right) \leq \cdots \leq \operatorname{Dist}\left(\mathbf{x}, \mathbf{c}_{i K}\right) \end{array}$

一个是非质心节点 assign post list 的个数，也就是如果其他质心与 x 的距离比离 x 最近的质心的距离要大过一定比例，那么就直接放弃。

另一个优化就是 $\operatorname{Dist}\left(\mathbf{c}_{i j}, \mathbf{x}\right)>\operatorname{Dist}\left(\mathbf{c}_{i j-1}, \mathbf{c}_{i j}\right)$ ，简单来说也就是用 rng 的思想。

搜索也是一样：

$\begin{array}{r} \mathbf{q} \stackrel{\text { search }}{\longrightarrow} \mathbf{X}_{i j} \Longleftrightarrow \operatorname{Dist}\left(\mathbf{q}, \mathbf{c}_{i j}\right) \leq\left(1+\epsilon_{2}\right) \times \operatorname{Dist}\left(\mathbf{q}, \mathbf{c}_{i 1}\right), \\ \operatorname{Dist}\left(\mathbf{q}, \mathbf{c}_{i 1}\right) \leq \operatorname{Dist}\left(\mathbf{q}, \mathbf{c}_{i 2}\right) \leq \cdots \leq \operatorname{Dist}\left(\mathbf{q}, \mathbf{c}_{i K}\right) \end{array}$

# Hybrid HNSW-IF

作者直接说，他们是受到了 spann 论文的启发

Inspired by the SPANN paper, we at the Vespa team implemented a simplified version of SPANN using Vespa primitives, released as a Vespa sample application. We call this hybrid ANN search method for HNSW-IF .

# 索引的构建

# 质心向量的索引构建

不同于 spann 使用层次 kmeans 来进行质心的搜寻，HNSW-IF 随机地将 20% 的向量作为质心，然后对这些质心向量进行 HNSW 索引构建。构建得到的图还有向量全部存放在内存当中。

# 非质心向量的索引构建

直接通过对 HNSW 进行 search 得到 k 个接近的 centroid，然后根据 spann 的裁剪策略 assign 到这些 post list 中。注意，这里不再是存放 id+vector 向量，而是存放 distance+id，也就是它的倒排索引的含义。

# 查询算法

先从 HNSW 中查对应的 centoid 节点。

# cluster centroid dynamic pruning

这个就是上面 spann 的剪枝策略。先查出 centroid 然后就可以导入 post list。

# Retrieve using dynamic pruning

这里文章中提到了一个两阶段 rank 策略。

根据 closeness (q, centroid) * closeness (centroid, v) 计算 post list 中点的权重 z，根据权重进行排序，取固定数量的点。
从 disk 中取出全精度的向量，然后再计算与 query 的距离，最后进行 rank 输出 topk。

# 构建参数

HSNW：

 <nodes deploy:environment="perf" count="1" groups="1">
    <resources memory="128GB" vcpu="16" 
      disk="200Gb" storage-type="remote"/>
</nodes>

非质心索引构建：

<nodes deploy:environment="perf" count="4" groups="1">
    <resources memory="32GB" vcpu="8" 
      disk="300Gb" storage-type="local"/>
 </nodes>

ANNS