Design object storage and file sync

"Design Dropbox: files sync across a user's devices, 100 million users, and a 2 GB file edited on one device should not re-upload 2 GB."

Step 1: clarify (4 minutes)

Two systems are being asked for and they should be separated immediately:

STORAGE      Durable, cheap, content-addressed blob storage.
             Solved problem in shape: chunks in object storage,
             metadata in a database.

SYNC         Detecting change, transferring the minimum, and
             reconciling concurrent edits across devices.
             This is the hard part, and it is where the design
             is actually evaluated.

The clarifications:

Scale       100M users, ~50 GB average, ~5 EB total
            ~10M active devices at any moment
Files       Long tail: 60% of files under 100 KB, but 80% of
            BYTES are in files over 10 MB. Both matter, for
            different reasons.
Sync target Under 5 s from save on device A to visible on
            device B, for a small change
Conflicts   Two devices edit the same file offline. What happens?
            THIS is the question that determines the design.
Sharing     Assume folder-level sharing with a permission model,
            because it changes the metadata design substantially

The question worth asking explicitly: "On a conflict, do we merge, pick a winner, or keep both? For a general file sync the only honest answer is keep both, because we cannot merge arbitrary binary content and silently discarding someone's work is the failure users never forgive."

Step 2: capacity math (4 minutes)

Storage
  100M users x 50 GB = 5 EB logical.
  Deduplication: cross-user dedup on identical chunks typically
  removes a large fraction in consumer workloads (shared media,
  installers, common documents). Assume 30% -> 3.5 EB physical.
  With erasure coding at 1.4x overhead instead of 3x replication:
    3.5 EB x 1.4 = ~4.9 EB raw.
    Against 3x replication that would be 10.5 EB.
  *** Erasure coding saves ~5.6 EB, which at any storage price
  is the single largest cost decision in the design. ***

Chunk metadata
  Average chunk 4 MB -> 3.5 EB / 4 MB = ~875 billion chunks.
  Each chunk record ~100 bytes (hash, size, location, refcount)
  -> ~87 TB of chunk metadata.
  *** The metadata is itself a large distributed database. ***
  This is the number people miss: metadata scale is why file
  sync is hard, not blob storage.

File metadata
  100M users x ~50,000 files = 5 trillion file records.
  -> Sharded by user, because every query is user-scoped.
     This is a clean partition key and it should be named as one.

Notification fan-out
  10M active devices, each needing near-real-time change
  notification.
  Long-lived connections: 10M concurrent.
  At ~100k connections per node -> ~100 notification servers.
  These connections are mostly idle: the design is
  connection-bound, like the LLM gateway.

Change rate
  ~500M file changes/day = ~6,000/sec average, bursty.
  Each change fans out to that user's other devices (~3) plus
  any shared-folder members.

Two numbers drive the design: 875 billion chunk records, and erasure coding saving over 5 exabytes. The first says the metadata store is the hard engineering problem; the second says the storage layer's main decision is redundancy scheme, not filesystem.

Step 3: content-defined chunking

This is the mechanism that answers the "do not re-upload 2 GB" requirement, and getting it right is the core of the design.

FIXED-SIZE CHUNKING (naive)
  Split every 4 MB. Insert one byte at the start of the file:
  every subsequent chunk boundary shifts, every chunk hash
  changes, the entire file re-uploads.
  *** Fails on the exact case the requirement names. ***

CONTENT-DEFINED CHUNKING (rolling hash)
  Slide a window over the bytes and cut where the rolling hash
  satisfies a condition. Boundaries are determined by CONTENT,
  so an insertion shifts only the chunk containing it.
  Insert one byte -> ONE chunk changes.

# Rabin-style content-defined chunking. The boundary condition is
# a property of the data, which is why insertions are local.
WINDOW  = 48
MASK    = (1 << 22) - 1        # target ~4 MB average chunk
MIN_SZ  = 1 << 20              # 1 MB: avoids pathological tiny chunks
MAX_SZ  = 1 << 23              # 8 MB: bounds worst case

def chunk(data: bytes):
    start, h = 0, RollingHash(WINDOW)
    for i, b in enumerate(data):
        h.roll(b)
        size = i - start + 1
        # Cut on a content-determined condition, or when the chunk
        # gets too large. Min size prevents a degenerate stream of
        # tiny chunks on low-entropy data.
        if size >= MIN_SZ and ((h.value & MASK) == 0 or size >= MAX_SZ):
            yield data[start:i + 1]
            start, h = i + 1, RollingHash(WINDOW)
    if start < len(data):
        yield data[start:]

The concrete answer to the requirement:

2 GB file, ~500 chunks at 4 MB average.
Edit 10 KB in the middle:
  Fixed chunking:   1 chunk changes IF the edit is in-place, but
                    ANY insertion or deletion shifts every
                    subsequent boundary -> up to 500 chunks.
  Content-defined:  1-2 chunks change regardless of insertion.
  Upload: ~8 MB instead of 2 GB. *** 250x less. ***

The min and max size bounds matter and are usually omitted. Without a minimum, low-entropy data (a file of zeros, or highly repetitive text) hits the boundary condition constantly and produces thousands of tiny chunks, and the per-chunk metadata overhead then exceeds the data. Without a maximum, high-entropy data can produce one enormous chunk.

Deduplication falls out for free. Chunks are addressed by their hash, so an identical chunk anywhere (same user, different user, different file) is stored once.

Client uploads: "I have chunks [h1, h2, ..., h500]"
Server replies: "I already have h1-h497. Send h498 and h499."
-> The upload negotiation is a set difference on hashes, which
   is cheap and is where the 250x saving is actually realised.

The security caveat to name: cross-user deduplication leaks information. If a user can observe that uploading a file was instant, they learn someone else already has that exact file, which is a confirmed-file-existence attack. The mitigations are per-user dedup only (losing most of the saving), or randomised upload delays, or client-side encryption with a per-user key (which eliminates cross-user dedup entirely by construction).

Step 4: the sync protocol

DEVICE                          SERVER
  │                               │
  │  1. long-poll / websocket     │
  │     "cursor = 88412"          │
  │◄──────────────────────────────┤  2. change since 88412:
  │                               │     file X, new version, chunks
  │                               │     [h1..h500], cursor 88413
  │  3. which chunks do I lack?   │
  │     local diff, no network    │
  │                               │
  │  4. GET missing chunks ───────┤  from object storage / CDN,
  │◄──────────────────────────────┤  NOT from the metadata service
  │                               │
  │  5. reassemble, write, ack    │
  │     cursor = 88413            │

Four properties worth defending:

A monotonic per-user cursor, not timestamps. A cursor makes "what changed since I was last online" a single indexed range scan, and it is immune to clock skew across devices. Timestamps require a tolerance window and produce either missed or duplicated changes.

Chunk transfer is separate from metadata. Chunks come from object storage or a CDN; the metadata service never proxies bytes. That is what keeps the metadata service small and what lets chunk delivery be cached at the edge.

The client computes the diff. The server says "the file is now these chunks"; the client determines which it lacks. That is zero server work per device and it is why the same change can fan out to millions of devices cheaply.

Changes are a log, not a state diff. A device offline for a month replays the log from its cursor rather than comparing full trees, and log compaction handles the case where a file changed 400 times.

Step 5: conflicts

The premise question from step 1, answered.

Device A (offline): edits report.docx at 10:00
Device B (offline): edits report.docx at 10:05
Both come online at 10:10.

Options:
  LAST WRITER WINS   One edit is silently destroyed. For a
                     photo library this is annoying; for a
                     document someone worked on for two hours
                     it is unforgivable, and users do not
                     forgive it.

  MERGE              Only possible for known formats with a
                     merge function. Text: sometimes. Binary:
                     no. General file sync cannot assume format.

  KEEP BOTH          "report.docx" and
                     "report (Device B's conflicted copy).docx"
                     Ugly, visible, and never destroys work.

Keep both, and this is the position to state clearly: for general file sync, silent data loss is a far worse failure than an ugly filename. Dropbox, Google Drive and OneDrive all do this, which is convergent evidence rather than a coincidence.

Detection uses version vectors, not timestamps:

# Per-file version vector: one counter per DEVICE that has
# modified it. Bounded by the user's device count, which is small.
def detect(local: dict, remote: dict) -> str:
    l_gt = any(local.get(d, 0) > remote.get(d, 0) for d in local | remote)
    r_gt = any(remote.get(d, 0) > local.get(d, 0) for d in local | remote)
    if l_gt and r_gt: return "CONFLICT"      # genuinely concurrent
    if l_gt:          return "LOCAL_NEWER"
    if r_gt:          return "REMOTE_NEWER"
    return "SAME"

Timestamps cannot distinguish "concurrent edit" from "sequential edit with a skewed clock", and version vectors can. A device whose clock is an hour fast would win every conflict under LWW, silently.

Where merging IS possible, it is worth doing, and it is a per-format decision: a CRDT for collaborative documents (which is what Google Docs and Notion do, and it is a different product than file sync), three-way merge for text with a common ancestor. The design should allow a format-specific merge handler while defaulting to keep-both.

Step 6: metadata storage

875 billion chunk records and 5 trillion file records is the real engineering problem.

FILE METADATA        sharded by user_id
  Every query is user-scoped ("list my files", "what changed
  since cursor N"), so user_id is a clean partition key with
  no cross-partition queries in the common path.
  Shared folders are the exception and are handled by a
  separate membership table plus a fan-out on change.

CHUNK METADATA       sharded by chunk_hash
  hash -> (storage_location, size, refcount)
  Hash-sharding is uniform by construction and the lookup is
  always by hash, so there is never a scan.

REFERENCE COUNTING   the operationally hard part
  A chunk is deletable when no file version references it.
  Naive refcounting races with concurrent uploads: a chunk's
  count drops to zero while an upload that will reference it
  is in flight, and the chunk is deleted underneath it.
  -> Mark-and-sweep with a grace period rather than immediate
     refcount deletion: mark unreferenced chunks, wait (say)
     7 days, sweep. An upload during the window resurrects it.
     This is the same reasoning as Cassandra's gc_grace_seconds.

Naming the refcount race and the grace-period fix is a strong signal, because it is the kind of problem that only appears in production and only under concurrency.

Step 7: storage layer

ERASURE CODING rather than replication
  Reed-Solomon (10, 4): 10 data shards + 4 parity shards.
  Tolerates any 4 shard losses. Overhead: 1.4x.
  Against 3x replication: same or better durability at less
  than half the storage.
  At 3.5 EB logical that is a difference of ~5.6 EB.

  The cost: a read requires 10 shards, so it is more expensive
  and higher-latency than reading one replica, and a repair
  requires reading 10 shards to rebuild 1.
  -> Hot chunks get a cached full copy; cold chunks live only
     as erasure-coded shards. Which is the same hot/cold
     tiering as any storage system.

PLACEMENT
  Shards spread across failure domains: different racks,
  different availability zones. The durability claim depends
  entirely on failure independence, and co-locating shards on
  one rack makes the arithmetic a lie.

TIERING
  Hot (accessed in 30 days)   -> SSD-backed, full copy cached
  Warm                        -> erasure-coded on HDD
  Cold (untouched 1 year)     -> archival tier, slower retrieval
  Access is extremely skewed: a small fraction of chunks serve
  most of the reads, so tiering is a large real saving.

Step 8: failure modes

Device offline for months
  -> Replays the change log from its cursor. If the log has been
     compacted past that point, fall back to a full tree
     comparison using per-directory hashes so the comparison is
     logarithmic rather than a full file listing.

Partial upload interrupted
  -> Chunks are content-addressed and idempotent, so resume is
     "which chunks do you already have". No special resume
     protocol is needed, which is a real benefit of content
     addressing and worth pointing out.

Chunk corrupted at rest
  -> Verify the hash on read; it is content-addressed so
     verification is free. Repair from parity shards.
     Background scrubbing to find corruption before a user does.

User deletes a shared folder
  -> Deletion is a metadata operation on their view. The chunks
     survive because others reference them, and the refcount
     grace period covers the race.

Clock skew between devices
  -> Version vectors, not timestamps. Skew affects nothing.

Metadata shard unavailable
  -> That user cannot sync; others are unaffected. Sharding by
     user is what bounds the blast radius, and it is the main
     operational argument for that partition key.

A user with 10 million small files
  -> The metadata, not the bytes, is the problem: 10M file
     records and a change log to match. Rate-limit per-user
     metadata operations and treat this as a distinct workload
     rather than an outlier of the normal one.

Step 9: what changes at ten times the scale

At 1 billion users and 50 exabytes:

Chunk metadata becomes the dominant system. 8.75 trillion chunk records is beyond a single sharded database, and the move is to embed location information in the chunk address itself (a deterministic placement function from hash to storage location) so the lookup becomes computation rather than a database read. This is what large object stores do, and it removes a database from the hot path entirely.

Larger average chunks. Doubling the average chunk to 8 MB halves the metadata at the cost of worse deduplication and larger deltas. That trade shifts as metadata cost grows relative to storage cost.

Regional data residency partitions the whole system. A user's chunks must live in their region, which breaks global cross-user deduplication into per-region deduplication and reduces the dedup saving.

Notification fan-out becomes its own platform, at 100 million concurrent connections, which is the notification fan-out design at a different scale.

Production evidence

Dropbox's "Magic Pocket" write-ups describe their move from S3 to a custom exabyte-scale storage system using erasure coding, and their published rationale is precisely the storage-overhead arithmetic above.

Content-defined chunking with a Rabin fingerprint originates in Muthitacharoen et al., "A Low-Bandwidth Network File System" (SOSP 2001), which is the primary source for the insertion-locality property.

rsync's rolling checksum (Tridgell and Mackerras, 1996) is the earlier and simpler version of the same idea applied to a single file pair.

Reed-Solomon erasure coding in Facebook's f4 and Microsoft Azure's Local Reconstruction Codes are the production references for the durability-at-lower-overhead argument, and Azure's LRC paper documents the repair-cost problem that motivated a variant scheme.

Dropbox's, Google Drive's and OneDrive's conflicted-copy behaviour is convergent evidence for keep-both: three independent teams reached the same conclusion that silent loss is unacceptable for general file sync.

Cross-user deduplication side channels are documented in the security literature (Harnik, Pinkas and Shulman-Peleg, 2010), which is the basis for the caveat in step 3.

The debate

The case for content-defined chunking: it is the only approach that makes an insertion local, which is exactly the requirement. Fixed chunking fails the stated case.

The case for fixed chunking: simpler, faster to compute, and predictable metadata size. For workloads dominated by whole-file replacement (photos, videos, most consumer files) the insertion case rarely arises, and the extra CPU of a rolling hash on every byte of every file is real.

The case for delta-encoding against the previous version instead: transfer only a binary diff against the version the server already has. Smaller transfers than chunk-level granularity, and it requires the server to hold the previous version and to compute diffs, which does not deduplicate across users and does not parallelise.

My position: content-defined chunking with bounded min and max sizes, content-addressed storage, erasure coding, and keep-both on conflict.

Content-defined chunking because the requirement explicitly names the insertion case, and because content addressing gives deduplication and resumable uploads for free rather than as separate features. The min and max bounds are not optional: without a minimum, low-entropy files produce thousands of tiny chunks and metadata overhead exceeds the data.

Erasure coding because at this scale it is the largest single cost decision in the design: 1.4x overhead against 3x replication is over 5 exabytes of difference at equal or better durability. The cost is read amplification and repair cost, which is what the hot-chunk cache is for.

Keep-both on conflict, without hedging. Last-writer-wins silently destroys work that someone spent hours on, and it is the failure users never forgive. An ugly filename is a small price, and the fact that Dropbox, Drive and OneDrive all made the same choice independently is strong evidence rather than mimicry.

And version vectors rather than timestamps for conflict detection, because timestamps cannot distinguish a genuinely concurrent edit from a sequential one with a skewed clock, and a device an hour fast would win every conflict silently.

Where I would flag a risk unprompted: cross-user deduplication is a confirmed-file side channel. If an upload completes instantly, the uploader learns someone else has that exact file. For a consumer product that is usually an accepted trade; for anything handling sensitive documents it is not, and client-side encryption with per-user keys eliminates it by making cross-user dedup impossible.

Follow-up Q&A

"How do you avoid re-uploading 2 GB for a 10 KB edit?" Content-defined chunking. A rolling hash slides over the bytes and cuts a chunk boundary where the hash meets a condition, so boundaries are determined by content rather than by offset. That means inserting a byte shifts only the chunk containing it, instead of shifting every subsequent boundary as fixed-size chunking would. A 2 GB file is about 500 chunks at 4 MB average, and a small edit changes one or two of them, so the upload is about 8 MB instead of 2 GB.

"Why do min and max chunk sizes matter?" Without a minimum, low-entropy data hits the boundary condition constantly: a file of zeros or highly repetitive text produces thousands of tiny chunks, and per-chunk metadata overhead then exceeds the data itself. Without a maximum, high-entropy data can run a long way before hitting a boundary and produce one enormous chunk. Those bounds are usually omitted in interview answers and they are what makes the scheme work on real data.

"How does deduplication work, and what does it cost?" It falls out of content addressing: chunks are keyed by hash, so an identical chunk anywhere is stored once, and the upload negotiation becomes a set difference on hashes. The cost is a security one: cross-user dedup is a confirmed-file side channel, because an instant upload tells the uploader that someone else already has that exact file. Mitigations are per-user dedup, which loses most of the saving, randomised delays, or client-side encryption with per-user keys, which removes cross-user dedup entirely.

"Two devices edit the same file offline. What happens?" Keep both, with a conflicted copy. Last-writer-wins silently destroys work someone spent hours on, and that is the failure users never forgive. Merging is only possible for known formats with a merge function, and general file sync cannot assume format. The fact that Dropbox, Drive and OneDrive independently made the same choice is good evidence it is right. I would allow a format-specific merge handler where one exists, defaulting to keep-both.

"How do you detect that two edits were concurrent rather than sequential?" Version vectors, one counter per device that has modified the file, bounded by the user's device count. If each side has a counter the other does not dominate, the edits are genuinely concurrent. Timestamps cannot make that distinction: a device whose clock is an hour fast would win every conflict under last-writer-wins, silently, and the user would never know which of their edits survived.

"Why erasure coding rather than replication?" Cost, at equal or better durability. Reed-Solomon with 10 data and 4 parity shards tolerates any four losses at 1.4x overhead, against 3x for triple replication. At 3.5 exabytes logical that is a difference of over 5 exabytes, which is the single largest cost decision in the design. The trade is read amplification, since a read needs ten shards, and expensive repair, since rebuilding one shard reads ten. So hot chunks keep a cached full copy and cold chunks live only as shards.

"What's the actual hard part of this system?" The metadata, not the bytes. Around 875 billion chunk records and 5 trillion file records is a large distributed database in its own right, and blob storage is the comparatively solved part. The specific operational trap is reference counting: a chunk's count can drop to zero while an upload that will reference it is in flight, so it gets deleted underneath. The fix is mark-and-sweep with a grace period rather than immediate deletion, which is the same reasoning as Cassandra's gc_grace_seconds.

"How does a device that has been offline for three months catch up?" It replays the per-user change log from its cursor. A monotonic cursor rather than timestamps makes that a single indexed range scan and is immune to clock skew. If the log has been compacted past its cursor, it falls back to a tree comparison using per-directory hashes, so unchanged subtrees are ruled out with one comparison and the work is proportional to what changed rather than to the file count.

"How do you shard this?" File metadata by user id, because every query in the common path is user-scoped, so there are no cross-partition queries and a shard failure affects only those users. Chunk metadata by chunk hash, which is uniform by construction and always looked up by hash so there is never a scan. Shared folders are the exception, handled with a separate membership table and a fan-out on change, which is the same shape as the notification fan-out problem.

Common misconceptions

"Fixed-size chunks are fine." Any insertion shifts every subsequent boundary, which is exactly the case the requirement names.

"Dedup is free." It is a confirmed-file side channel across users, and it conflicts with client-side encryption.

"Last-writer-wins is acceptable for files." It silently destroys work. Every major product chose keep-both instead.

"The bytes are the hard part." Chunk and file metadata at this scale is the larger engineering problem.

"Refcounting handles chunk deletion." It races with in-flight uploads. Mark-and-sweep with a grace period is the correct mechanism.

Interview delivery note

Split the problem in the first thirty seconds: "There are two systems here. Storage, which is chunks in object storage with metadata in a database and is a solved shape. And sync, which is detecting change, transferring the minimum and reconciling concurrent edits. Sync is the hard part and it's where the requirement actually points."

Answer the stated requirement mechanically: "For the 2 GB file, content-defined chunking. A rolling hash cuts boundaries based on content rather than offset, so inserting a byte shifts only the chunk containing it instead of every subsequent boundary. Five hundred chunks at 4 MB, a small edit changes one or two, so you upload 8 MB instead of 2 GB. And I'd bound the minimum and maximum chunk size, because without a minimum a low-entropy file produces thousands of tiny chunks and the metadata costs more than the data."

Take a clear position on conflicts, because hedging here is a weak answer: "On conflict, keep both, with a conflicted copy. Last-writer-wins silently destroys work someone spent hours on, and that's the failure users never forgive. Dropbox, Drive and OneDrive independently reached the same conclusion. And detection is version vectors rather than timestamps, because a device with a fast clock would otherwise win every conflict silently."

Name where the difficulty really is: "The hard part of this isn't the bytes, it's the metadata: around 875 billion chunk records and 5 trillion file records. And the specific production trap is reference counting, because a chunk's count can hit zero while an upload that will reference it is in flight. Mark-and-sweep with a grace period, not immediate deletion."

Close with the cost decision: "and the biggest single cost lever is erasure coding rather than replication: 1.4x overhead against 3x, at equal or better durability, which at this scale is over five exabytes of difference. The cost is read amplification and expensive repair, so hot chunks keep a cached full copy."

The Staff & Team Lead Interview Reference