On-demand multi-car indexing
- 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
Assessment
This issue has not been assessed yet.