multithreading / parallelism in borg2: state of things, hard constraints, next steps

[ThomasWaldmann]

This consolidates the old multithreading umbrella tickets #37 (2015), #929 (2016) and #3500 (2017)
into one up-to-date place. Those threads span 10 years, ~150 comments, and most of their content is
about borg 1.0/1.1 code that no longer exists (remote.py, AES-CTR, OpenSSL 1.0) or about
Bountysource, which does not exist as a company any more.
Everything from them that is still valid for borg2 is collected below; they are closed in favour of
this ticket and stay readable for the full history.

Parallel decompression on extract is tracked separately in #10032 and is not repeated here.
The closed tickets #8217 and #9961 hold the measurements the compression thresholds below are based
on and stay the reference for compressor-internal multithreading.

Scope

"Multithreading" in borg has always meant three quite different things, and mixing them up is what
made the old tickets hard to follow:

1. Parallelism inside a library we call (zstd, blake3) - done, see below.
2. Overlapping one slow stage with another (I/O with CPU) - partly done, cheap, low risk.
3. Running the same stage on N cores (N chunkers, N encryptors) - not done, needs a crypto
   redesign, and this is the part that all the old "borg only uses one core" complaints are about.

Already done in borg2 master

The "limited multithreading" line of work from 2026, which is what the last comments in #37 and #929
were pointing at:

• GIL released in the pure-C hot paths of chunkers and crypto (chunkers, crypto: release the GIL in pure-C hot paths #10014), and in the AES chunkers'
  scan kernels (PR chunkers: release the GIL in the AES chunkers' scan kernels #10103). Without this, threads that call into these paths just serialize.
• Multi-threaded blake3 for big chunks, borg2: use blake3-mt #9958. Threshold BLAKE3_MT_THRESHOLD_KIB = 256 KiB,
  overridable via BORG_BLAKE3_MT_THRESHOLD.
• Multi-threaded zstd for big chunks, zstd multithreading: borg never sets nb_workers, and job_size must be forced for it to help #9961 (follow-up of Use multithreaded zstd compression #8217). Threshold
  ZSTD_MT_MIN_SIZE = 768 KiB, nb_workers = min(cpu_count, 4) for chunks (compression: cap the default zstd MT workers at 4 for chunks #10115) - 4 workers
  beat 12 on every corpus tested on a 12-core machine.
• create: storing a pack overlaps with building the next one (borg2 create: overlap pack store and build of next pack? #9988). Up to ~2x when the two take
  about the same time.
• Thread-safety groundwork that any further work depends on: thread-safe LRUCache (lrucache: allow replacing an entry, make it thread-safe #10041),
  per-thread LZ4 scratch buffers, bounded/daemonized lock-refresh and pack-store threads.

Hard constraints (verified on current master)

These are the reasons "just add a thread pool" does not work, and they are the modern version of
the "likely AES counter uniqueness is broken" note from the very first comments in #37:

• AEADKeyBase.encrypt is stateful. It keeps session_blocks and takes self.cipher.next_iv()
  (src/borg/crypto/key.py). Two threads encrypting concurrently with one key object can hand out
  the same IV - nonce reuse under OCB/ChaCha20, i.e. a crypto break, not a race that costs
  performance. Decryption is thread-safe (fresh cipher per call), which is why parallel
  extract (borg2 extract: parallel decompression #10032) is reachable and parallel create is not.
  Any same-stage encrypt pool needs per-thread sessions (own key/session id and IV space) first.
• borgstore serializes store operations with one internal RLock. Threads can therefore overlap
  I/O with CPU, but not I/O with I/O. Parallel repository I/O would have to be a borgstore feature
  first.
• ChunkIndex is single-owner - only the calling thread may touch it.
• The chunker yields memoryviews into a reusable buffer, so handing a chunk to another thread
  requires a copy.
• Compressor-internal MT does not scale down to chunk size. borg compresses each chunk on its
  own, target size 2 MiB and often far less; splitting that further loses more to thread setup than
  it wins. Measured in Use multithreaded zstd compression #8217: with 10 GB of chunk-sized inputs, workers>0 was never faster than
  workers=0, and at levels 6-15 it was 1.5-2.6x slower. This is why the thresholds above exist.

Design knowledge worth keeping

From #929 - the staged pipeline, still the reference design:

finder -q- reader -q- id-hasher -q- compressor -q- encryptor -q- writer

One thread per stage, connected by queue.Queue, deliberately no same-stage parallelism. It can
be introduced in steps by fusing stages, e.g. finder/reader -q- hasher/compressor/encryptor -q- writer.
It solves "CPU idle while waiting for I/O" and "I/O idle while waiting for CPU"; it does not solve
"one slow compressor", and shouldn't try to. A useful side effect is that the stages get untwisted
and communicate over well-defined data structures.

From #37:

• enkore's actor-style plan and prototype (2017) is the same idea with more stages and an explicit
  metadata/error channel: enkore@4664f2d
• The measured result of that prototype: ~20-30% faster wall clock at ~100% more CPU on large files,
  and ~20% slower on small files (quad-core Xeon). The lesson stated there still holds: the design
  scales, but the consume/produce loops have to run without the GIL, i.e. in native code - which is
  exactly what chunkers, crypto: release the GIL in pure-C hot paths #10014 / PR chunkers: release the GIL in the AES chunkers' scan kernels #10103 started laying down.
• An alternative that never got tried: keep the logic single-threaded and await only the expensive
  operations (chunking, crypto, compression) on thread pools. Break points stay explicit, so the
  logic needs no locking.
• restic scales its worker counts by whether the operation is CPU- or I/O-bound:
  Adjust worker goroutines to number of backend connections restic/restic#3611 - worth copying if we ever pick worker counts
  automatically.
• Free-threaded CPython (3.13+) changes the arithmetic of all of this and should be re-evaluated
  rather than assumed: https://codspeed.io/blog/state-of-python-3-13-performance-free-threading

Measurements worth keeping: read parallelism per storage type

#3500 collected ~12 measurements with fd0's https://github.com/fd0/prb (one traversal thread,
N reader threads) across very different storage. Condensed, throughput at N workers relative to 1:

storage	best N	speedup	note
single HDD (internal, 7200rpm)	1	-	monotonically worse with more workers, 0.68x at 10
USB HDD, NTFS, no NCQ	1	-	0.25x at 10 workers - seek thrashing
2x HDD mirror	2	1.75x	two heads, no gain beyond
SATA SSD	3-4	1.68x	flat plateau afterwards
NVMe, many small files	4-6	~3.0x	flat afterwards, 3.2x at 10, no penalty
NVMe, few very large files	1	-	2.67 GB/s at 1 worker, 1.8 GB/s at 3+
8-disk software RAID5 (HDD)	8-10	~2x	still climbing at 10
8-disk RaidZ2	5-9	~2.5x	warm ARC; 14x on the cold first pass
MooseFS, 13ms RTT	>10	6.1x	latency hiding, still climbing at 10
AWS EFS (provisioned)	>10	4.4x	still climbing at 10

What this says for borg2:

• There is no single good default. The win is latency hiding, and it is huge for network/object
  storage and multi-spindle arrays, zero-to-negative for a single spinning disk and for streaming
  few huge files. Any reader parallelism must be tunable, with a conservative default (fd0's
  original recommendation in multithreading: input file discovery / reading parallelism #3500 was 2), and ideally settable per source.
• For incremental backups the interesting bottleneck is not reading file contents at all. borg
  does not open unchanged files; it stats them and fetches xattrs/ACLs/flags. Several reporters in
  multithreading: input file discovery / reading parallelism #3500 (4.2M files, 750k dirs) were bound by traversal, not by reads. A parallel scanner
  (traversal + stat + xattr/ACL) is a separate, probably more valuable item than parallel readers,
  and it is the one genuinely unfinished idea from multithreading: input file discovery / reading parallelism #3500.
• Windows/NTFS is reported to be disproportionately slow single-threaded; robocopy defaults to 8
  threads. Worth measuring before assuming the POSIX numbers transfer.

Next steps (each one its own ticket/PR, in rough order of value/risk)

1. check/verify_data: iterate in pack order and use get_many instead of per-chunk get, so it
   does one store request per pack instead of one ranged read per chunk. No threads at all. This also
   covers the "verify data in parallel" half of the closed repo check speedup: add ability to restart an interrupted check, verify data in parallel #1952.
2. Read-ahead in Repository.get_many: one background thread loads pack N+1 while the caller parses
   pack N. Hint-only, falls back to the sync path on any failure. Helps extract/tar/transfer on
   sftp/rest/NFS; no benefit for mount, which fetches one chunk per call.
3. Parallel input scanning (traversal + stat/xattr/ACL) with a tunable, conservative worker count -
   the remaining substance of multithreading: input file discovery / reading parallelism #3500.
4. repo-compress: prefetch the next pack while recompressing the current one.
5. create formatter thread: move chunk formatting including all encryption onto one single
   worker thread. This keeps the encrypt session single-threaded by construction, so it needs no
   crypto changes, and buys ~1.1-1.4x on CPU-bound full backups (about nothing on incrementals).
   Needs flush barriers where chunks must be durable before metadata refers to them.
6. Re-evaluate on free-threaded CPython, and only then consider same-stage pools - which requires the
   per-thread crypto session redesign described above.

Explicitly not planned: a full queued/actor rewrite of the whole pipeline in one step (the 2016
multithreading branch was exactly that and was abandoned because it could not be kept in sync),
compressor-internal MT below the thresholds, and any same-stage encrypt pool before the crypto work.