borg2 extract: parallel decompression, thread-safety blocker in LZ4

[ThomasWaldmann]

borg extract is fully serial today. Profiling shows ~55% of its cpu is per-chunk work that is trivially parallel (decompress + decrypt), and a throwaway experiment gets 2.8x on wallclock. Filing the plan, the numbers and - importantly - a thread-safety blocker that has to be fixed first.

This cannot use zstd's internal multi-threading

Worth stating up front, because it is the obvious first guess: libzstd has no multi-threaded decompression. DecompressionParameter has exactly one member, window_log_max - there is no nb_workers counterpart to the compression side (#9961). A single frame cannot be split because blocks back-reference earlier data.

The parallelism has to come from borg decompressing independent chunks concurrently. Two things make that possible:

• the zstd binding releases the GIL: measured 990 / 1886 / 3373 / 4046 MB/s at 1 / 2 / 4 / 8 threads
• the AEAD layer already has with nogil: around the EVP calls (low_level.pyx:321,543,613), so decryption parallelises in the same worker

Where the time goes today

borg extract, 6 GiB archive, zstd,3 / aes256-ocb / sha256 ids, master f8dee0c, native sampling, Apple M3 Pro (12 cores):

	share of extract cpu
zstd decompression	48.1%
file write	23.9%
memory management	17.5%
aes-ocb decryption	6.6%
file read	3.3%
python interpretation	0.6%

Experiment and result

Crude patch to Archive.fetch_many() (archive.py:352): submit repo_objs.parse() to a bounded ThreadPoolExecutor, yield strictly in submission order. 6 GiB archive, median of 3, output sha256-verified against the source on every run:

workers	extract	MB/s	cpu	speedup	correct
off	10.0s	614	8.8s	1.00x	yes
2	5.2s	1178	9.4s	1.92x	yes
4	3.6s	1725	9.9s	2.81x	yes
8	3.9s	1586	10.7s	2.58x	yes
12	4.1s	1513	10.7s	2.46x	yes

Two things to note:

• It peaks at 4 and then regresses. Beyond that the serial write path is the limit and extra workers only add contention (cpu climbs 9.9s -> 10.7s for less throughput). A default of 4, or min(4, cpu_count()), looks right - not cpu_count() like BORG_ZSTD_MT_WORKERS.
• The cpu cost is small: +12% cpu for 2.81x wall. Compare +22% for zstd-mt (zstd multithreading: borg never sets nb_workers, and job_size must be forced for it to help #9961) and +55% for blake3-mt (use multi-threaded blake3 for big chunks, #9958 #9959). This is much closer to free than either.

I predicted ~1.6x from Amdahl (54.7% parallelisable) and was wrong by a lot. The reason is that file write and memory management are not all serial overhead: the AEAD output buffer alloc/free and zstd's output assembly move into the worker threads together with the decompression.

Thread-safety: LZ4.decompress() is NOT thread-safe

This is a blocker, and it affects the default compression.

compress.pyx has a module-level shared scratch buffer:

https://github.com/borgbackup/borg/blob/master/src/borg/compress.pyx#L89

buffer = Buffer(bytearray, size=0)

LZ4 uses it in both directions - _decide() (line 262) and, critically, decompress() (line 288):

                buf = buffer.get(osize)
                dest = <char *> buf

Two threads decompressing lz4 chunks concurrently get the same bytearray and write into it simultaneously. The zstd path does not touch this buffer, which is why the experiment above looked clean - the test repo used zstd.

Demonstrated on a 1.5 GiB archive, extract output sha256-compared to the source, 3 trials each:

=== -C lz4 ===
  serial       3/3 correct  OK
  8 workers    0/3 correct  *** CORRUPTION / FAILURE ***

=== -C zstd,3 ===
  serial       3/3 correct  OK
  8 workers    3/3 correct  OK

Since both runs used aes256-ocb and only the compressor differed, this also tells us the AEAD decrypt path is thread-safe - low_level.pyx allocates its output per call and the decrypt IV comes from the envelope, so there is no shared mutable state.

Fixing it means giving each thread its own scratch buffer - thread-local, or per-decompressor-instance, or simply allocating in LZ4.decompress() and relying on the Buffer only for the compress side. Whichever way, the safety fix has to land before or with any parallel consumer, otherwise anyone enabling this on an lz4 repo gets silent data corruption.

Other state considered:

• parsed_cache is an LRUCache (OrderedDict-backed, no locking) and is not thread-safe. In the design below it is only touched from the main thread, so no lock is needed - but that is a property of the design, not of the class, and should be commented as such.
• repository.get_many() is a generator advanced only from the main thread.
• The zero_chunk_ids memoisation is written on the main thread in the same loop.
• Worth auditing ZLIB/LZMA decompress for the same shared-buffer pattern before enabling this for those.

Plan

Step 1 (done) - throwaway patch, measure the ceiling. Result above: 2.81x, so it is worth building.

Step 2 - fix LZ4.decompress() thread-safety. Standalone, useful on its own, and a prerequisite.

Step 3 - real implementation in fetch_many():

• bounded look-ahead pool (queue ~2x workers, so ~50 MB of 2 MiB chunks at 12 workers - comparable to one pack)
• yield strictly in submission order; extract_item depends on it and violating it corrupts files silently, so this wants an explicit test
• exceptions raised at .result() so IntegrityError still names the right chunk id
• BORG_EXTRACT_WORKERS to control it, same lazy+cached env pattern as BORG_ZSTD_MT_WORKERS; default 4-ish given the regression past that
• check parsed_cache before submitting, populate it on the main thread

Step 4 - extend to borg check --verify-data, which is the same parse-every-chunk shape with no write path at all, so it should scale better than extract.

Caveats

• One machine (12 cores), one workload shape, warm cache. A 2-core box will see much less, and a cold/slow disk may move the bottleneck to reads entirely.
• Highly compressible test data maximises decompression's share. On incompressible archives zstd bails out and the win shrinks.
• If borg later grows chunk-level parallelism elsewhere (Multithreading #37, multithreading: input file discovery / reading parallelism #3500), this pool and that one must not stack.

🤖 Generated with Claude Code