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

这是系列博客文章的第 3 部分 最初发布在我的个人博客上。从 第 1 部分 和 第 2 部分开始这段旅程。

我们可以在 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。

将 Arroy 集成到 Meilisearch 中

当我们致力于更新 Meilisearch 以包含新的向量存储 arroy 时，我们第一次尝试了结对编程。这是我们所有人同时一起编写代码的地方。这听起来可能会减慢我们的速度，但实际上它使我们非常高效！通过在问题出现时立即共同解决问题，我们比单独工作更快地将 arroy 融入了 Meilisearch。

Arroy 是不同的，因为它不返回迭代器来返回搜索结果。现在，我们的搜索引擎更智能，可以计算出需要返回的确切结果数量，即使在需要考虑过滤器的情况下也是如此。这种团队合作改进了我们的搜索工具，并向我们展示了在面对大型技术挑战时，合作是关键。

在 Arroy 中搜索时进行过滤

您可以在 本系列的第 1 部分中找到对 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 对结果进行排序，以便能够去重，避免多次返回同一文档，然后再次按距离排序，最后只返回前 20 个文档。这看起来可能很复杂，但我们讨论的是每个文档的向量数乘以 20 个文档。通常，用户只有一个向量。

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 社区或订阅 新闻通讯。您可以通过查看 路线图 并参与 产品讨论 来了解更多关于该产品的信息。