Subject: [quicwg/base-drafts] WIP: Reorganize QPACK (#1852)

From: afrind <[email-masked]>
Date: Thu, 11 Oct 2018 17:11:11 +0000 (UTC)

Added a "Compression Process Overview" section near the top, with a high level description of how to compress/decompress.  This section now encompasses a lot of what used to be "Encoding Strategies".

In the places where I added new text, I temporarily added HTML comments to indicicate so it can get a bit more detailed review.

I also deleted a few sentences/paragraphs/sections that I found to be redundant:

- Preventing Eviction Races
- "An encoder also respects..."
- "For header blocks encoded in..."
- Single Pass Encoding
- "All table updates occur on..."
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1852

-- Commit Summary --

  * WIP: Reorganize QPACK

-- File Changes --

    M draft-ietf-quic-qpack.md (729)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1852.patch
https://github.com/quicwg/base-drafts/pull/1852.diff

-- 
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/pull/1852

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Oct 2018 16:00:36 -0700

martinthomson commented on this pull request.

This is an improvement (feel free to defer some of the comments, I got a little carried away).

> +Encoder:
+
+: An implementation which transforms a header list into a header block.
+
+Decoder:
+
+: An implementation which transforms a header block into a header list.
+
+<!-- new definitions -->
+Absolute Index:
+
+: A unique index for each entry in the dynamic table.
+
+Base Index:
+
+: An absolute index in a header block from which relative indices are made

Period.

 Like HPACK, QPACK uses two tables for associating header fields to indices.  The
 static table (see {{table-static}}) is predefined and contains common header
 fields (some of them with an empty value).  The dynamic table (see
 {{table-dynamic}}) is built up over the course of the connection and can be used
 by the encoder to index header fields repeated in the encoded header lists.
 
+- The encoder uses a unidirectional stream to modify the state of the dynamic
+table without generating header fields to any particular request.
+
+- HEADERS and PUSH_PROMISE frames on request and push streams reference the
+table state without modifying it.
+
+- The decoder sends feedback to the encoder on a unidirectional stream that
+enables the encoder to manage dynamic table state.
+
+## Encoder
+
+<!-- new -->
+An encoder encodes a header list by emitting either an indexed or a literal
+representation of each header field in the list.  Index references to the static

s/of/for

> +- The encoder uses a unidirectional stream to modify the state of the dynamic
+table without generating header fields to any particular request.
+
+- HEADERS and PUSH_PROMISE frames on request and push streams reference the
+table state without modifying it.
+
+- The decoder sends feedback to the encoder on a unidirectional stream that
+enables the encoder to manage dynamic table state.
+
+## Encoder
+
+<!-- new -->
+An encoder encodes a header list by emitting either an indexed or a literal
+representation of each header field in the list.  Index references to the static
+table and literals do not require any dynamic state and never risk head-of-line
+blocking.  References to the dynamic table do risk head-of-line blocking if the

s/do//

> +
+An encoder MUST ensure that a header block which references a dynamic table
+entry is not received by the decoder after the referenced entry has already been
+evicted.  To enable this, the encoder needs to track outstanding
+(unacknowledged) header blocks that reference the dynamic table.
+
+### Blocked Dynamic Table Insertions {#blocked-insertion}
+
+An encoder MUST NOT insert an entry into the dynamic table (or duplicate an
+existing entry) if doing so would evict an entry with unacknowledged references.
+For header blocks that might rely on the newly added entry, the encoder can use
+a literal representation and maybe insert the entry later.
+
+To ensure that the encoder is not prevented from adding new entries, the encoder
+can avoid referencing entries that will be evicted soonest.  Rather than
+reference such an entry, the encoder SHOULD emit a Duplicate instruction (see

s/SHOULD/can - it's not a normative requiement

> +To ensure that the encoder is not prevented from adding new entries, the encoder
+can avoid referencing entries that will be evicted soonest.  Rather than
+reference such an entry, the encoder SHOULD emit a Duplicate instruction (see
+{{duplicate}}), and reference the duplicate instead.
+
+Determining which entries are too close to eviction to reference is an encoder
+preference.  One heuristic is to target a fixed amount of available space in the
+dynamic table: either unused space or space that can be reclaimed by evicting
+unreferenced entries.  To achieve this, the encoder can maintain a draining
+index, which is the smallest absolute index in the dynamic table that it will
+emit a reference for.  As new entries are inserted, the encoder increases the
+draining index to maintain the section of the table that it will not
+reference.  Draining entries - entries with an absolute index lower than the
+draining index - will not accumulate new references.  The number of
+unacknowledged references to draining entries will eventually become zero,
+making the entry available for eviction.

for the last two sentences, suggest: "If the encoder does not create new references to entries with an absolute index lower than the draining index, the number of unacknowledged references to those entries will eventually become zero, allowing the entry to be evicted."  That loses the "draining entries" thing, but I would then change the picture to say "Unreferenceable Entries".

> + Dropping    Draining Index               Base Index /
+  Point                                   Insertion Point
+~~~~~~~~~~
+{:#fig-draining-index title="Draining Dynamic Table Entries"}
+
+
+### Avoiding Head-of-Line Blocking {#overview-hol-avoidance}
+
+Because QUIC does not guarantee order between data on different streams, a
+header block might reference an entry in the dynamic table that has not yet been
+received.
+
+Each header block contains a Largest Reference {{header-prefix}} which
+identifies the table state necessary for decoding. If the greatest absolute
+index in the dynamic table is less than the value of the Largest Reference, the
+stream is considered "blocked."  While blocked, header field data should remain

s/should/can - though we're hiding a footgun here (maybe a separate discussion)

> +identifies the table state necessary for decoding. If the greatest absolute
+index in the dynamic table is less than the value of the Largest Reference, the
+stream is considered "blocked."  While blocked, header field data should remain
+in the blocked stream's flow control window.  When the Largest Reference is
+zero, the frame contains no references to the dynamic table and can always be
+processed immediately. A stream becomes unblocked when the greatest absolute
+index in the dynamic table becomes greater than or equal to the Largest
+Reference for all header blocks the decoder has started reading from the stream.
+If a decoder encounters a header block where the actual largest reference is not
+equal to the Largest Reference declared in the prefix, it MAY treat this as a
+stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+
+A decoder can permit the possibility of blocked streams by setting
+SETTINGS_QPACK_BLOCKED_STREAMS to a non-zero value (see {{configuration}}).
+This setting specifies an upper bound on the number of streams which can be
+blocked.

Single sentence: "The SETTINGS_QPACK_BLOCKED_STREAMS setting (see {{configuration}}) specifies an upper bound on the number..."

> +blocked.
+
+An encoder can decide whether to risk having a stream become blocked. If
+permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS, compression efficiency
+can be improved by referencing dynamic table entries that are still in transit,
+but if there is loss or reordering the stream can become blocked at the decoder.
+An encoder avoids the risk of blocking by only referencing dynamic table entries
+which have been acknowledged, but this means using literals. Since literals make
+the header block larger, this can result in the encoder becoming blocked on
+congestion or flow control limits.
+
+An encoder MUST limit the number of streams which could become blocked to the
+value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. Note that the decoder
+might not actually become blocked on every stream which risks becoming blocked.
+If the decoder encounters more blocked streams than it promised to support, it
+MUST treat this as a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.

Move this to the one-sentence paragraph above.

> +When blocking references are permitted, the encoder uses acknowledgement of
+header blocks to identify the Largest Known Received index, as described in
+{{header-acknowledgement}}.
+
+To acknowledge dynamic table entries which are not referenced by header blocks,
+for example because the encoder or the decoder have chosen not to risk blocked
+streams, the decoder sends a Table State Synchronize instruction (see
+{{table-state-synchronize}}).
+
+
+### Speculative table updates {#speculative-updates}
+
+Implementations can *speculatively* send instructions on the encoder stream
+which are not needed for any current HTTP request or response.  Such headers
+could be used strategically to improve performance.  For instance, the encoder
+might decide to *refresh* by sending Duplicate representations for popular

I don't think that the emphasis here is going to produce good results.

> +Implementations can *speculatively* send instructions on the encoder stream
+which are not needed for any current HTTP request or response.  Such headers
+could be used strategically to improve performance.  For instance, the encoder
+might decide to *refresh* by sending Duplicate representations for popular
+header fields ({{duplicate}}), ensuring they have small indices and hence
+minimal size on the wire.
+
+## Decoder
+
+<!-- new -->
+
+Like in HPACK, the decoder processes header blocks and emits the corresponding
+header lists. It also processes dynamic table modifications from instructions on
+the encoder stream.
+
+A decoder MUST must emit header fields in the order their representations appear

MUST must MuST mUsT

> +
+
+### Speculative table updates {#speculative-updates}
+
+Implementations can *speculatively* send instructions on the encoder stream
+which are not needed for any current HTTP request or response.  Such headers
+could be used strategically to improve performance.  For instance, the encoder
+might decide to *refresh* by sending Duplicate representations for popular
+header fields ({{duplicate}}), ensuring they have small indices and hence
+minimal size on the wire.
+
+## Decoder
+
+<!-- new -->
+
+Like in HPACK, the decoder processes header blocks and emits the corresponding

Maybe make a note here or above that the design of QPACK is such that the encoder takes on all complex tasks, where the decoder is simple.

> -
-# Wire Format
-
-QPACK instructions occur in three locations, each of which uses a separate
-instruction space:
-
- - The encoder stream is a unidirectional stream of type `0x48` (ASCII 'H')
-   which carries table updates from encoder to decoder. Instructions on this
-   stream modify the dynamic table state without generating output to any
-   particular request.
+~~~~~ drawing
+             Base Index
+                 |
+                 V
+    +---+-----+-----+-----+-----+
+    | n | n-1 | n-2 | ... | d+1 |  Absolute Index

This could be clearer, I think.

The 2 here (in n-2) is confusing.  What you really want is a diagram that shows the different values in a block.

Largest reference will be the largest value, that's your baseline.
Base offset is taken relative to the largest reference.  Here it's 2, which is confusing.  We need to show examples of where base allows for post-base references and one where it doesn't.

Including entries that have been evicted in this diagram confuses the matter.  It would be better to rely on text or to show that new entries appear on the left and old entries are evicted on the right.

Does this help?

```
Indexing Overview

    <- Absolute Indices (increase to left)
          L = Largest Reference
          B = Base Reference

       Newer                     Older
    <- Entries                 Entries ->
       Added                   Evicted

Indexing (simple case, B == L):
       ---+---+---+---+---+---+---+---+---
       ...| L |L-1|L-2|L-3|L-4|L-5|L-6|...
       ---+---+---+---+---+---+---+---+---
Index:      0   1   2   3   4   5   6  ...

Indexing (B > L):
       ---+---+---+---+---+---+---+---+---
       ...| B |B-1|...| L |L-1|L-2|L-3|...
       ---+---+---+---+---+---+---+---+---
Index:      x   x   x   D  D+1 D+2 D+3 ...
            x = invalid index
                        D = B - L

Post-Base Indexing (where B < L)
       ---+---+---+---+---+---+---+---+---
       ...| L |...|B+2|B+1| B |B-1|B-2|...
       ---+---+---+---+---+---+---+---+---
Index:                      0   1   2  ...
Post-Base:  P  ...  1   0
            P = L - B - 1
```

> +## Stream Types
+
+QPACK instructions occur in three locations, each of which uses a separate
+instruction space:
+
+ - The encoder stream is a unidirectional stream of type `0x48` (ASCII 'H')
+   which carries table updates from encoder to decoder.
+
+ - The decoder stream is a unidirectional stream of type `0x68` (ASCII 'h')
+   which carries acknowledgements of table modifications and header processing
+   from decoder to encoder.
+
+ - Finally, the contents of HEADERS and PUSH_PROMISE frames on request streams
+   and push streams reference the QPACK table state.
+
+<!-- s/exactly/no more than/  ? -->

Yeah, let's leave that question for the moment.

> @@ -618,6 +715,7 @@ An encoder that receives an Insert Count equal to zero or one that increases
 Largest Known Received beyond what the encoder has sent MUST treat this as a
 connection error of type `HTTP_QPACK_DECODER_STREAM_ERROR`.
 
+<!-- move? -->

Yeah, I think that this belongs in the decoder section.

> @@ -633,7 +731,8 @@ After processing a header block whose declared Largest Reference is not zero,
 the decoder emits a Header Acknowledgement instruction on the decoder stream.
 The instruction begins with the '1' one-bit pattern and includes the request
 stream's stream ID, encoded as a 7-bit prefix integer.  It is used by the
-peer's QPACK encoder to know when it is safe to evict an entry.
+peer's QPACK encoder to know when it is safe to evict an entry, and possibly

s/QPACK// ?

> @@ -633,7 +731,8 @@ After processing a header block whose declared Largest Reference is not zero,
 the decoder emits a Header Acknowledgement instruction on the decoder stream.
 The instruction begins with the '1' one-bit pattern and includes the request
 stream's stream ID, encoded as a 7-bit prefix integer.  It is used by the
-peer's QPACK encoder to know when it is safe to evict an entry.
+peer's QPACK encoder to know when it is safe to evict an entry, and possibly

...and remove the possessive.

-- 
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/pull/1852#pullrequestreview-164035903

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 11 Oct 2018 18:12:50 -0700

dtikhonov requested changes on this pull request.

-# Header Tables
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
+"SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this
+document are to be interpreted as described in BCP 14 {{!RFC2119}} {{!RFC8174}}
+when, and only when, they appear in all capitals, as shown here.
+
+Definitions of terms that are used in this document:
+
+Header field:
+
+: A name-value pair sent as part of an HTTP message.
+
+Header list:
+
+: The ordered collection of header fields associated with an HTTP message.  A

Why _a_ name-value pair, but _the_ ordered collection?  For comparison [RFC7541](https://tools.ietf.org/html/rfc7541#section-1.3) has "_an_ ordered collection."

> +## Notational Conventions
+
+Diagrams use the format described in Section 3.1 of {{?RFC2360}}, with the
+following additional conventions:
+
+x (A)
+: Indicates that x is A bits long
+
+x (A+)
+: Indicates that x uses the prefixed integer encoding defined in Section 5.1 of
+  [RFC7541], beginning with an A-bit prefix.
+
+x ...
+: Indicates that x is variable-length and extends to the end of the region.
+
+# Compression Process Overview

> to index header fields _repeated_ in the encoded header lists

A header field does not need to be repeated in order to be indexed and referenced.

What does it mean to generate header fields _to_ a request?

Which enables the encoder to manage state: decoder feedback or the unidirectional stream?

> An encoder _encodes_ ...

A better wording could probably be found.  For example:

- An encoder compresses a header list... ; or
- An encoder creates a compressed representation of a header list.

In the previous sentences we have "_index_ references to the static table," but here we have simply "references to the dynamic table."  We can drop the "index" to have "references to the static table."

Does "literals" here mean "literal values" or "index references to ... literals?"  If it is the former, I suggest rephrasing this to

> Literal values and references to the static table ...

to avoid ambiguity.

+QPACK preserves the ordering of header fields within each header list.  An
+encoder MUST emit header field representations in the order they appear in the
+input header list.
+
+### Reference Tracking
+
+An encoder MUST ensure that a header block which references a dynamic table
+entry is not received by the decoder after the referenced entry has already been
+evicted.  To enable this, the encoder needs to track outstanding
+(unacknowledged) header blocks that reference the dynamic table.
+
+### Blocked Dynamic Table Insertions {#blocked-insertion}
+
+An encoder MUST NOT insert an entry into the dynamic table (or duplicate an
+existing entry) if doing so would evict an entry with unacknowledged references.

Consider simplifying this to

> An encoder MUST NOT evict an entry with unacknowledged references.

This is shorter and clearer.  Also, changing table size can also evict an entry.

> +### Reference Tracking
+

Only one entry can be evicted _soonest_.  I'd drop the "soonest" in favor of "entries that are close to being evicted" or the like.

Use two dashes for the long dash.

Number agreement: "draining entries" vs "the entry."

+
+An encoder MUST limit the number of streams which could become blocked to the
+value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. Note that the decoder
+might not actually become blocked on every stream which risks becoming blocked.
+If the decoder encounters more blocked streams than it promised to support, it
+MUST treat this as a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+
+### Largest Known Received
+
+For the encoder to identify which dynamic table entries can be safely used
+without a stream becoming blocked, the encoder tracks the absolute index of the
+decoder's Largest Known Received entry.
+
+When blocking references are permitted, the encoder uses acknowledgement of
+header blocks to identify the Largest Known Received index, as described in

s/acknowledgement of header blocks/header block acknowledgements/

Why _a_ decoder here, but _the_ decoder in the previous paragraph?  The draft uses both "a decoder" and "the decoder;" I cannot detect a method to it.

> @@ -123,6 +342,10 @@ addressed.
 The static table consists of a predefined static list of header fields, each of
 which has a fixed index over time.  Its entries are defined in {{static-table}}.
 
+<!--new -->
+Note the QPACK static table is indexed from 0, whereas the HPACK static table
+was indexed from 1.

Use present tense: HPACK static table _is_ indexed.

-- 
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/pull/1852#pullrequestreview-164012122

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 12 Oct 2018 13:55:27 -0700

dtikhonov commented on this pull request.

> +: The compressed representation of a header list.
+
+Encoder:
+

If we list the Base Index here, we should also have the Largest Reference.

-- 
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/pull/1852#pullrequestreview-164405769

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 12 Oct 2018 14:05:14 -0700

> +   +----------+---------------------------------+--------+
+   ^          ^                                 ^
+   |          |                                 |

Add parentheses around `{{header-prefix}}`

-- 
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/pull/1852#pullrequestreview-164408864

---

From: Mike Bishop <[email-masked]>
Date: Fri, 12 Oct 2018 16:40:54 -0700

MikeBishop commented on this pull request.

Comments so far; I find myself adding +1s to a lot of existing comments.  :-)

+
+Decoder:
+
+QPACK is a name, not an acronym.

🤣

Perhaps "without emitting header fields associated with any particular request"?

This bulleted list feels like it comes out of nowhere.  Perhaps this could be turned into something more narrative, or at least introduced?

I'm okay with the existing wording; these are representations of the headers.  But emitting one for one is also a valid way to construct it.

Given that this doesn't always result in an improvement, perhaps "can often" or "can sometimes"?

Similarly, "this could mean"

"In order to identify...."

I feel like this section doesn't qualify to be a separate section.  This is inherent in the fact that table updates and encoding a header set are separable operations.  I'd perhaps condense this to a single sentence and mention it in 2.1?

> Updates to the dynamic table can be performed independent of any particular header set being compressed.  Encoders MAY insert entries speculatively.

Title needs to be capitalized if retained.

+

More colloquial than I'd choose; "As in HPACK..."?

> +A decoder MUST must emit header fields in the order their representations appear
+in the input header block.
+
+
+### State Synchronization
+
+The decoder stream ({{decoder-stream}}) signals key events at the decoder that
+permit the encoder to track the decoder's state.  These events are:
+
+- Complete processing of a header block
+- Abandonment of a stream which might have remaining header blocks
+- Receipt of new dynamic table entries
+
+Regardless of whether a header block contained blocking references, the
+knowledge that it has been processed permits the encoder to evict
+entries to which no unacknowledged references remain; see {{blocked-insertion}}.

Now that we only acknowledge blocks with dynamic references, perhaps this should read "Knowledge that a header block which contains references to the dynamic table has been processed permits [...], regardless of whether those references were potentially blocking."

-- 
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/pull/1852#pullrequestreview-164374242

---

From: Mike Bishop <[email-masked]>
Date: Mon, 15 Oct 2018 14:47:36 -0700

-- 
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/pull/1852#pullrequestreview-164910099

---

From: Mike Bishop <[email-masked]>
Date: Wed, 17 Oct 2018 18:20:58 +0000 (UTC)

@MikeBishop pushed 1 commit.

9e56562  Unwrap error code entries

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1852/files/4758a1cdb535d2da6d8b0571d12abed4b413549f..9e565628e065aea972e6b0ab52228ba1623aa312

---

From: Martin Thomson <[email-masked]>
Date: Mon, 29 Oct 2018 20:23:39 -0700

Closed #1852.

-- 
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/pull/1852#event-1933968868

---

From: Martin Thomson <[email-masked]>
Date: Mon, 29 Oct 2018 20:24:26 -0700

Reopened #1852.

-- 
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/pull/1852#event-1933969809

---

From: Martin Thomson <[email-masked]>
Date: Mon, 29 Oct 2018 20:25:01 -0700

Hmm, I wondered why I couldn't clean up the `reorganize` branch, did it manually, then this got closed as a result.  You learn new things every day with GitHub.

-- 
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/pull/1852#issuecomment-434158426

---

From: afrind <[email-masked]>
Date: Tue, 30 Oct 2018 13:32:36 -0700

@afrind pushed 1 commit.

5e54faf  Addressing more editorial feedback

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1852/files/6ff9fda2a2e74b5a29fe26a81b57579e07f54283..5e54faf7111c78cbfe62fa934c3fcbe7e83f7102

---

From: Martin Thomson <[email-masked]>
Date: Wed, 31 Oct 2018 23:18:47 +0000 (UTC)

So, reviewing this is now hard for some reason.  It shows changes that were landed on master.  Maybe this will be addressed by creating a new PR from the branch.

-- 
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/pull/1852#issuecomment-434879971