Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
schomatis opened this issue Sep 3, 2021 · 0 comments
Open

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

schomatis opened this issue Sep 3, 2021 · 0 comments
Assignees
Labels
need/triage Needs initial labeling and prioritization

Comments

@schomatis
Copy link
Contributor

Spawned from ipfs/go-unixfs#106. As explained there, WalkDepth 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 ipfs/go-unixfs#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

@schomatis schomatis added the need/triage Needs initial labeling and prioritization label Sep 3, 2021
@schomatis schomatis self-assigned this Sep 3, 2021
@Jorropo Jorropo changed the title [unsharding] concurrent dag.Walk does a BFS ipld/unixfs: concurrent dag.Walk does a BFS when unsharding Jun 26, 2023
@Jorropo Jorropo transferred this issue from ipfs/go-unixfs Jun 26, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
need/triage Needs initial labeling and prioritization
Projects
No open projects
Archived in project
Development

No branches or pull requests

1 participant