Data Compression vs Data Deduplication

Compression shrinks one stream by finding byte patterns that repeat inside it and re-encoding them with fewer bits; deduplication shrinks a whole corpus by cutting data into blocks, storing each unique block exactly once, and replacing every later copy with a small pointer to it. Both remove redundancy — but compression attacks redundancy within the data it can see in a small window, while dedup attacks redundancy across files, machines, and backups it has ever seen. That difference in scope is the whole story, and it is why real storage systems run them together rather than choosing one.

How compression works (the mechanism)

The workhorse of general-purpose lossless compression is DEFLATE (used by gzip, zlib, ZIP, PNG). It is two stages stacked:

1. LZ77 dictionary matching. A sliding window (32 KB in DEFLATE) holds the recently-seen bytes. When the encoder finds that the upcoming bytes already appeared in the window, it emits a (distance, length) back-reference instead of the bytes themselves — "copy length bytes from distance bytes ago."
2. Huffman entropy coding. The resulting stream of literals and back-references is then re-coded so that frequent symbols get short bit codes and rare ones get long codes.

Traced example — the string ababab (6 bytes):

• pos 0 → a: nothing behind it, emit literal a.
• pos 1 → b: emit literal b.
• pos 2 → ababab…: the bytes abab already exist starting 2 positions back. Emit one back-reference (distance=2, length=4). The copy overlaps itself, which is legal and how LZ77 encodes runs.

Output = a, b, (2,4) — 6 input bytes collapse to two literals plus one pointer token. Lossy codecs (JPEG, MP3, H.264) go further by throwing information away the eye or ear will not miss; that is a separate axis from lossless and is irreversible.

How deduplication works (the mechanism)

Dedup does not look inside patterns — it works on whole blocks:

1. Chunk the incoming data into blocks.
2. Hash each chunk with a strong cryptographic hash (SHA-256 is standard) to get a content fingerprint.
3. Look up the fingerprint in a global index. If it is new, store the chunk once and record it; if it already exists, store nothing — just append a pointer to the existing block in the file's "recipe."

The single most consequential design choice is how you draw chunk boundaries:

• Fixed-length chunking — cut every 4 KB (or 128 KB). Simple and fast, but it has the boundary-shift problem: insert one byte at the front of a file and every subsequent block shifts by one byte, so no chunk hashes match the previous version — dedup ratio collapses to ~1:1 on an otherwise-identical file.
• Variable / content-defined chunking (CDC) — slide a cheap rolling hash (Rabin fingerprint) over the bytes and cut a boundary wherever the hash hits a chosen pattern (e.g. low bits all zero). Boundaries are anchored to content, so an inserted byte only disturbs the one chunk around it; every chunk after re-synchronises and still dedupes. This is why backup tools (Restic, Borg, Data Domain) use CDC, not fixed blocks.

Worked example — dedup then compress, with real numbers

A backup run captures three files, chunked (via CDC) into 4 KB blocks. File 2 is an edit of File 1 where the last chunk changed:

• File 1 → A B C
• File 2 → A B D
• File 3 → A B C (a second machine has an identical copy)

Feed the 9 chunks through the index in order:

Dedup result: 9 logical chunks (36 KB) reduced to 4 unique blocks (16 KB). Ratio = 36/16 = 2.25:1.

Now compress the 4 unique blocks. They are text, so DEFLATE gets roughly 2:1 → the physical store shrinks from 16 KB to ~8 KB. Overall 36 KB logical stored in 8 KB physical = 4.5:1. The two techniques multiply: dedup removes cross-file duplication; compression then squeezes the residual entropy inside each surviving block.

The boundary-shift trap in numbers: if File 2 had instead prepended one byte and we used fixed 4 KB blocks, chunks A' B' D' would all mis-align and hash differently — dedup on File 2 drops to ~1:1 despite the files being 99% identical. CDC keeps the ~2:1.

Combining them: order matters in the pipeline

The canonical storage/backup pipeline is chunk → dedup → compress → encrypt, and the order is not arbitrary:

• Dedup before compress. Two identical plaintext chunks hash the same and dedupe cleanly. Compress first and you (a) shift chunk boundaries and (b) turn identical inputs into differently-framed high-entropy blobs whose hashes no longer match — the dedup hit rate craters. So find duplicates on the plaintext, then compress only the unique survivors.
• Encrypt last. Good ciphertext is indistinguishable from random: it neither compresses (no patterns) nor dedupes (no repeats). Anything after encryption sees noise. Encryption is therefore the final stage — never before dedup or compression.

Pitfalls

• Fixed-block boundary shift. The classic dedup disappointment: a nearly-identical file dedupes to almost nothing because a byte was inserted upstream and fixed blocks all mis-aligned. Use content-defined chunking for anything that gets edited.
• The chunk-size dilemma. Small chunks (4 KB) find more duplicates but explode the index; 100 TB at 4 KB is ~25 billion chunks × ~32 B/entry ≈ 800 GB of index. If that index does not fit in RAM, every write does a disk seek to check for duplicates and throughput collapses (the "dedup wall"). Bigger chunks shrink the index but lower the dedup ratio.
• Hash-collision anxiety (and real risk). Dedup trusts that equal hashes mean equal data. With SHA-256 a false collision is astronomically unlikely; with a weak or truncated hash it is not, and a collision silently corrupts data by aliasing two different blocks. Paranoid systems do a byte-for-byte verify on a hash match.
• Compressing already-compressed data. Re-zipping a JPEG, MP4, or .gz burns CPU for ~0% gain and can even grow the file. Detect and skip.
• Encryption kills both. Client-side-encrypted or already-encrypted data is high-entropy noise — it will neither compress nor dedupe. This routinely surprises teams who enable end-to-end encryption and then wonder why their dedup ratio fell to 1:1.
• Fragmentation & restore cost. A deduped file's blocks are scattered across the store, so reading it back ("rehydration") turns sequential reads into random I/O. Great space savings, slower restores — a real trade-off for backup RTO.

When to use which — and how a senior engineer decides

Reach for compression when the redundancy lives inside individual objects and objects are mostly unique across the corpus: log lines, JSON/HTML payloads, database pages, columnar analytics data, network transfer. Signal: "each file is different, but each file is internally repetitive/verbose."

Reach for deduplication when the same bytes recur across many objects: backup sets (yesterday's snapshot ≈ today's), VM images and container layers, home directories full of the same corporate documents, email servers with the same 10 MB attachment in 500 mailboxes. Signal: "we are storing the same thing over and over."

Trade-off vs the named alternative:

• Compression costs CPU on every read and write and gives you nothing when different files happen to be identical — it re-compresses each copy independently. Dedup catches exactly that case but costs a large in-RAM index, hashing on the write path, and slower fragmented restores.
• Choose compression alone for a CDN edge, a single-tenant app database, or wire transfer where data is unique and you cannot afford an index. Choose dedup (then compression) for a backup appliance or multi-tenant object store where duplication across tenants/snapshots is the dominant cost.

A second decision inside dedup — inline vs post-process: inline dedup hashes and checks the index before writing, so it never lands duplicate bytes on disk (best for capacity) but adds latency to every write. Post-process dedup writes everything raw first and dedupes later on a schedule — faster writes, but you must provision "landing zone" space for the un-deduped data. Choose inline when disk is the constraint; choose post-process when write latency/throughput is the constraint and you have spare capacity.

Takeaways

• Scope is the dividing line: compression removes redundancy within a stream (LZ77 back-references + Huffman); dedup removes redundancy across a corpus (chunk → hash → store-once + pointer).
• They multiply, in this order: chunk → dedup → compress → encrypt. Dedup on plaintext, compress the survivors, encrypt last — reordering silently destroys the gains.
• Content-defined chunking is non-negotiable for editable data; fixed blocks fall to the boundary-shift problem.
• The dedup index is the real cost: chunk size trades dedup ratio against an index that must fit in RAM, and dedup wins big only where the same bytes genuinely repeat.

Re-authored and deepened for this guide. Drawn from Ziv & Lempel's LZ77 (1977) and the DEFLATE spec (RFC 1951); content-defined chunking from Muthitacharoen et al., "A Low-Bandwidth Network File System" (LBFS, SOSP 2001) and Rabin fingerprinting; production dedup design from Zhu, Li & Patterson, "Avoiding the Disk Bottleneck in the Data Domain Deduplication File System" (FAST 2008); plus Salomon's Data Compression: The Complete Reference and the ZFS, Restic, and Borg documentation.