Cloudflareが数学とRustでグローバルのRAMを100TB超削減——一貫性ハッシュの最適化と構造体圧縮の舞台裏

9月18日、Cloudflareが「Saving another 100TB of RAM with math (and Rust)」と題した記事を公開した。一貫性ハッシュアルゴリズムの改善とRust構造体の最適化によって、グローバルで100TB以上のRAMを削減した技術的経緯を詳しく解説したものだ。

Cloudflareは世界中にサーバーを展開し、ペタバイト規模のRAMと数百万のCPUコアを運用している。そのスケールでは、1%の改善でも莫大なコスト削減につながる。今回の改善はDNSチームによる同様のメモリ削減の取り組みに続くもので、発端は「社内チケット一枚」だった。

発端：「メモリを使いすぎている」というチケット

パフォーマンスチームに寄せられたそのチケットは、エンジニアのIvanが報告したものだった。「Pingora Backend Router（PBR）において、pingora-ketama（一貫性ハッシュを扱うCloudflareのオープンソースライブラリ、GitHub）が過剰なメモリを消費している」という内容で、場合によっては1インスタンスあたり6GBに達するケースもあったという。

PingoraはCloudflareが自社開発したRust製プロキシフレームワークで、NGINXを置き換える形で同社のグローバルインフラで稼働している。PBRはそのPingora上で動くルーターコンポーネントだ。

一貫性ハッシュとは何か、なぜメモリを食うのか

一貫性ハッシュ（Consistent Hashing）は、サーバーの増減があっても大規模な再配置が不要な、負荷分散の定番手法だ。CloudflareではURLベースでキャッシュリクエストをサーバーにルーティングするために使用しており、データセンター内でファイルのコピーを一か所に集約できる。

基本的な仕組みはシンプルで、サーバーとリクエストをそれぞれハッシュ値として数直線上にマッピングし、「自分の左隣のサーバー」に処理を割り当てる。ただし素朴な実装では負荷の偏りが深刻になる。サーバー100台の場合、各サーバーが担当するレンジの変動係数（CV）はおよそ**99%**に達する。あるサーバーは期待の2倍の処理をこなし、別のサーバーはほぼ何もしない、という極端な状況が生じうる。

この問題への対策が「各サーバーに複数のハッシュポイントを割り当てる」方法だ。NGINXやPingoraではデフォルト160ポイントが使われており、これによりCVは約8%まで改善される。

さらにCloudflareでは、ストレージ容量の異なるサーバーが混在するため、ディスク容量に比例してハッシュ数を増やす「重み付き」のketamaアルゴリズムを採用している。加えて、コンプライアンス要件やキャッシュ機能の有無によって「特定のサーバー群でしか処理できないリクエスト」が存在するため、機能の組み合わせごとに別々のハッシュリングを保持する必要があり、その数が数十にも膨れ上がる。これがメモリ爆発の根本原因だった。

改善その1：構造体を8バイトから6バイトに縮める（25%削減）

エンジニアのZaidoonによる最初の改善は、ハッシュポイントを格納する構造体の見直しだ。

元の構造体：

struct Point {
    hash: u32,
    index: u32,
}

この構造体はメモリ上で8バイトを消費する。hashの4バイトは避けられないが、index（サーバーを指すインデックス）に32ビットを使うのは過剰だ。PBRが同時に扱うサーバー数は65,000台（2の16乗）を超えることはないため、16ビットで十分である。

struct PointV2 {
    hash: u32,
    index: u16,
}

ただし、これだけではRustのアライメント規則により実際のメモリ消費は変わらない。Rustは構造体のサイズを「最大フィールドのアライメント」の倍数に揃えるため、u32が残っている限り合計は8バイトのままだ。

解決策は、構造体をバイト配列として表現し、ゲッターで値を取り出す方法だ：

struct Point([u8; 6]);
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())
   }
}

8バイトから6バイトへ。この変更だけでメモリ使用量が25%削減された。

改善その2：数学でハッシュ数の最適解を導く

もう一つの改善は、「そもそも何ポイント使えばいいのか」を数学的に正確に求めることだ。

N台のサーバーにkポイントを使った場合の変動係数は、CV_k = sqrt((N-1) / (N*k + 1)) で表される。この式から、精度の向上はハッシュ数の増加に対して逓減することがわかる。CVを半分にするには4倍のハッシュ数が必要で、10分の1にするには100倍必要だ。

つまり、デフォルトの160ポイントは多くのユースケースで過剰であり、必要な精度を維持しながらポイント数を大幅に削減できる余地がある。Cloudflareはこの式を使い、許容する誤差範囲から逆算して最適なポイント数を導き出した。構造体の縮小と合わせることで、グローバルで合計100TB超のRAM削減を実現している。

Rustのアライメント制約を意識した構造体設計と、統計的な裏付けに基づくアルゴリズムのチューニング——この2つのアプローチを組み合わせた改善の詳細はSaving another 100TB of RAM with math (and Rust)を参照していただきたい。