CDNやDDoS防御サービスなどを展開するCloudflareは、平均で毎秒6000万件を超える大量のHTTPリクエストを処理しています。そうしたHTTPリクエストの処理において、「処理を見直すことでCPU使用率を1％以上削減できた」と公式ブログに投稿しました。

A good day to trie-hard: saving compute 1% at a time

https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/



Cloudflareのサービスで使用されているPingoraフレームワークにおいて、ユーザーのリクエストを実際の宛先サーバーである「origin」に送信する際にはCloudflareの内部だけで使用されるヘッダーを削除する必要があります。

ヘッダーを削除するため、Cloudflareは外部宛の全てのリクエストに対し下記の処理を行っていたとのこと。下記の「clear_internal_headers」関数は外部宛のリクエストを処理する「pingora-origin」サービスの合計CPU時間の1.7％以上を消費していました。外部宛のリクエストは毎秒3500万件発生しており、影響が大きいためエンジニアチームはこの関数の最適化に取り組むことにしたそうです。



エンジニアチームは最初にCriterion.rsという評価ライブラリを使用して関数の平均実行時間を計測し、手法ごとの実行時間の違いを視覚化できるようにしました。最適化前の段階では平均実行時間が3.65µsだったとのこと。

当初のコードでは、内部ヘッダーの一覧表を元に全てのヘッダーを順番に処理しており、「ヘッダーを見つけて削除する」という処理が100回以上行われていました。



エンジニアチームは、ほとんどの場合各リクエストには10件から30件程度しか内部ヘッダーが使用されていないことに着目。「リクエストの各ヘッダーを内部ヘッダーに照らし合わせて削除する」という処理に変更することで処理時間を1.53µsまで削減できたとのこと。これだけで関数の速度が2.39倍になりました。



さらに、「各ヘッダーを内部ヘッダーに照らし合わせる」という部分の高速化に着手。O-記法を用いて表記する際、ハッシュテーブルの読み取り時間はO(1)のためこれ以上高速化の余地はないように見えますが、実際にはキーの長さをLとしてハッシュの計算にO(L)の時間がかかります。

エンジニアチームは検討を重ねた結果、トライ構造を採用することにしました。トライ構造は文字列の先頭から順に一致を探す構造で、単語リストにない文字列の探索を比較的高速に終了できるという特徴があります。例えば単語リストが「and」「ant」「dad」「do」「dot」で構築されている場合、「a」や「d」で始まっていない単語はすぐに「単語リストにない」と判定することができます。



トライ構造では検索空間を素早く縮小することができるため、単語リストに一致しない場合の検索時間をO(log(L))に抑えることが可能です。単語リストに一致する場合の検索時間はO(L)でハッシュの計算と変わらないものの、リクエストのヘッダーのうち内部ヘッダーに一致するヘッダーは10％以下のため高速化できるとのこと。

Cloudflareのユースケースにあうようにトライ構造を実装するなどの努力の結果、当初1.71％だったclear_internal_headers関数のCPU使用率を0.34％まで削減できたと述べられています。



ブログ記事は、「この記事の本当の結論は、最適化の方法よりもコードがどこでどれだけ遅くなっているのかを知る方が重要ということだ」「少し時間を取ってプロファイリングやベンチマークツールを活用してください」と締めくくられています。