Object Storage Service (Amazon S3) with Deduplication

0) Problem Restatement

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.

1) Requirements

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

• PUT /{bucket}/{key} (body = data, header Content-SHA256)
• GET /{bucket}/{key} (supports a Range header)
• DELETE /{bucket}/{key}
• GET /{bucket}?prefix=photos/2026/&continuation-token=
• Multipart: POST ?uploads → upload parts → POST ?uploadId=... to complete

2) High-Level Architecture

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

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 --> SN1

3) Data 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, size

4) Key Flows

4.1 Upload

1. 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.
2. For each chunk, the placement service picks nodes in different zones, and the chunk is written with replication or erasure coding.
3. 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.

5) Deep Dive A — Durability

• Replication: 3 copies in 3 zones. Simple, fast reads, but 3x the storage cost.
• Erasure coding: split a chunk into e.g. 10 data pieces + 4 parity pieces across 14 disks. Any 10 can rebuild the chunk. That survives 4 failures at only 1.4x storage cost. It's used for most data, while small or hot objects may use replication.
• Scrubbing: background jobs read every chunk regularly and verify checksums, catching silent disk corruption.
• Fast repair: when a disk dies, its pieces are rebuilt from the others in parallel by many nodes, so the "at-risk" window is short. Durability comes from failures being independent (different racks and zones) and repair being faster than new failures.

6) Deep Dive B — Deduplication with content hashes

• 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.

7) Trade-offs & Alternatives

8) Common Follow-up Questions

• "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.

9) Wrap-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.