News for hackers. Stuff that matters.
Re:Improving compression at scale with Zstandard by jclay on Wednesday December 19, 2018 @04:30PM (#18719880)
I find the first chart so hard to understand. The axes need labels, and the color scheme is not ideal. They should use different line styles, and add a caption below summarizing the findings. There's a reason journals often require graphs to be formatted this way.

This is a resource I've found helpful: https://www3.nd.edu/~pkamat/pdf/graphs.pdf

"Consider readers with color blindness or deficiencies"

"Avoid colors that are difficult to distinguish"

Re:Improving compression at scale with Zstandard by kzrdude on Wednesday December 19, 2018 @04:38PM (#18719951)
Sure, this is the chart they usually show so it should be:

x-axis: compression speed (in input data)

y-axis: compression ratio (1x is no compression).

Re:Improving compression at scale with Zstandard by jclay on Wednesday December 19, 2018 @04:33PM (#18719905)
That being said, can anyone able to decode this share some cases in which this would be better suited than zlib?
Re:Improving compression at scale with Zstandard by cmurphycode on Wednesday December 19, 2018 @04:56PM (#18720112)
The short answer is that zstd is faster and better at compressing than zlib for most input data.

For more details, here's a comment I made a couple years ago:

There's a nice comparison of compression algorithms (including zlib, zstd, brotli, snappy, etc) here: https://quixdb.github.io/squash-benchmark/ It's nice because it uses many datasets and machine platforms. Unfortunately the graphs leave a bit to be desired, especially when you're trying to compare two algorithms. They provide the raw data, but it needs a little munging to make it workable.

For my day job I made the following graph to compare zlib level1 and zstd. This was using the "peltast" platform which is a Xeon based system, because that was most relevant for us.

http://imgur.com/a/0a3kK

(the original comment: https://news.ycombinator.com/item?id=12400503 )

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @06:46PM (#18721138)
Note, that this benchmark uses an old version of zstd and doesn't use large window brotli.
Re:Improving compression at scale with Zstandard by terrelln on Wednesday December 19, 2018 @04:37PM (#18719944)
The x axis is compression speed, and the y axis is compression ratio.

Zstandard outperforms zlib in compression ratio, compression speed, and decompression speed (not shown). The only reason to stick with zlib is for compatibility with systems that expect zlib.

Re:Improving compression at scale with Zstandard by jclay on Wednesday December 19, 2018 @04:40PM (#18719970)
That sounds fantastic. What is the porting process generally like? Are there any possibilities to create an API compatible wrapper to make it a drop in replacement for zlib?
Re:Improving compression at scale with Zstandard by terrelln on Wednesday December 19, 2018 @04:47PM (#18720041)
Porting is generally very easy.

* If you already have the compression algorithm tagged, through a file extension, or a field, then you can use that to dispatch to the right decompression algorithm.

* Zlib, gzip, xz, zstd, ... all have headers. If you are using zlib, and switching to zstd, you simply have to check the first 4 bytes for the zstd header using ZSTD_isFrame() [0], or attempting to decompress with zstd and if it fails fall back to the previous decompression algorithm.

* The zstd CLI can decompress both zstd and zlib/gzip if compiled with zlib support.

* Zstd provides a wrapper around the zlib API so you could transparently switch to zstd. [1]

[0] https://github.com/facebook/zstd/blob/dev/lib/zstd.h#L1409 [1] https://github.com/facebook/zstd/tree/dev/zlibWrapper

Re:Improving compression at scale with Zstandard by jclay on Wednesday December 19, 2018 @04:53PM (#18720096)
Great, thanks! Last question.

On the blog you mention you are underway porting the internal code to replace Zlib with Zstd. Is there a reason you decided not to use the wrapper as a first pass to migrate all uses of Zlib to Zstd across the entire codebase?

Re:Improving compression at scale with Zstandard by terrelln on Wednesday December 19, 2018 @05:14PM (#18720290)
There are a few reasons we haven't used the wrapper.

* The larger services require tuning to get the best performance out of zstd, and we use some advanced options.

* We have a "Managed Compression" library which does zstd dictionary compression, which doesn't work with the wrapper.

* We have our own automatic decompression framework that handles many algorithms [0].

* A lot of use cases switched over from other algorithms than zlib.

* A lot of use cases switched over to zstd organically, without our involvement, since it was such a clear win.

[0] https://github.com/facebook/folly/blob/master/folly/compress...

Re:Improving compression at scale with Zstandard by megous on Wednesday December 19, 2018 @04:46PM (#18720037)
Rather simple. For example here's my port of qemu to use zstd compression algorithm for QCOW2 images, instead of zlib:

https://megous.com/git/qemu-zstd/commit/?id=45df9c0510e737e6...

Re:Improving compression at scale with Zstandard by kstrauser on Wednesday December 19, 2018 @07:43PM (#18721490)
Awesome! What kind of metrics differences have you seen from the change?
Re:Improving compression at scale with Zstandard by megous on Wednesday December 19, 2018 @08:38PM (#18721806)
Much faster and/or better compression/decompression of images (tunable of course, depending on what level you set in the code), and also faster startup of VMs. I haven't measured exactly. I'd guess ~30% in my case.

But all this depends on where the bottleneck is in any particular case. My VMs are on HDD, so increased decompression speed doesn't matter that much, but reduced size helps reading the necessary data faster. Linux VMs seem to be more compressible than Windows ones.

It's certainly better than zlib in any case.

Re:Improving compression at scale with Zstandard by Cyan4973 on Wednesday December 19, 2018 @04:44PM (#18720013)
There is a zlib wrapper included in the project : https://github.com/facebook/zstd/tree/master/zlibWrapper
Re:Improving compression at scale with Zstandard by hinkley on Wednesday December 19, 2018 @05:05PM (#18720208)
The informatics dysfunction on this graph is just off the charts.

Here's the problem. The graph is designed to make your conclusion sound right, but it doesn't actually prove that.

Let's look at what the numbers really say:

For the sample data, and the best case, gzip gets you a file that's about 31% of the original size. zstandard can get you a file that is 25% of the original size but it will take you four times as long to get it. If you allow it the same time as gzip, you can get 27% compression instead of 31%. That's only 13% improvement on the wire.

That's nice, but it's not impressive at all. It's not a good enough reason to change your stack. The only thing that is impressive is that if you want the same compression ratio as gzip you can do it up to 20 times faster. On some hardware that's totally worth it, but not on all (because who is streaming at 700 MBps?)

Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @05:37PM (#18720538)
Hi. I made the graph. It was definitely not my intent to obscure or distort any information. Here's the raw data if you like [1]. Some context: the input text is silesia.tar, which is a standard mixed corpus of data. It was benchmarked by @Cyan4973 on his i7-9700k.

I guess I'm confused about how you feel we're misrepresenting the data? Are you talking about the sentence preceding that graph, "The benefits we’ve found typically range from a 30 percent better ratio to 3x better speed"? That's more describing the benefits we've seen in the real world, where for a variety of reasons (many of which are discussed in the rest of the post), we generally can get more out of zstd than this vanilla benchmark shows.

[1] https://gist.github.com/felixhandte/f6a91bf775d6e7df76ce06c0...

Re:Improving compression at scale with Zstandard by hinkley on Wednesday December 19, 2018 @07:00PM (#18721232)
Edward Tufte will set you straight.

The first rule of objective graphs is always show the origin at 0. As an informed graph consumer, if the origin is not 0 you should immediately distrust your eyes, and question the motives of the person showing you the data. The relative sizes are being distorted. Why?

In this case, there's a 15% difference in Y values in your data that on the graph is presented as two lines that are separated from each other by 33%. Just by removing 0 and 1 from the chart.

On the other hand, that effect is diluted a bit by what you've done on the X axis. Log scale tells a story about trends. The relative slope of two lines on log scale says something. The distance between them doesn't mean much, if anything, although the brain can't help trying to make it mean something.

I believe you will find that a great deal of what you lose by plotting y = 0 you'll gain back by plotting x on a linear scale. Those lines deserve to be much farther apart.

Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @07:17PM (#18721330)
The Visual Display of Quantitative Information is one of my favorite books!

0 in this case is not really a relevant value (since that would mean transforming the input into something infinitely large). The functional identity value / origin here is 1x. Here's what that looks like [1].

To me, this is a significantly less useful image. But maybe that stems from a lot of comfort with both the subject matter and the detail log-log plots that I work with to evaluate zstd performance, e.g. [2].

[1] https://imgur.com/gU2Gdf6 [2] https://github.com/facebook/zstd/pull/1317#issuecomment-4260...

Re:Improving compression at scale with Zstandard by hinkley on Wednesday December 19, 2018 @07:53PM (#18721558)
Hey thanks for the new chart, and you're right about 1x. But we might have to disagree because I don't think this graph is that bad. I can see a bunch of talking points in this graph that are about strategy instead of about why I hate bad graphs.

First, that data point for lz4 out around 820 MB/s kind of throws the groove off of that graph. Despite that, I would still suggest you prune the graph off at 850 or 900 to reduce the squish of the horizontal data (pruning the graph to put the last value at 100% of width or height isn't considered a no-no).

One of the things I can see now but couldn't before is that the size/speed tradeoff is pretty linear except for the giant dog-leg around 3.6:1, and a less pronounced but still notable one occurs at 2.9:1.

If I sat down with my team to discuss this chart I'd suggest we agree that we aren't interested in anything above 3.6:1. And then I'd suggest we look at everything above 2.9:1, but my eye is on 3.2:1 (where zlib tops out and is 1/10th the speed). If they don't like 2.9:1, then the next interesting point is at about 2.7:1 when zlib bottoms out. We're already at such a high bandwidth rate that something else is probably going to be the bottleneck.

Re:Improving compression at scale with Zstandard by taneq on Wednesday December 19, 2018 @05:40PM (#18720556)
Having spent the last few years in the 'real' (ie. non-software) world, it boggles me how anything less than an order of magnitude improvement is handwaved as trivial. 13% of bandwidth or 20% of offline storage space is huge savings for a company like FB. Once the software development industry matures a little, more people will start realising this.
Re:Improving compression at scale with Zstandard by hinkley on Wednesday December 19, 2018 @07:09PM (#18721278)
I don't find myself disagreeing with you that much here, but 13% is not quite enough to get me to push my team to make such a big change.

On the other hand, I've also had to push for getting any compression turned on at all. If all of my infrastructure already supported zstandard, getting a 3.5:1 compression ratio would be more compelling than 3.2:1, and I can imagine situations where it's easier to get buy-in.

But first every old cell phone and crappy web browser (read: 6 year old Microsoft browser) has to support it. Which is why you have people creating backward-compatible compressors that spit out files that zlib can decompress. Because otherwise you have to support and test 3 transport formats instead of 2.

Re:Improving compression at scale with Zstandard by jclay on Wednesday December 19, 2018 @05:19PM (#18720353)
There's so much that _feels_ misleading here.

Paragraph before the chart:

"The benefits we’ve found typically range from a 30 percent better ratio to 3x better speed."

In what cases? What methodology was used to evaluate this? I certainly expected a scientific (honest) treatment of how the performance was evaluated and the corresponding trade-offs to follow on at some point.

Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @05:55PM (#18720714)
In short, we work with individual teams and projects to evaluate their priorities, and select or build the compression scheme that best addresses their needs. Some of those cases are described in the post, but we wanted to summarize the general kinds of results we see.

I did spend a fair amount of time working on a graphic for the post to try to capture the distribution of improvements we've seen across different use cases at Facebook, but it ended up being very hard to interpret / glean anything meaningful from.

It's difficult to present rigorous conclusions: the reality of data compression is that every use case is different, with different priorities and data characteristics that cause different compressors to behave differently.

Some data (random noise) is totally incompressible, and zstd will do just as poorly as any other algorithm. On the other hand, with highly structured / repetitive data like JSON, zstd can do enormously better than zlib. It all depends on the specific context.

Another example of how benchmarking is hard: we recently spent a fair amount of time improving zstd for highly-contended memory scenarios [1]. This work basically won't show up in a standard single-threaded single-workload benchmark. But we saw meaningful improvements in the real world at Facebook.

Ultimately, if you are evaluating using zstd (or any other compressor), the best predictor for performance will be a benchmark you run yourself with your own data. And hopefully you like what you see!

[1] https://github.com/facebook/zstd/releases/tag/v1.3.6

Re:Improving compression at scale with Zstandard by hinkley on Wednesday December 19, 2018 @05:44PM (#18720591)
I will say that we've been 'doing just fine' with zlib for longer than I'm comfortable with. I hung out on comp.compression when I was still in college and shared the dream of writing the next great compression library. Maybe the only thing I ever accomplished though was altering a Java minifier to improve compressibility of the class files.

On a very deep level I'm pretty disappointed that zlib has been 'good enough' for almost 30 years. When it was Google proposing a change, I wasn't enthused about handing more control over HTTP to Google. They have too much already. The ways I'm concerned about Facebook have nothing to do with standards bodies or protocols. So maybe this is good enough.

There are more options for files-in-motion and files-at-rest, and that could put it over the top. But you need to be filing high quality PRs on both HAProxy and Nginx if you want anybody to care.

Re:Improving compression at scale with Zstandard by vjeux on Wednesday December 19, 2018 @05:31PM (#18720481)
If you read the full article there are many examples of real systems being migrated with their associated wins.
Re:Improving compression at scale with Zstandard by danielvf on Wednesday December 19, 2018 @04:41PM (#18719983)
zstd totally dominates zlib. There is nothing that zlib does that zstd does not do better.

It’s just that simple.

For a given compression speed, zstd will compress the file more that zlib would. For a given compression amount, zstd will compress the data much faster than zlib would.

Re:Improving compression at scale with Zstandard by jandrese on Wednesday December 19, 2018 @04:48PM (#18720057)
Except for compatibility. If you are compressing files for yourself it's no big deal, but when you're compressing them for someone else you have to consider if your bleeding edge compression software will be an issue, especially if they are on some corporate locked down machine and can't install new software.
Re:Improving compression at scale with Zstandard by Cyan4973 on Wednesday December 19, 2018 @04:52PM (#18720090)
zstd availability is becoming more and more common nowadays. See for example this tracker : https://repology.org/metapackage/zstd/versions
Re:Improving compression at scale with Zstandard by jandrese on Wednesday December 19, 2018 @05:07PM (#18720225)
Not listed: Windows
Re:Improving compression at scale with Zstandard by danielvf on Wednesday December 19, 2018 @05:14PM (#18720294)
I’ve used it for years on both Windows and OS X.
Re:Improving compression at scale with Zstandard by Cyan4973 on Wednesday December 19, 2018 @05:28PM (#18720456)
On Windows, I'm using Chocolatey package manager : https://chocolatey.org/

zstd is among the available packages.

Re:Improving compression at scale with Zstandard by tatersolid on Thursday December 20, 2018 @06:05PM (#18730057)
To the GGP’s point, not a single machine at $dayjob (financial services) has chocolatey on the whitelist of software allowed.

We couldn’t even use GoToMeeting in our industry for ages because it required an executable download that was mostly not on the whitelist of our 2000+ customer banks & credit unions.

Windows has this thing called Software Restriction Policies, think of it as an Apple App Store curated by windows sysadmins. You can whitelist by code signer, SHA256, or even file path and name (which is insecure). https://docs.microsoft.com/en-us/windows-server/identity/sof...