dagutils: DiffEnumerate traverses independent replacement subtrees serially

[eloramirez1356]

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.

git clone https://github.com/eloramirez1356/boxo-diffenumerate-repro.git
cd boxo-diffenumerate-repro
make boxo-test

On my machine:

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:

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:

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:

make kubo-test

One node contains OLD + NEW while the receiver initially contains OLD only. The receiver then performs:

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:

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:

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:

ipfs/kubo#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.