ChainSafe / ChainSafe/forest

On-demand multi-car indexing

Open
#3,565 1 comment 0 reactions 0 assignees View on GitHub
Performance Priority: 4 - Low Ready Type: Feature
Dominant language
Rust
Stars
697
Forks
200
Avg merge
1d 5h
Merged PRs (30d)
65

Description

**Issue summary**

ForestCAR files offer `O(1)` look-up of IPLD values. Unfortunately, with more than one ForestCAR file, the look-up time grows linearly and quickly becomes prohibitive. One option is to merge the ForestCAR files, but this is expensive. A cheaper option would be to build a new, ephemeral, on-disk index that covers multiple ForestCAR files.

Buckets in a ForestCAR file are stored sorted from low to high. This makes it possible to merge two ForestCAR indexes efficiently and linearly. It's possible to open a ForestCAR file and get a stream of CIDs with the guarantee that the bucket number is growing monotonically.

Tasks:
- [ ] Get a stream of CIDs from ForestCAR.
- [ ] Get the number of CIDs from ForestCAR.
- [ ] Merge multiple CID streams and linearly write out hash-table buckets to disk.
- [ ] Create a new data store that uses a single index to query multiple ForestCAR files.
- [ ] Define property tests to show that the new data store is semantically the same as a `ManyCar`.
- [ ] Add benchmark command to `forest-tool` for generating stand-alone indexes.
- [ ] Measure performance differences when graph-walking all of the diff calibnet snapshots.

**Other information and links**

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.