dagutils: DiffEnumerate traverses independent replacement subtrees serially
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 38/100
- Tipo di issue
- Bug
- Chiarezza
- Abbastanza chiara
- Stato di attività
- Tranquilla
- Stack tecnologico
- go
- Ambito
- distributed-systems
Direzione di ricerca
Inizia leggendo dagutils.DiffEnumerate e confrontando il relativo percorso di replacement-pair con il percorso concorrente di merkledag.Walk. Esegui il riproduttore autonomo con make boxo-test e go test -race -count=3 .; il lavoro è completato quando sostituzioni indipendenti espongono un recupero concorrente limitato, preservando la cancellazione, gli errori, la gestione di removed-set, i link duplicati e i limiti delle risorse.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
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:
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.
- Lingua principale
- Go
- Stelle
- 326
- Fork
- 165
- Metriche di merge delle PR
- Nessuna PR unita negli ultimi 30g
Preparare l'ambiente
- Nessun Dockerfile né file Docker Compose
- Ha un modello di pull request
- Nessuna guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di ipfs/boxo
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 70/100
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 46/100
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 55/100
-
dif/medium effort/hours kind/enhancement P3 topic/devexp
Difficoltà 5/5 Più di una settimana Idoneità per principianti 35/100
-
dif/expert effort/weeks kind/enhancement P2
Difficoltà 5/5 Più di una settimana Idoneità per principianti 25/100
Issue simili
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 66/100
unbound-force/gaze#353 ·
I maintainer di solito rispondono entro 1 giorno
-
bug cross-seed ready-for-human
Difficoltà 2/5 1-3 ore Idoneità per principianti 70/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 64/100
OneBusAway/maglev#2102 ·
I maintainer di solito rispondono entro 2 giorni
-
affects-8.5 component/session severity/moderate sig/transaction type/bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
I maintainer di solito rispondono entro 1 giorno
-
area: client enhancement priority: low
Difficoltà 2/5 1-3 ore Idoneità per principianti 75/100
opensro-dev/opensro#3681 ·
I maintainer di solito rispondono entro 1 giorno