go HTTP2 的頭部壓縮算法hpack實(shí)現(xiàn)詳解
Hpack 是啥
Hpack 是 HTTP2 的頭部壓縮算法。在 HTTP1 中，每次傳輸都會(huì)有大量的 Header 攜帶，我們可以拿一個(gè)實(shí)際的請(qǐng)求來(lái)看，如圖一：
圖一：請(qǐng)求 header
這里面 Header 很多是請(qǐng)求共性的，比如 method: POST，就是 post 請(qǐng)求的 header，那每個(gè) POST 請(qǐng)求都會(huì)攜帶這個(gè) header；以及同一個(gè)頁(yè)面里可能有很多請(qǐng)求需要帶上相同 header，比如 user-agent、鑒權(quán)相關(guān) header 等等。那如果 body 很小的話，每次傳輸利用率就很低了。HTTP2 為了提高傳輸效率設(shè)計(jì)了 HPACK 頭部壓縮算法。
HPACK 原理
HPACK 維護(hù)了兩張表，靜態(tài)表和動(dòng)態(tài)表。如果 Header key、value 在表里的話，直接將 Header kv 用 index 編碼即可；如果不存在表中的話，則采用 Huffman 編碼或者不編碼發(fā)送。每條連接維護(hù)各自的動(dòng)態(tài)表，request 和 response 的動(dòng)態(tài)表是分開(kāi)的。
靜態(tài)表存儲(chǔ)常見(jiàn)的 Header kv，比如 :method: GET、:method: POST、:schema: http 等一共 61 項(xiàng)，具體的項(xiàng)可以參考 RFC 7541 文檔。
動(dòng)態(tài)表是一個(gè)先進(jìn)先出的表，先進(jìn)入的在高索引空間，后進(jìn)入的在低索引空間（索引空間從0到最后遞減）。header 根據(jù)一定的規(guī)則判斷是否加入動(dòng)態(tài)表，有三種規(guī)則：
- 將 header 字段添加到動(dòng)態(tài)表的開(kāi)頭
- 不將 header 字段添加到動(dòng)態(tài)表
- 不將 header 添加到動(dòng)態(tài)表，另外規(guī)定 header 始終不被動(dòng)態(tài)表編碼，常見(jiàn)于有代理或者網(wǎng)關(guān)的場(chǎng)景。這是為了保護(hù) header 字段值，比如通過(guò)大量嘗試判斷 header size 可以推斷出動(dòng)態(tài)表的內(nèi)容。
動(dòng)態(tài)表也有一定大小，通過(guò) SETTINGS_HEADER_TABLE_SIZE 來(lái)設(shè)置。如果新的 Header kv size 超過(guò)了這個(gè)值，就會(huì)逐出動(dòng)態(tài)表，直到能夠放下這個(gè) Header kv 或者將所有的逐出。特別的，如果一個(gè) Header kv size 大于了動(dòng)態(tài)表的最大值，那么這個(gè) Header 的作用就是清空動(dòng)態(tài)表。
如何編碼
- 該 Header 已經(jīng)存在動(dòng)態(tài)表中
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 的索引
這個(gè) Header 會(huì)被加在 server 和 client 的動(dòng)態(tài)表中。
- 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 未索引且絕對(duì)不允許保存
0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | 1 | Index (4+) | +---+---+-----------------------+ | H | Value Length (7+) | +---+---------------------------+ | Value String (Length octets) | +-------------------------------+
- Key、value 均未索引且絕對(duì)不允許保存
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) | +-------------------------------+
舉個(gè)編碼??
:method: GET :scheme: http :path: / :authority: www.example.com
編碼后的 16 進(jìn)制如下
8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff
82 = 10000010 -> 8 表示 kv 均被索引，表項(xiàng)為靜態(tài)表第 2 項(xiàng)-> :method: GET
86 = 10000110 -> 8 表示 kv 均被索引，表項(xiàng)為靜態(tài)表第 6 項(xiàng)-> :scheme: http
84 = 10000100 -> 8 表示 kv 均被索引，表項(xiàng)為靜態(tài)表第 4 項(xiàng) -> :path: /
41 = 01000001 -> 4 表示 Key 被索引，value 未索引且允許保存，name 為靜態(tài)表第1項(xiàng)，即 :authority。接下來(lái)表示這個(gè) header對(duì)應(yīng)的 value。
8c = 10001100 -> 第一個(gè) bit 為1，表示 huffman 編碼，字符串的長(zhǎng)度為 1100b = 12。接著解析12個(gè)字節(jié)為 huffman 編碼后的字符 f1e3 c2e5 f23a 6ba0 ab90 f4ff， 解碼為www.example.com
所以得到最后一個(gè)頭部 :authority: www.example.com
HPACK 實(shí)現(xiàn)
我們可以先想一下，如果要做到索引的復(fù)雜度盡可能小，同時(shí)又要有序方便逐出，那應(yīng)該采用什么數(shù)據(jù)結(jié)構(gòu)呢？
那應(yīng)該很容易想到，我們需要用一個(gè) slice 存下來(lái)所有的數(shù)據(jù)，也方便逐出；如果一個(gè) Header 來(lái)了，我們也需要兩個(gè) map 存下這個(gè)這個(gè) Header 對(duì)應(yīng)的在 slice 中的 index。
Golang 中 HPACK 的實(shí)現(xiàn)在 hpack 文件夾中，動(dòng)態(tài)表的數(shù)據(jù)結(jié)構(gòu)和我們想的一樣。
動(dòng)態(tài)表的實(shí)現(xiàn)在 tables.go 當(dāng)中
type headerFieldTable struct {
// 用 slice 存儲(chǔ)具體的表項(xiàng)，同時(shí)也方便逐出
ents []HeaderField
// 逐出數(shù)量，可以理解為偏移修正量。如果一個(gè) header 被逐出后，那其他 header 的
// 索引就會(huì)升高。在 map 中修改需要 O(n) 的開(kāi)銷，所以計(jì)算 id 時(shí)在這里統(tǒng)一加
// 一個(gè)修正量即可。
evictCount uint64
// 只根據(jù) header 找對(duì)應(yīng)的 id。
byName map[string]uint64
// 根據(jù) header kv 找對(duì)應(yīng)的 id。
byNameValue map[pairNameValue]uint64
}
type pairNameValue struct {
name, value string
}
func (t *headerFieldTable) addEntry(f HeaderField) {
// 計(jì)算唯一 id，同時(shí)保證不和已經(jīng)在表中的 id 重復(fù)
id := uint64(t.len()) + t.evictCount + 1
// 在兩個(gè) map 中存下索引
t.byName[f.Name] = id
t.byNameValue[pairNameValue{f.Name, f.Value}] = id
// 保存索引
t.ents = append(t.ents, f)
}
// 逐出 n 個(gè)
func (t *headerFieldTable) evictOldest(n int) {
...
for k := 0; k < n; k++ {
f := t.ents[k]
// 根據(jù) index 算出在 map 中的 id
id := t.evictCount + uint64(k) + 1
// 雙重校驗(yàn)，如果校驗(yàn)通過(guò)就刪除表項(xiàng)
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 個(gè)表項(xiàng)覆蓋前面的表項(xiàng)實(shí)現(xià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]
// 逐出數(shù)量 +n
// 表項(xiàng)遷移帶來(lái)的索引減小會(huì)通過(guò) evictCount 的增加補(bǔ)回來(lái)，所以 id 并不會(huì)變
t.evictCount += uint64(n)
}
// 在表項(xiàng)中尋找，如果沒(méi)有匹配的 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 {
// 校驗(yàn)。不在這里 panic，下面根據(jù) index 索引的時(shí)候，slice 也會(huì) panic
if id <= t.evictCount {
panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
}
// 將 id 轉(zhuǎn)換為 slice 中的 index
k := id - t.evictCount - 1 // convert id to an index t.ents[k]
// 如果是動(dòng)態(tài)表，需要減去靜態(tài)表的長(zhǎng)度
if t != staticTable {
return uint64(t.len()) - k // dynamic table
}
return k + 1
}
其他部分的實(shí)現(xiàn)就很簡(jiǎn)單了，基本上就是照著上面的流程寫(xiě)就可以了。其中有一個(gè)解析當(dāng)前 header 是哪種類型的實(shí)現(xiàn)還挺有意思的。
func (d *Decoder) parseHeaderFieldRepr() error {
b := d.buf[0]
switch {
case b&128 != 0:
// 128 => 10000000
// 設(shè)置了最高位，對(duì)應(yīng)上面的第 1 種 kv 均在的情況
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.1
return d.parseFieldIndexed()
case b&192 == 64:
// 192 => 11000000
// 對(duì)應(yīng)前三位為 010 的情況，即允許保存的情況
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.1
return d.parseFieldLiteral(6, indexedTrue)
case b&240 == 0:
// 240 => 11110000
// 對(duì)應(yīng)前四位都是0的情況，即不允許保存的情況
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.2
return d.parseFieldLiteral(4, indexedFalse)
case b&240 == 16:
// 240 => 11110000
// 對(duì)應(yīng)前四位是0001的情況，即絕對(duì)不允許保存的情況
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.2.3
return d.parseFieldLiteral(4, indexedNever)
case b&224 == 32:
// 224 => 11100000
// 對(duì)應(yīng)前三位是001的情況，即動(dòng)態(tài)表大小更新的情況
// https://httpwg.org/specs/rfc7541.html#rfc.section.6.3
return d.parseDynamicTableSizeUpdate()
}
return DecodingError{errors.New("invalid encoding")}
}
遇到的坑
寫(xiě)這篇文章是因?yàn)?hertz 在接入 h3 的時(shí)候會(huì)偶發(fā)的 panic，原因是在動(dòng)態(tài)表存表項(xiàng)的時(shí)候，存入了一個(gè) unsafe string，后面這一項(xiàng)給變了，導(dǎo)致雙重校驗(yàn)的時(shí)候沒(méi)有刪掉，從而引發(fā)了 panic。
參考文檔
www.rfc-editor.org/rfc/rfc7541
以上就是go HTTP2 的頭部壓縮算法hpack實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于go HTTP2 頭部壓縮算法hpack的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
sync.Map是Golang標(biāo)準(zhǔn)庫(kù)提供的并發(fā)安全的Map類型，可以在多個(gè)goroutine并發(fā)讀寫(xiě)Map的場(chǎng)景下不需要加鎖，這篇文章主要介紹了Golang中的同步工具sync.Map詳解,需要的朋友可以參考下2023-05-05
Golang?Gin框架獲取請(qǐng)求參數(shù)的幾種常見(jiàn)方式
在我們平常添加路由處理函數(shù)之后,就可以在路由處理函數(shù)中編寫(xiě)業(yè)務(wù)處理代碼了,但在此之前我們往往需要獲取請(qǐng)求參數(shù),本文就詳細(xì)的講解下gin獲取請(qǐng)求參數(shù)常見(jiàn)的幾種方式,需要的朋友可以參考下2024-02-02
這篇文章主要介紹了使用Golang的Context管理上下文的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
攔截信號(hào)Golang應(yīng)用優(yōu)雅關(guān)閉的操作方法
這篇文章主要介紹了攔截信號(hào)優(yōu)雅關(guān)閉Golang應(yīng)用,本文介紹了信號(hào)的概念及常用信號(hào)，并給出了應(yīng)用廣泛的幾個(gè)示例，例如優(yōu)雅地關(guān)閉應(yīng)用服務(wù)、在命令行應(yīng)用中接收終止命令，需要的朋友可以參考下2023-02-02
這篇文章主要為大家介紹了golang?字符串拼接方法對(duì)比分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
Go?io/fs.FileMode文件系統(tǒng)基本操作和權(quán)限管理深入理解
這篇文章主要為大家介紹了Go?io/fs.FileMode文件系統(tǒng)基本操作和權(quán)限管理深入理解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
這篇文章主要為大家詳細(xì)介紹了Golang中一些常用的if代碼優(yōu)化小技巧,w文中的示例代碼簡(jiǎn)潔易懂,具有一定的借鑒價(jià)值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-10-10
今天小編就為大家分享一篇關(guān)于go for range坑和閉包坑的分析，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-04-04
Go實(shí)現(xiàn)mongodb增刪改查工具類的代碼示例
這篇文章主要給大家介紹了關(guān)于Go實(shí)現(xiàn)mongodb增刪改查工具類的相關(guān)資料,MongoDB是一個(gè)NoSQL數(shù)據(jù)庫(kù),它提供了靈活的文檔存儲(chǔ)模型以及強(qiáng)大的查詢和操作功能,需要的朋友可以參考下2023-10-10
這篇文章主要為大家詳細(xì)介紹了Go實(shí)現(xiàn)文件上傳和下載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-07-07