Subject: HTTP/2 Header Encoding Status Update

From: James M Snell <[email-masked]>
Date: Wed, 27 Feb 2013 13:16:16 -0800

As I'm not going to be able to meet y'all in Orlando, I wanted to give
a quick status update on where I'm at with the Header Encoding.

After much experimentation, implementation and discussion with
Roberto, I've got an implementation that is a good balance between
Delta and BOHE. It uses the fundamental delta encoding mechanism that
Roberto created (with a few notable changes) but allows for four
distinct types of header values: text, numeric, date and raw-binary.
Every header value is encoded with a single additional byte flag that
indicates the value type. Further, the flags indicate whether text is
ISO-8559-1 or UTF-8 and whether it is huffman-coded or not.  This
scheme gives us a good balance and allows us to achieve maximum
compression ratios and increased long term functionality without
sacrificing too much in complexity or backwards compatibility.

Text values:

  The rules for text values are simple:

  1. Text can be either UTF-8 or ISO-8859-1 Encoded. A single bit in
the flags is used to indicate which it is.
  2. Text can be huffman coded or not. A single bit in the flags is
used to indicate which.
  3. A single text header field may contain up to 0xFF separate text
strings of arbitrary length.
  4. Each individual text string is prefixed by a unsigned, variable
length integer specifying the length of the string.

  For example, assuming UTF-8 and non-huffman coded values...

  The string value "Bar" is encoded as:
    10 00 03 42 61 72

    10 = Flags byte
    00 = Number of values encoded (0-based.. 00 == one value)
    03 = uvarint length of the value
    42 61 72 = UTF-8 bytes

  The multiple string values ["Bar", "Baz"] would encode as:
     10 01 03 42 61 72 03 42 61 7A

Numeric values:

  1. Numeric values are encoded as variable-length, unsigned integers.
  2. Numeric headers can only have a single encoded value (text values
are the only ones that allow multiples)

  For example, value "100" is encoded as 24 64

  25 = Flags byte indicating numeric value
  64 = uvarint encoded value

Date values:

  1. Dates are encoded as the number of seconds since a new epoch
(Midnight GMT, Jan 1 1990)
  2. Encoded as uvarints, just like Numeric values, but with an
additional flag bit set

  For example, the date "2013-02-27T12:51:19.409-08:00" is encoded as:
    26 AA A9 BF DC 02

  26 = Flags byte indicating date value
  AA A9 BF DC 02 = uvarint indicating the date

Binary values:

  1. Binary values are encoded as a raw sequence of octets prefixed by
the length encoded as a uvarint

  For example, the byte sequence 01 02 03 is encoded as:
    20 03 01 02 03

Those four encodings would be all we define within the basic header
encoding. At the HTTP semantics layer, specific headers would be
required to explicitly declare support for numeric, date or binary
encoding. This means that all of the existing HTTP header definitions,
which are currently all text, would be required to use the Text value
encoding unless they are specifically redefined to use the new type
options. Specific headers in the core set (:status, content-length,
date, last-modified, etc) would be have updated definitions to allow
those to use the new more compact encodings right from the start. This
allows us to get some immediate benefit out of the box and gives us a
way of smoothly transitioning headers over to more compact and
optimized encoding options later on without sacrificing backwards
compatibility.

Differences from Delta:

  The scheme I have implemented has a number of technical details that
are different from Roberto's delta implementation. These details are
fairly technical and low level so feel free to ignore them unless you
have a particular interest in implementation details at this point...

  1. For one, I wrote the thing in Java.. which is good, we now have
at least three different language implementations of the basic delta
scheme. (C++, python and Java)
  2. It uses uvarints for all length prefixing rather than fixed width
integer encodings.
  3. It uses all of the above type encodings
  4. It uses a slightly different mechanism for managing and
renumbering the delta storage state index. This is an internal
difference in implementation but all implementations will be required
to implement the same basic scheme for reindexing internal state so I
am evaluating different options to see which is the most efficient.
  5. It introduces an additional "Ephemeral Clone" opcode which is
essentially a combination of Clone and Eref (it's like clone but
doesn't change state).
  6. It implements additional heuristics for determining when to merge
multiple adjacent toggl indices into a single trang operation.
Basically, it just checks to see if converting to a Trang would save
or cost additional bytes before doing the conversion.
  7. It uses eref or eclone operations for :path, referer,
authorization, www-authenticate, proxy-authenticate, date and
last-modified headers. These tend to change very frequently and take
up a significant amount of space in the storage context. Given how
variable these are, it doesn't make sense to store them. The
likelihood of reuse within a given context is minimal compared to the
cost of storage.
  8. It uses a modified version of the default header dictionary used
by Roberto's delta implementation. I've added additional values and
changed it to use the new value encodings.
  9. I have not yet implemented the additional huffman coding for text values.

I'm still working on making the delta state management as efficient as
possible in my implementation. The running time for the
serialize-deserialize roundtrip is still well above what I'm happy
with. Part of that is Java's fault, part of it is the delta mechanism
itself.

Anyway, that's the run down. Still a ways off from having something
that I'd be comfortable calling "complete" but looking pretty good so
far.

- James

---

From: Julian Reschke <[email-masked]>
Date: Wed, 27 Feb 2013 22:55:38 +0100

> the flags is used to indicate which it is.

Why can't we stick to UTF-8 for text?

 > ...

Best regards, Julian

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Feb 2013 14:00:44 -0800

> Why can't we stick to UTF-8 for text?

A good question.  Conversion to and from ISO-8859-1 is probably easier
than supporting both in protocol.  Saves a bit too.

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 28 Feb 2013 09:45:08 +1100

Hi James,

> sacrificing too much in complexity or backwards compatibility.

Thanks. That sounds good.

>  The string value "Bar" is encoded as:

So, the biggest concern here, I think, is that the conversion of a UTF-8 value to ASCII/Latin-1 -- to be able to forward the header on a HTTP/1.x hop -- requires knowledge of the header.

Would you want to define a standard way to encode UTF-8 in Latin-1 (e.g., percent-encoding) for headers that use this? It would constrain the headers (and likely rule out any existing headers from using UTF-8), but I don't see how this is going to be viable otherwise.

>  For example, the byte sequence 01 02 03 is encoded as:

Similar problem as with UTF-8, unless you define a single transformation between binary and ASCII (base64?).

> that I'd be comfortable calling "complete" but looking pretty good so

All good stuff. Thanks again,

--
Mark Nottingham   http://www.mnot.net/

---

From: James M Snell <[email-masked]>
Date: Wed, 27 Feb 2013 15:00:08 -0800

On Wed, Feb 27, 2013 at 2:45 PM, Mark Nottingham <[email-masked]> wrote:
>[snip]

Yes, I think that is reasonable. One key thing is that existing
headers would need to be explicitly redefined to take advantage of the
new encoding options so it would be technically invalid to take any of
the existing headers and encode them as UTF-8 unless their definition
has been changed in spec. That said, a standard mapping like you
suggest would be good in the cases we do have to drop down from http/2
to /1. Percent-encoding seems to be perfectly reasonable.

>[snip]

Yes, I had imagined that the transform here would be base64.

- James

---

From: James M Snell <[email-masked]>
Date: Wed, 27 Feb 2013 15:02:27 -0800

I'd prefer only a single option also but I want to avoid having to
re-encode data when going from http/1 to http/2... I'd like the option
of passing stuff through as is when it's appropriate to do so. For the
most part, tho, I'd personally prefer UTF-8 only across the board. If
we can reach consensus on that point I'd gladly drop the extra bit.

- James

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 28 Feb 2013 10:03:58 +1100

One other thing - 

> (Midnight GMT, Jan 1 1990)

So, how many bytes does changing the epoch save us?

I just get concerned about putting little landmines like this in...

Cheers,

---

From: James M Snell <[email-masked]>
Date: Wed, 27 Feb 2013 15:12:25 -0800

Not much really... assuming we're representing the value as a 64-bit
long, the maximum number of uvarint bytes we can ever encode for each
date is 10. Using the original epoch, I think we use six bytes
currently. The new epoch uses five. As it is, the use of the uvarint
gives us plenty of room to grow with or without the new epoch so I'd
be perfectly fine without that detail.

- James

---

From: James Cloos <[email-masked]>
Date: Wed, 27 Feb 2013 20:24:42 -0500

>>>>> "JMS" == James M Snell <[email-masked]> writes:

JMS> Not much really... assuming we're representing the value as a 64-bit
JMS> long, the maximum number of uvarint bytes we can ever encode for each
JMS> date is 10. Using the original epoch, I think we use six bytes
JMS> currently. The new epoch uses five. As it is, the use of the uvarint
JMS> gives us plenty of room to grow with or without the new epoch so I'd
JMS> be perfectly fine without that detail.

A quick test reminds one that the tick before 1990/01/01 00:00:00 UTC was
1989/12/31 23:59:60 UTC, a leap second.  So the reference will differ
depending on right vs posix localtime rules and be extra ambiguous because
it is just after a leap second.

  :; TZ=posix/UTC perl -e 'print localtime(631152000)."\n"'
  Mon Jan  1 00:00:00 1990

  :; TZ=right/UTC perl -e 'print localtime(631152015)."\n"'
  Mon Jan  1 00:00:00 1990

It probably would be better to define a specific offset from time_t 0 or
a specific offset from the GPS epoch.  Or even better define time zero
to be a specific 128-bit ntp time.

But it would be easier to use either time_t or an ntp timestamp directly.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 1024D/ED7DAEA6

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 28 Feb 2013 19:05:59 +1300

> we can reach consensus on that point I'd gladly drop the extra bit.

We are already re-encoding the text->binary forms of the headers in such 
gateways. The whole process is relatively slow and re-coding to UTF-8 is 
a trivial part of the whole process.

I'm for UTF-8 where possible.

Amos

---

From: Julian Reschke <[email-masked]>
Date: Thu, 28 Feb 2013 08:27:09 +0100

> to /1. Percent-encoding seems to be perfectly reasonable.

That's not going to work for existing header fields and existing code on 
HTTP/1.1.

This is a hairy problem. If it wasn't, we would already have solved it.

Best regards, Julian

---

From: "Martin J. Dürst" <[email-masked]>
Date: Thu, 28 Feb 2013 17:11:37 +0900

Hello Julian,

> This is a hairy problem. If it wasn't, we would already have solved it.

Can you give actual examples?

Regards,   Martin.

---

From: Julian Reschke <[email-masked]>
Date: Thu, 28 Feb 2013 09:22:20 +0100

> Can you give actual examples?

Non-ASCII characters in Content-Disposition's filename parameter; 
sometimes decoded as UTF-8, sometimes as ISO-8859-1, sometimes based on 
the referring page's encoding, sometimes using the browser's default locale.

Whatever you choose here *will* break some UAs.

Best regards,

Julian

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 28 Feb 2013 19:22:27 +1100

On 28/02/2013, at 6:27 PM, Julian Reschke <[email-masked]> wrote:

> That's not going to work for existing header fields and existing code on HTTP/1.1.
> 

I think what's being suggested is that *new* headers can opt-in to a format whereby the entire value is percent-encoded where needed when expressed in Latin-1, but not when it's in UTF-8. Existing headers wouldn't be able to do so (unless they already fit this convention).

Cheers,

---

From: Julian Reschke <[email-masked]>
Date: Thu, 28 Feb 2013 10:13:27 +0100

> I think what's being suggested is that *new* headers can opt-in to a format whereby the entire value is percent-encoded where needed when expressed in Latin-1, but not when it's in UTF-8. Existing…

But for *new* headers we could simply pick UTF-8, no? (even on 1.1)

Best regards, Julian