Design a File Sync Service Like Dropbox

This is lesson 2 of System Design Case Studies, Part 2. The earlier Design File Upload lesson covers presigned URLs and multipart upload for one file. Here we design the whole sync product: many devices, many versions, edits, deletes and conflicts. The storage part builds on Object Storage.

Words used in this lesson

• Sync means making the files on two or more places the same.
• Chunk (block) is a piece of a file. A file is a list of chunks.
• Content-addressed storage means a chunk's name is the hash of its bytes. Same bytes, same name, so the same chunk is never stored twice.
• Dedup (deduplication) means storing identical data only once.
• Hash is a fixed-size fingerprint of data. SHA-256 gives 32 bytes. Two different chunks having the same SHA-256 is so unlikely that systems treat it as impossible.
• Fixed-size chunking cuts every N bytes. Content-defined chunking (CDC) cuts where the content itself says so, using a rolling hash, so the cut points follow the content.
• Delta sync means sending only the changed part of a file.
• Metadata is information about files (name, folder, size, list of chunk hashes, version), not the bytes.
• Journal (change log) is an ordered list of changes. A device asks "what changed since position 4021?".
• Long poll means a request the server holds open until it has something to say, then answers.
• Conflicted copy is a second file saved next to the first when two devices changed the same file at once.
• Resumable upload is an upload that can continue from where it stopped after a network drop.

1. Requirements

Functional

• A user installs a client on several devices. A folder stays the same on all of them (upload, download, edit, rename, delete).
• Changes made offline sync when the device is online again.
• Share a folder or a link with other people.
• Version history: restore an older version or a deleted file (assume 30 days).

Non-functional

• Reliable: never lose a file, never silently overwrite a newer version. This matters more than speed.
• Efficient: a small edit to a large file should not re-upload the file. A 50 GB file should upload on a flaky network.
• Fast notification: a change should show up on other devices within a few seconds (assume).
• Scalable: assume 100 million users and many small files.
• Secure: encrypted in transit and at rest, and access checks on every chunk.

Out of scope: real-time co-editing of one document (that is Lesson 3), search, and virus scanning (I mention it only).

2. Back-of-envelope numbers

All numbers below are assumptions. Method: Back-of-the-Envelope Estimation.

Users                : 100,000,000 total, 20,000,000 active per day (assume)Stored per user      : 2 GB average (assume)Raw storage          : 100e6 * 2 GB = 200e6 GB = 200 PBDedup saves          : assume 25% -> 150 PB of unique chunksDurability overhead  : erasure coding or copies, assume 1.5x -> 225 PB on diskChanges              : 20e6 active users * 10 file changes/day = 200e6 changes/dayMetadata commits     : 200e6 / 86,400 = ~2,300 /s average, assume 3x peak -> ~7,000 /sBytes uploaded       : assume 1 MB of new chunks per change after dedup and delta                       200e6 * 1 MB = 200 TB/day = 2.3 GB/s = ~18.5 Gbit/s averageChunk metadata       : a chunk entry = 32-byte hash + 8-byte size = 40 B  1 GB file, 4 MB chunks -> 256 chunks * 40 B = ~10 KB of metadata  1 GB file, 4 KB chunks -> 262,144 chunks * 40 B = ~10 MB   <- why chunks are not tinyNotifications        : assume 10,000,000 devices online at once, one open connection each                       one server holds ~50,000 idle connections (assume) -> 200 servers

Look at the chunk metadata line. Smaller chunks save more bandwidth on edits, but the metadata and the number of storage requests grow in proportion. This is the main design trade-off, discussed in 6.1.

3. API

# Metadata serviceGET  /v1/changes?cursor=4021     -> 200 { "entries": [ {"path":"/docs/a.txt","rev":7,"chunks":["h1","h2"],"size":8192,"deleted":false} ],              "cursor": 4057, "hasMore": false }POST /v1/commit     { "path": "/docs/a.txt", "baseRev": 6, "chunks": ["h1","h9"], "size": 8192, "device": "laptop-1" }     -> 200 { "rev": 7 }                                  # accepted     -> 200 { "conflict": true, "savedAs": "/docs/a (laptop-1's conflicted copy).txt" }     -> 409 { "missing": ["h9"] }                          # some chunks have not been uploaded yet# Block servicePOST /v1/blocks/missing   { "hashes": ["h1","h9"] }   -> { "missing": ["h9"] }PUT  /v1/blocks/{hash}    body: bytes                 -> 200  (server re-hashes the bytes and checks they match {hash})GET  /v1/blocks/{hash}    -> bytes# NotificationGET  /v1/subscribe?cursor=4057      # long poll: waits up to ~60 s, answers when the cursor is out of date

The order is the key rule: upload chunks first, commit metadata last. A commit that names a chunk the server lacks is refused (409 missing). So the folder can never point at data that does not exist.

4. Data model

-- Metadata DB (relational, sharded by user_id or namespace_id)CREATE TABLE file_entry (  namespace_id bigint,          -- a user's folder tree or a shared folder  path         text,  rev          bigint,          -- version number of this path, goes up by 1 on each commit  size         bigint,  deleted      boolean,  modified_by  text,            -- device id  journal_id   bigint,          -- position in the namespace's change journal  PRIMARY KEY (namespace_id, path));CREATE TABLE file_chunks (      -- ordered list of chunks for a revision  namespace_id bigint, path text, rev bigint, seq int, chunk_hash bytea,  PRIMARY KEY (namespace_id, path, rev, seq));CREATE TABLE journal (          -- the change feed, one row per commit  namespace_id bigint, journal_id bigint, path text, rev bigint,  PRIMARY KEY (namespace_id, journal_id));-- Block index: which chunks exist and how many files use themCREATE TABLE block (chunk_hash bytea PRIMARY KEY, size int, refcount bigint, storage_key text);

The chunk bytes are in object storage under blocks/ab/cd/<hash>. The database stores only the list of hashes. A namespace is one folder tree; a shared folder is its own namespace that several users can mount. Sharding by namespace keeps one user's journal on one database shard, so a commit is a normal transaction there (Sharding).

5. High-level architecture

 Device A                                                         Device B +------------+   1. watch folder, chunk, hash                   +------------+ | sync client|   2. ask: which hashes are missing?              | sync client| | local DB   |------------------------------+                   | local DB   | +-----+------+                              |                   +-----^------+       | 3. upload missing chunks            v                         | 6. download new chunks       |                          +--------------------+               |       |                          |   API / edge       |               |       v                          +----+----------+----+               | +------------+                        |          |                    | | Block      |<-----------------------+          +--> +-------------+ | | service    |  hash check, refcount                   | Metadata    | | +-----+------+                                         | service     | |       |                                                | (journal)   | |       v                                                +------+------+ | +------------+      4. commit (baseRev check)                |        | | Object     |                                               | 5. new journal entry | storage    |                                               v        | +------------+                                        +-------------+ |                                                       | Notification|-+  long poll: "cursor moved"                                                       | service     |                                                       +-------------+

Flow for an edit on A: the client sees the file change, cuts it into chunks, hashes them, asks the block service which hashes are missing, uploads only those, then commits the new list of hashes. The metadata service checks the base revision, writes a journal entry, and tells the notification service. B's long poll returns, B reads the journal from its cursor, finds the new revision, downloads only chunks it lacks, and rebuilds the file.

6. Deep dives

6.1 Chunking: fixed-size or content-defined

Fixed-size chunking cuts every N bytes (for example 4 MB). It is simple, but there is a bad case: insert a few bytes at the start of a file and every later chunk shifts, so every chunk gets a new hash and the whole file uploads again.

Content-defined chunking (CDC) decides the cut points from the data. A rolling hash over the last few bytes is computed at each position, and where it matches a pattern (for example the low 12 bits are all ones), the chunk ends. A match happens on average once every 2^12 = 4096 bytes. Because the cut depends only on nearby bytes, an insert at the start changes only the first chunk. Later cut points are found at the same places as before. Minimum and maximum chunk sizes stop tiny and huge chunks.

I ran both on a 400 KiB random file, then inserted 10 bytes at the start.

fixed 4 KiB  first upload : 100 chunks, sent 400 KiB  after insert : 101 chunks, sent 400.0 KiB of 400 KiBcontent-defined (avg 4 KiB)  first upload : 82 chunks, sent 400 KiB  after insert : 82 chunks, sent 3.4 KiB of 400 KiB

Fixed-size chunking re-sent everything. CDC re-sent 3.4 KiB, less than one percent. Core of the CDC code:

function cdcChunks(data: Buffer, avg = 4096, min = 1024, max = 16384, W = 16): Buffer[] {  const mask = avg - 1;                          // avg is a power of two  const out: Buffer[] = [];  let start = 0;  for (let i = 0; i < data.length; i++) {    const len = i - start + 1;    if (len < min) continue;    let h = 0;                                   // hash of the last W bytes (recomputed: simple, not fast)    for (let j = Math.max(start, i - W + 1); j <= i; j++) h = (Math.imul(h, 31) + data[j]) | 0;    if (((h >>> 0) & mask) === mask || len >= max) { out.push(data.subarray(start, i + 1)); start = i + 1; }  }  if (start < data.length) out.push(data.subarray(start));  return out;}

My hash is a simple multiply-and-add over a window of 16 bytes, recomputed at every byte. A production chunker uses a true rolling hash (such as Rabin fingerprints or Gear hashing) that updates in constant time per byte. The behaviour in my test came from the idea, not from speed.

What size? Syncthing's protocol spec says block size is between 128 KiB and 16 MiB, in powers of two, and picks "the smallest block size that results in fewer than 2000 blocks" for the file (128 KiB up to 250 MiB, 256 KiB up to 500 MiB, and so on, up to 16 MiB for files over 16 GiB). That is a way to keep the block list short for big files. Dropbox is commonly described as using 4 MB blocks (not re-read). My view: for a cloud service with millions of files, a few MB is a good start; use smaller CDC chunks (tens of KB) only if edits inside big files are the main cost, and accept the metadata growth shown in the numbers above.

Small files (most files) fit in one chunk. For those, chunking brings only dedup, and the cost is one request per file. Batch many small files into one request to avoid the per-request overhead.

6.2 Content-addressed storage and dedup

The chunk name is its hash. The block store has three simple rules:

1. missing(hashes) returns the hashes not yet stored.
2. put(bytes): compute the hash; if it exists, do nothing; otherwise store it.
3. Many files point to the same hash. A reference count says how many. A background job deletes a chunk when the count is zero and it is older than a grace period (so a chunk uploaded just before its commit is not deleted by mistake).

class BlockStore {  blocks = new Map<string, Buffer>(); bytesStored = 0; bytesOffered = 0;  missing(hashes: string[]) { return hashes.filter((h) => !this.blocks.has(h)); }  put(buf: Buffer) { const h = sha(buf); this.bytesOffered += buf.length; if (!this.blocks.has(h)) { this.blocks.set(h, buf); this.bytesStored += buf.length; } return h; }}function sync(store: BlockStore, chunks: Buffer[]) {            // what a client does  const hashes = chunks.map(sha);  const need = new Set(store.missing(hashes));                  // ask first  let sent = 0;  chunks.forEach((c, i) => { if (need.has(hashes[i])) { store.put(c); need.delete(hashes[i]); sent += c.length; } });  return { chunks: chunks.length, sentBytes: sent, hashes };}

Two users uploading the same file:

user 1 sent 400 KiB, user 2 (same file) sent 0 KiB, server stores 400 KiB

User 2's client sent only the list of hashes; the server already had every chunk, so no bytes moved. The same happens when one user copies a file, renames it, or has the same chunk in two different files.

The server must re-hash every uploaded chunk and check it equals the hash in the URL. If it trusted the client, a bad client could store wrong bytes under a good hash and poison every file that uses it.

6.3 The metadata service and the journal

The metadata service is the brain. It stores, per namespace, an ordered journal of changes, with a rising journal_id. Each device keeps a cursor: the last journal_id it has seen. To catch up, a device asks GET /v1/changes?cursor=… and gets everything after it. This is the same idea as a log in Apache Kafka, and it is simple and resumable: a device that was off for a week asks from its old cursor.

A commit is one database transaction: check the base revision, insert the chunk list, update the file_entry, append a journal row. Because one namespace lives on one shard, this is a local transaction. Two devices committing to the same namespace are serialised by the database, so the order is decided in one place.

Rename and move are metadata-only: change the path, no chunk moves. Delete sets deleted = true, and the chunks stay (for version history) until the retention period ends and the reference count drops.

6.4 Notifications: telling other devices

Polling every few seconds from 10 million devices is wasteful. So each client opens a long poll (or a WebSocket, see Real-Time Apps) to the notification service and sends its cursor. The service answers when the namespace's latest journal_id is above that cursor. The answer carries no data. It just says "something changed"; the client then calls /changes. This keeps notification servers simple and stateless.

Where does the notification service learn about new commits? The metadata service publishes namespace X moved to journal_id N on a message queue (Queues vs Pub/Sub), and each notification server subscribes for the namespaces its connections care about. If a notification is lost, the cost is small: the client's poll times out after about a minute, it asks /changes anyway, and catches up. Notifications are a hint; the journal is the truth.

On a local network, clients can also find each other and exchange chunks directly (a "LAN sync"), which saves internet bandwidth. I list this as an extension.

6.5 Delta sync

"Delta sync" in this design needs no special protocol. Content-defined chunking already gives it: the client uploads only chunks the server lacks, and the receiving device downloads only chunks it lacks. For a one-line edit in a 100 MB file with 4 MB chunks, you upload one chunk (about 4 MB) plus a new metadata entry. For finer deltas (rsync-style, sending only changed bytes inside a chunk) you can add a second level inside a chunk, but the gain over small chunks is usually not worth the code.

The receiving device builds the new file from a mix of chunks it already has on its disk (from the old version) and the ones it downloads.

6.6 Resumable upload

The "ask which chunks are missing" step is also the resume step. Upload a 5 GB file as 1,250 chunks of 4 MB. The client's connection drops after chunk 612. When it returns, it hashes the file again (or reads its saved list), calls missing and gets the chunks that never arrived, and sends only those. No special upload session is needed, because each chunk is a separate request that can be repeated safely: uploading the same hash twice is harmless (it is idempotent, see Idempotency, Pagination & API Versioning).

For very large chunks, or when each request has overhead, also let a single chunk upload resume by byte range. The commit still happens only after all chunks exist, so a half-finished upload is invisible to other devices.

6.7 Conflicts

Two devices edit the same file while apart. Both commit with baseRev = 6. The first commit becomes rev 7. The second sees that the current rev is 7, not 6, so its edit was made on an outdated version. The server must not overwrite. The usual product rule is: keep both. The loser's content is saved as a conflicted copy next to the original, and the user decides.

I ran this with the commit rule current rev must equal baseRev:

function commit(path: string, baseRev: number, hashes: string[], device: string): string {  const cur = meta.get(path);  if ((cur?.rev ?? 0) !== baseRev) {                     // someone else committed first    const copy = `${path} (${device}'s conflicted copy)`;    meta.set(copy, { rev: 1, hashes });    return `CONFLICT -> saved as "${copy}"`;  }  meta.set(path, { rev: baseRev + 1, hashes });  return `ok, rev ${baseRev + 1}`;}

laptop commit : ok, rev 1phone  commit : ok, rev 2laptop (stale): CONFLICT -> saved as "report.txt (laptop's conflicted copy)"[  'report.txt rev=2 h2',  "report.txt (laptop's conflicted copy) rev=1 h3"]

This works because the commit is compare-and-set on the revision (a write that only succeeds if the value is still what you expect). The metadata database does it in a transaction. Nobody's data is lost: both versions exist. Other designs: Syncthing uses version vectors per file (its spec has a version field made of counters per device) so peers without a central server can tell "newer" from "concurrent". With a central server, a single revision counter is enough and simpler.

Merging text automatically would need the ideas from Lesson 3. Sync services mostly do not try, because the file may be a binary. Two other conflicts: edit vs delete (keep the edit, restore the file) and two creates of the same path (rename one).

6.8 Sharing and permissions

A shared folder is its own namespace, and members have it mounted in their tree. Every metadata call checks the user's role on the namespace. Every block call must also check that the caller may read a chunk. Because chunks are shared across users, the check is by file: the download URL is issued only after the metadata check says this user's file lists this hash. Without that, anyone who guessed a hash could download any chunk.

7. Failure modes and trade-offs

Trade-offs to say aloud

• Chunk size: small = better dedup and delta, more metadata and requests. Large = the opposite. A few MB is a reasonable default.
• Cross-user dedup: saves storage, weakens privacy and per-user encryption.
• Central ordering vs peer-to-peer: a central metadata service makes ordering and conflicts easy and is a single logical dependency. P2P tools like Syncthing avoid the server but need version vectors.
• Client work: chunking and hashing happen on the client (CPU, battery) so the server stays light and bandwidth falls.

8. How to say it in an interview (60 seconds)

"The core idea is to separate bytes from metadata. The client cuts each file into content-defined chunks of a few MB, hashes them with SHA-256, and asks the server which hashes are missing. It uploads only those, then commits a list of hashes to a metadata service. Chunks are stored by hash in object storage, so identical data is stored once, uploads resume by asking again what is missing, and a small edit uploads about one chunk. In my test, inserting 10 bytes at the start of a 400 KiB file re-sent 3.4 KiB with content-defined chunks and 400 KiB with fixed chunks. The metadata service keeps an ordered journal per folder. Each device keeps a cursor and asks for changes since then; a long-poll notification just says that the cursor is behind. A commit carries the base revision. If it is stale, the server keeps both and saves a conflicted copy. Chunks are re-hashed on the server, and access is checked per file, not per hash. Numbers: 100 million users at 2 GB is about 200 PB raw, and about 2,300 commits per second on average."

Run it yourself

Run node chunks.ts with Node 22. It uses only node:crypto. The data is random bytes made in memory. If you change avg, min and max, you can see the trade-off between chunk count and re-sent bytes.

Interview questions

Key takeaways

• Separate bytes from metadata. Chunks live in object storage by hash. A small metadata service holds the file tree and an ordered journal.
• Content-defined chunking makes delta sync work: in my test, a 10-byte insert re-sent 3.4 KiB instead of 400 KiB.
• Content addressing gives dedup, safe retries and cheap renames. Re-hash on the server, and check access per file.
• Upload chunks first, commit last. Resume is just "which hashes are missing?".
• Notifications are hints, the journal is the truth. Use long polls and cursors.
• Conflicts: compare-and-set on the revision, and keep both versions.

What's next

Lesson 3: Design Collaborative Editing Like Google Docs. Sync keeps both versions of a file when two people edit. Now we ask the harder question: how can two people edit the same document at the same time and end up with one merged text?