Subject: Header compression: header set diff

From: RUELLAN Herve <[email-masked]>
Date: Thu, 21 Mar 2013 12:50:59 +0000

A difference between Delta and HeaderDiff is the choice of the initial state for a new set of headers. Delta starts from the previous set of headers (or from one of the previous sets, as it can support remembering several sets of headers) describing the differences with the new set. HeaderDiff starts from a blank state, describing the whole new set.

To better understand the impact of this choice of persisting the header set, we tested it inside HeaderDiff and saw a slight improvement of compaction for requests but also a slight(er) decrease of compaction for responses.

Implementing the persistence of the header set has a few subtleties: a literal header that is not added to the buffer must be added to the current set of headers, but must not be kept in the persisted set (which will be used as an initial state for the next set of headers).
But the main difficulty comes from the interaction with the management of the buffer: for example, an entry should not be removed from the buffer if it's in the persisted set of header.

We are wondering if the complexity of the implementation of header set persistence is worth the benefit. We think that most of the compaction improvements could be obtained by allowing to encode a group of indexed headers in one operation (this is what the *trang opcodes of Delta does).

Do you have any insight on this feature, or any data helping to understand its effects?

Hervé.

---

From: Patrick McManus <[email-masked]>
Date: Thu, 21 Mar 2013 09:12:57 -0400

> To better understand the impact of this choice of persisting the header set, we tested it inside HeaderDiff and saw a slight improvement of compaction for requests but also a slight(er) decrease of…

All else being equal (which is of course never true), compression
ratio of requests is more important than responses because the MUX
allows multiple requests to fit inside the cwnd (and thus avoid
scaling by rtt). The better the ratio, the greater the number of
transactions in 1-flight-mux. On the response side the headers are
mixed in with data frames which in many (but not all) scenarios
overhwelm the headers on a byte count basis - so the effect of header
compression is less likely to impact congestion control.

---

From: James M Snell <[email-masked]>
Date: Thu, 21 Mar 2013 12:53:12 -0700

+1.. In addition to this,  response headers tend to be significantly more
variable than request headers...  Which,  of course means much lower
compression ratios anyway if we're talking about delta based mechanisms.
It makes very little sense to optimize for the response side.
On Mar 21, 2013 6:14 AM, "Patrick McManus" <[email-masked]> wrote:

> > To better understand the impact of this choice of persisting the header
> set, we tested it inside HeaderDiff and saw a slight improvement of
> compaction for requests but also a slight(er) decrease of compaction for
> responses.
>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 21 Mar 2013 16:47:08 -0400

Unless, of course, you ever intend to do server push :)
-=R

---

From: Roberto Peon <[email-masked]>
Date: Thu, 21 Mar 2013 17:09:53 -0400

To clarify-- when we do server push, often many resources with extremely
similar headers are being pushed.

Herve-- have you checked in the changes to HeaderDiff for this so I can
reproduce?
-=R

On Thu, Mar 21, 2013 at 4:47 PM, Roberto Peon <[email-masked]> wrote:

>>> > To better understand the impact of this choice of persisting the
>>> header set, we tested it inside HeaderDiff and saw a slight improvement of

---

From: James M Snell <[email-masked]>
Date: Thu, 21 Mar 2013 15:57:54 -0700

True, but to see any benefit with delta each of those streams would need to
share compression state forcing us to synchronize encoding for all pushed
streams in the same group...  Which would obviously be detrimental to
throughput depending on our optimization strategy overall.

Also, truth be told,  other than in truly exceptional cases, I imagine many
servers are not going to want to hold on to response compression state for
any length of time - - opting instead to dump that state as quickly as
possible after sending the response so it can free up resources for the
next request.

reproduce?
>>> +1.. In addition to this,  response headers tend to be significantly
more variable than request headers...  Which,  of course means much lower
compression ratios anyway if we're talking about delta based mechanisms.
It makes very little sense to optimize for the response side.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 13:31:49 +0000

There are two sides on that coin.

First, for the compression ratio, in the general context of the web (i.e.: downloading webpages...), I agree that compressing request headers will have more impact on the user perceived latency than compressing response headers.
However, compressing response headers is also important in many contexts. For example, for the web, being able to MUX many 304 in the cwnd could have an impact. As Roberto pointed, it is also important for server push: the smaller the size of the push promises, the faster the data for the requested page will be sent.
In addition, from the results obtained by both Delta and HeaderDiff, I'm not so sure on the variability of response headers. I would think that their variability for one server is roughly of the same level as the variability of the request headers. In addition, server/site developers could take advantage of HTTP/2.0 in the future and reduce the variability of the response headers.

The other side of the coin is the complexity of this feature. I don't think we must only think compression ratio, but also complexity. From the data I have, this feature allows improving compaction of about 1 point for requests, while losing .25 point for responses. From my point of view, it's not worth the trouble implementing it. But I'm willing to reconsider it in view of new data.

Hervé.

From: Roberto Peon [mailto:[email-masked]]
Sent: jeudi 21 mars 2013 21:47
To: James M Snell
Cc: Patrick McManus; HTTP Working Group; RUELLAN Herve
Subject: Re: Header compression: header set diff

On Thu, Mar 21, 2013 at 3:53 PM, James M Snell <[email-masked]<mailto:[email-masked]>> wrote:

+1.. In addition to this,  response headers tend to be significantly more variable than request headers...  Which,  of course means much lower compression ratios anyway if we're talking about delta based mechanisms.  It makes very little sense to optimize for the response side.
On Mar 21, 2013 6:14 AM, "Patrick McManus" <[email-masked]<mailto:[email-masked]>> wrote:
On Thu, Mar 21, 2013 at 8:50 AM, RUELLAN Herve

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 22 Mar 2013 13:33:10 +0000

Roberto,

I haven't checked in these changes, and I have many changes to check in already :-(
I'll try to do it anyway.

Hervé.

From: Roberto Peon [mailto:[email-masked]]
Sent: jeudi 21 mars 2013 22:10
To: James M Snell
Cc: Patrick McManus; HTTP Working Group; RUELLAN Herve
Subject: Re: Header compression: header set diff

To clarify-- when we do server push, often many resources with extremely similar headers are being pushed.

Herve-- have you checked in the changes to HeaderDiff for this so I can reproduce?
-=R

On Thu, Mar 21, 2013 at 4:47 PM, Roberto Peon <[email-masked]<mailto:[email-masked]>> wrote:
Unless, of course, you ever intend to do server push :)
-=R

---

From: James M Snell <[email-masked]>
Date: Fri, 22 Mar 2013 16:51:17 -0700

On Fri, Mar 22, 2013 at 6:31 AM, RUELLAN Herve
<[email-masked]>wrote:

>  There are two sides on that coin.****
>
> ** **
>
> First, for the compression ratio, in the general context of the web (i.e.:
> downloading webpages…), I agree that compressing request headers will have
> more impact on the user perceived latency than compressing response headers.
> ****
>
> However, compressing response headers is also important in many contexts.
> For example, for the web, being able to MUX many 304 in the cwnd could
> have an impact. As Roberto pointed, it is also important for server push:
> the smaller the size of the push promises, the faster the data for the
> requested page will be sent.****
>
> In addition, from the results obtained by both Delta and HeaderDiff, I’m
> not so sure on the variability of response headers. I would think that
> their variability for one server is roughly of the same level as the
> variability of the request headers. In addition, server/site developers
> could take advantage of HTTP/2.0 in the future and reduce the variability
> of the response headers.****
>
> **
>
​
I ran some numbers testing variability on the various sample datasets we
have so far. Obviously these are far from being a statistically significant
sample but they are telling... The raw output data is here:
https://github.com/jasnell/compression-test/tree/headerstats/counts

If we take a look at just one of those (for amazon) and examine the
variability of each header across requests.. we get the following (my
apologies, fairly long list...)

accept-language      0.00273224043716  Req
:version             0.00273224043716  Req/Resp
user-agent           0.00273224043716  Req
accept-encoding      0.00273224043716  Req
:scheme              0.00273224043716  Req
connection           0.00446428571429  Req
:method              0.00546448087432  Req
x-cache              0.00847457627119  Resp?
content-encoding     0.00925925925926  Req/Resp (typically Resp)
:status              0.0109289617486   Resp
:status-text         0.0109289617486   Resp
via                  0.0127118644068   Resp
accept               0.0191256830601   Req
vary                 0.0194174757282   Resp
server               0.0280112044818   Resp
transfer-encoding    0.03125           Req/Resp (typically Resp)
pragma               0.0322580645161   Req/Resp (typcailly Req: pragma:
no-cache)
content-type         0.0502645502646   Resp
x-requested-with     0.0588235294118   Resp?
accept-ranges        0.0666666666667   Req
:host                0.068306010929    Req
referer              0.0694444444444   Req
nncoection           0.0714285714286   ?
x-cache-lookup       0.125             Resp?
if-modified-since    0.142857142857    Req
p3p                  0.173076923077    Resp
expires              0.200636942675    Resp
cache-control        0.206686930091    Resp
etag                 0.21686746988     Resp
cookie               0.238095238095    Req
set-cookie           0.25              Resp
location             0.4               Resp
content-transfer-encoding 0.5          Resp (typically)
content-location     0.5               Resp
date                 0.693150684932    Resp
x-amz-request-id     0.75              Resp
x-amz-id-2           0.815789473684    Resp
x-amz-meta-md5-hash  0.833333333333    Resp
x-amz-meta-jets3t-original-file-date-iso8601 0.833333333333 Resp
x-amz-id-1           0.866666666667    Resp
content-length       0.867605633803    Resp
last-modified        0.880794701987    Resp
age                  0.958158995816    Resp
:path                0.964480874317    Req
keep-alive           1.0               Req
if-none-match        1.0               Req

These are measurements of variability between 0.0 and 1.0. With 0.0 being
"doesn't ever change" and 1.0 being "changes with every request". I've
pulled out some of the less relevant application specific X-? extension
headers from this sample and added indicators of where the header is used.
While there are a number of Response headers with low variability (:status,
:status-text, via, content-type, the overwhelming majority of headers with
high variability are Response headers.

Yes, we will see some benefit to compressing response headers, I'm not
arguing that by any means. All I am saying is that, given these results, I
do not see any significant advantage to optimizing compression for
responses. In fact, I highly doubt most servers are going to want to
maintain response compression state for any length of time longer than it
takes to completely send that response, especially since the server has
absolutely no guarantee that it will ever need to reuse that compression
context beyond responding to the immediate request.

> **
>
> The other side of the coin is the complexity of this feature. I don’t
> think we must only think compression ratio, but also complexity. From the
> data I have, this feature allows improving compaction of about 1 point for
> requests, while losing .25 point for responses. From my point of view, it’s
> not worth the trouble implementing it. But I’m willing to reconsider it in
> view of new data.****
>
> **
>

​Here I definitely agree and I am struggling with this particular point. I
am currently implementing Roberto's delta compression mechanism in Java (
https://github.com/jasnell/http2) just so we can have another
implementation to play around and experiment with, particularly for interop
testing. While there are certainly many ways the mechanism can (and will)
be optimized, the mechanism adds an additional degree of complexity that
I'm not yet fully convinced is justified. For one, the additional state
storage requirements could become rather significant, even with the
restriction that the receiver gets to control the amount of stored state.
Existing infrastructure is not designed to handle those additional memory
requirements and could require a fairly significant upgrade in order to
support it. Roberto's argument to me when I've raised that point is that
infrastructure providers for whom better compression ratios are important
will be willing to invest in upgrading their existing hardware to support
it. While that's a logical argument, I remain not fully convinced. In the
worse case, infrastructure providers will simply do a software upgrade and
set the amount of stored state to zero, which kills our compression ratios.
Furthermore, for services that operate at significantly high volume,
concerns about overall throughput is likely going to trump compression
ratio. So while I do like the idea of delta in theory, and I am impressed
with the work Roberto has done on this, my fear is that delta is trying to
be "too clever". Perhaps all we really ought to be doing at this point is
finding a more efficient way of encoding the header data (i.e. the
binary-optimized header encoding draft) and hold off on delta until we have
better analytical data to work from.

>  **
>
> Hervé.****
>
> ** **
>
> ** **
>
> *From:* Roberto Peon [mailto:[email-masked]]
> *Sent:* jeudi 21 mars 2013 21:47
> *To:* James M Snell
> *Cc:* Patrick McManus; HTTP Working Group; RUELLAN Herve
> *Subject:* Re: Header compression: header set diff****
>
> ** **
>
> -=R****
> ** **
> On Thu, Mar 21, 2013 at 3:53 PM, James M Snell <[email-masked]> wrote:*
> ***
>
> It makes very little sense to optimize for the response side.  ****
>
> On Mar 21, 2013 6:14 AM, "Patrick McManus" <[email-masked]> wrote:**
> **
>
> compression is less likely to impact congestion control.****
>
> ** **
>

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 25 Mar 2013 17:50:23 +0000

From: James M Snell [mailto:[email-masked]]
Sent: samedi 23 mars 2013 00:51
To: RUELLAN Herve
Cc: Roberto Peon; Patrick McManus; HTTP Working Group
Subject: Re: Header compression: header set diff

On Fri, Mar 22, 2013 at 6:31 AM, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:

First, for the compression ratio, in the general context of the web (i.e.: downloading webpages…), I agree that compressing request headers will have more impact on the user perceived latency than compressing response headers.
However, compressing response headers is also important in many contexts. For example, for the web, being able to MUX many 304 in the cwnd could have an impact. As Roberto pointed, it is also important for server push: the smaller the size of the push promises, the faster the data for the requested page will be sent.
In addition, from the results obtained by both Delta and HeaderDiff, I’m not so sure on the variability of response headers. I would think that their variability for one server is roughly of the same level as the variability of the request headers. In addition, server/site developers could take advantage of HTTP/2.0 in the future and reduce the variability of the response headers.

​
I ran some numbers testing variability on the various sample datasets we have so far. Obviously these are far from being a statistically significant sample but they are telling... The raw output data is here: https://github.com/jasnell/compression-test/tree/headerstats/counts

If we take a look at just one of those (for amazon) and examine the variability of each header across requests.. we get the following (my apologies, fairly long list...)

pragma               0.0322580645161   Req/Resp (typcailly Req: pragma: no-cache)

These are measurements of variability between 0.0 and 1.0. With 0.0 being "doesn't ever change" and 1.0 being "changes with every request". I've pulled out some of the less relevant application specific X-? extension headers from this sample and added indicators of where the header is used. While there are a number of Response headers with low variability (:status, :status-text, via, content-type, the overwhelming majority of headers with high variability are Response headers.

Yes, we will see some benefit to compressing response headers, I'm not arguing that by any means. All I am saying is that, given these results, I do not see any significant advantage to optimizing compression for responses. In fact, I highly doubt most servers are going to want to maintain response compression state for any length of time longer than it takes to completely send that response, especially since the server has absolutely no guarantee that it will ever need to reuse that compression context beyond responding to the immediate request.

I think that in many usages, a server knows it will send several responses to a single client. Due to the bulk of the data contained in the responses, it will probably not want to spend too much resources compressing the response headers. However, if we can provide a compression mechanism that can be customized to use only limited resources while still providing good compaction, this could hit a sweet spot for servers.

The other side of the coin is the complexity of this feature. I don’t think we must only think compression ratio, but also complexity. From the data I have, this feature allows improving compaction of about 1 point for requests, while losing .25 point for responses. From my point of view, it’s not worth the trouble implementing it. But I’m willing to reconsider it in view of new data.

​Here I definitely agree and I am struggling with this particular point. I am currently implementing Roberto's delta compression mechanism in Java (https://github.com/jasnell/http2) just so we can have another implementation to play around and experiment with, particularly for interop testing. While there are certainly many ways the mechanism can (and will) be optimized, the mechanism adds an additional degree of complexity that I'm not yet fully convinced is justified. For one, the additional state storage requirements could become rather significant, even with the restriction that the receiver gets to control the amount of stored state. Existing infrastructure is not designed to handle those additional memory requirements and could require a fairly significant upgrade in order to support it. Roberto's argument to me when I've raised that point is that infrastructure providers for whom better compression ratios are important will be willing to invest in upgrading their existing hardware to support it. While that's a logical argument, I remain not fully convinced. In the worse case, infrastructure providers will simply do a software upgrade and set the amount of stored state to zero, which kills our compression ratios. Furthermore, for services that operate at significantly high volume, concerns about overall throughput is likely going to trump compression ratio. So while I do like the idea of delta in theory, and I am impressed with the work Roberto has done on this, my fear is that delta is trying to be "too clever". Perhaps all we really ought to be doing at this point is finding a more efficient way of encoding the header data (i.e. the binary-optimized header encoding draft) and hold off on delta until we have better analytical data to work from.

I you have time, we would welcome another implementation of HeaderDiff.

I think we really should aim at a customizable compression mechanism: if you don’t want to spend too much resources (or even any resource) on compression, just use a simple encoder. From my experience, by using very few resources, you can easily divide the size of the headers by at least two. If you really want to save some bytes, then you can implement a very complex and very clever encoder.
I think that binary-optimized headers are also interesting. We experimented with a few of them internally and found that a binary encoding for dates and integers are simple to add and provide good compaction improvements.

Hervé.

---

From: James M Snell <[email-masked]>
Date: Mon, 25 Mar 2013 10:58:24 -0700

On Mon, Mar 25, 2013 at 10:50 AM, RUELLAN Herve
<[email-masked]>wrote:

> ​[snip]​

​Gimme about two to three weeks and I'll see if I can put it together...​

> I think we really should aim at a customizable compression mechanism: if
> you don’t want to spend too much resources (or even any resource) on
> compression, just use a simple encoder. From my experience, by using very
> few resources, you can easily divide the size of the headers by at least
> two. If you really want to save some bytes, then you can implement a very
> complex and very clever encoder.
>

​I tend to fear solutions that are "too clever", especially if it's not yet
completely clear how much benefit the solution will ultimately provide. In
the meantime, I'm still going to be writing the code tho ;-)​

> I think that binary-optimized headers are also interesting. We
> experimented with a few of them internally and found that a binary encoding
> for dates and integers are simple to add and provide good compaction
> improvements.
>

In about a week I'll have a modified draft of the BOHE draft spec that adds
binary encoding to Roberto's delta2 encoding. I can look at HeaderDiff and
add it in there also. If we focus on a limit number of value types
(specifically text, numbers, dates and binary blobs) then things can remain
very simple.

- James
​​

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 29 Mar 2013 15:31:29 +0000

> -----Original Message-----
> Sent: lundi 25 mars 2013 18:58
> To: RUELLAN Herve
[snip]
> add it in there also. If we focus on a limit number of value types (specifically
> text, numbers, dates and binary blobs) then things can remain very simple.

That would be great. I think that focusing on the value types you propose should be enough for a start: it would be simple but already should provide some good improvement in compaction.

Hervé.