Subject: Header Compression Implementation Feedback

From: James M Snell <[email-masked]>
Date: Mon, 8 Jul 2013 13:33:53 -0700

So I've gone through and updated my header compression implementation
based on the current spec. Some feedback (shouldn't be too surprising
to anyone who may have followed my previous inputs on this topic)

1. I'd be *MUCH* happier without the Differential Encoding and the
Reference Set requirement. These mechanisms are designed to further
cut down on the number of bits set across the wire but they do add
complexity to the implementation that I do not feel is strictly
necessary. It would be possible to greatly simplify implementation if
Differential Encoding and the Reference Set we dropped from the
mechanism altogether at the cost of only a handful of additional bytes
per serialized header block.

2. I'd be *MUCH* happier if Eviction in the Header Table did not cause
renumbering of the existing items and if there was a fixed range of
index positions. Roberto has argued that doing so gives much worse
compression overall when dealing with lots of smaller valued headers
but my testing against the current corpus of test headers has not
demonstrated any significant problems. I will be drafting up a
modified bohe proposal that describes what I'd like to see in detail.

3. Going with the fixed range of index positions would allow us to do
away with the distinction between Literal with Incremental and Literal
with Substitution indexing. Everything would essentially be Literal
with Incremental until the fixed range is consumed, then the index
would simply rollover to reuse the existing index positions. Yes, I
get that the current scheme gives encoders more flexibility to develop
alternative algorithms for management the header table but, so far, I
do not agree that the flexibility is worth the additional complexity.

- James

---

From: James M Snell <[email-masked]>
Date: Mon, 8 Jul 2013 17:01:23 -0700

Another minor item as I've been going through the implementation:

4. Right now, the Header Compression scheme assumes two separate
pre-filled header tables... one for Request headers, the other for
response headers. The challenge with this is that it does not account
for the use of Request Headers within PUSH_PROMISE frames. This is
minor right now, but it means that PUSH_PROMISE frames will not have
optimum compression because the request headers will need to be added
as Literal representations with Indexing. It would be better if we
just had ONE prefilled table (it would make implementation generally
easier as well)

---

From: Amos Jeffries <[email-masked]>
Date: Tue, 09 Jul 2013 17:13:44 +1200

> just had ONE prefilled table (it would make implementation generally

+1.

Amos

---

From: Michael Sweet <[email-masked]>
Date: Tue, 09 Jul 2013 07:45:03 -0400

If you are suggesting that each endpoint should maintain a single encoding and a single decoding table per stream, I'm +1 on that.

Sent from my iPad

---

From: Mike Bishop <[email-masked]>
Date: Tue, 9 Jul 2013 13:38:51 +0000

No -- there's a single encoding and single decoding table *per connection* and this wouldn't change that.  Each table starts in an initial state with common values in each direction already in the table for convenient back-reference.

The problem with the initial state as it's currently defined is that it assumes clients only send request headers and servers only send response headers.  In fact, servers also send request headers (PUSH_PROMISE).

The suggestion is that both directions start with the same initial state.

-----Original Message-----
From: Michael Sweet [mailto:[email-masked]] 
Sent: Tuesday, July 9, 2013 4:45 AM
To: Amos Jeffries
Cc: [email-masked]
Subject: Re: Header Compression Implementation Feedback

Sent from my iPad

---

From: Michael Sweet <[email-masked]>
Date: Tue, 09 Jul 2013 10:28:10 -0400

Mike,

> The suggestion is that both directions start with the same initial state.

I'm ok with that part.

However, I think we need to make it clear in the HTTP/2.0 specification that (partial) HEADER frames cannot be interleaved from multiple streams, otherwise the state of the header table will be undefined.  For example, let's say a (multithreaded) client wants to GET /image1.jpg and /image2.png from a server over a single HTTP/2.0 connection using streams 1 and 2, respectively. And let's say that, because of cookies used by the web site, we can't fit all of the request headers into a single HEADER frame.  If the client doesn't serialize the two requests you could end up with:

    1:HEADER  (first request frame on stream 1)
    2:HEADER  (first request frame on stream 2)
    2:HEADER  (second request frame on stream 2)
    1:HEADER  (second request frame on stream 1)
    2:HEADER  (last request frame on stream 2)
    1:HEADER  (last request frame on stream 1)

Since each frame cannot be guaranteed to end at a header boundary, the server reading those HEADER frames has no way to reliably update its copy of the header table used for decoding.  So this means the client needs to serialize HEADER frames (and thus any requests it sends) at a cost of memory and some complexity - whether this cost is greater than per-stream header tables will likely depend on the situation.  It will also limit how quickly a client can issue requests, but that isn't necessarily a bad thing and in most cases the limiting factor is network bandwidth, not CPU...  Oh, and implementations will need to add protection against receiving interleaved HEADER frames from multiple streams...

Similarly, servers have to serialize their outgoing HEADER frames and do the same sort of error checking for incoming HEADER frames.

If instead we use a per-stream header table then we avoid this complexity but end up with less effective compression, particularly if clients and servers do not reuse streams for multiple requests.  But personally I think the savings in connection setup time and simultaneous streaming of multiple requests and responses makes this loss in compression acceptable.  It would also simplify the protocol and implementation.

>>> just had ONE prefilled table (it would make implementation generally 

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Mike Bishop <[email-masked]>
Date: Tue, 9 Jul 2013 15:00:39 +0000

No, you couldn't end up with that sequence as currently specced.  I agree, it would be an issue if the client did that, and you're right that there's no guarantee the individual HEADERS frame ends at a boundary -- but it's required to be the only frame type sent until a boundary is reached, and you are guaranteed to have reached a boundary at the end of the last HEADERS frame in the sequence.

>From http://tools.ietf.org/html/draft-ietf-httpbis-http2-04:
      A HEADERS frame without the END_HEADERS flag set MUST be followed
      by a HEADERS frame for the same stream.  A receiver MUST treat the
      receipt of any other type of frame or a frame on a different
      stream as a connection error (Section 5.4.1) of type
      PROTOCOL_ERROR.
...
   A compressed and encoded header block is transmitted in one or more
   HEADERS or PUSH_PROMISE frames.  If the number of octets in the block
   is greater than the space remaining in the frame, the block is
   divided into multiple fragments, which are then transmitted in
   multiple frames.

   Header blocks MUST be transmitted as a contiguous sequence of frames,
   with no interleaved frames of any other type, or from any other
   stream.  The last frame in a sequence of HEADERS frames MUST have the
   END_HEADERS flag set.  The last frame in a sequence of PUSH_PROMISE
   frames MUST have the END_PUSH_PROMISE flag set.
...
   An HTTP request or response each consist of:

   o  one contiguous sequence of HEADERS frames;

   o  zero or more DATA frames; and

   o  optionally, a contiguous sequence of HEADERS frames

   The last frame in the sequence bears an END_STREAM flag.

   Other frames, including HEADERS, MAY be interspersed with these
   frames, but those frames do not carry HTTP semantics.

   Trailing header fields are carried in a header block that also
   terminates the stream.  That is, a sequence of HEADERS frames that
   carries an END_STREAM flag on the last frame.  Header blocks after
   the first that do not terminate the stream are not part of an HTTP
   request or response.

-----Original Message-----
From: Michael Sweet [mailto:[email-masked]] 
Sent: Tuesday, July 9, 2013 7:28 AM
To: Mike Bishop
Cc: Amos Jeffries; [email-masked]
Subject: Re: Header Compression Implementation Feedback

Mike,

I'm ok with that part.

>>> response headers. The challenge with this is that it does not 
>>> account for the use of Request Headers within PUSH_PROMISE frames. 
>>> This is minor right now, but it means that PUSH_PROMISE frames will 
>>> not have optimum compression because the request headers will need 
>>> to be added as Literal representations with Indexing. It would be 
>>> better if we just had ONE prefilled table (it would make 
>>> implementation generally easier as well)
>> 
>> +1.
>> 
>> Amos
>> 
> 
> 
> 
>

---

From: Martin Thomson <[email-masked]>
Date: Tue, 9 Jul 2013 08:17:36 -0700

On 9 July 2013 07:28, Michael Sweet <[email-masked]> wrote:
> If instead we use a per-stream header table then we avoid this complexity but end up with less effective compression, particularly if clients and servers do not reuse streams for multiple requests.

Perhaps there is a misapprehension about how this works.  The draft
says: "An HTTP request/response exchange fully consumes a single
stream."

That means that:
 1. You only get one set of headers on every stream in each direction,
with the exception of push promises, of which there can be any number
on the same stream as a response.
 2. As a result, unless you have lots of push promises, per-stream
header compression will net almost zero compression gain.

---

From: Michael Sweet <[email-masked]>
Date: Tue, 09 Jul 2013 11:44:58 -0400

Mike,

> From http://tools.ietf.org/html/draft-ietf-httpbis-http2-04:

Ah, I had been deep in section 6 and hadn't remembered the text earlier in section 4; perhaps it would be appropriate to include a back reference to section 4.3 in sections 6.2 and 6.6 as a reminder about the contiguous HEADER/PUSH_PROMISE frame requirements?

Also, if an implementation gets a bad HEADER/PUSH_PROMISE frame, would that fall under Connection Error Handling (5.4.1) or Stream Error Handling (5.4.2)?  If this is a connection error (which given that header tables are per-connection, I think it should be) then I think we need an error for headers - HEADER_ERROR (10) and PUSH_PROMISE_ERROR (11)?

That still leaves us with the added complexity/overhead of serializing headers, but I'll hold off on further comments until I have a more complete implementation to test with.

Thanks!

---

From: James M Snell <[email-masked]>
Date: Tue, 9 Jul 2013 08:50:19 -0700

> header compression will net almost zero compression gain.

Well, header compression is at the framing layer, which could have any
number of HEADERS frames and PUSH_PROMISE frames sent, but the point
stands... per-stream header tables would be a very bad idea... (in my
opinion it's bad enough that we need to have one for each direction).

---

From: Michael Sweet <[email-masked]>
Date: Tue, 09 Jul 2013 11:50:24 -0400

Martin,

> header compression will net almost zero compression gain.

Perhaps my confusion comes from the beginning of section 6.2:

6.2. HEADERS

   The HEADERS frame (type=0x1) carries name-value pairs.  The HEADERS
   is used to open a stream (Section 5.1).  Any number of HEADERS frames
   can be sent on an existing stream at any time.

I was definitely under the impression that you could do multiple (sequential) requests over a single stream, with the END_STREAM flag signaling the close of the stream.

---

From: Michael Sweet <[email-masked]>
Date: Tue, 09 Jul 2013 11:51:34 -0400

Never mind, re-reading the latest draft I see the back reference and error handling are fully specified now...