Support zstd compression for binary caches

[domenkozar]

https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/

Requested by @nh2 in cachix/cachix#55 (comment)

[nh2]

Moving discussion from cachix/cachix#55 (comment) over here:

Note that in my experience, zstd and brotli don't compress binaries better than xz.

Nix does already support brotli compression (e.g. nix copy --to file:///bla?compression=br). Unfortunately, the default compression quality (11) makes it superslow, about 10x slower than xz -6 (with a worse compression ratio). OTOH with quality 6 it's 6x faster than xz -6. So we really should have a setting in Nix for the compression quality.

@edolstra That's correct, xz remains to have the best compression ratio (this is also stated in the article I linked). The idea is that it compresses a lot faster.

Here are some examples:

zstd v1.3.4
brotli 1.0.4
xz 5.1.0alpha
gzip 1.6
lzop 1.03, LZO library 2.08

% du -sh /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/
310M  /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | lzop | pv > /dev/null
 140MiB 0:00:01 [ 130MiB/s]

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | gzip | pv > /dev/null
98.2MiB 0:00:11 [8.85MiB/s]

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | zstd | pv > /dev/null
94.5MiB 0:00:01 [60.8MiB/s]

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | xz | pv > /dev/null
66.6MiB 0:02:10 [ 524KiB/s]

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | brotli --quality=6 - | pv > /dev/null
79.6MiB 0:00:13 [5.77MiB/s]

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | brotli --quality=3 - | pv > /dev/null
  93MiB 0:00:02 [  31MiB/s]

zstd is

• 7x faster than gzip while having the same output size
• 120x faster than xz while having 30% increased output size
• 2x faster than brotli --quality=4 while having the same output size

It also supports mutliple cores; when used, that bumps the above numbers by some more integer factors:

% tar c /nix/store/cn8yyi1z0y79hjnvs7qpmrb23drphhb6-chromium-65.0.3325.162/ | zstd -T4 | pv > /dev/null
94.5MiB 0:00:00 [ 140MiB/s]

[nh2]

So we really should have a setting in Nix for the compression quality.

@edolstra That would be very appreciated; while zstd seems to do even better than brotli, being able to use brotli at level 4 would already be a huge improvement (4x vs gzip, 60x vs xz).

[dtzWill]

We already have an option for enabling multithreaded compression, options for compression level seem like an easy addition (I say this to indicate that anyone interested can tackle this).

Hardest part seems to be sorting out how this should be specified in context of each compression method having different ranges and defaults. But I think they all support a basic notion of integer level so this seems workable...

As for zstd, implementing support for it is likely also rather straightforward -- I haven't seen it's API but AFAIK they are all loosely similar. I was able to add brotli support pretty easily, for example, and I'd never used it's API before.

I can't promise support for every compression technique will be eagerly merged but zstd seems reasonable addition...

In short: these features likely take only an hour or two of an interested party's dev time, so if you want this supported consider tackling it and submitting a PR! The relevant parts of Nix involved here are rather accessible and don't rely on much beyond the task at hand (and maybe source/sink abstractions).

[davidak]

FYI: Arch's Switch To Zstd: ~0.8% Increase In Package Size For ~1300% Speedup In Decompression Time

So this might speed up installation of packages.

[AleXoundOS]

How did they achieve only 0.8% package size increase? Impressive ratio for zstd. Maybe xz compressed package size was a factor of 0.8 compared to zstd and not percentage?
Max compression level? Looking and the zstd manual, it's not promising, affecting decompression:

--ultra
              unlocks high compression levels 20+ (maximum 22), using a lot more memory. Note that decompression will also require more memory when using these levels.

Nix already uses a lot of RAM.

[AleXoundOS]

The request is interesting. But the current points for xz (lzma) are saved network bandwidth and server storage costs.
If it happens that download speed is slower than decompression while both are done in a streaming fashion (currently not), then we (users) hardly win anything.

$ dd if=/nix/store/dbc7wxisaax83lsg54wwrlhy9xnd5n1y-linux-4.19.84.tar.xz | xzcat > /dev/null
201853+0 records in
201853+0 records out
103348736 bytes (103 MB, 99 MiB) copied, 6.89651 s, 15.0 MB/s

15 MiB/s is 120 Mibit/s. I wonder if many of us do really have this download speed from cache.nixos.org. So the request is more oriented towards uploading caches to private servers.

As for common users I don't know if it is tricky to implement download->decompression streaming for nix store (most notably hash validation should happen after? (but xz -d checks integrity too)). But this brings to a question what are we going to solve and by which means?

[edolstra]

Nix already does download -> decompression streaming.

[yorickvP]

Yes, I get 120 mbit/s from the cache, but I think the real benefit is on the compression side, where zstd uses significantly less CPU.

[nagisa]

I think the real benefit is on the compression side

Seconding this. nix copy for large outputs generally spends a ton of time just compressing and failing to saturate the uplink. Parallel compression helps (and also comes at a cost of compression ratio), but is still insufficient to saturate the uplink in certain setups.

[AleXoundOS]

Nix already does download -> decompression streaming

Oh, good. My fault I haven't observe it yet.
Then it's solely the compression side benefit (contrary to Arch Linux's aims).