HPACKのしくみ

すぐ忘れるので、HPACKのしくみをまとめておきます。

HPACKとは

HTTP/1.1 では、ヘッダフィールドは圧縮されません。 通信時のデータ量を削減するために、HTTP/2ではHPACK(RFC7541)という方式を用いてヘッダフィールドの圧縮を行っています。 HPACKは、主に以下の2つの方法によって実現されます。

  • ハフマン符号化
  • インデックステーブル

ハフマン符号化

ハフマン符号化は、出現頻度の高い文字に短いビット列を、出現頻度の低い文字に長いビット列を割り当てることで実現する、データの可逆圧縮の方法です。

HPACKでは、ヘッダフィールドにおける文字の出現頻度から導いた対応表をもとにして、ハフマン符号化を適用することが可能です。なお、HPACKにおいてハフマン符号化は必須ではななく、ヘッダごとに送信者が使用の有無を決めることができます。符号化の有無は1bitのフラグとして表現され、サーバをこれをみてデコード操作を切り替えます。

インデックステーブル

インデックステーブルには静的テーブルと動的テーブルという2種類のテーブルがあります。 これらを利用したデータ量の削減方法は、以下のようなものです。

静的テーブル

静的テーブルは、一般的に使用頻度の高いヘッダフィールドを、1~61番までのインデックス値で管理しています。インデックス値を用いてヘッダフィールドをやり取りすることで、通信時のデータ量を削減しています。

動的テーブル

動的テーブルは、静的テーブルのインデックスの終端値に続く、62番から始まるインデックス値とヘッダフィールドの対応表です。変更のできない静的テーブルとは異なり、一度使用したヘッダフィールドを追加していくことができます。使用済みのヘッダフィールドをインデックスで表現するための工夫です。

動的テーブルは、エンコード用とデコード用にそれぞれ独立したテーブルを用意して管理します。対応する動的テーブルは、コネクションが切断されるまでの間、クライアントとサーバで同期が取れた状態を保ちます。

f:id:sgyatto:20190410193351p:plain:w500

ヘッダフィールドを追加する場合は、常に62番目のインデックスに対して追加していきます。 そのため、既存のデータは1つずつずれていく格好となります。
なお、動的テーブルにヘッダフィールドを追加するか否かは選択可能です。

ヘッダフィールドに使用される型

ヘッダーフィールドのエンコーディングでは、整数型と文字列型が使用されます。

整数型

整数型には以下のフォーマットが使用されます。 この場合は、1オクテット中の下位5ビットのプレフィックスを使用して、符号なし整数値が表現されること示しています。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? |       Value       |
+---+---+---+-------------------+

この場合だと0~31までの整数値が表現できます。 32より大きい値を使用する場合は、以下のようにフォーマットが拡張されます。 LSBは最下位ビット、MSBは最上位ビットを意味しています。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | 1   1   1   1   1 |
+---+---+---+-------------------+
| 1 |    Value-(2^N-1) LSB      |
+---+---------------------------+
               ...
+---+---------------------------+
| 0 |    Value-(2^N-1) MSB      |
+---+---------------------------+

要約すると、

第1オクテットのプレフィックスを1で埋め(2N-1に相当)、整数値から2N-1を引いた値を第2オクテット以降で表現する。

というようなことが書かれています。1000という整数値を例に、このフォーマットで表現してみます。

# 整数値と2^N-1の差(Nは5)
1000 - 31 = 969

# 差の2進数表現
0011 1100 1001

これらを下位7ビットから順に敷き詰めていきます。次のオクテットを必要とする場合はそのオクテット内の最上位ビットを1に、これ以上オクテットが続かない場合は最上位ビットを0に設定します。

最終的には以下のようになります。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | 1   1   1   1   1 |
+---+---+---+-------------------+
| 1 | 1   0   0   1   0   0   1 |
+---+---------------------------+
| 0 | 0   0   0   0   1   1   1 |
+---+---------------------------+

文字列型

文字列の場合は、以下のようなフォーマットを使用します。

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| H |    String Length (7+)     |
+---+---------------------------+
|  String Data (Length octets)  |
+-------------------------------+

先程、ハフマン符号化は必須でないと書きましたが、このフォーマットにおけるHが符号化の有無を表現しています。
Hが1のとき、String Dataにはハフマン符号が設定されます。
Hが0のとき、String Dataにはasciiが設定されます。

ヘッダフィールドのフォーマット

ヘッダフィールドはフォーマットに従って設定され、HEADERSフレーム内のHeader Block Fragmentの領域に格納されます。 フォーマットには以下のような種類があり、用途に応じて使い分けます。

  • インデックスヘッダフィールド表現
  • リテラルヘッダフィールド表現
    • インデックス更新を伴うリテラルヘッダフィールド
    • インデックス更新を伴わないリテラルヘッダフィールド
    • インデックスされないリテラルヘッダフィールド

インデックスヘッダフィールド表現

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+

静的テーブルまたは動的テーブルのインデックス値を指定するためのフォーマットです。
最上位ビットが1から始まるのが特徴です。

リテラルヘッダフィールド表現

ヘッダフィールドがインデックス値だけで表現できない場合は、リテラルヘッダフィールド表現を用います。

インデックス更新を伴うリテラルヘッダフィールド

動的テーブルにヘッダフィールドを追加する場合に使用します。 追加方法は2種類あり、「インデックスされたヘッダ名を使用」する方法と、「新しいヘッダ名を使用」する方法があります。
第1オクテットの最上位ビットが01から始まるのが特徴です。

インデックスされたヘッダ名を使用する場合のフォーマット
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
新しいヘッダ名を使用する場合のフォーマット
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |           0           |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

インデックス更新を伴わないリテラルヘッダフィールド

動的テーブルにヘッダフィールドを追加しない場合に使用します。
「インデックス更新を伴うリテラルヘッダフィールド」とのフォーマットの違いは、 第1オクテットの最上位ビットだけです。
こちらは0000から始まります。

インデックスを利用する場合のフォーマット
0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
インデックスを利用しない場合のフォーマット
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

インデックスされないリテラルヘッダフィールド

動的テーブルにヘッダフィールドを追加しない場合に使用します。
「インデックス更新を伴わないリテラルヘッダフィールド」との違いは、
RFCの「7.1.3. Never-Indexed Literals」において、

An intermediary MUST NOT re-encode a value that uses the never- indexed literal representation with another representation that would index it. If HPACK is used for re-encoding, the never-indexed literal representation MUST be used.

と述べられているように、中継者(プロキシ)が何かしらのインデックス等によって、ヘッダフィールドを再エンコードすることを禁止する意図が含まれています。
こちらも、フォーマットの違いは第1オクテットの最上位ビットだけです。
こちらは0001から始まります。

インデックスを利用する場合のフォーマット
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
インデックスを利用しない場合のフォーマット
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+


上記のリテラルヘッダフィールド表現を使用した例は、こちらを確認するとよいです。