Design Object Storage

Most designs in this track end with "the bytes go in an object store". Here you build that box. A user sends PUT photos/2026/cat.jpg with 4 MB of bytes, and years later, after thousands of disks have died and been replaced, a GET must return exactly those 4 MB. Amazon S3 is the kind of product this question means.

The API is tiny and every hard part is underneath: keeping billions of names apart from petabytes of bytes, turning "never lose data" into arithmetic, storing a 1 TB object, and reclaiming space without deleting something still in use. For the user's side, read Blob Storage; this lesson does not repeat it. The steps follow A Framework for Any Design.

#Clarify the problem

• Functional: create buckets; put, get (whole or a byte range) and delete objects; list keys by prefix, page by page; upload large objects in parts.
• Non-functional: eleven nines of durability per object per year (checked with arithmetic below); reads available 99.99% of the time; a successful put is visible to every later get and list; first byte within about 100 ms; storage overhead well under 3x.
• Out of scope: access policies, billing, storage classes, cross-region replication; versioning is a follow-up.

#Estimate the scale

The average object is 100 PB ÷ 100 billion = 1 MB.

• Ingest: 4,000 puts a second × 1 MB = 4 GB/s. A month is about 2.6 million seconds, so 4,000 × 2.6 million ≈ 10 billion objects, 10 PB, a month, which matches the growth given.
• Egress: 40,000 gets a second × 1 MB = 40 GB/s on average, 120 GB/s at a 3x peak. If one front-end server moves about 1 GB/s, that is about 120 servers for peak reads alone. This store is limited by bandwidth, not request count.

#Define the API

PUT    /{bucket}/{key}          x-checksum: sha256=9f2c...
  200 { "etag": "9f2c...", "version": "v2" }
  400 Bad Digest            bytes do not match the checksum; nothing stored
  412 Precondition Failed   If-Match / If-None-Match did not hold
 
GET    /{bucket}/{key}          Range: bytes=0-1048575 (optional)
  200 or 206 + bytes         404 no such key
 
DELETE /{bucket}/{key}
  204 No Content             also when the key did not exist
 
GET    /{bucket}?prefix=photos/2026/&delimiter=/&limit=1000&after=...
  200 { "keys": [...], "prefixes": ["photos/2026/01/"], "next": "token" }
 
POST   /{bucket}/{key}?uploads                start  -> { "upload_id": "u7" }
PUT    /{bucket}/{key}?upload_id=u7&part=3   one part -> { "etag": "..." }
POST   /{bucket}/{key}?upload_id=u7          complete, body: [{part, etag}, ...]
DELETE /{bucket}/{key}?upload_id=u7          abort

The decision worth arguing is two clients putting the same key at once. Default to last writer wins, ordered by the metadata commit, and offer conditional puts: If-None-Match: * ("only if the key does not exist") and If-Match: <etag> ("only if nobody changed it since I read it"). Users get compare-and-swap with no locks in the store. Delete returns 204 even for a missing key, so retries are safe (see idempotency and retries).

#Model the data

objects                       -- sorted by (bucket_id, key)
  bucket_id    BIGINT
  key          VARCHAR(1024)  -- "photos/2026/cat.jpg"
  version      BIGINT
  size_bytes   BIGINT
  checksum     CHAR(64)       -- sha256 of the bytes (multipart: of the parts' sums)
  chunks       LIST           -- [(volume_id, chunk_id, length, crc32c), ...]
  PRIMARY KEY (bucket_id, key)
 
volumes                       -- the volume map, about 10 million rows
  volume_id    BIGINT PRIMARY KEY
  state        VARCHAR(8)     -- open | sealed | coded
  layout       LIST           -- 3 disks while open; 14 fragment disks once coded
  generation   INT            -- bumped when compaction rewrites it
 
multipart_parts
  upload_id, part_number, chunks, checksum

The indirection is key → chunks → volume → disks. A volume is a 10 GB append-only file packing many objects' chunks; 100 PB ÷ 10 GB = 10 million volumes, and at about 200 bytes each the volume map is 2 GB, small enough for every front end to cache. Each storage node keeps its own index from chunk id to offset.

Gets and puts are single-key lookups that must be strongly consistent. List scans keys in sorted order from a prefix, which rules out hash partitioning: it scatters neighbouring keys. Use a range-partitioned, sorted key-value store with consensus per range, such as TiKV. Each contiguous key range is replicated three ways with a leader chosen by consensus, and busy ranges split.

#High-level design

Metadata is small, strongly consistent and touched by every request. Data is huge, written once and mostly cold. They scale for different reasons, so they are separate services. The front end writes bytes first and metadata second, so an object never points at bytes that are not there.

#Deep dives

#Durability: copies or erasure coding

Eleven nines means a 1 in 10¹¹ chance of losing a given object in a year: across 100 billion objects, about 1 object a year. Assume, as a planning figure, that 2% of disks fail a year and a lost piece is rebuilt within 24 hours.

• The chance a given disk fails in a 24-hour window: p = 0.02 × 24 ÷ 8,760 ≈ 5.5 × 10⁻⁵.
• 3 copies. One of the 3 disks fails 3 × 0.02 = 0.06 times a year, and the object is lost only if both others fail before the rebuild: p² ≈ 3.0 × 10⁻⁹. Yearly loss ≈ 0.06 × 3.0 × 10⁻⁹ = 1.8 × 10⁻¹⁰, just under ten nines: about 18 objects a year. Fresh data stays in copies only until its volume fills and is coded, so the coded figure is the one that counts.
• 10 + 4 coding. One of 14 disks fails 14 × 0.02 = 0.28 times a year, and the object is lost only if 4 of the other 13 fail before the rebuild: 715 ways to pick them, so 715 × p⁴ ≈ 6.4 × 10⁻¹⁵. Yearly loss ≈ 0.28 × 6.4 × 10⁻¹⁵ ≈ 1.8 × 10⁻¹⁵, almost fifteen nines.
• Faster repair pays twice. Repair in 1 hour and p falls 24 times, so the 3-copy loss falls 24² = 576 times, to about 3 × 10⁻¹³.

The model assumes disks fail independently. They do not: a rack loses power, a disk batch shares a firmware bug, a release deletes the wrong files. Correlated failures, not code maths, are the real threat. So put each volume's pieces in different racks, roll out software slowly, and wait days before erasing deleted data.

Repair is the price of coding, so compute it. 7,000 disks at 2% a year is 140 failures, one every 2.6 days. Rebuilding a 20 TB disk under 10 + 4 reads 10 fragments per lost one: 200 TB read, 20 TB written. Over 24 hours that is 200 TB ÷ 86,400 s ≈ 2.3 GB/s of background traffic, against 0.23 GB/s for copies. Normal reads do not pay it: the code is systematic, so the 10 data fragments hold the original bytes and a 1 MB read usually touches one fragment and decodes nothing.

Durability also needs detection: a silently rotted copy is a copy you do not have. Every chunk carries a CRC checked on each read, and a scrubber reads every disk end to end. Scrubbing a 20 TB disk every 14 days is 20 TB ÷ 1.2 million s ≈ 17 MB/s, a small slice of a disk's sequential speed.

#Huge objects and multipart upload

A 1 TB object arrives as parts, say 10,000 of 100 MB, uploaded in any order and in parallel. Inside the store a part is just a small put: chunks appended to volumes plus a multipart_parts row. Re-uploading part 3 replaces its row.

Complete moves no bytes. It checks every listed part exists with the given etag, then writes one object row whose chunk list is the parts' chunks in order, in one metadata transaction. A 1 TB object appears atomically, in milliseconds, with a checksum computed from the parts' checksums. Abort, or a rule that expires uploads idle for a week, deletes the part rows and leaves the chunks to garbage collection. Range reads map a byte range to the chunks that cover it.

#Listing by prefix

There are no folders. photos/2026/ is just the start of some keys, so listing it scans the sorted store from the first key at or after the prefix until keys stop matching. Range partitioning means that scan touches one or two ranges, not all of them.

• Pages: at most 1,000 keys plus a token holding the last key returned; the next page starts after it.
• Delimiter: with delimiter=/, keys under photos/2026/01/ collapse into one entry, and the scan seeks straight past them instead of reading a million rows.
• Hot ranges: keys starting with a timestamp all land at the end of one range, and splitting cannot help because every new key goes to the newest half. Suggest a short hash prefix for hot writers.

List reads the same consistent store as get, so a key is listed the moment its put returns. A separate listing index updated asynchronously would show new objects late and break every job that writes files and then lists them.

#Deleting and reclaiming space

Delete removes the object row in one metadata write, so the object vanishes at once. Its bytes still sit in an append-only volume beside live chunks. Reclaiming them is a separate, slower job.

Use both, with two safety rules. A grace period: never erase a chunk younger than a few days, because a put may have written bytes and not yet committed its row. The commit refuses chunks older than a day, so a put stalled past the window fails instead of pointing at erased bytes. And compaction keeps chunk ids: when a sealed volume is over 40% dead, a worker copies its live chunks into a new generation of the same volume and updates the volume map. Object rows still say "volume 5,120,331, chunk 88", so the metadata never changes. The old generation stays readable for a day for gets that looked up the old layout.

#Bottlenecks and failures

At 10x, 40,000 puts and 400,000 gets a second, add storage nodes (placement sends new volumes to the emptiest disks, so nothing old moves) and front ends. The metadata store strains first: every request is a lookup and every put a consensus write. Split busy ranges and cache hot rows in the front ends.

#What a strong answer sounds like

#Follow-up questions

#How would you add versioning?

Put the version in the key so each put adds a row, and make delete add a "delete marker" row. A plain get reads the newest row that is not a marker. GC must treat every version's chunks as live.

#How do you survive losing a whole data center?

No zone may hold more fragments than the code can lose. With 3 zones, 12 data + 6 parity, 6 per zone, survives a zone at 18 ÷ 12 = 1.5x. While a zone is down there is no margin left, so repair must be fast.

#What about billions of tiny objects?

Coding is per 10 GB volume, so a 1 KB object costs 1.4 KB of disk. Its 500-byte metadata row now rivals the data, so the metadata store is the real limit.

#One object gets 50,000 gets a second. What breaks?

The disk holding its data fragment. Cache hot objects in front-end memory or behind a CDN. Objects never change in place, so cached copies cannot go stale.

#How do you delete a bucket with a billion objects?

Mark it deleted so it refuses requests, then remove its key range in background batches: one contiguous scan in a range-partitioned store.