Subject: CONTINUATION proposal w/ minimum change

From: <[email-masked]>
Date: Mon, 30 Jun 2014 18:00:16 +0000

On Friday,27 June 2014 09:36, [email-masked]<mailto:[email-masked]> wrote:
> Can someone please provide a proposal?

I've incorporated many of the ideas mentioned on the list and in the NYC minutes to create a proposal that (I believe) accomplishes the goals with a minimum amount of change.

Changes:

+ Only the HEADERS and PUSH_PROMISE frames can alter the compression context.

+ CONTINUATION frames can only use hpack literals (optionally Huffman encoded) that don't alter the table.

  - CONTINUATION is flow controlled

  - CONTINUATION has an END_STREAM flag

Benefits:

+ Simplifies CONTINUATION implementation

  - i.e. fixes the nonsensical END_STREAM that doesn't actually end the stream

+ Flow control of CONTINUATION:

  - removes the incentive for implementations to cheat and send large amounts of data in the HEADERS+CONTINUATION jumbo frames

  - may help with certain HOL blocking situations (e.g. connection coalescing)

See pull request here: https://github.com/shearl/http2-spec/commit/5a548553334e35cbba5946d238e9a14c6ba03f7e

This email message is intended only for the use of the named recipient. Information contained in this email message and its attachments may be privileged, confidential and protected from disclosure. If you are not the intended recipient, please do not read, copy, use or disclose this communication to others. Also please notify the sender by replying to this message and then delete it from your system.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Jun 2014 11:11:35 -0700

On 30 June 2014 11:00,  <[email-masked]> wrote:
> I've incorporated many of the ideas mentioned on the list and in the NYC
> minutes to create a proposal that (I believe) accomplishes the goals with a
> minimum amount of change.

I think that there is a little more work to be done to clean up the
proposal.  See my comments on the pull request (they are all
editorial).

---

From: Mike Bishop <[email-masked]>
Date: Mon, 30 Jun 2014 18:53:28 +0000

It feels very awkward to make the compressor aware of framing.  Previously, we had said that you take your header set, run it through HPACK, then frame up and send the output using HEADERS/PUSH_PROMISE and CONTINUATION.  Now, the HPACK compressor has to know where the boundary is and change its behavior when it passes that boundary.  I assume that means on the decompression side that the reference set is emitted when the frame boundary is hit, which means the decompressor also needs to be aware of framing.

It gets worse, because a given instruction could cross the boundary.  Whether a header can be indexed or not would depend on whether the header name is already in the table, because the compressor needs to check whether a given header will cause it to cross the boundary.  There's new HPACK text here that will be required, and not very pretty.

By the way, I thought the point of making CONTINUATION only carry literals was to break the requirement that a CONTINUATION MUST immediately follow the incomplete HEADERS/PUSH_PROMISE frame - but I don't see that your pull request does that.  You've brought in new ugliness without getting the return you're looking for.

(Having now read Martin's comments, there's a lot of overlap here.)

From: [email-masked] [mailto:[email-masked]]
Sent: Monday, June 30, 2014 11:00 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]
Subject: CONTINUATION proposal w/ minimum change

Changes:

Benefits:

---

From: Jason Greene <[email-masked]>
Date: Mon, 30 Jun 2014 14:44:33 -0500

On Jun 30, 2014, at 1:53 PM, Mike Bishop <[email-masked]> wrote:

> It gets worse, because a given instruction could cross the boundary.  Whether a header can be indexed or not would depend on whether the header name is already in the table, because the compressor needs to check whether a given header will cause it to cross the boundary.  There’s new HPACK text here that will be required, and not very pretty.

You could just have the hpack routines be reusable, and have the compressor accept an output length limit. Once the limit is hit, the compressor backs up and informs the caller where it left off. When an overflow occurs the caller then invokes the generic hpack routine again at a resume point using zero-compression settings (literals, restricted table size etc). For simplicity, I think its important to ensure that opcode splits are not allowed.

This of course could be much more intelligent. If we look at the primary use-case of a kerberos ticket, the ideal implementation would sort the gigantic headers into the second uncompressed call, likely resulting in no actual overflow on the first call.

You can look at decompression the same way. The generic hpack routine gets a HEADER frame, it completely decodes it, and emits a reference set because for all it knows, it’s done. Subsequent hpack decodes do not use compression state, so the reference set need not be touched. 

Alternatively you could opt for a less protocol efficient input limit check, and simply split when your input is > 16K, leaving your hpack routine largely unaltered.

>  
> By the way, I thought the point of making CONTINUATION only carry literals was to break the requirement that a CONTINUATION MUST immediately follow the incomplete HEADERS/PUSH_PROMISE frame – but I don’t see that your pull request does that.  You’ve brought in new ugliness without getting the return you’re looking for.
>  
> (Having now read Martin’s comments, there’s a lot of overlap here.)
>  
> On Friday,27 June 2014 09:36, [email-masked] wrote:

--
Jason T. Greene
WildFly Lead / JBoss EAP Platform Architect
JBoss, a division of Red Hat

---

From: Mike Bishop <[email-masked]>
Date: Mon, 30 Jun 2014 21:49:49 +0000

Op-code splits are required -- if a single header can be up to 64KB, and the limit of a single frame is 16KB, then just to encode that header will cross several frames.  If you're simply saying that op-codes can't cross the *first* boundary, that may be possible, though it means that a very small HEADERS frame could still have a CONTINUATION.

At any rate, my biggest piece of feedback remains -- this isn't a minimal change.  It's going to require pretty substantial changes in HPACK and how it interfaces with the remainder of the protocol.

-----Original Message-----
From: Jason Greene [mailto:[email-masked]] 
Sent: Monday, June 30, 2014 12:45 PM
To: Mike Bishop
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: CONTINUATION proposal w/ minimum change

You can look at decompression the same way. The generic hpack routine gets a HEADER frame, it completely decodes it, and emits a reference set because for all it knows, it's done. Subsequent hpack decodes do not use compression state, so the reference set need not be touched. 

> See pull request here: 
> https://github.com/shearl/http2-spec/commit/5a548553334e35cbba5946d238
> e9a14c6ba03f7e
>  
>  

--
Jason T. Greene
WildFly Lead / JBoss EAP Platform Architect JBoss, a division of Red Hat

---

From: Jason Greene <[email-masked]>
Date: Mon, 30 Jun 2014 17:15:23 -0500

On Jun 30, 2014, at 4:49 PM, Mike Bishop <[email-masked]> wrote:

> Op-code splits are required -- if a single header can be up to 64KB, and the limit of a single frame is 16KB, then just to encode that header will cross several frames.  

Right, large headers would get kicked into another frame. Ideally you would do that before even encoding. As a mental model picture having two header sets. A smaller efficiently compressed set that fits in a frame and represents 99.9% of the internet, and the overflow set which contains the exceptional and legacy content which is split over N CONTINUATION frames.

> If you're simply saying that op-codes can't cross the *first* boundary, that may be possible,

Yes that’s exactly what I meant.

> though it means that a very small HEADERS frame could still have a CONTINUATION.

Sure, if you had say 4-5 common routing fields, and then a large kerberos ticket, that would be two frames with a small header. This would basically be the reverse of the current draft which would have a max HEADERS frame and a small CONTINUATIONS frame. IMO, this is actually beneficial because the state affecting frame will be faster to process than the non-state-affecting.

> At any rate, my biggest piece of feedback remains -- this isn't a minimal change.  It's going to require pretty substantial changes in HPACK and how it interfaces with the remainder of the protocol.

I don’t see how the HPACK spec needs to be touched, but maybe I am missing something?

---

From: Mike Bishop <[email-masked]>
Date: Mon, 30 Jun 2014 23:47:44 +0000

You're currently putting the language into the HTTP/2 spec, which otherwise knows nothing about the operation of HPACK.  HPACK would need to have a concept of a non-state-modifying frame, plus the concept of emitting the reference set at the end of the HEADERS/PUSH_PROMISE frame rather than at the end of the entire headers block.  But I'm more thinking about changes in HPACK *implementations* which are currently libraries that operate completely independently of the framing.  This would require what is effectively framing information to be passed in/out of those libraries.

Also, the fact that CONTINUATION is flow-controlled has ramifications for both sides.  For the encode, your text says that CONTINUATION can't *change* state, but if there are multiple CONTINUATIONs, they can't *use* state either.  If I have a huge header to send, and the window doesn't permit me to send the whole thing, then I can't reference the static table at all without blocking all header compression on the flow control window for that stream.  That's not too bad, since saving the size of the header name on a >16KB header is relatively small overhead.

But on the receiver side, the implication is worse.  DATA frames have the nice property of being divisible -- if you don't have enough window to send the whole thing, you can segment the DATA frame and send as much as your window allows.  On the remote peer, that gets passed to the app, and as the app reads and frees up memory, WINDOW_UPDATES can be sent to receive the rest.  CONTINUATION frames have the same property of being divisible, but not the same property of being streamable without major API changes.

With this proposal, I can use flow control to control how much header data I receive at once, but I can't drain that filled space by sending it to the app, because I'm still waiting for the rest of the header.  That means a server can't use "application read" as the trigger to send a WINDOW_UPDATE, because it's not passing anything to the app, just realizing that there's more to read in before it can, and RTTs are burning while that happens.  With a POST, that's acceptable, because the (non-flow-controlled) headers might have told the server what size body to expect, plus the body can be streamed to the app as it arrives.  I suspect no server API streams incomplete header sets, and especially not incomplete individual headers to the application layer above it.

We're trying not to make invasive changes at this point, and this feels a bit large.  I'm much more sympathetic to Willy's proposal, which doesn't change the wire format but helps discourage CONTINUATION abuse by only allowing them when the preceding frame was the max-size.  That permits them in the real use-case, but lets someone identify a peer that's being overly silly.

-----Original Message-----
From: Jason Greene [mailto:[email-masked]] 
Sent: Monday, June 30, 2014 3:15 PM
To: Mike Bishop
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: CONTINUATION proposal w/ minimum change

> boundary, that may be possible,

Yes that's exactly what I meant.

> At any rate, my biggest piece of feedback remains -- this isn't a minimal change.  It's going to require pretty substantial changes in HPACK and how it interfaces with the remainder of the protocol.

I don't see how the HPACK spec needs to be touched, but maybe I am missing something?

>>  - removes the incentive for implementations to cheat and send large 
>> amounts of data in the HEADERS+CONTINUATION jumbo frames

---

From: Jason Greene <[email-masked]>
Date: Mon, 30 Jun 2014 23:14:14 -0500

> You're currently putting the language into the HTTP/2 spec, which otherwise knows nothing about the operation of HPACK.  HPACK would need to have a concept of a non-state-modifying frame, plus the…

Sure there is definitely non-trivial implementation changes required.

> Also, the fact that CONTINUATION is flow-controlled has ramifications for both sides.  For the encode, your text says that CONTINUATION can't *change* state, but if there are multiple CONTINUATIONs…

Keith’s proposal limits everything to literals. I’m not sure if he meant to exclude static table entries with a size 0 table or not (I added a comment to this effect). In both cases, the header table is always empty. In the latter you can still reference static entries but you get no differential encoding. So there is nothing to block on. I do think it was unintentional that the wording in Keith’s proposal allows muxing on the same stream. I don’t think that makes a lot of sense to do. 

Mathew had mention an option in a past email that involved a stream local hpack state that would create something to potentially block on, but if you establish that CONTINUATIONS don’t mux on the same stream, then even that option wouldn’t cause a problem.

> With this proposal, I can use flow control to control how much header data I receive at once, but I can't drain that filled space by sending it to the app, because I'm still waiting for the rest of…

It’s true that flow controlled headers force a server to potentially buffer multiple streams. Although, the same thing can happen with multiple connections in the current draft, and since it also introduces HOL blocking, multiple connections will be the workaround.

I see a lot of things a server can do before receiving a full header set. To ensure expedient processing, senders have an incentive to stick the important routing based headers in the HEADERS frame, which has a lot of space. So even before they have buffered everything they can actually reject a request right away based on that information, and even the stream can be preserved. In the existing draft, the server is forced to either continually decode or blow-up the whole connection.

I take it your point about incomplete individual headers to the application layer above it refers to the 64KB kerbose case? I would imagine that in that case the server could just process it as soon as it gets it. Of course there is existing APIs and existing code that has to work with http/2 and that code won’t be as efficient. However, thats the case no matter what the transport does with gigantic headers.
> 
> We're trying not to make invasive changes at this point, and this feels a bit large.  I'm much more sympathetic to Willy's proposal,

Sure it’s unfortunate that this is late, but cementing the existing CONTINUATION design that “nobody likes”, and will even go unimplemented by several products, into the most widely used internet specification seems far, far worse. 

Is anyone even remotely confident that CONTINUATION, as it is currently described,  will survive h3, let alone wide deployment in h2?

>  which doesn't change the wire format but helps discourage CONTINUATION abuse by only allowing them when the preceding frame was the max-size.  That permits them in the real use-case, but lets someone identify a peer that's being overly silly.

I agree its certainly better.

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 1 Jul 2014 14:16:03 +1000

Hi Jason,

> Is anyone even remotely confident that CONTINUATION, as it is currently described,  will survive h3, let alone wide deployment in h2?

Let's keep discussions focused on H2 for now; speculating on what will be in H3 is just that - speculation.

Cheers,

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

---

From: Matthew Kerwin <[email-masked]>
Date: Tue, 1 Jul 2014 15:49:48 +1000

On 1 July 2014 14:14, Jason Greene <[email-masked]> wrote:

> > You're currently putting the language into the HTTP/2 spec, which
> otherwise knows nothing about the operation of HPACK.  HPACK would need to
> have a concept of a non-state-modifying frame, plus the concept of emitting
> the reference set at the end of the HEADERS/PUSH_PROMISE frame rather than
> at the end of the entire headers block.  But I'm more thinking about
> changes in HPACK *implementations* which are currently libraries that
> operate completely independently of the framing.  This would require what
> is effectively framing information to be passed in/out of those libraries.
>
> > Also, the fact that CONTINUATION is flow-controlled has ramifications
> for both sides.  For the encode, your text says that CONTINUATION can't
> *change* state, but if there are multiple CONTINUATIONs, they can't *use*
> state either.  If I have a huge header to send, and the window doesn't
> permit me to send the whole thing, then I can't reference the static table
> at all without blocking all header compression on the flow control window
> for that stream.  That's not too bad, since saving the size of the header
> name on a >16KB header is relatively small overhead.
>
> Keith’s proposal limits everything to literals. I’m not sure if he meant
> to exclude static table entries with a size 0 table or not (I added a
> comment to this effect). In both cases, the header table is always empty.
> In the latter you can still reference static entries but you get no
> differential encoding. So there is nothing to block on. I do think it was
> unintentional that the wording in Keith’s proposal allows muxing on the
> same stream. I don’t think that makes a lot of sense to do.
>
> Mathew had mention an option in a past email that involved a stream local
> hpack state that would create something to potentially block on, but if you
> establish that CONTINUATIONS don’t mux on the same stream, then even that
> option wouldn’t cause a problem.
>
>
I think I said "state", not "hpack state."​ I meant buffering any partial
headers that carry over from CONTINUATION to CONTINUATION. Sorry if that
wasn't clear. (The end result is similar, though.)

​While this proposal aims to be uninvasive, it's effectively introducing
the concept of two HPACK profiles, which may or may not be a big​ deal
code-wise, but is a big conceptual change.

I suspect it would be less disruptive to completely replace CONTINUATIONS
with a whole new ​frame with its own stand-alone internal encoding. Hell,
if the concatenated payloads of the CONTINUATION frames was just a
traditional "h1: v1\r\nh2: v2\r\n\r\n" string, that'd get the data out
there at least. It does mean either sitting on the header block from HPACK
and then adding the continuated headers, or forcing the application to
accept partial/streamed headers.

Mike:

> >
> > But on the receiver side, the implication is worse.  DATA frames have
> the nice property of being divisible -- if you don't have enough window to
> send the whole thing, you can segment the DATA frame and send as much as
> your window allows.  On the remote peer, that gets passed to the app, and
> as the app reads and frees up memory, WINDOW_UPDATES can be sent to receive
> the rest.  CONTINUATION frames have the same property of being divisible,
> but not the same property of being streamable without major API changes.
>

That's true if you're communicating with someone that doesn't support
header streaming (i.e. anything designed to work with HTTP/1.1, be it a
network component or an application or whatever); but if you're talking
HTTP/2 out both ends (e.g. as a proxy, or part of a new from-the-ground-up
application stack) there's no such restriction.

Theoretically, if the data window and the headers window were controlled
separately (and you could set the headers window size to "infinite") would
that make the idea of flow-controlled headers more acceptable? I say
theoretically because I realise that's even *more* change.

​For the record, I don't necessarily care about header flow control, but I
like being able to progress other information on a connection even while
large/slow headers are oozing their way down one stream's tubes.

> >
> > We're trying not to make invasive changes at this point, and this feels
> a bit large.  I'm much more sympathetic to Willy's proposal,
>
> Sure it’s unfortunate that this is late, but cementing the existing
> CONTINUATION design that “nobody likes”, and will even go unimplemented by
> several products, into the most widely used internet specification seems
> far, far worse.
>
> Is anyone even remotely confident that CONTINUATION, as it is currently
> described,  will survive h3, let alone wide deployment in h2?
>
> >  which doesn't change the wire format but helps discourage CONTINUATION
> abuse by only allowing them when the preceding frame was the max-size.
>  That permits them in the real use-case, but lets someone identify a peer
> that's being overly silly.
>
Assuming you're continuating because the metadata is big, that's fair
enough and I agree; but if there's a header that takes a long time to
generate (say you have a religious preference for content-length over
T-E:chunked, or something), it might be nice to send what headers you
already have, then sleep the current stream while the rest of the headers
are generated. The other way to do that is to force the sender to buffer
the outgoing headers, which is no better than forcing the receiver to do
the buffering. Just a theoretical there, BTW; I got over chunking years ago.

-- 
  Matthew Kerwin
  http://matthew.kerwin.net.au/