去年五月， IETF 正式发布了 HTTP/2 协议与之配套的 HPACK 头部压缩算法。 RFC 如下:
笔者在研究 HPACK 时，翻阅了部分网上的博客与教程，不甚满意。要么泛泛而谈，要么漏洞百出，要么讲解不够完整。于是，笔者研读了 RFC7541 ，希望能写出一篇完备的 HPACK 讲解，给想要学习这个算法的朋友一些帮助。
如有不足或者疑惑之处，欢迎大家指出。
HPACK的由来
HTTP1.X 由于其设计的缺陷，被大家诟病已久，其中头疼的问题之一，就是无意义的重复的头部。
于是出现了各种各样的解决方案， 如 Google 直接在 HTTP1.X 的基础上设计了 SPDY 协议， 对头部使用 deflate 算法进行压缩，一并解决了多路复用和优先级等问题。
而 HTTP/2 的实现就是参考了 SPDY 协议， 但是专门为头部压缩设计了一套压缩算法，就是我们的 HPACK 。
HPACK的实现
基本原理
简单的说，HPACK 使用2个索引表(静态索引表和动态索引表)来把头部映射到索引值，并对不存在的头部使用 huffman 编码，并动态缓存到索引，从而达到压缩头部的效果。
实现细节
HPACK 中有2个索引表，分别是静态索引表和动态索引表。
静态索引表
是预先定义在 RFC 里的固定的头部，这里展示部分:
| 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 | |
| 16 | accept-encoding | gzip, deflate |
| ... | ... | ... |
也就是说当要发送的值符合静态表时，用对应的 Index 替换即可，这样就大大压缩了头部的大小。
当然，这个表是预先定义好的，只有固定的几十个值，如果遇到不在静态表中的值，就会用到我们的动态表。
动态索引表
动态表是一个由先进先出的队列维护的有空间限制的表，里面同样维护的是头部与对应的索引。
每个动态表只针对一个连接，每个连接的压缩解压缩的上下文有且仅有一个动态表。
什么是连接，抽象的说是HTTP依赖的可靠的传输层的连接，一般来说指的是一个TCP连接。 HTTP/2 中引入了多路复用的概念，对于同一个域名的多个请求，会复用同一个连接。
那么动态表就是，当一个头部没有出现过的时候，会把他插入动态表中，下次同名的值就可能会在表中查到到索引并替换掉头部。为什么我说是可能呢，因为动态表是有最大空间限制的。
动态表的大小 = (每个 Header 的字节数的和+32) * 键值对个数
为什么要加32呢，32是为了头所占用的额外空间和计算头被引用次数而估计的值。
而动态表的最大字节数由 HTTP/2 的 SETTING 帧中的 SETTINGS_HEADER_TABLE_SIZE 来控制。
同时压缩时，可以插入一个字节来动态的修改动态表的大小，但是不可以超过上面预设的值。这个下面会介绍。
那么动态表是如何管理大小呢，2种情况下，动态表会被修改：
- 压缩方用上述方式要求动态修改动态表的大小。在这种情况下，如果新的值更小，并且当前大小超过了新值，就会从旧至新，不断的删除头，直到小于等于新的大小。
- 收到或发出一个新的头部，会触发插入和可能的删除操作。 RFC 里面说的比较复杂，我用等价的语义解释一下。新的值被插到队首，一样从旧到新删除直到空间占用小于等于最大值。那么在这种情况下，如果新来的头比最大值还要大，就等于变相的清除了动态表。
动态索引表中最新的值是索引值最小的，最旧的值是索引值最大的。
动态表与静态表共同组成了索引表的索引空间。
索引空间
索引空间就是动态表和静态表组成的头部与索引的映射关系。这个看起来很高深，实际上很简单。
静态表的大小现在是固定的 61， 因此静态表就是从1到61的索引，然后动态表从新到旧，依次从62开始递增。这样就共同的组成了一个索引空间，且互不冲突。
如果以后静态表扩充了，依次往后推即可。
编码解码
无符号整数编码
在 HPACK 中，经常会用一个或者多个字节表示无符号整数。在 HPACK 中一个无符号整数，并不总是在一个字节的开始，但是总是在一个字节的末尾结束。
这么说有些抽象，什么叫不是一个字节的开始。如下所示:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | Value |
+---+---+---+-------------------+
0-2 bit可能会用于其他的标识， 那么表达数值只占了5个 bit , 因此只能表示2^5-1，因此当需要表达的数值小于32时，一个字节足够表达了，如果超过了2^n-1以后，剩下的字节是如何编码的呢:
0 1 2 3 4 5 6 7
+-------+---+---+---+---+---+---+---
| (0/1) | ? | ? | ? | ? | ? | ? | ? |
+-------+---+---+---------------+---
第一个字节的 n 个 bit 全部置1，然后假设这个数为 i,
那么remain = i - (2^n - 1);然后用剩余的字节表示这个 remain 值，然后首 bit 标识是否是最后一个字节，1表示不是，0表示是。
去掉首字节，就类似于用7个 bit 的字节的小端法表示无符号整数 remain 。
一个整数0x12345678用标准的 byte 数组 buffer 用小端法表示就是:
buffer[0] = 0x78；
buffer[1] = 0x56;
buffer[3] = 0x34;
buffer[3] = 0x12;
那么我们整体的字节表示无符号数 i 的伪代码如下:
if I < 2^N - 1, encode I on N bits
else
encode (2^N - 1) on N bits
I = I - (2^N - 1)
while I >= 0x7f
encode (I & 0x7f | 1 << 7) on 8 bits
I = I >> 7
encode I on 8 bits
同样，解码的伪代码如下:
decode I from the next N bits
if I < 2^N - 1, return I
else
M = 0
repeat
B = next octet
I = I + (B & 0x7f) * (1 << M)
M = M + 7
while (B >> 7) & 1
return I
那么举例如果我们用 3 个 bit 作为前缀编码，
5 = ?????101
(101b = 5)
8 = ?????111 00000001
(111b + 1 = 8)
135 = 7 + 128 = ?????111 10000000 00000001
(111b + 0 + 128 * 1 = 135)
字面字符串编码
有了无符号整数编码的基础，我们可以对字符串进行编码，如下所示:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| H | String Length (7+) |
+---+---------------------------+
| String Data (Length octets) |
+-------------------------------+
H : 表示是否是 huffman 编码，1 是 0 不是
StringLength : 表示随后跟随的字符串的长度，用上述的整数编码方式编码
StringData: 如果是 huffman 编码，则使用 huffman 编码后的字符串，否则就是原始串。
静态HUFFMAN编码
先简单介绍一下 huffman 编码，huffman 编码是一个根据字符出现的概率重新编排字符的二进制代码，从而压缩概率高的字符串，进而压缩整个串的长度。如果不了解的话，建议先去学习一下，这里不再赘述。
这里的 huffman 编码是静态的，是根据过去大量的 Http 头的数据从而选出的编码方案。整个静态表在这里 http://httpwg.org/specs/rfc7541.html#huffman.code
二进制编码
有了上述所有的准备，我们就可以真正的进行二进制编码压缩了。
有以下几种类型的字节流:
1 已被索引的头部
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Index (7+) |
+---+---------------------------+
已被索引的头部，会被替换成如上格式:
第一个 bit 为1， 随后紧跟一个 无整数的编码表示 Index，即为静态表或者是动态表中的索引值。
2.1 name在索引 value不在索引且允许保存
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
第一个字节的前两个 bit 为 01，随后 无符号整数编码 Index 表示 name 的索引。
下面紧随一个字面字符串的编码，表示 value 。
这个 Header 会被两端都加入动态表中。
2.2 name, value都没被索引且允许保存
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) |
+-------------------------------+
第一个字节为01000000, 然后紧随2个字面字符串的编码表示。
这个 Header 会被两端都加入动态表中。
3.1 name被索引， value未索引且不保存
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
第一个字节前四个 bit 为 0000， 随后是一个 无符号整数编码的 Index 表示 name ，然后跟随一个字面字符串编码 value 。
这个 Header 不用加入动态表。
3.2 name, value都未被索引且不保存
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) |
+-------------------------------+
第一个字节为全0，紧跟2个字面字符串编码的 name 和 value 。
这个 Header 不用加入动态表。
4.1 name在索引表中， value不在，且绝对不允许被索引
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
和3.1是类似的，只是第一个字节第四个 bit 变成了1， 其他是一样的。
这个和3.1的区别仅仅在于，中间是否通过了代理。如果没有代理那么表现是一致的。如果中间通过了代理，协议要求代理必须原样转发这个 Header 的编码，不允许做任何修改，这个暗示中间的代理这个字面值是故意不压缩的，比如为了敏感数据的安全等。而3.1则允许代理重新编码等。
4.2 name 和 value 都不在索引表中，且绝对不允许被索引
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) |
+-------------------------------+
和3.2类似，只是第一个字节的第4个 bit 修改为1。
对此的解释同4.1。
5 修改动态表的大小
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | Max size (5+) |
+---+---------------------------+
和前面的不一样，之前的都是传送数据,这个是用来做控制动态表大小的。
第一个字节前三个 bit 为001， 随后跟上一个无符号整数的编码 表示动态表的大小。上文有提过，这个数值是不允许超过 SETTINGS_HEADER_TABLE_SIZE 的， 否则会被认为是解码错误。
解码状态机
我们都知道，想要正确无误的解码，每个编码都要满足一个条件，就是每种编码方式，都不是另外一个编码的前缀。这里的 HPACK 的编码的最小单位是字节。我们看一下整个二进制流解码的状态机:
HPACK 解码状态机
图例的根据对应规则解码就是上面介绍的编码规则。
实战举例
以下是要被编码的 Headers:
:method: GET
:scheme: http
:path: /
:authority: www.example.com
这里大概说一下， :xxxx 为 name 的 header， 实际上是 HTTP/2 所谓的伪头的概念。就是把HTTP1.X的请求头替换成伪头对应的 name 和 value，然后再编码传输，完全的定义在这里 http://httpwg.org/specs/rfc7540.html#PseudoHeaderFields
好的，过掉整个话题，我们看整个 Headers 编码后的16进制字节如下:
8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff
其实解析很简单，就按照上面我画的解码状态机来就好了:
82 = 10000010 -> 静态表Index = 2 -> :method: GET
86 = 10000110 -> 静态表Index = 6 -> :scheme: http
84 = 10000100 -> 静态表Index = 4 -> :path: /
41 = 01000001 -> name = 静态表1 = :authority
接着是一个字面字符串的解码,表示 header :authority 对应的 value
8c = 10001100 -> 第一个 bit 为1，表示 huffman 编码，字符串的长度为 1100b = 12
接着解析12个字节为 huffman 编码后的字符
f1e3 c2e5 f23a 6ba0 ab90 f4ff， 查表可知为www.example.com
从而得到最后一个头部 :authority: www.example.com
小结
好的，至此我们的 HPACK 完全解析已经结束了，希望大家能通过本文对 HPACK 有更深入的了解。后面我会继续填坑，给大家带来 HTTP/2 与 OkHttp 对应的实现。
这里是笔者的个人博客地址: dieyidezui.com
也欢迎关注笔者的微信公众号，会不定期的分享一些内容给大家
网友评论