Re: Header Compression - streaming proposal

[Gábor Molnár <[e-mail]>]

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.

2013/7/8 Gábor Molnár <[e-mail]>:
> 2013/7/5 Martin Thomson <[e-mail]>
>>
>> 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.
>
>
> 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).
>
>>
>> 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 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!
>
>>
>> On 5 July 2013 01:51, Gábor Molnár <[e-mail]> wrote:
>> > 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 <[e-mail]>
>> >>
>> >> 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
>> >
>> >
>
>