Documentation
¶
Overview ¶
Package walker provides memory-efficient DAG traversal with deduplication. Optimized for the IPFS provide system, but useful anywhere repeated DAG walks need to skip already-visited subtrees.
The primary entry point is WalkDAG, which walks a DAG rooted at a given CID, emitting each visited CID to a callback. When combined with a VisitedTracker (e.g. BloomTracker), entire subtrees already seen are skipped in O(1).
For entity-aware traversal that only emits file/directory/HAMT roots instead of every block, see WalkEntityRoots.
Blocks are decoded using the codecs registered in the process via the global multicodec registry. In a standard kubo build this includes dag-pb, dag-cbor, dag-json, cbor, json, and raw.
Use LinksFetcherFromBlockstore to create a fetcher backed by a local blockstore. For custom link extraction (e.g. a different codec registry or non-blockstore storage), pass your own LinksFetcher function directly to WalkDAG.
Index ¶
- Constants
- func BloomParams(fpRate uint) (bitsPerElem uint, hashLocs uint)
- func WalkDAG(ctx context.Context, root cid.Cid, fetch LinksFetcher, emit func(cid.Cid) bool, ...) error
- func WalkEntityRoots(ctx context.Context, root cid.Cid, fetch NodeFetcher, emit func(cid.Cid) bool, ...) error
- type BloomTracker
- type EntityType
- type LinksFetcher
- type MapTracker
- type NodeFetcher
- type Option
- type VisitedTracker
Constants ¶
const ( // DefaultBloomFPRate is the target false positive rate, expressed as // 1/N (one false positive per N lookups). At the default value of // ~1 in 4.75 million (~0.00002%), each CID costs ~4 bytes (32 bits) // before ipfs/bbloom's power-of-two rounding. // // This is low enough for most IPFS deployments. IPFS content // typically has multiple providers, so a single node's false // positive has no impact on content availability. Any CID skipped // by a false positive is caught in the next reprovide cycle. // // Actual memory depends on how [BloomTracker] chains blooms; see // the scaling table in its documentation. As a rough guide, a // single bloom sized for N items uses N*32 bits rounded up to the // next power of two (e.g. 2M CIDs -> ~8 MB, 10M CIDs -> ~64 MB). // // Lowering this value (e.g. 1_000_000) uses less memory per CID // but skips more CIDs. Raising it (e.g. 10_000_000) uses more // memory but skips fewer. DefaultBloomFPRate = 4_750_000 // DefaultBloomInitialCapacity is the number of expected items for // the first bloom filter when no persisted count from a previous // cycle exists. 2M items produces an ~8 MB bloom at the default FP // rate, covering repos up to ~2M CIDs without chain growth. DefaultBloomInitialCapacity = 2_000_000 // BloomGrowthMargin is multiplied with the persisted CID count from // the previous reprovide cycle to size the initial bloom. The 1.5x // margin provides headroom for repo growth between cycles so that // a stable repo does not trigger chain growth on every cycle. BloomGrowthMargin = 1.5 // BloomGrowthFactor determines how much larger each new bloom in the // chain is compared to the previous one. 4x keeps the chain short // (fewer blooms = less Has() overhead) while converging quickly to // the actual repo size. BloomGrowthFactor = 4 // MinBloomCapacity is the smallest expectedItems value accepted by // [NewBloomTracker]. ipfs/bbloom derives k probe positions from a // single SipHash via double hashing (h + i*l mod size). For small // bitsets the stride patterns overlap, pushing the actual FP rate // far above the designed target. Empirically, at capacity=1000 // (32K-bit bitset) with k=22 the FP rate is ~50x worse than // theory; at 10000 (512K bits) it matches. 10000 uses ~64 KB of // memory while ensuring the actual FP rate matches the design. MinBloomCapacity = 10_000 )
Default bloom filter parameters.
See NewBloomTracker for creating a tracker with a specific FP rate.
Variables ¶
This section is empty.
Functions ¶
func BloomParams ¶
BloomParams derives ipfs/bbloom parameters (bits per element, hash location count) from a target false positive rate expressed as 1/N.
The number of hash functions k is derived as round(log2(N)), and bits per element as k / ln(2). Because k must be a positive integer, not every FP rate is exactly achievable -- the actual rate will be equal to or better than the target. Additionally, ipfs/bbloom rounds the total bitset to the next power of two, which further improves the actual rate.
func WalkDAG ¶
func WalkDAG( ctx context.Context, root cid.Cid, fetch LinksFetcher, emit func(cid.Cid) bool, opts ...Option, ) error
WalkDAG performs an iterative depth-first walk of the DAG rooted at root, calling emit for each visited CID. Returns when the DAG is fully walked, emit returns false, or ctx is cancelled.
The walk uses an explicit stack (not recursion) to avoid stack overflow on deep DAGs. For each CID:
- VisitedTracker.Visit -- if already visited, skip entire subtree. The CID is marked visited immediately (before fetch). If fetch later fails, the CID stays in the tracker and won't be retried this cycle, but is caught in the next reprovide cycle. This avoids a double bloom scan per CID.
- If WithLocality is set, check locality -- if not local, skip.
- Fetch block via fetch -- on error, log and skip.
- Push child link CIDs to stack (deduped when popped at step 1).
- Call emit(c) -- return false to stop the walk.
Traversal order ¶
Pre-order DFS with left-to-right sibling visiting: the root CID is always emitted first, and children are visited in the order they appear in the block's link list. This matches the legacy fetcherhelpers.BlockAll selector traversal and the conventional DFS order described in IPIP-0412.
func WalkEntityRoots ¶
func WalkEntityRoots( ctx context.Context, root cid.Cid, fetch NodeFetcher, emit func(cid.Cid) bool, opts ...Option, ) error
WalkEntityRoots traverses a DAG calling emit for each entity root.
Entity roots are semantic boundaries in the DAG:
- File/symlink roots: emitted, children (chunks) NOT traversed
- Directory roots: emitted, children recursed
- HAMT shard nodes: emitted (needed for directory enumeration), children recursed
- Non-UnixFS nodes (dag-cbor, dag-json, etc.): emitted AND children recursed to discover further content. The +entities optimization (skip chunks) only applies to UnixFS files; for all other codecs, every reachable CID is emitted.
- Raw leaf nodes: emitted (no children to recurse)
Same traversal order as WalkDAG: pre-order DFS with left-to-right sibling visiting. Uses the same option types: WithVisitedTracker for bloom/map dedup across walks, WithLocality for MFS locality checks.
Types ¶
type BloomTracker ¶
type BloomTracker struct {
// contains filtered or unexported fields
}
BloomTracker tracks visited CIDs using a chain of bloom filters that grows automatically when the current filter becomes saturated.
Why it exists ¶
When the reprovide system walks pinned DAGs, many pins share the same sub-DAGs (e.g. append-only datasets where each version differs by a small delta). Without deduplication, the walker re-traverses every shared subtree for each pin -- O(pins * total_blocks) I/O. The bloom filter lets the walker skip already-visited subtrees in O(1), reducing work to O(unique_blocks).
A single fixed-size bloom filter requires knowing the number of CIDs upfront. On the very first cycle (or after significant repo growth) this count is unknown. BloomTracker solves this by starting with a small bloom and automatically appending larger ones when the insert count reaches the current filter's designed capacity.
How it works ¶
BloomTracker maintains an ordered chain of bloom filters [b0, b1, ...]. Each filter's parameters (bits per element, hash count) are derived from the target false positive rate via BloomParams.
- Has(c) checks ALL filters in the chain. If any filter reports the CID as present, it returns true. False positives are independent across filters because each uses unique random SipHash keys via bbloom.NewWithKeys (generated from crypto/rand). This also means different processes in a cluster hit different false positives, so a CID skipped by one node is still provided by others.
- Visit(c) checks all filters first (like Has). If the CID is not found, it adds it to the latest filter and increments the insert counter. When inserts exceed the current filter's capacity, a new filter at BloomGrowthFactor times the capacity is appended. Saturation is detected via a simple integer comparison on every insert (O(1)).
Scaling behavior (at default FP rate) ¶
With DefaultBloomInitialCapacity = 2M and BloomGrowthFactor = 4x. Memory includes ipfs/bbloom's power-of-two rounding of each bitset.
2M CIDs: 1 bloom (~8 MB) 10M CIDs: 2 blooms (~42 MB) 40M CIDs: 3 blooms (~176 MB) 100M CIDs: 4 blooms (~713 MB)
On subsequent cycles, the persisted count from the previous cycle sizes the initial bloom correctly (with BloomGrowthMargin headroom), so the chain typically stays at 1 bloom.
Concurrency ¶
NOT safe for concurrent use. See VisitedTracker for the single-goroutine invariant.
func NewBloomTracker ¶
func NewBloomTracker(expectedItems uint, fpRate uint) (*BloomTracker, error)
NewBloomTracker creates a bloom filter tracker sized for expectedItems at the given false positive rate (expressed as 1/N via fpRate).
The bloom parameters (bits per element, hash count) are derived from fpRate via BloomParams. Because the hash count must be a positive integer, the actual FP rate may be slightly better than the target. ipfs/bbloom also rounds the bitset to the next power of two, further improving the actual rate.
Returns an error if expectedItems is below MinBloomCapacity, or fpRate is zero.
When inserts exceed the current filter's capacity, a new filter at BloomGrowthFactor times the capacity is appended automatically.
NOT safe for concurrent use. See VisitedTracker for the single-goroutine invariant.
func (*BloomTracker) Count ¶
func (bt *BloomTracker) Count() uint64
Count returns the total number of unique CIDs added across all blooms. Used to persist the cycle count for sizing the next cycle's bloom.
func (*BloomTracker) Deduplicated ¶
func (bt *BloomTracker) Deduplicated() uint64
Deduplicated returns the number of Visit calls that returned false (CID already seen or bloom false positive). Useful for logging how much dedup occurred in a reprovide cycle.
type EntityType ¶
type EntityType int
EntityType represents the semantic type of a DAG entity.
const ( EntityUnknown EntityType = iota EntityFile // UnixFS file root (not its chunks) EntityDirectory // UnixFS flat directory EntityHAMTShard // UnixFS HAMT sharded directory bucket EntitySymlink // UnixFS symbolic link )
type LinksFetcher ¶
LinksFetcher returns child link CIDs for a given CID. Used by WalkDAG which doesn't need entity type information.
func LinksFetcherFromBlockstore ¶
func LinksFetcherFromBlockstore(bs blockstore.Blockstore) LinksFetcher
LinksFetcherFromBlockstore creates a LinksFetcher backed by a local blockstore. Blocks are decoded using the codecs registered in the global multicodec registry (via ipld-prime's cidlink.DefaultLinkSystem). Identity CIDs are handled transparently via blockstore.NewIdStore.
For custom link extraction, pass your own LinksFetcher to WalkDAG directly.
type MapTracker ¶
type MapTracker struct {
// contains filtered or unexported fields
}
MapTracker tracks visited CIDs using an in-memory map. Zero false positives. Useful for tests and small datasets.
NOT safe for concurrent use.
func NewMapTracker ¶
func NewMapTracker() *MapTracker
NewMapTracker creates a new map-based visited tracker.
func (*MapTracker) Deduplicated ¶
func (m *MapTracker) Deduplicated() uint64
Deduplicated returns the number of Visit calls that returned false (CID already seen). Useful for logging how much dedup occurred.
type NodeFetcher ¶
type NodeFetcher func(ctx context.Context, c cid.Cid) (linkCIDs []cid.Cid, entityType EntityType, err error)
NodeFetcher returns child link CIDs and entity type for a given CID. Used by WalkEntityRoots which needs UnixFS type detection to decide whether to descend into children (directories, HAMT shards) or stop (files, symlinks).
func NodeFetcherFromBlockstore ¶
func NodeFetcherFromBlockstore(bs blockstore.Blockstore) NodeFetcher
NodeFetcherFromBlockstore creates a NodeFetcher backed by a local blockstore. Like LinksFetcherFromBlockstore, it decodes blocks via ipld-prime's global multicodec registry (dag-pb, dag-cbor, raw, etc.) and handles identity CIDs transparently via blockstore.NewIdStore.
Entity type detection:
- dag-pb with valid UnixFS Data: file, directory, HAMT shard, or symlink
- dag-pb without valid UnixFS Data: EntityUnknown
- raw codec: EntityFile (small file stored as a single raw block)
- all other codecs (dag-cbor, dag-json, etc.): EntityUnknown
type Option ¶
type Option func(*walkConfig)
Option configures WalkDAG and WalkEntityRoots.
func WithLocality ¶
WithLocality sets a check function that determines whether a CID is locally available. When set, the walker only emits and descends into CIDs for which check returns true. Used by MFS providers to skip blocks not in the local blockstore (pass blockstore.Has directly).
The locality check runs after the VisitedTracker check (which is a cheap in-memory operation), so already-visited CIDs never pay the locality I/O cost.
func WithVisitedTracker ¶
func WithVisitedTracker(t VisitedTracker) Option
WithVisitedTracker sets the tracker used for cross-walk deduplication. When set, CIDs already visited (by this walk or a previous walk sharing the same tracker) are skipped along with their entire subtree.
type VisitedTracker ¶
type VisitedTracker interface {
// 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.
Has(c cid.Cid) bool
}
VisitedTracker tracks which CIDs have been seen during DAG traversal. Implementations use c.Hash() (multihash bytes) as the key, so CIDv0 and CIDv1 of the same content are treated as the same entry.
Implementations may be exact (MapTracker) or probabilistic (BloomTracker). Probabilistic implementations must keep the false positive rate negligible for the expected dataset size, or allow callers to adjust it (see NewBloomTracker).
NOT safe for concurrent use. The provide pipeline runs on a single goroutine per reprovide cycle. Adding parallelism requires switching to thread-safe variants (bbloom AddTS/HasTS) or external synchronization.
Source Files