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.
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".
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.
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.
the blocksexabytes, never changed,bought by the petabytethe metadata, the half that hurts750 billion small rows,read in order, all day