RE: Header Compression Overview

James, 

Thanks for this description. I matches the intent behind the spec, and hopefully also the spec.

I have a few comments below on the eviction mechanism.

> -----Original Message-----
> From: James M Snell [mailto:jasnell@gmail.com]
> Sent: mardi 2 juillet 2013 02:41
> To: Mike Bishop
> Cc: ietf-http-wg@w3.org
> Subject: Re: Header Compression Overview
> 
> There are a few other things to consider:
> 
> The size of the dynamic table can be bound by the recipient. The sender is
> not permitted to exceed that size. If adding a new item to the dynamic table
> will cause the table to grow beyond this limit, existing name+value pairs need
> to be removed, starting with the
> name+value pairs that were least-recently written to the table.
> 
> (((Ed. Note: We need clarity on this next part: )))

The eviction mechanism uses the table order: when the size of the header table is greater than the limit, then the first entry is dropped. This is repeated until the header table size becomes smaller than the limit. The entries are renumbered to keep the indexes small.

> 
> 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.
> 
> For example, let's suppose that I send one HEADERS frame that
> incrementally adds three items to the dynamic table. Let's call those #1, #2
> and #3. Later, I send a new HEADERS that substitutes a new value for Index
> #2. Last, I send a new HEADERS frame that adds two new headers for #4 and
> #5. The only problem is, adding #4 and #5 to the dynamic table will cause it to
> exceed it's size limit, so I need to evict some of the existing entries. Because
> of the substitution of #2, Items #1 and #3 are the first to be evicted (in that
> order). So the dynamic table contents become #2, #4, and #5).
> 
> (((Ed. Note: Or is it.... that Substitution DOES NOT change the Least-Recently-
> Written eviction order? In which case, a more recently substituted value can
> be dropped before a less-least-recently written Incremental value? That
> doesn't feel right to me...)))

The reasoning here was that an eviction mechanism was needed to be able to reduce the header table size when the decoder decrease the maximum size. The choice was to have a simple eviction mechanism by dropping the first entries of the table.
 
> 
> Eviction needs to be handled carefully with regards to the current reference
> set. Suppose, for instance, that in one request, I add "foo1 = bar" to the
> header table and to the current reference set. In the *same request*, I add
> "foo2 = baz" to the header table and to the current reference set, however,
> adding this second item causes the header table to exceed it's defined size,
> forcing the previously written "foo1 = bar" to be evicted...
> 
> On the receiving end, I'll see the instruction to add "foo1 = bar"
> first, which will add it to the reference set and the header table, then I'll see
> the instruction to add "foo2 = baz", which adds it to the reference set and
> the header table, but evicts "foo1 = bar" from the dynamic table. Despite this
> eviction, both "foo1 = bar" and "foo2 = baz" are both STILL in the reference
> set.
> 
> The next time around, "foo1 = bar" ends up being treated as a non-indexed
> literal and is dropped automatically from the reference set if it is not explicitly
> mentioned in the new set of headers.

Yes. After finishing the processing of a set of headers, it is necessary to check which headers are in the header table to find those that are kept in the reference set. Removed headers include headers that were never indexed, headers that have been replaced in the header table, headers that have been dropped from the header table.

> 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 header table.
> 
> Substitution Indexing provides only a partial solution to this problem by
> making it possible to reuse existing index positions. The problem with using
> Substitution indexing, however, is that it's not clear yet how it impact the LRU
> eviction semantics (see the Ed. Note above)

Incremental indexing allows to fill the header table when starting the connection. Substitution indexing allows to manage the header table once it is almost full.
It is true that the integration of the eviction mechanism with these two indexing possibilities is somewhat rough. This is mostly due because the eviction mechanism was designed to be simple.

Hervé.

Received on Tuesday, 2 July 2013 13:29:54 UTC