在 128 TB 虚拟内存中挤压数百万个文档

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

我们在 Meilisearch 艰难地找到了这些问题的准确答案。 在本文中，我们将分享我们关于虚拟内存的学习成果，以及虚拟内存如何以惊人的微妙方式与应用程序交互。

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

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

汽车销售员 meme，但汽车是 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 的问题（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 或订阅我们的新闻通讯。 您可以通过查看我们的路线图并参与我们的产品讨论来了解有关我们产品的更多信息。