Design a File Storage Service: Chunking, Dedup and Sync

"Design a file storage and sync service" sounds like "put files in object storage". The interview is about what comes next: a user edits one paragraph of a huge file and expects every device to update in seconds, without re-sending gigabytes. The answer is to think in chunks named by their hash.

The problem it solves

State the requirements first. The lesson's illustrative assumptions:

• Keep one folder identical on several devices and in the cloud, around 100 GB per user.
• Files up to 10 GB, and the common case is a small edit to a large file.
• Work offline, then reconcile, without silently losing anyone's edit.
• Durable storage: once the service acknowledges a save, the bytes survive.

The naive design uploads the whole file on every save: 10 GB to change a few kilobytes, and 10 GB again down to every other device.

The intuition

Split each file into chunks of a few megabytes and name each chunk by a cryptographic hash of its bytes. Two pieces of state now describe everything:

1. Metadata, in a database: for each file, a list of versions, and each version is just an ordered list of chunk hashes, plus owner, path and timestamps. Small, hot and relational.
2. Blobs, in object storage: hash → bytes. Huge, cold and immutable. Keeping them out of the database stops it becoming the bottleneck for every operation.

A save becomes: chunk and hash locally, ask the metadata service which hashes it has never seen, upload only those, and commit the new version as a list of hashes. Other devices hear "file X has version 7", fetch that list, and download only what they lack. As of October 2026, mainstream object stores offer pre-signed URLs and multipart uploads, so chunk bytes can bypass your API servers.

Three details separate a good answer from a sketch:

• Where to cut. Fixed-size chunks work for edits that keep the length, but inserting a single byte shifts every later boundary, so every later chunk gets a new hash. Content-defined chunking cuts wherever a rolling hash of the last few dozen bytes matches a pattern, so boundaries move with the content and resynchronise just after the edit.
• Concurrent edits. A commit names the version it was based on. If the head has moved, two devices edited the same file; keep both as a conflicted copy rather than guessing a winner.
• Deduplication and deletion. Identical chunks are stored once, across files and even users. A chunk can be deleted only when no version references it, so count references or periodically mark what is reachable. Cross-user dedup also leaks information: a suspiciously fast upload means someone already stored that file, so services may limit dedup to one user's own data.

Watch it run

The animation starts with a ten-gigabyte document with one paragraph changed: sending all of it is the answer to beat. The client cuts the file into chunks and hashes each one, 2,500 of them. Then it asks the metadata service which of those hashes already exist. Two of the three shown are known from the last save; only c2 is new, so one of three goes up. Four megabytes cross the wire instead of ten gigabytes, and the bytes go to blob storage. A version is just an ordered list of hashes, committed as metadata: v7. Metadata, not the bytes, tells the other device that something moved, and device B pulls the single chunk it lacks and rebuilds the file locally. Two users holding the same chunk share one copy, so content addressing is free dedup. When both devices edit while offline and both commit, the service keeps two versions rather than guess a winner. The bill: an index of every chunk, and hashing the whole file on every save.

The code

A toy model, scaled down a thousandfold: a 256 KiB file and 4 KiB chunks instead of gigabytes and megabytes. It compares fixed chunks with content-defined chunks for an in-place overwrite and for a 100-byte insertion, counting how many chunks each save must upload:

import hashlib
import random
from collections import Counter

rng = random.Random(33)
GEAR = [rng.getrandbits(32) for _ in range(256)]     # one random number per byte value

def fixed_chunks(data, size=4096):
    return [data[i:i + size] for i in range(0, len(data), size)]

def cdc_chunks(data, mask=0xFFF, min_size=1024, max_size=16384):
    """Content-defined: cut where a rolling hash of the last bytes hits a pattern."""
    chunks, start, h = [], 0, 0
    for i, byte in enumerate(data):
        h = ((h << 1) + GEAR[byte]) & 0xFFFFFFFF       # a byte's effect is gone after 32 steps
        size = i + 1 - start
        if (size >= min_size and h & mask == 0) or size >= max_size:
            chunks.append(data[start:i + 1])
            start, h = i + 1, 0
    if start < len(data):
        chunks.append(data[start:])
    return chunks

def digest(chunk):
    return hashlib.sha256(chunk).hexdigest()

class Server:
    """Metadata: file -> versions, each an ordered list of hashes. Blobs: hash -> bytes."""
    def __init__(self):
        self.blobs, self.versions, self.refs = {}, {}, Counter()

    def missing(self, hashes):
        return [h for h in dict.fromkeys(hashes) if h not in self.blobs]

    def commit(self, name, chunks):
        hashes = [digest(c) for c in chunks]
        need = set(self.missing(hashes))
        for c in chunks:                                # the client uploads only these
            if digest(c) in need:
                self.blobs[digest(c)] = c
        self.refs.update(set(hashes))                   # one reference per version
        self.versions.setdefault(name, []).append(hashes)
        return len(need)

    def read(self, name, version=-1):
        return b"".join(self.blobs[h] for h in self.versions[name][version])

    def delete_version(self, name, version):
        for h in set(self.versions[name].pop(version)):
            self.refs[h] -= 1
            if self.refs[h] == 0:                       # no version needs it any more
                del self.refs[h], self.blobs[h]

doc = bytes(rng.getrandbits(8) for _ in range(256 * 1024))   # a 256 KiB "large file"
mid = len(doc) // 2
overwrite = doc[:mid] + b"x" * 100 + doc[mid + 100:]         # same length, bytes changed
insert = doc[:mid] + b"x" * 100 + doc[mid:]                  # 100 bytes added

for name, chunker in (("fixed", fixed_chunks), ("content-defined", cdc_chunks)):
    s = Server()
    uploads = [s.commit("doc", chunker(v)) for v in (doc, overwrite, insert)]
    print(name, uploads, s.read("doc") == insert, s.read("doc", 0) == doc)
# fixed [64, 1, 33] True True
# content-defined [58, 1, 1] True True

s.commit("copy-of-doc", cdc_chunks(doc))         # another user, same bytes
print(len(s.blobs))                              # 60  stored once: content addressing dedups
s.delete_version("doc", 0)                       # its chunks live on in the copy
s.delete_version("doc", 0)                       # the overwrite: one chunk was only its own
print(len(s.blobs), s.read("copy-of-doc") == doc, s.read("doc") == insert)   # 59 True True

Both schemes upload one chunk for the overwrite. For the insertion, fixed chunks re-upload 33 of 64, everything after the edit; content-defined chunks upload one. Next, 200 seeded random files, each edited up to five times: chunking must lose nothing, "missing" must match a brute force over every chunk ever committed, every version must rebuild from blobs, and after random deletions the stored blobs must be exactly those a remaining version reaches:

def brute_missing(history, hashes):
    """Brute force: scan every chunk of every version ever committed."""
    seen = [h for version in history for h in version]
    return [h for h in dict.fromkeys(hashes) if h not in seen]

ok = True
for _ in range(200):
    base = bytes(rng.getrandbits(8) for _ in range(rng.randint(0, 40_000)))
    s, history = Server(), []
    for _ in range(rng.randint(1, 5)):
        at, cut = rng.randint(0, len(base)), rng.randint(0, 300)
        base = base[:at] + bytes(rng.getrandbits(8) for _ in range(rng.randint(0, 300))) + base[at + cut:]
        chunks = rng.choice([fixed_chunks, cdc_chunks])(base)
        ok &= b"".join(chunks) == base                       # chunking loses nothing
        hashes = [digest(c) for c in chunks]
        ok &= s.missing(hashes) == brute_missing(history, hashes)
        name = rng.choice(["a", "b"])
        s.commit(name, chunks)
        history.append(hashes)
        ok &= s.read(name) == base                           # rebuilt from blobs alone
    for name in list(s.versions):                            # delete versions at random
        while s.versions[name] and rng.random() < 0.6:
            s.delete_version(name, rng.randrange(len(s.versions[name])))
    live = {h for vs in s.versions.values() for v in vs for h in v}
    ok &= set(s.blobs) == live                               # brute force: mark what is reachable
print(ok)                                                    # True

The complexity

• Save: hashing is linear in file size on the client, every time; upload is proportional to the changed chunks.
• Metadata: one row per chunk reference per version, so a 10 GB file at 4 MB chunks is about 2,500 entries per version.
• Storage: unique chunks only, plus old versions until they are deleted.

Where it goes wrong

• Bytes in the database. Metadata and blobs scale differently; mixing them kills the database.
• Fixed chunks with insertions. Every chunk after the edit changes; cut by content.
• Last writer wins. Silently discarding an offline edit is the bug users remember; keep a conflicted copy.
• Deleting a chunk too early. An upload in flight may reference a chunk the collector thinks is dead; delete only after a grace period.
• Notifying with bytes. Push "version 7 exists", not the file; devices pull what they lack.

When it shows up in interviews

As "design a file sync service", "design cloud storage" or "design a shared drive". Expect follow-ups on chunk size, resumable uploads, conflict handling, notification fan-out to devices (long polling or WebSockets), and how deletion interacts with dedup. The hashing ideas connect to consistent hashing when the blob store itself is sharded.

How to say it in an interview

"I'd separate metadata from bytes. Files are split into chunks of a few megabytes, named by their SHA-256. A version is an ordered list of chunk hashes in a metadata database; the chunks live in object storage, keyed by hash. On save, the client hashes locally, asks which hashes are missing, uploads only those, then commits the version against the version it was based on, so concurrent edits become a conflicted copy instead of a lost update. Other devices get a notification, fetch the chunk list, and download what they lack. I'd use content-defined chunking so insertions don't shift every boundary, and reference counting with a grace period for deletion."