Cloudflare は構造体を1つとパラメータを1つ変えただけで、100TB のメモリを回収した

Cloudflare の規模はどれほどなのか。何年働いても、いまだに実感が湧かない。世界中に数千台のサーバーがあり、メモリは PB 級、CPU コアは数百万。しかもそのすべてが限界ぎりぎりで動いている。リソースは多く見えても所詮は有限で、どのノードも全サービスを動かすとなれば、無駄にできる余地はない。この規模ではどんな小さな改善も増幅されるから、1% の最適化でも祝う価値がある。中にはそれをはるかに超えるものもある。本記事で扱うのは、あるアルゴリズムへの小さな変更が、Pingora ベースのあるサービスのメモリ使用量を大きく減らした話だ。これにより世界中で 100TB 以上のメモリを回収できた。ちょうど先月、DNS チームが100TB を削減したばかりだった。

無駄を出さない

チーム間でリソース配分を公平に保つのは難しい。組織が大きくなるほど、それは難しくなる。Cloudflare は Performance チームの絶え間ない働きによってこのバランスを維持している。話は Ivan が起票したチケットから始まる。_Pingora Backend Router における pingora-ketama のメモリ使用量が過大_というものだ。問題は、社内のロードバランシングサービス Pingora Backend Router（そう、PBR）が想定を大きく超えるメモリを使っていたこと。具体的には pingora-ketama 関連のデータ構造、つまりコンシステントハッシュを扱う私たちのオープンソースライブラリに原因があった。このメモリ使用量の過大さをどう解消したかを説明するには、まずコンシステントハッシュとは何か、PBR がなぜそれを使うのか、そしてどうしてこんなにメモリを食うようになったのかを話す必要がある。ついでに Rust の話も少し、数学も少し。

コンシステントハッシュ

コンシステントハッシュは広く使われているタスク割り当ての手法で、サーバーを増減しても大規模な変更をせずにタスクを複数のサーバーに分散できる。社内では URL ごとにキャッシュ可能なリクエストをサーバーへルーティングするために使っていて、各データセンターがファイルのコピーを 1 つだけ持てばよく、しかも各ファイルの所在を安定して見つけられる。この仕組みについては以前何度も紹介してきたが、このアルゴリズムが何の役に立ち、どう動くのかを改めて追ってみよう。コンシステントハッシュの要点は、ハッシュ関数が任意の入力を受け取る一方で、出力は符号なし整数 1 つだけ（使うハッシュ関数によって 32、64、128 ビット）だという点にある。これによりタスクとサーバーを_一貫した_方法で対応付けられる。コンシステントハッシュの解説の多くは、出力空間を最大値からゼロへ戻る連続したリングとして想像させる。この描き方は視覚的には優れているが、整数の区間という単純な概念を実際より複雑に見せてもしまう。本記事では、ハッシュ関数の 32 ビット出力を数直線として表す。

BLOG-3083 2.png

サーバー A、B、C の集合と、タスク t〜z の集合があるとしよう。それぞれが表す値のハッシュに基づいて、数直線上に写像できる。サーバーは IP アドレス、タスクはキャッシュキーを使う。

BLOG-3083 3.png

タスクをサーバーに割り当てる作業は、各タスクの左側にある最初のサーバーを探すことに変わる。各サーバーに対応するハッシュ区間に色を塗れば、一目でわかる。サーバー C の区間は先頭に回り込んでいる点に注意。だからハッシュはリング上に分布すると言われる。

BLOG-3083 4.png

これだけだ。最も基本的なレベルでは、コンシステントハッシュとはこういうものに過ぎない。だが、改善の余地があることにはすぐ気づく。この例ではサーバー A の区間が B や C より明らかに大きい。これは問題だ。サーバーが処理するリクエストの割合は、数直線上での区間の大きさに比例するからだ。理想的にはどのサーバーの区間も同じ大きさにしたいが、ハッシュは本質的に乱数なので、区間の大きさは_統計的に_しか語れない。😨

数学とその帰結

まず最初に、慌てないこと。私が嘘をつかないことは保証するし、これから話す内容も入門レベルの確率の授業の範囲を出ない。統計分布の話になると、不確実性を定量的に扱うのに役立つ概念が2つある。期待値と標準偏差だ。（かなり乱暴に言えば）期待値はある分布に従う測定値が集まる中心を示し、標準偏差はほとんどの測定値がその中心からどれくらい近くにあるかを示す。

一貫性ハッシュについて、N台のサーバーのうち1台が対応する区間の割合を、次のように計算できる。（この式の導出は後回しにする。）

 Exp = (1)/(N) 

 SD = (1)/(N)√((N-1)/(N+1))

具体的な数字を入れてみよう。サーバーが100台あるとすると、上の式からこうなる。

Exp=1/100 = 1% 

 SD= (1)/(100)√((100-1)/(100+1)) ≈ 0.99%

つまり、各サーバーが担当する区間は全体の0.99%を中心とし、ほとんどの区間の長さは期待値の前後1%に収まる。これ_だけ聞くと_悪くなさそうだが、これは_全体の長さ_の0.99%だという点を忘れてはいけない。誤差が目標の大きさに対してどれくらいの割合を占めるかを見るには、標準偏差を期待値で割る必要がある。この値を変動係数と呼ぶ。

CV = (SD)/(Exp) = √((N-1)/(N+1))

N=100, CV ≈ 99% のとき、つまり、本来の仕事より99%多く（2倍のリクエストを）処理しなければならないサーバーもあれば、ほとんど何もしなくていいサーバーもあるということだ。一貫性ハッシュでサーバーの負荷がどれくらい均等になるかを予測する方法が手に入ったので、改善に取りかかれる。

ハッシュを増やすとどうなるか

一貫性ハッシュの単純さは諸刃の剣だ。理解も実装も容易なのは、すべてが同じ数直線上に対応づけられるハッシュ値になるからだが、改善もまたこの数直線上に対応づけられなければならない。つまり、一貫性ハッシュの問題は、解決策が_より多くのハッシュ_しかありえないということだ。金のハンマー（それを持つと何でも釘に見える）というよりは、金の_釘_に近い。あらゆる道具をハンマーに変えてしまうのだ。

負荷の偏りを解消するには、サーバーごとに1つではなく複数のハッシュを持たせればいい。背後の数学は後で述べるが、直感的には納得できるはずだ。個々の区間の標準偏差は大きくても、区間をたくさん足し合わせれば合計の大きさは平均に近づく。上の図の3サーバーの例で、各サーバーにランダムなハッシュを2つずつ追加すると、負荷がより均等になるのがわかる。

BLOG-3083 5.png

この例はかなり作為的だ。システムにランダム性がある以上、サーバーごとにハッシュを2つ追加してどれだけ改善するかに保証はない。だが、そうしたハッシュの断片をより多く組み合わせれば分布はより均一に近づくというのは直感的に理解できる。和を取る各区間には、別の区間を相殺する機会がある。短すぎる区間もあれば、長すぎる区間もある。大数の法則が言っているのはほぼこれだ……明らかな問題は、それが大数でしか成り立たないことだ。NGINXでは、サーバーごとのハッシュ数の基準値が160にハードコードされており、Pingoraも同じ値をデフォルトで使っている。数学の導出はここでは省くが、先ほどの100台の例に戻ると、サーバーごとに1点ではなく160点を使えば、変動係数（誤差範囲のようなものだと思えばいい）は約99%から約8%に下がる。かなりの改善だ。

ハッシュ値をもっと増やすとどうなるか

ここまでで、サーバーごとのハッシュ数を固定で増やせば、負荷をサーバー間でより均等に分散できることがわかった。では、負荷を_均等にしたくない_場合はどうか。Cloudflareの状況では、他のサーバーよりストレージが大きいサーバーもあり、そのサーバーに割り当てるリクエスト数をディスク容量に比例させる方が都合がいい。これを実現する方法の1つがketamaアルゴリズムだ。面白い名前だが、最初にこれを実装したライブラリに由来しており、そのライブラリの名前は……自分で検索してほしい 😶‍🌫️。

アルゴリズムを突き詰めるとこうなる。任意の2台のサーバー S_1 と S_2 について、S_1 に S_2 の w× 倍のリクエストを処理させたいなら、S_1 に関連づけるハッシュ数は H_1 = w× H_2 を満たす必要がある。こうすれば、サーバーごとに「重み」を設定し、そのサーバーに関連づけるハッシュ数のスケーリングに使える。残念ながら、前節で加えた固定のスケーリング係数の代わりにはならない。あのスケーリングは誤差範囲の下限を決めるために残す必要があり、それは重みが最も小さいサーバーに現れる。

ストレージの規模に合わせてワークロードをスケールさせたいなら、ディスク容量を重みとして使えばいい。Pingora チームは長年そうしてきた。社内の他の計算集約的なワークロードでは、CPU や GPU の数で重みを決めることもある。

もっとハッシュを増やしたら？

最後に残った問題はこうだ。ここまではどのサーバーでもどのリクエストでも処理できると仮定してきたが、現実はそうではない。コンプライアンス要件や有効になっているキャッシュ機能などの要因で、特定のリクエストを処理できるサーバーは一部に限られる。厄介なのは、これまでと同じように同じリングにハッシュを足すだけでは済まないことだ。完全に_独立した_リングを新たに追加する必要があり、しかもそれだけでは足りない——機能の_組み合わせ_ごとに専用のリングが要りうる。

組み合わせごとに複製するのは、指数爆発の典型的なレシピだ。我々のケースでは、いくつかの機能の違いだけで 2^handful = dozens 個の独立したコンシステントハッシュリングが生まれる。もうお察しだろうが、Ivan が見つけた「メモリ使用量が過大」（場合によっては 6GB に達した）は、必要な機能をすべて賄うためにハッシュの数が膨大になり、しかもそれを常駐させなければならなかったことが原因だ。ではどうするか。

ストレージの最適化

大きな改善は Zaidoon による、PBR でハッシュを格納する struct への新しい着想から生まれた。その struct はこうなっている：

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

メモリ上では 8 バイトを占め、うち 4 バイトがハッシュ（ここは削れない）、残り 4 バイトが別の配列に格納されたサーバーを指すインデックスだ。Zaidoon の洞察は、このインデックスを 32 ビット整数で持つのは無駄だというものだった。PBR が同時に調整するサーバーが 2^16 ≈ 65k 台を超えることはまずないから、16 ビット整数で足りる。そこで上の struct をこう置き換えられる：

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

あいにく Rust はそう簡単には許してくれない。上のようにインデックスのサイズを変えてもメモリ使用量は減らない。Rust のアラインメント規則により、構造体のメモリ上のサイズは最も大きい（つまり「アラインメント要件が最も高い」）フィールドの整数倍でなければならないからだ。ここではハッシュが最大で 4 バイトを占めるので、メモリに載せるときの Point のサイズは N × 4、最小でも 8 バイトになる。

幸い、定番の回避策がある。#[repr(packed)] を使いたくなるかもしれない（実際は私がそう思った）が、これが物議を醸すのには十分な理由がある。より安全だが可読性に劣る方法は、ハッシュとインデックスを生のバイト配列として格納し、getter でアクセスするやり方だ。どちらの書き方もコンパイル結果はまったく同じになる。

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())
 }
}

この単純な（とはいえ冗長な）変更で、コンシステントハッシュが使うメモリが一気に 25% 減った。さらに先へ進むには数学に戻る必要がある。つかまっていてほしい、これが最後の追い込みだ。

ハッシュをもっと少なくしたら？

すでにお気づきかもしれないが、示した標準偏差の式はサーバーごとにハッシュが 1 つの場合にしか当てはまらない。サーバーごとに k 個のハッシュがある場合の式を導くのは容易ではなく、たいていの資料は近似値か漸近極限しか与えない。だが我々は違う。私は統計学者ではないが、微積分の教師に育てられた身だ（母さん、こんにちは！）。あの_本当の_値が知りたい。完全な導出は補足記事に置いて、ここでは結果だけ示す。

Exp_k = (1)/(N),

 SD_k=√(((k+1))/(N(kN+1))-(1)/(N^2))

ハッシュ数を増やすことが精度をどう上げるかを見るには、変動係数をもう一度見ればいい。

CV_k=(SD_k)/(Exp_k)=√((N-1)/((N*k+1)))

CV_k をプロットすると、「ハッシュを増やせばいい」という発想の潜在的な問題が見えてくる（メモリを食う以外にも）。

BLOG-3083 6.png

誤差が 1 段下がるごとに、サーバーあたりのハッシュ数はほぼ 1 桁増える。つまりハッシュを増やすほど効果は薄れる。思い出してほしいが、我々は 160 を基数とし、サーバーのストレージ容量でスケールさせたハッシュ数を使っている。計算を簡単にするため、あるサーバーの重み係数 m_w を 625 とすると、k = 160×625 = 100,000 になる。上のグラフからわかるように、最後に足した 90,000 個のハッシュがもたらす誤差の低下はわずか 0.7% だ。しかも悪い話はまだ先にある。

この美しい数学の予測は、ハッシュを連続環として考えたときにしか成り立たない。だが実際にはハッシュは 32 ビットの数値で、衝突の可能性があり、ハッシュ数が増えるにつれて衝突確率は驚くほど速く上がる（誕生日のパラドックスを参照）。衝突が問題なのは、理想的な状況では各ハッシュが対応するサーバーが処理するリクエストの量と分布に影響を与えるのに対し、衝突が起きると一部の寄与がランダムに捨てられ、予測できない誤差が持ち込まれるからだ。32 ビットハッシュを使ったシミュレーション結果と予測誤差率を比べると、2048 台のサーバーを持つデータセンターでは、サーバーあたり 10,000 から 100,000 個のハッシュの間で誤差率が上がり始めるのがわかる。

BLOG-3083 7.png

正直なところ、この結論にはまだ少し引っかかるものがある。とはいえ、RAM を一部回収するという計画にとっては朗報だ。数学的な裏付けが得られたことで、サーバーごとに生成するハッシュ数を 90% 削減しても目立った誤差は生じないと判断し、そのとおりに実行した。

移行、ただしオリジンは壊さない

問題がもう一つある。ハッシュリングを変えれば、キャッシュ可能なリクエストの一部は行き先が変わる。新しいリングのほうが優れていても、ネットワーク全体を一度に切り替えれば、ほぼすべてのキャッシュが無効になってしまう。メモリ最適化のはずが、オリジンへの壊滅的なトラフィック増を招きかねない。

そこで一括切り替えはやめた。しばらくの間、PBR はキャッシュ可能なロードバランサーをメモリ上に 2 つ保持していた。旧 ketama リングと、新しい小さなリングだ。各リクエストをどちらのリングで処理するかは、通常の移行フレームワークが決める。これにより、ロールアウトの判断はリクエストハッシュごとに安定し、ロールバックの道筋も明確になった。異常が見つかれば、PBR を再デプロイすることなく、新しいリクエストを旧リングに戻せる。

次に移行を段階的に進めた。まず小規模な検証ポイントで試し、徐々に対象データセンターを増やし、最後に世界各地域へ展開した。

重要なのは、2 つの軸を独立に制御したことだ。新しいリングを使うトラフィックの割合と、そのトラフィックをどこまで移行させるか。全世界一律のパーセンテージで進めれば、キャッシュの揺れがあちこちに同時に広がる。データセンター単位で進めれば影響範囲を小さく抑えられ、変更が本当に安全かどうかを判断しやすくなる。

移行中は、バックエンド選択の trace、リングバージョンのカウンター、PBR の接続エラー、プロセスメモリ、起動時間、キャッシュの挙動、オリジンへのトラフィックを継続的に監視した。移行が 100% に達したところで、一時的な旧リングの経路を削除して完了だ。

BLOG-3083 8.png

上のグラフは、変更した週に PBR が使用したメモリと数週間前のデータ、そしてその差分を比較したものだ。急激な落ち込みは、大規模な（現在は使われていない）ハッシュリングを搭載した PBR のバージョンが完全に停止した日に対応している。差分を見れば満足のいく結果が出ている。これらの変更で使用メモリが 100TB 減った。

BLOG-3083 9.png

自分で試す

本記事で触れた変更はすべて pingora-ketama crate で利用できる。現時点では特に宣伝していない cargo feature という形だ。v2 リングはコンパクトな保存形式と高速なソート手法を採用し、ノードごとの基礎ハッシュ数を調整できる。これらの変更は安定性と制御性を最優先で進める必要があったため、v1 リングは pingora ketama の従来の実装と完全に一致しており、このライブラリは両方を同時に動かし、リクエストごとにどちらをいつ使うかを決められる。

私たちの一貫性ハッシュ実装を自分で書き換えるのもいいが、それ以上に伝えたいのはこういうことだ。自分のシステムを見直し、「単純」あるいは「自明」に見える決定の中に、数字を真面目に計算する気さえあれば大きな利益が隠れていることがある。すべてを Rust で解決できるとは限らないが、数学はどこでも通用する。