Repository navigation
extract of a single large item from a remote repo is quadratic in its chunk count (list.pop(0) in RemoteRepository.call_many) #10450
Description
Note: I have created this issue with the help of Claude Opus 5.5. All observations and diagnostics are its, not mine. I understand that there is a lot of AI trash these days. So feel free to investigate or ignore. In any case, I hope it's useful for others. We have worked around it by using larger chunks.
Thanks.
Here's what Claude found:
Have you checked borgbackup docs, FAQ, and open GitHub issues?
Yes. #8075 had a similar symptom (a slow extract from a remote repo), but was traced to a kernel/ext4 issue. This one is CPU-bound in borg.
Is this a BUG / ISSUE report or a QUESTION?
Bug (performance).
System information
- borg client: 1.4.4 (Ubuntu 26.04 package), Python 3.14.4, x86_64
- borg server: 1.4.4 (
borg-1.4 serveon a Hetzner Storage Box), accessed via ssh:// - The repository is encrypted with repokey-blake2 and compressed with lz4.
Describe the problem you're observing
We back up a database as a single stdin item:
mariadb-backup --backup --stream=mbstream | borg create --chunker-params buzhash,14,18,16,4095 --stdin-name beatunesdb.mbstream ::db-... -
The item is 1.22 TB (505 GB stored) in about 12.3 M chunks.
borg extract --stdout ::db-... beatunesdb.mbstreamfrom a local copy of such a repository takes 47 minutes.- The same extract from the remote repository runs at about 6 MB/s. The borg client sits at 100 % of one core, and the whole extract takes about 17 hours.
perf record on the client shows about 99 % of the samples in a single libc function (memmove). The code path is RemoteRepository.call_many (src/borg/remote.py on 1.4-maint):
calls = list(calls), thencalls.pop(0)for every chunk (l. 839, 929/931). Forget_many(item.chunks, is_preloaded=True)that list holds all 12 M chunk ids.self.preload_ids.pop(0)for every chunk (l. 942).preload()appends all chunk ids of the item (self.preload_ids += ids).waiting_for.pop(0)(l. 854). That list is bounded by MAX_INFLIGHT, so it doesn't matter here.
Each pop(0) shifts the rest of the list, so the extract of one item costs O(n²) in its number of chunks. A micro-benchmark (CPython 3.14, list of ints):
| list length | list.pop(0) |
|---|---|
| 1 M | 0.26 ms |
| 4 M | 1.0 ms |
| 12 M | 2.7 ms |
collections.deque.popleft() on 12 M items takes 0.09 µs. With two such pops per chunk at 12 M chunks, this adds up to many hours. That matches what we see, and it gets faster towards the end of the extract as the lists shrink.
This probably also affects borg mount, borg check --verify-data and other preloading paths for large items. We haven't measured those.
Suggested fix
Use collections.deque for calls and self.preload_ids (and waiting_for), with popleft() instead of pop(0). The calls[0] peek and += / extend work the same on a deque. self.chunkid_to_msgids[chunkid].pop(0) operates on short per-chunk lists and is fine.
As a workaround we switched to larger chunks (buzhash,17,21,19,4095, ~512 KiB), which cuts the chunk count and the quadratic cost.
Can you reproduce the problem?
Yes, every time, with any single item of several million chunks in a remote (ssh://) repository, e.g. a large stdin item created with small chunker parameters.
Activity
ThomasWaldmann commentedon Sep 28, 2026
Thanks for the issue report, it sounds like a good analysis.
You have an extreme case there:
A very large single item AND a rather small (~64KB) chunk size, which amplifies the problem.
So guess your workaround helps for this performance issue at the cost of slightly(?) worse deduplication. It will still produce a large amount of chunks though, so make sure you have enough RAM to deal with the overall chunks amount in that repository.
The proposed fix sounds good. An alternatve slightly "hackish" solution might be reversing the list, so that we do not pop from the front, but from the back (avoiding the memmove).
ThomasWaldmann commentedon Sep 28, 2026
Besides extreme cases like the above, this might well have a performance impact also on less extreme cases, too.
ThomasWaldmann commentedon Sep 28, 2026
Issue reproduced - it is quadratic. Implementing a fix for 1.4.6 release...
This is an important fix, for borg 1.x and also for borg 2 (where it affects transfers from borg 1.x repositories).
remote: use deques for the RPC call queues, fixes #10450
Merge pull request #10454 from ThomasWaldmann/remote-deque-10450-1.4
ThomasWaldmann commentedon Sep 28, 2026
1.2-maint fix: ...
1.4-maint fix: #10454
master fix: #10456
ThomasWaldmann commentedon Sep 28, 2026
I reproduced this and measured the proposed
collections.dequefix.Setup: Ryzen 5 8500GE (Zen 4, 16 MB L3), Debian 13, Python 3.13. The repo is
repokey-blake2with lz4 and holds one stdin item of N unique 4 KiB chunks (--chunker-params fixed,4096). The data compresses to almost nothing, so these numbers show the per-chunk cost, not I/O. "Remote" isssh://__testsuite__/...(a localborg serveover pipes, no ssh or network), so the times are pure client CPU.borg 1.4:
borg extract --stdout ::a bigWithout the fix, the extra time grows 3.9×, 5.0× and 8.4× per doubling of the chunk count. That is quadratic, and worse once the lists no longer fit in the L3 cache and every
pop(0)memmove goes to DRAM. At 2 M chunks the unpatched client already drops to about 9.5 MB/s, close to the 6 MB/s reported here. With the deques, remote extract is linear at about 15.5 µs per chunk, and your 12.3 M-chunk case takes about 3 minutes on this box. Peak memory does not change.borg 1.2: same test, 1 M chunks
local 10.0 s, remote 1.2-maint 112.7 s, remote with deque fix 15.4 s.
master (borg 2)
borg2's own repository access (borgstore) has no such lists, so extract/mount/check on borg2 repos are not affected. The only remaining
calls.pop(0)is in the legacy remote client. It is reached byborg transfer --from-borg1 --chunker-paramsfrom a remote borg 1.x repo, which is quadratic too, though milder because there is no preload list there:PRs
Reversing the lists instead of using deques would work for
calls. It would not work well forpreload_ids, though:preload()appends ids for every item, so keeping that list reversed means prepending each time, which becomes quadratic again with many small items. So all PRs use deques.hendriks73 commentedon Sep 28, 2026
Gee, you're quick, @ThomasWaldmann ! Thanks for fixing this!
remote: use deques for the RPC call queues, fixes #10450
Merge pull request #10457 from ThomasWaldmann/remote-deque-10450-1.2
legacy remote: use deques for the RPC call queues, fixes borgbackup#1…
Merge pull request borgbackup#10456 from ThomasWaldmann/legacy-remote…