Deduplication and compression: the benefit and the bill

A retention scheme decides how many recovery points exist; deduplication and compression decide what those recovery points cost to keep, which is why a retention argument and a storage-savings claim so often arrive in the same meeting. Both mechanisms are real and both are measurable. Neither is free: they move work off the storage invoice and onto the CPU, the memory and the restore path, and the point here is to be able to say exactly where.

Chunk boundaries are what deduplication actually depends on

Deduplication is the refusal to store the same bytes twice. Before a system can refuse, it needs a unit — some span of bytes it can name, hash and compare. The choice of unit decides everything else.

The naive unit is a fixed-size block: cut every four megabytes and hash each piece. This works where offsets are stable, which is why block-level deduplication of virtual disks and volumes is a reasonable design. It falls apart on files. Insert one byte at the front and every later boundary shifts by one; every block after the insertion hashes differently, and a system meant to store a one-byte change stores the whole file again.

Content-defined chunking removes the dependence on offsets. A rolling hash is computed over a small sliding window as the input streams past, and a chunk boundary is declared wherever that hash satisfies a fixed predicate — say, when its low bits are all zero. Because the predicate is evaluated on the content inside the window rather than on the position, the boundaries move with the data. Insert a byte and only the chunk containing it changes; the chunks before and after it are cut in the same places as before and are recognised as already stored. Minimum and maximum chunk sizes bound the result so that pathological inputs cannot produce one-byte or gigabyte chunks. Each chunk is then hashed cryptographically, and that hash is both its identity and its key in the index.

Two consequences follow, and both matter operationally. First, deduplication is not per-file and not per-snapshot: any two spans of bytes that chunk identically are stored once, whether they are in the same file, in different files, in snapshots months apart, or on different hosts writing into one repository. Second, because the identity is computed on the plaintext before the chunk is encrypted, deduplication works inside an encrypted repository and never crosses between repositories holding different keys. A per-tenant key is a deliberate decision to forfeit cross-tenant deduplication, and that is a capacity decision as much as a security one.

Measured: a second backup of 60.000 MiB stored 1.370 KiB

The mechanism is worth watching on real output. A restic repository was initialised, a 60 MiB tree of three files was backed up, one file was changed, and the same tree was backed up again.

$ restic backup /work/prod --tag daily

using parent snapshot 3fe43af4

Files:           0 new,     1 changed,     2 unmodified
Dirs:            0 new,     3 changed,     1 unmodified
Added to the repository: 2.062 KiB (1.370 KiB stored)

processed 3 files, 60.000 MiB in 0:00
snapshot 3e349a12 saved

>>> exit code: 0

Read the two size lines against each other. The snapshot covers 60.000 MiB and is a complete view of the tree — the snapshot listing in the same capture reports both snapshots at 60.000 MiB, not as deltas. What the repository had to absorb to gain that view was 2.062 KiB, of which 1.370 KiB is what it reports as stored. The distance between either figure and 60.000 MiB is deduplication: the chunks of the two unmodified files were already there, so they were referenced rather than written again.

Resist reading the second number as “the first one, compressed”. The first backup in the same capture reported Added to the repository: 60.005 MiB (60.008 MiB stored) — stored larger than added, on the same tree with the same settings, because the stored figure counts what the repository actually wrote, packing and per-blob overhead included. It lands on either side of the added figure depending on what the data gives compression to remove. On the filesystem both runs came to the same place: source tree 61M, repository 61M, after two backups of 60 MiB each.

Borg reports the same physics with the accounting made explicit.

$ borg create --stats /work/repo::day2 .

Number of files: 2
Utilization of max. archive size: 0%
------------------------------------------------------------------------------
                     Original size      Compressed size    Deduplicated size
This archive:               41.94 MB             41.94 MB                613 B
All archives:               83.89 MB             83.89 MB             41.95 MB

                     Unique chunks         Total chunks
Chunk index:                      23                   40
------------------------------------------------------------------------------

>>> exit code: 0

Three numbers describe the same archive. Its original size is 41.94 MB. Its compressed size is also 41.94 MB — on this data the compression stage handed back the number it was given, a result we will come back to. Its deduplicated size is 613 B, and that is the only one of the three that corresponds to bytes newly occupied. Across both archives, 83.89 MB of logical content is held in 41.95 MB of deduplicated storage. The chunk index line is the mechanism showing through the reporting surface: 23 unique chunks underneath 40 total chunk references.

Compression spends CPU on redundancy that may not be there

Compression and deduplication are different reductions on different axes. Deduplication removes repetition between chunks and needs an index to find it; compression removes repetition within a chunk and needs only the chunk in front of it. A backup system normally does both, and the order is not arbitrary: chunk the plaintext, deduplicate, then compress only what is left. Reversing it would break the first stage, because a compressor’s output for a span depends on everything it saw before that span — the same file compressed inside two different streams does not produce the same bytes, and a chunker reading those bytes would find no duplicates at all. So compression is applied last, per chunk, to the residue of a run that deduplication did not eliminate.

What compression costs is CPU, twice: on the backup path, where a stronger setting buys fewer stored and transferred bytes at the price of throughput, and on the restore path, where every byte read back must be decompressed before it can be written. What it buys is capacity, and time on a link where bytes are the constraint; which of those dominates is an architecture question rather than a default.

The caveat is the one the borg capture already showed. Compression works on redundancy, and data that has already been compressed or encrypted has had its redundancy removed on purpose — media files, container image layers, .gz and .zst archives, and anything random to begin with. When that is the mix, the compressed column equals the original column, exactly as the borg capture shows: 41.94 MB against 41.94 MB. Compression that finds nothing still costs the CPU of looking; only the saving goes missing.

A related reduction is regularly mistaken for compression and is not compression at all: whether the format represents absent data as absent. A sparse file has an apparent size much larger than the blocks allocated to it, and an archiver either understands that or expands the holes into real zero bytes.

$ tar -cf naive.tar src

archive size: 201M
[restored from default tar]
sparse.img apparent    : 200M
sparse.img allocated   : 200M

$ tar --acls --xattrs --xattrs-include='*' --sparse -cf full.tar src

archive size: 100K
[restored from tar --acls --xattrs --sparse]
sparse.img apparent    : 200M
sparse.img allocated   : 0

201M against 100K, from the same source tree, because the default archive read the hole as 200 MiB of zero bytes and wrote every one of them out. Piping that 201M archive through a compressor would have hidden the size and none of the work: the zeros were still read and written, and the restore still landed sparse.img with allocated 200M where the source had 0. That reduction came from a flag that changed what was represented, not from an algorithm.

Source-side and target-side save different resources

Where the chunking happens changes which resource is conserved.

Source-side deduplication chunks and hashes on the client, consults a local cache and the repository index, and sends only the chunks the repository does not already hold. It saves network transfer, backup window and capacity at once, at the cost of CPU and memory on the production host — and it depends on state that can be lost. Look again at the restic output, which printed using parent snapshot 3fe43af4 and then counted two of the three files as unmodified. That classification is made from file metadata compared against the parent snapshot: a separate mechanism from deduplication, and the one that decided how much data was read at all. When that change-detection cache is empty — a rebuilt client, a restored host, inode timestamps that all moved — every file is read and re-hashed even though almost nothing is stored. The backup runs for hours and still reports a few hundred kilobytes added, and an operator watching only the added figure cannot see why the window blew out.

Target-side deduplication puts the work on the appliance or backup server. The client sends the whole stream; the target chunks, hashes and stores it. It saves capacity on the target and nothing else — the network carries everything and the window is the full transfer. In return, production hosts spend no CPU on it, and the target can deduplicate across clients that share no client-side state.

Scope is the part most often assumed rather than checked: deduplication finds duplicates only inside the pool it indexes. Fifty virtual machines built from one template overlap enormously, but only if they land in one indexed pool. Split across fifty per-client repositories, the shared base is stored fifty times, and no setting recovers that.

The bill: index memory, scattered reads and shared fate

The savings are real, and so is what comes with them.

Index memory grows with the repository. It is the one capacity line that does not shrink when the retention window does, because it tracks unique chunks and a shorter window removes references before it removes chunks. When the index stops fitting in memory, every lookup becomes a disk access and backup throughput falls off a cliff — on a system still reporting job success.

Restore locality is destroyed by design. A file written contiguously at the source is stored as chunks scattered across packs written on many different days. Reconstructing it is many small reads at unrelated offsets, and the snapshot that cost 1.370 KiB to store still requires all 60.000 MiB to be located and written back. Where each request carries latency — spinning disks, or object storage over a network — a deduplicating repository can restore more slowly than it backed up, and the backup duration gives no warning of it.

One chunk is shared fate. Independent full copies fail independently; a deduplicated repository does not. In the restic capture, ten bytes overwritten in one pack produced pack 2c3be6d1... contains 2 errors, and the restore of snapshot 3fe43af4 — the earlier of the two, written before the second backup ran and before the damage — came back with Restored 6 / 7 files/dirs (59.401 MiB / 60.000 MiB) and exit code 1. Age bought it nothing: the blob it needed was the single stored instance both snapshots referenced. That is the argument for verification that reads the data, and for a second, independently stored copy — the undamaged copy in the same capture passed restic check --read-data with no errors were found and exit code 0.

A deduplication ratio is a measurement, never a planning input

For all of the above, this lesson will not tell you what ratio to expect. One input deserves separating out, because it is the one that flatters a proposal: retention depth. Each further snapshot of similar content raises the cumulative ratio with no new efficiency, so a headline figure quoted after a year of dailies is not the figure that governs next month’s growth. That one is marginal — stored bytes per run — and it is smaller.

The alternative is not difficult. Run the real tool over a representative sample of the real data, for at least one full retention cycle, and read the ratio out of the repository’s own accounting rather than out of a proposal.

REPO=/srv/backup/repo
SAMPLE=/srv/data/fileserver-sample
borg create --stats "$REPO::measure-$(date +%F)" "$SAMPLE"

The three columns in that output — original, compressed and deduplicated — are the measurement, and repeating it after a week of daily runs gives the marginal figure as well as the first-run one. Size the storage on measured stored bytes plus a growth rate, record the date and the sample it came from, and re-measure when the data mix changes. A ratio with a date and a sample attached is evidence. A ratio without them is an assumption wearing a number.

What to take from this

• The second backup of a 60.000 MiB tree reported Added to the repository: 2.062 KiB (1.370 KiB stored) on restic 0.19.1, and the snapshot is still a complete 60.000 MiB view. The stored figure is not the added figure compressed: the first backup of the same tree reported 60.005 MiB (60.008 MiB stored).
• Borg 1.4.0 reported the second archive as 41.94 MB original, 41.94 MB compressed and 613 B deduplicated: the compressed column equalled the original column, so every byte of the saving came from chunks already stored.
• The same capture’s chunk index line reported 23 unique chunks against 40 total: reference counting made visible, 40 references resolved to 23 stored chunks.
• A default tar -cf of a tree holding a 200 MiB sparse file produced a 201M archive and restored the file with allocated 200M; tar --sparse produced 100K and allocated 0. That reduction came from representation, not from an algorithm.
• Ten bytes overwritten in one pack produced contains 2 errors and a restore of 6 / 7 files/dirs (59.401 MiB / 60.000 MiB), exit code 1 — shared chunks mean shared damage.
• After three archives were deleted from an append-only borg repository, the capture still reported 41M of repository data on disk, because removing references is not reclaiming space.

Cross-course references

• Ceph & Distributed Storage for Production Sysadmins — Part XXVI (Erasure Coding Trade-offs) analyses the same shape of bargain in a storage cluster: capacity bought with CPU and with a reconstruction path that reads from more places than a replica would, which is the distributed-storage version of the scattered-restore cost described here.
• Linux for Production Sysadmins — Part III (Filesystems and Files) covers apparent size versus allocated blocks, the distinction that makes the 200M apparent, 0 allocated sparse file in this lesson meaningful and that decides whether an archiver has anything to save.
• Proxmox VE for Production Operators — Part XIII (Proxmox Backup Server) applies exactly this chunk-store model to virtual machine images, where the chunk index and its garbage collection become the operational surface that the reference counting described here explains.

Quiz