通过静态哈夫曼代码对传输的标头字段进行编码,从而减小数据传输的大小。
单个连接中,client和server共同维护一个相同的标头字段索引列表(笔者称为HPACK索引列表),此列表在之后的传输中用作编解码的参考。
本篇不对哈夫曼编码做过多的阐述,主要对双端共同维护的索引列表进行分析。
HPACK 压缩上下文包含一个静态表和一个动态表:静态表在规范中定义,并提供了一个包含所有连接都可能使用的常用 HTTP 标头字段的列表;动态表最初为空,将根据在特定连接内交换的值进行更新。
HPACK索引列表认识静/动态表需要先认识headerFieldTable
结构体,动态表和静态表都是基于它实现的。
type headerFieldTable struct { // As in hpack, unique ids are 1-based. The unique id for ents[k] is k + evictCount + 1. ents []HeaderField evictCount uint64 // byName maps a HeaderField name to the unique id of the newest entry with the same name. byName map[string]uint64 // byNameValue maps a HeaderField name/value pair to the unique id of the newest byNameValue map[pairNameValue]uint64 }
下面将对上述的字段分别进行描述:
ents
:entries的缩写,代表着当前已经索引的Header数据。在headerFieldTable中,每一个Header都有一个唯一的Id,以ents[k]
为例,该唯一id的计算方式是k + evictCount + 1
。
evictCount
:已经从ents中删除的条目数。
byName
:存储具有相同Name的Header的唯一Id,最新Header的Name会覆盖老的唯一Id。
byNameValue
:以Header的Name和Value为key存储对应的唯一Id。
对字段的含义有所了解后,接下来对headerFieldTable几个比较重要的行为进行描述。
(*headerFieldTable).addEntry:添加Header实体到表中
func (t *headerFieldTable) addEntry(f HeaderField) { id := uint64(t.len()) + t.evictCount + 1 t.byName[f.Name] = id t.byNameValue[pairNameValue{f.Name, f.Value}] = id t.ents = append(t.ents, f) }
首先,计算出Header在headerFieldTable中的唯一Id,并将其分别存入byName
和byNameValue
中。最后,将Header存入ents
。
因为使用了append函数,这意味着ents[0]
存储的是存活最久的Header。
(*headerFieldTable).evictOldest:从表中删除指定个数的Header实体
func (t *headerFieldTable) evictOldest(n int) { if n > t.len() { panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len())) } for k := 0; k < n; k++ { f := t.ents[k] 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) } } 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] if t.evictCount+uint64(n) < t.evictCount { panic("evictCount overflow") } t.evictCount += uint64(n) }
第一个for循环的下标是从0开始的,也就是说删除Header时遵循先进先出的原则。删除Header的步骤如下:
删除
byName
和byNameValue
的映射。将第n位及其之后的Header前移。
将倒数的n个Header置空,以方便垃圾回收。
改变ents的长度。
增加
evictCount
的数量。
(*headerFieldTable).search:从当前表中搜索指定Header并返回在当前表中的Index(此处的Index
和切片中的下标含义是不一样的)
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 }
如果Header的Name和Value均匹配,则返回当前表中的Index且nameValueMatch
为true。
如果仅有Header的Name匹配,则返回当前表中的Index且nameValueMatch
为false。
如果Header的Name和Value均不匹配,则返回0且nameValueMatch
为false。
(*headerFieldTable).idToIndex:通过当前表中的唯一Id计算出当前表对应的Index
func (t *headerFieldTable) idToIndex(id uint64) uint64 { if id <= t.evictCount { panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount)) } 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 }
静态表:Index
从1开始,且Index为1时对应的元素为t.ents[0]
。
动态表: Index
也从1开始,但是Index为1时对应的元素为t.ents[t.len()-1]
。
静态表中包含了一些每个连接都可能使用到的Header。其实现如下:
var staticTable = newStaticTable() func newStaticTable() *headerFieldTable { t := &headerFieldTable{} t.init() for _, e := range staticTableEntries[:] { t.addEntry(e) } return t } var staticTableEntries = [...]HeaderField{ {Name: ":authority"}, {Name: ":method", Value: "GET"}, {Name: ":method", Value: "POST"}, // 此处省略代码 {Name: "www-authenticate"}, }
上面的t.init
函数仅做初始化t.byName
和t.byNameValue
用。笔者在这里仅展示了部分预定义的Header,完整预定义Header参见https://github.com/golang/go/blob/master/src/vendor/golang.org/x/net/http2/hpack/tables.go#L130。
动态表结构体如下:
type dynamicTable struct { // http://http2.github.io/http2-spec/compression.html#rfc.section.2.3.2 table headerFieldTable size uint32 // in bytes maxSize uint32 // current maxSize allowedMaxSize uint32 // maxSize may go up to this, inclusive }
动态表的实现是基于headerFieldTable
,相比原先的基础功能增加了表的大小限制,其他功能保持不变。
前面介绍了动/静态表中内部的Index和内部的唯一Id,而在一次连接中HPACK索引列表是由静态表和动态表一起构成,那此时在连接中的HPACK索引是怎么样的呢?
带着这样的疑问我们看看下面的结构:
上图中蓝色部分表示静态表,黄色部分表示动态表。
H1...Hn
和H1...Hm
分别表示存储在静态表和动态表中的Header元素。
在HPACK索引中静态表部分的索引和静态表的内部索引保持一致,动态表部分的索引为动态表内部索引加上静态表索引的最大值。在一次连接中Client和Server通过HPACK索引标识唯一的Header元素。
HPACK编码众所周知HTTP2的标头压缩能够减少很多数据的传输,接下来我们通过下面的例子,对比一下编码前后的数据大小:
var ( buf bytes.Buffer oriSize int ) henc := hpack.NewEncoder(&buf) headers := []hpack.HeaderField{ {Name: ":authority", Value: "dss0.bdstatic.com"}, {Name: ":method", Value: "GET"}, {Name: ":path", Value: "/5aV1bjqh_Q23odCf/static/superman/img/topnav/baiduyun@2x-e0be79e69e.png"}, {Name: ":scheme", Value: "https"}, {Name: "accept-encoding", Value: "gzip"}, {Name: "user-agent", Value: "Go-http-client/2.0"}, {Name: "custom-header", Value: "custom-value"}, } for _, header := range headers { oriSize += len(header.Name) + len(header.Value) henc.WriteField(header) } fmt.Printf("ori size: %v, encoded size: %v\n", oriSize, buf.Len()) //输出为:ori size: 197, encoded size: 111
注:在 HTTP2 中,请求和响应标头字段的定义保持不变,仅有一些微小的差异:所有标头字段名称均为小写,请求行现在拆分成各个 :method
、:scheme
、:authority
和 :path
伪标头字段。
在上面的例子中,我们看到原来为197字节的标头数据现在只有111字节,减少了近一半的数据量!
带着一种 “卧槽,牛逼!”的心情开始对henc.WriteField
方法调试。
func (e *Encoder) WriteField(f HeaderField) error { e.buf = e.buf[:0] if e.tableSizeUpdate { e.tableSizeUpdate = false if e.minSize < e.dynTab.maxSize { e.buf = appendTableSize(e.buf, e.minSize) } e.minSize = uint32Max e.buf = appendTableSize(e.buf, e.dynTab.maxSize) } idx, nameValueMatch := e.searchTable(f) if nameValueMatch { e.buf = appendIndexed(e.buf, idx) } else { indexing := e.shouldIndex(f) if indexing { e.dynTab.add(f) // 加入动态表中 } if idx == 0 { e.buf = appendNewName(e.buf, f, indexing) } else { e.buf = appendIndexedName(e.buf, f, idx, indexing) } } n, err := e.w.Write(e.buf) if err == nil && n != len(e.buf) { err = io.ErrShortWrite } return err }
经调试发现,本例中:authority
,:path
,accept-encoding
和user-agent
走了appendIndexedName
分支;:method
和:scheme
走了appendIndexed
分支;custom-header
走了appendNewName
分支。这三种分支总共代表了两种不同的编码方法。
由于本例中f.Sensitive
默认值为false且Encoder给动态表的默认大小为4096,按照e.shouldIndex
的逻辑本例中indexing
一直为true(在笔者所使用的go1.14.2源码中,client端尚未发现有使f.Sensitive
为true的代码)。
笔者对上面e.tableSizeUpdate
相关的逻辑不提的原因是控制e.tableSizeUpdate
的方法为e.SetMaxDynamicTableSizeLimit
和e.SetMaxDynamicTableSize
,而笔者在(*http2Transport).newClientConn
(此方法相关逻辑参见前篇)相关的源码中发现了这样的注释:
// TODO: SetMaxDynamicTableSize, SetMaxDynamicTableSizeLimit on // henc in response to SETTINGS frames?
笔者看到这里的时候内心激动不已呀,产生了一种强烈的想贡献代码的欲望,奈何自己能力有限只能看着机会却抓不住呀,只好含恨埋头苦学(开个玩笑~,毕竟某位智者说过,写的越少BUG越少?)。
(*Encoder).searchTable:从HPACK索引列表中搜索Header,并返回对应的索引。
func (e *Encoder) searchTable(f HeaderField) (i uint64, nameValueMatch bool) { i, nameValueMatch = staticTable.search(f) if nameValueMatch { return i, true } j, nameValueMatch := e.dynTab.table.search(f) if nameValueMatch || (i == 0 && j != 0) { return j + uint64(staticTable.len()), nameValueMatch } return i, false }
搜索顺序为,先搜索静态表,如果静态表不匹配,则搜索动态表,最后返回。
索引Header表示法此表示法对应的函数为appendIndexed,且该Header已经在索引列表中。
该函数将Header在HPACK索引列表中的索引编码,原先的Header最后仅用少量的几个字节就可以表示。
func appendIndexed(dst []byte, i uint64) []byte { first := len(dst) dst = appendVarInt(dst, 7, i) dst[first] |= 0x80 return dst } func appendVarInt(dst []byte, n byte, i uint64) []byte { k := uint64((1 << n) - 1) if i < k { return append(dst, byte(i)) } dst = append(dst, byte(k)) i -= k for ; i >= 128; i >>= 7 { dst = append(dst, byte(0x80|(i&0x7f))) } return append(dst, byte(i)) }
由appendIndexed
知,用索引头字段表示法时,第一个字节的格式必须是0b1xxxxxxx
,即第0位必须为1
,低7位用来表示值。
如果索引大于uint64((1 << n) - 1)
时,需要使用多个字节来存储索引的值,步骤如下:
第一个字节的最低n位全为1。
索引i减去uint64((1 << n) - 1)后,每次取低7位或上
0b10000000
, 然后i右移7位并和128进行比较,判断是否进入下一次循环。循环结束后将剩下的i值直接放入buf中。
用这种方法表示Header时,仅需要少量字节就可以表示一个完整的Header头字段,最好的情况是一个字节就可以表示一个Header字段。
增加动态表Header表示法此种表示法对应两种情况:一,Header的Name有匹配索引;二,Header的Name和Value均无匹配索引。这两种情况分别对应的处理函数为appendIndexedName
和appendNewName
。这两种情况均会将Header添加到动态表中。
appendIndexedName: 编码有Name匹配的Header字段。
func appendIndexedName(dst []byte, f HeaderField, i uint64, indexing bool) []byte { first := len(dst) var n byte if indexing { n = 6 } else { n = 4 } dst = appendVarInt(dst, n, i) dst[first] |= encodeTypeByte(indexing, f.Sensitive) return appendHpackString(dst, f.Value) }
在这里我们先看看encodeTypeByte
函数:
func encodeTypeByte(indexing, sensitive bool) byte { if sensitive { return 0x10 } if indexing { return 0x40 } return 0 }
前面提到本例中indexing一直为true,sensitive为false,所以encodeTypeByte的返回值一直为0x40
。
此时回到appendIndexedName函数,我们知道增加动态表Header表示法的第一个字节格式必须是0xb01xxxxxx
,即最高两位必须是01
,低6位用于表示Header中Name的索引。
通过appendVarInt
对索引编码后,下面我们看看appendHpackString
函数如何对Header的Value进行编码:
func appendHpackString(dst []byte, s string) []byte { huffmanLength := HuffmanEncodeLength(s) if huffmanLength < uint64(len(s)) { first := len(dst) dst = appendVarInt(dst, 7, huffmanLength) dst = AppendHuffmanString(dst, s) dst[first] |= 0x80 } else { dst = appendVarInt(dst, 7, uint64(len(s))) dst = append(dst, s...) } return dst }
appendHpackString
编码时分为两种情况:
哈夫曼编码后的长度小于原Value的长度时,先用appendVarInt
将哈夫曼编码后的最终长度存入buf,然后再将真实的哈夫曼编码存入buf。
哈夫曼编码后的长度大于等于原Value的长度时,先用appendVarInt
将原Value的长度存入buf,然后再将原Value存入buf。
在这里需要注意的是存储Value长度时仅用了字节的低7位,最高位为1表示存储的内容为哈夫曼编码,最高位为0表示存储的内容为原Value。
appendNewName: 编码Name和Value均无匹配的Header字段。
func appendNewName(dst []byte, f HeaderField, indexing bool) []byte { dst = append(dst, encodeTypeByte(indexing, f.Sensitive)) dst = appendHpackString(dst, f.Name) return appendHpackString(dst, f.Value) }
前面提到encodeTypeByte
的返回值为0x40
,所以我们此时编码的第一个字节为0b01000000
。
第一个字节编码结束后通过appendHpackString
先后对Header的Name和Value进行编码。
前面理了一遍HPACK的编码过程,下面我们通过一个解码的例子来理一遍解码的过程。
// 此处省略HPACK编码中的编码例子 var ( invalid error sawRegular bool // 16 << 20 from fr.maxHeaderListSize() from remainSize uint32 = 16 << 20 ) hdec := hpack.NewDecoder(4096, nil) // 16 << 20 from fr.maxHeaderStringLen() from fr.maxHeaderListSize() hdec.SetMaxStringLength(int(remainSize)) hdec.SetEmitFunc(func(hf hpack.HeaderField) { if !httpguts.ValidHeaderFieldValue(hf.Value) { invalid = fmt.Errorf("invalid header field value %q", hf.Value) } isPseudo := strings.HasPrefix(hf.Name, ":") if isPseudo { if sawRegular { invalid = errors.New("pseudo header field after regular") } } else { sawRegular = true // if !http2validWireHeaderFieldName(hf.Name) { // invliad = fmt.Sprintf("invalid header field name %q", hf.Name) // } } if invalid != nil { fmt.Println(invalid) hdec.SetEmitEnabled(false) return } size := hf.Size() if size > remainSize { hdec.SetEmitEnabled(false) // mh.Truncated = true return } remainSize -= size fmt.Printf("%+v\n", hf) // mh.Fields = append(mh.Fields, hf) }) defer hdec.SetEmitFunc(func(hf hpack.HeaderField) {}) fmt.Println(hdec.Write(buf.Bytes())) // 输出如下: // ori size: 197, encoded size: 111 // header field ":authority" = "dss0.bdstatic.com" // header field ":method" = "GET" // header field ":path" = "/5aV1bjqh_Q23odCf/static/superman/img/topnav/baiduyun@2x-e0be79e69e.png" // header field ":scheme" = "https" // header field "accept-encoding" = "gzip" // header field "user-agent" = "Go-http-client/2.0" // header field "custom-header" = "custom-value" // 111 <nil>
通过最后一行的输出可以知道确确实实从111个字节中解码出了197个字节的原Header数据。
而这解码的过程笔者将从hdec.Write
方法开始分析,逐步揭开它的神秘面纱。
func (d *Decoder) Write(p []byte) (n int, err error) { // 此处省略代码 if d.saveBuf.Len() == 0 { d.buf = p } else { d.saveBuf.Write(p) d.buf = d.saveBuf.Bytes() d.saveBuf.Reset() } for len(d.buf) > 0 { err = d.parseHeaderFieldRepr() if err == errNeedMore { // 此处省略代码 d.saveBuf.Write(d.buf) return len(p), nil } // 此处省略代码 } return len(p), err }
在笔者debug的过程中发现解码的核心逻辑主要在d.parseHeaderFieldRepr
方法里。
func (d *Decoder) parseHeaderFieldRepr() error { b := d.buf[0] switch { case b&128 != 0: return d.parseFieldIndexed() case b&192 == 64: return d.parseFieldLiteral(6, indexedTrue) // 此处省略代码 } return DecodingError{errors.New("invalid encoding")} }
第一个字节与上128不为0只有一种情况,那就是b为0b1xxxxxxx
格式的数据,综合前面的编码逻辑可以知道索引Header表示法对应的解码方法为d.parseFieldIndexed
。
第一个字节与上192为64也只有一种情况,那就是b为0b01xxxxxx
格式的数据,综合前面的编码逻辑可以知道增加动态表Header表示法对应的解码方法为d.parseFieldLiteral
。
通过(*Decoder).parseFieldIndexed
解码时,真实的Header数据已经在静态表或者动态表中了,只要通过HPACK索引找到对应的Header就解码成功了。
func (d *Decoder) parseFieldIndexed() error { buf := d.buf idx, buf, err := readVarInt(7, buf) if err != nil { return err } hf, ok := d.at(idx) if !ok { return DecodingError{InvalidIndexError(idx)} } d.buf = buf return d.callEmit(HeaderField{Name: hf.Name, Value: hf.Value}) }
上述方法主要有三个步骤:
通过
readVarInt
函数读取HPACK索引。通过
d.at
方法找到索引列表中真实的Header数据。将Header传递给最上层。
d.CallEmit
最终会调用hdec.SetEmitFunc
设置的闭包,从而将Header传递给最上层。
readVarInt:读取HPACK索引
func readVarInt(n byte, p []byte) (i uint64, remain []byte, err error) { if n < 1 || n > 8 { panic("bad n") } if len(p) == 0 { return 0, p, errNeedMore } i = uint64(p[0]) if n < 8 { i &= (1 << uint64(n)) - 1 } if i < (1<<uint64(n))-1 { return i, p[1:], nil } origP := p p = p[1:] var m uint64 for len(p) > 0 { b := p[0] p = p[1:] i += uint64(b&127) << m if b&128 == 0 { return i, p, nil } m += 7 if m >= 63 { // TODO: proper overflow check. making this up. return 0, origP, errVarintOverflow } } return 0, origP, errNeedMore }
由上述的readVarInt函数知,当第一个字节的低n为不全为1时,则低n为代表真实的HPACK索引,可以直接返回。
当第一个字节的低n为全为1时,需要读取更多的字节数来计算真正的HPACK索引。
第一次循环时m为0,b的低7位加上
(1<<uint64(n))-1
并赋值给i后续循环时m按7递增,b的低7位会逐步填充到i的高位上。
当b小于128时结速循环,此时已经读取完整的HPACK索引。
readVarInt
函数逻辑和前面appendVarInt
函数逻辑相对应。
(*Decoder).at:根据HPACK的索引获取真实的Header数据。
func (d *Decoder) at(i uint64) (hf HeaderField, ok bool) { if i == 0 { return } if i <= uint64(staticTable.len()) { return staticTable.ents[i-1], true } if i > uint64(d.maxTableIndex()) { return } dt := d.dynTab.table return dt.ents[dt.len()-(int(i)-staticTable.len())], true }
索引小于静态表长度时,直接从静态表中获取Header数据。
索引长度大于静态表时,根据前面介绍的HPACK索引列表,可以通过dt.len()-(int(i)-staticTable.len())
计算出i在动态表ents
的真实下标,从而获取Header数据。
通过(*Decoder).parseFieldLiteral
解码时,需要考虑两种情况。一、Header的Name有索引。二、Header的Name和Value均无索引。这两种情况下,该Header都不存在于动态表中。
下面分步骤分析(*Decoder).parseFieldLiteral
方法。
1、读取buf中的HPACK索引。
nameIdx, buf, err := readVarInt(n, buf)
2、 如果索引不为0,则从HPACK索引列表中获取Header的Name。
ihf, ok := d.at(nameIdx) if !ok { return DecodingError{InvalidIndexError(nameIdx)} } hf.Name = ihf.Name
3、如果索引为0,则从buf中读取Header的Name。
hf.Name, buf, err = d.readString(buf, wantStr)
4、从buf中读取Header的Value,并将完整的Header添加到动态表中。
hf.Value, buf, err = d.readString(buf, wantStr) if err != nil { return err } d.buf = buf if it.indexed() { d.dynTab.add(hf) }
(*Decoder).readString: 从编码的字节数据中读取真实的Header数据。
func (d *Decoder) readString(p []byte, wantStr bool) (s string, remain []byte, err error) { if len(p) == 0 { return "", p, errNeedMore } isHuff := p[0]&128 != 0 strLen, p, err := readVarInt(7, p) // 省略校验逻辑 if !isHuff { if wantStr { s = string(p[:strLen]) } return s, p[strLen:], nil } if wantStr { buf := bufPool.Get().(*bytes.Buffer) buf.Reset() // don't trust others defer bufPool.Put(buf) if err := huffmanDecode(buf, d.maxStrLen, p[:strLen]); err != nil { buf.Reset() return "", nil, err } s = buf.String() buf.Reset() // be nice to GC } return s, p[strLen:], nil }
首先判断字节数据是否是哈夫曼编码(和前面的appendHpackString
函数对应),然后通过readVarInt
读取数据的长度并赋值给strLen
。
如果不是哈夫曼编码,则直接返回strLen
长度的数据。如果是哈夫曼编码,读取strLen
长度的数据,并用哈夫曼算法解码后再返回。
在前面我们已经了解了HPACK索引列表,以及基于HPACK索引列表的编/解码流程。
下面笔者最后验证一下已经编解码过后的Header,再次编解码时的大小。
// 此处省略前面HAPACK编码和HPACK解码的demo // try again fmt.Println("try again: ") buf.Reset() henc.WriteField(hpack.HeaderField{Name: "custom-header", Value: "custom-value"}) // 编码已经编码过后的Header fmt.Println(hdec.Write(buf.Bytes())) // 解码 // 输出: // ori size: 197, encoded size: 111 // header field ":authority" = "dss0.bdstatic.com" // header field ":method" = "GET" // header field ":path" = "/5aV1bjqh_Q23odCf/static/superman/img/topnav/baiduyun@2x-e0be79e69e.png" // header field ":scheme" = "https" // header field "accept-encoding" = "gzip" // header field "user-agent" = "Go-http-client/2.0" // header field "custom-header" = "custom-value" // 111 <nil> // try again: // header field "custom-header" = "custom-value" // 1 <nil>
由上面最后一行的输出可知,解码仅用了一个字节,即本例中编码一个已经编码过的Header也仅需一个字节。
综上:在一个连接上,client和server维护一个相同的HPACK索引列表,多个请求在发送和接收Header数据时可以分为两种情况。
Header在HPACK索引列表里面,可以不用传输真实的Header数据仅需传输HPACK索引从而达到标头压缩的目的。
Header不在HPACK索引列表里面,对大多数Header而言也仅需传输Header的Value以及Name的HPACK索引,从而减少Header数据的传输。同时,在发送和接收这样的Header数据时会更新各自的HPACK索引列表,以保证下一个请求传输的Header数据尽可能的少。
最后,由衷的感谢将HTTP2.0系列读完的读者,真诚的希望各位读者能够有所收获。