Subject: Fwd: HPACK

From: Mark Nottingham <[email-masked]>
Date: Tue, 17 Jun 2014 10:55:36 +1000

More feedback from PHK, forwarded with permission.

See:
  <https://github.com/http2/http2-spec/issues/532>

Begin forwarded message:

> Page 8, appending static table
> ------------------------------
> 
> Lacking documentation, I find it somewhat dubious that
> assigning higher indicies to the static tables very common
> entries makes sense performance wise.
> 
> Forcing "GET" to have an index >30 causing it to encode into two
> bytes (or likely even three bytes) rather than one seems very
> counter inuitive.
> 
> The dynmic and shifting indicies for the static table also robs
> high-performance load balancers an important optimization opportunity
> (ie: screening out non-GETs and similar).
> 
> The optimal case is probably to have a small static table
> at the front and another one with less used entries at the
> tail, but I doubt that complexity is warranted.  I would just
> put the static table at the front.
> 
> 
> Page 25, just before the table
> ------------------------------
> 
>   As an example, the Huffman code for the symbol 48 (corresponding to
>   the ASCII character "0") consists in the 5 bits "0", "0", "1", "0",
>   "1".  This corresponds to the value 5 encoded on 5 bits.
> 
> This does not match the table.
> 
> Page 25, the table(s)
> ---------------------
> 
> The RFC should document for the future where these tables came from,
> people are (rightfully) quite paranoid about "magic numbers appearing
> out of nowhere" these days.
> 
> It might be wise to reserve a couple of bits somewhere to allow the
> tables to be revised if experience shows them to be too suboptimal.
> 
> Why does it make sense to assign huffman codes to characters which
> are illegal in HTTP headers, such as 0x01-0x31 and which should cause
> errors if encountered ?
> 
> -- 
> Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
> [email-masked]         | TCP/IP since RFC 956
> FreeBSD committer       | BSD since 4.3-tahoe    
> Never attribute to malice what can adequately be explained by incompetence.

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

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 17 Jun 2014 10:27:36 +0000

> -----Original Message-----
> From: Mark Nottingham [mailto:[email-masked]]
> Sent: mardi 17 juin 2014 02:56
> To: HTTP Working Group
> Subject: Fwd: HPACK
> 

I will add some text to better explain the design choices made here.

> > Page 25, just before the table

This is now correct in the latest version of the spec.

> > Page 25, the table(s)

I added some explanation in the latest version of the spec for the Huffman table. I'll add some for the static table.

>From various experiments and feedback, it can be hoped that the table will not be too suboptimal. In any case, now that we have extensibility back into HTTP/2, we can define a new setting for negotiating the Huffman table to use.

Hervé

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 18 Jun 2014 09:52:54 +0000

In message <[email-masked]>, RUELL

>I will add some text to better explain the design choices made here.

Adding some restrictions which closely mirror similar restrictions
in HTTP/1.1, will make it much easier to do high-speed "triage"
processing of HTTP/2.0.

I would allocate a few constant low indices to the values which
represent the majority of "trivial" traffic:

        1       :method         GET
        2       :scheme         http
        3       :status         200
        4       :status         304
        5       :authority
        6       :path
        7       :query

and I would mandata that a request always provide the following
fields in this exact order, as the first fields in HEADER(...):

	:scheme
	:method
	:authority
	:path
	:query

and that responses always have the :status as the first field.

My finger in the air estimate that this reduces the processing
requirement for the "is this a trivial case" decision by about
a factor of ten.

---

From: Cory Benfield <[email-masked]>
Date: Wed, 18 Jun 2014 11:20:51 +0100

> requirement for the "is this a trivial case" decision by about

This is an interesting proposal, I'll be interested to see the
response it gets from the list. This isn't problematic for hyper to
do, though having to sort the headers is a bit of a pain. I wonder if
it defeats the 'streaming' nature of HPACK, however, if we mandate
some kind of ordering from the higher layers.

I'm tentatively OK with this if intermediaries think it will help them.

---

From: "Martin J. Dürst" <[email-masked]>
Date: Wed, 18 Jun 2014 19:50:06 +0900

> and that responses always have the :status as the first field.

Given that this is essentially the case in HTTP/1.1 (except for :method 
being before :scheme, but we can bikeshead about that), I think that's a 
quite reasonable request.

Regards,   Martin.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 18 Jun 2014 14:10:01 +0200

I'm totally on board with having the static table at fixed index's below
the dynamic table.  I would also like to avoid the need to copy static
entries from the static table to the dynamic table in order to use them!

But we can't require that the first few fields are :scheme etc. because the
intention is that most of those common unchanging fields will end up in the
reference set and not be sent at all.  ie, there is no need to send :scheme
or :authority on every request. :method will mostly be GET or POST and only
occasionally  switch.  Path and query will mostly be sent, so perhaps they
can be first encoded.

Perhaps we can insist that all : headers are sent first and that at the
first non : header, we can then emit all : headers from the refset.

But if we are going to consider such significant changes, then I would
change a lot more about hpack.

cheers

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Michael Sweet <[email-masked]>
Date: Wed, 18 Jun 2014 08:10:24 -0400

Cory,

> some kind of ordering from the higher layers.

Given that these fields are what forms the initial request line in HTTP/1.1, I don't think it will be an issue for streaming...

I'm also +1 on this, and FWIW IPP mandates something similar in its message encoding.

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Mike Bishop <[email-masked]>
Date: Wed, 18 Jun 2014 18:24:45 +0000

They previously were at the beginning, and were moved to the end for a couple of reasons:

·         Having the static table first means that the headers you add are always two bytes to reference instead of one.  An extra byte per indexed header on both add and remove adds up, and analysis of header sets showed that compressor-added entries were referenced more often than entries from the static table.

·         To partially mitigate that, client and server had separate (shorter) static tables; unifying them (since at the end, total length of the static table matters less) reduced complexity.

The copying is there because otherwise, the reference set would include things in the static table.  There was a push for operation to be totally stateless with a context size of zero, which it’s not if you have to track the reference set between requests even without a header table.  (Alternately, you could say that referencing something in the static table doesn’t add it to the reference set, but then you’re forking the semantics of the two tables even further, and the most common headers have to be re-sent every time.)

Requiring headers to be “first” when they’re in the reference set gets interesting.  Your suggestion of having two rounds of reference set emissions is a possible way around that, but requires the decoder to have additional knowledge of the header contents.  Currently, it doesn’t actually know anything about headers, just key-value pairs where both key and value are a series of octets.

I’m certainly not going to argue that what we have is perfect, but I will argue that we previously had some of what’s being proposed, and we moved away from it based on data and the consensus of implementers.  Has new data and implementation experience arisen to suggest we made an error, and is the error of a sufficient magnitude that it’s worth blowing out the schedule?

If not, an extension that always encodes the routing headers as literals and places them first might be an interesting experiment….  ☺

From: Greg Wilkins [mailto:[email-masked]]
Sent: Wednesday, June 18, 2014 5:10 AM
To: HTTP Working Group
Cc: Poul-Henning Kamp
Subject: Re: HPACK

I'm totally on board with having the static table at fixed index's below the dynamic table.  I would also like to avoid the need to copy static entries from the static table to the dynamic table in order to use them!
But we can't require that the first few fields are :scheme etc. because the intention is that most of those common unchanging fields will end up in the reference set and not be sent at all.  ie, there is no need to send :scheme or :authority on every request. :method will mostly be GET or POST and only occasionally  switch.  Path and query will mostly be sent, so perhaps they can be first encoded.
Perhaps we can insist that all : headers are sent first and that at the first non : header, we can then emit all : headers from the refset.
But if we are going to consider such significant changes, then I would change a lot more about hpack.

cheers

On 18 June 2014 11:52, Poul-Henning Kamp <[email-masked]<mailto:[email-masked]>> wrote:
In message <[email-masked]<mailto:[email-masked]>>, RUELL

        1       :method         GET
        2       :scheme         http
        3       :status         200
        4       :status         304
        5       :authority
        6       :path
        7       :query

        :scheme
        :method
        :authority
        :path
        :query

--
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]<mailto:[email-masked]>         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.

--
Greg Wilkins <[email-masked]<mailto:[email-masked]>>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 18 Jun 2014 20:08:04 +0000

Mike,

You may have had some of what I proposed earlier, and you may have
eliminated it because you focused entirely on compression ratio.

What I'm suggesting is focusing on making it possible to implement
HTTP/2.0 at relevant wire speeds on contemporary hardware, even at
the cost of some compression.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 18 Jun 2014 23:30:06 +0200

On 18 June 2014 20:24, Mike Bishop <[email-masked]> wrote:

>
>
> The copying is there because otherwise, the reference set would include
> things in the static table.  There was a push for operation to be totally
> stateless with a context size of zero, which it’s not if you have to track
> the reference set between requests even without a header table.
>

Ah, that's the first I've heard that argument.... and at least it makes
sense.

But surely the copy is a pretty expensive cost on normal stateful operation
in order  to support a possible desire for stateless operation.   It would
have been fair better to just say that if the max table size is 0, then you
can't add entries to the reference set.

(Alternately, you could say that referencing something in the static table
> *doesn’t* add it to the reference set, but then you’re forking the
> semantics of the two tables even further, and the most common headers have
> to be re-sent every time.)
>

Actually I think it would have been good to have the semantic to reference
static entries without adding them to the reference set.   Fields like
:status:404 are hopefully not going to be repeated on the next response.

> I’m certainly not going to argue that what we have is perfect, but I will
> argue that we previously had some of what’s being proposed, and we moved
> away from it based on data and the consensus of implementers.
>
Sure - and it's good enough to go forward as we are to get more data and
implementors.

cheers

---

From: Roberto Peon <[email-masked]>
Date: Wed, 18 Jun 2014 15:15:03 -0700

Note that you don't actually have to copy anything, you just have to
account for it.
An entry in the dynamic table consisting of a bit and a reference to the
static entry would work, for instance.

Expressing it as 'copying' seemed to be the most clear way to get the point
across at the time it was written.

-=R

On Wed, Jun 18, 2014 at 2:30 PM, Greg Wilkins <[email-masked]> wrote:

> But surely the copy is a pretty expensive cost on normal stateful
> operation in order  to support a possible desire for stateless operation.
> It would have been fair better to just say that if the max table size is 0,
> then you can't add entries to the reference set.
>
>>  I’m certainly not going to argue that what we have is perfect, but I
>> will argue that we previously had some of what’s being proposed, and we
>> moved away from it based on data and the consensus of implementers.
>>

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 19 Jun 2014 12:50:56 +0200

Roberto,

I agree that there is not need to copy the bytes.  But that is not the
expense that I'm concerned about.   You have to "copy" the reference to the
entry into the header table and account for it's size.  That means evicting
other entries and causing churn in the header table so useful entries have
to be resent again.

To avoid this table churn, jetty does not use the static entries for things
like :status:404, and instead send them as a non indexed literal with
indexed name and huffman value.  We only put 200 and 304 in the table as we
think they are the only ones for which repeat occurrences are likely, and
thus the table churn is not totally wasted effort.

cheers

On 19 June 2014 00:15, Roberto Peon <[email-masked]> wrote:

> Expressing it as 'copying' seemed to be the most clear way to get the
> point across at the time it was written.
>
> -=R
>
>
>> (Alternately, you could say that referencing something in the static
>>> table *doesn’t* add it to the reference set, but then you’re forking
>>> the semantics of the two tables even further, and the most common headers
>>> have to be re-sent every time.)
>>>
>>
>> Actually I think it would have been good to have the semantic to
>> reference static entries without adding them to the reference set.   Fields
>> like :status:404 are hopefully not going to be repeated on the next
>> response.
>>
>>

---

From: "Martin Nilsson" <[email-masked]>
Date: Thu, 19 Jun 2014 19:47:05 +0200

On Thu, 19 Jun 2014 12:50:56 +0200, Greg Wilkins <[email-masked]> wrote:

>
> To avoid this table churn, jetty does not use the static entries for  
> things like :status:404, and instead send them as a non indexed literal  
> with indexed >name and huffman value.  We only put 200 and 304 in the  
> table as we think they are the only ones for which repeat occurrences  
> are likely, and thus >the table churn is not totally wasted effort.

Having error codes in the table was probably a mistake. Why would you need  
to fail efficiently?

/Martin Nilsson

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Thu, 19 Jun 2014 18:07:23 +0000

>Having error codes in the table was probably a mistake. Why would you need  

I was surprised by the error codes as well.

When that is said, it would make good sense to have suitable
replies for "overload" available so they can be produced
cheaply.