Design Distributed Storage (S3)

You're asked to design an object storage service like Amazon S3 or Google Cloud Storage. Users create buckets, upload objects of any size up to several terabytes, read them back by key, and expect the service to never lose a byte. It should scale to trillions of objects, serve reads from anywhere, and survive whole machines and whole racks failing without anyone noticing.

Most other system design answers assume object storage already exists. Here you need to design it, so focus on durability, capacity planning, and recovery from hardware failures.

Clarify the requirements

• What's the object size range? A few bytes to several terabytes. The wide range is the point, because small objects and huge objects need different handling within one system.
• What consistency do we promise on writes? Read-after-write for new objects is the modern expectation. Confirm whether overwrites are also strongly consistent because that changes the metadata design.
• Is the namespace flat or hierarchical? Object storage uses a flat namespace. A bucket holds keys, and slashes in a key are a display convention rather than real directories. Establish this early because it affects listing and metadata.
• What durability target? Eleven nines is the industry claim, and it's the number that forces erasure coding rather than plain replication.
• Do we need versioning and lifecycle rules? Both are standard features, and both affect how deletion works.

Assume: objects up to 5 TB, read-after-write consistency for new objects, a flat namespace, and very high durability.

Back-of-envelope numbers

• Capacity: $100\text{B objects} \times 1\text{ MB avg} \approx 100\text{ PB}$ of logical data
• With 1.5× erasure coding overhead: $100\text{ PB} \times 1.5 = 150\text{ PB}$ physical, against $100\text{ PB} \times 3 = 300\text{ PB}$ for triple replication
• Metadata: $100\text{B objects} \times 1\text{ KB} \approx 100\text{ TB}$, which needs its own partitioned store
• Request rate: $1\text{M requests/sec}$ at peak, the vast majority of them reads

The two approaches differ by 150 petabytes of hardware. Use that estimate to explain why erasure coding matters at this scale.

High-level architecture

Components

1. Frontend. Terminates the request, authenticates it, and coordinates the write or read across data nodes.
2. Metadata service. Owns the bucket and key namespace, and records which fragments compose each object and where they live.
3. Metadata store. Partitioned by bucket and key, holding a small record per object.
4. Data nodes. Machines full of disks that store immutable fragments and nothing else.
5. Placement and repair. Decides which nodes hold which fragments, and continuously rebuilds fragments lost to failed disks.

Deep dive 1: separating metadata from data

Split the architecture into two systems. The data plane stores bytes, while the metadata plane stores the small records that locate those bytes.

They have completely different profiles. Metadata records are around a kilobyte, are queried by exact key, need transactional updates, and total a hundred terabytes. Object data is opaque, immutable once written, accessed as a stream, and totals a hundred petabytes. Trying to serve both from one system means either a database holding petabytes of blobs or a blob store being asked to do key lookups and atomic updates.

Splitting them lets each scale on its own terms. Metadata partitions by bucket and key, which keeps every lookup inside one partition since there are no cross-key queries. Data placement is driven by capacity and failure-domain spreading, not by key at all.

Keep object bytes out of the metadata service. Stream writes directly from the client to data nodes, then store only the resulting fragment locations in metadata. This keeps the metadata tier small.

Deep dive 2: erasure coding

Triple replication gives you three copies and 200% overhead. Erasure coding gives you comparable durability at roughly 50% overhead, and explaining why is the core of this question.

An object is split into $k$ data fragments, and $m$ parity fragments are computed from them using Reed-Solomon coding. Any $k$ of the $k + m$ fragments are sufficient to reconstruct the original. A common configuration is $k = 6, m = 3$: nine fragments spread across nine failure domains, tolerating any three simultaneous losses, at $9 \div 6 = 1.5\times$ overhead.

Compare that to triple replication, which also tolerates two failures but costs $3\times$. At a hundred petabytes, the difference is 150 petabytes of disks, power, and floor space.

The cost is paid on reads and repairs. Reading requires contacting $k$ nodes rather than one, which adds latency and makes the read sensitive to the slowest of them. Repairing a single lost fragment requires reading $k$ fragments to recompute it, so losing a disk generates far more network traffic than it would under replication.

That trade points to a hybrid that real systems use: replicate small and hot objects, where the per-read overhead of contacting many nodes dominates, and erasure code large and cold ones, where storage cost dominates.

Deep dive 3: uploading very large objects

A single HTTP request carrying five terabytes is not viable. A connection reset an hour in would mean starting over, and no single machine should have to buffer that much.

Use multipart upload for large objects. The client first initiates an upload and receives an ID. It uploads parts independently, typically between 5 MB and 5 GB each, in parallel and in any order. Finally, it sends a completion request listing the parts in order, and the service creates one logical object by writing metadata that points to those parts.

Several properties follow from this:

• Failed parts retry individually, so a network problem costs one part rather than the whole upload.
• Parallelism raises throughput well beyond what a single stream achieves, because parts land on different data nodes.
• Completion is a metadata operation. No bytes are copied at assembly time, since the object is defined as an ordered list of parts.
• Abandoned uploads accumulate, which is why a lifecycle rule to clean up incomplete multipart uploads after some days is standard.

Deep dive 4: failure and repair

At a hundred petabytes, disks fail constantly. A fleet with a hundred thousand drives and a 2% annual failure rate loses about five drives a day, so repair has to be a continuous background process rather than an incident response.

A background scrubber verifies stored fragments against their checksums. This catches silent corruption, or bit rot that returns incorrect data without an error. Treat a fragment that fails verification as lost.

The repair pipeline reconstructs missing fragments from the surviving ones and places the rebuild on a healthy node. The speed of this matters more than it first appears: durability depends on repairing faster than additional failures accumulate, so repair throughput is what actually produces the eleven-nines number.

Placement is what makes those failures independent. Fragments must be spread across separate racks, power domains, and ideally availability zones, because nine fragments in one rack tolerate zero rack failures no matter what the coding scheme promises.

Deep dive 5: consistency and deletion

Read-after-write for new objects is straightforward when metadata is the source of truth and its write commits before the request returns. Overwrites and deletes are harder, since caches and replicas may still serve the old version, and the usual approach is to make objects immutable internally and have an overwrite create a new version that the metadata record then points at.

Versioning falls out of that naturally. Keeping older versions rather than discarding them is a metadata change, since the fragments already exist and are already immutable.

Deletion is asynchronous, for the same reason it is in any content-addressed system. Removing the metadata record makes the object disappear immediately from the user's perspective, while a background reclaimer frees fragments once nothing references them. Doing it the other way around risks deleting fragments still referenced by another version or by an in-flight read.

Common pitfalls

• Storing object bytes in a database. Metadata and data have different access patterns and different scaling limits, and combining them caps both.
• Routing bytes through the metadata tier. It turns a small coordination service into a petabyte-scale data path.
• Triple replication with no mention of erasure coding. At this scale, that's double the hardware for the same durability.
• Erasure coding tiny objects. Reconstructing a small object from many fragments costs more in round trips than the storage it saves.
• Placing fragments without failure domains. Nine fragments in one rack tolerate one rack failure, whatever the coding math says.
• Synchronous deletion. Versions and in-flight reads can still reference fragments you're about to free.

Leveling signals

Related lessons

Design a Key-Value StoreHard

Build a distributed key-value store with replication and tunable consistency.

Design DropboxHard

Sync files across a user's devices, handling large files and version history.