GoogleのHTTP/2コーデックがEnvoyを遅くする

しばらく前に、顧客専用プロキシのEnvoyをルーチンアップグレードしたところ、同じ設定、同じトラフィックにもかかわらず、CPUグラフが約5分の1増加しました。これは原因不明のままカレンダー招待を受けるような種類のグラフだったので、これを機に調査を開始することにしました。バージョンをバイセクトした結果、Envoy v1.34が原因であることが判明しました。このバージョンでEnvoyはデフォルトのHTTP/2コーデックをnghttp2からGoogleのoghttp2に切り替えていました。この問題に気づいたのは我々だけではありませんでした。ユーザーはリリース以来15-25%のレイテンシ回帰を報告しており、v1.37.0でデフォルトはnghttp2に戻されました。ソースコードのコメントには、「パフォーマンスがnghttp2と一致するようになったら」再度試すという旨が記されていました。これで顧客の問題は解決しました。しかし、我々の好奇心は解決しませんでした。なぜパフォーマンスが一致しないのか？HTTP/2コーデックは何に時間を費やしているのか？この記事はその調査結果です。後編では、高速なコーデックをさらに高速化する取り組みについて述べますが、まずは基本から。最高のコーデック、最悪のコーデックEnvoyは、ランタイムフラグの背後に2つのHTTP/2実装を持っていますが、フレイムグラフなしでどちらがどちらであるかを言える人はいませんでした。nghttp2 - 2013年以来HTTP/2のワークホースであり、EnvoyのオリジナルのコーデックであるTatsuhiro Tsujikawa氏のCライブラリ。軽量なC構造体、呼び出し元提供のバッファ。oghttp2 - QUICHEファミリーのGoogleのC++コーデックで、HTTP/3スタックとコードを共有しています。v1.34でEnvoyのデフォルトとなり、その時に回帰報告が始まりました。我々は4つのマイクロアーキテクチャ（Intel Sapphire Rapids、AMD Zen 4、AWS Graviton4、Google Axion）で両方をベンチマークしました。セットアップは簡単です。同じホストのループバック（h2load → Envoy → Go h2cバックエンド、またはEnvoyがdirect_responseをサーブ）、各プロセスは分離された物理コアにピン留めされ、Envoyは--concurrency 1で実行されたため、RPS/コアは純粋なCPU効率の数値です。ユーザーの報告はほぼ正確に再現されました。nghttp2は、ヘッダー負荷の高いプロキシトラフィックにおいて、すべてのホストで15-25% RPS/コア、接続の激しいチャーン下では7-19% oghttp2を上回りました。したがって、回帰は現実的で、移植可能で、コーデック内のどこかに存在します。プロファイルを開く時です。PSAEnvoyを自分でビルドする場合、最適化フラグを確認してください。Envoyの.bazelrcはデフォルトで-c optになっていません。プレーンなbazelビルド//source/exe:envoy-staticは、完全に機能するように見えるfastbuild（デバッグ）バイナリを生成し、同じソースを-c optでビルドしたものと比較してコアあたり15-32倍遅くベンチマークされます。この記事のすべての数値は-c optビルドからのものです。我々はこれを恥ずかしい方法で発見しました。HTTP/2コーデックが1日を過ごす場所フレイムグラフは、両方のコーデックで同じジョブに支配されています。ヘッダーの圧縮解除です。プロキシを通過するすべてのHTTP/2リクエストは、ヘッダーが圧縮された状態で到着し、プロキシはルーティングできる前にそれを解除する必要があります（ホップごとに2回、デコードと再エンコード）。これはリクエストあたり数百バイトの作業ですが、それを掛け合わせると、コアあたり毎秒数万リクエスト、各リクエストに12以上のヘッダーフィールドがあるため、フィールドごとのデコードパスは毎秒数十万回実行されます。圧縮スキームはHPACK（RFC 7541）です。2つのメカニズムが連携しています。最初のメカニズムはインデックス付けです。固定の61エントリの静的テーブルが普遍的なヘッダー（:method: GETは1バイト）をカバーし、両方の側が最近見たヘッダーフィールドの同期された動的テーブルを維持します。そのため、2回目にcookie: session=abc...を送信すると、文字通りキロバイトかかる代わりに1〜2バイトで済みます。2番目のメカニズムは、インデックスヒットしないものすべてを処理します。リテラル文字列はハフマン符号化されます。初めてのヘッダー、ユニークな値（リクエストID、トークン、広告ベンダーがリクエストごとにローテーションするCookie）、そして新しい接続を通過するほとんどすべてがハフマンパスを通ります。エッジにあるプロキシは、多くの新しい接続と多くのユニークな値を目にするため、このパスはホットです。ハフマンコーディングの2分間のツアーDavid A. Huffman 1925-1999 1951年、MITの情報理論コースのRobert Fanoは学生に選択肢を与えました。最終試験を受けるか、彼が提供した問題に関するレポートを書くかです。問題の1つは、ほとんど単純すぎて採点に値しないように思えました。シンボルのセットと各シンボルの出現頻度が与えられた場合、それらに最も効率的なバイナリコードを見つけることです。Fanoは、彼とClaude Shannon（はい、あのClaude Shannon）がこの正確な問題に取り組み、近似値しか得られなかったことには言及しませんでした。David Huffmanという大学院生がそのレポートを選び、数ヶ月間苦労しましたが、彼自身の説明によると、試験勉強を始めようとノートをゴミ箱に捨てたときに解決策が現れたそうです。それ以前の誰もがトップダウンでコードを構築していましたが、シンボルセットを半分に分割していました。Huffmanはそれを反転させました。ボトムアップから始めます。最も珍しい2つのシンボルを取り、それらを1つにマージし、単一のツリーが残るまで繰り返します。珍しいシンボルはツリーの深くに長いコードで配置され、頻繁なシンボルは浅い場所に短いコードで配置されます。そのレポート作成の構築は証明可能に最適です。75年後、それはJPEG、gzip、MP3（子供向けには、これはSpotifyのようなものですが広告なしです）に収められています。そして、インターネット上のすべてのHTTP/2ヘッダーに。Huffmanのボトムアップ構築 - 二都物語FIG. 01各ノードは重みを示しています。小説の文字のどの割合をカバーしているかです。マージは重み順に行われます。まずmとi、次にそのペアとt、最後にeです。葉に沿った0/1ビットがコードになり、太字で表示されています。0101019.4%18.4%30.9%e12.5% 0m2.6% 100i6.8% 101t9.0% 11ハフマンの構築は、A Tale of Two Citiesの実際の文字頻度で重み付けされた4文字アルファベットで行われます。頻繁な文字は短いコードで浅い場所に配置され、珍しい文字は深い場所に配置されます。そして、文字は葉にしか存在しないため、どのコードも他のコードのプレフィックスにはなれません。カーソルを文字に合わせると、ルートからのパスをたどることができます。葉は、上から下へ、デコーダーがそれに到達したときに何をするかを物語っています。HPACKはヘッダーテキスト用に1つの固定ハフマンコードを送信します。その頻度は10年前にキャプチャされた実際のヘッダーコーパスからRFCに焼き付けられているため、接続の両端は常にそれに同意します。小文字と数字はツリーの上部近くにあり、5〜7ビットです。珍しいバイトは30レベル下にあります。典型的なヘッダーテキストは、バイトあたり約6ビットになります。ここで、ツリー構造が無料で提供するプロパティに注目してください。シンボルは葉にしか存在しないため、どのコードも他のコードの始まりにはなれません。したがって、ビットストリームには区切り文字はまったく必要ありません。ビットを読み取って葉へのパスをたどります。それがシンボルです。ルートからやり直します。ストリームはそれ自体の境界を運びます。正しい場所から始めることが前提です。また、コストがどこにあるかも示します。エンコーディングはテーブルルックアップとビット追加です。デコーディングは、そのウォークです。0で左、1で右、葉で発行、ルートに戻る。HPACKのコードの場合、出力バイトあたり平均約6個の依存分岐ロードステップが必要ですが、Cookieの1文字には多くの機械が必要です。実際のヘッダー値のエンコーディング側を次に示します。文字ごとにステップスルーし、コードがバイトにどのようにパックされるかを確認します。バイト境界は無視されます。ハフマン、展開済み - "application/json"FIG. 02accept: "application/json"16文字・88ビット→11バイト・-31%1・各文字は、頻繁な文字には短いコードが割り当てられる、固定のRFC 7541コードにマッピングされます。a000115ビットp1010116ビットp1010116ビットl1010006ビットi001105ビットc001005ビットa000115ビットt010015ビットi001105ビットo001115ビットn1010106ビット/0110006ビットj11101007ビットs010005ビットo001115ビットn1010106ビット2・コードは1つのビットストリームに連結され、バイトに分割されます。88ビットはちょうど11バイトです。この文字列にはEOSパディングは必要ありません。000111010x1d011101010x75110100000xd0011000100x62000011010x0d001001100x26001111010x3d010011000x4c011101000x74010000010x41111010100xea←→文字 1 / 16"a"→000115ビット固定RFC 7541コードの下の1つのヘッダー値: 16文字、88ビット、ワイヤー上11バイト。矢印（キーボードでも操作可能）でステップするか、何かをホバーしてください。コードはバイト境界を無視するため、1バイトに2〜3文字の一部が含まれることがよくあります。まさにデコードが興味深い部分になる理由です。nghttp2は、2014年からずっと、はるかに優れたことを行っています。それはd