Chunking and deduplication
Cutting files into pieces so uploads resume and repeats are stored once.
01The intuition
The problem it solves
You are emailing a 400-page thesis to your supervisor over a bad connection. The upload fails at page 390 and the mail client starts again from page 1. Your supervisor then sends back the same thesis with one paragraph changed, and the full 400 pages travel again. A courier would have done better: number the pages, send them in envelopes, resend only the lost envelope, and when the thesis comes back changed, swap just the one page.
File systems that sync across devices have exactly this problem. A 4 GB video on a flaky phone connection cannot be uploaded in one piece, and ten colleagues who each save the same presentation should not cost ten times the storage. Chunking cuts a file into pieces that can be moved independently; deduplication notices when a piece has been seen before and stores it once.
Build it one piece at a time
Step 1: fixed-size chunks. Cut the file every 4 MB. A 4 GB file is 1,000 chunks. Each is uploaded on its own; a failed chunk is retried alone. The file's record is a list of chunk ids in order.
Step 2: name chunks by their content. Hash each chunk (SHA-256) and use the hash as its name (content addressing). Before uploading a chunk, the client asks "do you have hash H?"; if yes, it skips the upload and just references it.
| Event | Chunks uploaded | Chunks stored | File records |
|---|---|---|---|
| Rao uploads deck.pptx (10 chunks) | 10 | 10 | Rao/deck → [h1…h10] |
| Sharma uploads the same deck.pptx | 0 | 10 | Sharma/deck → [h1…h10] |
| Rao edits slide 3 (inside chunk 2) | 1 | 11 | Rao/deck → [h1, h2′, h3…h10] |
Step 3: resume and sync. The client keeps the chunk list; after a dropped connection it compares what it has sent with what the server confirmed and continues. On another device, syncing a changed file means downloading only the chunks whose hashes changed.
Step 4: variable-size chunks. Fixed cuts have a flaw: insert one byte at the start and every chunk boundary shifts, so every hash changes. Content-defined chunking picks boundaries by looking at the bytes themselves (a rolling hash that cuts when it hits a pattern), so an insertion changes only the chunk it lands in. Chunks then average, say, 1 MB but vary.
Step 5: count references and clean up. A chunk is shared by many files, so it can be deleted only when no file references it. Keep a reference count per chunk, or run a periodic mark-and-sweep over file records. Encrypt per tenant where needed, and remember that "we already have this hash" can reveal that someone else has the same file, which is why the multi-tenant dedup problem is its own design.
Why it works, with the numbers
Resumability bounds wasted transfer by one chunk: a failure at 99 percent of a 4 GB file costs at most 4 MB to redo instead of 4 GB. Deduplication's saving is the fraction of repeated chunks, which for enterprise file sets is often 30 to 70 percent. The chunk size is a trade:
metadata per file ≈ (file size ÷ chunk size) × 32-byte hash; a 4 GB file at 4 MB chunks is 32 KB of hashes, at 64 KB chunks it is 2 MB
Smaller chunks find more duplicates and resume more finely but multiply the index; larger chunks are the reverse. The guarantee is that a file is exactly the concatenation of its chunks, verified by the chunk hashes and a whole-file hash. The failure modes are a hash collision (vanishingly rare with SHA-256, so treated as impossible), a reference count that drifts and deletes a live chunk (hence the periodic sweep), and a "do you have H?" check used as an oracle to confirm someone else's secret file.
The trade-off you must say out loud
Chunking adds a layer of indirection and an index that must stay consistent; deduplication adds reference management and a privacy question. Say the chunk size and why, say fixed or content-defined, and say how deletion works. The interviewer's follow-up is often "what changes if files are encrypted per user?", and the honest answer is that dedup across users then mostly stops working, unless you use convergent encryption and accept its leaks.
Where it shows up in the 100 Google problems
- Design Google Drive: chunks make resumable uploads and delta sync possible; dedup makes shared files nearly free.
- Design a distributed file system (GFS): 64 MB fixed chunks on chunkservers, chosen large to keep the master's index small.
- Design Google Photos: the same photo backed up from two phones is stored once.
- Design deduplicated multi-tenant file storage: the whole design is chunk-level dedup plus the privacy and quota accounting it forces.