An object store looks like a hash map with two methods: PUT(key, bytes) and GET(key) -> bytes. That framing is exactly why it is hard. A hash map lives in one process’s memory; this one holds trillions of objects and exabytes of bytes across hundreds of thousands of disks in dozens of datacenters, and promises that once a PUT returns 200 OK the bytes will still be there in a thousand years - eleven nines of durability, meaning if you store ten million objects you expect to lose one every ten thousand years. The naive version is a directory on a big disk behind an HTTP server, and it dies the first time a disk fails, the first time one key gets a billion reads, and the first time the index of keys outgrows a single machine. Everything real about S3 is the machinery that keeps a dumb key-value interface alive when the disk will fail, the datacenter will burn, and the keyspace will not fit anywhere.

The whole engineering problem is this: store an arbitrary blob under an arbitrary key so that reads and writes are fast, the bytes survive any plausible hardware or datacenter failure without ever being lost, and both the number of objects and the total bytes scale without bound - while a metadata layer maps keys to physical locations across a fleet too large to ever fit that map on one node. Durability is the headline; the metadata index over trillions of keys is the quiet part that decides whether it works at all. Let me build it properly.

Functional Requirements (FR)

In scope:

  • PUT an object. Store an arbitrary blob (1 byte to 5TB) under a user-chosen key inside a bucket. Return success only when the bytes are durably committed.
  • GET an object. Retrieve the bytes for a key, or a byte range of them. Support streaming large objects.
  • DELETE an object. Remove a key (subject to versioning semantics below).
  • List objects in a bucket by key prefix, paginated (list objects starting with photos/2026/).
  • Buckets as the top-level namespace and unit of ownership, region placement, and access policy.
  • Multipart upload. Upload a huge object in parallel parts and complete it atomically, with resumability.
  • Versioning. Keep prior versions of an object; a DELETE places a marker rather than destroying history; any version is restorable.
  • Lifecycle policies. Per-bucket rules that transition objects to colder/cheaper storage after N days or expire (delete) them automatically.
  • Multi-region replication. Asynchronously replicate a bucket’s objects to another region for disaster recovery and locality.

Explicitly out of scope (say it so you own the scope):

  • A POSIX filesystem. No partial in-place writes, no rename, no append. Objects are immutable - you overwrite a whole key, you never edit bytes in place. This immutability is a design gift I will lean on hard.
  • Strong cross-key transactions. No “update these 3 objects atomically.” Each object operation is independent. (Single-object PUT is atomic; that is the whole guarantee.)
  • Auth/IAM internals, billing, and encryption key management. Assume a service authenticates the caller and answers “may this principal do this on this bucket.” I will note where encryption-at-rest hooks in.
  • A CDN. Edge caching sits in front and is a separate design; I will note the seam.

The one decision that shapes everything: this is an immutable, write-once-read-many blob store where durability is the hard non-negotiable and the metadata keyspace is the hidden scaling wall. Unlike a database (mutable rows, transactions, joins) an object never changes after it is written, which means no locks on data, trivial caching, and content that can be erasure-coded once and left alone. That immutability plus “durability above all” is the entire character of the system.

Non-Functional Requirements (NFR)

  • Scale: trillions of objects, exabytes stored. Object sizes span 12 orders of magnitude (a 200-byte JSON to a 5TB video master); the count of small objects and the bytes of large objects are two different scaling problems in one system. Hundreds of thousands of storage disks across dozens of datacenters.
  • Durability: eleven nines (99.999999999%) on stored objects. This is the flagship number. It is achieved with redundancy that survives concurrent disk, rack, and datacenter failure - not by hoping disks do not die (they die constantly at this fleet size).
  • Availability: ~99.99% on the request path (four nines). Availability and durability are different: a brief inability to serve an object is tolerable; losing it is not. We trade availability for durability, never the reverse.
  • Latency: first-byte latency in the low tens of milliseconds for a warm small object; throughput-bound for large objects (saturate the client’s pipe). PUT returns only after durable commit, so PUT latency includes the redundancy write.
  • Consistency: read-after-write consistency for new objects (a GET right after a successful PUT returns the new bytes), and strong read-after-write for overwrites and deletes as well (modern S3 is strongly consistent). List operations are also consistent. This is a raised bar from the old “eventually consistent list” world and it drives the metadata design.
  • Throughput: must scale horizontally with no per-bucket ceiling that a heavy user can hit; hot prefixes must not create hot shards.

Durability is the requirement that earns its own paragraph, so here it is: eleven nines does not come from a magic disk. It comes from erasure coding spread across independent failure domains, continuous background integrity scrubbing, and fast automated repair that rebuilds lost redundancy before a second failure can catch up. Every deep-dive below is ultimately in service of that number.

Back-of-the-Envelope Estimation (BoE)

Real numbers with the arithmetic, because they pick the architecture.

Objects and bytes:

Assume 100 trillion objects total, 1 exabyte (10^18 bytes) stored (post-encoding logical).
   Average object size = 1 EB / 100T = 10^18 / 10^14 = ~10 KB average.
   (Skewed: billions of tiny objects, millions of huge ones. The AVERAGE is small
    because tiny objects dominate the COUNT; huge objects dominate the BYTES.)

That average is the single most important number in the whole estimate: most objects are small, so the metadata-record-per-object count is enormous, and per-object overhead dominates for small objects. A 10KB object cannot afford a 10KB metadata row or 3x replication overhead.

Request rate:

Say 50M requests/sec at peak globally across the fleet (GET-heavy).
   Read:write ratio ~ 10:1 for a typical mixed workload.
   => ~45M GET/sec, ~5M PUT/sec (+ DELETE, LIST folded into reads).
Per region (say 20 regions, uneven): order 1-5M req/sec in a big region.

Metadata store size (the quiet wall):

100 trillion objects * ~1 KB metadata each (key, size, version, chunk/shard map,
   checksum, timestamps, storage class) = 10^14 * 10^3 = 10^17 bytes = 100 PB of metadata.
   Replicated 3x for the metadata store's own durability = ~300 PB.

100 PB of metadata alone - that is the punchline. The index that maps keys to bytes is itself a petabyte-scale distributed database with trillions of rows and millions of QPS. You cannot put it on one machine, one shard, or even one thousand shards casually; the metadata layer is a first-class distributed system, not a lookup table.

Storage overhead - erasure coding vs replication:

3x replication: store 1 EB logical => 3 EB physical. Overhead 200%.
Erasure coding, say 10 data + 4 parity (10+4):
   physical = logical * 14/10 = 1.4x => 1.4 EB physical. Overhead 40%.
   Tolerates ANY 4 of 14 shards lost with zero data loss.
Savings vs 3x: (3 - 1.4)/3 = ~53% less physical storage at HIGHER fault tolerance.

At exabyte scale a 1.6x reduction in physical bytes is billions of dollars of disks and power. Erasure coding is not an optimization here; it is the difference between a viable and an unviable cost structure.

Bandwidth:

Reads: 45M GET/sec * 10KB avg = 450 GB/sec egress steady (plus large-object streams).
Big objects skew this far higher in bytes; CDN offloads the hottest reads.
Writes: 5M PUT/sec * 10KB = 50 GB/sec ingest, then fanned out to 14 EC shards
   across racks => internal write amplification of 1.4x on the storage network.

Durability math (why 11 nines is even possible):

Single disk annual failure rate ~ 2-4%. With 10+4 EC across 14 independent disks
in 14 independent racks, you lose data only if 5+ of the 14 fail within the
repair window (hours). With fast repair (rebuild a lost shard in minutes-to-hours),
the probability of 5 concurrent correlated-domain failures inside that window is
astronomically small => 11 nines. Repair SPEED is the durability lever, not just
the code width.

The takeaways: metadata is a 100PB, trillion-row, millions-of-QPS distributed database and it is the real scaling wall; the data plane is an erasure-coded exabyte blob store where repair speed buys the durability; and the small-object-dominated size distribution means per-object overhead must be tiny. Those three, not the raw petabyte counts, are the interview.

High-Level Design (HLD)

The architecture splits along the same seam every large storage system splits on: metadata (small structured records: key -> where the bytes physically live, plus size/version/checksum) is a separate distributed system from the data plane (huge immutable byte shards on disks). A stateless front-end tier authenticates and routes. The metadata service resolves a key to a set of physical shard locations. The storage nodes hold erasure-coded shards on raw disks. Background services scrub, repair, replicate, and enforce lifecycle rules.

        ┌───────────┐   ┌───────────┐   ┌───────────┐
        │  Client   │   │  Client   │   │  Client   │   (SDK / REST over HTTPS,
        │ (PUT/GET) │   │  (LIST)   │   │(multipart)│    signed requests)
        └─────┬─────┘   └─────┬─────┘   └─────┬─────┘
              └───────────────┼───────────────┘
                     ┌────────▼─────────┐
                     │  Load Balancer   │
                     └────────┬─────────┘
                     ┌────────▼───────────────────────┐
                     │   Front-End / API Service        │  stateless:
                     │   auth, quota, request parse,     │  authn/z, routing,
                     │   multipart orchestration         │  checksum verify
                     └───┬───────────────────────┬──────┘
                         │ resolve key            │ read/write shards
                ┌────────▼──────────┐    ┌────────▼──────────────────────────┐
                │  Metadata Service  │    │        Data Plane                  │
                │  key -> {version,  │    │  ┌──────────┐ ┌──────────┐         │
                │  size, checksum,   │    │  │ Storage  │ │ Storage  │  ...    │
                │  shard map, class} │    │  │ Node     │ │ Node     │         │
                │  buckets, policies │    │  │ (disks,  │ │ (disks,  │         │
                └────────┬───────────┘    │  │ EC shards│ │ EC shards│         │
                         │                │  └──────────┘ └──────────┘         │
                ┌────────▼───────────┐    │   spread across racks & DCs        │
                │  Metadata Store     │    └───────┬───────────────────────────┘
                │  (sharded, strongly │            │
                │   consistent KV /   │    ┌───────▼───────────────────────────┐
                │   NewSQL, RF=3)     │    │  Background services                │
                └─────────────────────┘    │  - Scrubber (read + verify checksums│
                                            │  - Repair (rebuild lost EC shards)  │
    ┌───────────────────────────────┐      │  - Lifecycle engine (transition/exp)│
    │ Async Replication Pipeline      │◄─────┤  - GC (reclaim deleted/orphan bytes)│
    │ (bucket -> other region)        │      │  - Replication reader               │
    └───────────────────────────────┘      └────────────────────────────────────┘

PUT flow (write a new object):

  1. Client sends PUT /bucket/key with the bytes and a checksum (e.g. MD5/CRC in the Content-MD5 header). The Load Balancer routes to any Front-End node (stateless).
  2. Front-End authenticates, checks bucket ownership and quota, and verifies the payload checksum as bytes stream in (reject silent corruption on the wire).
  3. Front-End streams the object into the data plane: it splits the object into fixed-size data shards, computes parity shards (erasure coding, e.g. 10 data + 4 parity), and writes all 14 shards to 14 different storage nodes in 14 different failure domains (different racks, spread across availability zones). It waits for a durable write quorum of shard acks.
  4. Once enough shards are durably persisted, Front-End calls the Metadata Service to commit the mapping: bucket/key -> {version_id, size, checksum, shard_locations[14], storage_class, timestamp}. This commit is the atomic, strongly-consistent moment - the object “exists” the instant this metadata record commits.
  5. Front-End returns 200 OK with the version id. The bytes are now durable (survives 4 shard losses) and discoverable (metadata committed).

GET flow (read an object):

  1. GET /bucket/key hits a Front-End node. Auth check.
  2. Front-End asks the Metadata Service to resolve the key -> the latest version’s shard map, size, and checksum.
  3. Front-End reads shards from the storage nodes. It only needs any 10 of the 14 shards to reconstruct (that is the point of 10+4). It reads the fast/nearest 10, decodes the object, and verifies the checksum before returning a byte.
  4. Streams the bytes (or the requested byte range) back to the client. Hot objects are served from a read cache / CDN in front of the Front-End tier.

The key insight: the Front-End is a stateless erasure-coding pipe, the Metadata Service is the strongly-consistent brain that says where bytes live, and the storage nodes are dumb durable shard-holders. The object exists exactly when its metadata record commits, which gives read-after-write consistency for free - if the metadata says it is there, all its shards are already durably written; if the PUT died before the metadata commit, the orphaned shards are just garbage the GC reclaims and no GET ever sees them.

Component Deep Dive

The hard parts, naive-first then evolved: (1) durability - how to actually hit eleven nines; (2) the metadata index over trillions of keys - the real scaling wall; (3) large objects and multipart upload; (4) versioning, lifecycle, and multi-region replication as one immutable-data story.

1. Durability: from one disk to eleven nines

Naive approach: write the object to a disk, return OK. One HTTP server, one big filesystem, one copy of the bytes.

Where it breaks:

  • Disks fail constantly at scale. A 2-4% annual failure rate across hundreds of thousands of disks means dozens die every day. One copy means every one of those deaths is permanent data loss. This is not eleven nines; it is roughly two nines. Catastrophic.
  • A single machine or rack loss takes everything with it. Correlated failure (a rack’s top-of-rack switch, a power distribution unit, a datacenter cooling event) wipes many “independent” disks at once.

Evolution A: N-way replication. Store 3 full copies on 3 different nodes in 3 different racks. Lose any 2, still have the data; repair by copying a surviving copy onto a fresh disk.

Where it breaks - cost, not correctness:

3x replication does give strong durability, and it is simple, and it makes reads cheap (read any copy). But at exabyte scale it means storing 3 EB of physical disk for 1 EB of data - 200% overhead. That is billions of dollars of extra hardware, power, and cooling. And to push replication to eleven nines with better fault tolerance you would need 4x or 5x, which is even more absurd. Replication buys durability by brute force; the cost curve is unacceptable.

3x replication: 1 EB logical -> 3 EB physical.   Tolerates 2 losses.  Overhead 200%.

Evolution B: erasure coding (Reed-Solomon), spread across failure domains. Split each object into k data shards, compute m parity shards (e.g. k=10, m=4), and store all k+m = 14 shards on 14 nodes in 14 independent failure domains. Any k of the k+m shards can reconstruct the whole object. Lose up to m shards (any 4 of 14) with zero data loss.

10+4 erasure coding: 1 EB logical -> 1.4 EB physical.  Tolerates ANY 4 losses.
   Overhead 40%  (vs 200% for 3x replication)
   Fault tolerance 4  (vs 2 for 3x replication)
   => MORE durable AND ~53% cheaper. This is why object stores use EC, not replication.

Why this is more durable than 3x for less storage: replication’s redundancy is coarse (whole copies); EC’s redundancy is fine-grained parity that tolerates more simultaneous failures per byte of overhead. The math:

Object -> [d1 d2 d3 d4 d5 d6 d7 d8 d9 d10] data shards
       -> [p1 p2 p3 p4] parity shards (Reed-Solomon over the 10 data shards)
Place each of the 14 on a DIFFERENT rack / failure domain.
Read: fetch ANY 10 of 14, decode. (Read the fastest 10 -> tail-latency win too.)
Lose d3, d7, p1, p4 (4 shards): still have 10 -> reconstruct perfectly.

The three pillars that actually produce eleven nines (EC width alone is not enough):

  1. Failure-domain-aware placement. The 14 shards must land in 14 independent domains - different disks, different nodes, different racks, ideally spanning availability zones. If two shards share a rack, a rack failure counts as 2 shard losses at once and your fault budget shrinks. Placement is durability.
  2. Continuous background scrubbing. A scrubber service constantly reads every shard, recomputes its checksum, and compares to the stored checksum. Disks suffer silent data corruption (bit rot) - a shard can rot without the disk reporting an error. Scrubbing catches a rotted shard and triggers repair before enough shards rot to cross the fault budget. Without scrubbing, latent corruption accumulates invisibly and eventually two “good” shards are both bad when you finally read.
  3. Fast automated repair. When a shard is lost (disk death or scrub-detected corruption), a repair service reconstructs it from the surviving k shards and writes a fresh shard onto a new disk in a valid failure domain. Repair speed is the dominant durability lever. Durability is a race: you lose data only if you cross the fault budget (5+ of 14) within the repair window. Halve the repair time and you square the durability. This is why big object stores obsess over rebuild throughput - parallel repair reading from many nodes at once, prioritized by how depleted an object’s redundancy is.
Durability = f(code width, failure independence, SCRUB frequency, REPAIR speed)
Lose data only if >m shards die inside the repair window.
Fast repair shrinks the window -> the probability of >m correlated deaths in it
                                  becomes astronomically small -> 11 nines.

End-to-end integrity. Checksums are computed at the client, verified at ingest, stored in metadata, verified by the scrubber at rest, and verified again on read before returning a byte. Corruption cannot silently pass any stage. This closed loop is what lets you believe the eleven-nines number rather than merely hope for it.

There is a real trade-off with EC: small objects. Erasure coding a 200-byte object into 14 shards is wasteful (each shard is tiny; fixed per-shard overhead dominates, and the parity is larger than the data). So the system packs many small objects together into large fixed-size storage “extents” (say 1GB blocks) and erasure-codes the extent, not the individual object. The metadata for a small object then points into an extent at an offset. Big objects (above the extent size) are EC’d directly in their own extents. This packing is essential given the 10KB average - without it, small objects would drown in per-shard overhead.

2. The metadata index over trillions of keys

Naive approach: one big table key -> location, on one strongly-consistent database. A GET looks up the key; a PUT inserts it; a LIST scans by prefix.

Where it breaks:

  • 100 PB of metadata does not fit on one machine, or ten, or a thousand. Trillions of rows at ~1KB each is a petabyte-scale database on its own. One node is off by six orders of magnitude.
  • Millions of QPS on lookups and inserts saturates any single primary immediately.
  • LIST by prefix is a range scan - you cannot hash-partition naively and still list photos/2026/ efficiently, because the keys under that prefix would be scattered across every shard.
  • Hot buckets create hot shards. A single popular bucket or a sequential key pattern (log-000001, log-000002, …) funnels all writes to one shard.

Evolution A: hash-shard the metadata by key. Partition the key -> location map across thousands of shards by hash(bucket + key). Spreads load and storage evenly.

Where it breaks: LIST dies. list objects with prefix photos/2026/ now has to fan out to every shard and merge, because hashing scattered those keys uniformly. LIST is a first-class API; making it an all-shards scatter-gather at trillions-of-keys scale is a non-starter.

Evolution B: range-partition the keyspace, with dynamic splitting. Keep keys sorted and partition the sorted keyspace into contiguous ranges, each range owned by a shard (this is the B-tree / LSM-tree-of-ranges model used by Bigtable, Spanner, and friends). bucket + key is the sort key.

Sorted keyspace, split into ranges (each range = one shard, replicated RF=3):
  Range A: [ aaa.. , cats/.. )
  Range B: [ cats/.. , dogs/photo_500.jpg )
  Range C: [ dogs/photo_500.jpg , photos/2026/.. )
  Range D: [ photos/2026/.. , photos/2027/.. )     <- a hot prefix lives here
  ...
LIST prefix "photos/2026/" -> hits only the range(s) covering that prefix. Efficient.
GET/PUT key -> route to the one range that contains it. Single-shard, fast.
  • LIST is now a contiguous scan over one or a few adjacent ranges - efficient, paginated with a continuation token (the last key returned).
  • Dynamic range splitting handles hot spots and growth. When a range gets too big or too hot, it splits into two ranges served by two shards. When ranges go cold they can merge. This auto-balancing is what lets one bucket scale without a fixed per-bucket ceiling - a hammered prefix splits into more and more ranges until the load spreads across many nodes. (S3’s historical “randomize your key prefixes for performance” advice was exactly to help this splitting; modern S3 auto-splits so the advice is mostly obsolete.)
  • Sequential-key hot shard fix: a range receiving all the appends (log-000001...) gets hot, so it splits, and the split point moves the write frontier onto a fresh shard. Continuous splitting chases the hot tail. For extreme cases the system can salt/scatter internally while preserving list order via a secondary index.

Consistency and read-after-write. The metadata store is strongly consistent (each range is a replicated state machine, RF=3, committed by consensus like Paxos/Raft). Because the object “exists” exactly when its metadata record commits, and the shards were durably written before that commit, a GET that resolves the key is guaranteed to find committed shards. That is how modern S3 delivers strong read-after-write and consistent LIST: the metadata commit is the single linearization point, and the data write strictly precedes it.

PUT: (1) write 14 shards durably  ->  (2) COMMIT metadata record (linearization point)
GET: resolve metadata -> if committed, shards are guaranteed present -> read + decode
An interrupted PUT that never reached step 2 leaves orphan shards, invisible to reads,
reclaimed by GC. No half-visible object ever exists. Read-after-write holds.

Metadata record (small, ~1KB):

bucket/key + version_id ->
   { size, content_type, etag/checksum,
     storage_class,                 // STANDARD / IA / GLACIER
     placement: extent_id + offset  // OR shard_locations[14] for big objects
     created_at, is_delete_marker,
     encryption_key_ref }

This range-partitioned, consensus-replicated, dynamically-splitting sorted map is the actual heart of S3. Durability gets the headlines; this index is what makes “trillions of keys, strong consistency, efficient LIST, no hot shards” simultaneously true, and it is where most naive designs quietly fall over.

3. Large objects and multipart upload

Naive approach: PUT the whole object in one HTTP request, buffer it, then write it. Works for a 10KB JSON.

Where it breaks:

  • A 5TB object cannot be one request. A single TCP stream that must complete atomically means one network blip near the end wastes hours and terabytes of transfer - no resume. Buffering 5TB anywhere is impossible.
  • No parallelism. One stream cannot saturate a fat pipe; you leave throughput on the floor.
  • Front-end memory. You cannot hold the object in RAM to checksum-then-write.

The fix: multipart upload - split the object into independent parts, upload them in parallel, complete atomically.

1. POST /bucket/key?uploads              -> returns an upload_id
2. PUT  /bucket/key?partNumber=1&uploadId=...   (upload part 1, e.g. 100MB) -> ETag1
   PUT  /bucket/key?partNumber=2&uploadId=...   (part 2, in PARALLEL)       -> ETag2
   ... up to 10,000 parts, retriable/resumable independently ...
3. POST /bucket/key?uploadId=...  { parts: [{1,ETag1},{2,ETag2},...] }
                                         -> COMPLETE: atomically publish the object
4. (or) DELETE ...?uploadId=...          -> ABORT: discard parts, GC reclaims them
  • Each part is stored and erasure-coded independently as soon as it arrives (parts are just objects internally, keyed by uploadId + partNumber). A failed part is re-uploaded alone - no restart of the whole 5TB.
  • Parts upload in parallel across many connections, saturating the client’s bandwidth.
  • Completion is a metadata operation, not a data copy. CompleteMultipartUpload writes ONE metadata record whose placement is the ordered list of the parts’ extents/locations. The bytes are never rewritten or concatenated on disk - the object is logically the concatenation of its parts, resolved at read time. This is only possible because objects are immutable: the parts, once written, never change, so pointing at them is safe forever.
  • Atomicity: the object becomes visible exactly at the completion metadata commit. Before that, no GET sees a partial object. Unfinished uploads are cleaned by a lifecycle rule (abort incomplete multipart uploads after 7 days) so abandoned parts do not leak storage.

Reads of a large multipart object use byte-range GETs: the metadata knows each part’s size and offset, so GET Range: bytes=X-Y maps to the specific parts/shards covering that range - the client can download a 5TB object in parallel ranges too, mirroring the upload.

4. Versioning, lifecycle, and multi-region replication (one immutable-data story)

Naive approach: overwrite the key in place, delete removes the bytes, and to copy to another region re-PUT everything nightly.

Where it breaks:

  • Overwrite-in-place loses history and races. A concurrent overwrite + read could tear. Accidental overwrite/delete is unrecoverable - fatal for backup/compliance use cases.
  • Delete-the-bytes fights dedup/immutability and makes point-in-time recovery impossible.
  • Nightly full re-copy across regions moves petabytes redundantly and gives an unbounded RPO (you can lose a day).

The fix, and it all falls out of immutability: every version is a new immutable record; nothing is ever mutated in place.

Versioning. A key is not a slot; it is a sequence of immutable versions. Each PUT to an existing key writes a new version with a new version_id and its own shard placement; the old version’s bytes are untouched.

PUT photos/cat.jpg  -> version v1 (bytes A)
PUT photos/cat.jpg  -> version v2 (bytes B)   // v1 STILL EXISTS, not overwritten
GET photos/cat.jpg              -> returns latest = v2
GET photos/cat.jpg?versionId=v1 -> returns v1
DELETE photos/cat.jpg -> writes a DELETE MARKER as the new latest version.
   GET now returns 404 (latest is a marker), but v1/v2 bytes are intact.
   DELETE ...?versionId=v2 -> permanently removes THAT version's bytes (real delete).

The metadata range for a key holds its version chain (sorted by version, so listing versions is a scan). A plain DELETE is non-destructive (a marker) - this is what makes accidental deletion recoverable. Only an explicit versioned delete or a lifecycle expiration reclaims bytes. Because versions are immutable, no locking is needed between a reader of v1 and a writer of v2 - they touch disjoint bytes.

Lifecycle policies. Per-bucket rules evaluated by a background lifecycle engine that scans metadata (it can scan cheaply because metadata is sorted and separate from data):

Rules (per bucket / prefix / tag):
  - transition to STANDARD_IA after 30 days      (move to cheaper, slower media)
  - transition to GLACIER after 90 days          (cold archive)
  - expire (delete) after 365 days
  - expire noncurrent versions after 30 days     (bound version-history cost)
  - abort incomplete multipart uploads after 7 days

A transition does not touch the object’s identity - it re-encodes/moves the bytes to a different storage tier (e.g. denser EC with slower media, or an archive tier) and updates only the storage_class + placement in the metadata record. The key and version id are unchanged. Expiration is a versioned delete that lets GC reclaim the bytes. Lifecycle runs as a massive background sweep over the sorted metadata, not on the request path.

Multi-region replication. Asynchronous, driven by a replication pipeline fed by a per-bucket change log:

PUT/DELETE in region A  -> append event to the bucket's replication log (durable).
Replication readers stream the log -> for each new version:
   copy the object's bytes to region B (server-side, over backbone),
   then commit the version's metadata in region B.
Ordering preserved per key; version ids carried across so B mirrors A's history.
  • Asynchronous by design. Replication is eventual (seconds to minutes RPO), because making cross-region replication synchronous would put a cross-continent round trip on every PUT’s critical path - unacceptable latency, and a remote-region outage would block local writes. DR/locality does not need synchronous; it needs bounded lag and no loss of the log.
  • The change log is the source of truth for replication, so it survives restarts and never re-copies everything - it resumes from the last replicated log position (bounded, incremental, not a nightly full sweep).
  • Immutability makes cross-region copy trivial: a version never changes, so once copied it is correct forever; no reconciliation of concurrent edits (there are none - a new write is a new version, replicated as its own event). Conflicts reduce to “latest version wins per key,” and since versions are immutable and ordered, that is unambiguous.

The theme across all three: because objects are immutable, versioning is “append a version,” lifecycle is “move/expire an immutable blob,” and replication is “copy an immutable blob and its metadata.” Mutability would have forced locks, merge logic, and torn reads into every one of these; immutability makes them all variations of copy-and-point.

API Design & Data Schema

REST over HTTPS, signed requests (SigV4-style). Bucket + key form the address; the object bytes are the body.

REST API

PUT    /{bucket}/{key}                      -- upload an object (single-shot)
   Headers: Content-Length, Content-MD5/x-amz-checksum, x-amz-storage-class,
            x-amz-meta-*  (user metadata)
   Body: object bytes
   Response 200: { ETag, VersionId }

GET    /{bucket}/{key}                       -- download an object (latest version)
   Optional: ?versionId=... , Range: bytes=START-END
   Response 200/206: object bytes + ETag, Content-Length, Last-Modified, VersionId

HEAD   /{bucket}/{key}                       -- metadata only (size, etag, class), no body

DELETE /{bucket}/{key}                       -- delete (writes a delete marker if versioned)
   Optional: ?versionId=...                  -- permanently delete a specific version
   Response 204

GET    /{bucket}?list-type=2&prefix=photos/2026/&delimiter=/&max-keys=1000&continuation-token=...
   -- list objects by prefix, paginated
   Response 200: { Contents:[{Key,Size,ETag,LastModified,StorageClass}...],
                   CommonPrefixes:[...], NextContinuationToken, IsTruncated }

-- Multipart --
POST   /{bucket}/{key}?uploads                -> { UploadId }
PUT    /{bucket}/{key}?partNumber=N&uploadId=U   (body = part bytes) -> { ETag }
POST   /{bucket}/{key}?uploadId=U   { Parts:[{PartNumber,ETag}...] } -> { ETag, VersionId }
DELETE /{bucket}/{key}?uploadId=U             -- abort

-- Bucket config --
PUT    /{bucket}                              -- create bucket (region, class defaults)
PUT    /{bucket}?versioning   { Status:Enabled }
PUT    /{bucket}?lifecycle    { Rules:[...] }
PUT    /{bucket}?replication  { Role, Rules:[{Destination:region-B, Prefix}] }

Data store schemas

1. Metadata store - range-partitioned, strongly consistent, sorted KV / NewSQL, RF=3 per range. Sort key is bucket + key + version. This is SQL-flavored NewSQL/consensus-KV, NOT a plain hash KV, because LIST needs sorted range scans and PUT-commit needs strong consistency.

Table: objects        -- the key -> bytes index; PARTITIONED BY RANGE of (bucket,key)
  bucket          STRING   } composite
  key             STRING   } SORT / RANGE-PARTITION KEY  (enables prefix LIST)
  version_id      STRING   (sortable, newest-first within a key)
  size            BIGINT
  etag            STRING            -- checksum (integrity + client compare)
  storage_class   ENUM              -- STANDARD | IA | GLACIER
  placement       BLOB              -- extent_id+offset (small obj) OR shard_locs[14]
  is_delete_marker BOOL
  encryption_ref  STRING
  created_at      TIMESTAMP
  user_metadata   MAP
  PRIMARY KEY (bucket, key, version_id DESC)
  -- latest version = first row for (bucket,key); LIST = range scan by (bucket,key)

Table: buckets
  bucket          STRING  PRIMARY KEY
  owner_id        BIGINT
  region          STRING
  versioning      ENUM (Off|Enabled|Suspended)
  lifecycle_rules JSON
  replication     JSON
  default_class   ENUM

2. Placement / extent index - the physical layer (wide-column KV, sharded by extent_id). Maps a storage extent to the disks holding its shards; used by repair and read.

Table: extents
  extent_id       STRING  PARTITION KEY
  ec_scheme       STRING            -- e.g. "10+4"
  shard_locations ARRAY<node_id+disk+path>   -- the 14 physical shard homes
  shard_checksums ARRAY<checksum>            -- per-shard integrity
  state           ENUM (WRITING|SEALED|REPAIRING)
  refcount        BIGINT            -- how many object versions point into it (GC)

3. Data plane - raw shards on disks, content addressed by extent+shard index. No relational schema; a storage node just holds (extent_id, shard_index) -> shard bytes + checksum on local disks. Immutable once sealed.

4. Replication log - append-only per-bucket change stream (a distributed log / queue).

  bucket, seq_no (monotonic), op (PUT|DELETE), key, version_id, timestamp
  Replication readers track a per-destination cursor (last seq_no replicated).

Why this split of stores: the object index is relational-ish and needs sorted scans + strong consistency (LIST + read-after-write), so it is range-partitioned NewSQL/consensus-KV - not a hash KV, which would kill LIST. The bytes are immutable, enormous, and need only durable content storage, so they live on raw disks as EC shards - a database would be catastrophically wrong for exabytes. The extent index is a high-volume point-lookup map (NoSQL wide-column) bridging logical objects to physical shards. Each layer gets exactly the consistency and cost model its access pattern demands; forcing one store to do all three is the naive mistake.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Metadata hot range / hot shard (breaks first). A hammered prefix or a sequential key pattern (log-000001, log-000002, ...) funnels all writes to the single range that owns that key span, and that shard saturates. Fix: dynamic range splitting - a hot or large range auto-splits into two ranges on two nodes; the split point chases the write frontier, so sequential appends keep landing on fresh shards. Cold ranges merge. This gives per-bucket scale with no fixed ceiling. Sharding by sorted range (not user_id, not a raw hash) is the deliberate choice: it keeps LIST as a local scan while splitting handles the hot spots. A hash of the key would kill LIST; range + auto-split gets both.

2. Durability under constant disk failure (the whole point). Fix: erasure coding (10+4) across independent failure domains, continuous scrubbing to catch bit rot, and fast parallel repair to shrink the vulnerability window. Repair speed is the durability lever - rebuild reads from many surviving nodes in parallel and prioritizes objects whose redundancy is most depleted. Place shards across racks/AZs so no single domain failure eats more than one shard.

3. Read bandwidth and hot objects (a viral object). Fix: objects are immutable, so caching is trivially safe with no invalidation - front a read cache and a CDN edge tier; a hot object is served from cache, never re-decoded from shards each time. EC also gives a tail-latency win: read the fastest 10 of 14 shards and skip stragglers. Replicate hot extents to more nodes/zones.

4. Write amplification and PUT latency. Fix: EC writes 1.4x the bytes (vs 3x for replication) across the storage network, and PUT waits only for a durable shard quorum, not all 14. Small objects are packed into large extents and coded together, so a tiny PUT does not pay full 14-shard fixed overhead. Multipart parallelizes large writes.

5. LIST at scale / deep pagination. Fix: LIST is a bounded range scan over sorted metadata with a continuation token (last key), so it never scans the whole bucket and page N does not cost more than page 1. delimiter=/ rolls up common prefixes so listing a “folder” does not enumerate everything under it.

6. Garbage collection of orphaned and deleted bytes. Fix: extents carry a refcount of how many object versions point into them; a deleted version (versioned delete or lifecycle expiry) decrements refcounts, and a background GC reclaims extents at refcount 0 after a grace period. Interrupted PUTs (shards written, metadata never committed) and aborted multipart parts are unreferenced from the start and swept the same way. The grace period plus atomic refcount prevents a PUT racing a GC from losing bytes.

7. Metadata store as a single point of failure. Fix: each range is a consensus group (Raft/Paxos) replicated RF=3 across failure domains with automatic leader failover; a committed object record survives node loss. The store is the linearization point for strong consistency, so it is engineered like a database, not a cache.

8. Cross-region replication lag / regional outage. Fix: async replication off a durable per-bucket change log with a resumable per-destination cursor - bounded RPO, no full re-copies, and a destination-region outage never blocks local PUTs (it just grows the replication backlog, drained on recovery). Immutability means a replicated version is correct forever with no reconciliation.

9. Shard keys and partition keys, stated plainly.

  • Metadata objects table -> range-partitioned by sorted (bucket, key) (enables prefix LIST + read-after-write; auto-splits for hot spots). Not hashed (would break LIST), not by user_id (would create per-user hot ranges and still break global LIST).
  • Extent index -> partitioned by extent_id (uniform, point lookup for read/repair).
  • Data plane -> placement is failure-domain-aware across racks/AZs (durability is placement).
  • Replication log -> partitioned by bucket (per-bucket ordered stream).

10. Stateless everything on the request path. Front-End/API nodes hold no state - any node serves any request, scale by adding nodes behind the LB. All durable state is in the metadata store (consensus) and the data plane (EC shards). No single box whose loss loses data; at worst a request retries against another front-end.

Wrap-Up

The trade-offs that define this design:

  • Erasure coding over replication. 10+4 EC gives higher fault tolerance (survive any 4 losses vs 2) at ~1.4x storage instead of 3x - a ~53% physical-storage cut that is worth billions at exabyte scale. The cost is CPU for encode/decode and read complexity (reconstruct from k shards), plus the need to pack small objects into extents so they do not drown in per-shard overhead. Replication was rejected on cost; single-copy was rejected on durability.
  • Durability is placement + scrub + repair speed, not just code width. Eleven nines comes from spreading shards across independent failure domains, continuously scrubbing for silent corruption, and repairing lost redundancy fast enough that crossing the fault budget inside the repair window is astronomically unlikely. Fast repair is the dominant lever.
  • A range-partitioned, strongly-consistent metadata index is the real scaling wall. Sorting the keyspace makes LIST an efficient local scan and read-after-write a single commit-point guarantee; dynamic range splitting kills hot shards with no per-bucket ceiling. Hash partitioning was rejected because it destroys LIST; one big table was rejected because 100PB of metadata fits nowhere.
  • Immutability is the design’s superpower. Objects never change in place, so caching needs no invalidation, versioning is “append a version,” lifecycle is “move/expire a blob,” multipart completion is “point at existing parts,” and cross-region replication is “copy a blob that is correct forever.” Mutability would have injected locks, torn reads, and merge logic into every one of these.
  • Durability over availability, always. A brief inability to serve is tolerable; losing an acknowledged object is not. PUT returns only after a durable shard quorum plus the metadata commit, so a 200 OK is an ironclad promise.

One-line summary: an S3-like object store is a stateless erasure-coding front-end that splits every immutable object into k+m shards spread across independent failure domains for eleven nines of durability, backed by a range-partitioned strongly-consistent metadata index that maps trillions of sorted keys to their physical shards (auto-splitting to kill hot spots and enabling efficient prefix LIST and read-after-write), with small objects packed into large coded extents, background scrubbing and fast parallel repair sustaining the durability, and versioning, lifecycle tiering, and async multi-region replication all falling out cleanly because the stored bytes never change.