Design File Sync

The 30-second version

You've used one: a "cloud drive" folder on your laptop, phone and the web. Save a file on the laptop, and a few seconds later the phone has it. Edit it on a plane, and it syncs when you land. That looks simple, but files can be gigabytes, networks drop, and two devices can edit the same file while both are offline.

The five ideas this page builds

1. Split metadata from content (§04). File names and versions go in a database; the bytes go in cheap Object storageObject storageA cloud service that stores files ("objects") by key in buckets over HTTP, cheaply and almost without limit (Amazon S3, Google Cloud Storage). Not a disk you mount..
2. Cut files into chunks (§05). Edit one paragraph of a 2 GB video project, and only the chunk around it changes. Upload that, not 2 GB.
3. Name each chunk by its hash and store it once (§06). Identical chunks, in old versions, copies or other files, are kept once.
4. Upload what's missing, then commit (§07–§08). Ask "which of these chunks do you lack?", send those, then make the new version visible in one step. Other devices learn about it from a change log.
5. Never silently lose an edit (§09–§11). When two devices edit the same file offline, notice it and keep both versions.

What are we building?

Requirements come in two kinds. Functional ones describe what a user can do. Non-functional ones describe how well the system does it: how fast, how reliable, how cheap. The second list is usually where the hard design problems hide.

Functional: what a user can do

• Sync a folder. Put a file in the folder on one device, and it appears on all the user's other devices. Edits and deletes sync the same way.
• Large files. A 10 GB video must work, on a phone connection too.
• Offline edits. Edit files with no network. They sync when the device reconnects, and the system must notice when two devices edited the same file meanwhile (§09).
• Version history. See and restore older versions of a file, say for the last 30 days. This also rescues people from accidental deletes and ransomware.
• Sharing (stretch goal). Share a folder with another user, so it syncs into their account too. We'll mark where sharing changes the design (§10), but won't build it fully.

Out of scope, and worth saying out loud: real-time co-editing of documents (that's a different product, closer to chat), search inside files, and photo galleries.

Non-functional: how well

A note on "the same everywhere"

How quickly must devices agree? Not instantly. If the phone shows the old file for five seconds after the laptop saves, nobody minds. That's Eventual consistencyEventual consistencyA promise that if writes stop, every copy or derived view of the data (replicas, caches, read models, other services) will end up agreeing — but for a while, different readers may see different (stale) versions.: copies may differ for a short while, but they converge once changes stop. What we must never do is end up with devices that disagree forever, or quietly drop one of two edits. Keep those two promises apart; the rest of the design depends on it.

How big is it? A rough estimate

All numbers below are approximate and invented for a mid-sized cloud drive. They're not any real company's figures. Being within 10× is good enough: we only want to know which numbers are scary.

Step 1: the inputs

• 10 million users. On a given day 20% of them change something: 2 million daily active users.
• Each user has 1,000 files averaging 1 MB. (A few huge videos, lots of small documents.)
• Each active user changes 10 files a day. Thanks to chunking (§05), each change uploads about 1 MB on average.
• Each user has 3 devices, so every change must be downloaded by 2 other devices.
• Identical chunks are stored once (§06). Assume that saves a third: a dedup ratioDedup ratioLogical bytes (what users think they store) divided by physical bytes (what's really on disk after deduplication). A ratio of 1.5 means 15 TB of user files fit in 10 TB of storage. of 1.5.
• Old versions are kept 30 days. The busiest hour is about 3× the daily average.

Step 2: storage

What users think they store: 10,000,000 users × 1,000 files × 1 MB = 10,000,000,000 MB = 10 PB (1 PB = 1,000 TB = 1,000,000 GB).

After deduplication: 10 PB ÷ 1.5 ≈ 6.7 PB.

Version history: each day, new bytes arrive: 2,000,000 users × 10 changes × 1 MB = 20,000,000 MB = 20 TB a day. Kept 30 days: 20 TB × 30 = 600 TB.

So we store about 7.3 PB of unique data, before the blob store makes its own spare copies to survive broken disks (§10). That's far more than any one machine holds, so the bytes go into Object storageObject storageA cloud service that stores files ("objects") by key in buckets over HTTP, cheaply and almost without limit (Amazon S3, Google Cloud Storage). Not a disk you mount., which is built for exactly this.

Step 3: requests and bandwidth

Commits (one per changed file): 2,000,000 × 10 = 20,000,000 a day. 20,000,000 ÷ 86,400 seconds ≈ 230 commits/s on average, ≈ 700/s at peak.

Upload bandwidth: 20 TB a day ÷ 86,400 s ≈ 230 MB/s. Multiply by 8 for bits: ≈ 1.9 Gbit/s on average, ≈ 5.6 Gbit/s at peak.

Download bandwidth: every change goes to 2 other devices, so 40 TB a day ≈ 3.7 Gbit/s on average, ≈ 11 Gbit/s at peak.

Waiting devices: 2,000,000 active users × 3 devices = 6,000,000 devices. If about half are online at once, that's 3 million open connections waiting to hear "something changed" (§08).

Step 4: metadata

Files: 10,000,000 users × 1,000 files = 10 billion file records. At roughly 300 bytes each (the path and IDs, plus the current version's row with its chunk list) that's 10,000,000,000 × 300 B = 3 TB.

Old versions: 20,000,000 new versions a day × 30 days = 600 million rows. At about 200 bytes each ≈ 120 GB.

Chunk index (one row per unique chunk, §06): most files are smaller than one chunk, so roughly one chunk per file, minus dedup: 10 billion ÷ 1.5 ≈ 7 billion rows × ~80 bytes ≈ 560 GB.

Change log (§08), kept 90 days: 20,000,000 a day × 90 = 1.8 billion rows × ~40 bytes ≈ 72 GB.

Total: 3 TB + 120 GB + 560 GB + 72 GB ≈ 3.75 TB, call it 4 TB of metadata. That fits on a few large database servers, but not comfortably on one, and every commit writes to it.

Play with the inputs

Try a dedup ratio of 3 (lots of shared files in a company), or keep history for 365 days, and watch which number grows fastest.

Version one: split metadata from bytes

The naive first try

The very first idea is "upload the file to the server, and the server saves it on its disk under the user's folder". It works for a demo. Then it fails every requirement from §02: editing one line of a 1 GB file re-uploads 1 GB, a dropped connection restarts from zero, the server's one disk is a single point of failureSingle point of failure (SPOF)One component that, if it breaks, takes the whole system down with it — because everything depends on it and nothing can take its place., and two copies of the same file take twice the space.

The fix starts with noticing that a "file" is really two different kinds of data.

Two kinds of data, two homes

A database is great at small rows that change together, and bad at storing gigabytes of video. An object storeObject storageA cloud service that stores files ("objects") by key in buckets over HTTP, cheaply and almost without limit (Amazon S3, Google Cloud Storage). Not a disk you mount. (Cloud Basics: managed services) is the opposite: it holds unlimited bytes cheaply and keeps several copies for durability, but it can't do "update these three things together or not at all". So each gets the job it's good at.

Chunks are immutableImmutableCan't be changed after it's created. To “change” an immutable value you make a new one. Immutable objects can be shared freely, because nobody can modify them under you.: once written, a chunk's bytes never change. Editing a file creates new chunks and a new list; the old ones stay for version history. Immutable data is easy to copy, cache and keep durable, because there's never an "old copy" that's out of date.

The sync client, the app on each device, does more work than you might think. It watches the folder for changes, cuts files into chunks, hashes them, and keeps a small local database of "which chunks make up which file" so it can tell what changed without asking the server.

The data model

Here's the metadata schema, in SQL for Postgres. Read the comments first; the details come back in later sections.

CREATE TABLE namespaces (            -- one folder tree, e.g. "Ana's files"
  id       bigint PRIMARY KEY,
  last_seq bigint NOT NULL DEFAULT 0 -- newest change-log number (§08)
);

CREATE TABLE files (
  id              bigserial PRIMARY KEY,
  namespace_id    bigint  NOT NULL REFERENCES namespaces(id),
  path            text    NOT NULL,           -- "/Reports/q3.pdf"
  current_version int     NOT NULL,
  deleted         boolean NOT NULL DEFAULT false, -- a tombstone (§11)
  UNIQUE (namespace_id, path)
);

CREATE TABLE file_versions (
  file_id    bigint      NOT NULL REFERENCES files(id),
  version    int         NOT NULL,            -- 1, 2, 3… per file
  size       bigint      NOT NULL,
  chunks     text[]      NOT NULL,            -- ← the manifest: chunk hashes in order
  created_at timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (file_id, version)
);

CREATE TABLE chunks (                -- which chunks the blob store really has
  hash       text        PRIMARY KEY,  -- SHA-256, as 64 hex characters
  size       int         NOT NULL,
  object_key text        NOT NULL,     -- where the bytes are in the object store (§12)
  last_used  timestamptz NOT NULL DEFAULT now() -- for safe garbage collection (§12)
);

CREATE TABLE changes (               -- the change log (§08)
  namespace_id bigint NOT NULL,
  seq          bigint NOT NULL,      -- 1, 2, 3… per namespace
  file_id      bigint NOT NULL,
  version      int    NOT NULL,
  op           text   NOT NULL,      -- 'put' or 'delete'
  PRIMARY KEY (namespace_id, seq)
);

A namespaceNamespaceOne folder tree with its own history: usually “everything in Ana's account”, or one shared folder. Paths, versions and the change log are all counted per namespace, which also makes it a natural unit to shard by. is one folder tree with its own history, usually "one user's files" (later, also "one shared folder"). Almost every query is scoped to a single namespace: list my folder, give me my changes. Remember that; it decides how we split the database in §10.

Chunking: fixed-size vs content-defined

ChunkingChunking (files)Splitting a file into pieces (say 4 MB each) that are hashed, uploaded and stored separately. Only changed chunks need re-uploading, identical chunks are stored once, and a failed upload resumes from the last chunk. gives us three things at once. Upload only what changed: re-send the chunks that differ. Resume: after a dropped connection, continue from the next chunk. Store once: identical chunks are kept a single time (§06). Everything depends on one property: a small edit should change few chunks.

Fixed-size chunks, and the one-byte problem

The obvious way is to cut every N bytes: the first 4 MB are chunk 1, the next 4 MB are chunk 2, and so on. If you overwrite a few bytes in the middle, only the chunk containing them changes. Great.

Now insert one byte at the start, like a word added to the first line of a document. Every byte moves one position to the right. Chunk 1 now ends one byte earlier in the old content, chunk 2 starts one byte earlier, and so on: every chunk's bytes are different, so every hash is different, so the whole file uploads again.

Content-defined chunking

"Cut after every space" only works for text, and gives tiny chunks. Content-defined chunkingContent-defined chunking (CDC)Choosing chunk boundaries by looking at the bytes themselves (“cut wherever the last few bytes hash to a special value”) instead of every N bytes. An edit then only moves the boundaries next to it, so the other chunks keep their hashes. generalizes it to any bytes:

1. Slide a small window (say the last 48 bytes) along the file, one byte at a time.
2. At each position, compute a hash of just the bytes in the window.
3. If the hash matches a pattern that happens about once every N positions (for example "the top 12 bits are all zero", true about 1 time in 4,096), cut here.

The decision at each position depends only on the bytes in the window. Insert a byte at the start, and the windows further along still contain the same bytes as before, so they make the same decisions: the cut points move along with the content. Only the chunks around the edit change. In effect the file grows its own "spaces".

The average chunk size is set by the pattern: "the top k bits are zero" happens about once every 2^k positions. 12 bits gives chunks of about 4 KB (2¹² = 4,096 bytes); about 22 bits gives about 4 MB (2²² = 4,194,304).

Recomputing a 48-byte hash at every one of a billion positions would be slow. A rolling hashRolling hashA hash of the last few bytes (a sliding window) that can be updated in one cheap step as the window moves forward by one byte: add the new byte, subtract the one that fell out. It lets a chunker test every position in a file quickly. makes each step cheap: when the window moves forward one byte, add the new byte and subtract the one that fell out, instead of hashing the whole window again.

Two guard rails make real chunkers practical. A minimum size stops the chunker from cutting twice in a row and making 3-byte chunks. A maximum size forces a cut in boring data, such as a long run of zeros, where the pattern might never appear.

The minimum size has a side effect you can see in the lab: a cut is skipped if it's too close to the previous cut, so each cut depends a little on the one before. After an edit, the next few chunks can change before a cut lands in exactly its old place and everything lines up again. Still far better than "every chunk after the edit".

A chunker you can run

This program chunks a short text both ways, inserts one byte at the start, and counts how many of the new chunks were already stored. Chunk sizes are tiny so the output is readable; the logic is the same at 4 MB.

package main

import (
	"crypto/sha256"
	"fmt"
)

const (
	window  = 8  // the rolling hash looks at the last 8 bytes
	minSize = 16 // never cut a chunk shorter than this…
	maxSize = 96 // …and always cut by this length
)

// cdcChunks cuts data wherever the hash of the last `window` bytes
// has its top 4 bits all zero: about 1 position in 16.
func cdcChunks(data []byte) [][]byte {
	var pow uint32 = 1 // 31^window, used to drop the oldest byte
	for range window {
		pow *= 31
	}
	var chunks [][]byte
	var h uint32
	start := 0
	for i, b := range data {
		h = h*31 + uint32(b) // add the newest byte…
		if i >= window {
			h -= pow * uint32(data[i-window]) // …and remove the oldest one
		}
		size := i + 1 - start
		if (size >= minSize && h>>28 == 0) || size >= maxSize {
			chunks = append(chunks, data[start:i+1]) // ← boundary depends only on nearby bytes
			start = i + 1
		}
	}
	if start < len(data) {
		chunks = append(chunks, data[start:])
	}
	return chunks
}

func fixedChunks(data []byte, size int) [][]byte {
	var chunks [][]byte
	for len(data) > size {
		chunks = append(chunks, data[:size])
		data = data[size:]
	}
	return append(chunks, data)
}

func report(name string, v1, v2 [][]byte) {
	stored := map[[32]byte]bool{}
	for _, c := range v1 {
		stored[sha256.Sum256(c)] = true
	}
	reused := 0
	for _, c := range v2 {
		if stored[sha256.Sum256(c)] {
			reused++
		}
	}
	fmt.Printf("%-16s v2 has %d chunks, %d already stored → upload %d\n",
		name, len(v2), reused, len(v2)-reused)
}

func main() {
	v1 := []byte("Meeting notes. Ana will ship the sync client on Friday. " +
		"Ben is fixing the upload retry bug. Chen asked about quotas for " +
		"shared folders. Next meeting: Tuesday at ten, same room as last week.")
	v2 := append([]byte("!"), v1...) // insert ONE byte at the very start

	report("fixed (32 B):", fixedChunks(v1, 32), fixedChunks(v2, 32))
	report("content-defined:", cdcChunks(v1), cdcChunks(v2))
}

Output (Go 1.24 and Node 22 print the same):

fixed (32 B):    v2 has 6 chunks, 0 already stored → upload 6
content-defined: v2 has 8 chunks, 7 already stored → upload 1

How big should a chunk be?

There's a trade-off. A 1 GB file makes 1 GB ÷ 4 MB = 256 chunks at 4 MB, or 1 GB ÷ 64 KB = 16,384 chunks at 64 KB (counting in powers of two here, 1 GB = 1,024 MB, so the numbers come out round). Smaller chunks find more duplicates and re-upload less after an edit, but they mean 64× more hashes to send, more rows in the chunk index, and more requests to the blob store. Most designs land on chunks of hundreds of KB to a few MB. One public data point: Dropbox's API documents a content_hash built from fixed-size 4 MiB blocks (4,194,304 bytes), each hashed with SHA-256 (Dropbox developer docs, "Content hash"). That's a fixed-size scheme for a checksum; it says nothing about whether their sync uses content-defined chunks.

Hashing and deduplication

A chunk's name is its fingerprint

A SHA-256SHA-256The standard cryptographic hash function today: it turns any data into a 32-byte (64 hex characters) fingerprint, and changing one byte of the input changes the fingerprint completely. Part of the SHA-2 family (2001); no practical attacks are known. hash turns any bytes into a 32-byte fingerprint. Same bytes, same fingerprint; change one byte, and the fingerprint is completely different. (You may know the same trick as a Content hashContent hashA fingerprint computed from data's contents (usually with a hash function like SHA-256) and used as its name or ID. Same contents → same hash, so it works for cache-busting file names like index-DbfMV5Es.js, and for storing identical file chunks only once. in build tools; here we apply it to chunks instead of whole files.) For the background on hash functions and why SHA-256 is safe to rely on, see Crypto Basics: hashes.

Storing data under a key that is its hash is called content-addressed storageContent-addressed storageStoring data under a key computed from the data itself (its hash) instead of a name you choose. The same bytes always get the same key, so duplicates are found for free, and a reader can check that what it got matches the key.. (The object store's physical key will get an extra upload ID in §12, for safe deletes; the hash stays the chunk's name everywhere else.) It gives us three things for free:

• Duplicates find themselves. Before storing a chunk, look up its hash. Already there? Don't store it again.
• Corruption is detectable. Whoever reads chunk e76d… can hash the bytes they got and check the result is e76d… (§11).
• Chunks never need updating. A changed chunk has a new hash, so it's a new object. Nothing is ever overwritten, which is why chunks are immutable (§04).

A file version is then just a manifestManifest (chunk list)The ordered list of chunk hashes that make up one version of a file, e.g. [e76d…, 7362…, c358…]. To rebuild the file, fetch each chunk by its hash and glue them together in order.: the list of its chunk hashes, in order. Git stores files the same way: see Git Internals.

Store once: a tiny deduplicating store

This program saves three files into a store keyed by SHA-256: a note, an edited copy of it, and an exact copy. Watch the "new" count.

package main

import (
	"crypto/sha256"
	"encoding/hex"
	"fmt"
)

const chunkSize = 16 // real systems use ~4 MB; tiny here so we can see it

// store maps a chunk's hash to its bytes: each unique chunk is kept once.
var store = map[string][]byte{}

// save splits a file into chunks, stores the new ones,
// and returns the file's manifest: the list of chunk hashes.
func save(name string, file []byte) []string {
	var manifest []string
	added := 0
	for start := 0; start < len(file); start += chunkSize {
		chunk := file[start:min(start+chunkSize, len(file))]
		sum := sha256.Sum256(chunk)
		key := hex.EncodeToString(sum[:])
		if _, ok := store[key]; !ok { // ← dedup: skip chunks we already have
			store[key] = chunk
			added++
		}
		manifest = append(manifest, key[:8]) // short prefix, for printing
	}
	fmt.Printf("%-8s %d chunks, %d new  %v\n", name, len(manifest), added, manifest)
	return manifest
}

func main() {
	v1 := []byte("Dear team, the offsite is on May 4. Bring a laptop.")
	v2 := []byte("Dear team, the offsite is on May 4. Bring a jacket.")
	save("v1", v1)
	save("v2", v2)   // same start, new ending
	save("copy", v1) // an identical file: nothing new to store
	fmt.Println("unique chunks stored:", len(store))
}

Output (Go 1.24 and Node 22 print the same):

v1       4 chunks, 4 new  [e76d12da 7362214a 6ef382a2 fa50339d]
v2       4 chunks, 2 new  [e76d12da 7362214a c3585e52 86f8e976]
copy     4 chunks, 0 new  [e76d12da 7362214a 6ef382a2 fa50339d]
unique chunks stored: 6

Three files, twelve chunks in their manifests, but only six stored. The edited version shares its first two chunks with the original; the copy shares all four.

How far should dedup reach?

DeduplicationDeduplication (storage)Keeping only one copy of data that appears many times. In file sync: if a chunk with the same hash is already stored, by an older version, another file or another user, don't store or upload it again; just point at the existing copy. can work at three widening scopes:

1. Across versions of one file. Version 8 reuses the chunks of version 7 it didn't change. This is the big, safe win; it's what makes 30 days of history affordable.
2. Across one user's files. The same PDF saved in two folders, or a renamed file, costs nothing. Also safe.
3. Across all users. A popular installer or a viral video is stored once for everyone. Biggest savings, but it has a cost.

The catch with cross-user dedup

If the server tells clients "you don't need to upload chunk X, we already have it", then anyone can ask whether anyone else has stored chunk X. That's a side channelSide channelInformation that leaks through how a system behaves rather than through what it returns: timing, size, or whether something happened. For example, “this upload finished instantly” can reveal that someone else already stored the same file.: information leaks through behaviour (an upload that finishes instantly) instead of through an answer.

A concrete attack: a document template is known except for one field, say a 4-digit PIN in a bank letter. An attacker builds all 10,000 versions and uploads each one. The version that "uploads instantly" is the one the victim stored. This was described in "Side Channels in Cloud Services: Deduplication in Cloud Storage" (Harnik, Pinkas and Shulman-Peleg, IEEE Security & Privacy, 2010).

Common defences, each with a cost:

• Dedup only within one user (or one company account) on the client-visible path. You lose the cross-user savings in bandwidth.
• Dedup cross-user on the server side only. The client always uploads; the server quietly keeps one copy. Saves storage, not bandwidth, and leaks nothing through timing.
• Make clients prove they have the file, not just its hash, before skipping an upload: proof of ownershipProof of ownershipA short exchange in which a client proves it really has a file's bytes (for example by answering questions about random parts of it), not just its hash, before the server lets it skip the upload. It stops “I know the hash, so give me credit for the file” tricks.. More complex.

Uploading: ask, send what's missing, commit

The protocol, step by step

Say you edit report.pdf on your laptop. It was version 7: chunks A B C D. Your edit changed the third chunk and added one at the end.

1. Chunk and hash locally. The client cuts the new file into chunks (§05) and hashes each one: A B C′ D E. It needs no network for this.
2. Ask what's missing. POST /chunks/check with the five hashes. The server looks them up in its chunks table and answers: missing C′ and E.
3. Upload the missing chunks. PUT each one. The receiver recomputes the SHA-256 of the bytes and rejects them if it doesn't match the hash the client claimed. Only then is the hash added to the chunks table. (In version one the API server receives the bytes and does both; with direct uploads, below, the work is split.)
4. Commit. POST /files/commit with { path: "report.pdf", base_version: 7, chunks: [A, B, C′, D, E] }. The server makes version 8 real, in one Database transactionDatabase transactionA group of database changes that happen all together or not at all (COMMIT keeps them, ROLLBACK undoes them). How much other users can see or interfere with the half-done state depends on the isolation level..
5. Tell the other devices. The commit added a line to the change log; other devices hear about it and download only C′ and E (§08).

Step through it, then turn on connection drops to see the upload survive a dead network.

1async function save(path, file, baseVersion) {
2  const chunks = cdcChunks(file);          // §05
3  const hashes = chunks.map(sha256);       // §06
4  for (;;) {                               // loop = resume after a drop
5    try {
6      const { missing } = await api.checkChunks(hashes);
7      for (const h of missing) {
8        await api.putChunk(h, chunks[hashes.indexOf(h)]);
9      }
10      return await api.commit({ path, baseVersion, hashes });
11    } catch (err) {
12      if (!isNetworkError(err) && !err.missingChunks) throw err; // 409 → §09
13      await sleepWithBackoff();            // then ask again (missing: §12)
14    }
15  }
16}

Why the commit must be atomic

Steps 1–3 can take minutes for a big file, and the network can die at any moment. That's fine, because nothing in steps 1–3 is visible to anyone. Uploaded chunks are just anonymous blobs; no file points at them yet. Only the commitCommit (a version)The single step that makes a new file version real: one database transaction that checks the chunks exist and the base version is still current, writes the new version and adds a change-log entry. Before it, nobody sees the new version; after it, everyone can. changes what users see, and it changes everything at once.

Here's the commit as one database transaction. If any check fails, ROLLBACK undoes everything, and the old version stays current.

BEGIN;

-- 1. Lock the file's row, and check the client edited the newest version.
SELECT id, current_version FROM files
 WHERE namespace_id = 42 AND path = '/report.pdf'
   FOR UPDATE;                        -- ← other commits to this file now wait
-- app: if current_version = 8 and v8's chunks equal the request's chunks,
--      this is a retry of a commit that already worked: ROLLBACK, answer success.
-- app: else if current_version <> 7 (the client's base_version):
--      ROLLBACK and answer 409 Conflict (§09)

-- 2. Check every chunk in the manifest is really stored, and lock it (§12).
UPDATE chunks SET last_used = now() WHERE hash = ANY($1);  -- $1 = the 5 hashes
-- app: if fewer rows updated than distinct hashes: ROLLBACK, "upload these first"

-- 3. Write the new version and point the file at it.
INSERT INTO file_versions (file_id, version, size, chunks)
VALUES (1001, 8, 3145728, $1);
UPDATE files SET current_version = 8 WHERE id = 1001;

-- 4. Append to the change log with the namespace's next sequence number.
UPDATE namespaces SET last_seq = last_seq + 1 WHERE id = 42
RETURNING last_seq;                   -- say it returns 57
INSERT INTO changes (namespace_id, seq, file_id, version, op)
VALUES (42, 57, 1001, 8, 'put');

COMMIT;                               -- ← the moment version 8 exists

A brand-new file has no row to lock yet. Its commit INSERTs the files row with version 1 instead; if two devices create the same path at once, the second INSERT hits the UNIQUE (namespace_id, path) rule, and the server turns that error into the same 409 Conflict.

Because it's all one transaction, the ACIDACIDThe four guarantees of a database transaction: Atomic (all or nothing), Consistent (rules hold), Isolated (concurrent transactions don't see each other's half-done work), Durable (once committed, it survives a crash). guarantees from Transactions apply. A crash before COMMIT leaves no trace: no half-written version, no change-log line pointing at nothing. The base_version check is a form of Optimistic concurrencyOptimistic concurrencyLetting two clients edit without locking, but rejecting a write if the resource changed since the client read it: the client sends If-Match with the ETag it saw, and the server answers 412 Precondition Failed if it no longer matches.: don't lock while the user edits for an hour; just refuse the commit if someone else got there first. (HTTP APIs often do the same with an ETag and 412; here it's a version number and 409.)

Resumable uploads

The chunk is already a natural unit of resume: after a drop, the client simply asks again which chunks are missing. The server's chunks table is the source of truth, so the client doesn't need to remember anything reliable about what it sent. That's a Resumable uploadResumable uploadAn upload that can continue where it stopped after a dropped connection, instead of starting over. The server remembers which chunks or bytes already arrived. at chunk level.

With 4 MB chunks, losing a half-sent chunk wastes at most 4 MB. For bigger pieces, or very slow links, uploads can also resume within a chunk: the client opens an upload session, the server remembers how many bytes arrived, and after a drop the client asks "what offset do you have?" and continues from there. The open protocol tus works this way. The IETF is working on the same idea for plain HTTP: as of October 2026, "Resumable Uploads for HTTP" (draft-ietf-httpbis-resumable-upload) is still an Internet-Draft, not yet an RFC.

Downloading is the mirror image

When the phone learns that report.pdf is now version 8 (§08), it:

1. Fetches the manifest: A B C′ D E.
2. Compares it with its local chunk index, a small database of "which chunks I already have on disk, and where". It already has A, B and D from version 7.
3. Downloads only C′ and E, and checks each one's hash.
4. Writes the new file to a temporary file, then does an atomic renameAtomic renameReplacing a file by writing the new contents to a temporary file, then renaming it over the old one. On the same disk the rename happens all at once, so other programs see either the whole old file or the whole new one, never half. over report.pdf. An app reading the file sees either the whole old version or the whole new one, never a half-written mix.

Hearing about changes: change log and cursors

The change log

In §07 the commit wrote a row to the changes table with the namespace's next sequence number. Together those rows form the change logChange log (journal)An append-only list of every change in a namespace, each with an increasing sequence number: “#41 put /notes.txt v3”, “#42 delete /old.pdf”. Devices read it from their last position to learn what changed.: an append-only list of everything that happened in one folder tree, in order.

Because numbers only go up, a device needs just one number to know where it is: its cursorSync cursorA device's bookmark in the change log: “I have applied everything up to #41.” It asks for changes after its cursor, applies them, then moves the cursor forward. A device that was off for a week resumes from its cursor., "I've applied everything up to 55". To catch up, it asks for the rest:

SELECT seq, file_id, version, op
  FROM changes
 WHERE namespace_id = 42 AND seq > 55   -- ← "after my cursor"
 ORDER BY seq
 LIMIT 1000;                            -- page through big backlogs

Over HTTP that's GET /changes?cursor=55, answered with the changes plus the new cursor (57) and a has_more flag. The device applies each change (downloading chunks as in §07) and only then saves the new cursor. If it crashes halfway, it re-reads from the old cursor and re-applies a few changes, which is harmless because applying "put report.pdf v8" twice gives the same result. This is the same idea as cursor paginationCursor (pagination)An opaque token the server hands out with each page that means “continue after here”. The client sends it back unchanged to get the next page; only the server knows what's inside (often the last row's sort key). in an API, and the same shape a chat app uses to catch up on missed messages.

A laptop that was closed for a week works exactly like one that was off for a second: it sends its old cursor and gets a longer list.

Nudging devices: don't make them poll

How does the phone know it's time to ask? It could ask every few seconds, plain PollingPollingChecking a condition again and again, with a short pause in between, until it becomes true or a deadline passes. Slower than being told when something happens, but works when nothing tells you., but 3 million devices asking every 5 seconds is 600,000 requests a second, nearly all answering "nothing new". Two better options from WebSockets: choosing:

• Long pollingLong pollingThe client asks “anything new?” and the server holds the request open until it has news (or a timeout passes), then answers. The client immediately asks again. News arrives almost at once.: the device asks "anything after 57?" and the server holds the request open until there is something, or 60 seconds pass. Works through any proxy or firewall.
• A WebSocketWebSocketA long-lived two-way connection between browser and server, used for chat and live updates. It starts as a normal HTTP request, then the server takes over (“hijacks”) the raw connection. or similar long-lived connection: the server pushes a message the moment a commit lands.

Either way, the message is only a nudgeNudge (sync notification)A tiny message from the server that says only “something changed, go look”, with no file data. The device then reads the change log itself, so a lost nudge delays a sync but never loses a change.: "namespace 42 changed, go look". It carries no file data. The device then reads the change log as above.

Dropbox's public HTTP API exposes this exact shape, per its developer documentation: files/list_folder/continue takes a cursor and returns changes plus a new cursor, and files/list_folder/longpoll blocks until something changes after a cursor.

Conflicts: two devices edit offline

How a conflict happens

Ana's shopping list is at version 1 on the server, her laptop and her phone. She takes the laptop on a train with no signal and adds "eggs". Meanwhile at home, her phone (online) gets "bread" added by her partner. Now:

• The phone commits first: base version 1, server is at 1, so it's accepted as version 2.
• The laptop reconnects and tries to commit "eggs" with base version 1. But the server is at 2.

That mismatch is the whole detection mechanism. The base versionBase versionThe version of a file a device started editing from. When the device uploads, it says “this edit is based on version 7”. If the server is still on 7, the edit simply comes next; if it has moved on, two edits happened in parallel: a conflict. says "I started from 1"; the server says "1 is no longer the latest". The commit transaction from §07 refuses it with 409 Conflict, the HTTP status that means "your change clashes with the current state". No clocks involved: the server has a single, ordered history per file, and it simply compares two numbers.

Three ways to resolve it

1. Last writer wins (LWW). Keep whichever edit has the later timestamp; drop the other. Simple and automatic, and it silently destroys an edit. (It's the same rule replicated databases use; see Replication: multi-leader.) With Last write winsLast write wins (LWW)A conflict rule: attach a timestamp to every write and keep the one with the biggest timestamp. Simple, but it silently discards the other write, and clocks on different machines disagree., Ana's "eggs" or the "bread" vanishes and nobody is told.
2. Keep both. Keep the server's version as the file, and save the other edit next to it as a conflicted copyConflicted copyA second file the sync system creates when two devices changed the same file in parallel, e.g. “notes (Ben's laptop's conflicted copy).txt”. Both edits survive; a person decides how to combine them.: list (Ana's laptop's conflicted copy).txt. Nothing is lost; a person merges them later. This is the usual default for general files, because the sync service can't understand a PDF or a spreadsheet.
3. Merge. For formats the system understands, combine the edits. Plain text can use a three-way mergeThree-way mergeCombining two versions of a file by also looking at the common ancestor (the merge base). A change made on only one side is taken automatically; a change both sides made to the same lines is a conflict.: compare both versions with the common base (version 1). Lines only one side changed are taken from that side; if both changed the same line differently, it's a real conflict and you fall back to option 2. Apps that edit together live use CRDTsCRDTConflict-free replicated data type: a data structure (counter, set, text…) designed so concurrent changes can always be merged automatically, in any order, to the same result. (also introduced in Replication: multi-leader), data structures designed so concurrent edits always merge.

Try all three. Take both devices offline, edit on each, and bring them back.

Why timestamps can't decide

LWW needs to know which edit was "last", and the only thing it has is each device's clock. Device clocks are wrong all the time: a laptop whose battery died resets to 2010, a phone set an hour ahead, a desktop that never syncs its time. This difference between machines' clocks is Clock skewClock skewThe difference between two machines' clocks. Even with time sync (NTP) it is often milliseconds, and can be much more after a fault, so timestamps from different machines can't reliably order events.. In the simulator above, push device B's clock ahead and its edits win every LWW contest, even ones it made earlier.

There's a deeper problem, explained in Clocks: vector clocks. Two offline edits don't have an order at all: neither device knew about the other's edit. They're concurrent. A timestamp forces a fake order onto them, and whichever edit loses the coin toss is gone. What you want to know is not "which came later?" but "did one of these edits know about the other?" The base version answers exactly that.

Two special cases

• Edit vs delete. The laptop deleted notes.txt while the phone edited it. Most designs keep the edited file: losing an edit is worse than an unwanted file coming back, which the user can delete again.
• Renames and moves. If a file is identified only by its path, "rename A to B" looks like "delete A, create B", and an edit to A on another device turns into a conflict with nothing. Giving every file a stable file ID (our files.id) and treating the path as a changeable attribute lets the system apply the rename and the edit together.

What breaks at 10× and 100×

Drag the slider and watch boxes appear. The red box is the one that breaks next.

1. Bytes off the API servers

At first the API server receives chunk bytes and writes them to the object store. At a few Gbit/s of uploads (§03), API servers spend all their time copying bytes. Fix: hand the client a presigned URLPresigned URLA link to one object in a bucket with a signature and an expiry time baked in. Whoever holds it can upload or download that one object until it expires, without any cloud credentials of their own. and let it upload straight to the object store (§07). Behind a Load balancerLoad balancerA component that spreads incoming requests or connections across several servers, so no single one is overloaded and a dead one can be skipped. (how load balancers work), the API servers are now small and statelessStateless serverA server that keeps nothing about a user between requests in its own memory: sessions, carts and uploads live in a shared database, cache or object store. Any instance can serve any request., so you add more as needed.

2. Connections get their own servers

3 million devices holding a long poll or a WebSocket open (§08) is a different job from answering short requests: it's mostly idle memory and open sockets. Put them on dedicated notification servers; Load Balancing: long-lived connections explains why they need different balancing from short requests. When a commit lands, the API publishes "namespace 42 changed" to a Publish/subscribePublish/subscribe (pub/sub)Senders (publishers) emit messages without knowing who receives them; receivers (subscribers) sign up for the kinds of message they care about. The two sides never reference each other directly. channel (a message broker, see Queues), and whichever notification servers hold connections for namespace 42 forward the nudge. See WebSockets: scaling for how that routing works and what happens when a server restarts (all its devices reconnect at once, so add JitterJitterA small random amount added to a delay or timer — a retry wait, a reconnect, a connection's maximum age — so that many clients don't all act at the same instant and stampede a server. to their retries).

3. Shard the metadata by namespace

At a few TB and hundreds of commits a second, one database becomes the bottleneck. Split it with sharding: pick a shard key so that each request touches one shard.

The namespace is the natural key. A commit touches the file row, its versions, the change log and the namespace's sequence counter, and all of them belong to one namespace. Put the whole namespace on one shard and the commit stays a simple, single-database transaction. "List my folder" and "changes since cursor N" also hit one shard.

The chunk index is different: it's keyed by hash, and hashes are spread evenly, so shard it by hash. The commit's "do these chunks exist?" check now asks other shards, but that's just a read of immutable facts (a chunk, once stored, stays until garbage collection, §12), so no cross-shard transaction is needed.

Reads that can be a little behind, like "changes since cursor N", can go to read replicas. A lagging replica just returns fewer changes this time; the cursor guarantees the device picks up the rest on its next read.

4. The storage bill

Past a few PB, money matters more than machines. Three levers:

• Dedup (§06) and a sensible history policy: 30 days of versions cost 600 TB in our estimate; 365 days would cost about 7 PB, as much as all current files.
• Erasure codingErasure codingA way to survive lost disks with less extra space than full copies: split data into k pieces, compute m extra “parity” pieces, and store all k + m on different disks. Any k of them rebuild the data. 6 + 3 survives 3 losses for 1.5× the space, versus 3× for three copies. instead of full copies inside the blob store: survive as many lost disks or more for about 1.5× the space instead of 3× (6 + 3 survives any 3 lost pieces; 3 full copies survive 2).
• Cold storageCold storageA cheaper storage tier for data that's rarely read, such as old file versions: costs much less per GB per month, but reads are slower or cost extra. Hot storage is the opposite. for old versions and files nobody opened in a year. Reads get slower, but most of them never happen.

5. Many regions

At 100× and beyond, users on other continents want low latency, and some countries require data to stay inside their borders. Give each user a home regionHome regionIn a system running in several geographic regions, the one region that owns a given piece of data (e.g. all of customer 42's keys). Requests for it are routed there so two regions never process the same key at once. where their metadata shard and chunks live. Cross-region dedup becomes a trade-off: either check another region's chunk index (slow) or store a second copy (costly). Most designs simply dedup within a region.

Failure modes: what if X dies?

Pick a failure, then flip between a naive design and this design to see the difference.

The four data failures, in words

A crash in the middle of an upload. The laptop dies after uploading 3 of 5 new chunks. Because only the commit makes a version visible (§07), the server still shows version 7 to everyone. The 3 uploaded chunks are orphans for now: when the laptop restarts, it asks "which are missing?", gets 2 hashes back, and finishes. If it never comes back, garbage collection (§12) removes the orphans later.

A corrupted chunk. A disk flips a bit, or a buggy client uploads wrong bytes. Content addressing catches both. On upload, the server recomputes the SHA-256 and rejects bytes that don't match their hash. On download, the client does the same hash checkHash check (verify on read and write)Recomputing a chunk's SHA-256 and comparing it with the hash it's stored under. A mismatch means the bytes were damaged (or forged), so the chunk is rejected or re-fetched from another copy instead of being given to a user., and on a mismatch fetches the chunk again (the blob store has other copies). The blob store also does scrubbingScrubbingA storage system re-reading its data in the background and checking each piece's checksum, to find and repair silent corruption (bit rot) from another copy before a user ever reads the bad bytes.: re-reading its disks in the background to catch rot before a user does.

A deleted file comes back to life. Ana deletes old.pdf on her laptop. Her tablet, offline for a month, still has it. If the server simply erased the file's row, the tablet's reconnect looks like "I have old.pdf, the server doesn't, so it must be new: upload it". The file is resurrected. The fix is a tombstoneTombstone (deleted file)A record that says “this file was deleted in version 9”, kept instead of erasing the file's row. Without it, a device that was offline during the delete can't tell “deleted on the server” from “new file I made”, and uploads the file again.: the delete is recorded as a new version 9 with an empty manifest and size 0, the files row gets deleted = true, and the change log gets a delete line. The tablet reads "deleted in v9, based on v8", sees that it has v8 unchanged, and deletes its copy. (If it had edited v8 offline, that's the edit-vs-delete conflict from §09, and the edit is kept.)

Tombstones can't be kept forever. Keep them at least as long as change-log entries (§08); a device older than that does a full resync, which compares versions instead of trusting its own leftovers.

A client with its clock in the future. A desktop's clock says 2031. If the server ordered edits by device timestamps, that desktop would win every conflict for five years. This design never uses client clocks for ordering: versions come from the server's counter and conflicts from base_version (§09). Client timestamps are only shown to users, as "modified" dates.

When a component dies

Running it: garbage collection and monitoring

Deleting chunks without deleting someone's file

When version history expires or a user empties their trash, some chunks are no longer listed in any manifest. They should be deleted, or storage grows forever. That's chunk garbage collectionChunk garbage collectionFinding chunks that no file version points at any more and deleting them to free space. Tricky because chunks are shared: a chunk can only go once no version of any file, in any account, still lists it., and it's harder than it looks, because chunks are shared across versions, files and (with cross-user dedup) accounts.

Reference counting, keeping a count per chunk of how many manifests list it, sounds simple. In practice every commit must update counts on chunk-index shards other than its own, a missed decrement leaks a chunk forever, and an extra decrement deletes a chunk that's still in use. That last one is data loss.

Most designs use mark and sweepMark & sweepThe classic tracing algorithm. Mark: walk from the roots and tag every object you reach. Sweep: go through the whole heap and free every object without a tag. instead: periodically walk all live manifests and mark every chunk they list; then sweep (delete) the chunks that weren't marked. Marking billions of manifests takes hours, and uploads keep happening meanwhile. That opens races with the upload protocol, in three orders:

Order 1 is already safe: the commit re-checks that every chunk exists (§07), sees C is gone, and the client re-uploads it. Order 2 is the dangerous one. C is an old orphan: no manifest has listed it for weeks, so the mark phase leaves it unmarked. A client is told "we have C", commits a version that lists C, and only then does the sweep reach C, using a list of unmarked chunks computed before that commit existed. A grace period based on "how long ago was C last referenced" doesn't help: C really was unreferenced for weeks.

Order 3 is about the bytes, not the row. If the object store keeps C's bytes under the key chunks/C (the bare hash), then a client that re-uploads C after the sweep writes to the same key, and the sweep's delayed byte delete then removes the brand-new upload. With a soft delete of several days (below), that window is several days wide.

The fix, in two parts

Part 1: record when each chunk was last promised to someone, and re-check it at delete time. Part 2: never reuse an object key. Each upload of a chunk gets its own key, chunks/<hash>/<upload id>, and the row remembers which key holds the bytes (object_key in the §04 schema). Deleting an old key can then never hit a newer upload.

-- chunks.last_used: when a chunk was last promised to a client.
-- chunks.object_key: where its bytes are, e.g. 'chunks/9f2c…/u-7f3a' (§04).

-- /chunks/check: report which chunks exist, and touch them.
UPDATE chunks SET last_used = now()
 WHERE hash = ANY($1)
RETURNING hash;                     -- present; every other hash is missing

-- Commit, step 2 (§07): touch AND lock every chunk the new version lists.
UPDATE chunks SET last_used = now()
 WHERE hash = ANY($1);
-- app: fewer rows updated than distinct hashes → ROLLBACK, "upload these first"

-- Sweep, once per unmarked chunk.
-- $2 = when this mark phase started, minus a grace period (say 1 day)
DELETE FROM chunks
 WHERE hash = $1 AND last_used < $2 -- ← re-checked at delete time
RETURNING object_key;               -- a row back? queue THIS key for deletion in 7 days

Why that closes all three orders:

• Touched by the check. Once a client is told "we have C", C's last_used is newer than the mark phase's start, so this sweep can't delete it. That covers the minutes the client spends uploading its other chunks.
• Locked by the commit. The commit's UPDATE locks C's row until the transaction ends. If the sweep's DELETE arrives meanwhile, it waits. When the commit finishes, Postgres re-evaluates the WHERE on the updated row, finds a fresh last_used, and deletes nothing.
• Deleted first? Then the commit's UPDATE touches fewer rows than it asked for, so it rolls back and the client re-uploads C (order 1).
• Re-uploaded after the sweep? The new upload gets a new key, chunks/C/u-9b21, and a new row points at it. The delayed delete removes only the old key that the sweep returned, which no row points at any more (order 3).
• Committed before the mark started? Then the mark phase sees the manifest and marks C.

We ran this on Postgres 16 with two sessions, including the shared-lock variant from the callout below (the sweep waited for it the same way). A commit held its transaction open for 2 seconds; the sweep's DELETE waited about 1.5 s for the lock, then reported DELETE 0. In the other order the sweep deleted C and got back its object_key, the commit's UPDATE touched only 1 of its 2 chunks and rolled back, and the re-upload inserted a new row with a different object_key.

Leftover bytes from abandoned uploads (uploaded, never confirmed, so no row) are cleaned up by a separate job driven by upload sessions, not by "no row points at it": for each session that expired more than a day ago without a confirm, it deletes that session's key. That's safe because keys are never reused and the API only confirms an upload while its session is open, an hour at most (§07), so such a key can't get a row any more. Driving it from sessions matters: "delete every object with no row" would also match the keys the sweep just queued and delete them early, defeating the 7-day safety net below.

What to monitor

Use the signals from Observability, but pick ones that match the requirements from §02:

Check yourself

Predict the answer before you click. Q1 is covered in §05, Q2 in §06, Q3 in §07, Q4 in §08, Q5 in §09 and Q6 in §12.

Cheat sheet