Meilisearch 太慢了

这篇文章最初发布在 kero 的个人博客上。

本文探讨了Meilisearch 文档索引器的缺点和解决方案。我们将从现状开始，探索各种技术，最终设计一个功能强大的新文档索引器。

我目前正在度假，但作为 Meilisearch 的 CTO 和联合创始人，我情不自禁地思考如何改进我们的产品，尤其是文档索引器。写作有助于理清我的思路，所以我很高兴能在登山间隙分享我的思考过程。

Meilisearch 是 GitHub 上星标第二多的搜索引擎。它具有简单的 HTTP API，采用 Rust 构建，并集成了结合关键词和语义搜索的混合搜索系统，以提供高度相关的结果。我们需要优化索引器，以更好地处理大型数据集，包括数亿个文档。

什么是文档索引引擎？

每个搜索引擎都建立在倒排索引之上。倒排索引是因子化的键值存储，其中键对应于集合中出现的一个项，而集合是与之关联的位图；例如，一个 词 -> 文档 ID 倒排索引将词与包含这些词的文档 ID 位图匹配，例如 'chocolate' 出现在文档 1、2、20 和 42 中。Meilisearch 使用 大约二十一种不同的倒排索引来提供高度相关的搜索结果。此外，它还采用各种有趣的数据结构，例如 arroy 树，以增强其功能。

当前的索引引擎效率很高，在一台高性能 CPU 机器上，大约二十小时内可以索引 2.5 亿个文档。然而，仍有很大的改进空间。本文将探讨构建更优索引器的方法。

Arvid Kahl 购买了一台 96 核机器，希望 Meilisearch 能高效利用它们，但事实并非如此。

在内部，我们注意到一个趋势：客户希望索引数亿个文档并频繁更新它们。一位客户拥有超过 3.11 亿个文档，每周增长约一千万。该搜索引擎在处理大型数据集时速度快且可靠，以至于用户通常不会注意到索引问题，直到他们需要从头开始重新索引所有内容。这通常发生在加载 Meilisearch 转储或从 SQL 数据库进行批量更新时，尤其是在初始设置期间。

历史简介

我们在不到一年前引入了差异索引。在 1.6 版本之前，我们的引擎在更新和删除方面表现不佳。它过去常常软删除文档，并将新版本作为全新文档进行索引，导致磁盘使用量增加、复杂性提高和错误增多。这种方法需要重新索引所有内容，并像垃圾收集器一样，仅在达到特定阈值时才删除软删除的文档，这影响了随机更新。

自 1.6 版本以来，索引管道的效率大大提高。它处理文档的当前版本和新版本，以仅确定倒排索引中必要的更改。这种方法通过减少 LMDB 中的操作数量，极大地加快了文档更新速度。差异索引器使用提取器创建块，本质上是对 LMDB 中位图进行删除和插入的倒排索引。

蓝色尖峰代表 99% 的自动批处理和 1% 的软删除文档垃圾回收，这些在 v1.6 中不再可见。

LMDB，即 Lightning Memory-Mapped Database（闪电内存映射数据库），是 Meilisearch 索引的核心组件。它是一个出色的键值存储，因为它

• 读取操作随 CPU 数量扩展，
• 支持零分配读取，
• 支持原子和完全序列化的事务，
• 需要最少的配置，
• API 表面小，
• 写入放大率低，
• 可靠，已在 Firefox 中使用了多年。

但它也有一些缺点

• 可见的碎片化，
• 每次只能进行一个写入事务，
• 非对齐的值字节，限制了零拷贝反序列化。

本文将深入探讨 Howard Chu 这一出色键值存储的细节。

2022 年，我们发布了 Cloud 的第一个版本 ✨，但遇到了大量内存不足崩溃的问题。

基于磁盘的索引器以对抗 OOM

我们改造了索引系统，使其基于分块，这大幅减少了内存使用。现在，Meilisearch 将文档更新拆分为 4MiB 的临时 grenad 文件，由各种提取器并行处理。每个提取器处理一个块，并生成一个或多个额外的块，通常是倒排索引。

我们将令牌提取器围绕 grenad¹ Sorter 进行设计。 Sorter 将键值对保存在内存缓冲区中，直到缓冲区满。当缓冲区满时，它会

• 按键对条目进行排序，
• 通过反序列化 Roaring Bitmaps 合并它们，
• 执行位图合并，
• 序列化合并结果，
• 使用 Writer 将合并后的条目写入临时文件，
• 一旦达到临时文件数量限制，文件将被合并。

此过程包括

• O(n * log(n)) 的条目排序，
• 多次 memcpy 操作，
• 大量的小分配和 I/O 操作，
• 插入期间的位图序列化，
• 将键多次保存在内存中。

所有这些都需要大量资源，特别是对于像食谱数据集中的 'chocolate' 或电影数据集中的 'science fiction' 标签这样的高频条目。

大多数情况下，提取器依赖于其他提取器，而这些提取器又依赖于原始文档块。这种依赖链可能导致临时 grenad 文件长时间存在，造成打开文件堆积，并在索引期间导致“打开文件过多”的错误。打开文件过多还会给文件系统缓存带来额外压力，这会进一步降低性能。

当提取器完成生成块后，我们将其直接发送到 LMDB 写入器。写入线程的任务包括

• 遍历 grenad 文件条目并解码删除和插入的位图，
• 检索并解码 LMDB 中每个相应键的位图，
• 在 LMDB 位图上进行删除和插入操作，
• 编码并将更新后的位图保存回 LMDB。

// For each inverted index chunk received
for chunk_reader in chunks_channel {
    // Iterate throught the grenad file entries
    let mut iter = chunk_reader.into_cursor();
    while let Some((key, deladd_bitmaps)) = iter.next()? {
        // Deserialiaze both operations
        let deletions = deladd_bitmaps.get(Deletion).unwrap_or_default();
        let additions = deladd_bitmaps.get(Addition).unwrap_or_default();
        // Get the bitmaps from LMDB and do the operations
        let mut bitmap = database.get(wtxn, key)?.unwrap_or_default();
        bitmap -= deletions;
        bitmap |= additions;
        // Serialize and write back into LMDB
        database.put(wtxn, key, &bitmap)?;
    }
}

Meilisearch 无法并行执行合并，因为这些操作依赖于已在当前写入事务中合并的块。简而言之，我们已在当前事务中进行了更改，这些更改对于读取事务尚不可见。这意味着我们无法打开多个读取事务以并行工作。

LMDB 的“即写即读”功能允许我们在写入事务中看到刚刚写入的内容。然而，频繁写入相同条目可能导致数据库碎片化和内存使用增加，因为 LMDB 将热页保存在分配的内存区域中以减少磁盘写入。因此，在检查慢速索引时，我们经常发现只有一个工作线程处于活动状态。

Meilisearch 任务调度器自动批量处理任务，以提高大型数据集的延迟和索引速度。然而，由于任务大小不同，它并未针对实时索引进行优化。最初引入自动批处理是为了处理用户逐个发送文档导致索引速度变慢的问题。有时，Meilisearch 会处理过多任务并崩溃（因 OOM 被终止）。这可以通过围绕总批次大小而非任务数量来设计自动批处理系统来解决。

总之，尽管我们成功解决了内存不足问题，但现在面临更高的磁盘使用率和文件系统压力。磁盘操作比 RAM 访问慢，并且可用 RAM 通常只被部分利用。此外，系统经常单线程运行，这影响了索引性能。

更优的索引引擎

在我们的行业中，重写通常被认为是禁忌。主要原因是重写功能会延迟新特性，并导致项目面临不确定的延迟和新错误，而无法立即提供可见价值。然而，在 Meilisearch，我们信奉这一原则，因为我们过去在重写方面取得了巨大成功，并且知道如何有效地管理它们。

第一个想到的例子是索引调度器的重写。我们采用了一种非常健全的方法论，列出了我们希望在发布中实现的功能、未来的功能以及过去一年的主要错误。通过在两到四小时的结对编程会话中混合这些元素，我们创造了一个出色的产品，没有重大错误，并理想地分享了知识，从而改进了支持、高效的错误修复和流畅的功能添加。

另一个例子是最近的 Spotify/Annoy 移植，从 C++ 到基于 LMDB 的 Rust。一系列博客文章详细介绍了这个故事，最终形成了一个完美集成的库，具有共享知识、更好的性能和更少的错误。

当一个软件组件在设计之初就考虑了所有必需的功能时，它的设计会显著优化，类型更清晰，更容易理解，也更具未来适应性。这与那些最初只为适应部分计划功能而设计的组件形成对比，后者因此难以集成必要的更改。

可用技巧与技术

让我重点介绍一些我们从 LMDB 中学到的技巧和技术，它们对于我们计划实现的新文档索引器至关重要。当前的索引器无法高效利用这些技术；尝试这样做会增加复杂性并导致更多错误。

LMDB 一次只允许一个写入事务，这是其可序列化的关键，而 RocksDB 支持多个并行写入器。这种根本性差异此前限制了我对 Meilisearch 如何优化的思考。然而，我们已经意识到，LMDB 可以**在写入的同时并行读取**。这是增强 Meilisearch 索引器最具影响力的发现！我们可以在每个索引线程中使用读取事务来访问数据库内容，同时使用写入事务——请注意，在写入时拥有更多读取器会明显影响写入吞吐量。然而，与 RocksDB 相比，拥有大值（即大型位图）的 LMDB 即使只有单个写入器，其性能仍然令人印象深刻。此外，LSM 树具有更高的写入放大，尤其是在并行写入时，而我们旨在将其最小化。

LSM 在处理小型、写入密集型任务方面表现出色，而 LMDB 在处理较大值方面性能更好。上图显示了插入和读取 4k 值的性能。

Meilisearch 索引器确定要在数据库上执行的操作。这些操作通过指定要从 LMDB 中给定位图中移除和插入的文档 ID 来表示。在写入数据库的同时并行读取数据库的能力，为**并行执行这些合并操作**并向主写入线程发送最终序列化的位图提供了可能性，进一步平衡了计算负载。

然而，这种优化仅在我们**停止将设置更新与文档更新重新排序**并在单个写入事务中处理它们时才有效。当前的引擎试图通过首先处理设置来变得更智能，这可以减少新文档的工作量。但是，在一个事务中处理所有内容可能会触发 MDB_TXN_FULL 错误，因为事务变得太大。这些设置更改很少发生，并且以这种方式优化使得由于中间设置更改而无法读取倒排索引。

在实现 arroy 的多线程支持时，我们找到了一种从 LMDB **并行读取未提交更改**的方法。有关详细见解和代码示例，请查阅我的向量存储实现文章。这项技术利用了 LMDB 的“即写即读”能力和零拷贝内存映射原理：LMDB 中的条目是指向内存映射区域的指针，在环境被释放或发生任何进一步写入之前有效。收集所需条目的指针，然后并行共享它们，同时确保写入事务保持不变。

我们计划通过首先准备如上所述的最终倒排索引位图，执行**单次写入来设置条目状态**。一旦这些操作并行合并，结果将被发送到写入线程。构建基于磁盘的 B 树可能需要大量的内存分配，但 LMDB 提供了 MDB_APPEND 参数，它**允许条目在仍保持词典顺序的情况下附加到数据库末尾**。这减少了插入过程的开销，减少了碎片，并降低了写入放大。

我们可以通过**减少线程间的通信开销和数据传输**来进一步提升性能。最有效的策略是将位图序列化到内存缓冲区中，最好是并行进行。这能最大程度地减少分配并使用无等待数据结构。当与写入线程端的活跃读取循环结合时，bbqueue crate 是一个很有前景的解决方案。

ferrous systems 的 bbqueue 博客文章插图，展示了循环缓冲区中的读取方法。

grenad² 的早期版本之一包含一项功能，可以在**读取部分释放内存的同时进行文件流式传输**，从而为数据库或其他 grenad 文件释放空间。此功能可以通过使用 fallocate(2) 系统调用（目前仅在 Linux 上可用）来帮助减少写入放大。当 grenad Sorter 需要合并临时文件时，此功能非常有用。

要支持的功能集

现在我们已经探索了所有这些令人兴奋的新工具和技术，让我们看看如何利用它们来使我们的文档索引器更快、更高效，同时还支持我们设想的那些酷炫新功能。

人们主要使用 Meilisearch 进行**文档插入**，无论是通过合并 (PATCH) 还是替换 (POST) 文档。用户通过 HTTP 路由发送文档，Meilisearch 异步接收它们，将其转换为 grenad JSON 文件并注册到索引调度器中。为了适应逐个发送文档的用户，调度器会自动批处理多个任务以在一个事务中处理。然后索引器会去重并将最终的文档版本写入另一个临时 grenad 文件。这种方法导致了数据重复和在慢速磁盘上的性能下降。我尝试了即时合并文档并使用新的多线程索引管道进行并行迭代，结果非常出色。

另一个常见的任务是升级到最新的 Meilisearch 版本。这包括使用新引擎创建和**加载转储**。转储是一个包含索引设置和 JSON-lines 文件中文档的 tarball (.tar.gz)。tarball 中文件的顺序很重要，因为你只能顺序访问它们。为了高效地准备索引，我们需要重新排序文件，使设置先于大型文档文件。

当加载包含数亿文档的转储时，我们经常遇到 MDB_TXN_FULL 错误，因为事务变得太大。这发生在处理和合并 grenad 块期间的大量写入和覆盖。为了解决这个问题，我们可以**将文档分解成更小的块进行处理**，并在不同的事务中进行。此外，由于加载转储时数据库为空，使用 MDB_APPEND 选项有助于**添加条目并减少脏页**。

在索引的生命周期中，设置经常发生变化。我们最近投入了大量精力进行差异索引，并计划保持这种方法。我们**只向提取器提供必要的文档字段**（例如，新声明的可搜索/可过滤字段）。由于*文档本身不发生变化*，我们可以跳过文档写入循环，从而避免一些磁盘操作。

我们最近推出了**“按函数编辑文档”功能**，它允许用户通过自定义函数修改任何属性来重塑文档。目前，此函数并行应用于所有文档，生成一个单独的 grenad JSON 文件，然后继续进行标准索引过程。这在编辑大量文档时可能导致空间问题。我们不应该将所有内容写入磁盘，而应该*流式传输新编辑的文档*。通过这样做，即使我们多次运行该函数，我们也可以生成不同的倒排索引并将其写入 LMDB。

分析我们最大的客户数据库后，我们发现文档数据库（我们存储原始 JSON 以实现最佳检索的地方）是最大的。我们开始使用 zstd 进行字典压缩，通过采样 1 万个文档来创建字典，这将大小减少了 2-3 倍。当前的索引器在索引后压缩文档，这会降低速度，因此我们没有合并该 PR。新的索引器将在内存中保留足够的文档以构建压缩字典，从而在索引期间实现**文档的压缩和并行流式传输**。

我们希望减少磁盘使用量，以**更好地利用 CPU 和内存**，避免缓慢的 I/O 等待。我们注意到 grenad Sorter 并未高效利用可用内存，过于依赖磁盘写入。为了解决这个问题，我们将为每个索引线程添加*一个缓存*，以便首先在内存中处理条目，仅在必要时才写入磁盘。我们还将确保这些缓存不会使用过多内存，以防止 OOM 问题。我们甚至可以调整 roaring 和 lru crate 以支持自定义分配器，就像 hashbrown 支持 bumpalo 一样，这得益于 Allocator trait。

当前的引擎使用 4MiB 的文档块，这些块随后由提取器处理，为写入线程或其他提取器生成新的块。这种方法可能效率低下，因为如果某个块处理起来更复杂，它可能会减慢整个管道。相反，我们可以使用 Rayon 和其工作窃取功能来单独处理文档。这样，如果某些文档处理起来更困难，**工作负载可以在线程之间更有效地平衡**。

Meilisearch 的关键工具之一是 charabia，它通过 Whatlang 处理语言检测，并实现高效的令牌提取和标准化。我们正在考虑从 Whatlang 库切换到 Whichlang，以实现**10 倍的速度提升**。我们还在 @ManyTheFish 的帮助下*努力使 charabia 更快*，以加速整个提取过程。

为了**支持不同类型的索引**——实时和大量插入——我们可以调整任务调度器，根据用户发送的文档有效负载大小来批处理任务。更大的批处理意味着更长的延迟但更快的整体索引速度。更小的批处理允许更快地看到文档但索引所有任务所需时间更长。通过配置自动批处理大小，用户可以选择他们偏好的行为。

未来改进

我们的目标是使 Meilisearch 更新无缝衔接。我们的愿景包括**避免非重大更新使用转储**，并将其仅保留给重要的版本更改。我们将实现一个系统来对内部数据库和结构进行版本控制。有了这个，Meilisearch 可以即时读取旧数据库版本并将其转换为最新格式。这一转变将使整个引擎*基于资源*，并且 @dureuill 正在推动这项工作。

为了确定处理倒排索引内容的最佳方式，我们应该**测量磁盘速度**。这将帮助我们决定是将内容写入磁盘供 LMDB 写入线程稍后处理，还是并行处理这些值并直接发送给写入线程而不使用磁盘。我们总是会通过多个读取事务并行计算倒排索引的合并版本。

等待可能很困难，尤其是在没有更新的情况下。通过**显示索引管道的进度**，使用多个加载条，我们可以让等待更容易忍受，让用户了解情况，甚至协助调试慢速管道以进行进一步改进。

来自 console-rs/indicatif 库的酷炫加载条。想象一下它们在网络仪表板上会多么棒！

总结

我们的目标是创建一个超高效的键值存储，类似于 LSM，并针对并行写入进行了优化，以便在更新 LMDB 倒排索引之前构建倒排索引。通过更智能地利用 RAM 来减少磁盘写入，并为 LMDB 聚合操作，我们可以显著减少写入这个主要为重度读取操作设计的 B+Tree 键值存储的次数。好消息是，我们可以在写入 LMDB 的同时计算这些倒排索引，从而大大提高效率。

我希望您像我们一样，对这些技术和改进的探索感到兴奋！我们渴望在索引器重写中实施这些策略，并在各种机器和数据集上对其进行彻底基准测试。我们的目标是确保最小程度的退化并实现显著的速度提升，尤其是在处理大型数据集的较大机器上。

如果您有任何问题或建议，请直接在此帖子、HackerNews、Lobsters、Rust sub-Reddit 或 X（前身为 Twitter）上评论。敬请关注更多更新，祝您搜索愉快！