Design Dropbox
Read firstSQL vs NoSQLMessage queues
You edit a spreadsheet on a laptop with the wifi off. Someone else edits the same file from their desk. You land, open the lid, and the two versions have to become one thing without anybody being asked to sort it out.
That is the job of a file sync service: one folder that looks the same on every device you own, even the ones that were asleep or offline when you changed something. Watch one edit travel from a laptop to a phone.
Split. You save report.xlsx on the laptop. The client splits the file into blocks and names each block by its hash.
Uploading a file is the easy part of this question. Keeping one folder identical across four devices, two of which are asleep, one on hotel wifi, and one switched off for a month, is the part that gets designed badly.
A few words come up on every line of this page:
- A block (or chunk) is a piece of a file. Files are stored as a list of blocks.
- A hash is a short fingerprint of some bytes: same bytes, same hash, every time. If the idea is new, the hashing article shows one being computed live.
- Metadata is the data about a file rather than the file itself: its path, its size, and which blocks it is made of.
- A namespace is one synced folder: your private Dropbox, or one shared folder. All the metadata for one namespace is kept together.
This page builds a file sync service like Dropbox: edit a file on one device and see it on the others, even after working offline. The numbers and choices below are interview assumptions, not Dropbox's own. Two parts will look familiar if you use Dropbox: files are stored as blocks of up to 4MB named by their hash, and when two edits clash you get a "conflicted copy".
Step 1: Understand the problem#
Three of the six answers below decide the whole design, and the first one decides the bandwidth bill.
| You ask | They say | What it settles |
|---|---|---|
| How big are files, and how much of one changes in an edit? | A 2KB note up to a 50GB video, and an edit usually touches a few percent. | Chunking. You never upload a whole file after a one line change. Files are split into blocks and only changed blocks move. That one answer removes most of the traffic in the system. |
| How many devices per user, and are they online? | Three or four, and most of them are asleep most of the time. | The server cannot push data to a device that is not there. So a device pulls a list of changes, starting from a bookmark it keeps. A small nudge wakes it up, and the nudge carries no data. |
| What happens when two devices edit the same file? | Keep both. Never silently lose one. | Conflicted copies, not a merge. Say this out loud: a general sync service cannot merge two versions of a video, so the honest answer is to keep both and name them clearly. |
| Do we store identical bytes once, even across different users? | Yes. Storage is the second largest line on the bill. | Blocks are named by their hash, so identical blocks are stored once. That has a privacy cost you should name: if an upload finishes instantly because someone else already has that block, you have told the uploader that the file exists on the service. |
| How fast must a change reach another device? | A few seconds when both are online. | A long lived notification channel, separate from the data. The nudge is tiny and urgent, the transfer is large and allowed to be slow. Mixing them is how one slow upload delays everybody. |
| Do we need version history? | 30 days, plus undelete. | Almost nothing extra, which is the quiet payoff of chunking. Blocks are never changed after they are written, so an old version is just an old list of hashes, and a delete is a flag. |
What you are building, and what you cut#
- Keep a folder identical across a user's devices. Including devices that have been offline for weeks.
- Upload and download with resume, and store identical blocks once. Nobody restarts a 50GB upload because a train went into a tunnel.
- Handle two devices editing at once without losing data. A conflicted copy, named so a human can tell which is which.
- Share a folder with other users. Which is where permissions and waking many devices both get interesting.
- 500 million users, a few hundred files each.
- A change on one device appears on another in under 5 seconds when both are online.
- A device offline for a month catches up without downloading the folder again.
- No file is ever lost, including when two people edit at once.
- Several people typing in one document at the same time. Different problem, different algorithm, and it has its own page: Design Google Docs.
- Full text search inside documents. An indexing pipeline that reads this system, not part of it.
- Per file permissions. Sharing whole folders is enough to show the design.
- Which folders a phone chooses to sync. A client product decision with nothing interesting on the server.
Back of the envelope#
Three inputs. Watch which number ends up in the headline, because it is not the one most people expect. (The back of the envelope chapter explains the method.)
Two things fall out of this. The bytes go to object storage, which you can buy by the petabyte. The 750 billion small rows, read in order by every device from its own bookmark, are the part that gets redesigned twice. And chunking is the whole bandwidth story: a one line change to a 12MB document moves one 4MB block, and a one line change to a 2GB video also moves one 4MB block.
Candidates size the block store, find an impressive number of petabytes, and design around it. Blocks are the easy half: they never change once written, they are named by their content, and you can buy that storage. The metadata is the half that hurts. Every device keeps asking "what changed since I last asked", and that question has to be answered in order, cheaply, billions of times a day, for folders that range from one file to two million.
Step 2: Propose the high level design#
The API#
Five calls, and the first one is the one most designs are missing.
{
"hashes": ["a3f1...", "7c90...", "1b2e..."]
}{
"path": "/work/report.xlsx",
"blocks": ["a3f1...", "7c90..."],
"baseVersion": 41207
}That last call is a long poll: the device sends a request and the server simply does not answer until it has news (or about 90 seconds pass, and the device asks again). It is one of four ways to get news from a server to a client, compared side by side in WebSockets vs SSE vs long polling.
The block upload gets a property for free that most APIs work hard for. Because the block's name is its own hash, sending it twice changes nothing, so a phone that loses signal halfway can simply send it again. A request that is safe to repeat is called idempotent, and idempotency keys shows the extra work other APIs need to get the same guarantee.
The data model#
Two stores, split by how the data behaves rather than by what it is. Blocks are big and never change. Metadata is small and changes all the time.
| namespace_id | bigint | PK | Which folder this row belongs to: one user's private folder or one shared folder. All rows for a folder live together, so reading them in order is one quick scan. |
| seq | bigint | PK | A counter that only goes up within the folder. This number is the cursor every device remembers. |
| path | varchar(1024) | IDX | The path at this moment. A rename is a new row, not an update, which is why history survives one. |
| block_list | array of sha256 | The file is this list. The bytes live somewhere else entirely, shared with whoever else has the same blocks. | |
| size, mtime | bigint, timestamp | Enough for a device to decide what to fetch without opening anything. | |
| deleted | boolean | A delete is a new row like every other change. That is why undelete and 30 day history come for free. |
| sha256 | char(64) | PK | The name is the content. Two users with the same holiday photo store it once. |
| size | int | Up to 4MB. Bigger blocks mean fewer metadata rows but more bytes moved per small edit. This number is the knob. | |
| refs | approximate | Not an exact count of who uses the block. Counting that exactly across a billion folders is a distributed counter nobody wants. |
The blocks live in object storage: a huge, cheap store for files addressed by a key. How one works inside is its own question, in design object storage.
The whole system on one whiteboard#
Figure 1 is the same trip as the picture at the top, with the background jobs added.
Walking Figure 1:
- The client notices a file changed and splits it into blocks. This happens on the device, before anything touches the network. How it splits is the first deep dive.
- It asks which of those block hashes the server is missing. Usually most are already there, from the previous version of this file or from another user entirely.
- Only the missing blocks are uploaded, straight to the block store. Uploads can resume after a dropped connection and run in parallel.
- Then, and only then, the client commits: a path, an ordered list of hashes, and the version it believed it was editing.
- The metadata service checks that version against the journal.
- If it matches, one row is appended. The file is now real, and it was never real at any moment when its bytes were missing.
- The notifier learns that a namespace moved.
- Every awake device holding a long poll for that namespace is told, with no payload.
- Each of them asks for changes since its own cursor and gets exactly what it missed.
The three dashed arrows are background work. Membership decides who sees a namespace, history is a view over old journal rows, and a sweeper eventually deletes blocks nothing points at any more.
Step 2 asks the server which blocks it already has before uploading anything. What does that one question buy you, and what does it quietly leak?
Step 3: Design deep dive#
Sending an edit without sending the file#
You changed one line of a 2GB file. What goes over the network?
- First tryUpload the whole file on every saveWatch the folder, and whenever a file changes, upload all of it. It works on day one and it is how most people first sketch this.Where it breaks: A one line change to a 2GB video project moves 2GB. Every save. From every device. Over hotel wifi.
- BetterFixed size blocks, upload only the changed onesCut the file every 4MB, hash each block, and upload only blocks whose hash is new. Change a byte in the middle and one block moves.Where it breaks: Insert a line at the top of a document. Every byte after it shifts along, so every 4MB cut now lands somewhere different, every block looks new, and a one word edit uploads the whole file again.
- What you shipContent defined chunks, and ask before uploadingLet the bytes themselves decide where the cuts go, so an insert disturbs only the block it lands in. Then ask the server which block hashes it is missing and send only those.
The middle rung is the one to feel. Try both ways of cutting on one sentence, then add a word at the start.
Content defined chunking works like this. A small window slides along the file one byte at a time, and the client keeps a hash of just the bytes inside the window. Whenever that hash happens to match a pattern, it cuts. Because the decision depends only on the bytes in the window, not on how far into the file you are, the cuts after an insert land in exactly the same places as before. Here is the same thing one stage at a time.
Be honest about the cost. With variable sized chunks you cannot jump to byte 9,000,000 without walking the chunk list, and the rolling hash is real CPU on the client. Both are fine. The alternative is uploading a 2GB video because somebody renamed a layer in it.
"What chunk size would you pick?" Smaller chunks share better and move less per edit, but cost more metadata rows and more round trips per file. Give the shape of the trade and a range, not one number: somewhere around 1MB to 8MB on average, tuned by measuring bytes moved against bytes changed on real files. Then add the detail that shows you have thought about it: you also need a minimum and a maximum chunk size, because an odd file can produce a boundary every 50 bytes, or none at all for a gigabyte.
Syncing by cursor, not by comparison#
Your phone was asleep. How does it find out what changed?
- First tryCompare the whole folder with the serverThe phone lists every file it has, the server lists every file it has, and they fix the differences. It is correct.Where it breaks: It costs a full comparison on every sync, the phone must hold the whole tree, and it gets slower as the folder grows even when nothing changed. A folder with two million files pays for two million files to learn that nothing happened.
- BetterThe server pushes each change to every deviceWhen the laptop commits, the server sends the change itself to the phone and the desktop.Where it breaks: A phone that is asleep misses the push. Now the server has to remember what every device has and has not received, and a phone that missed twenty changes needs a separate catch up path that is rarely run and therefore buggy.
- What you shipA journal, a cursor per device, and a nudge with no dataEvery change is one row in an ordered journal. Each device remembers one number, its cursor: the last row it has applied. Syncing means asking "what came after my number?". A long poll only says "something changed, come and ask".
Think of a group chat you muted for a week. You do not ask your friends to resend everything, and you do not compare your phone against theirs. You scroll from the last message you read. The cursor is that "last read" line. (This is the pull side of push vs pull: the server pushes a tiny nudge, the device pulls the data when it is ready.)
The property worth naming out loud: there is no catch up path. Offline for an hour and offline for a year run the same code with a different number in it. The rarely used path and the constantly used path are the same path, which is how you avoid the bug that only shows up after somebody's long holiday.
The journal is split across machines by namespace (the sharding chapter explains splitting data this way). One folder never spans two machines, so its rows stay in one order and the cursor stays one simple number. The price of that choice shows up in Break it below.
Two devices, one file#
The commit sends baseVersion: 41207, which means "I was editing version 41207". If the
journal is already at 41209, someone else committed in between, and the server answers 409.
Nothing was locked while you edited. The server only checks at the end whether the version
you started from is still the latest. That pattern is optimistic locking, and
optimistic vs pessimistic locking explains
when it is the right bet. For files edited on laptops that are often offline, it is the only
bet: you cannot hold a lock on a laptop in a plane.
The 409 is where a product decision lives, and the interviewer is asking which one you make. Try all three.
Pick conflicted copies, and say the sentence that justifies it: the server knows the bytes, the user knows the intent, and only one of those is qualified to throw work away. (When the product really does need two people in one file at once, it becomes Design Google Docs, a different design.)
Break it#
Push each failure and watch which box goes red first. Notice that none of them is about bytes.
Read every step as text
- normal · Healthy. Most devices are asleep. The awake ones hold a long poll that does nothing, commits are a few rows, and the block store handles large but entirely unexciting transfers.
- shared team folder · Degraded. Fifty people share one folder, so one commit wakes fifty devices and all of them ask for changes in the same 200 milliseconds. One commit became fifty reads of one partition, instantly. Add a small random delay to each wake up (jitter), and return small changes inside the long poll reply so a tiny edit does not cost a second request from every device.
- someone pastes 200k files · Down. A namespace lives on one partition by design, so 200,000 appends all land on one machine while the rest of the fleet idles. That is a hot partition, and this design accepts it on purpose. The fixes are a write rate limit per namespace and batching a bulk import into fewer, larger journal rows.
- a client goes into a loop · Down. A bug makes one device re-upload the same folder every thirty seconds. The block check makes it cheap in bytes and expensive in requests, which is the failure you never see on a bandwidth graph. Rate limit each device, and put a "back off for N seconds" value in every response, so you can slow a misbehaving client without shipping it a new build.
- repaired · Healthy. None of the repairs were about bytes. Every failure in this system is about metadata operations and wake ups, which is why the napkin math put the row count in the headline and not the petabytes.
Rate limits per namespace and per device are the main tool in two of those levels. The difference between refusing work and slowing it down is in rate limiting vs throttling vs backpressure.
Trade-offs#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Content defined chunking | An insert at the top of a file changes one chunk instead of all of them, and identical regions are stored once across users. | Rolling hash CPU on the client, chunks of different sizes, and no way to jump to a byte offset without walking the list. | Any sync product where files are edited, not only added. For write once storage, fixed blocks are simpler and fine. |
| Cursor journal over tree comparison | Sync cost follows what changed, not how many files exist, and offline for an hour and offline for a year are the same code path. | A journal per namespace is a hot partition for bulk operations, and the log has to be compacted eventually. | Always. Tree comparison looks simpler and gets slower every month the product succeeds. |
| Conflicted copies over merging | No edit is ever lost, and the behaviour can be explained to a user in one sentence. | Users sometimes see two files and have to decide, which feels like the product failing at its job. | Whenever the service does not understand the file format, which for a general sync service is always. |
| Storing identical blocks once across users | A large cut in stored bytes, and instant uploads for files the service has seen before. | An upload that finishes suspiciously fast tells the uploader that someone else has that exact file. | Consumer storage, usually yes. If that leak matters, share blocks only within one user and accept the bill. |
Interview replay#
Checkpoint#
1. Why are chunk boundaries chosen by a rolling hash rather than by byte offset?
2. Why must blocks be uploaded before the metadata commit, not after?
3. Same design, but it now syncs a single multi gigabyte database file that changes constantly. What breaks first?
- 4MB blocks: a one line edit to a 2GB file moves 4MB. That is the whole bandwidth argument.
- Hundreds of billions of metadata rows, which is a harder problem than the exabytes of content.
- One cursor per device per namespace. Offline for an hour and offline for a year are the same code path.
- Blocks first, metadata last. A file must never exist in the namespace pointing at bytes that are not there.
A file sync service is a chunking problem and a cursor problem, and almost nothing else. The client splits each file using a rolling hash so boundaries are decided by content, which means inserting a line changes one chunk instead of every chunk after it. It asks the server which chunk hashes are missing, uploads only those, and commits metadata last, so a file never exists in the namespace pointing at bytes that are not there. Metadata is an append only journal per namespace, and every device remembers one cursor into it, so syncing is asking what came after that number. A device offline for an hour and one offline for a year run exactly the same path. Notifications are a separate long poll that carries no data, just a nudge, which keeps the push tier stateless. Concurrent edits produce a conflicted copy rather than a merge, because a sync service does not know the file format and losing work silently is much worse than showing two files. The failure I would call out is that a namespace is deliberately one partition, so a shared folder with a bulk import is a hot shard, and I would rate limit and batch rather than give up the ordered cursor.