go HTTP2 的头部压缩算法hpack实现详解
作者:Duslia 发布时间:2024-05-21 10:27:37
Hpack 是啥
Hpack 是 HTTP2 的头部压缩算法。在 HTTP1 中,每次传输都会有大量的 Header 携带,我们可以拿一个实际的请求来看,如图一:
图一:请求 header
这里面 Header 很多是请求共性的,比如 method: POST,就是 post 请求的 header,那每个 POST 请求都会携带这个 header;以及同一个页面里可能有很多请求需要带上相同 header,比如 user-agent、鉴权相关 header 等等。那如果 body 很小的话,每次传输利用率就很低了。HTTP2 为了提高传输效率设计了 HPACK 头部压缩算法。
HPACK 原理
HPACK 维护了两张表,静态表和动态表。如果 Header key、value 在表里的话,直接将 Header kv 用 index 编码即可;如果不存在表中的话,则采用 Huffman 编码或者不编码发送。每条连接维护各自的动态表,request 和 response 的动态表是分开的。
静态表存储常见的 Header kv,比如 :method: GET、:method: POST、:schema: http 等一共 61 项,具体的项可以参考 RFC 7541 文档。
动态表是一个先进先出的表,先进入的在高索引空间,后进入的在低索引空间(索引空间从0到最后递减)。header 根据一定的规则判断是否加入动态表,有三种规则:
将 header 字段添加到动态表的开头
不将 header 字段添加到动态表
不将 header 添加到动态表,另外规定 header 始终不被动态表编码,常见于有代理或者网关的场景。这是为了保护 header 字段值,比如通过大量尝试判断 header size 可以推断出动态表的内容。
动态表也有一定大小,通过 SETTINGS_HEADER_TABLE_SIZE 来设置。如果新的 Header kv size 超过了这个值,就会逐出动态表,直到能够放下这个 Header kv 或者将所有的逐出。特别的,如果一个 Header kv size 大于了动态表的最大值,那么这个 Header 的作用就是清空动态表。
如何编码
该 Header 已经存在动态表中
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Index (7+) |
+---+---------------------------+
Key 被索引,value 未索引且允许保存
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
01 后的 index 表示 Header Key 的索引
这个 Header 会被加在 server 和 client 的动态表中。
Key 被索引,value 未索引且不允许保存
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
Key、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) |
+-------------------------------+
Key、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) |
+-------------------------------+
Key 被索引,value 未索引且绝对不允许保存
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | Index (4+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
Key、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) |
+-------------------------------+
举个编码??
:method: GET
:scheme: http
:path: /
:authority: www.example.com
编码后的 16 进制如下
8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff
82 = 10000010 -> 8 表示 kv 均被索引,表项为静态表第 2 项-> :method: GET
86 = 10000110 -> 8 表示 kv 均被索引,表项为静态表第 6 项-> :scheme: http
84 = 10000100 -> 8 表示 kv 均被索引,表项为静态表第 4 项 -> :path: /
41 = 01000001 -> 4 表示 Key 被索引,value 未索引且允许保存,name 为静态表第1项,即 :authority。接下来表示这个 header对应的 value。
8c = 10001100 -> 第一个 bit 为1,表示 huffman 编码,字符串的长度为 1100b = 12。接着解析12个字节为 huffman 编码后的字符 f1e3 c2e5 f23a 6ba0 ab90 f4ff, 解码为www.example.com
所以得到最后一个头部 :authority: www.example.com
HPACK 实现
我们可以先想一下,如果要做到索引的复杂度尽可能小,同时又要有序方便逐出,那应该采用什么数据结构呢?
那应该很容易想到,我们需要用一个 slice 存下来所有的数据,也方便逐出;如果一个 Header 来了,我们也需要两个 map 存下这个这个 Header 对应的在 slice 中的 index。
Golang 中 HPACK 的实现在 hpack 文件夹中,动态表的数据结构和我们想的一样。
动态表的实现在 tables.go 当中
type headerFieldTable struct {
// 用 slice 存储具体的表项,同时也方便逐出
ents []HeaderField
// 逐出数量,可以理解为偏移修正量。如果一个 header 被逐出后,那其他 header 的
// 索引就会升高。在 map 中修改需要 O(n) 的开销,所以计算 id 时在这里统一加
// 一个修正量即可。
evictCount uint64
// 只根据 header 找对应的 id。
byName map[string]uint64
// 根据 header kv 找对应的 id。
byNameValue map[pairNameValue]uint64
}
type pairNameValue struct {
name, value string
}
func (t *headerFieldTable) addEntry(f HeaderField) {
// 计算唯一 id,同时保证不和已经在表中的 id 重复
id := uint64(t.len()) + t.evictCount + 1
// 在两个 map 中存下索引
t.byName[f.Name] = id
t.byNameValue[pairNameValue{f.Name, f.Value}] = id
// 保存索引
t.ents = append(t.ents, f)
}
// 逐出 n 个
func (t *headerFieldTable) evictOldest(n int) {
...
for k := 0; k < n; k++ {
f := t.ents[k]
// 根据 index 算出在 map 中的 id
id := t.evictCount + uint64(k) + 1
// 双重校验,如果校验通过就删除表项
if t.byName[f.Name] == id {
delete(t.byName, f.Name)
}
if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
delete(t.byNameValue, p)
}
}
// 用后 n 个表项覆盖前面的表项实现逐出
copy(t.ents, t.ents[n:])
for k := t.len() - n; k < t.len(); k++ {
t.ents[k] = HeaderField{} // so strings can be garbage collected
}
t.ents = t.ents[:t.len()-n]
// 逐出数量 +n
// 表项迁移带来的索引减小会通过 evictCount 的增加补回来,所以 id 并不会变
t.evictCount += uint64(n)
}
// 在表项中寻找,如果没有匹配的 i 就是 0.如果 kv 都匹配上了就返回 index, true;
// 如果只有 k 匹配上了就返回 index, false。
func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
if !f.Sensitive {
if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
return t.idToIndex(id), true
}
}
if id := t.byName[f.Name]; id != 0 {
return t.idToIndex(id), false
}
return 0, false
}
func (t *headerFieldTable) idToIndex(id uint64) uint64 {
// 校验。不在这里 panic,下面根据 index 索引的时候,slice 也会 panic
if id <= t.evictCount {
panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
}
// 将 id 转换为 slice 中的 index
k := id - t.evictCount - 1 // convert id to an index t.ents[k]
// 如果是动态表,需要减去静态表的长度
if t != staticTable {
return uint64(t.len()) - k // dynamic table
}
return k + 1
}
其他部分的实现就很简单了,基本上就是照着上面的流程写就可以了。其中有一个解析当前 header 是哪种类型的实现还挺有意思的。
func (d *Decoder) parseHeaderFieldRepr() error {
b := d.buf[0]
switch {
case b&128 != 0:
// 128 => 10000000
// 设置了最高位,对应上面的第 1 种 kv 均在的情况
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.1
return d.parseFieldIndexed()
case b&192 == 64:
// 192 => 11000000
// 对应前三位为 010 的情况,即允许保存的情况
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.1
return d.parseFieldLiteral(6, indexedTrue)
case b&240 == 0:
// 240 => 11110000
// 对应前四位都是0的情况,即不允许保存的情况
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.2
return d.parseFieldLiteral(4, indexedFalse)
case b&240 == 16:
// 240 => 11110000
// 对应前四位是0001的情况,即绝对不允许保存的情况
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.3
return d.parseFieldLiteral(4, indexedNever)
case b&224 == 32:
// 224 => 11100000
// 对应前三位是001的情况,即动态表大小更新的情况
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.3
return d.parseDynamicTableSizeUpdate()
}
return DecodingError{errors.New("invalid encoding")}
}
遇到的坑
写这篇文章是因为 hertz 在接入 h3 的时候会偶发的 panic,原因是在动态表存表项的时候,存入了一个 unsafe string,后面这一项给变了,导致双重校验的时候没有删掉,从而引发了 panic。
参考文档
www.rfc-editor.org/rfc/rfc7541
来源:https://juejin.cn/post/7154718492032237575
猜你喜欢
- <?php $fp = fopen("http://www.***.com/**
- Python GUI 库有很多,下面给大家罗列常用的几种 GUI 库。下面介绍的这些GUI框架,能满足大部分开发人员的需要,你可以根据自己的
- 最近,带领我的学生进行一个URTP项目设计,需要进行人脸识别。由于现在的OpenCV已经到了2.X版本,因此就不想用原来的1.X版本的代码,
- 测试方法首先使用implode, serialize, json_encode, msgpack_pack创建四个文本文件,用于测试。创建代
- 背景最近在负责开发维护的一款数据平台,有一个功能是把数据从某个源头数据源(如常规的JDBC数据源,MySQL,Oracle等)推到目地数据源
- 本文实例讲述了python自动化测试之setUp与tearDown的用法,分享给大家供大家参考。具体如下:实例代码如下:class Roma
- 以如下代码为例,我们在局部作用域内使用全局变量a,需要使用global关键字进行声明。否则代码会不可用。a = 100def fun():&
- 1、Select元素2、定位select方法一:二次定位先定位 select 框,再定位 select 里的选项但有时候选项是无法定位的,所
- 在实际的工作中,尤其是在生产环境里边,SQL语句的优化问题十分的重要,它对数据库的性能的提升也起着显著的作用.我们总是在抱怨机器的性能问题,
- 安全性问题一直DBA是比较关心的问题,因为建立数据库的目的就是让相关的的客户端来进行访问,所以很难避免不出现安全隐患,例如客户端链接的权限、
- 加密算法分类 对称加密算法:对称加密采用了对称密码编码技术,它的特点是文件加密和解密使用相同的密钥发送方和接收方需要持有同一把密钥,发送消息
- 在vue中使用ant-design-vue组件官方地址:Ant Design Vue1. 安装首先使用vue-cli创建项目,然后进入项目,
- 1.聚合运算(1)使用内置的聚合运算函数进行计算1>内置的聚合运算函数sum(),mean(),max(),min(),size(),
- 爬虫与发爬虫的厮杀,一方为了拿到数据,一方为了防止爬虫拿到数据,谁是最后的赢家?重新理解爬虫中的一些概念爬虫:自动获取网站数据的程序反爬虫:
- execjs 使用有了selenium+Chrome Headless 加载页面为什么还要用execjs来运行js?selenium+Chr
- 目录引入依赖配置构建实体类保存数据查询数据项目中需要存放大量设备日志,且需要对其进行简单的数据分析,信息提取工作.结合众多考量因素,项目决定
- 使用Resample函数转换时间序列 一、什么是resample函数?它是Python数据分析库Pandas的方法函数。它主要用于
- 目录1、条件语句1.1 if语句2、嵌套的分支语句3、案例练习4、循环语句4.1 for-in循环4.2 range()函数4.3 实例1:
- 1.php in_array方法说明PHP查找数组元素是否存在,一般会使用in_array方法。bool in_array ( mixed
- 熟悉css的开发者一定知道图像替换技术,也深知它的意义,Dave Shea 曾在他的一篇文章对此做了详细的总结,参看 Dave Shea’s