Subject: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?

From: Tom Bergan <[email-masked]>
Date: Mon, 23 Jan 2017 16:39:42 -0800

I implemented the HTTP/2 response scheduler in Go's HTTP/2 server library.
I'm trying to understand the worst-case behavior of that scheduler. I
believe the worst-case behavior is necessarily O(n) operations per frame
sent on the wire, where n is the number of streams in the dependency tree.
Here is my rationale.

The key operation is finding the highest-priority stream that is ready to
send data.

If we don't care about weights, and we don't care about balancing bandwidth
usage across sibling nodes in a tree, then we can label each node with two
fields: "ready" (true if the stream is ready to send data) and "depth" (the
node's distance from the root of the tree). The scheduler must find a node
with the smallest depth over all nodes with ready = true. It is fairly
trivial to implement this in O(log n).

Now, let's introduce weights. The scheduler must allocate bandwidth to all
ready nodes, which happens recursively as follows:

  func allocateBandwidth(node, bw) {
    if (node.ready) {
      node.bandwidthShare = bw
      return
    }
    totalWeight = 0
    for (n in node.children) {
      if (n.ready || descendantIsReady(n)) {
        totalWeight += n.weight
      }
    }
    for (n in node.children) {
      if (n.ready || descendantIsReady(n)) {
        allocateBandwidth(n, bw * n.weight / totalWeight)
      }
    }
  }
  allocateBandwidth(root, 1.0)

I believe the above definition is a direct translation of RFC 7540 Section
5.3.2 (also see this thread
<https://lists.w3.org/Archives/Public/ietf-http-wg/2016OctDec/0601.html>,
which discussed bandwidth allocation). Given a complete bandwidth
allocation, the server can translate each node's bandwidthShare to a number
of tokens that are updated using a token bucket algorithm (or similar). The
scheduler would then pick the node with the most available tokens. The
scheduler looks something like:

  func scheduleNextFrame() {
    if (tree changed since last frame written) {
      allocateBandwidth(root, 1.0)
      assign tokens and build a priority queue containing all nodes with
allocated bandwidth
    }
    node = priorityQueue.head()
    node.consumeTokens() // consume up to frame size or flow-control limit
    priorityQueue.update(node)
    return node
  }

There are two steps in scheduleNextFrame. The first step updates the
bandwidth allocation if the tree changed since the last frame was written.
This is the most expensive step. I don't believe it's possible to implement
allocateBandwidth using fewer than O(n) worst-case steps. For example, if
the tree is mostly flat, meaning that most nodes are children of the same
node, then the loop to compute totalWeight is O(n). I believe Firefox
<http://bitsup.blogspot.com/2015/01/http2-dependency-priorities-in-firefox.html>
creates mostly-flat trees. Further, allocateBandwidth makes O(depth)
recursive steps, where "depth" is the maximum depth of the dependency tree.
If the tree is mostly-linear, then O(depth) becomes O(n). Chrome
<https://cs.chromium.org/chromium/src/net/spdy/http2_priority_dependencies.cc>
creates mostly-linear trees.

The overall runtime depends on how often the tree changes. If the tree
changes rarely, the scheduler is cheap. If the tree changes frequently, the
scheduler is worst-case O(n). A tree has "changed" if it changed shape
(nodes are added/moved/removed) or if any node's ready state has changed.
Both kinds of changes can happen often in practice, suggesting that the
overall scheduler is worst-case O(n). For example, consider a server that
sends small responses (one or two DATA frames per response) -- each stream
will be closed after one or two DATA frames, so on average, the tree will
change shape every few frames. Further, it's possible for ready states to
change more frequently than you might think. In Go's HTTP/2 implementation,
a stream does not become ready until the application handler calls Write to
buffer response data. After that buffered data is serialized on the wire,
the stream transitions to "not ready" because the scheduler cannot know
when the next Write call will happen. The stream will transition back to
"ready" during the next Write call. Each Write call typically buffers about
32KB of data. This is a "push" model, where the application handler
"pushes" data into the scheduler. I'm aware of one other HTTP/2 server that
works similarly. I suspect that frequent ready/not-ready transitions are
common to most HTTP/2 servers that use a "push" model. These servers will
be more susceptible to the O(n) worst case.

Questions:

1. Am I missing a clever implementation, or is it true that a faithful
HTTP/2 scheduler necessarily requires O(n) operations per frame sent on the
wire, in the worst case? I could not find much discussion of this question
after a quick search. H2O claims to implement an O(1) scheduler
<https://h2o.examp1e.net/configure/http2_directives.html>, however, the
code seems to be worst-case O(depth) or O(n) -- see here
<https://github.com/h2o/h2o/blob/9b70b61b0705ccce22a188e65363cdb506285ff1/lib/http2/scheduler.c#L326>
, here
<https://github.com/h2o/h2o/blob/9b70b61b0705ccce22a188e65363cdb506285ff1/lib/http2/scheduler.c#L342>,
and here
<https://github.com/h2o/h2o/blob/9b70b61b0705ccce22a188e65363cdb506285ff1/lib/http2/scheduler.c#L214>
.

2. If the above is correct, should I be concerned about the O(n) worst
case? I doubt that a typical web browsing session will trigger O(n)
behavior frequently, so I'm less concerned about the average case; I'm more
concerned about pathological cases or possible DoS vectors. Also, think
about cases where the "client" is actually a proxy server, meaning the
HTTP/2 connection may have many more concurrent streams than a typical
browsing session. For comparison, if you recall the predecessor to HTTP/2
(SPDY), a SPDY scheduler could be trivially implemented in O(1), since SPDY
used just eight priority buckets.

3. If I should be concerned about an O(n) worst case, are there any
suggested mitigations beyond setting SETTINGS_MAX_CONCURRENT_STREAMS to a
smallish constant?

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 24 Jan 2017 16:36:44 +0900

Regarding your question, I am unaware of a scheduler design that is
better than O(n) for both dequeuing (i.e. selecting the stream to
send) and for rescheduling a stream (especially a stream with many
decendants).

While designing the scheduler of H2O (you are right in pointing out
the fact that it is O(depth)), I came up with two options. One was to
retain the vertical (i.e. parent-children) relationship between the
streams. The other was to squash the vertical relationships to
generate a one-dimensional list of streams ordered by priority.

By taking the latter approach, you could create a scheduler that
dequeues at O(1). But such scheduler would need to perform O(N)
operation when receiving a priority frame or a stream-level window
update (in this case N is number of direct and indirect decendants of
the reprioritized stream).

Considering this, we chose to implement the scheduler of H2O as O(1)
weight-wise, and O(n) depth-wise, but that the constant for O(n) would
be small enough so that it cannot be used an attack vector.

2017-01-24 9:39 GMT+09:00 Tom Bergan <[email-masked]>:
> 5.3.2 (also see this thread, which discussed bandwidth allocation). Given a
> complete bandwidth allocation, the server can translate each node's
> bandwidthShare to a number of tokens that are updated using a token bucket
> algorithm (or similar). The scheduler would then pick the node with the most
> available tokens. The scheduler looks something like:
>
> If the tree is mostly-linear, then O(depth) becomes O(n). Chrome creates
> mostly-linear trees.
>
> the stream transitions to "not ready" because the scheduler cannot know when
> the next Write call will happen. The stream will transition back to "ready"
> during the next Write call. Each Write call typically buffers about 32KB of
> data. This is a "push" model, where the application handler "pushes" data
> into the scheduler. I'm aware of one other HTTP/2 server that works
> similarly. I suspect that frequent ready/not-ready transitions are common to
> most HTTP/2 servers that use a "push" model. These servers will be more
> susceptible to the O(n) worst case.
>
> Questions:
>
> after a quick search. H2O claims to implement an O(1) scheduler, however,
> the code seems to be worst-case O(depth) or O(n) -- see here, here, and
> here.
>
> 2. If the above is correct, should I be concerned about the O(n) worst case?
> I doubt that a typical web browsing session will trigger O(n) behavior
> frequently, so I'm less concerned about the average case; I'm more concerned
> about pathological cases or possible DoS vectors. Also, think about cases
> where the "client" is actually a proxy server, meaning the HTTP/2 connection
> may have many more concurrent streams than a typical browsing session. For
> comparison, if you recall the predecessor to HTTP/2 (SPDY), a SPDY scheduler
> could be trivially implemented in O(1), since SPDY used just eight priority
> buckets.
>

-- 
Kazuho Oku

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Tue, 24 Jan 2017 16:53:56 +0900 (JST)

Hi Tom,

Probably, this material would help you:

http://www.mew.org/~kazu/material/2015-http2-priority2.pdf
http://www.mew.org/~kazu/doc/paper/http2-haskell-2016.pdf

--Kazu

---

From: Stefan Eissing <[email-masked]>
Date: Tue, 24 Jan 2017 09:26:47 +0100

The very same problem exists for stream processing in order to generate response data.

> Am 24.01.2017 um 08:53 schrieb Kazu Yamamoto (山本和彦) <[email-masked]>:
> 
> Hi Tom,
>

---

From: Tom Bergan <[email-masked]>
Date: Tue, 24 Jan 2017 14:22:51 -0800

Thanks for the feedback. Sounds like the worst-case time really is O(n).

> kazuhooku@
> the constant for O(n) would be small enough so that it cannot be used an
attack vector

Don't you need to ensure that n is small, otherwise even O(n) with a small
constant factor can lead to degraded performance? e.g.,
if SETTINGS_MAX_CONCURRENT_STREAMS = 20,000, I may end up computing a sum
of 20,000 numbers every few frames, which is not terribly slow, but not
terribly fast either.

> kazu@

Thanks. IIUC, the algorithms described in both links are still at least
O(depth), which can be O(n) for dependency trees generated by certain
clients such as Chrome.

> stefan.eissing@

What did you mean by "stream processing"?

On Tue, Jan 24, 2017 at 12:26 AM, Stefan Eissing <
[email-masked]> wrote:

> case?

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 25 Jan 2017 07:55:10 +0900 (JST)

Hi Tom,

> O(depth), which can be O(n) for dependency trees generated by certain

Yes. Your understanding is correct.

If a browser creates a list-like tree, I think it is misuse of priority.
And servers should limit the depth of trees.

--Kazu

---

From: Tom Bergan <[email-masked]>
Date: Tue, 24 Jan 2017 15:09:47 -0800

> And servers should limit the depth of trees.

Why is that a misuse of priority? It seems entirely reasonable for a client
to specify a mostly-linear order. There is a very good reason for this:
inside HTML pages, CSS links and synchronous scripts must be evaluated in
the order they appear in the HTML file. This implies that the server should
send those resources in a linear order. This is exactly the rationale
behind Chrome using mostly-linear orders. (This is not to say that
mostly-linear orders are not occasionally problematic -- they are
<https://bugs.chromium.org/p/chromium/issues/detail?id=651538#c1> -- but
there are good reasons to linear orders at least some of the time.)

(sorry for the duplicate message, replied from the wrong address)

---

From: Patrick McManus <[email-masked]>
Date: Wed, 25 Jan 2017 08:20:53 +0900

media frames are another really good use case for linear orders. These, and
Tom's cases, were all cited as use cases during standardization.

I think the discussion about how to process that organization is germane
and interesting (chair hat!), and we should do that cognizant that this is
an expected use of the priority feature.

On Wed, Jan 25, 2017 at 8:09 AM, Tom Bergan <[email-masked]> wrote:

> Why is that a misuse of priority? It seems entirely reasonable for a
> client to specify a mostly-linear order. There is a very good reason for
> this: inside HTML pages, CSS links and synchronous scripts must be
> evaluated in the order they appear in the HTML file. This implies that the
> server should send those resources in a linear order. This is exactly the
> rationale behind Chrome using mostly-linear orders. (This is not to say
> that mostly-linear orders are not occasionally problematic -- they are

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 25 Jan 2017 10:59:58 +0900

2017-01-25 7:22 GMT+09:00 Tom Bergan <[email-masked]>:
> constant factor can lead to degraded performance? e.g., if
> SETTINGS_MAX_CONCURRENT_STREAMS = 20,000, I may end up computing a sum of
> 20,000 numbers every few frames, which is not terribly slow, but not
> terribly fast either.

I agree. For H2O, the maximum is hard-coded to 100 partly to avoid
that kind of attack.

> On Tue, Jan 24, 2017 at 12:26 AM, Stefan Eissing
> <[email-masked]> wrote:
>>

-- 
Kazuho Oku

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Wed, 25 Jan 2017 11:01:26 +0900

Hi,

> of 20,000 numbers every few frames, which is not terribly slow, but not
​If large n is concern, server can limit SETTINGS_MAX_CONCURRENT_STREAMS to
the reasonable number.  Usually we use 100, and it is pretty fast.

Best regards,
Tatsuhiro Tsujikawa​

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 25 Jan 2017 13:03:58 +0900 (JST)

Hi Tom,

> there are good reasons to linear orders at least some of the time.)

Thank you for your explanation.
I did not know this use case.
So, I would like to withdraw my previous word "misuse".

--Kazu

---

From: Cory Benfield <[email-masked]>
Date: Wed, 25 Jan 2017 08:32:27 +0000

> On 25 Jan 2017, at 02:01, Tatsuhiro Tsujikawa <[email-masked]> wrote:
> 
> ​If large n is concern, server can limit SETTINGS_MAX_CONCURRENT_STREAMS to the reasonable number.  Usually we use 100, and it is pretty fast.=

The various Python HTTP/2 implementations also set SETTINGS_MAX_CONCURRENT_STREAMS to 100.

Cory

---

From: Stefan Eissing <[email-masked]>
Date: Wed, 25 Jan 2017 10:14:12 +0100

> Am 24.01.2017 um 23:22 schrieb Tom Bergan <[email-masked]>:
> 
> > stefan.eissing@

A server has limited resources. In order to determine which stream's response gets calculated first priorities and weight need also apply.

Stefan Eissing

<green/>bytes GmbH
Hafenstrasse 16
48155 Münster
www.greenbytes.de

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 26 Jan 2017 22:51:18 +1300

> Tom's cases, were all cited as use cases during standardization.

Gateways translating for HTTP/1 clients also need their responses to be
as linear as possible to match the 1.1 sequence. Otherwise they will be
forced to either spend RAM caching response data with a blocked
pipeline, or forgoe the h2 multiplexing and PUSH benefits.