feat(dag/walker): opt-in BloomTracker to avoid duplicated walks#1124
Draft
feat(dag/walker): opt-in BloomTracker to avoid duplicated walks#1124
Conversation
c16a5b7 to
4dad6c1
Compare
VisitedTracker interface for memory-efficient DAG traversal dedup. BloomTracker uses a scalable bloom filter chain (~4 bytes/CID vs ~75 for a map), enabling dedup on repos with tens of millions of CIDs. - BloomTracker: auto-scaling chain, configurable FP rate via BloomParams, unique random SipHash keys per instance (uncorrelated FPs across nodes) - MapTracker: exact dedup for tests and small datasets - *cid.Set satisfies the interface for drop-in compatibility - go.mod: update ipfs/bbloom to master (for NewWithKeys)
4dad6c1 to
c8962fc
Compare
iterative DFS walker that integrates VisitedTracker dedup directly into the traversal loop, skipping entire subtrees in O(1). - LinksFetcherFromBlockstore: extracts links from any codec registered in the global multicodec registry (dag-pb, dag-cbor, raw, etc.) - ~2x faster than legacy go-ipld-prime selector traversal (no selector machinery, simpler decoding, fewer allocations) - WithLocality option for MFS providers to skip non-local blocks - best-effort error handling: fetch failures log and skip, do not mark the CID as visited (allows retry via another pin or next cycle) - benchmarks comparing BlockAll vs WalkDAG across dag-pb, dag-cbor, and mixed-codec DAGs
19bf557 to
224c2ae
Compare
Codecov Report❌ Patch coverage is @@ Coverage Diff @@
## main #1124 +/- ##
==========================================
+ Coverage 62.56% 62.77% +0.20%
==========================================
Files 261 265 +4
Lines 26216 26522 +306
==========================================
+ Hits 16402 16649 +247
- Misses 8125 8166 +41
- Partials 1689 1707 +18
... and 7 files with indirect coverage changes 🚀 New features to boost your workflow:
|
emits entity roots (files, directories, HAMT shards) skipping internal file chunks. core of the +entities provide strategy. - NodeFetcherFromBlockstore: detects UnixFS entity type from the ipld-prime decoded node's Data field - directories and HAMT shards: emit and recurse into children - non-UnixFS codecs (dag-cbor, dag-json): emit and follow links - same options as WalkDAG: WithVisitedTracker, WithLocality - tests: dag-pb, raw, dag-cbor, mixed codecs, HAMT, dedup, error handling, stop conditions
catch unexpected regressions in ipfs/bbloom behavior or BloomParams derivation that would silently degrade the false positive rate. - measurable rate (1/1000): 100K probes produce observable FPs, asserts rate is within 5x of target - default rate (1/4.75M): 100K probes must produce exactly 0 FPs
- NewPrioritizedProvider: stream init error no longer stops remaining streams (e.g. MFS flush error does not prevent pinned content from being provided) - NewConcatProvider: concatenates pre-deduplicated streams without its own visited set, for use with shared VisitedTracker
…vider NewUniquePinnedProvider: emits all pinned blocks with cross-pin dedup via shared VisitedTracker (bloom or map). walks recursive pin DAGs first, then direct pins. NewPinnedEntityRootsProvider: same structure but uses WalkEntityRoots, emitting only entity roots and skipping internal file chunks. existing NewPinnedProvider is unchanged.
- remove unused daggen variable in uniquepinprovider_test.go
…tency match the defensive read-side ctx.Done select pattern already used by NewPrioritizedProvider in the same file
- deduplicate LinkSystem construction used by both LinksFetcherFromBlockstore and NodeFetcherFromBlockstore - wrap blockstore with NewIdStore so identity CIDs (multihash 0x00, data inline in the CID) are decoded without a datastore lookup
identity CIDs (multihash 0x00) embed data inline, so providing them to the DHT is wasteful. the walker now traverses through identity CIDs (following their links) but never emits them. - add isIdentityCID check to WalkDAG and WalkEntityRoots - simplify WalkEntityRoots emit/descend logic - tests for identity raw leaf, identity dag-pb directory with normal children, normal directory with identity child
- inline identity CID check (c.Prefix().MhType == mh.IDENTITY) in all emit paths: WalkDAG, WalkEntityRoots, and direct pin loops in both NewUniquePinnedProvider and NewPinnedEntityRootsProvider - move all identity CID tests to dag/walker/identity_test.go - add provider-level identity tests for direct pins and recursive DAGs
the stack-based DFS was pushing children in link order, causing the last child to be popped first (right-to-left). reverse children before pushing so the first link is on top and gets visited first. this matches the legacy fetcherhelpers.BlockAll selector traversal (ipld-prime iterates list/map entries in insertion order) and the conventional DFS order described in IPIP-0412. - walker.go, entity.go: slices.Reverse(children) before stack push - walker.go: document traversal order in WalkDAG godoc - entity.go: document order parity in WalkEntityRoots godoc - walker_test.go, entity_test.go: add sibling order regression tests
a corrupted pin entry was stopping the entire provide cycle because the goroutine returned on RecursiveKeys/DirectKeys error. change to continue so remaining pins are still provided (best-effort). the error from the pinner iterator already contains context (bad CID bytes, datastore key, etc.) -- sc.Pin.Key is zero-value on error so including it in the log would be noise. matches the best-effort pattern used in WalkDAG/WalkEntityRoots where fetch errors are logged and skipped.
- collectLinks: note that map keys are not recursed (no known codec uses link-typed map keys) - detectEntityType: extract c.Prefix() once for readability - grow: document MinBloomCapacity invariant that prevents small-bitset FP rate issues in grown blooms
gammazero
approved these changes
Mar 24, 2026
Contributor
gammazero
left a comment
There was a problem hiding this comment.
Made a few suggestions but nothing blocking.
| // skip identity CIDs: content is inline, no need to provide. | ||
| // we still descend (above) so an inlined dag-pb directory's | ||
| // normal children get provided. | ||
| if c.Prefix().MhType == mh.IDENTITY { |
Contributor
There was a problem hiding this comment.
Should this be done before any other work is done?
| stack = append(stack, children...) | ||
|
|
||
| // skip identity CIDs: content is inline, no need to provide | ||
| if c.Prefix().MhType == mh.IDENTITY { |
Contributor
There was a problem hiding this comment.
Do this before other work? Prevent polluting tracker with identity CIDs?
Comment on lines
+137
to
+141
| if tracker.Visit(sc.Pin.Key) { | ||
| if !emit(sc.Pin.Key) { | ||
| return | ||
| } | ||
| } |
Contributor
There was a problem hiding this comment.
Matches above logic flow.
Suggested change
| if tracker.Visit(sc.Pin.Key) { | |
| if !emit(sc.Pin.Key) { | |
| return | |
| } | |
| } | |
| // Skip if not first visit. | |
| if !tracker.Visit(sc.Pin.Key) { | |
| continue | |
| } | |
| // Emit pin key on first visit. | |
| if !emit(sc.Pin.Key) { | |
| return | |
| } |
Do we want to track how many pins are skipped and maybe log the number? Maybe even log that there is a x% chance skipping a pin that should be provided?
| // synchronization. | ||
| type VisitedTracker interface { | ||
| // Visit marks a CID as visited. Returns true if it was NOT | ||
| // previously visited (first visit). |
Contributor
There was a problem hiding this comment.
Suggested change
| // previously visited (first visit). | |
| // previously visited (first visit). Returns false if high | |
| // probability that CID was previously visited. |
| // Visit marks a CID as visited. Returns true if it was NOT | ||
| // previously visited (first visit). | ||
| Visit(c cid.Cid) bool | ||
| // Has returns true if the CID was previously visited. |
Contributor
There was a problem hiding this comment.
Suggested change
| // Has returns true if the CID was previously visited. | |
| // Has returns true if there is a high probability that the CID | |
| // was previously visited. Returns false if NOT visited. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Warning
not ready for review, this is a sandbox for running CI
Summary
New
dag/walkerpackage for memory-efficient DAG traversal with bloom filter deduplication, plus new pinned-provider strategies that use it to avoid re-announcing duplicate blocks across pins.dag/walker(new package)VisitedTrackerinterface with two implementations:BloomTracker-- auto-scaling bloom filter chain (~4 bytes/CID vs ~75 for a map), with uncorrelated false positives across nodes (unique random SipHash keys per instance)MapTracker-- exact dedup for tests and small datasetsWalkDAG-- iterative DFS traversal with integrated dedup, codec-agnostic link extraction (dag-pb, dag-cbor, raw, and any registered codec). ~2x faster than the legacygo-ipld-primeselector-based walker.WalkEntityRoots-- entity-aware traversal that emits only file/directory/HAMT shard roots instead of every block, skipping internal file chunks.pinnerNewUniquePinnedProvider-- emits all blocks reachable from pins with cross-pin bloom dedup (recursive DAGs first, then direct pins).NewPinnedEntityRootsProvider-- same but emits only entity roots viaWalkEntityRoots.providerNewPrioritizedProvidernow continues to the next stream when one fails instead of stopping all streams.NewConcatProvideradded for pre-deduplicated streams that don't need thecidutil.StreamingSetoverhead.Other