Subject: [quicwg/base-drafts] Boolean blocked streams setting (#3073)

From: Bence Béky <[email-masked]>
Date: Wed, 02 Oct 2019 06:56:22 -0700

# Proposal

Replace the numerical limit SETTINGS_QPACK_BLOCKED_STREAMS on number of blocked
streams by a Boolean setting: if 0, the encoder MUST not send a header block
with Required Insert Count exceeding Known Insert Count and the decoder MUST
treat the receipt of such a header block as connection error.  If 1, the number
of blocked streams is not directly limited.

Given the necessary implementation complexity especially on the encoder side, I
do not believe that a numerical limit is worth its purported advantages.

# Pros

Determining the number of blocked streams has considerable computational
complexity on the encoding side.  While it is true that the encoder already has
to keep track of all unacknowledged header blocks, it takes extra work to count
the blocked ones.

One approach is to keep a count of blocked streams that needs to be updated
every time a header acknowledgement, an insert count increment, or a stream
cancellation instruction is received.  Examples include [nghttp3](https://github.com/ngtcp2/nghttp3/blob/master/lib/nghttp3_qpack.h#L239) and
[Quinn](https://github.com/djc/quinn/blob/master/quinn-h3/src/qpack/dynamic.rs#L337).

Another approach is to count blocked streams every time a new header list is
encoded to determine if it is allowed to use unacknowledged references, by
iterating through all unacknowledged header blocks at least until the limit is
reached.  An example is [QUICHE](https://quiche.googlesource.com/quiche/+/master/quic/core/qpack/qpack_blocking_manager.cc#74) (the Google one, not the Cloudflare one).

Both approaches are considerably complex and thus error-prone to implement.

The situation is further complicated by two factors.  The first is that there
can be multiple unacknowledged header blocks on each stream (in case of 1xx
status code or trailing headers).  The second is that if there is already a
potentially blocking unacknowledged header block on a given stream, then
referencing unacknowledged entries is always allowed in subsequent header blocks
on the same stream regardless of the limit.

This is one of the most complex requirements necessary to implement a blocking
QPACK encoder, raising concerns of potential implementation bugs that could
result in incorrect behavior, or vulnerability to CPU attacks due to buggy or
suboptimal algorithms.  Replacing the numerical limit with a Boolean would allow
the encoder implementation to be much simplified.

# Cons

The desire for a limit on blocked streams is articulated at
https://github.com/quicwg/base-drafts/issues/1140#issuecomment-371677474, and is
further motivated by flow control considerations.

The number of streams with blocked header blocks a is already limited by the
number of bidirectional streams the peer can open, set by the decoder using the
initial_max_streams_bidi transport parameter and the MAX_STREAMS frame.  Since
the total memory footprint of the objects representing a stream (including
transport functionalities like buffering, ordering, flow control, and
retransmissions) are not expected to be dominated by the footprint of the QPACK
decoder and buffered header block (not considering the buffered data itself in
either case), there is little additional value in selectively limiting the
number of streams blocked on header block decoding given that the number of open
streams is already limited.

As for the issue of a blocked header block taking up a large amount of the flow
control window, SETTINGS_QPACK_BLOCKED_STREAMS only addresses this concern if
the stream level flow control window multiplied by the blocked stream limit is
less than the connection level flow control window.  However, a typical decoder
is expected to set the blocked stream limit to either zero or at least a dozen,
and connection level flow control is typically only a few times larger than the
stream level flow control for performance reasons.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 02 Oct 2019 12:59:26 -0700

This proposal reduces complexity at the cost of flexibility.  We cannot foresee all possible use cases for HTTP/3; this change to the draft may inadvertently make some usages impossible.  Keep in mind that HTTP is not just for the web.

The current version of the draft allows an implementation to avoid complexity by both not allowing its peer to use blocked streams nor to risk any blocked streams itself.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-537655053

---

From: ianswett <[email-masked]>
Date: Wed, 02 Oct 2019 16:03:11 -0700

This proposal also allows no blocked streams, since I believe that is useful and blocked streams do add implementation complexity, so this proposal should not increase implementation complexity for anyone and should reduce it for most implementers.

I'm not aware of a use case that needs a number of blocked streams larger than 0 and smaller than the max number of open streams allowed, but if there is one, I think we should detail it and ensure it can't be better solved by flow control or another mechanism.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-537717177

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 02 Oct 2019 16:36:03 -0700

I think I might be in favor of seeing the proposed change.

As @ianswett says, the flexibility that we would lose is very minor (i.e. the capability to limit the use of blocked streams to non-zero, but below MAX_STREAMS). I am not sure if there would be an HTTP application in which having such a requirement is important.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-537724588

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Wed, 02 Oct 2019 17:02:02 -0700

The only reason to set the limit under MAX_STREAMS I can think of is avoid too much of head of line blocking. If there is no evidence that numerical limit (fraction of MAX_STREAMS) brings better performance, then boolean thing would be better.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-537729621

---

From: afrind <[email-masked]>
Date: Thu, 03 Oct 2019 09:08:38 -0700

I didn't find the numeric setting significantly more complicated to implement than a boolean setting.  The [diff](https://github.com/facebook/proxygen/commit/09cb1304fb52149b7343f9f22d44ed3efa130840#diff-cde3cb3125e1e0b319d8264cb67c7de8) that converted it from a boolean to a number touched about 25 lines of code in the encoder.  I find that the bigger complexity comes from having the implementation allow both blocking and non-blocking.

proxygen uses the count, which is incremented when sending a header block with a potentially blocking reference and decremented on acks and cancellations.  I don't decrement the count on Insert Count Increment, and I count multiple potentially blocking blocks on the same stream individually.  Both of these make the implementation more conservative than necessary, but the code is pretty simple.

As for a use case, lately I've been working with our RPC over HTTP stack, which generally sets the stream limit in the 100k range.  There's more of a case to be made for keeping the QPACK blocking limit lower than the stream limit when you've got a bonkers stream limit.  When the stream limit is 100 or something else webish, 10 vs. 50 vs 100 doesn't seem super meaningful.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-538012823

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 08 Oct 2019 06:31:45 -0700

@tatsuhiro-t writes:
> If there is no evidence that numerical limit (fraction of MAX_STREAMS) brings better performance, then boolean thing would be better.

Absence of evidence is not the same as evidence of absence.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-539514680

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 17 Oct 2019 07:05:19 -0700

Historical reference:

@martinthomson first floats the idea to use a numerical limit for the maximum number of blocked headers in email thread titled _Head-of-Line Blocking Allows Attacks_ (on Compression Design Team) on December 11, 2017.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-543190608

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 17 Oct 2019 14:08:11 +0000 (UTC)

@afrind writes:

> As for a use case, lately I've been working with our RPC over HTTP stack, which generally sets the stream limit in the 100k range. There's more of a case to be made for keeping the QPACK blocking limit lower than the stream limit when you've got a bonkers stream limit.

This is a good example.  A decoder may want to allow *some* number of blocked headers without having to implement a data structure that can scale to 100K entries.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-543191863

---

From: ianswett <[email-masked]>
Date: Thu, 17 Oct 2019 09:46:55 -0700

You only need the datastructure to scale to the max number of open streams, which is commonly closer to 100, not 100k.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-543263157

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 17 Oct 2019 09:50:19 -0700

Well, it's 100K in Alan's case.  That's the "good example."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-543264686

---

From: afrind <[email-masked]>
Date: Thu, 17 Oct 2019 15:32:15 -0700

Discussed in Cupertino.  Close with no action.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#issuecomment-543388433

---

From: afrind <[email-masked]>
Date: Thu, 17 Oct 2019 15:32:17 -0700

Closed #3073.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3073#event-2722960604