クラウドフラウドにおける 100TB のメモリ削減：Pingora と一貫性のあるハッシュ化の最適化

クラウドフラウド（Cloudflare）の規模はあまりに巨大で、その現実性を疑いたくなるほどです。数千台のサーバー、ペタバイト級の RAM、数百万コアの CPU を搭載していますが、すべてのリソースが最大限のパフォーマンスを発揮するよう求められています。

• リソースが広大に見えることにかかわらず、それは有限であり、全サービスが全ノードで稼働する限り無駄な領域はありません。
• この規模において、小さな改善は大幅に増幅されるため、1% 進歩だけでも称賛に値します。
• 微調整の合計が、DNS チームが先月削減した 100TB を超えるグローバルでさらに 100TB 以上の RAM の再獲得につながりました。

本記事では、単一アルゴリズムへのわずかな変更（Pingora ベースサービスのメモリフットプリント削減）と、それを実現するための技術的深掘りをご紹介します。

無駄を省くこと：過剰なメモリの発見

大規模組織で公平なリソース共有を維持することは容易ではありません。クラウドフラウドは、PBR (Pingora Backend Router) という内部ロードバランサーのメモリ使用量異常という課題に直面しました。

• 問題の核心: PBR はオープンソースライブラリ

  pingora-ketama

  （一貫性のあるハッシュ化の実装）に関連する構造体が、予想外に多くのメモリを使用していました。
• 発見者の功績: チケットを提出した Ivan が、この過剰な使用量を特定しました。

一貫性のあるハッシュ化とは？

サーバーの追加・削除時に大規模な変更なしでタスクを分配するための手法です。

• 仕組み: URL をキャッシュキーとしてサーバーにルーティングし、データセンターごとにファイルを一本のみ保持して場所を安定させます。
• 基本原理: ハッシュ関数はあらゆる入力を受け入れ、それを単一无符号整数（32/64/128 ビット）に変換します。
  • これにより、タスクとサーバーを「リング」上の位置関係で結びつけます。
• 割り当てロジック: タスクのハッシュ値より左隣にある最初のサーバーに割り当てられます（サーバー C は範囲がリングを巻き戻ります）。

数学的な不均等性と改善の必要性

一貫性のあるハッシュ化は単純ですが、サーバー間の負荷分配には統計的な偏りがあります。

• 期待値 (Exp) と標準偏差 (SD)
  • $N$ 台のサーバーにおける範囲サイズ： $$ \text{Exp} = \frac{1}{N}, \quad \text{SD} = \frac{1}{N}\sqrt{\frac{N-1}{N+1}} $$
  • サーバー数 $N=100$ の場合、期待値は 1%、標準偏差は約 0.99% です。
• 変動係数 (CV)
  • エラーマージンを理解するために重要： $$ \text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}} $$
  • $N=100$ の場合、$\text{CV} \approx 99%$ です。
  • 意味: サーバーごとの負荷が意図通り均等でない可能性が高く、一部のサーバーが 2 倍のリクエストを処理している状況が発生します。

解決策：ハッシュ数を増やす（万能の釘）

問題を「数直線上」で比較可能にするため、単一ハッシュではなく複数のハッシュを導入します。

• 大数の法則: セグメント数が増えると、全体的な負荷分担が均等化されます。
• 効果: NGINX や Pingora のデフォルト（160 ハッシュ）を使用すると、CV は約 99% から**約 8%**へ劇的に低下します。
• 重み付けの導入 (Ketama): サーバーごとに異なる容量を持つ場合、重み $w$ に比例してハッシュ数を設定します ($H_1 = w \times H_2$)。
  • クラウドフラウドでは、ディスクスペースを重みとして活用し、負荷をストレージサイズに合わせてスケーリングしています。

さらにの課題：リングの組み合わせ爆発

すべてのリクエストをどのサーバーも処理できるとは限らない場合（キャッシュ有効化要件など）、新しいリングが必要になります。

• 指数関数的な複雑さ: 異なる特徴（リージョン、機能等）ごとにリングを作る必要が生じ、メモリ消費が爆発的に増大します。
• 発見: 「過剰なメモリ使用量」の原因は、必要な全機能をカバーするための膨大な数のハッシュをメモリ内に格納していたことでした。

ストレージの構造最適化：25% の削減

メモリ使用量を削減する第一歩目は、データ構造の再設計です。

• 元の問題構造体:

  struct Point {
      hash: u32,
      index: u32, // 4 バイト (無駄な領域)
  }
  

• 洞察: PBR は同時に最大 65k ($2^{16}$) サーバーを管理する必要がないため、インデックスは

  u16

  で十分です。
• Rust の課題: メモリアラインメントにより、構造体のサイズは最大のフィールドの倍数になります。単純な型変更では削減できません。

実装ソリューション：生のバイト配列を使用

struct Point([u8; 6]); // 6 バイト固定 (4 ハッシュ + 2 インデックス)

impl Point {
    fn hash(&self) -> u32 {
        u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
    }

    fn index(&self) -> u16 {
        u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
    }
}

• 成果: この変更により、一貫性のあるハッシュ化に関連するメモリ使用量が驚くべき 25% 削減されました。

ハッシュ数の削減：数学による根拠

さらに削減するには、必要なハッシュ数を減らす必要がありますが、精度低下を避けるための計算が必要です。

• 多ハッシュ環境での変動係数: $$ \text{CV}_k = \sqrt{\frac{N-1}{(N*k+1)}} $$ （ここで $k$ はサーバーあたりのハッシュ数）
• 限界: エラーマージンを下げるためには、ほぼ一位桁増やすだけのハッシュ数を追加する必要があり、改善率は低下します。
• 衝突のリスク: 32 ビットハッシュを使用するため、ハッシュ数が増えると生日のパラドックスにより衝突確率が急上昇します。
  • 衝突はランダムなエラーを発生させ、予測不能な負荷不均等をもたらします。
• 結論: 数学的な裏付けのもと、サーバーあたり生成するハッシュ数を90% 削減しても大きな誤差にはなりません。

オリジンへの影響なく移行する戦略

ハッシュリングを変更するとキャッシュ無効化が発生するため、段階的かつ安全な移行が必要です。

• デュアルリング運用:
  • PBR に旧 (

    ketama

    ) と新（小型）の両方のリングを同時に保持させます。
  • 各リクエストは移行フレームワークで最適なリングを選択し、ロールバックも可能です。
• 段階的 Rollout (段階的な展開):
  • 小規模検証: ローカル環境から開始。
  • データセンター単位: 影響範囲（Blast Radius）を小さく保ちながら徐々に拡大。
  • グローバル展開: 全データを対象に実施。
• 監視指標: バックエンド選択、リングバージョン、メモリ使用量、キャッシュ挙動などを追跡し、問題が発生した場合に迅速に対応します。

移行結果

• 移行完了後、旧リングのパスを削除。
• 成果: 変更週の PBR メモリ使用量 vs 数週間前の比較において、100TB のメモリ削減を確認しました。

ご自身でもお試しください

本記事で述べた変更はすべて公開されています。安定性と制御性を重視し、旧機能との共存も可能です。

• 利用方法:

  pingora-ketama

  クレート内で Cargo feature として利用可能。
  • v2 リング: コンパクトなフォーマット、高速ソート、スケーリング機能付き。
  • v1 リング: 既存の安定した挙動を維持。
• 推奨事項: システムごとの検証を行い、数学的な最適化による潜在的な勝利を探ってみてください。
• 哲学: Rust で解決できない問題はありますが、数学は普遍的です。