Re: [whatwg] Expose XMLHttpRequest [Fetch?] priority

I replied on Friday night, but exceeded the 40 KB mailing list limit, and
it has not been moderated through yet.  So, replying again:

On Tue, Oct 14, 2014 at 10:02 AM, Ilya Grigorik <igrigorik@gmail.com> wrote:

>
> On Thu, Oct 9, 2014 at 12:12 PM, Chad Austin <caustin@gmail.com> wrote:
>
>>
>> This thread has been a bit confusing, partially because I did not have a
>> deep understanding of HTTP 2's priority semantics and partially because I
>> feel your responses have been too short and vague to truly answer the use
>> case described at the top of the thread.  For example, you said "0-7
>> priority is not sufficient.  Please see the previous proposal.", yet I
>> don't see any discussion in the previous proposal about why 0-7 is not
>> sufficient.
>>
>> In addition, because I'm not sure it's clear, priorities and weights are *different
>> concepts*.  Weights are used to allocate resources between streams of
>> identical priority.  Priorities are used to specify that one request should
>> be completed before another if possible.
>>
>
> That was never the case in SPDY. In v1-v3.1 priority never guaranteed
> strict delivery. Priorities were always advisory for the server, and in v4
> draft we changed that to the tree model that is in HTTP/2.
>
> Also, note that this behavior is *intentional*. When using transport
> priorities, you're effectively telling the server:
> - I need all of these requests, please mux all the frames such that I
> receive all of the data as quickly as possible
> - Also, if possible, please allocate the pipe based on specified
> weights/dependencies/etc
>
> The above does not guarantee any order. Take an extreme example: B depends
> on A; A is taking 3 seconds to generate on the backend, while B is ready to
> ship. The server should not starve the connection while its waiting on A,
> and it should pump bytes for B until its ready to return bytes for A.
>
> If you need *strict* response ordering, then you have to choices:
> - Dispatch requests from the client based on completion of previous
> request, instead of firing them off simultaneously
> - Change your server to enforce your own arbitrary semantics (general
> purpose servers won't do this)
>

Of course priorities are advisory.  :)  I don't need strict response
ordering.  I simply want to simultaneously maximize bandwidth utilization
but also, when possible, have the server transmit bytes in the desired
order.

This is not an unreasonable request either: nginx backed by Varnish,
assuming Varnish cache hits (~1ms latency), and assuming the connection is
bandwidth-constrained, will send stream frames in approximately priority
order.  nginx's SPDY implementation is five small C files, and it
prioritizes streams and frames with a very simple priority queue
implementation.

So while priority is advisory, it's also very important for achieving good
performance, and it will also be effective in practice.  If HTTP 2 servers
don't prioritize, they run the risk of regressing performance relative to
HTTP.  This is because browsers currently prioritize HTTP behind the scenes
with a priority queue.

*The Use Case*
>>
>> Our application issues thousands (sometimes tens of thousands) of XHR
>> HTTP requests to populate a WebGL-rendered 3D scene.
>>
>> Many of those requests are higher *priority* than others, in that, if
>> possible, they should be completed *before* expending bandwidth on
>> lower-priority resources.  Moreover, there is no benefit to having multiple
>> responses downloading simultaneously: assuming saturated bandwidth, it is
>> always better here to complete one response before moving to the next.
>> (Having two half-downloaded textures or meshes is not useful.  Having one
>> fully-downloaded texture or mesh and one not started yet is useful.)
>>
>
> Makes sense. To match this, create a tree that captures these relationship.
>

Except it would be a linked list instead of a tree.  Per Martin Thomson in
http://lists.w3.org/Archives/Public/ietf-http-wg/2014OctDec/0164.html, "We
can't express a dependency on multiple resources, except by creating a
linear chain: B2 -> B1 -> A2 -> A1 -> 0."

In the use case described, managing priorities numerically is much simpler.

If three resources A0, A1, A2 have priority 7, and resources B0, B1, and B2
have priority 6, and resource C has priority 5, then it's not a tree.  It's
a linked list:  C -> B2 -> B1 -> B0 -> A2 -> A1 -> A0 -> 0.  (C -> B0 -> B2
-> B1 -> A1 -> A2 -> A0 -> 0 would also be a fine ordering, as the
sequencing within each level does not matter.)

>From a software development point of view, the ideal JavaScript API would
>> allow issuing *all* requests simultaneously, indicating their relative
>> priority to the browser, and let the browser map the desired priority to
>> the underlying protocol stack.
>>
>
> Dependencies and weights. You're using priority values as crude levels to
> indicate "ordering". Instead, identify think of each "priority level" as a
> level in the deps tree, where each level can have multiple requests,
> resources for which can be further customized via weights.
>

Again, weights are not useful for prioritization.

You keep mentioning weights, so perhaps you have some example where it
would be relevant in the prioritization use case?  Ideally, in the WebGL
content load use case, I would always *complete* one resource before
starting the next.  Weights are for dividing available resources up among
streams of identical priority.

Sadly, priority values do not correspond to 'levels in the tree'.  The
reason is that HTTP 2 dependencies collapse upon stream completion.  Let's
take your proposal and apply it to the short example above.

A0, A1, A2 at priority 7
B0, B1, B2 at priority 6
C at priority 5

If that were a tree, it would look something like: {A0, A1, A2} -> 0.  {B0,
B1, B2} -> A0.  C -> B0.

As Martin described in the other thread, that's wrong if you want assurance
that A0, A1, and A2 are always higher priority than B0, B1, and B2.  And
B0, B1, and B2 are higher priority than C.  The reason is that dependencies
collapse upon stream close.  If A0 finished first, the tree would collapse
to:  {B0, B1, B2, A1, A2} -> 0.  C -> B0.

This places B0, B1, B2, A1, and A2 at equal priority!

You could say "Well, due to weight rebalancing, B0 has 1/3 of the weight of
A1, so it will use fewer bytes on the socket..." but that misses the
point.  The point is that, to optimally use the bandwidth, I don't want to
spend ANY bytes on B0, B1, or B2 until A0, A1, and A2 are all complete.

You could also say "Well, priorities are advisory, and the server may
implement whatever algorithm it wants."  That's true, but the HTTP 2 spec
is quite clear about how priority SHOULD work.  Quote:

Streams with the same parent SHOULD be allocated resources
proportionally based on their weight.  Thus, if stream B depends on
stream A with weight 4, and C depends on stream A with weight 12, and
if no progress can be made on A, stream B ideally receives one third
of the resources allocated to stream C.

Thus, a linked list is necessary to achieve prioritization semantics.

>
>> *Current Browser Behavior*
>> Browsers have widespread support for two protocols (HTTP and SPDY) and
>> are likely to support HTTP 2 very soon.
>>
>
> They will support HTTP/2, it's only a question of how soon. Latest FF and
> Chrome are already rolling out HTTP/2 support in stable channels, and the
> plan (for all browsers) is to actively deprecate SPDY.
>

Fair enough.  Let's assume supporting SPDY priority bits is a total nongoal
of this API then.

*So what interface should the browser expose?*
>>
>
>> Before designing a browser API, a few questions must be answered:
>>
>> 1) Should the priority API support legacy HTTP and SPDY?
>>
>
> - SPDY is going to be aggressively deprecated.
> - Legacy HTTP has a lot of potential gotchas, I'd flag this as at risk.
>

Can you enumerate those gotchas?  I would say we ought to at least attempt
to support legacy HTTP, because:

1) we can and it's not hard! :)
2) browsers already do it
3) since HTTP connections are probably slower, prioritization is especially
important
4) HTTP 2 will not be ubiquitous for at least five years, and it would be a
real shame if we built an API that left short term benefits on the table

2) Should the priority API support future protocols beyond HTTP 2?
>>
>
> - Yes, it shouldn't be tied directly to HTTP/2 semantics.
>
>
>> 3) How likely is it future protocols will support non-dependency-based
>> priority models.
>>
>
> - Note that you *can* implement whatever you want on the server. Client
> sends its preferences, you do what you want.
>
>
>> 3) How much work should be placed on application developers?  aka how
>> closely should the API fit the application domain?
>>
>
> - I'm not sure what "application domain" means, since that'll be different
> for every application. That said, yes, a sensible abstraction over the
> low-level plumbing is good.
>
>
>> IMO, the answers to the above questions are "yes", "yes", and "possible",
>> and "better for the API to fit the application domain than for the API to
>> reflect one possible underlying protocol so that a truer implementation in
>> non-HTTP-2 protocols is possible".
>>
>> In that light, I think your proposal [
>> http://lists.w3.org/Archives/Public/public-whatwg-archive/2014Aug/0081.html
>> ] is not satisfactory.  It requires application bookkeeping to map priority
>> values to the linked list of XHRs, which:
>>
>> * in the case of vanilla HTTP, the browser must convert the dependency
>> tree back to 32-bit integers.  (or reimplement the browser's own priority
>> queue as a stream dependency model.  I'd love to get a sense from browser
>> authors if that's likely to happen.)
>>
>
> I think it's premature to block on this. And yes, I'm also wondering if we
> should bother at all with 'plain HTTP'.
>
>
>> *Why not expose priority as a signed 32-bit integer?*
>>
>> For HTTP, this API is trivial to implement: just plumb the priority value
>> from Fetch down to the HTTP network stack.
>>
>
[snip SPDY]

For HTTP 2, mapping a 32-bit priority to an HTTP 2 linked list or skip list
>> is straightforward and O(lg N):
>> https://github.com/chadaustin/Web-Benchmarks/blob/master/http2/simpriority.py#L76
>>
>
> I disagree, as that runs precisely counter to our experience with SPDY.
> You've cited Will's post that provides at least one concrete example where
> this fails, and there are more:
> https://insouciant.org/tech/spdy-prioritization-case-study-gmail/
>

To make sure I understand your objection, I will replay it:  Are you saying
that, if two resources have the same numeric priority, but we map requests
to a dependency linked list, then HTTP 2 may starve the CSS in lieu of the
much larger script.  Is that what you meant?

(If you're saying that the fetches had incorrect priorities, which is the
specific example in Will's post, then I don't see how whether the
priorities were numeric or stream-based would have any effect on whether
the script would starve the CSS.)

You know, this is a fundamental flaw in HTTP 2's dependency model.  Given
the example above:

A0, A1, A2 at priority 7
B0, B1, B2 at priority 6
C at priority 5

There is no way to express the following partial ordering (and what is
prioritization but a partial ordering)...

{A0, A1, A2} <- {B0, B1, B2} <- C

...without also defining an ordering within {A0, A1, A2} and {B0, B1, B2},
due to Martin's linear chain explanation above.

If HTTP 2 supported numeric priorities, then A0, A1, and A2 are not ordered
relative to each other, and could be processed in parallel.  But since it
doesn't, to express that B0 depends on all of {A0, A1, A2}, you also need
A0 <- A1 <- A2 (or some other sequencing thereof).

Maybe it's time for me to go back to ietf-http-wg, though at this point in
the game, it's unlikely that anyone will want to change the spec.  Perhaps
the "dependency collapsing on close" requirement could be reversed, however.

The final piece necessary is some calibration against the browser's own
>> prioritization.  That is, the browser already prioritizes certain resources
>> - what priority value should they be given?  Or, if you wanted an XHR to
>> have lower-priority than a certain script tag, you could say something like:
>>
>> var xhr = new XMLHttpRequest;
>> // assume large values are higher priority
>> xhr.fetch.priority = document.getElementById('script').fetch.priority - 1;
>>
>
> In terms of high level requirements:
> - The developer *must* be able to override browser set priorities.
>

Agreed.


> - Developer set priorities must be on same playing field as browser set
> priorities
>

Agreed.


> As far as the API... I don't think `priority` is sufficient, for reasons
> stated above.
>

As I understand it, your only specific objection about numeric priorities
is that, given HTTP 2 semantics, there's no way to simultaneously express
"all requests at priority X can execute concurrently" and "all requests at
priority X should trump requests at priority X-1".

I agree that's a major problem with HTTP 2 priority semantics.  It seems
like a couple small changes to the HTTP 2 spec could solve this.  If, upon
stream close, dependencies didn't collapse until the entire level
collapses, then none of this would be an issue at all.  In that world, I
would be able to assign each priority as a level in the tree.

This is all great feedback and discussion -- thanks! Let's continue
> iterating...
>

Agreed, thank you.

Received on Monday, 20 October 2014 18:13:32 UTC