Content-Defined Chunking

CDC uses a rolling hash algorithm to scan a sliding window across the data stream. A chunk boundary is declared when the hash value of the current window satisfies a predefined condition, such as matching a specific bit pattern. This ensures boundaries are determined by local content rather than absolute position. If data is inserted or deleted, only the chunks directly overlapping the change are affected; all subsequent chunks remain identical to their original versions, enabling maximal deduplication.

Unlike fixed-size block chunking, which is vulnerable to the byte-shifting problem, CDC produces chunks of varying lengths. In fixed-size chunking, a single byte insertion at the beginning of a file shifts all subsequent block boundaries, rendering every block different. CDC's content-defined boundaries prevent this cascading failure. The trade-off is a slightly higher computational cost for hash calculation, but this is offset by dramatically improved storage efficiency in backup and synchronization systems.

CDC implementations rely on efficient rolling hashes that can be updated in O(1) time as the window slides one byte forward. Key algorithms include:

• Rabin-Karp: A classic polynomial hash using a fixed modulus and base, easily updatable by subtracting the outgoing byte's contribution and adding the incoming byte's.
• Gear Hash: A fast, table-driven rolling hash designed specifically for CDC, offering better performance and more uniform distribution than Rabin-Karp.
• Buzhash: An XOR-based rolling hash that uses a precomputed table of random values for each byte, providing extremely fast computation.

Purely content-defined boundaries can produce pathological cases, such as chunks that are extremely small or excessively large. To prevent this, CDC algorithms enforce minimum and maximum chunk size constraints. If a boundary condition is met before the minimum size is reached, it is ignored. If no boundary is found by the maximum size, a cut is forced. This ensures chunks remain within a manageable range for indexing and storage, balancing deduplication granularity with metadata overhead.

CDC is the foundational technology behind many modern deduplication systems. Key applications include:

• Incremental Backup: Only new or changed chunks are uploaded, drastically reducing bandwidth and storage.
• File Synchronization: Tools like rsync use a related rolling hash approach to detect differences and transmit only delta chunks.
• WAN Optimization: Network appliances use CDC to cache chunks at both ends of a connection, avoiding redundant data transfer.
• Distributed Storage: Systems like Dell PowerProtect and Veeam use CDC to deduplicate data globally across backup repositories.

The term Rabin fingerprinting is often used interchangeably with CDC, though it specifically refers to the mathematical hash function developed by Michael Rabin. A Rabin fingerprint treats a data window as a polynomial over a finite field and evaluates it modulo an irreducible polynomial. This provides strong collision resistance and is efficiently updatable. While Rabin's method is the most famous CDC technique, modern systems may use faster alternatives like Gear hashing that sacrifice some mathematical elegance for raw throughput.