Q69 — Design a distributed file storage system (like S3)

What the system must do

Users upload arbitrary files (images, videos, documents, backups) and retrieve them by key. The system must store petabytes of data reliably, serve reads with low latency, and survive disk and machine failures without data loss.

Core operations: PUT(key, data), GET(key) → data, DELETE(key)

Requirements:

• Durability: a file uploaded today must be retrievable years later. Target: 99.999999999% (11 nines) durability.
• Availability: 99.99% uptime for reads and writes
• Scale: billions of objects, petabytes of total storage
• Variable object size: a few bytes to terabytes
• Cost efficiency: cheap storage, expensive computation is the inversion of typical services

The fundamental problem: disk failure is certain at scale

A single hard drive has a roughly 1–2% annual failure rate. With 100,000 drives (a small data center), you expect 3–5 drive failures per day. With millions of drives across a region, multiple drives fail every hour. Storing each file on a single disk guarantees data loss over time.

Durability comes from replication — storing each piece of data on multiple drives, on multiple machines, in multiple racks, across multiple data centers. When one fails, others serve the data and the failed copy is rebuilt elsewhere.

Replication vs Erasure Coding

3-way replication: store three full copies of every file on three different machines. On read, any one copy can serve the data. On machine failure, two copies remain and a third is rebuilt asynchronously. Simple, fast reads (just pick any replica), but 3x storage cost.

Erasure coding: split the file into N data chunks and generate M parity chunks using Reed-Solomon codes. You can reconstruct the original file from any N of the N+M chunks. For example, 6+3 erasure coding: split into 6 chunks, generate 3 parity chunks, store all 9. Any 6 of the 9 chunks reconstruct the full file. Storage overhead: 9/6 = 1.5x (much cheaper than 3x replication).

S3 uses a combination: newly uploaded objects start with 3-way replication for fast durability, and hot objects stay replicated; cold objects transition to erasure coding to reduce storage cost at the expense of slightly higher read latency (reconstruction requires fetching N chunks).

Architecture: separating metadata from data

A file storage system has two distinct concerns:

Metadata: "where is this file stored?" The key (bucket + object name), the file's size, checksum, replication locations, creation time, access control. This is structured data — small, needs strong consistency (you must never point to the wrong location), and is queried on every GET.

Data: the actual bytes. Large, write-once, read-many, doesn't need transactional guarantees beyond durability.

These two concerns need completely different storage systems:

Metadata service: a strongly-consistent distributed database (etcd-like or a distributed SQL store). Small data volume (metadata for billions of objects is gigabytes to terabytes, not petabytes). Needs fast key-value lookups. Needs linearizability for location data.

Data nodes: commodity servers with many large hard drives. Optimized for high sequential throughput, not latency or random access. Organized as a distributed hash table (consistent hashing — Q34) or as a replicated blob storage system.

Upload path

1. Client calls the API: PUT /bucket/key with the file body
2. API server generates an object ID (Snowflake ID — Q61) and determines which data nodes will store the file (via consistent hashing on the object ID)
3. API server writes the data to the primary data node, which replicates to 2 more data nodes in parallel (or uses erasure coding)
4. Once the primary and N replicas acknowledge the write, the API server writes metadata to the metadata store: {key → object_id, size, checksum, [replica_node_1, replica_node_2, replica_node_3]}
5. Return 200 to the client

The checksum (MD5 or SHA-256 of the file content) is stored with the metadata and used to verify data integrity on reads — detecting silent bit rot from disk corruption.

For large files (>5MB), the client splits the file into parts (multipart upload). Each part is uploaded independently and can be parallelized across connections. The API assembles parts into the final object after all parts are uploaded. This enables resumable uploads (retry only the failed part) and parallel upload for large files.

Read path

1. Client: GET /bucket/key
2. API server looks up the key in the metadata store → gets object_id and replica locations
3. API server selects the closest/healthiest replica (load balancing across replicas)
4. API server fetches data from the data node and streams to client (or redirects the client directly to the data node with a signed URL)

Signed URLs: for large object downloads, the API server generates a pre-signed URL — a URL with a cryptographic signature and expiry time that allows direct access to the data node. The client downloads directly from the data node without the API server proxying bytes. This avoids the API server becoming a bandwidth bottleneck.

Failure handling

Data node failure during write: if a replica fails during upload, the write may still succeed if enough replicas (a quorum) acknowledged. The failed replica's chunk is rebuilt asynchronously from the surviving replicas. A background repair job monitors replica counts and schedules rebuild operations for under-replicated objects.

Data node failure during read: route to a healthy replica. The metadata store knows all replica locations; the API server tries the next one on failure.

Bit rot (silent disk corruption): the checksum stored in metadata is verified on every read. If the checksum doesn't match, the data node is corrupt — route to another replica and schedule repair for the corrupt copy.

Data node replacement: when a disk dies, all objects it stored must be rebuilt on new disks from surviving replicas. The repair queue processes objects in priority order (objects with only 1 surviving replica first — most at risk). At scale, this repair queue can have billions of objects — it's a background service that runs continuously.

CDN integration

User-facing reads for popular files (images, videos on a website) should be served from a CDN (Q21), not from the origin data nodes. The CDN caches the file at edge locations globally. The data nodes only serve the CDN on cache miss. This dramatically reduces load on the storage system and latency for end users.

The mental model

Core insight: disk failure is certain at scale → durability requires replication

Durability strategies:
  3-way replication: 3 full copies → simple, 3x cost
  Erasure coding (6+3): 6 data + 3 parity → 1.5x cost, higher read latency
  S3: replicate for hot data, erasure code for cold/archive

Architecture: separate metadata from data
  Metadata service: strongly consistent DB → maps key → {object_id, replica locations, checksum}
  Data nodes: commodity servers with many disks → store raw bytes

Upload:
  1. Generate object_id → determine replica nodes (consistent hashing)
  2. Write to primary → replicate to 2+ nodes → all ack
  3. Write metadata (key → locations) → return success
  Multipart: large files split → parallel upload → assembled at end
  Checksum: computed at upload, stored in metadata

Read:
  Metadata lookup → pick healthy replica → stream bytes (or signed URL)
  Signed URL: client downloads directly from data node (API not in bandwidth path)

Failure handling:
  Write failure: quorum ack → background repair of under-replicated objects
  Read failure: try next replica
  Bit rot: checksum mismatch → mark corrupt, repair from healthy replica
  Repair queue: continuous background process prioritized by replica count

CDN: sit in front for user-facing reads → data nodes only handle cache misses

Scale:
  Metadata: gigabytes to terabytes → distributed consistent DB
  Data: petabytes → thousands of data nodes, consistent hash routing
  Repair: background continuous job, billions of objects

Distributed file storage is where hardware failure is the normal case, not the exception. Every design decision — replication factor, erasure coding, checksums, repair queues, signed URLs — exists to make hardware failure invisible to the user. The system's job is to maintain the illusion that the file you uploaded will be there forever, even though the disk it's on will fail.