Cloudflareは、Pingora Backend Router（PBR）サービスのリクエスト分散アルゴリズムの一部を再設計した結果、グローバルネットワーク全体で100テラバイトを超えるRAMを取り戻すことに成功しました。この改善は、ハッシュポイントの表現を圧縮し、統計分析に基づいてポイント数を減らし、キャッシュの安定性とオリジンサーバーへのトラフィックを維持する段階的な移行を実施したことによるものです。
リクエスト分散の問題
Cloudflareはconsistent hashingを実装するためにpingora-ketamaライブラリを使用しています。これは、キャッシュ可能なリクエストを可能な限り同じサーバーへ送る方法です。これにより、データセンター内にファイルのコピーを1つだけ保持し、安定した経路でアクセスできるようになります。
しかし、サーバーごとにハッシュポイントを1つだけ使用すると、ハッシュリング上でサーバーが所有する範囲の大きさに大きなばらつきが生じ、結果としてワークロードにも偏りが生じる可能性があります。そのためPingoraは、各サーバーに対して多数の仮想ハッシュポイントを使用し、ストレージ容量に関連付けられた重みも設定しています。また、異なる特性や制約を持つグループごとに個別のリングも作成されます。これらのリングが積み重なったことで、場合によっては1プロセスあたり最大6ギガバイトを消費していました。
データ表現の改善とハッシュ数の削減
リング上の各ポイントを表す要素は、32ビットのハッシュ値と、サーバーへの32ビットのインデックスで構成され、メモリ上で8バイトを占有していました。Cloudflareのチームは、サービスが同時に調整するサーバー数は約6万5,000台を超えないため、インデックスは実際には16ビットを超える必要がないと判断しました。
ただし、Rustのアライメント規則により、インデックスの型を小さくするだけでは不十分でした。構造体のサイズは依然として8バイトのままになるためです。そこでCloudflareは、値とインデックスを6バイトの生配列に格納し、それぞれにアクセスする関数を用意しました。この変更により、ハッシュ関連のメモリ消費量は25%削減されました。
より大きな効果をもたらしたのは、ハッシュ数の見直しでした。サービスでは、サーバーあたりの基本値として160ポイントを使用し、それをストレージ容量に関連付けられたサーバーの重みに乗じていました。分析の結果、ハッシュ数を大幅に増やしても誤差の余裕に対する改善は逓減することが分かりました。Cloudflareが検討した例では、最後の9万個のハッシュを追加しても、誤差の低下は約0.7%にとどまりました。
また、32ビットのハッシュ値を使用すると、ポイント数が増えるほど衝突が起こりやすくなり、分散に予期しない誤差が加わる可能性があります。計算とシミュレーションに基づき、Cloudflareは目立った誤差の増加なしに、サーバーあたりのハッシュ数を90%削減しました。これが最終的な節約に貢献しました。
実際には何が変わるのか
ネットワーク全体でハッシュリングを一度に切り替えるのは安全な選択肢ではありませんでした。リクエストが再分散され、キャッシュの有効性が実質的に大きく失われ、オリジンサーバーへのトラフィックが増加する可能性があったためです。そこでPBRは一時的に旧リングと新リングの両方をメモリに保持し、リクエストごとにどちらかを選択しました。これにより、明確なロールバック経路が確保されました。
移行は段階的に実施され、まず小規模な検証サイトから開始し、その後、より大規模なデータセンターへと進められました。また、新しいリングを使用するリクエストの割合を制御する仕組みと、参加を許可するデータセンターを指定する仕組みを分離しました。Cloudflareは、旧経路を削除する前に、サーバー選択の影響、リングのバージョン、接続エラー、メモリ消費量、起動時間、キャッシュの挙動、オリジンサーバーへのトラフィックを監視しました。
エンジニアリング上の意義
この取り組みは、データ構造内のフィールドサイズの選択や、適切なハッシュポイント数の決定といった低レベルの最適化が、数千台のサーバーを擁するネットワーク全体に適用されると、大きな効果へと拡大し得ることを示しています。同時に、この結果は、メモリ削減があらゆるシステムで安全だという意味ではありません。分散の精度、衝突の可能性、サーバーの重み、機能上の制約、移行の実装方法など、変更前に測定すべき要因があります。
この変更は現在、pingora-ketamaパッケージで、現時点では公開されていないCargo機能を通じて利用できます。v2では、圧縮ストレージ形式、より高速なソート方法、基本ハッシュ数を設定する機能をサポートしています。また、v1も引き続き維持され、2つのリングを同時に稼働させ、リクエスト単位で判断することも可能です。