ipfs / ipfs/boxo

ipld/unixfs: concurrent dag.Walk does a BFS when unsharding

Open
#392 0 comments 0 reactions 1 assignee Claimed by @schomatis View on GitHub
need/triage
Dominant language
Go
Stars
316
Forks
163
Avg merge
4d 12h
Merged PRs (30d)
8

Description

Spawned from https://github.com/ipfs/go-unixfs/pull/106. As explained there, [`WalkDepth`](https://github.com/ipfs/go-merkledag/blob/4a8891d5ef68f0711656579672d17f8533100add/merkledag.go#L397) does a BFS when called with the concurrent option, which is what we do in the HAMT when enumerating all links (`(*Shard).EnumLinksAsync()`).

Depending on the distribution of the shards in the HAMT this _might_ mean that we will unnecessarily fetch more nodes/shards than we need to. This is currently exemplified in the test in https://github.com/ipfs/go-unixfs/pull/106:
* we traverse a complete HAMT to fetch enough directory entries to reach the threshold
* the _artificial_ HAMT used in the test is complete in the sense that every node has the maximum number of children allowed per `DefaultShardWidth` and all leaf nodes have the same depth
* to reach the directory entries ('value' links) we need to reach the leaf nodes in the base of the tree
* in a BFS to do that we need to fetch *every* node above that last layer

cc @aschmahmann @Stebalien

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.