I have been incredibly impressed with Zstandard, and if you are not currently using I suggest giving it a try.
I'm a sysadmin so this has worked it's way into every corner of my servers, from backups, to log compression, and more. Most of my servers run FreeBSD, and with the merge of linux/FreeBSD ZFS I am looking forward to the integration of ZSTD into ZFS so I can use that for on-the-fly Zpool compression.
I can safely say that ZSTD has saved me TB of space over LZ4 & GZIP.
You probably have some conditioning that discourages use of '-9', but that's generally totally fine to use with zstd in terms of speed.
I've been a zstd convert for a few years now and haven't settled on any particular ideal setting. Sometimes the very high compression levels (-19) produce a worse result, sometimes they kill it. I think most of the time I'm using -9.
I've seen cases where '--ultra --long -22' was bringing size down by 10% or more compared to the normal settings, and also cases where changing the defaults at all produced significantly lower compression.
Compressing large files/backups using all available cores at the highest setting is a bliss. Sadly the choke point now is encryption. Hopefully some kind soul will some day add this to gpg or equivalent. There are parallelizable cipher modes like CTR and GCM.
If your need of encryption is related to backups, look into "Borg backup". It can handle both encryption and zstd, also do dedupe natively since it's storing data as blocks.
Borg only utilizes one thread and does not support multithreaded zstd, so the write throughput will likely be (much) lower than ZFS -- typically 60-120 MB/s. Since ZFS can also dedupe, Borg might not even be faster for heavily deduped backups.
I used to be a big fan of XZ(which uses lzma2), but Zstandard has good-enough compression at high levels with orders of magnitude faster decompression. It's also more versatile in its compression levels. It's now also my go-to for new projects.
XZ/LZMA2 has the problem that it slows down a lot on incompressible data and can even choke pretty badly on compressible data, which Yann Collet's algorithms (LZ4 and ze standard) don't do nearly as much. This means zstd can be used indiscriminately, while LZMA would frequently need some sort of qualifier to avoid processing incompressible data and the associated loss of performance.
To put some numbers to this, on the machine (>10yo laptop) I'm typing this on:
(xz is a compression container format that doesn't imply any particular compression algorithm. It has a concept of "filters" that are applied in "chains" over "blocks". One filter happens to be "lzma2", but to say xz "uses lzma2" is a bit of a confusing mental model, as xz could just as easily "use zstd" if someone allocated a filter ID for such.)
In principle yes, but in practice the only filters included in my version are lzma1, lzma2, a basic delta filter and a few filters for executable code. As far as I can tell all the presets that are reachable without explicitly specifying a filter chain are just lzma2 with various options set.
I would love if xz had a zstd filter and a filter that adds/processes some error correction code. But with what's there right now I think it's fair to treat it as a pure lzma2 container format.
For system backups and logs and stuff that rarely need to be decompressed, but stored for a while and then deleted in rotation, I still strongly prefer xzip. It's much slower to create a .tar.xz file with the default settings, but also saves a considerable amount of disk space.
Side by side comparison right now between a full system file tree backup of a mediawiki server, the .tar.xz file is about 1.8GB, the .tar.zstd file is 2.15GB. The same thing in traditional .tar.gz format is obviously even larger.
From the research I've done on common uses of zstd it's much better suited to applications where very high speed of compression and decompression is a major requirement, but absolute smallest file size is not. Typically as a replacement for gzip.
Try xz -1. Faster than gzip, smaller size. We use it for regular backups. Although the xz format is not recommended for long term archiving because it's unsafe.
I'm going to read this in more detail later today when I have time. But I just skimmed it, and most of the points about xz being fragile and having a weird format would seem to apply in a scenario in which a .tar.xz file became corrupted or bit-flipped from its original? eg: in which the .xz file, after some long period of archiving, no longer matched the same sha256sum as when it was originally created. Thereby making it difficult or a huge hassle to get authentic lossless/uncorrupted data out of it?
The "unsafe" thing is nonsense. The expressed concern is how the contents degrade in the presence of arbitrary bit flips. Any highly-compressed format is going to be susceptible to corruption amplification from random bitflips, and the higher compression level, the larger fallout. Ensure your compressed archives are not corrupted using some external FEC; either in your hardware, or something like par2.
In my tests with the mix of files on this particular virtual machine, increasing the compression ratio of zstd to achieve an equally small output file size as xzip, it's equally as slow on a per-core basis.
It does have a performance advantage in that it by default uses both CPU cores, while a default tar with -J option will use xzip on only one CPU core.
xz on highest (normal) compression level easily beats the compression ratio of zstd on highest compression level (--ultra -22) on any data I've tested. However with xz reading the compressed files easily becomes a bottleneck, zstd has great read speeds regardless of compression ratio.
In my experience (a couple years ago, YMMV) high-level (22) zstd compression is about as slow as high-level xz (9) compression and the results are slightly larger. High-level zstd decompresses vastly faster than xz — so I would use it for things like CDNs, where users are decompressing contents much more frequently than compression — but for backups, which are decompressed zero or one times, it probably doesn't matter.
This is basically what arch linux has done with their repo/packages.
> zstd and xz trade blows in their compression ratio. Recompressing all packages to zstd with our options yields a total ~0.8% increase in package size on all of our packages combined, but the decompression time for all packages saw a ~1300% speedup.
In some things it's often a trade off of expected network speed vs cpu power. On very limited network speed connections such as a last mile ISP connection in a developing nation, where speeds might be under 5Mbps downstream, xz has some advantages in lower transfer times.
Often times persons on very limited bandwidth connections (even a Hughesnet or Viasat consumer grade satellite link in a very rural area of the USA) will have more than sufficient CPU to decompress xz in a reasonable amount of time. Such as a five year old core i5 desktop computer.
In environments where it can be expected that the bulk of users are on very fast broadband connections, zstd and slightly larger file sizes have an advantage.
This (purported) benefit is bounded by the difference between compression ratios. You're responding to a claim that the difference was 0.8%. This is pretty marginal — that first 99.2% takes exactly the same with xz or zstd, and the remaining 0.8% is not large in comparison.
Take for example ~13.5 GB. This is a 6 hour download at your 5Mbps figure. An extra 0.8% is less than 3 minutes on that 6 hour download.
For the corpus of things I've dealt with recently, the difference is a lot more than 0.8% in size. As much as the difference between an entire compressed virtual machine (copy of a set of LVM logical volumes that have been copied with dd and compressed) being 4.2GB vs 5.15GB in size.
If it might take ten hours to transfer 900MB in some unusual environments, that's a big savings.
Also there is a degree of asymmetry, in that it's not so difficult for the system creating the xzip archive to have a lot of CPU (four CPU cores out of 12 or 16 on a dual socket current generation xeon system, or a threadripper). Since xzip is much more time consuming to create than to extract.
Or for any other environment where WAN connectivity is extremely limited in throughput.
I'd like to see some real example where the compression difference between xz and zstd is actually 4.2 vs 5.15 GB. That's huge and bigger than any difference I've ever seen published between the two. Are you sure you actually used comparable settings with zstd? IMO, this is not a typical difference and shouldn't guide intuitions about where to use one or the other.
I don't think zstd makes sense for transparent disc encryption (compared with lz4). The table at [1] shows that zstd is half the speed of lz4, and provides only a modest improvement in compression ratio.
For latency-sensitive operations - in particular, decompression - lz4 maintains an extreme lead in performance (at a cost of lower compression ratios). This has borne out in practice for me as well.
Last I looked at benchmarks, only lz4 level 1 compression is faster than fastest zstd setting. At all other lz4 levels, zstd has a mode as fast but with significantly better compression.
But that is throughput. How latency (on small files/chunks) is affected I have no idea.
LZ4 makes sense when you need fast (i.e. runtime) compression; for anything compressed ahead of time and distributed to be decompressed, Zstd is probably better.
You have that backwards. LZ4 is completely about decompression speed, while zstd balances compression and decompression speed. For data that will be decompressed many times, and which decompression speed is most important, LZ4. Most other cases zstd wins
ZStandard is great - I used it as a replacement for PNG
for texture loading in the game engine for Weapon Hacker. Also for all game entity data - reduced asset loading time by about 4x, so things pretty much start instantly.
Thanks - biggest difference from web development is the mental model, instead of responding to discrete events you're updating everything a tiny bit once per frame.
There's a ton of resources out there for learning engines - Unity, Unreal, Godot, etc. I went the low-level route and built a custom engine, which was fun and taught me a lot about programming. No single resource comes to mind - requires piecing together a lot of different things.
The zstd tool defaults to one thread for IO and one for compression. You can change the number of compression threads with the parameter -T (e.g. -T0 to use all physical cores).
Zstandard is great indeed. Performance is excellent, but in my experience its killer feature is the user definable dictionary. My search engine software stores its documents in an archive to which I need random access. Lots of small documents, random access: bad for compression. Use of zstd with a tuned dictionary improved compression fivefold(!) when compared to the older zlib solution.
> but in my experience its killer feature is the user definable dictionary.
If I had to guess, since this originated from within Facebook, they're using the feature for user definable dictionary to maintain a large corpus of sample, representative user uploaded content.
Which would accomplish the purpose of tuning its performance for their own specific internal usage.
This didn't originate from within Facebook. It is an evolution of the work done in late 2013/early 2014 around FSE[1]. Facebook later hired Yann to support his work around this (pretty amazing!) tool.
The ability to define your own dictionary is useful beyond simply large indexable datasets. Anything application-specific can usually benefit from user-defined dictionaries.
The dictionary helps with the boilerplate stuff that is shared between records but not repeated inside them. So it works like a charm for relatively small fragments of structured data like e.g. HTML pages, XML-docs or SQL statements: lots of "SELECT * FROM" fragments that can be replaced by a single token. I suspect it works even better for this kind of data than for natural language data, which tends to be skewed in a Zipf-like way.
I've wanted to use zstandard with a dictionary, but how do people manage their dictionaries? What if I want to update a dictionary, will that break old compressed data? Do I need to 'tag' the data so I know which dictionary to fetch?
It is not the responsibility of a compressor to manage (or even store) your data. So yes, you have to come up with some sort of scheme yourself. But the overhead of a version number or something is usually negligible compared to the gains.
We documented some of this in our Engineering blog posts on Zstandard. Check this one out and search for "Managed Compression" for the system we built.
My first thought would be to store the dictionary in a file with the same name as the archive, but with '.dict' or something like that appended. If you're concerned about wasting space by duplicating the dictionary for many many archives, use a single file and hard links instead.
If anyone from Facebook is reading, please look at making zstd seekable. There is already experimental support but it needs to be standardized. This could open up really interesting new use-cases [see my comment linked above], where currently we have to use much slower xz/lzma instead.
So, xz isn't as much of a compression algorithm as a compression container format (which is a big reason why it generates slightly larger files than directly using the lzma tooling, and also the reason why a lot of people dislike it for solving a kind of weird problem); why not just add a filter type for zstd to xz? Adding this support to zstd when we already have this awkward container format to solve this specific problem in isolation seems like the wrong abstraction.
Sure - the problem isn't really on a technical level, it's the social problem of getting everyone to agree to adhere to one standard and then we can implement that in a single set of formats and tools.
I'm actually working on a sqlite addon right now that allows to transparently compress tables in sqlite using zstd dictionaries and the preliminary results are really promising! One DB I have compresses down from 1GB to 80MB and random SELECTs are faster in the compressed DB when the cache is cold and only somewhat slower when it is hot :)
Brotli has a static dictionary (contents of which can be seen here[1]) which was created from a web corpus. It’s part of the spec[2]. A derivative implementation of zstd could make use of this as a static dictionary.
Browsers, no, they haven't shipped support at present.
Facebook is using it for its HTTP traffic to its apps though. We've seen significant benefits. The compression ratio is pretty comparable to Brotli, but it decompresses very much faster, which is nice when the client is a mobile device--lower latency, longer battery life, etc.
It would be good to see some charts[1] similar to the zfs zstd integration. At that time, I found it notable that LZ4 was still the most optimized point for anyone without an actual preference between speed and compression.
Zstd fully supports binary deltas. If you're computing a delta between `old` and `new` you would do this to round trip it:
zstd --patch-from=old new -c | zstd -d --patch-from=old
Using the library this can be achieved by using the old file as a dictionary. If you have very large files (MB-GB range) you will also want to enable long range mode, otherwise zstd might not be able to find the repetition. --patch-from on the CLI will manage this automatically.
The release notes from zstd-1.4.5 [0] contain some details about the speed/size tradeoff of "patch-from" mode, compared to other delta engines. There is also a wiki page detailing how to use zstd as a delta engine [1].
I don't think you are doing the correct comparison in your article. BSDiff is two steps, the first step is calculating the binary subtraction mappings, and then compressing these mappings with a compressor. Colin Percival used zlib compression in his original bsdiff paper, but the performance of zlib is not great. If you really wanted to compare zstd deltas with bsdiff you need to replace zlib with a modern compressor like regular old zstd.
You're right that a totally fair comparison would use zstd. I didn't personally run these benchmarks, but I believe that the dominate time was computing the binary subtraction mappings, so I would expect similar results.
Also, if you give zstd binary delta a try, we would be super interested in hearing the results you get! Especially around the tradeoff between compressed size, compression time, and decompression time. Opening an issue would be the best way to communicate it.
Zstandard uses finite state entropy (FSE) for entropy encoding (after finding repeats), which in turn us based on asymmetric numeral system (ANS) encoding.
The canonical paper on ANS is indecipherable to me (i honestly think it's poorly written, it's not just me, although it is partly me!), but this seems like a clearer explanation (although i still don't entirely get it):
76 comments
[ 5.1 ms ] story [ 125 ms ] threadI'm a sysadmin so this has worked it's way into every corner of my servers, from backups, to log compression, and more. Most of my servers run FreeBSD, and with the merge of linux/FreeBSD ZFS I am looking forward to the integration of ZSTD into ZFS so I can use that for on-the-fly Zpool compression.
I can safely say that ZSTD has saved me TB of space over LZ4 & GZIP.
I've been a zstd convert for a few years now and haven't settled on any particular ideal setting. Sometimes the very high compression levels (-19) produce a worse result, sometimes they kill it. I think most of the time I'm using -9.
I've seen cases where '--ultra --long -22' was bringing size down by 10% or more compared to the normal settings, and also cases where changing the defaults at all produced significantly lower compression.
(On the dataset used for the figure, zstd -9 was about the same MB/s as gzip -4, and compressed at ~3.5x to gzip's ~3.0x.)
https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
To put some numbers to this, on the machine (>10yo laptop) I'm typing this on:
I would love if xz had a zstd filter and a filter that adds/processes some error correction code. But with what's there right now I think it's fair to treat it as a pure lzma2 container format.
Side by side comparison right now between a full system file tree backup of a mediawiki server, the .tar.xz file is about 1.8GB, the .tar.zstd file is 2.15GB. The same thing in traditional .tar.gz format is obviously even larger.
From the research I've done on common uses of zstd it's much better suited to applications where very high speed of compression and decompression is a major requirement, but absolute smallest file size is not. Typically as a replacement for gzip.
https://www.nongnu.org/lzip/xz_inadequate.html
It does have a performance advantage in that it by default uses both CPU cores, while a default tar with -J option will use xzip on only one CPU core.
> zstd and xz trade blows in their compression ratio. Recompressing all packages to zstd with our options yields a total ~0.8% increase in package size on all of our packages combined, but the decompression time for all packages saw a ~1300% speedup.
Often times persons on very limited bandwidth connections (even a Hughesnet or Viasat consumer grade satellite link in a very rural area of the USA) will have more than sufficient CPU to decompress xz in a reasonable amount of time. Such as a five year old core i5 desktop computer.
In environments where it can be expected that the bulk of users are on very fast broadband connections, zstd and slightly larger file sizes have an advantage.
Take for example ~13.5 GB. This is a 6 hour download at your 5Mbps figure. An extra 0.8% is less than 3 minutes on that 6 hour download.
If it might take ten hours to transfer 900MB in some unusual environments, that's a big savings.
Also there is a degree of asymmetry, in that it's not so difficult for the system creating the xzip archive to have a lot of CPU (four CPU cores out of 12 or 16 on a dual socket current generation xeon system, or a threadripper). Since xzip is much more time consuming to create than to extract.
Or for any other environment where WAN connectivity is extremely limited in throughput.
1. https://facebook.github.io/zstd/
But that is throughput. How latency (on small files/chunks) is affected I have no idea.
For someone that's a web developer that's never done game development at all, do you have any recommended resources for learning?
There's a ton of resources out there for learning engines - Unity, Unreal, Godot, etc. I went the low-level route and built a custom engine, which was fun and taught me a lot about programming. No single resource comes to mind - requires piecing together a lot of different things.
If I had to guess, since this originated from within Facebook, they're using the feature for user definable dictionary to maintain a large corpus of sample, representative user uploaded content.
Which would accomplish the purpose of tuning its performance for their own specific internal usage.
The ability to define your own dictionary is useful beyond simply large indexable datasets. Anything application-specific can usually benefit from user-defined dictionaries.
[1] http://fastcompression.blogspot.com/2013/12/finite-state-ent...
https://engineering.fb.com/2018/12/19/core-data/zstandard/
If anyone from Facebook is reading, please look at making zstd seekable. There is already experimental support but it needs to be standardized. This could open up really interesting new use-cases [see my comment linked above], where currently we have to use much slower xz/lzma instead.
https://github.com/phiresky/sqlite-zstd
Lacking a clear source for a public dictionary suited to the web corpus, there's not much point in putting it in browsers.
[1] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e
[2] https://tools.ietf.org/html/rfc7932#appendix-A
Facebook is using it for its HTTP traffic to its apps though. We've seen significant benefits. The compression ratio is pretty comparable to Brotli, but it decompresses very much faster, which is nice when the client is a mobile device--lower latency, longer battery life, etc.
There's discussion on this topic here: https://github.com/facebook/zstd/issues/1355
1 https://github.com/openzfs/zfs/pull/10278
zstd --patch-from=old new -c | zstd -d --patch-from=old
Using the library this can be achieved by using the old file as a dictionary. If you have very large files (MB-GB range) you will also want to enable long range mode, otherwise zstd might not be able to find the repetition. --patch-from on the CLI will manage this automatically.
The release notes from zstd-1.4.5 [0] contain some details about the speed/size tradeoff of "patch-from" mode, compared to other delta engines. There is also a wiki page detailing how to use zstd as a delta engine [1].
[0] https://github.com/facebook/zstd/releases/tag/v1.4.5
[1] https://github.com/facebook/zstd/wiki/Zstandard-as-a-patchin...
The canonical paper on ANS is indecipherable to me (i honestly think it's poorly written, it's not just me, although it is partly me!), but this seems like a clearer explanation (although i still don't entirely get it):
https://bjlkeng.github.io/posts/lossless-compression-with-as...