How to design a cloud file-storage service

In this lesson, we’ll design a cloud file-sync service. Dropbox, Google Drive, OneDrive, and iCloud Drive are all the same system underneath. Here is the target we’re building toward: edit one cell in a 50 MB spreadsheet and, within about a second, the changed file reappears on every other device you own and every device you’ve shared it with, having moved only the kilobyte that actually changed. By the end you’ll be able to size the byte budget, defend content-defined chunking over fixed blocks, resolve two offline edits without losing either, and name the privacy side channel that cross-user dedup opens.

Four questions carry the whole design, and the second is the one most people skip:

• How many bytes cross the network when a 50 MB file changes by 1 KB, and why.
• Why a file boundary computed from content survives an edit that a boundary computed from position cannot.
• How to resolve a conflict between two devices that both edited while offline, without destroying either edit.
• The privacy side channel that sharing storage across users opens.

The concrete input and output

Input: a change to a file in a folder on one device. Someone edits a cell, renames a document, or drops in a photo.

Output: that same folder, in that same state, on every other device the user owns and every device the file is shared with, within about a second, moving as few bytes as the change can be expressed in.

Underneath, one change produces three artifacts:

1. A list of content hashes describing the file’s pieces.
2. A small metadata row saying the file is now at revision 8.
3. A numbered entry in a per-user change log, which other devices read to discover what moved.

The one-line architecture

The standard first sentence is: metadata in a database, bytes in object storage. Three terms in it carry the whole design.

• Metadata is the small mutable facts about a file: name, parent folder, size, revision number, who may read it.
• Object storage stores arbitrarily large blobs of bytes under a string key, with no query language and no joins. Amazon S3 is the familiar example.
• A chunk is one contiguous piece of a file, cut out of it by a boundary rule, then stored and transferred independently. A file becomes a list of chunks instead of one unbroken run of bytes. What decides where one chunk ends and the next begins is content-defined chunking, covered below.

That split is correct, and it is where the design work starts. It also lets us name three mistakes to avoid before we make them:

• Asserting “we only sync the diff” without saying what a block boundary is.
• Picking last-write-wins for conflicts without noticing it is silent data loss.
• Describing cross-user deduplication (storing one physical copy of a file that many accounts hold) as a free win, when it is a documented privacy side channel.

The two-store split

A sync service is two stores that must agree and cannot share a transaction. One is a small, hot, strongly-consistent metadata database. The other is an enormous, cold, immutable blob store.

• Hot means frequently read and expensive per byte; cold means rarely read and cheap.
• Strongly consistent means every reader sees the latest committed value, with no window in which two readers disagree.
• Immutable means a stored blob is never edited in place. A changed file becomes new blobs; the old ones stay exactly as they were.

The load-bearing half is “cannot share a transaction.” A database and an object store are separate systems. There is no single atomic operation that either writes both or writes neither, so a crash can always land between the two writes. Almost every hard property in this design comes from that split.

The invariant to hold onto: the bytes are immutable and content-addressed, the metadata is mutable and authoritative, and the two stores must never disagree in the direction that loses data.

Requirements

Functional

• Upload, download, rename, move, delete, restore from trash.
• Sync a local folder on any number of devices, including after a long offline period.
• Share a file or folder with other users, read or write.
• Revision history, and restore to a prior revision.
• Detect a concurrent edit and never destroy either side.

Out of scope: real-time collaborative editing (that is operational transform, an algorithm that rewrites concurrent edits so they can both apply inside a document format the server understands, which a file store cannot do), full-text search, and the desktop client’s filesystem watcher. Each is real work; none of it moves the architecture.

Non-functional

Two terms first:

• Linearizable means every operation appears to take effect at one instant between its start and finish, so all readers agree on a single order. Here: there is exactly one authoritative answer to “what revision is this file at right now.”
• Read-after-write consistency means that once a write returns, any subsequent read is guaranteed to see it.

The asymmetry that shapes everything: metadata needs linearizability and is 0.02% of the bytes; blobs need only durability and are 99.98% of the bytes. That is permission to run two stores with two different consistency bills: a small expensive consistent one for metadata, and an enormous cheap eventually-consistent one for blobs.

Why is the weak guarantee affordable for blobs? Because a blob is named by its own hash. A replica either has those bytes under that name or does not have that name at all. It can never have different bytes under that name, so there is no disagreement to resolve, only a delay.

Back of the envelope

Three numbers get used for the rest of the lesson: how many bytes the service stores, how many it would move per day if it did the obvious thing, and how small the metadata is next to both.

Rounding follows the discipline of back-of-the-envelope estimation: a day is treated as 100,000 seconds, which costs ~15% accuracy and lets every division be done in the head. Two figures below are quoted as final results, not intermediates, so they use exact seconds; those are flagged where they occur.

Assumptions: 50 M registered users, 10 M daily active (DAU), 10 GB quota each at 20% utilization, 10 file changes/day per active user, of which 90% are small (100 KB avg) and 10% are large (20 MB avg).

Corpus and load.

• Logical bytes stored: 50 M × 10 GB × 0.20 = 100 PB. No database holds this; it is object-storage territory, and every percentage point of dedup is worth a petabyte.
• File changes: 10 M × 10 = 100 M/day → 1,000 writes/s, 3,000 at 3× peak. Unremarkable, comparable to the URL shortener. The metadata tier is not the hard part.

Bytes on the wire, naive (re-upload the whole file on every change).

• 100 M changes × the mix (90% × 100 KB + 10% × 20 MB) = 209 TB/day, or 16.7 Gbps sustained, 50.1 peak. This is the hard part.
• The 20 MB files are 10% of the changes but 96% of the bytes (200 of the 209 TB). Every byte-saving technique in this lesson aims at that 10%; nothing helps the other 90%, because a 100 KB file is smaller than a single chunk and has nothing inside it to diff.

Metadata, and how small it is: a metadata row is about 284 bytes (ids, name, size, timestamps, revision, content hash, overhead). Using the 2.09 MB mean change size as a stand-in for mean file size (nothing here fixes a file count directly, so this is the one number worth replacing with a real measurement):

• ~47.8 B files → 957 files/user → 13.6 TB of file metadata.
• Chunk map at the 1 MB average chunk (derived below): 100 B chunk-map rows → ~4 TB.
• Total 17.6 TB, about 0.018% of the corpus.

That fits on 30 to 80 commodity boxes, spread across them by sharding on owner_id (splitting rows across machines by a key, so one user’s data lands on one machine). At that size the tier is cheap enough to make strongly consistent, replicated, and boring. That is exactly the right place to spend a consistency budget: on the 0.018% where disagreement corrupts, not on the 99.98% where it cannot.

API sketch

The client asks which pieces the server is missing, uploads those, commits the new revision, and separately keeps a live channel open to hear about everyone else’s changes.

• POST creates, PUT writes a specific named thing, GET reads. 200 is success, 409 is conflict, 410 means gone (a bookmark too old to serve).
• WSS is a WebSocket over TLS: a connection that stays open so the server can push instead of the client repeatedly asking.
• A cursor is a bookmark: a number the client remembers, meaning “I have seen everything up to here.”

POST /v1/chunks:probe   {"hashes": [...]} -> {"missing": [...]}
                        -- read the dedup side-channel section before shipping
PUT  /v1/chunks/{sha256}  raw bytes; idempotent, because the name IS the content

POST /v1/files:commit
  {"path": "/finance/q3.xlsx", "parent_rev": 7,
   "chunks": ["sha256:...", ...], "device_id": "mac-01"}
  200 {"rev": 8}
  409 {"head_rev": 9, "conflict_copy": "/finance/q3 (conflict, mac-01).xlsx"}

GET  /v1/delta?cursor=<seq>   -> {"entries": [...], "cursor": <seq>}
                              410 if the cursor is too old: full resync
GET  /v1/notify?cursor=<seq>&timeout=60      -- long-poll fallback
WSS  /v1/stream                              -- push, the default
GET  /v1/files/{id}/revisions

Four choices in that sketch are deliberate:

• Commit is a compare-and-swap on parent_rev. A compare-and-swap (CAS) succeeds only if the value is still what you last read: “set the revision to 8, but only if it is currently 7.” That single integer comparison is the entire conflict-detection mechanism. A 409 is not an error to retry blindly; it is a signal to reconcile.
• Chunks are PUT by content hash, so every upload is idempotent for free. Idempotent means doing it twice has the same effect as doing it once. There is no idempotency key, no dedupe table, no exactly-once protocol, because a retried PUT writes identical bytes to an identical key.
• Commit is separate from upload. Bytes land first, metadata commits last, and that commit is the single instant at which the change becomes true for everyone. The opposite order can show a user a file with no contents.
• 410 on an expired cursor is part of the contract. A device offline for two months cannot be served from any change log you are willing to retain, and pretending otherwise means an unbounded log.

Data model

Six tables carry the design. PK marks the primary key; BYTEA(32) is a fixed 32-byte binary column, exactly the width of a SHA-256 hash.

files                                  -- sharded on owner_id
  file_id BIGINT PK, owner_id BIGINT, parent_id BIGINT, name VARCHAR(255),
  head_rev BIGINT,                     -- the compare-and-swap target
  size BIGINT, mtime TIMESTAMP,
  status SMALLINT                      -- active | trashed | conflict_copy

revisions   file_id, rev, size, author_device, created_at     -- append only
chunk_map   file_id, rev, ordinal, chunk_hash BYTEA(32), length INT
chunks      chunk_hash BYTEA(32) PK, length INT, blob_locator, first_seen
            -- GLOBAL, not per user
journal     owner_id, seq BIGINT, file_id, op, rev            -- the cursor source
shares      object_id, grantee_id, permission

Four choices here are worth defending:

• owner_id is the shard key, not file_id. Every real query is “everything that changed in this user’s tree.” Partitioning by owner keeps that on one machine. Partitioning by file_id would scatter one user’s files across every machine, turning each sync into a scatter-gather: fan the question to all shards, wait for the slowest, merge. Assign users to machines with the consistent-hashing ring so that adding the N+1-th machine relocates only 1/(N+1) of users instead of the ~94% a plain “hash modulo machine count” scheme would move.

• The chunks table is global, so it cannot be sharded by owner. A chunk belongs to everyone who holds those bytes; there is no owner to shard on. It is keyed by a 32-byte hash with no locality and no range queries, a pure key-value workload, hash-partitioned on the chunk hash itself.

• revisions and chunk_map are append-only. Rows are added and never modified. Two replicas of an append-only table can only ever disagree about whether a row exists yet, never about what a row says. So revision reads can be served from any replica, while only the head_rev compare-and-swap goes to the single primary that owns the ordering. The expensive coordination is confined to one 8-byte column.

• A shared folder is an edge, not a copy. Sharing lives in shares as one row per grant. Do not duplicate rows into the grantee’s tree: a folder shared with 500 people would then need 500 metadata writes per change, turning a 1,000/s write tier into a 500,000/s one on its worst day.

High-level architecture

The whole design is one loop: a change leaves one device, becomes durable, and comes back to every other device as a notification that carries no data at all. The three numbered arrows are the write path, in order; everything below them is the read path.

flowchart TD
    C["Desktop / mobile client<br/>watcher, chunker, local index"]
    C -->|"1. probe chunk hashes"| API["Metadata API"]
    C -->|"2. PUT missing chunks"| BLK["Block service"]
    BLK --> OBJ[("Object store<br/>content-addressed, erasure coded<br/>authoritative for the bytes")]
    C -->|"3. commit, CAS on parent_rev"| API
    API --> MDB[("Metadata DB<br/>sharded on owner_id<br/>authoritative for file facts")]
    API --> JRN[("Change journal<br/>per-user monotonic seq")]
    JRN --> NOTIF["Notification service<br/>~20 M live sockets<br/>sized by sockets, not CPU"]
    NOTIF -->|"cursor moved"| C2["Other devices"]
    C2 -->|"GET /v1/delta?cursor="| API
    C2 -->|"chunk fetch"| CDN["CDN / signed blob URLs<br/>read capacity"]
    CDN --> OBJ
    GC["Mark-and-sweep GC, weekly<br/>the one irreversible step"] --> OBJ
    GC --> MDB

There are two authoritative stores here, which is the whole point: the metadata DB is authoritative for the 0.02% of bytes that need linearizability, and the object store is authoritative for the other 99.98%.

The write path

The client does three jobs before it speaks to the server. A watcher notices the file changed; a chunker splits it into pieces; a local index remembers the hash of each piece. Then:

1. probe chunk hashes asks which of those hashes the server is missing.
2. PUT missing chunks sends only those to the block service, whose only job is moving bytes into and out of the object store. The store keeps them content-addressed (the key is the hash of the contents) and erasure coded (a redundancy scheme priced below).
3. commit, CAS on parent_rev writes the new revision, and appends one row to the change journal, a per-user monotonic sequence (numbers only ever increase, so a client can say “everything above 4,102, please” and get an unambiguous answer).

The read path

The journal feeds a notification service holding roughly 20 million live sockets, one per connected device. That service tells other devices one thing only: your cursor moved. Each woken device then issues GET /v1/delta?cursor= to find out what changed, and fetches any chunks it lacks.

Chunk fetches go through a CDN (a content delivery network: caching servers placed near users) using signed blob URLs, short-lived authenticated links that let a cache deliver a private object without ever holding the user’s credentials.

Off to the side, a weekly garbage collection job reclaims chunks that no file references any more, using mark-and-sweep instead of reference counting (explained below).

The arrow that is not there is the important one: the notification service never carries file contents and never carries the change list. It carries “your cursor moved.” Everything else is a pull, which keeps the socket tier stateless with respect to file data and lets it be sized purely on connection count.

Deep dive 1: what block-level sync actually saves

Block-level sync (delta sync) means splitting a file into pieces and uploading only the pieces whose contents changed. Price it on one file first, then across the fleet, where the saving is much smaller.

On a single file, a 1 KB edit to a 50 MB file costs:

• Naive: re-upload all 50 MB.
• Fixed 4 MB blocks: ship one block, 4 MB. 12.5×.
• 1 MB content-defined chunks: ship one chunk, 1 MB. 50×.

Across the whole fleet, sort the 100 M daily changes into three buckets (assuming 80% of large-file changes edit a file the server already holds, an edit dirties 2 chunks, and small files always ship whole):

• Small files, untouched by delta sync: 9 TB/day.
• Large-file edits, 2 chunks each: 16 TB/day.
• New large files, shipped whole: 40 TB/day.
• Total 65 TB/day, a 3.2× saving over the naive 209 TB/day.

So delta sync is 50× on the file but only 3.2× on the fleet, because after it runs, 62% of the remaining bytes are first-time uploads that no diff can shrink. The only thing that removes first-upload bytes is discovering someone else already uploaded them. That is deduplication.

Deduplication assumes 25% of newly uploaded chunks already exist somewhere. That drops upload to 55 TB/day (a combined 3.8× over naive) and, more importantly, removes 25 PB of logical data: the corpus falls from 100 PB to 75 PB.

The stored bytes are protected with three terms:

• Replication factor (RF) is how many complete copies you keep. RF 3 costs 3× the data.
• Erasure coding is cheaper: split data into k fragments, compute m parity fragments, store all k + m on different machines, and any k rebuild the original.
• RS(10,4) is Reed-Solomon with k = 10, m = 4. It survives any four simultaneous losses while storing 14/10 = 1.4× the data instead of 3×.

On the 75 PB deduplicated corpus, RS(10,4) costs 105 PB of physical media against 225 PB at RF 3, a 120 PB saving. Deduplication moves the bandwidth saving only from 3.2× to 3.8×, a modest gain. The storage win is the real one: 25 PB of logical data removed, and 120 PB of physical media saved by coding instead of replicating.

The catch is repair cost. Under RS(10,4), rebuilding one lost fragment requires reading 10 surviving ones, so a repair moves ten times the bytes that were lost. That is fine for cold data, where failures are rare relative to reads, but unacceptable for the hot working set, where repair traffic competes with live reads. So keep the last 30 days replicated and erasure-code everything older.

Deep dive 2: content-defined chunking, and the insert that kills fixed blocks

Delta sync priced above never said what a chunk boundary is, and the obvious answer fails on an ordinary edit.

A fixed-size block boundary is a function of offset. A content-defined boundary is a function of content. Everything below follows from that.

Overwrite is fine; insert loses everything

The measure is write amplification: bytes actually transferred divided by bytes the user actually changed. 1 is perfect; higher is waste.

Take the 50 MB file cut into fixed 4 MB blocks (13 blocks), and run two edits:

• Overwrite 1 KB at offset 30 MB. The file stays 50 MB, one block changes, 7.7% of the file re-uploaded. Respectable, which is why fixed blocking survives in tutorials.
• Insert 1 KB at offset 0. The file becomes 50 MB + 1 KB, and every byte after the insertion slides 1,024 positions right.

Why the insert is fatal: block i is defined as the bytes at offsets [4 MB·i, 4 MB·(i+1)), and nothing about its contents enters into it. Make it small enough to see. Blocks 4 bytes wide, file ABCDEFGH: block 0 is ABCD, block 1 is EFGH. Insert X at the front and the file is XABCDEFGH: block 0 is now XABC, block 1 is DEFG. Neither block holds what it held before, though seven of the eight original bytes were never touched.

So no block after the insertion point holds the bytes it did, every block hash changes, and the client re-uploads the entire file: 50,000× write amplification for a 1 KB change. Inserts are not exotic. Prepending a header, a database file growing a page at the front, a log with a rewritten preamble, and every “save as” that rewrites a container all shift content downstream.

flowchart TD
    E["1 KB inserted at the front of a 50 MB file<br/>every later byte shifts right by 1 KB"]
    E --> FX["Fixed-size blocks<br/>boundary = a byte offset"]
    E --> CD["Content-defined chunks<br/>boundary = the bytes at the cut point"]
    FX --> FXR["Every block now holds shifted content<br/>all 13 block hashes change<br/>re-upload 100% of the file"]
    CD --> CDR["Downstream boundaries move with their content<br/>those chunk hashes are unchanged<br/>re-upload 2 of 50 chunks = 4%"]

How content-defined chunking survives it

The mechanism is three steps:

1. Slide a window. Walk a w-byte window along the file one byte at a time; at each position it covers the last w bytes read.
2. Keep a rolling hash of that window. A rolling hash updates in constant time as the window advances: mix in the byte entering on the right, mix out the byte leaving on the left. You never re-hash all w bytes, which is what makes this affordable on a 50 MB file.
3. Cut where a predicate fires. Conventionally: are the hash’s low b bits all zero? If yes, end a chunk. A good hash makes that fire about once every 2^b bytes, so with b = 19, cuts land on average 524,288 bytes apart.

Nothing in those steps mentions an offset. A boundary at position p was decided by the w bytes ending at p. After a 1,024-byte insert at the front, those same w bytes now end at p + 1,024; the predicate reads those bytes and nothing else, so it still fires. The boundary moved with its content instead of staying at a fixed offset. Every boundary downstream of the edit is preserved, so every chunk downstream hashes exactly as before, so the server already has it. Only the chunk containing the insertion is destroyed, plus a bounded amount of resynchronization, because a sliding-window predicate is memoryless past w bytes: once the window no longer overlaps the edit, the chance of a cut is the same as it always was.

Deriving the 1 MB chunk size starts from the parameters: 48-byte window, low 19 bits zero (2^19 = 524,288 bytes between natural cuts), a 512 KiB floor (no cut accepted below it), and a 4 MiB cap (a cut forced at it). The floor guarantees at least 524,288 bytes; past it, memorylessness means the expected wait to the next cut is another full 524,288 bytes. Add them: mean chunk = 524,288 + 524,288 = 1,048,576 bytes, exactly 1 MiB, and the cap fires on only 0.09% of chunks so it barely perturbs the mean. This is why the rest of the lesson can spend “1 MB”: it is a computed value, not a chosen one.

The floor and cap are not decoration. Without a floor, chunk length is purely geometric and puts a lot of mass on tiny chunks, each needing an index row and saving no bandwidth. Without a cap, a long run of zeroes never satisfies the predicate and produces a chunk of arbitrary size.

One unit note: the mask is a power of two, so this derivation lands on 1 MiB = 1,048,576 bytes (2^20), while the rest of the lesson rounds it to a decimal 1 MB = 1,000,000. Counts obtained by dividing bytes by chunk size are therefore ~4.9% high, all in the same direction, which is well inside the accuracy of the assumptions feeding them.

On this edit, fixed blocks re-upload 100% of the file while CDC re-uploads 2 of 50 chunks = 4%. That is 25×, and it is the whole argument.

Why 1 MB and not 64 KB

Chunk size is simultaneously a bandwidth decision, an index-size decision, and a request-rate decision, and the last two push back. Smaller chunks find more redundancy and shrink the delta, but at 64 KB instead of 1 MB:

• The chunk map grows to 62.5 TB, which is 4.6× the size of all other metadata combined.
• The blob store takes 10,156 chunk writes/s instead of 650.

Index size and request rate both scale as 1/chunk_size, so halving the chunk doubles both. The delta saving does not scale that way; it saturates, because an edit is already down to 2 chunks and cannot go below 1. 1 MB is where those curves cross for this workload. A backup product, whose data has far more redundancy to find, legitimately picks 256 KB and pays the index.

The chunking rule, in code

The teaching point is one distinction: does the boundary rule read offsets or bytes? These two functions make it concrete.

"""Content-defined chunking, and the insert that breaks fixed-size blocks."""
import hashlib

MASK64 = (1 << 64) - 1
TABLE = [int.from_bytes(hashlib.sha256(bytes([i])).digest()[:8], "big")
         for i in range(256)]

def _rotl(x, n):
    n %= 64
    return ((x << n) | (x >> (64 - n))) & MASK64

def fixed_blocks(data, size):
    """Boundaries at 0, size, 2*size, ... -- a function of OFFSET alone."""
    return [data[i:i + size] for i in range(0, len(data), size)]

def cdc_chunks(data, window, mask_bits, min_chunk, max_chunk):
    """Boundaries where the rolling hash of the last `window` bytes has
    `mask_bits` low zero bits -- a function of CONTENT alone."""
    mask = (1 << mask_bits) - 1
    out, start, h = [], 0, 0
    for i, b in enumerate(data):
        h = _rotl(h, 1) ^ TABLE[b]                        # roll the new byte in
        if i - start >= window:
            h ^= _rotl(TABLE[data[i - window]], window)   # roll the old one out
        n = i - start + 1
        if n < min_chunk:                                 # the floor
            continue
        if (h & mask) == 0 or n >= max_chunk:             # natural cut, or cap
            out.append(data[start:i + 1])
            start, h = i + 1, 0
    if start < len(data):
        out.append(data[start:])
    return out

The two lines that make the hash rolling are the _rotl(h, 1) ^ TABLE[b] that mixes the new byte in and the h ^= _rotl(TABLE[...], window) that mixes the departing byte out; rotating by the window width is what makes the second line cancel the first exactly window steps later. In fixed_blocks the boundary is pure arithmetic on the index, with data never consulted. In cdc_chunks the boundary is (h & mask) == 0 on a hash of recent bytes; the index appears only to enforce the floor and cap.

Run both over the same file after an insert and the result is a proof, not a promise: a one-byte insert forces fixed_blocks to re-upload the whole file, while cdc_chunks ships two chunks (about 100 bytes here), a gap of well over 50×.

One caveat the code hides is worth naming. That “100%” holds because the test file is high-entropy random bytes, so every shifted block is content the server has never seen. On an all-zero file, every shifted block hashes to one the server already holds and fixed blocking looks perfect. Zero-padded containers, sparse VM images, and repeated headers are ordinary, so where a file is repetitive, fixed blocking gets rescued by deduplication, not by its boundary rule. That is a different argument and buys nothing on the 50 MB spreadsheet this design is about. The claim that survives is the mechanism: a fixed boundary is a function of offset, so an insert relabels every block.

Deep dive 3: two devices, both offline, same file

Device A and device B both hold revision 7 of q3.xlsx. Both go offline, both edit, both come back. Every sync product must answer this.

Why last-write-wins is not an option

Last-write-wins (LWW) keeps whichever version was written later and discards the other. Assume 0.1% of daily changes commit against a parent revision that is no longer head. That is 100,000 conflicts/day, so LWW silently destroys 36.5 million edits a year, with no error and no log line.

The clock is a red herring. With 100 ms of clock skew against conflict gaps spread over a 10-minute window, skew flips the winner in about 100 / 600,000 of cases, roughly 17 conflicts a day. A perfect clock (the never-runs-backwards machinery of the ID-generator design) would fix those 17 and leave 99,983. The defect in LWW is not that it occasionally picks the wrong version but that it discards one at all.

Detecting the conflict costs one integer, not a vector clock

A version vector (vector clock) is a per-object map from every writer that ever touched the object to a counter. It travels with the data so any two versions can be compared and declared ordered or genuinely concurrent. A Dynamo-style key-value store needs one because it has no single machine that decides the order of writes; causality has to travel with the data or it is lost.

A sync service does have that single point: the metadata shard that owns the file. Every commit for that file goes through one machine, so the whole causality question collapses to one comparison: was your parent revision still the head revision when you committed? A version vector on a file shared with 20 collaborators at 3 devices each is 960 bytes and grows with every device that ever touched the file. A compare-and-swap on head_rev is 8 bytes, 120× smaller, and never grows. Reserve the vector for genuine multi-writer systems with no common ordering, which this is not.

The commit is therefore an optimistic concurrency loop (take no lock, do the work, check at the end whether anyone got there first): read head_rev, upload the chunks, call commit(parent_rev=head). A mismatch comes back as a 409 carrying the current head, and the client reconciles. Nothing is locked in the meantime, which matters because the upload can take minutes.

flowchart TD
    A["Read head_rev"] --> B["Upload chunks"]
    B --> C["commit with parent_rev = head"]
    C --> D{"parent_rev still head?"}
    D -->|yes| E["Commit succeeds, head advances one revision"]
    D -->|"no, 409"| F["Reconcile: write the loser as a renamed conflict copy, keep both"]

Resolving it: keep both, and be honest about it

Detecting a conflict is cheap; deciding what to do about it is a product decision. Four policies:

Keeping both means keeping a second copy of every conflicting file, which costs about 76.3 TB/year, 0.076% of the corpus. So conflict copies cost 0.076% of storage and lose nothing, while last-write-wins costs 0% of storage and destroys 36.5 million edits a year. There is no argument.

Conflict copies are what every consumer sync product ships. A merge requires understanding the bytes, and a file store is defined by not understanding the bytes. The real cost is human: a misbehaving client in a shared folder can generate copies faster than anyone deletes them. Two free mitigations: suppress the copy when both revisions have identical content hashes (concurrent identical saves are common and are not conflicts), and name the copy with the device and timestamp so it becomes a two-second decision instead of a mystery file.

Deep dive 4: how a device finds out, and why the cursor beats the tree

Two questions get conflated: how is the device woken up? (a connection-model question) and what does it fetch once awake? (a protocol question, where the wrong answer costs more than the files themselves).

Waking the device

Three delivery models, against a fleet of 20 M live sockets (10 M DAU × 2 devices) learning about 5 changes each per day:

• Short polling (ask on a fixed timer, usually told no): at 30 s that is 666,667 QPS, 99.85% of it returning “no change,” and still 15 s of average latency.
• Long polling (server holds the request open until something happens or a timeout): halves the request rate to 333,333/s and removes the latency, though the request count is still enormous.
• Push (client opens one connection and the server writes to it): about 5,556 connection setups/s, 60× fewer than long polling, and each one avoided is a TLS handshake, not just a packet.

Sizing the socket tier is where the surprise lives. 20 M sockets hold about 200 GB of connection state, which naively divides to about three machines. Reality is 40 to 200, because three limits bind before memory: file descriptors (the per-process kernel ceiling on open connections), CPU spent on TLS setup, and blast radius (how many users one machine failure disconnects, usually the limit that sets the floor).

Push adds the cost that causes the outage. If a deploy drops all 20 M sockets and they return in 5 seconds, that is 4 million connects/s, a denial of service you performed on yourself. The fix is jitter: a random delay before each retry so clients that failed together do not return together. Spread over a 10-minute jittered window, the same reconnect is 33,333/s, 120× smaller. Full jitter on the client’s reconnect backoff is mandatory, the same arithmetic as the rate-limiter retry storm. Keep long polling as a fallback anyway, because some corporate proxies terminate WebSocket connections.

What the device fetches: a cursor, never the tree

The naive answer, “send me my whole folder tree,” quietly becomes the largest traffic source in the system. A full listing of one user’s 957 files at 284 B is 272 KB; the delta since a cursor is 5 changes at ~300 B, 1.5 KB. That is 181×. Fleet-wide at four wakes a day, the full-tree model is 21.7 TB/day of metadata chatter against 65 TB/day of actual file bytes, so a third of all traffic would be re-describing files nobody touched. It gets worse as accounts age: file count grows, change count does not.

The cursor is the per-user monotonic sequence number: every metadata mutation appends one row (owner_id, seq, file_id, op, rev) to that user’s journal, an append-only log of what changed, and a client presents its last seq to receive everything after it. Three properties come with that structure:

• Resumable. A client that dies halfway through a page re-requests from the same cursor. The server holds no per-client state.
• Idempotent. Each entry names a (file_id, rev) pair the client either has or does not. Applying it twice changes nothing.
• Ordered within a user. So the cursor is a plain counter on that owner’s shard, not a distributed ID generator. There is no ordering across users, and nothing asks for one.

The journal is not free: 100 M rows/day at 64 B is 6.4 GB/day, so 30 days of retention is 192 GB, nothing at this scale. But the window is finite, and that has a consequence you must design for: beyond the window the cursor is invalid and the client must do a full resync, so put that 410 in the contract instead of discovering it during an incident. Then rate-limit the resync path, because the failure mode is 40,000 devices listing their entire tree in the same minute.

Deep dive 5: cross-user dedup, and the side channel it opens

A side channel is information that leaks not from what a system tells you but from how it behaves, here from how long a response takes. There are two places to deduplicate:

• Server-side: the client always uploads, and the server discards a copy it already holds. Saves storage only.
• Client-side: hash the chunk, ask the server whether it has it, upload only if not. Saves bandwidth too, which is why it is tempting.

The client-side version hands every user an oracle: a way to ask a yes-or-no question about other people’s data and get a reliable answer. The attack is three steps: construct a candidate file, offer its hash, and observe whether the server asks for the bytes. A “no thanks” means someone, somewhere, already has that exact content.

The signal is loud. On a 10 Mbps uplink a new 4 MB chunk takes 3.2 s to upload; a chunk the server already holds takes about 0.05 s for the hash exchange. That is 64×, a boolean you can read off a stopwatch. What the oracle is worth depends on how much of the candidate the attacker must guess (its entropy):

• A date of birth inside a known template: 36,500 possibilities, about 6 minutes at 100 probes/s.
• A nine-digit national ID in the same template: 10^9, about 116 days.
• “Is this specific leaked document in anybody’s account?”: one probe, because the attacker already holds the whole file. That last case turns your storage service into a membership oracle over private data and is the one with legal consequences.

Four mitigations

1. Server-side dedup only. The client always uploads; the server discards duplicates after receipt. The channel closes completely, because nothing the client observes depends on other users’ data. You give up 15% of bandwidth (10 TB/day) and keep all 35 PB of physical storage saving. Since storage, not bandwidth, is where the money is, this trade is close to free, and it is the industry standard answer.

2. Randomized threshold (Harnik, Pinkas, and Shulman-Peleg, 2010). Draw a secret threshold t uniformly from 1..T per chunk and refuse to deduplicate until the server has seen the chunk at least t times. Because t is unknown, a “please upload it” answer no longer means “nobody has this.” With T = 20 the attacker pays on average 10.5 full uploads per probe. Whether that defends depends on which resource binds: if the server still answers 100 probes/s, the six-minute attack becomes about an hour (not a defence); if the attacker’s own 10 Mbps uplink now binds, the same attack takes 14 days (a defence). Ship this only in the second case. The cost is storing up to T copies of genuinely rare chunks, which is bounded because rare chunks are rare.

3. Scope the dedup to what the user can already read (within one account, and within an explicitly shared folder). The oracle then reveals only data the querier is already entitled to see. The cost is most of the cross-user dedup ratio.

4. Convergent encryption. Encrypt each chunk under a key derived from that chunk’s own plaintext hash, so identical plaintext yields identical ciphertext and dedup still works while the server holds no readable data. It is worth knowing but does not fix this attack: the ciphertext is a deterministic function of the plaintext, so an attacker who can guess the plaintext computes the same ciphertext hash and runs the identical probe.

Ship mitigation 1, and mention 2 as the way to buy back most of the bandwidth if the bill demands it. The one thing not to do is call cross-user client-side dedup a pure win.

Deep dive 6: two stores, one commit

There is no transaction spanning the metadata database and the object store, so a crash can always land between the two writes. You cannot prevent that; you can only choose which write goes first, and only one order is survivable.

Write the blob first, commit the metadata last, and treat the metadata commit as the moment the file exists. That rule is why the API splits PUT /chunks from files:commit.

An orphan is a chunk in the object store with no metadata row referring to it. At 0.1% of uploads failing between the two writes, that is 100,000/day, 36.5 TB/year, 0.037% of the corpus. Two facts keep it bounded: a retried upload writes the same hash to the same key, so retries never compound the total, and a weekly sweep reclaims the rest. Content addressing is what makes the unsafe-looking order safe.

Deleting is the mirror problem

Deduplication sharpens it: one chunk may be referenced by thousands of files across hundreds of accounts, so deleting a file must not delete its chunks.

Reference counting (keep a count per chunk, free it at zero) is exact and immediate, which is why it is the first thing everyone reaches for. It is rejected because the counter update would have to be transactional across two differently-sharded stores (owner-sharded metadata and hash-sharded chunks), and no such transaction exists, so updates get dropped. The two ways to drop one are wildly asymmetric: a dropped decrement leaks storage forever (costs money), but a dropped increment deletes a user’s data (ends the product).

Use mark and sweep instead: walk every metadata row to mark which chunks are still referenced, then sweep away the unmarked. The scan is 4 TB of chunk map at 1 GB/s, about 1.1 machine-hours, run weekly, which costs far less than the distributed transaction a reference count would need.

One detail is not optional: a grace period, a minimum age below which the sweep refuses to delete. A chunk uploaded ten seconds ago has no referrer yet, because its commit has not happened, which is the whole point of blob-first ordering. A sweep that does not exclude it deletes a file out from under an upload in progress, and the user sees corruption instead of an error. 24 hours is the standard number; the only requirement is that it exceeds your longest upload plus its retry window.

Bottlenecks and scaling

The one usually missed: a shared folder is a fan-out multiplier on the write tier. Because the cursor is per-user, every grantee needs a journal entry, so a folder shared with 500 people and changed 100 times a day produces 500 × 100 = 50,000 journal appends from one person’s activity. Cap share sizes, keep each journal entry a reference to the shared object instead of a per-grantee metadata copy, and treat a 10,000-member share as a different product with a different design.

Failure modes

Most of these guards are not runbook steps but ordering decisions taken at design time, too late to add once the incident is underway.

Alternatives rejected

Each is ruled out by a number, and several are right for a different product.

Fixed-size 4 MB blocks. Trivial to implement, no rolling hash, aligned reads, smaller index. Rejected because a 1 KB insert at the head of a 50 MB file re-uploads all 13 blocks, 50,000× write amplification, and inserts are ordinary. Correct when files are only overwritten in place (VM images, fixed-layout databases).

Whole-file upload, no chunking. Removes the chunk map, GC, boundary rule, and 4 TB of metadata. Rejected on the fleet number: 209 TB/day instead of 55 is 3.8× the ingress and 3.8× the client’s upload time, the one resource users actually notice.

Version vectors for conflict detection. Exact concurrency detection with no serialization point, which is what makes a Dynamo-style store always writeable. Rejected because there is a serialization point here; an 8-byte head revision does the same job as a 960-byte vector, 120× cheaper. Revisit only if clients may commit to a regional replica during a partition, at which point you are building Dynamo.

Last-write-wins on the server clock. No conflict interface, no extra storage, almost no code. Rejected because it destroys 36.5 million edits a year silently while a conflict copy costs 0.076% of storage. Acceptable only for regenerable state, which a user’s file is not.

Operational transform or a CRDT. The best possible experience: no conflict copies, both edits merged. Rejected because it requires the server to understand the file format, and a general file store’s defining property is that it does not. Correct inside a document editor, which is a different service that happens to store its output here.

Short polling for change notification. No connection state, no reconnect storms, works through every proxy. Rejected on both axes at once: 666,667 QPS of which 99.85% return nothing, and 15 s of average latency. Keep long polling as the fallback for devices behind proxies that break sockets.

Client-side cross-user deduplication. Removes 15% of ingress at no storage cost. Rejected because it is a membership oracle with a 64× timing signal that can confirm a specific file’s presence in one probe. Server-side dedup keeps all 35 PB of physical saving and closes the channel.

Reference counting chunks. Immediate reclamation, no scan, no grace period. Rejected because the counter would have to be transactional across two differently-sharded stores, and a lost increment deletes user data, while a full sweep costs 1.1 machine-hours weekly.

What the design depends on

The design is correct only relative to its assumptions. Four are load-bearing: if they are wrong, the design is not suboptimal, it is invalid, and whole boxes appear or disappear.

• A small share of changes carries almost all the bytes (10% carry 96%). If every file were 100 KB, nothing is bigger than one chunk, delta sync saves zero, and the chunker, chunk map, probe call, and chunk-level GC should not exist.
• Edits include inserts, not just in-place overwrites. With overwrites only (VM images, fixed-layout databases), fixed 4 MB blocks are correct and the rolling hash is pure complexity.
• Exactly one shard owns each file, so there is a single serialization point. Allow commits to regional replicas during a partition and you need version vectors, sibling reconciliation, and a pruning policy; you are building Dynamo.
• Nothing may ever be silently lost. If the product tolerated losing an edit, last-write-wins is correct and the whole conflict story collapses to one line.

The rest are tunable: the 25% cross-user duplicate rate, the 30-day journal window, the 0.1% conflict and orphan rates, the corpus assumptions, and the rolling-hash parameters all scale a number linearly without changing a mechanism. The one worth measuring instead of assuming is that mean file size equals the 2.09 MB mean change size, a stand-in used because nothing here fixes a file count directly; a real number rescales the file count, files-per-user, and metadata figures together but changes no mechanism.

Conclusion

• Split the system in two: a small strongly-consistent metadata store and an enormous eventually-consistent content-addressed blob store. They cannot share a transaction, and almost every hard property follows from that.
• Chunk files by content, not offset, so an insert moves boundaries with their content instead of relabelling every block. This is the difference between re-uploading 4% and 100% of a file on a head insert.
• Detect conflicts with an 8-byte compare-and-swap on the head revision, not a version vector, because one shard owns each file. Never resolve by discarding; write a conflict copy and keep both.
• Notify with a cursor bump only; the device pulls the delta and any missing chunks. Sending the whole tree would make metadata a third of all traffic.
• Deduplicate server-side, not client-side, or you build a membership oracle with a 64× timing signal.
• Order the two writes blob first, metadata last, and reclaim orphans with a weekly mark-and-sweep plus a grace period, never a reference count.

One line to remember: the bytes are immutable and named by their own hash, the metadata is mutable and authoritative, and every hard property in this design falls out of the fact that those two stores can never share a transaction.

Summary

Further reading

• Muthitacharoen, Chen, and Mazières, “A Low-Bandwidth Network File System” (SOSP 2001). The canonical source for content-defined chunking with a rolling hash.
• Tridgell and Mackerras, “The rsync algorithm” (1996). The rolling-checksum delta-transfer technique that delta sync descends from.
• Harnik, Pinkas, and Shulman-Peleg, “Side Channels in Cloud Services: Deduplication in Cloud Storage” (IEEE Security & Privacy, 2010). The published attack behind the dedup side channel, and the randomized-threshold mitigation.
• DeCandia et al., “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP 2007). Version vectors and why a store with no serialization point needs them, the machinery this design avoids.

Related: consistent hashing partitions the metadata tier and the chunk table; key-value store is the conflict machinery you do not need here, and knowing why is the point; back-of-the-envelope estimation sizes the 20 M-socket notification tier.