將數百萬份文件壓縮至 128 TB 的虛擬記憶體中

程式可以從作業系統請求多少虛擬記憶體？當然，不會超過機器中安裝的 RAM 容量？我們或許可以再加上設定的交換空間或分頁檔容量？等等，這也可能取決於其他程式使用了多少記憶體嗎？

我們 Meilisearch 團隊歷經一番辛苦，才找到這些問題的精確答案。在這篇文章中，我們將分享我們對虛擬記憶體的了解，以及它如何以令人驚訝的微妙方式與應用程式互動。

Meilisearch 是一個開源搜尋引擎，旨在提供快速、高度相關且幾乎無需整合的搜尋。它允許將文件儲存在磁碟上的群組中，稱為索引，並搜尋這些索引以擷取與每個查詢相關的文件。

自Meilisearch v1.1以來，我們現在已進入v1.6！我們移除了索引數量和最大大小的限制。在本文中，我們將分享動態虛擬記憶體管理如何成為實施這些改進的關鍵。

汽車銷售員迷因，但汽車是 Linux 程式的虛擬位址空間

虛擬記憶體及其對 Meilisearch 的限制

什麼是虛擬記憶體？

虛擬記憶體是作業系統 (OS) 建立的抽象概念，用於管理實體記憶體。此抽象概念允許作業系統為執行中的程式提供虛擬位址空間。每個程式的虛擬位址空間都與其他程式隔離。這樣，可以防止程式意外（或惡意）存取屬於其他程式的記憶體。這與所有程式都可直接存取實體記憶體的情況相反，這種情況在較舊的作業系統中曾經存在，並且在某些嵌入式系統中仍然存在。

作業系統透過將應用程式操作的虛擬記憶體頁面轉換為它們在實體記憶體中的對應部分來實作虛擬記憶體。

虛擬記憶體還使作業系統能夠實作一種稱為交換的機制（也稱為分頁檔）。透過將虛擬記憶體頁面對應到較慢的磁碟儲存記憶體，以便在下次存取該頁面時重新載入到實體記憶體中，虛擬記憶體也提供了一種解決比實體可用記憶體更多記憶體的方法。

下圖顯示了兩個程式的虛擬記憶體範例，其中每個程式只能存取作業系統分配給它的實體記憶體部分。程式 A 的一個頁面在磁碟上「換出」，並將在下次存取時從磁碟載入到實體記憶體中。

虛擬位址轉換的簡化表示

Meilisearch 中的虛擬記憶體

在 Unix 環境中，您可以使用 htop 等命令列介面工具來查看程式使用了多少虛擬記憶體。以下是 Meilisearch 執行個體的命令輸出

如您所見，Meilisearch 正在使用驚人的 8593 GB 虛擬記憶體，遠遠超過此機器上的實體記憶體 (16GB) 和磁碟 (1000GB)。虛擬記憶體可以為程式提供幾乎無限的記憶體。請注意，實體記憶體使用率（實際 RAM）要低得多，僅使用了 38464 KB。

Meilisearch 虛擬記憶體使用的主要原因是記憶體對應，其中作業系統將檔案內容對應到虛擬記憶體。Meilisearch 使用 LMDB 鍵值儲存來將磁碟上儲存的索引內容對應到虛擬記憶體。這樣，對索引檔案的任何讀寫操作都會透過虛擬記憶體緩衝區進行。作業系統透明且有效地在實體記憶體和磁碟之間交換記憶體頁面。

現在的問題是，此類記憶體對應檔案可能會佔用虛擬位址空間的相當一部分。當對應 10 GB 的檔案時，您基本上需要一個對應的 10 GB 連續虛擬記憶體緩衝區。

此外，必須在建立對應時指定可透過記憶體對應寫入檔案的最大大小，以便作業系統可以判斷用於對應的連續虛擬記憶體緩衝區的大小。

回到 Meilisearch 使用的 8593 GB 虛擬記憶體，我們現在了解，其中大部分實際上用於建立文件索引的記憶體對應。Meilisearch 分配了如此多的記憶體，以確保這些記憶體對應足夠大，足以容納磁碟上索引的成長。

但是限制是什麼？一個程式的虛擬記憶體可以成長多少？結果，可以同時存在多少索引，以及它們的最大大小是多少？

128 TB 只能容納這麼多索引！

理論上，在 64 位元電腦上，虛擬位址空間為 2^64 位元組。也就是 18.45 EB。超過 1600 萬 TB！但是實際上，作業系統為程式專用的虛擬位址空間要小得多：Linux 上為 128TB，而 Windows 上為 8TB。

128 TB 看起來可能很多。但是，在 Meilisearch 執行個體可以使用的索引數量 (N) 與索引的最大大小 (M) 之間存在一個需要考慮的取捨。基本上，我們需要 N * M 保持在 128 TB 限制以下。而且，由於文件索引有時會成長到數百 GB 以上，這可能是一個挑戰。

在 v1.0 之前的 Meilisearch 版本中，這種取捨透過 --max-index-size CLI 參數公開。這讓開發人員可以定義每個索引的對應大小，預設值為 100 GB。在先前的這些版本中，如果您想要擁有大於 100 GB 的索引，則需要將 --max-index-size 的值變更為索引所需的估計最大大小。

因此，儘管這不明顯，變更 --max-index-size 參數的值會限制 Meilisearch 執行個體可以使用的索引數量：在 Linux 上，預設值為 100 GB 時，約為 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 或訂閱我們的 電子報。您可以查看我們的路線圖並參與我們的產品討論，以了解更多關於我們產品的資訊。