TLB 充填の最適化とページテーブルメモリ効率の課題

リン・トーヴァルズ氏による「ハッシュ型のページテーブルへの非難」に関する議論は、キャッシュラインあたりの TLB エントリー数という観点から成り立っています。

TLB 充填効率性の再考

• ツリー構造（マルチレベル）：近傍の項目が隣接しているため、1 つのキャッシュラインで複数の TLB エントリを同時に満たせる。
• ハッシュテーブル：近傍の要素がバケットに分散するため、このメリットが発揮されにくいと考えられている。
• 著者の見解：「良き（GOOD）」な構造とは限らない。優れた TLB 充填とは、「1 つのキャッシュラインで納めることができるすべての項目を事前に入荷する」ことである。
• Intel CPU の能力：1 回で 8 つの TLB エントリーを読み込める。
  • これに自己マッピング（または他のレベルへの専用キャッシュ）を組み合わせると、単一メモリ参照だけで、ハッシュテーブルがもたらす「愚かしい」性能の約 8 倍の被覆範囲が可能になる。

---

ページテーブルのメモリ効率性：一次から二次的懸念へ

ページテーブル自体のサイズは当初、レイテンシの問題に比べ次要的な懸念とされてきたが、状況は変化した。

• 2003 年頃の認識：
  • リン氏の修士論文（1997 年）では、レイテンシへの関心が優先されていた。
  • メモリ容量については十分に重視されていなかった（三段階マルチレベルページテーブルを採用）。
• 2020 年の転換点：シェイクール・ブット氏が、メモリ効率化が「二次的な懸念ではない」正確なケースを見出した。
  • page table の計量指標を

    memory.stat

    に追加した。
  • 一般的なケース：ページテーブルはマッピング済みのメモリの約 1/512 程度のみ使用する（多くの cgroup では 1% を下回る）。
    • ※ゼロコピーでアプリケーションメモリをマッピングするネットワークドライバなど、巨大な pgtable を必要とする特殊なケース以外。

N プロセスによる共有メモリのコスト増

各プロセスが同一ページをマップすると、それらのプロセスは独自の PTE（ページテーブルエントリー）を必要とするため、コストが増加する。

• 計算ロジック：
  • ページサイズ：4 KiB
  • PTE サイズ：8 バイト
  • 共有マッピングするプロセス数：N
  • コスト比率：データページの約 N/512 のメモリが必要となる。
• 具体例（512 プロセス）：
  • 512 つの PTE × 8 バイト = 4 KiB の追加メモリ必要。
  • この場合、ページテーブルのコストはデータページそのものと同程度になる。

リアルなケーススタディ：巨大な PTE メモリ消費

カーネルメーリングリストやコミュニティから報告された、多数のプロセスが大規模な共有メモ리를マッピングする際の「エッジケース」事例。

1. アンデリア・アランジェリ（Andrea Arcangeli, 2002 年）

• 問題：64 GiB の x86 マシンで空きメモリはあるのに、OOM（Out Of Memory）が発生したケース。
• 原因：数百のプロセスがそれぞれ同じ 1 GiB を共有マッピング。データページは共有だが、PTE は各プロセスごとに存在し、PAE で約 2 MiB を占有していた。
• 制約：x86（32 ビット）では「lowmem」領域に制限があり（物理メモリの約 896 MiB）、ページテーブルが低メモリアドレスを圧迫していた。
• 解決策：PTE の配置を lowmem から highmem に移動させるパッチ化。

2. カリド・アジズ（Khalid Aziz, 2022 年）

• 問題：512 GB RAM、300 GB SGA を持つ Oracle DB サーバーで、1,500 クライアント接続時に OOM クラッシュ。
• 原因：各プロセスが独自 PTE を持つため、最悪ケース（全プロセスが SGA をマッピング）では PTE 単体で 878 GB を占有する計算になる。
  • 例：4 KiB ページを 2,000 プロセスがマップ → 16 KB の PTE 必要。
• 解決策：mshare という仕組みの提案（プロセス間で PTE を共有化）。※未マージ。

3. チー・Zheng（Qi Zheng, 2021 年）

• 問題：RSS 590 GiB に対し、ページテーブルが 110 GiB も消費しているプロセス。
  • PTE 必要量推定：約 1.2 GiB のみだったはずだが、実際は 110 GiB。
• 原因：

  munmap()

  ではなく

  madvise(MADV_DONTNEED)

  を使用してメモリを返却した際、データページは解放されるが、PTE は割り当てられたまま残り、空の PTE が蓄積された。

  • free_pgtables

    →

    free_pgd_range

    の呼び出しで解消を試みたが、共有マッピングなしの単一プロセスによる持続的な保持が原因。
• 結果：パッチを改変し、2025 年にマージ。

データベース環境における実績

データベース関連の研究・測定でも同様の傾向が確認されている。

ペルコナ（Percona, 2021 年）の事例

• 現象：PostgreSQL が生産環境で頻発する OOM キル。
  • 環境：192 GiB マシン、共有バッファ 138 GiB、接続数 80。
• 進行状況：バックエンドキャッシュの拡大に伴い、ページテーブルが 45 MiB から 25 GiB に成長。メモリ圧迫とスワップを招いた。
• 解決策：巨大ページ（Huge Pages） の採用。
  • 結果：同ワークロード下でもページテーブルは 61 MiB で安定化。

クリックハウス（ClickHouse, 2026 年）の測定

• 現象：128 GiB マシン（共有バッファ 32 GiB）で、バックエンドキャッシュ（15.6 GiB）をスキャンするごとにページテーブルが増加。
  • キャッシュスキャン時：+31 MiB/回
  • 接続数 200 時：6.1 GiB を占有。
• 解決策：巨大ページの採用。
  • 結果：同接続数下でもコストを 111 MiB に抑制。

巨大ページ導入のデメリット

無償のものではなく、以下のような制約がある。

• フラグメント化されていない（連続した）メモリが必要。
• 負荷のかかったマシンでは同一リクエストの常時失敗や、THP（透明な巨大ページ）割り当てでのストールが発生する。
• THP の見直し：メル・ゴーマン氏（2016 年）は THP デフォルト無効化を提案。「数年経ったので手放す時」と述べている。ネルソン・エルハグ氏も、メモリリークや CPU 使用率問題への言及がある。

---

NUMA マシンにおける新たな課題

複数のノードを持つ NUMA マシンでは、レイテンシとメモリ容量に新たな制約が生まれる。

• 問題の本質：他のノード上のスレッドが TLB ミスすると、リモートメモリのページテーブルを参照しなければならない。
  • Mitosis（ASPLOS 2020）の研究：リモート PTE の参照は、遠隔データアクセスと同程度のパフォーマンス低下を引き起こす。
  • Hydra paper（USENIX ATC 2024）：8 ソケット・8 TB RAM マシンで再現確認。

スコープと同期のジレンマ

NUMA アプローチには主に 2 つの戦略があるが、いずれもトレードオフが存在する。

1. 全体ツリーの複製（Mitosis 方式）
   • 手法：各ノードで全体ページテーブルツリーを複製。
   • デメリット：
     • メモリコスト増（サイズ × ノード数）。
     • 変更時に全コピーを更新する必要がある（同期コスト）。
2. オンデマンドコピー（Hydra 方式）
   • 手法：PTE がフォールト発生したノードのみへコピー。ページテーブルページには「コピーを持つノードのリスト」を保持。
   • 特徴：初期メモリコストは抑えられ、アクセス時に応答。

結論：トレードオフの選択

NUMA マシンにおいて页面テーブルのコピー戦略を選ぶ際、以下の二択が迫られる。

• オプション A：コピーを 1 つだけ保ち、TLB ミス時にリモートテーブルを読むコストを負う。
  • → レイテンシパフォーマンスへの影響が懸念。
• オプション B：各ノードにコピーを持ち、同期コスト（メモリ使用量増）を負う。
  • → メモリ容量と保守性への影響が懸念。