Design S3-Like Distributed Object Storage

1. Problem Statement & Scope Clarification

System Mission

Design a planetary-scale, multi-tenant distributed Object Storage Service (equivalent to Amazon Simple Storage Service / AWS S3) engineered to ingest, persist, and serve exabytes of unstructured binary objects (images, videos, documents, database backups, analytical datasets) with $99.999999999\%$ (11 9s) annual durability, sub-$50\text{ ms}$ $P99$ read latency, and strong read-after-write consistency for PUT and DELETE operations.

Functional Requirements

1. Object CRUD Operations: Clients upload (PUT), read (GET), delete (DELETE), and inspect headers (HEAD) for immutable objects identified by a unique (bucket_name, object_key) coordinate.
2. Multipart Parallel Upload: Objects larger than $100\text{ MB}$ (and up to $5\text{ TB}$) can be split into arbitrary chunks ($5\text{ MB} - 5\text{ GB}$ per part) uploaded concurrently in random order and assembled atomically.
3. Prefix-Based Listing & Delimiters: Hierarchical folder simulation allowing clients to list objects under a given bucket prefix (e.g., GET /photos/2026/09/?delimiter=/) with cursor-based pagination.
4. Presigned URLs & Fine-Grained Access Control: Generate cryptographically signed, time-bounded URLs allowing untrusted web/mobile clients to stream direct uploads and downloads without passing through application backend servers.
5. Intelligent Lifecycle Tiering & Versioning: Automatic object versioning (version_id) and background policy transition from High-Throughput NVMe/EBS Standard storage to lower-cost Infrequent Access (S3-IA) and archival cold tiers (S3 Glacier / Glacier Deep Archive).

Non-Functional Requirements (SLAs & SLOs)

• Durability: $99.999999999\%$ (11 9s) annual durability per object via Reed-Solomon Erasure Coding ($8+4$ or $10+4$) striped across independent failure domains (racks and availability zones).
• Availability: $99.99\%$ ("four nines") uptime SLA for the data and metadata planes across multi-AZ deployments.
• Latency (P99):
  • Metadata Operations (HEAD, Small GET $< 64\text{ KB}$): $P99 < 15\text{ ms}$.
  • Streaming Ingress (PUT chunks): Time-to-First-Byte (TTFB) $< 20\text{ ms}$, sustaining link saturation.
  • Streaming Egress (GET streaming): TTFB $< 25\text{ ms}$, continuous line-rate throughput.
• Consistency Model: Strong Read-After-Write Consistency for PUT and DELETE requests of both new and overwritten objects. Any subsequent read instantly reflects the latest committed byte stream and metadata.
• Throughput & Scale: Support $> 100\text{ Billion}$ total objects, $20\text{ Petabytes}$ initial raw storage capacity (scaling to Exabytes), and peak ingress/egress network bandwidth exceeding $400\text{ Gbps}$.

---

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Ingestion Scale & Traffic Projections

• Total Objects Stored: $100,000,000,000$ ($100\text{ Billion objects}$).
• Average Object Size:
  • Small objects / thumbnails ($20\%$ of count): $50\text{ KB}$.
  • Medium documents / images ($60\%$ of count): $2\text{ MB}$.
  • Large media files / backups ($20\%$ of count): $50\text{ MB}$.
  • Weighted Average Object Size: $\overline{S} = (0.20 \times 0.05\text{ MB}) + (0.60 \times 2.0\text{ MB}) + (0.20 \times 50.0\text{ MB}) = 0.01 + 1.20 + 10.0 = \mathbf{11.21\text{ MB}}$
• Total Raw Data Footprint: $\text{Raw Storage} = 10^{11}\text{ objects} \times 11.21\text{ MB} \approx 1.121 \times 10^{12}\text{ MB} \approx \mathbf{1.121\text{ Exabytes (EB)}}$ (For a baseline initial cluster footprint, we model a $20\text{ PB}$ active tier with $1.8\text{ Billion}$ live objects).

Request Throughput (QPS)

• Read/Write Ratio: $10:1$ read-heavy workload.
• Average Write QPS: $\text{Write QPS}_{\text{avg}} = 10,000\text{ writes/sec}$
• Peak Write QPS ($2.5\times$ peak): $\text{Write QPS}_{\text{peak}} = 25,000\text{ writes/sec}$
• Average Read QPS: $\text{Read QPS}_{\text{avg}} = 100,000\text{ reads/sec}$
• Peak Read QPS ($2.5\times$ peak): $\text{Read QPS}_{\text{peak}} = 250,000\text{ reads/sec}$

Network Bandwidth & Egress Sizing

• Assuming average streaming read size is $200\text{ KB}$ for online traffic (larger payloads fetched via byte-range streams): $\text{Average Egress Bandwidth} = 100,000\text{ reads/sec} \times 200\text{ KB} = 20\text{ GB/sec} = 160\text{ Gbps}$ $\text{Peak Egress Bandwidth} = 250,000\text{ reads/sec} \times 200\text{ KB} = 50\text{ GB/sec} = \mathbf{400\text{ Gbps}}$
• Peak Ingress Bandwidth: $\text{Peak Ingress Bandwidth} = 25,000\text{ writes/sec} \times 200\text{ KB} = 5\text{ GB/sec} = \mathbf{40\text{ Gbps}}$

Erasure Coding Storage & Rebuild Bandwidth Mathematics

To deliver $11\text{ 9s}$ durability without the $3.0\times$ cost penalty of triple replication, we deploy Reed-Solomon $8+4$ Erasure Coding ($K=8$ data chunks, $M=4$ parity chunks):

• Storage Overhead: $\text{Storage Overhead Factor} = \frac{K + M}{K} = \frac{8 + 4}{8} = \mathbf{1.5\times} \quad (33.3\% \text{ parity overhead vs } 200\% \text{ for 3-way replication})$
• For a $20\text{ PB}$ raw active working set: $\text{Effective Physical Storage} = 20\text{ PB} \times 1.5 = \mathbf{30\text{ PB}}$
• Durability Guarantee: The system can sustain the complete, simultaneous destruction of any 4 storage nodes/racks/AZs without a single bit of data loss.
• Reconstruction Bandwidth Sizing: When a storage node holding a $16\text{ TB}$ NVMe drive fails, the cluster must read $K=8$ surviving chunks to reconstruct the 1 lost chunk for every stripe: $\text{Total Network Read Volume to Reconstruct 1 Drive} = 16\text{ TB} \times 8 = \mathbf{128\text{ TB Network Read}}$ To rebuild within an MTTR (Mean Time to Repair) window of $\tau = 4\text{ hours}$ ($14,400\text{ sec}$): $\text{Required Cluster Rebuild Bandwidth} = \frac{128 \times 10^{12}\text{ bytes}}{14,400\text{ sec}} \approx 8.89\text{ GB/sec} \approx \mathbf{71.1\text{ Gbps}}$ AWS multi-chassis $100\text{ Gbps}$ VPC network fabrics easily accommodate this rebuild overhead without degrading client traffic.

Metadata Footprint Estimation

• Metadata Record Size: Bucket name ($32\text{B}$), object key ($64\text{B}$), version ($16\text{B}$), size ($8\text{B}$), ETag/MD5 ($32\text{B}$), timestamp ($8\text{B}$), storage class ($8\text{B}$), chunk manifest pointers ($12 \times 16\text{B} = 192\text{B}$) $\approx 360\text{ Bytes}$.
• With B-Tree and primary key index overhead $\approx 600\text{ Bytes/record}$.
• For $100\text{ Billion objects}$: $\text{Total Metadata Size} = 10^{11} \times 600\text{ Bytes} \approx 60\text{ TB}$ This dataset is distributed across an Amazon Aurora PostgreSQL Multi-Master / Multi-AZ Cluster combined with an Amazon DynamoDB Single-Table Store.

---

3. AWS-First High-Level Architecture

The architecture decouples the Control & Metadata Plane (handling authorization, key indexes, bucket ACLs, and multipart manifests) from the Data Plane (responsible for chunking, erasure coding, streaming I/O, and raw block storage on NVMe clusters).

Synthesizing vector architecture diagram...

Data Flow Walkthrough

1. Request Ingress & Signature Validation: Requests arrive via Route 53 Anycast DNS and NLB. The API Gateway validates the request using AWS Signature Version 4 (SigV4) against an in-memory AWS IAM/KMS caching layer.
2. Metadata Authorization & Resolution:
   • For PUT: The gateway queries the Metadata Plane to verify bucket existence, write permissions, and bucket quota.
   • For GET: The gateway queries Aurora/Redis to retrieve the object's chunk manifest, version ID, and the physical network addresses of the 12 storage nodes holding the $8+4$ stripes.
3. Data Streaming & Erasure Coding:
   • On PUT: The client payload streams directly into the Data Router. As data arrives, the Erasure Coding Engine slices the stream into $K=8$ equal data chunks, computes $M=4$ parity chunks via Galois Field SIMD instructions, and concurrently writes the 12 chunks to 12 distinct storage nodes distributed across 3 Availability Zones.
   • Once all 8 data chunks and at least 2 parity chunks acknowledge persistence (a durable quorum of $\ge 10/12$), the Metadata Plane updates the object status to ACTIVE, and an HTTP 200/201 with the object ETag is returned to the client.
4. Zero-Copy Streaming Read:
   • On GET: The gateway connects concurrently to the first 8 fastest responding storage nodes holding data chunks. Chunks stream directly to the client over an HTTP/2 response stream. If 1 or 2 nodes are slow or offline, parity chunks are read in parallel and decoded on the fly with zero client-perceived disruption.

Concrete Step-by-Step Request Walkthrough: Tracing an Object Upload (PUT)

---

4. API Interface Design & Wire Protocol

The service exposes an S3-compatible REST API over HTTP/1.1 and HTTP/2 with strict AWS Signature Version 4 authentication.

1. Object Upload (PUT)

httpCopy
PUT /my-media-bucket/videos/2026/presentation.mp4 HTTP/1.1
Host: s3.us-east-1.amazonaws.com
Authorization: AWS4-HMAC-SHA256 Credential=AKIAIOSFODNN7EXAMPLE/20260916/us-east-1/s3/aws4_request, SignedHeaders=content-length;content-type;host;x-amz-content-sha256;x-amz-date, Signature=fe5f80f779dad5328e...
Content-Type: video/mp4
Content-Length: 67108864
x-amz-date: 20260916T120000Z
x-amz-storage-class: STANDARD
x-amz-checksum-sha256: 47DEQpj8HBSa+/TImW+5JCeuQeRkm5NMpJWZG3hSuFU=

<binary video payload stream (64 MB)>

Response:

httpCopy
HTTP/1.1 200 OK
x-amz-id-2: LriByRT6OQIqZ0yKq3h8dQe9n1F2c...
x-amz-request-id: 4A41C16489469FB2
Date: Wed, 16 Sep 2026 12:00:01 GMT
ETag: "c8b417e8ef28258b538053c9e99a8123"
x-amz-version-id: "9mQkPzY_1n0J12Vw"
x-amz-server-side-encryption: AES256
Content-Length: 0

2. Initiate Multipart Upload (POST ?uploads)

httpCopy
POST /my-media-bucket/backups/database_dump.tar.gz?uploads HTTP/1.1
Host: s3.us-east-1.amazonaws.com
Authorization: AWS4-HMAC-SHA256 Credential=...
Content-Type: application/gzip
x-amz-date: 20260916T120500Z

Response: 200 OK
Content-Type: application/xml

<?xml version="1.0" encoding="UTF-8"?>
<InitiateMultipartUploadResult xmlns="http://s3.amazonaws.com/doc/2006-03-01/">
  <Bucket>my-media-bucket</Bucket>
  <Key>backups/database_dump.tar.gz</Key>
  <UploadId>upload_id_7a8b9c0d1e2f3a4b</UploadId>
</InitiateMultipartUploadResult>

3. Upload Part (PUT ?partNumber=N&uploadId=X)

httpCopy
PUT /my-media-bucket/backups/database_dump.tar.gz?partNumber=1&uploadId=upload_id_7a8b9c0d1e2f3a4b HTTP/1.1
Host: s3.us-east-1.amazonaws.com
Content-Length: 104857600
Content-MD5: Q2hlY2sgSW50ZWdyaXR5IQ==

<binary part 1 payload (100 MB)>

Response: 200 OK
ETag: "b10a8db164e0754105b7a99be72e3fe5"

4. Complete Multipart Upload (POST ?uploadId=X)

httpCopy
POST /my-media-bucket/backups/database_dump.tar.gz?uploadId=upload_id_7a8b9c0d1e2f3a4b HTTP/1.1
Host: s3.us-east-1.amazonaws.com
Content-Type: application/xml

<CompleteMultipartUpload>
  <Part>
    <PartNumber>1</PartNumber>
    <ETag>"b10a8db164e0754105b7a99be72e3fe5"</ETag>
  </Part>
  <Part>
    <PartNumber>2</PartNumber>
    <ETag>"1b2cf535f27731c974343645a3985328"</ETag>
  </Part>
</CompleteMultipartUpload>

Response: 200 OK
<CompleteMultipartUploadResult>
  <Location>https://my-media-bucket.s3.amazonaws.com/backups/database_dump.tar.gz</Location>
  <Bucket>my-media-bucket</Bucket>
  <Key>backups/database_dump.tar.gz</Key>
  <ETag>"3a72810f92b0e9d6b2c8a14e1011e40b-2"</ETag>
  <VersionId>4vJk90Wqz18LkmQ</VersionId>
</CompleteMultipartUploadResult>

---

5. Data Models & Storage Architecture

Relational Schema: Amazon Aurora PostgreSQL (Control & Object Catalog)

The metadata tier manages buckets, object hierarchies, and multipart tracking.

sqlCopy
-- 1. Buckets Table
CREATE TABLE storage_buckets (
    bucket_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    bucket_name VARCHAR(63) UNIQUE NOT NULL,
    owner_account_id VARCHAR(32) NOT NULL,
    region VARCHAR(32) NOT NULL,
    versioning_status VARCHAR(16) DEFAULT 'DISABLED' CHECK (versioning_status IN ('DISABLED', 'ENABLED', 'SUSPENDED')),
    encryption_algorithm VARCHAR(32) DEFAULT 'AES256',
    kms_master_key_id VARCHAR(128),
    created_at TIMESTAMPTZ DEFAULT NOW(),
    storage_quota_bytes BIGINT DEFAULT 109951162777600 -- 100 TB Default
);
CREATE INDEX idx_buckets_owner ON storage_buckets(owner_account_id);

-- 2. Object Metadata Table (Strong Read-After-Write Consistency Catalog)
CREATE TABLE object_metadata (
    object_uuid UUID DEFAULT gen_random_uuid(),
    bucket_id UUID NOT NULL REFERENCES storage_buckets(bucket_id) ON DELETE CASCADE,
    object_key VARCHAR(1024) NOT NULL,
    version_id VARCHAR(64) NOT NULL,
    is_latest BOOLEAN NOT NULL DEFAULT TRUE,
    is_delete_marker BOOLEAN NOT NULL DEFAULT FALSE,
    object_size_bytes BIGINT NOT NULL,
    etag VARCHAR(64) NOT NULL,
    content_type VARCHAR(128) DEFAULT 'application/octet-stream',
    storage_class VARCHAR(32) DEFAULT 'STANDARD' CHECK (storage_class IN ('STANDARD', 'INTELLIGENT_TIERING', 'STANDARD_IA', 'GLACIER', 'DEEP_ARCHIVE')),
    lifecycle_expiry_ts TIMESTAMPTZ,
    created_at TIMESTAMPTZ DEFAULT NOW(),
    manifest_id UUID NOT NULL,
    PRIMARY KEY (bucket_id, object_key, version_id)
);

-- Fast range scanning for hierarchical listing with delimiters (e.g. photos/2026/%)
CREATE INDEX idx_objects_prefix_listing ON object_metadata (bucket_id, object_key text_pattern_ops, is_latest)
WHERE is_delete_marker = FALSE;

-- 3. Multipart Upload Sessions Table
CREATE TABLE multipart_uploads (
    upload_id VARCHAR(64) PRIMARY KEY,
    bucket_id UUID NOT NULL REFERENCES storage_buckets(bucket_id),
    object_key VARCHAR(1024) NOT NULL,
    storage_class VARCHAR(32) DEFAULT 'STANDARD',
    initiator_identity VARCHAR(64) NOT NULL,
    status VARCHAR(16) DEFAULT 'INITIATED' CHECK (status IN ('INITIATED', 'COMPLETING', 'ABORTED', 'COMPLETED')),
    created_at TIMESTAMPTZ DEFAULT NOW(),
    abort_rule_deadline TIMESTAMPTZ NOT NULL DEFAULT (NOW() + INTERVAL '7 days')
);

-- 4. Multipart Parts Table
CREATE TABLE multipart_parts (
    upload_id VARCHAR(64) NOT NULL REFERENCES multipart_uploads(upload_id) ON DELETE CASCADE,
    part_number INT NOT NULL CHECK (part_number BETWEEN 1 AND 10000),
    part_size_bytes BIGINT NOT NULL,
    etag VARCHAR(64) NOT NULL,
    manifest_id UUID NOT NULL,
    uploaded_at TIMESTAMPTZ DEFAULT NOW(),
    PRIMARY KEY (upload_id, part_number)
);

DynamoDB Single-Table Design: BlobChunkManifestTable

While Aurora handles SQL prefix listing and ACID operations on buckets, raw chunk placements are persisted in DynamoDB for ultra-low latency ($< 3\text{ ms}$) key-value lookups by the data router during streaming:

---