Subject: Re: h2 priority

From: Chad Austin <[email-masked]>
Date: Wed, 22 Oct 2014 11:09:04 -0700

On Thu, 4 Sep 2014 12:57:41 -0400, Patrick McManus wrote:

Hi Roy,

So the priority dependencies is really a feature googlers championed, I'm
surprised that we haven't seen anyone from that team contributing to this.
I do, however, support it so I'll carry on the discussion.

The most important bit of consensus was that experience has shown us the
few bits of spdy priority can't be aggregated well. The easiest
illustration is a proxy...

if 2 inbound sessions have 3 streams each of priorities {0,1,2} and {5, 6,
7} all headed to the same origin what is a reasonable implementation for
the priorities on the 1 outbound session? The incoming priorities only have
meaning wrt other streams in the same session, they have no global meaning.
Each client is incented to pick priorities at the most important end of the
spectrum - indeed perhaps to only use the highest priority which is back to
having no priority at all.

PREAMBLE

Sometimes people argue that priorities are advisory and thus don’t deserve all that much consideration.  However, as Patrick McManus and Will Chan have said, muxing connections without prioritization is actually slower than HTTP 1 [because browsers already prioritize HTTP 1, just inefficiently across N TCP connections].  Given that a primary goal of HTTP 2 is performance, getting prioritization correct is important to its success.

ON THE PROXY USE CASE
I understand the motivation behind the dependencies-and-weights model, but I question whether it actually solves the proxy / outbound connection muxing use case.  If your goal is fairness when muxing connections, I am not sure streams-and-dependencies is all that natural or practical.

To implement fair muxing on top of HTTP 2’s dependency tree:

Each input stream ID is mapped to a corresponding output stream ID.

Assume we want to fairly mux two input connections (A and B) against one output connection.  That is, at any moment, for output stream 0 (the implied root), the sum of weights of A’s root streams equals the sum of weights of B’s root streams.

That is, if input connection A has streams {A0, A1, A2} -> 0 and input connection B has stream B0 -> 0, then the output tree would map to:

Strategy #1

{A0, A1, A2, B0} -> 0

where: weight(A0) + weight(A1) + weight(A2) = weight(B0)

OR

Strategy #2

{A0, A1, A2} -> Adummy

{B0} -> Bdummy

{Adummy, Bdummy} -> 0

where Adummy and Bdummy are “dummy streams” created purely for prioritization.  (Is this even possible in HTTP/2?)

Let us consider the possible arrival of a [PRIORITY stream=A1, exclusive=true, parent=0] frame on connection A.  The proxy’s action depends on whether strategy #1 or #2 is undertaken.

In strategy #1, the input PRIORITY frame would be translated into 2 output PRIORITY frames:

[PRIORITY stream=A0, exclusive=false, parent=A1]

[PRIORITY stream=A2, exclusive=false, parent=A1]

OR:

[PRIORITY stream=A1, exclusive=true, parent=0]

[PRIORITY stream=B0, exclusive=false, parent=0]

Either results in the following output tree:

{A1, B0} -> 0

{A0, A2} -> A1

In general, it’s possible for each input PRIORITY frame to become N output PRIORITY frames.

Strategy #2 is simpler: any mention of stream “0” on an input connection is mapped to the appropriate dummy stream on the output.  So if connection A has [PRIORITY stream=A1, exclusive=true, parent=0], the PRIORITY frame to the backend becomes [PRIORITY stream=A1, exclusive=true, parent=Adummy].  This strategy depends on being able to allocate dummy streams purely for prioritization.

Thus, it’s certainly possible to fairly allocate resources by multiplexing resources onto an output stream.  Is it particularly natural?  I’d argue no.

In addition, there’s the question of maximum stream concurrency.  If input connections A and B have 100 streams, and output connection B has a concurrency limit of 100, then the proxy must prioritize manually anyway.

Finally, what if the backend will only actually process, say, 8 streams at a time?  If input connection A’s streams were sent to the backend before B’s streams (assuming equal priority), it’s possible the backend will starve B in lieu of A.

How realistic is the proxy mux use case?  Does anybody implement it today?  If so, how?

I would also love to hear from the people who championed dependencies-and-weights.  I am finding it quite challenging to solve our use case with it. [1] [2]

After that you get into more speculative use cases for sure. I've got one
whiteboarded regarding dependencies for images based on what the layout
engine says might be visible at any moment in time, but its stalled mostly
on non-network internal browser stuff of figuring out what might be visible
at any moment in time :) For the most part I agree we are basically
speculating on what might work in that space right now, but the previously
mentioned aggregation bits were a known problem that the text sought to
address.
I’d love to see a document containing a list of use cases for HTTP 2 priority.  I am happy to start one if desired.

In particular, dependencies-and-weights, as written, does not solve for “all As are more important than all Bs, which are more important than all Cs” without having a linked list of dependencies.  A linked list is fine for some uses cases (mine linked below, for example), but interleaving responses is preferable in other cases. [3]

I have not worked out the details, but perhaps there are small changes to HTTP 2’s priority model that would solve for current gaps.

[1] http://lists.w3.org/Archives/Public/public-whatwg-archive/2014Oct/0027.html

[2] http://lists.w3.org/Archives/Public/ietf-http-wg/2014OctDec/0016.html

[3] https://insouciant.org/tech/spdy-prioritization-case-study-gmail/

Thanks,
Chad