数学（とRust）でさらに100TBのRAMを節約

数学（とRust）でさらに100TBのRAMを節約する

Cloudflareは、その規模があまりにも大きいため、長年勤務していても現実味がないほどです。世界中に数千台のサーバーを配置し、ペタバイト級のRAMと数百万のCPUコアを搭載し、それらすべてを最大限に活用しています。これらのリソースは広大に感じられますが、それでも有限であり、すべてのサービスをすべてのノードで実行する必要がある場合、無駄なスペースの入り込む余地はありません。

この規模では、小さな改善も大きく増幅されるため、1%ずつの改善でさえ祝う価値があります。そして、いくつかの微調整はさらに大きな効果をもたらします。この記事では、単一のアルゴリズムに対する小さな変更が、Pingoraベースのサービスのメモリフットプリントをどのように大幅に削減したかを見ていきます。これにより、DNSチームが先月削減できた100TBのメモリに加えて、世界中で100TB以上のRAMを回収することができました。

無駄にしない

チーム間で公平なリソース共有を維持することは容易ではありません。特に大規模な組織では。Cloudflareがバランスを保つ方法の1つは、素晴らしいパフォーマンスチームのたゆまぬ努力によるものです。

この話は、Ivanが「Pingora Backend Routerにおけるpingora-ketamaの過剰なメモリ使用量」というチケットを提出したことから始まります。その発見は、私たちの内部ロードバランシングサービスであるPingora Backend Router（はい、PBRです）が、予想よりも大幅に多くのメモリを使用しているということでした。具体的には、一貫性ハッシュ処理のためのオープンソースライブラリであるpingora-ketamaに関連する構造体で顕著でした。

このメモリの過剰使用と思われる問題にどのように対処したかを説明するには、まず一貫性ハッシュとは何か、なぜPBRで使用しているのか、そしてそれがどのようにしてメモリを大量に消費するようになったのかを説明する必要があります。その過程で、Rustと少しの数学も学びます。

一貫性ハッシュ

一貫性ハッシュは、サーバーの追加や削除時に大規模な変更を必要とせずに、タスクを複数のサーバーに分散するための広く使用されている手法です。内部的には、URLごとにキャッシュ可能なリクエストをサーバーにルーティングするために使用しています。これにより、データセンターごとにファイルのコピーを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の範囲よりも大幅に大きいことに注目してください。これは問題です。なぜなら、サーバーが処理するリクエストの割合は、数値直線上のその範囲のサイズに比例するからです。理想的には、各サーバーが均等なサイズを持つことを保証したいのですが、ハッシュは基本的にランダムな数値であるため、領域のサイズについては統計について話す必要があります。😨

数学と結果

まず、パニックにならないでください。私はあなたを騙そうとしているわけではないことを約束しますし、1日目の確率の授業の範囲内で安全に留まります。統計分布について話すとき、不確実性を役立つ方法で定量化するのに役立つ2つの大きな要因があります：期待値と標準偏差です。非常に単純化すると、期待値は分布に基づいた測定値が中心となる点を与え、標準偏差はほとんどの測定値がその中心点にどれだけ近い可能性が高いかを示します。

一貫性ハッシュの場合、N個のサーバーのうち1つに関連付けられた範囲の分数サイズについて、これらの要因を計算できます。（この数式の由来の詳細は後ほど）。

$$m \begin{align] \text{Exp} &= \frac{1}{N} \ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align]  m$$

具体的な数値で言うと、サーバーが100台あるとします。上記の数式は次のような結果になります。

$$m     \text{Exp}=1/100 = 1% \     \text{SD}= \frac{1}{100}\sqrt{\frac{100-1}{100+1}} \approx 0.99% m$$

これは、各サーバーが処理する範囲が平均して全体の0.99%を中心に分布し、ほとんどの長さが期待値の1%以内に収まることを意味します。これは、総長の0.99%であるため、一見すると良いように聞こえます。しかし、標準偏差を期待値でスケーリングして、ターゲットサイズに対するエラーの大きさを確認する必要があります。この値は変動係数と呼ばれます。

$$m \text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}} m$$

$m N=100$の場合、$\text{CV} \approx 99%$です。これは、一部のサーバーが本来より99%多く（リクエストの2倍を処理）、他のサーバーはほとんど何もしていない可能性があることを意味します！サーバーごとの負荷の均一性を一貫性ハッシュで予測する方法がわかったので、改善に取り掛かることができます。

ハッシュを追加したらどうなるか？

一貫性ハッシュの単純さは諸刃の剣です。すべてが同じ数値直線上の理解しやすいハッシュに変換されるため、理解と実装が容易ですが、システムへのあらゆる改善もその数値直線に関連付ける必要があります。つまり、一貫性ハッシュの問題に対する解決策はハッシュの追加しかないということです。黄金のハンマー（すべての問題を釘に見せる道具）というよりは、すべての道具をハンマーに変える黄金の釘のようなものです。

負荷分散の不均衡問題を解決するために、各サーバーを表すハッシュを1つだけでなく複数追加できます。これの背後にある数学はすぐに説明しますが、個々の範囲には大きな標準偏差がありますが、それらをたくさん組み合わせると、合計サイズが均一になるという直感的な感覚があるはずです。上記の図の3サーバーの例で、各サーバーにランダムに2つのハッシュを追加すると、各サーバーのワークロードの均一化に役立つことがわかります。

［画像: BLOG-3083 5.png］

これは確かに人工的な例です。システムのランダムな性質により、サーバーあたり2つの追加ハッシュを追加することで得られる改善の保証はありませんが、より多くのハッシュセグメントを組み合わせることで、より均一な分布が得られるという直感的な感覚があるはずです。合計の各セグメントには、バランスを取る機会があります。1つは短すぎるかもしれません。1つは長すぎるかもしれません。これは基本的に大数の法則が示していることです…明らかな問題は、それが大きな数にしか機能しないことです。NGINXでは、サーバーあたりのハッシュの基本数は160にハードコードされており、Pingoraはデフォルトと同じ値を使用しています。ここでは数学的な詳細は省きますが、100サーバーの例に戻ると、1つだけではなくサーバーあたり160個のハッシュを使用すると、変動係数（エラーマージンと考えることができます）は約99%から約8%に低下し、大幅な改善となります。

さらにハッシュを追加したらどうなるか？

上記で、サーバーあたりのハッシュ数を定数だけ増やすことで、サーバーごとのワークロードの分布を改善できることがわかりましたが、ワークロードを均等に分散したくない場合はどうでしょうか？Cloudflareの場合、他のサーバーよりもストレージ容量が多いサーバーがいくつかあるため、サーバーに割り当てられるリクエスト数をディスク容量に比例させる方が良いでしょう。これを達成する1つの方法は、ketamaアルゴリズムを使用することです。この名前は少し面白いです。なぜなら、アルゴリズムは最初に実装されたライブラリにちなんで名付けられ、そのライブラリは…まあ、ググってみてください 😶‍🌫️。

アルゴリズム全体は次のようになります：任意の2つのサーバー、$m S_1m$と$mS_2m$について、$mS_1m$によって処理されるリクエスト数が$mS_2m$によって処理されるリクエスト数の$mw\timesm$倍になるようにしたい場合、$mS_1m$に関連付けられるハッシュの数は$mH_1 = w\times H_2m$である必要があります。これにより、各サーバーに「重み」を設定でき、そのサーバーに関連付けられるハッシュの数がスケーリングされます。残念ながら、これは前のセクションで追加した定数スケールファクターの代わりにはなりません。そのスケーリングは、最小のエラーマージンを設定するために必要であり、これは最も重みが低いサーバーに現れます。

私たちの場合、ワークロードをストレージに基づいてスケーリングしたいので、ディスク容量を重みとして使用できます。これは、Pingoraチームが長年行ってきたことです。社内の他の場所で、ワークロードがより計算集約型の場合、重みはCPUまたはGPUの数に基づいている可能性があります。

さらにさらにハッシュを追加したらどうなるか？？？

最後に解決する必要がある問題は、これまでのところ、どのサーバーでもどのリクエストも処理できるという仮定の下で作業してきましたが、実際にはそうではないということです。コンプライアンス要件や有効なキャッシュ機能などにより、特定のリクエストを処理できるのは一部のサーバーだけです。残念ながら、以前とは異なり、同じリングにハッシュを追加するだけではこの問題を解決できません。完全に新しいリングを追加する必要があり、さらに、機能のすべての組み合わせがそれぞれ固有のリングを必要とする可能性があります！

組み合わせによる重複は、指数関数的な爆発の典型的なレシピです。私たちのケースでは、いくつかの異なる機能があり、$m2^\text{handful} = \text{dozens}m$個の個別のハッシュリングにつながります。したがって、おそらくお気づきの通り、「過剰なメモリ使用量」（場合によっては6GB）は、必要なすべての機能に対応するために生成される膨大な数のハッシュが原因であり、それらはメモリに格納する必要がありました。では、どうすればよいでしょうか？

ストレージの改善

大きな改善の1つは、Zaidoonによるもので、PBRでハッシュを格納するための構造体に関する洞察でした。その構造体は次のようになります。

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

メモリ上では8バイトとして表現され、4バイトはハッシュ（避けられない）、4バイトは別の配列に格納されているサーバーを指すインデックスに使用されます。Zaidoonの洞察は、インデックス用の32ビット整数は無駄であるということでした。なぜなら、PBRは同時に$m2^{16} \approx 65\text{k} m$台以上のサーバーを調整する必要はまずないため、16ビット整数で十分だからです。したがって、上記の構造体を次のように置き換えることができます。

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

残念ながら、Rustではそれほど簡単ではありません。上記のようにインデックスのサイズを変更しても、メモリフットプリントは削減されません。これは、Rustのアライメント規則により、メモリ内の構造体のサイズが、そのフィールドの中で最も大きい（または「最もアラインされた」）フィールドの倍数である必要があるためです。この場合、ハッシュが4バイトで最も大きいため、メモリに格納される場合、Pointのサイズは$mN \times 4m$である必要があり、最小サイズは8バイトになります。

幸いなことに、これにはよく知られた回避策があります。あなたは（つまり私）#[repr(packed)]を使いたくなるかもしれませんが、それは良い理由で議論の的となっています。より安全で読みやすい解決策は、ハッシュとインデックスを生のバイト配列として格納し、ゲッターでアクセスすることです。どちらの方法も同じものにコンパイルされます。

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つだけの場合の標準偏差の数式を提示したことに気づいたかもしれません。サーバーあたり$m k m$個のハッシュがある場合の数式の導出は簡単ではなく、ほとんどの情報源は近似値または漸近限界しか提供しませんが、私たちは違います。私は統計学者ではないかもしれませんが、高校時代に数学の先生（ママ、こんにちは！）がいて、実際の値を知りたかったのです。完全な導出は補足記事にありますが、ここではその結果を示します。

$$m     \text{Exp}_k = \frac{1}{N},     \text{SD}_k=\sqrt{\frac{(k+1)}{N(kN+1)}-\frac{1}{N^2}} m$$

ハッシュ数を増やすことが精度をどのように向上させるかを見るには、変動係数に再び注目する必要があります。

$$m \text{CV}_k=\frac{\text{SD}_k}{\text{Exp}_k}=\sqrt{\frac{N-1}{(N*k+1)}} m$$

$m\text{CV}_km$をプロットすると、「ハッシュを追加するだけ」という考え方（RAMの過剰使用という問題以外）の潜在的な問題が見えてきます。

［画像: BLOG-3083 6.png］

エラーマージンの各ステップダウンには、サーバーあたりのハッシュ数の（ほぼ）1桁の増加が必要であることがわかります。したがって、ハッシュを追加しても改善は少なくなる一方です。私たちは、サーバーのストレージサイズでスケーリングされた160個のハッシュをベースとして使用していることを思い出してください。計算を簡単にするために、サーバーの重み付け係数$m{m_w}m$を625とすると、$m{k = 160\times625 = 100\text{,}000}m$になります。上記のグラフから、最後の90,000個のハッシュは、エラーの削減にわずか0.7%しか貢献していないことがわかります。残念ながら、事態はさらに悪化します。

私の美しい数学からの予測は、ハッシュを連続したリングとして考える場合にのみ機能しますが、実際にはハッシュに32ビット整数を使用しており、衝突の可能性があります。ハッシュ数が増えるにつれて、衝突の確率は驚くほど速く上昇します（誕生日のパラドックスを参照）。理想的なケースでは、すべてのハッシュが関連サーバーが処理するボリュームとリクエストの分布に貢献しますが、衝突は一部の貢献がランダムにドロップされることを意味し、予測不可能なエラーが発生します。32ビットハッシュを使用したシミュレーション結果と予測エラー率を比較すると、2048台のサーバーを持つデータセンターでは、エラー率が上昇することがわかります。サーバーあたり10,000から100,000個のハッシュの間です。

［画像: BLOG-3083 7.png］

最終的に、この認識は少し悪い気分になりますが、RAMを回収するという計画にとっては素晴らしいニュースです！数学的な裏付けが得られたので、顕著なエラーを発生させることなく、生成するハッシュ数を90%削減できると判断しました。そこで、私たちはその目標を設定しました。

オリジンを燃やすことなく移行する

もう1つの問題がありました。ハッシュリングを変更すると、一部のキャッシュ可能なリクエストの送信先が変わります。新しいリングが優れているとしても、ネットワーク全体を一度に変更すると、ほぼすべてのキャッシュコンテンツが無効になります。メモリ最適化が、オリジンへのトラフィックの壊滅的な増加に変わるでしょう。

そのため、単一のグローバルな切り替えにはしませんでした。しばらくの間、PBRはキャッシュ可能なロードバランサーの両方のバージョンをメモリに保持していました。古いketamaリングと新しい小さなリングです。各リクエストは、通常の移行フレームワークを使用して、どちらのリングがバックエンドを選択すべきかを決定しました。これは、ロールアウトの決定がリクエストハッシュごとに安定していることを意味し、クリーンなロールバックパスも提供しました。問題が発生した場合、PBRを再デプロイすることなく、古いリングを介して新しいリクエストを送信できました。

その後、移行を段階的に展開しました。小さな検証場所から始め、徐々に大きなデータセンターグループに移行し、その後、世界の他の地域に進みました。

重要なのは、2つの次元を独立して制御できたことです。新しいリングを使用したトラフィックの量と、そのトラフィックが移動できる場所です。単純なグローバルパーセンテージロールアウトでは、キャッシュの乱れが一度にすべてに広がってしまいます。データセンター単位のロールアウトは、影響範囲を小さく保ち、変更が実際に安全かどうかを判断するのをはるかに容易にしました。

移行中、バックエンド選択トレース、リングバージョンカウンター、PBR接続エラー、プロセスメモリ、起動時間、キャッシュ動作、オリジントラフィックを監視しました。移行が100%に達した後、一時的な古いリングパスを削除し、完了しました！

［画像: BLOG-3083 8.png］

上のグラフは、変更週のPBRが使用したメモリと、その数週間前のデータを比較したものです。差分は、大きな（現在は未使用の）ハッシュリングを持つPBRのバージョンが永久に廃止された日の結果です。差分を見ると、変更によって使用メモリが100TB削減されたという満足のいく結果が得られました！

［画像: BLOG-3083 9.png］

自分で試す

この記事で説明したすべての変更は、現在pingora-ketamaクレートで（現時点では非公式の）カーゴ機能として利用可能です。v2リングは、コンパクト化されたストレージ形式、より高速なソート方法、およびノードあたりの基本ハッシュ数をスケーリングする機能を持っています。これらの変更を行う上での私たちの焦点は、安定性と制御にあり、v1リングはpingora ketamaが常に使用してきたものと同一であり、ライブラリは両方を同時に実行し、リクエストごとにどちらを使用するかを決定できるようにします。

私たちの実際の一貫性ハッシュの変更を試すことに加えて、皆さんも自分のシステムを掘り下げて、「単純」または「明白」な決定の中に、もし数字を調べる意欲があれば、潜在的な利益が隠されていることへのインスピレーションを得てほしいと思います。すべての問題をRustで解決できるわけではないかもしれませんが、数学は普遍的です。