Zstandard v1.4.7 | Hacker News Reader

Zstandard v1.4.7

github.com

211 pointsvarbhat73 comments

https://github.com/facebook/zstd/issues/395#issuecomment-535...

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.

You can use sqlite with zstd compression (which can be extremely efficient with a shared compression dictionary).

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 :)

https://github.com/phiresky/sqlite-zstd

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.

What kind of compression level do you use?

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.

For approximate reference (N.B., this graph is somewhat dated — zstd 1.3.4 is from March 2018): https://raw.githubusercontent.com/facebook/zstd/v1.3.4/doc/i...

(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.)

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.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

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.

ZFS dedupe is broken and I don’t recommend using it unless you really know what you’re getting into.

Broken in what way?

It uses a ludicrous amount of RAM and a fixed block size and offset boundry, making it very slow and fairly ineffective.

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:

              trivial    random     .wav file
     LZMA     ~20 MB/s   ~2 MB/s    ~1 MB/s
     zstd     ~500 MB/s  ~250 MB/s  ~70 MB/s
     zlib     ~40 MB/s   ~13 MB/s   ~6 MB/s

(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.

https://www.nongnu.org/lzip/xz_inadequate.html

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.

Those are with the default settings but can't you increase the compression ratio target of zstd to match xz and still be significantly faster?

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.

If the compression ratio is about the same, I'd choose zstd. The decompression performance is much better than xz.

And zstd keeps evolving contrary to xz, which means they'll outperforms xz compression ratio in the following years

We can hope!

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 wonder if software compression can now cost compete with compression cards like Intel QuickAssist on constantly loaded servers.

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.

1. https://facebook.github.io/zstd/

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.

[1] http://fastcompression.blogspot.com/2013/12/finite-state-ent...

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.

I'm a lot less concerned with adding a version number and much more concerned with the additional complexity of having to fetch a dictionary.

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.

https://engineering.fb.com/2018/12/19/core-data/zstandard/

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.

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.

That's a really cool looking game.

For someone that's a web developer that's never done game development at all, do you have any recommended resources for learning?

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.

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):

https://bjlkeng.github.io/posts/lossless-compression-with-as...

One of the maintainers of zstd here, AMA

What's the future of binary deltas in Zstd? I saw some work on a github chat, but not sure if it's being seriously planned.

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].

[0] https://github.com/facebook/zstd/releases/tag/v1.4.5

[1] https://github.com/facebook/zstd/wiki/Zstandard-as-a-patchin...

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.

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

We were using modified lz4 (very much molded over our data) that was actually faster than memcpy of data that we were compressing.

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.

1 https://github.com/openzfs/zfs/pull/10278

Is anyone serving zstd over HTTP to browsers (instead of gzip or brotli)? It seems like the speed would be ideal in this use case.

The performance of zstd suffers without a dictionary, making it comparable to brotli on large files, but worse on small files.

Lacking a clear source for a public dictionary suited to the web corpus, there's not much point in putting it in browsers.

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.

[1] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e

[2] https://tools.ietf.org/html/rfc7932#appendix-A

Yeah I think the only holdup is getting an agreement on dictionary or, more likely, dictionaries, to be shipped with the spec implementation

https://tools.ietf.org/html/rfc8478 I'm unfamiliar with the IETF process and whether or not browsers support zstd compression yet.

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.

Usage question: Does it use multicore by default?

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).

Alternatives: zstdmt is an alias for zstd -T0 and zstd will listen to the ZSTD_NBTHREADS environment variable.

Has anyone tried to use zstd on the web with WebAssembly?

Yeah, I've experimented. It is actually surprisingly close to native performance! A testament to the wasm engine, I guess.

There's discussion on this topic here: https://github.com/facebook/zstd/issues/1355

Reply on news.ycombinator.com