Skip to content

Content addressing and deduplication

Naming data by the hash of its bytes, so identical content gets one name, verifies itself and is stored once. File sync and backup use it to cut storage and upload cost, paying with an index and garbage collection.

On this page

What it is

Content addressing means the key of a stored object is derived from its bytes, usually by a cryptographic hash, instead of being chosen by whoever stores it. Git's object store is the familiar case: a key-value store where you hand in content and get back a SHA-1 of that content plus a small header, and the object lives in a directory named by the first two characters of that hash. A tree object then lists each entry's mode, type, filename and the hash of its blob or subtree, so a tree's hash covers everything beneath it. Two consequences follow. An object under a given key is immutable, because changing a byte changes the key, short of a hash collision. And anyone holding the key can check what they fetched by hashing it again: the OCI image spec says exactly this about the digest in a descriptor, which identifies a layer or manifest by a collision-resistant hash and lets a client verify content pulled from an untrusted source. The spec requires SHA-256 support and writes digests as sha256: followed by 64 hex characters.

Deduplication follows from content keys: writing the same bytes twice lands on the same key, so a lookup can detect the repeat and skip the second write. Detecting is the easy part; the index that answers the lookup and the tracking of who still uses a chunk are where the cost lives, as the OpenZFS section below shows. Before that comes the question of the unit you hash. A whole file catches exact re-uploads. Dropbox's 2014 description of its sync protocol splits each file into 4 MB blocks, hashes each with SHA-256 and represents the file as the ordered list of those hashes, a blocklist, so two files that share blocks share storage. restic goes one step further for backups: fixed-size chunks fail when a user inserts bytes at the start of a file, because every boundary shifts and almost every chunk hashes to something new, so it picks boundaries from the content instead.

Unit hashedCatchesMissesExample

Whole file

Exact copies, re-uploads, renames

A single changed byte anywhere

Git blobs, an object store keyed by file hash

Fixed-size block

Shared blocks at the same offsets, appends

Inserts that shift later bytes

Dropbox 4 MB blocks

Content-defined chunk

Shared regions wherever they sit in the file

Little; boundaries fall differently, so a region the fixed scheme matched can be cut another way. Costs more CPU

restic; FastCDC-style chunkers

How content-defined chunking finds a boundary. restic runs a rolling hash (a Rabin fingerprint) over a sliding 64-byte window and declares a chunk boundary wherever the lowest 21 bits of the fingerprint are zero. Because a boundary depends on the 64 bytes just before it, an insert usually disturbs the chunk it lands in and leaves later boundaries where they were: in restic's worked example, adding 20 bytes at the front of a 4 MiB file changed the first chunk and left the other three with the same SHA-256, so just the first one needed saving. Chunk sizes vary within limits, which is the price of content-defined boundaries. The other price is CPU: the FastCDC paper (USENIX ATC 2016) describes the overhead of classic approaches as computing and judging a rolling hash at every byte, and reports its own approach as about ten times faster than the best open-source Rabin-based chunker it measured while keeping nearly the same dedup ratio, partly by skipping cut-points below a minimum chunk size and then normalizing the size distribution so the ratio doesn't drop.

The bookkeeping nobody draws. Dedup needs an index from hash to location, and some way to know when a chunk's last owner is gone, because one chunk can belong to many files. How eagerly you consult them is a design choice, and OpenZFS shows the expensive end of it in its current dedup page, the one that covers the fast dedup feature: dedup there is synchronous, every unique block gets an entry in the dedup table, the table is checked on every write and every free, and the guidance is to plan for at least 1.25 GiB of RAM per TiB stored, with the real figure depending on block size and how much really repeats. Turning dedup off later stops new sharing but doesn't undo any; shared blocks stay until the last reference is freed. A store you build yourself needs the same two pieces in some form: a hash index sized for every unique chunk, and either a reference count kept on each write and delete or a periodic mark-and-sweep, so that deleting one file doesn't remove a chunk another file still points at.

When to use it

Reach for it when the same bytes arrive many times. File sync and sharing: in Dropbox's protocol the client first commits a blocklist for a path, the metadata server checks which hashes it already knows and answers with the ones it needs, and the client uploads just those blocks to the block server, which is a key-value store from hash to contents. On download the client checks whether it already has a block locally, in another file or its deleted-file cache, before fetching it. Backups: restic's second run over an unchanged 100 MiB file finished in under a second and added nothing to the repository, and a copied file added nothing either, because every chunk hash was already present. Container images and other artifacts: OCI descriptors name layers by digest and have the client verify what it fetched; the spec defines the identifier and the check, and keeping one copy of a layer that many images share is the design a registry naturally builds on top of it. OpenZFS's own list of workloads where dedup pays is similar: VM images built from a common base and backup targets receiving many similar systems.

Content addressing is also worth it without any duplication when you want immutability and verification: an artifact that any mirror or cache can serve, because the client recomputes the digest and rejects a tampered copy. The OCI descriptor carries a size next to the digest so a client knows how many bytes to expect before it starts, which bounds the download even when the source is hostile.

When not to

Skip it when little repeats. OpenZFS's advice is to try compression first and to simulate the dedup table on existing data before enabling dedup; if the simulated ratio isn't comfortably above 2x, it isn't worth the lookup on every write and the RAM for the table, and for general file storage compression gives most of the benefit at a fraction of the cost. Our reading of that for a design you build: media libraries of unique photos and videos, and anything where users rarely upload the same bytes twice, are poor candidates. A plain unique key per upload, with compression where it helps, is the right answer there.

Encrypted-per-user data defeats cross-user dedup. If each user encrypts with their own key before upload, the same plaintext yields different ciphertext per user, so the hashes differ and the content is not shared. OpenZFS makes the same trade on encrypted datasets: a dataset deduplicates against itself, its snapshots and its clones, not across datasets, and its documentation notes that even then the table reveals which blocks inside the dataset are identical. Our advice: if the product promise is that the server can't read user files, drop cross-user dedup from the design rather than weaken the encryption to get it back.

The lookup can be a side channel. A protocol that tells the client which blocks it still needs before the bytes are sent, as Dropbox's commit step does, answers from what the server already holds; Dropbox's description has the server check both whether the hashes are known and whether this user or namespace has access, which is the control that keeps the answer from being a global existence check. Our advice for a design of your own: scope the reply to content the caller may already read, or dedup after the upload completes so the client learns nothing, when the existence of a file is itself sensitive. For public or low-sensitivity data, the pre-upload answer is fine. And treat the hash as a strong claim, not a proof: OpenZFS offers a verify mode that compares bytes when two blocks share a checksum, at the cost of a read per match, which is the right choice when a silent false match would be unacceptable.

Mutable names still have to live somewhere. Content addresses are immutable by construction, so a system still needs a layer that maps a human name to the current hash: Dropbox keeps an append-only journal that maps a namespace and path to a blocklist, and a version control tree maps file names to blob hashes. If your data is a small mutable record edited in place, a row in a database with a normal primary key is simpler than content addressing with a rename layer on top.

Compared

ApproachWhat it savesWhat it costsWhen it's the right choice

Unique key per upload, no dedup

Nothing

No dedup index or lookup on write

Data is unique or encrypted per user; writes must stay cheap; duplication would be under 2x

Compression per block or object

Redundancy inside one object

CPU per write and read

General file storage where cross-file repeats are rare, which OpenZFS suggests trying before dedup

Whole-file hashing

Exact re-uploads and copies

One hash per file; a small index

Shared documents and attachments that are copied unchanged; the simplest dedup to run

Fixed-size blocks

Repeated blocks at the same offsets, appended files, resumable partial uploads

Index entry per block; misses shifted content

Sync clients and VM images where edits replace or append rather than insert

Content-defined chunks

Repeated regions after inserts and deletes anywhere

A rolling hash over the data, byte by byte in the classic form; variable chunk sizes

Backups and version histories of edited files, where the extra redundancy found pays for the CPU

In a picture

ClientChunk and hash

Step 1 of 4

Hash on the client

The client splits the file into chunks and hashes each one, producing an ordered list of digests that stands for the file.

How to say it in an interview

The common mistake

Quiz

A user inserts 20 bytes at the start of a 4 GB file stored as fixed 4 MB blocks. How much must be re-uploaded?
A user deletes a file in a deduplicated store. Why can't the server delete its chunks right away?
Each user encrypts files on their device with their own key before upload. What happens to cross-user deduplication?
Your upload API returns "already stored" from the hash alone, before any bytes are sent. What does a caller learn?

Questions that use this

Related

Sources

  1. Pro Git, 2nd edition: Git Internals - Git Objects
  2. OCI Image Format Specification: Content Descriptors (main branch)
  3. Dropbox tech blog: Streaming File Synchronization (2014)
  4. restic blog: Foundation - Introducing Content Defined Chunking (2015)
  5. USENIX ATC '16: FastCDC: a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication (abstract)
  6. OpenZFS documentation: Deduplication
Sign in to report a mistake