<-- 返回首页

RFC 7541, HTTP2 头部压缩

1. 介绍

RFC 7541 规定了 HTTP2.0 的头部压缩方法,称为 HPACK。

1.1 概述

http2 头部的各个域被看作是一个个键值对的有序集合,而且允许重复。键和值都用字节表示,并且各个域的顺序都是固定的。

头部域组成一张表,将各个域映射到对应的值上,表中的成员可以动态的增长。

被重新编码以后,头部各个域要么是用字符串表示,或者用表中的 index 表示,所以,给定一个头部域的列表,里面可能同时混合了两种表示方式。

字符串要么是直接编码,要么是霍夫曼编码。

编码器决定如何编码,例如决定是否把一个域作为新的成员插入表中。解码器负责解码。具体的例子可以参考 Appendix C 。

1.2 惯例 (略)

1.3 术语

Header Field, 键值对。键和值都用字节表示。

Dynamic Table, (2.3.2 节)用 index 存头部各个域,它的内容会根据用户使用场景的编码和解码的不同而变换。

Static Table, (2.3.1 节)把最常用的头部字段编成一张静态表,不同的请求之间可以共享。表中内容有序,并且只读。

Header List, 头部域的有序集合,http2 header block 的完整内容都在这个 list 里面。

Header Field Representaion, (2.4 节)头部域的表示,字符或者 index。

Header Block, 头部域的表示的有序集合,当它被解码之后,能生成一个完整的头部域列表。

2. 压缩过程

本文不会详细介绍压缩算法,而是简单介绍编码器/解码器应该如何配合工作。

2.1 Header List 的顺序

HPACK 压缩算法保留了 header list 中各个域的原始顺序。所以 编码器必须严格的按照 header list 中的顺序,将 header field representation 编码到 header block 中。

2.2 解码和编码

为了解压缩 header blocks,解码器只需要维护一份动态表(dynamic table)即可。当全双工通信时,通信双方各自维护一份动态表。

2.3 索引表(indexing table)

HAPCK 算法使用两张表去索引 header field。静态表用于记录预定义的各种头部域,动态表记录本次会话的特有的一些 field 信息。

2.3.1 静态表 (Static table)

记录预定一个各个头部域,详见 Appendix A。

2.3.3 动态表 (Dynmic table)

表中各项按照 FIFO “先来先进” 的顺序记录,最新的条目在列表的最底部。初始时表的内容为空,随着不断解压缩 header block,新的条目不断被加入表中。

动态表中允许有重复的内容。

2.3.3 Index Address Space

静态表和动态表组合在一起成为一张完整的表,静态表在前,动态表在后。索引的顺序如下图所示,任何大于 s+k 的值都是错误的,会触发一个 decoding error。

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

                       Figure 1: Index Address Space

2.4 Header Field Representation (我给起的名字叫 头部域标记)

Header Field 由 header field name 和 header field vaule 组成。

一个所谓的 header field name 既可以是一个字符串,也可以是一个数字索引。而 header field vaule 则只能是字符串。

3. 头部块的编码 Header Block Decoding

3.1 Header Block Processingg

解码器顺序的处理头部块,重新构建原始的头部列表。

头部块是一连串的头部域标记(Header Field Representation),不同的头部与标记在 Section 6 中详细描述。一旦头部域被解码并且被加入 header list 之后就不能被删除,因此可以安全的传递给应用程序。

3.2 Header Field Representation Processing (头部域标记处理)

一个 indexed representaion 的标记必须作一下处理:它的头部域对应的 entry 必须已经在静态表或者动态表中,然后加入到 header list 中去。

一个 不加入动态表的 literal representation 需要这样处理:头部域被加入到 header list。

一个 加入动态表的 literal representation 需要这样处理:

  • 头部域加入 header list。
  • 头部域被插入到动态表的顶端,这样做可能会导致已有的条目被删除。(见 Section 4.4)

4. 动态表管理

动态表的存在主要是为了节约内存。

4.1 计算表的大小

动态表的大小 = 总个数 * 每个条目的大小。

条目的大小 = 名字的长度(定义在 Section 5.2),值的长度(都是字节表示), 以及 + 32个字节。

条目大小的计算使用的是它没有被霍夫曼编码过的键-值的长度。

额外的32个字节用途:一个条目使用 2 个 64-bit 的指针指向名字和值,以及2个 64-bit 计数器记录指向名字和值得个数。所以一共会有32 字节的大小。

4.2 最大表的大小

使用 HPACK 的协议自行决定动态表占用内存的最大值,在 HTPP/2 中,这个值是 SETTINGS_HEADER_TABLE_SIZE (详见 HTTP2 Section 6.5.2)

一旦动态表的最大值被改变,需要通过 dynamic table size update 告知(Section 6.3),这样的改变必须发生在第一个 header block 中,并且附上新的最大值。在 HTTP/2协议中,用 settings acknowledgment表示。(详见 HTTP2 Section 6.5.3)

最大值更新可以在两个 header block 之间发生多次,但是只会选择较小的值作为最后的最大值。

当最大值被设置为0的时候,意味着对动态表的清零。

4.3 当有条目被删除时,动态表大小的变化

当动态表的最大值改变时,超过最大值的部分就自动丢弃了。例如一开始动态表中有100个条目,然后最大值更新为50,那么表中的后50个条目自动丢弃。

4.4 新条目加入时,已有的被删除

往动态表中加入新条目时,如果此时表已经满了,那么整个表会自动清零,动态表变成一个空表。

当新条目是引用表中条目时,将它插入一个已满的表可能会导致整个表都被清零(它的引用也无效了),所以在实现的时候要注意这种情况(如何做?)

5. 基本类型的表示

HPACK 使用两种基本类型:无符号可变长度的整数,字节串。

5.1 整数的表示

整数用来表示索引号和值得长度。整数由两部分组成,前缀和值。一个无符号整数,并不总是在一个字节的开始,但是总是在一个字节的末尾结束。举个例子,如果遇到下面这样的表示,

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | ? | ? | ? |       Value       |
   +---+---+---+-------------------+

    Figure 2: Integer Value Encoded within the Prefix (Shown for N = 5)

一个字节中 0-2 bit 用于其他的内容, 那么只剩下了5个 bit , 因此只能表示 2^5-1,因此当需要表达的数值小于32时,就把它直接放在这里,如果超过了32就这样表示:

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

    Figure 3: Integer Value Encoded after the Prefix (Shown for N = 5)

第一个字节的 n 个 bit 全部置1,假设这个数为 i,那么remain = i - (2^n - 1),实际存储的是这个 remian。最左端的一位表示是否是最后一个字节,1表示不是,0表示是。所以实际就是用7个 bit 的字节的小端法表示无符号整数 remain。

编码、解码的具体算法请参考 RFC,貌似很简洁。

5.2 字符串表示

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

                  Figure 4: String Literal Representation

H 表示是否是霍夫曼编码。

6. 二进制格式

6.1 已被索引的头部(Indexed Header Field Representaion)

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 1 |        Index (7+)         |
   +---+---------------------------+

                      Figure 5: Indexed Header Field

已被索引的头部,会被替换成如上格式,第一个 bit 为1, 随后紧跟一个整数的编码表示 Index,即为静态表或者是动态表中的索引值。这个整数有 7bit 的前缀。(Section 5.1)

6.2 字符头部域标记

包含三种类型:已索引、未索引、不能被索引。

6.2.1 带有可增长索引号的字符串头部域

一种是 name 在索引,value 不在索引,且允许保存

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

    Figure 6: Literal Header Field with Incremental Indexing -- Indexed
                                   Name

第一个字节的前两个 bit 为 01,随后 Index 表示 name 的索引。下面紧随一个字面字符串的编码 value 。这个 Header 会被通信两端都加入动态表中。

另一种是 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)  |
   +-------------------------------+

   Figure 7: Literal Header Field with Incremental Indexing -- New Name

第一个字节为 0x01000000, 然后紧随2个字面字符串的编码表示。

6.2.2 没有索引号的字符串头部域

与上面的两种不同的是,下面的这两种都不需要保存到动态表中(虽然他们的格式很相似)。

name被索引, value未索引且不保存

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

      Figure 8: Literal Header Field without Indexing -- Indexed Name

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)  |
   +-------------------------------+

        Figure 9: Literal Header Field without Indexing -- New Name

6.2.3 不可被索引的字符串头部域

同样的道理,他们的格式都与上面类似,不同的只是头部的编码,具体格式参考 RFC。

6.3 动态表大小更新

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 1 |   Max size (5+)   |
   +---+---------------------------+

               Figure 12: Maximum Dynamic Table Size Change

上述的几个格式都是传递数据,而这个是用来控制参数的。

附上一个网上抄来的解码状态机。

state machine

7. 安全性

7.1 探测动态表的状态

HPACK 的目的是减少 HTTP 请求和回复头部传输的数据量。

7.1.1 应用 HPACK 到 HTTP 上

7.1.2 迁移

7.1.3 不索引的字符串

7.2 静态霍夫曼编码

目前还没有针对霍夫曼编码的攻击,不过有一篇很有意思的文章仅作课外阅读 PETAL

7.3 内存消耗

黑客会试图发起恶意请求从而造成内存暴涨,因此 HPACK 会严格限制内存的使用量,例如 4.2 节提到的限制最大表的大小等等。

编码器和解码器会在解析头部域的时候会临时分配一些内存,同样也需要限制最大值。

7.4 实现时的一些限制

实现的时候需要注意整数的最大值,长整数的编码,长字符串的处理可能造成的内存泄漏等。(Section 5.1 和 5.2)

参考链接

  • https://tools.ietf.org/html/rfc7541
  • https://tools.ietf.org/html/rfc7540
  • http://www.jianshu.com/p/f44b930cfcac
  • http://www.wolfcstech.com/2016/10/29/hpack-spec/

<-- 返回首页