Design an S3-like object storage system

Store trillions of objects of any size with eleven nines of durability, and serve reads and writes over an HTTP API at high throughput.

We are building a multi-tenant object store like S3: clients put and get immutable blobs of any size (bytes to 5 TB) by bucket/key over HTTP, with eleven nines of annual durability, at trillions of objects and millions of requests per second.

Clarifying questions worth asking first: object size distribution (most are small, most bytes are in large ones), whether keys are overwritten in place (yes, last writer wins), whether versioning is required (optional per bucket), list consistency (strong read-after-write, as S3 has offered since 2020), and whether data stays in one region (yes; cross-region replication is an async add-on).

Functional requirements

• Buckets: create, delete, list; each has an owner, region, and settings (versioning, lifecycle rules).
• Objects: PUT, GET (including byte ranges), HEAD, DELETE, and LIST by prefix with pagination.
• Multipart upload for large objects: parts uploaded in parallel, retried one at a time, committed atomically.
• Optional versioning: overwrites and deletes keep old versions; delete writes a delete marker.
• Presigned URLs so browsers and jobs upload or download without holding long-lived credentials.
• Lifecycle rules: move objects to colder tiers after N days, expire them after M days.

Non-functional requirements

• Durability 99.999999999% per object per year; survive the loss of a whole availability zone.
• Availability 99.99% for reads, 99.9% for writes.
• Strong read-after-write consistency for PUT, DELETE, and LIST of a single key.
• First-byte latency p99 under 100 ms for small objects; large objects limited by client bandwidth, not by us.
• Horizontal scale on every axis: object count, bytes, request rate, and per-prefix hot spots.
• Cost per stored GB is the main business metric, so storage overhead must stay near 1.5×, not 3×.

Back-of-the-envelope estimation

• 1 trillion objects; median size 32 KB but mean 1 MB (a long tail of large files) → about 1 EB logical.
• Erasure coding at 1.67× → about 1.7 EB raw. With 20 TB disks that is about 85,000 disks, or about 2,000 servers with 42 disks each per region.
• Metadata: about 400 B per object (key, version, size, ETag, chunk locations, ACL pointer) → 400 TB, 1.2 PB with 3 replicas. This does not fit in one database; it must be sharded.
• Traffic: 5M GET/s and 1M PUT/s at peak. At a 200 KB mean transfer that is about 1 TB/s out and 200 GB/s in.
• Disk failures: at a 1.5% annual failure rate, 85,000 disks lose about 3–4 disks a day. Repair is constant background work, not an incident.

REST over HTTPS, authenticated with a signed request (HMAC of method, path, headers, and body hash, like SigV4).

Errors: 404 NoSuchKey, 412 PreconditionFailed, 400 BadDigest when the checksum does not match, 503 SlowDown with Retry-After when a partition is overloaded.

Large objects and the gateway. The gateway never buffers a whole object. It streams the body: it cuts it into 8 MB chunks, erasure-codes each chunk, and pipelines fragments to storage nodes while the next chunk arrives. Memory per request is a few chunks, not the object. Multipart lets clients use many connections and many gateways at once (a 100 GB upload as 1,000 parts of 100 MB across 50 connections). Downloads use byte-range GETs for the same parallelism. The gateway stays a stateless stream router, and the fleet scales by adding hosts behind the load balancer.

Three stores, separated because their access patterns differ.

Bucket table (small, strongly consistent, replicated with Raft): bucket_name (PK), owner_account_id, region, versioning, lifecycle_rules (JSON), created_at. Tens of millions of rows; cached in every gateway.

Object metadata (sharded, ordered KV store with Raft replication per range, e.g. a FoundationDB- or Spanner-like layer):

Rows are partitioned by range on (bucket_id, key), not by hash, because LIST by prefix must be an ordered scan. Ranges split at about 1 GB or at a request-rate threshold, and move between nodes automatically.

Chunk index (separate sharded KV, hash-partitioned by chunk_id): chunk_id → {volume_id, ec_scheme, fragment_locations[15], refcount, length, checksum}.

Data plane: storage nodes write fragments into large append-only volume files (about 100 GB each) on local disks, with an in-memory index fragment_id → (offset, length). Packing many small fragments into big files avoids filesystem inode limits and keeps disk I/O sequential.

flowchart LR
  C[Client] --> LB[Load balancer]
  LB --> GW[API gateway fleet]
  GW --> AUTH[Auth and IAM]
  GW --> MD[(Object metadata store)]
  GW --> CI[(Chunk index)]
  GW --> PL[Placement service]
  GW --> SN1[Storage node AZ1]
  GW --> SN2[Storage node AZ2]
  GW --> SN3[Storage node AZ3]
  PL --> CM[Cluster map]
  RP[Repair and scrubber] --> SN1
  RP --> CI
  GC[Garbage collector] --> CI
  LC[Lifecycle worker] --> MD

1. Upload. The gateway authenticates the signature and checks the bucket policy. For each 8 MB chunk it asks the placement service for 15 disks spread 5 per AZ, with no two fragments in the same rack. It computes a 9+6 Reed-Solomon code and writes all 15 fragments in parallel. It waits for 12 acks, which survives a slow node. Stragglers finish in the background or are repaired later. Then it writes the chunk index entries, then commits the object metadata row in one transaction. The object becomes visible only at the metadata commit, so readers never see a half-written object.
2. Download. The gateway reads the metadata row (one point read, cached briefly on the read path with ETag invalidation). It maps the requested byte range to chunks. For each chunk it reads the 9 data fragments, which needs no decode. If a fragment is slow beyond the p95, it also reads parity and decodes from the first 9 that arrive. It streams bytes out as they come.
3. Delete. The gateway writes a delete marker (versioned bucket) or removes the metadata row in a transaction, and enqueues decrements for the manifest's chunks. Space is reclaimed asynchronously by the garbage collector. Deletes are fast and never touch disks synchronously.
4. Background. Scrubbers verify checksums. The repair service rebuilds fragments lost to dead disks. Lifecycle workers scan metadata ranges and move objects between tiers.

Why it holds together: the metadata commit is the only point of truth for "this object exists". Data is written before it, and data is reclaimed long after it. Every failure in between leaves orphan chunks, which GC cleans up, but never a dangling pointer.

Durability: erasure coding, placement, and repair.

Use RS 9+6 for STANDARD. Small objects under 1 MB are first written 3× replicated (EC on tiny data wastes IOPS), then a compactor packs them into 8 MB chunks and erasure-codes them within hours. Durability math: a disk fails at 1.5% a year. Repair of one lost fragment is detected in minutes and finished in about 1 hour, because the 20 TB of a dead disk is rebuilt by about 1,000 peers in parallel, each doing about 20 GB. Losing data needs 7 of one chunk's 15 disks to fail inside that window. That probability is many orders below 1e-11 per year, so the real risks are correlated: a bad firmware batch, a software bug, or an operator deleting a volume. Defend against those with mixed disk batches per placement group, staged rollouts, and a deletion grace period. Repair is prioritized by remaining margin: a chunk with 4 fragments lost repairs before one with 1 lost.

Metadata scalability and hot prefixes. 1 trillion rows in about 400 TB is split into about 400,000 ranges of 1 GB, each a 3-replica Raft group, spread over a few thousand metadata servers. Range splitting by load as well as size fixes the classic hot-prefix problem: a bucket writing logs/2026-10-12/... at 50K PUT/s sends every write to the tail range. The split detector notices the range exceeds its budget (about 3,500 writes/s) and splits at the hot key, so the new tail keeps moving across nodes. During the split, clients see 503 SlowDown and retry with backoff. LIST is a range scan that returns 1,000 keys at a time. The continuation token is the last key returned, so pagination is stateless. A cache of bucket and IAM policy in each gateway keeps auth off the metadata path.

Content-addressable dedup and garbage collection. Chunk IDs are SHA-256(chunk bytes), scoped per account. Before writing a chunk, the gateway looks up the hash in the chunk index. If it exists, it increments the refcount and skips the data write. This is a large win for backups and ML checkpoints, where most chunks repeat between versions. Scope dedup to one account: cross-tenant dedup leaks whether someone else stored a file (a timing or cost side channel), and it breaks per-tenant encryption keys.

GC cannot trust refcounts alone. A crash between "write chunk" and "commit metadata" leaves an orphan, and a lost decrement leaks space forever. Use both mechanisms:

• Refcount decrements, sent through a durable queue, reclaim most space within hours.
• A weekly mark-and-sweep per account rebuilds the true reference set from metadata manifests and deletes chunks that are unreferenced and older than 7 days. The age guard protects in-flight uploads, which write chunks before their metadata exists.
• Physical deletion only marks fragments dead in their volume. A volume is compacted, with live fragments copied to a new volume, when it is over 40% dead.

Variable-length chunking. Fixed 8 MB boundaries lose all dedup after a 1-byte insert near the start of a file, because every later boundary shifts. Content-defined chunking puts boundaries where a rolling hash (Rabin or Gear/FastCDC) over a 48-byte window matches a mask. Target an average of 4 MB, with a minimum of 1 MB and a maximum of 16 MB. An insert then changes only one or two chunks. Typical gains on versioned backups are 2–5× more dedup than fixed chunks. The costs: hashing at about 1 GB/s per core on the gateway, and more chunk-index entries. Enable it per bucket for backup-like workloads only.

Integrity, bit rot, and tiering. Checksums at every layer: the client's Content-MD5 or SHA-256 is verified on ingest (400 BadDigest if wrong). Every fragment stores a CRC32C, checked on every read. Each chunk has a SHA-256. A scrubber reads every fragment about every 2 weeks, which is about 1.5% of disk bandwidth. On a mismatch it treats the fragment as lost and triggers repair from the other 14. Tiering: lifecycle workers move objects not read for 30 days to INFREQUENT, which is the same EC on denser and slower HDD shelves. After 90 days they move to ARCHIVE: wide EC such as 20+5 at 1.25×, on disks that are powered down most of the time, or on tape, with restores taking hours. An access log sample (1 in 100 GETs) drives intelligent tiering without logging every read.

• Erasure coding cuts storage from 3× to 1.67×, but makes small writes and repairs more expensive (9× read amplification on repair) and adds decode CPU on degraded reads. Replicate-then-compact gives up some write simplicity to keep small objects fast.
• Range-partitioned metadata makes LIST a cheap ordered scan, but creates hot spots on sequential keys. Hash partitioning avoids hot spots but makes prefix listing a scatter-gather over every shard.
• Strong consistency through a Raft-replicated metadata commit costs one consensus round trip per write (a few ms in-region) in exchange for no stale reads or phantom lists.
• Waiting for 12 of 15 acks lowers tail latency, but the object briefly has less redundancy than its target until stragglers or repair catch up.
• Dedup saves space for repetitive data, but adds a chunk-index lookup to every write, makes deletes asynchronous and GC complex, and must stay inside one tenant to avoid side channels.
• Content-defined chunking improves dedup but costs gateway CPU and creates more, smaller index entries; fixed chunks are cheaper for unique data such as media.
• Cold tiers cut cost by about 3–5×, but make first byte take hours and add retrieval fees, so lifecycle rules must be opt-in and visible.

Mid-level (L4)

• Separates metadata from blob data, and gives a working PUT/GET/DELETE flow with a sensible API.
• Uses replication across failure domains and knows why: a disk or host can die at any time.
• Streams large objects instead of buffering them, and knows multipart upload exists.

Senior (L5)

• Makes the metadata commit the point of visibility, and explains how orphans are then cleaned up.
• Chooses erasure coding with a concrete scheme, the reasoning behind its overhead, and its AZ placement, and does rough durability math.
• Shards metadata by range for LIST, handles hot prefixes by splitting, and explains checksums plus scrubbing for bit rot.

Staff (L6+)

• Quantifies repair bandwidth and time-to-repair as the real durability lever, and names correlated failures (firmware, bugs, operators) as the actual risk.
• Designs GC with both refcounts and mark-and-sweep plus an age guard, and scopes dedup to a tenant for security reasons.
• Discusses cost per GB as the product metric: tiering, content-defined chunking where it pays off, volume compaction, and the replicate-then-EC path for small objects.