首页 > 资讯 > 后端开发 > GO >goHTTP2的头部压缩算法hpack实现详解

773

分享到

goHTTP2的头部压缩算法hpack实现详解

2024-04-02 19:04:59 773人浏览独家记忆

摘要

目录Hpack 是啥HPACK 原理如何编码举个编码?HPACK 实现遇到的坑Hpack 是啥 Hpack 是 Http2 的头部压缩算法。在 HTTP1 中，每次传输都会有大量的

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

以上就是go HTTP2 的头部压缩算法hpack实现详解的详细内容，更多关于go HTTP2 头部压缩算法hpack的资料请关注编程网其它相关文章！

您可能感兴趣的文档:

Go语言（Golang）教程

--结束END--

本文标题: goHTTP2的头部压缩算法hpack实现详解

本文链接: https://lsjlt.com/news/121257.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

goHTTP2的头部压缩算法hpack实现详解

目录

Hpack 是啥

HPACK 原理

如何编码

举个编码?

HPACK 实现

遇到的坑

goHTTP2的头部压缩算法hpack实现详解

HTTP/2如何实现头部压缩

Python3压缩和解压缩的实现方法

Android实现zip文件压缩及解压缩的方法

ZIP4j 压缩与解压的实例详解

Linux下常用压缩格式的压缩与解压方法详解

Python中实现一个LZ77压缩算法

Java 实现LZ78压缩算法的示例代码

Python实现图片压缩的案例详解

基于Python实现文件的压缩与解压缩

Redis怎么实现数据的压缩和解压缩

Pythonshutil模块实现文件的裁剪、压缩与解压缩的方法

Python实现压缩与解压gzip大文件的方法

C语言字符串压缩之ZSTD算法详解

java实现稀疏矩阵的压缩与解压的方法

Android图片压缩的实例详解

Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

iOS实现简单的头部缩放功能

C#实现批量压缩和解压缩的示例代码

Android Bitmap压缩方法的选择详解

Sqlx 连接具有相同字段的表

如何从 go 中的另一个包访问结构变量？

使用 kafka-go 在 Kafka 中计划创建消费者

无法从 Golang 中的 Google userinfo API 响应访问电话号码（使用 golang.org/x/oauth2 和 Google People API）

如何在Golang中为Azure SDK指定x509证书

etcd 事务中的原子计数器增量

将字段添加到 MongoDB 内部对象

如何处理关闭同一通道的多个 go 例程？

Cron Job 不会用 TimeZone 触发

API 网关 -> Go Lambda 参数