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

Hi Ilya,

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.  Per HTTP 2, "Streams with the
same parent SHOULD be allocated resources proportionally based on their
weight."  This is not the same thing as priority.  Weights may have value
to others, but they don't have value to the use case below.

OK, now that that's clear, let's have a redo:

*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.)

>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.

This goal of this thread is to provide feedback into how said priorities
should be specified.


*Current Browser Behavior*
Browsers have widespread support for two protocols (HTTP and SPDY) and are
likely to support HTTP 2 very soon.  Browsers currently prioritize requests
but there is no content-facing access to said priorities beyond the limited
<script defer> and various iframe tricks.

For basic HTTP connections, browsers maintain a fixed-size connection pool
which is fed by a priority queue.  Requests are issued on sockets in
priority order.

For SPDY, Chrome maps its own internal request priority to SPDY's 3-bit
priorities:
https://code.google.com/p/chromium/codesearch#chromium/src/net/spdy/spdy_http_utils.cc&sq=package:chromium&rcl=1412658928&l=168

Firefox does something similar
http://mxr.mozilla.org/mozilla-central/source/netwerk/protocol/http/SpdyStream3.cpp#370

HTTP 2 will not use a numeric priority but instead allows a partial
ordering between streams:
http://tools.ietf.org/html/draft-ietf-httpbis-http2-14#section-5.3

*The HTTP 2 Dependency Tree*

Unlike SPDY, HTTP 2 specifies priorities via a tree of stream
dependencies.  Streams at the root of a tree should be processed before
streams farther down the tree.

However, as discussed on ietf-http-wg [
http://lists.w3.org/Archives/Public/ietf-http-wg/2014OctDec/0059.html ], to
implement true *priority* semantics in HTTP 2, either a linked list of
streams is required [ see
https://github.com/chadaustin/Web-Benchmarks/blob/master/http2/simpriority.py#L72
] or the browser or server needs to guarantee that 1) it will remember
priority state about closed streams "long enough" and 2) children of closed
streams are processed AFTER the closed streams' siblings.  (Once closed, an
HTTP 2 stream is promoted to its parent's priority, which would mix up the
desired prioritization.  I can elaborate if desired.)

The trouble with a linked list is that the HTTP 2 PRIORITY frame costs
O(depth(parent) - depth(stream)) [
https://github.com/chadaustin/Web-Benchmarks/blob/master/http2/simpriority.py#L35
], and, with a linked list, reprioritizing a stream would be O(N), where N
is the number of requests.  Re-prioritizing M requests would be O(M*N).  In
that thread, there is some discussion of using skip lists once the number
of requests grows large, but that seems more like a workaround than a
solution.

It appears the dependency tree model originated from William Chan's
proposal here:
https://insouciant.org/tech/spdy-prioritization-case-study-gmail/

*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?
2) Should the priority API support future protocols beyond HTTP 2?
3) How likely is it future protocols will support non-dependency-based
priority models.
3) How much work should be placed on application developers?  aka how
closely should the API fit the application domain?

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 SPDY, the browser must then convert back to 3-bit integers
somehow
* 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.)


*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.

For SPDY, 32 bits would need to be mapped to 3 bits.  Something like
Mozilla's algorithm is likely sufficient:
http://mxr.mozilla.org/mozilla-central/source/netwerk/protocol/http/SpdyStream3.cpp#370

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

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;

*What about exposing weights?*

The only use case I've heard for HTTP 2 stream weights is when you have a
pile of progressive images on a page.  In almost all other cases, it's
better to download some resources sooner rather than have a bunch
partially-downloaded.

Should I write a document with a formal API proposal including rationale or
is this thread sufficient?

Thanks,
Chad


On Wed, Oct 1, 2014 at 9:33 PM, Ilya Grigorik <igrigorik@gmail.com> wrote:

>
>
> On Wed, Oct 1, 2014 at 8:39 PM, Chad Austin <caustin@gmail.com> wrote:
>
>> Weight is actually not what I want.  I want priority.  They're different
>> concepts in that priority implies trumping and weight implies proportional
>> resource allocation.
>>
>> That is, if I make 10 high-priority requests, 20 medium-priority
>> requests, and 30 low-priority requests, I don't want ANY of the
>> low-priority requests to consume any resources until either 1) all
>> higher-priority requests have been serviced or 2) there are spare resources
>> that cannot otherwise be used for higher-priority requests.
>>
>
> And.. you've just defined a three-level deep dependency tree, with weights
> for resources within each group.
>


> As you quoted, "Streams with the same parent SHOULD be allocated resources
>> proportionally based on their weight."  Proportional allocation would be
>> incorrect for this use case.
>>
>
> Proportional within the same level of the tree, and based on assigned
> weights within that level.
>
> ig
>
>
>
>>
>> On Wed, Oct 1, 2014 at 8:19 PM, Ilya Grigorik <igrigorik@gmail.com>
>> wrote:
>>
>>>
>>> On Wed, Oct 1, 2014 at 7:59 PM, Chad Austin <caustin@gmail.com> wrote:
>>>
>>>> I don't see a way to set a priority value in there.  The specific
>>>> wording is "Streams can be prioritized by marking them as dependent on the,
>>>> completion of other streams".
>>>>
>>>> I see that a client can specify the weight of a stream and you can say
>>>> that a stream depends on another stream.  Neither of those are what I
>>>> want.  I simply want to specify priorities of a bunch of requests.  How
>>>> would I do that in HTTP 2.0?
>>>>
>>>
>>> Weight is exactly what you want:
>>> http://tools.ietf.org/html/draft-ietf-httpbis-http2-14#section-5.3.2
>>>
>>> "A stream that is not dependent on any other stream is given a stream
>>>    dependency of 0x0.  In other words, the non-existent stream 0 forms
>>>    the root of the tree."
>>>
>>> All dependent streams are allocated an integer weight between 1 to
>>>    256 (inclusive)... Streams with the same parent SHOULD be allocated
>>> resources
>>>    proportionally based on their weight. "
>>>
>>> In other words, if you don't care about dependencies, then don't assign
>>> the parent. Doing so will make all streams children of the root of the tree
>>> (0x0), and from there you can use weights to assign relative priority.
>>>
>>> Hope that makes sense.
>>>
>>> ig
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Chad Austin
>> http://chadaustin.me
>>
>
>


-- 
Chad Austin
http://chadaustin.me

Received on Thursday, 9 October 2014 19:27:25 UTC