Fixed-Block Chunking vs. Variable-Block (Rabin Fingerprinting)
File deduplication systems break files into smaller blocks. In Fixed-Block Chunking, the file is sliced every N bytes (e.g., exactly 4MB). While fast and simple, if an edit inserts a single byte at the beginning of the file, every subsequent block boundary shifts, destroying deduplication across the entire file (the boundary shift problem).
Content-Addressable Storage (CAS)
In CAS, the storage address of a block is literally the cryptographic hash of its contents: Address = SHA256(BlockBytes). If two users upload identical files (or identical chunks of different files), the system computes the exact same hash and stores the chunk only once on disk, achieving massive deduplication savings.
Worked example: inserting one byte
- A 100 MB file with 4 MB fixed blocks has 25 blocks. Insert one byte at offset 0: every block now starts one byte later, all 25 hashes change, and the client re-uploads 100 MB.
- With content-defined chunking, the client slides a 48-byte window over the data computing a rolling hash, and declares a boundary wherever the low 20 bits of the hash are zero. That happens on average every 2^20 bytes, so chunks average about 1 MiB (with a minimum of 256 KiB and maximum of 4 MiB to bound the extremes). After the insertion, only the first chunk changes; the next boundary is found at the same content as before, and the remaining roughly 99 chunks keep their hashes. The client uploads about 1 MB.
Content addressing
The chunk's address is SHA-256 of its bytes, for example blocks/ab/cd/abcd.... Writing is idempotent (the same bytes always produce the same address), so retries are safe and two users uploading the same chunk store it once. Reads can verify integrity by re-hashing.
Fixed versus content-defined
| Aspect | Fixed-size blocks | Content-defined chunks |
|---|---|---|
| CPU cost | Hash only | Rolling hash over every byte plus hash |
| Insertions and deletions | Shift all later boundaries | Change only nearby chunks |
| In-place edits and appends | Excellent | Excellent |
| Chunk size | Exactly N | Variable around a target average |
| Random access by offset | Simple arithmetic | Needs an offset index |
| Used by | Dropbox (4 MB blocks), many block stores | LBFS, restic, Borg, many backup systems |
Related techniques
- rsync uses a weak rolling checksum to find matching fixed-size blocks at any offset, plus a strong hash to confirm matches, so it also handles insertions without content-defined boundaries.
- FastCDC and Gear-based hashing make content-defined chunking several times faster than classic Rabin fingerprinting.
- Security: in 2011 researchers showed that Dropbox's client-side dedup let anyone who knew a file's hashes obtain the file, which is why hash-only uploads must still prove possession of the bytes.