Subject: SPDY and the HTTP Binding

From: James M Snell <[email-masked]>
Date: Thu, 11 Oct 2012 10:13:33 -0700

I've been going back through the HTTP binding described in the initial SPDY
draft [1] and going through a variety of options for the header encoding
and the thought struck me.. if headers such as :version, :method and
:scheme are always going to be included in the SYN_STREAM, and these are
always going to have fairly static and well defined values, there's really
no reason at all why those should be encoded as headers in the first place
-- let's just give them fixed positions within the SYN_STREAM block..

[1] http://tools.ietf.org/html/draft-mbelshe-httpbis-spdy-00#section-2.6.1

+------------------------------------+
|1|    version    |         1        |
+------------------------------------+
|  Flags (8)  |  Length (24 bits)    |
+------------------------------------+
|X|           Stream-ID (31bits)     |
+------------------------------------+
|X| Associated-To-Stream-ID (31bits) |
+------------------------------------+
| Pri|S|Unused| Slot |M|             |
+----------------------+             |
| Number of Name/Value pairs (int32) |
+------------------------------------+
|     Length of name (int32)         |
+------------------------------------+
|           Name (string)            |
+------------------------------------+
|     Length of value  (int32)       |
+------------------------------------+
|          Value   (string)          |
+------------------------------------+
|           (repeats)                |

For one, we already have the version field in the SYN_STREAM... we
shouldn't need two separate protocol version identifiers within a single
SYN_STREAM..

This would add one single-bit flag following the priority and one
single-byte fields following the Slot.

The single-bit field following the Priority would indicate whether or not
the SYN_STREAM is secure... this is equivalent to sending
":scheme"="https". This would use up one fo the currently-unused 5-bits
that exist after the priority. (I'm not even yet convinced that this flag
is necessary at all. We might be able to drop the :scheme indicator
completely).

The one-byte field following Slot identifies the HTTP Method. Each method
would be assigned a numeric identifier (GET=0x1, PUT=0x2, etc). New methods
would be registered to get a new identifier (if a server gets a SYN_STREAM
with an unknown method identifier it's no different than if they get a
HTTP/1.1 request with an unknown method name).

Using this approach, we eliminate three special case headers (":version",
":method" and ":scheme") and save at least around 31-bytes per SYN_STREAM.

- James

---

From: William Chan (陈智昌) <[email-masked]>
Date: Thu, 11 Oct 2012 10:43:50 -0700

I don't really care to dive into this level of detail in the framing yet,
since I feel like there are plenty of other contentious high level stuff
people we'll want to settle first. That said, I'll note a few things:
* The version field in SPDY isn't very well thought out, because we weren't
sure about how we were going to communicate the version. In practice, we
always rely on TLS-NPN, so this is kinda vestigial. Just FYI for the
history for it.
* Baking in those special headers into specific fields merges the HTTP
layer into the SPDY layer. Maybe that's the right way forward for HTTP/2.0,
but we have discussed other protocols layering on top of SPDY, for which
these HTTP specific fields would be undesirable.
* Roberto's proposing a new name/value header block anyway.

Meh. I figure we can optimize the framing after we've settled what features
we want.

On Thu, Oct 11, 2012 at 10:13 AM, James M Snell <[email-masked]> wrote:

> I've been going back through the HTTP binding described in the initial
> SPDY draft [1] and going through a variety of options for the header
> encoding and the thought struck me.. if headers such as :version, :method
> and :scheme are always going to be included in the SYN_STREAM, and these
> are always going to have fairly static and well defined values, there's
> really no reason at all why those should be encoded as headers in the first
> place -- let's just give them fixed positions within the SYN_STREAM block..
>

---

From: James M Snell <[email-masked]>
Date: Thu, 11 Oct 2012 11:01:56 -0700

On Thu, Oct 11, 2012 at 10:43 AM, William Chan (陈智昌)
<[email-masked]>wrote:

> * The version field in SPDY isn't very well thought out, because we
> weren't sure about how we were going to communicate the version. In
> practice, we always rely on TLS-NPN, so this is kinda vestigial. Just FYI
> for the history for it.
>

Granted. However, it makes very little sense to have three separate version
identification mechanisms (at the TLS-NPN level, the SYN_STREAM version
field, and the :version header).

> these HTTP specific fields would be undesirable.

Granted. However, the difference really boils down to only a single
additional byte. Surely that single byte wouldn't be too difficult to
ignore in non-http cases.

> * Roberto's proposing a new name/value header block anyway.

Looking forward to seeing his suggested changes.

- James

> Meh. I figure we can optimize the framing after we've settled what
> features we want.
>
>> [1]
>> http://tools.ietf.org/html/draft-mbelshe-httpbis-spdy-00#section-2.6.1
>>

---

From: "Martin Nilsson" <[email-masked]>
Date: Thu, 11 Oct 2012 20:13:00 +0200

On Thu, 11 Oct 2012 20:01:56 +0200, James M Snell <[email-masked]>  
wrote:

>> <[email-masked]> wrote:
>> I don't really care to dive into this level of detail in the framing  
>> yet, since I feel like there are plenty of other contentious high level  
>> stuff people we'll >>want to settle first. That said, I'll note a few  
>> things:
>> practice, >>we always rely on TLS-NPN, so this is kinda vestigial. Just  
>> FYI for the history for it.
>
> Granted. However, it makes very little sense to have three separate  
> version identification mechanisms (at the TLS-NPN level, the SYN_STREAM  
> >version field, and the :version header).

I would expect to see this part completely reworked, since there are both  
syntactical and semantic issues with the current versioning system.

>> layer into the SPDY layer. Maybe that's the right way forward for  
>> HTTP/2.0, >>but we have discussed other protocols layering on top of  
>> SPDY, for which these HTTP specific fields would be undesirable.
>
> ignore in non->http cases.

Looking at it in a more high level, I certainly makes sense to build in  
mandatory fields into a fix frame structure, both to save overhead and to  
simplify looking at only those fields. The real question is if non-HTTP  
should be possible in the HTTP/2.0 structure.

/Martin Nilsson

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

---

From: Roberto Peon <[email-masked]>
Date: Thu, 11 Oct 2012 14:18:18 -0700

The version field could/should be pulled out and a better way to express
this determined.
This was original conceived as a way to allow proxies to carry multiple
different versions of SPDY simultaneously over the same connection (e.g. to
a server from multiple clients), but I've seen no support for such a
requirement in any real deployments yet, and it doesn't seem likely to
change.

I believe strongly that we don't want to corrupt the session-layer with
bits from the application-semantic layer unless we're getting significant
benefit from it.
The benefit we get from encoding scheme in bits is relatively small, and
very much not future proof-- We do send both HTTP and HTTPS over a single
SPDY connection today, and hopefully won't be limited to just these as we
don't know what the future will bring (e.g. upgrade to ws over stream?
Change of some other property? I know I can't predict it).

Given the way the compressor that I've been working on works, the "http"
and "https" schemes are already present in the initial compression seed,
thus end up being encoded in very few bits. Since it is delta-encoded, it
is also not mentioned again unless you change the scheme. This would likely
end up using fewer bits than attempting to encode it in the session-level
frames...

On the compression stuff-- I apologize for the delay in getting the
compression spec out. If all people want is a description of the
fundamentals, I can do that quickly. For now I've been concentrating on the
'working code' informing the specification, and so have been working to
ensure that the final product isn't more complex than is really required.

On that note, what is it that people want to see here w.r.t. the
compression stuff?-- Something high-level quickly, or a functional spec
proposal in 1-3 weeks?

-=R

---

From: James M Snell <[email-masked]>
Date: Thu, 11 Oct 2012 16:31:33 -0700

> Change of some other property? I know I can't predict it).
There's only so much we can and should do when it comes to "future
proofing"... and dropping the :scheme for a secure-bit does not rule out
the possibility of supporting other things in the future... it merely takes
a currently unused bit that already exists in the current framing and
assigns a meaning to it. If someone comes along in the future and wishes to
layer some as-yet-undefined-and-currently-theoretical protocol on top of
http 2.0, then they can still do so using headers. Nothing I've suggested
interferes with that.

> end up using fewer bits than attempting to encode it in the session-level

The less we need to compress the better, right? This reduces scheme and
method down to only 9 bits total and gives them a fixed location in the
syn_stream which makes processing much more efficient... e.g. we don't have
to go looking for them at arbitrary positions in an arbitrary bag of
headers.

> compression stuff?-- Something high-level quickly, or a functional spec
Yes :-) ... that is, can we have both, please :-)

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 12 Oct 2012 08:46:27 +0200

Hi Roberto,

> ensure that the final product isn't more complex than is really required.

For having lived the same experience a few months ago, I can confirm that
it is *very* hard to provide a spec or just an idea without working code,
because you need to see your compressor work in order to validate the
concept. Amos experienced the same too.

In my opinion, it would be a lot simpler that we all work on the same
code basis, each with his own fork and feedback with results and ideas.
I didn't have enough time to help Amos when he took over the job, but
I'm sure it could have gone further and faster with more help here from
other implementers.

> compression stuff?-- Something high-level quickly, or a functional spec

If you think you can already express the basic ideas and what was tested
vs what still needs to be validated, it would be a first step. But as soon
as you have some code anyone can experiment with without having to rebuild
a full browser, I think it could progress quickly.

Cheers,
Willy

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Oct 2012 00:49:47 -0700

As a warning, I do need to explicitly put the license in there for the code.
The license would be the Chromium license.

I've been checking my code into:
  https://github.com/grmocg/SPDY-Specification/tree/gh-pages/example_code

The python code, while outdated, is end-to-end. It does delta-encoding,
huffman coding, serialization, deserialization, decoding and re-inflating.
It is super-duper slow and wasn't written to test CPU performance.

The c++ code, while incomplete, gives me a much better idea of the
performance.
Currently, the not-terribly-well optimized code is happy to do ~200MB/s of
raw header into delta-encoded instructions/sec/core on my workstation and
given my dataset. In terms of HTTP requests/second I think it is on the
order of 30k/core. It will get slower once the serialization goes in (which
includes huffman coding and thus more bit-twiddling). I honestly have no
idea how much slower it may get, but am anxious to find out.

The missing pieces from the c++ code are the serialization,
deserialization, inflating.
The parts which are done are the bitbucket, huffman (including canonical
huffman), and delta-encoder.
It is missing the decoder (which is trivial) and
serialization/deserialization components, which may not be trivial,
depending on how efficient/inefficient the bitshifting operations end up
being.

Compressor unknowns/tradeoffs (a.k.a. things I intend to play with):
  *  Byte or bit alignment in various variations.
  *  Huffman coding of non-text fields (e.g. the opcodes themselves)
  *  Removal of opcodes-- instead, simply indicate the number of each type
or use a token to indicate the end of a section of the expected type. This
could save somewhere between 2-4 bits per operation, at least
pre-huffman-coded.
  *  Using different frequency tables (and thus huffman encodings) for
cookie data (unless this brings significant benefit, I'll prefer to not
have this)
  *  ID renumbering (does a referenced item get renumbered when it is used
so that consecutive items are likely to have been used together?)
  *  little-endian or big-endian, and specifically how (given that most
things today are little-endian...)
  *  implementation of proxy-pass-through-- one of the design goals here
was to allow a proxy to skip doing most of the delta or huffman encoding,
and just have to maintain a mapping between the IDs on the ingress and
egress sides for the different connection contexts. I believe it is doable,
but.. haven't done it. At the very least, since the huffman coding is
currently completely static, much can be taken without having to be
re-translated from the ingress side.
  *  providing a mechanism for the negotiation of a different huffman
encoding to be transferred. Given that a canonical huffman code is used
(ostensibly to increase decode speed), it is also easy/cheap to send one. I
haven't determined how big a savings this could be on a per-page basis.
This is something that could be done with the python code without too much
effort.
  *  modifying the instructions which create new IDs (i.e. clone and kvsto)
to not require mention of the ID which they're creating-- this is
unnecessary so long as a single ID is mentioned with the HEADERS frame--
each new ID will simple increment from there.
  *  and some more esoteric stuff.
  *  ensure that the pre-populated dictionary items never get thrown off
the LRU, since they must be maintained in memory anyway for any
server/client which uses multiple connections... it is likely that this
wouldn't incur any additional memory cost and it could increase compressor
efficiency.

The general scheme:

Delta-encoding of the headers, with the atoms being key-value pairs.
Cookie-crumbs are separated so that only the part of the cookie that
changes must be sent.

If none of the headers changed from one request to another (unlikely-- at
least the path would most of the time), then no textual information is sent.

After the delta-encoding is done, a static-huffman encoding is applied to
the text.

   - have an LRU of key, value entries.
   - the default-size for this state is 20k, or the size of the current
      header, whichever is larger.
      - the server can change this size
      - the first N-values are pre-populated with common keys and common
      values,
         - e,g. "method", "get"  - is a pre-populated entry
      - each time a particular key-value is used/referred-to, it goes to
      the front of the LRU.
      - The oldest key-value pairs (at the back of the LRU) go away if the
      state size is exceeded.
      - The LRU is updated with a small set of operations:
         - clone(key_idx, new_val):
         this adds a new key-value pair to the LRU by copying the key from
         at the key-index 'key_idx" in the LRU, and adding a new value
to it. e.g.:
         LRU: [ 0: ("method", "get") ]
         clone(0, "put") ->
         LRU [ 0:("method", "get"), 1: ("method", "put") ]
         - kvstore(new_key, new_val):
         this adds a new key-value pair to the LRU .. by inserting it at
         the end.
         e.g.:
         LRU [0:("method", "get")]
         kvstore("path", "/index.html") ->
         LRU [0:("method", "get"), 1:("path", "/index.html")]
      - have a constrained number of header-index-sets
      - a header-index-set represents an HTTP header
         - each index in the set corresponds to an entry in the LRU (by
         index)
         - each index in the set thus represents a key-value pair, one of
         the many that may compose the entirety of the headers
      - header-index-sets are modified by the encoder by putting indices
      into, or removing them from the sets.
         - the instruction do this is called 'toggle':, e.g:
           LRU [0:("method", "get"), 1:("path", "/index.html"), 2:("path",
         "/")]
           header-index-set [0: (0, 1) ]
         which represents a request like this:
           get /index.html
         If the following operations are applied:
           toggle(0, 1)  # header-index-group 0, toggle LRU index 1 off
           toggle(0, 2)  # header-index-group 0, toggle LRU index 2 on
         would cause the state to now be:
           LRU [0:("method", "get"), 1:("path", "/index.html"), 2:("path",
         "/")]
           header-index-set [0: (0, 2) ]
         and now the request would be:
           get /
      - keys and values are compressed with static-huffman codes
      - the huffman-table for request and response are different
      - the huffman-codes are canonical to improve decoding speed and to
      potentially allow for either side to publish a new huffman-code in the
      future in a space-efficient manner
      - the frequency-count for the construction of these codes was found
      by running a bunch of headers from different sites through the delta
      encoding (this is key) and computing the frequency of the letters of the
      values that *change* in the headers.
   - keys are refcounted and counted against the compression state only
   once until removed
   - keys have their own ID space so they can be referenced separately
   (e.g. in the clone operation)

There are a number of interesting things about this approach:

   1. As far as anyone can tell so far, it isn't vulnerable to the attacks
   we're seeing right now on gzip+TLS.
   2. You don't need to decode header values in order to interpret them
      1. First of all, because only changes are sent, if you're smart, you
      only have to figure out what to do with any particular header value once
      2. Since the huffman encoding is static, you just compare the encoded
      values-- no need to decode them. This can end up faster as the number of
      bytes to compare is very very likely smaller.
      3. You can choose to not do huffman encoding if you wish. This is
      necessary since, as with any entropy-compression, sometimes the encoded
      value is larger than the original.
   3. It is easy to share encoder and decoder state on either side of a
   proxy, and can be done efficiently.
      1. Any values that don't change need not be re-encoded- they can be
      blitted from ingress to egress
   4. It should be a fair bit cheaper than gzip to encode
   5. The compression achieved thusfar is competitive with gzip
      1. higher gzip window sizes will outperform the new compression
      scheme over current headers
      2. trying to be less optimal with headers results in better
      compression with gzip
      3. There is more compression to be gained over what I've gotten to so
      far..

The code hopefully makes this far more clear for those who take a gander.

-=R

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Fri, 12 Oct 2012 08:07:23 +0000

--------
In message <CAP+FsNcp7r2ad-X=2aNYq=[email-masked]>, Roberto Peon write
s:

>In terms of HTTP requests/second I think it is on the
>order of 30k/core.

This is why I think we need to do an envelope+content like format:
HTTP-routers will need to do several orders of magnitude faster
than that in a few years.

-- 
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: Roberto Peon <[email-masked]>
Date: Fri, 12 Oct 2012 01:14:50 -0700

One of the to-dos is to see how well the proxy-mode works.
The proxy doesn't have to redo delta-coding, nor does it have to huffman
code.

In any case, we'll find out with more experimentation.

-=R

On Fri, Oct 12, 2012 at 1:07 AM, Poul-Henning Kamp <[email-masked]>wrote:

> --------
> In message <CAP+FsNcp7r2ad-X=2aNYq=_
> [email-masked]>, Roberto Peon write
> s:
>

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 12 Oct 2012 10:47:04 +0200

> than that in a few years.

Not only in a few years, but already today. I have some haproxy
users who run it at 100kreq/s already. That's why I'm extremely
picky about the CPU impact of compression.

Willy

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Oct 2012 14:49:20 -0700

The most recent output, copy/pasted is:

"Delta-coding took: 0.642199 seconds for: 104300 header frames or
6.15723e-06 per header or 162411 headers/sec or 8.88429e+07 bytes/sec"

So, ~89 million bytes/second and 162k requests/second for the delta-coding
on one core. Given that most machines have more than once core, this
performance seems pretty reasonable to me, especially given that it is not
really been optimized. I'd hope that bandwidth was predominantly
entity-bodies and not headers, and so the bandwidth doesn't seem
problematic to me either.

The input data for this was a 1000 iterations over the following har files
representing full page loads:

mail.google.com.har pinterest.com-bicycle-search.har
pinterest.com-homepage.har www.amazon.com-bicycle-search.har
www.amazon.com-homepage.har www.bing.com-bicycle-search.har
www.bing.com.har www.cnn.com-homepage.har www.facebook.com-homepage.har
www.google.com-bicycle-image-search.har www.google.com-bicycle-search.har
www.google.com-homepage.har

I'd prefer to have more comprehensive test data, but this is a decent start.

-=R

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 13 Oct 2012 00:53:19 +0200

Hi Roberto,

On Fri, Oct 12, 2012 at 02:49:20PM -0700, Roberto Peon wrote:
> on one core.

It does not seem bad, and I also know that it's hard to compare numbers.
I like to count in terms of bytes per second or headers per second, but
obviously it depends on the coding scheme.

Right now I made a test on haproxy using a request to pinterest.com that
I captured from Firefox 13 (didn't know the site so I tried it). The
request looks like this, it's 282 bytes long and has 7 header fields :

  GET / HTTP/1.1
  Host: pinterest.com
  User-Agent: Mozilla/5.0 (X11; Linux i686; rv:13.0) Gecko/20100101 Firefox/13.0.1
  Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
  Accept-Language: en-us,en;q=0.5
  Accept-Encoding: gzip, deflate
  Connection: keep-alive

It was running on a single core of a core i7 2600 @3.4 GHz. I sent it 4
million times to haproxy which sent a redirect on them, and it took 3.609
seconds for the 4 million reqs, which is 1.1 million req/s, which is also
exactly the same number as it reports in the stats, and 312 MB/s. So at
first glance it's 3.5-7 times faster on a single core than the compressor
alone. So this would mean that it would spend 88% of its CPU time in the
compressor alone, and the 12% remaining doing its job.

I understand the code is not optimized yet, but this typically is the type
of thing I want us to be extremely careful about, because it's very easy
to completely kill performance for the last percent of optimization over
the wire. In fact I'm not that much worried for the 1.1-to-2.0 conversion
because as time goes, the need for this work will fade away and won't
represent most of the CPU usage. But routing and processing 2.0 to 2.0
should be optimally fast.

> Given that most machines have more than once core, this

Unfortunately my experience has often been that most of the requests
are if-modified-since and most of the responses are 304 on a number of
web sites, so we still need to be careful.

Thanks for sharing your data BTW !

Willy

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Oct 2012 15:59:55 -0700

> compressor alone, and the 12% remaining doing its job.

No, that means that a loadtest client would spend 88% of its time doing
compression. :)
Decompresion is faster, and 'recompression' is also faster, as you can
resuse much of the client's compression state, at least theoretically.

> should be optimally fast.

I know that we're coming at this from different motiviations as well-- I
suspect that most sites that are handling millions of requests/second are
perfectly happy to spend the money to get another HAProxy box in exchange
for lower client latency, if that is the tradeoff they can get, since much
of the time lower latency translates into higher conversion rates and thus
more profit.

Yup. I hope that we'll come to a useful compromise where we can get
consensus on the latency/CPU tradeoff, and vastly improve over what we've
had with SPDY thusfar.
I suspect that the best way to do that is to gather data from working code,
but I've always been biased that way :)
-=R

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 13 Oct 2012 01:11:06 +0200

> No, that means that a loadtest client would spend 88% of its time doing

:-)

> resuse much of the client's compression state, at least theoretically.

Well, responses still need to be sent to clients, so compression time
matters too. That's where I think that tokenizing must help, as it
saves the CPU from having to deal with protocols made for humans.

> of the time lower latency translates into higher conversion rates and thus

What is important in my opinion is to keep the CPU overhead low. I would have
loved to see a CPU improvement instead, but we're not there yet :-)

I think it is reasonable to expect some waste when converting 1.1 to 2.0, but
we must absolutely avoid having to explain to end users that switching from
1.1 to 2.0 will require 5 times more hardware, because even if the hardware
is cheap, managing it is not always and synchronizing states between them is
an entire new story. So there are trade-offs there too (eg: be less efficient
at fighting DDoSes).

> I hope that we'll come to a useful compromise where we can get

I think it's already better anyway because I don't remind having ever
seen zlib reach such numbers. Still the goal would be to be faster than
HTTP/1.1 :-)

> but I've always been biased that way :)

I agree with you on this.

Cheers,
Willy

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Oct 2012 16:37:33 -0700

On Fri, Oct 12, 2012 at 4:11 PM, Willy Tarreau <[email-masked]> wrote:

> > > Right now I made a test on haproxy using a request to pinterest.comthat
> > >   Accept:
> text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8

There are a couple of ways that could be fast (I don't have numbers yet).
use ERefs (ephemereal references). These don't change the compressor state,
and always require the full key-value text is sent.

A better approach would be to have the common parts of such things use
stuff that is known to exist in the LRU (e.g. the pre-defined items, which
include almost every key that I've seen, and also included many common
values). If you do redirects for a particular field enough, you could
simply ensure that you maintain a pointer to the LRU items that informs you
if it ever expires from the LRU, in which case you'd have to recreate the
sate, but otherwise you'd not even have to do a lookup... and in that case
it will be as fast as a branch and memcopy.

> loved to see a CPU improvement instead, but we're not there yet :-)

It could happen-- if the size of the requests become substantially smaller
(especially if/when people understand how to optimize for a delta-encoded
protocol), the time spent doing interpretation or doing IO also drops.
My experience running Google's edge tells me that this could be a
significant cost savings, but only time will tell if it completely offsets
the cost of the compression, etc.

-=R