Implementation and Analysis of HPACK 05

HPACK 05 has following compression mechanisms:

Index
By sharing learning dictionary of headers, a header can be represented as a small integer.
Reference set
By comparing a set of the previous indices and that of the current indices, difference can be calculated.
Huffman code
Strings (header names and header values) themselves can be shorten.

Since "reference set" depends on "index", we can consider 6 kinds of HPACK encoding. For convenience, I give a name for each.

Index Refset Huffman
Naive - - -
NaiveH - - X
Linear X - -
LinearH X - X
Diff X X -
DiffH X X X

To implement Naive and Linear, an HPACK encoder first sends index 0 to clear reference set and encodes the headers in order (see Appendix in detail). The algorithm for Diff was posted to ietf-http-wg ML by Tsujikawa, the author of "nghttp2". The last "H" means using huffman encoding.

Note that the order of headers is kept in Naive and Linear while not in Diff.

I implemented the 6 encodings above in my implementation, the http2 library in Haskell. We Japanese community provides test cases for HPACK. My http2 library passed the all inter-operability tests.

As you can see, we provides 31 stories where 21 stories for HTTP request and 10 stories for HTTP response. Of course, each story targets the same :authority in it.

Correction: it appeared that multiple :authority values are mixed together. We should make another experiment with better input.

We can also use these test cases to calculate compression ratio. Compression ration is calculated by dividing the length of result representation by that of header set.

Here is the results.

I confirmed the following things.

  • The "hpack" library in Go uses NaiveH. I verified that my NaiveH encoding produces the same results as it.
  • "nghttp2" uses DiffH. I verified that my DiffH encoding produces the same results as it.

Here is a chart to visualize the results:

As you can see, Diff(H) has almost the same compression ratio as Linear(H). My calculation leads to the following conclusion.

  • Diff(H) saves only 1.57 byte per HEADERS frame in average against Linear(H).
  • Huffman encoding saves 31.36 bytes per HEADERS frame in average against non-huffman.

So, I would suggest the designers of HPACK to remove reference set. This has the following advantages:

  • Implementation of HPACK encoder becomes much easier.
  • Inter-operability is improved.
  • The order of headers are always kept.
  • The compression ratio does not go worse.

Implementation notes

I first implemented HPACK with simple data structures and algorithms. Profiling tells me there were three bottlenecks:

  1. Converting a header to an index in HPACK encoding.
  2. Converting bit sequence to a character in Huffman decoding.
  3. Concatenating bit sequences in Huffman encoding.

Linear search is slow for the purpose of 1). To solve this problem, I created a reverse index. To avoid hash DOS attacks, I used search trees to implement it. Since we need to find either an index for a pair of header key and header value OR an index for a header key, search trees should be nested. When the outer search tree is looked up with a header key, an inner search tree cab be obtained if exists. Then the inner search tree is looked up with a header value.

My choice is as follows:

Bit-by-bit traversing on a binary tree is slow for the purpose of 2). So, I adopted Fast Prefix Code Processing. I prepared state transition tables for 4 bits. The reason why I chose 4 bits, not 8 bits, is that 4 bits can ensure one character is generated at most.

To solve problem 3, I prepared N shifted bytes for bit sequences in advance where N is from 0 to 7. Concatenation can be done just by copying bytes and ORed a seam point if necessary.

Conclusion

  • Index
    • It has good compression ratio.
    • Fast implementation is possible.
  • Reference set
    • It has poor compression ratio.
    • It should be removed from HPACK.
  • Huffman encoding
    • Its compression ratio is so so.
    • Fast implementation is possible.

Appendix

To see the difference between Naive and Linear, let's see examples. Suppose that the first header set is as follows:

key1: value1
key2: value2
key3: value3

Both Naive and Linear encodes this to:

Indexed 0
Literal NotAdd (Lit "key1") "value1"
Literal NotAdd (Lit "key2") "value2"
Literal NotAdd (Lit "key3") "value3"

Then suppose that the next header set is as follows:

key1: value1
key2: value2
key3: value3'

Naive encodes this to:

Indexed 0
Literal NotAdd (Lit "key1") "value1"
Literal NotAdd (Lit "key2") "value2"
Literal NotAdd (Lit "key3") "value3'"

Linear encodes this to:

Indexed 0
Indexed 3
Indexed 2
Literal Add (Idx 1) "value3'"