Library
39 min read

Design Dropbox

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.

LaptopChunkerBlock checkBlock storeSync APIMetadata serviceJournal DBChange notifierPhone

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.
The real Dropbox

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 askThey sayWhat 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#

Functional requirements
What the system does.
  • 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.
Non-functional requirements
How well it has to do it. The numbers you commit to.
  • 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.
Out of scope
What you cut, and say so out loud.
  • 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.)

What actually moves, and what actually piles up
500 million
500
12 MB
Files stored500M x 500 = 250 billion
Logical bytes250B x 12MB = 3.0 EB
After storing shared blocks once, about 25% less2.3 EB
Metadata rows at 3 versions each250B x 3 = 750 billion
Metadata size at ~300 bytes a row225 TB
750 billion rows
of metadata, which is a harder problem than the exabytes of file content

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.

The number people get wrong

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.