dagutils: DiffEnumerate traverses independent replacement subtrees serially
- Dominant language
- Go
- Stars
- 316
- Forks
- 163
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 8
Description
## Summary
`dagutils.DiffEnumerate` appears to traverse independent replacement subtrees serially, while wholly-added subtrees use the concurrent DAG walker.
In a synthetic reproduction using Boxo v0.42.1, replacement-heavy traversal exposes only one NEW `NodeGetter.Get` at a time, while a wholly-added subtree exposes up to 32 concurrent NEW retrievals.
I also reproduced the same behavior end-to-end with Kubo v0.43.0: during `ipfs pin update OLD NEW`, the replacement-heavy case kept the Bitswap wantlist around 1, while the addition case reached ~31-32.
This can have a significant performance impact when updating between large, highly similar DAGs containing many independent replacements.
## Versions
- Boxo: `v0.42.1`
- Kubo used for end-to-end validation: `v0.43.0`
## Minimal reproduction
I created a standalone reproducer here:
https://github.com/eloramirez1356/boxo-diffenumerate-repro
The primary reproduction is Boxo-only and does not require Kubo, Docker, Bitswap, or network access beyond fetching the Go dependencies.
```sh
git clone https://github.com/eloramirez1356/boxo-diffenumerate-repro.git
cd boxo-diffenumerate-repro
make boxo-test
```
On my machine:
```text
replacement: max NEW in-flight = 1; wall = 645ms
addition: max NEW in-flight = 32; wall = 40ms
PASS
```
The exact timings are not important here. The relevant observation is the retrieval frontier:
```text
replacement: max NEW in-flight = 1
addition: max NEW in-flight = 32
```
The test constructs deterministic synthetic OLD/NEW DAGs and adds a small delay only to NEW-only `NodeGetter.Get` calls.
It also passes repeatedly under the race detector:
```sh
cd boxo
go test -race -count=3 .
```
## Kubo/Bitswap end-to-end reproduction
The repository also contains an optional Docker reproduction using two isolated Kubo v0.43.0 nodes:
```sh
make kubo-test
```
One node contains OLD + NEW while the receiver initially contains OLD only. The receiver then performs:
```sh
ipfs pin update OLD NEW
```
The receiver is recreated between the replacement and addition cases so NEW blocks cannot be reused between tests.
With 32 leaves and 15 ms one-way delay applied to source egress, I currently get:
```text
replacement:
wall = 10s
max Bitswap wantlist = 1
addition:
wall = 5s
max Bitswap wantlist = 31
```
This suggests the difference observed at the `NodeGetter` level propagates through Kubo's blockservice/Bitswap retrieval path.
To be clear, I don't think Bitswap itself is serializing these downloads. Rather, the replacement traversal appears to expose a very small retrieval frontier to the underlying retrieval layer.
## Larger controlled experiment
I originally investigated this with a larger synthetic Kubo/Bitswap experiment.
Using:
- 6250 leaves
- 16 KiB leaves
- 30 ms one-way source-egress delay
- Kubo v0.43.0 / Boxo v0.42.1
I measured:
| | Replacement | Addition |
|---|---:|---:|
| Max Bitswap wantlist | 1 | 32 |
| Wall time | 572.139 s | 18.703 s |
| Average throughput | 0.181 MB/s | 5.142 MB/s |
The smaller reproductions in the repository are intended to demonstrate the behavior without requiring maintainers to run this long benchmark.
## Source analysis
From reading `dagutils.DiffEnumerate`, the asymmetry appears to come from how the two cases are traversed.
For wholly-added subtrees, traversal goes through `merkledag.Walk` with concurrent fetching enabled.
For replacement pairs, `DiffEnumerate` recursively processes the changed children from the replacement traversal, effectively waiting on each replacement subtree before moving to the next one.
Conceptually, the behavior appears to be:
```text
wholly-added subtree
-> concurrent Walk
-> multiple NEW Gets can be in flight
replacement pairs
-> recursive DiffEnumerate for each replacement
-> approximately one NEW Get exposed at a time
```
The standalone Boxo reproduction is intended to isolate this behavior without involving Bitswap or networking.
## Expected behavior
For independent replacement subtrees, I would expect it to be possible to expose a bounded concurrent retrieval frontier, similar in spirit to the existing concurrent traversal for wholly-added subtrees.
Any change would of course need to preserve the existing semantics around cancellation, errors, removed-set handling, duplicate links, and bounded resource usage.
I'm not suggesting that the concurrency necessarily needs to be 32 or that a particular implementation should be used.
## Actual behavior
Independent replacement-heavy traversal exposes approximately one NEW retrieval at a time in the reproducer.
With non-trivial retrieval latency, this means latency is repeatedly paid serially rather than being overlapped across independent replacement subtrees.
## Related issue
This looks potentially related to the broader similar-DAG pinning performance reported in:
https://github.com/ipfs/kubo/issues/4124
That issue predates Boxo and, as far as I can tell, does not identify this specific replacement-recursion behavior, so I'm not treating it as a confirmed duplicate.
## Question / possible direction
Would bounded concurrency for independent replacement pairs be appropriate inside `DiffEnumerate`, or would you prefer this concurrency to be introduced at another layer/abstraction?
If this behavior is considered unintended and `DiffEnumerate` is the appropriate place to address it, I'd be interested in working on a fix.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading dagutils.DiffEnumerate and comparing its replacement-pair path with the concurrent merkledag.Walk path. Run the standalone reproducer with make boxo-test and go test -race -count=3 .; done means independent replacements expose bounded concurrent retrieval while preserving cancellation, errors, removed-set handling, duplicate links, and resource bounds.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- distributed-systems
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100