探索HTTP/2: HPACK協(xié)議簡述
探索HTTP/2系列的第一篇文章已經(jīng)介紹了HTTP 2協(xié)議，本文則將簡述用于HTTP/2頭部壓縮的
HPACK協(xié)議。(2016.10.01最后更新)
1. 基本原理
HPACK頭部壓縮的基本原理就是使用索引表和
Huffman編碼。在壓縮(編碼)與解壓(解碼)過程，可將指定的頭部字段(包含字段名與字段值)存儲(chǔ)在索引表中。索引表中的每一個(gè)條目由索引(一個(gè)整數(shù))，字段名和字段值組成。對(duì)于存在索引表中的頭部字段，在編碼時(shí)可以僅使用索引作為該字段的代表，在解碼時(shí)通過該索引從表中查找出對(duì)應(yīng)的字段。對(duì)于其它的字符串，則可以使用Huffman編碼進(jìn)行壓縮。
1.1 索引表
索引表由靜態(tài)表與動(dòng)態(tài)表組成。靜態(tài)表由HPACK協(xié)議預(yù)定義的61個(gè)常用的頭部字段組成，其中大部分字段的值為空。靜態(tài)表是只讀的，其中的條目及其位置均不可更改。HPACK協(xié)議中的
附錄A列出了全部的靜態(tài)表?xiàng)l目。動(dòng)態(tài)表也由一系列頭部字段組成，但其中的元素不固定，在實(shí)際操作中可以插入新的條目，也允許刪除已有的條目。
HPACK協(xié)議要求靜態(tài)表與動(dòng)態(tài)表合并在同一個(gè)存儲(chǔ)空間中，其中靜態(tài)表置于前部，動(dòng)態(tài)表緊隨其后。那么在整個(gè)索引表空間中，動(dòng)態(tài)表的第一個(gè)條目的索引將是62。動(dòng)態(tài)表的維護(hù)原則是先進(jìn)先出(FIFO)。當(dāng)向動(dòng)態(tài)表中增加條目時(shí)，將總是從第62位插入，原有的條目將全部向右移動(dòng)一個(gè)位置。當(dāng)從動(dòng)態(tài)表中刪除條目時(shí)，將總是從最后一位進(jìn)行刪除。
雖說，協(xié)議要求將靜態(tài)表與動(dòng)態(tài)表合并在一起，但這只是邏輯上的要求。只要?jiǎng)討B(tài)表的索引是從62開始，那么各個(gè)實(shí)現(xiàn)可以根據(jù)自己的喜好自由地使用存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。比如，可以將靜態(tài)表單獨(dú)放在一個(gè)不可變的數(shù)組中，而動(dòng)態(tài)表由另一個(gè)鏈表進(jìn)行存儲(chǔ)，這樣可能會(huì)便于插入和刪除條目。只不過，這個(gè)鏈表中元素的下標(biāo)與動(dòng)態(tài)表中條目的索引之間相差62。
(動(dòng)態(tài))索引表中的條目允許重復(fù)。
1.2 Huffman編碼
Huffman編碼是一種用于無損數(shù)據(jù)壓縮的權(quán)路徑編碼算法。在使用該算法時(shí)，需要一張所有被編碼字符的權(quán)重(出現(xiàn)頻率)代碼表。在對(duì)大量的HTTP頭部樣本進(jìn)行統(tǒng)計(jì)之后，得出了一份適用于HPACK的Huffman代碼表，由協(xié)議中的
附錄B列出。
必須注意的是，HPACK協(xié)議并不要求該協(xié)議的實(shí)現(xiàn)一定要使用索引表，即便某個(gè)字段已經(jīng)存在于索引表中了。而且也不要求一定要對(duì)字符串實(shí)施Huffman壓縮。也就是說，理論上，在編碼時(shí)可以不對(duì)頭部字段進(jìn)行任何形式的壓縮，而只需將所有的字符轉(zhuǎn)化成字節(jié)形式。
2. 基本數(shù)據(jù)類型表示法
HPACK協(xié)議使用的基本數(shù)據(jù)類型只有兩種：整數(shù)；字符串。該協(xié)議使用整數(shù)去表示索引和字符串的長度。頭部字段名和值中出現(xiàn)的數(shù)字，只會(huì)被當(dāng)作字符串進(jìn)行處理。
2.1 整數(shù)表示法
HPACK在表示整數(shù)時(shí)并不是把它簡單的轉(zhuǎn)換成二進(jìn)制形式。因?yàn)镠PACK希望每一個(gè)整數(shù)的表示能夠從某個(gè)8比特位字節(jié)(octet，下文將其簡寫為"字節(jié)")中的任何一個(gè)比特位開始，但總是要在某個(gè)字節(jié)的最后一個(gè)比特位結(jié)束。比如表示127，讓它從字節(jié)的第一個(gè)比特位開始填充，肯定會(huì)在最后一個(gè)比特位結(jié)束，如下圖所示：
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
如果第一個(gè)比特位被其它值占用(用"?"代表)，只能從第二個(gè)比特位開始填充呢？結(jié)果依然只需要一個(gè)字節(jié)，如下所示：
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| ? | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
但如果是從第三個(gè)比特位開始填充呢？這時(shí)會(huì)發(fā)現(xiàn)一個(gè)字節(jié)已經(jīng)不夠了，必須要第二個(gè)字節(jié)。但能否表示成如下形式呢？
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| ? | ? | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+-------------------+
| 1 | ? | ? | ? | ? | ? | ? | ? |
+---+---+---+---+---+---+---+---+
這顯然不符合HPACK協(xié)議的要求，因?yàn)樗Ｍ軌蛟谀硞€(gè)字節(jié)的最后一個(gè)比特位結(jié)束這個(gè)表示。為達(dá)到這一目的，HPACK協(xié)議設(shè)計(jì)出了一種如下圖所示的表示法，
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| ? | ? | 1 | 1 1 1 1 1 |
+---+---+---+-------------------+
| 1 | Value-(2^N-1) LSB |
+---+---------------------------+
...
+---+---------------------------+
| 0 | Value-(2^N-1) MSB |
+---+---------------------------+
第一個(gè)字節(jié)中能夠被用來填充整數(shù)表示位的比特位數(shù)(上圖中的為6)被稱為prefix。下面是該表示法的Java語言實(shí)現(xiàn)，
public void encodeInteger(int value, int prefix) {
if (value >> prefix <= 0) {
printBinary(value);
} else {
int number = (1 << prefix) - 1;
printBinary(number);
for (value -= number; value >= 128; value /= 128) {
printBinary(value % 128 + 128);
}
printBinary(value);
}
}
private void printBinary(int value) {
System.out.println(String.format("%8s", Integer.toBinaryString(value)).replace(" ", "0"));
}
根據(jù)上述算法可知，當(dāng)prefix為6時(shí)，127的表示法如下圖所示：
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| ? | ? | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+-------------------+
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+-------------------+
2.2 字符串表示法
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| H | String Length (7+) |
+---+---------------------------+
| String Data (Length octets) |
+-------------------------------+
HPACK協(xié)議使用上圖展示的表示法，它由三部分組成：
[1]Huffman標(biāo)志，表示該字符串是否為Huffman編碼，占用一個(gè)比特位。
[2]字符串長度，一個(gè)使用2.1節(jié)所述方法表示的整數(shù)，其中prefix為7。
[3]字符串值。若Huffman標(biāo)志為0，該值就是原始字符串的字節(jié)，否則該值是經(jīng)Huffman編碼過的數(shù)據(jù)。由于經(jīng)Huffman編碼過的數(shù)據(jù)并不總是能在一個(gè)字節(jié)的最后一個(gè)比特位處結(jié)束，所以可能會(huì)使用EOS(end-of-string)符號(hào)進(jìn)行填充。
3. 頭部字段表示法
有了第2節(jié)介紹的基本數(shù)據(jù)類型的表示法作為基礎(chǔ)，現(xiàn)在就可以闡述頭部字段的表示法了。HPACK協(xié)議將字段表示法分成3種類型。在表示法開頭有一個(gè)或若干個(gè)比特位用于表示類型。
3.1 已在索引表的頭部字段
類型標(biāo)識(shí)占用1個(gè)比特位，值為1。索引使用prefix為7的整數(shù)表示法。在解碼時(shí)，不會(huì)更新動(dòng)態(tài)表。
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Index (7+) |
+---+---------------------------+
3.2 將置入索引表的頭部字段
類型標(biāo)識(shí)占用2個(gè)比特位，值為01。在解碼時(shí)，會(huì)向動(dòng)態(tài)表內(nèi)插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為6的整數(shù)表示法，而字段值使用字符串表示法。
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個(gè)字節(jié)的后6個(gè)比特位均使用0填充。
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) |
+-------------------------------+
3.2 暫不置入索引表的頭部字段
類型標(biāo)識(shí)占用4個(gè)比特位，值為0000。在解碼時(shí)，不向動(dòng)態(tài)表內(nèi)插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為4的整數(shù)表示法，而字段值使用字符串表示法。
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個(gè)字節(jié)的后4個(gè)比特位均使用0填充。
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) |
+---+---------------------------+
3.3 永不置入索引表的頭部字段
類型標(biāo)識(shí)占用4個(gè)比特位，值為0001。在解碼時(shí)，不向動(dòng)態(tài)表內(nèi)插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為4的整數(shù)表示法，而字段值使用字符串表示法。
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個(gè)字節(jié)的后4個(gè)比特位均使用0填充。
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) |
+-------------------------------+
可以發(fā)現(xiàn)，3.2節(jié)與3.3節(jié)中的表示法除了類型標(biāo)識(shí)不同之外，其它的都完全相同。那么它們的區(qū)別是什么呢？類型0000表示的字段在經(jīng)過多次解碼與編碼時(shí)，可能會(huì)被某個(gè)中介者置入索引表中。而類型0001表示法強(qiáng)調(diào)了該字段無論在任何時(shí)候都不可置入索引表。類型0001可用于表示包含有敏感信息，如密碼，的字段值，以避免對(duì)這些值進(jìn)行壓縮時(shí)產(chǎn)生的風(fēng)險(xiǎn)。
4. 動(dòng)態(tài)表的管理
動(dòng)態(tài)表中的條目被認(rèn)為是有尺寸的，其計(jì)算公式為：字段名的字節(jié)長度+字段值的字節(jié)長度+32。字段名/值的長度是指它們的原始字節(jié)的長度，而非經(jīng)過Huffman編碼后的字節(jié)的長度。
動(dòng)態(tài)表的尺寸就是其中所有條目的尺寸之和。動(dòng)態(tài)表的最大尺寸是有限的，可以通過下面的整數(shù)表示法來通知協(xié)議的現(xiàn)實(shí)去改變動(dòng)態(tài)表的最大尺寸。
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | Max size (5+) |
+---+---------------------------+
當(dāng)插入新的條目或改變動(dòng)態(tài)表的最大尺寸時(shí)，可能導(dǎo)致已有的一個(gè)或多個(gè)條目被逐出，甚至清空整個(gè)動(dòng)態(tài)表。將動(dòng)態(tài)表的最大尺寸設(shè)置為0是合法的，實(shí)際上，這是一種常用的清空動(dòng)態(tài)表的途徑。