Meilisearch 通过 Arroy 的过滤磁盘 ANN 扩展搜索能力

这是系列博客文章的第三部分， 最初发布在我的个人博客上。 请从 第一部分 和 第二部分开始。

我们可以在Arroy中存储向量并高效计算搜索树节点，但我们仍需要一些功能才能使其在Meilisearch中可用。我们的全文搜索引擎对过滤有很好的支持；选择文档子集是一个必不可少的功能。例如，我们最大的客户之一需要能够通过超过1亿个YouTube视频元数据及其相关的图像嵌入进行过滤，以有效选择在特定时间范围（如一天或一周）内发布的视频。这代表了我们旨在通过过滤系统解决的可伸缩性和响应性挑战，使其成为定制我们开发的完美用例。

Meilisearch支持对文档的可过滤属性使用以下运算符： <、 <=、 =、 !=、 >=和 >。在内部，我们广泛使用 RoaringBitmap，这是一种经过优化的整数集，支持快速的二进制操作，如并集和交集。当引擎收到带有过滤器的用户请求时，它首先计算将输入到搜索算法中的文档子集（即按质量对文档进行排名的算法）。这个子集由一个 RoaringBitmap表示。

在Arroy之前它是如何工作的？

自2018年以来，仅对已过滤的文档子集进行排名一直运行良好，但现在我们有了新的数据结构可以进行搜索，我们需要研究如何实现它。该引擎已经支持向量存储功能数月，但效率低下。我们当时使用的是内存中的HNSW，并将整个数据结构反序列化到内存中，搜索目标向量的最近邻，并返回一个迭代器。

fn vector_store(db: Database, subset: &RoaringBitmap, target_vec: &[f32]) -> Vec<DocumentID> {
    // This takes a lot of time and memory.
    let hnsw = db.deserialize_hnsw();

    let mut output = Vec::new();
    for (vec_id, vec, dist) in hnsw.nearest_neighbors(target_vec) {
        let doc_id = db.document_associated_to_vec(vec_id).unwrap();
        if !output.contains(&doc_id) {
          output.push(doc_id);
          if output.len() == 20 { break }
        }
    }

    output
}

您可能想知道我们为什么要检索与向量ID关联的文档ID。自向量存储功能开始以来，Meilisearch一直支持一个文档多个向量。这很不幸，因为我们必须查找正在迭代的每个向量。我们需要维护这个查找表。如果子集足够小，例如 document.user_id = 32，迭代器可以遍历整个向量数据集。我们希望文档操作是原子且一致的，因此我们必须将HNSW存储在磁盘上，并避免在LMDB事务和此向量存储数据结构之间维护同步。噢！并且该库不支持增量插入。每次插入单个向量时，我们都必须从头开始在内存中重建HNSW。

在Meilisearch中集成Arroy

在我们更新 Meilisearch 以包含新的向量存储 Arroy 的过程中，我们首次尝试了结对编程。这是我们所有人同时进行编码的方式。这听起来可能会让我们变慢，但实际上却让我们效率极高！通过在问题出现时就一起解决它们，我们比单独工作更快地将 Arroy 融入 Meilisearch。

Arroy 的不同之处在于它不会返回迭代器来给出搜索结果。现在，我们的搜索引擎更智能，即使需要考虑过滤器，它也能准确地计算出需要返回的结果数量。这次合作改进了我们的搜索工具，并向我们展示了在面对大型技术挑战时，团队合作是关键。

在Arroy中搜索时进行过滤

您可以在本系列的第一部分中找到Arroy内部数据结构的描述。以下是您可以找到的不同类型节点的列表

• 项目节点。用户提供的原始向量。左边的小点。
• 普通节点，也称为分割平面。它们代表将项目节点子集一分为二的超平面。
• 后代节点。它们是树叶，由如果您遵循某个普通节点路径将找到的项目ID组成。

典型的搜索会将所有普通节点加载到一个与无限距离相关联的二叉堆中。请记住，有许多随机生成的树，因此有许多入口点。二叉堆按距离升序排列；找到的最短节点将首先弹出。

在搜索算法中，我们从这个堆中弹出最近的项。如果它是一个普通节点，我们获取超平面的左侧和右侧

• 如果我们再次发现普通节点，我们将超平面到目标/查询向量的距离关联为正距离和负距离。
• 如果我们发现后代节点，我们不会将它们推入队列，而是直接将它们添加到潜在输出列表中，因为它们代表我们找到的最近向量。

您可能已经注意到我想去哪里，但这就是奇迹发生的地方。我们修改了Arroy，将后代列表存储在 RoaringBitmap中，而不是原始的整数列表。这是与原始Spotify库相比的另一个改进，因为这些列表的权重更小。现在，与过滤子集进行交集变得更容易了。

然而，总有一个问题：向量ID不是文档ID，Meilisearch在执行过滤器后，只知道文档。遍历我之前提到的查找表，构建包含所有与过滤文档对应的向量ID的最终位图在许多文档属于此子集时（例如 document.user_id != 32）效率不高。我不建议在搜索函数中使用 O(n) 算法。

使用多个索引进行高效过滤

幸运的是，我们开发了一个有趣的功能，它在Arroy中并非为此目的设计：在单个LMDB数据库中支持多个索引。我们最初开发多个索引功能是为了能够只打开一个LMDB数据库来存储不同的向量类型。是的！在Meilisearch v1.6中，您可以描述存在于单个索引中的不同嵌入器。您可以使用不同维度和距离函数的不同数量的嵌入器来标识不同的向量，这些向量可以存储在单个文档中。为单个文档定义与同一嵌入器关联的多个向量也是可能的。

索引由 u16标识。此功能可以欺骗算法，使其比以前的HNSW解决方案更高效。在一个文档中为每个嵌入器和向量使用一个存储很有趣，因为我们现在可以使用文档ID标识向量。不再需要查找数据库和向量ID。向量ID被简化为文档ID。我们可以使用过滤器的输出来过滤arroy索引。

Meilisearch 方面的搜索算法有所不同。我们请求每个 Arroy 索引中的最近邻，按文档 ID 对结果进行排序以进行去重，避免多次返回同一文档，再次按距离排序，然后只返回前二十个文档。这可能看起来很复杂，但我们指的是单个文档的向量数量乘二十个文档。通常，用户只会有一个向量。

fn vector_search(
    rtxn: &RoTxn,
    database: Database,
    embedder_index: u8,
    limit: usize,
    candidates: &RoaringBitmap,
    target_vector: &[f32],
) -> Vec<(DocumentId, f32)> {
    // The index represents the embedder index shifted and
    // is later combined with the arroy index. There is an arroy
    // index by vector for a single embedded in a document.
    let index = (embedder_index as u16) << 8;
    let readers: Vec<_> = (0..=u8::MAX)
        .map(|k| index | (k as u16))
        .map_while(|index| arroy::Reader::open(rtxn, index, database).unwrap())
        .collect();

    let mut results = Vec::new();
    for reader in &readers {
        let nns = reader.nns_by_vector(rtxn, target_vector, limit, None, Some(candidates)).unwrap();
        results.extend(nns_by_vector);
    }

    // Documents can have multiple vectors. We store the different vectors
    // into different arroy indexes, we must make sure we don't find the nearest neighbors
    // vectors that correspond to the same document.
    results.sort_unstable_by_key(|(doc_id, _)| doc_id);
    results.dedup_by_key(|(doc_id, _)| doc_id);

    // Sort back the documents by distance
    results.sort_unstable_by_key(|(_, distance)| distance);
    results
}

这些改进背后的设计理念

我们正在努力使 Meilisearch 足够灵活，以满足每个人的需求。无论您的文档是由单个嵌入（如 OpenAI 巧妙工具生成的类型）驱动，还是混合使用文本和图像嵌入（如许多电子商务网站所做），我们都希望您的搜索体验是无缝的。对于使用多模态嵌入器生成多个嵌入的超级用户，我们也没有忘记你们。我们的最新改进确保每个人都可以增量更新和微调他们的搜索索引，使整个过程像黄油一样顺滑。

非常感谢大家：总而言之，向团队——@dureuill、@irevoire和@ManyTheFish——致以崇高的敬意，感谢他们卓越的才华和辛勤的付出，将我们的想法变为现实。请关注@irevoire即将发布的文章，他将在其中解释我们如何在Arroy中实现增量索引——这意味着您可以添加新向量而无需从头开始重建一切。更多信息即将发布！

您可以在 Lobste.rs、 Hacker News、 Rust Subreddit 或 X (原 Twitter) 上评论本文。

Meilisearch 是一个开源搜索引擎，它不仅为最终用户提供最先进的体验，还提供简单直观的开发人员体验。

如需了解更多关于 Meilisearch 的信息，您可以加入 Discord 社区或订阅 新闻通讯。您可以通过查看 路线图 并参与 产品讨论 来了解更多产品信息。