Object Storage

Problem Statement & Requirements

Design a distributed object storage system that stores and retrieves arbitrary binary objects (files) of any size with high durability, availability, and scalability — similar to Amazon S3, Google Cloud Storage, or Azure Blob Storage.

Functional Requirements

• PUT object — upload objects from bytes to 5 TB in size
• GET object — download objects by key; support range reads (byte-range fetches)
• DELETE object — remove an object permanently
• LIST objects — list objects in a bucket with prefix filtering and pagination
• Multipart upload — upload large objects in parallel parts, then assemble
• Buckets — logical namespace for objects (globally unique name)
• Metadata — per-object user-defined metadata (key-value headers) and system metadata (size, content-type, etag, created_at)
• Versioning — optional per-bucket; retain all historical versions of an object
• Presigned URLs — generate time-limited, signed URLs for unauthenticated upload/download
• Lifecycle policies — auto-transition objects between storage classes or auto-delete after N days
• Storage classes — Standard (hot), Infrequent Access, Archive (cold)

Non-Functional Requirements

• Durability — 99.999999999% (11 nines) — lose < 1 object per 10 billion stored per year
• Availability — 99.99% (< 53 min downtime/year)
• Scalability — store exabytes of data, trillions of objects
• Throughput — handle millions of requests/second globally
• Consistency — strong read-after-write consistency (S3 achieved this in 2020)
• No size limit — individual objects up to 5 TB; buckets unlimited

Out of Scope

• POSIX file system semantics (no rename, no directories, no locks)
• Real-time streaming (this is blob storage, not a streaming platform)
• Block storage (EBS) or file storage (EFS/NFS)

Scale Estimations

Traffic

Storage

Bandwidth

Hardware Estimate

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

API Design

PUT Object

PUT /{bucket}/{key} HTTP/1.1
Host: s3.region.example.com
Content-Type: image/jpeg
Content-Length: 3145728
x-amz-meta-camera: "iPhone 15"          # user metadata
x-amz-storage-class: STANDARD
Authorization: AWS4-HMAC-SHA256 Credential=.../s3/aws4_request, ...

<3 MB binary body>

Response (200 OK):
ETag: "d41d8cd98f00b204e9800998ecf8427e"
x-amz-version-id: "v3nR2ql9sa8GhZ1"     # if versioning enabled

GET Object

GET /{bucket}/{key} HTTP/1.1
Host: s3.region.example.com
Range: bytes=0-1048575                    # optional: first 1 MB only
If-None-Match: "d41d8cd98f00b204e9800998ecf8427e"   # conditional

Response (200 OK / 206 Partial / 304 Not Modified):
Content-Type: image/jpeg
Content-Length: 3145728
ETag: "d41d8cd98f00b204e9800998ecf8427e"
Last-Modified: Thu, 03 Apr 2026 10:00:00 GMT
x-amz-meta-camera: "iPhone 15"

<binary body>

Multipart Upload (Large Objects)

Step 1: Initiate
POST /{bucket}/{key}?uploads HTTP/1.1

Response: { "upload_id": "upl-abc123" }

Step 2: Upload Parts (parallel)
PUT /{bucket}/{key}?partNumber=1&uploadId=upl-abc123
<part 1 body: 100 MB>  → ETag: "etag1"

PUT /{bucket}/{key}?partNumber=2&uploadId=upl-abc123
<part 2 body: 100 MB>  → ETag: "etag2"

... (up to 10,000 parts, 5 MB - 5 GB each)

Step 3: Complete
POST /{bucket}/{key}?uploadId=upl-abc123
{
  "parts": [
    {"part_number": 1, "etag": "etag1"},
    {"part_number": 2, "etag": "etag2"}
  ]
}

Response (200 OK):
ETag: "composite-etag-abc"

LIST Objects

GET /{bucket}?prefix=photos/2026/&delimiter=/&max-keys=1000&continuation-token=...

Response (200 OK):
{
  "name": "my-bucket",
  "prefix": "photos/2026/",
  "delimiter": "/",
  "max_keys": 1000,
  "is_truncated": true,
  "continuation_token": "next-page-token",
  "common_prefixes": ["photos/2026/01/", "photos/2026/02/"],   # "folders"
  "contents": [
    {
      "key": "photos/2026/cover.jpg",
      "size": 3145728,
      "etag": "d41d8cd98f00...",
      "last_modified": "2026-04-03T10:00:00Z",
      "storage_class": "STANDARD"
    }
  ]
}

Presigned URL

# Server-side generation (SDK)
url = s3.generate_presigned_url(
    method="GET",
    bucket="my-bucket",
    key="photos/cat.jpg",
    expires_in=3600   # 1 hour
)
# → https://s3.region.example.com/my-bucket/photos/cat.jpg
#     ?X-Amz-Expires=3600
#     &X-Amz-Signature=a1b2c3...
#     &X-Amz-Credential=...

# Client uses URL directly — no SDK or credentials needed
GET https://s3.region.example.com/my-bucket/photos/cat.jpg?X-Amz-Expires=...
→ 200 OK + binary data (if signature valid and not expired)

Data Model

Object Metadata Schema

Data Chunk Layout

Bucket Metadata

Core Design Decisions

Decision 1: Data Durability — How to Achieve 11 Nines

This is THE most important decision. Losing even one customer object is unacceptable.

Option A: Replication (3 copies across AZs)

Option B: Erasure Coding (Reed-Solomon)

Recommendation: Hybrid Approach

Decision 2: Metadata Store — The Brain of the System

Decision 3: Consistency Model

Detailed Flow Diagrams

PUT Object Flow

GET Object Flow

Multipart Upload Flow

Garbage Collection & Compaction

The Problem

GC Architecture

Aggregate File Compaction

Storage Node Internals

Disk Layout

Data Integrity — Checksums Everywhere

Storage Classes & Lifecycle

Handling Edge Cases

Concurrent PUT to Same Key

Problem: Two clients PUT the same key simultaneously

  Client A: PUT bucket/key val=A → writes to nodes, commits metadata
  Client B: PUT bucket/key val=B → writes to nodes, commits metadata

Resolution:
  • Metadata store uses optimistic concurrency (version vector or CAS)
  • "Last writer wins" based on metadata commit timestamp
  • Both data payloads are written; GC later cleans up the loser's chunks
  • With versioning enabled: both versions are preserved

  The client that receives 200 OK last is the "winner"
  All subsequent GETs return the winner's value
  Guaranteed by strong consistency of metadata store

Partial Failure During PUT

Problem: Data written to 2 of 3 nodes, then gateway crashes

Scenario 1: Metadata NOT yet committed
  → Object doesn't exist (metadata is source of truth)
  → Orphaned chunks on 2 nodes → GC cleans up in 72h
  → Client gets timeout → retries → new PUT succeeds

Scenario 2: Metadata committed (quorum write succeeded)
  → Object exists with 2 of 3 replicas
  → Repair service detects under-replicated chunks
  → Copies from surviving replica to new 3rd node
  → Full durability restored within minutes

Key insight: Metadata commit is the "point of no return"
  Before commit: object doesn't exist, chunks are garbage
  After commit: object exists, repair ensures full replication

Hot Bucket / Hot Key

Problem: One bucket gets 1M+ requests/sec (e.g., viral content, popular API)

Metadata hotspot:
  All requests for bucket X hit the same metadata partition
  → Add request-level caching for metadata (short TTL, 1-5s)
  → Partition metadata by hash(bucket + key) not just bucket

Data hotspot:
  One object read 100K times/sec
  → CDN / caching layer in front of object storage
  → Read from any of 3 replicas (load balance)
  → For extreme cases: create temporary read-only replicas

S3 solved this with automatic partition splitting:
  Bucket with increasing key prefix "2026/04/03/photo-001"
  → Auto-splits partition at "2026/04/03/photo-500"
  → Each partition served by different nodes

LIST Performance at Scale

Problem: Bucket with 10 billion objects, LIST with prefix scan

  Naive approach: scan all 10B keys → timeout

  Solution: Metadata index designed for prefix scans
  
  Key layout in metadata store:
    bucket=my-photos key=photos/2026/01/01/img001.jpg
    bucket=my-photos key=photos/2026/01/01/img002.jpg
    bucket=my-photos key=photos/2026/01/02/img001.jpg
    ...

  LIST ?prefix=photos/2026/01/01/
  → Range scan from "photos/2026/01/01/" to "photos/2026/01/01/\xff"
  → Returns first 1000 keys + continuation token
  → Continuation token = last key seen (for next page)

  With ordered KV store: range scan is O(log N + K) where K = results
  → Fast regardless of total bucket size

Cross-Region Replication

Tradeoffs & Design Decisions Summary

Reliability & Fault Tolerance

Single Points of Failure & Mitigations

Durability Math (11 Nines in Detail)

Graceful Degradation

Level 1 (single disk failure):
  → Chunks on that disk read from other 2 replicas. Zero impact.
  → Repair creates new 3rd replica within 1-4 hours.

Level 2 (single node failure):
  → All chunks on that node served from replicas.
  → Repair redistributes replacement replicas across cluster.
  → Brief increase in cross-AZ traffic.

Level 3 (full AZ outage):
  → 1/3 of primary replicas unavailable.
  → Remaining 2 AZs serve all reads (2 of 3 replicas survive).
  → Writes: quorum (2 of 3) still possible across remaining AZs.
  → Metadata: Raft continues with majority of nodes.

Level 4 (metadata store degradation):
  → PUTs and DELETEs may fail (need metadata write).
  → GETs for recently accessed objects served from gateway cache.
  → LIST requests fail until metadata recovers.
  → Data is safe on storage nodes regardless.

Level 5 (region outage):
  → Failover to DR region (if cross-region replication enabled).
  → RPO: seconds to minutes (replication lag).
  → RTO: minutes (DNS update + metadata sync verification).

High-Level Architecture

Component Breakdown

Full System Architecture (Production-Grade)

Compare storing a million small objects with storing a few enormous ones. The first workload stresses metadata and per-request overhead; the second stresses transfer throughput, multipart recovery, and repair bandwidth. Use those differences to explain why one redundancy and placement policy may not suit every storage tier.

Interview Tips

1. Start with the separation of metadata and data — This is the foundational insight. Metadata (where is this object?) is small, needs strong consistency, and lives on SSD. Data (the actual bytes) is large, needs durability, and lives on HDD. They have completely different requirements.

2. Explain 11 nines of durability concretely — Don't just say "replicate 3 times." Walk through the math: disk failure rate, repair window, probability of correlated failure. Show that fast repair (MTTR) matters more than replica count.

3. Erasure coding vs replication is the #1 tradeoff — At exabyte scale, 3× replication costs 2× more than erasure coding. Explain RS(10,4): 40% overhead instead of 200%, tolerates any 4 chunk failures. Use replication for hot data (speed), EC for cold (cost).

4. Multipart upload shows depth — Explain that parts are NOT physically concatenated. Metadata records the ordered list of part locations. GET streams parts in sequence. Zero-copy assembly. This is a non-obvious insight that impresses interviewers.

5. Address the small object problem — Millions of 1 KB files on disk = inode exhaustion + wasted allocation blocks. Solution: pack into aggregate files (256 MB). Index maps (object_id → file + offset + length). This shows practical systems knowledge.

6. GC with grace period prevents data loss — Explain the race condition: in-flight PUT writes chunks before metadata commits. If GC deletes "unreferenced" chunks during this window, data is lost. 72-hour grace period eliminates this risk.

7. Strong consistency is achievable — S3 switched to strong read-after-write in 2020. Explain how: quorum reads/writes on metadata store, linearizable operations via Raft, and why this eliminates an entire class of application bugs.

8. LIST performance at scale — Naive LIST on a billion-object bucket is a disaster. Explain ordered key-value store with range scans: O(log N + K) where K is result count. Prefix filtering is just a range scan with bounds.

9. Mention storage classes and lifecycle — Shows you understand the economics. Standard (3× replication, fast) → IA (EC, cheaper) → Glacier (EC, cheapest, slow retrieval). Lifecycle engine transitions automatically.

10. End with operational concerns — Background scrubbing (detect bit rot before it's needed), repair prioritization (most-at-risk chunks first), capacity planning (predict when to add nodes), and the importance of cross-AZ and cross-region placement for correlated failure resistance.