Design Dropbox

Source: https://www.hack2hire.com/question-bank/questions/system-design/69cdf6feff3ebde766ceea74
Company: Databricks, Tesla, Microsoft, Google
Difficulty: Hard

Problem statement

Sync files across a user's devices and shared folders: upload large files reliably, transfer only what changed, and handle conflicting edits.

Requirements

We are building a Dropbox-style file sync service: a desktop/mobile client keeps a local folder in sync with the cloud and with every other device of the same user, including folders shared with other users. The hard parts are reliable uploads of very large files, moving only changed bytes, and never losing data when two devices edit the same file.

Functional requirements

• Add, edit, rename, move and delete files and folders on any device; changes appear on the user's other devices and on every member of a shared folder.
• Upload files up to 50 GB over flaky links; an interrupted upload resumes where it stopped.
• Transfer only what changed: a 2 GB file with one edited region uploads a few MB, and a file already stored (same content) uploads nothing.
• A device that was offline for days catches up from where it left off, without re-listing everything.
• Concurrent edits to the same file never lose data: one version wins the path, the other is kept as a conflicted copy.
• Version history and restore of deleted files for 30 days (180 on paid plans).
• Device registry: list, rename and unlink devices; unlinking stops sync and revokes the device token.

Out of scope: real-time co-editing (that is Google Docs), full-text search, previews.

Non-functional requirements

• Durability 11 nines for committed content; a committed revision is never lost or corrupted.
• Metadata is strongly consistent per namespace (a user's root or a shared folder): every device sees changes in the same order.
• Sync latency: a small edit reaches other online devices in under 5 s p95.
• Availability 99.95% for metadata; downloads keep working when the commit path is degraded.
• Bandwidth-efficient: dedup and compression on both directions; no full re-upload after a rename or move.

Back-of-the-envelope estimation

• 500M users with data, 100M DAU, 2.5 devices each → ~250M connected devices at peak.
• Storage: 8 GB average per user → 4 EB logical; ~25% saved by block dedup → 3 EB unique; erasure coding at 1.5× → ~4.5 EB raw.
• Commits: 100M DAU × 30 file changes/day = 3B/day ≈ 35K/s average, ~100K/s peak.
• Upload: 3B × ~500 KB of genuinely new bytes after dedup ≈ 1.5 PB/day ≈ 17 GB/s average, ~50 GB/s peak. Downloads run 2–3× that (more devices read than write).
• Metadata: 5,000 files/user × 500M = 2.5T live file entries; with revisions and journal ≈ 1 PB → ~2,000 sharded MySQL primaries at 500 GB each.
• Blocks: 4 MB max block, ~1 MB average (small files dominate) → ~3T blocks; 60 B per index entry ≈ 180 TB of dedup index.
• Notifications: 250M long-poll connections at ~100K per server → ~2,500 notification servers.

API design

All calls carry a device token. Writes carry a client-generated client_op_id so retries are idempotent.

Upload session lifecycle

• POST /v1/upload_sessions {namespace_id, size, block_hashes: ["sha256..."]} → {session_id, expires_at, missing: [3, 7], put_urls: {...}}. The server checks which hashes it already has (within the dedup scope) and only asks for the rest.
• PUT /v1/upload_sessions/{session_id}/blocks/{sha256} body = compressed block → 204. The server recomputes the hash; mismatch → 400 hash_mismatch. Re-sending a stored block is a no-op.
• GET /v1/upload_sessions/{session_id} → {received: [...], missing: [...]} for resume after a crash.

Revision commit and download

• POST /v1/commit {namespace_id, path, file_id?, parent_rev, session_id, block_hashes, size, mtime, client_op_id} → 200 {file_id, rev, journal_id}; 409 {code: "conflict", current_rev, current_block_hashes}; 412 {code: "missing_blocks", missing}; 507 {code: "quota_exceeded"}.
• POST /v1/ops {namespace_id, op: "move" | "delete" | "mkdir", path, to_path?, parent_rev, client_op_id} → {rev, journal_id}. Move is metadata only.
• GET /v1/files/{namespace_id}/{file_id}?rev=42 → {rev, size, blocks: [{hash, size, url}]} with short-lived signed block URLs.
• GET /v1/blocks/{sha256} with Range: bytes=0-1048575 → block bytes. Served from block servers or the CDN.

Sync feed

• GET /v1/delta?cursor=opaque&limit=2000 → {entries: [{journal_id, namespace_id, path, file_id, op, rev, block_hashes, size}], cursor, has_more}; 410 {code: "cursor_reset"} when the cursor is older than journal retention.
• POST /v1/longpoll {cursor} → held up to 60 s → {changes: true} or {changes: false, backoff: 30}. It is a hint only; the data always comes from /delta.

Namespace and device registry

• GET /v1/namespaces → mounted namespaces: [{namespace_id, mount_path, role, journal_head}].
• POST /v1/devices {name, platform} → {device_id, token}; DELETE /v1/devices/{id} unlinks and revokes.

Errors and retries: 429/503 carry Retry-After; clients use exponential backoff with full jitter. Commit retries reuse client_op_id, so a commit that succeeded but whose response was lost returns the original {rev, journal_id}.

Data model

Metadata: sharded MySQL, shard key namespace_id. A commit must append a journal row, compare-and-set the latest row and bump the namespace counter in one transaction, and all of that lives in one namespace. That is the durable SQL boundary; nothing that needs cross-namespace atomicity goes here.

Manifests: KV store keyed by manifest_hash (hash of the ordered block list) → [block_hash, size]. Immutable and content-addressed, so it caches forever. A 1 GB file is 256 × 36 B ≈ 9 KB; single-block files inline the block hash in files_latest and skip the manifest.

Block index: separate sharded KV, key block_hash (hash-prefix sharding) → {size, placement, refcount, state: uploading|live|delete_pending, state_changed_at}. Kept out of the metadata shards because blocks are shared across namespaces.

Upload sessions: KV with TTL → {namespace_id, expected_hashes, received_hashes, expires_at}.

Block storage: an erasure-coded blob store (6+3 Reed-Solomon across zones, or S3) keyed by block_hash. Blocks are written once and never modified.

High-level design

flowchart LR
  C[Desktop or mobile client] --> LB[Load balancer]
  LB --> MS[Metadata service]
  LB --> BS[Block service]
  LB --> NS[Notification service]
  MS --> DB[("Metadata MySQL, sharded by namespace")]
  MS --> MF[Manifest KV]
  BS --> BI[Block index KV]
  BS --> BLOB[Erasure coded blob store]
  C --> CDN[CDN]
  CDN --> BS
  DB --> CDC[Journal tailer]
  CDC --> NS
  CDC --> RC[Refcount updater]
  RC --> BI
  GC[Block GC] --> BI
  GC --> BLOB
  SCR[Scrubber] --> BLOB

1. Create and upload a file. The client splits the file into 4 MB blocks, hashes each with SHA-256, and calls POST /upload_sessions with the hash list. The block service answers with only the missing hashes. The client uploads those with 4–8 parallel streams, each verified on arrival and written to the blob store as state=uploading. It then calls commit with parent_rev=0. The metadata service checks that every block is present, writes the manifest, and in one transaction appends the journal row, inserts files_latest, and bumps next_journal_id.
2. Download by revision. The client gets the manifest for rev, compares it with its local block cache (keyed by hash), and range-GETs only the missing blocks through the CDN. It writes to a temp file, verifies each block hash, then renames the file into place atomically.
3. Catch up after being offline. The client's cursor encodes {namespace_id → last journal_id} for each mount. /delta reads each shard from that journal_id onward, merges pages up to the limit, and returns a new cursor. The client applies each page to its local SQLite state and persists the cursor in the same local transaction. Then it opens a long-poll.
4. Concurrent edits to the same file. Devices A and B both edit rev 7. A commits first and gets rev 8. B's commit with parent_rev=7 fails the compare-and-set and gets 409 with rev 8's block list. B keeps its own bytes, commits them as report (B's conflicted copy 2026-10-12).docx (the blocks are already uploaded, so this costs one metadata call), then downloads rev 8 to the original path.
5. Fan-out. The journal tailer reads each shard's binlog. For each committed namespace it notifies the notification servers holding long-polls for that namespace's mounted users. Separately, it emits manifest add/remove events to the refcount updater.

Deep dives

Content-addressed manifests, refcounts and safe chunk GC. A file revision is just a list of block hashes, so identical blocks are stored once, and rename, move and restore never touch bytes. The danger is GC deleting a block that a commit is about to reference. The rules:

• Refcounts are updated asynchronously from journal events. Each event is idempotent by (manifest_hash, journal_id), so replays do not double-count. A revision still references its blocks until its restore window ends.
• A block whose count reaches 0 moves to delete_pending with a timestamp. GC hard-deletes it only after a 14-day grace period, and only after re-checking refcount = 0 with a CAS on the state.
• The commit path does a CAS from delete_pending or uploading to live for every block it references. If GC won that race, the commit returns 412 missing_blocks and the client re-uploads. Losing a race costs a retry, never data.
• A weekly mark-and-sweep reconciliation over manifests catches refcount drift. It logs discrepancies and never deletes on its own.

Sync cursor semantics, total order and idempotent apply. Order is total within a namespace and undefined across namespaces, and nothing needs more than that. journal_id comes from namespaces.next_journal_id under the row lock inside the commit transaction, so it is gap-free and matches commit order. That serializes commits per namespace at roughly 1–2K/s, which is plenty for one person or one team folder. Each journal entry carries the full target state (path → rev, manifest), not a diff. Applying it twice, or applying an older entry after a newer one, is a no-op for the client: it skips any entry whose rev is not newer than what it has. Mounting a shared folder adds namespace_id → 0 to the cursor. A gap of more than 100K entries returns a snapshot listing of files_latest instead of a journal replay. When the journal is trimmed past the cursor (90-day retention), the server returns 410. The client then re-lists and reconciles by hash, so unchanged files are not downloaded again.

Concurrent commits at the same path.

Edge rules: edit vs delete, the edit wins and the file is resurrected. Rename vs edit compose, because the edit targets file_id rather than the path. Two creates at the same new path give the second one a conflicted copy. Moving a file between namespaces is copy plus delete, and the copy is metadata only because the blocks are shared.

Multipart upload lifecycle and orphan cleanup. A session lives 7 days and is extended on activity, so a 50 GB upload over a slow link (about 12K blocks) survives sleep and reboots. The client persists session_id locally; on restart it calls GET /upload_sessions/{id} and sends only missing. Blocks are verified by hash on arrival, so a corrupt or partial block is rejected and re-sent. Uploaded-but-never-committed blocks sit at state=uploading, refcount=0. When a session expires, a sweeper moves its unreferenced blocks to delete_pending, and normal GC removes them after the grace period. Cross-user dedup leaks information: knowing a hash would prove that a file exists, or even fetch it. So missing is computed only against blocks already in the caller's own namespaces. Global dedup still happens silently at the storage layer after the bytes are received.

Operating at scale.

• Tombstones vs restore window. A delete writes a journal entry and sets files_latest.deleted_at. The row and its blocks stay for 30/180 days so devices that were offline still see the delete and the user can restore. After that a compactor drops the tombstone and the refcounts. Journal retention (90 days) is longer than the free restore window, so most offline devices get the real deletes rather than a reset.
• Hot-user sync storms. A company-wide shared folder can have 50K member devices. The notification service coalesces to one hint per namespace per 2 s, and clients add 0–5 s of jitter before calling /delta. Delta pages are capped at 2,000 entries, and each response carries a backoff the server can raise under load.
• Integrity. Clients hash before upload, the block service re-hashes on write, and clients verify again on download. A scrubber reads every fragment about every 2 weeks (≈ 4.5 EB / 14 days ≈ 3.7 TB/s across the fleet, run at low priority) and rebuilds bad fragments from parity in other zones.
• Index and manifest cost. The ~180 TB block index sits on SSD and is sharded by hash prefix. A Bloom filter in front answers "definitely new" for most fresh blocks without a lookup. Inlining single-block files skips the manifest for the ~70% of files under 4 MB.
• Push vs poll. Long-poll hints are lossy by design: a dropped connection or a missed hint only delays sync, because correctness lives entirely in the cursor plus /delta. Clients also poll /delta every 10 min as a safety net.

Trade-offs

• Fixed 4 MB blocks are simple and cheap to index, but an insert near the start of a file shifts every later block. Content-defined chunking (rolling hash) survives inserts at the cost of variable block sizes and more CPU on mobile.
• Per-namespace serialized journals give a simple total order and cheap cursors, but cap the write rate of one giant shared folder at ~1–2K commits/s.
• Conflicted copies never lose data, but push the merge onto the user and clutter folders when an app autosaves often.
• Async refcounts plus a grace period keep the commit path fast and GC safe, but freed space comes back 2+ weeks late (about 1–2% extra storage).
• Restricting the dedup check to the caller's own namespaces closes the hash-probing leak, but re-uploads popular files that are already stored.
• Hint-only push keeps the notification tier stateless and lossy-tolerant, but adds a round trip (hint, then /delta) to every change.

Interviewer expectations

Mid-level (L4)

• Splits files into blocks, hashes them, and uploads only missing blocks; separates metadata from block storage.
• Defines upload, commit, download and a change feed with a cursor.
• Notices concurrent edits and proposes a version check with conflicted copies.

Senior (L5)

• Per-namespace journal with monotonic ids, an opaque multi-namespace cursor, idempotent apply, and a reset path.
• Resumable upload sessions, hash verification on every hop, and long-poll as a hint rather than the source of truth.
• Sizing that drives choices: sharded SQL for metadata, erasure-coded blob store, CDN for downloads.

Staff (L6+)

• Proves GC safety: the race between commit and delete, the CAS on block state, the grace period, and reconciliation.
• Sets the transactional boundary (namespace) and its cost, and handles cross-namespace moves and shared-folder mounts.
• Raises the dedup privacy leak, sync storms in huge shared folders, scrubbing, and the operating cost of tombstones and the index.