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