この記事では、HTTP/3で導入されるHTTPヘッダ圧縮の仕組みである「QPACK 」について説明します。（執筆時 draft 07）
2020/06/01追記
まるっと解説記事を書き直しました
asnokaze.hatenablog.com
- HTTP/2の場合
- HTTP/3とQPACKの導入背景
- QPACKの概要
- Encoder Instructions
- Decoder Instructions
- Header Block Instructions
- エラーハンドリング
- その他
- QPACKという名称について
HTTP/2の場合
簡単に、HTTP/2で導入されたヘッダ圧縮の仕組みである「RFC7541 HPACK」について補足します。飛ばしていただいても大丈夫です。
HTTP/2の元となったSPDYというプロトコルではHTTPヘッダを単純にDeflateで圧縮していましたが、CRIME攻撃の危険があったため、HTTP/2では新しいヘッダ圧縮の仕組みHPACKが考えられました。
HPACKでは以下の２つの方法を用いてHTTPヘッダを少ないデータ量で表現します。
- ハフマン符号
- 静的テーブル、動的テーブル
ハフマン符号
各ヘッダ名と値のテキストをハフマン符号を用いて表現します。
ハフマン符号は各文字の出現頻度に合わせてbit表現を変更します。例えば出現頻度の多い'a'は0b00011を割り当て 5bitで表現できますが、出現頻度の低い'q'は0b1110110 が割り当てられており 7bit での表現となります。
このハフマン符号を用いてヘッダ名やヘッダ値の文字列(リテラル)を短く表現できます。
ハフマン符号の対応表は仕様中に定義されており、通信中に変更されるものではありません。
静的テーブル、動的テーブル
テーブルとは、ヘッダ名と値が格納された辞書データのようなものです(値は空の場合もあります)。このテーブルの何番目に格納されたヘッダなのかを指し示すことで、そのHTTPヘッダを表現できます。
たとえば、「accept-encoding: gzip, deflate」というヘッダは静的テーブルの16番に格納されているので、index:16 (1byte) で表現できるようになります。格納されているひとつのヘッダ名・値のペアをエントリと呼びます。
静的テーブルは一般に使用されるヘッダのリストが事前に定義されているテーブル領域であり、仕様で定義されています。
動的テーブルはクライアントとサーバが通信してる中で更新していくテーブルです。例えば、一度「user-agent: hoge」というヘッダを文字列(リテラル)表現で送信し、合わせて動的テーブルにそのヘッダを格納します。次から同じヘッダを送信する場合は静的ヘッダを参照する場合と同様に index: 62と送るだけで「user-agent: hoge」を表現できるようになります。
もちろん送りたいヘッダがテーブルにない場合もあります。その場合は以下のどちらかでヘッダを表現します。ヘッダ名は既存のテーブルから、ヘッダ名は文字列で表現する。もしくはヘッダ名と値とも文字列で表現する。のどちらかになります（文字列での表現にはハフマン符号が使用できる）。その際に合わせて動的テーブルにエントリを追加できます。
HPACKでは、動的テーブルのインデックスは静的デーブルに続いて62番から始まります。
動的テーブルに新しいエントリを追加する際は常にindex62から追加され、古いものは後ろにずれていきます。テーブルサイズを超えた場合、古いエントリから削除されていきます。
動的テーブルは、エンコードコンテキストとデコードコンテキスト用でそれぞれ管理されます。クライアントがHTTPリクエストを送信する場合はエンコーダとして振る舞いますが、HTTPレスポンスを受信する場合はデコーダとして振る舞います。逆にサーバはHTTPリクエストを受信する場合はデコーダで、HTTPレスポンスを送信する場合はエンコーダとなります。
動的テーブルは、ヘッダの送信者(エンコーダ)とヘッダの受診者(デコーダ)でテーブルの状態が同期されます。もちろん、一度コネクションが切れれば動的テーブルは引き継がれるようなことはありません。
HPACKでは、実際に解釈されるHTTPヘッダを格納したHEADERSフレーム内でヘッダを表現するのとテーブルに追加を指示するのをあわせて行っていました。ですので、各ストリーム上で動的テーブルの変更と参照が行われていました。
HTTP/3とQPACKの導入背景
HTTP/3ではトランスポートプロトコルとしてQUICを使用しています。HTTP/2ではパケットがドロップした場合は、OSレイヤで欠損したデータを回復した後アプリケーションにデータが渡されていたましたが、HTTP/3ではUDPとなるので後続の届いたパケットが処理可能であれば処理を進めることが出来ます。
こうすることで、ヘッドオブラインブロッキングを回避することが出来ます。しかし、HPACKをそのままHTTP/3で使おうとすると動的テーブルの更新と廃棄が、ヘッダの送信者(エンコーダ)とヘッダの受診者(デコーダ)で同期的に行われる必要があり、エンコーダが送信した順番にデコーダも処理する必要があります。これでは、後続のパケットが届いていても、ドロップしたり順番の入れ替わったパケットを回復するまで処理を進めることが出来ません。
そこで、HPACKの基本コンセプトとなるハフマン符号とテーブルの概念はそのまま、パケットの順番が入れ替わっても処理が進められるようにQPACKというヘッダ圧縮の標準化が議論されています。
動的ヘッダテーブル及びインデックスの示し方の変更がメインです、その他の部分については
- ハフマン符号については変更なし(エンコーダ側がヘッダ名と値にハフマン符号を使用するか選択する
- 静的ヘッダテーブルについては、中身が変更されており、現在多く使用されているヘッダが追加されました。（また、動的テーブルとインデックスが共有されなくなりました。参照する際に、どちらのテーブルを参照しているかフラグで示します。）
静的テーブルの具体的な中身については仕様を参照 (Appendix A)
QPACKの概要
QPACKにおける動的テーブルの更新と参照の概要を以下にします。
（クライアントがエンコーダの場合のみの図ですが、クライアント側がデコーダの場合は逆の図になります。）
- Encoderストリーム: 動的テーブルへのエントリ追加を指示するEncoder Instructionsを転送する単方向ストリーム (Type=0x02)
- Decoderストリーム: デコーダからエンコーダへのフィードバックであるDecoder Instructionsを転送するための単方向ストリーム (Type=0x03)
- Requestストリーム: HTTP/3のリクエスト・レスポンスのペア毎に使用される双方向ストリーム。実際のリクエストヘッダやレスポンスヘッダのやりとりがされる。QPACKでは、HEADERSフレームやPUSH_PROMISEフレームでは動的テーブルを変更しません。Header Block Instructionsで動的テーブルを参照するだけです。(Requestストリームの定義自体はHTTP/3側)
QUICでは、同一ストリーム内の整合性(データの順番)は保証されます。一つのEncoderストリーム上で動的テーブルの更新を行いますので、エンコーダが送信した順番通りデコーダも動的テーブルを更新します。
一方で、ストリームをまたがって順番は保証されません、Encoderストリームのデータを含むパケットが欠損した場合でも、Requestストリームはブロックされません。もし、HEADERSの処理が可能であれば処理が進められます。ただし必要な動的テーブルがまだ追加されていなければ、追加されるまでHEADERSフレームの処理は待たされます。
逆に、特定のRequestストリームのパケットが欠損した場合、動的テーブルに追加したエントリが使用されたかどうかわからないため、動的テーブルから削除することが出来ません。そのために、デコーダはDecoderストリームで、Requestストリームの処理が完了したことをエンコーダ側にフィードバックを送ります。こうすることで、エントリを動的テーブルから安全にevictionすることが出来ます。エンコーダはこのようにevictionされるエントリを考慮して動的テーブルにエントリを追加する必要があります。
もう一つの問題として、Requestストリームのやりとりとは独立して動的テーブルが変更される点です。エンコーダ側の動的テーブルがどういう状態で送信されたHEADERSフレームかがわからないと正しくデコードすることが出来ません。そこでQPACKでは、HPACKのような絶対インデックスではなく相対インデックスを用いてテーブルの各エントリを指し示します。また、ワンパスエンコーディングを実現するために、Post-Baseインデックスという指し示し方も行います。
Encoder Instructions
エンコーダ側からEncoderストリームで、動的テーブルが更新するEncoder Instructionsが送信されます。命令の種類は4つです
- Insert With Name Reference: 動的テーブルにエントリを追加します。ヘッダ名についてはテーブルを参照し、値については文字列で指定します
- Insert Without Name Reference: 動的テーブルにエントリを追加します。ヘッダ名と値両方共文字列で指定します。
- Duplicate: 動的テーブルにエントリを追加します。既存のエントリを複製します。
- Set Dynamic Table Capacity: テーブルのキャパシティを変更します。
(文字列を使う場合はハフマン符号を使用できます)
最初に追加されたエントリは絶対インデックス0であり、次に追加されるエントリは絶対インデックス1へと、1つずつ増えていきます。新しいエントリを追加する際に、設定したテーブルのキャパシティを超える場合はキャパシティに収まるように古いエントリからevictionされます。なお、デコーダが使用する可能性があるエントリがevictionされないようにエンコーダが注意する必要があります。
もし、エントリの追加が出来ない場合は、HEADERSフレームではヘッダ名とヘッダ値の両方とも文字列で表現してHTTPリクエスト・レスポンスのやり取りをすることになります。
追加するエントリは、evictionされるエントリを参照できるので、evictionされるタイミングでDuplicateすることが出来ます。
Decoder Instructions
デコーダ側からDecoderストリームで、動的テーブルの一貫性を保証するためエンコーダにフィードバックが送信されます。命令の種類は3つです。
- Insert Count Increment: 以前に送信してから、動的テーブルに追加されたエントリの増分を示す。
- Header Acknowledgement: 動的テーブルを参照するストリームを処理した際に、そのストリームIDを示す。
- Stream Cancellation: ストリームをキャンセルした(動的テーブルを参照せず、不使用となる)
これらの情報をエンコーダにフィードバックすることで、エンコーダはどのエントリが参照可能か、eviction可能か判別できるようになります。
Header Block Instructions
Header Block Instructionsは、HEADERSフレームやPUSH_PROMISEフレームで実際にHTTPリクエストやHTTPレスポンスのヘッダを示すのに使用されます。静的・動的テーブルを参照することでヘッダ名・値を表現することが出来ます。また、テーブルは使用せず文字列(リテラル)で直接ヘッダを表現することも出来ます。
圧縮されたヘッダのリストをヘッダブロックと呼び、HEADERSフレームで送信されます。
具体的にはプレフィックスである2つの値と、ヘッダブロックであるCompressed Headersが送信されます。
- Required Insert Count: このヘッダブロックをデコードするのに必要な、動的テーブルの追加カウント数(動的テーブルを参照しない場合は0)
- Delta Base: 相対インデックスのベースとなる、Required Insert Countからの差分 (正の場合と負の場合で表現方法が異なる)
- Compressed Headers: 圧縮された実際の各ヘッダリスト
ヘッダブロックを受け取ったデコーダが、Required Insert Countで示された数より自身の動的テーブルに追加されたエントリが少ない場合は、まだこのヘッダブロックをデコードすることは出来ないので、十分な追加のEncoder Instructionsが送られてくるまで待つことになる。ブロックされうるストリームの上限は別途SETTINGS_QPACK_BLOCKED_STREAMSパラメータを使用して指定することが出来る。
相対インデックス
先述の通り、HEADERSフレームの送信と、動的ヘッダテーブルへのエントリ追加のパケットは順番が入れ替わって処理される可能性があります。どのような順番でも正しく動的テーブル上のエントリを参照できるようにするために相対インデックスを用います。
エンコーダがHeader Block Instructionsを作成した時に基準となるインデックス(Base)を設定して、そこからの差分でインデックスを参照します。これを相対インデックスと呼んでいます。
相対インデックスはBaseのインデックスを基準に絶対インデックスとは逆に増えていきます。Post-BaseインデックスはBaseインデックスを基準に同じ方向に増えていきます。
動的テーブルを参照する際は、この相対インデックスやPost-Baseインデックスを使用して動的テーブルのエントリを指し示します。
相対インデックスとPost-Baseインデックスが分からえているのは、ワンパスエンコーディングを行うためです。エンコーダがHeader Block Instructionsを作成する際のことを考えます。
エンコードしたいヘッダのリストが有る際に、まずBaseを決めます。順々にヘッダをエンコードしていき、動的テーブルが使えれば使用します。しかし、エンコードを開始してから、エンコードしようとしているヘッダが動的テーブルにはなく動的テーブルに追加したいとします。その際には、Baseより絶対インデックスが大きい場所にエントリを追加することになります。このようにエンコード中に追加したエントリは、Post-Baseインデックスを使うことで参照できます。一通りのヘッダのエンコードが終わったら、Required Insert Countを決定し、そこからの差分を求めBaseフィールドに設定しHeader Block Instructionsの出来上がりです。こうすることで、ワンパスのエンコーディングが行えます。
Compressed Headers
ヘッダブロックであるCompressed Headersは下記の表現の集合です。1つのヘッダ名と値のペアは必ず下記のいずれかの表現によって表されます。
- Indexed Header Field: 静的テーブルもしくは動的テーブルの相対インデックスの指定のみからなる。ヘッダ名・値とも示されたインデックスのエントリのものになる。
- Indexed Header Field With Post-Base Index: 動的テーブルのPost-Baseインデックスの指定のみからなる。ヘッダ名・値とも示されたインデックスのエントリのものになる。
- Literal Header Field With Name Reference: ヘッダ名については静的テーブルもしくは動的テーブルの相対インデックスを用いて指定する。ヘッダ値に関しては文字列(リテラル)で指定する。
- Literal Header Field With Post-Base Name Reference: ヘッダ名については動的テーブルのPost-Baseインデックスを用いて指定する。ヘッダ値に関しては文字列(リテラル)で指定する。
- Literal Header Field Without Name Reference: ヘッダ名・値とも文字列(リテラル)で指定する。
(文字列を使う場合はハフマン符号を使用できます)
エラーハンドリング
テーブルの範囲外を参照したり、不適切な値が検出された場合は下記のエラーを発生させストリームやコネクションを終了します
その他
今回は、数値表現について詳しく触れませんでしたが、QPACKのインデックスなどの値を指定する際は可変長表現を利用します。小さな値はより少ない長さで表現することが出来ます。
その他にもRequired Insert Countも短い長さで表現できるように工夫されています。
QPACKという名称について
最後に、QPACKという名称について触れておきます。
もともと別にQPACKと、QCRAMという提案仕様が出されていましたが、議論の結果QCRAMという提案が採用されました。そして、このQCRAMがQPACKに名称変更されて、今のQPACKの元となっています。
HTTP over QUICがHTTP/3となったのを期に、HPACK3という名称にしてはどうかという意見が出ましたが、そうはなりませんでした。
github.com
