Design an Object Store (Amazon S3)

A durability-engineering problem

An object store (S3, GCS, Azure Blob) holds arbitrary blobs keyed by name, in flat buckets, at exabyte scale, with the headline promise of 11 nines of durability. The interview tests how you achieve that durability cheaply (erasure coding), how the metadata layer scales, and the consistency and read semantics (multipart, range GET). It is a durability-engineering problem more than a throughput one.

Erasure coding

Durability drives cost. Full replication (store 3 copies) gives durability and simple reads but costs 3x storage. Erasure coding gives the same or better durability for far less overhead. Split an object into k data shards, compute m parity shards (Reed-Solomon), and store all k + m shards on different disks, racks, or AZs. Any k of the k + m shards reconstruct the object, so you tolerate m simultaneous failures. A common scheme is 10 + 4: 40% overhead to survive any 4 losses, versus 200% overhead for 3-way replication with weaker tolerance. The tradeoff: erasure coding adds CPU (encode on write, reconstruct on degraded read) and read amplification when a shard is missing, so hot small objects sometimes still use replication and large cold objects use erasure coding.

Interview nuance: if you say "just keep 3 copies everywhere," name erasure coding immediately as the cost-saver and quantify it (roughly 1.4x vs 3x). Not knowing erasure coding is the tell that separates junior from senior on this problem.

The metadata service

The blob data is easy (write shards to storage nodes), but you need a massive index mapping bucket + key to the shard locations and object metadata (size, etag, version, ACL). At trillions of objects this index cannot be one database. Partition it: shard the key space (often by a hash of bucket + key, or by key-range for prefix listing), store it in a horizontally scalable KV store or a sharded and replicated database, and cache hot metadata. Listing a bucket with billions of keys efficiently requires a sorted, range-partitioned index so prefix scans do not touch every shard.

Consistency and large objects

S3 now offers strong read-after-write consistency for new objects and overwrites, achieved by making the metadata commit the point of truth (the write is not acknowledged until the index update is durable and visible). Versioning keeps old versions instead of overwriting, so a PUT to an existing key writes a new version and the index points at the latest.

Multipart upload lets a client split a large object into parts, upload them in parallel (and retry individual failed parts), and then issue a complete call that assembles them, which is how you upload terabytes reliably. Range GET lets a reader fetch bytes [start, end], essential for video seeking and resumable downloads; the store reads only the shards covering that range.

Background health: every shard is checksummed on write and periodically scrubbed. A scrubber detects bit rot or a failed disk, reconstructs the lost shards from the survivors, and rebalances data when nodes are added or removed, which is how durability is maintained over years, not just at write time. Lifecycle policies tier cold objects to cheaper storage (S3 to Glacier).

PUT obj -> split into k data shards -> compute m parity (Reed-Solomon)
        -> place k+m shards across racks/AZs -> commit metadata (bucket+key -> shard map)
GET range -> metadata lookup -> read shards covering range -> (reconstruct if shard missing)

Recap: hit 11 nines with erasure coding (k + m Reed-Solomon, roughly 1.4x overhead) instead of 3x replication, scale the metadata index by partitioning bucket+key across a KV store, give strong read-after-write via a durable metadata commit, support multipart upload and range GET, and maintain durability with checksums, scrubbing, and reconstruction.