Object Storage Internals (S3-Style)

Object storage systems like Amazon S3, MinIO, and Ceph's RADOS Gateway has become the dominant storage abstraction for unstructured data at scale.
They trade the hierarchical namespace and POSIX semantics of traditional filesystems for a flat key-value model optimized for durability, availability, and horizontal scalability.
Understanding how these systems work internally is essential for anyone building on top of them or designing similar infrastructure.

The Object Storage Data Model

An object store presents a deceptively simple API: PUT(key, blob), GET(key), DELETE(key), and LIST(prefix).
Objects live in buckets (namespaces), and each object is identified by a string key.
There are no directories, no renames, no appends, and no partial updates.
This constrained interface is what makes the system scalable.

Each stored object consists of three components:

1. Data: The opaque byte payload, potentially many gigabytes.
2. Metadata: System-defined (content type, creation time, ETag) and user-defined key-value pairs.
3. Object ID / Key: The unique identifier within a bucket namespace.

The absence of rename and in-place mutation is not an omission.
It is a fundamental design choice that eliminates the need for distributed locking on the data path and allows aggressive replication and caching strategies.

Architecture Overview

A production object store consists of several cooperating subsystems.

Metadata Tier

The metadata tier maps (bucket, key) tuples to the physical locations of object data.
This is typically backed by a distributed, strongly consistent key-value store or a partitioned relational database.
Amazon's internal metadata systems for S3 are proprietary and not publicly documented in detail; the 2007 Dynamo paper describes a separate highly available key-value store built on consistent hashing and NRW quorum replication that informed the broader industry, but Dynamo itself used eventual consistency and was not specifically designed as S3's metadata layer.

The metadata record for an object includes:

• Bucket and key name
• Object version ID (if versioning is enabled)
• Size, ETag (typically the MD5 or a multipart-specific hash)
• Storage class
• A manifest or pointer to one or more data chunks on the storage tier
• ACL and encryption metadata

Because LIST operations must return lexicographically sorted results, the metadata store must support efficient range scans over the key space.
This is why many implementations use a B-tree-based or LSM-tree-based store partitioned by a hash of the bucket name, with keys sorted within each partition.

Data Tier (Placement and Storage)

Object data is split into chunks (sometimes called "parts" or "slabs") and distributed across a cluster of storage nodes.
Two replication strategies dominate:

Full replication. Each chunk is written to N independent storage nodes (typically N=3) across distinct failure domains (racks, availability zones).
This is simple and gives excellent read throughput, at the cost of 3x storage overhead.

Erasure coding. Chunks are encoded using a scheme like Reed-Solomon.
A common configuration is RS(8,3), where 8 data fragments and 3 parity fragments are distributed across 11 nodes.
Any 8 of the 11 fragments are sufficient to reconstruct the original chunk.
This reduces raw storage overhead to 11/8 = 1.375x (not counting metadata, and index overhead) while tolerating up to 3 simultaneous node failures.
Most production systems (S3 included) use erasure coding for the standard storage class.

Placement and Routing

A consistent hashing ring, or a variant like jump consistent hashing or CRUSH (Ceph's algorithm), determines which storage nodes hold which chunks.
The placement function takes a chunk identifier and returns a set of target nodes, ensuring even distribution and minimal data movement when nodes are added or removed.

Walkthrough

The following walkthrough describes a simplified PUT operation for a large object using multipart upload, the standard mechanism for objects larger than a few hundred megabytes.

Multipart PUT Sequence

1. Client → API Gateway: InitiateMultipartUpload(bucket, key)
   Gateway generates upload_id, stores pending upload record in metadata tier.
   Returns upload_id to client.

2. For each part p (typically 8-64 MB):
   a. Client → API Gateway: UploadPart(bucket, key, upload_id, part_number, data)
   b. Gateway computes chunk_id = hash(upload_id, part_number)
   c. Gateway runs placement(chunk_id) → [node_1, node_2, ..., node_n]
      (where n = data_fragments + parity_fragments for erasure coding;
       e.g., n=11 for RS(8,3))
   d. Gateway erasure-encodes the part into n fragments.
   e. Gateway writes fragment_i to node_i in parallel.
   f. Each node writes fragment to local storage (often an append-only log
      or a content-addressed blob store on a local filesystem like XFS).
   g. Gateway waits for acknowledgment from all n nodes (or a high-watermark
      write quorum sufficient to guarantee durability and future
      reconstructability). Unlike reads — where hedged requests can use any
      data_fragment_count responses — writes must ensure enough fragments are
      durably stored before reporting success. Accepting fewer acknowledgments
      than the reconstruction threshold would risk data loss if those nodes
      fail before repair.
   h. Gateway stores part metadata (part_number, size, ETag, fragment locations)
      in metadata tier under the upload_id.
   i. Returns part ETag to client.

3. Client → API Gateway: CompleteMultipartUpload(bucket, key, upload_id, part_list)
   a. Gateway validates all parts are present and ETags match.
   b. Gateway atomically writes the final object metadata record:
      {bucket, key, version_id, manifest: [part_1_location, ..., part_n_location]}
   c. Gateway deletes the pending upload record.
   d. Returns success (HTTP 200) with the final object ETag.

The atomicity of step 3b is critical.
Until the metadata record is committed, the object does not exist from a reader's perspective.
This provides the write-then-reveal consistency model.
S3 achieved strong read-after-write consistency in December 2020, meaning a successful CompleteMultipartUpload guarantees that any subsequent GET will return the new object.
This is implemented by ensuring the metadata tier provides linearizable reads.

Consistency and Durability

Durability

S3 advertises 99.999999999% (eleven nines) in annual durability.
This is achieved through the combination of erasure coding across availability zones, continuous background integrity checking (bit rot detection via checksums), and automated repair of degraded fragments.

The durability calculation for an RS(8,3) scheme across independent failure domains follows from the probability that 4 or more fragments are simultaneously lost before repair completes.
With typical annual disk failure rates of 1-2% and repair times under 24 hours, the math works out to roughly 10^-11 annual loss probability per object.

Consistency

Modern object stores provide strong consistency for individual object operations.
This means:

• A GET after a successful PUT always returns the new data.
• A GET after a successful DELETE always returns 404.
• LIST reflects all completed writes, though at planetary scale, LIST consistency can have edge cases and is generally harder to guarantee than single-object read/write consistency.

Achieving strong per-object consistency requires the metadata tier to support linearizable (or at minimum sequentially consistent) reads and writes.
Systems like S3 are believed to accomplish this by fronting their metadata stores with a synchronous cache invalidation layer or by using a consensus protocol (Paxos, Raft) at the metadata layer — the precise internal mechanism is proprietary, but the observable guarantee is linearizable object operations.

Garbage Collection and Compaction

Deleted and overwritten objects leave behind orphaned data fragments.
A background garbage collector (GC) reconciles the data tier against the metadata tier:

1. The GC scans storage nodes for chunks not referenced by any live object metadata record.
2. Orphaned chunks are marked for deletion after a grace period (to avoid races with in-flight writes).
3. Marked chunks are physically removed, reclaiming disk space.

This is conceptually similar to a mark-and-sweep garbage collector.
The grace period is essential because a CompleteMultipartUpload might be in flight while the GC is scanning; deleting unreferenced chunks too eagerly would corrupt uploads in progress.

Storage Tiering and Lifecycle

Production systems offer multiple storage classes (Standard, Infrequent Access, Glacier/Archive) with different cost, latency, and durability profiles.
Lifecycle policies automatically transition objects between tiers based on age or access patterns.
Internally, transitioning an object to a colder tier may involve:

• Re-encoding data with a different erasure coding configuration optimized for the target media and access pattern. For example, using more parity fragments relative to data fragments can maintain durability guarantees on slower, less reliable media at the cost of higher reconstruction latency.
• Moving data to slower, denser media (SMR drives, tape libraries).
• Updating only the metadata record to point to the new physical locations. The key and bucket remain unchanged.

Performance Considerations

Several design decisions shape the performance characteristics of object stores:

Request routing. Partitioning the key space across API frontends by bucket, or key prefix hash, enables horizontal scaling of throughput.
Hot partitions (millions of requests per second to a single prefix) require automatic splitting.

Small object overhead. Each object, regardless of size, incurs metadata tier overhead.
Storing billions of 1 KB objects is significantly more expensive per byte than storing millions of 1 GB objects.
Some systems (like Haystack at Meta, formerly Facebook) pack small objects into larger physical volumes to amortize metadata costs.

Multipart parallelism. Large objects benefit from parallel upload of parts.
The system's throughput for a single large object scales linearly with the number of concurrent part uploads, up to the bandwidth limits of the client or the storage cluster.

Read amplification with erasure coding. A read requires fetching at least data_fragment_count fragments from that many different nodes.
Tail latency can be mitigated by issuing hedged requests to all data_fragments + parity_fragments nodes and using the first data_fragment_count responses, at the cost of additional network traffic.

Key Points

• Object stores sacrifice POSIX semantics (rename, append, partial update) to eliminate distributed locking and enable horizontal scalability.
• The metadata tier, typically a partitioned, strongly consistent key-value store, is the critical coordination point and the most common bottleneck.
• Erasure coding (commonly Reed-Solomon) reduces raw storage overhead from 3x (triple replication) to roughly 1.375x for RS(8,3), while maintaining high durability across failure domains.
• Multipart upload provides atomicity for large objects: data fragments are written first, and the object becomes visible only when the final metadata record is committed.
• Strong read-after-write consistency requires linearizable operations at the metadata layer, typically implemented via consensus protocols or synchronous cache invalidation.
• Write durability requires that a sufficient number of fragments (at minimum the reconstruction threshold) are acknowledged before reporting success — this is distinct from the hedged-read optimization used to reduce read tail latency.
• Background garbage collection reconciles orphaned data fragments against the metadata tier, using grace periods to avoid races with in-flight writes.
• Small objects are disproportionately expensive due to per-object metadata overhead, motivating techniques like object packing and volume aggregation.

References

DeCandia, G., Hastorun, D., Jampani, M., et al. "Dynamo: Amazon's Highly Available Key-Value Store." Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP), 2007.

Weil, S. A., Brandt, S. A., Miller, E. L., et al. "Ceph: A Scalable, High-Performance Distributed File System." Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006.

Beaver, D., Kumar, S., Li, H. C., Sobel, J., Vajgel, P. "Finding a Needle in Haystack: Facebook's Photo Storage." Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2010.

Huang, C., Simitci, H., Xu, Y., et al. "Erasure Coding in Windows Azure Storage." Proceedings of the USENIX Annual Technical Conference (ATC), 2012.

Lamport, L. "Paxos Made Simple." ACM SIGACT News, 32(4):18-25, 2001.