Some proposed spec changes for v4

[Roberto Peon]

Hello all--

As you probably know, now that much of the craziness of IO has died down, I've been working on SPDY spec changes.

My proposed changes are here:

https://github.com/grmocg/SPDY-Specification/tree/gh-pages

The HTML and TXT is generated from the XML, and the XML and HTML are kept most up-to-date.

A few things that I've ben changing:

1) Making the ascii-art more clear for implementors. It is less pretty, but it should show every field down to the bit level clearly. The notation here was meant to be similar to that given in the gzip and related RFCs.

2) Different header compression. I've put together a scheme for doing application-layer header compression. 

An example is listed in the doc, but I'll copy it here for discussion as well.

Header compression example:

Request 1 (for index.html):
SYN_STREAM 1, stream-group (G)=0
  Header-block:
  Store(0x1): level(C),index(0),k: ":method"
  Store(0x1): level(C),index(0),v: "GET"
  Store(0x1): level(C),index(1),k: ":version"
  Store(0x1): level(C),index(1),v: "HTTP/1.1"

  Store(0x1): level(C),index(2),k: "user-agent"
  Store(0x1): level(C),index(2),v: "blah blah browser version blah blah"
  Store(0x1): level(C),index(3),k: "accept-encoding"

  Store(0x1): level(C),index(3),v: "sdch, bzip, compress"
  Store(0x1): level(G),index(0),k: ":host"

  Store(0x1): level(G),index(0),v: "www.foo.com"
  Store(0x1): level(G),index(1),k: "cookie"
  Store(0x1): level(G),index(1),v: "SOMELONGSTRINGTHATISMOSTLYOPAQUE;BLAJHBLA"

  Store(0x1): level(G),index(2),k: ":path"
  Store(0x1): level(G),index(2),v: "/index.html"

  Store(0x1): level(G),index(3),k: "date"
  Store(0x1): level(G),index(3),v: "Wed Jul 18 11:50:43 2012"


At this point the connection headers table looks like this:

  0: ":method", "GET"
  1: ":version", "HTTP/1.1"

  2: "user-agent", "blah blah browser version blah blah"
  3: "accept-encoding", "sdch, bzip, compress"

The stream-group table for group zero looks like this:
  0: ":host", "www.foo.com"

  1: "cookie", "SOMELONGSTRINGHTATISMOSTLYOPAQUE;BLAJHBLA"
  2: ":path", "/index.html"

  3: "date", "Wed Jul 18 11:50:43 2012"


Request 1 (on stream 1) would look like the following if forwarded on HTTP/1.1:
  GET /index.html HTTP/1.1

  host: www.foo.com
  date: Wed Jul 18 11:50:43 2012

  cookie: SOMELONGSTRINGTHATISMOSTLYOPAQUE;BLAJHBLA
  user-agent: blah blah browser version blah blah

  accept-encoding: sdch, bzip, compress



Request 2 (for index.js):
SYN_STREAM 3, stream-group (G)=0
  Header-block:
  Store(0x1): level(G),index(2),v: "/index.js"
  Store(0x1): level(G),index(3),v: "Wed Jul 18 11:50:44 2012"


At this point the connection headers table is unchanged:

  0: ":method", "GET"
  1: ":version", "HTTP/1.1"

  2: "user-agent", "blah blah browser version blah blah"
  3: "accept-encoding", "sdch, bzip, compress"

The stream-group table for group zero looks like this:
  0: ":host", "www.foo.com"

  1: "cookie", "SOMELONGSTRINGHTATISMOSTLYOPAQUE;BLAJHBLA"
  2: ":path", "/index.js"

  3: "date", "Wed Jul 18 11:50:44 2012"
Both the path and the date have changed.


Request 2 (on stream 3) would look like the following if forwarded on HTTP/1.1:

  GET /index.js HTTP/1.1
  host: www.foo.com

  date: Wed Jul 18 11:50:44 2012
  cookie: SOMELONGSTRINGTHATISMOSTLYOPAQUE;BLAJHBLA

  user-agent: blah blah browser version blah blah
  accept-encoding: sdch, bzip, compress



Request 3 (for index.css):

SYN_STREAM 5, stream-group (G)=0
  Header-block:

  Store(0x1): level(G),index(2),v: "/index.css"
  Store(0x1): level(G),index(3),v: "Wed Jul 18 11:50:44 PDT 2012"

Connection level-headers are implied.

Stream-group level headers are implied.

For this example, using TaCo (truncate and concatenate) wasn't useful.
If the user, however, changes the cookie on the next request...


Request 3 (for somepage.html):
SYN_STREAM 5, stream-group (G)=0
  Header-block:
  Store(0x1): level(G),index(2),v: "/somepage.html"
  TaCo(0x1): level(G),index(1),v,TruncTo(40),"FOOBLA"


At this point the connection headers table remains unchanged.

  0: ":method", "GET"
  1: ":version", "HTTP/1.1"

  2: "user-agent", "blah blah browser version blah blah"
  3: "accept-encoding", "sdch, bzip, compress"

The stream-group table for group zero looks like this:
  0: ":host", "www.foo.com"

  1: "cookie", "SOMELONGSTRINGHTATISMOSTLYOPAQUE;FOOBLA"
  2: ":path", "/somepate.html"

Both the path and the date have changed.

Request 3 (on stream 5) would look like the following if forwarded on HTTP/1.1:
  GET /somepage.html HTTP/1.1
  host: www.foo.com
  date: Wed Jul 18 11:50:44 2012
  cookie: SOMELONGSTRINGTHATISMOSTLYOPAQUE;FOOBLA
  user-agent: blah blah browser version blah blah
  accept-encoding: sdch, bzip, compress

[Ryan Hamilton]

I'd love to see some data about the effectiveness of the new application-layer header compression at either reducing either bytes on the wire or cpu/memory consumption on endpoints.  It's clearly more complex, so hopefully it has commensurate savings elsewhere.  Without such data, I'm reluctant to see it enter the spec.

Cheers,

Ryan

[Roberto Peon]

Yes, yes-- you're absolutely right!

There is a reason this isn't checked into the spec. This is merely a proposed change.

The intention is to expose fully-formed ideas as soon as possible so as to be as open as possible :)

I'll be playing with it soon.

I also want comments on the rest of the changes (how the frames are portrayed in the ascii art)

-=R

[Ryan Hamilton]

Sounds great.  I can't wait to see what you come up with!

[Marcelo Fernandez]

2012/7/23 Ryan Hamilton <r...@google.com>:

> I'd love to see some data about the effectiveness of the new
> application-layer header compression at either reducing either bytes on the
> wire or cpu/memory consumption on endpoints. It's clearly more complex, so
> hopefully it has commensurate savings elsewhere. Without such data, I'm
> reluctant to see it enter the spec.

Ryan,

On the compression effectiveness topic, Roberto's spec says [1]: "It
is expected that this scheme will achieve similar compression to the
algorithm available in previous versions of SPDY for most requests,
though the first request may be larger."

So, after taking a very quick glance of it, seems there's no new
compression gains, but setting a new hierarchical order (Connection
and Group headers), in order to reduce header overhead.

[1] https://github.com/grmocg/SPDY-Specification/blob/gh-pages/draft-mbelshe-httpbis-spdy-00.txt#L1541

Regards
--
Marcelo F. Fernández
Buenos Aires, Argentina
Lic. en Sistemas de Información

E-Mail: ferna...@gmail.com
Web Site: http://www.marcelofernandez.info
Twitter: @fidelfernandez

[Roberto Peon]

There would likely be some gains, but the question is one of tradeoffs-- this is more complicated and requires state tracking. Is the change in CPU cost/memory cost and compression gains worth the change?

-=R

[Jim Roskind]

IMO, two of the most critical items to discuss in a compression algorithm are:

a) What gets added, and where/when, to the compression state?

b) What gets discarded, and when, from the compression state?

Re: (a):  In your example, it was not at all clear to me how/why some keys (and associated values) were targeted at the "connection" vs "stream" group context, and why.  To be fair, I see that *you* made the decision, but it is not clear how this is automagically done in a more general context that scales into the future, and competes well with the adaptivity of gzip.

Re: (b): It was not clear how/when these entries got discarded (your example above didn't get that far).  I think I saw stuff about state not exceeding some total size, but don't recall seeing LRU discard, vs some use-count discard, vs etc. etc.

If we have any hope of "comparing" algorithms, it is critical to explain an algorithm at such a level of detail.  

From my experience (playfully, though for an extended period of time) writing and evaluating compression algorithms, the best way to nail such stuff is to try it out, and iterate rapidly (compressors often surprised me).

Your approach seems very plausible (could be reasonably competitive compression)... but IMO the above details are more critical than the state-accesses shown in your example, at least for evaluating effectiveness and doing a comparison.

Jim

p.s., If you had plans for automagically dividing data among several distinct contexts (as suggested above), the obvious question would be: How would gzip work given such pre-division across multiple contexts?

[Roberto Peon]

With the approach outlined in the proposal, the gzip compressor would be mostly useful in finding and compressing self-similar repetitions for individual long values, e.g. cookies, and so probably doesn't need differentiation like the stream-groups do at the line level, so we'd still use just one.

I'm writing the (toy) compressor and decompressor in python now so we (all) can play with it.

I could have chosen to have more operators or chosen different operators. 'Insert' and 'replace' are far more general than what we currently have and would allow for "patching" into the middle of strings.

I'm wary of the effect of getting operations like insert or replace wrong w.r.t. security/buffer overruns, which I'm comparatively less worried about with the set of operators proposed right now.

In any case, thanks for the comments all. I'll be putting the python toy out there as soon as I can!

-=R

[Roberto Peon]

Here is the rudiments of the compressor for the proposed change

I haven't hooked in the gzip stuff yet, nor ensure that it will respect the various limits, but that'll come shortly, at which point I'll begin to see how effective the total compression is as compared to what we have today.

This is hacky code, but at least it isn't that long.

https://github.com/grmocg/SPDY-Specification/blob/gh-pages/headers_sample.py

[Roberto Peon]

I have the toy updated and working with gzip. It now does comparisons between spdy/3 and proposed spdy/4  frame sizes.

Amusingly, if you stick entirely to the "ERef" SPDY/4 headers opcode for everything, spdy/3 and spdy/4 yield the same result after gzip.

If you do the "smart" thing, the proposed spdy/4 stuff currently results in ever-so-slightly larger on-the-wire sizes after gzip, at least for the toy requests.

The next step is to gather some data from real sites and see how it performs.

-=R

[Hasan Khalil]

Let me get this straight (just to make sure I'm parsing this right) -- so far, the SPDY 4 changes as implemented in the 'toy' show, at best, no on-the-wire-size benefit over SPDY 3?
    -Hasan

[Mike Belshe]

If I understand the proposal - you'll get really good 2nd request compression, because its a diff from the first request.  But, because you're doing name/value level compression, rather than text-level compression, you're losing the byte-level compression of gzip.  Since gzip is able to get about 50% compression on the first request already (typically ~450B to ~250B), you'll likely lose on the first compressed request.  But, you'll likely win on the subsequent requests.

Did I misread?

I do suspect that this algorithm is pretty cheap to implement computationally and memory wise.

There is a problem with upper-bounds, however.   This is likely more theoretical than practical.  But gzip using a rolling window and has finite, bounded memory constraints.  I believe your algorithm is unbounded; so if you're churning headers, the memory bounds is infinite.  This could be problematic for proxies with long-lived connections to backends.

Mike

On Mon, Jul 23, 2012 at 11:24 AM, Roberto Peon <fe...@google.com> wrote:

[Hasan Khalil]

Regarding boundedness -- yes there's an obvious issue here, which I voiced with Roberto offline. I think that we'll need some strict bounds on the library size and that we'll need these to be configurable at runtime (say, via SETTINGS).

    -Hasan

[Roberto Peon]

Yes, the proposal defined three SETTINGS vars and defaults for bounding the total size.

Performance on a few sessions (google, bing, cnn, yahoo, amazon) seems to indicate that the dict-level compression does surprisingly well. It is typically within a factor of 2 of what we'd get with gzip (if gzip got 90% compression, (1-(1-.9)*2) the table-based approach would get 80%)

I suspect we'll get better than that with smarter compressing, this is the "naive" compressor using this opset, and is certainly not the best that could be created.

-=R