Re: Header Compression Overview

On Mon, Jul 1, 2013 at 2:41 PM, Mike Bishop
<Michael.Bishop@microsoft.com> wrote:
> Thanks for writing this up – by comparing this with the draft and our
> understandings of it, you’ll help us find points that need to be clarified
> so implementations agree on the behavior.
>

Agreed.

>[snip]
> That sounds straightforward, however, given the distinction between
> Incremental and Substitution indexing, the Least Recently Written rule can
> become a bit complicated in the implementation. Using Substitution indexing
> resets the Write time for that particular index, meaning that eviction does
> not necessary occur in Index order.
>
> But the draft says:
>
> When an entry is added to the header table, if the header table size is
> greater than the limit, the table size is reduced by dropping the entries at
> the beginning of the table until the header table size becomes lower than or
> equal to the limit.  Dropping entries from the beginning of the table causes
> a renumbering of the remaining entries.
>
> I had interpreted this to mean that the eviction is truly LRW only if one is
> using Incremental all the time; if you choose to use Substitution, you trade
> off getting a smaller index against the fact that the slot is going to be
> evicted sooner than if you hadn’t substituted.
>

Saying that the LRW only applies when using Incremental is problematic
depending on the ordering of operations. For instance, let's suppose
that our table size limit is 20 bytes and we currently have 20 bytes
stored. We use substitution indexing referencing item #0 and pass in a
value that would cause the size to be exceeded. If we substitute index
#0 first, then pop off because our size is exceeded, the item #0 that
we *just added* is removed. Which is really quite silly. If we pop off
first, then add, then what we are really doing is dropping #0 and
substituting the current #1 (because popping apparently causes the
index to be renumbered according to the current text).

The way the text is currently written (which differs from the earlier
"least recently written" language I'd seen in a previous draft), we
pop off *after* we substitute, which means our new value at #0
disappears entirely.

>
>
> Dropping only from the beginning of the table and renumbering also partially
> addresses your concern about monotonically-increasing indices, since the
> index will never become longer than the number of entries in the
> (size-bounded) table.
>

Yes, I had missed the renumbering statement that's in the current draft.

>
>
> I also can’t find anything in the document which says that the initial
> values are a separate, unchangeable table.  All it says is that the values
> in Appendix A constitute the initial contents of the header table.  Unless
> there’s specific language around eviction that says you can’t evict the
> initial values, I would expect eviction to “drop the entries at the
> beginning of the table,” meaning the initial entries.
>

This is another bit that should be clarified. In all of the previous
header compression drafts, there were two separate tables: one static
and one dynamic. If this has been changed, it would be very helpful to
know :-)

- James

>
>
> -----Original Message-----
> From: James M Snell [mailto:jasnell@gmail.com]
> Sent: Monday, July 1, 2013 1:32 PM
> To: ietf-http-wg@w3.org
> Subject: Re: Header Compression Overview
>
>
>
> Minor correction with regards to substitution indexing for literal
> headers...
>
>
>
> You can use substitution to change both the name and value of existing
> header positions, making it fairly simple to reuse existing memory slots.
>
>
>
> Generally speaking, an intelligent implementation is likely going to want to
> make smart use of substitution indexing as much as possible, in order to
> keep the compression context from filling up and incurring more frequent
> eviction operations.
>
>
>
> On Mon, Jul 1, 2013 at 11:32 AM, James M Snell <jasnell@gmail.com> wrote:
>
> [snip]
>
>>
>
>> We have an index position for the header field foo1 but not the full
>
>> name+value pair "foo1=bar". Remember when I briefly mentioned
>
>> Incremental Indexing vs. Substitution indexing? We need to make a
>
>> decision. When Incremental Indexing, I can add "foo1 = new" as an
>
>> entirely new entry in the dynamic table (#2) or I can replace the
>
>> value of the existing "foo1 = bar" entry sitting at index #3. The
>
>> choice is entirely up to the sender and can be based on a number of
>
>> factors... the most important of which is basic memory management. For
>
>> now, let's keep things simple and use Incremental Indexing. We want to
>
>> minimize the amount of data we're going to send, however, so instead
>
>> of sending the header field name as a length prefixed string, we're
>
>> going to reference the existing index position and send along a new
>
>> value ( 0x43 0x03 0x6E 0x65 0x77 ).
>
>>
>
> ...
>
>>
>
>> Another consideration that must be carefully weighed is the choice
>
>> between Incremental and Substitution indexing. If an implementation
>
>> always chooses to use Incremental Indexing, Eviction will become the
>
>> only reliable means of memory management. Long lived connections will
>
>> build up full compression contexts that tie up a potentially
>
>> significant amount of memory. This could be dangerous, especially
>
>> since there is no explicit mechanism for deleting items from the
>
>> dynamic table.
>
>>
>
> ...
>
>>
>
>> Substitution Indexing provides only a partial solution to this problem
>
>>by making it possible to reuse existing index positions so long as the
>
>>header field name remain the same. There still exists the possibility
>
>>of tying up memory, however, if there are a large number of different
>
>>header names.
>
>>[snip]
>
>
>
>
>
>

Received on Monday, 1 July 2013 22:00:00 UTC