blocks of up to 4 MB, hashed
Dropbox has described splitting files into blocks of up to 4 MB, identified by a SHA-256 hash, so that a client uploads only the blocks the server does not already have and identical blocks are stored once.
Design Interviews · lesson 8 of 15 · about 30 min
Design file storage like Google Drive
A file-sync service end to end: how content and metadata are stored, how a small edit becomes a small upload, how identical files are stored once, what happens when two offline devices disagree, how devices learn about changes, and why sharing a big folder must not copy permissions per file. Tap any for a plain-language card.
0 / 9 sections done
Two stores, not one
Billions of files, most of them small and a few enormous. The names and folders are tiny; the contents are huge. They should not live together.
The sizes differ by orders of magnitude, and so do the access patterns: metadata is small but hot and needs strong consistency; blocks are large and mostly cold. Size both.
500 million users with 200 files each of 2 MB is 100 billion files, 200 PB of content (600 PB with 3 replicas) and about 50 TB of metadata at 500 bytes per file.
Files100B
Content, one copy200 PB
Content stored (3 copies)600 PB
Metadata50 TB
Content to metadata4,000 : 1
500 million users with 200 files of 2 MB are 100B files: 200 PB of content (600 PB with 3 copies) but only 50 TB of metadata. The metadata is 4,000× smaller and gets the strongly consistent database; the content goes to cheap object storage.
Arithmetic. Content is deduplicated and compressed in practice, so real storage is lower; version history raises both numbers.
Fix one typo in a 20 MB document
Do you upload 20 MB, or 20 bytes? The answer decides your bandwidth bill, your battery, and how fast sync feels.
The numbers below come from really chunking a 2 MB pseudo-random file both ways, applying the edit you choose, and measuring how many of the new file's chunks already existed. That share is then applied to a day of sync traffic across all users. The same trick gives cross-user deduplication: identical blocks are stored once.
Insert one byte near the start of a 2 MB file with 64 KB average blocks: 0% of fixed blocks survive, 96% of content-defined blocks do. For 100 million users editing 5 files of 20 MB a day, uploading whole files is 10 PB; with content-defined chunks it is about 0.4 PB.
Blocks unchanged: fixed / content-defined0% / 96%
Daily upload, whole files10 PB
Daily upload, content-defined0.4 PB
After "inserting a byte at the start", 0% of fixed 64 KB blocks and 96% of content-defined blocks are unchanged. A day of 100 million users editing 5 files of 20 MB uploads 10 PB as whole files, 10 PB with fixed blocks and 0.4 PB with content-defined blocks.
Real chunking of 2 MB of seeded pseudo-random data (Gear rolling hash for content-defined chunking). Real documents compress and have structure, so results vary.
Everybody has the same PDF
The same lecture slides, the same installer, the same viral video clip: a million different people upload the same bytes.
There is a subtle privacy cost: if uploads are skipped when the server already has the content, an attacker can tell whether anyone has stored a specific file by seeing whether the upload was instant. Systems defend by deduplicating only within an account or organisation, or by adding checks. Below, uploads are drawn from a catalogue of distinct files with popularity skew; see how much is actually stored.
200,000 uploads drawn from 50,000 distinct files with Zipf skew 1.0 store only 28,800 unique ones: an 86% saving.
Uploads200K
Unique files stored28.8K
Storage saved by deduplication86%
Storage without / with deduplication1 / 0 TB
200K uploads drawn from 50K distinct files at skew 1.0 leave 28.8K unique files: 86% of the data is stored once and referenced many times (0 TB instead of 1 TB).
Seeded simulation: each upload is a draw from a Zipf-popular catalogue; a repeat is a deduplicated upload. Cross-user deduplication has a privacy side channel (instant uploads reveal that someone has the file).
Your laptop and your phone disagree
On the plane you edit the file on your laptop. Your phone, offline in your pocket, also edits it. Both reconnect. Whose version wins?
For mergeable data (text, collaborative documents) or operational transformation can combine edits automatically, which is why real-time editors rarely conflict. For opaque binary files there is no merge, so a conflicted copy is the only honest answer. How often this happens depends on how long devices stay out of sync. Try it.
Two devices each editing a file twice a day and syncing every 8 hours on average conflict about once in four edits; last-writer-wins would silently destroy about 47% of all edits, a conflicted copy loses none.
Edits made in 60 days235
Sync conflicts to resolve63
Conflicts per edit27%
Over 60 days the two devices made 235 edits, syncing about every 8 hours: 63 syncs conflicted. Last-writer-wins would have lost 47% of the edits without telling anyone; saving a conflicted copy loses none.
Seeded simulation with Poisson edits and sync times. A push conflicts when the server version moved since the device's last sync; under last-writer-wins the previously pushed version's edits are overwritten.
“Anything new?” — “No.”
A hundred million apps ask the server every 30 seconds whether any file changed. Almost always the answer is no.
Cursors make the exchange reliable: if a notification is lost or the client was offline, the next request with its old cursor returns everything it missed. The notification is only a hint, never the data. Compare the request load of polling with the real number of changes.
100 million clients polling every 30 seconds is 3.3 million requests a second, of which only about 5,800 find a change: 99.8% wasted. A push channel sends only the useful messages.
Poll requests per second3.33M
Requests that actually find a change5.79K
Wasted requests99.8%
Worst-case delay before a change is seen30 s
100 million clients polling every 30 s send 3.33M requests a second; only 5.79K a second find anything, so 99.8% are wasted. A push channel needs 5.79K small messages a second, and changes arrive in well under a second instead of up to 30 s.
Arithmetic. Holding connections costs memory instead of request rate (see the chat design); many systems push through a notification service and poll only as a fallback.
Pick the mechanism
Six problems, four mechanisms.
Each problem has one mechanism that fits best. Each answer is worth 20 XP.
Match the symptom: big re-uploads, lost edits, idle polling, or slow sharing?
Question 1 / 6
A one-word edit to a 50 MB document uploads the whole file again.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
File sync in practice.
Published ideas behind file-sync systems.
in-house exabyte-scale storage
Dropbox moved the bulk of its stored files from a public cloud to its own storage system, Magic Pocket, which it built to store file blocks on its own hardware at lower cost.
delta transfer
Andrew Tridgell's rsync algorithm compares a file's blocks with a rolling checksum so that only differing parts need to be sent, the idea behind many delta-sync tools.
operational transformation
Google's collaborative editor uses operational transformation to merge simultaneous edits from many people into one consistent document, which is why live documents rarely produce conflicted copies.
Interview angle
What interviewers actually ask.
Six questions, each worth 20 XP. Strong answers separate metadata from content and handle conflicts honestly.
Say how content is stored, how it syncs, how conflicts are handled and how access is checked.
Question 1 / 6
Why store file content and metadata separately?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
A company shares its 1,000,000-file knowledge folder with all 100,000 employees. Click Share. The page spins. And spins.
The standard fix is inheritance: store the permission once on the folder (and once per group, not per person), and compute a file's effective access by walking up its ancestors at check time, cached. Sharing becomes one write per grantee; the cost moves to reads, which are cheap to cache and invalidate. Use groups so adding a person is one membership row. Mark exceptions explicitly where a file differs from its parent.
1,000,000 files shared with 100,000 people at 50,000 writes a second: explicit rows need 100 billion writes, 23 days. With inheritance it is 100,000 writes, 2 seconds. Granting to one group is a single row.
Permission rows to write100B
Time to finish the share23.1 days
With the other design2 s
Writing a row for each of 1M files for each of 100K people is 100B rows: 23.1 days at 50,000 writes a second.
Arithmetic: explicit = files × members; inherited = members (or 1 if granted to a group). Moves and renames also stay cheap with inheritance, since only the folder's parent pointer changes.