Distributed File Storage (S3-like Object Storage)

Object storage lets you upload any file — a 2 KB JSON config, a 500 MB video, a 5 GB database backup — and retrieve it later using a simple key. You give the system a name (the key) and it gives you back the bytes, no matter how big the file is or how many files the system already holds. Amazon S3, Google Cloud Storage, and Azure Blob Storage all work this way.

Think of it like a planet-sized filing cabinet. You label each folder (the key), drop your file inside, and the cabinet stores it across thousands of drawers in dozens of buildings so that even if an entire building burns down, your file survives intact. You never need to know which drawer holds your file — you just ask for it by name and the system figures out where the pieces are.

What makes this deceptively hard is the combination of extreme durability (S3 promises 99.999999999% — eleven nines — meaning you would statistically lose one object out of 10 million over a 10,000-year period), massive scale (trillions of objects, exabytes of data), and the fundamental separation between metadata and data (where a file is vs. what a file contains are completely different problems at scale).

This case study follows the same eight-step framework:

• Clarify constraints (Steps 1-2) — What does the system do, and how much data must it handle?
• High-level design (Step 3) — What are the major components and how do they connect?
• Deep dives (Steps 4-7) — How do the trickiest parts actually work?
• Trade-offs (Step 8) — What did we give up, and when would we choose differently?

Step 1: Clarify Requirements#

Functional Requirements#

These describe what the system does.

Non-Functional Requirements#

These describe how well the system works.

The single most important non-functional requirement is durability. Users can tolerate brief unavailability — they retry and it works a minute later. They cannot tolerate data loss. Every architectural decision in this system prioritizes durability above all else. Availability is second. Latency is third.

Step 2: Back-of-the-Envelope Estimation#

Key insight from the math: Metadata is small (250 GB) but is accessed on every single request — every upload, download, list, and delete starts by looking up metadata. The data itself is enormous (petabytes) but each object is accessed infrequently. This asymmetry is the reason the architecture must separate metadata from data into two distinct services optimized for their different access patterns.

Why erasure coding uses 1.5x, not 3x: Traditional replication stores three full copies of every byte — a 3x overhead. Erasure coding (which we will deep dive into in Step 4) achieves the same or better durability with only ~1.5x overhead by storing computed "parity" fragments instead of full copies. At petabyte scale, this difference saves millions of dollars in storage hardware per year.

Step 3: High-Level Design#

The foundational principle: separate the metadata path from the data path. When a client uploads a file, the metadata (where the file lives, its size, checksum) goes to one service, and the actual bytes go to another. This separation is why object storage scales to exabytes — the metadata service handles billions of small, fast lookups while the data service handles petabytes of large, sequential reads and writes independently.

What each component does:

• API Gateway — Authenticates requests (signature-based auth like AWS SigV4), enforces rate limits per account, and routes to the correct internal service. Also terminates TLS and handles request validation (is the bucket name valid? is the object key within length limits?).
• Metadata Service — The brain of the system. For every object, it stores the mapping from (bucket_id, object_key) to the physical storage locations where the object's data fragments live. It handles LIST operations entirely on its own (no data service involved) and coordinates with the data service during uploads and downloads to locate data.
• Metadata DB — A distributed key-value store (DynamoDB, Cassandra, or a sharded PostgreSQL cluster) that stores one row per object version. The partition key is bucket_id + object_key, giving even distribution and fast point lookups. At 500 million objects and ~500 bytes per row, the total dataset is ~250 GB — comfortably handled by any distributed database.
• Data Service — Manages the actual reading and writing of file bytes to storage nodes. On upload, it splits the file into chunks, applies erasure coding, and distributes the fragments across storage nodes in different failure domains. On download, it reads the required fragments and reassembles the file.
• Storage Nodes — Commodity servers with large local disk arrays (HDDs for capacity, SSDs for hot data). Each node manages its local disk space, reports health metrics, and serves read/write requests from the data service. Nodes are organized into failure domains — different racks, power supplies, and network switches — so that a single hardware failure cannot destroy all fragments of an object.

API Design#

Why PUT and not POST for uploads? PUT is idempotent — uploading the same object to the same key twice produces the same result (the second upload overwrites the first). This matches the semantics of object storage: the key is the identity, and the operation is "place this content at this key." POST is used only for operations that create server-side state with a new identifier (like initiating a multipart upload, which generates a unique upload_id).

Metadata Schema#

Object Metadata Record:
  bucket_id       UUID          -- the bucket this object belongs to
  object_key      VARCHAR(1024) -- the full key path (e.g. "photos/2026/may/sunset.jpg")
  version_id      UUID          -- unique per version (for versioned buckets)
  size_bytes      BIGINT        -- total object size
  checksum_sha256 VARCHAR(64)   -- integrity check; verified on every read
  content_type    VARCHAR(128)  -- MIME type (e.g. "image/jpeg")
  created_at      TIMESTAMPTZ
  storage_class   VARCHAR(16)   -- STANDARD, INFREQUENT, ARCHIVE
  fragment_map    JSONB         -- ordered list of {node_id, disk_id, offset, length}
                                --   for each erasure-coded fragment
  is_delete_marker BOOLEAN      -- for versioned buckets: marks a logical delete

  Primary Key: (bucket_id, object_key, version_id)
  Partition Key: bucket_id + object_key
  Sort Key: version_id (latest version served by default)

The fragment_map is the critical field — it tells the data service exactly which storage nodes hold which fragments of this object. A typical 1 MB object stored with 6+3 erasure coding has 9 entries in the fragment map, each pointing to a different storage node in a different failure domain.

Upload and Download Flows#

Why data is written before metadata: The upload flow writes object bytes to storage nodes first, then writes the metadata record. If the process crashes after writing data but before writing metadata, the data fragments become orphans — unreferenced bytes on disk. This is harmless: the garbage collector (covered in Step 7) eventually reclaims them. The alternative — writing metadata first — is dangerous: the metadata would point to data that does not exist, causing download failures. Dangling data is safe; dangling metadata is broken.

Step 4: Deep Dive — Data Partitioning and Durability#

How do you store a file so that it survives disk failures, server failures, and even entire data center outages? This is the core durability problem, and there are two competing approaches.

Approach A: Triple Replication#

The simplest strategy: store three complete copies of every object on three different storage nodes in three different failure domains (different racks, different power supplies).

This is how the Google File System (GFS) originally worked. It is simple to understand, simple to implement, and fast to read (any replica can serve the full file). But it costs 3x the raw storage — every petabyte of data requires three petabytes of disk.

Approach B: Erasure Coding#

Erasure coding is a mathematical technique borrowed from satellite communications. Instead of storing full copies, you split the original data into k data fragments and compute m parity (redundancy) fragments, producing k + m total fragments. You can reconstruct the original data from any k of the k + m fragments — meaning up to m fragments can be lost (due to disk failures, node crashes, or entire rack outages) and you still recover everything.

Think of it like a jigsaw puzzle with extra pieces. If you have a 6-piece puzzle and you create 3 additional "backup" pieces calculated from the original 6, you now have 9 pieces total. Even if you lose any 3 of those 9 pieces, the remaining 6 contain enough information to reconstruct the full picture.

With a 6+3 scheme, the storage overhead is (6+3)/6 = 1.5x — half the cost of triple replication, with the ability to survive 3 simultaneous fragment losses.

Step 5: Deep Dive — Metadata Design#

The metadata service is the brain of the entire system. Every operation — upload, download, delete, list — starts with a metadata lookup. If the metadata service is slow, the entire system is slow. If it is down, the entire system is down. If it loses data, objects become permanently inaccessible even though the data still exists on storage nodes.

Why consistent hashing? With 500 million objects across potentially hundreds of metadata nodes, you need a way to determine which node stores the metadata for a given key without consulting a central directory. Consistent hashing maps each (bucket_id, object_key) to a position on a virtual ring, and the nearest metadata node clockwise on the ring owns that key. When a node is added or removed, only the keys adjacent to it on the ring are redistributed — roughly 1/N of all keys, rather than reshuffling everything. This makes scaling the metadata tier smooth and predictable.

LIST Operation: The Hidden Performance Challenge#

The LIST operation — "give me all objects in this bucket with prefix photos/2026/" — is fundamentally different from point lookups. A point lookup (GET /bucket/key) hits one partition. A LIST must scan across potentially all partitions because objects with the same prefix may hash to different nodes.

Production systems optimize LIST by maintaining a secondary index sorted by prefix within each bucket, so that prefix-filtered listing requires scanning only the relevant range rather than all keys. DynamoDB handles this naturally with a sort key; Cassandra achieves it with clustering columns.

Step 6: Deep Dive — The Upload Path and Multipart Upload#

The upload path must handle everything from a 1 KB config file to a 5 GB database backup, and it must guarantee that once the system acknowledges the upload, the data is durable — even if a server crashes one second later.

Small Object Upload (Single PUT)#

Write-ahead logging (WAL): Before the data service confirms fragment writes to the metadata service, it logs the operation to a write-ahead log — a sequential, append-only file on stable storage. If the data service crashes mid-write, it reads the WAL on recovery to determine which fragments were successfully written and which need to be retried or cleaned up. This is the same technique databases use to guarantee durability across crashes.

Large Object Upload (Multipart)#

For files larger than 100 MB, a single PUT is risky — a network hiccup 4 GB into a 5 GB upload means starting over from zero. Multipart upload solves this by splitting the work into independently uploadable parts.

Why multipart upload matters:

• Parallelism — Upload 10 parts simultaneously to different storage nodes. Multiple TCP connections overcome single-connection bottlenecks (TCP slow start, per-connection server-side rate limits) and can better utilize available bandwidth. If each storage node throttles individual connections, parallel parts to different nodes bypass that limit.
• Resilience — If part 7 of 10 fails, retry only part 7. Without multipart, a failure at 4.5 GB into a 5 GB upload means re-uploading the entire 5 GB.
• Resumability — Parts already uploaded survive client crashes. The client can resume by querying which parts are already complete and uploading only the missing ones.

Step 7: Deep Dive — Consistency and Garbage Collection#

Object storage must answer a deceptively tricky question: when a client uploads a file and immediately reads it back, do they see the new file or the old one (or nothing at all)? And when a client deletes a file, when is the storage actually freed?

Consistency Model#

Why the difference? A new object PUT creates a new metadata record. The system returns 200 OK only after the metadata is durably written to a quorum of metadata nodes. Any subsequent read will find this record — it either exists or it does not.

An overwrite updates an existing record. The old version's metadata may still be cached or replicated on some nodes. Until all replicas converge, different reads may see different versions. The convergence window is typically sub-second, but the system does not guarantee it.

Note on S3's evolution: Amazon S3 originally had eventual consistency for all operations, including new object PUTs. In December 2020, S3 upgraded to strong read-after-write consistency for all operations at no additional cost — a major engineering achievement that required rearchitecting the metadata tier. Our design follows the simpler approach of strong consistency for new PUTs and eventual consistency for overwrites, which is easier to implement and sufficient for most use cases.

Garbage Collection#

Garbage collection in a distributed storage system is more complex than memory garbage collection in a programming language, but the core idea is the same: find data that is no longer referenced and reclaim the space.

The 72-hour grace period is critical. Without it, the garbage collector could delete fragments that belong to an upload that is still in progress. Imagine: a client starts a large multipart upload, the data service writes fragments to disk, but the metadata service has not yet recorded them. If the garbage collector runs during this window, it sees unreferenced fragments and deletes them — destroying an active upload. The grace period ensures that any in-flight operation has ample time to complete before its fragments become eligible for deletion.

Step 8: Trade-offs & Production Reality#

Every design decision involves a trade-off. Here is a consolidated view of the choices made in this design and when you would choose differently.

What This Design Intentionally Excludes#

Production object storage systems include additional layers that are out of scope for this case study:

• Cross-region replication — automatically copying objects to a geographically distant region for disaster recovery. Adds a replication pipeline, conflict resolution for concurrent writes to the same key in different regions, and bandwidth cost management.
• Storage tiering and lifecycle management — automatically moving objects to cheaper storage classes (Infrequent Access, Glacier/Archive) based on access patterns. Requires access-frequency tracking, a policy engine, and a background data migration system.
• Server-side encryption — encrypting objects at rest with customer-managed keys (SSE-KMS) or server-managed keys (SSE-S3). Adds key management infrastructure and per-request encryption/decryption overhead.
• Event notifications — triggering Lambda functions or SQS messages when objects are created or deleted. Requires an event bus integrated with the metadata service.
• Access control policies — bucket policies, IAM roles, and access control lists (ACLs) that govern who can read/write which objects. Adds a policy evaluation engine on the critical request path.

Each of these adds significant systems without fundamentally changing the core metadata-data separation architecture described here.

Summary#

Distributed file storage is one of the most foundational systems in cloud computing — nearly every other cloud service depends on it. The design process surfaces decisions that reappear across all distributed systems: how to achieve durability without prohibitive cost (erasure coding), how to separate concerns that scale differently (metadata vs. data), how to handle partial failures gracefully (write-ahead logging, garbage collection), and how to choose the right consistency guarantee for each operation. Master these patterns here, and you will recognize them in every distributed system you encounter.

Sources:

• Amazon S3 Strong Consistency — AWS Blog (2020)
• The Google File System — Ghemawat, Gobioff, Leung (2003)
• Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency — Calder et al. (2011)
• Erasure Coding in Windows Azure Storage — Huang et al. (2012)
• Building and Operating a Pretty Big Storage System (S3) — Andy Warfield, USENIX ATC 2023 Keynote
• Design a Distributed Object Storage (S3) — AlgoMaster