Meilisearch 太慢了

本文最初发布在 kero 的个人博客上。

本文将讨论Meilisearch文档索引器的缺点和解决方案。我们将从当前情况开始，探索各种技术，最后草拟一个强大的新文档索引器。

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

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

什么是文档索引引擎？

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

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

Arvid Kahl购买了一台96核的机器，希望Meilisearch能高效地使用它们，但它没有。

在内部，我们注意到一种趋势：客户希望索引数亿个文档并频繁更新它们。一个客户拥有超过3.11亿个文档，每周增长约1000万个。该搜索引擎在大型数据集上如此之快且可靠，以至于用户在需要从头开始重新索引所有内容之前，不会注意到索引问题。这通常发生在加载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¹ Sorters 设计了我们的 token 提取器。当内存缓冲区满时，Sorter 会将键值对保存在内存缓冲区中。当它满时，它会

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

此过程包括

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

所有这些都需要大量的资源，特别是对于高频条目，例如食谱数据集中的*巧克力*或电影数据集中的*科幻*标签。

大多数时候，提取器依赖于其他提取器，而这些提取器又依赖于原始文档块。这种依赖链可能导致临时 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 会将热页保存在 malloced 区域中以减少磁盘写入。因此，我们经常注意到在检查缓慢的索引操作时，只有一个工作线程处于活动状态。

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

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

一个更好的索引引擎

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

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

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

当一个软件组件从头开始构建时，考虑到每个所需功能，它将变得设计、类型、可理解和面向未来方面显著更优。这与最初只打算适应某些计划功能，因此难以整合必要更改的组件形成对比。

可用的技巧和技术

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

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

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

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

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

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

我们计划通过如上所述，首先准备好最终的倒排索引位图，从而执行一次写入以设置条目状态。一旦这些操作并行合并，结果将被发送到写入线程。构建一个基于磁盘的 B-Tree 可能会导致大量的内存分配，但 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-lines 文件中的文档。tarball 中文件的顺序很重要，因为您只能按顺序访问它们。为了高效地准备索引，我们需要对文件进行重新排序，以便设置文件位于大型文档文件之前。

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

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

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

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

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

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

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

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

未来的改进

我们的目标是使 Meilisearch 的更新无缝衔接。我们的愿景包括避免非主要更新的转储，并仅将它们保留用于重要的版本更改。我们将实现一个系统来版本化内部数据库和结构。通过这种方式，Meilisearch 可以即时读取旧数据库版本并将其转换为最新格式。这种转变将使整个引擎变得*基于资源*，并且 @dureuill 正在推动这项倡议。

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

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

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

总结

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

希望您发现这种对技术和改进的探索和我们一样令人兴奋！我们渴望在索引器重写中实施这些策略，并在各种机器和数据集上对其进行彻底的基准测试。我们的目标是确保最小的回归并实现显著的加速，特别是在具有大量数据集的大型机器上。

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