Re: Header Compression Overview

This does not adapt well to key-values which change quickly or are small.
-=R


On Mon, Jul 1, 2013 at 11:21 PM, James M Snell <jasnell@gmail.com> wrote:

> After implementing several variations,  I want something even simpler...
> A fixed index range,  assigned incrementally with rollover at the end and
> no substitution. It becomes very simple that way.
> On Jul 1, 2013 8:29 PM, "Mike Bishop" <Michael.Bishop@microsoft.com>
> wrote:
>
>> Yes -- we just need to clarify the eviction behavior.  I actually prefer
>> the evict-from-front model, because it means there's no need for metadata
>> to include a timestamp on each entry in the table.  You know which item
>> you're going to evict, because it's clear.
>>
>> -----Original Message-----
>> From: James M Snell [mailto:jasnell@gmail.com]
>> Sent: Monday, July 1, 2013 5:41 PM
>> To: Mike Bishop
>> Cc: ietf-http-wg@w3.org
>> Subject: Re: Header Compression Overview
>>
>> Ok, so I'm taking another look through the current header compression
>> draft and I'd swear that it said some things differently the last time I
>> read it ;-) ... (which is, of course, impossible... so I'm going to blame
>> it on the 110+ degree heat here today and the fact that I've read so many
>> different versions of header compression drafts over the last few months
>> that my specific recollection of any individual version is a bit gooey in
>> the middle). So.. with that said, allow me to make a few corrections to the
>> explanation... Let's see if this is a bit closer to reality:
>>
>> The sender and receiver each maintain their own synchronized view of the
>> compression context.
>>
>> The compression context consists of two components:
>>
>>   1. A dynamic table of name+value pairs
>>   2. The current "reference set" of name+value pairs
>>
>> When the connection is first established the reference set (#2) is empty
>> and the header table is prepopulated.
>>
>> The sender constructs a logical set of header name+value pairs, where
>> each name can have multiple values. Each distinct name+value combination is
>> treated independently of the others.
>>
>> For each name+value pair in the set, the sender needs to determine
>> whether or not to use an Indexed or Literal representation. The Indexed
>> representation is appropriate if the name+value pair already exists in
>> either the header table (#1). The Literal representation is appropriate if
>> the name+value pair either does not exist in #1, or if the sender does not
>> want the name+value pair stored in the compression context (more on this
>> part later)
>>
>> For example, let's assume that the header table initially consists of
>> three name+value pairs:
>>
>>   0 = :method = GET
>>   1 = :method = POST
>>   2 = :path = /
>>
>> Then, let's assume that I've created a new connection and the first set
>> of headers I send to the server contains the header fields:
>>
>>   :method = GET
>>   :path = /
>>   foo1 = bar
>>   foo2 = baz
>>
>> When I process this set of header fields, I first check each pair against
>> the header table and find that :method = GET uses the index
>> (0) while :path = / uses the index (2). Since I don't find foo1 or
>> foo2 in the static table, I determine that I have to use the Literal
>> representation for those two fields.
>>
>>   :method = GET  ==>  Indexed as (0)
>>   :path = / ==> Indexed as (2)
>>   foo1 = bar ==> Literal
>>   foo2 = bar ==> Literal
>>
>> Now, still on the sending side, once I determine the kind of
>> representation, I need to determine what changes need to be made to the
>> reference set (#2). The reference set is what the sender and receiver both
>> use to determine what set of header fields are currently active. Since this
>> is a brand new connection, the reference set is empty, so with this first
>> set of headers, the changes to the reference set are straightforward... I'm
>> adding everything...
>>
>> To add an Indexed representation of a header, all I do is reference it's
>> index.. that's easy enough to do...
>>
>> To add a Literal representation of a header, there are two options:
>> With Indexing, or Without Indexing. With Indexing means that when the
>> header field is added to the Reference set (#2), the name+value pair is
>> also added to the header table (#1). Without indexing means that when the
>> header field is added to the Reference set (#2) the
>> name+value pair is NOT added to the dynamic table. Which of these to
>> use to entirely up to the sender. So I'm going to decide that foo1 is
>> going to be With Indexing, while foo2 is going to be Without Indexing.
>>
>> (there is another option here between incremental vs. substitution
>> indexing but I'll get to that in a few minutes)
>>
>> At this point, I have a set of instructions of how to modify the
>> reference set:
>>
>>   1. Add Index #0
>>   2. Add Index #2
>>   3. Add Literal "foo1 = bar" with Indexing
>>   4. Add Literal "foo2 = baz" without Indexing
>>
>> At this point, I can create the serialized header block that will be
>> transmitted within the HEADERS frame. This block ONLY contains the
>> serialized set of instructions for modifying the reference set.
>>
>> For instructions 1 and 2 (adding index #0 and index #2), the
>> serialization is very simple and requires exactly two bytes (0x81 0x83). (I
>> have to bump up the index values by 1 when serializing for some reason)
>>
>> For instruction #3, it's slightly more complicated, but not much... we
>> have a single prefix byte (0x40) followed by the length prefixed header
>> name (0x04 0x67 0x6F 0x6F 0x31) and the length prefixed header value (0x03
>> 0x62 0x61 0x72).
>>
>> For instruction #4, the encoding is only slightly different. The single
>> prefix byte is 0x60 followed by the length prefixed header name
>> (0x04 0x67 0x6F 0x6F 0x32) and the length prefixed value (0x03 0x62
>> 0x61 0x7A).
>>
>> Putting it all together, the complete sequence of octets that I will send
>> within the HEADERS frame is:
>>
>>  0x81 0x83 0x40 0x04
>>  0x67 0x6F 0x6F 0x31
>>  0x03 0x62 0x61 0x72
>>  0x60 0x04 0x67 0x6F
>>  0x6F 0x32 0x03 0x62
>>  0x61 0x7A
>>
>> Once I generate this sequence, a new entry is added to the header table
>> (#1):
>>
>>   3 = foo1 = bar
>>
>> And the reference set (#2) has been updated to include the four headers I
>> sent:
>>
>>   :method = GET
>>   :path = /
>>   foo1 = bar
>>   foo2 = baz
>>
>> (this is a simplification actually but it's close enough for now)
>>
>> I send the serialized instructions to the other endpoint. It receives
>> those and reverses the process first by parsing the octet sequence to
>> determine the exact set of instructions it needs to follow to modify it's
>> own view of the reference set. Once it knows what the operations are, it
>> begins making the necessary changes to the reference set.
>> First, it sees two Index representations, so it looks those index values
>> up in the header table (#1). It finds Index #0 and Index #2 in the static
>> table so it adds those name+value pairs to it's reference set. Next, it
>> finds the Literal With Indexing instruction for "foo1 = bar". Since it is
>> "With Indexing", the server adds the name+value pair to the reference set
>> *AND* to the header table. Next it finds the Literal Without Indexing
>> instructions for "foo2 = baz". Since it is "Without Indexing", the server
>> only adds the name+value pair to the reference set and notes the fact that
>> the header was not indexed at all.
>>
>> At this point, the sender and receiver should have identical views of
>> both the header table and reference set.
>>
>> So far so good.
>>
>> Let's move on... back on the sending side. Now I want to send another
>> request to the server. Some of the header fields remain the same, some have
>> different values, some are no longer used at all.
>>
>>   :method = POST
>>   :path = /
>>   foo1 = new
>>   foo3 = new
>>
>> When serializing these headers, I'm going to follow the same process, but
>> since our header table and reference set are both different, the serialized
>> results are going to be a bit different.
>>
>> Going through each of the headers, I first determine that :method = POST
>> is already contained in the header table at Index #1. I also note that
>> :path = / is also in the header table using Index #2 (this hasn't changed).
>>
>> Also looking at the header table, I see that there is a "foo1" header
>> with a different value sitting at Index #3. I make note of that index
>> position so I can use it next.
>>
>> Lastly, I determine that the new header field "foo3 = new" is not in
>> header table at all. I'm going to have to use the Literal representation
>> for that one.
>>
>> Once I've determined the basic type of representation, I need to
>> determine how the current reference set needs to be changed. As a reminder,
>> here's what the current reference set looks like:
>>
>>   :method = GET
>>   :path = /
>>   foo1 = bar
>>   foo2 = baz
>>
>> Immediately, I see that :method = GET needs to be replaced with :method =
>> POST, since we know the static index positions for both of those, we can
>> simple turn one off by referencing it's index and turn the other on (also
>> by referencing it's index). That requires a simple two-byte sequence (0x81
>> 0x82).
>>
>> I see that :path = / is already in the reference set. So for that one, I
>> don't have to do anything! Awesome. Let's move on.
>>
>> 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 ( 0x44 0x03 0x6E 0x65 0x77 ). (again, I
>> have to bump up the value of index value by 1)
>>
>> Moving on, we determine that "foo2 = baz" needs to be removed from the
>> reference set. We see, however, that "foo2 = baz" was previously sent as a
>> Literal without any indexing. This means that it will automatically be
>> removed from the reference set the next time around without the sender
>> having to do anything! That's helpful.
>>
>> Now all we need to deal with is the new "foo2 = new" header field, we'll
>> do that using Literal With Indexing, like we did originally with the "foo1
>> = bar" header field in the first request..  0x40 0x04 0x67 0x6F 0x6F 0x33
>> 0x03 0x6E 0x65 0x77.
>>
>> The complete sequence of octets for the second request is:
>>
>>   0x81 0x82 0x44 0x03
>>   0x6E 0x65 0x77 0x40
>>   0x04 0x67 0x6F 0x6F
>>   0x33 0x03 0x6E 0x65
>>   0x77
>>
>> After I construct this sequence, my header table has five entries:
>>
>>   0 = :method = GET
>>   1 = :method = POST
>>   2 = :path = /
>>   3 = foo1 = bar
>>   4 = foo1 = new
>>
>> And my reference set looks like:
>>
>>   :method = POST
>>   :path = /
>>   foo1 = new
>>   foo3 = new
>>
>> I send the HEADERS frame to the server and it deconstructs the set of
>> instructions, applies those to it's own reference set, updates it's header
>> table, and goes on from there.
>>
>> The process can get a bit complicated at times, but that's the basic
>> operation. 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: )))
>>
>> 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...)))
>>
>> 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.
>>
>> 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)
>>
>> ...
>>
>> Ok, I *think* that's a more accurate description. Do folks agree?
>>
>> - James
>>
>>
>>