hesela.devDuplication-frequency histogram
A duplication-frequency histogram counts how many distinct chunk identities occur at each repetition count in a specified population.
Bin x_i counts distinct identities occurring exactly i times, not all occurrences in that bin. The total distinct count is sum(x_i); the total occurrence count is sum(i * x_i). Six positions A,A,B,B,C,C have x_2 = 3, three identities and six occurrences. Equal-sized chunks let the count ratio represent payload-byte reduction directly; unequal lengths require byte weights, even when count and byte ratios happen to agree. [1]
A histogram built from sampled positions describes that sample, not unseen identities in the full population. With variable chunk sizes or compression, count weights alone do not determine the physical footprint. Sampling design, matching scope and storage overhead must be stated separately. [1]
Constructed example: four copies of a 1 KiB chunk and one 4 KiB chunk give a 5/2 count ratio but an 8/5 payload-byte ratio. Swapping the two lengths leaves the count histogram unchanged but gives 17/5 in bytes. For each frequency i, retain the unique payload-byte sum B_i; logical payload is sum(i * B_i), while retained unique payload is sum(B_i). This excludes compression, metadata, replicas and allocation padding. Variable-length segmentation and its metadata trade-off are described separately in DDFS. [2]
Relations
Citations
- Harnik, Khaitzin and Sotnikov. Estimating Unseen Deduplication. FAST 2016, sections 2.1 and 3.3.
- Zhu, Li and Patterson. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System. FAST 2008, sections 2.1, 2.2 and 3.1.
Sources & caveats
- The six-position example is a constructed counting illustration, not measured storage data or a reproduction of the paper's estimator.
- The byte-weighted counterexample is exact constructed payload accounting, checked against byte-equality controls; it is not a measurement or replication of DDFS.