HPACK in Erlang

HTTP/2 Header Encoding

Joe DeVivo / @joedevivo

hpack

joedevivo.com/lambdajam2015

HTTP/2

HTTP/1*

Semantically Identical

What's Different Then?

HTTP/2 in 90 Seconds!

HTTP/2 Connection

How?

Multiplexed Streams

It's Binary!

Frames

+-----------------------------------------------+
|                 Length (24)                   |
+---------------+---------------+---------------+
|   Type (8)    |   Flags (8)   |
+-+-------------+---------------+-------------------------------+
|R|                 Stream Identifier (31)                      |
+=+=============================================================+
|                   Frame Payload (0...)                      ...
+---------------------------------------------------------------+

Jargon Watch!

A connection has multiple streams each of which can accept a single request message, and send a single response message, each message consisting of multiple frames in order

Frames

What you need to know!

  • There's a maximum length
  • Flags signal if more are coming

Type (8)

10 Types

  • HEADERS
  • CONTINUATION

  • PUSH_PROMISE

PUSH_PROMISE?!

Phew!

HPACK - RFC-7541

A whole spec just for header compression

What's HPACK About?

Where HPACK fits in HTTP/2

HEADERS

Name          Value
+------------+---------------+
|   :path    |       /       |
+------------+---------------+
| user-agent |      IE6      |
+------------+---------------+
|  :method   |     POST      |
+------------+---------------+
|   accept   |  text/plain   |
+------------+---------------+
|   cookie   |      ...      |
+------------+---------------+

HPACK Shrinks That

hpack:encode(Headers, Context).

+--------------------------+
|                          |
|   Encoded Header Block   |
|                          |
+--------------------------+

Maybe too big?

Break it up!

+--------+ +--------+ +--------+
|Fragment| |Fragment| |Fragment|
|   #1   | |   #2   | |   #3   |
|        | |        | |        |
+--------+ +--------+ +--------+

They've been Framed!

+------------+   +------------+   +------------+
|  HEADERS   |   |CONTINUATION|   |CONTINUATION|
+------------+   +------------+   +------------+
|    NONE    |   |    NONE    |   |END_HEADERS |
+------------+   +------------+   +------------+
|Fragment #1 |   |Fragment #2 |   |Fragment #3 |
|            |   |            |   |            |
+------------+   +------------+   +------------+

Send them over the wire

+------------+
|  HEADERS   |
+------------+
|    NONE    |
+------------+
|Fragment #1 |
|            |
+------------+

Send them over the wire

+------------+
|CONTINUATION|
+------------+
|    NONE    |
+------------+
|Fragment #2 |
|            |
+------------+

Send them over the wire

+------------+
|CONTINUATION|
+------------+
|END_HEADERS |
+------------+
|Fragment #3 |
|            |
+------------+

Reconstruct the Encoded Header Block

+------------+   +------------+   +------------+
|  HEADERS   |   |CONTINUATION|   |CONTINUATION|
+------------+   +------------+   +------------+
|    NONE    |   |    NONE    |   |END_HEADERS |
+------------+   +------------+   +------------+
|Fragment #1 |   |Fragment #2 |   |Fragment #3 |
|            |   |            |   |            |
+------------+   +------------+   +------------+

Reconstruct the Encoded Header Block

+--------+ +--------+ +--------+
|Fragment| |Fragment| |Fragment|
|   #1   | |   #2   | |   #3   |
|        | |        | |        |
+--------+ +--------+ +--------+

Reconstruct the Encoded Header Block

+--------------------------+
|                          |
|   Encoded Header Block   |
|                          |
+--------------------------+

HPACK Decode

hpack:decode(BinaryHeaderBlock, Context).

It's a header list again!

Name          Value
+------------+---------------+
|   :path    |       /       |
+------------+---------------+
| user-agent |      IE6      |
+------------+---------------+
|  :method   |     POST      |
+------------+---------------+
|   accept   |  text/plain   |
+------------+---------------+
|   cookie   |      ...      |
+------------+---------------+

How it does it

Header Compression

HTTP is stateless

Stateless protocols are repetitive

Stateless protocols are repetitive

Compression Context is Stateful

What is a Compression Context?

The Static Table

+-------+--------------------+---------------+
| Index | Header Name        | Header Value  |
+-------+--------------------+---------------+
| 1     | :authority         |               |
| 2     | :method            | GET           |
| 3     | :method            | POST          |
| 4     | :path              | /             |
| 5     | :path              | /index.html   |
| 6     | :scheme            | http          |
| 7     | :scheme            | https         |
| 8     | :status            | 200           |
| 13    | :status            | 404           |
| 14    | :status            | 500           |
| 15    | accept-charset     |               |
| 16    | accept-encoding    | gzip, deflate |
                    ...
| 57    | transfer-encoding  |               |
| 58    | user-agent         |               |
| 59    | vary               |               |
| 60    | via                |               |
| 61    | www-authenticate   |               |
+-------+--------------------+---------------+

hpack_index.erl

[{1  , <<":authority">>       , undefined},
 {2  , <<":method">>          , <<"GET">>},
 {3  , <<":method">>          , <<"POST">>},
 {4  , <<":path">>            , <<"/">>},
 {5  , <<":path">>            , <<"/index.html">>},
 {6  , <<":scheme">>          , <<"http">>},
 {7  , <<":scheme">>          , <<"https">>},
 {8  , <<":status">>          , <<"200">>},
 {13 , <<":status">>          , <<"404">>},
 {14 , <<":status">>          , <<"500">>},
 {15 , <<"accept-charset">>   , undefined},
 {16 , <<"accept-encoding">>  , <<"gzip, deflate">>},
              ...
 {57 , <<"transfer-encoding">>, undefined},
 {58 , <<"user-agent">>       , undefined},
 {59 , <<"vary">>             , undefined},
 {60 , <<"via">>              , undefined},
 {61 , <<"www-authenticate">> , undefined}]

Initial Context

IS

the Static Table

The Dynamic Table

Add your own!

Indexes 62+

Bounded by size in the HTTP/2 Connection Settings

Dynamic Table Source

-type header_name() :: binary().
-type header_value():: binary().
-define(DYNAMIC_TABLE_MIN_INDEX, 62).

-record(dynamic_table, {
    table = [] :: [{pos_integer(), header_name(), header_value()}],
    max_size = 4096 :: pos_integer(),
    size = 0 :: non_neg_integer()
}).
-type dynamic_table() :: #dynamic_table{}.

hpack API

-spec encode([{binary(), binary()}], encode_context()) ->
                                 {binary(), encode_context()}.
-spec decode(binary(), decode_context()) ->
                                 {headers(), decode_context()}.

Identity Property

Encoding a header that has already been encoded, does not change the context 

StaticTable = hpack:new_encode_context(),
{HeaderBin, StaticTable} =
    hpack:encode([{<<":status">>, <<"200">>}], StaticTable).

StaticTable = hpack:new_decode_context(),
{[{<<":status">>, <<"200">>}], StaticTable} =
    hpack:decode(HeaderBin, StaticTable).

Context Modifying Operation

Encoding something new, changes the dynamic table 

StaticTable = hpack:new_encode_context(),
{HeaderBin, NewContext} =
    hpack:encode([{<<":status">>, <<"600">>}], StaticTable),
NewContext =/= StaticTable,
%% Second time we try and encode this header
{HeaderBin, NewContext} =
    hpack:encode([{<<":status">>, <<"600">>}], NewContext).

Every Header changes the context

Where do they live?

There Are Four Contexts!

Given two peers: X & Y, connected over C

  • A1: encoding outbound requests on X to Y over C
  • A2: decoding inbound requests on Y from X over C
  • B1: encoding outbound responses on Y to X over C
  • B2: decoding inbound responses on X from Y over C

The Basic Case

                    +---------------+           +---------------+
                    |Peer X (Client)|           |Peer Y (Server)|
+-------------------+---------------+           +---------------+-------------------+
|                                   |           |                                   |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
| |Plain Req |   |Encode (A1)|   | Encoded Request |   |Decode (A2)|   |Plain Req | |
| | Headers  |-->|  Context  |-->|     Headers     |-->|  Context  |-->| Headers  | |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
|                                   |   Cloud   |                                   |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
| |Plain Resp|   |Decode (B2)|   |Encoded Response |   |Encode (B1)|   |Plain Resp| |
| | Headers  |<--|  Context  |<--|     Headers     |<--+- Context  |<--| Headers  | |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
|                                   |           |                                   |
|                                   |           |                                   |
+-----------------------------------+           +-----------------------------------+

A More Interesting Case

                    +---------------+           +---------------+
                    |Peer X (Client)|           |Peer Y (Server)|
+-------------------+---------------+           +---------------+-------------------+
|                                   |           |                                   |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
| |Plain Req |   |           |   | Encoded Request |   |           |   |Plain Req | |
| |Headers #1|-->|           |-->|   Headers #1    |-->|           |-->|Headers #1| |
| +----------+   |           |   +--+-----------+--+   |           |   +----------+ |
| +----------+   |           |   +--+-----------+--+   |           |   +----------+ |
| |Plain Req |   |           |   | Encoded Request |   |           |   |Plain Req | |
| |Headers #2|-->|           |-->|   Headers #2    |-->|           |-->|Headers #2| |
| +----------+   |Encode (A1)|   +--+-----------+--+   |Decode (A2)|   +----------+ |
| +----------+   |  Context  |   +--+-----------+--+   |  Context  |   +----------+ |
| |Plain Req |   |           |   | Encoded Request |   |           |   |Plain Req | |
| |Headers #3|-->|           |-->|   Headers #3    |-->|           |-->|Headers #3| |
| +----------+   |           |   +--+-----------+--+   |           |   +----------+ |
| +----------+   |           |   +--+-----------+--+   |           |   +----------+ |
| |Plain Req |   |           |   | Encoded Request |   |           |   |Plain Req | |
| |Headers #4|-->|           |-->|   Headers #4    |-->|           |-->|Headers #4| |
| +----------+   +-----------+   +--+-----------+--+   +-----------+   +----------+ |
+-----------------------------------+           +-----------------------------------+

Order Matters!

+---------------+           +---------------+
|Peer X (Client)|           |Peer Y (Server)|
+---------------+           +---------------+------------------------------+
                |           |                                              |
---------+   +--+-----------+--+              +-----------+   +----------+ |
         |   | Encoded Request |              |           |   |Plain Req | |
         |-->|   Headers #1    |------------->|           |-->|Headers #1| |
         |   +--+-----------+--+              |           |   +----------+ |

         |   +--+-----------+--+              |           |   +----------+ |
         |   | Encoded Request |              |           |   | Bad Req  | |
         |-->|   Headers #2    |------\       |           |-->|Headers #3| |
code (A1)|   +--+-----------+--+   ----\----->|Decode (A2)|   +----------+ |
Context  |   +--+-----------+--+  /     \     |  Context  |   +----------+ |
         |   | Encoded Request |-/       \    |           |   |Bad Req   | |
         |-->|   Headers #3    |          --->|           |-->|Headers #2| |
         |   +--+-----------+--+              |           |   +----------+ |
         |   +--+-----------+--+              |           |   +----------+ |
         |   | Encoded Request |              |           |   |Plain Req | |
         |-->|   Headers #4    |------------->|           |-->|Headers #4| |
---------+   +--+-----------+--+              +-----------+   +----------+ |
                |           |                                              |
---------+   +--+-----------+--+              +-----------+   +----------+ |
code (B2)|   |Encoded Response |              |Encode (B1)|   |Plain Resp| |
Context  |<--|     Headers     |<-------------|  Context  |<--| Headers  | |
---------+   +--+-----------+--+              +-----------+   +----------+ |
----------------+           +----------------------------------------------+

How HPACK Packs

Data Types

  • Numbers
  • Strings

Indexed Header Field

0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+

7+?

  • Indexes can be greater than 2^7-1 (127)
  • Sometimes HPACK has as few as 5 bits to use.

Integer Representation (N=5)

0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | 1   1   1   1   1 |
+---+---+---+-------------------+
| 1 |    Value-(2^N-1) LSB      |
+---+---------------------------+
               ...
+---+---------------------------+
| 0 |    Value-(2^N-1) MSB      |
+---+---------------------------+

1337, N=5

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 1 | 1 | 1 | 1 | 1 |  Prefix = 31, I = 1306
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |  1306>=128, encode(154), I=1306/128
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |  10<128, encode(10), done
+---+---+---+---+---+---+---+---+

1306

0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+---+

10

0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+---+---+

hpack_integer:encode(1337, 5)

encode(Int, N) when Int < (1 bsl N - 1) ->
    <<Int:N>>;
encode(Int, N) ->
    Prefix = 1 bsl N - 1,
    Remaining = Int - Prefix,
    Bin = encode_(Remaining, <<>>),
    <<Prefix:N, Bin/binary>>.

<

encode(Int, N) when Int < (1 bsl N - 1) ->
    <<Int:N>>;

>=

encode(Int, N) ->
    Prefix = 1 bsl N - 1, %% (2^N)-1
    Remaining = Int - Prefix,
    Bin = encode_(Remaining, <<>>),
    <<Prefix:N, Bin/binary>>.

hpack_integer

-spec encode_(non_neg_integer(), binary()) -> binary().
encode_(I, BinAcc) ->
    LeastSigSeven = (I rem 128),
    RestToEncode = I bsr 7,
    case RestToEncode of
        0 ->
            <<BinAcc/binary, LeastSigSeven>>;
        _ -> %% Adds the continuation bit
            ThisByte = 2#10000000 bor LeastSigSeven,
            encode_(RestToEncode, <<BinAcc/binary, ThisByte>>)
    end.

call stack

EncInt = hpack_integer:encode(1337, 5) ->
  <<2#11111:5, hpack_integer:encode_(1306, <<>>)>>.
hpack_integer:encode_(1306, <<>>) ->
  hpack_integer:encode_(10, <<2#10011010>>).
hpack_integer:encode_(10, <<2#10011010>>) ->
  <<2#10011010,2#00001010>>.

EncInt = <<2#11111:5,2#10011010,2#00001010>>.

Livin' on the edge: 31, N=5

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 1 | 1 | 1 | 1 | 1 |  Prefix = 31, I = 0
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  0<128, encode(0), done
+---+---+---+---+---+---+---+---+

Literal Header Field w/ Index

0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+

Huffman Code

  • uses less than 8 bits per char (sometimes)
  • the more common the char, the fewer bits

Huffman examples

                                                     code
                       code as bits                 as hex   len
     sym              aligned to MSB                aligned   in
                                                    to LSB   bits
' ' ( 32)  |010100                                       14  [ 6]
'!' ( 33)  |11111110|00                                 3f8  [10]
'"' ( 34)  |11111110|01                                 3f9  [10]
'#' ( 35)  |11111111|1010                               ffa  [12]
'$' ( 36)  |11111111|11001                             1ff9  [13]
'0' ( 48)  |00000                                         0  [ 5]
'1' ( 49)  |00001                                         1  [ 5]
'2' ( 50)  |00010                                         2  [ 5]
'r' (114)  |101100                                       2c  [ 6]
's' (115)  |01000                                         8  [ 5]
't' (116)  |01001                                         9  [ 5]
    (253)  |11111111|11111111|11111101|111          7ffffef  [27]
    (254)  |11111111|11111111|11111110|000          7fffff0  [27]
    (255)  |11111111|11111111|11111011|10           3ffffee  [26]

Literal Header Field non-Indexed

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)  |
+-------------------------------+

Types of Literal Fields

  • with Indexing - added to the dynamic table
  • without Indexing - not added to the DT
  • never Indexed - never added to any DT

Binary Pattern Matching!

decode(<<>>, HeadersAcc, C) -> {HeadersAcc, C};
%% First bit is '1', so it's an 'Indexed Header Feild'
decode(<<2#1:1,_/bits>>=B, HeaderAcc, Context) ->
    decode_indexed_header(B, HeaderAcc, Context);
%% First two bits are '01' so it's a 'Literal Header Field with Incremental Indexing'
decode(<<2#01:2,_/bits>>=B, HeaderAcc, Context) ->
    decode_literal_header_with_indexing(B, HeaderAcc, Context);
%% First four bits are '0000' so it's a 'Literal Header Field without Indexing'
decode(<<2#0000:4,_/bits>>=B, HeaderAcc, Context) ->
    decode_literal_header_without_indexing(B, HeaderAcc, Context);
%% First four bits are '0001' so it's a 'Literal Header Field never Indexed'
decode(<<2#0001:4,_/bits>>=B, HeaderAcc, Context) ->
    decode_literal_header_never_indexed(B, HeaderAcc, Context);
%% First three bits are '001' so it's a 'Dynamic Table Size Update'
decode(<<2#001:3,_/bits>>=B, HeaderAcc, Context) ->
    decode_dynamic_table_size_update(B, HeaderAcc, Context);

HPACK Tables Example

Three Requests

Headers1 = [
           {<<":path">>, <<"/">>},
           {<<"user-agent">>, <<"my cool browser">>},
           {<<"x-custom-header">>, <<"some custom value">>}
          ],
HeaderContext1 = hpack:new_encode_context(),
{HeadersBin1, HeaderContext2} = hpack:encode(Headers1, HeaderContext1),

Headers2 = [
           {<<":path">>, <<"/some_file.html">>},
           {<<"user-agent">>, <<"my cool browser">>},
           {<<"x-custom-header">>, <<"some custom value">>}
          ],
{HeadersBin2, HeaderContext3} = hpack:encode(Headers2, HeaderContext2),

Headers3 = [
           {<<":path">>, <<"/some_file.html">>},
           {<<"user-agent">>, <<"my cool browser">>},
           {<<"x-custom-header">>, <<"new value">>}
          ],
{HeadersBin3, _HeaderContext4} = hpack:encode(Headers3, HeaderContext3),

Request #1

Headers1 = [
   {<<":path">>, <<"/">>},
   {<<"user-agent">>, <<"my cool browser">>},
   {<<"x-custom-header">>, <<"some custom value">>}
],

Wiresharked R1

Header: :path: /
    Representation: Indexed Header Field

    Index: 4
Header: user-agent: my cool browser
    Representation: Literal Header Field with Incremental Indexing - Indexed Name

    Index: 58
    Value: my cool browser
Header: x-custom-header: some custom value
    Representation: Literal Header Field with Incremental Indexing - New Name

    Name: x-custom-header
    Value: some custom value

R1 Context Updates

DynamicTable = [
                {62,<<"x-custom-header">>,<<"some custom value">>},
                {63,<<"user-agent">>,     <<"my cool browser">>}
              ]
  • :path changes nothing
  • "user-agent"/"my cool browser" is now Index 62
  • "x-custom-header"/"some custom value" is now Index 62
  • "user-agent"/"my cool browser" is +1'd to 63

Request #2

Headers2 = [
  {<<":path">>, <<"/some_file.html">>},
  {<<"user-agent">>, <<"my cool browser">>},
  {<<"x-custom-header">>, <<"some custom value">>}
],

Wiresharked R2

Header: :path: /some_file.html
    Representation: Literal Header Field with Incremental Indexing - Indexed Name

    Index: 4
    Value: /some_file.html
Header: user-agent: my cool browser
    Representation: Indexed Header Field

    Index: 64
Header: x-custom-header: some custom value
    Representation: Indexed Header Field

    Index: 63

R2: Context updates

[
  {62,<<":path">>,          <<"/some_file.html">>},
  {63,<<"x-custom-header">>,<<"some custom value">>},
  {64,<<"user-agent">>,     <<"my cool browser">>}
]
  • ":path"/"/some_file.html" is the new Index 62
  • "x-custom-header"/"some custom value" is +1'd 63
  • "user-agent"/"my cool browser" is +1'd to 64

Request #3

Headers3 = [
  {<<":path">>, <<"/some_file.html">>},
  {<<"user-agent">>, <<"my cool browser">>},
  {<<"x-custom-header">>, <<"new value">>}
],

Wiresharked R3

Header: :path: /some_file.html
    Representation: Indexed Header Field

    Index: 62
Header: user-agent: my cool browser
    Representation: Indexed Header Field

    Index: 64
Header: x-custom-header: new value
    Representation: Literal Header Field with Incremental Indexing - Indexed Name

    Index: 63
    Value: new value

R3: Context updates

[
  {62,<<"x-custom-header">>,<<"new value">>},
  {63,<<":path">>,          <<"/some_file.html">>},
  {64,<<"x-custom-header">>,<<"some custom value">>},
  {65,<<"user-agent">>,     <<"my cool browser">>}
]
  • "x-custom-header"/"new value" is the new 62
  • ":path"/"/some_file.html" is +1'd to 63
  • "x-custom-header"/"some custom value" is +1'd 64
  • "user-agent"/"my cool browser" is +1'd to 65

Thanks!

github.com/joedevivo/hpack