Subject: Question about HTTP 2.0 priority

From: Chad Austin <[email-masked]>
Date: Wed, 1 Oct 2014 18:12:36 -0700

Hi,

I am reading the HTTP 2.0 draft, and I wonder whether HTTP 2.0 supports
implementing simple stream priorities like SPDY does.

Our use case is documented in detail at
http://chadaustin.me/2014/08/web-platform-limitations-xmlhttprequest-priority/
, but I will summarize here.

We have a whole pile of 3D assets that we need to retrieve from various
URLs and load into WebGL.  Some of them are higher-priority than others.
None of them depend on any other.  For example, we may want to prioritize
resources closer to the camera.  We definitely want to prioritize meshes
and low-resolution textures over high-resolution textures and animation
files.

Ideally, our application would immediately issue ALL requests and let the
browser's network stack (and HTTP/SPDY/HTTP2 backend) efficiently utilize
the socket(s) and bandwidth to transfer high-priority assets before
low-priority assets.  However, if there is available bandwidth, we would
benefit from receiving low-priority assets in the meantime.

We would benefit from a large number of priority bits, but could make it
work with as low as 3 bits.  (2 bits would be too few.)

How do I map that use case to HTTP 2.0's dependency graph?  At first blush,
it seems hard: I'd have to define a stream per priority level, and set
dependencies such that all low-priority streams depend on high-priority
streams?  And if a high-priority stream finishes, then reset the dependency
to another high-priority stream?

-- 
Chad Austin
http://chadaustin.me

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 02 Oct 2014 19:01:07 +1300

On 2/10/2014 2:12 p.m., Chad Austin wrote:
> Hi,
> 
> I am reading the HTTP 2.0 draft, and I wonder whether HTTP 2.0
> supports implementing simple stream priorities like SPDY does.
> 
> 
> We have a whole pile of 3D assets that we need to retrieve from
> various URLs and load into WebGL.  Some of them are higher-priority
> than others. None of them depend on any other.  For example, we may
> want to prioritize resources closer to the camera.  We definitely
> want to prioritize meshes and low-resolution textures over
> high-resolution textures and animation files.
> 
> Ideally, our application would immediately issue ALL requests and
> let the browser's network stack (and HTTP/SPDY/HTTP2 backend)
> efficiently utilize the socket(s) and bandwidth to transfer
> high-priority assets before low-priority assets.  However, if there
> is available bandwidth, we would benefit from receiving
> low-priority assets in the meantime.
> 
> We would benefit from a large number of priority bits, but could
> make it work with as low as 3 bits.  (2 bits would be too few.)
> 
> How do I map that use case to HTTP 2.0's dependency graph?  At
> first blush, it seems hard: I'd have to define a stream per
> priority level, and set dependencies such that all low-priority
> streams depend on high-priority streams?  And if a high-priority
> stream finishes, then reset the dependency to another high-priority
> stream?
> 

Not hard at all. Just reverse your thinking about priority levels.

You have to create a stream per asset in HTTP/2. The priority for the
stream is assigned based on which *single* asset that stream is being
used to deliver.

For assiging HTTP/2 priorities to your assets just work out the
dependency tree they naturally have anyway. Then walk down it
assigning the root asset the highest priority and each successive
level gets assigned a dependency on the asset/stream above it in the tree.

If the drawing dependency is something like:
 map/mesh -> objects -> skeletons -> low-res texture -> high-res texture

The HTTP/2 fetch dependency would be:
 map-/mesh <- objects <- skeletons <-low-res <- high-res

eg.
 - everything depends on the map/mesh finishing first.
 - object descriptions need to finish next,
 - followed by skeletons as the object they are for finishes,
 - followed by low-res textures once skeleton+object are finished,
 - high-res texture for a construct only required after all the
previous bits are in.

When there is multiple (say 20) high-priority objects/skeletons
depending on a single low-res texture it is up to you whether you make
a dependency of the low-res texture on the 1st objects stream ID or
the 20th objects. If priority is obeyed, depending on the first object
will allow that and later received objects to a bit render earlier
incrementally, depending on the last one will make them all wait for
complete data, but then render as a batch.

HTTP/2 explicitly makes priority optional, so it helps your download
performance if the requests are ordered in a similar way to how you
want them prioritized ("by group" as it were). That way even a naive
intermediary which ignores priority is likely to server the
most-wanted assets first due purely to their stream ID numbers being
first.

Amos

---

From: Chad Austin <[email-masked]>
Date: Thu, 2 Oct 2014 01:07:44 -0700

Thank you for your explanation, Amos.  Thanks especially for clarifying
that each assets is its own stream.

You're right that I can use dependencies to implement statically-known
priorities.  Let me see if it's possible to do the same with a more
complicated and dynamic (and realistic) example:

Let's imagine loading a 3D scene.  It contains one room object, 3 avatar
objects (including your own), and 5 pieces of furniture.

To load an object, first a JSON "object description" must be downloaded.
This object description roughly corresponds to the HTML on a web page; it
contains links to the remaining assets: meshes, thumbnail textures, and
high-res textures.  Once the object description JSON is downloaded, all of
the remaining assets are requested in parallel.  The object will not be
visible in WebGL until the meshes and low-res textures are downloaded.
Afterwards, the high-res textures are placed in the scene when they finish
downloading (which could be many seconds or even minutes in the future, as
a scene typically contains 50 MB of high-resolution texture data.)

Calculating priority for a request takes three factors into consideration:
which object the request is for, the type of the asset being loaded, and
for some objects the distance from the camera, per the following table:

Room, My Avatar

Furniture, Other Avatars

Object Descriptions

290

280 - DistanceFromCamera

Meshes, Lo-res Textures

190

180 - DistanceFromCamera

High-res Textures

90

80 - DistanceFromCamera

The loadObject algorithm looks something like the following JavaScript.
Load requests happen in some arbitrary order on the web page (as people
come and go from the 3D scene.)  The web page knows how to calculate the
priorityModifier given the above algorithm.

function loadObject(url, priorityModifier) {
    var object = new Object3D;

    // first we need to load the object description JSON
    return request(url, 200 + priorityModifier)

        // parse it into an object description
        .then(parseObjectDescription)

        .then(function(desc) {
            // optimistically begin fetching all low-priority, high-res
textures
            requestHighResTextures(desc.highResTextures + priorityModifier);

            // then, once the meshes and low-res textures loaded, place the
object in the scene
            return Promise.all([
                requestMeshes(desc.meshes, 190 + priorityModifier),
                requestTextures(desc.lowResTextures, 190 +
priorityModifier),
            ]).then(function() {
                object.makeVisibleInScene();
            });
        });
}

function calledEverySecond() {
    // go through all pending object loads for furniture and other avatars
    // adjust priorities based on distance from camera
}

// call loadObject once for the room, once for your avatar, a few times for
the other avatars, and a few times for the furniture
// the sequence of loadObject calls is not necessarily known in advance

That was a long example, but I hope it demonstrates why it's not entirely
obvious how to build an HTTP/2 dependency graph from what are conceptually
just priorities.

This gets especially hairy when a bunch of low-priority requests depend on
a request that finishes...  if I understand the spec correctly, that will
implicitly bump up the priority of the low-priority requests, which would
be undesirable here.  Low-priority needs to STAY low-priority, even as
higher-priority (aka dependent) requests finish.

Why does HTTP/2 have such a complicated system for priority rather than
SPDY's simple priority integer?  It seems a simple priority value would
make everything so much simpler for both clients and servers.

Thanks again.  I truly appreciate that you took the time to understand my
use case and respond as such.

Chad

On Wed, Oct 1, 2014 at 11:01 PM, Amos Jeffries <[email-masked]> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.22 (MingW32)
>
> iQEcBAEBAgAGBQJULOojAAoJELJo5wb/XPRjoCkIAMsSm78OpqY+HxJXwkBfDRb8
> +2wDSSBuXuTRkCdhkblT2u/5wgsSvfnoZaPAf2dEMa9j2qK2LUgUUiwMN6wIPH38
> WFvq/YLNKMNKecx2r7JvbZ//vvLgyFp5vP1D4mcSpWbf1RY3jKoRd7bfnD7wu/vO
> OOZify8d3Qq5r6Ax2Cj2kkhfuudFwlpg1CsmOd5PNrxan7qjLc3tRYeMB5SJU6W/
> TxmuIq0iLSvdiHDawANk/sI9sesjB7Wblu8WjuZh4+XaQClHRuNv9PS8yFrY/Qzq
> I5chqtT27X+cV8CX4GojjWQi9pFqUksAsnmP2VlKquBeSqDq7tl/1/M/H/VTHhU=
> =ZG/f
> -----END PGP SIGNATURE-----
>
>

-- 
Chad Austin
http://chadaustin.me

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 02 Oct 2014 22:07:06 +1300

On 2/10/2014 9:07 p.m., Chad Austin wrote:
> Thank you for your explanation, Amos.  Thanks especially for
> clarifying that each assets is its own stream.
> 
> You're right that I can use dependencies to implement
> statically-known priorities.  Let me see if it's possible to do the
> same with a more complicated and dynamic (and realistic) example:
> 
> Let's imagine loading a 3D scene.  It contains one room object, 3
> avatar objects (including your own), and 5 pieces of furniture.
> 
> To load an object, first a JSON "object description" must be
> downloaded. This object description roughly corresponds to the HTML
> on a web page; it contains links to the remaining assets: meshes,
> thumbnail textures, and high-res textures.  Once the object
> description JSON is downloaded, all of the remaining assets are
> requested in parallel.  The object will not be visible in WebGL
> until the meshes and low-res textures are downloaded. Afterwards,
> the high-res textures are placed in the scene when they finish 
> downloading (which could be many seconds or even minutes in the
> future, as a scene typically contains 50 MB of high-resolution
> texture data.)
> 
> Calculating priority for a request takes three factors into
> consideration: which object the request is for, the type of the
> asset being loaded, and for some objects the distance from the
> camera, per the following table:
> 
> 
> 
> Room, My Avatar
> 
> Furniture, Other Avatars
> 
> Object Descriptions
> 
> 290
> 
> 280 - DistanceFromCamera
> 
> Meshes, Lo-res Textures
> 
> 190
> 
> 180 - DistanceFromCamera
> 
> High-res Textures
> 
> 90
> 
> 80 - DistanceFromCamera
> 
> 
> The loadObject algorithm looks something like the following
> JavaScript. Load requests happen in some arbitrary order on the web
> page (as people come and go from the 3D scene.)  The web page knows
> how to calculate the priorityModifier given the above algorithm.
> 
> function loadObject(url, priorityModifier) { var object = new
> Object3D;
> 
> // first we need to load the object description JSON return
> request(url, 200 + priorityModifier)
> 
> .then(function(desc) { // optimistically begin fetching all
> low-priority, high-res textures 
> object in the scene return Promise.all([ requestMeshes(desc.meshes,
> 190 + priorityModifier), requestTextures(desc.lowResTextures, 190
> + priorityModifier), ]).then(function() { 
> object.makeVisibleInScene(); }); }); }
> 
> function calledEverySecond() { // go through all pending object
> loads for furniture and other avatars // adjust priorities based on
> distance from camera }
> 
> // call loadObject once for the room, once for your avatar, a few
> times for the other avatars, and a few times for the furniture //
> the sequence of loadObject calls is not necessarily known in
> advance
> 
> 
> That was a long example, but I hope it demonstrates why it's not
> entirely obvious how to build an HTTP/2 dependency graph from what
> are conceptually just priorities.
> 
> This gets especially hairy when a bunch of low-priority requests
> depend on a request that finishes...  if I understand the spec
> correctly, that will implicitly bump up the priority of the
> low-priority requests, which would be undesirable here.
> Low-priority needs to STAY low-priority, even as higher-priority
> (aka dependent) requests finish.

Nod. Its a bit hairy, yes.

The PRIORITY frame can help. I would have the requestHighResTextures()
maintain a list of pending the low-priority assets, which are
prioritized as a sequential dependency chain. With the first stream of
that chain being bumped around by PRIORITY to depend on lowest of the
hi-priority set if/when new hi-priority are added.

> 
> Why does HTTP/2 have such a complicated system for priority rather
> than SPDY's simple priority integer?  It seems a simple priority
> value would make everything so much simpler for both clients and
> servers.

Complication is an emergent property of design-by-commitee combining
both dependency and weighting. For simplicity you can ignore the
weighting, but when you get down to fine-tuning priorities it comes in
handy.

Given you have a table of values to work from, you could map those
into HTTP/2 weight values and have all your high-priority types set
with default dependency. That places them all as highest priority but
bandwdth weighted. The low-priority set as I mention above in a
sequential dependency chain whih is bumped "down" to depend on
whatever the outstanding hi-priority object(s) are.

Remember this is all just a preference, if there is spare bandwidth
and data are available for any asset it can and probably will be
delivered earlier than indicated by the priority order.
> 
> Thanks again.  I truly appreciate that you took the time to
> understand my use case and respond as such.
> 
> Chad
> 
> 
>>>> I am reading the HTTP 2.0 draft, and I wonder whether HTTP
>>>> 2.0 supports implementing simple stream priorities like SPDY
>>>> does.
>>>> 
>>>> 
>>>> We have a whole pile of 3D assets that we need to retrieve
>>>> from various URLs and load into WebGL.  Some of them are
>>>> higher-priority than others. None of them depend on any
>>>> other.  For example, we may want to prioritize resources
>>>> closer to the camera.  We definitely want to prioritize
>>>> meshes and low-resolution textures over high-resolution
>>>> textures and animation files.
>>>> 
>>>> Ideally, our application would immediately issue ALL requests
>>>> and let the browser's network stack (and HTTP/SPDY/HTTP2
>>>> backend) efficiently utilize the socket(s) and bandwidth to
>>>> transfer high-priority assets before low-priority assets.
>>>> However, if there is available bandwidth, we would benefit
>>>> from receiving low-priority assets in the meantime.
>>>> 
>>>> We would benefit from a large number of priority bits, but
>>>> could make it work with as low as 3 bits.  (2 bits would be
>>>> too few.)
>>>> 
>>>> How do I map that use case to HTTP 2.0's dependency graph?
>>>> At first blush, it seems hard: I'd have to define a stream
>>>> per priority level, and set dependencies such that all
>>>> low-priority streams depend on high-priority streams?  And if
>>>> a high-priority stream finishes, then reset the dependency to
>>>> another high-priority stream?
>>>> 
> 
> You have to create a stream per asset in HTTP/2. The priority for
> the stream is assigned based on which *single* asset that stream is
> being used to deliver.
> 
> If the drawing dependency is something like: map/mesh -> objects ->
> skeletons -> low-res texture -> high-res texture
> 
> The HTTP/2 fetch dependency would be: map-/mesh <- objects <-
> skeletons <-low-res <- high-res
> 
> eg. - everything depends on the map/mesh finishing first. - object
> descriptions need to finish next, - followed by skeletons as the
> object they are for finishes, - followed by low-res textures once
> skeleton+object are finished, - high-res texture for a construct
> only required after all the previous bits are in.
> 
> depending on a single low-res texture it is up to you whether you
> make a dependency of the low-res texture on the 1st objects stream
> ID or the 20th objects. If priority is obeyed, depending on the
> first object will allow that and later received objects to a bit
> render earlier incrementally, depending on the last one will make
> them all wait for complete data, but then render as a batch.
> 
> HTTP/2 explicitly makes priority optional, so it helps your
> download performance if the requests are ordered in a similar way
> to how you want them prioritized ("by group" as it were). That way
> even a naive intermediary which ignores priority is likely to
> server the most-wanted assets first due purely to their stream ID
> numbers being first.
> 
> Amos
> 
>> 
>> 
> 
>

---

From: Chad Austin <[email-masked]>
Date: Mon, 6 Oct 2014 10:39:37 -0700

Hi Amos,

*On the dependency tree:*

Over the weekend, I built a little simulation of HTTP 2 priority semantics
to get a feel for how it would play out.  Note: I ignored weight, since
weight and priority are different concepts, and weight is not useful for my
use case or particularly controversial.

https://github.com/chadaustin/Web-Benchmarks/blob/master/http2/simpriority.py

The implementation of the dependency tree on the server side is
straightforward.  However, it seems that changing priority via the PRIORITY
frame is O(depth(parent) - depth(stream)) for the cycle check.  For a
mostly linear dependency tree, this means reprioritizing is approximately
O(n) where n is the number live streams.

Is there a faster way to detect whether a stream is going to be prioritized
below one of its children?

*On mapping priority numbers to the dependency tree:*
By keeping a sorted, stable list of (priority, stream_id), with, say, O(lg
N) right-insertion, we can implement the invariant that "requests of higher
priority are higher in the tree.  within a priority level, streams are
ordered in request order."  This could be implemented with a self-balancing
binary tree.

The prioritization algorithm described results in a linear dependency
"tree".  This means that reprioritization is approximately O(n) per
PRIORITY frame.  Given even our simple use case can request up to
10,000-20,000 assets at a time, reprioritization cost is worth worrying
about.

If it's truly the case that PRIORITY is O(depth(parent) - depth(stream)),
does that leave an implementation of HTTP 2's priority graph open to denial
of service?

p.s. While I have argued for a simple priority integer (and have not yet
ruled out that a priority integer would be superior), I see the advantages
of the dependency tree model.  The dependency tree model defines a partial
ordering and thus sidesteps the problem of calibration.  "What does
priority 100 mean?  200?  What priority value do XHR requests get?  Image
loads?  HTML loads?"  The dependency tree model lets you say "A before B"
or "A before B and its siblings".

Design by committee can work, but you should consider maintaining a set of
rationales for design decisions.  :)

On Thu, Oct 2, 2014 at 2:07 AM, Amos Jeffries <[email-masked]> wrote:

> iQEcBAEBAgAGBQJULRW6AAoJELJo5wb/XPRjFMgH/3J0C4klXronIszBvvnCkYDU
> prIleZAqJfkMyM6/HVeBXf9+4oMkaxleZDmJYo8496Phh6BWbBboRsRW0+/pwrtK
> YGAnNg0NrHScxJRBDCZR75ENPEIPBdemKMPpBQwWsS7mFYrQR2GCeR+CXTCSeKma
> AyBaqMtwNfzHqBvz4cfNWqyE/+1wU12h9Wg1XndeTJo/Pi3R5BMp08LwnKjhJ/QY
> h1tw6f71xLZDU0yifj/J44nCq3KkCcMMSznRuB8VhkftuMgc5kOYQWr5r/d7N1V8
> NNmiDEm7a/j1y2+7JeUzDeB4MjAFXvA8Zf5x8obQQjQJI7UJ/yPujsJDK4FaviQ=
> =5k/P

-- 
Chad Austin
http://chadaustin.me

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Oct 2014 11:20:35 -0700

> does that leave an implementation of HTTP 2's priority graph open to denial

That depends on what trade-offs you want to make.

If you really do have a tree that is 10k entries deep, then walking
what is effectively a linked list is going to cost a non-trivial
amount of time.  But you don't have to maintain a linked list.  As you
note, a small increase in complexity and storage allows for certain
kinds of reprioritization.

But if you are talking about attack modes, then I'd consider just
dropping any prioritization that doesn't work out for you.

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 7 Oct 2014 10:01:55 +1100

The sllght concern that I have with the priority model is that it
represents a dynamic weighted priority tree that gives a level of
resolution that a server will not be able to well achieve, or that it may
be counter productive for a server to attempt to achieve.

Asking for resource A before B does not mean that the server can actually
generate A before B. Asking for a 20:80 split between A and B does not mean
that those resources will can actually be generated at that rate.    A
server may not know if a resource is available to be served until it has
allocated resources to it (eg dispatch at thread) and then the availability
of that resource will often be dependent on external resources (eg
database).

Given that limitation, it is likely that servers may implement priorities
in accordance with 5.3's

Most importantly, priority can be used to select streams for transmitting
frames when there is limited capacity for sending.

I'm not sure this is "most importantly" - at least not for the server as
enforcing priorities at the point of selecting which frames to send is not
really a good way of allocating server resources.   Once generation of a
resource on the server has started, significant CPU/memory will have been
allocated before the first byte is ready to be sent and  it may be a higher
server priority to let that generation run to completion rather than hold
it up while it allocates more resources to any dynamically increased client
priorities on other streams.

But having priorities is definitely important. When confronted with a
connection that has just delivered 80+ requests, the last thing a server
should do is simply dispatch them all and let them smear the data from a
single user over all the servers cores/caches (Jetty currently does just
dispatch them all).     To make servers scalable, we will definitely need
to restrict requests from a single connection to a lower degree of
parallelism than is possible, so we will definitely need priorities to
assist with that.

But any priorities result achieved by dispatch order and/or thread priority
is going to only be a very rough approximation of the high resolution
priority tree that 5.3 describes.     So the question is, should the server
also then attempt to enforce priorities when selecting the frames to send?
Ie should it double down resources in an attempt to more closely match the
clients priority model? Having already committed CPU and memory in an
approximation of the clients priorities, should it hold up those resources
and commit more to other streams to try to achieve a more precise match to
an individual clients priorities?       Difficult question and the answer
will depend on the tradeoff a server is willing to make between individual
QoS and scaling for many connections.

So I think that something more than a simple High/Low/Medium priority is
required as we do need to get a partial ordering of many resources.   But
equally, I think it is hard to say if the detail of a dynamic weighted tree
is going to be overkill or worse - counter productive to try to
calculate/enforce.

I think a lot of experimentation is needed and that it is worthwhile giving
the tree model a go.... but it would be good if we also had a fall back to
simple absolute values that could be used to communicate a partial
ordering.    Would it be worthwhile to explicitly say that streams can be
given weights against a dependency on stream 0, which would then act as an
absolute priority declaration?

Also,  I suspect that it might also be good to have a priority frame that
could send many stream priorities in a single frame - so the server could
re-evaluate the tree only once, rather repeatedly as each priority frame
arrives.

cheers

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Oct 2014 17:28:24 -0700

On 6 October 2014 16:01, Greg Wilkins <[email-masked]> wrote:
> simple absolute values that could be used to communicate a partial ordering.
> Would it be worthwhile to explicitly say that streams can be given weights
> against a dependency on stream 0, which would then act as an absolute
> priority declaration?

When we discussed this, we decided that we'd do almost that, but leave
the weighting scheme intact.  That's going to be suboptimal, but if
weights are artificially exaggerated by a server, the net effect is
not too dissimilar.

---

From: Chad Austin <[email-masked]>
Date: Mon, 6 Oct 2014 22:13:13 -0700

> kinds of reprioritization.

The part I haven't been able to wrap my head around -- and maybe you can
help -- is, if I reduce the depth of the tree from an N-entry linked list,
where N is the number of requests, to a K-depth tree, where K is the number
of unique priorities, how do I prevent completion of the dependent request
from automatically bumping everything at a lower priority to a higher
priority?  That is, given three priorities A, B, and C (A is highest):

A1    A2    A3
^
+-----+
+     +-----+
B1    B2    B3
^
+-----+
+     +-----+
C1    C2    C3

Sorry for the terrible ASCII art.  :)  Everything at priority B depends on
some element in A, and everything in C depends on some element in B.

How do I handle the case that B1 completes before B2?

As I understand the spec, if that happens, then the dependency tree would
be reduced to:

A1    A2    A3
^
<-----+
|     <-----+
|     |     <-----+
+     +     +     +-----+
C1    C2    C3    B2    B3

It seems a linked list is truly necessary to express "Everything in B is
lower priority than everything in A" and "Everything in C is lower priority
than everything in B".

Am I missing something?

-- 
Chad Austin
http://chadaustin.me

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Oct 2014 22:26:01 -0700

> How do I handle the case that B1 completes before B2?

I tend to write it out like so:  (A1, A2, A3) -> 0; B1 -> A1; B2 -> A1
and B3 -> A1; C1 -> B1; C2 -> B1; and C3 -> B1.

So yes, if B1 is removed, then all the C moves up to depend on A1...
and takes a proportional weight from the removed B1.

But the draft recommends not removing when a stream completes, because
that loses information.  Keep it around.  Put it in a LRU list or
something and remove it when you have to, or when it isn't referenced,
or when it is too old.  Then you lose nothing more than a few bytes of
RAM, and maybe a few extra cycles when nearby elements move around, or
are added.

A linked list is fine for nodes with the same dependency, but I tend
to think of it as a set.  A skip list might be more efficient if you
think that you'll have lots of adjacent nodes.

---

From: Chad Austin <[email-masked]>
Date: Mon, 6 Oct 2014 22:48:25 -0700

> RAM, and maybe a few extra cycles when nearby elements move around, or

"Keep it around."

Are you suggesting that either the client, server, or both keep it around?
Does it matter if it's half closed?

If an efficiently prioritizing server can simply keep the dependencies for
old streams around then my concern is less valid.

> think that you'll have lots of adjacent nodes.

[Note: the next two paragraphs are only relevant if for some reason it's
hard to keep old stream records around.]

Yeah, all nodes at a given priority *are* a set, but it sounds like there's
no way to get set dependency semantics without a linked list.  A linked
list is too much precision: I don't particularly care the order of
completion within a priority level.  A skip list, while slightly more
efficient for the server, allows a bit of "priority leakage".

It's not the worst thing in the world, but ultimately we're going to be
pushing the customer experience as hard as we can.  With a linked list (and
an optimally prioritizing server), the theoretical lower bound on load
times is ideal: the customer's network connection wouldn't even begin
consuming bandwidth on low-priority responses until the high-priority
responses are done.

-- 
Chad Austin
http://chadaustin.me

---

From: Martin Thomson <[email-masked]>
Date: Tue, 7 Oct 2014 13:34:17 -0700

> Does it matter if it's half closed?

Well, a client that knows it's not going to use a stream as a basis
for prioritization can discard the state immediately.  A server
doesn't have that opportunity, so it has to use some heuristics to
determine what to keep and what to delete.

The point is that prioritization state isn't strictly tied to stream
state.  If stream 7 depends - or could depend - on stream 5, stream 5
might be closed at the server when initial or updated priority
information for stream 7 arrives.  If the server cares about
respecting prioritization for stream 7, it had best find a way to keep
stream 5 in its priority graph somehow.

---

From: Chad Austin <[email-masked]>
Date: Thu, 9 Oct 2014 11:05:05 -0700

Thanks, Martin.  If a client can rely on two things, then a linked list is
not necessary:

1. the server will keep the priority tree information for closed streams
"long enough"
2. In the case of "(A1, A2, A3) -> 0; (B1, B2, B3) -> A1", if A1 completes
before A2, the server will apply any available resources to A2 and A3
before any of B1, B2, or B3.

Sounds like you're saying #1 is likely.

Can you confirm that #2 is also the behavior specified by the current draft?

Are there any implementations of HTTP 2 priority semantics in the wild?  Do
we have any real-world experience with how they work?  Will Chan argues
compellingly that prioritization is a crucial part of SPDY [1] -- where 3
bits has been precise enough for basic browser use cases -- and it seems
the HTTP 2 stream priority model originates from his deck Considerations
for HTTP/2 Prioritization [2].

What's your over-under on whether a future protocol or version of HTTP 2
would support numeric priorities in addition to or in lieu of the stream
dependency model?

I ask because I'm simultaneously pushing to have a request prioritization
API added to browsers, and it seems a bit optimistic for the API exposed to
JavaScript to map directly to HTTP 2 semantics.

[1] https://insouciant.org/tech/prioritization-is-critical-to-spdy/
[2]
https://docs.google.com/presentation/d/1OfgPJsW6P7pky5PiyEzBNZnf5dWXq-y19ReSSg6BIeM/pub

-- 
Chad Austin
http://chadaustin.me

---

From: Mike Bishop <[email-masked]>
Date: Thu, 9 Oct 2014 18:17:41 +0000

Note that priority is always strictly advisory - the client cannot "rely" on the server having any particular behavior in response to the priority information it sends.  The priority field permits the client to provide the server additional information to consider when making its own decisions about how to allocate resources.  A server would be completely compliant with the HTTP/2 protocol to return the resources with A1 last.  Now, that's probably not a good implementation unless there's some factor the client doesn't know about - but that's the point.  There might well be, and the protocol doesn't forbid that case.

From: Chad Austin [mailto:[email-masked]]
Sent: Thursday, October 9, 2014 11:05 AM
To: Martin Thomson
Cc: Amos Jeffries; HTTP Working Group
Subject: Re: Question about HTTP 2.0 priority

Thanks, Martin.  If a client can rely on two things, then a linked list is not necessary:
1. the server will keep the priority tree information for closed streams "long enough"
2. In the case of "(A1, A2, A3) -> 0; (B1, B2, B3) -> A1", if A1 completes before A2, the server will apply any available resources to A2 and A3 before any of B1, B2, or B3.
Sounds like you're saying #1 is likely.

Are there any implementations of HTTP 2 priority semantics in the wild?  Do we have any real-world experience with how they work?  Will Chan argues compellingly that prioritization is a crucial part of SPDY [1] -- where 3 bits has been precise enough for basic browser use cases -- and it seems the HTTP 2 stream priority model originates from his deck Considerations for HTTP/2 Prioritization [2].
What's your over-under on whether a future protocol or version of HTTP 2 would support numeric priorities in addition to or in lieu of the stream dependency model?
I ask because I'm simultaneously pushing to have a request prioritization API added to browsers, and it seems a bit optimistic for the API exposed to JavaScript to map directly to HTTP 2 semantics.

[1] https://insouciant.org/tech/prioritization-is-critical-to-spdy/
[2] https://docs.google.com/presentation/d/1OfgPJsW6P7pky5PiyEzBNZnf5dWXq-y19ReSSg6BIeM/pub

On Tue, Oct 7, 2014 at 1:34 PM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:

--
Chad Austin
http://chadaustin.me

---

From: Chad Austin <[email-masked]>
Date: Thu, 9 Oct 2014 11:35:59 -0700

Hi Mike,

I fully understand that priority is advisory.  In practice, however,
priority is critically important, and we will implement solutions that take
full advantage of it.  (We will also push our CDN partners, HTTP servers,
etc. to have reasonable behavior.)  Without priority, there's no way to
both maximize the customers' network connection AND minimize
time-to-interactivity and time-to-perceived-load.

Without priority, HTTP 2 can be slower than HTTP!  Browsers maintain a
fixed-size HTTP connection pool which is fed from a priority queue of
requests.  See the analysis here:
https://insouciant.org/tech/prioritization-is-critical-to-spdy/

If a server does not implement reasonable priority semantics, clients must
sacrifice effective network utilization by waiting for all high-priority
responses before issuing any low-priority requests.  Especially on
high-latency connections, this results in a poor customer experience.

And, of course, the most interesting thing about this entire discussion is
that managing a request priority queue is often very easy for both clients
and servers.  I will expect all high-quality HTTP 2 caching proxies and
CDNs to implement priority.

I still wonder whether a simple 8-bit or 32-bit priority value would have
been superior of the stream tree model.  However, I'm also prepared to
handle the situation where HTTP 2 ships as currently-specified.  :)

Thanks,
Chad

On Thu, Oct 9, 2014 at 11:17 AM, Mike Bishop <[email-masked]>
wrote:

>  Note that priority is always strictly advisory - the client cannot
> "rely" on the server having any particular behavior in response to the
> priority information it sends.  The priority field permits the client to
> provide the server additional information to consider when making its own
> decisions about how to allocate resources.  A server would be completely
> compliant with the HTTP/2 protocol to return the resources with A1 last.
> Now, that's probably not a good implementation unless there's some factor
> the client doesn't know about - but that's the point.  There might well be,
> and the protocol doesn't forbid that case.
>
>
>
> *From:* Chad Austin [mailto:[email-masked]]
> *Sent:* Thursday, October 9, 2014 11:05 AM
> *To:* Martin Thomson
> *Cc:* Amos Jeffries; HTTP Working Group
> *Subject:* Re: Question about HTTP 2.0 priority
>
>
>
> Are there any implementations of HTTP 2 priority semantics in the wild?
> Do we have any real-world experience with how they work?  Will Chan argues

-- 
Chad Austin
http://chadaustin.me

---

From: Martin Thomson <[email-masked]>
Date: Thu, 9 Oct 2014 11:41:50 -0700

On 9 October 2014 11:05, Chad Austin <[email-masked]> wrote:
> before A2, the server will apply any available resources to A2 and A3 before
> any of B1, B2, or B3.
>

Yep.

> Can you confirm that #2 is also the behavior specified by the current draft?

Not as specified.  This would allocate any resources that might have
been allocated to A1 to its descendants.  We can't express a
dependency on multiple resources, except by creating a linear chain:
B2 -> B1 -> A2 -> A1 -> 0.

---

From: Greg Wilkins <[email-masked]>
Date: Fri, 10 Oct 2014 11:12:08 +1100

On 10 October 2014 05:35, Chad Austin <[email-masked]> wrote:

> and servers.

Actually it can be very hard for a server and there are some tough issues
to deal with.  Priority is going to be a very hard nut to crack on the
Server.    From a clients point of view it is mostly about optimising round
trips and network utilisation, but a server has to consider overall through
put as well as keeping individual connections optimal.     It is probably
not sensible for a server to throw all of it's cores at a single connection
to optimally drive the network utilisation for 1 client when it may have
99,999+ other client connections to consider.

Thus I believe that servers are going to have to limit the degree of
parallelism they are prepared to allocated to a single connection,
otherwise HTTP/2 will have very bad mechanical sympathy.

So lets say that we have a queue of 30 request in priority order.    A
server may wish to limit the parallelism that it gives to this, so it may
allocate threads only to the first few requests and it makes sense to pick
them in priority order.    But what if those high priority requests are
slow to generate?   Should the server still wait for them to complete even
though the network connection for that client is idle at if it allocated a
thread to a lower priority resource it might be able to progress?

This will of course be further complicated by push, where 29 of those
requests are generated from push_promises from information that the server
knows about the base request, which could include time to generate
dependencies and priorities assigned on previous pushes.  A server might
know that it has some low priority quick resources that it can dispatch and
server in the time it takes some high priority slow resources to be
generated.  Static resources might be able to be asynchronously pushed
while generated resources may need a thread, further complicating the
resource allocation.

cheers

-- 
Greg Wilkins <[email-masked]>  @  Webtide - *an Intalio subsidiary*
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 10 Oct 2014 10:08:16 +0900

"long enough"
> 2. In the case of "(A1, A2, A3) -> 0; (B1, B2, B3) -> A1", if A1
completes before A2, the server will apply any available resources to A2
and A3 before any of B1, B2, or B3.

Nghttp2 implements dependency based periority.  It also supports 1 and 2
behaviour you described above.  You can test nghttp2 server at
https://nghttp2.org

Best regards,
Tatsuhiro Tsujikawa

---

From: Chad Austin <[email-masked]>
Date: Wed, 15 Oct 2014 01:09:34 -0700

On Thu, Oct 9, 2014 at 5:12 PM, Greg Wilkins <[email-masked]> wrote:

>> And, of course, the most interesting thing about this entire discussion
>> is that managing a request priority queue is often very easy for both
>> clients and servers.
>
>

I did not mean that prioritization in general is easy all the time.  I was
just pointing that managing a priority queue is simpler than (or as simple
as) a dependency tree model.  I have yet to understand why HTTP 2 chose a
dependency tree for priority over a priority queue.  I understand, however,
that it's unlikely to change at this point in the process.

> thread to a lower priority resource it might be able to progress?

In the past, to solve similar problems, I've broadly characterized request
handlers as CPU-bound, disk-bound, or whatever.  A-bound for some resource
A.  :)  Then each resource gets its own priority queue.  The HTTP 2
connection would push each request into the appropriate resource queue,
where it would be executed as resources are available.  Thus, if a bunch of
CPU-bound requests arrive, and ~all the cores are effectively busy, a
disk-bound request could still be processed and returned immediately.

This approach gets trickier when request handlers are bound on a mix of
multiple resources.

-- 
Chad Austin
http://chadaustin.me