15 — Design Google Drive

“Design a file sync and sharing service. Files upload, download, sync across devices, and are shared with other people.”

A file sync and sharing service: Dropbox, Google Drive, OneDrive and iCloud Drive are all the same system.

By the end you will be able to do four things:

• Say exactly how many bytes cross the network when a 50 MB spreadsheet changes by one kilobyte, and why.
• Explain why a file boundary computed from content survives an edit that a boundary computed from position cannot.
• Resolve a conflict between two devices that both edited while offline, without destroying either edit.
• Price the privacy side channel that sharing storage across users opens.

The second one is the one to over-learn. It is called content-defined chunking, it is a two-line argument, and almost nobody produces it on a whiteboard. You should be able to close the chapter and explain it to someone else from memory.

The concrete input and the concrete output

In goes a change to a file in a folder on one device: someone edits a cell, renames a document, or drops a photo in.

Out comes that same folder, in that same state, on every other device that user owns and on every device the file is shared with, within about a second. On the wire between them: as few bytes as the change can possibly be expressed in.

Underneath, one change produces three concrete 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, and why it is only worth ninety seconds

Every candidate reaches for the same first sentence: metadata in a database, bytes in object storage. Three words in that sentence carry the whole chapter, so pin them down now.

• Metadata is the small mutable facts about a file: name, parent folder, size, revision number, who may read it.
• Object storage is a service that 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 of the rest. A file becomes a list of chunks rather than a run of bytes. What decides where one chunk ends and the next begins is the subject of Deep dive 2 content defined chunking and the insert that kills fixed blocks.

That split — small facts in a database, big bytes in a blob store — is correct. It is also where the interesting part starts rather than ends.

The interview is the four questions after it:

1. What exactly goes on the wire when a 50 MB file changes by 1 KB?
2. How does a device find out something changed?
3. What happens when two devices change the same file while both are offline?
4. Who owns a chunk that eight thousand users share?

Three places candidates lose this round:

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

What you can skip

Three other chapters are referenced for depth. None of them is required reading first, and everything borrowed from them is restated here in a sentence at the point of use.

• Chapter 02 is where the estimation habits come from.
• Chapter 05 is the hash ring that spreads the metadata store across machines.
• Chapter 06 is the same family of conflict machinery, with one crucial difference that 9b detecting the conflict costs one integer not a vector clock makes precise.

1. Framing: what decision, and what breaks

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.

Four adjectives in that sentence need definitions:

• 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, and the old ones stay exactly as they were.

“Cannot share a transaction” is the load-bearing half. A database and an object store are separate systems. There is no single atomic operation that either writes both or writes neither. A crash can always land between the two writes, and Deep dive 6 two stores one commit is entirely about living with that.

Almost every hard property in this design comes from that split: four properties the product needs, each with the design work it forces on you.

Say this early: “the bytes are immutable and content-addressed, the metadata is mutable and authoritative, and I will never let those two stores disagree in the direction that loses data.” That buys you the whole two-store discussion later and signals you know where the bodies are.

What actually breaks in production, in order of frequency:

1. A client’s bookmark into the change log expires, and 40,000 devices simultaneously request a full listing of their entire folder tree.
2. A deploy drops every long-lived connection at once, and the storm of devices reconnecting is larger than the traffic those connections were serving.
3. A shared folder produces duplicate copies of conflicting files faster than the humans can delete them.

Each of those gets a section below. None of them is a coding bug; all three are consequences of design choices made in the first ten minutes.

2. Requirements

What the product must do is the short list; the seven measurable promises after it are where linearizability, a one-second notification budget and a bandwidth target come from, and where the architecture is decided.

Functional

The capabilities the product must have, none of them surprising:

• 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, said explicitly: real-time collaborative editing (that is operational transform, an algorithm that rewrites concurrent edits so they can both be applied inside a document format the server understands — not something a file store can do), full-text search, and the desktop client’s filesystem watcher. Each is real work; none of it moves the architecture.

Non-functional — the ones that shape everything below

Two terms in the table need plain definitions before they can constrain anything.

• Linearizable means every operation appears to take effect at one instant between its start and its finish, so all readers agree on a single order of events. In practice 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.

Each promise below is paired with the fact about users or hardware that leaves you no choice about it.

The asymmetry to name out loud: metadata needs linearizability and is 0.02% of the bytes; blobs need only durability and are 99.98% of the bytes. (3b metadata and how small it is computes that split.)

That asymmetry 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. Eventual consistency means replicas are allowed to disagree for a while and are only guaranteed to converge once writes stop. It is the opposite end of the scale from the linearizability defined just above.

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.

3. Back of the envelope

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

Two abbreviations recur. DAU is daily active users, the number of distinct people who touch the service in a day. QPS is queries per second, the request rate the service must absorb.

One rounding convention runs through every block below: a day is 86,400 seconds, and this chapter calls it 100,000. That is the standing discipline of chapter 02. It costs about 15% accuracy and buys you the ability to do every division in your head. The two places the chapter deliberately breaks the rule — where a number is quoted as a result rather than used as an intermediate — are flagged where they occur (Deep dive 5 cross user dedup and the side channel it opens and Bottlenecks and scaling).

3a. Users, bytes, and what the naive design costs

The naive design is the one where any change re-uploads the whole file. Pricing it first is what makes every byte-saving technique later in the chapter measurable rather than asserted.

Quota utilization below means the fraction of their allowance users actually fill, which is far less than all of it. The block starts from six assumptions and derives five numbers; the two that matter are the 100 PB corpus and the 16.7 Gbps of sustained ingress.

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

logical bytes stored
  50,000,000 x 10,000,000,000 x 0.20    =  100,000,000,000,000,000
the same, in PB
  100,000,000,000,000,000 / 1,000,000,000,000,000  =  100
file changes/day
  10,000,000 x 10                       =  100,000,000
write QPS
  100,000,000 / 100,000                 =  1,000
peak, at 3x
  1,000 x 3                             =  3,000

bytes/day if every change re-uploads the whole file
  100,000,000 x 0.90 x 100,000          =  9,000,000,000,000
  100,000,000 x 0.10 x 20,000,000       =  200,000,000,000,000
  9,000,000,000,000 + 200,000,000,000,000  =  209,000,000,000,000
average bytes per change
  209,000,000,000,000 / 100,000,000     =  2,090,000
sustained ingress at that rate, in Gbps
  209,000,000,000,000 x 8 / 100,000 / 1,000,000,000  =  16.7
peak, at 3x, in Gbps
  16.7 x 3                              =  50.1
large files' share of the changed bytes
  200,000,000,000,000 / 209,000,000,000,000  =  0.957

Three readings come out of that block.

100 PB of logical data puts you in object-storage territory immediately. No database holds this. It also makes every percentage point of deduplication worth a petabyte, which is why Deep dive 1 what block level sync actually saves bothers to price dedup at all.

1,000 writes per second is unremarkable. It is comparable to the URL shortener in ch 08. The metadata tier is not the hard part of this problem.

16.7 Gbps — gigabits per second, sustained around the clock — is the hard part, and ten percent of the changes carry 96% of it. That last figure is the 0.957 on the final line of the block: the 20 MB files are a tenth of the changes and 96% of the bytes.

Every byte-saving technique in this chapter aims at that 10%. None of it helps the other 90%, because a 100 KB file is smaller than a single chunk and there is nothing inside it to diff. Saying that out loud is the difference between “we use delta sync” — shipping only the pieces of a file whose contents changed rather than the whole file, priced in Deep dive 1 what block level sync actually saves — and knowing what delta sync can actually reach.

3b. Metadata, and how small it is

Metadata matters out of proportion to its size, because its size determines whether you can afford to make it strongly consistent — and the answer turns out to be an easy yes.

The chunk-map row count below uses the 1 MB average chunk size that 8b how content defined chunking survives it derives rather than assumes, so you can take it on credit for now.

One line of the block is a borrowed parameter, and it is flagged rather than hidden. The first line divides total stored bytes by 2.09 MB to get a file count. But 2.09 MB is the mean size of a change, computed in 3a users bytes and what the naive design costs as 209 TB/day ÷ 100 M changes/day. Nothing so far establishes that the mean file is the same size as the mean change.

It is a stand-in, used because no assumption in this chapter fixes a file count directly. Five numbers inherit it:

• 47.8 billion files in the corpus
• 957 files per user
• 13.6 TB of file metadata
• the 271,788-byte tree listing in 10b what the device fetches a cursor never the tree
• the 181x cursor-versus-tree ratio in the same section

Say “I am using mean change size as a proxy for mean file size” when you write that line down. It is in the assumption ledger as an ask it, and it is the cheapest thing in the whole estimate for an interviewer to replace with a real number.

files in the corpus, using the 2.09 MB mean CHANGE size as a proxy
for the mean FILE size -- a borrowed parameter, see the ledger
  100,000,000,000,000,000 / 2,090,000   =  47,846,889,952
files per user
  47,846,889,952 / 50,000,000           =  957

metadata row: file_id 8 + owner 8 + parent 8 + name 100 + size 8 + mtime 8
              + head_rev 8 + content_hash 32 + flags 4 + index and row overhead 100
  8 + 8 + 8 + 100 + 8 + 8 + 8 + 32 + 4 + 100  =  284
file metadata, in TB
  47,846,889,952 x 284 / 1,000,000,000,000  =  13.6

chunk-map rows at the 1 MB average chunk derived in section 8b
  100,000,000,000,000,000 / 1,000,000   =  100,000,000,000
chunk map at 40 B/row, in TB
  100,000,000,000 x 40 / 1,000,000,000,000  =  4
metadata total, in TB
  13.6 + 4                              =  17.6
metadata as a fraction of the corpus
  17,600,000,000,000 / 100,000,000,000,000,000  =  0.000176

Metadata is 0.018% of the bytes and 100% of the consistency problem.

17.6 TB fits on 30 to 80 commodity boxes. Spread the rows across them by sharding on owner_id — sharding meaning you split rows across machines by a key, here the owner’s identifier, so everything belonging to one user 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.

4. API sketch

Four of the design’s most consequential decisions are visible in the request shapes alone. The sketch is a sequence: 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.

Some notation, glossed once:

• POST creates, PUT writes a specific named thing, GET reads.
• 200 is success. 409 is conflict — the server disagrees with the client’s belief about the current state. 410 means gone, used below for a bookmark so old the server can no longer serve it.
• WSS is a WebSocket over TLS: a connection that stays open so the server can push to the client, instead of the client repeatedly asking.
• A cursor is that bookmark — a number the client remembers, meaning “I have seen everything up to here”.

One call in the sketch carries a security consequence rather than a performance one. chunks:probe lets a client ask the server which chunks it is missing, and Deep dive 5 cross user dedup and the side channel it opens is why its comment says to read before shipping.

POST /v1/chunks:probe   {"hashes": [...]} -> {"missing": [...]}
                        -- read section 11 before shipping this
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, and each one is defended later.

• Commit is a compare-and-swap on parent_rev. A compare-and-swap, abbreviated CAS, is a write that 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 (9b detecting the conflict costs one integer not a vector clock). A 409 is therefore 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 performing the operation twice has the same effect as performing it once. There is no idempotency key here, no dedupe table and no exactly-once protocol, because a retried PUT writes identical bytes to an identical key. Chapter 08 solves the same retry problem with an explicit key; here the naming scheme solves it on its own.
• Commit is separate from upload. Bytes land first and metadata commits last, and that commit is the linearization point — the single instant at which the change becomes true for everyone (Deep dive 6 two stores one commit). The opposite order is the one that can show a user a file with no contents.
• 410 on an expired cursor is part of the contract. A device that has been offline for two months cannot be served from any change log you are willing to retain, and pretending otherwise means an unbounded log (10b what the device fetches a cursor never the tree).

5. Data model

Six tables carry the design; the decisions inside them that are not obvious are defended after the sketch.

Two bits of schema notation: PK marks the primary key, the column that uniquely identifies a row; BYTEA(32) is a fixed 32-byte binary column, which is exactly the width of a SHA-256 hash.

Three details in the block carry weight: files carries head_rev, which is the single integer the whole conflict story turns on; chunks has no owner_id column at all; and journal is the only table with a sequence number in it.

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 in that schema are worth defending explicitly.

owner_id is the shard key, not file_id

The shard key is the column whose value decides which machine a row lives on.

Every real query in this product is “everything that changed in this user’s tree”. Partitioning by owner keeps that query on a single machine.

Partitioning by file_id would scatter one user’s files across every machine, turning each sync into a scatter-gather: fan the question out to all shards, wait for the slowest one, merge the answers. That is the expensive shape you spend a design avoiding.

Assign users to machines with the hash ring of ch 05. Hash both users and servers onto a circle, and let each user belong to the next server clockwise. Adding the N+1-th machine then relocates only 1/(N+1) of users, instead of the roughly 94% that 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 happens to hold those bytes. There is no owner to shard on.

It is keyed by a 32-byte hash, with no locality and no range queries. That is a pure key-value workload (ch 06), hash-partitioned on the chunk hash itself.

revisions and chunk_map are append-only

Append-only means rows are added and never modified.

The consequence is worth stating slowly, because it is what makes replication cheap here. Two replicas of an append-only table can only ever disagree about whether a row exists yet. They can never disagree about what a row says, because nothing ever rewrites one.

So revision reads can be served from any replica, while 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 the shares table as one row per grant.

Do not model sharing by duplicating 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.

6. 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 in the diagram 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<br/>erasure coded")]
    C -->|"3. commit, CAS on parent_rev"| API
    API --> MDB[("Metadata DB<br/>sharded on owner_id<br/>files, revisions, chunk_map")]
    API --> JRN[("Change journal<br/>per-user monotonic seq")]
    JRN --> NOTIF["Notification service<br/>20 M live sockets"]
    NOTIF -->|"cursor moved"| C2["Other devices"]
    C2 -->|"GET /v1/delta?cursor="| API
    C2 -->|"chunk fetch"| CDN["CDN / signed blob URLs"]
    CDN --> OBJ
    GC["Mark-and-sweep GC<br/>weekly"] --> OBJ
    GC --> MDB

    style MDB fill:#1d3557,color:#fff
    style OBJ fill:#1d3557,color:#fff
    style CDN fill:#2d6a4f,color:#fff
    style NOTIF fill:#bc6c25,color:#fff
    style GC fill:#9d0208,color:#fff

The colours are chapter 01’s published key, and this diagram is the one place in the track where two boxes are blue.

• Blue is the authoritative copy of the data. There are two here, which is the split named in Framing what decision and what breaks: 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%. One authority per half, and neither one overlaps the other.
• Green is read capacity — anything that answers a read without asking the authority. Here that is the CDN, and only the CDN.
• Orange is a box sized by something other than processor time. The notification tier is sized by open sockets and blast radius, never by CPU (10a waking the device).
• Red is the one thing you cannot undo, which is the sweep that deletes bytes (Deep dive 6 two stores one commit).

The write path, arrow by arrow

The desktop or mobile client does three jobs before it speaks to the server at all. A watcher notices the file changed. A chunker splits it into pieces. A local index remembers the hash of each piece.

Then come the three numbered arrows.

1. probe chunk hashes asks the metadata API which of those hashes the server is missing.
2. PUT missing chunks sends only those, to the block service — a separate tier whose only job is moving bytes into and out of the object store. The object store keeps them content-addressed (the key is the hash of the contents) and erasure coded (a redundancy scheme priced in Deep dive 1 what block level sync actually saves).
3. commit, CAS on parent_rev writes the new revision. CAS is compare-and-swap, defined in Api sketch.

That third arrow updates two stores at once. It writes the file’s metadata into the metadata DB, sharded by owner_id, which holds the files, revisions and chunk_map tables. And it appends one row to the change journal, a per-user monotonic sequence — monotonic meaning the numbers only ever increase, so a client can say “everything above 4,102, please” and get an unambiguous answer.

The read path, which is deliberately anticlimactic

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 does two pulls of its own. It issues GET /v1/delta?cursor= to find out what changed. Then it fetches any chunks it lacks.

Those chunk fetches go through a CDN — a content delivery network, meaning caching servers placed near users — using signed blob URLs. A signed URL is a short-lived authenticated link that lets a cache deliver a private object without the cache itself ever holding the user’s credentials.

Off to the side sits the node labelled Mark-and-sweep GC weekly. GC is garbage collection: reclaiming chunks that no file references any more. Deep dive 6 two stores one commit explains why it beats counting references.

The five assertions this picture makes

Each one gets a section below to earn it.

1. The client chunks the file before it talks to anyone (Deep dive 2 content defined chunking and the insert that kills fixed blocks).
2. Bytes go to a different service from metadata, and they land first (Deep dive 6 two stores one commit).
3. The commit is a compare-and-swap (9b detecting the conflict costs one integer not a vector clock).
4. Notification is a cursor bump and never a payload (Deep dive 4 how a device finds out and why the cursor beats the tree).
5. The object store is garbage collected rather than reference counted (Deep dive 6 two stores one commit).

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.

7. Deep dive 1: what block-level sync actually saves

The technique the whole product is sold on deserves a real price — and then the thing candidates skip: a check whether it still looks impressive applied to the whole fleet rather than to one flattering file.

Block-level sync, also called delta sync, means splitting a file into pieces and uploading only the pieces whose contents changed, instead of the whole file.

Start with the single file, because that is the number the interviewer asks for first. The block below compares three ways to ship a 1 KB edit to a 50 MB file.

a 50 MB file, edited by 1 KB

naive, re-upload the whole file, in bytes
  50,000,000
fixed 4 MB blocks, ship the one block containing the edit, in bytes
  4,000,000
saving factor
  50,000,000 / 4,000,000                =  12.5
1 MB content-defined chunks, ship the one chunk, in bytes
  1,000,000
saving factor
  50,000,000 / 1,000,000                =  50

12.5x for 4 MB blocks, 50x for 1 MB chunks, on the file the technique applies to.

Now the honest part, which separates this answer from the memorized one. Run the same technique across the whole fleet, using the change mix from 3a users bytes and what the naive design costs.

The next block sorts the 100 million daily changes into three buckets and adds up what each bucket still costs after delta sync. Watch what happens to the third bucket, which is the one delta sync cannot touch.

assume  of the large-file changes, 80% are edits to a file the server
        already holds and 20% are new files; an edit dirties 2 chunks
        (section 8b derives the 2). Small files are under one chunk and
        always ship whole.

small files, untouched by delta sync
  100,000,000 x 0.90 x 100,000          =  9,000,000,000,000
large-file edits, 2 chunks of 1 MB each
  100,000,000 x 0.10 x 0.80 x 2,000,000 =  16,000,000,000,000
new large files, shipped whole
  100,000,000 x 0.10 x 0.20 x 20,000,000  =  40,000,000,000,000
total after delta sync
  9,000,000,000,000 + 16,000,000,000,000 + 40,000,000,000,000  =  65,000,000,000,000
saving over the naive 209 TB/day
  209,000,000,000,000 / 65,000,000,000,000  =  3.2
new-file bytes as a share of what remains
  40,000,000,000,000 / 65,000,000,000,000  =  0.615

Delta sync is 50x on the file and 3.2x on the fleet, because after it runs, 62% of the remaining bytes are first-time uploads that no diff can shrink.

That is the sentence to say out loud. It also points at what to attack next: the only thing that removes first-upload bytes is discovering that somebody else already uploaded them. That is deduplication, and the next block prices it.

The same block prices how the stored bytes are protected once they land, which needs three terms.

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

assume  25% of newly uploaded chunks already exist somewhere in the store

bytes that dedup away
  40,000,000,000,000 x 0.25             =  10,000,000,000,000
upload after delta and dedup
  65,000,000,000,000 - 10,000,000,000,000  =  55,000,000,000,000
combined saving over naive
  209,000,000,000,000 / 55,000,000,000,000  =  3.8

corpus with no dedup, in PB
  100
corpus with 25% cross-user dedup, in PB
  100 x 0.75                            =  75
physical bytes at replication factor 3, in PB
  75 x 3                                =  225
Reed-Solomon (10,4) overhead
  14 / 10                               =  1.4
the same corpus erasure coded, in PB
  75 x 1.4                              =  105
saved by coding instead of replicating, in PB
  225 - 105                             =  120

Deduplication moves the bandwidth saving only from 3.2x to 3.8x. That is a modest gain, and it is not the reason to do it.

The storage win is the real one: dedup removes 25 PB of logical data, and erasure coding saves a further 120 PB of physical media — the same conclusion ch 02 reaches for cold photos.

Quote the deduplicated corpus when you say that. The 120 PB is 75 x (3 - 1.4), computed on the 75 PB that survives dedup. Start from the raw 100 PB and the number does not reproduce.

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 actually lost.

That is fine for cold data, where failures are rare relative to the read volume. It is unacceptable for the hot working set, where the repair traffic competes with live reads. Keep the last 30 days replicated and erasure-code everything older.

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

Deep dive 1 what block level sync actually saves priced delta sync but never said what a chunk boundary is — and the obvious answer fails catastrophically on an ordinary edit.

This is the best deep dive available in this problem, and it is a two-line argument almost nobody produces on the whiteboard. Content-defined chunking, abbreviated CDC throughout, is the technique that fixes the failure.

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

8a. Overwrite is fine; insert loses everything

Two edits that feel equally small to a user separate the schemes: fixed-size blocking handles one perfectly and the other not at all.

The measure used is write amplification: the number of bytes the system actually transfers divided by the number of bytes the user actually changed. A write amplification of 1 is perfect. Higher is waste.

Take the 50 MB file, cut into fixed 4 MB blocks. Run two separate experiments on it:

• Overwrite. Replace 1 KB at offset 30,000,000. The file stays 50 MB. Nothing moves.
• Insert. Add 1 KB at offset 0. The file becomes 50 MB + 1 KB, and every byte after the insertion point slides 1,024 positions to the right.

The block below prices both. The two lines to compare are “fraction of the file re-uploaded” — 0.077 in one case, 1 in the other.

blocks in the file
  50,000,000 / 4,000,000                =  12.5     -- so 13, the last partial
the block containing offset 30,000,000
  30,000,000 / 4,000,000                =  7.5      -- so block 7

OVERWRITE -- blocks whose bytes changed
  1
fraction of the file re-uploaded
  1 / 13                                =  0.077

INSERT -- blocks whose bytes changed
  13
fraction of the file re-uploaded
  13 / 13                               =  1
write amplification against the 1 KB actually written
  50,000,000 / 1,000                    =  50,000

The overwrite result is 7.7% of the file re-uploaded. That is respectable, and it is exactly why fixed blocking survives in tutorials.

The insert result is the one that matters, and it is worth walking through slowly because it is the whole argument.

A fixed block boundary sits at a fixed offset. Block i is defined as the bytes living at offsets [4,000,000i, 4,000,000(i+1)) — nothing about its contents enters into it. After the insert, every byte has shifted right by 1,024, so those same offsets now hold the old file’s bytes [4,000,000i - 1,024, 4,000,000(i+1) - 1,024).

Make it small enough to see. Say blocks are 4 bytes wide and the file is ABCDEFGH, so block 0 is ABCD and block 1 is EFGH. Insert X at the front and the file is XABCDEFGH. Block 0 is now XABC and block 1 is DEFG. Neither block holds what it held before, even though seven of the eight original bytes were never touched.

No block after the insertion point contains the bytes it did before, so every block hash changes, so the client re-uploads the entire file.

A 1 KB insert at the head of a 50 MB file costs 50,000x write amplification under fixed-size blocking. The same 1 KB written 30 MB in costs 4,000x — one 4 MB block shipped for 1 KB written.

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” from an application that rewrites its container all shift content downstream.

8b. How content-defined chunking survives it

First the mechanism, then the 1 MB average chunk size the chapter uses everywhere else — derived rather than picked.

The mechanism, in three steps

1. Slide a window. Walk a w-byte window along the file, one byte at a time. At every position, the window covers the last w bytes you have read.
2. Keep a rolling hash of that window. A rolling hash is a hash you can update 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. A predicate is a yes-or-no test on the hash. Conventionally: are the hash’s low b bits all zero? If yes, end a chunk here. If no, keep sliding.

Why 1/2^b? A good hash spreads its output evenly, so each of the b low bits is 0 about half the time and independent of the others. All b zero at once is (1/2)^b. With b = 19 that is one position in 524,288, so cuts land on average 524,288 bytes apart.

Nothing in any of those three steps mentions an offset. The cut position depends only on the w bytes ending there.

Why that survives the insert

Here is the two-line argument, and it is the thing to memorize.

A boundary at position p in the original file 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 position 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 of the edit hashes exactly as it did before, so the server already has it.

Only the chunk containing the insertion point is destroyed, plus whatever it takes to resynchronize.

That resynchronization distance is bounded in expectation, because a predicate over a sliding window is memoryless past w bytes. Once the window has slid far enough that it no longer overlaps the edit, the chance of a cut at each position is the same as it always was, regardless of what happened earlier. There is no state carried forward to remember the disturbance.

The same memorylessness is why chunk lengths follow a geometric distribution — the same shape as “how many coin flips until the first head” — with mean 2^b bytes.

Deriving the chunk size

The block below picks the window, mask, floor and cap, and then computes what mean chunk size those choices produce. The line to watch is the mean: it comes out at exactly 1 MiB, which is why the rest of the chapter can spend “1 MB” without having assumed it.

rolling-hash window w, in bytes
  48
cut predicate: low 19 bits zero, so expected bytes between natural cuts
  2^19                                  =  524,288
minimum chunk, below which no cut is accepted, in bytes -- 512 KiB
  524,288
mean chunk = floor + memoryless remainder, in bytes -- 1 MiB exactly
  524,288 + 524,288                     =  1,048,576
maximum chunk, at which a cut is forced, in bytes -- 4 MiB
  4,194,304
probability the remainder runs past the 3.5 MiB of headroom to that cap
  (1 - 1/524,288)^3,670,016             =  0.00091
the same figure as a decimal 1 MB, which is what the rest of the chapter spends
  1,048,576 / 1,000,000                 =  1.0486

chunks in the 50 MB file at that 1 MB average
  50,000,000 / 1,000,000                =  50
chunks that change after a 1 KB insert at offset 0
  2
fraction of the file re-uploaded
  2 / 50                                =  0.04
CDC over fixed blocks, on this edit
  50,000,000 / 2,000,000                =  25

The floor and the cap are not decoration.

Without a floor, chunk length is purely geometric with mean 2^19, and a geometric distribution puts a lot of mass on very short draws. Those tiny chunks each need an index row, so they inflate the chunk map without saving any bandwidth.

Without a cap, a low-entropy region — a long run of zeroes, say — never satisfies the predicate and produces a chunk of arbitrary size.

Where the mean of exactly 1 MiB comes from is the one arithmetic step in that block that is not just a substitution, so here it is spelled out. The floor guarantees at least 524,288 bytes with no cut allowed. Past the floor, memorylessness applies: the expected wait to the next cut is the full period, another 524,288 bytes, exactly as if you had just started. Add them and the mean is 524,288 + 524,288 = 1,048,576 bytes, which is 1 MiB. The 1 MB this chapter spends everywhere else is therefore a computed value, not a chosen one, and the cap only fires on 0.09% of chunks, so it barely perturbs the mean.

One unit note, stated once and then never repeated. The mask is a power of two, so this is the one derivation in the chapter that lands on a binary quantity. 1 MiB is 1,048,576 bytes (2^20); 1 MB is 1,000,000.

Five figures downstream of it round that 1,048,576 to a decimal 1,000,000 and are computed that way, because ch 02’s rounding discipline says an estimate never carries a 1,024: 50 chunks in a 50 MB file, 100 billion chunk-map rows, the 4 TB chunk map, 650 PUTs/s, and the 1.1-machine-hour sweep.

Each of those five is a count obtained by dividing by chunk size, and dividing by a chunk size that is too small makes the count too large. The error is 1,048,576 / 1,000,000 = 1.0486, so all five are 4.86% high, in the same direction, and by less than the assumptions feeding them. The 64 KB alternative in 8c why 1 mb and not 64 kb is decimal 64,000 for the same reason.

Fixed blocks re-upload 100% of the file on a head insert; CDC re-uploads 4%. That is 25x, and it is the whole argument.

8c. Why 1 MB and not 64 KB

Chunk size is not only a bandwidth decision — it is simultaneously an index-size decision and a request-rate decision, and those two push the other way.

Smaller chunks find more redundancy and shrink the delta further. They also multiply two costs that are easy to forget.

The block below re-runs two earlier figures — the chunk-map size from 3b metadata and how small it is and the chunk write rate — at 64 KB instead of 1 MB, so you can see both costs move together.

chunk-map rows in the 100 PB corpus at 64 KB
  100,000,000,000,000,000 / 64,000      =  1,562,500,000,000
chunk map at 40 B/row, in TB
  1,562,500,000,000 x 40 / 1,000,000,000,000  =  62.5
against the 13.6 TB of file metadata
  62.5 / 13.6                           =  4.6
chunk PUTs/s at 1 MB, on the 65 TB/day post-delta traffic
  65,000,000,000,000 / 1,000,000 / 100,000  =  650
chunk PUTs/s at 64 KB
  65,000,000,000,000 / 64,000 / 100,000  =  10,156

At 64 KB the chunk map is 4.6x the size of all other metadata combined, and the blob store takes 10,156 writes per second instead of 650.

The shape of the trade is what to remember. 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.

8d. Working code

The argument runs, so the claim “fixed blocking re-uploads everything on an insert” is a passing assertion rather than a promise. The three asserts at the very end are the deep dive.

The first block defines four functions. Three lines inside them carry the whole lesson:

• In fixed_blocks, the boundary is range(0, len(data), size) — pure arithmetic on the index, with data never consulted.
• In cdc_chunks, the boundary is (h & mask) == 0, where h is a hash of recent bytes. The index i appears only to enforce the floor and the cap.
• In uploaded, the server’s knowledge is a set of hashes. A chunk costs bandwidth only if its hash is absent from that set, which is exactly what a real chunks:probe call decides.

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[data[i - window]], window) that mixes the departing byte back out. Rotating by the window width is what makes the second line cancel the first one exactly window steps later.

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

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

def uploaded(old, new):
    """Bytes the client must ship: every chunk of `new` whose hash the
    server does not already hold from `old`."""
    have = {hashlib.sha256(c).hexdigest() for c in old}
    return sum(len(c) for c in new
               if hashlib.sha256(c).hexdigest() not in have)

The toy is not the production chunker shrunk. It is a smaller chunker of the same family, and that distinction is worth writing down before you quote its numbers.

Six parameters change, and no two of them change by the same factor.

Only the floor and the cap share a ratio, so “the toy is 1/16,384 of production scale” would be false. The two places it is false both change a number you might otherwise carry across.

What the toy does reproduce exactly is the thing under test: whether a boundary rule reads offsets or bytes. That is a property of the rule, not of its parameters.

The second block runs both rules over the same 200,000-byte file, twice — once after an overwrite, once after an insert.

random.seed(7)
FILE = bytes(random.randrange(256) for _ in range(200_000))
P = dict(window=16, mask_bits=6, min_chunk=32, max_chunk=256)
BLOCK = 1_000
chunks = cdc_chunks(FILE, **P)

# mean chunk = floor + the remainder its OWN cap allows, not floor + period:
#   32 + 64 x (1 - e^-3.5) = 94.07, because this cap truncates 3% of draws
assert abs(len(FILE) / len(chunks) - 94.07) < 8           # measured 95.1

# case 1 -- OVERWRITE one byte in the middle. Both schemes do well.
over = bytearray(FILE); over[100_000] ^= 0xFF; over = bytes(over)
fixed_over = uploaded(fixed_blocks(FILE, BLOCK), fixed_blocks(over, BLOCK))
assert fixed_over == BLOCK                                # exactly one block
cdc_over = uploaded(chunks, cdc_chunks(over, **P))
assert cdc_over < len(over) / 100          # 150 B: the chunk, plus resync

# case 2 -- INSERT one byte at offset 0. Fixed blocking loses everything.
ins = b"\x00" + FILE
fixed_ins = uploaded(fixed_blocks(FILE, BLOCK), fixed_blocks(ins, BLOCK))
cdc_ins = uploaded(chunks, cdc_chunks(ins, **P))

assert fixed_ins == len(ins)                 # 200,001: EVERY block re-uploads
assert cdc_ins < len(ins) / 100              # 104 bytes: two chunks
assert fixed_ins / cdc_ins > 50              # measured 1,923x

Those last three assertions are the deep dive.

fixed_ins == len(ins) states the failure as a proof: a one-byte insert forced a full re-upload of all 200,001 bytes. cdc_ins < len(ins) / 100 says content-defined chunking shipped under 1% — 104 bytes, which is two chunks. The third line puts the gap at over 50x, and it measured 1,923x.

Nothing in that argument depends on chunk size. It depends only on whether the boundary rule reads offsets or bytes, so the same three lines hold at production parameters, at a couple of hundred times the runtime.

Why the bounds are loose

An assertion advertised as a proof has to survive more than the seed it was written on, and these bounds did not always.

On a 20,000-byte file, changing one character — random.seed(269) instead of random.seed(7) — gives a cdc_ins of 431 bytes against a limit of 200, and a ratio of 46.4x rather than 192x. Two of the three assertions fail.

Swept over 400 seeds, the old bounds failed at these rates:

Three changes fixed all five: widen the file to 200,000 bytes, centre the mean on the value the toy’s own cap implies (94.07, not 96), and loosen the ratio to > 50. Every one of the 400 seeds now passes, with the worst insert ratio at 464x against a bound of 50, and the worst overwrite at 450 bytes against a bound of 2,000.

A test that passes on seed 7 and fails on seed 269 is measuring the random number generator, not the chunker.

The caveat the code does not state

fixed_ins == len(ins) is true here because FILE is high-entropy random bytes. Every shifted block is content the server has never seen, so every block costs a full upload.

Hand the same code an all-zero file and fixed_ins is 1, not 200,001. Every shifted block hashes to a block the server already holds, and fixed blocking looks perfect.

Zero-padded containers, sparse virtual-machine images and repeated headers are ordinary, not contrived, so this is not a corner case you can wave away.

The claim that survives is the mechanism: a fixed boundary is a function of offset, so an insert relabels every block. The 50,000x number is what that mechanism costs on data with no internal repetition.

Where a file is repetitive, fixed blocking gets rescued by deduplication rather than by its boundary rule. That is a different argument, and it buys nothing on the 50 MB spreadsheet this chapter is about.

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

Every sync product must answer this case, and most candidates answer it wrongly: the naive resolution rule turns out to be silent data loss (9a why last write wins is not an option), detecting the conflict costs one integer rather than the elaborate machinery a distributed database needs (9b detecting the conflict costs one integer not a vector clock), and what to actually do about it is a product decision with a number attached (9c resolving it you keep both and you are honest about that).

The scenario is concrete. Device A and device B both hold revision 7 of q3.xlsx. Both go offline. Both edit the file. Both come back.

9a. Why last-write-wins is not an option

Last-write-wins, abbreviated LWW, is the rule that when two versions conflict you keep whichever was written later and discard the other.

“Discard the other” has a price per year, and the objection that a better clock would fix it does not survive the same arithmetic.

The block below needs two assumptions: how often a commit lands against a revision that is no longer current, and how badly two consumer devices’ clocks disagree. Its last two lines are the ones that settle the clock argument.

assume  0.1% of daily changes are committed against a parent revision that
        is no longer head, and clock error between two consumer devices is
        100 ms with conflict gaps uniform over a 10-minute offline window

conflicting changes/day
  100,000,000 x 0.001                   =  100,000
edits destroyed per year under last-write-wins
  100,000 x 365                         =  36,500,000
fraction of conflicts where clock skew flips the winner
  100 / 600,000                         =  0.00017
conflicts/day where LWW picks the wrong winner
  100,000 x 0.00017                     =  17

Last-write-wins silently destroys 36.5 million edits a year, with no error, no log line, and no way for the loser to find out.

The clock is a red herring, and it is worth showing why so that you do not spend the deep dive there.

Clock skew is the disagreement between two machines’ idea of the current time. The block assumes 100 ms of it, against conflict gaps spread over a 10-minute offline window — 600,000 ms — so skew decides the winner in 100 / 600,000 of cases, which is 17 conflicts a day out of 100,000.

Put those two numbers side by side: 17 wrong winners a day, against 100,000 destroyed edits a day. LWW’s defect is not that it sometimes chooses incorrectly. It is that it chooses at all.

A perfect clock — the monotonic-clock machinery of chapter 07, where a clock is never allowed to run backwards — would fix those 17 cases a day and leave 99,983.

9b. Detecting the conflict costs one integer, not a vector clock

How this design relates to a distributed key-value store is the sharpest thing you can say in this interview, so both sides deserve precise statement.

A version vector (also called a vector clock) is a per-object map from every writer that ever touched the object to a counter. It travels with the data, so that any two versions can be compared and declared either ordered or genuinely concurrent.

Chapter 06 needs one because a Dynamo-style store has no single serialization point — no one machine that decides the order of writes to an object. Any replica may accept a write, so causality has to travel with the data or it is lost.

A sync service does have a serialization point: the metadata shard that owns the file. Every commit for that file goes through that one machine. So the whole causality question collapses to a single comparison — was your parent revision still the head revision when you committed?

The block below sizes both approaches on the same file, so the choice is a number rather than a preference.

version-vector entries for a file shared with 20 collaborators at 3 devices each
  20 x 3                                =  60
at 16 B/entry (8 B actor id + 8 B counter), in bytes
  60 x 16                               =  960
against the 284 B metadata row
  960 / 284                             =  3.4
compare-and-swap state instead: one head revision, in bytes
  8
ratio
  960 / 8                               =  120

A version vector on a widely shared file is 3.4x the rest of the metadata row, and it grows with every device that ever touched the file. A compare-and-swap on head_rev is 8 bytes and does not grow. Reserve the vector for genuine multi-writer systems with no common ordering, which this design does not have.

The commit therefore becomes an optimistic concurrency loop. Optimistic means you take no lock, do the work, and check at the end whether anyone got there first. Three steps:

1. Read head_rev.
2. Upload the chunks.
3. Call commit(parent_rev=head).

A mismatch at step 3 comes back as a 409 carrying the current head, and the client reconciles from there. Nothing was locked in the meantime, which matters because step 2 can take minutes.

9c. Resolving it: you keep both, and you are honest about that

Detecting a conflict is cheap. Deciding what to do about it is a product decision with a data-loss number attached.

Four policies are available. Three of them lose nothing, so the choice comes down to where each one actually works.

The third row is the one that costs storage, because keeping both revisions means keeping a second copy of every conflicting file. The block below prices a year of that. The last line is the one that ends the argument: conflict copies as a fraction of the whole corpus.

extra bytes per conflict copy, at the 2.09 MB average
  2,090,000
per day, in bytes
  100,000 x 2,090,000                   =  209,000,000,000
per year, in TB
  209,000,000,000 x 365 / 1,000,000,000,000  =  76.3
as a fraction of the 100 PB corpus
  76,300,000,000,000 / 100,000,000,000,000,000  =  0.00076

Conflict copies cost 0.076% of storage and lose nothing. Last-write-wins costs 0% of storage and destroys 36.5 million edits a year. At that exchange rate there is no argument.

Conflict copies are also what every consumer sync product ships. Dropbox, Drive, OneDrive and iCloud all produce a renamed second file, and not out of laziness: a merge requires understanding the bytes, and a file store is defined by not understanding the bytes.

The real cost is human, and worth naming before the interviewer does. A misbehaving client in a shared folder can generate conflict copies faster than anyone deletes them. Two mitigations, both free:

• Suppress the copy when both revisions have identical content hashes. Concurrent identical saves are common and are not conflicts.
• Name the copy with the device and timestamp. That turns a mystery file into a two-second decision for the user who finds it.

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

Two questions get conflated constantly here, and they deserve different answers. How is the device woken up? is a connection-model question. What does it fetch once awake? is a protocol question, and the wrong answer there costs more traffic than the files themselves.

10a. Waking the device

Three delivery models are compared below, so define them once.

• Short polling. The client asks “anything new?” on a fixed timer, and is usually told no.
• Long polling. The client asks the same question, but the server holds the request open until either something happens or a timeout expires. This removes the latency without removing the requests.
• Push. The client opens one connection and leaves it open. The server writes to it whenever it likes.

The block prices all three against the same fleet. The three numbers to compare are the poll QPS, the reconnect rate, and the delivery latency.

assume  10 M DAU with 2 devices online each

sockets to hold
  10,000,000 x 2                        =  20,000,000
changes a device must learn about per day
  100,000,000 / 20,000,000              =  5

short poll every 30 s -- polls per device per day
  100,000 / 30                          =  3,333
poll QPS across the fleet
  20,000,000 / 30                       =  666,667
fraction of polls that return nothing
  1 - 5 / 3,333                         =  0.9985
mean delivery latency, in seconds
  30 / 2                                =  15

long poll with a 60 s hold -- reconnects/s from timeouts alone
  20,000,000 / 60                       =  333,333
push, at one reconnect per device per hour -- reconnects/s
  20,000,000 / 3,600                    =  5,556
push against long polling
  333,333 / 5,556                       =  60

Short polling is 666,667 QPS to deliver five events per device, 99.85% of it returning “no change,” and still 15 seconds of average latency.

Long polling halves the request rate and removes the latency. The latency is the real win there, since 333,333/s is still an enormous request count.

Push over a persistent connection is what removes the requests: 60x fewer connection setups, and each one avoided is a TLS handshake, not just a packet.

Sizing the socket tier, and the trap in it

This is ch 02’s third estimation exactly, and the trap is worth restating.

20 million open sockets hold about 200 GB of connection state. Divide by the RAM in a machine and you get about three machines. That answer is wrong.

Reality is 40 to 200 machines, because three limits bind before memory does:

• File descriptors. A descriptor is the small integer handle the kernel gives you per open connection, and the operating system enforces a hard per-process ceiling on them.
• Processor time spent on connection setup, which is TLS work, not data transfer.
• Blast radius — how many users a single machine failure disconnects at once. This is a reliability limit rather than a capacity one, and it is the one that usually sets the floor.

Push also adds a cost of its own, and it is the cost that causes the outage.

Jitter means adding a random delay before each retry, so that clients which failed together do not return together. Full jitter means the delay is drawn uniformly from zero up to the current backoff window, rather than being that window plus a small wobble.

The block below prices one deploy that drops every socket, with and without it.

a deploy drops all 20 M sockets; they return over a 5 s window -- connects/s
  20,000,000 / 5                        =  4,000,000
the same, spread over a 10-minute jittered window
  20,000,000 / 600                      =  33,333
reduction from jitter
  4,000,000 / 33,333                    =  120

An unjittered reconnect is a 4 M/s denial of service you performed on yourself, 120 times the jittered rate.

Applying full jitter to the client’s reconnect backoff is mandatory. It is the same arithmetic as the retry storm in ch 04.

Keep long polling as a fallback regardless. Some corporate proxies terminate WebSocket connections, and the fallback costs you a 333,333/s ceiling on a small minority of devices rather than an unreachable product.

10b. What the device fetches: a cursor, never the tree

Waking the device is solved. What it asks for next is a separate decision, and the naive answer — “send me my whole folder tree” — quietly becomes the largest traffic source in the system.

The block compares the two answers on one user, then multiplies both up to the fleet. The last line is the one that decides it: full-tree chatter as a fraction of the actual file bytes the service moves.

full listing of one user's 957 files at 284 B each, in bytes
  957 x 284                             =  271,788
delta since a cursor: 5 changes at ~300 B each, in bytes
  5 x 300                               =  1,500
ratio
  271,788 / 1,500                       =  181
fleet-wide, 20 M devices waking 4x/day on the full-tree model, in bytes/day
  20,000,000 x 4 x 271,788              =  21,743,040,000,000
the same on the delta model, in bytes/day
  20,000,000 x 4 x 1,500                =  120,000,000,000
full-tree chatter against the 65 TB/day of actual file bytes
  21,743,040,000,000 / 65,000,000,000,000  =  0.33

“Send me the whole tree” makes metadata a third of all traffic on the service, to transmit five changes per device. The delta model makes it 0.18%.

The gap widens as accounts age, which is the part that makes the full-tree model worse over time: file count grows, change count does not.

What the cursor actually is

The cursor is the per-user monotonic sequence number from High level architecture: it only ever increases, never repeats, and never goes backwards.

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. A client presents its last seq and receives everything after it.

Three properties come with that structure, and each one is a real requirement rather than a nicety.

• Resumable. A client that dies halfway through a page simply re-requests from the same cursor. The server holds no per-client state, so there is nothing to lose when either side restarts.
• Idempotent. Each entry names a (file_id, rev) pair that the client either already has or does not. Applying an entry twice changes nothing.
• Ordered within a user. That is why the cursor can be a plain counter on that owner’s shard rather than the distributed identifier generator of ch 07. There is no such thing as ordering across users here, and nothing in the product ever asks for one.

The journal is not free storage, so price it before you promise a retention window.

journal rows/day
  100,000,000
at 64 B/row, in GB/day
  100,000,000 x 64 / 1,000,000,000      =  6.4
30 days of retention, in GB
  6.4 x 30                              =  192

192 GB buys a month of offline tolerance. At the scale of this system that is nothing, so retention is a policy choice rather than a cost problem.

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. Put that 410 in the API contract rather than discovering it during an incident.

Then rate limit the resync path, because the failure mode is 40,000 devices deciding to list their entire tree in the same minute.

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

The most attractive form of deduplication is also a privacy vulnerability with a published attack against it. Four mitigations are priced below, and exactly one of them is the one to ship.

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, and they are not equivalent.

• Server-side dedup: the client always uploads, and the server discards a copy it already holds. This saves storage only.
• Client-side dedup: hash the chunk, ask the server whether it already has it, and upload only if the answer is no. This also saves bandwidth, which is why it is tempting.

The second 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 that someone, somewhere in the service, already has that exact content.

The block below does two things: it measures how loud the signal is, then counts how many probes it takes to guess the unknown part of a document.

assume  a 10 Mbps client uplink and a 4 MB chunk

upload time if the chunk is new, in seconds
  4,000,000 x 8 / 10,000,000            =  3.2
upload time if the server already holds it (hash exchange only), in seconds
  0.05
the observable ratio
  3.2 / 0.05                            =  64

probes to confirm a date of birth inside a known template, over 100 years
  365 x 100                             =  36,500
at 100 probes/s, in minutes
  36,500 / 100 / 60                     =  6.1
probes to confirm a 9-digit national ID number in the same template
  10^9                                  =  1,000,000,000
at 100 probes/s, in days -- exact seconds, because this is a reported result
  1,000,000,000 / 100 / 86,400          =  115.7

A 64x timing difference is not a side channel that needs statistics. It is a boolean you can read off a stopwatch.

What the oracle is worth to an attacker depends on how much of the candidate file they must guess, which is what entropy measures: the number of possibilities they have to work through.

A low-entropy field falls in six minutes. A nine-digit one takes 116 days. And “is this specific leaked document in anybody’s account?” costs exactly one probe, because the attacker already holds the whole file and has nothing to guess.

That last case is the one with legal consequences. It turns your storage service into a membership oracle over private data, using documents the attacker already has.

A note on the arithmetic: both durations above divide by 86,400 and not by 100,000. A number that leaves your mouth as a result gets exact seconds. That is the second half of ch 02’s rounding rule, and it is the half candidates drop.

Four mitigations, each priced

1. Server-side dedup only. The client always uploads and the server discards duplicates after receipt. The channel closes completely, because nothing the client can observe depends any longer on other users’ data.

The block below is the bill — the first two lines are what you give up, the last two what you keep.

bandwidth saving given up, in bytes/day
  10,000,000,000,000
as a fraction of post-delta traffic
  10,000,000,000,000 / 65,000,000,000,000  =  0.154
storage saving retained, in PB
  25
physical media that saves, at the RS(10,4) overhead, in PB
  25 x 1.4                              =  35

You give up 15% of bandwidth and keep all 35 PB of physical storage saving. Deep dive 1 what block level sync actually saves already showed that storage, not bandwidth, is where the money is, so this trade is close to free. It is also the standard answer in the industry.

2. Randomized threshold (Harnik, Pinkas and Shulman-Peleg, 2010). For each chunk, draw a secret threshold t uniformly at random from 1..T. Refuse to deduplicate that chunk until the server has seen it at least t times.

Because t is unknown to the client, a “please upload it” answer no longer means “nobody has this”. It might mean “fewer than t people have this”, and the attacker cannot tell which.

The block prices what that costs an attacker. (1 + 20) / 2 is the mean of a uniform draw from 1 to 20, so an attacker pays 10.5 full uploads per probe on average.

copies the attacker must upload before the oracle answers, T = 20
  (1 + 20) / 2                          =  10.5
the six-minute date-of-birth attack, still at 100 probes/s, in minutes
  6.1 x 10.5                            =  64
the same attack if the 3.2 s upload now binds instead, in days
  36,500 x 10.5 x 3.2 / 86,400          =  14.2

A factor of 10.5 sounds decisive, but where it lands depends on which resource is now scarce, and the two answers are very different.

If the server still answers 100 probes a second, the six-minute attack becomes about an hour. That is not a defence. If the attacker’s own 10 Mbps uplink has become the constraint, the same attack takes 14.2 days. That is.

So mitigation 2 is worth shipping only in the second case, and saying which case you mean is the difference between a priced defence and a slogan. It helps that a bulk uploader repeating identical content is trivially visible in the abuse logs.

The cost of mitigation 2 is storing up to T copies of genuinely rare chunks. That is bounded and small, because rare chunks are by definition 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 computed from that chunk’s own plaintext hash. Two users holding identical plaintext then produce identical ciphertext, so deduplication still works while the server never holds readable data.

It is worth knowing, and worth being honest about: it 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. 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. It is the likeliest place in this problem for an interviewer to be carrying a specific published finding.

12. Deep dive 6: two stores, one commit

The split named in Framing what decision and what breaks has a consequence that cannot be engineered away: 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 of the two writes goes first, and only one of the two orders has a survivable failure. Deletion turns out to be the mirror problem, where the same absence of a shared transaction rules out the obvious answer.

There are exactly two orders. The table walks both, and the third column is where the decision is made.

Write the blob first, commit the metadata last, and treat the metadata commit as the linearization point: a file exists exactly when its metadata row does. That rule is why the API splits PUT /chunks from files:commit instead of offering one call.

The safe order still leaves a mess to clean up, so price it rather than waving at it. The block below counts a year of stranded chunks and puts them against the corpus.

assume 0.1% of uploads fail between the blob write and the metadata commit

orphaned chunks/day
  100,000,000 x 0.001                   =  100,000
bytes at the 1 MB average chunk, in GB/day
  100,000 x 1,000,000 / 1,000,000,000   =  100
one year of orphans, in TB
  100 x 365 / 1,000                     =  36.5
as a fraction of the 100 PB corpus
  36,500,000,000,000 / 100,000,000,000,000,000  =  0.000365

An orphan is a chunk that exists in the object store with no metadata row referring to it. They cost 0.037% of the corpus per year.

Two facts keep that bounded. A retried upload writes the same hash to the same key, so retries never compound the total. And the weekly sweep below reclaims what accumulates. 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 — keeping a count of how many files use each chunk, and freeing the chunk 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: an owner-sharded metadata store and a hash-sharded chunk table. There is no such transaction, so updates get dropped, and the two ways to drop one are wildly asymmetric.

• A dropped decrement leaks storage forever. That costs money.
• A dropped increment deletes a user’s data. That ends the product.

That asymmetry is the whole argument. Use mark and sweep instead: walk every metadata row to mark which chunks are still referenced, then sweep away the unmarked ones. The only question is whether the scan is affordable, so price it.

chunk-map rows to scan
  100,000,000,000
bytes at 40 B/row
  100,000,000,000 x 40                  =  4,000,000,000,000
at the standing 1 GB/s sequential, on one machine, in hours
  4,000,000,000,000 / 1,000,000,000 / 3,600  =  1.1

A full sweep is 1.1 machine-hours, so a weekly garbage-collection job costs less than the distributed transaction a reference count would need.

One detail is not optional: the grace period, a minimum age below which the sweep refuses to delete anything.

Here is why it is mandatory. A chunk uploaded ten seconds ago has no referrer yet, because its commit has not happened — that is the whole point of the 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 rather than an error.

24 hours is the standard number. The requirement it has to satisfy is simply that it exceeds your longest upload plus that upload’s retry window.

13. Bottlenecks and scaling

What breaks first, and at what number? Every limit derived above is collected here — the summary you would draw in the last five minutes of the round, with the section each number came from linked where it is not obvious.

The one that gets missed: a shared folder is a fan-out multiplier on the write tier.

Every grantee needs a journal entry, because the cursor is per-user. So a folder shared with 500 people and changed 100 times a day produces 500 x 100 = 50,000 journal appends from one person’s activity.

Three responses. Cap share sizes. Keep each journal entry a reference to the shared object rather than a per-grantee copy of the metadata. And be explicit that a 10,000-member share is a different product with a different design.

14. Failure modes

This system fails in production in eight ways. Each row pairs the trace an engineer would see with the signal that detects it and the mechanism that prevents it — and most of those guards are not runbook steps but ordering decisions taken at design time, too late to add once the incident is underway.

15. Alternatives rejected

Eight designs a reasonable engineer would reach for instead — each genuinely attractive, each ruled out by a number. Several are not wrong so much as right for a different product, and saying which is what turns a rule into a judgement.

Each entry runs in that order: the attraction first, then the number that kills it, then — for most of them — the product where it is the right answer after all. That last line is the one worth carrying into the room.

Fixed-size 4 MB blocks. The attraction is real. It is trivial to implement, needs no rolling hash, gives aligned reads, and produces a smaller index than content-defined chunking at the same average size.

It is rejected because a 1 KB insert at the head of a 50 MB file re-uploads all 13 blocks, which is 50,000x write amplification, and inserts are ordinary rather than exotic.

Fixed blocks are correct when files are only overwritten in place — virtual machine images, fixed-layout databases — which is why some block-storage products still use it.

Whole-file upload, with no chunking at all. This removes a great deal of machinery: no chunk map, no garbage collection, no boundary rule, and 4 TB less metadata.

It is rejected on the fleet number. 209 TB/day instead of 55 is 3.8 times the ingress and 3.8 times the client’s upload time, and upload time is the one resource users actually notice.

Version vectors for conflict detection (ch 06). These give exact concurrency detection with no serialization point at all, which is precisely what makes a Dynamo-style store always writeable.

They are rejected because there is a serialization point here. An 8-byte head revision does the same job as a 960-byte vector, 120 times cheaper, with no pruning heuristic to get wrong.

You should revisit this if clients may ever commit to a regional replica during a network partition — at which point you are building Dynamo and should say so out loud.

Last-write-wins on the server clock. It needs no conflict interface, no extra storage, and almost no code.

It is rejected because it destroys 36.5 million edits a year with no error and no audit trail, while a conflict copy costs 0.076% of storage.

Last-write-wins is acceptable only for regenerable state, which a user’s file is not.

Operational transform or a CRDT. This is the best possible user experience: no conflict copies at all, both edits merged.

It is rejected because it requires the server to understand the file format, and a general file store’s defining property is that it does not.

Automatic merge is correct inside a document editor — that is what Google Docs is, and it is a different service that happens to store its output here.

Short polling for change notification. It holds no connection state, causes no reconnect storms, and works through every proxy on earth.

It is rejected on both axes at once: 666,667 queries per second of which 99.85% return nothing, and 15 seconds of average delivery latency.

Keep long polling as the fallback, at 333,333/s and near-zero latency, for the minority of devices behind proxies that break persistent sockets.

Client-side cross-user deduplication. It removes 15% of ingress at no cost in storage.

It is rejected because it is a membership oracle with a 64x timing signal, able to confirm a specific file’s presence in one probe.

Server-side dedup keeps all 35 PB of physical saving and closes the channel entirely.

Reference counting chunks. It reclaims space immediately, with no scan and no grace period.

It is 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.

Immediate reclamation is not worth a distributed transaction whose failure mode is data loss.

16. Interviewer pushback

Seven questions this design attracts, answered at interview length and in the first person. The italic line under each names what is actually being tested, which is rarely what was literally asked.

“You said you only sync the changed part. Changed part of what, exactly?”

Testing: whether “delta sync” is a mechanism or a phrase.

Of a chunk, where a chunk boundary is decided by content rather than by offset. I slide a 48-byte window over the file, keep a rolling hash of it, and cut wherever the low 19 bits are zero, with a 512 KiB floor and a 4 MiB cap. That makes the mean chunk exactly 1 MiB, which I then spend as a decimal 1 MB everywhere downstream.

A 1 KB edit inside a 50 MB file then costs one or two chunks instead of 50 MB, so 25x to 50x on that file. Across the fleet it is only 3.2x, because after delta sync 62% of the remaining bytes are first-time uploads that no diff can shrink, and 90% of my changes are files smaller than a single chunk. I would rather give you both numbers than the flattering one.

“Why not just use fixed 4 MB blocks? Much simpler.”

Testing: the single best question in this problem.

Because a fixed boundary is a function of offset. Insert one kilobyte at the front of a 50 MB file and every subsequent byte shifts, so block i now holds different content than it did, so all 13 block hashes change and the client re-uploads the entire file. That is 50,000x write amplification for a 1 KB change.

A content-defined boundary is a function of the 48 bytes ending at it, and those 48 bytes moved along with everything else. The predicate still fires at the same content, so every boundary downstream of the edit survives. Only the chunk containing the insert is destroyed, plus about one chunk of resynchronization, because a sliding-window predicate is memoryless past the window. So 4% of the file instead of 100%.

Fixed blocks are right when files are only overwritten in place — VM images, fixed-layout databases — and wrong for documents.

“Two devices edit offline. Walk me through it.”

Testing: whether you will reach for last-write-wins.

Both hold revision 7. Both upload chunks, both commit with parent_rev=7. The first wins and head becomes 8. The second’s compare-and-swap fails and the server returns 409 with the current head. That mismatch is the conflict detection, and it costs 8 bytes rather than a version vector, because unlike Dynamo I have a single serialization point per file.

Then I keep both: the loser is written as a renamed conflict copy carrying the device name and timestamp. I do not merge, because merging requires understanding the format and a file store does not.

The arithmetic for why not last-write-wins: at 0.1% of 100 million daily changes, LWW destroys 100,000 edits a day, 36.5 million a year, silently, while conflict copies cost 0.076% of the corpus. There is no version of that trade where LWW wins.

“How does a device know something changed? Don’t say polling.”

Testing: whether you know what push actually costs.

Push over a persistent connection, with long polling as the fallback for proxies that break sockets. The numbers: 20 million live devices, five changes each per day. Short polling at 30 seconds is 666,667 QPS of which 99.85% return nothing, with 15 seconds of average latency. Long polling halves the request rate and removes the latency. Push cuts connection setups 60x further, to about 5,556 a second.

What push costs is the reconnect. If a deploy drops all 20 million sockets and they return in five seconds, that is 4 million connects a second, 120x the jittered rate, and it is a TLS-handshake denial of service I did to myself. So full jitter over ten minutes and gradual drain. And the notification carries no payload — just “your cursor moved.”

“Why a cursor? Why not send the client the current state?”

Testing: whether you thought about the steady state, not just the first sync.

Because state is 957 files at 284 bytes, which is 272 KB, and the change is five entries at 300 bytes, which is 1.5 KB. That is 181x. Fleet-wide at four wakes a day, the full-state model is 21.7 TB/day of metadata chatter against 65 TB/day of actual file bytes, so a third of my traffic would be re-describing files nobody touched. It gets worse as accounts age, because file count grows and change count does not.

The cursor is a per-user monotonic journal sequence, which also makes sync resumable and idempotent.

The part I have to design rather than hand-wave: the journal is trimmed at 30 days, so a device offline longer gets a 410 and does a full resync, and that path needs its own rate limit, because the failure mode is a whole region resyncing at once.

“You dedup across users. Any problem with that?”

Testing: whether you know the published attack.

Yes, and it is why I dedup server-side rather than client-side. If the client asks “do you already have this hash?” before uploading, that answer is an oracle over everyone’s data. A 4 MB chunk on a 10 Mbps uplink takes 3.2 seconds to upload and about 50 milliseconds to skip, so the signal is 64x and needs no statistics.

Confirming a specific document exists somewhere in the service costs one probe. Guessing a low-entropy field in a known template, like a date of birth, is 36,500 probes, about six minutes.

So the client always uploads and the server dedups after receipt. That costs 15% of ingress and keeps all 35 petabytes of physical storage saving, which is where the money was. If I needed the bandwidth back I would use a randomized threshold — dedup only after the server has seen a chunk t times, t random in 1 to 20 — which forces an attacker through about 10.5 full uploads per probe.

“Metadata database and blob store. What if one write succeeds and the other doesn’t?”

Testing: whether you noticed there is no transaction across them.

There is none, so I pick the ordering whose failure is survivable. Blob first, metadata last, and the metadata commit is the linearization point: a file exists exactly when its row does.

The failure that ordering produces is an orphaned chunk. At 0.1% of uploads that is 100,000 a day, 36.5 TB a year, 0.037% of the corpus, reclaimed by a weekly mark-and-sweep that reads 4 TB of chunk map at 1 GB/s, so 1.1 machine-hours. The other ordering gives you a file that lists on every device and 404s on download, which is worse than any storage cost.

Two details that matter. Chunks are named by their own SHA-256, so a retried upload is idempotent for free and retries never compound the orphan count. And the sweep needs a 24-hour grace period, because a chunk uploaded ten seconds ago has no referrer yet, and deleting it corrupts a file mid-upload.

The assumption ledger

Every design is a set of assumptions with a diagram attached, and the diagram is only correct relative to them. Everything this chapter has leaned on is collected here, so that you can state the design’s foundations in twenty seconds and say what replaces the design when each one fails.

Sort each assumption into one of three bins.

• State it. You are free to pick, and being wrong costs a re-derivation and nothing more.
• Ask it. The answer moves a policy or a threshold, so it is worth an interviewer’s time.
• Load-bearing. If it is wrong the design is not suboptimal, it is invalid. A box appears or disappears, rather than the count inside a box changing.

The one-line test comes from ch 03. Move the assumption an order of magnitude in each direction, then ask whether the set of boxes changes or only the number of machines inside them.

The sentence that makes this visible to an interviewer: “This design rests on four things. One, a small share of changes carries almost all the bytes, which is what makes chunking worth building at all. Two, edits include inserts, which is what forces content-defined boundaries rather than fixed ones. Three, one shard owns each file, which is what lets an 8-byte compare-and-swap replace a version vector. Four, the product may never silently lose an edit, which is what rules out last-write-wins no matter how convenient it is.”

Cheat sheet

Every line below is derived somewhere above; this table is the recall test, not the explanation.

Related: 05 — Consistent Hashing partitions the metadata tier and the chunk table; 06 — Key-Value Store is the conflict machinery you do not need here, and knowing why is the point; 02 — Back-Of-The-Envelope sizes the 20 M-socket notification tier.