File sync
File sync keeps a folder identical on every device a user owns. The core decision is to split metadata from bytes: files are cut into chunks named by their content hash and stored once in a blob store (S3-like), while a metadata service records, per revision, which chunks make up each file. An edit uploads only the chunks the server doesn’t have, so a small change to a large file costs one chunk, and identical content is stored once. Every commit names the revision it was based on, so concurrent edits are detected, not lost, and the loser becomes a “conflicted copy”. Devices learn about changes from a long-poll and pull a journal from a cursor. Upload cost is O(changed chunks); hashing is O(file size) on the client.
The problem
Section titled “The problem”People expect a file saved on a laptop to appear on their phone in seconds, to survive the laptop being stolen, and to come back if they deleted it by mistake last week. At Dropbox or Google Drive scale that’s hundreds of millions of users, billions of files and exabytes of data, over flaky mobile networks.
The goals pull against each other:
| Goal | What it means | Pulls toward |
|---|---|---|
| Fast, cheap transfers | A one-line edit to a 1 GB file doesn’t re-upload 1 GB | Small chunks, delta sync, dedupe |
| Never lose data | Concurrent edits, crashes mid-upload and flaky networks never destroy a version | Immutable chunks, versioned metadata, optimistic concurrency |
| Converge quickly | Every device reaches the same state in seconds | Push notifications, cursors, small metadata diffs |
| Cheap at rest | Exabytes stored at low cost | Large chunks (less metadata), dedupe, cold tiers |
Small chunks help the first goal and hurt the last (more metadata rows and hashes). Most of the design is choosing where to sit.
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Sync a folder across a user’s devices; upload, download, rename, move, delete; version history (30 days); restore; share a folder with others. | Real-time co-editing of documents (that’s operational transforms / CRDTs, a different system)? Selective sync? Web and mobile clients? |
| Scale | 50M daily active users, ~10 GB stored each, ~30 file changes per user per day, files from bytes to 50 GB. | Distribution of file sizes? How many devices per user? Shared folders with thousands of members? |
| Latency | A change appears on other online devices within a few seconds. | Is that for small files only? |
| Consistency | Per-file revisions are totally ordered; no write is silently lost; devices converge. | What should happen on a concurrent edit: last writer wins, or keep both? |
| Durability | 11 nines for stored blocks; nothing acknowledged is lost. | Encryption at rest? End-to-end encryption (which rules out server-side dedupe)? |
| Out of scope | Full-text search, previews and thumbnails, malware scanning (all async consumers of the change journal). |
Back of the envelope
Section titled “Back of the envelope”Compare the two upload rows: sending only changed chunks is what makes the system affordable. Then check metadata commits per second, which sizes the metadata tier, and open connections, which sizes the notifier.
What to say out loud: “About 350 PB stored, so the block store is object storage with erasure coding, not something I build. Commits are ~17k/s average, maybe 50k/s at peak, which is a sharded relational database. Bandwidth depends on uploading only changed chunks, and 30M open long-polls need a notifier built for idle connections.”
API and data model
Section titled “API and data model”commit(namespace, path, base_rev, block_hashes[], size) -> ok(rev) | need(missing_hashes) | conflict(latest_rev)put_block(hash, bytes) -- via a presigned URL; the store checks sha256(bytes) == hashget_block(hash) -> byteslist_changes(namespace, cursor) -> (entries[], new_cursor, has_more)longpoll(namespace, cursor) -> changed | timeout -- held open ~60 s
Metadata (one row per revision): namespace_id, path, rev, block_hashes[], size, modified_at, author_device, deleted?Journal (per namespace, append-only): seq -> (path, rev) -- what list_changes pages throughBlock store: sha256 -> bytes -- immutable, written once, reference-countedTwo decisions hide in that sketch:
commitis a compare-and-set. The client says which revision it edited. If that’s still the latest, the commit wins; if not, it’s a conflict. Withoutbase_rev, the last upload would silently overwrite the other device’s work. Because blocks are content-addressed and commits are compare-and-set, a retried commit is naturally idempotent.- The journal is per namespace, not global. A namespace is a user’s folder tree or a shared folder. Each has its own monotonically increasing sequence, so a device’s cursor is just a number, metadata shards by namespace, and one busy shared folder doesn’t slow everyone else’s change feed.
High-level design
Section titled “High-level design”Step through the flows. File bytes never pass through the API servers; only hashes and block lists do.
| Component | Role | Why it’s there |
|---|---|---|
| Sync client | Watches the folder, chunks and hashes files, keeps a local DB of (path → rev, block list) and the cursor, applies remote changes atomically. | Most of the intelligence lives here: deciding what changed on each side. |
| Metadata API (×N) | Stateless: commit, list_changes, presigned block URLs, permission checks. | Small requests at high rates; scales horizontally. |
| Metadata DB | Revisions and journals, sharded by namespace (Dropbox runs this on sharded MySQL). | Strong consistency per namespace is needed for compare-and-set commits. |
| Block store | Immutable blobs keyed by hash, replicated or erasure-coded. S3 offers strong read-after-write consistency (since December 2020); Dropbox built its own (Magic Pocket). | Cheap, durable bytes; writes are simple because blocks never change. |
| Notifier | Holds long-polls (or WebSockets / mobile push) per device; wakes them when a namespace advances. | Change latency of seconds without devices polling the metadata DB. |
Deep dive: chunking and dedupe
Section titled “Deep dive: chunking and dedupe”Name each chunk by its hash and two good things follow: an unchanged chunk never needs re-uploading, and identical chunks anywhere are stored once. The catch is where the chunk boundaries go. Insert a few bytes near the start of the file below and compare the two strategies.
Fixed-size chunks (Dropbox uses 4 MB blocks) are simple and fast, and fine for in-place edits. But an insertion shifts every later byte, so every later chunk changes. Content-defined chunking (CDC) cuts wherever a rolling hash over the last few dozen bytes hits a pattern, so boundaries follow the content and realign right after the edit. The rolling hash page covers the hash itself; the boundary rule is the building block:
mask <- 2^b - 1 -- average chunk ≈ 2^b bytes (e.g. b = 13 → 8 KB)start <- 0; h <- 0for i in 0 .. len(data) - 1: h <- roll(h, data[i]) -- depends only on the last w bytes (e.g. 48) size <- i - start + 1 if (size >= MIN and h & mask == 0) or size >= MAX: emit chunk data[start .. i], named sha256(data[start .. i]) start <- i + 1emit the remainder, if anyMIN and MAX bound the variance: without MIN, tiny chunks bloat the metadata; without MAX, a long run of identical bytes (zeros) would never cut. LBFS (2001) used Rabin fingerprints over a 48-byte window with 8 KB average chunks; FastCDC (2016) uses a cheaper gear hash and is several times faster.
| Fixed-size | Content-defined | |
|---|---|---|
| Insert or delete in the middle | Every later chunk changes | One or two chunks change |
| In-place overwrite (databases, VM images) | One chunk changes | One or two chunks change |
| CPU | Hash only | Rolling hash + hash, still well over 1 GB/s per core with gear hashing |
| Chunk count | Exactly size / chunk | Varies around the average |
Dedupe scope. Dedupe within one account is safe and catches renames, moves and copies for free. Dedupe across all users saves more, but it leaks information: if uploading a file finishes instantly, its content must already exist on the server, which tells an attacker someone else has that exact file. Many services restrict dedupe to an account or a team, and end-to-end encryption rules out server-side dedupe entirely.
Small files. Most files are small, and a chunk per file means a block-store object per file. Pack small chunks into larger objects (with an index of offsets) so the store isn’t dominated by per-object overhead.
Deep dive: the sync protocol
Section titled “Deep dive: the sync protocol”Syncing is two loops on every device: push local changes up, and pull remote changes down, with a local database recording what the client last agreed with the server. Step through three scenarios, including a conflict:
The upload loop, as a building block (blocks first, then metadata, so a commit never references a block that doesn’t exist yet):
push(path): hashes <- chunk_and_hash(read(path)) base <- local_db.rev(path) -- the revision this edit started from loop: r <- commit(ns, path, base, hashes, size) if r is ok: local_db.set(path, r.rev, hashes); return if r is need: for h in r.missing (in parallel): put_block(h, bytes of h) continue -- retry the commit; it is idempotent if r is conflict: rename local file to "<name> (<device>'s conflicted copy <date>)" push(that new path); pull(); returnAnd the pull loop:
pull(): loop: (entries, cursor', more) <- list_changes(ns, local_db.cursor) for e in entries: if e.deleted: move local file to trash (if unchanged locally) else: fetch blocks of e not already present locally -- dedupe works on download too write to a temp file, fsync, atomic rename into place local_db.set(e.path, e.rev, e.blocks) local_db.cursor <- cursor' -- only after the entries are applied if not more: break longpoll(ns, local_db.cursor) -- returns "changed" or times out, then pull againDetails that come up:
- Three-way comparison. For each path the client knows three things: the local file, the remote latest, and the last synced revision (the “base”). Only local changed: push. Only remote changed: pull. Both changed: conflict. Without the base you can’t tell “I deleted it” from “it was never synced”.
- Cursor after apply. Saving the cursor before applying entries means a crash skips changes forever. Saving it after means a crash replays some entries, which is harmless because applying the same revision twice is a no-op.
- Moves and renames are metadata-only: the block list is unchanged, so no bytes move. Detecting a move rather than a delete plus an add needs the watcher (or the file’s inode/ID) to connect the two events.
- Partial uploads. A 10 GB file uploads block by block; on reconnect,
commitreturns only the still-missing hashes, so the upload resumes where it stopped.
Deep dive: notifications, versions and scale
Section titled “Deep dive: notifications, versions and scale”Long-polling. A device holds one HTTP request open to the notifier: “tell me when namespace 77 passes cursor #9,411”. It returns as soon as the namespace advances, or after ~60 s with nothing (then the device reconnects). The response carries no data, just a nudge, so the notifier is a giant in-memory map of namespace → waiting connections, fed by commit events. Mobile apps use platform push (APNs, FCM) when in the background. Dropbox’s desktop client has long used long-polling for exactly this.
Versioning. Since blocks are immutable and revisions are rows, version history is nearly free: keeping 30 days of history costs the metadata rows plus only the blocks that changed. Restore writes a new revision pointing at old blocks. A garbage collector deletes blocks with no references after the retention window; it must not race uploads in progress (mark-and-sweep with a grace period is common). See Versioning and Snapshots.
Shared folders. A shared folder is its own namespace, mounted into each member’s tree. A change bumps one journal; each member’s client follows the cursors of all namespaces it mounts. A folder with 10,000 members means one commit wakes 10,000 long-polls, which is a fan-out problem like a news feed, handled by batching wake-ups.
Hot spots. Metadata shards by namespace, so one enormous shared folder (a company drive) can overload a shard. Split very large namespaces by subtree, and rate-limit pathological clients (a build directory rewriting 100k files a minute).
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Upload interrupted | Some blocks stored, no commit | Commit lists the missing blocks; resume from there; orphan blocks are GC’d after a grace period |
| Two devices edit the same revision | Second commit rejected | Conflicted copy; never last-writer-wins for user files |
| Client crashes mid-download | Half-written file | Temp file + fsync + atomic rename; cursor saved only after apply |
| Notifier down | Changes still committed, devices don’t hear | Clients fall back to polling list_changes every minute or so |
| Metadata shard down | Commits for those namespaces fail | Replicated primary with failover; clients queue local changes and retry |
| Clock skew on devices | Wrong “newest” if comparing mtimes | Never order by device clocks; order by server revision |
| A client bug deletes files | Mass deletes sync everywhere | Version history and trash; detect bulk deletes and ask before propagating |
| Hash collision | Wrong content served | SHA-256 makes it negligible; verify hash on upload |
| Garbage collector races an upload | A just-uploaded block deleted | Grace period before deleting unreferenced blocks |
What it costs
Section titled “What it costs”| Operation | Time | Space / transfer |
|---|---|---|
| Chunk + hash a file of n bytes (client) | O(n), ≈ 1 GB/s per core | O(n / chunk) hashes in the local DB |
| Commit | O(k) for k block hashes: one DB transaction + one existence check per hash | one revision row with k hashes (32 B each) |
| Upload an edit | O(changed chunks) | ≈ chunk size per changed chunk, not file size |
| list_changes from a cursor | O(entries since cursor), paged | — |
| Notify | O(waiting devices) per namespace change | one idle connection per online device |
| Restore a version | O(1) metadata write | no bytes move |
| Storage | — | unique chunks × (1 + erasure-coding overhead, ≈ 1.2-1.5×) + metadata |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). File sizes, devices per user, sharing, version history, what to do on concurrent edits, encryption.
- Split metadata from bytes (10 min). Chunks by hash in a blob store, revisions in a metadata DB, API servers that never carry file data, presigned URLs.
- Sync protocol (15 min). Commit with base revision, “need these blocks”, journal + cursor, long-poll notifications, pull loop, atomic apply, conflicted copies.
- Efficiency (10 min). Fixed vs content-defined chunking, dedupe scope, small files, resumable uploads.
- Stretch (5 min). Shared folders and fan-out, garbage collection, hot namespaces, offline for a month.
Follow-ups to expect: “Why not rsync?” rsync computes a delta between two copies with a rolling checksum, which needs both sides online for the session; content-addressed chunks let any device, at any time, ask the server “which of these do you have”. “Why not merge conflicts automatically?” You can only merge formats you understand; for anything else, keeping both is the only way to lose nothing. “How do you test it?” A model-based fuzzer: random interleavings of edits, renames, deletes, crashes and network drops across simulated devices, then assert all devices converge and no revision was lost (Dropbox describes testing its rewritten sync engine this way).
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Muthitacharoen, Chen, Mazières, A Low-bandwidth Network File System (SOSP 2001): content-defined chunking with Rabin fingerprints and chunk-level dedupe, the idea under modern sync.
- Xia et al., FastCDC: a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication (USENIX ATC 2016): gear-hash chunking, much faster than Rabin.
- Dropbox Tech: Rewriting the heart of our sync engine: the three-tree (local, remote, synced) model, and why sync engines are hard to get right and to test.
- Tridgell, Mackerras, The rsync algorithm: the rolling weak checksum plus strong hash, the session-based alternative to content-addressed chunks.
Concept pages to drill: Rolling hash · Hash map · Versioning · Snapshots · Idempotency · Event-driven · File paths