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

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

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

Meilisearch 支持对文档的可筛选属性使用以下运算符： <、 <=、 =、 != >= 和 >。在内部，我们广泛 使用 RoaringBitmaps，这是一种经过良好优化的整数集合，支持快速的二元运算，如并集和交集。当引擎收到带有过滤器的用户请求时，它首先计算来自过滤器的文档子集，该子集将输入到搜索算法中，该算法按质量对文档进行排名。此子集由 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 组成的树叶，如果您遵循特定的普通节点路径，您会找到这些项目 ID。

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

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

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

您可能已经注意到我想去哪里了，但这就是奇迹发生的地方。我们修改了 arroy 以将后代列表存储在 RoaringBitmaps 中，而不是原始的整数列表。这是与原始 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 上的社区或订阅新闻通讯。您可以通过查看路线图并参与产品讨论来了解更多关于该产品的信息。