Subject: Re: [quicwg/base-drafts] Clarify QPACK eviction races (#1237)

From: Mike Bishop <[email-masked]>
Date: Thu, 26 Apr 2018 20:39:48 +0000 (UTC)

MikeBishop commented on this pull request.

> -entry remains unacknowledged.  If a new header to be inserted into the dynamic
-table would cause the eviction of such an entry, the encoder MUST NOT emit the
-insert instruction until the reference has been processed by the decoder and
-acknowledged.
-
-The encoder can emit a literal representation for the new header in order to
-avoid encoding delays, and MAY insert the header into the table later if
-desired.
-
-To ensure that the blocked eviction case is rare, references to the oldest
-entries in the dynamic table SHOULD be avoided.  When one of the oldest entries
-in the table is still actively used for references, the encoder SHOULD emit an
-Indexed-Duplicate representation instead (see {{indexed-duplicate}}).
+The encoder MUST NOT emit an instruction that evicts an entry while a reference
+to that entry remains unacknowledged. When the encoder encounters a blocked
+eviction in the course of encoding a header block, it SHOULD emit a literal

SHOULD implies that the encoder has a different option which is appropriate in certain circumstances.  What else could the encoder do, and when would it choose that?  (I don't think it does, in which case I'd just skip the normative language here and say that's what the encoder does.)

> +any eviction-prone entries, which are dynamic table entries that might be
+evicted soon.  Rather than reference an eviction-prone entry, the encoder SHOULD
+emit an Indexed-Duplicate representation (see {{indexed-duplicate}}), and
+reference the duplicate instead.
+
+To identify eviction-prone entries, 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 increments the
+draining index such that the amount of free and draining space in the dyanmic
+table is larger than its target threshold.
+
+~~~~~~~~~~  drawing
+   +----------------+-----------------------+------------+
+   | Eviction-prone |     Referenceable     | Free Space |
+   |    Entries     |        Entries        |            |
+   +----------------+-----------------------+------------+

I'm not sure if "Free Space" is necessarily the correct thing here, at least in a steady state (which is the only time eviction is an issue).  I suppose it's sometimes possible to insert something small without evicting anything, but I'm not sure if that's relevant.

-- 
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/1237#pullrequestreview-115738461

---

From: afrind <[email-masked]>
Date: Thu, 26 Apr 2018 16:57:45 -0700

afrind commented on this pull request.

ok

-- 
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/1237#discussion_r184562278

---

From: afrind <[email-masked]>
Date: Thu, 26 Apr 2018 16:58:13 -0700

There's usually some free space because it's not possible to evict a partial header.   Maybe I could make it look smaller?  The text talks about the sum of free space and draining space so I wanted to include it in the picture.

-- 
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/1237#discussion_r184562358

---

From: Martin Thomson <[email-masked]>
Date: Sun, 29 Apr 2018 21:53:45 -0700

martinthomson commented on this pull request.

The point here is not that there might be some free space (there is almost always free space because header fields are not necessarily a neat fit for the available space), but that the encoder needs to keep its hands off those entries that are close to eviction.  Eviction-prone is misleading, because it implies that there is a probability of eviction.

I think that this map is misleading though.  There are three important classifications here:

* Entries that are near eviction, such that new insertions might be blocked by outstanding references to those entries.
* Entries that are recently added (i.e., those that are "vulnerable"), such that references to them might cause the receiver to block.
* Other entries that are acknowledged, but not near eviction.

The line between those that are "vulnerable" and acknowledged is crisp.  The point here is that the line between near-eviction and merely acknowledged is fuzzy and subject to heuristics.

I think that you also want to say that keeping the near-eviction index in the range of acknowledged entries will prevent perverse behaviour.  If the two ever cross, you can get duplication on every header block, which causes unnecessary churn.  (It's also possible to get that without the two crossing with a naive implementation, but I don't think that we need to get into that too much.)

-- 
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/1237#discussion_r184911335