Subject: Header Compression - streaming proposal

From: Gábor Molnár <[email-masked]>
Date: Fri, 05 Jul 2013 04:42:44 +0200

This a proposal for a seemingly minor change, that could make it possible
to implement
a streaming encoder/decoder for the compression spec, and make the decoding
process
simpler. It would also eliminate certain corner cases, like the shadowing
problem.

There's a lot of talk recently on enforcing the memory usage limits of the
compression
spec. There's one component however, that we don't take into account when
computing
the memory usage of compression implementations: it's the Working Set. The
problem
is that it can grow without bounds, since as far as I know, HTTP does not
impose limits
on the size of the header set. I tried to come up with a decoder
implementation
architecture for the compression spec that would not have to store the
whole set in the
memory.

Such a decoder would instead stream the output of the decoding process,
header by
header. This seems to be a legitimate approach, since most of the
memory-conscious
parsers I know are implemented as streaming parsers (streaming json, xml,
http, ... parsers). Gzip, the base of the previously used header
compression mechanism
is a streaming compressor/decompressor as well, of course.

It turns out that it is not possible to implement the current spec as a
streaming parser.
The only reason is this: *if an entry gets inserted into the working set,
it is not guaranteed
that it will remain there until the end of the decompression process, since
it could be
deleted any time*. Because of this, it is not possible to emit any headers
until the end
of the process.

I propose a simple change, that could, however, guarantee this: *in header
blocks, Indexed
Representations should come first*. This would guarantee that after the
Indexed
Representations are over, there will be no deletion from the Working Set.
This is the only
thing that would have to be changed. Existing decoding process can be
applied as if nothing
would change.

But it is now possible to implement a streaming, and - as a side effect -
much simpler
decoder like this:

0. There's only one component: the Header Table. An entry in the Header
Table is a
    name-value pair with an index (just like before), and a 'reference'
flag that is not set by
    default.
1. First phase of decoding: dealing with indexed representations. Indexed
representations
    simply flip the 'reference' flag on the entry they reference.
2. Second phase of decoding: before starting the processing of literal
representations, emit
    every name-value pair that is flagged in the Header Table.
3. Third phase of decoding: for every literal representations:
  1. emit the name-value pair
  2. insert it in the table if needed (incremental or substitution indexing
with table size
      enforcement)
4. When a new header block arrives, jump to 1.

It is maybe not obvious at first, but this process is equivalent the the
current decoding process,
if indexed representations come first. Please point out corner cases if you
find any.

I think that the 'Indexed Representations come first' pattern is something
that comes naturally
when implementing an encoder. Even examples in the spec can remain
unchanged, since they
follow this pattern already.

Regards,
  Gábor

---

From: Gábor Molnár <[email-masked]>
Date: Fri, 05 Jul 2013 10:51:32 +0200

An important detail was left out:
  3.3. step: if the entry was inserted, set the reference flag to true on
it.

2013/7/5 Gábor Molnár <[email-masked]>

> a streaming encoder/decoder for the compression spec, and make the
> decoding process
> that it will remain there until the end of the decompression process,
> since it could be
> deleted any time*. Because of this, it is not possible to emit any
> headers until the end
> of the process.
>
> I propose a simple change, that could, however, guarantee this: *in
> header blocks, Indexed
>   2. insert it in the table if needed (incremental or substitution
> indexing with table size
>       enforcement)
> if indexed representations come first. Please point out corner cases if
> you find any.
>

---

From: Martin Thomson <[email-masked]>
Date: Fri, 5 Jul 2013 10:38:47 -0700

In terms of simplicity, doing toggles first, then literals (w/ or w/o
changes to the table), makes a lot of sense to me.

That shifts some complexity to the encoder.  An encoder will have to
run two passes over its headers.

It also makes routing decisions a little harder for intermediation,
since routing information (usually :path, but the other :-headers need
to be checked too) are no longer at the head of the line if we assume
that :path changes request-by-request.

I'm just pointing out the trade-off.  Those costs do seem manageable.

On 5 July 2013 01:51, Gábor Molnár <[email-masked]> wrote:
>> The only reason is this: if an entry gets inserted into the working set,
>> it is not guaranteed
>> deleted any time. Because of this, it is not possible to emit any headers
>> until the end
>> of the process.
>>
>> I propose a simple change, that could, however, guarantee this: in header
>> blocks, Indexed
>> Representations should come first. This would guarantee that after the
>> Indexed

---

From: Gábor Molnár <[email-masked]>
Date: Mon, 08 Jul 2013 10:54:41 +0200

2013/7/5 Martin Thomson <[email-masked]>

> run two passes over its headers.

I've been thinking about this for a while: is it worth moving complexity
from
the decoder to the encoder, when a resource constrained client have to
implement both (for request/response)? I think the answer is yes, because
 1. it *remains possible* to implement encoding with minimal resource
     usage: just use literal representations without indexing for all
headers.
 2. it *becomes possible* to implement decoding with minimal resource
     usage (streaming decoder).

> that :path changes request-by-request.

I don't think it becomes harder. If an output buffer is used, and at the end
the headers are reordered, then we get back to the situation we have now.
When implementing a routing logic that can handle streaming, then the
routing
decision can be made somewhat sooner than the end of the decompressing
process. I agree that implementing such a streaming capable routing logic
might be more difficult and might not be worth it (especially given that
proxies are usually not memory-constrained).

> I'm just pointing out the trade-off.  Those costs do seem manageable.

Thanks for the feedback!

---

From: Gábor Molnár <[email-masked]>
Date: Wed, 10 Jul 2013 09:53:32 +0200

I opened an issue on GitHub for this proposal with minor modification
to the original text:
https://github.com/http2/compression-spec/issues/11

If I get more feedback, I will be happy to draft a PR as well.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 10 Jul 2013 09:47:41 -0700

> If I get more feedback, I will be happy to draft a PR as well.

The only feedback I have is that you could reclaim a bit from each of
the existing opcodes by doing this, which could produce a pretty big
increase in performance.

Starting the header block with a count (the number of index entries,
prefix size 0), could make this quite efficient.

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 11 Jul 2013 16:26:09 +0000

I've been pondering on this proposal for some time.

I think it has several impact on the header compression mechanism.

1. The decoder can be much simpler. In particular, it can help avoiding nasty bugs due to the working set shadowing the index table.

2. It makes the encoder more complex. It think that the current spec allows for an encoder doing only one pass on the headers to encode, with the removed headers encoded at the end.
This new proposal enforce doing at least two pass on the headers to encode.

3. For performances, I will believe only when I see some numbers ;-).
The count of indexed entries will usually cost 8 bits. But 1 bit will be reclaimed on each entry, allowing to encoding larger index values on the first byte of each entry. I'm inclined to think this will result in a net gain, but I don't know how much.
However, if we decide to include typed codec, the reclaimed bit could be used as part of the signaling of which codec was used, and could decrease the cost of this inclusion.

Hervé.

> -----Original Message-----
> From: Martin Thomson [mailto:[email-masked]]
> Sent: mercredi 10 juillet 2013 18:48
> To: Gábor Molnár
> Cc: HTTP Working Group
> Subject: Re: Header Compression - streaming proposal
> 
> The only feedback I have is that you could reclaim a bit from each of the
> existing opcodes by doing this, which could produce a pretty big increase in
> performance.
> 
> Starting the header block with a count (the number of index entries, prefix
> size 0), could make this quite efficient.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 11 Jul 2013 12:40:08 -0700

The delta2 codec did have a requirement on doing toggles first.
It also had a mode which used 8-bit index sizes.

Both/all of these things have been played with already, and have had both
drafts and implementations, and one can feel free to look at both :)
-=R

On Thu, Jul 11, 2013 at 9:26 AM, RUELLAN Herve
<[email-masked]>wrote:

> 1. The decoder can be much simpler. In particular, it can help avoiding
> nasty bugs due to the working set shadowing the index table.
>
> 2. It makes the encoder more complex. It think that the current spec
> allows for an encoder doing only one pass on the headers to encode, with
> the removed headers encoded at the end.
> The count of indexed entries will usually cost 8 bits. But 1 bit will be
> reclaimed on each entry, allowing to encoding larger index values on the
> first byte of each entry. I'm inclined to think this will result in a net
> gain, but I don't know how much.
> However, if we decide to include typed codec, the reclaimed bit could be
> used as part of the signaling of which codec was used, and could decrease
> the cost of this inclusion.
>
> Hervé.
>
> prefix