介绍一种新的向量存储格式：DiskBBQ

DiskBBQ 是一种改进的倒排向量文件 (IVF) 索引。它是分层可导航小世界 (HNSW) 的一种替代方案，通过将向量划分为较小的簇，以更有效地处理低内存场景，同时提供良好的查询性能。

HNSW 的问题是什么？

我们非常喜欢 HNSW。这是一个快速且计算高效的算法，能够对向量数据进行对数级缩放。然而，这种速度是有代价的。为了让 HNSW 良好运作，所有向量都需要驻留在内存中。尽管我们通过引入更好的量化水平降低了成本，但仍然存在向量超出内存导致性能下降的问题。

此外，在进行索引时，您必须搜索现有的 HNSW 图。因此，所有内存成本在索引时也会出现。这可能会显著减慢无法完全在内存中保存向量的硬件的速度。

DiskBBQ 有何不同？

DiskBBQ 使用层次化 K-means将向量划分为小簇。它会先选择代表性的质心进行查询，然后再查询各个向量。它利用这种层次结构的多层特性，最多查询两个层次的质心，从而限制了总的查询空间。最后，通过批量计算簇内向量与查询向量之间的距离，来探索每个簇内的向量。

Hierarchical KMeans 算法流程示例。将向量分割成部分，聚类每个部分，并递归分割直到达到所需的分区大小。

图 0. Hierarchical KMeans 算法流程示例。将向量分割成部分，聚类每个部分，并递归分割直到达到所需的分区大小。

如其名，DiskBBQ 还使用我们的 BBQ（更好的二进制量化）来减小向量和质心的大小。这允许将多个向量块同时加载到内存中进行快速评分，同时要求的内存和磁盘开销非常低。

DiskBBQ 另一个有趣的方面是，它允许将向量分配给多个质心。它利用 Google 的正交增强残差溢出 (SOAR)版本将向量分配到多个簇，这在向量位于两个簇边界附近时特别有用。由于向量被大量量化，这只增加了极小的磁盘开销，并在搜索时需要探索的质心更少。

数据胜于雄辩

HNSW 以对数级缩放。因此，它必定比需要搜索质心然后评分质心中所有向量的方案快得多，对吧？

我们一直在努力让 DiskBBQ 完全与 HNSW 竞争。虽然我们还没有在所有情况下达到 100% 的水平，但我们对结果感到满意。

DiskBBQ 利用批量评分向量，并尽可能多地在堆外执行操作。这意味着我们可以直接从文件中读取向量到内存中进行优化的向量操作，从而产生相当不错的性能。

DiskBBQ 的两个主要场景特别有趣。第一个场景是整个索引可以放入内存中。由于这是 HNSW 性能的关键，因此看看 DiskBBQ 在这种情况下的表现是公平的。

表 0. 在超过 100 万个向量上 DiskBBQ 的表现对比。所有数据都舒适地驻留在内存中。DiskBBQ 的索引速度可以快 10 倍，同时在 BBQ 量化向量上几乎与 HNSW 一样快。

随着内存逐渐减少到整个索引无法再适应内存的程度，情况变得更加有趣。我们将会有一个单独的博客深入探讨 DiskBBQ 在低内存情况下表现更好的原因及我们的测试方法。以下是一些高层次的数字：

索引时间（毫秒）与 RAM / JVM 堆

图 1：显示索引时间（毫秒）与 RAM / JVM 堆的关系

随着整体内存减少，DiskBBQ 的索引性能逐渐下降。然而，一旦内存变得非常有限，HNSW 的性能就会完全崩溃。

图 2：显示搜索延迟（毫秒）与 RAM / JVM 堆的关系

同样，我们看到 DiskBBQ 的搜索延迟逐渐下降。确实，它开始变慢，但随着内存进一步受限，HNSW 的延迟开始呈指数级上升。

什么时候应该使用 DiskBBQ？

DiskBBQ 和 HNSW 都将在 Elasticsearch 中继续得到改进。目前，DiskBBQ 在非常高召回率（99% 以上）和非常低延迟方面的性能不如 HNSW。我们希望在继续投资 HNSW 的同时改善这一点。

如果您需要非常高的召回率，有大量的堆外内存（或者愿意为此付费），并且索引更新很少（因此索引成本较低），使用带有某种形式量化的 HNSW 可能仍然是最佳选择。

然而，如果您可以接受 95% 或更低的召回率，且对成本敏感，但仍然希望快速搜索，DiskBBQ 可能是您的解决方案。

如何使用 DiskBBQ？

以下是启用 DiskBBQ 并开始查询的方法：

设置映射如下：

{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "similarity": "l2_norm",
        "index_options": {
          "type": "bbq_disk"
        }
      }
    }
  }
}

插入一个向量：

{ "image-vector": [0.0127, 0.1230, 0.3929] }

以下是查询该向量的示例：

{
  "query": {
    "knn": {
      "field": "image-vector",
      "query_vector": [0.0127, 0.1230, 0.3929]
    }
  }
}

您仍然可以使用 num_candidates 来控制近似程度。

以下是查询该向量的示例：

{
  "query": {
    "knn": {
      "field": "image-vector",
      "query_vector": [0.0127, 0.1230, 0.3929],
      "k": 10,
      "num_candidates": 50
    }
  }
}

或者，如果您希望更精细地控制搜索考虑的向量数量，可以直接设置 visit_percentage。

以下是查询该向量的示例：

{
  "query": {
    "knn": {
      "field": "image-vector",
      "query_vector": [0.0127, 0.1230, 0.3929],
      "k": 10,
      "visit_percentage": 10.0
    }
  }
}

DiskBBQ 将很快在 Elasticsearch Serverless 中提供。