Why Your Backups Are Too Big: A Practical Guide to Content-Defined Chunking
By Gilles Chehade
You change one line in a large file. Your “incremental” backup re-uploads the whole thing anyway.
Nine times out of ten, it’s not the network, and it’s not your storage backend. It’s the algorithm deciding where to cut your data into pieces.
Every deduplication system works the same way: split data into pieces, hash each piece, keep one copy per distinct hash. A piece is named after its own content, so two identical pieces are, by definition, the same piece. Snapshot a filesystem today and again tomorrow, and if most of the data hasn’t changed, most pieces are already in the store. The second snapshot costs you almost nothing.
That’s not a nice-to-have. A backup that actually survives an incident needs to be encrypted, frequent, immutable, replicated and verified, and each of those requirements multiplies what you store. When deduplication is weak, those multipliers stack until backing up everything becomes unaffordable, and teams quietly retreat to backing up only what they call “critical.” Good deduplication is what makes backing up everything affordable again.
And all of it rests on one assumption: unchanged data should yield unchanged pieces.
Where fixed-size chunking falls apart
The obvious way to split a file is to cut every N bytes. It’s fast. It also wrecks deduplication the moment you touch the file.
Add one byte near the front and every boundary after it slides over by one. Nothing lines up with where it used to be, so every hash downstream is “new,” so the store treats the entire rest of the file as fresh data. Edit one line in a 40 GB file and you re-upload close to 40 GB of it. Nothing meaningful changed, only the offsets did, and fixed-size boundaries are glued to offsets.
How content-defined chunking fixes it
Content-Defined Chunking (CDC) picks boundaries based on what the data is, not where it happens to sit.
Slide a small window over the byte stream and keep a rolling hash, cheap enough to update incrementally that the whole scan stays linear, then cut a boundary wherever that hash matches an agreed pattern.
Now insert a byte. The boundaries right around the edit shift. But once the window slides past the change, the hash sequence goes back to matching what it was before, and the boundaries fall back into place on their own. One piece changes. Everything else deduplicates cleanly against the previous snapshot. That self-resynchronizing behaviour is the whole point of CDC.
Picking an algorithm
There’s more than one way to build a rolling hash and a cut rule.
Rabin fingerprinting is the textbook original, correct but slow and allocation-heavy by today’s standards. FastCDC swapped the polynomial hash for a much cheaper Gear hash and normalized the chunk-size distribution, and it became the field’s workhorse. UltraCDC trades a bit of speed for fewer, larger chunks. JC is a newer design that turns out to be strikingly fast. There are also keyed variants, where the hash table is seeded from a secret so two different stores cut the same data at different points, which matters if you care about not leaking which chunks you hold.
We benchmarked these in go-cdc-chunkers, the open-source chunking library behind our backup engine, Plakar, on 1 GiB of random data, the worst case since there’s no structure to exploit. JC hits 3747 MB/s, comfortably ahead of the Gear-based FastCDC variants. Rabin runs about 7.5x slower and allocates roughly 3.3 MB per operation versus a few KB for the others, which on a busy host is the difference between a run you notice and one you don’t. Full benchmarks and charts are published separately.
Using it is trivial:
// One interface for the whole family.
c, _ := chunkers.NewChunker("jc", reader) // or "fastcdc", "ultracdc", "kfastcdc"
for {
chunk, err := c.Next()
// ... hash and store the chunk ...
if err == io.EOF {
break
}
}
Determinism is the feature that matters most
Here’s the part that gets too little respect.
Give it enough time and “FastCDC” stops meaning one thing. Every implementation picks up small departures from the paper: a mask off by a bit, a window starting a byte early, a threshold nudged for taste. Harmless for a benchmark. For a storage system it’s a slow-motion disaster, because boundaries are part of your data’s identity. Change how you cut and yesterday’s pieces stop matching today’s, so deduplication degrades with no error and no warning. The store just grows faster than it should.
The fix is to publish spec-faithful, explicitly versioned variants and treat the version number as a promise: a given version cuts a given input the same way, on any machine, forever. Improvements ship under a new name people adopt on purpose, so nothing re-cuts existing data out from under anyone. Versioning also buys you cross-language conformance vectors, published inputs with expected boundaries that any implementation, in any language, can check itself against, byte for byte. That’s what turns “spec-faithful” from a claim into something you can actually test.
So whatever you pick, hold out for two things: a pinned, versioned spec of exactly how boundaries get computed, and published test vectors you can verify yourself. Speed is negotiable. Determinism isn’t.
Why we built this in the open
go-cdc-chunkers is open source for the same reason all of Plakar is. Backup is a trust problem before it is a technical one: you hand one system the single copy of your data meant to survive everything else, yet with most products you cannot read the code, review the cryptography, or verify the recovery path until the day you need it. Open source is the only honest answer I know, and it is the one I took from years on OpenSMTPD and OpenBSD: formats outlive vendors, a backup you cannot open in ten years is not a backup, and the community that reads the code is part of the security model.
Try it yourself
To see the deduplication effect directly, you can reproduce the experiment with an open source backup implementation that uses CDC. The following example uses Plakar.”
On macOS, brew install plakarkorp/tap/plakar; on any platform with Go 1.23.3 or newer, go install github.com/PlakarKorp/plakar@latest. Prebuilt binaries, apt and AUR packages for every platform are on the download page.
Create a local store (Plakar calls it a Kloset). It will prompt for a passphrase, since everything is encrypted before it touches disk:
plakar at $HOME/backups create
Now back up a directory:
plakar at $HOME/backups backup $HOME/Documents
The last line of the output tells you what happened:
info: backup: created unsigned snapshot dd62691d of size 6.4 KiB in 125ms (wrote 577 KiB)
Two numbers matter there: the logical size of what you backed up, and the bytes actually written to the store. Now the part that shows CDC working. Change one file, add a paragraph to a document, then run the exact same backup command again. You get a new, self-contained snapshot, but the bytes written the second time are a small fraction of the first, because every chunk that did not change was already in the store and is simply referenced rather than rewritten. Insert a few bytes at the top of a large file and the diagram above becomes concrete: the chunks after the edit resynchronise and deduplicate against the first snapshot instead of being stored again.
You can list snapshots, verify one is intact, then restore it somewhere else:
plakar at $HOME/backups ls
plakar at $HOME/backups check dd62691d
plakar at $HOME/backups restore -to $HOME/restored dd62691d
If you would rather look before installing anything, a public instance of the web UI runs at https://demo.plakar.io with real backups to browse.
Resources
It’s all open source: the chunking library is go-cdc-chunkers and the backup engine is Plakar, with the full v1.1.0 benchmarks published for anyone who wants to reproduce them.
Gilles Chehade is a long-time OpenBSD developer and the co-founding CTO of PlakarKorp. He created Plakar.io as a personal tool in 2015 before turning it into an open backup platform that gives security and infrastructure teams “resilience as code.”
The post Why Your Backups Are Too Big: A Practical Guide to Content-Defined Chunking appeared first on Linux.com.
Source: Linux.com