Cloudflare、サーバーハッシュを9割削減しRAMを100TB節約

Cloudflareが再び約100TBのメモリを節約した。今回の対象はハッシュマッピングのアルゴリズムだ。同社の主要な事業の一つがデータのキャッシュ、すなわち配信元サイトへ取りに行く代わりにURLをメモリやディスクから直接返す仕組みであり、任意のURLを多数のキャッシュサーバーのどれかに割り当てる処理には、Ketamaアルゴリズムを用いた自社のオープンソース実装を使っている。

仕組み自体は素朴だ。入ってきたURLをハッシュ化し、得られた数値をもとに配信先のサーバーを決める。ただし単純に順番で割り当てると、同じURLが常に同じサーバーへ行かなくなる。そこでサーバー側もIPアドレスや名前からハッシュ値を作り、URLのハッシュ値と数値的に近いものを突き合わせる。URLのハッシュ値の分布は実質的にランダムになるため、これで均等に振り分けられる。

問題は次にある。4台のサーバーが25％ずつ処理している状態で1台が落ちると、その分がハッシュ空間上で隣のサーバーに丸ごと寄ってしまい、1台だけが過負荷になる。この偏りを避けるために、1台のサーバーにつき多数のハッシュを作り、ランダムに散らして配置する。こうすれば1台が落ちても残りへ均等に分配される。ただしこの手法はメモリを食う。さらに、大きなサーバーにより多くのリクエストを割り当てる重み付けの階層や、コンテンツ規制や地域構成の都合ですべてのサーバーがすべてのリクエストを処理できるわけではないという事情が重なり、Cloudflareではマシンあたり最大10万個ものサーバーハッシュを抱えるまでに膨らんでいた。

見直しのきっかけは、代数と基礎的な統計による検討だった。エンジニアたちは、10万という数が収穫逓減の点をはるかに超えていると結論づけた。1万個を超えた先では、1桁増やしてもエラー率はほとんど下がらない。つまり10分の1で実用上ほぼ同じ結果が得られる。あわせて、Rustのデータ構造を工夫してハッシュとサーバーの対応表を1エントリあたり2バイト削った。2バイトと聞くと些細に思えるが、数十億件規模になると効いてくる。

合計で節約できたメモリは約100TBに達した。展開の手順も慎重で、この新方式は既存コードを置き換える形ではなく「v2」として追加された。何か壊れた場合に元のアルゴリズムへ即座に戻せるようにするためだ。

この事例が示すのは、性能改善の余地が必ずしも新しいアルゴリズムの発明にあるわけではない、という点だ。仮想ノード数のようなパラメータは、導入時に安全側へ大きく取ったまま誰も見直さないことが多い。実際の分散品質を測って収穫逓減の点を特定すれば、桁単位で削れる場合がある。