いやいや、難産だったよ。
2020年から2021年にかけて、HaskellでHTTP/3ライブラリを作成する過程で、QPACKを実装した。HPACKやQPACKでは、圧縮を担う符号器(encoder)よりも、伸長を担う復号器(decoder)の方が、圧倒的に簡単である。このため、Haskellの復号器は、静的表に加えて動的表も使うように実装できたが、符号器は難し過ぎて静的表しか活用しない状態でライブラリをリリースした。
2021年に執筆した「QUICをゆっくり解説(16):ヘッダ圧縮」の「おわりに」では、
私の現時点の実装では、圧縮側は動的表を全く利用していません。この記事を書いたことをきっかけに、実装に挑戦してみようかと思います。
と表明してた。
あれから4年。ようやく時間が取れたので、符号器を動的表に対応させる宿題に取り組んだ。
このブログは、QPACKを実装した経験の備忘録である。HPACKは知っているけど、QPACKはよく分からない人の役に立つかもしれない。
用語は、今どきの IETF 用語に合わせる。
- フィールド名 - 世間で言うヘッダ名
- フィールド値 - 世間で言うヘッダの値
- フィールド:フィールド名とフィールド値の組
- セクション - フィールドの集合。いわゆるヘッダ。
仕様
QPACKの目的は、HPACKの Head-of-Line ブロッキングを「緩和」することである。HPACKでは、セクションが圧縮された順番で、伸長される必要があった。パケットの欠損などにより、途中の伸長が止まれば、たとえ以降のセクションが届いていても、伸長の工程は止まる。
QPACKでは、伸長側(復号器)をできるかぎり並列化できるように設計されている。鍵となるアイディアは、「動的表の更新命令」(encoder instruction)と「フィールド表現」(field representation)を分離することである。
HPACKでは、これらの区別がなかった。そのため、動的表を変更するセクションに次のセクションが依存し、後続のセクションもまた依存しと、依存の連鎖が起きていた。
QPACKでは、動的表の更新命令を一方向ストリームで送る。フィールド表現は、HTTPのリクエスト&リスポンスをやりとりするための、双方向ストリームで送る。このHTTPのストリームは、更新命令を送るストリームにのみ依存する。
動的表の更新命令
動的表に登録されるエントリは、フィールドである。動的表の更新命令(encoder instruction)は以下の通り:
- 動的表の大きさの設定
- 「文字列のフィールド名」(literal)を使ったエントリの挿入
- 「フィールド名の参照」(index)を使ったエントリの挿入
- エントリの複製 (duplicate)
HPACKでは、静的表と動的表のインデックスが同じ空間として扱われていた。静的表のエントリ数は61なので、動的表のインデックス62から始まる。動的表は62以降をFIFOとして使う。つまり、新しく挿入したエントリのインデックスは62であり、その挿入によって元々のエントリのインデックスは1増加する。動的表の大きさを超えた古いエントリは、動的表から削除される。明示的な削除命令はない。
QPACKでは、静的表と動的表のインデックスは、別の空間として扱われる。動的表のインデックスは、単調に増加する。単純に大きなインデックスを符号化すると、バイト数が大きくなるので、動的表の更新命令では、「挿入点」(insertion point)からの相対値で表現される。挿入によって動的表の大きさの制限を超えると、必要な分、古いエントリが削除される。明示的な削除命令はない。
ここが重要なのだが、QPACKの動的表に挿入するエントリは、これから追い出されるエントリを参照してもよい。もちろん、追い出された後のエントリは参照してはならない。
フィールド表現
フィールド表現は、以下の3つに大別される。
- インデックスを使ってフィールドを表現する
- インデックスを使ってフィールド名を表現し、フィールド値には文字列を使う
- フィールド名にもフィールド値にも文字列を使う
符号器は、これから圧縮するセクションに対して、現在の挿入点を「基準点」(base point)とて指定する。フィールド表現で使われるインデックスは、バイト数を抑えるために、基準点からの相対値を利用する。圧縮開始までに挿入されているエントリのインデックスは、基準点よりも小さい。圧縮中に挿入されたエントリのインデックスは、基準点の値以上となる(post base-indexing)。
重要なのは、(「動的表の更新命令」の節で説明した「これから追い出されるエントリ」も含めて)動的表にないエントリは、参照してはならないことである。
並列化
圧縮されたセクションには、圧縮されたフィールドと基準点に加えて「必要挿入数」(required insert count)が付与される。復号器の動的表に、少なくとも必要挿入数分のエントリが挿入済みであれば、そのセクションの伸長は「ブロックされない」。不足していれば、「ブロックされる」。
復号器は、動的表に挿入されたエントリの数を以下のACK(decoder instruction)によって通知できる。
- 動的表に新たに何個エントリを挿入したかのACK
- 圧縮されたセクションを伸長できたことのACK
1)は直感的に分かりやすい。動的表の更新命令に対して、ACKを返すからである。2)は、復号側で動的表を管理しないコードが発するACKなので、少し分かりにくい。
実装モデルとして、スレッド・プログラミングを考えよう。リクエスト&リスポンスに1スレッドを割り当てるとする。(1HTTPストリーム、1スレッドという意味。)
リクエストは同時に複数発生するかもしれない。実装して分かったのだが、圧縮側には並列性は必要ない。HoLブロッキングは、伸長側の問題なので、圧縮側は直列に実装するのが理にかなっている。
あるスレッドがリクエストのセクションを圧縮する際は、動的表をロックする。そして、動的表の操作命令が発生した場合は、それを専用の一方向ストリームで送る。また、圧縮したセクションを、双方向のHTTPストリームで送信する。
伸長側では、動的表の操作命令を一方向ストリームから読み取り、動的表を操作する専用スレッドが必要である。このスレッドのみが、動的表に書き込む。書き込めたら、「この専用スレッドが1)のACKを返す」。
リクエストが送られてくるHTTPストリームを読み込むスレッドは、動的表を読む。読むだけなので、並列化できる(ロックは必要ない)。動的表に必要なだけエントリが挿入されていれば、このスレッドはブロックされない。そうでなければ、ブロックされる。セクションの伸長が終わったら、「このHTTP用のスレッドが2)のACKを返す」。
圧縮側にも、ACKを読み込んで処理するための専用スレッドが必要である。2)を処理するためには、あるセクションに対する「ストリーム番号」と「必要挿入数」を記録しておく必要がある。2)のACKが返れば、その必要挿入数分、挿入されたと判断できる。
動的表を参照しない場合、符号器は必要挿入数に0を指定する。復号器は、必要挿入数が0の場合、2)のACKは返さない。
ブロックされてもよいストリーム数
動的表の大きさに加えて、もう一つのパラメータとして、「ブロックされてもよいストリーム数」がある。この値が許す限り、送信側は、「ACKが返っていない動的表のエントリを参照したフィールド表現」を含むセクションを送信してもよい。
伸長側は、2)のACKを返すだけで十分であると考えがちだが、実際は1)のACKも返す必要がある。たとえば、現在のブロックされてもよいストリーム数が0だとしよう。
- 圧縮側は、将来のために動的表の挿入命令を送る
- ブロックされてもよいストリーム数が0なので、新たに挿入したエントリは参照できない
- 動的表をまったく参照しないで圧縮し場合、必要挿入数には0が指定される
- 伸長側は、そのセクションを伸長する際、必要挿入数が0なので、2)のACKは返さない
これだけだと、将来使うためのエントリには、ACK は返ってこないので、いつまでたっても利用できない事態に陥る。そこで、伸長側は、少なくとも必要挿入数が0の場合、1)のACKを返す必要がある。
そろそろ、嫌になってきたでしょ。
動的表の大きさ
HPACKもQPACKも最初の大きさは0で、初期値を交渉することで、大きさを決定する。HPACKでは、最初のセクションを送信する前に、大きさが決定されることが保証されている。QPACKでは、初期値を交渉を待たずに、セクションを送ることができ、その場合の動的表の大きさは、もちろん0である。この短い期間内では、動的表は使えないので、静的表だけ活用してセクションの圧縮を試みる。
後述のように、この性質をうまく利用したエントリ管理の方法(ニーモニック技法)がある。
エントリの削除
HPACKでは、動的表の末尾から自由にエントリを削除できた。
QPACKでは、動的表の各エントリに対して、どのセクションから参照されているかのリファレンス数を管理しないといけない。参照する際にリファレンス数を増やし、2)のACKが返って来れば、対応するエントリのリファレンス数を減らす。
動的表の末尾のエントリは、リファレンス数が0の場合にのみ削除できる。つまり、エントリを挿入する際は、末尾からリファレンス数が0のエントリが連続しているかを調べ、「それらの合計数」と「未使用の大きさ(使いきれないギャップ)」の合計が、新たに挿入するエントリの大きさ以上の場合に限り、そのエントリを挿入できる。
末尾にリファレンス数が0のエントリが連続するようにする技法として、RFC 9204では「排除点」(draining point)が紹介されている。見付かったエントリが、排除点よりも小さい場合は、利用しない。そうすれば、新たな参照は発生しないので、いずれリファレンス数が0になるという訳である。
Haskellでの実装
Haskellには軽量スレッドがあるので、上記のスレッド・プログラミングを採用している。
初期実装
符号器を動的表に対応させる初期の実装としては、RFC 9204 の内容に従って排除点を利用していた。動的表から見付かったエントリのインデックスが、排除点よりも小さい場合、それは利用しない。可能であれば、そのエントリを複製して、利用しようとする。
この時点でのコードは、見通しが悪かった。なぜなら組み合わせ爆発が起きていたからである。
- 検索結果の種類
- 「フィールド」が見付かった
- 「フィールド名のみ」が見付かった
- 見付からなかった
- 表の種類
- 静的表
- 動的表
- 排除点との関係
- 排除対象
- 排除対象外
QIFs
QIFsとは、QPACKの相互接続性検証プロジェクトである。ここには、Facebook と netbsd.org でサンプリングされたセクション群と、各QPACK実装での圧縮結果が置かれている。
Haskellの復号器は、これらの圧縮結果を伸長することで、正しさを検証していた。
圧縮するためのパラメータは以下の通り:
- 動的表の大きさ:0、256、512、4096
- ブロックされてもよいストリーム数:0、100
- ACK: ACKはまったく返されない(no)、すぐにACKが返される(yes)
ACKに関しては、解釈の範囲が広い。Haskellのテストプログラムでは、あるセクションに対して、ある圧縮したセクションと動的表の操作命令両方を送信し終えた直後、1)と2)のACKが返ってくるという解釈を採用した。(動的表の操作命令ごとに1)のACKが返るのではなく、セクション単位でまとめて返るという意味。)
長い期間、他の実装と圧縮率の傾向に相違があって、ずいぶんと悩んだ。そうして、ようやく期待される振る舞いを理解した。下2つのパラメータの組み合わせに対して、符号器の期待される振る舞いを記す。
- (0, no):動的表は育ててもよいが、ACKは返ってこないので、動的表はまったく参照できない
- (0, yes):育てた動的表は、次のセクションから利用できる。
- (100, no):100つのセクションまでは、挿入したエントリをすぐに利用できる。101目以降は、動的表は活用できない。
- (100, yes):挿入したエントリをすぐに利用できる。
ngtcp2/nghttp3
QIFs のセクションを Haskellの符号器で圧縮した結果は、まず Haskell の復号器で伸長できることを確かめた。
次に、ngtcp2/nghttp3を使って、Haskellで圧縮したセクションを伸長できるか検査した。ngtcp2/nghttp3の実装は、極めて正確であり、安心して信頼できた。また、僕が慣れているC言語で書かれているので、printf debug できるようにコードを変更しやすかったのも助かった。
ニーモニック技法
QIFs に圧縮結果を登録しているLITESPEEDのブログサイトに「Developer’s Corner: QPACK Mnemonic Technique」という記事を発見した。
QPACKに挿入されるエントリは、HPACKよりも追い出しにくいので、挿入するエントリを慎重に選ばないといけない。多くの実装では、フィールド名ごとに挿入するかしないかの情報をアドホックに定義して使っている。
この記事で紹介されている「ニーモニック技法」のアイディアはこうだ。利用されたフィールドの「集合」を管理する。その集合を利用して、2回以上フィールド(あるいはフィールド名)が利用された場合に限り、動的表に挿入する。
最初の出現では動的表には登録しないので、それがよく使われるフィールドであれば、出遅れた分、圧縮率が悪くなるかと思いきや、動的表の大きさの初期値は0なので、ペナルティは発生しないのである。
逆インデックスと排除エントリ
「排除エントリが見付かった場合には複製すべき」という思い込みによって、初期実装では、組合せ爆発が起きていた。あるとき、「複製は一旦あきらめて、排除エントリを検索対象から外せば組み合わせの数が低減されるのでは?」というアイディアを思いついた。
動的表にインデックスでアクセスするとフィールドが得られる。逆にフィールドからインデックスを得るためには、何も工夫がなければ、動的表を端から端まで走査しなければならない。
Haskellの符号器では、高速化のために逆インデックスを持っている。この逆インデックスから排除エントリを排除することにした。検索できるエントリは、排除エントリでないことが保証されたため、コードが簡潔になった。
そもそも、ニーモニック技法を使っているので、排除点が不要なのではないかと思って試したが、排除点は圧縮率に貢献していることが分かった。
フィールド名
圧縮率を比較していて、なかなかLITESPEEDの性能に迫れなかったとき、LITESPEEDの圧縮結果を解析すると、LITESPEEDでは動的表の(フィールドではなく)フィールド名をうまく活用していることが分かった。
動的表のフィールド名は、QPACKの魔境である。
動的表をフィールドのみで利用するのであれば、逆インデックスは「フィールド→インデックス」というデータ構造で済む。フィールド名(のみ)も利用するであれば、「フィールド名→(フィールド値→インデックス)」というデータ構造が必要となる。
あるフィールド名に対して、「フィールド値→インデックス」は複数登録されうるから、どのエントリを利用するかが問題となる。最近のエントリを使うと「要求挿入数が大きくなる」(ブロックされる確率が上がる)し、古いエントリを使うと「リファレンス数が増えて、そのエントリを削除しにくくなる」というジレンマがある。
さらに、古いエントリが排除エントリであるかもしれないという問題もあったが、この問題は上記のアイディアで考えなくてもよくなった。排除エントリでない、もっとも古いエントリを発見するために、「フィールド値→インデックス」のデータ構造としては、PSQ(Priority Search Queue)を利用することにした。
- key はフィールド値
- value はインデックス
- priority もインデックス
とすると、
- key による検索は O(log n)
- key による削除は O(log n)
- 最小の priority のエントリを発見するには O(1)
である。
これに加えて、ニーモニック技法の集合にも、フィールド値を空文字列としたフィールドを登録しなければならない。
動的表のフィールド名を参照しながら、動的表に新しいエントリを追加する場合、参照したエントリが動的表から削除される可能性がある。フィールド表現では、この削除されたエントリを参照してはならない。
末尾複製
複製に関して、末尾複製(tail duplicate)というアイディアを思いついた。動的表の操作命令では、これから削除されるエントリを参照してもよい。末尾を複製すれば、先頭に追加されたエントリと末尾のエントリのサイズは同じなので、動的表の大きさを気にせずに削除できる。(ただしリファレンス数が0の場合に限る。)
あとは、いつ末尾複製するかである。いろいろ試したが、動的表がいっぱいでフィールドを挿入できない場合、つまり「フィールド名にもフィールド値にも文字列を使う」フィールド表現を発行した場合に、末尾のエントリのリファレンス数が0であり、これまで一定数(現在は10)使われていたなら、末尾複製するのが一番圧縮率が高かった。
圧縮率
参考までに、現時点での圧縮率の結果を示す。
qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.0.0 62.0 qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.0.0 62.0 qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.0.0 82.9 qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.0.1 18.9 qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.0.1 17.3 qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.0.1 37.6 qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.100.0 50.4 qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.100.0 50.8 qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.100.0 50.6 qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.100.1 19.7 qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.100.1 15.2 qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.100.1 19.4
これは、あくまでFacebookのサイトのサンプリングに対する結果である。入力データが変われば、結果も変わる。
LITESPEEDの圧縮率に肩を並べるには、複製のアルゴリズムを工夫しなければならないようだが、まだ何もアイディアを思いつかない。
おまけ
HPACKを実装したときとは違って、QPACKの実装過程では、特に目新しいことは発見できなかった。貢献できたことは以下の通り:
謝辞
安定したQPACKの実装を提供しており、またいくつかの質問に答えてくださった Tsujikawa さんに心から感謝します。QPACKに関する素敵なブログを公開してくださった Dmitri Tikhonov さんにお礼を申し上げます。