GoogleのHTTP/2コーデックがEnvoyを遅くする
Google's HTTP/2 codec slows Envoy (apoxy.dev)
要約
EnvoyがデフォルトのHTTP/2コーデックをnghttp2からGoogleのoghttp2に変更したことで、CPU使用率が約20%増加し、レイテンシが15-25%悪化するという問題が報告されました。調査の結果、このパフォーマンス低下の主な原因はHTTP/2ヘッダーの圧縮解除、特にHPACKにおけるリテラル文字列のハフマン符号化処理であることが判明しました。筆者は、このボトルネックの特定と、将来的なパフォーマンス改善に向けた取り組みについて解説しています。
全文翻訳
A Tale of Two HTTP/2 Codecs
EngineeringAug 4, 20268 min read
Envoyのバージョンアップが顧客のHTTP/2スループットを20%低下させる原因となった。その原因は、2つのコーデック、大量のフレイムグラフ、そしてすべてのヘッダーに隠されたハフマンコードへとたどる。
[画像: Dmitry Ilyevsky]
Dmitry Ilyevsky
Co-founder & CTO
先日、顧客専用プロキシのルーチンなEnvoyアップグレードを実施した。設定もトラフィックも同じだったにもかかわらず、CPUグラフは約5分の1増加した。これは、議題なしのカレンダー招待を受けるような種類のグラフだったので、これを機に調査を開始することにした。
バージョンをビスケット(bisect)していくとEnvoy v1.34にたどり着いた。このバージョンでEnvoyはデフォルトのHTTP/2コーデックをnghttp2からGoogleのoghttp2に変更していた。我々が最初に気づいたわけではない。ユーザーはすでにそのリリース以降、15–25%のレイテンシ回帰を報告しており、v1.37.0では最終的にデフォルトを戻すことになった。ソースコードのコメントには、「パフォーマンスがnghttp2と一致するようになったら」再度試みると書かれていた。それが顧客の問題を解決した。しかし、我々の好奇心は解決されなかった。なぜパフォーマンスが一致しないのか?HTTP/2コーデックは何に時間を費やしているのか?
この記事はその調査についてである。パフォーマンスの良いコーデックをさらに高速化する続編があるが、まずは基本から。
最良のコーデック、最悪のコーデック
Envoyには、ランタイムフラグの背後に2つのHTTP/2実装があるが、どちらがどちらかはフレイムグラフなしでは誰も言えないだろう。
- nghttp2 - Tatsuhiro Tsujikawa氏によるCライブラリ。2013年以来HTTP/2のワークホースであり、Envoyのオリジナルのコーデック。軽量なC構造体、呼び出し元提供のバッファ。
- oghttp2 - GoogleのC++コーデックで、QUICHEファミリーの一部であり、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はoghttp2よりも15–25% RPS/コアで優れており、すべてのホストで同様の結果だった。また、接続の急激な変動下では7–19%優れていた。したがって、この回帰は現実的で、ポータブルであり、コーデック内に存在する。プロファイルをオープンする時が来た。
PSA
Envoyを自分でビルドする場合、最適化フラグを確認してください。 Envoyの.bazelrcはデフォルトで-c optになっていない。単なるbazel build //source/exe:envoy-staticは、同じソースを-c optでビルドした場合と比較して、15–32倍遅いfastbuild(デバッグ)バイナリを生成する。この記事のすべての数値は-c optビルドからのものである。我々はこれを恥ずかしい思いをして発見した。
HTTP/2コーデックが時間を費やす場所
両コーデックのフレイムグラフは同じジョブに支配されている。ヘッダーの圧縮解除だ。プロキシを通過するすべてのHTTP/2リクエストは、ヘッダーが圧縮された状態で到着し、プロキシはルーティングする前にそれを解除する必要がある。これはホップごとに2回(デコードと再エンコード)行われる。リクエストあたり数百バイトの作業だが、これを掛け合わせると、コアあたり毎秒数万リクエスト、ヘッダーフィールドが12個以上あると、フィールドごとのデコードパスは毎秒数十万回実行されることになる。
圧縮スキームはHPACK (RFC 7541)である。2つのメカニズムが連携して機能する。1つ目はインデックス付け:固定の61エントリの静的テーブルは普遍的なヘッダー(:method: GETは1バイト)をカバーし、両サイドは最近見たヘッダーフィールドの同期された動的テーブルを維持する。これにより、2回目にcookie: session=abc...を送信する際には、文字通りキロバイトかかる代わりに1〜2バイトで済む。2つ目のメカニズムは、インデックスヒットしないすべてのものを処理する。リテラル文字列はハフマン符号化される。初めてのヘッダー、ユニークな値(リクエストID、トークン、広告ベンダーがリクエストごとにローテーションするクッキー)、そして新しい接続で通過するほとんどのものはハフマンパスを通る。エッジにあるプロキシは、多くの新しい接続と多くのユニークな値を見るため、このパスはホットになる。
ハフマン符号化の2分間ツアー
1951年、Robert FanoはMITの情報理論コースの学生に選択肢を提示した。最終試験を受けるか、彼が提供した問題に関するレポートを書くかである。問題の1つは、グレードに値するとは思えないほど単純に見えた。与えられたシンボルのセットとその出現頻度から、それらに最も効率的なバイナリコードを見つけるというものだ。Fanoは、彼とClaude Shannon(そう、あのClaude Shannon)がこの問題に挑み、近似値しか得られなかったことには言及しなかった。大学院生のDavid Huffmanがそのレポートを選び、数ヶ月間苦労したが、自身の証言によれば、試験勉強を始めようとノートをゴミ箱に捨てたときに解決策が現れたという。
それ以前のすべての人々はトップダウンでコードを構築し、シンボルセットを半分に分割していた。Huffmanはそれを逆転させた。ボトムアップから始める。最も稀な2つのシンボルを取り、それらを1つにマージし、単一のツリーが残るまで繰り返す。稀なシンボルはツリーの深くに長いコードで配置され、頻繁なシンボルは浅い場所に短いコードで配置される。そのレポートの構築は証明可能に最適である1。75年後、それはJPEG、gzip、MP3(子供向けには、これは広告なしのSpotifyのようなものだ)の中にあり、そしてインターネット上のすべてのHTTP/2ヘッダーの中に存在する。
Huffmanのボトムアップ構築 - A Tale of Two Cities
FIG. 01
各ノードはその重みを示している。小説の文字のどの割合をカバーしているか。マージは重みの順に行われる。まずmとi、次にそのペアとt、そして最後にe。葉のパスに沿った0/1ビットがそのコードとなり、太字で示されている。
0101019.4%18.4%30.9%e12.5% 0m2.6% 100i6.8% 101t9.0% 11
4文字アルファベットでのHuffman構築。A Tale of Two Citiesの各文字の頻度で重み付けされている。
頻繁な文字は短いコードで浅い位置に、稀な文字は深い位置に配置される。そして文字は葉にしか存在しないため、どのコードも他のコードのプレフィックスにはなり得ない。葉にカーソルを合わせると、ルートからのパスをたどることができる。葉は、デコーダーがそれに到達したときに何をするかを、上から下に示している。
HPACKはヘッダーテキスト用の固定ハフマンコードを1つ出荷する。その頻度は10年前にキャプチャされた実際のヘッダーコーパスからRFCに焼き付けられているため、接続の両端は常にそれに同意する。小文字と数字はツリーの上部にあり、5〜7ビット。稀なバイトは30レベル深くぶら下がっている。典型的なヘッダーテキストは、バイトあたり約6ビットになる。ここで、ツリー構造が無料で与えてくれるプロパティに注目してほしい。シンボルは葉にしか存在しないため、どのコードも他のコードの始まりにはなり得ない。したがって、ビットストリームには区切り文字が全く必要ない。ビットを読み取り、葉へのパスをたどるまで読み取る。それがシンボルだ。ルートからやり直す。ストリームは、正しい場所から開始すれば、それ自体の境界を運ぶ。
また、コストがどこにあるかも示している。エンコードはテーブルルックアップとビット追加である。デコードは、そのウォークである。0で左、1で右、葉で出力、ルートに戻る。HPACKのコードでは、平均で約6回の依存分岐ロードステップが出力バイトごとにかかる。これは、クッキーの1文字のために多くの機械が必要であることを意味する。
ヘッダー値のエンコード部分を以下に示す。文字ごとにステップし、コードがバイトにどのようにパックされるか、バイト境界を無視して見てほしい。
Huffman、解凍済み - “application/json”
FIG. 02
accept: “application/json”16文字 · 88ビット → 11 B · −31%
1 · 各文字は固定RFC 7541コードにマッピングされる。頻繁な文字は短いコードを得る。
a
00011
5
ビット
p
101011
6
ビット
p
101011
6
ビット
l
101000
6
ビット
i
00110
5
ビット
c
00100
5
ビット
a
00011
5
ビット
t
01001
5
ビット
i
00110
5
ビット
o
00111
5
ビット
n
101010
6
ビット
/
011000
6
ビット
j
1110100
7
ビット
s
01000
5
ビット
o
00111
5
ビット
n
101010
6
ビット
2 · コードは1つのビットストリームに連結され、バイトにカットされる。88ビットはちょうど11バイトであり、この文字列にはEOSパディングは不要。
0
0
0
1
1
1
0
1
0x
1d
0
1
1
1
0
1
0
1
0x
75
1
1
0
1
0
0
0
0
0x
d0
0
1
1
0
0
0
1
0
0x
62
0
0
0
0
1
1
0
1
0x
0d
0
0
1
0
0
1
1
0
0x
26
0
0
0
0
1
1
0
1
0x
3d
0
1
0
0
1
1
0
0
0x
4c
0
1
1
1
0
1
0
0
0x
74
0
1
0
0
0
0
0
1
0x
41
1
1
1
0
1
0
1
0
0x
ea
char 1 / 16“a”→000115 bits
固定RFC 7541コードでの1つのヘッダー値:16文字、88ビット、ワイヤー上では11バイト。
矢印(キーボードでも操作可能)でステップするか、何かをホバーすると、コードはバイト境界を無視するため、1つのバイトがしばしば2つまたは3つの文字の断片を運ぶ。まさにデコードが興味深い部分である理由だ。
nghttp2は2014年から、それをはるかに優れた方法で行っている。事前計算された有限状態機械(FSM)でデコードするのだ。デコーダーはストリームの途中で有限個の状態しか持ち得ない。ハフマンツリーの各内部ノードにつき1つの状態、そしてHPACKの標準ツリーにはちょうど256個の状態があるので、状態は1バイトに収まる。各(状態、次のnビット)のペアについて、どこに到達し、どのシンボル(もしあれば)を出力するかを事前計算できる。デコードは次のようになる:次のnビットを取得し、テーブルをインデックス化し、バイトを書き込み、繰り返し。ビットバッファなし、コード長での分岐なし。
以下のマシンは、標準RFC 7541コードの下で例のヘッダー値をデコードする。2ビットずつ読み取るため、状態テーブル全体が画面に収まる。ステップして見てほしい。テーブルとツリーは、異なる服を着た同じものである。
高速プレフィックスデコード - “application/json” n = 2
FIG. 03
同じ
88
ビットを
2
ビットずつ読み取る - 88回の分岐決定の代わりに44回のルックアップ。チャンクをクリックするか、←/→(キーボードでも操作可能)でステップしてください。チャンクは文字境界を無視します。
lookup 1 / 44⟨start⟩+00→ε · mid-code→⟨00⟩out:
テーブル - T[state][chunk]
⇒
emit + next state ·
20
状態
×
4
チャンク値
state \ bits
00
01
10
11
⟨start⟩
ε
→00
ε
→01
ε
→10
ε
→11
⟨00⟩
∅
ε
→0001
ε
→0010
ε
→0011
⟨0001⟩
∅
∅
a
→0
a
→1
⟨1⟩
∅
ε
→101
∅
ε
→111
⟨101⟩
ε
→10100
ε
→10101
∅
∅
⟨10101⟩
n
→0
n
→1
p
→0
p
→1
⟨10100⟩
l
→0
l
→1
∅
∅
⟨0⟩
ε
→000
ε
→001
ε
→010
ε
→011
⟨001⟩
c
→start
∅
i
→start
o
→start
⟨0010⟩
c
→0
c
→1
∅
∅
⟨000⟩
∅
∅
∅
a
→start
⟨01⟩
ε
→0100
∅
ε
→0110
∅
⟨0100⟩
s
→0
s
→1
t
→0
t
→1
⟨0011⟩
i
→0
i
→1
o
→0
o
→1
⟨011⟩
ε
→01100
∅
∅
∅
⟨01100⟩
/
→0
/
→1
∅
∅
⟨111⟩
∅
ε
→11101
∅
∅
⟨11101⟩
j
→start
∅
∅
∅
⟨10⟩
∅
∅
ε
→1010
∅
⟨1010⟩
l
→start
∅
n
→start
p
→start
ツリー上の状態 - 四角はこのストリームのチャンク境界状態。青は現在のルックアップのウォークです。
11000011100100000110000110100010111startaciost/lnpj
n=2での高速プレフィックスFSM。FIG. 02のヘッダー値をデコードしています。nghttp2はn=4で同じマシンを出荷しています。
テーブル行は、この文字列がデコード中に訪れる状態をカバーしています。∅は、チャンクのパスがこの文字列の枝刈りされたアルファベットから外れるチャンクを示します。プロダクションHPACKデコーダーは、同じ方法で完全な257シンボルコードを構造化します。256状態×16ニブル値(n=4の場合)。この技術は、2003年にRenato Pajarolaが彼の「Fast Prefix Code Processing」論文で初めて発表しました。
ツリー上では、ウォークがチャンクの途中で葉に到達すると、その文字を出力して⟨start⟩(破線矢印)に戻り、残りのビットの消費を続けます。小さな点は、チャンク境界が決して着地しないツリー上の位置です。テーブル行をホバーすると、その状態がわかります。
nghttp2は、4ビットチャンクでこのマシンを正確に実行します。256状態×16ニブル値のテーブルへの入力バイトあたりの2つのルックアップ。16KiBで、L1キャッシュに快適に収まります。妥当性チェック(HPACKはパディングがすべて1であること、埋め込まれた文字列終了シンボルはエラーであることを要求する)は、同じルックアップに折り込まれます。これは本当に素晴らしいエンジニアリングです。nghttp2のHPACKパスが非常にフラットにプロファイルされる理由の1つです。
では、oghttp2のハフマンデコーダーが問題のはずですよね?
それが我々の当初の仮説であり、プロファイルはそれを否定しました。QUICHEのハフマンカーネルはnghttp2のFSMよりも遅いですが、差の大部分はデコーダーの上にあります。HttpHeaderBlockと、デコードされた各ヘッダーが通過する表現とブックキーピングのレイヤーが、測定したすべてのホストで、nghttp2のパスよりも一貫してリクエストあたり20〜30 µs多くコストがかかります。1つの項目が際立っていました。デコーダーはシンボルをstd::string::push_back経由で1バイトずつ出力しますが、その呼び出しだけで、x86ホストでのヘッダー飽和実行において、EnvoyのCPUの13〜20%を消費します。
ソースコードでその形状を見ることができます。デコーダーのホットループは、デコードされた各文字を個別にstd::stringに渡します。
$quiche/http2/hpack/huffman/hpack_huffman_decoder.cc (短縮版)
CPP
bool HpackHuffmanDecoder::Decode(absl::string_view input, std::string* output) { input.remove_prefix(bit_buffer_.AppendBytes(input)); while (true) { if (bit_buffer_.count() >= 7) { // Top 7 bits may hold a complete 5-, 6- or 7-bit code. uint8_t short_code = bit_buffer_.value() >> (kHuffmanAccumulatorBitCount - 7); if (short_code < kShortCodeTableSize) { ShortCodeInfo info = kShortCodeTable[short_code]; bit_buffer_.ConsumeBits(info.length); output->push_back(static_cast<char>(info.symbol)); // one byte per call continue; } } // ... longer codes take a second path (PrefixToInfo + a canonical-order // table) that ends in another output->push_back(c), then the loop refills // bit_buffer_ from input or returns. } }
各push_backは、ヘッダーテキストのバイトごとに容量チェックと再割り当ての可能性があります。次に、値が完全にデコードされると、すべてのヘッダーはEnvoyがそれを認識する前に、ハッシュマップルックアップとアリーナコピーを通過します。
$quiche/common/http/http_header_block.cc
CPP
void HttpHeaderBlock::AppendValueOrAddHeader(const absl::string_view key, const absl::string_view value) { value_size_ += value.size(); auto iter = map_.find(key); if (iter == map_.end()) { AppendHeader(key, value); // copies key and value into storage_ return; } value_size_ += SeparatorForKey(key).size(); iter->second.Append(storage_.Write(value)); // another copy, kept as a fragment }
どちらも、単独では完全に合理的なC++です。ホットパスがヘッダーフィールドごとに1回、コアあたり毎秒数十万回実行される場合、再割り当てチェック、マップルックアップ、コピーは、プロファイルが示す20〜30 µsに積み重なります。一方、nghttp2のデコーダーは呼び出し元提供のバッファに書き込み、次に進みます。
CPUフレイムグラフ - oghttp2デコードパス
FIG. 04
Stack
all
wrk:worker_0
Event::DispatcherImpl::run
ConnectionImpl::onReadReady [downstream]
OgHttp2Adapter::ProcessBytes
HpackDecoderAdapter::HandleControlFrameHeadersData
HpackDecoder::DecodeFragment
HpackHuffmanDecoder::Decode
std::string::push_back
HpackDecoderState::OnHeader
HttpHeaderBlock::AppendValueOrAddHeader
ConnectionManagerImpl::decodeHeaders
Router::Filter::decodeHeaders
UpstreamRequest::encodeHeaders
HpackEncoder::EncodeHeaderBlock
HuffmanEncode
tcp_sendmsg
ConnectionImpl::onReadReady [upstream]
OgHttp2Adapter::ProcessBytes
HpackDecoderAdapter::HandleControlFrameHeadersData
HpackDecoder::DecodeFragment
HpackHuffmanDecoder::Decode
std::string::push_back
HpackDecoderState::OnHeader
HttpHeaderBlock::AppendValueOrAddHeader
ConnectionManagerImpl::encodeHeaders
HpackEncoder::EncodeHeaderBlock
HuffmanEncode
tcp_sendmsg
tcp_recvmsg
176 µs/req · 36 frames · 10 levels
oghttp2のデコードパス。「push_back」を検索してみてください。カーネルの上と下の配管が時間の経過する場所です。
フレーム幅はリクエストあたりの合計µs。暗いほどホット。フレームをクリックするとズームイン、スタックトレースをクリックするとズームアウト、ホバーすると詳細表示、検索すると一致するフレームがハイライトされます。
公平を期せば、oghttp2のフレーミングとセッションレイヤーはnghttp2よりも安価です。ヘッダーリテラルが支配的でなくなるシナリオ(現実的なヘッダー、ダイレクトレスポンス、プロキシなし)では、oghttp2は8〜13%の優位性があります。コーデックはどこでも遅いわけではありません。しかし、プロキシの職務記述はヘッダー負荷が高く、ヘッダー負荷の高いトラフィックでは、配管税がフレーミングの勝利を埋もれさせます。
アップストリームに必要な修正は、デコードされたバイトからヘッダーブロックへのよりスリムなパスですが、これは単一のホットループよりも深いリファクタリングです。おそらく、Envoyのデフォルトがフォワードではなくバックにフリップされたのはこのためでしょう。
修正
私たちと顧客にとって、修正は心地よく退屈なものでした。
- Envoy 1.37+: 完了です。nghttp2がデフォルトに戻りました。
- Envoy 1.34–1.36:
envoy.reloadable_features.http2_use_oghttp2: falseを設定してください。これはランタイム設定の1行で、ほとんどのプロキシHTTP/2トラフィックで15〜25%のRPS/コアの価値があります。
我々はフリート全体にフラグを展開し、顧客のグラフは元に戻ったので、カレンダー招待は(今のところ)来ませんでした。ヘッダーパイプラインをリファクタリングするよりも、ランタイムフラグをフリップする方がはるかに良いことなので、エスケープハッチを残してくれたEnvoyチームに感謝します。
結論
コーデックのデフォルトはパフォーマンス変更です。 Envoyのマイナーバージョンアップが、ワイヤー上のバイトを1つも変更せずに、顧客のCPU請求額を20%変更しました。プロキシを運用している場合は、実際に出荷するバージョンをベンチマークしてください。ただし、実際のプロダクショントラフィックを代表する負荷を生成するのは難しい場合があります。それについては後で詳しく書きます。
最適化する前にプロファイルしてください。 我々はハフマンデコーダーが悪役だと確信していましたが、フレイムグラフは代わりに文字列の配管を指していました。デコーダーは、どちらのコーデックでも、むしろ最高の部分でした。
ヘッダー圧縮解除は実質的なワークロードです。 リクエストあたり数百バイト、ヘッダーフィールドあたり12個、コアあたり毎秒数万リクエスト、ホップごとに2回。計算はすぐに面白くなくなります。HTTP/2の帯域幅節約の試みは、CPU使用率を本当に噛む可能性があります。トレードオフなど...
しかし、その間、nghttp2のn=4テーブルと、nghttp2の作者と友人による2017年の論文をじっと見ていました。そこでは、1バイト全体を一度に読み取ることができると述べられています。ただし、16倍大きいテーブルを支払う意思がある場合。そのトレードオフがCPUキャッシュとの接触に耐えられるかどうかは、次の投稿で。
乞うご期待。
参考文献
- Minimum-redundancy codes - David A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, September 1952. レポートそのもの、最適性証明を含む。
[画像: Dmitry Ilyevsky]
Dmitry Ilyevsky
Co-founder & CTO
Dmitry is co-founder and CTO of Apoxy. He previously built and operated infrastructure at Google, Cruise, and Mux (where he and Matt met).