Design a file sync service
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.
Uploading a file is the easy part of this question. Keeping one folder identical across four devices, two of which are asleep, one of which is on hotel wifi, and one of which has been switched off for a month, is the part that gets designed badly.
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, so files are split into blocks and only changed blocks move. That single 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 to a device that is not there, so syncing is a device pulling a change log from a cursor it holds. A nudge wakes it up, the nudge carries no data. |
| What happens when two devices edit the same file? | Keep both. Never silently lose one. | Conflicted copies rather than a merge. Say this out loud: a general file sync service cannot merge a binary file, so the honest answer is to keep both and name them clearly. |
| Do we deduplicate the same bytes across different users? | Yes. Storage is the second largest line on the bill. | Content addressed blocks, and a privacy problem you should name: if an upload is instant because someone else already has that block, you have told the uploader that 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 path. The nudge is tiny and urgent, the transfer is large and allowed to be slow, and 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 immutable and content addressed, so a version is a list of hashes and a delete is a flag, not a destructive operation. |
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 dedupe. Nobody restarts a 50GB upload because a train went into a tunnel.
- Handle concurrent edits without losing data. A conflicted copy, named so a human can tell which is which.
- Share a folder with other users. Which is where the permission model and the fan out 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.
- Collaborative editing of the file contents. Different problem, different algorithm, and it has its own page.
- Full text search inside documents. An indexing pipeline that reads this system rather than part of it.
- Fine grained per file permissions. Folder level sharing is enough to show the design.
- Selective sync policy on mobile. A client product decision with no interesting server side.
Back of the envelope#
Two things fall out of this. The bytes are object storage, which is a solved problem you can buy by the petabyte, while 750 billion small rows that have to be read in order, per device, from a cursor, is the part that gets redesigned twice. And chunking is the entire 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 are immutable, content addressed, and you can buy that storage. The metadata is the half that hurts, because every device asks "what changed since I last asked" and that question has to be answered in order, cheaply, billions of times a day, for namespaces 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
}The data model#
Two stores, split by what changes rather than by what the data is.
| namespace_id | bigint | PK | Partition key. One user's private folder or one shared folder. Everything about it lives together, which is what makes a cursor read a single partition scan. |
| seq | bigint | PK | Clustering key, strictly increasing within the namespace. This number is the cursor every device remembers. |
| path | varchar(1024) | IDX | The current path. A rename is an entry, 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 and are shared with whoever else has them. | |
| size, mtime | bigint, timestamp | Enough for a client to decide what to fetch without opening anything. | |
| deleted | boolean | A delete is an append like every other change. That is what makes undelete and 30 day history fall out 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 less metadata and worse delta efficiency, and this number is the knob. | |
| refs | approximate | Not a transactional reference count. Counting references to a block from a billion namespaces exactly is a distributed counter nobody wants. |
The whole system on one whiteboard#
Walking Figure 1:
- The client notices a file changed and splits it into blocks. This happens on the device, before anything touches the network, and how it splits is the first deep dive.
- It asks which of those block hashes the server is missing. Usually most of them are already there, either from the previous version of this file or from another user entirely.
- Only the missing blocks are uploaded, straight to the block store, resumable and 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, the change is appended. The file is now real, and it was never real at any moment when its bytes were missing.
- The notifier learns 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 the background: membership decides who sees a namespace, history is a view over old journal entries, 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#
Why fixed size blocks are the wrong answer#
Split a file every 4MB and you get a design that works beautifully until someone inserts a line at the top of a document. Every byte after the insertion shifts, so every block boundary lands in a different place, and a one character edit uploads the entire file.
The fix is to let the content decide where the boundaries go.
Be honest about the cost. Variable chunks mean you cannot compute where a byte is without walking the 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 deduplicate better and move less on an edit, and cost you more metadata rows and more round trips per file. Say the shape of the trade and give a range rather than a number: somewhere around 1MB to 8MB average, tuned by measuring the ratio of bytes moved to bytes changed on real files. Then name the detail that shows you have thought about it, which is that you also need a minimum and maximum chunk size, because a pathological file can produce a boundary every 50 bytes or none at all for a gigabyte.
Syncing by cursor, not by comparison#
The tempting model is that a client compares its folder to the server's folder and fixes the differences. That is correct, and it costs you a full comparison on every sync, needs the client to hold the entire tree, and gets slower as the folder grows even when nothing changed.
The journal replaces it with a number. Every device remembers one integer per namespace, and syncing means asking what came after it.
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 exercised path and the constantly exercised path are the same path, which is how you avoid the bug that only shows up after somebody's long holiday.
Two devices, one file#
The 409 from the commit endpoint is where a product decision lives, and the interviewer is asking which one you make.
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.
Break it#
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 is handling 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. Jitter the wake up, and return small changes inline with the long poll so a trivial edit does not cost a second round trip from every device.
- someone pastes 200k files · Down. A namespace is one partition by design, so 200,000 appends all land on one shard while the rest of the fleet idles. This is the hot partition this design chooses to accept, and the mitigations are a per namespace write rate limit and batching a bulk import into fewer, larger journal entries.
- 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 do not see on a bandwidth graph. Per device rate limits and a server told backoff interval in every response, so you can slow a misbehaving client without shipping it a new build.
- repaired · Healthy. Notice none of the repairs were about bytes. Every failure in this system is about metadata operations and wake ups, which is why the napkin maths put the row count in the headline rather than the petabytes.
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 dedupe across users. | Rolling hash CPU on the client, variable chunk sizes, and no way to seek to a byte offset without walking the list. | Any sync product where files are edited rather than only added. For write once storage, fixed blocks are simpler and fine. |
| Cursor journal over tree comparison | Sync cost is proportional to what changed, not to 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 is explainable to a user in one sentence. | Users occasionally 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. |
| Cross user deduplication | A large cut in stored bytes, and instant uploads for files the service has seen before. | An upload that completes suspiciously fast tells the uploader that someone else has that exact file. | Consumer storage, usually yes. If that leak matters, scope dedupe to 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, rather than 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.