Zstandard – Fast real-time compression algorithm | Hacker News Reader

Zstandard – Fast real-time compression algorithm

github.com

227 pointstosh93 comments

I needed to compress a TCP stream [0] for a block-storage project and I've been very impressed with zstd. Combined with io_uring, I'm getting less CPU usage and higher throughput to send and compress data than using socat to send uncompressed data.

[0]: https://github.com/fathyb/zstd-proxy

> This repository represents the reference implementation, provided as an open-source dual BSD and GPLv2 licensed C library

Dumb question, why dual license? Why not just provide it as BSD (the more permissive of the two)?

Just venturing a guess - may be that libraries that link this would want the option of GPL whereas commercial/non-libre software might prefer BSD?

GPL code can already link BSD libraries without an explicit GPL license option.

Isn’t BSD flavour with advertisement clause + GPL problematic? Specifically that GPL requires no further hindrance to distribution.

Approximately no one uses the 4-clause BSD (the problematic one). The one Zstd uses has three clauses: https://github.com/facebook/zstd/blob/dev/LICENSE

https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_...

There are derivates of the 4 clause BSD, like PHP License, which bave some relevant users. Considering Facebook has some historic use of PHP things (while rewritten to Hack, but that uses some PHP libraries) pure GPL might cause issues for them.

Still doesn't explain why pure BSD won't work for them, though

In case somebody still reads this a theory: Maybe they want to get standard into GNU coreutils, so it natively works with tar etc. for that GPL may make things simpler politically.

The commit history shows the GPLv2 was added as an option the same time they removed the PATENTS.txt file. React's former "BSD + PATENTS" licence had been criticised, being replaced with the MIT (Expat) licence. Similar motivation here presumably.

As non-author of any work, you can't relicense it no matter how permissive the license is.

When linking BSD code with GPL-licensed code, you have to have all the code follow the terms of GPL, which means effectively relicensing it. This is why some companies require copyright assignment even if they plan to stay open source.

Only the public domain code allows free mixing and matching.

Not a lawyer though, so take the above with a bowl of salt.

Edit: in theory, this allows using zstd in GPL2 projects, for instance, in the Linux kernel.

> As non-author of any work, you can't relicense it no matter how permissive the license is.

There are some licenses such as MIT where you can. But GPL is very much the code has to be GPL. But I also think it infects your code and forces your code to be GPL, but that may only be if you make a modification and change it and not just use GPL code within your code.

If you redistribute it, not change it.

> it infects your code and forces your code to be GPL

Does this dual license satisfy companies who have a policy of “no GPL” code?

It should. They would take the BSD option. (Corp lawyers can be paranoid, and might still object. But in theory they should be able to accept this under the BSDL.)

The GPL v2 requires that any code that this code is linked to is also released as GPL.

For example, if I want to use Pango, which is GPLv2, in my application, then the GPL requires that I also release my application's source code as GPLv2, or another compatible license.

It also requires that if I make changes to Pango and redistribute it then I need to release the source code for that as well. In other words, if I fork Pango then my fork also has to be GPLv2.

It's not so much that it 'infects' your code as that it's not compatible with closed source (or some open source licenses).

A while back, Microsoft decided to abandon their awful TCP/IP stack and use a better one - FreeBSD's TCP/IP stack. Since FreeBSD is BSD-licensed, it was possible for them to take that code, use it, modify it, and redistribute compiled versions of it, without having to give back any changes or optimizations to the open-source community.

By choosing the BSD license for their code, the project was implicitly saying that they were okay with this code sharing, and so they don't look at this as a bad thing. Microsoft's OS got better, and it didn't cost anyone else anything.

Some groups, however, think that open-source should only benefit open-source, because that's beneficial to users and the world as a whole. This is the purpose of the GPL: you can use our code, but only if all of us benefit and not just you.

To be clear, the GPL does not say anything in particular about "linking;" that's a common interpretation of what it means to be a derivative work. Wikipedia has a blurb on this:

> This key dispute is whether non-GPL software can legally statically link or dynamically link to GPL libraries. Different opinions exist on this issue. The GPL is clear in requiring that all derivative works of code under the GPL must themselves be under the GPL. Ambiguity arises with regards to using GPL libraries, and bundling GPL software into a larger package (perhaps mixed into a binary via static linking). This is ultimately a question not of the GPL per se, but of how copyright law defines derivative works.

https://en.wikipedia.org/wiki/GNU_General_Public_License#Lin...

Few people mention it, but whether (dynamically) "linking" to a library makes it a derivative work is closely related to the GOOGLE v. ORACLE case. The issue with dynamic linking is basically "copying the API (and ABI)". Unfortunately the USSC didn't really give a clear ruling on this one.

A more obvious case is the one of Linux (GPLv2 licensed) closed source binary modules: Linus has specifically said that he is not opposed to such usage, so it's never been tested in court either.

> in theory, this allows using zstd in GPL2 projects, for instance, in the Linux kernel.

More than theory, there is actually an implementation of zstd in the Linux kernel. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

Maybe it is for patent protection? I think BSD licenses do not grant explicit patent licenses but GPL does.

In combination with SQLite to allow fast random access (query) and compression: https://github.com/phiresky/sqlite-zstd

Discussed a few months ago:

Show HN: Reduce SQLite database size by up to 80% with transparent compression - https://news.ycombinator.com/item?id=32303762 - Aug 2022 (90 comments)

sqlite-zstd: Transparent dictionary-based row-level compression for SQLite - https://news.ycombinator.com/item?id=32297193 - July 2022 (1 comment)

Looks awesome and I don't want to detract. But a few things from the documentation to be aware of:

  - Q: Is this library production ready?
    A: I wouldn't trust it with my data (yet). Make sure you have backups of everything.

  - usual zstd checksum is stripped from compressed data

  - columns you want to index can't be compressed

  - works best with rows containing less than ~30kB of data

From the readme

    Zstandard is currently deployed within Facebook. It is used continuously to compress large amounts of data in multiple formats and use cases. Zstandard is considered safe for production environments.

That's a statement about the block compression algorithm.

The part that is claimed as not production ready is the third party sqlite integration.

Skimming the code I can see why. It does some pretty gnarly things involving altering the schema of all your tables. Not to say it doesn't work or isn't good, but, it seems like it really does a lot of intrusive, potentially failure prone stuff.

I love everything about zstd. It compresses well, it compresses and decompresses fast.

I wish browsers supported it for content encoding because it's a good deal faster and smaller than gzip, nevermind brotli.

The only downside is that zstd has a (relatively) large binary size. I evaluated using it for one of my projects, but it’s a massive library. The zstd-sys crate is 714kb, and zstd has no native rust port presumably because of its size.

I ended up using lz4 instead for my project. Lz4 only added 4kb to my compiled wasm size for an encoder and decoder. And it’s native rust (which makes wasm compilation effortless). Lz4 is a no-brainer to include.

The downside of lz4 is that it can’t be configured to run at higher & slower compression ratios.

> The downside of lz4 is that it can’t be configured to run at higher & slower compression ratios.

lz4 has some level of configurability? https://github.com/lz4/lz4/blob/v1.9.4/lib/lz4frame.h#L194

There's also LZ4_HC.

LZ4 (which includes the HC encoder) doesn't have an entropy encoder stage, so it's fairly limited in what compression levels it can achieve.

I feel that is a valid argument for server-side resources not supporting it, but browsers are already hundreds of MB (if not multiple GB) in size.

Exactly, and that couple hundred KB in the browser could pay for itself in terms of bandwidth saved in almost no time over gzip/br.

There is a reasonably feature complete implementation of Zstd for Go: https://github.com/klauspost/compress/tree/master/zstd

It may not offer the same API 1:1, but it has no interoperability issues that I've encountered. I think no one has bothered to implement it in Rust because most use cases don't mind the added bloat you're talking about, not because implementing it in Rust would be insurmountable. Plus, other comments I've seen suggest that you can actually tune the size of the C zstd library, although I'm not sure if the Rust bindings expose that.

According to a comment in the Chromium issue, it can be configured/stripped down quite a bit:

> While it's true that a kitchen-sink version of libzstd does weigh in at 1.5MB, the build is easily configurable and much of that can be shed. If Chromium is just going to ship the decoder, a full build of the decoder is 212kB (162kB stripped, 71kB gzipped). A size-optimized version of that is 99kB (62kB stripped, 26kB gzipped). As of recently, we had someone from the busybox project working to strip that down even more, so we very well may be able to improve further on those numbers.

While still larger than 4K, it does seem possible to make much smaller builds.

Chrome issue: https://bugs.chromium.org/p/chromium/issues/detail?id=124697...

The "nevermind brotli" seems overly dismissive. Browsers should add support for zstd, and I like zstd a lot, but I have found more cases than I would have expected where brotli compresses files better than zstd, even while using a ridiculously high compression level setting on zstd (for example, 19).

I can't remember encountering anything that compresses better with gzip than with brotli, so brotli is usually a better choice than gzip to reduce bandwidth, and brotli has been better than zstd on more than a few occasions for me as noted previously. Brotli is very worthwhile, at least for static assets, and choosing to offer only gzip compressed assets to browsers is almost always a waste of bandwidth.

If faster to compress is all you care about, then sure, brotli might not be the best choice.

My views on brotli are just from my experience with it.

I'm looking at my static assets now; our largest JS bundle is 6.3MB uncompressed. With brotli at level 9 it takes 400ms to compress down to 1.34mb, and with zstd at level 13 it squeezes down to 1.31mb in 300ms. If I use zstd at level 19, it takes 1.1s to compress, but size is even further reduced to 1.21mb. Decompression time is identical for both (33ms). So, for our static data the edge goes to zstd.

For dynamic data there's no contest. Most of our responses are binary and brotli is not just slow, it's so slow we have to disable it otherwise people assume our services have hung. By far most of the data that leaves our servers is dynamic, so having zstd support in browsers would be a huge win for us because we would spend less time compressing (compared to gzip) and have smaller responses.

I was looking at one particularly pathological case last month where we had a 2.7gb response that was quite sparse. We were spending 30s of server time as part of the request in gzip, the end result being 52mb. With zstd at level 12 it was 5s to compress it down to 41mb. I don't even know how long it would have taken with brotli as I stopped timing after 10 minutes.

I mean, if brotli wasn't working for people it wouldn't be supported by browsers, but I really really wish zstd was an option.

The OpenZFS project added support for ZSTD a while ago for transparent compression, and it's fantastic. I was seeing substantial compression rates given the type of data we were storing for basically free.

We have a delta-encoded binary format for trade logs that we use and zstd still does a pretty good job on them for the last bit.

It's just a pity that storage providers won't implement transparent compression. We store our logs on S3 and on-prem and it's just annoying that we have to store them compressed on S3. Would be cool to just store without the compression stage and have S3 do that bit.

I haven't tried btrfs with the transparent zstd compression, but perhaps worth a shot.

One upshot of compressing outside s3 is that you save on data transfer. In theory I suppose the compressed data could be sent over to the client and decompressed but then it’s basically the same thing.

it’s also a conflation of two things that are each much more sustainable if kept independent. You don’t want a particular compression pattern becoming part of the S3 standard IMO

Yeah I’ve suggested to the s3 leadery folks many times to provide some sort of managed compression and other sorts of codec interfaces. They could do other things like convert between structured encodings as well. Unfortunately it’s never gone anywhere.

Isn’t that what S3 object lambda access points are for?

https://docs.aws.amazon.com/AmazonS3/latest/userguide/olap-c...

It’s too expensive. The thing is s3 has a ton of compute sitting around. The disks have a full system behind them on the storage nodes. A big question always was how can we do more with the edge storage? S3 select was one effort (although I don’t know if ever got pushed to the edge, it originally ran in the front end servers). But I always figured compression was a real obvious s3 edge storage operation, along with as I said format conversions.

I still wish s3 object select supported zstd on json.

Could you use a Lambda to compress with zstd on write and S3 Object Lambda to decompress the stream seamlessly on GET (and update the content length on HEAD)?

Yes. That adds costs though

Obviously, but the whole point of this exercise would be because you anticipated the reduced storage GB-hours saving more than the compute time, right?

One reason this could be messy to add is that the S3 API includes support for reading arbitrary byte ranges within a file. There's an inherent conflict between that API and support for transparent compression. Compression performs best when compressing the entire file from beginning to end; when decompressing you'd similarly decompress from the beginning. To support byte range reads, the data could be compressed in short blocks, but those blocks will not compress as well.

zstd is quite slow at higher compression levels, if S3 would compress who pays the compute?

Maybe they could offer it as an extra, and spawn EC2 instances as needed and bill you.

They have a nice table on that page: https://github.com/facebook/zstd#benchmarks

Looking at that table, I think LZ4 is a winner. The compression ratio is not too far, compression speed is slightly faster, decompression speed is significantly faster, the code is much simpler so the compiled binary is smaller, and the project is unrelated to Facebook.

Both ZSTD and LZ4 were built by the same author. They have slightly different target goals: https://news.ycombinator.com/item?id=23211804

Given the table they have in their README I’d still choose LZ4 over ZSTD even if the ratio is 2.8 vs 2.1 or so for compression given the decompression is so much faster with LZ4 than with ZSTD. Also compressing is, as well.

interesting, it depends on which is more important: saving space or saving time. I never used LZ4 but I'm interested more in speed for some products, will use it in the future.

It’s not that straight forward. If you compress better before passing through a relatively low bandwidth channel you’re saving time with the slower but better compressing algorithm.

Can someone help me understand why browsers don't support Zstandard yet? Caddy supports it natively, and it's quite good, if only browsers could decode it.

Here is a relevant link: https://bugs.chromium.org/p/chromium/issues/detail?id=124697...

It sounds like they haven't decided whether to do it or not

zstd rocks. I'm using it in zfs with zfs set compression=zstd-fast-1 for a recordsize=16k postgresql dataset and compressratio is about 2.0 and it's super fast. Doubling usable SSD space for as good as free is always neat.

Here’s a recent talk by Yann Collet at Stanford which leads into an interesting Q&A about his development of Zstandard: https://youtu.be/gZikN5hhlxA

We employed zstd to compress telemetry and logs from mobile devices. We reduced total bandwidth (not including CDN) by 70%, which is a big deal for mobile devices and battery life. CPU overhead was insignificant.

zstd with a well-trained dictionary is fantastic for a lot of applications, it's super fast, and can compress your data around 4-5x smaller than normal zstd (tested with JSON that has known keys and some known values).

Interesting that the benchmarks were performed on a i7-6700K CPU which was released in 2015. Gonna err on the side of that just being outdated ... git blame shows that line has not changed in 5 years.

The 6th-generation Core CPU had BMI2 which is the only modern micro-optimization zstd uses.

Are there any attempts to make zstd into standard general-purpose archive format? I think leap from .zip is big enough to bother

You can install 7zip with zstandard!

Overall good thing!

except

* standard 7z does not support zstandard

* 7z file extension does not explain what's inside, so if you hand .7z file with zstd inside to someone, that person will blame you for unopenable archive

well if only we could rebrand 7z-with-zstd as some new format, e.g. .zstd (no changes required) ...

I was thinking of https://community.chocolatey.org/packages/7zip-zstd/1.4.9.20

You can use zstd in 7z files with Peazip: https://peazip.github.io/

Rebrand "zstd in 7z" as separate format with separate extension and new format is born

I compress things with zstd solely so that I can find out if anyone's trying to consume my stuff with ancient tooling.

What kind of files exactly? User oriented stuff is hard to migrate.

We are planning to expose zstd as a runtime API in Bun. zstd is great

did a quick check, zip on linux does not support lz4, zstd but 7z does, so I'm going to use 7z more, unfortunately 7z is still not universally installed on *nixes.

Why not just use zstd directly?

want to have encryption and compression all in one command for simplicity, zip and 7a are the only two do both

Zstd doesn’t archive multiple files?

You are conflating compression algorithms with archive file formats.

Use `tar` format and you can combine it with whatever compression utilities available such as `gzip`, `bzip2`, `lz4`, `zstd`, `xz`, etc. `tar` also preserves Unix permission. The downside is tar doesn't have an index for random-access, so you cannot do partial extraction quickly.

Use `zip` format if you don't care about Unix permission, and want to do partial extraction. `Zip` technically support multiple compression algorithms, but is primarily only used with DEFLATE (the same one as `gzip`) for compatibility reason.

How to get your backup to half of its size – ZSTD support - https://news.ycombinator.com/item?id=33644798 - Nov 2022 (51 comments)

Zstd Compressed Debug Sections - https://news.ycombinator.com/item?id=32788343 - Sept 2022 (4 comments)

Zstandard – Real-time data compression algorithm - https://news.ycombinator.com/item?id=32715933 - Sept 2022 (56 comments)

AWS switch from gzip to zstd – about 30% reduction in compressed S3 storage - https://news.ycombinator.com/item?id=32529412 - Aug 2022 (201 comments)

Show HN: Reduce SQLite database size by up to 80% with transparent compression - https://news.ycombinator.com/item?id=32303762 - Aug 2022 (90 comments)

The Bizarre Case of Zstd's Slow Performance on Arch Linux - https://news.ycombinator.com/item?id=31794958 - June 2022 (8 comments)

Zstandard Worked Example - https://news.ycombinator.com/item?id=31411714 - May 2022 (50 comments)

Zstandard RFC 8878 - https://news.ycombinator.com/item?id=29281360 - Nov 2021 (43 comments)

Compressing JSON: Gzip vs. Zstd - https://news.ycombinator.com/item?id=27707834 - July 2021 (11 comments)

Zstandard v1.5.0 - https://news.ycombinator.com/item?id=27155857 - May 2021 (36 comments)

Zstandard v1.4.7 - https://news.ycombinator.com/item?id=25455314 - Dec 2020 (73 comments)

Facebook/Zstandard – Fast real-time compression algorithm - https://news.ycombinator.com/item?id=24714854 - Oct 2020 (13 comments)

Zstandard - https://news.ycombinator.com/item?id=24348394 - Sept 2020 (11 comments)

Introduce ZSTD compression to ZFS - https://news.ycombinator.com/item?id=23210491 - May 2020 (38 comments)

Now using Zstandard instead of xz for package compression - https://news.ycombinator.com/item?id=21958585 - Jan 2020 (153 comments)

Zstandard v1.4.1 - https://news.ycombinator.com/item?id=20482424 - July 2019 (15 comments)

Zstandard v1.4.0 - https://news.ycombinator.com/item?id=19678115 - April 2019 (67 comments)

Improving compression at scale with Zstandard - https://news.ycombinator.com/item?id=18719592 - Dec 2018 (87 comments)

Zstandard – Fast real-time compression algorithm - https://news.ycombinator.com/item?id=18530628 - Nov 2018 (51 comments)

Zstandard Compression and the application/zstd Media Type - https://news.ycombinator.com/item?id=18133515 - Oct 2018 (19 comments)

Zstandard v1.3.4 – faster everything - https://news.ycombinator.com/item?id=16718402 - March 2018 (33 comments)

Zstandard – Real-time data compression algorithm - https://news.ycombinator.com/item?id=16226923 - Jan 2018 (96 comments)

Zstandard: Fast real-time compression algorithm from Facebook Opensource - https://news.ycombinator.com/item?id=16222669 - Jan 2018 (2 comments)

Better Compression with Zstandard - https://news.ycombinator.com/item?id=13813212 - March 2017 (62 comments)

Comparing gzip, brotli and zstd - https://news.ycombinator.com/item?id=12634812 - Oct 2016 (1 comment)

Smaller and faster data compression with Zstandard - https://news.ycombinator.com/item?id=12399804 - Aug 2016 (156 comments)

Zstandard – Fast and efficient compression algorithm - https://news.ycombinator.com/item?id=8941955 - Jan 2015 (24 comments)

I can’t find the Weissman score on the page, anyone know what it is? 3.8?

Weissman scores are effectively fictitious and meaningless for any real application. Why are you looking for one instead of benchmarking data?

You're responding to a low-effort joke based on a plot line in HBO's Silicon Valley TV show.

I'm aware of the reference, but I'd rather try and inform on the off-hand chance that they're serious about the question. I figured that there's little harm in making sure, other than looking a little silly :)

2.97.

https://github.com/facebook/zstd/issues/1087#issuecomment-44...

I'm always enormously impressed with efforts to move the dial when it comes to RTE, but slightly depressed when you see that it involves Facebook/Meta.

Solid engineers work at all kinds of places and are capable of producing really cool stuff no matter where they are working. Don't judge something too much by its sponsors, IMO!

please - out of all the tech giants the one constant is Meta delivers insane technology beyond their social networks. They are the goats of shipping cool shit.

For the low low price of your soul and personal data

Whatcpersonal data does zstd collects?

did I say zstd collects personal data? no. I was commenting on someone praising Facebook as a whole

LZ4 and ZStd were started by Yann Collet (the main author) quite some time before he was hired by Facebook/Meta.

Don’t worry, they track everything compressed with zstd and render appropriate advertisements to you using that data.

RTE?

Runtime or real-time encoding is my guess.

Reply on news.ycombinator.com