Problem RestatementProblem
Design a cloud object store like Amazon S3. Users create buckets and store objects (files of any size, from bytes to terabytes) under keys like photos/2026/cat.jpg. They upload, download, list and delete objects. The service must almost never lose data (S3 promises "11 nines" of durability, meaning 99.999999999%).
Two variants appear in interviews:
- Snowflake: reduce storage cost by not storing duplicate files.
- OpenAI: a photo service where each image has a SHA-256 digest (a fingerprint of the content). Explain where the digest is computed and how identical images are handled.
RequirementsRequirements
1.1 Functional
- PUT, GET, DELETE objects; LIST by prefix.
- Multipart upload for large objects, and ranged GET (download part of a file).
- Optional: deduplicate identical content.
1.2 Non-Functional
- Durability above everything, then availability.
- Scale: trillions of objects, exabytes of data.
- Throughput: large files must upload and download fast.
- Consistency: after a successful PUT, a GET returns the new object (read-after-write).
1.3 Scale Estimates
- 100B objects, average 1 MB → 100 PB of data.
- Metadata: ~500 bytes per object → 50 TB of metadata, which must itself be sharded.
- Requests: millions per second across all users.
1.4 API Design
/{bucket}/{key}(body = data, header Content-SHA256)/{bucket}/{key}(supports a Range header)/{bucket}/{key}/{bucket}?prefix=photos/2026/&continuation-token=?uploads→ upload parts → POST ?uploadId=... to completeHigh-Level ArchitectureArchitecture
2.1 Overview
- Front-end / API servers: authenticate, route and stream data. They are stateless.
- Metadata service: maps
(bucket, key)→ object info (size, content hash, where the data chunks live). Stored in a sharded, strongly consistent database. - Data (storage) nodes: store the actual bytes as chunks on many disks across many racks and zones.
- Placement service: decides which nodes store each chunk.
- Repair / scrubber: constantly checks chunks, and rebuilds lost ones from replicas or parity.
- Garbage collector: frees chunks that nothing references anymore.
2.2 Architecture Diagram
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Client"] --> FE["API front-ends"]
FE --> MD[("Metadata DB - sharded by bucket+key")]
FE --> PL["Placement service"]
FE -->|"write / read chunks"| SN1["Storage node - zone A"]
FE --> SN2["Storage node - zone B"]
FE --> SN3["Storage node - zone C"]
SC["Scrubber + repair"] --> SN1
SC --> SN2
SC --> SN3
GC["Garbage collector"] --> MD
GC --> SN1Data ModelData model
objects (metadata DB, key = bucket + key [+ version]):
bucket, key, version_id, size, content_sha256, chunk_ids[], created_at, storage_class
chunks (for dedup, key = content hash):
chunk_hash, locations[] (node, disk, offset) or erasure-coded fragments, ref_count, sizeKey FlowsFlows
4.1 Upload
- The front-end streams the data, splits it into chunks (e.g., 8 MB), and computes a SHA-256 for each chunk and for the whole object.
- For each chunk, the placement service picks nodes in different zones, and the chunk is written with replication or erasure coding.
- Only after all chunks are safely stored does the front-end write the metadata row, which makes the object visible. That's how we get read-after-write consistency, and it means a failed upload never leaves a half-visible object.
4.2 Download
Look up the metadata, then read chunks from the nearest healthy nodes (in parallel for big files), verify each chunk's checksum, and stream to the client.
Deep Dive A — Eleven nines of durabilityDeep dive
S3 advertises 99.999999999% durability: lose one object in a hundred billion per year. Disks fail constantly, so that number is a statement about repair, not about hardware.
One copy, with backups
Store each object once and take nightly backups to another system.
A disk failure loses everything written since the last backup, and at this scale disks fail every day. Restoring from backup is a manual, hours-long operation per incident. Silent corruption — a disk returning wrong bytes without reporting an error — is not detected at all, and it propagates into the backup.
Three replicas across three zones
Write every object to three disks in three availability zones. Surviving two simultaneous failures is easy, reads can be served from whichever copy is closest, and repair is a simple copy.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
O["Object"] --> Z1["Zone A - full copy"]
O --> Z2["Zone B - full copy"]
O --> Z3["Zone C - full copy"]
Z1 --> COST["3x storage for every byte stored"]It is correct and it costs three times the raw capacity. At exabyte scale that difference is most of the business, and the durability it buys is more than three copies can actually deliver on its own — replicas do not help against corruption nobody notices.
Erasure coding, scrubbing, and repair that outruns failure
Split each chunk into 10 data pieces plus 4 parity pieces across 14 disks in different racks and zones. Any 10 of the 14 reconstruct the chunk.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Chunk"] --> EC["Erasure code 10 + 4"]
EC --> D["14 pieces - separate racks and zones"]
D --> SURV["Survives any 4 simultaneous losses"]
D --> COST["1.4x storage, not 3x"]
SCRUB["Scrubber - re-reads and verifies checksums"] --> D
FAIL["Disk dies"] --> PAR["Many nodes rebuild its pieces in parallel"]
PAR --> SHORT["At-risk window is minutes, not days"]Tolerating four failures at 1.4x cost instead of three copies at 3x is the headline, but the two supporting mechanisms are what produce the eleven nines:
- Scrubbing. Background jobs continuously re-read every piece and verify its checksum. Without this, corruption accumulates silently and is only discovered when enough pieces have rotted that the chunk is already unrecoverable.
- Parallel repair. When a disk dies, its pieces are rebuilt by many nodes at once, so the window during which the chunk has reduced redundancy is minutes. Durability is the race between repair speed and the next failure — and that is the number the design actually optimises.
Both depend on failures being independent, which is why pieces are spread across racks and zones. Fourteen pieces in one rack tolerate four disk failures and zero power failures.
Small or very hot objects often still use plain replication: erasure coding adds read amplification and reconstruction work that is not worth it for a 2 KB object read a million times a day.
Deep Dive B — Deduplication with content hashesDeep dive
- Content-addressed storage: the chunk's ID is its SHA-256 hash. If a new upload has a chunk whose hash already exists, we don't store it again. We just add a reference.
- Where to compute the hash: the client can send it (for integrity checks), but the server must compute it too. Never trust a client-sent hash for dedup, or someone could claim a hash they don't own and read another user's data.
- Reference counting: each chunk tracks how many objects use it. Deleting an object decrements counts, and a chunk is removed only when its count reaches 0. Do this with a garbage collector that runs later and double-checks, not immediately, because a new upload might be referencing the chunk at that moment.
- Privacy: cross-user dedup can leak "someone already uploaded this exact file" through timing. Many systems dedup only within one account or tenant.
- Savings depend on data. Backups and photos shared many times dedup well, while unique encrypted data doesn't.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Durability | Erasure coding (+ replication for small objects) | High durability, low cost | 3x replication: simpler, 2x more storage |
| Metadata | Sharded strongly consistent DB | Read-after-write, fast listing | Eventually consistent store: listings may be stale |
| Dedup | Content hash + ref count + delayed GC | Saves storage safely | No dedup: simpler, costlier |
| Visibility | Metadata written last | No half-written objects | Write metadata first: readers may see missing data |
Common Follow-up QuestionsFollow-ups
- "How does LIST by prefix scale?" Store metadata sorted by
(bucket, key)(range-partitioned), so a prefix is one contiguous range. - "Storage classes?" Move cold objects to cheaper disks or tape (e.g., Glacier) by lifecycle rules. The metadata stays the same, and only the location changes.
- "Versioning?" Keep old versions as separate metadata rows with a version ID, and have DELETE add a delete marker instead of removing data.
Wrap-UpWrap-up
Separate a sharded, strongly consistent metadata store from storage nodes that keep chunks spread across zones, using erasure coding for cheap high durability. Write data first and metadata last so objects appear atomically. Scrub and repair constantly. For deduplication, address chunks by a server-computed SHA-256, count references, and let a delayed garbage collector delete chunks nobody uses.