borg2: Consider implementing multithreading for lz4

[PhrozenByte]

Following my compression benchmark results in #10315 (comment), we discussed whether lz4 could be made multi-threaded in Borg, similar to how zstd already is.

LZ4 does support multithreading (reported by Phoronix and as implemented for the CLI in lz4/lz4#1336), but this functionality seems to be limited to the CLI tool right now. Unlike zstd, there is no simple threads= option available for library integration, which makes implementation more challenging.

The LZ4 project lists https://pypi.org/project/py-lz4framed/ as a "multi-threadable" Python binding. However, "multi-threadable" in this context means the implementation is thread-safe, not that it provides built-in multithreading. Any parallelization would need to be implemented manually in Borg.

It might be worth investigating:

• Whether Borg currently uses the block-based compression format or the newer frame-based compression format, and what implications a potential switch to the frame-based format would have, given that it appears as if only the latter can be implemented thread-safe
• Whether Borg could leverage LZ4's multithreading support
• Which implementation approach would be most practical
• How the performance would compare to the current zstd multithreaded results, in particular in comparison to zstd,-4

Related: #10161

[ThomasWaldmann]

I did some experiments with claude and, as a side-effect, #10326 was found.

And now that zstd,-4 MT is so fast, there isn't much to win with lz4 MT for compression speed (based on measurements) and it would be quite more effort than what we have with zstd.

[ThomasWaldmann]

I benchmarked the split-and-compress idea against multithreaded zstd. Setup: Silesia corpus cut into 2 MiB buffers (borg's default chunk size), the complete data compressed (no sampling), 4 workers for both codecs, best of 5 passes, liblz4 1.10.0 / libzstd 1.5.7.

lz4 frame MT(4) is the hypothetical implementation: the chunk is split into 4 parts, each part compressed into its own lz4 frame, and the frames are concatenated. That detail is forced - independently compressed raw lz4 blocks cannot be concatenated, because a block's last sequence is literals-only with no offset field, so a decoder cannot tell where the next block starts. Frames are self-delimiting, so LZ4F_decompress walks them one after another. This is not implemented in borg; it is measured standalone with python-lz4.

Compression throughput, 2 MiB chunks, 4 workers

codec	M3 Pro	Ryzen 8500GE	ratio
borg lz4, today (single-threaded)	900 MB/s	921 MB/s	2.10x
lz4 frame MT(4), hypothetical	2574 MB/s	2170 MB/s	2.09x
borg zstd,-4 MT(4), pool per chunk (today)	1771 MB/s	1490 MB/s	2.14x
borg zstd,-4 MT(4), with #10326	2753 MB/s	1598 MB/s	2.14x

Notes:

• Splitting costs lz4 about 0.5% ratio (2.10x -> 2.09x). That is small because lz4's match window is only 64 KiB, so 512 KiB parts lose almost nothing at the boundaries. zstd,-4 still compresses 2.2% smaller than lz4 either way.
• The two zstd rows differ only by compress: reuse the zstd compressor per thread #10326, which keeps libzstd's worker pool alive between chunks instead of building and tearing it down per chunk. Without it, MT zstd pays a full pool setup for every 2 MiB chunk.
• lz4 decompresses 2-3x faster than zstd in every configuration measured (5400-5900 MB/s vs 1800-2800 MB/s). None of this touches that, and it is arguably lz4's more interesting property here.
• The Ryzen figures are the weak part of this table: that CPU is 2x Zen 4 plus 4x Zen 4c, and thread placement between the two core types varies from run to run (25-80% spread between best and worst pass on an otherwise idle machine). With placement fixed by hand - main thread pinned to a Zen 4 core, all worker threads pinned to the four Zen 4c cores - the numbers reproduce to ~1%: lz4 frame MT(4) 2041 MB/s vs borg zstd,-4 MT(4) 1820 MB/s, so lz4-MT leads by ~12% there rather than the ~36% the unpinned column suggests.

Caveat: this measures the codecs in isolation. In a real borg create the compressor shares the machine with chunking, hashing, crypto and I/O, so a codec-level difference of this size does not translate 1:1 into backup time.

[ThomasWaldmann]

Guess not worth the effort.

[PhrozenByte]

#10326, nice! 🚀

I've done a bit of research myself and also got the impression that lz4 should outperform zstd here (2170 MB/s vs. 1598 MB/s on Ryzen is pretty impressive), although implementing it will be anything but trivial. So yeah, that confirms my impression.

Regarding "not worth the effort": I can't really say anything about the effort involved myself - you're the expert here. If you say it gets too complicated, I agree.

Even if multithreaded lz4 were just above the "worth the effort" threshold, I think we might actually gain more from #10161 and parallelizing at the chunk level instead. If that's still reasonably high on the priority list, I don't think it would make much sense to invest much more work into compression-level parallelism. With chunk-level parallelism, we'd probably want fewer workers at the compression level anyway, to avoid nested parallelism and ending up with oversubscription due to too many threads.

So yeah, sounds good to me - thanks for looking into it! 👍