TraceMachina / TraceMachina/nativelink
Add a delta store (similar to `DedupStore`)
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 1.6k
- Forks
- 244
- Avg merge
- 1d 16h
- Merged PRs (30d)
- 54
Description
Inspiration is taken from how git packs achieve high compression rates with good random access performance. The 2 key components are (1) a clustering strategy to store similar objects together and (2) a delta algorithm to encode objects predicted by an existing object. The initial proposed algorithms for analysis are:
There are crates that implement these algorithms:
For background reading on how git achieves high density in a content-addressed store, see this blog post:
Git’s database internals I: packed object store
The combination of a DeltaStore and DedupStore is similar to the architecture of bup.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by examining the existing DedupStore and the proposed DeltaStore/DedupStore relationship. Read the linked Git packed-object-store background, then compare the tlsh2 and qbsdiff crates and the TLSH and BSDIFF approaches; the issue does not define a concrete algorithm, integration point, or acceptance criteria yet.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100