将数百万文档压缩到 128 TB 虚拟内存中

程序可以向操作系统请求多少虚拟内存？当然，不会超过机器中安装的 RAM 容量吧？也许还可以加上配置的交换空间或页面文件的容量？等等——这是否也取决于其他进程使用了多少内存？

我们 Meilisearch 团队通过艰难的实践才找到了这些问题的确切答案。在本文中，我们将分享我们关于虚拟内存的经验教训，以及它如何以令人惊讶的微妙方式与应用程序交互。

Meilisearch 是一款开源搜索引擎，旨在以极小的集成工作量提供闪电般快速、高度相关的搜索。它允许将文档存储在磁盘上，以索引为组进行存储，并搜索这些索引以获取与每个查询相关的文档。

自从 Meilisearch v1.1（我们现在已到 v1.6！）以来，我们解除了索引数量和最大大小的限制。在本文中，我们将分享动态虚拟内存管理如何成为实现这些改进的关键。

上图是汽车销售员梗，但汽车是 Linux 进程的虚拟地址空间

虚拟内存及其对 Meilisearch 施加的限制

什么是虚拟内存？

虚拟内存是操作系统（OS）为管理物理内存而创建的一种抽象。这种抽象允许操作系统为运行中的进程提供一个虚拟地址空间。每个进程的虚拟地址空间都与其他进程隔离。通过这种方式，可以防止进程意外（或恶意）访问属于其他进程的内存。这与所有进程直接访问物理内存的情况形成对比，后者是旧操作系统中的历史情况，在某些嵌入式系统中仍然如此。

操作系统通过将应用程序操纵的虚拟内存页面转换为物理内存中的对应页面来实现虚拟内存。

虚拟内存还使操作系统能够实现一种称为交换（swap）（也称为页面文件（pagefile））的机制。通过将虚拟内存页面映射到较慢的磁盘存储内存，并在下次访问该页面时将其重新加载到物理内存中，虚拟内存还提供了一种寻址比实际可用内存更多内存的方法。

下图显示了两个进程的虚拟内存示例，其中每个进程只能访问操作系统分配给它的物理内存部分。进程 A 的一个页面在磁盘上“换出”，并将在下次访问时从磁盘加载到物理内存中。

虚拟地址转换的简化表示

Meilisearch 中的虚拟内存

在 Unix 环境中，您可以使用命令行界面工具（如 htop）来查看进程使用了多少虚拟内存。以下是 Meilisearch 实例的命令输出

如您所见，Meilisearch 正在使用高达 8593GB 的虚拟内存——远超本机可用的物理内存（16GB）和磁盘（1000GB）。虚拟内存可以为进程提供几乎无限的内存。请注意，物理内存使用量——即实际 RAM——要低得多，仅使用了 38464KB。

Meilisearch 虚拟内存使用量的主要原因在于内存映射，即操作系统将文件的内容映射到虚拟内存。Meilisearch 使用 LMDB 键值存储来将磁盘上存储的索引内容映射到虚拟内存。通过这种方式，对索引文件的任何读写操作都通过虚拟内存缓冲区进行。操作系统在物理内存和磁盘之间透明高效地交换内存页面。

问题在于，这种内存映射文件会占用虚拟地址空间的相当大一部分。当映射一个 10GB 的文件时，您实际上需要一个相应的 10GB 连续虚拟内存缓冲区。

此外，通过内存映射写入文件的最大大小必须在创建映射时指定，以便操作系统可以确定用于映射的连续虚拟内存缓冲区的大小。

回到 Meilisearch 使用的 8593GB 虚拟内存，我们现在明白其中大部分实际上用于创建文档索引的内存映射。Meilisearch 分配如此大的内存，以确保这些内存映射足够大，以适应磁盘上索引的增长。

但极限在哪里？一个进程的虚拟内存能增长到多大？因此，可以同时存在多少个索引，以及它们的最大大小是多少？

128TB 也只能容纳这么多索引！

理论上，在 64 位计算机上，虚拟地址空间为 2^64 字节。这相当于 18.45 艾字节，超过 1600 万太字节！然而，实际上，操作系统为进程分配的虚拟地址空间要小得多：Linux 上是 128TB，Windows 上是 8TB。

128TB 听起来可能很多。但 Meilisearch 实例可以使用的索引数量 (N) 和索引的最大大小 (M) 之间存在一个权衡。基本上，我们需要 N * M 保持在 128TB 限制之下。而文档索引有时会增长到数百 GB 以上，这可能是一个挑战。

在 v1.0 之前的 Meilisearch 版本中，这种权衡通过 --max-index-size CLI 参数暴露出来。这允许开发者定义每个索引的映射大小，默认值为 100GB。在这些旧版本中，如果您想让索引大于 100GB，您需要将 --max-index-size 的值更改为索引所需的估计最大大小。

因此，尽管这并不容易察觉，但更改 --max-index-size 参数的值会限制 Meilisearch 实例可以使用的索引数量：在 Linux 上，默认值 100GB 大约可以支持 1000 个索引，在 Windows 上则大约 80 个。增加该参数以适应更大的索引会减少最大索引数量。例如，1TB 的最大索引大小会将您限制在 100 个索引以内。

那么，如何决定 --max-index-size 的值呢？没有直接的答案。因为 Meilisearch 构建的数据结构称为倒排索引，其大小以非显而易见的方式取决于被索引文本的特征。因此，索引的大小很难预先估计。

将这个具有微妙影响的决策留给用户，感觉与我们旨在拥有一个简单、可用且默认设置良好的引擎的目标相悖。随着 v1.0 即将发布，我们不希望稳定 --max-index-size 参数。因此，我们决定在 v1.0 中移除此选项。我们暂时将索引的内存映射大小硬编码为 500GB，并计划在 v1.1 版本中提供一个更直观的解决方案。

引入动态虚拟地址空间管理。

借助动态虚拟地址空间管理，实现无限可能

与动态数组的类比

让我们将当前的问题与固定大小的数组进行比较。在编译型语言中，固定大小的数组要求开发者在编译时定义其大小，因为它不能在运行时更改。使用已弃用的 --max-index-size 参数时，Meilisearch 用户面临着类似的限制。他们必须确定最佳索引大小，在大小和索引总数之间进行权衡。

真正让这个问题无法解决的是索引的两个相互竞争的使用场景

• 在索引中存储大量大文档，从而使索引达到数百 GB 的大小；
• 存储许多索引，可能多达数千个（尽管这通常旨在解决多租户问题，应通过租户令牌实现）。

用户基本上陷入了一个困境：拥有大索引大小但限制索引数量，或者限制索引大小以允许更多索引。我们必须想出更好的办法。

在编译型语言中，当数组的大小无法提前知道时，开发者会使用动态数组。动态数组是一种由三部分信息组成的数据结构

• 指向动态分配的连续数组的指针；
• 分配给该数组的大小，表示为容量；以及
• 数组中当前存储的元素数量。

向动态数组添加元素需要检查数组的剩余容量。如果新元素对于现有数组来说太大，则会以更大的容量重新分配数组以避免溢出。大多数系统语言在其标准库中都提供了动态数组的实现（Rust、C++）。

步骤 1：从小处着手，按需调整大小

遵循我们的数组类比，缓解索引数量和大小之间权衡的第一步是：当索引的内存映射已满时，动态调整索引大小，从而增加内存映射的容量。

在 Meilisearch 中，当索引映射已满时，我们可以通过调整索引大小来实现类似的行为。

我们将此逻辑添加到了负责管理 Meilisearch 实例索引的索引调度器中。它处理对索引的更改，例如新文档导入、设置更新等。特别是，我们更新了负责运行任务的 tick 函数，以处理 MaxDatabaseSizeReached 错误。顾名思义，当由于与索引关联的内存映射太小而无法容纳在该批次中执行的写入操作的结果时，就会返回此错误。

看看我们是如何在 Rust 中实现这一点的

// When you get the MaxDatabaseSizeReached error:
// 1. identify the  full index
// 2. close the associated environment
// 3. resize it
// 4. re-schedule tasks
Err(Error::Milli(milli::Error::UserError(
    milli::UserError::MaxDatabaseSizeReached,
))) if index_uid.is_some() => {
    // Find the index UID associated with the current batch of tasks.
    let index_uid = index_uid.unwrap();
    // Perform the resize operation for that index.
    self.index_mapper.resize_index(&wtxn, &index_uid)?;
    // Do not commit any change we could have made to the status of the task batch, since the batch failed.
    wtxn.abort().map_err(Error::HeedTransaction)?;


    // Ask the scheduler to keep processing, 
    // which will cause a new attempt at processing the same task,
    // this time on the resized index.
    return Ok(TickOutcome::TickAgain(0));
}

该错误通过调整索引大小来处理。它在 IndexMapper::resize_index 函数中实现，下面给出了其简化实现

/// Resizes the maximum size of the specified index to the double of its current maximum size.
///
/// This operation involves closing the underlying environment which can take a long time to complete.
/// Other tasks will be prevented from accessing the index while it is being resized.
pub fn resize_index(&self, rtxn: &RoTxn, uuid: Uuid) -> Result<()> {
    // Signal that will be sent when the resize operation completes.
    // Threads that request the index will wait on this signal before reading from it.
    let resize_operation = Arc::new(SignalEvent::manual(false));

    // Make the index unavailable so that other parts of code don't accidentally attempt to open it while it is being resized.
    let index = match self.index_map.write().insert(uuid, BeingResized(resize_operation)) {
        Some(Available(index)) => index,
        _ => panic!("The index is already being deleted/resized or does not exist"),
    };

    // Compute the new size of the index from its current size.
    let current_size = index.map_size()?;
    let new_size = current_size * 2;

    // Request to close the index. This operation is asynchronous, as other threads could be reading from this index.
    let closing_event = index.prepare_for_closing();

    // Wait for other threads to relinquish the index.
    closing_event.wait();

    // Reopen the index with its new size.
    let index = self.create_or_open_index(uuid, new_size)?;

    // Insert the resized index
    self.index_map.write().unwrap().insert(uuid, Available(index));

    // Signal that the resize operation is complete to threads waiting to read from the index.
    resize_operation.signal();

    Ok(())
}

如您所见，由于索引可以随时被其他具有读访问权限的线程请求，因此实现变得更加复杂。然而，其核心实现类似于动态数组的容量增加。

在这种新方案下，索引将以较小的尺寸（例如几 GB）开始，并在需要更多空间时动态调整大小，从而使我们能够解决上述两个相互竞争的使用场景中的任何一个。

我们本可以就此收工回家（嗯，严格来说不能，因为我们远程办公，但这无关紧要），但这个解决方案仍然存在两个问题

1. 如果我们想同时解决两种使用场景，即拥有大量索引和大尺寸索引，该怎么办？
2. 由于我们依赖 MaxDatabaseSizeReached 错误来判断索引是否需要调整大小，因此我们在此之前丢弃了批次的所有进度。这意味着在调整大小的索引上重新开始，这基本上会使索引操作的持续时间成倍增加。

我们想知道如何解决这些问题。在下一节中，我们将看到我们如何处理这些问题，以及进一步迭代引入的新边缘情况。

步骤 2：限制并发打开的索引数量

解决上述问题的第一步是找到一种方法来限制所有索引使用的总虚拟内存。我们的假设是，我们不应该同时将所有索引映射到内存中。通过将同时打开的索引数量限制在一个较小的数字，我们可以为每个索引分配大部分虚拟内存。

这是通过一个简化的最近最少使用 (LRU) 缓存实现的，具有以下特点

• 插入和检索操作是在线性时间内完成的，而不是通常的常数时间。考虑到我们存储的元素数量非常少，并且它们的键具有高性能的相等比较函数（UUID），这并不重要。
• 它可以被多个读者无阻塞地访问。在 Rust 术语中，这意味着数据结构是 Send 和 Sync，并且其检索元素的函数接受共享引用 (&self)。我们通过将缓存放在 RwLock 后面来利用这一特性。
• 缓存使用一个代数来跟踪对项目的访问。查找项目只需将其代数提升到缓存已知的最新代数。当缓存已满时，通过线性搜索缓存中最小代数（即访问时间最久的项目）来淘汰项目。这种简单的实现可以在不依赖 unsafe 的情况下实现，从而保护实现免受内存安全错误的风险。

借助此缓存，我们将同时打开的索引数量限制为（例如）20 个。Linux 机器上的索引在用尽虚拟空间之前可以增长到 2TB。而空间耗尽意味着这 20 个索引的总大小在磁盘上会以某种方式超过 128TB，这在当今标准下是相当大的，考虑到 2020 年一个 100TB SSD 的价格为 40,000 美元。如果您确实遇到由于累积打开索引大小高于 128TB 引起的问题，请随时与我们联系 😎

如果我们从大索引大小开始呢？

既然 LRU 允许我们支持 2TB 的内存映射而不会限制索引的总数，那么解决我们的调整大小性能问题的简单方法是让所有索引都以 2TB 的映射大小开始。请注意，创建 2TB 的映射大小并不会在磁盘上创建 2TB 的文件，因为只有文档数量和索引数据才会导致磁盘文件增长。如果某个索引确实增长到超过 2TB，调整大小机制将使其正常工作。但这仍然不太可能发生。有了缓存确保我们不能同时映射超过 20 个索引，我们就可以拥有任意数量的任意大小的索引，而无需付出任何调整大小的代价。

该方案中唯一剩下的障碍是，对于某些操作系统而言，可用的虚拟地址空间远小于 128TB。一个用户在 v1.0 中甚至没有 500GB 的虚拟内存可分配给单个索引的问题就说明了这一点。为了解决这些边缘情况，以及 Windows 仅为进程提供 8TB 虚拟内存的问题，我们决定在运行时测量我们可以进行内存映射的虚拟内存量。

我们未能找到一种既快速又可移植的方法来实现这一点。我们决定利用 LMDB（我们用于存储索引的开源键值存储）提供的现有可移植性，以及我们栈中依赖内存映射的部分。最终，我们对索引可以打开的最大映射大小实施了二分查找。

通过执行这种二分查找，我们测量出 Linux 上的实际分配预算接近 93TB，而 Windows 上的实际分配预算在 9 到 13TB 之间（这令人惊讶，因为它比宣传的要多！）。我们测量的 Linux 差异可以用虚拟地址空间在进程的所有分配（而不仅仅是环境映射）之间共享来解释。由于分配需要是连续的，因此单个小分配可能导致碎片化并减少连续可用的虚拟内存。

二分查找的实现可以在 IndexScheduler::index_budget 函数中找到。它计算可以同时打开多少个 2TB 的索引，或者，如果可用空间小于 2TB，则计算单个索引可以有多大。出于性能原因，如果至少可以映射 80TB（Windows 为 6TB），则会跳过此二分预算计算，因为在这种情况下我们认为有足够的空间。

结论

索引数量与其最大大小之间不幸的权衡，促使我们从静态选择的最大索引大小转向动态虚拟地址空间管理方案。Meilisearch 现在首先计算可以同时打开多少个 2TB 的索引而不会导致虚拟内存溢出。然后，它使用一个 LRU 缓存来管理这些以 2TB 映射大小打开的索引。因此，如果一个索引超出 2TB 限制，它将得到适当的调整。

我们不得不分两步执行此更改。首先，通过删除 --max-index-size CLI 选项，因为我们不希望将其与 v1 一起稳定。然后，我们必须设计一种透明的方式供用户管理索引 v1.1。这是v1 规划的一个例子。这项工作也受益于我们发布原型的新流程，这使得像 newdev8 这样的热心用户能够帮助我们检查这些更改是否在他们的配置中起作用。我们感谢他们的贡献 🤗

下表总结了本文中讨论的各种虚拟地址空间管理方案

以下是 Meilisearch 中一些现有的限制，我们可以着手改进以进一步完善该方案

• 无论索引大小如何，它在 LRU 中始终占用一个槽位。对于大于 2 TB 的索引，这可能导致分配错误。
• 当请求一个索引时，如果缓存已满，它会在逐出任何索引之前被打开。这迫使我们为新打开的索引保留一个槽位，并且如果同时请求许多新索引，则可能导致瞬时分配错误。
• 此实现要求读取索引的代码尽快释放它们，并且在同一任务中不要两次打开给定索引；未能遵守此要求可能会导致死锁。
• 遍历所有索引的任务变得更慢，尤其是在某些平台（macOS）上，这导致我们为其中一些添加了缓存（例如，请参阅此 PR）。

结束！在 /r/programming 上加入讨论。

欲了解更多 Meilisearch 相关内容，请加入我们的 Discord 服务器，或订阅我们的新闻通讯。您还可以查看我们的路线图并参与我们的产品讨论，以了解更多信息。