Design an object store (S3-like)

Requirements

Before diving in, ask yourself: if eleven nines means roughly one lost object per ten thousand years per ten million stored, what kind of redundancy mechanism do you actually need — and why can’t a single replicated copy get you there cheaply? The answers shape every decision below. Functional — store an object (opaque bytes) under a key in a bucket; GET it back by key; DELETE it; list keys in a bucket (often by prefix). That’s nearly the whole API: PUT(bucket, key, bytes), GET(bucket, key), DELETE, LIST(prefix). No partial updates — objects are immutable, you replace the whole thing. Multipart upload for large objects. This minimalism is deliberate: a narrow interface is what lets the implementation scale.

Non-functional — the headline is durability: ~11 nines, because customers build their entire businesses on “we will not lose your data.” Then availability (highly available reads/writes), scalability (exabytes, trillions of objects, no practical limit), and cost (it’s bulk storage — every 1× of storage overhead is a fortune at exabyte scale, so paying 3× to replicate everything is painful). Latency is secondary — object storage is throughput-and-durability-oriented, not a low-latency database.

Durability at ~11 nines with minimal storage overhead is the requirement that produces the entire interesting design: it’s why erasure coding exists in the answer at all.

Estimation

Scale:      trillions of objects, exabytes of data, no fixed ceiling
Object size: bimodal — many tiny objects (KB) + many huge ones (GB–TB)
Durability:  ~11 nines (99.999999999%) → ~1 object lost per 1e7 stored per ~1e4 years
Disk reality: a single disk's annual failure rate ~1–4%; at fleet scale thousands fail/day
             → durability MUST come from redundancy across disks/racks/datacenters
Overhead:    3× replication = 200% extra storage; erasure coding (e.g. 10+4) ≈ 40% extra
             at exabyte scale, 1.5× vs 3× is the difference between viable and bankrupt
Metadata:    key → {bucket, size, location/shard map, version, checksum} ≈ hundreds of bytes
             trillions of keys → petabytes of metadata in its own sharded store

The cost line is the whole argument for erasure coding: at this scale you cannot afford 3× replication for cold/large data, so you trade some CPU and reconstruction latency for ~1.5× storage that still hits 11 nines. And the metadata is itself a large distributed database — the index that maps keys to where the bytes live.

High-level design

Split into a metadata service (key → location, the index) and a data plane (the actual byte storage across many storage nodes), behind an API/load-balancer tier. A PUT writes bytes to the data plane (durably, via erasure coding or replication) and records the key→location mapping in metadata; a GET looks up the location in metadata and streams the bytes from the data nodes.

The user sees a flat namespace: a key like photos/2024/cat.jpg is one opaque string, not a path through directories. The slashes are convention for LIST prefix queries, but there are no real folders — which is exactly why the namespace scales to trillions of keys: there is no directory tree to traverse or rebalance, just a giant sorted key→location index that can be partitioned by key range or hash across the metadata store.

Deep dive: durability via erasure coding

When you see “eleven nines” stated as a requirement, translate it immediately: one lost object per ten million stored per ten thousand years. That number tells you replication alone — three copies — is not enough cheaply. To survive disk and machine failures, you must store redundancy. The obvious way is replication: keep N full copies (typically 3), on different racks and datacenters; lose two copies and the third still serves. It’s simple and gives fast reads, but it costs 200% extra storage — at exabyte scale, ruinous.

Erasure coding gets the same or better durability far cheaper. Split an object into k data shards, compute m parity shards (Reed-Solomon math), and store all k+m shards on independent nodes. The guarantee: you can reconstruct the original from any k of the k+m shards, so you tolerate losing up to m shards. A common scheme is k=10, m=4: 14 shards, survive any 4 failures, at only 14/10 = 1.4× storage overhead — versus 3× for triple replication, for better fault tolerance (4 simultaneous losses vs 2). Spread the shards across racks, zones, and datacenters and you get the eleven-nines durability the requirement demands, because the probability of losing more than m shards before repair completes is astronomically small.

Deep dive: metadata service, consistency, and multipart upload

The metadata service is the index: it maps each key to its bucket, size, version, checksum, and the locations of its shards (which nodes hold which shard). It’s a large distributed database in its own right — trillions of keys, partitioned by key hash or range — and it is the part that needs consistency. When a PUT completes, the metadata commit is the moment the object becomes readable, and it must be atomic: an object is either fully indexed (all shards recorded) or not visible at all, never half-written. Modern S3 offers strong read-after-write consistency, meaning a GET immediately after a successful PUT always returns the new object — achieved by making the metadata update the linearization point and not acknowledging the PUT until it’s durably recorded.

Multipart upload solves the 5 TB-over-a-flaky-link problem. The client splits a large object into parts, uploads each part independently (in parallel, and retryable on its own), and finally issues a “complete” call listing the parts; the service stitches them into one object. If part 37 fails at 90%, you retry only part 37, not the whole 5 TB. Parts can upload concurrently for throughput, and the object isn’t visible until “complete” assembles it — so multipart gives you reliability (per-part retry), throughput (parallelism), and atomicity (all-or-nothing completion) for huge objects, which a single monolithic PUT can’t.

Bottlenecks & tradeoffs

The defining tradeoff is redundancy scheme vs object profile: replicate small/hot (cheap reads, small storage hit) and erasure-code large/cold (huge storage savings, costlier reconstruction reads) — getting this wrong wastes either money (over-replicating cold data) or latency (erasure-coding hot tiny objects). The metadata service is the consistency bottleneck and the hot spot: it must be a scalable, strongly-consistent index, and poorly-chosen keys (monotonic prefixes) create hot partitions. Repair throughput matters more than it looks: durability assumes failed shards are rebuilt before enough others fail, so background re-replication/re-encoding must outpace the failure rate — eleven nines is a statement about the race between failure and repair. And the flat namespace is a feature, not a limitation: by refusing filesystem semantics it sidesteps the directory-tree scaling problems, at the cost of expensive prefix operations you must design your keys around. As throughout this unit, the bytes live in the durable data plane and the consistency lives in the metadata index.