数学（と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ビット出力を数値線として表現します。 次に、サーバーA、B、Cとタスクt-zのセットがあるとします。サーバーのIPアドレスやタスクのキャッシュキーなどの代表値のハッシュに基づいて、それぞれを数値線上にマッピングできます。 タスクをサーバーに割り当てることは、各タスクの左側にある最初のサーバーを見つけることになります。これを視覚的に表現するために、各サーバーに関連付けられるハッシュの領域を色分けします。サーバーCがカバーする範囲が最初に戻ってラップアラウンドしていることに注意してください。これが、ハッシュが円環上に存在するという考え方の由来です。 そして、それがすべてです。基本的なレベルでは、一貫性ハッシュはこれほど単純です。しかし、改善の余地があることに気づくのに時間はかかりません。例で示したサーバーAがカバーする範囲が、BやCの範囲よりも大幅に大きいことに注目してください。これは問題です。なぜなら、サーバーが処理するリクエストの割合は、数値線上のその範囲のサイズに比例するからです。理想的には、各サーバーが均等なサイズを持つことを保証したいのですが、ハッシュは本質的にランダムな数値であるため、統計的な観点から領域のサイズについて話す必要があります。 😨数学と結果 まず、パニックにならないでください。私はあなたに嘘をつくつもりはないし、初日の確率の授業の範囲内に留まることを約束します。統計分布について話すとき、不確実性を役立つ方法で定量化するのに役立つ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$の場合、$ ext{CV} \approx 99\% m$となります。これは、一部のサーバーが本来より99%も多くの作業（リクエストの2倍を処理）を行う可能性があり、他のサーバーはほとんど何もしていない可能性があることを意味します！サーバーの負荷がどれだけ均等になるかを一貫性ハッシュを使用して予測する方法がわかったので、改善に取り掛かることができます。 ハッシュを追加するとどうなるか？ 一貫性ハッシュの単純さは諸刃の剣です。すべてが同じ数値線上の容易に比較可能なハッシュに変換されるため、理解しやすく実装しやすいですが、システムへのあらゆる改善もその数値線に関連付けられる必要があります。これは、一貫性ハッシュの問題に対する解決策は、より多くのハッシュしかないことを意味します。それは、すべての問題が釘に見える万能の金槌というよりは、すべての道具を金槌に変えてしまう金色の釘のようなものです。 負荷分散の不均衡の問題を解決するために、各サーバーを表すハッシュを1つではなく複数追加できます。これの背後にある数学は後ほど説明しますが、個々の範囲は大きな標準偏差を持つ一方で、それらを複数組み合わせると合計サイズが均等になるということは、直感的に理解できるはずです。上記の図の3サーバーの例で、各サーバーにランダムにさらに2つのハッシュを追加すると、各サーバーのワークロードのバランスが取れるようになります。これは明らかに作為的な例です。システムのランダムな性質により、サーバーあたり2つの追加ハッシュを追加することで得られる改善の保証はありませんが、これらのハッシュセグメントをより多く組み合わせることで、より均一な分布が得られるということは直感的に理解できるはずです。合計の各セグメントには、他のセグメントをバランスさせる可能性があります。1つは短すぎるかもしれません。1つは長すぎるかもしれません。これは基本的に、大数の法則が示すべきことです… 明らかな問題は、それが大きな数にしか機能しないということです。NGINXでは、サーバーあたりのハッシュの基本数は160にハードコードされており、Pingoraはデフォルトで同じ値を使用しています。ここでは数学的な説明は省略しますが、100サーバーの例に戻ると、1つだけではなく、サーバーあたり160個のハッシュを使用すると、変動係数（エラーマージンと考えることができます）は約99%から約8%に低下し、大幅な改善となります。 さらにハッシュを追加するとどうなるか？ サーバーあたりのハッシュ数を定数だけ増やすと、サーバーあたりのワークロードの分布を改善できることがわかりましたが、w