HTTP2のヘッダ圧縮技術

整数表現の説明が一部間違っていたので修正。


# HTTP2ヘッダの概要

●HTTP1.1でのセマンティクス

```
GET / HTTP1/1
Host: www.example.com
Accept: */*
```

●HTTP2でのセマンティクス

```
:method GET
:path /
:scheme https
:authority www.example.com
Accept */*
```

次の三つは必須フィールドです。

```
:method
:path
:scheme
```

「:method」「:path」「:scheme」「:authority」は先頭に「:」を付けます。
「:」もフィールドの長さに含まれます。

これらのフィールドを決まったフォーマットに従って、下記の3種類のどれかで送ります。
　
●プレーンテキストで送信する。
●テーブルのインデクス指定で送信する。
●ハフマンコーディングで圧縮して送信する。

フィールド毎にプレーンテキストで送ったりインデクスしたり、方法を変更できます。
圧縮前(送信前)と後(送信後)でヘッダーリストは順序が保たれ、重複も許されます。


具体的なフィールドの記述方法やハフマンコーディングの仕方は後で説明するので、まずはテーブルの概念とリクエストの流れを見ます。

# 静的テーブル

HTTP2には使用頻度の高いヘッダフィールドがあらかじめ定義されていて番号で指定できるようになっています。
これを静的テーブルといいます。

現時点の最新は[こちら](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#appendix-A)です。

# 動的テーブル

HTTP2では一度送信したヘッダフィールドを覚えておいて、次回から番号で指定できるようになっています。
これを動的テーブルといいます。

動的テーブルはサイズが決まっています。
HTTP2通信を行う時に最初に交換するSettingフレームで、SETTINGS_MAX_HEADER_LIST_SIZEというプロパティで指定します。

動的テーブルの一つのヘッダフィールドのサイズは、
「フィールド名と値のオクテットの長さに 32バイト を加えた合計値」
です。
プログラムで値を処理するために32バイトの余白を与えています。

例えば動的テーブルに次の二つのフィールドを挿入した場合に動的テーブルのサイズは、

```
:method GET
:path / 

7 + 3 + 32 = 42
5 + 1 +32 = 38

42 + 38 = 80オクテット
```

になります。

動的テーブルに新たに値が追加され、テーブルのサイズを超えた場合は、ファーストインファーストアウトで最も古いものが削除されます。

静的テーブルと動的テーブルはインデクスを共有しています。
静的テーブルには61個の値が定義されていますから、動的テーブルに最初に追加した値のインデクスは62になります。

```
<----------  Index Address Space ---------->
<-- Static  Table -->  <-- Dynamic Table -->
+---+-----------+---+  +---+-----------+---+
| 1 |    ...    | s |  |s+1|    ...    |s+k|
+---+-----------+---+  +---+-----------+---+
                       ^                   |
                       |                   V
```


●1回目のリクエスト

次のリクエストを送信する場合、

```
:method GET
:path / 
:scheme https
:authority www.example.com
customheader costomvalue
```

上の三つは、フィールド名と値のペアがまるごと静的テーブルのインデクス指定を使えます。
さらに「:authority」は番号1で指定できるので、以下のようになります。

```
2
4
7
1 www.example.com
customheader costomvalue
```

「:authority www.example.com」と「customheader costomvalue」は動的テーブルに追加されます。


●2回目のリクエスト

２回目のリクエストで次のものを送信する場合、

```
:method GET
:path /mypage.html
:scheme https
:authority www.example.com
customheader costomvalue
```


パスの部分以外はインデクス指定できます。
そして「:authority www.example.com」「customheader costomvalue」は動的テーブルに追加されたはずなのでインデクス指定できます。


```
2
7
62
63
4 /mypage.html
```


次に具体的なフィールドの記述方法を見ていきます。


# ヘッダーフィールドで扱う型(表現)

符号なし整数と文字列です。

ただし文字列表現の中に、文字列の長さを表すために整数表現を使っています。



# 符号なし整数型

テーブルのインデクス指定と文字列の長さを指定するのに使用します。
そのために1オクテット中のNビットの情報を使います。
整数表現を何に使うかによってNは変化します。

```
 0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? |     Value (N)     |
+---+---+---+-------------------+
```

テーブルのインデクス指定では、Nは4、6、7のどれかです。
このNビットの部分の使える領域をプレフィックスと呼びます。

仮に今、例としてこのNを5とした場合は、整数で31まで表現できます。(2^N-1)
00011111

文字列の長さを表現する場合は、N=7です。なので7ビット(最大で127)を使えます。
01111111

以下は5ビットプレフィックスで整数表現の例です。(文字列の長さ指定は後で説明します)

```
 0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 1 | 1 | 1 | 1 | 1 |
+---+---+---+-------------------+
```

下位5ビットプレフィックスをフルに使うと整数の31です。(2^N-1)

31を超える場合は、その整数から31を引いて次のオクテットを消費します。
その場合は最上位ビットに継続フラグを立てます。
そのオクテットで終わりの場合は最上位ビットを0にします。

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

値のデコードは末尾のオクテットから始め、それぞれ最上位ビットを除去します。
これらの値は連結され、最後に31が加算されます。

たとえば1337をエンコーディングする場合

```
1337 - 31 = 1306
↓
1306 = x05x1a
↓
0101 00011010
```

下位7ビットから敷き詰めていく。

```
00011010
0101
↓
00011010
00000101
```

なので、

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+---+
```

になります。


# 文字列型

文字列はそのままASCIIで表現するか、ハフマンコーディングされているかのどちらかです。
どちらの場合も最初に長さを記述して、その後にデータを書きます。

この時に長さ(String Length)を表現するために使う整数表現のNの部分は「N=7」になります。
なので7ビットまで使えます。7ビット(127)以上の場合は、上記の整数表現に従って次のオクテットを消費します。

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

プレーンテキストで

```
:method GET
```

を表現するなら

```
0x07, 0x3a, 0x6d, 0x65, 0x74, 0x68, 0x6f, 0x64,         // 7 :method
0x03, 0x47, 0x45, 0x54       // 3 GET
```

になります。

Hが1ならハフマンコーディングされています。
ハフマンコーディングは出現頻度の高い文字を少ないビット列で表現できる圧縮方法です。
その場合のString Lengthはハフマンコーディングされた値のオクテット数になります。


# ハフマンコーディングの方法

どの値がどのビット配列になるかがあらかじめ定義されています。
それに当てはめて、ビット列を作っていくだけです。
現時点の最新は[こちら](http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#appendix-B)です。

ドラフトの例にあるように、

```
www.example.com
```

は

```
f1e3 c2e5 f23a 6ba0 ab90 f4ff 
```

になります。

なぜこうなるのか？

wはハフマンコーディング表で「1111000」です。
だからwwwは

```
111100011110001111000
```

になります。

「www.example.com」を愚直にすべてを連結させていくと、

```
11110001111000111100001011100101111100100011101001101011101000001010101110010000111101001
```

になります。
これを8ビット(1オクテット)単位で分割していくと、

```
11110001 f1
11100011 e3
11000010 c2
11100101 e5
11110010 f2
00111010 3a
01101011 6b
10100000 a0
10101011 ab
10010000 90
11110100 f4
1　      ff
```

になります。
ハフマンコーディングは中途半端なオクテットで終わる場合があるので、その場合は上記のように最後の中途半端なビットを全て1で埋めます。

このハフマンコーディングされたリテラル文字列は12バイトです。
なので、レングスはHビットを立てて12で「8c」になります。

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 | 0   0   0   1   1   0   0 |
+---+---------------------------+
|  f1  e3 c2 .......            |
+-------------------------------+
```

ハフマンコーディングの原理は[こちらのエントリ](http://qiita.com/iwanaga/items/98f60003c0114e04095e)がとても分かりやすかったです。


# ヘッダーフィールドの表現方法

ここまで整数を表現する方法と文字列を表現する方法が分かりました。
HTTP2のヘッダ表現ではこれをそのまま使うわけではなく、その前にヘッダフィールドの表現方法を指定します。

その方法は4種類です。

| 表現方法| フィールド名 | フィールド値 | 動的テーブル更新 | その他 |
|:-------|----------:|:------------:|:------------:|:------------:|
| インデックスヘッダフィールド表現 | 番号指定 | 番号指定 |なし| 名前と値をセットで1つの番号で指定する場合に使用する表現|
| インデックス更新を伴うリテラルヘッダフィールド | 番号指定か文字列 | 文字列かハフマンコーディング |あり||
| インデックス更新を伴わないリテラルヘッダフィールド | 番号指定か文字列 | 文字列かハフマンコーディング |なし||
| インデックスされないリテラルヘッダフィールド | 番号指定か文字列 | 文字列かハフマンコーディング |なし|テーブル更新なしをプロキシにも強制|


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

静的テーブルにあらかじめキーだけでなくバリューまで決められている場合に、それをインデクス指定するだけで使えます。
その場合に使う方法です。

例えば次のものは静的テーブルに定義されています。

```
2 :method GET
3 :method POST
4 :path /
5 :path /index.html
```

この場合の表現は次のフォーマットです。
7ビットプレフィックスの整数表現が使えます。

```
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+
```

例えば「:method GET」を表現すると、

```
10000010  →　x82
```

です。

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

動的テーブルを更新してほしい場合に使う表現方法です。
キー名を番号指定する場合は次のフォーマットです。
6ビットプレフィックスの整数表現が使えます。

```
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```


例えば「:method GET」をハフマンコーディングなしで表現すると、

```
x42 x03 x47 x45 x54
```

になります。
その理由は、

```
01000010  →　x42    // 静的テーブルの2番 :methodを指定
00000011  →  x03    // GETの長さ３を指定
0x47 0x45 0x54      // GETをオクテットで書く
```

です。

キー名も文字列で書く場合は次のフォーマットです。
動的テーブルにまだ存在しない新しい名前はこのフォーマットで書く必要があります。

```
+---+---+---+---+---+---+---+---+
| 0 | 1 |           0           |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

例えば「:method GET」をハフマンコーディングなしで表現すると、

```
x40 x07 x3a x6d x65 x74 x68 x6f x64 x03 x47 x45 x54
```

になります。
その理由は、

```
01000000  →　x40    // キー名にインデクスを使わない
00000111  →  x07    // :methodの長さ7を指定
x3a x6d x65 x74 x68 x6f x64       // :methodをオクテットで書く
00000011  →  x03    // GETの長さ３を指定
0x47 0x45 0x54      // GETをオクテットで書く
```

です。


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

動的テーブルを更新しなくていい場合に使うフォーマットです。
上の方法が理解できれば、最初のオクテットの上位4ビットを0にするだけという違いしかありません。

キー名を番号指定する場合は次のフォーマットです。
4ビットプレフィックスの整数表現が使えます。

```
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

例えば「:method GET」をハフマンコーディングなしで表現すると、

```
x02 x03 x47 x45 x54
```

になります。
その理由は、

```
00000010  →　x02    // 静的テーブルの2番 :methodを指定
00000011  →  x03    // GETの長さ３を指定
0x47 0x45 0x54      // GETをオクテットで書く
```

です。


キー名も文字列で書く場合は次のフォーマットです。
動的テーブルにまだ存在しない新しい名前はこのフォーマットで書く必要があります。

```
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

例えば「:method GET」をハフマンコーディングなしで表現すると、

```
x00 x07 x3a x6d x65 x74 x68 x6f x64 x03 x47 x45 x54
```

になります。
その理由は、

```
00000000  →　x00    // キー名にインデクスを使わない
00000111  →  x07    // :methodの長さ7を指定
x3a x6d x65 x74 x68 x6f x64       // :methodをオクテットで書く
00000011  →  x03    // GETの長さ３を指定
0x47 0x45 0x54      // GETをオクテットで書く
```

です。


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

上記の「インデックス更新を伴わないリテラルヘッダフィールド」の開始ビットが「0001」になるだけです。


# けっきょくどれを使えばいいのか？

バリエーションとしては次のようになります・

| 番号|表現|キー名インデクス指定|ハフマンコーディング|
|:-------|:-------|:-------|:-------|
|1|インデックスヘッダフィールド|-|-|
|2|インデックス更新を伴うリテラルヘッダフィールド |あり|あり(値だけ)|
|3|インデックス更新を伴うリテラルヘッダフィールド |あり|なし|
|4|インデックス更新を伴うリテラルヘッダフィールド |なし|あり(キーと値両方)|
|5|インデックス更新を伴うリテラルヘッダフィールド |なし|なし|
|6|インデックス更新を伴わないリテラルヘッダフィールド|あり|あり(値だけ)|
|7|インデックス更新を伴わないリテラルヘッダフィールド|あり|なし|
|8|インデックス更新を伴わないリテラルヘッダフィールド|なし|あり(キーと値両方)|
|9|インデックス更新を伴わないリテラルヘッダフィールド|なし|なし|
|10|インデックスされないリテラルヘッダフィールド|あり|あり(値だけ)|
|11|インデックスされないリテラルヘッダフィールド|あり|なし|
|12|インデックスされないリテラルヘッダフィールド|なし|あり(キーと値両方)|
|13|インデックスされないリテラルヘッダフィールド|なし|なし|

どれを使っても問題なく通信できます。
上のものほど圧縮率が高いです。
なので、上のものが使えるのなら使った方が効率がいいです。

例えば、今から送ろうとしているヘッダーフィールドが、次の条件を満たしている場合、

| 条件|
|:-------|
|静的テーブルか動的テーブルに存在する|
|キーとバリューがセットで定義されている|

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

を使います。
テーブルのインデクスで指定するだけです。

そうでない場合は、キー名だけでもインデクス指定できて、値にハフマンコーディングが使えるならば(使うのが通常だけど何かの理由で使いたくない場合もある)、

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

になります。

つまりインデクス指定できるならした方が良く、圧縮できるならした方が良く、動的テーブルを使えるなら使った方が良いです。


上記はあくまで効率を考えた場合です。
セキュリティ上の問題を考慮する場合は、圧縮せずに下の方のものをあえて使う選択肢があります。
詳しくはドラフトの[こちら](http://syucream.github.io/hpack-spec-ja/header-compression-10-ja.html#Security)をご覧ください。


# 平文で送りたい
難しいことは後で勉強するからとりあえず平文で送らせてくれ、という方は、

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

を使います。

上で説明した

「:method GET」が、

```
x00 x07 x3a x6d x65 x74 x68 x6f x64 x03 x47 x45 x54
```

になるパターンです。
最初にx00から開始して、フィールド名「:method」の長さを書いて(x07)、フィールド名(:method)を文字列で書きます(x3a x6d x65 x74 x68 x6f x64)。
次に値「GET」の長さ(x03)を書いて、フィールドの値(GET)を文字列で書きます(x47 x45 x54)。

これを連結させていって送りつけるだけです。
次のフィールドはまた最初にx00から開始して、長さと文字列を書きます。

ただし、上の例は文字列の長さが7ビット(127)に収まる場合です。
フィールド名や値が127文字以上の場合は整数表現にしたがって次のオクテットを消費して表現する必要があるので注意してください。

また、平文で送っても返ってくるレスポンスのヘッダーは圧縮されている可能性が高いです。


# 動的テーブルのサイズ更新

Settingフレームで動的テーブルのサイズが変わった場合は、ヘッダーフィールド表現の前に次のデータを送信します。
5ビットプレフィックスの整数表現が使えます。

```
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 |   Max size (5+)   |
+---+---------------------------+
```

サイズが縮小された場合は、溢れたデータは削除されます。