Re: Question about HTTP 2.0 priority

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 <squid3@treenet.co.nz> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> 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)
> >
> > // 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.
>
> 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
> >
> >
> > On Wed, Oct 1, 2014 at 11:01 PM, Amos Jeffries
> > <squid3@treenet.co.nz> wrote:
> >
> > 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.
> >>>>
> >>>> 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?
> >>>>
> >
> > 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
> >
> >>
> >>
> >
> >
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.22 (MingW32)
>
> iQEcBAEBAgAGBQJULRW6AAoJELJo5wb/XPRjFMgH/3J0C4klXronIszBvvnCkYDU
> prIleZAqJfkMyM6/HVeBXf9+4oMkaxleZDmJYo8496Phh6BWbBboRsRW0+/pwrtK
> YGAnNg0NrHScxJRBDCZR75ENPEIPBdemKMPpBQwWsS7mFYrQR2GCeR+CXTCSeKma
> AyBaqMtwNfzHqBvz4cfNWqyE/+1wU12h9Wg1XndeTJo/Pi3R5BMp08LwnKjhJ/QY
> h1tw6f71xLZDU0yifj/J44nCq3KkCcMMSznRuB8VhkftuMgc5kOYQWr5r/d7N1V8
> NNmiDEm7a/j1y2+7JeUzDeB4MjAFXvA8Zf5x8obQQjQJI7UJ/yPujsJDK4FaviQ=
> =5k/P
> -----END PGP SIGNATURE-----
>



-- 
Chad Austin
http://chadaustin.me