Meilisearch 借助 Arroy 的过滤磁盘近似最近邻（Filtered Disk 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 对结果进行排序，以便进行去重并避免多次返回相同文档，然后再次按距离排序，最后只返回前二十个文档。这可能看起来很复杂，但我们谈论的是每个文档的向量数量乘以二十个文档。通常，用户会有一个单一的向量。

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