Cloudflareは、ここで何年も働いた後でも現実とは思えないほど大規模に運営されています。世界中に数千台のサーバーがあり、ペタバイト級のRAMと数百万のCPUコアを備え、そのすべてが限界まで活用されています。これらのリソースは広大に感じられますが、それでも有限であり、すべてのサービスをすべてのノードで実行する必要がある場合、無駄なスペースの余地はありません。この規模では、小さな改善が大幅に増幅されるため、一度に1%の改善でも祝う価値があります。そして、いくつかの調整は合計するとさらに大きくなります。この記事では、単一のアルゴリズムへの小さな変更が、Pingoraベースのサービスの1つのメモリフットプリントを大幅に削減した方法を見ていきます。これにより、DNSチームが先月削減できた100TBのメモリに加えて、世界で100TB以上のRAMを回収することができました。

無駄にしない チーム間で公平なリソース共有を維持することは容易ではありません。特に大規模な組織ではそうです。Cloudflareがバランスを保つ方法の1つは、素晴らしいPerformanceチームの絶え間ない努力によるものです。この話は、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よりも著しく大きいことに注意してください。これは問題です。なぜなら、サーバーが処理するリクエストの割合は、数直線上でのその範囲のサイズに比例するからです。理想的には、各サーバーが等しいサイズを持つことを保証したいのですが、ハッシュは本質的に乱数であるため、私たちは...