Delta sync and content-defined chunking

How file sync and backup tools transfer only what changed: fixed-size versus content-defined chunking with rolling hashes, the rsync algorithm, chunk indexes and deduplication, block-level sync for large files, compression, metadata sync, and conflict handling.

Reading is half of it. See this used in a real interview: walk through Design Dropbox →

When a user edits one paragraph of a 200 MB file, uploading the whole file again wastes bandwidth, battery and time. Dropbox, backup tools, rsync and package managers transfer only the changed parts. The core technique is chunking files into pieces identified by hashes, so unchanged pieces are recognised and skipped. "Design Dropbox" interviews expect you to explain it.

Fixed-size chunks

Split each file into blocks of, say, 4 MB and hash each. To sync, compare block hashes with the server and upload blocks it does not have.

Problem: inserting a single byte near the start shifts every later block boundary, so every block's hash changes and the whole file uploads again. Fixed chunks only work well for in-place modifications (databases, disk images) where data does not shift.

Content-defined chunking

Choose chunk boundaries based on the content, not offsets:

1. Slide a window (for example 48 bytes) over the file, computing a rolling hash that updates in constant time per byte (Rabin fingerprints, Gear or Buzhash).
2. Declare a boundary wherever the hash matches a pattern (for example, its low 13 bits are zero), giving an average chunk size of about 8 KB (or larger, tuned to the use case), with minimum and maximum limits.

An insertion changes only the chunk containing it (and maybe its neighbour); boundaries after it re-synchronise because they depend on local content. Most chunks keep the same hash, and only a few upload. Modern variants (FastCDC) are fast enough for gigabytes per second.

The rsync algorithm

rsync syncs a file between two machines when neither knows the other's exact content:

1. The receiver splits its old version into fixed blocks and sends, for each, a weak rolling checksum and a strong hash.
2. The sender slides over its new version byte by byte, using the rolling checksum to find matches at any offset, confirming with the strong hash.
3. It sends back instructions: "copy block 17", "insert these literal bytes".

It handles insertions well without storing chunk indexes, at the cost of CPU on the sender. Chunk-store systems (like Dropbox) instead keep a global index of chunk hashes.

Chunk stores and deduplication

With content-defined chunks named by their hash:

• The server stores each unique chunk once, no matter how many files or users contain it. See hashing and encoding.
• A file version is a list of chunk hashes (a manifest), which makes versions cheap: a new version shares most chunks with the previous one.
• The client asks "which of these hashes do you not have?" and uploads only those.
• Deleting requires reference counting or garbage collection of unreferenced chunks.

Cross-user deduplication has privacy implications (a user could probe whether a file exists elsewhere), so some systems deduplicate only within an account or encrypt per user. See encryption and key management.

Metadata sync

Chunks are the bulk; metadata (file tree, names, versions, manifests) is what clients sync constantly:

• The server keeps a per-user (or per-namespace) change log with a cursor; clients ask "what changed since cursor N?" See offline-first apps and sync.
• Changes are pushed by notifications or long-lived connections, then fetched.
• Directory trees can be compared quickly with hash trees. See Merkle trees.

Conflicts

Two devices edit the same file offline. File sync systems usually keep both: the later upload becomes a conflicted copy alongside the original, since binary files cannot be merged automatically. Documents with structure can merge using CRDTs or operational transformation. See CRDTs vs operational transformation.

Other optimisations

• Compression of chunks before upload (skip already-compressed formats). See compression.
• Parallel and resumable uploads of chunks; failed chunks retry independently. See media uploads and processing.
• LAN sync: devices on the same network fetch chunks from each other.
• Streaming hashes while reading files to avoid a second pass.
• Mobile awareness: defer large syncs to Wi-Fi and charging. See mobile system design.

In the interview

For Design Dropbox: "Clients split files with content-defined chunking (average around 4 MB for big files, smaller for documents), hash chunks with SHA-256, and ask the server which hashes are missing; only those upload, in parallel and resumably, to a chunk store in object storage. A file version is a manifest of chunk hashes in the metadata database; clients sync metadata through a change log with cursors and push notifications. Conflicts produce conflicted copies."

Checklist

• Content-defined chunking with a rolling hash, so edits change few chunks.
• Chunks named by strong hashes; global or per-account deduplication.
• File versions as manifests of chunk hashes; garbage collection of unused chunks.
• Metadata sync via change logs and cursors; push to trigger fetches.
• Parallel, resumable, compressed chunk transfers.
• Conflicted copies for binary files; merges only for structured documents.