System Design · Lesson 14 of 18

File Storage (Dropbox / Drive)

Chunking, dedupe, delta sync, metadata service and conflict resolution.

  • Advanced
  • 52 min read
  • 6 objectives

Before this lessonLesson 13: Video Streaming (YouTube)

What you will learn

  • Size storage, commit traffic and connections for a Dropbox-scale drive
  • Split the metadata plane from the block plane and justify the stores
  • Implement content-defined chunking and SHA-256 dedupe, and explain their privacy trade-offs
  • Design the upload-then-commit protocol with compare-and-set revisions
  • Sync devices with journals, cursors, long-poll or WebSocket, and conflicted copies
  • Partition metadata by namespace, cache immutable blocks and tier cold storage

Your Progress

0 of 18 lessons 0%

  • Lessons0 / 18
  • Completed0
  • Est. time left~ 16 hours

Progress is saved in this browser. No account needed.

Tip: pressing Next marks this lesson complete automatically.

Design cloud file storage in the style of Dropbox, Google Drive or OneDrive: a user drops a file into a folder on one device and it appears, a few seconds later, on every other device they own and on the devices of everyone they shared it with. Edits made offline on a plane are merged on landing. Deleted files can be restored for 30 days. A 2 GB video that already exists anywhere in the system does not get uploaded a second time.

This prompt looks like "an upload API plus S3". It is not. The interesting parts are all about sync: how a client figures out what changed, how it moves only the changed bytes, how the server gives every device a consistent view of a folder tree, and what happens when two devices change the same file without seeing each other. The storage of bytes is the easy half.

The one sentence to anchor on: a file is a small, strongly consistent metadata record that points at a list of immutable, content-addressed blocks. Almost every good decision in this lesson falls out of that sentence.

Step 1 — Clarify the requirements

Why do people pay for cloud storage at all? Three reasons, and they become the non-functional requirements: availability (my files on any device, anywhere), durability (a dead laptop is not lost work, because copies live in several data centres) and elastic capacity (never think about disk space again). Now pin down scope.

Functional, in scope for v1

  • Upload and download files from desktop, mobile and web clients. Files up to 50 GB; resumable uploads.
  • A designated sync folder on each desktop that is automatically synchronised across all of a user's devices.
  • Offline editing: create, modify, rename and delete while disconnected; reconcile on reconnect.
  • Sharing: share a file or folder with other users (viewer / editor), or by link.
  • Version history: restore any earlier version for 30 days (180 on paid plans); a trash for deleted files with the same window.
  • Conflict handling: two devices edit the same file concurrently → no data is lost.

Explicitly out of scope

Real-time collaborative editing of document contents (that is Google Docs — operational transforms or CRDTs, a different system entirely), full-text search inside files, thumbnails and previews, virus scanning, e-discovery and legal hold, and billing. Name them. The most common confusion in this interview is designing Google Docs when you were asked for Google Drive.

Non-functional

  • Scale: 500M registered users, 100M daily active, ~3 devices each, ~200 files per user on average (a long tail of users with 500k files).
  • Durability: 11 nines on stored bytes. Losing a user's file is the one unforgivable failure.
  • Consistency: metadata operations are ACID — a commit either fully happens or does not; a folder listing never shows half a rename; every device converges on the same tree.
  • Latency: a small edit visible on other online devices in under 10 s at p95; folder listing p99 < 200 ms; metadata commit p99 < 500 ms.
  • Efficiency: bandwidth matters more than CPU — users are on hotel Wi-Fi and metered mobile. Transfer only what changed.
  • Read/write ratio: roughly 1:1, unusual among case studies. Sync means every write on one device becomes a read on two others.

Step 2 — Back-of-the-envelope estimation

users_total      = 500_000_000
dau              = 100_000_000
devices_per_user = 3
files_per_user   = 200
avg_file_kb      = 100
SECONDS_PER_DAY  = 86_400

# --- Storage: logical vs physical ---
files_total = users_total * files_per_user
logical_pb  = files_total * avg_file_kb * 1e3 / 1e15
dedupe_saving = 0.30            # identical attachments, installers, copied folders
replication   = 1.5             # erasure coding (e.g. 10+5), not 3x copies
physical_pb = logical_pb * (1 - dedupe_saving) * replication
print(f"files: {files_total/1e9:.0f}B   logical: {logical_pb:.0f} PB   physical: {physical_pb:.1f} PB")

# --- Write traffic: new or changed files ---
edits_per_dau = 10
commits_s = dau * edits_per_dau / SECONDS_PER_DAY
peak = commits_s * 3
changed_bytes = 60e3            # delta sync: most edits touch one chunk, not the file
ingest_gbps = peak * changed_bytes * 8 / 1e9
print(f"metadata commits: {commits_s:,.0f}/s avg, {peak:,.0f}/s peak")
print(f"block ingest at peak: {ingest_gbps:.0f} Gbit/s")

# --- Chunk metadata rows ---
chunks_per_file = 1.2           # most files are one chunk; a few are huge
chunk_rows = files_total * chunks_per_file
print(f"chunk rows: {chunk_rows/1e9:.0f}B   at 100 B/row: {chunk_rows*100/1e12:.0f} TB of index")

# --- Notification connections ---
online_devices = dau * devices_per_user * 0.4   # desktops online at the same time
print(f"open long-poll/websocket connections: {online_devices/1e6:.0f}M"
      f" -> ~{online_devices/100_000:,.0f} nodes at 100k conns each")
Output
files: 100B   logical: 10 PB   physical: 10.5 PB
metadata commits: 11,574/s avg, 34,722/s peak
block ingest at peak: 17 Gbit/s
chunk rows: 120B   at 100 B/row: 12 TB of index
open long-poll/websocket connections: 120M -> ~1,200 nodes at 100k conns each

What the numbers actually decide

  • 10 PB is an object-store problem, not a database problem. No relational database holds this; bytes go to S3-style blob storage (or a purpose-built block store like Dropbox's Magic Pocket). Erasure coding at ~1.5x overhead instead of 3 full replicas saves ~15 PB of disk — that is real money and worth saying.
  • 35k metadata commits/s at peak is large but not exotic. Too much for one Postgres primary, easy for a sharded MySQL/Postgres fleet. It forces a partitioning key decision (Step 12), not a switch to an eventually consistent store.
  • 120 billion chunk rows is ~12 TB of index before replicas. The blocks table needs its own sharding by hash — it cannot live alongside per-user tables.
  • 17 Gbit/s of ingest assumes delta sync. Without chunk-level diffs (re-uploading the whole file on every save) multiply by the average file-to-chunk ratio; for a 200 MB PowerPoint saved every few minutes, that is ~50x. Delta sync is not an optimisation here; it is what makes the bandwidth bill survivable.
  • 120M open connections for change notifications means a dedicated notification tier of ~1,200 nodes. It must be separate from the metadata service so a deploy of one does not drop the other.

Step 3 — The key decision: split metadata from blocks

Two planes, with opposite characters:

Metadata planeBlock plane
WhatPaths, folder tree, revisions, block lists, ACLs, devices, journalImmutable chunks of file content, keyed by SHA-256
SizeTens of TBTens of PB
AccessSmall, random, transactional, latency-sensitiveLarge, sequential, throughput-bound, retryable
ConsistencyStrong (ACID, serialised per namespace)Trivially consistent: a hash never changes meaning
StoreSharded MySQL / Postgres (or Spanner)S3 / GCS / in-house erasure-coded block store
Scales bySharding by namespaceAdding disks; placement by hash

Because blocks are content-addressed and immutable, the block plane never has an update, never has a conflict and never needs a lock. You can cache a block forever, replicate it lazily, and retry an upload blindly — the same bytes always land at the same key. All the hard consistency work is concentrated in the small metadata plane, where a relational database is good at it.

Wrong answers candidates commonly give

  • "Store files as BLOBs in the database." A 2 GB row blows up replication, backups and buffer pools. Listing /Projects competes with streaming a video from the same disks.
  • "Store each file as one S3 object named by its path." A rename becomes a copy of every byte; a one-byte edit re-uploads the whole object; a failed upload of a 20 GB file restarts from zero; and there is no dedupe.
  • "Use Cassandra for metadata because it scales." You then have to rebuild atomic multi-row commits (block list + journal + parent folder) and compare-and-set on revisions in application code. The requirement says ACID; take a store that gives it to you and shard it.

Step 4 — API design

Two families, mirroring the two planes. Block endpoints are dumb and idempotent; metadata endpoints carry the logic. Auth is an OAuth bearer token; the gateway resolves it to user_id.

## Block plane — content addressed, idempotent, resumable

POST /api/v1/blocks/check          { hashes: ["9f86d0...", "60303a...", ...] }
  -> 200 { missing: ["60303a..."] }
  # Batch of up to 1,000 hashes. Only the missing ones get uploaded.
  # (Scoped per user in the response -- see the dedupe privacy note in Step 8.)

PUT  /api/v1/blocks/{sha256}       body: raw bytes (<= 4 MiB), Content-Encoding: zstd
  -> 201 Created | 200 OK (already had it) | 400 HASH_MISMATCH
  # Server recomputes SHA-256 and rejects a body that does not match the URL.
  # Retrying the same PUT is always safe: same key, same bytes.
  # In practice this returns a pre-signed URL so bytes go straight to the
  # object store and never through our app servers.

GET  /api/v1/blocks/{sha256}       -> 200 bytes  (Cache-Control: immutable, 1 year)
                                   -> 403 if no file you can read references it

## Metadata plane — transactional, versioned

POST /api/v1/files/commit
  Headers: Idempotency-Key: <uuid>
  { namespace_id, path: "/Projects/plan.docx", parent_rev: 41,
    size: 18344211, blocks: ["9f86d0...", "60303a...", ...], mtime, device_id }
  -> 200 { file_id, rev: 42, journal_seq: 90817 }
     409 { code: "REV_CONFLICT", current_rev: 43 }   # someone committed first
     412 { code: "BLOCKS_MISSING", need: [...] }     # upload them, then retry
     403 NO_WRITE_PERMISSION | 507 QUOTA_EXCEEDED

POST /api/v1/files/move    { file_id, new_parent_id, new_name, parent_rev }
POST /api/v1/files/delete  { file_id, parent_rev }        # moves to trash
POST /api/v1/files/restore { file_id, rev }               # new rev = old block list
GET  /api/v1/files/{file_id}/revisions?cursor=
GET  /api/v1/folders/{folder_id}/children?cursor=&limit=500

## Sync — the delta feed every client lives on

GET  /api/v1/delta?namespace_id=&cursor=90800&limit=2000
  -> 200 { entries: [{ seq, op: "upsert"|"delete", path, file_id, rev,
                       blocks: [...], size, mtime }],
           cursor: 90817, has_more: false }
     410 CURSOR_EXPIRED   # journal compacted; client must do a full re-list

GET  /api/v1/notify?cursors=ns1:90817,ns7:5521   (long-poll, 60 s timeout)
  -> 200 { changed: ["ns1"] }   # a doorbell only -- then call /delta
  -> 200 { changed: [] }        # timeout; reconnect immediately
  # WebSocket equivalent: WS /api/v1/notify pushes the same tiny message.

## Sharing
POST   /api/v1/shares      { file_id | folder_id, grantee_email, role: "viewer"|"editor" }
POST   /api/v1/links       { file_id, access: "anyone_with_link", expires_at?, password? }
DELETE /api/v1/shares/{id}

Five API decisions worth defending

  • Upload blocks first, commit metadata second. The commit is a single small request that atomically flips the file to a new block list. There is never a moment where metadata points at bytes that do not exist (412 enforces it).
  • parent_rev on every mutation is optimistic concurrency. The server's only conflict rule is "your parent is not my current revision" → 409. Resolution happens on the client (Step 11).
  • Notify is a doorbell, delta is the data. Pushing full change payloads through 120M sockets duplicates the delta logic and loses messages during reconnects. A cursor-based pull is replayable and exact.
  • The cursor is opaque and per namespace. Clients never compute it; the server can change encoding, and a 410 lets it compact old journal entries.
  • Block GETs are authorised by reference, not by hash knowledge. Knowing a SHA-256 must not be a capability to download it.

Step 5 — Data model

Metadata lives in sharded MySQL/Postgres, partitioned by namespace_id (a user's root folder, or one shared folder, is a namespace). The global block index is a separate cluster sharded by hash.

-- =========================================================
-- NAMESPACE SHARDS  (partition key: namespace_id)
-- =========================================================
namespaces (
  namespace_id   BIGINT PRIMARY KEY,
  kind           SMALLINT NOT NULL,      -- 1 personal root, 2 shared folder, 3 team
  owner_id       BIGINT NOT NULL,        -- quota is charged here
  journal_seq    BIGINT NOT NULL,        -- last assigned seq; bumped in every commit
  created_at     TIMESTAMPTZ NOT NULL
);

files (                                  -- one row per file OR folder (the tree)
  namespace_id   BIGINT NOT NULL,
  file_id        BIGINT NOT NULL,        -- stable across renames and moves
  parent_id      BIGINT NULL,            -- NULL = namespace root
  name           TEXT NOT NULL,          -- case-folded copy kept for uniqueness
  is_dir         BOOLEAN NOT NULL,
  head_rev       INT NOT NULL,           -- the compare-and-set target
  size           BIGINT NOT NULL,
  deleted_at     TIMESTAMPTZ NULL,       -- non-NULL = in trash (soft delete)
  PRIMARY KEY (namespace_id, file_id),
  UNIQUE (namespace_id, parent_id, name) -- WHERE deleted_at IS NULL
);
-- Tree by parent_id, not by full path string: renaming a folder with 50k
-- descendants is ONE row update, not 50k.

file_revisions (                         -- immutable history; restore = new rev
  namespace_id   BIGINT NOT NULL,
  file_id        BIGINT NOT NULL,
  rev            INT NOT NULL,
  size           BIGINT NOT NULL,
  content_hash   CHAR(64) NOT NULL,      -- hash of the block list: cheap equality
  block_list     BYTEA NOT NULL,         -- packed array of 32-byte SHA-256s
  device_id      BIGINT NOT NULL,        -- who made it (shown in version history)
  created_at     TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (namespace_id, file_id, rev)
);
-- block_list is packed into the row instead of a file_blocks(seq, hash) table:
-- a 4 GB file is ~1,000 hashes = 32 KB, read and written as one unit, and it
-- avoids a billion-row join table.

journal (                                -- the ordered change feed per namespace
  namespace_id   BIGINT NOT NULL,
  seq            BIGINT NOT NULL,        -- gap-free within a namespace
  file_id        BIGINT NOT NULL,
  op             SMALLINT NOT NULL,      -- upsert | delete | move
  rev            INT NOT NULL,
  PRIMARY KEY (namespace_id, seq)
);
-- /delta is a range scan on this primary key. Compacted after 90 days
-- (clients older than that get 410 and re-list).

acls (
  namespace_id   BIGINT NOT NULL,        -- shares are granted at namespace level
  principal_id   BIGINT NOT NULL,        -- user or group
  role           SMALLINT NOT NULL,      -- 1 viewer, 2 commenter, 3 editor, 4 owner
  PRIMARY KEY (namespace_id, principal_id)
);

-- =========================================================
-- USER SHARDS  (partition key: user_id)
-- =========================================================
users   (user_id PK, email UNIQUE, plan, quota_bytes, used_bytes, root_namespace_id)
devices (user_id, device_id, platform, last_seen_at, PRIMARY KEY (user_id, device_id))
mounts  (user_id, namespace_id, mount_path,          -- where a shared folder
         PRIMARY KEY (user_id, namespace_id))        -- appears in MY tree
device_cursors (device_id, namespace_id, cursor)     -- advisory; the client owns it

-- =========================================================
-- BLOCK INDEX  (separate cluster, partition key: hash)
-- =========================================================
blocks (
  hash           CHAR(64) PRIMARY KEY,   -- SHA-256 of the plaintext chunk
  size           INT NOT NULL,
  storage_key    TEXT NOT NULL,          -- where the bytes live (bucket/extent)
  tier           SMALLINT NOT NULL,      -- 1 hot, 2 warm, 3 cold
  ref_count      BIGINT NOT NULL,        -- revisions pointing at it (for GC)
  created_at     TIMESTAMPTZ NOT NULL
);

-- =========================================================
-- CLIENT  (SQLite on every device -- the "internal metadata DB")
-- =========================================================
local_files (path PK, file_id, rev, size, mtime, inode, block_list)
local_blocks (hash PK, offset_in_cache)        -- chunk cache for fast re-assembly
pending_ops (id PK, op, path, parent_rev, state) -- queued while offline
cursors (namespace_id PK, cursor)

Four modelling decisions to explain

  • Namespace, not user, is the unit of consistency. A shared folder is touched by many users, so it cannot live on one user's shard. Making it its own namespace means every commit touches exactly one shard, and the journal for that folder is a single ordered sequence all members read.
  • Folders are rows with parent_id, not path prefixes. Moves and renames are O(1). The cost is that resolving a path walks the tree — cached on the client, which already has the whole tree in SQLite.
  • head_rev is the lock. UPDATE files SET head_rev = 42 WHERE file_id = ? AND head_rev = 41 — one row affected means you won; zero means 409.
  • The client keeps its own metadata database. It is what makes offline editing possible, what lets the client answer "what changed?" without a round trip, and what it diffs incoming deltas against.

Step 6 — High-level design

flowchart TB subgraph Client["Desktop client"] W[Watcher] --> IX[Indexer] IX --> CH[Chunker] IX --> LDB[("Local metadata DB
SQLite")] end CH -->|PUT blocks| LB1[Load balancer] IX -->|commit, delta| LB2[Load balancer] IX -.->|long-poll / WS| NS[Notification service] LB1 --> BLK[Block service] BLK --> BC[(Block cache
LRU)] BLK --> OBJ[("Object store
hot tier, erasure coded")] OBJ -->|lifecycle| COLD[(Cold tier)] BLK --> BIDX[(Block index
sharded by hash)] LB2 --> META[Metadata / sync service] META --> MC[(Metadata cache)] META --> MDB[("Metadata DB
sharded by namespace")] META --> RQ[[Request queue]] RQ --> SW[Sync workers] SW --> MDB MDB -->|journal CDC| BUS[[Change log / Kafka]] BUS --> NS BUS --> RESPQ[[Per-device response queues]] RESPQ --> NS BUS --> GC[Block GC + tiering jobs]

Bytes and metadata take different paths through different load balancers to different stores. Commits land in the namespace shard; the journal is tailed into a change log that rings the notification service's doorbell for every subscribed device.

What each component owns

  • Client — four parts. The Watcher subscribes to OS file events (FSEvents, inotify, ReadDirectoryChangesW) and to remote change notifications. The Chunker splits files into blocks, hashes them, and reassembles downloaded blocks into files. The Indexer turns watcher events into pending operations, diffs block lists, drives upload-then-commit, and applies remote deltas. The internal metadata DB (SQLite) records every file, revision and block it knows about.
  • Load balancers — two pools, one in front of block servers (long-lived, bandwidth-heavy connections) and one in front of metadata servers (short RPCs). Start with round robin; move to least-outstanding-requests once uneven request cost makes some servers slow (Step 12).
  • Block service — stateless. Validates hashes, answers check, issues pre-signed upload/download URLs, encrypts, and records blocks in the block index.
  • Metadata / sync service — the brain. Validates permissions and quota, runs the commit transaction, serves /delta from the journal, handles moves, trash and restore.
  • Request queue and sync workers — heavy or bulk operations (moving a 200k-file folder, restoring a whole namespace, mobile photo backups arriving in bursts) go through a durable queue so workers absorb spikes and clients get a 202 with a job id instead of a timeout.
  • Per-device response queues — every subscribed device has a logical queue of "namespace X changed" events. An offline device's queue keeps accumulating; when it reconnects it drains the queue, then pulls /delta. Because the cursor is authoritative, these queues can be lossy and coalesced — one pending "ns1 changed" is as good as fifty.
  • Notification service — holds 120M long-poll or WebSocket connections, maps namespace → subscribed connections, and sends doorbells.
  • Object store and cold tier — durable bytes. Lifecycle jobs move untouched blocks to cheaper storage.

Step 7 — Inside the client

The client is half of this system, and interviewers often probe it. Walk through what happens between the user pressing save and the first network packet.

  1. Watcher fires. The OS reports modified: ~/Dropbox/plan.docx. Editors often write a temp file and rename it over the original, producing three or four events in 50 ms, so the watcher debounces (wait ~1–2 s of quiet) and coalesces events per path.
  2. Indexer checks whether anything really changed. Compare size + mtime + inode against local_files. Same? Skip. Different? Hand to the chunker. This cheap check is what lets a client with 500k files start up without re-hashing 200 GB.
  3. Chunker produces a new block list. Hash each chunk; compare against the previous revision's block list; the difference is the set of candidate uploads.
  4. Indexer queues a pending op in SQLite (pending_ops) with the parent_rev it last saw. If the machine is offline, it stays there. The user sees a "syncing" badge.
  5. Upload, then commit (Step 9). On success, record the new rev and advance the local state.

Client behaviours worth naming

  • Exponential backoff with jitter on every retry — 1 s, 2 s, 4 s ... capped at a few minutes, randomised ±50%. After a regional blip, 300M devices reconnecting in lock-step is a self-inflicted DDoS; jitter spreads them out. Honour Retry-After when the server sends it.
  • Bandwidth throttling — cap upload at a fraction of the link so a sync does not ruin the user's video call.
  • Mobile syncs on demand. Phones do not mirror the whole tree; they fetch metadata, show placeholders, download a file when opened, and upload camera photos only on Wi-Fi and charging. Desktop "files on demand" mode does the same with OS placeholder files (smart sync).
  • Ignore rules — .DS_Store, ~$lock files, node_modules if the user opts in. Syncing editor lock files between devices creates phantom conflicts.

Step 8 — Chunking, dedupe and delta sync

Why split files at all? Four wins: a failed upload retries one 4 MB chunk rather than the whole 20 GB; chunks upload in parallel; an edit re-sends only the chunks that changed; and identical chunks are stored once. The question is where to cut.

Fixed-size chunking and why it breaks

Cutting at every 4 MiB offset is simple and works well for files edited in place (databases, VM images). But insert one byte at the top of a text file and every boundary after it shifts by one; every chunk's hash changes; the client re-uploads the whole file. This is the boundary-shift problem.

Content-defined chunking (CDC)

Instead of cutting at fixed offsets, slide a rolling hash over the bytes and cut wherever the hash of the last few dozen bytes matches a pattern (say, its top 10 bits are zero, giving an average chunk of 210 bytes). Because a boundary depends only on nearby content, an insertion changes the chunk it lands in, and the next boundary re-synchronises. Min and max sizes stop pathological inputs (a file of all zeros) from producing one giant or a million tiny chunks. The runnable demo below uses the Gear hash (the one used by FastCDC) at toy sizes so it runs instantly.

import hashlib, random

rng = random.Random(42)
GEAR = [rng.getrandbits(64) for _ in range(256)]   # one random 64-bit value per byte
MASK64 = (1 << 64) - 1

def fixed_chunks(data: bytes, size: int) -> list[bytes]:
    return [data[i:i + size] for i in range(0, len(data), size)]

def cdc_chunks(data: bytes, avg: int = 1024, min_size: int = 256,
               max_size: int = 4096) -> list[bytes]:
    """Gear rolling hash. A boundary is declared where the hash of the last
    ~64 bytes has its top bits all zero, so boundaries depend on CONTENT,
    not on absolute offsets. avg must be a power of two."""
    bits = avg.bit_length() - 1
    mask = ((1 << bits) - 1) << (64 - bits)        # test the high bits
    chunks, start, h = [], 0, 0
    for i, b in enumerate(data):
        h = ((h << 1) + GEAR[b]) & MASK64          # old bytes shift out after 64 steps
        length = i - start + 1
        if length < min_size:
            continue
        if (h & mask) == 0 or length >= max_size:
            chunks.append(data[start:i + 1])
            start, h = i + 1, 0
    if start < len(data):
        chunks.append(data[start:])
    return chunks

def sha(c: bytes) -> str:
    return hashlib.sha256(c).hexdigest()

def diff(old: list[bytes], new: list[bytes]) -> tuple[int, int]:
    known = {sha(c) for c in old}                  # what the server already has
    fresh = [c for c in new if sha(c) not in known]
    return len(fresh), sum(len(c) for c in fresh)

doc = random.Random(7).randbytes(64 * 1024)        # a 64 KiB "file"
edited = doc[:5000] + b"INSERTED!!" + doc[5000:]   # user types 10 bytes near the top

for name, split in (("fixed 1 KiB", lambda d: fixed_chunks(d, 1024)),
                    ("content-defined", cdc_chunks)):
    before, after = split(doc), split(edited)
    n, nbytes = diff(before, after)
    print(f"{name:16} chunks {len(before):3} -> {len(after):3}   "
          f"new chunks to upload: {n:3}   bytes: {nbytes:6,}")
Output
fixed 1 KiB      chunks  64 ->  65   new chunks to upload:  61   bytes: 61,450
content-defined  chunks  60 ->  60   new chunks to upload:   1   bytes:  2,148

Same 10-byte edit, same file. Fixed-size chunking re-uploads 61 of 64 chunks — effectively the whole file — because every boundary after byte 5,000 moved. CDC re-uploads one chunk, 2 KB. At production sizes (average 4 MiB, min 1 MiB, max 16 MiB) the ratio is the same: one chunk instead of the file.

Picking the chunk size

Average chunkGood forCost
64 KBFine-grained dedupe and small deltas60x more block-index rows and PUT requests; per-request overhead dominates
4 MBThe usual answer: a request per chunk is cheap relative to its bytes; one retry is cheapA tiny edit still re-sends up to 4 MB (fixed by in-chunk deltas below)
64 MBHuge sequential media filesPoor dedupe, expensive retries on flaky links, large client memory

The inputs to the decision are the object store's per-request cost and IOPS, typical client bandwidth, and the file-size distribution. Most files are smaller than one chunk anyway, so for them the chunk is the file.

Deduplication with SHA-256

Each chunk's identity is its SHA-256. Before uploading, the client sends the list of hashes; the server replies with the ones it lacks. This is inline (source-side) dedupe: duplicate bytes never cross the network.

  • Inline dedupe — hash on the client, check before upload. Saves bandwidth and storage immediately. Costs a round trip and a block-index lookup on the write path, and the index must be highly available because uploads depend on it.
  • Post-process dedupe — accept every upload, then a background job finds identical blocks and collapses them. The write path is simpler and never waits on the index, but you pay to transfer and temporarily store the duplicates. Useful as a second pass for data that arrives through paths that cannot hash first (web uploads, API imports).
  • Scope matters. Per-user dedupe (your second copy of a video) is safe and captures most savings. Cross-user dedupe saves more but leaks information: if blocks/check tells me a hash is already present, I can confirm whether anyone has stored a specific document ("confirmation of file" attack), and upload timing reveals it even if the response does not. Common mitigation: dedupe globally on the server side for storage, but always make the client upload the bytes the first time it references a hash, so the network behaviour reveals nothing.
  • Is SHA-256 collision safe? Yes in practice — 2128 work for a birthday collision. Do not use MD5 or SHA-1; SHA-1 collisions are demonstrated, and a crafted collision would let one user's block overwrite another's content.
  • Encryption and dedupe interact. Encrypting each chunk with a random key destroys dedupe. Systems either encrypt with a key derived from the chunk's hash (convergent encryption, keeps dedupe, same privacy caveat) or encrypt at the storage layer with service-managed keys after dedupe.

Delta sync inside a chunk

CDC shrinks an edit to one changed chunk. For large chunks you can go further with an rsync-style delta: the client that has the old chunk and the new chunk computes a binary diff (copy ranges from old + literal new bytes) and uploads only that, and the server reconstructs the new chunk. It only works when the server side knows the old chunk, so it is used for re-uploads of your own file, not for first uploads. Add zstd compression on every block transfer — text and office files compress 3–5x.

Step 9 — Upload and commit, end to end

Client A saves a file that is shared with a folder that Client B and Client C also sync. C is offline.

sequenceDiagram participant A as Client A participant B1 as Block service participant O as Object store participant M as Metadata service participant DB as Namespace shard participant K as Change log participant N as Notification participant B as Client B participant C as Client C (offline) A->>A: watcher event, chunk + hash (CDC) A->>B1: POST /blocks/check [h1..h5] B1-->>A: missing [h3] A->>O: PUT h3 (pre-signed URL, zstd) O-->>B1: object created B1->>B1: verify SHA-256, add to block index A->>M: POST /files/commit parent_rev=41 blocks=[h1..h5] M->>DB: BEGIN, check ACL + quota M->>DB: UPDATE files SET head_rev=42 WHERE head_rev=41 M->>DB: INSERT file_revisions + journal seq=90817, COMMIT M-->>A: 200 rev=42 seq=90817 DB->>K: journal row via CDC K->>N: namespace ns1 changed N-->>B: doorbell ns1 B->>M: GET /delta?cursor=90816 M-->>B: plan.docx rev 42 blocks=[h1..h5] B->>B1: GET h3 only (has h1,h2,h4,h5 locally) B->>B: reassemble, atomic rename into place Note over C: offline, event waits in its response queue C->>M: reconnect, GET /delta?cursor=90790 M-->>C: 27 entries incl. plan.docx rev 42

Bytes first, then one atomic metadata commit, then fan-out by doorbell. Every receiver pulls from its own cursor, so online and offline devices use exactly the same path.

The order of operations, and why

  1. Check hashes before uploading. This is where dedupe pays off: for a copied folder, nothing uploads at all.
  2. Upload blocks directly to the object store. Pre-signed URLs keep 17 Gbit/s off the app servers. Blocks are uploaded in parallel (4–8 at a time) and each is individually retryable, which is resumable upload for free.
  3. The server verifies the hash of what arrived. A client bug or a malicious client must not be able to store bytes under the wrong key — that would corrupt every file that dedupes onto it.
  4. Commit only after every block exists. The commit transaction checks the block index; a missing block means 412, not a dangling pointer. Blocks uploaded but never committed (the laptop lid closed) are orphans, cleaned up by GC after 24–48 h.
  5. One transaction per commit: CAS on head_rev, insert revision, bump namespace.journal_seq, insert journal row, adjust quota. All on one shard because they share namespace_id. This is the ACID requirement, satisfied without distributed transactions.
  6. Notify after commit, from the log. Tailing the journal (CDC or an outbox) means a notification is sent if and only if the commit is durable. Notifying from the request handler would lose events when the process dies between commit and send.
  7. Receivers write downloads to a temp file and rename atomically. A half-downloaded file must never appear in the user's folder, and the watcher must recognise the rename as its own write, not a new local edit to upload back (an echo loop).

Step 10 — Keeping every device in sync

How does a client learn something changed?

ApproachLatencyCost at 120M devicesVerdict
Poll /delta every 30 sUp to 30 s4M req/s, ~99% returning "nothing"Wasteful; fine as a fallback only
HTTP long-poll~1 s120M held requests; each returns only on change or 60 s timeoutDropbox's classic answer; works through every proxy
WebSocket<1 s120M sockets, tiny heartbeatsBest for desktop and web; needs sticky routing
Mobile push (APNs/FCM)Seconds, best-effortFree to hold; rate-limited by the platformOnly way to wake a backgrounded phone

With long-polling, the client asks "anything new after cursor X?" and the server simply does not answer until something changes or 60 seconds pass. The moment it answers, the client calls /delta and re-issues the poll. Either way, the notification carries no file data — just "namespace ns1 moved past your cursor".

The journal and cursors

Each namespace has a gap-free sequence of changes. A device stores, per namespace, the last seq it applied. Sync is then trivially correct: "give me everything after 90816". It survives reconnects, missed notifications, crashed notification nodes and a laptop that was in a drawer for a month. The only special case is a cursor older than the journal's retention, which returns 410 and forces a full listing and local reconciliation.

The runnable model below captures the core rules: commits are compare-and-set on the revision, commits refuse to reference blocks that were never uploaded, and a reconnecting device replays the journal from its cursor. Note that the server never merges anything — conflict resolution is the client's job.

from dataclasses import dataclass, field

@dataclass
class FileEntry:
    path: str
    rev: int
    blocks: list[str]

@dataclass
class Namespace:
    """One workspace (a user's root or one shared folder). Commits to it are
    serialised, so it owns a single, gap-free, increasing journal."""
    files: dict[str, FileEntry] = field(default_factory=dict)
    journal: list[tuple[int, str, int]] = field(default_factory=list)  # (seq, path, rev)
    blocks: set[str] = field(default_factory=set)   # hashes the block store holds

    def commit(self, path: str, parent_rev: int, hashes: list[str]) -> dict:
        need = [h for h in hashes if h not in self.blocks]
        if need:                                     # never point at bytes we lack
            return {"status": 412, "need": need}
        cur = self.files.get(path)
        cur_rev = cur.rev if cur else 0
        if cur_rev != parent_rev:                    # compare-and-set on the revision
            return {"status": 409, "current_rev": cur_rev}
        self.files[path] = FileEntry(path, cur_rev + 1, hashes)
        self.journal.append((len(self.journal) + 1, path, cur_rev + 1))
        return {"status": 200, "rev": cur_rev + 1, "seq": len(self.journal)}

    def changes_since(self, cursor: int) -> tuple[list, int]:
        return self.journal[cursor:], len(self.journal)

def client_commit(ns: Namespace, path: str, parent_rev: int,
                  hashes: list[str], device: str) -> dict:
    """The CLIENT resolves conflicts: it never overwrites, it forks a copy."""
    r = ns.commit(path, parent_rev, hashes)
    if r["status"] == 409:
        base, _, ext = path.rpartition(".")
        path = f"{base} ({device}'s conflicted copy).{ext}"
        r = ns.commit(path, 0, hashes)               # same blocks: zero re-upload
    return {"path": path, **r}

ns = Namespace()
ns.blocks |= {"h1", "h2", "h3", "h4"}               # already PUT to block storage
print(client_commit(ns, "plan.docx", 0, ["h1", "h2"], "laptop"))

# Laptop and phone both went offline at rev 1 and edited the same file.
print(client_commit(ns, "plan.docx", 1, ["h1", "h3"], "laptop"))   # first wins
print(client_commit(ns, "plan.docx", 1, ["h1", "h4"], "phone"))    # stale parent
print(client_commit(ns, "notes.txt", 0, ["h9"], "phone"))          # upload not done

# A tablet reconnects with the cursor it saved last time (seq 1).
changes, cursor = ns.changes_since(1)
print("tablet pulls:", changes, "-> new cursor", cursor)
Output
{'path': 'plan.docx', 'status': 200, 'rev': 1, 'seq': 1}
{'path': 'plan.docx', 'status': 200, 'rev': 2, 'seq': 2}
{'path': "plan (phone's conflicted copy).docx", 'status': 200, 'rev': 1, 'seq': 3}
{'path': 'notes.txt', 'status': 412, 'need': ['h9']}
tablet pulls: [(2, 'plan.docx', 2), (3, "plan (phone's conflicted copy).docx", 1)] -> new cursor 3

The phone's edit is not lost and not merged: it becomes a sibling file. The tablet, which saw neither device, pulls both entries from one cursor and ends up identical to the server.

Step 11 — Conflicts, versions, trash, sharing and security

Conflict handling

A conflict is two commits with the same parent_rev. The first wins the CAS. The loser's client receives 409 and — rather than overwriting or attempting a merge of arbitrary binary formats — renames its version to plan (Amar's MacBook conflicted copy 2026-09-23).docx, commits that as a new file (zero bytes to re-upload, the blocks are already there), and then downloads the winner into the original path. The user resolves it with the application that understands the format. It is deliberately boring: no data loss, no clever merge that is wrong 1% of the time.

  • Why not last-writer-wins? Wall clocks on devices disagree by minutes, and "last" silently discards a day of offline work. That is data loss dressed as a policy.
  • Why not merge? A drive stores opaque bytes. Merging a .psd or a .xlsx is not something a sync engine can do safely. Collaborative merge belongs to editors that own the format (Google Docs, Figma).
  • Other conflicts: edit vs delete (keep the edit — restoring is safer than losing), rename vs rename of the same folder (first wins, second becomes a move of the loser's children), and two new files with the same name in the same folder (the unique index rejects the second; client suffixes "(1)").

Versioning and trash

  • Every commit creates a file_revisions row. Because blocks are shared and immutable, a new version of a 1 GB file whose edit touched one chunk costs 4 MB of storage, not 1 GB.
  • Restore is just a new commit whose block list equals an old revision's. History stays linear and the restore itself is undoable.
  • Delete sets deleted_at and writes a journal delete entry; devices remove the local copy. Trash is a filtered view. A retention job after 30 days deletes the revision rows and decrements ref_count on their blocks.
  • Block garbage collection never deletes a block synchronously. Reference counts drift under crashes and retries, so a periodic mark-and-sweep (walk live revisions, mark referenced hashes, sweep unmarked blocks older than a grace period) is the safety net. A block that is deleted while a commit referencing it is in flight is the classic GC race; the grace period plus a re-check in the commit transaction closes it.

Sharing and permissions

  • Sharing a folder converts it into its own namespace (if it is not one already) and adds an acls row per grantee. Each grantee gets a mounts row placing it in their tree. Moving a folder between namespaces is therefore a re-home of every row — a background job, not a rename.
  • Roles are checked in the metadata service on every commit and delta; the block service authorises GETs by confirming the user can read some revision that references the hash (cached per session).
  • Links are unguessable 128-bit tokens mapped to (file_id, role, expires_at, password_hash); revocation deletes the row. Never encode permissions in a guessable URL.
  • Revoking access removes the ACL row and pushes a delta that tells the grantee's devices to delete their local copy. Be honest: bytes already downloaded to someone's laptop cannot be recalled.

Security

  • TLS for every connection; pre-signed block URLs expire within minutes.
  • Encryption at rest with per-block data keys wrapped by a KMS key; rotating the master key rewraps keys, not petabytes.
  • Audit log of shares, link creation and downloads for business accounts.
  • Per-user rate limits on blocks/check to slow hash-probing.

Step 12 — Scaling each layer

Metadata partitioning

Walk the options, because the interviewer wants to see you reject the weak ones for concrete reasons:

  • Vertical partitioning (users tables on one cluster, files on another). A reasonable first step, but the files tables alone hold hundreds of billions of rows, so it only delays the problem, and any query joining users to files is now cross-cluster.
  • Range partitioning by path (A–C on shard 1 ...). Predictable but badly skewed — far more paths start with /Photos than /Q — and a rename can move a file between shards.
  • Hash partitioning by file_id. Even distribution, but a folder listing or a namespace's journal scatters over every shard, and a commit touching a file and its parent folder becomes a distributed transaction.
  • Hash partitioning by namespace_id — the answer. Everything a commit touches is co-located, so commits are single-shard ACID transactions and /delta is one range scan. Map namespaces to logical shards through a directory (or consistent hashing over thousands of virtual shards) so a namespace can be moved without rehashing everything.

The catch is hot namespaces: a 50,000-person company's shared drive can produce thousands of commits per second into one namespace. Mitigations: give very large namespaces a dedicated shard; split big team spaces into sub-namespaces per top-level folder; and batch journal sequence allocation. The block index is sharded separately by hash, which is naturally uniform.

Caching

  • Block cache in front of the object store for hot blocks — a file just shared with a 1,000-person team is downloaded 1,000 times in an hour. Blocks are immutable, so there is no invalidation at all; LRU eviction is the only policy decision. A 256 GB cache node holds ~64k 4 MB blocks; size the fleet from the measured hot set, not total data. A CDN in front of shared-link downloads does the same job at the edge.
  • Metadata cache for folder listings, ACLs and namespace-to-shard mappings. Unlike blocks this is mutable: key it by (namespace_id, journal_seq) or invalidate on commit, and never serve commits' CAS checks from cache.
  • The client is the biggest cache. Each device's SQLite and local block cache means most reads never reach the server.

Load balancing

Round robin is fine to start: stateless servers, and a health check removes dead ones. It breaks down when requests have wildly different costs — a 4 MB PUT and a 200-byte hash check look the same to it — so one server ends up with all the slow uploads. Move the block pool to least-outstanding-requests or load-reporting balancing. The notification tier needs sticky, connection-aware balancing and a slow drain on deploy.

Block storage and cold tiering

Access to files decays fast: most blocks are read heavily in their first week and rarely after 90 days. Track last access per block (sampled, not on every read) and move cold blocks to cheaper tiers — S3 Standard to Infrequent Access to Glacier-class, or in-house from SSD-fronted to dense HDD with wider erasure codes. Keep the metadata hot always, so listings are fast even when content is cold; the first open of an archived file may take seconds, and the client shows progress. Tiering cuts storage cost by 50–70% on a 10 PB footprint.

Step 13 — Consistency, decided per feature

DataGuaranteeWhy
File commit (block list + rev)Strong, serialisable per namespaceAtomic flip; CAS on head_rev is the conflict detector
Folder tree (moves, renames)Strong per namespaceA move must never duplicate or lose a subtree
Journal orderStrong, gap-free per namespaceCursors are only correct if seq never skips or reorders
BlocksImmutable, so trivially consistentContent-addressed: a key's bytes can never change
Other devices' viewEventual, secondsEach device converges by pulling its cursor
ACL revocationStrong on the server, eventual on devicesServer checks every request; already-synced copies are gone only after the device pulls
Quota usageStrong-ish (in the commit TX), rolled up across namespaces asyncSlight overshoot is acceptable; a lost upload is not
Block ref countsEventual, repaired by mark-and-sweepNever trust a counter alone to delete user data

Step 14 — Failure modes

What failsWhat the user seesMechanism
Upload interrupted mid-fileSync resumes where it stoppedChunk-level retries; blocks/check skips chunks already uploaded
Blocks uploaded, commit never sentNothingOrphan blocks unreferenced; GC removes after grace period
Commit response lost, client retriesNothingIdempotency-Key returns the stored result instead of a spurious 409
Two devices edit offlineA "conflicted copy" fileCAS on head_rev; loser forks
Notification node diesChanges arrive after reconnect (seconds)Clients reconnect with jitter; cursors make missed doorbells harmless
Metadata shard primary failsCommits for that shard's namespaces pause ~30 sSemi-sync replica promoted; clients back off and retry. Never accept commits on an async replica — you would fork the journal
Object store region impairedDownloads slower; uploads queue locallyCross-region replicated blocks; client keeps pending ops in SQLite
Corrupt block on diskNothingHash verified on read; erasure coding rebuilds; background scrubbing
Client bug deletes 100k local filesFiles vanish everywhere, then come backMass-delete detection prompts before syncing; 30-day trash plus namespace-wide "rewind to time T"
Ransomware encrypts the sync folderGarbage files everywhereVersioning is the backup: detect entropy spike, offer bulk restore to pre-attack revisions
Echo loop (download triggers re-upload)Endless "syncing"Client records its own writes in SQLite and ignores the watcher event
Journal cursor too oldLonger first sync410 → full listing, reconcile by hash against local files

Step 15 — Observability

  • Sync SLIs: commit-to-visible latency on another device (measure with canary accounts that write on one device and watch on another), pending-ops age on clients (reported in telemetry), conflict rate per million commits.
  • Efficiency: dedupe ratio, bytes uploaded vs bytes changed (delta effectiveness), cache hit rate for blocks and listings.
  • Correctness: hash mismatches on PUT and on read, orphan block volume, ref-count repairs by the sweeper, and a nightly job sampling files end to end (metadata → blocks → bytes → hash).
  • Infrastructure: per-shard commit p99 and replication lag, notification connection count and reconnect storms, object-store error rates by tier.

The trade-off summary — how to close

  • Metadata and blocks are separate planes. Strong consistency is paid for only on the small plane; the huge plane is immutable and needs none.
  • Relational, sharded by namespace, not NoSQL. Single-shard ACID commits beat reimplementing transactions. The price is hot namespaces, handled by dedicated shards.
  • Content-defined 4 MB chunks with SHA-256. Edits cost one chunk, retries are cheap, dedupe is automatic. The price is a 120-billion-row block index and client CPU for hashing.
  • Inline dedupe, scoped to avoid leaking existence. Saves bandwidth now; post-process catches the rest.
  • Doorbell plus cursor, not pushed payloads. A missed notification costs seconds, never correctness.
  • Conflicted copies, not merges or last-writer-wins. Ugly but lossless.
  • Versions are almost free because blocks are shared; cold tiering keeps the old ones cheap.
  • What I would build first: fixed 4 MB chunks, one Postgres, S3, polling every 30 s. Then CDC, long-poll, and namespace sharding as the numbers demand.
// Write your solution here
// Write your solution here
// Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 15Web CrawlerFrontier design, politeness, dedupe, traps and distributed fetching.