Subject: delta encoding and state management

From: James M Snell <[email-masked]>
Date: Wed, 16 Jan 2013 17:23:36 -0800

Just continuing the investigation of delta... poking holes :-)

There is a potential issue with delta as currently designed. Assume we
 have a client A, a proxy B and a server C.

Let's assume the following default header dictionary:

  ID | Name | Value
 ----+------+-------
   1 | Foo  | A
   2 | Bar  |

A wants to send a message to C, the headers are:

  Foo: A
  Bar: B,C

The initial delta encoding would be:

  toggle(1)
  clone(2,B) => 3
  clone(2,C) => 4

B receives this message from A and forwards it on to C. C initializes it's
local copy of the compression context, storing the appropriate values. This
table has to be maintained from request-to-request, keeping header values
stored. The table on C becomes:

  ID | Name | Value
 ----+------+-------
   1 | Foo  | A
   2 | Bar  |
   3 | Bar  | B
   4 | Bar  | C

The active headers for the current request are pulled from the table [1,3,4]

A then wants to send another message to C, the headers are:

  Foo: A
  Bar: B,D

The delta encoding would be:

  toggle(4)
  clone(2,D) =>

B forwards this message on to C, which updates the context. The table on C
becomes:

  ID | Name | Value
 ----+------+-------
   1 | Foo  | A
   2 | Bar  |
   3 | Bar  | B
   4 | Bar  | C
   5 | Bar  | D

The active headers for the second request are pulled from the table
[1,3,5]. The table grows indefinitely as new header values are used within
the course of a single session. The complete value of the header would need
to be stored, highly variable values (cookies, timestamps, etc) would be
stored in full just in case they are reused later. (Roberto, please correct
me if I'm wrong on this point!)

So far, so good. Let's mess it up.

Let's assume that the connection between B and C dies before that second
request is sent to B, causing the compression context shared between B and
C to be reset and lost. Suddenly the delta encoding in the second message
becomes invalid, even though nothing has interrupted the connection between
A and B.

B and C need to have some way of reestablishing the compression context
after their connection is reestablished or the second message just becomes
nonsense.

At first review, there appear to be a few options:

1. B has to also maintain it's own copy of the complete header value table,
which could consume quite a bit of storage space on the proxy (relative to
current requirements). Once the connection is re-established, B would then
translate the delta-encoding in the second message to initialize the
reconstructed context on C. We currently do not have any metrics on just
how large this table could potentially become within the course of a single
session.

2. B needs to notify A that the compression context needs to be reset. If A
gets that message before is constructs the second message, all is fine, A
would just treat it like the initial response. If A already in the process
of sending that message to B, B is going to have to reject it or put it on
hold until the context is reconstructed... in which case B is going to need
some way of knowing whether the message needs to be rejected. Also, there
is a risk of too many reset messages being sent, causing a lot of churn.

3. B assigns a compression buffer window size of 0, effectively disabling
the stored compression context (every message effectively becomes an
initial message). The risk here is that a proxy might defensively always
send a 0.

My questions to the group are:

A. Am I missing anything obvious here?
B. Are there other possible options?
C. Which option seems to be the least painful?

- James

---

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Jan 2013 17:39:27 -0800

> Let's assume the following default header dictionary:
Correct, if you're doing compression, you'll need the compression state. A
proxy would need to keep this around at a minimum so it'd know what hosts,
methods, etc. were being used so as to appropriately route a query (else
you could just read from one TCP hose and write into the other and who
cares about the compression when you can do that).

> 1. B has to also maintain it's own copy of the complete header value
> table, which could consume quite a bit of storage space on the proxy
> (relative to current requirements). Once the connection is re-established,
> B would then translate the delta-encoding in the second message to
> initialize the reconstructed context on C. We currently do not have any
> metrics on just how large this table could potentially become within the
> course of a single session.
>
>
Well, current requirements are either no compression (HTTP/1), or use a
encoder-defined amount of memory at the decoder (gzip in SPDY).
The idea here with delta is to give the decoder more keys to the castle--
the decoder (not the encoder!) dictates how much state it is willing to
maintain and the encoder must stick within that. It wouldn't be too hard to
bolt this onto any compression scheme, probably.

As an encoder, you always have the option of using no state for encoding,
so all the other side can dictate is the maximum state you can use.

-=R

> 2. B needs to notify A that the compression context needs to be reset. If
> A gets that message before is constructs the second message, all is fine, A

---

From: James M Snell <[email-masked]>
Date: Thu, 17 Jan 2013 09:21:11 -0800

My main concerns with this approach are (a) even tho the decoder gets to
set limits on the amount of state used, keeping that state around is still
relatively expensive compared to what we have now, and (b) keeping it in
sync with the client, server and any number of intermediaries along the
path is likely going to prove difficult at best. We need to make sure we
have a good understanding of the worst case scenario with this approach
(i.e. nothing stored in context anywhere along the path).

The other concern is that this compression context would likely end up
storing potentially sensitive information for an indefinite period of time.
WWW-Authenticate and Cookie headers, API Keys, etc would all end up being
stored with (currently) no guarantees about security. Always using erefs
for those would headers would work but the current description you have
rules out user-agent use of erefs [1]. If I'm passing secure credentials
around in a header, I don't want those stored anywhere, especially on
intermediaries.

  [1]
http://tools.ietf.org/html/draft-rpeon-httpbis-header-compression-00#section-4

- James

On Wed, Jan 16, 2013 at 5:39 PM, Roberto Peon <[email-masked]> wrote:

>> B receives this message from A and forwards it on to C. C initializes
>> it's local copy of the compression context, storing the appropriate values.
>> This table has to be maintained from request-to-request, keeping header
>> values stored. The table on C becomes:
>>
>>   ID | Name | Value
>>  ----+------+-------
>>    1 | Foo  | A
>>    2 | Bar  |
>>    3 | Bar  | B
>>    4 | Bar  | C
>>
>> B forwards this message on to C, which updates the context. The table on
>> C becomes:
>>
>>   ID | Name | Value
>>  ----+------+-------
>>    1 | Foo  | A
>>    2 | Bar  |
>>    3 | Bar  | B
>>    4 | Bar  | C
>>    5 | Bar  | D
>>

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 11:49:39 -0600

On Thu, Jan 17, 2013 at 11:21 AM, James M Snell <[email-masked]> wrote:
> My main concerns with this approach are (a) even tho the decoder gets to set
> limits on the amount of state used, keeping that state around is still
> sync with the client, server and any number of intermediaries along the path
> is likely going to prove difficult at best. We need to make sure we have a
> good understanding of the worst case scenario with this approach (i.e.
> nothing stored in context anywhere along the path).

If the compression is hop-by-hop then there's no synchronization
issues.  But then middleboxes may have to decompress and always
re-compress (even if the headers are left unmodified) in each
direction.

In general I'd much rather not have connection-oriented state at all,
not even if it were transparent to HTTP.

Nico
--

---

From: James M Snell <[email-masked]>
Date: Thu, 17 Jan 2013 09:56:55 -0800

On Thu, Jan 17, 2013 at 9:49 AM, Nico Williams <[email-masked]>wrote:

> set
> path
That's the exact problem I'm having really. Middleboxes will be required to
maintain a complete compression state (for requests and responses) as
opposed to just passing things through. Maintaining that state could become
quite expensive. If we don't maintain it, tho, the potential sync issues
become too messy.

> not even if it were transparent to HTTP.
Agreed, not sure how to avoid it and still get good compression (outside of
simply optimizing the encoding of values as much as possible... i.e. bohe)

- James

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 12:46:54 -0600

On Jan 17, 2013 11:57 AM, "James M Snell" <[email-masked]> wrote:
> That's the exact problem I'm having really. Middleboxes will be required
to maintain a complete compression state (for requests and responses) as
opposed to just passing things through. Maintaining that state could become
quite expensive. If we don't maintain it, tho, the potential sync issues
become too messy.

Right, if you want to do dreadful compression then middleboxes will have to
be stateful.

> Agreed, not sure how to avoid it and still get good compression (outside
of simply optimizing the encoding of values as much as possible... i.e.
bohe)

I'd rather do the architecturally-clean thing: optimize encodings.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 12:47:45 -0600

s/dreadful/stateful/.  swype

---

From: Martin Thomson <[email-masked]>
Date: Thu, 17 Jan 2013 11:36:49 -0800

On 17 January 2013 10:47, Nico Williams <[email-masked]> wrote:
> s/dreadful/stateful/.

Roughly equivalent anyway.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Jan 2013 11:59:22 -0800

With delta, if you set compression state size to zero, all you get is
encoding.

-=R

---

From: James M Snell <[email-masked]>
Date: Thu, 17 Jan 2013 11:59:54 -0800

> quite expensive. If we don't maintain it, tho, the potential sync issues

Correction on this (the bits thankfully just kind of snapped together in my
brain finally)... a middlebox would have separate decompression and
compression contexts for each request and response and would translate
between the two. If it receives a kvsto, it can choose not to store
anything and pass those along as kvsto or eref, getting by without storing
any of the actual values, but still having to maintain some amount of state
for the translation to occur. So that part (finally) clicked in my head
correctly but we still need to make sure we have a solid sense of just how
expensive maintaining that context is going to be (best and worst cases).

- James

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Jan 2013 12:25:38 -0800

Correct. :)
-=R

On Thu, Jan 17, 2013 at 11:59 AM, James M Snell <[email-masked]> wrote:

> Correction on this (the bits thankfully just kind of snapped together in
> my brain finally)... a middlebox would have separate decompression and

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 14:45:12 -0600

Note that in general compression won't do better than minimal
encodings of header names and values.  I say "in general" because, as
we saw in the minimal date/time discussion, we can sometimes further
compress relative to some state (e.g., normalizing time to a newer
epoch), but even so, generic compression algorithms won't figure out
such things.

Therefore it seems best to focus on minimal encodings.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Jan 2013 12:52:00 -0800

Can you support that with data? The data I've seen thusfar strongly
disproves that assertion...

-=R

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 15:19:08 -0600

> disproves that assertion...

No need: it follows from basic information theory that a generic
compression algorithm cannot do better than a minimal encoding of the
same data.  The key is that the encoding has to be truly minimal,
otherwise all bets are off.

Of course, the encoding may not really be always minimal.  A varint
encoding of seconds since epoch is not minimal if the epoch is far in
the past, but resetting the epoch has its costs, and gzip and friends
won't know anything about that, -- in time a datetime encoding like
seconds-since-epoch will become less than minimal.

We probably cannot get truly minimal encodings of everything we care
about, but as we saw with the datetime encoding/compression
sub-thread, in some cases we can do much better than generic encoding.
 The thing about generic compression is that it has to look for
repeating patterns, but some patterns are hard to detect, and
dictionaries add overhead, which is why we stand a very good chance of
doing at least a satisfactory job with minimal encodings.  And if we
can avoid long-term per-connection compression state then that's a big
architectural win.  It doesn't have to be the case that we compress
better this way than the other, just well enough.

Nico
--

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 18 Jan 2013 08:33:21 +1100

> better this way than the other, just well enough.

The problem is that the biggest part of our target data is often opaque blobs -- in the forms of cookies, ETags, request URIs and referers. A "minimal encoding" of a cookie, as currently defined, isn't going to save us much at all.

Cheers,

--
Mark Nottingham   http://www.mnot.net/

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Jan 2013 13:35:24 -0800

Here are where my doubts stem from:

"Custom" keys and values (cookies, user-agent strings, etc) are added to
headers and repeated basically all the time. If we don't know the input a
priori, we cannot construct a perfect or minimal encoding.

Lets assume we do know about all of the possible header keys and values at
the time we create the spec.
Even then, we achieve something better than stateful compression only when
the sum-total of allowed permutations is less than the amount of bits you
need to toggle the visibility on a piece of state (which is very small
indeed).
-=R

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 15:40:23 -0600

> The problem is that the biggest part of our target data is often opaque blobs -- in the forms of cookies, ETags, request URIs and referers. A "minimal encoding" of a cookie, as currently defined, i…

Cookies won't compress; servers that set them should make sure they
are already minimal.

I get the rest.  URIs may not compress well at all without reference
to larger compression state, and that may have to be something we have
to live with.  Can we?

---

From: James M Snell <[email-masked]>
Date: Thu, 17 Jan 2013 13:44:42 -0800

> need to toggle the visibility on a piece of state (which is very small

We certainly cannot come up with optimized binary encodings for everything
but we can get a good ways down the road optimizing the parts we do know
about. We've already seen, for instance, that date headers can be optimized
significantly; and the separation of individual cookie crumbs allows us to
keep from having to resend the entire cookie whenever just one small part
changes. I'm certain there are other optimizations we can make without
feeling like we have to find encodings for everything.

- James

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 17 Jan 2013 22:51:48 +0100

> feeling like we have to find encodings for everything.

Yes indeed, have referrers relative to URI for example allows stateless
reduction in many cases (but not all) for pages composed of many objects.

Using single-byte for most well-known content types allows Accept to
send shorter lists.

Someone posted the WAP spec a few months ago, it was very useful because
all the research we're talking about was already done there. Even if it
needs some refreshing, the basic concepts of the web and the relation
between headers and their usual subsets of values generally remains.

Regards,
Willy

---

From: "Adrien W. de Croy" <[email-masked]>
Date: Thu, 17 Jan 2013 21:52:27 +0000

------ Original Message ------
From: "James M Snell" <[email-masked]>

>>>Let's assume that the connection between B and C dies before that 
>>>second request is sent to B, causing the compression context shared 
>>>between B and C to be reset and lost. Suddenly the delta encoding in 
>>>the second message becomes invalid, even though nothing has 
>>>interrupted the connection between A and B.
>>>
>>>B and C need to have some way of reestablishing the compression 
>>>context after their connection is reestablished or the second message 
>>>just becomes nonsense.
>>>
>>>(relative to current requirements). Once the connection is 
>>>re-established, B would then translate the delta-encoding in the 
>>>second message to initialize the reconstructed context on C. We 
>>>currently do not have any metrics on just how large this table could 
>>>potentially become within the course of a single session.
>>>
>>
>>Well, current requirements are either no compression (HTTP/1), or use 
>>a encoder-defined amount of memory at the decoder (gzip in SPDY).
>>The idea here with delta is to give the decoder more keys to the 
>>castle-- the decoder (not the encoder!) dictates how much state it is 
>>willing to maintain and the encoder must stick within that. It 
>>wouldn't be too hard to bolt this onto any compression scheme, 
>>probably.
>>
>>As an encoder, you always have the option of using no state for 
>>encoding, so all the other side can dictate is the maximum state you 
>>can use.
>>
>>-=R
>>
>>>2. B needs to notify A that the compression context needs to be 
>>>reset. If A gets that message before is constructs the second 
>>>message, all is fine, A would just treat it like the initial 
>>>response. If A already in the process of sending that message to B, B 
>>>is going to have to reject it or put it on hold until the context is 
>>>reconstructed... in which case B is going to need some way of knowing 
>>>whether the message needs to be rejected. Also, there is a risk of 
>>>too many reset messages being sent, causing a lot of churn.
>>>
>>>3. B assigns a compression buffer window size of 0, effectively 
>>>disabling the stored compression context (every message effectively 
>>>becomes an initial message). The risk here is that a proxy might 
>>>defensively always send a 0.
>>>

why not just get B to tell A that C went down.

Push the problem back to the client is the obvious boot-strap option.  
It already has all the data.

Adrien

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Jan 2013 14:00:03 -0800

I don't believe you'll find an argument that finding a good or optimal
encoding is a bad thing.

So, lets do that part. We know about a few proposals for that already:
Delta, bohe, wap, etc.

I do disagree that good encoding is sufficient. Breaking things into
crumbs, for instance, still requires state at any entity that wishes to
understand the content. If you don't wish to understand the content, then
you obviously don't need to keep state.
Proxies and end-users often have competing motivations-- the end-user often
cares most about latency, the proxy about throughput. The idea here is
that, by allowing the decoder to control how much state the encoder uses,
at worst you collapse to just using the encodings. If that is slow and the
users/customers complain, then you increase the state size from zero so as
to decrease latency.

-=R

On Thu, Jan 17, 2013 at 1:44 PM, James M Snell <[email-masked]> wrote:

> nnot come up with optimized binary encodings for everything but we can get
> a good ways down the road optimizing the parts we do know about. We've
> already seen, for instance, that date headers can be optimized
> significantly; and the sepa

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Jan 2013 16:16:55 -0600

> feeling like we have to find encodings for everything.

The only way cookie compression can work is by having connection
state.  But often the whole point of cookies is to not store state on
the server but on the client.

The more state we associate with connections the more pressure there
will be to close connections sooner and then we'll have to establish
new connections, build new compression state, and then have it torn
down again.  Fast TCP can help w.r.t. reconnect overhead, but that's
about it.

We need to do more than measure compression ratios.  We need to
measure state size and performance impact on fully-loaded middleboxes.
 We need to measure the full impact of compression on the user
experience.  A fabulous compression ratio might nonetheless spell doom
for the user experience and thence the protocol.  If we take the wrong
measures we risk failure for the new protocol, and we may not try
again for a long time.

Also, with respect to some of those items we cannot encode minimally
(cookies, URIs, ...): their size is really in the hands of the
entities that create them -- let *them* worry about compression.  That
might cause some pressure to create shorter, less-meaningful URIs,
but... we're already there anyways.

Nico
--

---

From: James M Snell <[email-masked]>
Date: Thu, 17 Jan 2013 15:32:06 -0800

Agreed on all points. At this point I'm turning my attention towards
identifying all of the specific headers we can safely and successfully
provide optimized binary encodings for. The rest will be left as is. The
existing bohe draft defines an encoding structure for the list of headers
themselves, I will likely drop that and focus solely on the representation
of the header values for now. My goal is to have an updated draft done in
time for the upcoming interim meeting.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 18 Jan 2013 13:50:02 +0000

I agree that finding optimized binary encodings for headers will help us reducing the size of the data transmitted.

At the same time, stateful information is also very useful when transmitting a set of successive messages. It allows encoding a header as a reference to another header present in a previous message.

In my experiments, I tried to devise a binary encoding for the Accept header. However, I found that I was not able to reach the compression ratio obtained by using references to previous messages. Currently, in a set of requests to get a full web page, the Accept header will take 4 or 5 different values. This allows for the stateful compression to be very efficient.

The drawback of stateful compression is that this state must be stored. I understand that this can be a critical problem for intermediaries. I think that we should work for minimizing the amount of state an intermediary has to store for each connection. I was also wondering if anyone had some rough figure of what would be acceptable by an intermediary.

Hervé.

> -----Original Message-----
> From: James M Snell [mailto:[email-masked]]
> Sent: vendredi 18 janvier 2013 00:32
> To: Nico Williams
> Cc: Roberto Peon; [email-masked]
> Subject: Re: delta encoding and state management
> 
> identifying all of the specific headers we can safely and successfully provide
> optimized binary encodings for. The rest will be left as is. The existing bohe
> draft defines an encoding structure for the list of headers themselves, I will
> likely drop that and focus solely on the representation of the header values
> for now. My goal is to have an updated draft done in time for the upcoming
> interim meeting.
> 
>

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 20 Jan 2013 10:48:36 +1100

Indeed. You can see this in the results for the simple compressor, which just keeps the previous set of headers on the connection as state. 

It's not as efficient as delta or gzip, but the numbers aren't bad (actually, much better than I reported in my blog post, due to a bug in the test runner which is fixed in my refactor branch), and the amount of state (and complexity!) is bounded.

---

From: William Chan (陈智昌) <[email-masked]>
Date: Tue, 22 Jan 2013 12:33:37 -0800

I think all this optimized encoding work is good for all the
aforementioned reasons. I also hear that people want to reduce
connection state. That makes sense. I know that Roberto also said that
he doesn't believe encoding is sufficient, and I agree. The question
is, at what point do the wins of stateful compression outweigh the
costs?

>From the SPDY whitepaper
(http://www.chromium.org/spdy/spdy-whitepaper), we note that:
"Header compression resulted in an ~88% reduction in the size of
request headers and an ~85% reduction in the size of response headers.
On the lower-bandwidth DSL link, in which the upload link is only 375
Kbps, request header compression in particular, led to significant
page load time improvements for certain sites (i.e. those that issued
large number of resource requests). We found a reduction of 45 - 1142
ms in page load time simply due to header compression."

That result was using gzip compression, but I don't really think
there's a huge difference in PLT between stateful compression
algorithms. That you use stateful compression at all is the biggest
win, since as Mark already noted, big chunks of the headers are
repeated opaque blobs. And I think the wins will only be greater in
bandwidth constrained devices like mobile. I think this brings us back
to the question, at what point do the wins of stateful compression
outweigh the costs? Are implementers satisfied with the rough order of
costs of stateful compression of algorithms like the delta encoding or
simple compression?

>> but... we're already there anyways.

Unless I missed something, this is not new pressure, right? I don't
think it's worked well so far, as evidenced by the current situation
(the existing sizes of headers as noted by the SPDY whitepaper)...but
perhaps you have evidence to the contrary?

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 22 Jan 2013 22:27:48 +0100

Hi William,

> costs of stateful compression of algorithms like the delta encoding or

I agree that most of the header overhead is from repeated headers.
In fact, most of the requests we see for large pages with 100 objects
contain many similar headers. I could be wrong, but I think that browsers
are aware about the fact that they're fetching many objects at once in
most situations (eg: images on an inline catalogue).

Thus maybe we should think a different way : initially the web was
designed to retrieve one object at a time and it made sense to have
one request, one response. Now we have much more contents and we
want many objects at once to load a page. Why now define that as the
standard way to load pages and bring in the ability to load *groups*
of objects ?

We could then send a request for several objects at once, all using
the same (encoded) headers, plus maybe additional per-object headers.
The smallest group is one object and works like today. But when you
need 10 images, 3 CSS and 2 JS, maybe it makes sense to send 1,2 or
3 requests only. We would also probably find it useful to define
a base for common objects.

We could then see requests like this :

    group 1
       header fields ...
       base http://static.example.com/images/articles/20130122/
       req1: GET corner-left.jpg
       req2: GET corner-right.jpg
       req3: GET center-banner.jpg
       req4: GET company-logo.png

etc...

Another big benefit I'm seeing there is that it's easy to switch from 1.1
to/from this encoding. And also intermediaries and servers will process
much less requests because they don't have to revalidate all headers each
time. The Host header would only be validated/rewritten once per group.
Cookies would be matched once per group, etc...

It would be processed exactly like pipelining, with responses delivered
in the same order as the requests. Intermediaries could even split that
into multiple streams to forward some of them to some servers and other
ones to other servers. Having the header fields and base URI before the
requests makes that easy because once they're passed, you can read all
requests as they come without the need to additionally buffer.

When you have an ETag or a date for an object, its I-M-S/I-N-M values
would be passed along with the requests and not the group.

I think this should often be more efficient than brute compression and
still probably compatible with it.

What do you think ?

Willy

---

From: William Chan (陈智昌) <[email-masked]>
Date: Tue, 22 Jan 2013 13:48:42 -0800

> still probably compatible with it.

This is an intriguing counterproposal. Perhaps we should fork the
thread to discuss it? I'd still like to get an answer here about what
folks think about the acceptability of the rough costs of stateful
compression.

One issue I see in this proposal is that, as always, it is difficult
to predict the future. You don't know when you're parsing the document
when you'll discover a new resource to request. How long do you delay
the resource request in order to consolidate requests into a load
group? The same thing is even more true for response headers.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 22 Jan 2013 13:51:29 -0800

You've described server push+stateful compression (delta) pretty closely
there ('cause that is what we get when we combine them, without requiring
web page writers to change how they write their pages...)! :)

With server push, you can do one request, many responses (except that you
can also cache and cancel and prioritize them, unlike bundling or inlining
or pipelining, which has nasty head-of-line blocking and infinite buffering
requirements... bleh).
With the delta compressor, you can define 'header groups', which allow you
to do exactly what you just described. The default implementation as it
exists today just guesses at the groupings by examining the hostname, but
that is a very naive approach-- splitting based on cookies and other
repeated fields makes the most sense.

The biggest hurdle, at least in my opinion, to usage of the new features is
how much effort the content writers have to put in to change their content
(basically never happens), or change their knowledge of the best practices
(also difficult :( ). The best solution (again in my opinion), is one where
the optimizations can be done automatically (while not necessarily
perfectly, close enough :) ) are, thus freeing ourselves from both
categories...

-=R

---

From: Roberto Peon <[email-masked]>
Date: Tue, 22 Jan 2013 13:54:18 -0800

The thing that isn't in delta, etc. already is the idea of 'rooting' the
path space with the single request (which I like, but... it is subject to
the CRIME exploit if path-prefix grouping is done automatically by the
browser (instead of being defined by the content-developer)).

IF we take your proposal for eliminating much of the common-path prefix and
ensure that it isn't subject to CRIME, that is a winner in any scheme.
-=R

On Tue, Jan 22, 2013 at 1:51 PM, Roberto Peon <[email-masked]> wrote:

> The biggest hurdle, at least in my opinion, to usage of the new features
> is how much effort the content writers have to put in to change their
> content (basically never happens), or change their knowledge of the best
> practices (also difficult :( ). The best solution (again in my opinion), is
> one where the optimizations can be done automatically (while not
> necessarily perfectly, close enough :) ) are, thus freeing ourselves from
> both categories...
>
> -=R
>
>

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 22 Jan 2013 23:29:45 +0100

> browser (instead of being defined by the content-developer)).

I think that if the path-prefix only contains complete path components (not
just some chars), then we're fine with the CRIME attack because in order to
make the browser merge requests, the attacker has to brute-force each path
component's name. Also, as long as it remains a path, it doesn't unveil what
is located behind, which generally contains the most interesting stuff.

> ensure that it isn't subject to CRIME, that is a winner in any scheme.

Let's face it, the CRIME attack is against optimizations for redundant
elements. We probably need to spend more time analysing all the failures
involved in the attack itself than refraining from optimizing redundancy.
I mean, how a forged request from an attacker slips in the middle of valid
requests and how we can prevent it from being merged, or at least have it
in its own group.

Willy

---

From: Roberto Peon <[email-masked]>
Date: Tue, 22 Jan 2013 14:33:59 -0800

Yup. There might be some modicum of safety in there if the path prefix for
a group never changes once defined, and it was impossible for an attacker
to define a group and include elements from something else in it, but it is
definitely the kind of thing that tickles my funnybone and makes me run to
security folks :)
-=R

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 22 Jan 2013 23:46:46 +0100

On Tue, Jan 22, 2013 at 01:48:42PM -0800, William Chan (?????????) wrote:
> thread to discuss it?

maybe, yes.

> I'd still like to get an answer here about what

It's hard to get opinions on what is considered as "heavy", it depends
a lot on what you're doing. In haproxy we default to 2*16kB of buffers
plus around 1 kB of state per connection. Some people are already
pressuring me to get rid of the 2*16kB for websocket connections so
that they don't need 32 GB of RAM per million connection.

And I know other contexts where completely buffering a 5 MB POST request
before passing it to a server is considered fairly acceptable.

One of the issue comes from the fact that no limit is suggested for how
large a request can be, and due to this we generally have to allocate
large amounts of resources "just in case". This is what is problematic
with whatever is stateful. However, I do think that being able to buffer
a full request will be acceptable for any agent (client, intermediary,
server), because all of them have to see the full request at least once,
and its buffers are adequately sized for this. If part of this request
is reused for next requests, there is no need for allocating more memory
and it's a win at the same time.

What is difficult to judge is how much we need to store for compression
states which have to be stored in addition to the request itself. As a
rule of thumb, I'd guess that doubling the whole state is quite annoying
but still manageable.

> when you'll discover a new resource to request.

I don't understand what you mean here.

> How long do you delay

I never want to delay anything, delays only do bad things when we
try to reduce latency.

In the example I proposed, the recipient receives the full headers
block, then from that point, all requests reuse the same headers
and can be processed immediately (just like pipelining in fact).

Concerning response headers, I'd say that you emit a first response
group with the headers from the first response, followed by the
response. When another response comes in, you have two possibilities,
either it shares the same headers and you can add a response to the
existing group, or it does not and you open a new group.

But that said, I would not spend too much energy trying to optimize
response headers. Right now they're commonly less important because
often accompanied with data and also because the downstream link
generally is much bigger than the upstream one. Still that's not
something to ditch either.

Regards,
Willy

---

From: William Chan (陈智昌) <[email-masked]>
Date: Tue, 22 Jan 2013 15:08:08 -0800

> I never want to delay anything, delays only do bad things when we

One of us has the wrong mental model for how the proposal would work.
Let's figure this out.

Let's say the browser requests foo.html. It receives a response packet
for foo.html, referencing 1.js. 5ms later, it receives packet 2 for
foo.html which references 2.js. 5ms it receives packet 3 for foo.html
which references 3.js. And so on. You say no delays. So does this mean
each "group" only includes one object each time?

And now let's ignore the 5ms delays. Consider how WebKit works. Let's
say WebKit has all of foo.html. It starts parsing it. It encounters
1.js. It immediately sends the resource request to the network stack.
It hasn't parsed the full document yet, so it doesn't know if it'll
encounter any more resources. Each time it encounters a resource while
parsing the document, it will send it to the network stack (in
Chromium and latest versions of Safari, this is a separate process).
What is the network stack to do if, as you say, it should never delay
anything? If I understand correctly, each "group" would always only
include one object then.

> existing group, or it does not and you open a new group.

Wait, is this the critical misunderstanding? Are you maintaining state
across requests and responses? Isn't this a minor modification on the
"simple" compressor? I was assuming you were trying to be stateless.

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 23 Jan 2013 01:00:18 +0100

> each "group" only includes one object each time?

Ah OK I didn't understand. My assumption was that browsers do have a list
of objects to be fetched, but with what you're explaining, it might not
always be true. Anyway the principle I proposed suggested that all subsequent
requests remain in the same group until a new group is emitted, so that
should cover the need for new objects that are discovered one at a time.
However, I do think (but may be wrong) that objects are not often scheduled
to go on the wire one at a time, but that when many objects appear in the
contents, many of them are seen together.

> Chromium and latest versions of Safari, this is a separate process).

I must say I'm a bit shocked by this behaviour which is very inefficient
from a TCP point of view. This means you have two possibilities for sending
your requests then :
  - either you keep Nagle enabled and your requests wait in the kernel's stack
    for some time (typically 40 ms) before leaving, even if the request is
    the last one ;

  - or you disable Nagle to force them to leave immediately, but then each
    request leaves with a TCP push flag, and then your TCP stack will not
    send anything else over the same socket for a full RTT (until its pending
    data are ACKed), which is worse.

This is why we generally try to fill packets over the wire as much as
possible. An alternative consists in opening many connections but this
is not efficient either then (RTTs, upstream packets).

So in practice I suspect that you already send requests with Nagle enabled
and disable it when you reach the end of the page, so that whatever can leave
is delayed at most 40ms and never more than the time to parse the whole page.
If this is the case, then you already have your requests delayed by as much
as 40ms and sent as groups.

> anything? If I understand correctly, each "group" would always only

I did not understand you meant delay between objects while parsing, I
thought you meant delay between groups.

Here you're limited by TCP. If you push too fast, you have to wait one RTT
between requests. If you ask the kernel to disable quick ACK or if you keep
NAGLE enabled (using TCP_CORK, MSG_MORE, etc...), your requests will
automatically leave between 40 and 200ms even if incomplete (far too much).

However, considering that only incomplete packets will remain pending
for the time it takes to parse the page and will leave anyway if it takes
longer than that, I think it remains optimal to feed the kernel's buffers
and let the first of the kernel or the HTML parser decide to send incomplete
segments. Otherwise you'd delay subsequent requests by an RTT in the TCP
stack.

> "simple" compressor? I was assuming you were trying to be stateless.

I'm having a hard time following you, I'm sorry. What state across requests
and responses do you mean ? The only "state" I'm talking about is the list
of common headers between the current message and the previous one in fact.
This is true both for requests and responses.

Regards,
Willy

---

From: William Chan (陈智昌) <[email-masked]>
Date: Tue, 22 Jan 2013 16:51:29 -0800

>     data are ACKed), which is worse.

We disable Nagle on our sockets. I must be missing something. Why
would the TCP stack only send one packet per roundtrip when you
disable Nagle? I do not believe TCP stacks only allow one packet's
worth of unack'd data.

> as 40ms and sent as groups.

No. See https://code.google.com/searchframe#OAMlx_jo-ck/src/net/socket/tcp_client_socket_win.cc&exact_package=chromium&q=nagle&type=cs&l=117.

> thought you meant delay between groups.

Indeed, there's a delay between objects. There must be. As previously
stated, we have no means of predicting the future. We do not know that
there are more objects in the document yet to be parsed. When we
encounter an object during parsing, we request it immediately.

> This is true both for requests and responses.

Yes, this is what I refer to as "simple" compression, as coined by
Mark (see http://www.mnot.net/blog/2013/01/04/http2_header_compression):
"""
“simple” - Omitting headers repeated from the last message, tokenising
common field names, and a few other tweaks. Otherwise, it looks like
HTTP/1.
"""

I consider this a form of stateful compression. If you are fine with
that, then great, I think we've made significant progress in our
discussions here, and it's a good starting point for discussing
connection state requirements.

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 23 Jan 2013 08:33:57 +0100

> disable Nagle? I do not believe TCP stacks only allow one packet's

I'm sorry William, I was wrong. I had memories from debugging a TCP stack
on a mobile network where each PUSH caused a stall waiting for an RTT,
which we attributed to the way they used nagle with the Minshall's
modification which consists in waiting for all small packets to be ACKed.
But this does not apply when NODELAY is set :

>From linux:net/ipv4/tcp_output.c:

    /* Return false, if packet can be sent now without violation Nagle's rules:
     * 1. It is full sized.
     * 2. Or it contains FIN. (already checked by caller)
     * 3. Or TCP_CORK is not set, and TCP_NODELAY is set.
     * 4. Or TCP_CORK is not set, and all sent packets are ACKed.
     *    With Minshall's modification: all sent small packets are ACKed.
     */
    static inline bool tcp_nagle_check(const struct tcp_sock *tp,
                                      const struct sk_buff *skb,
                                      unsigned int mss_now, int nonagle)
    {
            return skb->len < mss_now &&
                    ((nonagle & TCP_NAGLE_CORK) ||
                     (!nonagle && tp->packets_out && tcp_minshall_check(tp)));
    }

That said, the points remains that you don't necessarily want to push many
small packets over the wire!

> encounter an object during parsing, we request it immediately.

Got it.

> ?simple? - Omitting headers repeated from the last message, tokenising

Not exactly. The difference is that if we want to compress based on what
the previous request was, we just have an optimistic compression mode
which depends a lot on how requests are ordered. If we consider that a
browser sends grouped requests, then we can hope they're much better
ordered because its job will precisely be to be smart about how to group
them (eg: take care to avoid minor header variations that are not
indispensable and which might happen from time to time without this
consideration).

> connection state requirements.

As I said, I think that if the state itself is never larger than a request
and substitutes for the request, it's not that big of a deal. What we must
absolutely avoid is to cumulate states on intermediaries (and to a less
extent, servers). But considering that part of the request will be reused
for subsequent requests might be OK. In order to avoid undesired memory
allocations, we could even state that if a request holds data, then it
must be the last one in the group so that we don't have to keep the state
when we need the space to receive a message body.

Willy

---

From: Patrick McManus <[email-masked]>
Date: Wed, 23 Jan 2013 07:55:42 -0500

On Wed, Jan 23, 2013 at 2:33 AM, Willy Tarreau <[email-masked]> wrote:

> and substitutes for the request, it's not that big of a deal.
>

I'm more comfortable saying that the cost of the state should be
proportional to any latency-scaled win it can give... honestly, the trend
in ram prices is a lot friendlier to making progress than the trend in
bw-to-latency ratio.

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 23 Jan 2013 13:19:17 +0000

Content-Type: text/plain; charset=ISO-8859-1
--------
In message <[email-masked]>
, Patrick McManus writes:

>honestly, the trend in ram prices [...]

I think both of your perspectives are too near-sighted here.

The protocol you should be working on should be the one which
still works when most middle-class homes, not only in the western
world, but also in India and China, have fibre to the home at
speeds of 1Gbit/sec and above.

In that world, a major piece of global news, be it a naked breast,
an geophysical event or a shot politician, is going to make the
traffic spikes we have seen until now look tame.

HTTP is a very assymetric usage protocol, and therefore any amount
of state that the server _has to_ retain for a client must justify
it's existence, byte for byte, against the scenario where 10% of
the world want to access the same URL.

HTTP/1 allows you to deliver content without committing any per-client
state, beyond the TCP socket, and that is not a "degraded mode",
that is the default mode.

If your HTTP/2 proposal cannot do that, you're working on the wrong
protocol.

Poul-Henning

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: Patrick McManus <[email-masked]>
Date: Wed, 23 Jan 2013 09:41:49 -0500

I'm very comfortable optimizing for poor bw:latency ratios above other
considerations. There's no other important reason to rev the protocol.

On Wed, Jan 23, 2013 at 8:19 AM, Poul-Henning Kamp <[email-masked]>wrote:

> In message <
> [email-masked]>

---

From: Benjamin Carlyle <[email-masked]>
Date: Thu, 24 Jan 2013 14:46:00 +1000

I prefer the idea of bulk messages over stateful compression, but I'm not
sure either is practical or necessary.

Stateful compression adds overhead for clients, server, and intermediaries.
It also messes with my wireshark. When I start listening mid-way through a
conversation between a client and server I cannot tell what messages are
actually being sent because the redundant headers have all been stripped
out. Unfortunate, and a practical problem I think. It makes the protocol
more difficult to work with and as bandwidth increases and RAM increases
the problem stateful compression is designed to solve goes away but the
difficulty in working with the protocol stays forever. I would rather a
workable protocol than an efficient one, especially when the efficiency
improvement is an incremental improvement over a protocol that has worked
well enough for an Internet that was more bandwidth constrained than
today's internet and will be more bandwidth-constrained than tomorrow's
Internet. If a stateful protocol is to be used it seems like you quickly
start to want p-frames or the like to enable debugging which will undo
performance improvements. I may be in an minority here.

Between the stateful compression and bulk request scenarios I would choose
the latter. Now you can argue straight up that stateful compression will
reduce bandwidth usage in more cases because it doesn't require the client
to have more than one request in its queue at any given time. It will work
even with requests spaced seconds or more apart and it will save bytes and
may also some latency. Client-side compression into a bulk request only
works when there is more than one request in the queue. However, that I
would argue is exactly when you want the compression. If there is plenty of
bandwith - enough that you only have one request in the queue at a time,
how valuable is the stateful compression? Instead, you could choose to
perform no compression until multiple requests are in the queue - that's
the signal that you are bandwidth constrained and would benefit from
compression. However if the latter is a rare case in the developed world
then I don't really see browser developers implementing the latter as they
can avoid the extra effort and just send the requests in sequence as they
always do. Unless a real use case exists for it it will become
a potentially buggy and only occasionally used feature. At least with the
latter case whether the bulk request is implemented or not my wireshark
capture started 60 seconds into the HTTP connection is able to see what
request are being made and what responses are being generated. At least
with the latter proposal the protocol does not become more difficult to
work with in a way that tooling cannot overcome.

What I want from HTTP is not to make better use of bandwidth, but to make
better use of a single TCP connection. I want to be able to send multiple
requests rapidly down the connection. I want to be able to receive
responses to those requests in whatever order they happen to be generated
by the server, and I want some degree of fairness if a big resource is
being downloaded while smaller responses are also ready to be sent. At
a minimum it should be possible to stream a whole bunch of requests across
while occasionally sending a heartbeat request message and getting a timely
heartbeat response message in some reasonable time. This would eliminate
most problems HTTP has in off-Web system integration scenarios and allow
alternative protocols to be immediately or eventually retired.

I know that's not the main target for this protocol and I appreciate the
issues around minimising latency while loading Web pages, but the less you
can break debuggability of the protocol while ensuring efficient use of a
TCP connection the better in my book.

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 24 Jan 2013 08:08:18 +0100

Hi Pat,

> in ram prices is a lot friendlier to making progress than the trend in

You don't count the trend in user count which is faster than the trend
in RAM price unfortunately. I've had several times people ask me what
to change in their kernel to go beyond 1 million concurrent connections
in haproxy. A few years ago, they were only talking about several tens
of thousands. With everything device connected to everything all the
time, I don't expect this trend to revert any time soon :-/

Willy

---

From: Patrick McManus <[email-masked]>
Date: Thu, 24 Jan 2013 09:36:04 -0500

On Wed, Jan 23, 2013 at 11:46 PM, Benjamin Carlyle <
[email-masked]> wrote:

>  as bandwidth increases[..] the problem stateful compression is designed
> to solve goes away
>

I disagree.

compression in  http/2 (stateful or otherwise) is not meant to solve a
problem with insufficient bandwidth. It is meant to address the problems
created by poor rtt:bw ratios. Those ratios only get *worse* as bandwidth
improves, because latency does not improve as quickly.

Specifically, the major problem is that the TCP congestion window is driven
by RTT. This is a particular problem on the request side of things and
compression allows you to send more requests without absorbing a RTT delay
as the congestion window grows. That RTT is the bottleneck that needs to be
solved - not the bandwidth of the pipe - and that's too bad because
bandwidth is a much easier thing to improve.

I know this has been said before - but as long as people are still talking
about bandwidth we really aren't talking about the problem that's killing
HTTP performance right now.

Stateful (I presume we are defining that as meaning state between requests)
has a good record of addressing  this by effectively removing redundant
headers (i.e. cookies which may spill the CWND all by themeslves so are an
issue with even 1 request needing to be sent) from the byte stream. I
believe this justifies its inclusion as long as it is done in a thoughtful
and reasonable way.

This is not a direct criticism of the bulk-request (BR) proposal. BR is
effectively compression as well just over a limited scope.. I'm skeptical,
but if it can show the kinds of improvements spdy did without adding
artificial waits then it should be considered.

-P

---

From: Patrick McManus <[email-masked]>
Date: Thu, 24 Jan 2013 09:50:34 -0500

> time, I don't expect this trend to revert any time soon :-/

Hey Wily,

you're a wicked smart guy with customers backed by millions of people and
resources. Your problem is a "simple" (jokingly!) matter of engineering
bigger systems.

The latency problem is inherent in the speed of light and can't be fixed in
the same way. I remain convinced that it should trump other objectives when
designing the protocol.

That being said, I'm not here arguing for RAM bloat! All I said is that if
state can be justified by an improvement against the latency problem then
it is truly justified. If another scheme can do the same with less state -
then that's more awesome!

-Patrick

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 24 Jan 2013 16:05:33 +0100

Hi Pat,

> then that's more awesome!

That's why I said that I'm not against adding *some* state. For example, even
if I would be really bothered by doubling the state size on middle boxes, it's
not always the end of the world. But it must be really justified and provide
substantial benefits. In my case, we're talking about adding few data. People
still doing pattern matching in HTTP on routers/firewalls will have a harder
time maintaining a state anyway. As time permits, I'll do my best to help
focusing on reducing costs for intermediaries (CPU and RAM) because they are
the ones making scaling possible and we must ensure we don't needlessly bloat
them.

Regards,
Willy