Subject: [quicwg/base-drafts] Length-prefixes and flow control (#1432)

From: Martin Thomson <[email-masked]>
Date: Fri, 08 Jun 2018 12:36:22 +0000 (UTC)

HTTP/QUIC has a particular example of a pattern that seems likely to be usable in many other contexts.  A block of data is preceded by a length field.  The receiver of that block might read the length field then await the arrival of the entire block before processing the block.  During that time, the block is left unread so that the data can sit in the receive buffer of the transport.  This ensures that the data counts towards the flow control limits of the receiver.  This can prevent the sender from adding more messages that would only consume additional memory at the receiver.

In an extreme case, this leads to a deadlock.  The receiver is waiting for the end of a block.  The sender cannot send the remainder of the block because it does not have enough flow control credit.

This impasse doesn't naturally resolve in this case.  Worse, even if flow control might allow a single stream to make progress because the receiver ensures that it provides credit for the largest possible message or more, multiple concurrent streams could each consume a small part of the available flow control credit without allowing any single one to make progress.

Ultimately, there isn't an easy fix for this.  We could recommend a new input for prioritization: favour the sending of data for streams that are in the middle of sending a chunk, but that requires the transport be informed of message boundaries.  Relying on RST_STREAM to cancel streams until the logjam clears might work in some cases, but we have some examples already of streams that cannot be safely cancelled.  So this will always be a danger.  We gain some insight into what is going on with BLOCKED and friends, but ultimately this is just *hard*.

Not sure how much advice we can give here, or whether saying anything is even needed.

-- 
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/1432

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Jun 2018 05:47:46 -0700

How big is a block in this context? It can't be arbitrary because then strategy of waiting until the end before crediting flow won't work. If it isn't arbitrary, could flow be reserved for the reminder such that new streams can't be created if they cannot reserve enough flow?

-- 
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/1432#issuecomment-395750375

---

From: Martin Thomson <[email-masked]>
Date: Fri, 08 Jun 2018 06:07:06 -0700

This is the fun bit, I don't know.  We have frames in hq that are like this.  Some of those could be very large (think DATA), others small.  Some are naturally suited to streaming (DATA again), others not at all (HEADERS).  Smaller sizes change the odds, but they don't prevent the problem completely until the size hits zero.

I don't think that we're going to create a technical solution to this one.  I suspect that it will remain as one of the bits of the protocol that will be hard to get right.

-- 
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/1432#issuecomment-395755024

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Jun 2018 06:31:41 -0700

You could define a negotiable, but fixed, block size and require the application to drain after receiving that much, and prevent too many streams without additional block credits. This can still deadlock if the app won't buffer the block or it needs to create more streams, but it is not as arbitrary as random deadlocks.

-- 
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/1432#issuecomment-395761561

---

From: Mike Bishop <[email-masked]>
Date: Mon, 11 Jun 2018 09:59:26 -0700

Because the possible sizes on HQ frames are so very large, I tend to think of them as being "regions" in the stream.  Some are have to be received entire before you can do much useful with them (HEADERS, PRIORITY); others can reasonably be streamed (DATA).  HEADERS are the easiest place to deadlock, and one of the holdovers from HTTP/2 is an explicit communication of the largest header payload you're willing to process.

-- 
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/1432#issuecomment-396312823

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 11 Jun 2018 15:11:37 -0700

IMO, this is also an issue with TCP applications using _peek_ to see if a complete set of data is available in the receive buffer. The reason that it has not been considered as an issue is because TCP has expected applications to read data as they arrive, rather than using peek.

Considering that, could we recommend the same approach in the transport draft? Does doing so have a severe impact on HQ?

-- 
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/1432#issuecomment-396403735

---

From: Mike Bishop <[email-masked]>
Date: Mon, 11 Jun 2018 15:23:23 -0700

The issue is cross-stream dependencies.  If you craft a very large message which requires data from another stream to process it, if the application sucks up the large message anyway, then it will explode its memory.  The point of flow control is to limit this, by constraining the *unprocessed* data at any time.  We're using unread as a stand-in for unprocessed, and the corollary is that you shouldn't read something you know you won't be able to process.  The guidance in HQ is to read far enough to decide whether you can process the message, and if not, stop reading until you can.

-- 
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/1432#issuecomment-396406206

---

From: janaiyengar <[email-masked]>
Date: Mon, 11 Jun 2018 16:52:52 -0700

What @kazuho said. This is something that an application ought to be aware of when treating QUIC's stream buffers as storage. 

The problem is caused by something broader than the structure in the application data bytes -- an application could choose to not read data from the buffer until, for instance, the next consumer is ready for it.

In all these cases, I think it is not a good idea for an app to assume that the stream's buffers are a good place to store data, since that can interfere with network throughput and with resource allocation for other streams.

-- 
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/1432#issuecomment-396422059

---

From: krasic <[email-masked]>
Date: Mon, 11 Jun 2018 17:09:25 -0700

janaiyengar@  if an app isn't to use stream buffers for storage, what does it do in your example when the next consumer isn't keeping up?   if it drains all data from the stream, it may blow up its own memory, unless it implements its own flow control protocol at the app level?   that seems.. unsatisfactory.

-- 
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/1432#issuecomment-396424815

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 11 Jun 2018 17:34:13 -0700

Side note: the Huffman coding does have the EOS symbol.

-- 
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/1432#issuecomment-396428644

---

From: Martin Thomson <[email-masked]>
Date: Mon, 11 Jun 2018 17:36:48 -0700

Yeah, @krasic has it right.  The entire point of this thing is to apply back pressure - if you can't read, ensure that you don't get more of stuff you can't read that consumes more of the memory you don't have.

On the other hand, it is reasonable to say that applications (and application protocols) can't rely on QUIC providing them with any concrete amount of storage.   But we can't force people to read or we undermine the entire purpose of providing flow control.  (Here I'm assuming that reading releases flow control, but the key point is that you only release flow control once you are done with the octets, and for many of these cases, the point is that you can't be done with the octets until some external condition is met, or all the octets are in, or something like that.)

I don't think that this is something we have to provide a concrete solution for.  Flow control is fundamentally hard because it is about managing access to a finite resource and contention can occur, sometimes in sub-optimal ways.  What we can do is signpost the obvious pitfalls.  Like the case where you have 10 octets of connection flow control, 10 streams and 1 octet arrives for every stream, but you need to have >1 to make progress.

Using `peek()` is just an example, and not a necessary one.  The problem is that we're creating ways for an application to learn whether it wants to read octets before it reads them.  A length-prefixed encoding does that inherently, but it's just an example of a general class of things that a reader might use to decide to defer consumption of data.  That length-prefixes are also a great way to optimize processing of data means that we won't ever avoid using them, and nor can we avoid cases where atomic units take more than one octet to express.

If I get @dtikhonov's point, it seems like a suggestion that we might avoid a length-prefix, but I think that only makes reading harder, and doesn't avoid other styles of atomic processing over multi-octet fields.  It probably drives implementation complexity up, and it (unfortunately) uses a lot more bytes than a length prefix in many cases.

-- 
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/1432#issuecomment-396429043

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 11 Jun 2018 17:42:51 -0700

@martinthomson, mine wasn't a suggestion, but rather something to keep in mind as we weigh different options.  That is, there is a way to not use prefix length at all.  Your analysis is correct.  The biggest downside to me is that the EOS symbol is so long.

-- 
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/1432#issuecomment-396429945

---

From: janaiyengar <[email-masked]>
Date: Mon, 11 Jun 2018 18:01:32 -0700

@krasic Yes, you're right, and I wasn't being precise. It's not always a problem, but it can become one, based on how the application manages its data.

@martinthomson: I agree that we shouldn't be looking to provide a concrete solution for, but we can generally say something about the potential implications of consuming stream buffers for data that can be read. Beyond that, I think trying to capture this application design pattern -- worthy as it is of noting somewhere -- might be reaching too far for HTTP/QUIC or QUIC docs, since it applies to not just QUIC.

-- 
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/1432#issuecomment-396432664

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 11 Jun 2018 18:28:33 -0700

@MikeBishop Thank you for the clarification. I can understand the fact that we want to have a way to signal back-pressure when more than one stream is involved.

OTOH, as we all agree, using back-pressure has the danger of seeing a deadlock. It makes sense to have the implications being clarified in the documents.

And I would like to second @martinthomson's argument that the issue is not related to length-prefixes. Consider using HTTP/1 on QUIC. It makes perfect sense for an application to keep the response headers in the receive buffer until CR-LF-CR-LF arrives.

-- 
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/1432#issuecomment-396436567

---

From: Mike Bishop <[email-masked]>
Date: Mon, 11 Jun 2018 20:56:53 -0700

IIRC, HPACK EOS is so long because you never actually send all of it – if the Huffman-encoded string doesn’t end on a byte boundary (and it probably doesn’t), you put as many bits of the EOS symbol as needed to reach the byte boundary.  The whole thing should never appear on the wire; at most seven bits of it.  Of course, if you’re depending on recognizing it as it goes by, that requires parsing each symbol as it passes; the length prefix makes it much easier.

From: Dmitri Tikhonov <[email-masked]>
Sent: Monday, June 11, 2018 5:43 PM
To: quicwg/base-drafts <[email-masked]>
Cc: Mike Bishop <[email-masked]>; Comment <[email-masked]>
Subject: Re: [quicwg/base-drafts] Length-prefixes and flow control (#1432)

@martinthomson<https://github.com/martinthomson>, mine wasn't a suggestion, but rather something to keep in mind as we weigh different options. That is, there is a way to not use prefix length at all. Your analysis is correct. The biggest downside to me is that the EOS symbol is so long.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub<https://github.com/quicwg/base-drafts/issues/1432#issuecomment-396429945>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AEE2ha2hZGTKuCUGPvAxuog8eYQzTuTCks5t7w6KgaJpZM4UgCd3>.

-- 
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/1432#issuecomment-396458126