“请使用流量工作负载来对向量数据库进行基准测试”
优化‘使用流量工作负载对向量数据库进行基准测试’的标题
为什么静态负载不足以支持，并通过对比HNSWLIB和DiskANN在流式负载中的使用所学到的
向量数据库是为高维向量检索而构建的。如今，许多向量都是由深度神经网络生成的嵌入，如GPTs和CLIP，用于表示文本、图像或音频等数据点。嵌入在许多应用中被使用，如搜索引擎、推荐系统和聊天机器人。您可以在向量数据库中对嵌入进行索引，该数据库使用近似最近邻（ANN）索引来支持通过余弦或欧几里德距离函数快速检索最相似的邻居。对于100万个向量的索引，延迟为2到10毫秒，并且与索引大小的规模是次线性的（即O(log n)）。
在本文中，我指出了我们当前评估ANN索引的几个问题，并提出了一种新的评估方法。本文侧重于用于嵌入向量的ANN索引，这是最近受到大量关注的领域：向量数据库初创公司如Pinecone、Zilliz、Qdrant和Weaviate提供嵌入索引和检索作为它们的核心服务。
1. 静态负载基准测试不足以支持。
评估ANN索引的标准方法是使用静态负载基准测试，它由固定的数据集和固定的查询集组成。
静态负载基准测试首先从固定的数据集构建ANN索引，然后使用不同的参数设置多次运行固定的查询集，并在每个最小准确性水平下测量最高可实现的查询吞吐量。在对每个ANN索引执行相同的过程之后，基准测试会生成如下图所示的绘图：
上图比较了使用称为glove-100-angular的静态负载的不同ANN索引，该负载包含单词的嵌入。
这种评估方法在5年前的ann-benchmarks项目中被推广。现在，许多向量数据库都在他们的技术博客中使用这种方法来衡量性能。请参阅Qdrant基准测试和Timescale基准测试。
静态工作负载基准在我们比较不同索引算法的准确性和查询性能权衡时非常有用，因为结果易于理解，并允许我们使用相同的图表来进行比较。
但它并不是对ANN索引的完整评估，而且您不应该仅基于此选择用于项目的ANN索引。它过分强调召回准确性和查询性能，而忽略了其他重要方面，如索引性能和内存使用。
索引性能应得到反映。
索引吞吐量测量ANN索引接受新数据点的速度。与查询吞吐量类似，它通常与召回准确性呈反比关系。例如，下面的图表显示了HNSWLIB和DiskANN Vamana索引的索引吞吐量与召回的关系。
该图表类似于之前的召回-QPS图表，但是从该图表可以看出，更高的召回也是索引性能的取舍。然而，如果我对索引和查询性能都感兴趣，该图表仍然不够，因为它没有显示固定基准中进行召回性能权衡所需的余地。
许多ANN索引支持批量索引API，这可以比逐个添加向量的点索引更加优化，并且可以创建更准确的索引。例如，基于集群的ANN索引会批量构建所有向量的聚类。静态工作负载基准分离了索引和查询工作负载，因此鼓励使用可能不现实的批量索引。
与索引相关的另一个问题是产品量化（PQ）。许多ANN索引使用PQ或其他形式的向量压缩来加速计算。静态工作负载基准允许ANN索引在查询阶段开始之前构建优化的压缩码本，但在实践中可能无法实现这种最佳编码本。
内存使用量很重要。
大多数流行的ANN索引都是内存中的，这意味着它们的主要数据结构保留在易失性存储器（DRAM）中，用于提供查询。因此，衡量内存效率及其与性能和召回准确性的权衡非常重要。例如，在这篇研究论文中，作者测量出HNSW使用10亿个点的内存使用量为490 GB，而NSG为303 GB，但在召回和查询性能方面，HNSW只略微优于NSG。在对ANN索引进行基准测试时，这种权衡应该是首要考虑的。
然而，仅通过静态基准来获取内存效率的实际情况很困难，原因有几个。首先，ANN索引算法可以创建一个读优化的索引，非常紧凑，但会牺牲后续的索引性能。其次，工作负载只捕捉纯索引或纯查询，而不是两者的混合，这在实际场景中（如问答引擎或聊天机器人）中更容易发生，其中不断出现新数据。
数据分布会随时间变化。
在静态基准中，数据和查询集是不变的。这并不现实，因为数据和查询是由最终用户的兴趣驱动的，而兴趣会随时间变化。如果数据和查询集始终固定不变，那么最佳索引就是一个记忆所有查询结果的缓存。最近的ANN索引研究（例如FreshDiskANN）已开始测量分布之外的查询性能，这是一个向正确方向迈进的步骤。
删除操作呢？
删除API已成为ANN索引的标准，但没有静态基准来衡量。能够处理删除操作很重要，因为新兴的与AI相关的应用场景（例如聊天机器人）正在使用ANN索引作为类似在线事务处理（OLTP）数据库的操作性存储，其中数据不断添加和修改。
2. 流式工作负载会告诉您更多信息。
如果一个ANN索引支持以下API：
- Insert(ID, 向量)
- Query(向量)
- Delete(ID)
并且如果使用场景除了静态数据和查询之外的任何情况（例如，每个场景？），那么流式工作负载基准可以更深入地了解ANN索引的特性以及它们在您特定使用场景中的性能。
流式工作负载基准由两个流组成：一个数据流对应于Insert和Delete API调用的序列，以及一个查询流对应于Query API调用的序列。可以使用实际的流式系统，如Kafka，或更简单地使用一个类似于静态基准使用的数据集和查询集的指针序列的运行簿来实现。
上图展示了在NeurIPS 23′ Big ANN Benchmarks中使用的流式工作负载基准。具体来说，运行簿中的每个步骤对应于一批向量，因此操作可以并行执行。这种方法具有以下优点：
- 灵活性：可以将工作负载模式和数据分布变化建模为不同的流式工作负载，然后编译成不同的运行簿。
- 逼真：索引和查询交替进行，因此ANN索引必须适应未来的插入。此外，内存配置更准确地反映出实际的工作负载。
- 简单分析：性能可以用整体吞吐量来描述，而不是索引与查询吞吐量，因此可以轻松地可视化召回率和性能之间的权衡。
- 完整性：还评估了插入和删除操作。
在本博客文章中，我将深入探讨上述第4点，并展示使用流式工作负载基准发现的新见解。
比较召回率稳定性：HNSW vs. Vamana
在运行流式工作负载基准时，我们收集的一个重要指标是每个查询操作的召回率。我们可以通过观察其随时间的召回率稳定性来比较不同的索引设置（参数、算法等），并决定哪个索引适用于给定的使用场景。
我测量了在DiskANN的Vamana和各种HNSW实现下，根据NeurIPS 23′ Big ANN Benchmarks中的最终运行簿定义的流式工作负载的召回率稳定性。
关于Vamana和HNSW的一些背景知识：它们都是基于图的ANN索引，尤其擅长处理嵌入向量。在图的ANN索引中，每个向量是一个节点，查询执行为图遍历。通过有选择地构建有向边来限制内存使用，同时保证从任意节点到任意节点的快速遍历。在原地删除期间，对于被删除节点的每个入度邻居节点，图的ANN索引会执行边修复以维护有向图结构。
我们使用的第一个HNSW实现基于HNSWLIB，使用一个名为repairConnectionsForUpdate的修复算法实现了添加的Delete API，这已经是HNSWLIB的源代码的一部分。其思想是对要修复的节点执行“重新插入”操作，并更新其在各个层级上的出度邻居节点。下图显示了Vamana和HNSW的召回率随时间的变化。
请注意，我将Vamana的最大度参数设置为40 (R = 40)，并将HNSW的基础层的最大度也设置为40 (M = 20, M0 = 40)。因此，它们应该使用几乎相同的内存。
从此图中可以清楚地看出，删除对召回率有不利影响，因为在连续删除期间，召回率单调下降。相比之下，HNSW受到删除的影响要比Vamana大得多。
我们使用的第二种HNSW实现是用Vamana的边修复算法替换了HNSWLIB的，这两者非常不同。Vamana的边修复算法的思想是将已删除节点的每个入度邻居连接到已删除节点的出度邻居，并应用修剪步骤以保持最大度约束。在这种情况下，我们使用HNSW的原始修剪算法。它由HNSWLIB中的一个名为getNeighborsByHeuristic2的函数实现。
在所有参数保持不变的情况下，将HNSWLIB的边修复算法更改为Vamana的立即改善了HNSW的召回稳定性。
我们再更进一步，将HNSW的边修剪算法改为Vamana的算法。现在，HNSW索引几乎与Vamana的索引相同，只是它有多个层次。我们将这个索引称为“多层次Vamana”。
您可以看到，HNSW的召回率现在略高于Vamana的，同时使用了类似的内存量。我在任何研究论文中都没有找到这个观察结果。此外，尽管性能未在图中显示，但我注意到切换到Vamana的修剪算法时出现了显着的减速。
总之，通过使用流式工作负载基准测试，我能够发现关于不同的边修复和修剪算法的新事物。下一个逻辑步骤将是研究这些算法的性能影响，我可以通过使用流式工作负载基准测试来完成这项工作。
3. 结论
总而言之，在这篇博文中，我指出了静态工作负载基准测试对ANN索引的现实评估不足，并描述了我认为更好的替代工作负载基准测试-流式工作负载基准测试。我还使用了特定的流式工作负载来揭示HNSW和Vamana索引之间的新比较。向背后的团队致以赞誉NeurIPS 23′ Big ANN Benchmarks! 他们开源了我在这篇博文中使用的流式工作负载。
我们需要一个针对向量数据库的TPC-C和TPC-H。
在基准测试方面还有很多工作要做。ANN索引是向量数据库的核心功能，它们已经筹集了超过3.5亿美元的资金。然而，他们中的许多人仍然使用已过时的方法来测量性能，这不再反映实际的使用场景。数据库系统在90年代和2000年代初经历了类似的阶段。然后，像TPC-C和TPC-H这样的标准基准测试被开发出来，并且至今仍在使用。对于向量数据库，我们应该有类似的东西。
