Subject: Re: [hybi] Payload only compression extension, again

From: Takeshi Yoshino <[email-masked]>
Date: Thu, 7 Jul 2011 21:35:43 +0900

Here's new draft.
http://tools.ietf.org/html/draft-tyoshino-hybi-websocket-perframe-deflate-01
http://tools.ietf.org/tools/rfcdiff/rfcdiff.pyht?url1=http://tools.ietf.org/id/draft-tyoshino-hybi-websocket-perframe-deflate-00.txt&url2=http://tools.ietf.org/id/draft-tyoshino-hybi-websocket-perframe-deflate-01.txt

I've applied the change below, added some examples and changed requirement
on negotiation. Extension parameters (e.g. LZ77 window size negotiation) can
be added in future versions. Old server implementation just ignores received
extension parameters and reply with only extension token to ask the client
to fall back to old version.

Thanks,
Takeshi

On Tue, May 10, 2011 at 16:30, Takeshi Yoshino <[email-masked]> wrote:

> I can change my proposal to accept last blocks (blocks with BFINAL=1) to
> allow use of java.util.zip. In my proposal, receiver expects 3 header bits
> 0b000 (and padding to byte boundary) on the tail of the application data
> portion. Not to complicate receiver logic much, I'd make change like this
> - sender: send(<compressed data flushed with Z_FINISH> + "\x00")
> - receiver: inflate(received_data + "\x00\x00\xff\xff"). every time
> inflater encounters end of stream (the last octet of a last block), renew
> inflater and keep decompressing the remainder.
> or
> - sender: send(<compressed data flushed with Z_FINISH>)
> - receiver: inflate(received_data). every time inflater encounters end of
> stream, renew inflater and keep decompressing the remainder. if the end of
> received_data is not end of stream, inflate("\x00\x00\xff\xff").
>
> Either algorithm works for Z_SYNC_FLUSH-ed and "\x00\x00\xff\xff" stripped
> frame, too.
>
> Takeshi
>
>
>
> On Tue, May 3, 2011 at 07:52, Greg Wilkins <[email-masked]> wrote:
>
>> On 3 May 2011 08:02, John Tamplin <[email-masked]> wrote:
>> > My point was I see little value in having a compression extension which
>> > starts the compression state afresh with every frame, as on real-world
>> > applications this gives poor performance.
>>
>> +1
>>
>> My extension is more about prototyping plugable extension that work
>> well in a chain of extension, plus handling the negotiation and per
>> frame issues.    I'll follow the lead of the others/experience on the
>> exact algorithms to use (even though I think that is going to cause me
>> endless headaches with mismatched licenses and getting IP audits done
>> at eclipse :(
>>
>> cheers
>> _______________________________________________
>> hybi mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/hybi
>>
>
>

---

From: Iñaki Baz Castillo <[email-masked]>
Date: Thu, 7 Jul 2011 14:41:38 +0200

2011/7/7 Takeshi Yoshino <[email-masked]>:
> Old server implementation just ignores received extension parameters and
> reply with only extension token to ask the client to fall back to old
> version.

Hi, WS is still a draft, IMHO the specs should not include backawards
compatibility mechanisms with other revisions of the spec (while still
a draft). Maybe I miss something?

Regards.

-- 
Iñaki Baz Castillo
<[email-masked]>

---

From: John Tamplin <[email-masked]>
Date: Thu, 7 Jul 2011 10:17:23 -0400

> a draft). Maybe I miss something?

The problem is that there are deployed implementations, and breaking them
would be bad for adoption of the spec.  I agree, you don't want to clutter
up the spec with too much support for old versions, but in this case there
is very little cost.

In an ideal world, the spec would be finished before it was deployed, but
that also means not getting implementation experience back into the spec, so
there are tradeoffs both ways.

-- 
John A. Tamplin
Software Engineer (GWT), Google

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 22 Jul 2011 23:38:06 +0900

I've implemented this proposal on pywebsocket. pywebsocket's deflate-stream
implementation flushes compressed data for each frame using Z_SYNC_FLUSH.
Compression level is Z_DEFAULT_COMPRESSION. Default Huffman tree is used. No
dictionary is attached.

Here is the result of quick experiment. I exchanged some trivial text
messages with echo server and dumped occupation length on wire (strictly
speaking, occupation in TCP payload) for each frame. HyBi 07 is used.

Significant difference between deflate-stream and deflate-application-data
is
- deflate-stream cannot utilize history from previous frames' contents well
in C -> S direction due to different mask between frames

Non-significant one is
- output of deflate-stream are basically bigger than
deflate-application-data since Z_SYNC_FLUSH wastes 4 octets for each flush
operation

deflate-application-data compared to no compression
- for short messages, it just increases size because of ~2 octets for two
block headers and end of block symbol

In experiment #2, the size of deflate-stream output (C <- S) converges to 8.
This contains 5 octets and 5 bits (4 octet + 3 bit * 2 + 7 bit) for header
and Z_SYNC_FLUSH stuff. This means that the original 3 octet frame became 2
octets + 3 bits. This is the benefit of including WebSocket header to
compression target. If multiple similar frames are buffered and compressed
together at once, this benefit will be big, but I'm not sure if such case is
popular in practical use case.

----

#1: Send text frame 'a', 'b', 'c', 'd', 'e', then close

C -> S
plain:
7 7 7 7 7 8
deflate-stream:
13 13 13 13 13 15
deflate-application-data:
9 9 9 9 9 8

C <- S
plain:
3 3 3 3 3 4
deflate-stream:
9 9 9 9 9 10
deflate-application-data:
5 5 5 5 5 4

#2: Send text frame 'a', 'a', 'a', 'a', 'a', then close
C -> S
plain:
7 7 7 7 7 8
deflate-stream:
13 13 13 13 13 14
deflate-application-data:
9 9 9 9 9 8

C <- S
plain:
3 3 3 3 3 4
deflate-stream:
9 9 8 8 8 10
deflate-application-data:
5 5 5 5 5 4

#3: Send text frame 'HelloWorldWebSocketProtocol' 5 times, then close

C -> S
plain:
33 33 33 33 33 8
deflate-stream:
43 43 41 40 43 14
deflate-application-data:
35 11 10 10 10 8

C <- S
plain:
29 29 29 29 29 4
deflate-stream:
35 9 8 8 8 10
deflate-application-data:
31 7 6 6 6 4

#4: Send text frame '60b725f10c9c85c70d97880dfe8191b3'
,'3b5d5c3712955042212316173ccf37be' ,'2cd6ee2c70b0bde53fbe6cac3c8b8bb1',
'e29311f6f1bf1af907f9ef9f44b8328b', '9ffbf43126e33be52cd2bf7e01d627f9', then
close

C -> S
plain:
38 38 38 38 38 8
deflate-stream:
48 48 45 48 48 14
deflate-application-data:
40 40 39 40 38 8

C <- S
plain:
34 34 34 34 34 4
deflate-stream:
40 40 39 40 38 10
deflate-application-data:
36 36 35 36 34 4

#5: Send text frame 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
then close

C -> S
plain:
56 8
deflate-stream:
18 14
deflate-application-data:
12 8

C <- S
plain:
52 4
deflate-stream:
11 10
deflate-application-data:
8 4

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 23 Jul 2011 08:43:34 +1000

> Compression level is Z_DEFAULT_COMPRESSION. Default Huffman tree is used. No

Great - I'll make sure we have an implementation in  the next release of Jetty.

> deflate-application-data since Z_SYNC_FLUSH wastes 4 octets for each flush

I think you mean deflate-application-data frames are bigger....

> block headers and end of block symbol

Does this not suggest that we should use a reserve bit to indicate if
the frame is compressed or not?  This will allow uncompressed frames
(either because of small size or incompressible content) to be sent.

cheers

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 25 Jul 2011 15:03:42 +0900

Hi,

> I think you mean deflate-application-data frames are bigger....

yes... bad typo

> (either because of small size or incompressible content) to be sent.

Yeah. Taking 1 RSV bit, we can avoid inflation of the size for this kind of
content.

The problem is, as you and John were discussing once, how to give a good
criteria to determine if a certain content of a frame is worth compress or
not. Even if frame N is incompressible, it may be referred to deflate frame
N+1. If we don't get the frame N go through compressor, N+1 cannot refer
it. So, criteria like |compressed| < |original| don't work well. Criteria
like |original| < (some pre-specified size) are also not easy to
define. It's almost clear that for communicating 1 byte key type event,
deflate shouldn't be applied. Thinking of two byte, three byte, ... it's not
trivial. I think we cannot gather real data to define such criteria
sufficient to be put in the spec soon.

Servers can get some advice about this from application level, but user
agents don't have any way. May we ask API side to add some interface to
allow JavaScript to give some hint? Something like

attribute boolean compressOutgoing;

or, more generally

attribute DOMString extensionConfig;

to dynamically instruct the user agent.

It's also an option that we introduce COMP bit in wire spec but initially
have no API exposed for JavaScript to control that.

----

Based on granularity choices are grouped like:

- Connection-wise control: deflate-application-data or no compression
extension
- Direction-wise control: need to have two separate extension
deflate-application-data-server-to-client
deflate-application-data-client-to-server
- Message-wise control: need to have API to on/off compression

Thanks,
Takeshi

---

From: John Tamplin <[email-masked]>
Date: Mon, 25 Jul 2011 11:05:37 -0400

> allow JavaScript to give some hint? Something like

It seems unlikely to get this into the JS API anytime soon -- I think the
initial version will have to be entirely without hints from JS.

Longer term, I think you need to allow the JS code more control over
compression to get the best results, as frequently you can do much better
with domain-specific compression algorithms.  For example, chess endgame
databases get 2-3 times better compression with algorithms that know how the
index is structured.

> have no API exposed for JavaScript to control that.

That would also be useful if there were heuristics to choose when to
compress the data.

However, as long as the compression state is maintained across frames, I
don't think it is a real problem to simply compress everything.  Sure, if
someone sends random data it will get bigger, but not by much.  Even on
binary data like Quake update frames, there is substantial redundancy to be
removed via compression, so with real-world data the payload is almost never
going to get bigger by compressing.

---

From: Brodie Thiesfield <[email-masked]>
Date: Tue, 26 Jul 2011 08:46:00 +0900

> going to get bigger by compressing.

Certainly with this sort of payload that is initially being considered
normal for websocket I agree. However I expect that WS will also be
used to stream pre-compressed data to a client as well (e.g. images,
video, audio, resources in a zip at the server) for things like games.

It would also be useful if there were not heuristics to decide if the
data should be compressed or not. Often the client or server will have
external knowledge that the data will not benefit from compression,
and so having the ability to mark frames/messages as do-not-compress
is useful to allow savings of both network bytes and cpu time.

Regards,
Brodie

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 26 Jul 2011 09:56:57 +1000

> That would also be useful if there were heuristics to choose when to

Once there is a RSV bit used, then the sender can use a variety of
different strategies to determine if to compress or not.  Heuristics
is a good one and I think most server gzip filters apply simple
heuristics (eg if uncompressed is > size and if compression does not
overflow buffer of same size).   Although servers also have the
benefit of mime types (eg don't try to compress image/jpg).

> don't think it is a real problem to simply compress everything.

I think that is the simplest and best heuristic to start with, and
will probably be beneficial in the vast majority of cases.

>From the browser side of things, it may be the only practical
heuristic while the API is just simple text messages.   Perhaps when
binary messages are supported something else might do better, but
that's the benefit of using a RSV bit, as the strategy can evolve over
time without the need to update the protocol specification.

cheers

---

From: Brian <[email-masked]>
Date: Mon, 25 Jul 2011 17:56:35 -0700

FYI, the WebSocket API draft has already been updated to support binary
messages.

Brian

---

From: Takeshi Yoshino <[email-masked]>
Date: Tue, 26 Jul 2011 23:23:06 +0900

Thanks all. It seems that we'd
- add COMP bit
but for now
- leave advanced API, heuristics unspecified

And, as discussed in this thread a year ago
http://www.ietf.org/mail-archive/web/hybi/current/msg01810.html
I'm planning to add some parameters to this extension.

- Max size of LZ77 sliding window (and any other DEFLATE parameter if
useful)
-- requiring 32kB window for each connection might cause inacceptable memory
pressure for large scale system with lots of connection or embed system with
small memory
--- see the result of experiment done by spdy folk
https://spdy-dev.googlegroups.com/attach/4051c1467338d389/zlib_20100202.html?view=1&part=4
-- So, I'd add parameter "window_bits" to allow such endpoint to limit
sliding window size used by the other peer
-- if it's hard to get this negotiation into spec soon, the spec may
initially suggest some default values and limit based on these
investigation. Say, "endpoints MUST use sliding window of 2^12 or smaller".

Additionally, I'd like to propose one more parameter.

- No compression context sharing option
-- though I'm claiming that compression context sharing across frames is
good, it's sometimes harmful for intermediaries
-- for load balancers that dispatches WebSocket frames to different
backends, shared compression context means that the load balancer have to
perform decompression. it's burden in terms of both memory pressure and CPU
power.
-- So, I'd add parameter "finish_at_eof" to allow such intermediaries to ask
clients not to keep using the same compression context across frames

---

From: John Tamplin <[email-masked]>
Date: Tue, 26 Jul 2011 11:11:11 -0400

On Tue, Jul 26, 2011 at 10:23 AM, Takeshi Yoshino <[email-masked]>wrote:

> -- So, I'd add parameter "finish_at_eof" to allow such intermediaries to
> ask clients not to keep using the same compression context across frames
>

The problem is that if you don't share compression state across frames, then
it becomes critical to not try and compress incompressible content.  Look at
the experiment data I presented in that same thread -- it is very easy for
frame sizes to go up if you aren't sharing compression state, so I think if
this option is included we have to decide now how to turn off compression on
a frame-by-frame basis rather than delaying it for a future extension.  In
contrast, if compression state is maintained across frames, it is still
usually a win even on incompressible content because different frames have
redundancy, and the loss is never bad.

I would prefer, for the initial version, to simply have load balancers that
can't maintain compression state to simply refuse compression.

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Tue, 26 Jul 2011 17:25:53 +0200

* John Tamplin wrote:
>a frame-by-frame basis rather than delaying it for a future extension.

Deflate stores uncompressed data in up to 2^15 byte long blocks like

  1 byte indicating no compression and whether it's a final block
  2 byte indicating the length
  2 byte one's complement of the length
  n byte uncompressed data as per the length

Are you saying the 5 additional byte per block are a problem?
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 27 Jul 2011 12:39:01 +0900

On Wed, Jul 27, 2011 at 00:11, John Tamplin <[email-masked]> wrote:

> The problem is that if you don't share compression state across frames,
> then it becomes critical to not try and compress incompressible content.
>  Look at the experiment data I presented in that same thread -- it is very
> easy for frame sizes to go up if you aren't sharing compression state, so I
> think if this option is included we have to decide now how to turn off
> compression on a frame-by-frame basis rather than delaying it for a future
> extension.  In contrast, if compression state is maintained across frames,
> it is still usually a win even on incompressible content because different
> frames have redundancy, and the loss is never bad.
>
>
First, I'd like to make it clear that I intended to make this option one-way
property (i.e. if S included this, no shared-context in C->S direction but
allowed for C<-S direction).

I think it's still ok that clients choose to just compress everything.

With this option, service providers have two choices
1) put this option in extension response to reject shared context while
taking in the possible low efficiency you explained
2) reject compression completely

Inclusion of this parameter implies that the server-side thinks it's more
important to reject shared context than losing compression efficiency.
Looking at your experiment, for some app, there's still some gain from
frame-by-frame compression.

Without this option, they can take only 2).

That's all, I think.

---

From: Takeshi Yoshino <[email-masked]>
Date: Sat, 30 Jul 2011 01:49:53 +0900

I've conducted quick survey on zlib's memory consumption for decompress.

I injected my own alloc_func and free_func to zalloc and zfree of z_stream
to count max memory allocation on heap.

Input data is 1000000 of 10-byte long random sequences generated by rand of
stdlib. I called deflate for every 10-byte using Z_SYNC_FLUSH.

  res = deflateInit2(
      &compress_stream,
      Z_DEFAULT_COMPRESSION,
      Z_DEFLATED,
      -window_bits,
      mem_level,
      Z_DEFAULT_STRATEGY);

  res = inflateInit2(&decompress_stream, -window_bits);

deflateInit2() allocates memory as shown in this thread. deflate() never
allocates memory.
https://spdy-dev.googlegroups.com/attach/4051c1467338d389/zlib_20100202.html?view=1&part=4

window_bits=8, mem_level=1
deflateInit2: 9000, inflateInit2: 9560, inflate: 256

window_bits=8, mem_level=9
deflateInit2: 270120, inflateInit2: 9560, inflate: 256

window_bits=15, mem_level=1
deflateInit2: 138024, inflateInit2: 9560, inflate: 32768

window_bits=15, mem_level=9
deflateInit2: 399144, inflateInit2: 9560, inflate: 32768

inflateInit2()'s 9560 bytes are for inflate_state. Mainly spent for decoding
table. inflate()'s allocation is for LZ77 sliding window.

Heap necessary on compressor side ranges ~10k - ~40k.

According to the spdy survey, John suggests window bit of 10 (or 11) and
memory level of 1 shows good cost performance. For this configuration,
- allocation for compressor: 11048
- allocation for decompressor: 10584

Sounds reasonable to recommend.

mem_level seems not affecting compressor side's memory allocation (it does
affect the size of compressed data).

Thanks,
Takeshi