5 个硬向量搜索问题以及我们如何在 Apache Cassandra 中解决它们

矢量搜索是生成式 AI 工具的关键组成部分，因为检索增强生成 (RAG) 的方式如下：耀斑帮助法学硕士融入最新的定制信息，同时避免产生幻觉。同时，矢量搜索是一项功能，而不是产品 - 您需要查询与其余数据相关的矢量，而不是孤立的，并且您不需要构建管道来同步其余数据数据与向量存储来做到这一点。

2023 年，矢量搜索产品和项目出现爆炸式增长，因此在其中进行选择变得非常困难。在研究这些选项时，您需要考虑以下难题以及解决这些问题的不同方法。在这里，我将引导您解决这些挑战，并描述 DataStax 如何解决这些挑战，以实现 DataStax Astra DB 和 Apache Cassandra 的矢量搜索。

内容概述

• 维度的诅咒
• 问题 1：横向扩展
• 问题2：高效的垃圾收集
• 边栏：云应用程序工作负载
• 问题3：并发
• 问题4：有效利用磁盘
• 问题 5：可组合性
• 包起来

维度的诅咒

这些难题的核心在于研究人员所说的“维度的诅咒”。这在实践中意味着在 2-D 或 3-D 空间中进行精确向量搜索的算法，例如kd树，当向量达到 10、100 或 1000 维时，就会崩溃。结果是，使用高维向量进行精确相似搜索没有捷径；为了获得对数时间结果，我们需要使用近似最近邻（ANN）算法，这在以下方面带来了挑战。

问题 1：横向扩展

许多矢量搜索算法是为适合单机内存的数据集而设计的，这仍然是唯一测试的场景安基准。 （Ann 基准进一步将其测试限制为单个核心！）对于一百万个文档或行的学术工作来说，这可能没问题，但已经很多年了，因为它可以被认为代表现实世界的工作负载。

与任何其他域一样，横向扩展需要复制和分区，以及用于处理替换失效副本、在网络分区后修复它们等的子系统。

这对我们来说很简单：横向扩展复制是 Cassandra 的面包和黄油，并将其与新的 Cassandra-5.0 SAI（存储附加索引 - 请参阅CEP-7了解它的工作原理，以及SAI 文档了解如何使用它）免费有效地为我们的矢量搜索实现提供了强大的横向扩展功能。

问题2：高效的垃圾收集

我所说的“垃圾收集”是指从索引中删除过时的信息——清除已删除的行，并处理索引向量值已更改的行。这似乎不值得一提——四十年来，这在关系数据库世界中或多或少已经解决了一个问题——但向量索引是独一无二的。

关键问题是，我们所知的所有提供低延迟搜索和高召回率结果的算法都是基于图的。还有许多其他可用的向量索引算法 - FAISS实现了其中的许多方法 - 但所有这些方法要么构建速度太慢，搜索速度太慢，要么提供的召回率太低（有时三者兼而有之！），无法成为通用解决方案。这就是为什么我所知道的每个生产向量数据库都使用基于图形的索引，其中最简单的是 HNSW。分层可导航小世界图是由 Yury Malkov 等人于 2016 年提出;这篇论文很有可读性，我强烈推荐它。有关 HNSW 的更多信息请参见下文。

图形索引的挑战在于，当行或文档发生更改时，您不能直接删除旧的（与向量相关的）节点；而是要删除旧的（与向量相关的）节点。如果您这样做多次，您的图将不再能够实现将 BFS（广度优先搜索）引导至与查询向量更相似的区域的目的。

因此，您需要在某个时候重建索引来执行垃圾收集，但是何时以及如何组织它呢？如果您总是在进行更改时重建所有内容，则会大量增加执行的物理写入次数；这称为写放大。另一方面，如果您从不重建，那么您将在查询时做额外的工作来过滤掉过时的行（“读取放大”）。

这是 Cassandra 多年来一直在研究的另一个问题空间。由于SAI索引附加到主存储生命周期，因此它们也参与Cassandra压实，它以对数方式增加存储单元，以在读取和写入之间提供健康的平衡。

边栏：云应用程序工作负载

DataStax Astra DB 基于 Apache Cassandra 构建，为云应用程序工作负载提供平台。

这意味着工作负载是：

• 每秒大规模并发数千到数百万个请求，通常每次只检索几行。这就是为什么你不能在 Snowflake 上运行 Netflix，即使你负担得起：Snowflake 和类似的分析系统设计用于仅处理几个并发请求，每个请求运行数秒到几分钟甚至更长时间。

  
  

• 大于内存如果您的数据集适合单台计算机的内存，那么您使用什么工具几乎并不重要。 Sqlite、MongoDB、MySQL——它们都可以正常工作。如果情况并非如此，事情就会变得更具挑战性 - 坏消息是矢量嵌入通常为几 KB，或者比典型数据库文档大一个数量级，因此您将相对快速地获得比内存更大的数据。

  
  

• 应用程序的核心如果您不在乎是否丢失数据，或者因为它不那么重要，或者因为您可以从实际的记录源重建数据，那么您使用什么工具也并不重要。 Cassandra 和 Astra DB 等数据库旨在确保您的数据在任何情况下都可用且持久。

问题3：并发

我在上面提到了众所周知的安基准比较将所有算法限制在单个核心上。虽然这创造了公平的竞争环境，但它也给那些能够利用过去二十年硬件改进的主要来源的人带来了障碍。

一个相关的问题是 ann-benchmarks 一次只执行一种类型的操作：首先，它构建索引，然后查询它。处理与搜索交错的更新是可选的——甚至可能是一个障碍；如果您知道不需要处理更新，则可以做出许多在人工基准测试中看起来不错的简化假设。

如果您关心能够对索引执行多个并发操作或在构建索引后对其进行更新，那么您需要更深入地了解它的工作原理以及涉及哪些权衡。

首先，据我所知，所有通用矢量数据库都使用基于图形的索引。这是因为一旦插入第一个向量，您就可以开始查询图形索引。大多数其他选项要求您在查询之前构建整个索引，或者至少对数据进行初步扫描以了解一些统计属性。

然而，即使在图索引类别中，仍然存在重要的实现细节。例如，我们最初认为可以通过使用 Lucene 的 HNSW 索引实现来节省时间，就像 MongoDB Elastic 和 Solr 那样。但我们很快了解到Lucene只提供单线程、非并发的索引构建。也就是说，您既不能在构建它时对其进行查询（这应该是使用此数据结构的主要原因之一！），也不能允许多个线程同时构建它。

HNSW 论文表明细粒度锁定方法可以发挥作用，但我们采取了更好的方法并构建了非阻塞索引。这是开源的向量。

JVector 将并发更新线性扩展至至少 32 个线程。该图在 x 轴和 y 轴上均按对数缩放，表明线程数加倍可使构建时间减半。

更重要的是，JVector 的非阻塞并发性通过将搜索与更新混合在一起，有利于更现实的工作负载。以下是 Astra DB 在不同数据集上的性能（使用 JVector）与 Pinecone 的比较。虽然对于静态数据集，Astra DB 比 Pinecone 快约 10%，但在索引新数据时速度快 8 到 15 倍。我们根据他们对更高吞吐量和更低延迟的建议，选择了最好的可用 Pod 层 Pinecone（Pod 类型：p2，Pod 大小：x8，每个副本 2 个 Pod）。 Pinecone 并没有透露这对应的物理资源。在 Astra DB 方面，我们选择了默认的 PAYG 部署模型，并且不必担心选择资源，因为它是无服务器的。测试使用进行NoSQLBench 。

Astra DB 在做到这一点的同时还保持了更高的召回率和精确率（ F1 是查全率和查准率的结合） :

问题4：有效利用磁盘

我们从HNSW 图索引算法因为它构建索引快、查询快、准确度高且实现简单。然而，它有一个众所周知的缺点：它需要大量内存。

HNSW 索引是一系列层，其中基础层之上的每一层的节点数大约是前一层的 10%。这使得上层能够充当跳跃列表，从而允许搜索在包含所有向量的底层的右邻域归零。

然而，这种设计意味着（与所有图索引一样）您不能逃避说“磁盘缓存将拯救我们”，因为与正常的数据库查询工作负载不同，图中的每个向量都有几乎相同的机会与搜索相关。 （上层是个例外，我们可以缓存它们。）

以下是我们使用 Lucene 时，在具有 64GB RAM 的桌面上提供 100M 维基百科文章块矢量数据集（磁盘上大约 120GB）的配置文件的样子：

Cassandra 几乎所有时间都在等待从磁盘读取向量。

为了解决这个问题，我们实现了一种更先进的算法，称为 DiskANN 并将其开源为独立的嵌入式矢量搜索引擎，向量。 （具体来说，JVector 实现了 DiskANN 的增量版本，参见FreshDiskANN简而言之，DiskANN 使用比 HNSW 具有更长边的单级图以及向量和邻居的优化布局来减少磁盘 IOPS，并在内存中保留向量的压缩表示以加速相似性计算。这使得维基百科工作负载的吞吐量增加了两倍。

以下是 HNSW 与 DiskANN 在没有客户端/服务器组件的纯嵌入式场景中的对比。这衡量了 Lucene (HNSW) 和 JVector (DiskANN) 下搜索 Deep100M 数据集的速度。 Lucene索引为55GB，包括索引和原始向量。 JVector 索引为 64GB。搜索是在我的 24GB MacBook 上执行的，它的内存大约是 RAM 中保存索引所需内存的三分之一。

问题 5：可组合性

数据库系统中的可组合性是指以一致的方式无缝集成各种特性和功能的能力。在讨论矢量搜索等新功能类别的集成时，这一点尤其重要。非玩具应用程序始终需要经典增删改查数据库功能以及新的矢量搜索。

考虑简单的 人工智能聊天机器人Astra DB 的示例应用程序。这与您会发现的纯粹的 RAG 应用程序一样，使用矢量搜索向 LLM 提供适当的文档以回答用户问题。然而，即使是这样一个简单的演示，仍然需要对 Astra DB 进行“正常”的非向量查询以检索对话历史记录，该历史记录也必须包含在对 LLM 的每个请求中，以便它可以“记住”已经发生的内容发生在。因此关键查询包括：

1. 查找与用户问题最相关的文档（或文档片段）
2. 从用户对话中检索最后二十条消息

在一个更现实的用例中，我们的一位解决方案工程师最近与一家亚洲公司合作，该公司希望将语义搜索添加到其产品目录中，但也希望启用基于术语的匹配。例如，如果用户搜索[“红色”球阀]，那么他们希望将搜索限制为描述与术语“红色”匹配的项目，无论向量嵌入在语义上多么相似。那么关键的新查询（除了会话管理、订单历史记录和购物车更新等经典功能之外）是：将产品限制为包含所有引用术语的产品，然后找到与用户搜索最相似的产品

第二个示例清楚地表明，应用程序不仅需要经典查询功能和矢量搜索，而且通常需要能够在同一查询中使用每个功能的元素。

这个年轻领域的当前技术水平是尝试在“普通”数据库中执行我所说的经典查询，在向量数据库中执行向量查询，然后在两者都满足时以临时方式将两者缝合在一起。同时需要。这容易出错、缓慢且昂贵；它唯一的优点是你可以让它工作，直到你有更好的解决方案。

在 Astra DB 中，我们在 Cassandra SAI 之上构建（并开源）了更好的解决方案。由于 SAI 允许创建与 Cassandra 稳定和压缩生命周期相关的自定义索引类型，因此 Astra DB 允许开发人员混合和匹配布尔谓词、基于术语的搜索和向量搜索，而无需额外的开销管理和同步单独的系统。这为构建生成式人工智能应用程序的开发人员提供了更复杂的查询功能，从而提高生产力并加快上市时间。

包起来

矢量搜索引擎是一项重要的新数据库功能，具有多种架构挑战，包括横向扩展、垃圾收集、并发性、磁盘的有效使用和可组合性。我相信，在为 Astra DB 构建矢量搜索时，我们能够利用 Cassandra 的功能为生成式 AI 应用程序的开发人员提供一流的体验。 在此处了解有关 Astra DB 的更多信息，或者如果您想近距离接触矢量搜索算法，请查看向量。

- 乔纳森·埃利斯 (Jonathan Ellis)，DataStax