John Jiang

探索HTTP/2系列的第一篇文章已經介紹了HTTP 2協議，本文則將簡述用于HTTP/2頭部壓縮的HPACK協議。(2016.10.01最后更新)

1. 基本原理
    HPACK頭部壓縮的基本原理就是使用索引表和Huffman編碼。在壓縮(編碼)與解壓(解碼)過程，可將指定的頭部字段(包含字段名與字段值)存儲在索引表中。索引表中的每一個條目由索引(一個整數)，字段名和字段值組成。對于存在索引表中的頭部字段，在編碼時可以僅使用索引作為該字段的代表，在解碼時通過該索引從表中查找出對應的字段。對于其它的字符串，則可以使用Huffman編碼進行壓縮。
1.1 索引表
    索引表由靜態表與動態表組成。靜態表由HPACK協議預定義的61個常用的頭部字段組成，其中大部分字段的值為空。靜態表是只讀的，其中的條目及其位置均不可更改。HPACK協議中的附錄A列出了全部的靜態表條目。動態表也由一系列頭部字段組成，但其中的元素不固定，在實際操作中可以插入新的條目，也允許刪除已有的條目。
    HPACK協議要求靜態表與動態表合并在同一個存儲空間中，其中靜態表置于前部，動態表緊隨其后。那么在整個索引表空間中，動態表的第一個條目的索引將是62。動態表的維護原則是先進先出(FIFO)。當向動態表中增加條目時，將總是從第62位插入，原有的條目將全部向右移動一個位置。當從動態表中刪除條目時，將總是從最后一位進行刪除。
    雖說，協議要求將靜態表與動態表合并在一起，但這只是邏輯上的要求。只要動態表的索引是從62開始，那么各個實現可以根據自己的喜好自由地使用存儲數據結構。比如，可以將靜態表單獨放在一個不可變的數組中，而動態表由另一個鏈表進行存儲，這樣可能會便于插入和刪除條目。只不過，這個鏈表中元素的下標與動態表中條目的索引之間相差62。
    (動態)索引表中的條目允許重復。
1.2 Huffman編碼
    Huffman編碼是一種用于無損數據壓縮的權路徑編碼算法。在使用該算法時，需要一張所有被編碼字符的權重(出現頻率)代碼表。在對大量的HTTP頭部樣本進行統計之后，得出了一份適用于HPACK的Huffman代碼表，由協議中的附錄B列出。

    必須注意的是，HPACK協議并不要求該協議的實現一定要使用索引表，即便某個字段已經存在于索引表中了。而且也不要求一定要對字符串實施Huffman壓縮。也就是說，理論上，在編碼時可以不對頭部字段進行任何形式的壓縮，而只需將所有的字符轉化成字節形式。

2. 基本數據類型表示法
    HPACK協議使用的基本數據類型只有兩種：整數；字符串。該協議使用整數去表示索引和字符串的長度。頭部字段名和值中出現的數字，只會被當作字符串進行處理。
2.1 整數表示法
    HPACK在表示整數時并不是把它簡單的轉換成二進制形式。因為HPACK希望每一個整數的表示能夠從某個8比特位字節(octet，下文將其簡寫為"字節")中的任何一個比特位開始，但總是要在某個字節的最后一個比特位結束。比如表示127，讓它從字節的第一個比特位開始填充，肯定會在最后一個比特位結束，如下圖所示：
如果第一個比特位被其它值占用(用"?"代表)，只能從第二個比特位開始填充呢？結果依然只需要一個字節，如下所示：
但如果是從第三個比特位開始填充呢？這時會發現一個字節已經不夠了，必須要第二個字節。但能否表示成如下形式呢？
這顯然不符合HPACK協議的要求，因為它希望能夠在某個字節的最后一個比特位結束這個表示。為達到這一目的，HPACK協議設計出了一種如下圖所示的表示法，
第一個字節中能夠被用來填充整數表示位的比特位數(上圖中的為6)被稱為prefix。下面是該表示法的Java語言實現，
根據上述算法可知，當prefix為6時，127的表示法如下圖所示：
2.2 字符串表示法
HPACK協議使用上圖展示的表示法，它由三部分組成：
[1]Huffman標志，表示該字符串是否為Huffman編碼，占用一個比特位。
[2]字符串長度，一個使用2.1節所述方法表示的整數，其中prefix為7。
[3]字符串值。若Huffman標志為0，該值就是原始字符串的字節，否則該值是經Huffman編碼過的數據。由于經Huffman編碼過的數據并不總是能在一個字節的最后一個比特位處結束，所以可能會使用EOS(end-of-string)符號進行填充。

3. 頭部字段表示法
    有了第2節介紹的基本數據類型的表示法作為基礎，現在就可以闡述頭部字段的表示法了。HPACK協議將字段表示法分成3種類型。在表示法開頭有一個或若干個比特位用于表示類型。
3.1 已在索引表的頭部字段
    類型標識占用1個比特位，值為1。索引使用prefix為7的整數表示法。在解碼時，不會更新動態表。
3.2 將置入索引表的頭部字段
    類型標識占用2個比特位，值為01。在解碼時，會向動態表內插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為6的整數表示法，而字段值使用字符串表示法。
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個字節的后6個比特位均使用0填充。
3.2 暫不置入索引表的頭部字段
    類型標識占用4個比特位，值為0000。在解碼時，不向動態表內插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為4的整數表示法，而字段值使用字符串表示法。
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個字節的后4個比特位均使用0填充。
3.3 永不置入索引表的頭部字段
    類型標識占用4個比特位，值為0001。在解碼時，不向動態表內插入新條目。這種類型又被分成兩種情況：
[1]頭部字段名已在索引表中，字段名索引使用prefix為4的整數表示法，而字段值使用字符串表示法。
[2]頭部字段名不在索引表中，字段名和字段值均使用字符串表示法，而第一個字節的后4個比特位均使用0填充。   
    可以發現，3.2節與3.3節中的表示法除了類型標識不同之外，其它的都完全相同。那么它們的區別是什么呢？類型0000表示的字段在經過多次解碼與編碼時，可能會被某個中介者置入索引表中。而類型0001表示法強調了該字段無論在任何時候都不可置入索引表。類型0001可用于表示包含有敏感信息，如密碼，的字段值，以避免對這些值進行壓縮時產生的風險。

4. 動態表的管理
    動態表中的條目被認為是有尺寸的，其計算公式為：字段名的字節長度+字段值的字節長度+32。字段名/值的長度是指它們的原始字節的長度，而非經過Huffman編碼后的字節的長度。
    動態表的尺寸就是其中所有條目的尺寸之和。動態表的最大尺寸是有限的，可以通過下面的整數表示法來通知協議的現實去改變動態表的最大尺寸。
    當插入新的條目或改變動態表的最大尺寸時，可能導致已有的一個或多個條目被逐出，甚至清空整個動態表。將動態表的最大尺寸設置為0是合法的，實際上，這是一種常用的清空動態表的途徑。