在128 TB的虚拟内存中压缩数百万份文档

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

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

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

自Meilisearch v1.1起，我们现在是v1.6！我们取消了索引数量和最大大小的限制。在本文中，我们将分享动态虚拟内存管理是如何实现这些改进的关键。

汽车销售员梗，但这里的车是 Linux 进程的虚拟地址空间。

虚拟内存及其对 Meilisearch 的限制

什么是虚拟内存？

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

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

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

下图显示了两个进程的虚拟内存示例，其中每个进程只能访问由操作系统分配给它的物理内存部分。进程 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 EB。超过 1600 万 TB！然而，实际上，操作系统为进程分配的虚拟地址空间要小得多：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 命令行选项，因为我们不想在 v1 版本中将其稳定下来。然后，我们必须为用户设计一种透明的方式来管理 v1.1 索引。这是v1 规划的一个例子，这项工作也受益于我们发布原型的新流程，这使得像newdev8这样的热心用户能够帮助我们检查更改是否在他们的配置中生效。我们感谢他们的贡献 🤗

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

以下是 Meilisearch 中我们可能会改进该方案的一些现有限制：

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

就这样！加入 /r/programming 上的讨论。

有关 Meilisearch 的更多信息，请加入我们的 Discord 或订阅我们的新闻通讯。您可以通过查看我们的路线图并参与我们的产品讨论来了解更多关于我们产品的信息。