ipfs / ipfs/go-ipld-format

Better read-ahead when walking.

Open
#53 0 comments 0 reactions 0 assignees View on GitHub
kind/enhancement
Dominant language
Go
Stars
65
Forks
27
PR merge metrics
No merged PRs in 30d

Description

When walking an IPLD dag, the DagWalker prefetches the next 5-15 siblings of each node it fetches. Unfortunately, this means we don't always look ahead as much as we can.

For example, consider the following tree:

```
o
/|\
o o o
/| | |\
o o o o o
```

The current walker will fetch as follows:

1. Fetch the first layer:

```
?
/|\
o o o
/| | |\
o o o o o
```

2. When we get the root, fetch it's first 10 children in parallel:

```
x
/|\
? ? ?
/| | |\
o o o o o
```

3. When we get the first block, fetch it's first 10 children in parallel.

```
x
/|\
x ? ?
/| | |\
? ? o o o
```

However, given _this_ graph, we're now pre-fetching _at most_ 4 blocks. Worse, once we fetch the first two leaf nodes, we'll end up in the following state:

```
x
/|\
x x ?
/| | |\
x x o o o
```

At this point, we haven't started pre-fetching the next node. That means we'll have to pause before we can continue.

---

What _should_ we be doing? At a minimum, we should be prefetching at least 10 nodes at each layer. Ideally, we'd prefetch 10 nodes at each layer at a time until we've prefetched N nodes total (DFS order), where N is configurable.

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.