Quantcast

Faster compression, again

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Faster compression, again

Daniel Farina-4
For 9.3 at a minimum.

The topic of LZO became mired in doubts about:

* Potential Patents
* The author's intention for the implementation to be GPL

Since then, Google released "Snappy," also an LZ77-class
implementation, and it has been ported to C (recently, and with some
quirks, like no LICENSE file...yet, although it is linked from the
original Snappy project).  The original Snappy (C++) has a BSD license
and a patent grant (which shields you from Google, at least).  Do we
want to investigate a very-fast compression algorithm inclusion again
in the 9.3 cycle?

I've been using the similar implementation "LZO" for WAL archiving and
it is a significant savings (not as much as pg_lesslog, but also less
invasive).  It is also fast enough that even if one were not to uproot
TOAST's compression that it would probably be very close to a complete
win for protocol traffic, whereas SSL's standardized zlib can
definitely be a drag in some cases.

This idea resurfaces often, but the reason why I wrote in about it is
because I have a table which I categorized as "small" but was, in
fact, 1.5MB, which made transferring it somewhat slow over a remote
link.  zlib compression takes it down to about 550K and lzo (similar,
but not identical) 880K.  If we're curious how it affects replication
traffic, I could probably gather statistics on LZO-compressed WAL
traffic, of which we have a pretty huge amount captured.

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

ktm@rice.edu
On Wed, Mar 14, 2012 at 11:06:16AM -0700, Daniel Farina wrote:

> For 9.3 at a minimum.
>
> The topic of LZO became mired in doubts about:
>
> * Potential Patents
> * The author's intention for the implementation to be GPL
>
> Since then, Google released "Snappy," also an LZ77-class
> implementation, and it has been ported to C (recently, and with some
> quirks, like no LICENSE file...yet, although it is linked from the
> original Snappy project).  The original Snappy (C++) has a BSD license
> and a patent grant (which shields you from Google, at least).  Do we
> want to investigate a very-fast compression algorithm inclusion again
> in the 9.3 cycle?
>

+1 for Snappy and a very fast compression algorithm.

Regards,
Ken

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Merlin Moncure-2
In reply to this post by Daniel Farina-4
On Wed, Mar 14, 2012 at 1:06 PM, Daniel Farina <[hidden email]> wrote:

> For 9.3 at a minimum.
>
> The topic of LZO became mired in doubts about:
>
> * Potential Patents
> * The author's intention for the implementation to be GPL
>
> Since then, Google released "Snappy," also an LZ77-class
> implementation, and it has been ported to C (recently, and with some
> quirks, like no LICENSE file...yet, although it is linked from the
> original Snappy project).  The original Snappy (C++) has a BSD license
> and a patent grant (which shields you from Google, at least).  Do we
> want to investigate a very-fast compression algorithm inclusion again
> in the 9.3 cycle?
>
> I've been using the similar implementation "LZO" for WAL archiving and
> it is a significant savings (not as much as pg_lesslog, but also less
> invasive).  It is also fast enough that even if one were not to uproot
> TOAST's compression that it would probably be very close to a complete
> win for protocol traffic, whereas SSL's standardized zlib can
> definitely be a drag in some cases.
>
> This idea resurfaces often, but the reason why I wrote in about it is
> because I have a table which I categorized as "small" but was, in
> fact, 1.5MB, which made transferring it somewhat slow over a remote
> link.  zlib compression takes it down to about 550K and lzo (similar,
> but not identical) 880K.  If we're curious how it affects replication
> traffic, I could probably gather statistics on LZO-compressed WAL
> traffic, of which we have a pretty huge amount captured.

there are plenty of on gpl lz based libraries out there (for example:
http://www.fastlz.org/) and always have been.  they are all much
faster than zlib.  the main issue is patents...you have to be careful
even though all the lz77/78 patents seem to have expired or apply to
specifics not relevant to general use.

see here for the last round of talks on this:
http://archives.postgresql.org/pgsql-performance/2009-08/msg00052.php

lzo is nearing its 20th birthday, so even if you are paranoid about
patents (admittedly, there is good reason to be), the window is
closing fast to have patent issues that aren't A expired or B  covered
by prior art on that or the various copycat implementations, at least
in the US.

snappy looks amazing.

merlin

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Andrew Dunstan


On 03/14/2012 04:10 PM, Merlin Moncure wrote:
> there are plenty of on gpl lz based libraries out there (for example:
> http://www.fastlz.org/) and always have been.  they are all much
> faster than zlib.  the main issue is patents...you have to be careful
> even though all the lz77/78 patents seem to have expired or apply to
> specifics not relevant to general use.
>

We're not going to include GPL code in the backend. We have enough
trouble with readline and that's only for psql. SO the fact that there
are GPL libraries can't help us, whether there are patent issues or not.

cheers

andrew

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

ktm@rice.edu
On Wed, Mar 14, 2012 at 04:43:55PM -0400, Andrew Dunstan wrote:

>
>
> On 03/14/2012 04:10 PM, Merlin Moncure wrote:
> >there are plenty of on gpl lz based libraries out there (for example:
> >http://www.fastlz.org/) and always have been.  they are all much
> >faster than zlib.  the main issue is patents...you have to be careful
> >even though all the lz77/78 patents seem to have expired or apply to
> >specifics not relevant to general use.
> >
>
> We're not going to include GPL code in the backend. We have enough
> trouble with readline and that's only for psql. SO the fact that
> there are GPL libraries can't help us, whether there are patent
> issues or not.
>
> cheers
>
> andrew
>

That is what makes Google's Snappy so appealing, a BSD license.

Regards,
Ken

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Merlin Moncure-2
In reply to this post by Andrew Dunstan
On Wed, Mar 14, 2012 at 3:43 PM, Andrew Dunstan <[hidden email]> wrote:

>
>
> On 03/14/2012 04:10 PM, Merlin Moncure wrote:
>>
>> there are plenty of on gpl lz based libraries out there (for example:
>> http://www.fastlz.org/) and always have been.  they are all much
>> faster than zlib.  the main issue is patents...you have to be careful
>> even though all the lz77/78 patents seem to have expired or apply to
>> specifics not relevant to general use.
>>
>
> We're not going to include GPL code in the backend. We have enough trouble
> with readline and that's only for psql. SO the fact that there are GPL
> libraries can't help us, whether there are patent issues or not.

er, typo: I meant to say: "*non-gpl* lz based..."  :-).

merlin

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Daniel Farina-4
On Wed, Mar 14, 2012 at 2:03 PM, Merlin Moncure <[hidden email]> wrote:
> er, typo: I meant to say: "*non-gpl* lz based..."  :-).

Given that, few I would say have had the traction that LZO and Snappy
have had, even though in many respects they are interchangeable in the
general trade-off spectrum. The question is: what burden of proof is
required to convince the project that Snappy does not have exorbitant
patent issues, in proportion to the utility of having a compression
scheme of this type integrated?

One would think Google's lawyers did their homework to ensure they
would not be trolled for hideous sums of money by disclosing and
releasing the exact implementation of the compression used virtually
everywhere.  If anything, that may have been a more complicated issue
than writing and releasing yet-another-LZ77 implementation.

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Tom Lane-2
Daniel Farina <[hidden email]> writes:
> Given that, few I would say have had the traction that LZO and Snappy
> have had, even though in many respects they are interchangeable in the
> general trade-off spectrum. The question is: what burden of proof is
> required to convince the project that Snappy does not have exorbitant
> patent issues, in proportion to the utility of having a compression
> scheme of this type integrated?

Another not-exactly-trivial requirement is to figure out how to not
break on-disk compatibility when installing an alternative compression
scheme.  In hindsight it might've been a good idea if pglz_compress had
wasted a little bit of space on some sort of version identifier ...
but it didn't.

                        regards, tom lane

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Kevin Grittner
Tom Lane <[hidden email]> wrote:
 
> Another not-exactly-trivial requirement is to figure out how to
> not break on-disk compatibility when installing an alternative
> compression scheme.  In hindsight it might've been a good idea if
> pglz_compress had wasted a little bit of space on some sort of
> version identifier ... but it didn't.
 
Doesn't it always start with a header of two int32 values where the
first must be smaller than the second?  That seems like enough to
get traction for an identifiably different header for an alternative
compression technique.
 
-Kevin

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Daniel Farina-4
In reply to this post by Tom Lane-2
On Wed, Mar 14, 2012 at 2:58 PM, Tom Lane <[hidden email]> wrote:

> Daniel Farina <[hidden email]> writes:
>> Given that, few I would say have had the traction that LZO and Snappy
>> have had, even though in many respects they are interchangeable in the
>> general trade-off spectrum. The question is: what burden of proof is
>> required to convince the project that Snappy does not have exorbitant
>> patent issues, in proportion to the utility of having a compression
>> scheme of this type integrated?
>
> Another not-exactly-trivial requirement is to figure out how to not
> break on-disk compatibility when installing an alternative compression
> scheme.  In hindsight it might've been a good idea if pglz_compress had
> wasted a little bit of space on some sort of version identifier ...
> but it didn't.

I was more thinking that the latency and throughput in LZ77 schemes
may be best first applied to protocol compression.  The downside is
that requires more protocol wrangling, but at least terabytes of
on-disk format doesn't get in the picture, even though LZ77 on the
data itself may be attractive.

I'm interested allowing layering transports below FEBE (similar to how
SSL is "below", except without the complexity of being tied into auth
& auth) in a couple of respects, and this is one of them.

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Robert Haas
In reply to this post by Kevin Grittner
On Wed, Mar 14, 2012 at 6:08 PM, Kevin Grittner
<[hidden email]> wrote:

> Tom Lane <[hidden email]> wrote:
>> Another not-exactly-trivial requirement is to figure out how to
>> not break on-disk compatibility when installing an alternative
>> compression scheme.  In hindsight it might've been a good idea if
>> pglz_compress had wasted a little bit of space on some sort of
>> version identifier ... but it didn't.
>
> Doesn't it always start with a header of two int32 values where the
> first must be smaller than the second?  That seems like enough to
> get traction for an identifiably different header for an alternative
> compression technique.

The first of those words is vl_len_, which we can't fiddle with too
much, but the second is rawsize, which we can definitely fiddle with.
Right now, rawsize < vl_len_ means it's compressed; and rawsize ==
vl_len_ means it's uncompressed.  As you point out, rawsize > vl_len_
is undefined; also, and maybe simpler, rawsize < 0 is undefined.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Tom Lane-2
Robert Haas <[hidden email]> writes:
> On Wed, Mar 14, 2012 at 6:08 PM, Kevin Grittner
> <[hidden email]> wrote:
>> Doesn't it always start with a header of two int32 values where the
>> first must be smaller than the second?  That seems like enough to
>> get traction for an identifiably different header for an alternative
>> compression technique.

> The first of those words is vl_len_, which we can't fiddle with too
> much, but the second is rawsize, which we can definitely fiddle with.
> Right now, rawsize < vl_len_ means it's compressed; and rawsize ==
> vl_len_ means it's uncompressed.  As you point out, rawsize > vl_len_
> is undefined; also, and maybe simpler, rawsize < 0 is undefined.

Well, let's please not make the same mistake again of assuming that
there will never again be any other ideas in this space.  IOW, let's
find a way to shoehorn in an actual compression-method ID value of some
sort.  I don't particularly care for trying to push that into rawsize,
because you don't really have more than about one bit to work with
there, unless you eat the entire word for ID purposes which seems
excessive.

After looking at pg_lzcompress.c for a bit, it appears to me that the
LSB of the first byte of compressed data must always be zero, because
the very first control bit has to say "copy a literal byte"; you can't
have a back-reference until there's some data in the output buffer.
So what I suggest is that we keep rawsize the same as it is, but peek at
the first byte after that to decide what we have: even means existing
compression method, an odd value is an ID byte selecting some new
method.  This gives us room for 128 new methods before we have trouble
again, while consuming only one byte which seems like acceptable
overhead for the purpose.

                        regards, tom lane

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Robert Haas
On Wed, Mar 14, 2012 at 9:44 PM, Tom Lane <[hidden email]> wrote:
> Well, let's please not make the same mistake again of assuming that
> there will never again be any other ideas in this space.  IOW, let's
> find a way to shoehorn in an actual compression-method ID value of some
> sort.  I don't particularly care for trying to push that into rawsize,
> because you don't really have more than about one bit to work with
> there, unless you eat the entire word for ID purposes which seems
> excessive.

Well, you don't have to go that far.  For example, you could dictate
that, when the value is negative, the most significant byte indicates
the compression algorithm is in use (128 possible compression
algorithms).  The remaining 3 bytes indicate the compressed length;
but when they're all zero, the compressed length is instead stored in
the following 4-byte word.  This consumes one additional 4-byte word
for values that take >= 16MB compressed, but that's presumably a
non-problem.

> After looking at pg_lzcompress.c for a bit, it appears to me that the
> LSB of the first byte of compressed data must always be zero, because
> the very first control bit has to say "copy a literal byte"; you can't
> have a back-reference until there's some data in the output buffer.
> So what I suggest is that we keep rawsize the same as it is, but peek at
> the first byte after that to decide what we have: even means existing
> compression method, an odd value is an ID byte selecting some new
> method.  This gives us room for 128 new methods before we have trouble
> again, while consuming only one byte which seems like acceptable
> overhead for the purpose.

That would work, too.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Daniel Farina-4
In reply to this post by Daniel Farina-4
On Wed, Mar 14, 2012 at 11:06 AM, Daniel Farina <[hidden email]> wrote:
>...and it has been ported to C (recently, and with some
> quirks, like no LICENSE file...yet, although it is linked from the
> original Snappy project).

I poked the author about the license and he fixed it in a jiffy.  Now
under BSD, with Intel's Copyright.  He seems to be committing a few
enhancements, but the snail's trail of the Internet suggests that this
code has made its way into Linux as well, including btrfs.

So now I guess we can have at it... https://github.com/andikleen/snappy-c/

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Simon Riggs
In reply to this post by Daniel Farina-4
On Wed, Mar 14, 2012 at 6:06 PM, Daniel Farina <[hidden email]> wrote:

> If we're curious how it affects replication
> traffic, I could probably gather statistics on LZO-compressed WAL
> traffic, of which we have a pretty huge amount captured.

What's the compression like for shorter chunks of data? Is it worth
considering using this for the libpq copy protocol and therefore
streaming replication also?

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Daniel Farina-4
On Thu, Mar 15, 2012 at 3:14 PM, Simon Riggs <[hidden email]> wrote:
> On Wed, Mar 14, 2012 at 6:06 PM, Daniel Farina <[hidden email]> wrote:
>
>> If we're curious how it affects replication
>> traffic, I could probably gather statistics on LZO-compressed WAL
>> traffic, of which we have a pretty huge amount captured.
>
> What's the compression like for shorter chunks of data? Is it worth
> considering using this for the libpq copy protocol and therefore
> streaming replication also?

The overhead is between 1 and 5 bytes that reserve the high bit as a
continuation bit (so one byte for small data), and then straight into
data.  So I think it could be applied for most payloads that are a few
bytes wide.  Presumably that could be lifted, but the format
description only allows for 2**32 - 1 for the uncompressed size.

I'd really like to find a way to layer both message-oblivious and
message-aware transport under FEBE with both backend and frontend
support without committing the project to new code for-ever-and-ever.
I guess I could investigate it in brief now, unless you've already
thought about/done some work in that area.

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

ktm@rice.edu
In reply to this post by Simon Riggs
On Thu, Mar 15, 2012 at 10:14:12PM +0000, Simon Riggs wrote:

> On Wed, Mar 14, 2012 at 6:06 PM, Daniel Farina <[hidden email]> wrote:
>
> > If we're curious how it affects replication
> > traffic, I could probably gather statistics on LZO-compressed WAL
> > traffic, of which we have a pretty huge amount captured.
>
> What's the compression like for shorter chunks of data? Is it worth
> considering using this for the libpq copy protocol and therefore
> streaming replication also?
>
> --
>  Simon Riggs                   http://www.2ndQuadrant.com/
>  PostgreSQL Development, 24x7 Support, Training & Services

Here is a pointer to some tests with Snappy+CouchDB:

https://github.com/fdmanana/couchdb/blob/b8f806e41727ba18ed6143cee31a3242e024ab2c/snappy-couch-tests.txt

They checked compression on smaller chunks of data. I have extracted the
basic results. The first number is the original size in bytes, followed
by the compressed size in bytes, the percent compressed and the compression
ratio:

77 -> 60, 90% or 1.1:1
120 -> 104, 87% or 1.15:1
127 -> 80, 63% or 1.6:1
5942 -> 2930, 49% or 2:1

It looks like a good candidate for both the libpq copy protocol and
streaming replication. My two cents.

Regards,
Ken

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Simon Riggs
In reply to this post by Daniel Farina-4
On Thu, Mar 15, 2012 at 10:34 PM, Daniel Farina <[hidden email]> wrote:

> I'd really like to find a way to layer both message-oblivious and
> message-aware transport under FEBE with both backend and frontend
> support without committing the project to new code for-ever-and-ever.
> I guess I could investigate it in brief now, unless you've already
> thought about/done some work in that area.

Not done anything in that area myself.

I think its important that we have compression for the COPY protocol
within libpq, so I'll add that to my must-do list - but would be more
than happy if you wanted to tackle that yourself.

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Huchev
In reply to this post by Daniel Farina-4
For a C implementation, it could interesting to consider LZ4 algorithm, since it is written natively in this language. In contrast, Snappy has been ported to C by Andy from the original C++ Google code, which lso translate into less extensive usage and tests.

http://code.google.com/p/lz4/

Furthermode, LZ4 license is BSD. And it has been reported in several tests as being faster than Snappy/LZO, especially on decompression speed.

http://article.gmane.org/gmane.comp.file-systems.btrfs/15744

And last point, there is a "high compression" mode, which could be useful for data rarely written/modified but often read.

http://code.google.com/p/lz4hc/
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Faster compression, again

Daniel Farina-4
On Tue, Apr 3, 2012 at 7:29 AM, Huchev <[hidden email]> wrote:
> For a C implementation, it could interesting to consider LZ4 algorithm, since
> it is written natively in this language. In contrast, Snappy has been ported
> to C by Andy from the original C++ Google code, which lso translate into
> less extensive usage and tests.

From what I can tell, the C implementation of snappy has more tests
than this LZ4 implementation, including a fuzz tester.  It's a
maintained part of Linux as well, and used for btrfs --- this is why
it was ported.  The high compression version of LZ4 is apparently
LGPL.  And, finally, there is the issue of patents: snappy has several
multi-billion dollar companies that can be held liable (originator
Google, as well as anyone connected to Linux), and to the best of my
knowledge, nobody has been held to extortion yet.

Consider me unconvinced as to this line of argument.

--
fdr

--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
12
Loading...