ipfs / ipfs/boxo

dagutils: DiffEnumerate traverses independent replacement subtrees serially

Open
#1,208 0 comments 0 reactions 0 assignees View on GitHub
need/triage
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.