hesela.devSparse indexing (deduplication)
Sparse indexing uses sampled chunk fingerprints to select stored segment manifests against which incoming chunks are deduplicated.
Selected fingerprints, called hooks, identify candidate manifests. Matching uses the selected manifests, including unsampled chunks, so some existing duplicates may be stored again. [1]
The candidate limit bounds manifests examined, not total repository containers or restore reads. Unlike a complete-index Bloom filter, absence from the candidate set does not establish global uniqueness. [2] [3]
Relations
- related
- Data deduplication, Content-defined chunking, Bloom filter, Chunk fragmentation, Container capping
Citations
- Lillibridge et al. Sparse Indexing: Large Scale, Inline Deduplication Using Sampling and Locality. USENIX FAST 2009, pp. 111-123.
- Zhu, Li and Patterson. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System. USENIX FAST 2008, pp. 269-282.
- Hesela: Deduplication ratio does not predict restore cost
Sources & caveats
- Historical algorithm described at FAST 2009; status describes this research concept, not current product availability.
- The linked four-case demonstration uses synthetic identities, not the papers' backup traces.