File Storage & Sync

Clarify the requirements before drawing a box

The functional core is four things: upload and download files; sync changes across all of a user's devices; share files and folders; and keep version history so a user can recover an older revision. Name the nice-to-haves and defer them out loud: real-time collaborative editing, full-text search inside documents, and mobile photo auto-backup are separate systems. Interviewers reward a tight scope.

The non-functional requirements are where this problem earns its hard rating, and they map onto the gym's SLOs. Durability is the first principle: a user's bytes must survive disk, rack, and datacenter loss, which means replication or erasure coding across failure domains (the S3-class target is eleven nines). Availability is allowed to be slightly looser than durability, and the simulator pins it at 98 percent: a brief object-store blip must not fail more than a couple percent of operations. Bandwidth efficiency is a hard requirement unique to this problem, not a nicety: never re-upload data you already have. Metadata operations (list a folder, commit a change, fetch versions) must feel instant, with a 120 millisecond p99 budget, while cross-device sync is allowed to be eventually consistent. The system is write-heavy in bursts (everyone's laptop wakes and uploads at once), so it must absorb a 2x surge without redlining.

• Functional: upload/download, multi-device sync, share, version history
• Non-functional: 11-nines durability, 98 percent availability, bandwidth efficiency (no redundant uploads), fast metadata (p99 under 120 ms), eventually-consistent sync
• Defer: collaborative editing, search-inside-file, photo backup
• Workload shape: write-heavy in bursts, must absorb a 2x surge

Back-of-the-envelope: where the bytes and the ops go

Storage. Assume 500 million registered users at 10 GB stored each. That is 5 exabytes of logical data. Block-level dedup plus compression typically recovers a factor of about two (shared installers, common attachments, unchanged-but-recopied files), and durability via erasure coding adds roughly 1.5x overhead, so physical storage lands around 3.75 exabytes — the low single digits. The headline: blob storage is enormous and grows monotonically, so it must live in a horizontally scalable object store, never a database.

Metadata. Split each file into 4 MB blocks. Five exabytes over 4 MB is about 1.25 trillion blocks. At roughly 100 bytes of metadata per block (a 32-byte SHA-256 hash, a location pointer, a size, a reference count) that is on the order of 125 TB of block metadata, before you add the file tree, version history, and sharing ACLs. Metadata is four-plus orders of magnitude smaller than the blobs — hundreds of terabytes against exabytes, a roughly 40,000-to-1 ratio — but still far too big for one node: it must be sharded across many database servers and shielded by a cache. This is exactly the split the simulator models: a metadata-plus-block service in front of an object store, with a chunk-and-metadata cache between them.

Throughput. Take 100 million daily active users. Sync and metadata operations dominate the request count: at roughly 100 such ops per active user per day you get about 10 billion per day, near 116,000 per second on average and perhaps 350,000 per second at peak globally. The notification path is separate and cheap: 200 million devices each holding a 60-second long-poll yield about 3.3 million poll completions per second, but each is a near-free connection wakeup, not a database query. The simulator abstracts one metadata cell out of this fleet: 12,000 ops per second steady, 24,000 at the bulk-upload peak.

Bandwidth and the dedup win. This is the number that justifies the whole architecture. A user edits one paragraph of a 40 MB document. Naively you re-upload 40 MB. With 4 MB blocks you re-upload the one changed block: 4 MB, a 10x saving. A 100 MB installer shared by a million users costs 100 MB stored once with cross-user dedup, versus 100 TB without: a million-to-one saving on that file. Dedup and delta sync are not optimizations here; they are the difference between a viable service and an impossible bandwidth bill.

High-level architecture and why each piece exists

The request path is a clean chain that mirrors the simulator's scored topology: clients to an API gateway, to a metadata-and-block service, to a chunk/metadata cache, to an object store. A parallel notification service — not a node in the scored cell, but the sync path the rubric rewards — drives device convergence. Here is the role of each box and the reasoning that forces it.

API gateway. Terminates TLS, authenticates, rate-limits, and routes upload, download, and sync calls. It is cheap per request and must never be the bottleneck, so it is provisioned with large headroom and at least two replicas for fault tolerance. In the reference design it is two replicas at 40,000 ops per second each (80,000 effective) so it sits near 30 percent utilization even at the 24,000 peak.

Metadata-and-block service. The brains. It validates uploads, runs the have-I-seen-this-block check, writes file-tree and version entries to the metadata DB, and records the block list (the filejournal) for each file. It is stateless and replicated so it scales horizontally and survives a node death. This is the binding constraint of the whole system, which is why the reference scales it to five replicas at 7,000 ops per second each (35,000 effective).

Chunk and metadata cache. Holds two hot things: recently-read metadata (folder listings, version maps) and the dedup index (which block hashes already exist). A high hit ratio is doing double duty here. It keeps the metadata read load off the slower stores, and it lets the dedup check answer have-I-seen-this-block from memory instead of round-tripping to the object store. The reference pushes its hit ratio to 0.92, so only 8 percent of operations fall through to the object store behind it.

Object store. The durable backbone: content-addressed 4 MB blocks keyed by hash, stored with replication or erasure coding (think S3, or Dropbox's Magic Pocket). It is the source of truth for bytes but is deliberately kept off the hot read path by the cache. Critically, a blob outage should only fail the small fraction of requests that actually miss the cache.

Notification service. A long-poll or pub-sub channel, one logical subscription per user namespace. When a device commits a change, the service notifies that user's other devices, which then pull the metadata delta and fetch only the missing blocks. This replaces the naive design where every device polls its full file list every few seconds.

Deep dive 1: content-addressed chunking and dedup

This is the hard, distinctive part of the problem. Chunk every file client-side into blocks (Dropbox uses 4 MB) and address each block by the hash of its contents, for example SHA-256. The hash is both the block's name and its integrity check. Because the name is derived from the content, two identical blocks anywhere in the system, from any user, collapse to one stored object. That is dedup, and it falls out for free from content addressing.

Upload then becomes a negotiation, not a transfer. The client computes the hashes of all of a file's blocks and sends just the list. The service checks each hash against the dedup index (served from cache) and replies with only the blocks it has never seen. The client uploads those, then commits a metadata record mapping the file and version to its ordered block list. A one-byte change to a 40 MB file uploads one 4 MB block; a file a colleague already synced uploads zero blocks. This is why the cache hit ratio is the highest-leverage knob in the whole design: it backs both the read path and the dedup check.

Fixed-size versus content-defined chunking. Fixed 4 MB boundaries are simple but suffer the boundary-shift problem: insert one byte at the front of a file and every subsequent block shifts, changing every hash, defeating dedup. Content-defined chunking uses a rolling hash (Rabin fingerprinting) to place boundaries at content-determined points, so an insertion only disturbs the chunks around it. The trade-off is CPU on the client for far better dedup on edits. Naming the boundary-shift problem and this fix is what separates a strong answer from a rote one.

One caveat worth raising: cross-user dedup, where the server says I already have that block, leaks a proof-of-possession signal (an attacker who knows a file's hash can probe whether it exists). Mature systems mitigate this by scoping dedup per-user or per-team, or by requiring the client to prove it holds the actual bytes. It is a real security-versus-savings trade-off, not a footnote.

Deep dive 2: sync, delta transfer, and conflicts

Sync has three independent jobs, and the rubric rewards getting all three: notify, transfer only deltas, and resolve conflicts. The simulator's sync question marks full-list polling as the wrong answer for a concrete reason: 200 million devices each listing their whole tree every few seconds is tens of millions of expensive list operations per second against the metadata DB, and it scales with device count rather than with change rate.

Notify. Each device holds a long-poll or pub-sub subscription on its user's namespace cursor. The server replies only when that namespace advances. This makes idle devices nearly free and bounds load by the rate of actual changes, not by the number of watchers. When notified, a device pulls the metadata delta since its last cursor, a small diff, not the whole tree.

Transfer deltas. Sync reuses the chunking machinery: the device learns which blocks the new version references, compares against blocks it already has locally, and downloads only the missing ones. A 4 MB edit to a large file syncs 4 MB, matching the upload-side saving. Notification plus delta sync is what keeps the sync storm in the simulator (the 1.5x and 2x ramps) from saturating the service.

Resolve conflicts. Two devices editing the same file offline will both commit. Each namespace carries a version history; the metadata layer is strongly consistent per namespace (single-writer ordering via the metadata DB), so commits are serialized and a stale write is detected by comparing the parent version. The standard resolution is to keep both: accept the winner and write the loser as a conflicted copy, surfaced to the user, rather than silently losing data. Version vectors generalize this when you need to reason about causality across many replicas.

Bottlenecks under load and how the reference scales them

Trace the simulator's failure timeline against the reference design and the SLO math falls out. The metadata-and-block service is the binding constraint. At the 24,000 ops-per-second peak it runs at about 24,000 over 35,000, roughly 69 percent utilization, which clears the 90 percent saturation ceiling with margin and keeps queueing latency in check. The starter design (three replicas at 4,000, just 12,000 effective) drops half its load at peak; worse, when a replica is killed at 12 seconds under the 1.5x ramp it has only two replicas at 4,000 (8,000) against 18,000 offered, collapsing availability and throughput. The fix is to scale out and shard: the reference uses five replicas at 7,000, so even with that replica dead it still serves 4 times 7,000 equals 28,000 against the 18,000 ramp without a single drop, and once it heals it has the full 35,000 for the 24,000 peak.

The object-store blip at 22 seconds is survived by the cache, not by the blob. With the hit ratio at 0.92, only 8 percent of operations actually need the object store; when it goes dark for 6 seconds only that 8 percent fails. Over the full 38-second run that works out to roughly 98.3 percent availability, just clearing the 98 percent target. The starter's 0.70 hit ratio would fail 30 percent of traffic during the same outage and miss the SLO badly. This is the single most important lesson the gym is teaching: a high cache hit ratio is what turns a datastore outage into a non-event.

The gateway latency spike at 30 seconds multiplies gateway latency 8x for 6 seconds, briefly pushing the instantaneous p99 toward 147 milliseconds. It does not sink the latency SLO because the scored metric is the median of per-tick p99 samples, which is robust to a short spike; the sustained p99 sits near 108 milliseconds at the blob-served peak and lower earlier, so the median lands well under 120 (around 90 milliseconds). The lesson is that transient tail spikes are tolerable if your steady-state path has headroom; the service's 69 percent utilization is what buys that headroom, since queueing latency (modeled as 1 over 1-minus-utilization) explodes as utilization approaches one.

To scale beyond one cell in the real system: shard the metadata DB by user or namespace ID so each shard owns a slice of the tree and writes stay single-shard; replicate read replicas behind the cache; and partition the object store by hash prefix so block writes spread evenly. The gateway and service are stateless and scale by adding replicas; the cache scales by sharding the keyspace (consistent hashing) and raising the hit ratio before adding nodes.

Key trade-offs to state out loud

The cost ceiling forces discipline. The footprint SLO is nine instances, and the reference spends exactly nine: two gateway plus five service plus one cache plus one object store. That is not a coincidence; it is a budget. You cannot brute-force the service to twelve replicas to be safe, because that alone is sixteen instances and breaks the cost SLO. The lean answer is to size the service just past the worst case (peak load with one replica dead) and to buy resilience cheaply by raising the cache hit ratio rather than by adding compute. Recognizing that the cache, not more servers, is the cost-efficient lever is the senior move.

Other trade-offs worth naming: fixed-size chunking (simple, cheap CPU) versus content-defined chunking (better dedup on edits, more CPU). Cross-user dedup (maximum storage savings) versus scoped dedup (weaker savings, but no proof-of-possession leak). Strong per-namespace metadata consistency (clean conflict detection, single-writer ordering) versus eventual cross-device convergence (necessary because devices go offline). And blobs in an object store (cheap, durable, scalable) versus the tempting wrong answer of storing files as database BLOBs, which the rubric scores at zero because databases are the wrong home for multi-gigabyte binaries.