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 亿个文档，并且每周增长约一千万个。搜索引擎在处理大型数据集时速度非常快且可靠，以至于用户在需要从头开始重新索引所有内容之前不会注意到索引问题。这种情况通常发生在从 SQL 数据库加载 Meilisearch 转储或批量更新时，尤其是在初始设置期间。

一点历史回顾

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

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

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

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 会将热页面保存在 malloc 区域中以减少磁盘写入。因此，我们经常注意到，在检查缓慢的索引时，只有一个工作线程处于活动状态。

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

总而言之，虽然我们已成功解决了内存溢出问题，但我们现在面临着更高的磁盘使用率和增加的文件系统压力。磁盘操作比 RAM 访问慢，并且可用 RAM 通常仅部分利用。此外，系统经常以单线程方式运行，这会影响索引性能。

更好的索引引擎

在我们的行业中，重写通常被认为是禁忌。主要原因是重写功能会延迟新功能，并使项目经历不确定的延迟和新错误，而没有提供立即可见的价值。但是，在 Meilisearch，我们拥抱这一原则，因为我们在过去的重写中取得了巨大的成功，并且知道如何有效地管理它们。

首先想到的是索引调度器重写。我们采用了一种非常明智的方法，我们在其中列出了我们希望为发布版本提供的功能、未来版本的功能以及过去一年的主要错误。通过在两到四个小时的结对编程会话中混合这些元素，我们创建了一个出色的产品，没有重大错误，具有理想的共享知识，从而改进了支持、高效的错误修复和顺利的功能添加。

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

当一个软件组件从头开始构建，并考虑到每个所需的功能时，它在设计、类型、可理解性和面向未来方面都会变得明显更好。这与最初旨在仅容纳某些计划的功能，因此难以集成必要更改的组件形成对比。

可用的技巧和技术

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

LMDB 一次只允许一个写入事务，这是其可序列化的关键，而 RocksDB 支持多个并行写入器。这种根本的区别之前限制了我对如何优化 Meilisearch 的想法。但是，我们已经意识到，使用 LMDB 在写入时并行读取是可能的。这是增强 Meilisearch 索引器最有效的方法！我们可以在每个索引线程中使用读取事务来访问数据库内容，同时使用写入事务 — 请注意 在写入时拥有更多读取器显然会影响写入吞吐量。但是，与 RocksDB 相比，LMDB 具有单个写入器，但仍然具有令人印象深刻的性能，特别是对于我们倾向于拥有的大值，即大型位图。此外，LSM 树具有更高的写入放大，尤其是在并行写入时，而我们的目标是最大限度地减少写入放大。

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

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

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

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

我们计划通过首先准备如上所述的最终倒排索引位图来执行单次写入以设置条目的状态。一旦这些操作并行合并，结果将发送到写入线程。构建基于磁盘的 BTree 可能会占用大量分配，但 LMDB 提供了 MDB_APPEND 参数，如果条目仍然按字典顺序排列，则允许将条目附加到数据库的末尾。这减少了插入过程的开销，减少了碎片，并减少了写入放大。

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

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

早期版本的 grenad² 包含一个功能，该功能允许文件流式传输，同时解除分配读取部分，从而为数据库或其他 grenad 文件释放空间。使用 fallocate(2) 系统调用，此功能可以帮助减少写入放大，目前仅在 Linux 上可用。当 grenad Sorter 需要合并临时文件时，此功能非常方便。

要支持的功能集

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

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

另一个常见任务是升级到最新的 Meilisearch 版本。这涉及创建和加载转储以及新引擎。转储是一个 tarball (.tar.gz)，其中包含索引设置和 JSON 行文件中的文档。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 库的炫酷加载条。想象一下它们在 Web 仪表板上的外观有多棒！

总结

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

我希望您像我们一样对这种技术和改进的探索感到兴奋！我们渴望在我们的索引器重写中实施这些策略，并在各种机器和数据集上对其进行全面基准测试。我们的目标是确保最小的回归，并实现显着的加速，尤其是在具有大型数据集的较大型机器上。

如果您有任何问题或建议，请随时直接在此帖子下评论，HackerNews, Lobsters, Rust 子版块, 或 X (原 Twitter)。请继续关注更多更新，祝您搜索愉快！