Content-based sampling (deduplication)
Content-based sampling selects blocks by a predicate on their content fingerprints so identical blocks share the same sampling decision.
Estimation: Scan every block fingerprint, retain selected distinct identities and scale their total bytes by the inverse selection probability. A small retained sample does not remove the initial full scan. Xie et al. use a modulo filter and adapt its selectivity as the sample grows. [1]
Units: For a fixed divisor M, unique payload is estimated as M times the selected distinct bytes. Variable-size blocks require byte weighting. The paper calls unique bytes divided by original bytes a deduplication ratio; a reduction factor uses the reciprocal, and saved fraction subtracts that share from one. [1]
Uncertainty: Accuracy relies on fingerprint uniformity, negligible collisions and enough selected distinct content. Taking a reciprocal of an unbiased unique-byte estimate does not make the reduction-factor estimate unbiased. A zero sample cannot establish that no unique data exists. [1] [2]
Worked example: For six equal blocks A,A,A,A,B,C, averaging the within-sample saved fraction over every two-position sample gives 20%, while the full population saves 50%. This demonstrates a naive extrapolation error, not a measured backup workload. [2]
Position sampling has another limit: different full populations can yield identical probability laws for a small sampled frequency histogram, despite different unique-byte totals. This concerns inference from sampled positions, not the full fingerprint scan used above. Hesela provides an exact two-position example and a three-position control. [3]
Relations
- related
- Deduplication ratio, Sparse indexing (deduplication), Sampling design, Duplication-frequency histogram
Citations
- Xie, Condict and Shete. Estimating Duplication by Content-based Sampling. USENIX ATC 2013, pp. 181-186.
- Hesela: exact occurrence-sampling and fixed-probability content-sampling examples, method and tests.
- Hesela: identical sample histogram laws, different deduplication savings; exact derivation and executable controls.