Before You Hash, Define "Duplicate"

Every deduplication system starts with one decision: what counts as a duplicate? The spectrum runs from byte-identical copies through near-duplicates to sub-file redundancy, each needing a different mechanism family.

Exact dedup via SHA-256 is cheap and precise: hash each document, store it in a lookup set, discard matches. One billion fingerprints costs ~32 GB of memory. But it misses anything reformatted, re-encoded, or edited by a single character.

Raw documents from different sources may encode identical content with different whitespace, Unicode forms (NFC vs NFD), or HTML entities. Standard normalizations like lowercasing and collapsing whitespace catch more variants but risk merging materially distinct documents.

Fixed-size chunking splits a file into blocks at every N bytes. Insert one byte at the beginning and every downstream boundary shifts, so the system detects zero duplicates. This is the boundary-shift problem.

Content-Defined Chunking (CDC) solves this by setting boundaries based on content, not position. A rolling hash (originally a Rabin fingerprint) slides over the byte stream byte-by-byte. A cut-point is declared when the hash satisfies:

Because the cut condition depends on window content, not file position, inserting or deleting bytes only shifts the nearest boundary. Everything downstream stays aligned. CDC detects 10-20% more redundancy than fixed-size chunking.

Average chunk size ties together four competing cost dimensions. Smaller chunks find more redundancy but produce more index entries and hashing work. Larger chunks mean less metadata overhead but lower dedup ratios.

The C4 dataset stripped ~70% of raw text from Common Crawl by removing repeated 3-sentence spans. The Pile carried ~30% duplication, and GitHub repositories can exceed 50% redundancy from forks and boilerplate.

Microsoft reports ~50% redundancy in primary storage, EMC reports ~85% in secondary, with chunk-level dedup achieving up to 83% space savings. With fast chunking like FastCDC, the cryptographic hash becomes the primary CPU cost, not the rolling hash. FastCDC runs ~10x faster than Rabin-based CDC at nearly the same dedup ratio.

CDC boundaries create a side channel. Rolling hash-based chunking is exploitable because chunk boundaries are publicly observable. Attackers can extract hidden parameters like the prime modulus, multipliers, or coefficient maps.

Concrete parameter extraction has been demonstrated against Tarsnap, Borg, and Restic. Protocol-agnostic attacks can fingerprint files or extract sensitive portions purely from chunk size distribution analysis, without breaking any encryption.

The fixes: replace simple rolling hashes with cryptographically robust PRFs like HMAC, enlarge keyspaces (Buzhash to 64-bit), and introduce randomized chunking strategies so boundaries are not deterministic from content alone. Making the definition of "duplicate" unobservable is a constraint that shapes the chunking algorithm itself.