Design Object Storage (Amazon S3)

The single most load-bearing decision is separating the namespace from the bytes. Once an object's record points at immutable, checksummed shards, the blob layer becomes a dumb (and therefore reliable) byte farm - all the hard semantics concentrate in the metadata service.

What a metadata record holds
(bucket, key, version) → { size, content-type, checksum/ETag, storage class, creation time, ACL reference, shard map: [(shard_id, node, disk, extent, offset), ...] }. ~500 bytes. One trillion of these is a 500 TB strongly-consistent database serving millions of lookups per second - this is the system's beating heart.

Sharding the namespace
Partition by (bucket, key) ranges, lexicographically - not by hash. Hash-partitioning spreads load beautifully and destroys LIST (a prefix scan would touch every partition). Range-partitioning keeps LIST a local scan but concentrates sequentially-named keys on one partition, so the system must split hot partitions dynamically and move ranges between servers - the same design pressure that shaped Bigtable/DynamoDB-style stores. S3 exposes this reality directly: its guidance to "add key prefix entropy for high request rates" is the metadata partitioning showing through the API.

Why PUT commits metadata last
Stream bytes first, commit the record second. The metadata write is the linearization point: before it, the object doesn't exist (crash = orphaned shards, GC'd later); after it, the object fully exists. Inverting the order (metadata first) can expose a key whose bytes aren't durable - a catastrophic contract violation - while orphaned shards are merely wasted space with a background janitor.

Overwrites and versioning
Objects are immutable; an overwrite PUT writes new shards and swaps the record's pointer atomically (or, with versioning enabled, prepends a new version). Readers mid-flight on the old shard map finish safely because old shards are only GC'd after a grace period. Immutability is what makes "strong consistency" cheap: there's no partially-updated blob state to reason about, only an atomic pointer swap in one metadata partition.

Caching the metadata path
Every GET does a metadata lookup, so front-ends cache records aggressively. The classic trap: serving a GET from a stale cached record after an overwrite breaks read-after-write. Fixes: invalidation pushed on write (fragile at this fan-out) or - the honest answer - cache with short TTLs plus a version check against the authoritative partition for correctness-critical paths, accepting one cheap indexed lookup per GET. Metadata partitions serve point lookups from memory; the budget exists.

The blob layer stays dumb on purpose
Storage nodes know nothing about buckets, keys, or ACLs - only (shard_id → bytes at extent offset, checksum). Small shards pack into large append-only extent files, so a billion 100 KB objects don't become a billion filesystem inodes. All policy, naming, and consistency live above. Systems that let semantics leak into the byte layer (e.g., encoding keys into file paths) discover they've built a filesystem with a REST API - and inherited every filesystem scaling wall.

"Eleven nines" (99.999999999% annual durability) means: of a trillion objects, you expect to lose about one per decade... roughly. Interviewers love candidates who can derive why that's achievable rather than recite it.

Start with a single disk
A disk with 1-2% annualized failure rate (AFR) gives roughly two nines. Any real durability comes from redundancy plus repair - durability is a race between correlated failures and your repair speed.

Replication math (3x)
An object dies if all 3 replicas die before repair. With AFR ~1.5% and a repair window W after the first failure, the probability the two survivors both die within W (say 24 hours: 1.5% × 24/8766 ≈ 4×10⁻⁵ each) is ~(4×10⁻⁵)² ≈ 1.6×10⁻⁹ per initial failure - and each object's replica set sees ~4.5% initial-failure events/year. Net ≈ 7×10⁻¹¹/object-year: about ten nines, shy of the target, and it burned 3x the storage.

Erasure coding math (10+4)
Split the object into 10 data shards, compute 4 parity shards (Reed-Solomon); any 10 of the 14 reconstruct it. Losing the object requires 5 of 14 shards gone before repair - with independent daily-scale failure odds of ~4×10⁻⁵ per shard, a 5-way coincidence lands around 10⁻¹⁴-10⁻¹⁶/object-year. Comfortably past eleven nines, at 1.4x overhead instead of 3x. This is why every hyperscale store (S3, GCS, Azure, Ceph EC pools) erasure-codes bulk data: more durable and 2x cheaper than 3x replication.

The two assumptions doing all the work

1. Failure independence. A rack power event or bad firmware batch kills shards together, obliterating the exponent math. Hence placement rules: 14 shards on 14 nodes across ≥ 14 racks / multiple power and network domains (or across 3+ datacenters for regional stores), and heterogeneous disk batches so one firmware bug can't take out a whole stripe.
2. Repair speed. Durability scales with (window of vulnerability)ⁿ, so halving repair time buys orders of magnitude. This is a fleet bandwidth problem: a dead 20 TB disk holding shards from millions of stripes is rebuilt by thousands of nodes each reconstructing a few stripes in parallel - minutes-to-hours of exposure, not the days a single-disk resilver would take. Declining repair throughput is a durability incident before any object is lost; mature stores alert on it like an SLO.

Silent corruption: the sneakier enemy
Disks also lie - bit rot, misdirected writes, firmware bugs - at rates that matter at 47K-disk scale. Defenses: end-to-end checksums stored in metadata and verified on every read, plus continuous background scrubbing that reads every shard on a fixed cadence and repairs mismatches from parity. Without scrubbing, corruption hides until the moment you need that shard for a rebuild - the worst possible time to discover it.

Availability is a different number on purpose
11 nines durability with 4 nines availability: a partition or node crash can make an object briefly unreadable (availability event) while its bytes remain safe on 14 disks (no durability event). Conflating the two - or promising availability from the durability design - is a classic interview miss.

The durability math says "erasure code everything." Production says: the code's real costs surface on the read path, the repair path, and small objects. Managing those is the practice.

Reads under failure get amplified
Replication repair copies one replica (1:1 reads to bytes recovered). A 10+4 code must read 10 shards to rebuild one - 10x read amplification. When a 20 TB disk dies, the fleet reads ~200 TB to restore ~20 TB of shards. Do that naively fast and repair traffic starves foreground GETs; do it politely slow and you stretch the durability-critical vulnerability window. Production stores run repair under a token-bucket budget with priority by stripe risk: stripes missing 2+ shards jump the queue and repair at maximum speed, single-shard losses trickle - which keeps the (window)ⁿ math strong exactly where it's weakest.

Local Reconstruction Codes: paying storage to shrink repair
The dominant failure is a single lost shard, so optimize for it: LRC (Azure's 12+2+2) adds local parity over sub-groups, so a single-shard rebuild reads ~6 local shards instead of 12, roughly halving repair I/O for ~1.33x overhead. Wide global parity still covers multi-failure stripes. The general lesson: code choice is a three-way dial between storage overhead, repair cost, and fault tolerance - "Reed-Solomon 10+4" is a fine interview default, and naming LRC as the repair-cost refinement is a strong senior signal.

Degraded reads
A GET whose primary shards are missing reconstructs inline from any 10 survivors - correct, but latency jumps from one disk read to a 10-node fan-out plus decode, and p99 inherits the slowest of ten disks. Standard mitigations: request 11-12 shards speculatively and decode from the first 10 to arrive (tail-hedging inside a stripe), and repair proactively so degraded stripes are rare rather than routine.

Small objects don't want wide stripes
A 100 KB object in 10+4 means 10 KB shards - 14 disk ops per read, seek-dominated, plus per-shard metadata that can rival the data. Two production answers:

• Replicate small, erasure-code large. 3x on a 100 KB object costs 200 KB extra - nothing - while keeping reads to one disk op. Since most bytes live in large objects, the fleet-level overhead stays near EC levels.
• Pack-then-code. Batch thousands of small objects into large immutable extents, erasure-code the extents. Reads become (extent, offset, length) - one or two shard touches. Cost: GC must compact extents as constituent objects die (LSM-style write amplification returns wearing a storage-node costume).

Write-path fan-out
Each PUT streams through an encoder to 14 nodes and waits for all 14 durable acks before the metadata commit (a straggler node is handled by writing its shard to a fallback node and recording the substitution - never by acking at 13/14 and hoping). Encoding is cheap (Reed-Solomon with SIMD runs GB/s per core); the p99 cost is the 14-way straggler problem, which the fallback-write mechanism converts from a latency wall into a placement footnote.

A single-stream 5 TB PUT at 100 MB/s runs ~14 hours; one TCP reset at hour 13 and a naive design restarts from byte zero. Multipart upload is the protocol answer, and its design decisions echo through the whole write path.

The protocol

1. Initiate → the coordinator issues an upload ID (an in-progress record, invisible in the namespace).
2. UploadPart(upload_id, part_number, bytes) - parts of ~5 MB-5 GB (S3: up to 10,000 parts). Each part uploads independently: in parallel streams, in any order, retryable in isolation. Each returns an ETag the client must retain.
3. Complete(upload_id, [(part_number, etag), ...]) - the atomic assembly step: the service verifies every listed part's ETag, then writes one metadata record whose shard map is the concatenation of the parts' shards. The object appears in the namespace all-at-once or not at all.
4. Abort (or lifecycle timeout) frees accumulated parts - without this janitor, failed uploads become an invisible storage leak that surprises the capacity plan months later.

Why parts are the unit of everything
Each part is durably stored (erasure-coded) when uploaded, so a network failure costs at most one part's progress. Parallelism turns the 14-hour single stream into ~1.5 hours over 10 streams - bounded by client uplink, not server design. And parts map naturally onto blob-layer stripes: a part is the erasure-coding unit, so "assemble the object" is pure metadata - no bytes move at Complete time. That's what makes Complete fast and atomic even for a 5 TB object.

ETags and integrity
Per-part checksums are verified on upload; Complete verifies the client's part list matches what the server holds (catching lost/duplicated/reordered parts from client bugs). This is also why multipart objects' ETags aren't a simple content MD5 (S3 uses hash-of-part-hashes) - a detail that bites naive client-side integrity checks and a nice bit of realism to mention.

Concurrent completes and idempotency
Two clients completing the same upload ID, or a retry of a Complete whose response was lost: the coordinator makes Complete idempotent (same part list → same result, recorded against the upload ID) and last-write-wins at the key level, consistent with ordinary PUT semantics.

Range GETs: the read-path mirror
GET with a byte range resolves which parts/shards cover the range and reads only those - the shard map's offset index makes a 1 MB read from a 5 TB object cost one or two shard touches, not a scan. Large-object consumers (video players seeking, download managers resuming, analytics engines reading column footers) live on range reads; a design that can't serve them cheaply has hidden a full-object read behind a friendly API.

Interview signal: candidates who specify Complete's atomicity, the orphaned-part GC, and Complete-as-pure-metadata have designed the feature; candidates who say "split the file and upload chunks" have described the brochure.

For 14 years S3 was eventually consistent for overwrites and LIST, and an entire generation of data-engineering scar tissue formed around it. In 2020 it switched to strong read-after-write - for free, with no latency regression. Both halves of that story are interview gold.

What eventual consistency actually broke

• Read-after-overwrite: update a config object, read back the old version. Applications built shadow versioning (write new key + pointer swap) to dodge it.
• LIST lag: a completed PUT missing from LIST. For data pipelines that enumerate a prefix to discover work ("process all of today's files"), a lagging LIST silently dropped data - the nastiest failure mode, since nothing errored. Hadoop/Spark grew entire committer frameworks (and AWS shipped EMRFS "consistent view", a DynamoDB sidecar) purely to paper over this.
• The lesson worth saying out loud: when a storage layer's consistency is weak, the complexity doesn't disappear - it migrates into every client, badly.

What "strong" means here (and what it doesn't)
After a successful PUT (new or overwrite), any subsequent GET/HEAD/LIST reflects it - linearizable per-key read-after-write, immediately and globally within the region. It does not mean cross-object transactions, compare-and-swap, or rename; concurrent PUTs to one key still resolve last-writer-wins, and mutual exclusion remains the client's problem (or a conditional-write feature bolted on later). Scoping the guarantee precisely is exactly the kind of statement that separates senior candidates.

How you build it
Strong consistency was never impossible - it's a per-key linearizability problem over the metadata service:

1. Each key's record lives in exactly one metadata partition whose replicas run a consensus/replicated-log protocol (Raft-style); the PUT's metadata commit is the linearization point.
2. Reads either go through the partition leader or carry a lease/version check - stale replicas and stale front-end caches must be fenced, not trusted. (The witness/cache-invalidation layer to do this at S3's scale is the part AWS engineered for years before flipping the switch.)
3. LIST is a range scan against the same versioned partitions, so it observes the same linearization point - fixing LIST-lag by construction rather than by sidecar.

The honest reason it was eventual for so long: at trillion-object scale, cache coherence across a planet-sized front-end fleet is brutally hard, and eventual consistency let the caches be sloppy. The 2020 change was AWS paying that engineering cost centrally so every customer could delete their workaround code.

Immutability is the enabler
Note what made this tractable: blobs never mutate. Consistency is only ever about which record version a key resolves to - an atomic pointer swap in one partition - never about torn 5 TB writes. A design that allowed in-place blob mutation would need to solve consistency at the byte layer too, and would deserve what happened to it.

Multi-region is a different contract
Cross-region replication remains asynchronous (seconds-to-minutes lag, monitored per-rule): strong consistency within a region, eventual between regions. Global-strong would put a cross-continent consensus round-trip inside every PUT - the correct design refusal, and a good moment to say why.

GET and PUT are point operations - shard them and go home. LIST is an ordered range scan with pagination over a trillion-row keyspace, and it quietly dictates the metadata service's entire partitioning story.

The contract
LIST(bucket, prefix, start-after, max-keys) returns up to 1,000 keys, lexicographically ordered, with a continuation token. The ordering guarantee is the expensive part: it forces the metadata layer to keep keys range-partitioned (sorted runs per partition), because hash partitioning would turn every LIST into a scatter-gather across all partitions with a giant merge - a non-starter at this scale.

Range partitioning's tax: the hot partition
Sorted keys mean workloads with sequential names - logs/2026-07-08/14-32-01.json, invoice-000123456 - aim every PUT and the "what's new" LIST at the same tail partition. This is the classic time-series hot-shard problem relocated into a storage API. Mitigations, in the order a real system deploys them:

1. Dynamic partition split-and-move: monitor per-partition load, split hot ranges, migrate halves to other servers. Necessary, but splits chase a moving hot tail.
2. Key-design guidance: prefix entropy (reversed IDs, hash prefixes) spreads load - and this is precisely why S3 historically published per-prefix request-rate guidance; the partitioning scheme is visible through the API's performance model.
3. Write-path buffering for the pathological case: absorb sequential-key PUT bursts into a log, apply to partitions asynchronously - at the price of LIST freshness, which strong consistency then forbids. (S3 chose splits + horizontal prefix scaling; that choice is worth narrating.)

Delimiter listing: directories that don't exist
LIST with delimiter="/" returns keys under the prefix plus CommonPrefixes - synthesized "folders". There are no directories; the metadata layer fakes them with a range-scan trick: on hitting photos/2024/x.jpg, emit common prefix photos/2024/ and seek directly to the successor key of that prefix (the first key after the entire photos/2024/ subtree), skipping the rest of it. One seek per synthesized folder instead of scanning millions of member keys - without the skip-scan, listing a bucket's top level with a million-object "folder" reads a million rows to emit one line. This little algorithm is the difference between a usable console and a metadata DDoS.

Pagination as a cursor, not an offset
Continuation tokens encode the last key returned (an index seek position), never a numeric offset - OFFSET 500000 would re-scan half a million rows per page. Token-based pagination also makes LIST naturally resumable and (with versioned reads within a page) consistent per-page even as the namespace churns underneath; cross-page phantom keys are inherent and documented, not a bug to fix.

Versioning and delete markers
With versioning on, LIST reads the newest version per key and must skip keys whose newest version is a delete marker - so the scan cost tracks versions examined, not keys returned. A bucket with heavy churn (millions of delete markers from a lifecycle rule) can make an innocent LIST crawl; ListObjectVersions exposes the raw truth. Mentioning marker-skipping cost flags real operational literacy.

When LIST is the wrong tool
At a trillion objects, "enumerate the bucket" is a batch job measured in days. Real systems stop paginating and go async: a manifest/inventory export (daily listing to objects the customer reads with analytics tools) and event notifications (per-PUT events into a queue) replace polling LIST for pipelines. Recognizing when to demote LIST from the hot path entirely is the final senior move this topic offers.