borg2+: multithreading / parallelism

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 (#10014), and in the AES chunkers'
scan kernels (PR #10103). Without this, threads that call into these paths just serialize.
- Multi-threaded blake3 for big chunks, #9958. Threshold `BLAKE3_MT_THRESHOLD_KIB` = 256 KiB,
overridable via `BORG_BLAKE3_MT_THRESHOLD`.
- Multi-threaded zstd for big chunks, #9961 (follow-up of #8217). Threshold
`ZSTD_MT_MIN_SIZE` = 768 KiB, `nb_workers` = `min(cpu_count, 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 (#9988). Up to ~2x when the two take
about the same time.
- Thread-safety groundwork that any further work depends on: thread-safe `LRUCache` (#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* (#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 #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: https://github.com/enkore/borg/commit/4664f2df8bdf9a8d54e9fc18a571ca4e8a094957
- 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 #10014 / PR #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:
https://github.com/restic/restic/pull/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 #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
#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 #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 #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 #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.