Dropbox

File Storage

Design a file sync service that keeps a folder identical on every device a user owns, sends only the parts of a file that changed, lets people share folders, and never loses a file.

Overview

A file sync service keeps a folder the same on every device a user owns and on the server. When a file changes on one device, the change is uploaded, recorded, and pulled down by the others. Devices go offline for days, two people edit the same file, and files can be tens of gigabytes, so the design has to be careful about what it sends and what it treats as the truth.

The standard design, and the one Dropbox has described in its engineering blog, separates two kinds of data. File contents are split into blocks, each named by the hash of its bytes, and stored in a block store that knows nothing about files. File metadata (which blocks make up which file, in which folder, at which version) lives in a journal that every device reads from its own position. Most of the interesting behavior comes from that split.

Questions to ask first

How many users and changes? — 100 million daily active users, 10 file changes each a day
How many devices? — About 2 per user; half connected at peak
Largest file? — Tens of gigabytes
Offline editing? — Yes, for days; changes sync when the device reconnects
Real-time co-editing? — No: two edits to one file become a conflicted copy
Version history? — Yes, keep old versions for a retention period

What you will be able to do

Explain how a file becomes a list of block hashes, and why that makes sync, deduplication and integrity checks cheap.
Walk through the commit protocol: send hashes, upload only missing blocks, commit again.
Design the metadata journal and cursors that let a device catch up after days offline.
Detect conflicting edits and keep both versions.
Describe durable block storage: immutable blocks, replication across zones, then erasure coding.

Key concepts

Blocks and blocklists
Content addressing
Delta sync
Metadata journal
Cursors
Long polling
Conflicted copies
Namespaces
Erasure coding

Functional requirements

Upload, download and delete files and folders
Sync changes to all of a user's devices automatically
Keep working offline and sync on reconnect
Share a folder with other users as viewers or editors
Keep previous versions of a file and restore them
Resume large uploads after a dropped connection

Non-functional requirements

No file acknowledged by the server is ever lost
Other online devices see a change within about 10 seconds (a target we chose)
Send only the blocks that changed, never the whole file again
Every device converges on the same state once it is online
Conflicting edits never silently overwrite each other

Interview questions

How do you avoid re-uploading a whole file after a small edit?
How does a device find out about changes, and catch up after being offline?
What happens when two people edit the same file at once?
How does deduplication work, and what is the risk?
How do you store exabytes without losing files?
How do shared folders work?
How would you shard the metadata?