在HTTP/1.x时代，支持Body压缩，Header不支持压缩。而现在一个网页可能有几十到上百个请求，一个请求Header至少600Byte以上。那么这些页面的请求Header会消耗不必要的带宽，增加延迟。

在SPDY协议中，SPDY通过使用 DEFLATE 格式，有效的压缩了Headers。但是这种方法暴露了安全风险，比如 CRIME攻击 （轻松实现压缩率信息泄漏）。

在HTTP/2.0中，引入了Header Compression（rfc7541），头部压缩技术使用了HPACK，有效的压缩了Header，同时避免了未知的安全风险。

压缩效果

我们先来看一下HPACK压缩效果。比如说一个简单的HTTP请求，Header大约是 600 Byte，在HTTP/2.0中，首次请求会被压缩到 300 Byte，接着在后续的请求中会被压缩到 30 Byte，首次请求压缩率达到 50%，后续达到 95%。可以说效果是非常明显的，如下图（wireshark抓包）：

压缩原理

HPACK其实包含两个压缩模块：Indexs Table索引表和Static Huffman Encoding静态霍夫曼编码。结构图如下：

接下来我们详细的了解一下它们是如何工作。

Indexs Table

索引表（rfc7541#section-2.3），包含Static Table静态表、Dynamic Table动态表。静态表包含61个预定义的key value，动态表包含自定义的key value。

HPACK使用Static Table、Dynamic Table将Header字段与索引Index相关联，这两个表合并为一个地址空间，用于定义索引值，如下图：

Static Table

静态表（rfc7541#section-2.3.1），包含61个预定义Header key-value，传输的时候使用对应的索引Index替换。静态表内容具体的定义可以参考这里 rfc7541#appendix-A。

          +-------+-----------------------------+---------------+
          | Index | Header Name                 | Header Value  |
          +-------+-----------------------------+---------------+
          | 1     | :authority                  |               |
          | 2     | :method                     | GET           |
          | 3     | :method                     | POST          |
          | 4     | :path                       | /             |
          | 5     | :path                       | /index.html   |
          | 6     | :scheme                     | http          |
          | 7     | :scheme                     | https         |
          | 8     | :status                     | 200           |
          | 9     | :status                     | 204           |
          | 10    | :status                     | 206           |
          | 11    | :status                     | 304           |
          | 12    | :status                     | 400           |
          | 13    | :status                     | 404           |
          | 14    | :status                     | 500           |
          | 15    | accept-charset              |               |
          ...太多了，省略掉了
          | 58    | user-agent                  |               |
          | 59    | vary                        |               |
          | 60    | via                         |               |
          | 61    | www-authenticate            |               |
          +-------+-----------------------------+---------------+

实际传输的时候，是怎么对应的呢？举几个简单的例子：

:method GET = 2 = 00000010
:method POST = 3 = 00000011
:path / = 4 = 00000100
:path /index.html = 5 = 00000101
:scheme https = 7 = 00000111

这些很好理解，那么如果是下面这几个呢？

:authority www.laoqingcai.com 
:path /api/user 
:token xxxxxx

这时候仅仅使用静态表是无法压缩了，轮到Dynamic Table动态表登场了。

Dynamic Table

动态表（rfc7541#section-2.3.2），是一个FIFO队列，初始是空的，它有以下特点：

1. 解压header的时候按需添加，每次添加的时候，放在队首，移除的时候，从队尾开始。

2. 大小不是无限制的，可以通过SETTING Frame里的SETTINGS_HEADER_TABLE_SIZE设置，默认 256Byte。

如上图，每次添加的时候都是在62的位置（因为静态表已经固定61条了），移除的时候都是从结尾开始移除。比如说现在有两个自定义的Header：

:authority www.laoqingcai.com
:token 123456789

那么动态表的变化流程如下：

那么到这里，静态表和动态表已经能存储任何header了。

Static Huffman Encoding

静态霍夫曼编码（rfc7541#appendix-B），HTTP/2.0还支持对String的Key Value进行静态编码，一方面减少了传输字符串的体积，另一方面相当于加密了传书内容。

根据官方 rfc7541#section-7.2 描述，目前还没有针对静态霍夫曼编码的攻击。使用静态霍夫曼编码表创建的信息可能会泄漏，但是攻击者无法利用泄漏的信息来恢复任何有意义的信息。

Huffman Coding

那么什么是霍夫曼编码呢？
霍夫曼编码是一种最小冗余的算法，核心思想就是用短位表示频率大的符号，用长位表示频率小的符号。霍夫曼编码基于霍夫曼树生成的一种编码，那么霍夫曼树是怎么生成的呢？

1. 首先通过大量数据，计算每一项出现的频率，
2. 然后用二叉树的方式来表示这些频率，合并频率最小的两个，组成一个二叉树。
3. 然后继续将上一步得到的二叉树和剩下最小的频率合并，组成二叉树，上一步得到的二叉树作为右节点。
4. 循环步骤3，直到合并成一个二叉树为止。

这样就得到一个最短带权路径的二叉树，也就是最优二叉树。比如下面这个例子：

比如上图，第三步得出最优的二叉树，树的带权路径长度 = 53+53+72+131 = 57。
然后根据霍夫曼树求得霍夫曼编码，为每一个左子节点路径分配编码0，右子节点路径分配编码1，就得到霍夫曼编码了。然后A、B、C、D可以替换成以下的表现形式。

A:0
B:10
C:110
D:111

Static Huffman Encoding

了解了霍夫曼树、霍夫曼编码之后，我们再来看一下HTTP/2.0里的静态霍夫曼编码，引用官当文档 rfc7541#appendix-B 里的一句话：

This Huffman code was generated from statistics obtained on a large sample of HTTP headers

其实和Huffman Coding原理一样，也是通过大量HTTP Header数据样本，分析出来每个字符出现的频率，根据频率生成霍夫曼树，最后得出静态霍夫曼编码表。这里列出部分编码：

    ...省略部分内容
   'B' ( 66)  |1011101                                      5d  [ 7]
   'C' ( 67)  |1011110                                      5e  [ 7]
   'D' ( 68)  |1011111                                      5f  [ 7]
   'E' ( 69)  |1100000                                      60  [ 7]
   'F' ( 70)  |1100001                                      61  [ 7]
   'G' ( 71)  |1100010                                      62  [ 7]
    ...省略部分内容
   'd' (100)  |100100                                       24  [ 6]
   'e' (101)  |00101                                         5  [ 5]
   'f' (102)  |100101                                       25  [ 6]
   'g' (103)  |100110                                       26  [ 6]
   'h' (104)  |100111                                       27  [ 6]
   'i' (105)  |00110                                         6  [ 5]
   'j' (106)  |1110100                                      74  [ 7]
   'k' (107)  |1110101                                      75  [ 7]
   'l' (108)  |101000                                       28  [ 6]
   'm' (109)  |101001                                       29  [ 6]

举个例子，字符h对应100111，相当于8bit压缩成6bit了；字符e对应00101，相当于8bit压缩成5bit。

The Next

通过以上的分析，我们了解到了HTTP/2.0 HPACK压缩的核心实现，下一篇 我们继续了解HPACK实际压缩的过程。

参考链接

rfc1951 - DEFLATE

rfc7541 - Header Compression for HTTP/2