System Design · Lesson 14 of 18
File Storage (Dropbox / Drive)
Chunking, dedupe, delta sync, metadata service and conflict resolution.
- Advanced
- 52 min read
- 6 objectives
Before this lessonLesson 13: Video Streaming (YouTube)
What you will learn
- Size storage, commit traffic and connections for a Dropbox-scale drive
- Split the metadata plane from the block plane and justify the stores
- Implement content-defined chunking and SHA-256 dedupe, and explain their privacy trade-offs
- Design the upload-then-commit protocol with compare-and-set revisions
- Sync devices with journals, cursors, long-poll or WebSocket, and conflicted copies
- Partition metadata by namespace, cache immutable blocks and tier cold storage
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
Design cloud file storage in the style of Dropbox, Google Drive or OneDrive: a user drops a file into a folder on one device and it appears, a few seconds later, on every other device they own and on the devices of everyone they shared it with. Edits made offline on a plane are merged on landing. Deleted files can be restored for 30 days. A 2 GB video that already exists anywhere in the system does not get uploaded a second time.
This prompt looks like "an upload API plus S3". It is not. The interesting parts are all about sync: how a client figures out what changed, how it moves only the changed bytes, how the server gives every device a consistent view of a folder tree, and what happens when two devices change the same file without seeing each other. The storage of bytes is the easy half.
The one sentence to anchor on: a file is a small, strongly consistent metadata record that points at a list of immutable, content-addressed blocks. Almost every good decision in this lesson falls out of that sentence.
Step 1 — Clarify the requirements
Why do people pay for cloud storage at all? Three reasons, and they become the non-functional requirements: availability (my files on any device, anywhere), durability (a dead laptop is not lost work, because copies live in several data centres) and elastic capacity (never think about disk space again). Now pin down scope.
Functional, in scope for v1
- Upload and download files from desktop, mobile and web clients. Files up to 50 GB; resumable uploads.
- A designated sync folder on each desktop that is automatically synchronised across all of a user's devices.
- Offline editing: create, modify, rename and delete while disconnected; reconcile on reconnect.
- Sharing: share a file or folder with other users (viewer / editor), or by link.
- Version history: restore any earlier version for 30 days (180 on paid plans); a trash for deleted files with the same window.
- Conflict handling: two devices edit the same file concurrently → no data is lost.
Explicitly out of scope
Real-time collaborative editing of document contents (that is Google Docs — operational transforms or CRDTs, a different system entirely), full-text search inside files, thumbnails and previews, virus scanning, e-discovery and legal hold, and billing. Name them. The most common confusion in this interview is designing Google Docs when you were asked for Google Drive.
Non-functional
- Scale: 500M registered users, 100M daily active, ~3 devices each, ~200 files per user on average (a long tail of users with 500k files).
- Durability: 11 nines on stored bytes. Losing a user's file is the one unforgivable failure.
- Consistency: metadata operations are ACID — a commit either fully happens or does not; a folder listing never shows half a rename; every device converges on the same tree.
- Latency: a small edit visible on other online devices in under 10 s at p95; folder listing p99 < 200 ms; metadata commit p99 < 500 ms.
- Efficiency: bandwidth matters more than CPU — users are on hotel Wi-Fi and metered mobile. Transfer only what changed.
- Read/write ratio: roughly 1:1, unusual among case studies. Sync means every write on one device becomes a read on two others.
Step 2 — Back-of-the-envelope estimation
users_total = 500_000_000
dau = 100_000_000
devices_per_user = 3
files_per_user = 200
avg_file_kb = 100
SECONDS_PER_DAY = 86_400
# --- Storage: logical vs physical ---
files_total = users_total * files_per_user
logical_pb = files_total * avg_file_kb * 1e3 / 1e15
dedupe_saving = 0.30 # identical attachments, installers, copied folders
replication = 1.5 # erasure coding (e.g. 10+5), not 3x copies
physical_pb = logical_pb * (1 - dedupe_saving) * replication
print(f"files: {files_total/1e9:.0f}B logical: {logical_pb:.0f} PB physical: {physical_pb:.1f} PB")
# --- Write traffic: new or changed files ---
edits_per_dau = 10
commits_s = dau * edits_per_dau / SECONDS_PER_DAY
peak = commits_s * 3
changed_bytes = 60e3 # delta sync: most edits touch one chunk, not the file
ingest_gbps = peak * changed_bytes * 8 / 1e9
print(f"metadata commits: {commits_s:,.0f}/s avg, {peak:,.0f}/s peak")
print(f"block ingest at peak: {ingest_gbps:.0f} Gbit/s")
# --- Chunk metadata rows ---
chunks_per_file = 1.2 # most files are one chunk; a few are huge
chunk_rows = files_total * chunks_per_file
print(f"chunk rows: {chunk_rows/1e9:.0f}B at 100 B/row: {chunk_rows*100/1e12:.0f} TB of index")
# --- Notification connections ---
online_devices = dau * devices_per_user * 0.4 # desktops online at the same time
print(f"open long-poll/websocket connections: {online_devices/1e6:.0f}M"
f" -> ~{online_devices/100_000:,.0f} nodes at 100k conns each")files: 100B logical: 10 PB physical: 10.5 PB metadata commits: 11,574/s avg, 34,722/s peak block ingest at peak: 17 Gbit/s chunk rows: 120B at 100 B/row: 12 TB of index open long-poll/websocket connections: 120M -> ~1,200 nodes at 100k conns each
What the numbers actually decide
- 10 PB is an object-store problem, not a database problem. No relational database holds this; bytes go to S3-style blob storage (or a purpose-built block store like Dropbox's Magic Pocket). Erasure coding at ~1.5x overhead instead of 3 full replicas saves ~15 PB of disk — that is real money and worth saying.
- 35k metadata commits/s at peak is large but not exotic. Too much for one Postgres primary, easy for a sharded MySQL/Postgres fleet. It forces a partitioning key decision (Step 12), not a switch to an eventually consistent store.
- 120 billion chunk rows is ~12 TB of index before replicas. The
blockstable needs its own sharding by hash — it cannot live alongside per-user tables. - 17 Gbit/s of ingest assumes delta sync. Without chunk-level diffs (re-uploading the whole file on every save) multiply by the average file-to-chunk ratio; for a 200 MB PowerPoint saved every few minutes, that is ~50x. Delta sync is not an optimisation here; it is what makes the bandwidth bill survivable.
- 120M open connections for change notifications means a dedicated notification tier of ~1,200 nodes. It must be separate from the metadata service so a deploy of one does not drop the other.
Step 3 — The key decision: split metadata from blocks
Two planes, with opposite characters:
| Metadata plane | Block plane | |
|---|---|---|
| What | Paths, folder tree, revisions, block lists, ACLs, devices, journal | Immutable chunks of file content, keyed by SHA-256 |
| Size | Tens of TB | Tens of PB |
| Access | Small, random, transactional, latency-sensitive | Large, sequential, throughput-bound, retryable |
| Consistency | Strong (ACID, serialised per namespace) | Trivially consistent: a hash never changes meaning |
| Store | Sharded MySQL / Postgres (or Spanner) | S3 / GCS / in-house erasure-coded block store |
| Scales by | Sharding by namespace | Adding disks; placement by hash |
Because blocks are content-addressed and immutable, the block plane never has an update, never has a conflict and never needs a lock. You can cache a block forever, replicate it lazily, and retry an upload blindly — the same bytes always land at the same key. All the hard consistency work is concentrated in the small metadata plane, where a relational database is good at it.
Wrong answers candidates commonly give
- "Store files as BLOBs in the database." A 2 GB row blows up replication, backups and buffer pools. Listing
/Projectscompetes with streaming a video from the same disks. - "Store each file as one S3 object named by its path." A rename becomes a copy of every byte; a one-byte edit re-uploads the whole object; a failed upload of a 20 GB file restarts from zero; and there is no dedupe.
- "Use Cassandra for metadata because it scales." You then have to rebuild atomic multi-row commits (block list + journal + parent folder) and compare-and-set on revisions in application code. The requirement says ACID; take a store that gives it to you and shard it.
Step 4 — API design
Two families, mirroring the two planes. Block endpoints are dumb and idempotent; metadata endpoints carry the logic. Auth is an OAuth bearer token; the gateway resolves it to user_id.
## Block plane — content addressed, idempotent, resumable
POST /api/v1/blocks/check { hashes: ["9f86d0...", "60303a...", ...] }
-> 200 { missing: ["60303a..."] }
# Batch of up to 1,000 hashes. Only the missing ones get uploaded.
# (Scoped per user in the response -- see the dedupe privacy note in Step 8.)
PUT /api/v1/blocks/{sha256} body: raw bytes (<= 4 MiB), Content-Encoding: zstd
-> 201 Created | 200 OK (already had it) | 400 HASH_MISMATCH
# Server recomputes SHA-256 and rejects a body that does not match the URL.
# Retrying the same PUT is always safe: same key, same bytes.
# In practice this returns a pre-signed URL so bytes go straight to the
# object store and never through our app servers.
GET /api/v1/blocks/{sha256} -> 200 bytes (Cache-Control: immutable, 1 year)
-> 403 if no file you can read references it
## Metadata plane — transactional, versioned
POST /api/v1/files/commit
Headers: Idempotency-Key: <uuid>
{ namespace_id, path: "/Projects/plan.docx", parent_rev: 41,
size: 18344211, blocks: ["9f86d0...", "60303a...", ...], mtime, device_id }
-> 200 { file_id, rev: 42, journal_seq: 90817 }
409 { code: "REV_CONFLICT", current_rev: 43 } # someone committed first
412 { code: "BLOCKS_MISSING", need: [...] } # upload them, then retry
403 NO_WRITE_PERMISSION | 507 QUOTA_EXCEEDED
POST /api/v1/files/move { file_id, new_parent_id, new_name, parent_rev }
POST /api/v1/files/delete { file_id, parent_rev } # moves to trash
POST /api/v1/files/restore { file_id, rev } # new rev = old block list
GET /api/v1/files/{file_id}/revisions?cursor=
GET /api/v1/folders/{folder_id}/children?cursor=&limit=500
## Sync — the delta feed every client lives on
GET /api/v1/delta?namespace_id=&cursor=90800&limit=2000
-> 200 { entries: [{ seq, op: "upsert"|"delete", path, file_id, rev,
blocks: [...], size, mtime }],
cursor: 90817, has_more: false }
410 CURSOR_EXPIRED # journal compacted; client must do a full re-list
GET /api/v1/notify?cursors=ns1:90817,ns7:5521 (long-poll, 60 s timeout)
-> 200 { changed: ["ns1"] } # a doorbell only -- then call /delta
-> 200 { changed: [] } # timeout; reconnect immediately
# WebSocket equivalent: WS /api/v1/notify pushes the same tiny message.
## Sharing
POST /api/v1/shares { file_id | folder_id, grantee_email, role: "viewer"|"editor" }
POST /api/v1/links { file_id, access: "anyone_with_link", expires_at?, password? }
DELETE /api/v1/shares/{id}Five API decisions worth defending
- Upload blocks first, commit metadata second. The commit is a single small request that atomically flips the file to a new block list. There is never a moment where metadata points at bytes that do not exist (412 enforces it).
parent_revon every mutation is optimistic concurrency. The server's only conflict rule is "your parent is not my current revision" → 409. Resolution happens on the client (Step 11).- Notify is a doorbell, delta is the data. Pushing full change payloads through 120M sockets duplicates the delta logic and loses messages during reconnects. A cursor-based pull is replayable and exact.
- The cursor is opaque and per namespace. Clients never compute it; the server can change encoding, and a 410 lets it compact old journal entries.
- Block GETs are authorised by reference, not by hash knowledge. Knowing a SHA-256 must not be a capability to download it.
Step 5 — Data model
Metadata lives in sharded MySQL/Postgres, partitioned by namespace_id (a user's root folder, or one shared folder, is a namespace). The global block index is a separate cluster sharded by hash.
-- =========================================================
-- NAMESPACE SHARDS (partition key: namespace_id)
-- =========================================================
namespaces (
namespace_id BIGINT PRIMARY KEY,
kind SMALLINT NOT NULL, -- 1 personal root, 2 shared folder, 3 team
owner_id BIGINT NOT NULL, -- quota is charged here
journal_seq BIGINT NOT NULL, -- last assigned seq; bumped in every commit
created_at TIMESTAMPTZ NOT NULL
);
files ( -- one row per file OR folder (the tree)
namespace_id BIGINT NOT NULL,
file_id BIGINT NOT NULL, -- stable across renames and moves
parent_id BIGINT NULL, -- NULL = namespace root
name TEXT NOT NULL, -- case-folded copy kept for uniqueness
is_dir BOOLEAN NOT NULL,
head_rev INT NOT NULL, -- the compare-and-set target
size BIGINT NOT NULL,
deleted_at TIMESTAMPTZ NULL, -- non-NULL = in trash (soft delete)
PRIMARY KEY (namespace_id, file_id),
UNIQUE (namespace_id, parent_id, name) -- WHERE deleted_at IS NULL
);
-- Tree by parent_id, not by full path string: renaming a folder with 50k
-- descendants is ONE row update, not 50k.
file_revisions ( -- immutable history; restore = new rev
namespace_id BIGINT NOT NULL,
file_id BIGINT NOT NULL,
rev INT NOT NULL,
size BIGINT NOT NULL,
content_hash CHAR(64) NOT NULL, -- hash of the block list: cheap equality
block_list BYTEA NOT NULL, -- packed array of 32-byte SHA-256s
device_id BIGINT NOT NULL, -- who made it (shown in version history)
created_at TIMESTAMPTZ NOT NULL,
PRIMARY KEY (namespace_id, file_id, rev)
);
-- block_list is packed into the row instead of a file_blocks(seq, hash) table:
-- a 4 GB file is ~1,000 hashes = 32 KB, read and written as one unit, and it
-- avoids a billion-row join table.
journal ( -- the ordered change feed per namespace
namespace_id BIGINT NOT NULL,
seq BIGINT NOT NULL, -- gap-free within a namespace
file_id BIGINT NOT NULL,
op SMALLINT NOT NULL, -- upsert | delete | move
rev INT NOT NULL,
PRIMARY KEY (namespace_id, seq)
);
-- /delta is a range scan on this primary key. Compacted after 90 days
-- (clients older than that get 410 and re-list).
acls (
namespace_id BIGINT NOT NULL, -- shares are granted at namespace level
principal_id BIGINT NOT NULL, -- user or group
role SMALLINT NOT NULL, -- 1 viewer, 2 commenter, 3 editor, 4 owner
PRIMARY KEY (namespace_id, principal_id)
);
-- =========================================================
-- USER SHARDS (partition key: user_id)
-- =========================================================
users (user_id PK, email UNIQUE, plan, quota_bytes, used_bytes, root_namespace_id)
devices (user_id, device_id, platform, last_seen_at, PRIMARY KEY (user_id, device_id))
mounts (user_id, namespace_id, mount_path, -- where a shared folder
PRIMARY KEY (user_id, namespace_id)) -- appears in MY tree
device_cursors (device_id, namespace_id, cursor) -- advisory; the client owns it
-- =========================================================
-- BLOCK INDEX (separate cluster, partition key: hash)
-- =========================================================
blocks (
hash CHAR(64) PRIMARY KEY, -- SHA-256 of the plaintext chunk
size INT NOT NULL,
storage_key TEXT NOT NULL, -- where the bytes live (bucket/extent)
tier SMALLINT NOT NULL, -- 1 hot, 2 warm, 3 cold
ref_count BIGINT NOT NULL, -- revisions pointing at it (for GC)
created_at TIMESTAMPTZ NOT NULL
);
-- =========================================================
-- CLIENT (SQLite on every device -- the "internal metadata DB")
-- =========================================================
local_files (path PK, file_id, rev, size, mtime, inode, block_list)
local_blocks (hash PK, offset_in_cache) -- chunk cache for fast re-assembly
pending_ops (id PK, op, path, parent_rev, state) -- queued while offline
cursors (namespace_id PK, cursor)Four modelling decisions to explain
- Namespace, not user, is the unit of consistency. A shared folder is touched by many users, so it cannot live on one user's shard. Making it its own namespace means every commit touches exactly one shard, and the journal for that folder is a single ordered sequence all members read.
- Folders are rows with
parent_id, not path prefixes. Moves and renames are O(1). The cost is that resolving a path walks the tree — cached on the client, which already has the whole tree in SQLite. head_revis the lock.UPDATE files SET head_rev = 42 WHERE file_id = ? AND head_rev = 41— one row affected means you won; zero means 409.- The client keeps its own metadata database. It is what makes offline editing possible, what lets the client answer "what changed?" without a round trip, and what it diffs incoming deltas against.
Step 6 — High-level design
SQLite")] end CH -->|PUT blocks| LB1[Load balancer] IX -->|commit, delta| LB2[Load balancer] IX -.->|long-poll / WS| NS[Notification service] LB1 --> BLK[Block service] BLK --> BC[(Block cache
LRU)] BLK --> OBJ[("Object store
hot tier, erasure coded")] OBJ -->|lifecycle| COLD[(Cold tier)] BLK --> BIDX[(Block index
sharded by hash)] LB2 --> META[Metadata / sync service] META --> MC[(Metadata cache)] META --> MDB[("Metadata DB
sharded by namespace")] META --> RQ[[Request queue]] RQ --> SW[Sync workers] SW --> MDB MDB -->|journal CDC| BUS[[Change log / Kafka]] BUS --> NS BUS --> RESPQ[[Per-device response queues]] RESPQ --> NS BUS --> GC[Block GC + tiering jobs]
Bytes and metadata take different paths through different load balancers to different stores. Commits land in the namespace shard; the journal is tailed into a change log that rings the notification service's doorbell for every subscribed device.
What each component owns
- Client — four parts. The Watcher subscribes to OS file events (FSEvents, inotify, ReadDirectoryChangesW) and to remote change notifications. The Chunker splits files into blocks, hashes them, and reassembles downloaded blocks into files. The Indexer turns watcher events into pending operations, diffs block lists, drives upload-then-commit, and applies remote deltas. The internal metadata DB (SQLite) records every file, revision and block it knows about.
- Load balancers — two pools, one in front of block servers (long-lived, bandwidth-heavy connections) and one in front of metadata servers (short RPCs). Start with round robin; move to least-outstanding-requests once uneven request cost makes some servers slow (Step 12).
- Block service — stateless. Validates hashes, answers
check, issues pre-signed upload/download URLs, encrypts, and records blocks in the block index. - Metadata / sync service — the brain. Validates permissions and quota, runs the commit transaction, serves
/deltafrom the journal, handles moves, trash and restore. - Request queue and sync workers — heavy or bulk operations (moving a 200k-file folder, restoring a whole namespace, mobile photo backups arriving in bursts) go through a durable queue so workers absorb spikes and clients get a 202 with a job id instead of a timeout.
- Per-device response queues — every subscribed device has a logical queue of "namespace X changed" events. An offline device's queue keeps accumulating; when it reconnects it drains the queue, then pulls
/delta. Because the cursor is authoritative, these queues can be lossy and coalesced — one pending "ns1 changed" is as good as fifty. - Notification service — holds 120M long-poll or WebSocket connections, maps namespace → subscribed connections, and sends doorbells.
- Object store and cold tier — durable bytes. Lifecycle jobs move untouched blocks to cheaper storage.
Step 7 — Inside the client
The client is half of this system, and interviewers often probe it. Walk through what happens between the user pressing save and the first network packet.
- Watcher fires. The OS reports
modified: ~/Dropbox/plan.docx. Editors often write a temp file and rename it over the original, producing three or four events in 50 ms, so the watcher debounces (wait ~1–2 s of quiet) and coalesces events per path. - Indexer checks whether anything really changed. Compare size + mtime + inode against
local_files. Same? Skip. Different? Hand to the chunker. This cheap check is what lets a client with 500k files start up without re-hashing 200 GB. - Chunker produces a new block list. Hash each chunk; compare against the previous revision's block list; the difference is the set of candidate uploads.
- Indexer queues a pending op in SQLite (
pending_ops) with theparent_revit last saw. If the machine is offline, it stays there. The user sees a "syncing" badge. - Upload, then commit (Step 9). On success, record the new rev and advance the local state.
Client behaviours worth naming
- Exponential backoff with jitter on every retry — 1 s, 2 s, 4 s ... capped at a few minutes, randomised ±50%. After a regional blip, 300M devices reconnecting in lock-step is a self-inflicted DDoS; jitter spreads them out. Honour
Retry-Afterwhen the server sends it. - Bandwidth throttling — cap upload at a fraction of the link so a sync does not ruin the user's video call.
- Mobile syncs on demand. Phones do not mirror the whole tree; they fetch metadata, show placeholders, download a file when opened, and upload camera photos only on Wi-Fi and charging. Desktop "files on demand" mode does the same with OS placeholder files (smart sync).
- Ignore rules —
.DS_Store,~$lockfiles,node_modulesif the user opts in. Syncing editor lock files between devices creates phantom conflicts.
Step 8 — Chunking, dedupe and delta sync
Why split files at all? Four wins: a failed upload retries one 4 MB chunk rather than the whole 20 GB; chunks upload in parallel; an edit re-sends only the chunks that changed; and identical chunks are stored once. The question is where to cut.
Fixed-size chunking and why it breaks
Cutting at every 4 MiB offset is simple and works well for files edited in place (databases, VM images). But insert one byte at the top of a text file and every boundary after it shifts by one; every chunk's hash changes; the client re-uploads the whole file. This is the boundary-shift problem.
Content-defined chunking (CDC)
Instead of cutting at fixed offsets, slide a rolling hash over the bytes and cut wherever the hash of the last few dozen bytes matches a pattern (say, its top 10 bits are zero, giving an average chunk of 210 bytes). Because a boundary depends only on nearby content, an insertion changes the chunk it lands in, and the next boundary re-synchronises. Min and max sizes stop pathological inputs (a file of all zeros) from producing one giant or a million tiny chunks. The runnable demo below uses the Gear hash (the one used by FastCDC) at toy sizes so it runs instantly.
import hashlib, random
rng = random.Random(42)
GEAR = [rng.getrandbits(64) for _ in range(256)] # one random 64-bit value per byte
MASK64 = (1 << 64) - 1
def fixed_chunks(data: bytes, size: int) -> list[bytes]:
return [data[i:i + size] for i in range(0, len(data), size)]
def cdc_chunks(data: bytes, avg: int = 1024, min_size: int = 256,
max_size: int = 4096) -> list[bytes]:
"""Gear rolling hash. A boundary is declared where the hash of the last
~64 bytes has its top bits all zero, so boundaries depend on CONTENT,
not on absolute offsets. avg must be a power of two."""
bits = avg.bit_length() - 1
mask = ((1 << bits) - 1) << (64 - bits) # test the high bits
chunks, start, h = [], 0, 0
for i, b in enumerate(data):
h = ((h << 1) + GEAR[b]) & MASK64 # old bytes shift out after 64 steps
length = i - start + 1
if length < min_size:
continue
if (h & mask) == 0 or length >= max_size:
chunks.append(data[start:i + 1])
start, h = i + 1, 0
if start < len(data):
chunks.append(data[start:])
return chunks
def sha(c: bytes) -> str:
return hashlib.sha256(c).hexdigest()
def diff(old: list[bytes], new: list[bytes]) -> tuple[int, int]:
known = {sha(c) for c in old} # what the server already has
fresh = [c for c in new if sha(c) not in known]
return len(fresh), sum(len(c) for c in fresh)
doc = random.Random(7).randbytes(64 * 1024) # a 64 KiB "file"
edited = doc[:5000] + b"INSERTED!!" + doc[5000:] # user types 10 bytes near the top
for name, split in (("fixed 1 KiB", lambda d: fixed_chunks(d, 1024)),
("content-defined", cdc_chunks)):
before, after = split(doc), split(edited)
n, nbytes = diff(before, after)
print(f"{name:16} chunks {len(before):3} -> {len(after):3} "
f"new chunks to upload: {n:3} bytes: {nbytes:6,}")fixed 1 KiB chunks 64 -> 65 new chunks to upload: 61 bytes: 61,450 content-defined chunks 60 -> 60 new chunks to upload: 1 bytes: 2,148
Same 10-byte edit, same file. Fixed-size chunking re-uploads 61 of 64 chunks — effectively the whole file — because every boundary after byte 5,000 moved. CDC re-uploads one chunk, 2 KB. At production sizes (average 4 MiB, min 1 MiB, max 16 MiB) the ratio is the same: one chunk instead of the file.
Picking the chunk size
| Average chunk | Good for | Cost |
|---|---|---|
| 64 KB | Fine-grained dedupe and small deltas | 60x more block-index rows and PUT requests; per-request overhead dominates |
| 4 MB | The usual answer: a request per chunk is cheap relative to its bytes; one retry is cheap | A tiny edit still re-sends up to 4 MB (fixed by in-chunk deltas below) |
| 64 MB | Huge sequential media files | Poor dedupe, expensive retries on flaky links, large client memory |
The inputs to the decision are the object store's per-request cost and IOPS, typical client bandwidth, and the file-size distribution. Most files are smaller than one chunk anyway, so for them the chunk is the file.
Deduplication with SHA-256
Each chunk's identity is its SHA-256. Before uploading, the client sends the list of hashes; the server replies with the ones it lacks. This is inline (source-side) dedupe: duplicate bytes never cross the network.
- Inline dedupe — hash on the client, check before upload. Saves bandwidth and storage immediately. Costs a round trip and a block-index lookup on the write path, and the index must be highly available because uploads depend on it.
- Post-process dedupe — accept every upload, then a background job finds identical blocks and collapses them. The write path is simpler and never waits on the index, but you pay to transfer and temporarily store the duplicates. Useful as a second pass for data that arrives through paths that cannot hash first (web uploads, API imports).
- Scope matters. Per-user dedupe (your second copy of a video) is safe and captures most savings. Cross-user dedupe saves more but leaks information: if
blocks/checktells me a hash is already present, I can confirm whether anyone has stored a specific document ("confirmation of file" attack), and upload timing reveals it even if the response does not. Common mitigation: dedupe globally on the server side for storage, but always make the client upload the bytes the first time it references a hash, so the network behaviour reveals nothing. - Is SHA-256 collision safe? Yes in practice — 2128 work for a birthday collision. Do not use MD5 or SHA-1; SHA-1 collisions are demonstrated, and a crafted collision would let one user's block overwrite another's content.
- Encryption and dedupe interact. Encrypting each chunk with a random key destroys dedupe. Systems either encrypt with a key derived from the chunk's hash (convergent encryption, keeps dedupe, same privacy caveat) or encrypt at the storage layer with service-managed keys after dedupe.
Delta sync inside a chunk
CDC shrinks an edit to one changed chunk. For large chunks you can go further with an rsync-style delta: the client that has the old chunk and the new chunk computes a binary diff (copy ranges from old + literal new bytes) and uploads only that, and the server reconstructs the new chunk. It only works when the server side knows the old chunk, so it is used for re-uploads of your own file, not for first uploads. Add zstd compression on every block transfer — text and office files compress 3–5x.
Step 9 — Upload and commit, end to end
Client A saves a file that is shared with a folder that Client B and Client C also sync. C is offline.
Bytes first, then one atomic metadata commit, then fan-out by doorbell. Every receiver pulls from its own cursor, so online and offline devices use exactly the same path.
The order of operations, and why
- Check hashes before uploading. This is where dedupe pays off: for a copied folder, nothing uploads at all.
- Upload blocks directly to the object store. Pre-signed URLs keep 17 Gbit/s off the app servers. Blocks are uploaded in parallel (4–8 at a time) and each is individually retryable, which is resumable upload for free.
- The server verifies the hash of what arrived. A client bug or a malicious client must not be able to store bytes under the wrong key — that would corrupt every file that dedupes onto it.
- Commit only after every block exists. The commit transaction checks the block index; a missing block means 412, not a dangling pointer. Blocks uploaded but never committed (the laptop lid closed) are orphans, cleaned up by GC after 24–48 h.
- One transaction per commit: CAS on
head_rev, insert revision, bumpnamespace.journal_seq, insert journal row, adjust quota. All on one shard because they sharenamespace_id. This is the ACID requirement, satisfied without distributed transactions. - Notify after commit, from the log. Tailing the journal (CDC or an outbox) means a notification is sent if and only if the commit is durable. Notifying from the request handler would lose events when the process dies between commit and send.
- Receivers write downloads to a temp file and rename atomically. A half-downloaded file must never appear in the user's folder, and the watcher must recognise the rename as its own write, not a new local edit to upload back (an echo loop).
Step 10 — Keeping every device in sync
How does a client learn something changed?
| Approach | Latency | Cost at 120M devices | Verdict |
|---|---|---|---|
Poll /delta every 30 s | Up to 30 s | 4M req/s, ~99% returning "nothing" | Wasteful; fine as a fallback only |
| HTTP long-poll | ~1 s | 120M held requests; each returns only on change or 60 s timeout | Dropbox's classic answer; works through every proxy |
| WebSocket | <1 s | 120M sockets, tiny heartbeats | Best for desktop and web; needs sticky routing |
| Mobile push (APNs/FCM) | Seconds, best-effort | Free to hold; rate-limited by the platform | Only way to wake a backgrounded phone |
With long-polling, the client asks "anything new after cursor X?" and the server simply does not answer until something changes or 60 seconds pass. The moment it answers, the client calls /delta and re-issues the poll. Either way, the notification carries no file data — just "namespace ns1 moved past your cursor".
The journal and cursors
Each namespace has a gap-free sequence of changes. A device stores, per namespace, the last seq it applied. Sync is then trivially correct: "give me everything after 90816". It survives reconnects, missed notifications, crashed notification nodes and a laptop that was in a drawer for a month. The only special case is a cursor older than the journal's retention, which returns 410 and forces a full listing and local reconciliation.
The runnable model below captures the core rules: commits are compare-and-set on the revision, commits refuse to reference blocks that were never uploaded, and a reconnecting device replays the journal from its cursor. Note that the server never merges anything — conflict resolution is the client's job.
from dataclasses import dataclass, field
@dataclass
class FileEntry:
path: str
rev: int
blocks: list[str]
@dataclass
class Namespace:
"""One workspace (a user's root or one shared folder). Commits to it are
serialised, so it owns a single, gap-free, increasing journal."""
files: dict[str, FileEntry] = field(default_factory=dict)
journal: list[tuple[int, str, int]] = field(default_factory=list) # (seq, path, rev)
blocks: set[str] = field(default_factory=set) # hashes the block store holds
def commit(self, path: str, parent_rev: int, hashes: list[str]) -> dict:
need = [h for h in hashes if h not in self.blocks]
if need: # never point at bytes we lack
return {"status": 412, "need": need}
cur = self.files.get(path)
cur_rev = cur.rev if cur else 0
if cur_rev != parent_rev: # compare-and-set on the revision
return {"status": 409, "current_rev": cur_rev}
self.files[path] = FileEntry(path, cur_rev + 1, hashes)
self.journal.append((len(self.journal) + 1, path, cur_rev + 1))
return {"status": 200, "rev": cur_rev + 1, "seq": len(self.journal)}
def changes_since(self, cursor: int) -> tuple[list, int]:
return self.journal[cursor:], len(self.journal)
def client_commit(ns: Namespace, path: str, parent_rev: int,
hashes: list[str], device: str) -> dict:
"""The CLIENT resolves conflicts: it never overwrites, it forks a copy."""
r = ns.commit(path, parent_rev, hashes)
if r["status"] == 409:
base, _, ext = path.rpartition(".")
path = f"{base} ({device}'s conflicted copy).{ext}"
r = ns.commit(path, 0, hashes) # same blocks: zero re-upload
return {"path": path, **r}
ns = Namespace()
ns.blocks |= {"h1", "h2", "h3", "h4"} # already PUT to block storage
print(client_commit(ns, "plan.docx", 0, ["h1", "h2"], "laptop"))
# Laptop and phone both went offline at rev 1 and edited the same file.
print(client_commit(ns, "plan.docx", 1, ["h1", "h3"], "laptop")) # first wins
print(client_commit(ns, "plan.docx", 1, ["h1", "h4"], "phone")) # stale parent
print(client_commit(ns, "notes.txt", 0, ["h9"], "phone")) # upload not done
# A tablet reconnects with the cursor it saved last time (seq 1).
changes, cursor = ns.changes_since(1)
print("tablet pulls:", changes, "-> new cursor", cursor){'path': 'plan.docx', 'status': 200, 'rev': 1, 'seq': 1}
{'path': 'plan.docx', 'status': 200, 'rev': 2, 'seq': 2}
{'path': "plan (phone's conflicted copy).docx", 'status': 200, 'rev': 1, 'seq': 3}
{'path': 'notes.txt', 'status': 412, 'need': ['h9']}
tablet pulls: [(2, 'plan.docx', 2), (3, "plan (phone's conflicted copy).docx", 1)] -> new cursor 3
The phone's edit is not lost and not merged: it becomes a sibling file. The tablet, which saw neither device, pulls both entries from one cursor and ends up identical to the server.
Step 11 — Conflicts, versions, trash, sharing and security
Conflict handling
A conflict is two commits with the same parent_rev. The first wins the CAS. The loser's client receives 409 and — rather than overwriting or attempting a merge of arbitrary binary formats — renames its version to plan (Amar's MacBook conflicted copy 2026-09-23).docx, commits that as a new file (zero bytes to re-upload, the blocks are already there), and then downloads the winner into the original path. The user resolves it with the application that understands the format. It is deliberately boring: no data loss, no clever merge that is wrong 1% of the time.
- Why not last-writer-wins? Wall clocks on devices disagree by minutes, and "last" silently discards a day of offline work. That is data loss dressed as a policy.
- Why not merge? A drive stores opaque bytes. Merging a .psd or a .xlsx is not something a sync engine can do safely. Collaborative merge belongs to editors that own the format (Google Docs, Figma).
- Other conflicts: edit vs delete (keep the edit — restoring is safer than losing), rename vs rename of the same folder (first wins, second becomes a move of the loser's children), and two new files with the same name in the same folder (the unique index rejects the second; client suffixes "(1)").
Versioning and trash
- Every commit creates a
file_revisionsrow. Because blocks are shared and immutable, a new version of a 1 GB file whose edit touched one chunk costs 4 MB of storage, not 1 GB. - Restore is just a new commit whose block list equals an old revision's. History stays linear and the restore itself is undoable.
- Delete sets
deleted_atand writes a journaldeleteentry; devices remove the local copy. Trash is a filtered view. A retention job after 30 days deletes the revision rows and decrementsref_counton their blocks. - Block garbage collection never deletes a block synchronously. Reference counts drift under crashes and retries, so a periodic mark-and-sweep (walk live revisions, mark referenced hashes, sweep unmarked blocks older than a grace period) is the safety net. A block that is deleted while a commit referencing it is in flight is the classic GC race; the grace period plus a re-check in the commit transaction closes it.
Sharing and permissions
- Sharing a folder converts it into its own namespace (if it is not one already) and adds an
aclsrow per grantee. Each grantee gets amountsrow placing it in their tree. Moving a folder between namespaces is therefore a re-home of every row — a background job, not a rename. - Roles are checked in the metadata service on every commit and delta; the block service authorises GETs by confirming the user can read some revision that references the hash (cached per session).
- Links are unguessable 128-bit tokens mapped to
(file_id, role, expires_at, password_hash); revocation deletes the row. Never encode permissions in a guessable URL. - Revoking access removes the ACL row and pushes a delta that tells the grantee's devices to delete their local copy. Be honest: bytes already downloaded to someone's laptop cannot be recalled.
Security
- TLS for every connection; pre-signed block URLs expire within minutes.
- Encryption at rest with per-block data keys wrapped by a KMS key; rotating the master key rewraps keys, not petabytes.
- Audit log of shares, link creation and downloads for business accounts.
- Per-user rate limits on
blocks/checkto slow hash-probing.
Step 12 — Scaling each layer
Metadata partitioning
Walk the options, because the interviewer wants to see you reject the weak ones for concrete reasons:
- Vertical partitioning (users tables on one cluster, files on another). A reasonable first step, but the files tables alone hold hundreds of billions of rows, so it only delays the problem, and any query joining users to files is now cross-cluster.
- Range partitioning by path (A–C on shard 1 ...). Predictable but badly skewed — far more paths start with
/Photosthan/Q— and a rename can move a file between shards. - Hash partitioning by
file_id. Even distribution, but a folder listing or a namespace's journal scatters over every shard, and a commit touching a file and its parent folder becomes a distributed transaction. - Hash partitioning by
namespace_id— the answer. Everything a commit touches is co-located, so commits are single-shard ACID transactions and/deltais one range scan. Map namespaces to logical shards through a directory (or consistent hashing over thousands of virtual shards) so a namespace can be moved without rehashing everything.
The catch is hot namespaces: a 50,000-person company's shared drive can produce thousands of commits per second into one namespace. Mitigations: give very large namespaces a dedicated shard; split big team spaces into sub-namespaces per top-level folder; and batch journal sequence allocation. The block index is sharded separately by hash, which is naturally uniform.
Caching
- Block cache in front of the object store for hot blocks — a file just shared with a 1,000-person team is downloaded 1,000 times in an hour. Blocks are immutable, so there is no invalidation at all; LRU eviction is the only policy decision. A 256 GB cache node holds ~64k 4 MB blocks; size the fleet from the measured hot set, not total data. A CDN in front of shared-link downloads does the same job at the edge.
- Metadata cache for folder listings, ACLs and namespace-to-shard mappings. Unlike blocks this is mutable: key it by
(namespace_id, journal_seq)or invalidate on commit, and never serve commits' CAS checks from cache. - The client is the biggest cache. Each device's SQLite and local block cache means most reads never reach the server.
Load balancing
Round robin is fine to start: stateless servers, and a health check removes dead ones. It breaks down when requests have wildly different costs — a 4 MB PUT and a 200-byte hash check look the same to it — so one server ends up with all the slow uploads. Move the block pool to least-outstanding-requests or load-reporting balancing. The notification tier needs sticky, connection-aware balancing and a slow drain on deploy.
Block storage and cold tiering
Access to files decays fast: most blocks are read heavily in their first week and rarely after 90 days. Track last access per block (sampled, not on every read) and move cold blocks to cheaper tiers — S3 Standard to Infrequent Access to Glacier-class, or in-house from SSD-fronted to dense HDD with wider erasure codes. Keep the metadata hot always, so listings are fast even when content is cold; the first open of an archived file may take seconds, and the client shows progress. Tiering cuts storage cost by 50–70% on a 10 PB footprint.
Step 13 — Consistency, decided per feature
| Data | Guarantee | Why |
|---|---|---|
| File commit (block list + rev) | Strong, serialisable per namespace | Atomic flip; CAS on head_rev is the conflict detector |
| Folder tree (moves, renames) | Strong per namespace | A move must never duplicate or lose a subtree |
| Journal order | Strong, gap-free per namespace | Cursors are only correct if seq never skips or reorders |
| Blocks | Immutable, so trivially consistent | Content-addressed: a key's bytes can never change |
| Other devices' view | Eventual, seconds | Each device converges by pulling its cursor |
| ACL revocation | Strong on the server, eventual on devices | Server checks every request; already-synced copies are gone only after the device pulls |
| Quota usage | Strong-ish (in the commit TX), rolled up across namespaces async | Slight overshoot is acceptable; a lost upload is not |
| Block ref counts | Eventual, repaired by mark-and-sweep | Never trust a counter alone to delete user data |
Step 14 — Failure modes
| What fails | What the user sees | Mechanism |
|---|---|---|
| Upload interrupted mid-file | Sync resumes where it stopped | Chunk-level retries; blocks/check skips chunks already uploaded |
| Blocks uploaded, commit never sent | Nothing | Orphan blocks unreferenced; GC removes after grace period |
| Commit response lost, client retries | Nothing | Idempotency-Key returns the stored result instead of a spurious 409 |
| Two devices edit offline | A "conflicted copy" file | CAS on head_rev; loser forks |
| Notification node dies | Changes arrive after reconnect (seconds) | Clients reconnect with jitter; cursors make missed doorbells harmless |
| Metadata shard primary fails | Commits for that shard's namespaces pause ~30 s | Semi-sync replica promoted; clients back off and retry. Never accept commits on an async replica — you would fork the journal |
| Object store region impaired | Downloads slower; uploads queue locally | Cross-region replicated blocks; client keeps pending ops in SQLite |
| Corrupt block on disk | Nothing | Hash verified on read; erasure coding rebuilds; background scrubbing |
| Client bug deletes 100k local files | Files vanish everywhere, then come back | Mass-delete detection prompts before syncing; 30-day trash plus namespace-wide "rewind to time T" |
| Ransomware encrypts the sync folder | Garbage files everywhere | Versioning is the backup: detect entropy spike, offer bulk restore to pre-attack revisions |
| Echo loop (download triggers re-upload) | Endless "syncing" | Client records its own writes in SQLite and ignores the watcher event |
| Journal cursor too old | Longer first sync | 410 → full listing, reconcile by hash against local files |
Step 15 — Observability
- Sync SLIs: commit-to-visible latency on another device (measure with canary accounts that write on one device and watch on another), pending-ops age on clients (reported in telemetry), conflict rate per million commits.
- Efficiency: dedupe ratio, bytes uploaded vs bytes changed (delta effectiveness), cache hit rate for blocks and listings.
- Correctness: hash mismatches on PUT and on read, orphan block volume, ref-count repairs by the sweeper, and a nightly job sampling files end to end (metadata → blocks → bytes → hash).
- Infrastructure: per-shard commit p99 and replication lag, notification connection count and reconnect storms, object-store error rates by tier.
The trade-off summary — how to close
- Metadata and blocks are separate planes. Strong consistency is paid for only on the small plane; the huge plane is immutable and needs none.
- Relational, sharded by namespace, not NoSQL. Single-shard ACID commits beat reimplementing transactions. The price is hot namespaces, handled by dedicated shards.
- Content-defined 4 MB chunks with SHA-256. Edits cost one chunk, retries are cheap, dedupe is automatic. The price is a 120-billion-row block index and client CPU for hashing.
- Inline dedupe, scoped to avoid leaking existence. Saves bandwidth now; post-process catches the rest.
- Doorbell plus cursor, not pushed payloads. A missed notification costs seconds, never correctness.
- Conflicted copies, not merges or last-writer-wins. Ugly but lossless.
- Versions are almost free because blocks are shared; cold tiering keeps the old ones cheap.
- What I would build first: fixed 4 MB chunks, one Postgres, S3, polling every 30 s. Then CDC, long-poll, and namespace sharding as the numbers demand.
// Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
