在 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 艾字节。超过 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++）。

第一步：从小处开始并根据需要调整大小

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

在 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错误来了解索引是否需要调整大小，因此我们丢弃了该批次到目前为止所做的所有进度。这意味着在调整大小的索引上重新开始，并基本上延长了索引操作的持续时间。

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

第二步：限制并发打开的索引数量

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

这是使用简化的最近最少使用 (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 或订阅我们的时事通讯。您可以通过查看我们的路线图并参与我们的产品讨论来了解有关我们产品的更多信息。