ipfs / ipfs/kubo

Fast (parallel) Traversal For A DAG That Stops At Arbitrary Points

Open
#5,487 7 comments 0 reactions 0 assignees View on GitHub
kind/enhancement status/in-progress
Dominant language
Go
Stars
17.1k
Forks
3.2k
Avg merge
3d 18h
Merged PRs (30d)
11

Description

#### Summary
Given a root CID, I would like to traverse that node's DAG quickly (making requests for children in parallel), and stop traversal of links on a per node basis using logic I provide.

#### Use Case
The time to list large sharded directories is prohibitive because link traversal in the DAG is serialized. We need to speed this up. (#4908 )

### Requirements / Acceptance Criteria

Requirements:
- Minimize memory footprint
- Maximize requests made in parallel, enumerate the DAG as quickly as possible
- Leave what to do with each node up to caller (VisitNode)

### First Steps

- Use EnumeratChildrenAsync from go-merkeldag in HAMT link enumberation (ForEachLink) and test performance

### Additional Optimizations

- Get nodes in parallel (GetMany)
- Additional operations to increase speed

### Not Included

- Enumeration in any consistent order

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.