Chapter 15 · System Design Fundamentals
Design Google Drive
A file-sync service looks like a remote disk, but the real design lives in what it refuses to move: identical bytes are stored once, unchanged blocks are never re-uploaded, and restoring yesterday's file is a pointer flip, not a byte copy. Get the split between bytes and metadata right and everything else follows.
▶ Open the companion slidesStrip a file-sync service to its spine and there are two stores, not one. Anonymous blocks of bytes live in an object store keyed by their own hash; everything a human calls "my file" — the name, the folder, the version history, who may read it — lives in a metadata database. A file is just an ordered list of block hashes recorded in metadata. Every hard problem in this chapter — dedup, delta sync, versioning, sharing — is a variation on keeping those two stores honest with each other while moving as few bytes as possible.
Alex Xu, System Design Interview (Vol. 1), Chapter 15. Companion deck: slides — jump to any slide with the Slide N chips. Go deeper: Dropbox Engineering, Rewriting the heart of our sync engine.
What a file service owes its users Slide 2
Before naming a single technology, list the user-visible promises. Five behaviours together define the problem, and each one pulls the design in a specific direction — the interesting work is in the non-functional row, exactly as it was for the web crawler.
Upload & download
Any file type, a few KB to multi-GB videos. Transfers must be resumable on flaky networks and never lose bytes mid-flight.
Sync across devices
An edit on the laptop shows up on the phone seconds later. Every client converges to the same view without a manual refresh.
Share with others
Generate a link, invite by email, assign a role. Permissions cascade into nested folders and honour revocation.
Version history
Every save is recoverable. A user rolls back yesterday's accidental delete without ever contacting support.
The non-functionals are where the design is decided: durability (eleven nines — see Chapter 2), eventual consistency across devices, sub-second metadata reads, bandwidth-efficient sync, and encryption at rest. "Store a file, sync it, share it" is almost trivial by comparison.
The moving parts Slide 3
Read the shape before the detail. Clients talk to an API gateway that authenticates and routes. Behind it, a sync service orchestrates uploads and resolves diffs, a metadata DB records files and versions, and a notification service fans changes out to a user's other devices. The bytes themselves detour straight into block storage — an object store — and downloads are served from an edge cache. Metadata and bytes live in different stores so each scales on its own axis.
Cut every file into fixed-size blocks Slide 4
Treating a 4 GB video as one blob is a recipe for timeouts and wasted retries. Slice it into uniform 4 MB blocks and the transfer collapses into many small, parallel, retriable pieces. Each block is then hashed (SHA-256), and the hash — not a filename — becomes its address in the store.
Why blocks win
Parallelism saturates the uplink instead of starving one TCP stream; retriability means one failed block costs one retry, not the whole file; streaming lets a player start on the first blocks that land.
Why 4 MB?
Big enough that per-block overhead (HTTP headers, a metadata row) stays negligible; small enough that a failed retry is cheap. Dropbox picked 4 MB; anything from 1–16 MB works. It is a tunable, not a law.
Hash the block, store it exactly once Slide 5
The same PDF sits in a thousand inboxes; the same npm tarball sits in a million repos. Identical bytes should be stored a single time. Before uploading a block the client hashes it and asks the server "do you already have this hash?" — if yes, it skips the byte transfer entirely and just points the new file at the block that already exists.
Two layers of dedup
Per-user: uploading the same attachment twice costs storage once. Global: across all tenants, popular blocks — templates, shared libraries, identical photos — exist in storage exactly once.
The bookkeeping cost
Each block carries a reference count. When the last file pointing at it is deleted, the count hits zero and a background job can garbage-collect the bytes. Deleting a file never blindly deletes blocks.
Cross-tenant dedup lets one user probe whether the system already stores a given file: upload it, watch whether the bytes actually transferred. Privacy-sensitive deployments deliberately disable global dedup — or dedup only within an encryption boundary — accepting the extra storage to close that side channel.
Only re-upload what actually changed Slide 6
A user edits one paragraph in a 200-page document and hits save. A naive sync re-uploads the whole file; a delta-aware sync re-uploads one block. Same correctness, ~99% less bandwidth. The client re-chunks the local file, compares its block-hash list against the server's, and ships only the hashes the server has never seen — then commits a new file pointer over the resulting block list.
The metadata DB is where the file actually lives Slide 7
Blocks in the object store are anonymous bytes with no name and no owner. The metadata DB is what turns them into a file: it holds the name, the parent folder, the version chain, and the permissions. Four tables carry the model. A file points at its current version; a version is an ordered list of block hashes; permissions tie principals to roles.
| Table | Key columns | What it records |
|---|---|---|
| files | file_id, owner_id, parent_id, name, current_version, is_deleted | The named node in the tree and a pointer to its live version. Soft-delete flag keeps it recoverable. |
| versions | version_id, file_id, block_list, size, created_at | Append-only. Each row is an immutable ordered list of block hashes — the recipe to rebuild that version. |
| blocks | block_hash (PK), size, ref_count, storage_key | Content-addressed. ref_count drives garbage collection; storage_key locates the bytes. |
| permissions | file_id, principal_id, role, granted_at | Who may do what. Role is viewer / commenter / editor / owner. |
Sharding: shard files and versions by owner_id so one user's
whole tree lives on a single shard and a folder listing is one fast local read (the key-value patterns from
Chapter 6). The blocks table is global, so shard it by
block_hash prefix instead — its rows are shared across every tenant.
Block storage: an object store keyed by content Slide 8
The bytes never touch the relational database. They land in an object store — S3, GCS, or an in-house equivalent — where the key is the SHA-256 of the contents, not a path. Content-addressing hands you three properties for free, and tiering keeps the cost sane.
Dedup for free
Two identical blocks map to one key, so a second write is a no-op. The store cannot hold the same bytes twice.
Tamper-evident
Re-hash on read; if the digest no longer matches the key, that replica is corrupt and self-healing replication reads a good one instead.
Cache-friendly
The hash is the ETag. Because a key never refers to different bytes, CDNs and clients cache blocks forever without a staleness worry.
Tiered by heat
Hot blocks on SSD (~ms), warm on HDD (~10 ms), cold on tape/Glacier (minutes). Lifecycle policies demote by last-read; ref-counts drive the eventual delete.
Tell every other device, fast Slide 9
An upload isn't finished when the bytes land — it's finished when the user's phone, tablet, and second laptop all know. The notification service fans the change event out to every subscribed device. But the push is only an optimisation: each client also keeps a monotonic sync cursor and, on reconnect, simply asks "what changed since cursor X?" That cursor, not the push, is what makes sync correct even for a device that was offline.
Immutable blocks, mutable pointers Slide 10
Versioning gets cheap and correct the moment you commit to one rule: blocks never change.
A new version is just a new ordered list of block hashes; older versions keep pointing at their old blocks.
Editing block 3 mints B3′ and leaves B3 untouched, so v1 and v2 coexist
while sharing every block they have in common.
version_id. One row updated. Zero bytes moved.
A rename touches only files.name; a move is just a new parent_id — the version
chain and the bytes are untouched either way. A retention policy (keep 30 days, or the last 100 versions)
drops the oldest version rows, decrementing ref-counts so orphaned blocks become eligible for GC.
When two devices edit the same file Slide 11
Two laptops go offline, both edit budget.xlsx, both reconnect. Detection comes first: every
upload carries the parent_version_id it was derived from. If a client tries to commit on top
of v2 but the server has already advanced to v2′, the server sees the stale parent — that is
the conflict trigger. Without it, both strategies below collapse into "blindly overwrite."
Last-write-wins
Tag each upload with a server-assigned version number; the last to arrive becomes current. The loser's edits aren't lost — version history keeps them — but they stop being the live file. Fine when users expect one canonical "latest" and true simultaneous edits are rare.
Keep-both (fork)
Detect the divergence and, instead of choosing, create budget (conflicted copy from Laptop B).xlsx next to the original. Users reconcile manually — annoying, but nothing silently vanishes. Dropbox's classic default for spreadsheets, code, anything unsafe to auto-merge.
Real-time collaborative editing (Docs, Sheets) is a different problem one layer up: file-level resolution gives way to operation-level merging — every keystroke is an op transformed against concurrent ops (operational transform / CRDTs). The storage system underneath still just stores immutable versions.
Sharing, links, and who may do what Slide 12
Permissions are the subtlest correctness problem here: one bad row leaks private data, and an over-eager cache leaks stale private data. There are two share modes and a smallest-set-that-works role ladder, and a check that runs on every metadata read.
Per-principal
"Bob can edit this folder." A row in permissions tying a user or group to a role. Folder grants cascade down; an explicit grant on a child can widen but never narrow, so no one has a folder yet mysteriously lacks a file inside it.
Link-based (capability URL)
"Anyone with this URL can view." The link embeds an opaque, unguessable token (e.g. 128-bit random) the server looks up. Revoking rotates or invalidates the token — no user list to edit.
effective_acl so this walk stays hotEvery grant change is logged (actor, target, before, after). Token revocation is immediate; a denormalised ACL takes up to its cache TTL — usually seconds — to reflect a revoke, which is acceptable for files not actively under attack.
Six principles Slide 13
Separate bytes from metadata
Anonymous blocks in an object store; names, trees, and ACLs in a database. Each scales on its own axis.
Chunk first, hash always
Fixed-size blocks plus content-addressing turn one hard transfer into many easy ones — and hand you dedup for free.
Never move bytes you can avoid
Dedup skips duplicate writes; delta sync skips unchanged blocks; pointer-flips skip copies entirely.
Make blocks immutable
Cheap versions, safe deletes, forever-cacheable keys, and tamper-evidence all fall out of one rule.
Cursors are correctness, push is speed
Every client converges on reconnect via a monotonic cursor; notifications only make convergence faster.
Decide your conflict policy up front
Last-write-wins is simple but can hide work; keep-both is safer but noisier. Choose deliberately, document loudly.
Active recall
Cover the answers. Say each one out loud before you tap to check.
parent_version_id it derived
from. If the server has already advanced past that parent, the client's base is stale — that is the
trigger for last-write-wins or keep-both.