Subject: [quicwg/base-drafts] QCRAM encoding requires two passes (#1138)

From: afrind <[email-masked]>
Date: Fri, 23 Feb 2018 10:20:21 -0800

According to the spec "Base index is the cumulative number of entries added to the dynamic table prior to encoding the current block, including any entries already evicted."

However if you try to make a single pass encoder, you may end up with references to headers inserted while encoding the current block, which will be larger than the encoded base.  The hybrid representation would be negative, and HPACK cannot encode negative numbers.

```
encodedBase = baseIndex
writeBaseIndex(encodedBase, requestStream)
# save space for Depends
for h in headers:
  absIndex = getAbsoluteIndex(h)
  if absIndex == 0:
    if shouldIndex(h):
      absIndex = writeTableUpdate(h, controlStream)
    else:
      writeLiteral(h, requestStream)
      continue
  hybridIndex = encodedBase - absIndex
  # oops, absIndex may be larger than encodedBase
  writeIndexRef(hybridIndex, requestStream)
 ```

The only solution to implement the draft as specific is to make two passes, one that performs all necessary table inserts to get the right value of Base Index, and another to encode all the references relative to Base Index.

My QCRAM prototype did something bizarre to make this work in a single pass (https://goo.gl/nghK89) - using the maximum length of the dynamic table (MAX_HEADER_TABLE_SIZE / 32) to normalize negative numbers.  With the default maximum of 4KB, the first hybrid index after encodedBase is 128, then 127 and so on.

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

---

From: Mike Bishop <[email-masked]>
Date: Sun, 25 Feb 2018 13:55:00 +0000 (UTC)

While I agree it's a desirable property to add if we can, I also don't think this is debilitating.  In the worst case, an encoder which must stream could opt to double-encode -- a literal now, and an insert at its leisure if it thinks it will use the entry again.  There's a size penalty, but it's still compliant.

-- 
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/1138#issuecomment-368311213

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 17:40:44 +0000 (UTC)

Are folks ok with using literals if headers must be streamed?  Another approach is to extend the wire-format to efficiently encode negative Hybrid indexes (Depends would need this also).  

Single pass encoding that references newly indexed headers may also be challenging for implementations that don't use scatter-gather, since going back to write a variable length int at the beginning of a buffer is tricky.

The number of headers in a pass is likely small in a lot of common cases, and with some intermediate memory you can capture the required absolute indexes in the first pass.

-- 
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/1138#issuecomment-368584951

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 26 Feb 2018 13:14:46 -0800

> My QCRAM prototype did something bizarre to make this work in a single pass

I say if it works, it's not bizarre.

-- 
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/1138#issuecomment-368652806

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 26 Feb 2018 14:12:52 -0800

Upon reflection, I believe that the two-pass approach is untenable:
- Extra copy;
- Buffering;
- Delayed write.  (Imagine converting HTTP to QUIC and having to delay sending while all HTTP headers are read).

Using literals is a solution, but I don't like it, since compression suffers.

Note that it is not relevant which API is used -- streaming or scatter/gather.  A proxy may not have all HTTP headers. It wants to be able to send out what it has read ASAP, without having to wait to read all headers.

-- 
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/1138#issuecomment-368669536

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 23:33:55 +0000 (UTC)

If you want the proxy case to work without literals, then we would need to change the rules around BLOCKING and Depends, since the proxy cannot compute Depends correctly on the first header if it is allowed to insert and make references.  So far the only thing I can come up with is a flag/format which allows Depends to appear at the end of the block, and missing references are not treated as errors unless they turn out to be greater than Depends.  But this is ugly and has all sorts of problems.  At least some proxies will need the entire header block to make routing decisions, so I'm not sure how often the compression degradation will be a problem.

-- 
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/1138#issuecomment-368689861

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 26 Feb 2018 23:56:21 +0000 (UTC)

> If you want the proxy case to work without literals, then we would need to change the rules around BLOCKING and Depends, since the proxy cannot compute Depends correctly on the first header if it is allowed to insert and make references.

I don't understand this; but this may be because I need to re-read the draft.

As for the proxy -- I meant anything that translates HTTP to QUIC.  For example, imagine a QUIC frontend in front of an application server, for example.  What's the correct term -- gateway?  Why couldn't it write headers as soon as it received them?

Are you arguing that this scenario is something that is unlikely to be encountered and can therefore be ignored?

-- 
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/1138#issuecomment-368694561

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Feb 2018 16:01:40 -0800

Right now, there is either no blocking references, or two passes.  That is, concurrent table updates and inserts.   Well, references can still block - you don't have to wait for a full round trip - they just can't block based on the current set of header fields.

I think that this is fundamentally hard if you want blocking references to things that might be inserted as a result of the current set of header fields AND a single pass over the table.  If concurrent table inserts are being made, you have to rewrite any references that were made before the insert.  You also want a signal at the start of the header block about the expected table state so that you can use flow control for back pressure, which means that you have to hold the header block until you decide to stop making table updates.  Putting Depends at the end regresses functionality already agreed.

A gateway (yes that was correct) can write as it receives header fields, but it can't rely on any inserts that it makes concurrent with those writes.  That's all.  And I'm OK with that.

@dtikhonov, you were previously a champion of non-blocking.  Maybe you are OK with this too.

-- 
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/1138#issuecomment-368695707

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 27 Feb 2018 05:24:12 -0800

I agree that the case of concurrent table inserts is hard -- header blocks that are being encoded concurrently cannot reference _each other's_ entries. I am, indeed, OK with _that._

On the other hand, a header block should be able to (at least it seems that way to me!) reference entries that it itself adds.

I think it was mentioned before -- could we use a relative indexing scheme inside the header block? As in "reference 3rd entry added by this header block."

-- 
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/1138#issuecomment-368871677

---

From: afrind <[email-masked]>
Date: Tue, 27 Feb 2018 16:35:37 +0000 (UTC)

Header blocks on request streams do not contain any table modifications.  We're talking about inserts on the control stream generated while encoding a block on a request stream. 
 There's no guarantee in what order the inserts and references will arrive, hence Depends would need to be updated to reflect the highest entry referenced in the block.  

Older QCRAM drafts allowed the block itself to do the inserts, but we've stripped that complexity (resend on reset, out of order inserts, etc) out for now.

-- 
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/1138#issuecomment-368940054

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 10:22:56 -0800

Actually, we have this problem regardless of Depends.  The HEADERS frame is length-prefixed, so you have to have fully generated the output before you can send any of it.  We broke streaming compression when we removed CONTINUATION frames, except that I haven't heard of anyone actually using CONTINUATION that way.

-- 
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/1138#issuecomment-368976359

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 27 Feb 2018 18:50:08 +0000 (UTC)

> Header blocks on request streams do not contain any table modifications [...] referenced in the block.

Oh yes, how silly of me -- I forgot about that.

-- 
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/1138#issuecomment-368984761