Re: Comments on draft-chan-http2-stream-dependencies-00

On 2014-01-16 06:43, Martin Thomson wrote:
> On 14 January 2014 17:22, William Chan (ι™ˆζ™Ίζ˜Œ) wrote:
<snip>
>>> I don't think that you need the ORDERED bit.  It seems to me like you
>>> could do "A <- B -- C" just as easily by having C reference A.  The
>>> single chain of antecedent-dependent nodes is something an
>>> implementation could easily do, even if this were the case.  I don't
>>> see the advantage to having ORDERED in the protocol.
>> 
>> Having C reference A brings us back to dependency trees instead of
>> lists.
> 
> Not really.  If you send A <- B followed by A <- C, then that
> collapses to A <- B -- C.  You can do that based on the order that the
> priorities are set (or by stream identifier numbers, but that would be
> harder to work out).
> 
<snip>

>> Once you open it up to a possible tree, it gets more complicated. In
>> terms of the complexity tradeoff, I think adding a bit for order is
>> simpler than having to have peers/siblings.
> 
> It's not really a tree in the sense that you think.  It's a list of
> lists.  The exact same structure you describe in the draft in fact.
> See:
> 
> A
> ^
> B -- C
> ^
> D -- E
> 
> The only difference is that in the draft you make statements about
> what implementations do with their internal data structures, which
> isn't really necessary.
> 

I have been wondering exactly how best such a list tree would be 
implemented to prevent some objects at the leaf ends being starved or 
stateful interactions between the implementations. In particular how to 
avoid/reduce problems with stateless or stream-ID mapping 
intermediaries.

In short: I am completely against adding weightings and complex 
relationship indicators. Even though the feature is OPTIONAL, jumping 
through such hoops is completely unrealistic for middleware. Here is a 
simple off-the-cuff implementation example for the simplest A<-B, A<-C, 
C<-D type of dependency tree/list.

If each stream is assigned a single depends-on parent (which can be 
changed dynamically with PRIORITY). It could be implemented as a single 
list in stream-ID order with but one property indicating the depended-on 
stream. Scanning over the list for scheduling frame writes could 
recursively try to write available frames for the depended-on stream 
before writing the current stream frames, then moving on to the next 
listed. Garbage-collection would simply be removing depends-on 
information for already completed streams, effectively raising the child 
streams all up a level of priority.

Simple, fast and quite memory efficient. There are also a few very 
useful emergent properties from this:

1) Default priority (no dependencies or implementations ignoring this 
mechanism) would be to deliver frames for the lowest stream-ID first.
  a) HTTP/1.1 ordering maps cleanly to the 2.0 default priority for 
delivery.
  b) hops without the feature implemented mostly act as if default 
priority were being used.

2) all streams get at least one shot at delivering a frame on the 
connection each cycle.
  a) preventing any hanging completely.
  b) allowing implementations to limit how much they send (ie DATA) on 
one write, secure in the guarantee that high priority stream will get 
more (and earlier) chances to write than others relative to how many 
streams depend on it.

3) groups of requests depending on each other (ie from the same client) 
are served relatively close to each other,
  a) increasing the likelihood of shared headers compressing the traffic 
size, and
  b) allowing any middleware caches to make better use of temporal 
locality for relatedness of resources.

4) priority delivery is completely up to the sender,
  a) no need for any receiver implementation complexity,
  b) no END_STREAM_ACK management

5) priority of frames self-corrects to a certain degree after relaying 
over a hop without the mechanism implemented.

6) any buffered streams awaiting write or being processed are 
immediately affected by the PRIORITY changes of all other streams.
  a) no need for middleware complexity juggling relationships

7) robust error handling with broken middleware improperly adjusting 
PRIORITY frame stream-IDs when it changes transferred stream-IDs.
  * The feature otherwise assumes that stream-IDs are identical 
end-to-end (a false assumption with middleware).

8) a streams weight is a product of how many other streams are depending 
on it.
  a) depended-on streams are likely first in the list, so naturally will 
get more frames delivered without weightings or explicit rate-limiting 
later streams.
  b) no need for middleware complexity juggling and balancing weights 
from N servers with M clients.
  c) no need for server complexity determining relative weight importance 
to clients.
  d) no risk of middleware being tricked into turning a small received 
PRIORITY change into a massive set of emitted PRIORITY side-effect 
changes (or worse given weightings, these could trigger PRIORITY changes 
to other client<->server traffic transactions).

Amos

Received on Wednesday, 15 January 2014 22:48:51 UTC