52. Walkthrough: Design Object Storage (S3)

Step 0 — Clarify the business goal

🎤 Candidate: Object storage sells durability (losing data is the worst failure, worse than downtime), cost per GB (tiers), and elasticity. Is this a public cloud service, so multi-tenant and priced per request and per GB, or internal?

🧑‍💼 Interviewer: Public, multi-tenant, multi-region service.

Step 1–2 — Requirements

Step 3 — Estimates

Durability: with 3× replication, losing an object needs 3 overlapping failures before repair.
  Erasure coding, e.g. 10 data + 4 parity fragments (tolerates any 4 lost) at 1.4× overhead
  → MORE durable than 3× replication at less than half the storage cost, if repair is fast
Repair: disk 20 TB failed → re-create fragments from survivors; at 200 MB/s per disk in parallel across
  hundreds of disks → minutes to hours; repair speed (vs failure rate) determines real durability
Metadata: ~300T objects × ~100-300 B per index entry ≈ 30-90 PB of metadata (before replication)
  → the metadata index is itself one of the largest distributed databases in the system
Small objects: a large share of objects are tiny (KBs) → packing into larger extents is essential

Step 5 — High-level architecture

 Client ─▶ DNS / LB ─▶ Front-end (auth/SigV4, policy check, request routing, throttling per prefix)
   PUT path:
     1. stream object → split into chunks → erasure-code each chunk → write fragments to storage nodes
        in DIFFERENT failure domains (racks/AZs) via the placement service
     2. once ≥ write-quorum fragments durable → commit METADATA: key → {version, size, checksum,
        fragment locations} in the index (strongly consistent, partitioned by bucket+key ranges)
     3. return 200 (with ETag/checksum)
   GET path: index lookup → read k fragments (any k of n) in parallel → reconstruct → stream
   LIST: range scan over the sorted index partition(s) for the prefix
 Storage nodes: append-only extents on disks; checksums per block; background SCRUBBING
 Repair service: detects lost/corrupt fragments (heartbeats + scrubbing) → reconstruct elsewhere
 Lifecycle/tiering: moves objects between classes (hot → infrequent → archive); GC of deleted data

Step 6 — Deep dives

1. Metadata index scaling and hot prefixes: the index is partitioned by key ranges and splits hot ranges automatically. AWS's guidance for S3 is per-prefix request rates (on the order of 3,500 writes and 5,500 reads per second per partitioned prefix), with automatic scaling as load grows. That's why key design (spreading load across prefixes) used to matter and still matters at extremes.
2. Strong consistency: S3 moved to strong read-after-write consistency for all operations, including LIST, in December 2020, with no price or performance trade-off for customers. Conceptually it requires that the metadata path (including caches in front of the index) never serves a version older than the latest committed write. That's a cache coherence problem (§7.2) at enormous scale.
3. Durability engineering: erasure coding across failure domains, end-to-end checksums (client → storage → read), continuous scrubbing, fast repair prioritized by risk (objects that lost the most fragments first), and correlated failure avoidance (placement across power and network domains). Durability comes from math plus operations.
4. Multipart upload: parts uploaded in parallel and independently retryable, committed atomically by the final "complete" call. Incomplete uploads consume storage until they're aborted, so lifecycle rules should abort them.
5. Deletes and garbage collection: delete writes a tombstone or delete marker in metadata. Physical space is reclaimed later by GC and extent compaction, which must respect versioning, object lock, and legal hold (§24).

Step 7 — Failure modes & corner cases