Design an object storage service

Design the service that stores files for everyone else: Amazon S3, Google Cloud Storage, Azure Blob Storage, or an in-house equivalent. The interface is just put, get, delete and list. Behind it are hundreds of petabytes on disks that fail every day, and a promise that nothing written is ever lost.

1. The prompt

"Design a service like Amazon S3: users create buckets and store objects of any size by key, read them back, list them and delete them."

What makes it hard:

• Durability at scale: with a million disks, several fail every day; data must survive all of it.
• Two very different problems: billions of small metadata records, and petabytes of bytes.
• Cost: storing three full copies of everything is the obvious answer, and the expensive one.

2. Frame the problem

3. What it must do

1. A user can put an object (any size) into a bucket under a key, and get it back.
2. A user can list objects in a bucket by key prefix, page by page.
3. A user can delete objects, and optionally keep old versions.

Not now: a file-system interface (rename, append, directories), search by content, cross-region replication (a follow-up), billing.

4. How well it must do it

5. Numbers that change the design

Illustrative numbers. Skipped: bucket count (small), and per-user numbers.

6. The nouns

• Bucket: a namespace with an owner, policies and settings.
• Object: key, version, size, checksum, user metadata, and where its bytes live.
• Chunk (or stripe): a piece of an object's bytes, erasure-coded into fragments on different storage nodes.
• Volume: a large append-only file on a storage node that holds many fragments.

bucket     name, owner, region, versioning, policy, lifecycle_rules
object     (bucket, key, version) → size, etag/checksum, content_type, created_at, state, chunks[]
chunk      chunk_id, placement_group, fragments[(node, volume, offset, length)], ec_scheme (6+3)
volume     node, volume_id, size, sealed?                     (fragments appended, never edited)

7. The contract

PUT    /{bucket}/{key}                      body = bytes    → 200 {etag, version}
GET    /{bucket}/{key}?version=…            Range: bytes=…  → bytes
DELETE /{bucket}/{key}                                       → 204
GET    /{bucket}?prefix=photos/&continuation-token=…&max-keys=1000
       → {keys[], next_token}
POST   /{bucket}/{key}?uploads              → {upload_id}         (multipart)
PUT    /{bucket}/{key}?uploadId=…&partNumber=n  body       → {etag}
POST   /{bucket}/{key}?uploadId=…  {parts[(n, etag)]}  → complete

The caller is identified by a signature on each request (or a presigned URL that grants one operation for a limited time); never by a field in the body. Listing is paged with a continuation token, ordered by key.

Data flow (put): front end authenticates → splits into chunks → erasure-codes each chunk → writes fragments to storage nodes in different zones → all needed fragments durable → commit metadata (the moment the object exists) → 200.

8. First working version

Stateless front ends, a metadata service, and storage nodes. The separation of metadata from bytes is the first decision to say out loud.

8.1 Putting an object

The bytes are written first; the metadata commit comes last. If the front end dies halfway, the fragments are orphans with no metadata pointing at them, and a garbage collector removes them later. Readers never see half an object.

8.2 Getting an object

Metadata says where the fragments are; any 6 of the 9 rebuild the chunk. In practice the front end reads the 6 data fragments directly (no decoding needed) and only reads parity when a node is slow or down.

8.3 Listing

Metadata is partitioned by bucket and key range, not by hash, so a prefix listing reads a contiguous range from one or a few shards, in order.

9. Make it hold up

9.1 Redundancy: copies or erasure coding durability · cost

Placement matters as much as the code: fragments of one chunk go to different disks, nodes, racks and zones, so one failure takes at most a fragment or two from any chunk. Some systems use local reconstruction codes (Azure's LRC) so a single lost fragment is rebuilt from a few neighbours instead of k.

9.2 Disks die every day durability

• Scrubbing: every fragment is re-read and checked against its checksum on a schedule, catching silent corruption (bit rot) before a second failure makes it matter.
• Repair: when a disk or node is lost, every chunk with a fragment there is rebuilt from the survivors onto other nodes. Prioritise chunks that have lost the most fragments.
• Spread repair across many nodes so a 20 TB disk is rebuilt in hours by hundreds of peers, not days by one.
• Durability is the race between failure rate and repair speed: faster repair means fewer chunks ever reach their last k fragments.

9.3 Billions of small objects latency · cost

Storing each object as its own file on a storage node means billions of files, file-system metadata lookups on every read, and wasted blocks. Instead, nodes append fragments to large volume files (gigabytes each) and keep an in-memory index of (fragment → volume, offset, length): one disk seek per read. Facebook's Haystack paper described the same idea for photos. Deleted fragments leave holes, reclaimed by compacting volumes in the background.

9.4 Metadata for 100 billion keys consistency · latency

The metadata write is the linearization point: once it commits, every reader sees the new version, which is how read-after-write consistency is achieved. Caches in front of metadata must be invalidated or versioned for this to hold.

9.5 Huge uploads availability

A 5 TB upload over one connection would almost certainly fail somewhere. Multipart upload: the client starts an upload, sends parts (say 100 MB each) in parallel, retries any part alone, then completes the upload with the list of parts. Only the completion writes the object's metadata; abandoned uploads are cleaned up by a lifecycle rule. Reads support byte ranges, so large objects are also downloaded in parallel.

9.6 Deletes, versions and lifecycle cost · rules

• Delete writes a delete marker (with versioning) or removes the metadata row; the bytes are freed later by garbage collection, which checks that no version still points at them.
• Versioning protects against accidental overwrite and deletion; each version is a separate metadata row.
• Lifecycle rules move objects to colder tiers (fewer, denser, slower disks, or tape-like archives with retrieval delays) or delete them after a time.

9.7 The whole design after the deep dives

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Metadata and bytes stored separately, each in the structure that suits it.
• Erasure coding for cost, with copies for small or hot data.
• Range-partitioned metadata for ordered listings, at the cost of split machinery.
• Bytes first, metadata commit last: no partial objects, some garbage to collect.
• Lazy deletion through garbage collection.

What we'd watch: chunks below full redundancy (by how many fragments missing) · repair backlog and rate · scrub coverage · metadata latency p99 per range · request errors by type · storage overhead ratio.

At 10×: more nodes and metadata ranges; durability depends on keeping repair faster than failures as disks get bigger.

Common mistakes:

• Storing bytes in the metadata database.
• Three copies with no discussion of cost.
• Hash-partitioned metadata, then promising fast prefix listings.
• Writing metadata before the bytes are durable.
• Treating disk failure as a rare incident.

13. Try it, check yourself, read more

Erasure coding lab. Pick a scheme, then click storage nodes to fail them. Can the chunk still be read?

Teal = data fragment, amber = parity fragment (or a full copy for replication). Any k of the k + m fragments rebuild the chunk.