Content-Defined Chunking

Introduced polynomial fingerprinting over GF(2) as a rolling hash with provable collision bounds. The foundational technique behind all BSW-family CDC algorithms.

First major system to use CDC in practice. LBFS used a 48-byte sliding window with Rabin fingerprints to achieve dramatic bandwidth savings for file synchronization.

Introduced the cyclic polynomial (Buzhash) rolling hash. Replaces Rabin's polynomial division with barrel shifts and XORs, significantly improving throughput while maintaining comparable distribution properties.

Introduced the Gear hash, a feedforward rolling hash that eliminates the sliding window entirely. Demonstrated 2x throughput over Rabin by reducing per-byte operations from 7 (Rabin) to 3 (one shift, one add, one table lookup).

Combined Gear hashing with normalized chunking (dual-mask strategy) and cut-point skipping. Reported 10x throughput over Rabin-based CDC and 3x over standalone Gear and AE, while matching or exceeding deduplication ratios.

Extended FastCDC with a "rolling two bytes per iteration" optimization, adding 30-40% throughput over the 2016 version. Adopted as the default chunker in open-source projects including Rdedup.

Introduced PCI (Popcount Independence), which uses the Hamming weight of a sliding window for boundary detection. Targets incremental synchronization: improved Rsync calculation speed by up to 70% and reduced detected incremental data by 32-57%.

First hashless CDC algorithm. Finds boundaries by locating the maximum byte value in an asymmetric local range. Reported 3x throughput over Rabin-based CDC while achieving comparable deduplication ratios.

Introduced RAM (Rapid Asymmetric Maximum) with a skip optimization that jumps directly to the actual maximum when the current byte is not the maximum, giving sublinear average-case behavior.

Decouples the context window from chunk size parameters, so boundary candidates remain stable when parameters change. Reduced incremental data by 13-34% compared to other algorithms, targeting backup and data synchronization workloads.

Demonstrated that local-extrema algorithms are inherently SIMD-parallelizable. VRAM (vectorized RAM) achieved 6.5-30 GB/s with AVX-512, a 17x speedup over scalar RAM. Tested across 10 workloads from VM backups to web archives.

Two-pass algorithm that builds a digram frequency table and uses the most common byte pairs as chunk boundaries. Reported 10x faster chunking than Rabin-based BSW and 3x faster than TTTD.

Comprehensive survey organizing CDC algorithms into three families (BSW, Local Extrema, Statistical). Provides the taxonomic framework used in the CDC post series and includes systematic benchmarks across algorithms and datasets.

Introduced the container abstraction for CDC chunk storage and the Summary Vector index for deduplication lookup without per-chunk disk I/O. The foundation for most modern deduplication storage architectures.

Broad survey of deduplication techniques covering chunking, indexing, storage, and optimization. Provides context for how CDC fits into full deduplication system architectures.

Introduced sparse indexing for deduplication at scale by sampling a subset of chunk fingerprints rather than maintaining a complete index. Exploits locality to achieve high deduplication with much lower memory overhead.

Large-scale empirical study of deduplication across 857 desktop systems. Showed that cross-user deduplication yields modest gains relative to single-user, and that most deduplication comes from file-level rather than sub-file matches.

Studied the impact of chunk size configuration on deduplication effectiveness across different backup workloads. Argues that no single chunk size is optimal for all data types.

First systematic study of fragmentation in deduplication systems. Introduced the concept of forward assembly areas and capping to limit the read amplification caused by scattered chunk references across containers.

Analyzed restore performance degradation as backup generations accumulate. Proposed container capping and read-ahead strategies to improve restore throughput for deduplicated backups.

Used historical backup metadata to predict future access patterns, improving both restore speed and garbage collection efficiency in deduplication systems.

Systematic study of design tradeoffs in deduplication systems: container size, index structure, and rewriting strategies. Showed how each parameter affects deduplication ratio, backup throughput, and restore speed.

Detailed analysis of garbage collection in the Data Domain system. Describes the challenges of reclaiming space when chunks are shared across containers and backup generations.

Directly addresses the fundamental tension between deduplication ratio and data locality. Proposes techniques for improving restore performance without sacrificing deduplication effectiveness.

Combines garbage collection with defragmentation by rewriting live chunks into locality-optimized containers during GC passes. Improves restore speed as a side effect of reclaiming space.

Describes the engineering of moving deduplicated data to cloud object storage while preserving deduplication benefits. Addresses the specific challenges of per-operation cloud pricing for small-object workloads.

Showed that web request frequencies follow a Zipf distribution. Measured α values between 0.64 and 0.83 for web traffic, establishing the empirical basis for cache sizing models.

Found α values between 0.85 and 1.0 on real CDN and web application traces, indicating modern access patterns are even more skewed than Breslau et al. measured. Provides practical bounds for cache sizing.

Empirical study of source code file size distributions across open-source projects. Provides data used for modeling CDC workloads on source code repositories.

Analyzed commit size distributions in open-source projects. Provides empirical grounding for modeling change rates and deduplication effectiveness in version-controlled codebases.

Uses abstract syntax trees to chunk source code at structural boundaries rather than content-defined boundaries. Explores the frontier of structure-aware chunking for code retrieval and RAG applications.

Proposes a graph-based model for compression that can represent and optimize across different compression strategies including deduplication.

Describes Dropbox's use of CDC for streaming file synchronization, reducing bandwidth by transmitting only changed chunks.

Describes Dropbox's evolution of their CDC-based sync protocol, reducing sync overhead by intelligently skipping unchanged regions.

Applies CDC to mobile cloud storage synchronization, addressing the specific constraints of mobile bandwidth and battery life.

Documents Seafile's CDC implementation for file synchronization and deduplication in their open-source cloud storage platform.

Describes Riot Games' move from binary deltas to FastCDC-based content-defined chunking for League of Legends game updates.

Describes IPFS's use of Rabin fingerprinting for content-defined chunking alongside fixed-size splitting in content-addressed distributed storage.

Describes Restic's use of Rabin fingerprint-based CDC for deduplication in its backup tool.

Describes Borg's Buzhash-based chunker with a keyed seed for chunk boundary detection.

Describes Kopia's rolling-hash file splitting for content-addressable deduplication in its backup system.

Describes Duplicacy's variable-size CDC with configurable minimum, average, and maximum chunk sizes.

Describes Bupstash's GearHash-based content-defined chunking for encrypted, deduplicated backups.

Describes Tarsnap's context-dependent variable-size chunking for client-side deduplication.

Uses CDC to split filesystem images into variable-size chunks for efficient OS and container image distribution.