trie-hardの良き日: コンピューティングを1%節約
(blog.cloudflare.com)- Cloudflareは、毎秒平均6,000万件超のHTTPリクエストを処理するネットワークで、Rust製プロキシ Pingora のCPU使用量を削減するため、オープンソースのRust crate trie-hard を公開した
- ボトルネックは
pingora-originのclear_internal_headers関数で、Cloudflareを離れる非キャッシュリクエストから内部ルーティング・計測・最適化用ヘッダーを削除し、毎秒3,500万リクエストの経路で実行されていた - 従来実装では内部ヘッダー100個以上の削除を各リクエストごとに試みており、平均 3.65µs かかって、
pingora-origin全体のCPU時間の1.71%、すなわち毎秒4万 compute-seconds のうち680 CPUコア相当を消費していた - 実際のリクエストヘッダーを先に走査する方式は平均 1.53µs で2.39倍高速化したが、全体CPU削減は理論上0.993%にとどまり、より良い検索データ構造が必要だった
- 新しい trie 実装は平均実行時間を 0.93µs にまで下げ、2024年7月から本番環境で動かしたサンプリングでも
clear_internal_headersの実際のCPU使用率は0.34%まで低下した
Cloudflareが削減しようとしたコスト
- Cloudflareのグローバルネットワークは平均して毎秒 6,000万件超 のHTTPリクエストを処理している
- 今回の最適化は、Rust製プロキシサービスの中核である Pingora と、その上で動作する本番サービス
pingora-originから始まった pingora-originは、ユーザーの非キャッシュリクエストを実際の宛先サーバーである origin へ送る最後の段階を担う- このサービスは、リクエストがCloudflareインフラを離れる前に、内部ルーティング、計測、最適化に使われた情報をヘッダーから削除する必要がある
- 執筆時点で、世界全体で
pingora-originを離れるリクエストは毎秒 3,500万件 に達する
ボトルネック関数: clear_internal_headers
- 問題の関数は、すべてのリクエストで実行される非常にホットな経路にある
// PERF: heavy function: 1.7% CPU time
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
INTERNAL_HEADERS.iter().for_each(|h| {
request_header.remove_header(h);
});
}
- この小さな関数1つだけで
pingora-origin全体のCPU時間の 1.7%以上 を使っていた pingora-originの総CPU時間は毎秒 40,000 compute-seconds で、飽和したCPUコア4万個がこのサービスだけを実行しているのと同規模である- そのうち1.7%、すなわち約 680 CPUコア が
clear_internal_headersの評価だけに使われている計算になる
基準測定と最初の改善
- 性能測定には Rust crate criterion を使用した
- Criterionは複数回の隔離実行を集計し、Rustコードの時間を ナノ秒単位 で測定し、時間経過による性能改善・退行のフィードバックも提供する
- ベンチマーク入力には、内部ヘッダーと非内部ヘッダーが均等に分布するよう合成した大量のリクエスト集合を用いた
- 従来の
clear_internal_headersの平均実行時間は 3.65µs と測定された -
参照方向を反転する
- 従来コードは内部ヘッダー一覧の各項目に対して
request_header.remove_header(h)を実行するため、内部ヘッダーが100個以上あると各リクエストで100回以上評価していた - 平均的なリクエストのヘッダー数は100個よりかなり少ない 10〜30個 程度なので、実際のリクエストヘッダーを走査しながら内部ヘッダー集合を検索する方が読み取り回数を減らせる
- Rustの
http::HeaderMapにはまだretainがないため、削除すべき内部ヘッダーを別の段階で集めてから削除する必要がある - この変更だけで平均実行時間は 3.65µs から 1.53µs へ下がり、2.39倍高速になった
- 理論上、全体CPU使用率は1.71%から0.717%へ低下し、削減幅は 0.993% となる
- 従来コードは内部ヘッダー一覧の各項目に対して
より良い検索データ構造の探索
- 参照方向を変えたことで、静的な内部ヘッダー一覧をどのデータ構造に保存するか選べるようになった
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
let to_remove = request_header
.headers
.keys()
.filter_map(|name| INTERNAL_HEADER_SET.get(name))
.collect::<Vec<_>>();
to_remove.into_iter().for_each(|k| {
request_header.remove_header(k);
});
}
- 最初の試みは
std::HashMapだったが、文字列キーのハッシュはすべてのバイトを読む必要があるため、テーブルサイズに対しては定数時間でも キー長 L に対しては線形時間になる - 目標は、キー長に対して O(L) より良い読み取り挙動を示すデータ構造を見つけることだった
-
検討した代替案
BTreeSetのようなソート済み集合は比較ベースの検索を使うため、キー長に対して O(log(L)) の挙動を提供するが、集合サイズに対しても対数時間がかかる- 高速なソート済み集合である FST も、ベンチマークでは標準のハッシュマップより約 50ns 遅かった
- パーサーや正規表現のような状態機械は、入力を1単位ずつ受け取り、各段階で評価を続けるかどうかを判断するため、一致しない文字列を素早く識別できる
- 内部ヘッダーはリクエストあたり平均 1〜2個 にすぎず、否定例が大半という状況によく合っている
- 正規表現を使った
clear_internal_headersの実装は、ハッシュマップベースの解法より約 2倍 長くかかったが、生の速度で知られるツールではないことを考えれば高速な結果だった
trie が適している理由
- trie は、既知の文字列集合に対する接頭辞検索やオートコンプリートでよく使われる 木構造データ構造 である
- trie の各ノードは初期文字列集合で見つかる 部分文字列 を表し、ノード間の接続は特定の接頭辞の後に続きうる文字を表す
- ルートノードから始めて、あり得る先頭文字から検索空間を狭められるため、含まれない文字列を素早く除外できる
- trie の読み取りは不一致ケースに対して O(log(L)) の挙動を提供するが、一致ケースは依然として O(L) である
- リクエストヘッダーの90%以上は内部ヘッダーではないため、不一致ケースが多いこのユースケースに適している
-
既存 trie 実装の限界
- crates.io にある複数の trie 実装をベンチマークしたが、結果は期待に届かなかった
- ほとんどの trie は、キーボード入力に応じるオートコンプリートのような用途向けに作られており、毎秒数千万リクエストのホットパス最適化は優先事項ではない
- 見つかった中で最速の既存実装は radix_trie だったが、それでもなおハッシュマップより 1µs 遅かった
- 最終的に、このユースケース向けに新しい trie 実装を書くことになった
trie-hard と本番環境での結果
-
Cloudflareは新しいオープンソース Rust crate trie-hard を公開した
-
trie-hardは、符号なし整数のビットにノード関係を保存し、ツリー全体を 連続したメモリブロック に保持することで高速化している -
ベンチマークでは、
trie-hardはclear_internal_headersの平均実行時間を 0.93µs にまで下げた -
予測されるCPU使用率は 0.43% で、従来の1.71%と比べて
pingora-origin全体のコンピューティング使用量を 1.28% 削減する結果となった -
実際のサンプリング結果
trie-hardは2024年7月から本番環境で稼働している- 性能測定は、時間に沿ったスタックトレースの統計サンプリングによって収集された
- 特定の関数を含むサンプル比率から、その関数のCPU使用率を推定した
- 本番サンプリングの結果は、ローカルベンチマークの予測値とおおむね近かった
実装 clear_internal_headersを含むスタックトレースサンプル実際のCPU使用率 予測CPU使用率 Original 19 / 1111 1.71% n/a Hashmap 9 / 1103 0.82% 0.72% trie-hard 4 / 1171 0.34% 0.43%
運用視点での結論
- 新しいデータ構造を書くことより先に、コードのどこがどれだけ遅いのかを把握する必要がある
- flame graph、プロファイリング、ベンチマークツールを活用すれば、マイクロ秒単位の関数でも意味のある削減を見つけられる
- すでに非常に短い処理を最適化するのは些細に見えるかもしれないが、毎秒数千万リクエスト規模では小さな改善が積み重なり、全体のコンピューティング使用量を減らせる
1件のコメント
Hacker News の意見
Cloudflare が内部ヘッダーを保存して削除する方法を大ざっぱに推測しろと言われたら、別の辞書やデータ構造、内部メタデータをすべて入れる単一ヘッダー、内部／外部をプレフィックスで区別する方式、
CFIntのようなプレフィックスを思い浮かべたと思う特定のリストにあるヘッダー名を内部ヘッダーと見なす方式は思いつかなかったはず。他の誰かが同じ名前を使ったらどうなるのか、削除漏れが起きたらどうなるのか、同時に動くプログラム同士でリストが違っていたらどうなるのか、
Connectionヘッダーが Cloudflare の内部ヘッダーを指していたらどうなるのか、差集合アルゴリズムが遅かったらどうなるのか、といった疑問が湧くWeb はすでに、うんざりするほど曖昧なインバンド信号とヘッダー命名でいっぱいなのに、Cloudflare 規模の会社が内部でこんなに面倒でエラーを起こしやすい仕組みを使っているのは奇妙に感じる
cf-cache-status関連の目立つバグのように、あらゆる悪いことが起こり得たという点エッジプロキシで内部ヘッダーを双方向に削除することも含まれており、インバウンドでもそうしていた
リスト方式には欠点があるが、利点も多い。このアプローチの潜在的な欠陥を指摘するとき、Cloudflare 規模で生じた歴史や難しさが無視されがちに見える。列挙リストは最も単純で柔軟な方式であり、ヘッダーキー構造について事前合意も不要。Cloudflare のチーム数や技術買収の可能性などを考えると、この点は重要だったはず
事前に埋めておけば、実質的にこれらのアイデアを組み合わせつつ、各リクエストの内部ヘッダー数を固定することになる。その時点では、生成順を保持する連結ハッシュテーブルを使い、クライアントへ返す最終リストから先頭の N 個だけ削除すればよい
UTF-8 文字をビットマスクにマッピングする効果を少し考えてみたが、最初はあまり賢くなさそうに見えた。ところが 32 ビットなら
a-zと特殊文字 6 個を収められ、64 ビットなら大文字A-Zと特殊文字 6 個をさらに収められることに気づいたHTTP ヘッダーには十分な空間で、いくつかの整数をマスクして比較するだけなので、非常に高速なマッチングアルゴリズムになる。どの文字がどのビットに対応するかも、256 ワードのテーブルを 1 回参照するだけで済む
筆者が見落としている点は、この手法が技術的にはブルームフィルターだということ。こうしたものが興味深いのは、現在よりコンピューティング資源がはるかに限られていた時代、この場合は 1970 年に生まれた最適化なのに、今でも現実世界の片隅で同じ古い最適化を使っているから
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardとブルームフィルターの間には大きな違いがある。ブルームフィルターは確率的で、ハッシュを使う。まれな偽陽性を許容する代わりに偽陰性があってはならない場合には向いているが、ここで必要なのはそれではない。ここでは正確性が必要で、ハッシュ自体が克服すべき段階になっているむしろこれは、TeX でハイフネーション辞書を保存するために使われた Liang アルゴリズムの改良版または変種に近い。論文では Bloom のアルゴリズムを “superimposed coding” と呼んで扱っており、メモリが最も貴重な資源だった時代を強く思い起こさせる。気に入ると思う ^_^
https://tug.org/docs/liang/liang-thesis.pdf
利益を証明するために提示されたデータは、実際にはそれを示すには検出力が不足している。標本が十分ではない
R でごく単純に分析すると
prop.test(c(9, 4), c(1103,1171))で、連続性補正を適用した二つの比率の同一性検定では p 値は 0.222 になるp 値 0.22 は魔法の 0.05 より低くなく、95% 信頼区間は trie が実際には少し悪い可能性も示唆している
事前分析を見ると trie のほうが良さそうで、弱い証拠もあるが、標本をずっと多く取ってどれほど良いのかを確信したほうがよい
性能を分析する目的で比較回数をビッグオー記法で説明するのはぎこちない。比較は 1 サイクル程度で、命令レベル並列性や SIMD により 1 サイクルで複数個も可能
実際のボトルネックであり遅さの原因はメモリ。メモリにアクセスするには数千サイクルかかり、TLB ウォークや OS 割り込みが必要なら数万から数十万サイクルにまでなり得る。ビッグオーを使いたいなら、キャッシュミス回数を見積もるのに使うべき
自分ならカスタムの完全ハッシュ関数と Phil Bagwell の
popcountトリックを使うと思う。メモリを何度も参照する他の解法より速いはずCPU は速く、メモリは遅い
データ構造の最適化にそこまで詳しいわけではないが、特に検索対象のテーブルが静的であることを考えると、ハッシュテーブルを早々に除外したのは意外だった。特別に最適化したハッシュテーブルが彼らのトライ実装より速くならないとは考えにくい
この用途では、それがハッシュでは追いつけない利点になる。残りの技術は、トライの定数係数を十分に削って、この初期の利点が実際の性能で報われるようにする作業
std::collections::HashMapより速い FxHashMap がある: https://github.com/rust-lang/rustc-hash静的な項目が約100個なら o1hash も動きそう: https://github.com/rurban/smhasher/blob/master/o1hash.h
この記事は凝ったデータ構造で
to_remove集合を作り、その後それを走査して基本のヘッダーマップから削除しているremove_headerの呼び出しはこのコードのように見える: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576この関数は別の2つのデータ構造で
.remove()を呼び、どちらも最終的にこの巨大なコードに降りていく: https://docs.rs/http/latest/src/http/header/map.rs.html#1550ついにトライが出てくるブログ記事が出たね。トライの LeetCode 問題は無駄ではなかった ;)
それでも、頻繁に取り出す道具でないのは確か
Go 用のユーザーエージェントパーサー: https://github.com/medama-io/go-useragent
たいていこの種の問題は大量の正規表現パースに依存するので、もう少し新しいアプローチを試せてよかった
マッチする項目集合が静的なら、完全ハッシュテーブルを試したのか気になる。数回の算術演算の後に文字列比較1回まで減らせるはずで、トライとどう比較されるのか興味深い
理論的には正規表現を使えば状態機械でマッチするので、トライと同様に最悪 O(k) の性能になるはず。しかし自分の理解では、正規表現ライブラリは実際の状態機械を作るよりバックトラッキングを使うため、性能はもはや O(k) ではない
既存の高性能な状態機械ベースの正規表現ライブラリを見つけられなかったというのは驚きではある。トライと似た性能になるはずだが、実際にはメモリアクセスパターンや特定の算術演算の性能のような要素がより深く影響するので、推測は難しい
ごく小さなブルームフィルターは試したのだろうか。ヘッダーキーを高速に畳み込みのように処理してブルームフィルターと照合すれば、数サイクルのコストでほとんどの場合トライの走査を丸ごと避けられそう
SIMD、組み込み CRC 命令、256ビットのブルームフィルターサイズといった選択肢もありそう
もっと単純なアプローチにも価値があるかもしれない。トライノードのヒット/ミス頻度を分析すれば、先頭文字より失敗率が高い特定の文字位置を見つけられる可能性がある。そうした特殊な位置を先に検査すれば、さらに速くなるかもしれない。もちろん、ヘッダーデータが本質的にかなり規則的であるという前提が必要
私の考えはこうです。まず、これはやる価値のあることなのか？ CPU コア約500個を節約したように見えますが、これが実際のコアなのか、ハイパースレッドのコアまで含めたものなのかは分かりません
Cloudflare のコストは分かりませんが、サーバー数台分に相当し、削減額もおそらく年間数万ドル程度だと思います。無視できるほどではありませんが、エンジニアリング投資に対してプラスの ROI を期待できるかは分かりません
次に、ここまで細かく踏み込むのであれば、デシリアライズ段階にフィルターを入れて、そもそもヘッダーが生成されないようにする方法は検討したのか気になります
電力削減も続き、炭素排出も減ります
ヘッダーを AI で分析してサンダルを売りつけようとするような馬鹿げたことより、何かを1% 高速化しようとする企業を見るほうがいいです
その価値は100万ドルかもしれません