探索HTTP/2: HPACK协议简述(原)

标签: http hpack 协议 | 发表时间:2016-09-24 20:29 | 作者:John Jiang
出处:http://www.blogjava.net/
探索HTTP/2: HPACK协议简述
在本系列的第一篇文章中已经介绍了HTTP 2协议,本文则将简述用于HTTP/2头部压缩的 HPACK协议。(2016.09.24最后更新)

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,让它从字节的第一个比特位开始填充,肯定会在最后一个比特位结束,如下图所示:
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
但如果第一个比特位被其它值占用(用"?"代表),只能从第二个比特位开始填充呢?结果依然只需要一个字节,如下所示:
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
但如果是从第三个比特位开始填充呢?这时会发现一个字节已经不够了,必须要第二个字节。但能否表示成如下形式呢?
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+-------------------+
| 1 | ? | ? | ? | ? | ? | ? | ? |
+---+---+---+---+---+---+---+---+
这显然不符合HPACK协议的要求。它希望(至多)能够在第二个字节的最后一个比特位结束这个表示。为达到这一目的,HPACK协议设计出了一种如下图所示的表示法,
  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      |
+---+---------------------------+
第一个字节中能够被用来填充整数表示位的比特位数(上图中的为6)被称为prefix。下面是该表示法的Java语言实现,
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"));
}
根据上述算法可知,当prefix为6时,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协议使用上图展示的表示法,它由三部分组成:
[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的整数表示法。在解码时,不会更新动态表。
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+
3.2 头部字段将置入索引表
    类型标识占用2个比特位,值为01。在解码时,会向动态表内插入新条目。这种类型又被分成两种情况:
[1]头部字段名已在索引表中,字段名索引使用prefix为6的整数表示法,而字段值使用字符串表示法。
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
[2]头部字段名不在索引表中,字段名和字段值均使用字符串表示法,而第一个字节的后6个比特位均使用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 头部字段不置入索引表
    类型标识占用4个比特位,值为0000。在解码时,不向动态表内插入新条目。这种类型又被分成两种情况:
[1]头部字段名已在索引表中,字段名索引使用prefix为4的整数表示法,而字段值使用字符串表示法。
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
[2]头部字段名不在索引表中,字段名和字段值均使用字符串表示法,而第一个字节的后4个比特位均使用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 头部字段永不使用索引表
    类型标识占用4个比特位,值为0001。在解码时,不向动态表内插入新条目。这种类型又被分成两种情况:
[1]头部字段名已在索引表中,字段名索引使用prefix为4的整数表示法,而字段值使用字符串表示法。
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
[2]头部字段名不在索引表中,字段名和字段值均使用字符串表示法,而第一个字节的后4个比特位均使用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)  |
+-------------------------------+
    可以发现,3.2节与3.3节中的表示法除了类型标识不同之外,其它的都完全相同。那么它们的区别是什么呢?类型0000表示的字段在经过多次解码与编码时,可能会被某个中介者置入索引表中。而类型0001表示法强调了该字段无论在任何时候都不可置入索引表。类型0001可用于表示包含有敏感信息,如密码,的字段值,以避免对这些值进行压缩时产生的风险。

4. 动态表的管理
    动态表中的条目被认为是有尺寸,其计算公式为:字段名的字节长度+字段值的字节长度+32。动态表的尺寸就是其中所有条目的尺寸之和。
    动态表的最大尺寸是有限的,可以通过下面的整数表示法来通知协议的现实去改变动态表的最大尺寸。
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 |   Max size (5+)   |
+---+---------------------------+
    当插入新的条目或改变动态表的最大尺寸时,可能导致已有的一个或多个条目被逐出,甚至清空整个动态表。将动态表的最大尺寸设置为0是合法的,实际上,这是一种常用的清空动态表的途径。
    必须注意的是,在初始时,动态表是空的。动态表中的条目是在解码过程中插入到表中的,不可预先设置动态表中的条目。


John Jiang 2016-09-24 20:29 发表评论

相关 [http hpack 协议] 推荐:

探索HTTP/2: HPACK协议简述(原)

- - BlogJava-首页技术区
探索HTTP/2: HPACK协议简述. 在本系列的第一篇文章中已经介绍了HTTP 2协议,本文则将简述用于HTTP/2头部压缩的 HPACK协议. (2016.09.24最后更新).     HPACK头部压缩的基本原理就是使用索引表和 Huffman编码. 在压缩(编码)与解压(解码)过程,可将指定的头部字段(包含字段名与字段值)存储在索引表中.

Http协议详解

- - 浏览器 - 互联网 - ITeye博客
什么是HTTP协议 协议是指计算机通信网络中两台计算机之间进行通信所必须共同遵守的规定或规则,超文本传输协议(HTTP)是一种通信协议,它允许将超文本标记语言(HTML)文档从Web服务器传送到客户端的浏览器 目前我们使用的是HTTP/1.1 版本 Web服务器,浏览器,代理服务器 当我们打开浏览器,在地址栏中输入URL,然后我们就看到了网页.

http协议知识点

- - 互联网 - ITeye博客
媒体类型:http服务器会给在http中传送的http资源对象附加一个MIME类型,接收http资源对象的客户端会根据这个类型来判断是否能够进行处理,例如浏览器就能够处理上百种mime类型的http资源对象. MIME类型是一种文本标记,表示一种主要对象类型和一种特定的子类型,中间用一条斜杠来分隔,例如text/html、imge/gif.

HTTP 协议中的 Transfer-Encoding

- - JerryQu 的小站
本文作为我的博客「 HTTP 相关」专题新的一篇,主要讨论 HTTP 协议中的 Transfer-Encoding. 这个专题我会根据自己的理解,以尽量通俗的讲述,结合代码示例和实际场景来说明问题,欢迎大家关注和留言交流. Transfer-Encoding,是一个 HTTP 头部字段,字面意思是「传输编码」.

http协议:Web前端-HTTP Cache-control/浏览器缓存(转)

- - 互联网 - ITeye博客
HTTP协议分别在 1.0 / 1.1 两个时代推出了 Expires / Cache-control 两种cache策略,这里我们无需了解全部的细节,无需记住整个RFC内容,但是当我们需要使用HTTP cache策略时,我们需要注意以下细节:. Expires 是HTTP 1.0 那个时代的东西了,目前来看,可以不使用了,因为HTTP 1.0 的user agent占有率在 0.1% 以下(我们主要面向的web浏览器均默认使用HTTP 1.1),Cache-control 是 HTTP 1.1 的新特性,也是我们主要做文章使用cache策略的工具.

[转][转]深入理解HTTP协议

- - heiyeluren的Blog
来源: http://www.blogjava.net/zjusuyong/articles/304788.html.   HTTP是Hyper Text Transfer Protocol(超文本传输协议)的缩写. 它的发展是万维网协会(World Wide Web Consortium)和Internet工作小组IETF(Internet Engineering Task Force)合作的结果,(他们)最终发布了一系列的RFC,RFC 1945定义了HTTP/1.0版本.

http协议详解(超详细)转

- - 行业应用 - ITeye博客
http 协议学习系列       HTTP协议(HyperText Transfer Protocol,超文本传输协议)是用于从WWW服务器传输超文本到本地浏览器的传送协议.   HTTP是Hyper Text Transfer Protocol(超文本传输协议)的缩写. 它的发展是万维网协会(World Wide Web Consortium)和Internet工作小组IETF(Internet Engineering Task Force)合作的结果,(他们)最终发布了一系列的RFC,RFC 1945定义了HTTP/1.0版本.

浅析http协议与缓存

- - 博客园_Ruby's Louvre
最近几天在复习http协议中headers,缓存等相关知识,发现些新知识点. 这篇文章注重结合PHP去理解这些内容,也就是比较注重实践部分. 一、http headers. NO1:对于web应用,用户群在客户端 (各种浏览器)点击任何一个连接向服务器发送http请求,这过程肯定需要3次握手,建立连接,服务器响应返回数据.

XMPP协议、MQTT协议、HTTP协议、CoAP协议的基本比较

- - ITeye博客
一、先看下相关国外的专业数据对四大协议的比较:.           XML的解析对于嵌入多设备来说是比较痛苦的 ,所以在嵌入设备上做开发的时候,最好不要选择基于XML的协议.          二、四大协议的基本介绍:.    XMPP是一种基于标准通用标记语言的子集XML的协议,它继承了在XML环境中灵活的发展性.

XMLHttpRequest实现HTTP协议下文件上传断点续传

- - 张鑫旭-鑫空间-鑫生活
本文地址: http://www.zhangxinxu.com/wordpress/?p=3754. 不知大家有没有观察过,在秋季,也就是眼下这个时间,当阵风挂起的时候,地上的落叶就会以一个接一个,翻滚着一同被吹走,这就是“跟风”. 老祖宗确实很有智慧,造出来的词语源于生活,又高于生活. 眼下,又是另一波跟风之势——“网盘”,犹如当年团购一样.