S3-like Object Storage

Design object storage similar to Amazon S3. S3 launched 2006; 100+ trillion objects by 2021.

Storage system 101 #

1. Block: raw blocks as volumes, physically or network-attached (FC, iSCSI). Single-server ownership
2. File: built on block storage, hierarchical directories, shared via SMB/NFS
3. Object: flat structure, RESTful API, "cold" data, archival/backup. Sacrifices performance for durability + scale + low cost

Terminology:

1. Bucket: logical container, globally unique name
2. Object: payload + metadata (name-value pairs)
3. Versioning: multiple variants of an object in a bucket
4. URI: uniquely identifies resources
5. SLA: e.g. S3 Standard-IA: 99.999999999% durability, 99.9% availability

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in requirements and scale.

Requirements:

1. Bucket creation, object upload/download, versioning, listing objects in a bucket
2. Both massive objects (few GBs+) and many small objects (tens of KBs)
3. 100 PB data per year
4. Durability: 6 nines (99.9999%), availability: 4 nines (99.99%)
5. Storage efficiency (reduce costs while maintaining reliability/performance)

Back-of-the-envelope estimation:

1. Object distribution: 20% small (<1MB), 60% medium (1-64MB), 20% large (>64MB)
2. HDD: 100-150 IOPS (7200 rpm SATA)
3. Using median sizes (0.5MB, 32MB, 200MB), 40% storage usage:
   • 100 PB → 10¹¹ MB
   • ~0.68 billion objects
   • Metadata ~1KB each → 0.68 TB metadata

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on the metadata/data store split.

Key properties:

1. Object immutability: no incremental changes; replace with a new version
2. Key-value store: URI = key, object data = value
3. Write once, read many: 95% of requests are reads (LinkedIn)
4. Support both small and large objects

Analogy: like the UNIX file system: inode (metadata) separate from file data (disk blocks). Object storage: metadata store (object metadata) + data store (object data), connected via object UUID over the network.

Figure 2: Unix file system and object store

Figure 3: Bucket & object

High-level design #

Figure 4: High-level design

1. Load balancer: distributes RESTful API requests
2. API service: stateless, orchestrates IAM + metadata + data store calls
3. IAM: authentication + authorization
4. Data store: stores/retrieves object data by UUID
5. Metadata store: stores object metadata

Uploading an object #

Figure 5: Uploading an object

1. Client: PUT to create bucket → API service
2. API → IAM: verify WRITE permission
3. API → metadata store: create bucket entry
4. Client: PUT to create object script.txt
5. API → IAM: verify WRITE on bucket
6. API → data store: persist payload → returns UUID
7. API → metadata store: create entry (object_name, object_id/UUID, bucket_id)

Sample upload request:

PUT /bucket-to-share/script.txt HTTP/1.1
Host: foo.s3example.org
Authorization: authorization string
Content-Type: text/plain
Content-Length: 4567
x-amz-meta-author: Alex
[4567 bytes of object data]

Downloading an object #

Figure 6: Downloading an object

1. Client: GET /bucket-to-share/script.txt
2. API → IAM: verify READ access
3. API → metadata store: fetch UUID by object name
4. API → data store: fetch data by UUID
5. Return object data to client

Logical hierarchy via naming: bucket-to-share/script.txt implies a folder structure (no actual directories).

Step 3 of 4: Design deep dive #

Goal: data store internals, durability, metadata, versioning, large uploads, GC.

Data store #

Figure 7: Upload and download an object

Data store components:

Figure 8: Data store components

1. Data routing service: stateless RESTful/gRPC service. Queries the placement service for the best data node; reads/writes data to nodes
2. Placement service: determines which data nodes (primary + replicas) store an object. Maintains a virtual cluster map (physical topology). Ensures replicas are physically separated for durability. Monitors nodes via heartbeats (15s grace period). Critical → 5-7 nodes with Paxos/Raft consensus (tolerates minority failure)

Figure 9: Virtual cluster map

3. Data node: stores actual object data. Replicates to multiple nodes (replication group). Daemon sends heartbeats (how many drives, how much data). On first heartbeat, placement assigns: unique ID, virtual cluster map, replication targets

Data persistence flow:

Figure 10: Data persistence flow

1. API → data store: forward object data
2. Data routing: generate UUID, query placement → get primary data node (via consistent hashing)
3. Send data to primary + UUID
4. Primary saves locally → replicates to 2 secondary nodes → responds only after all replicas succeed
5. Return UUID to API service

Consistency vs latency trade-off:

Figure 11: Consistency vs latency

1. All 3 nodes: best consistency, highest latency
2. Primary + 1 secondary: medium consistency/latency (eventual)
3. Primary only: worst consistency, lowest latency (eventual)

How data is organized:

Storing each object as a separate file fails at scale:

1. Wastes disk blocks (4KB block for a tiny file)
2. Exhausts inode capacity
3. OS handles millions of inodes poorly

Solution: merge small objects into larger files (WAL-like). Append to a read-write file. At capacity (~few GBs) → mark read-only, create a new read-write file. Serialize writes to the read-write file. For multi-core servers: a dedicated read-write file per core.

Figure 12: Store multiple small objects in one big file

Object lookup:

To locate an object by UUID: need data file name, start offset, object size.

Database choice: read-heavy (write once, read many). RocksDB (SSTable-based, fast writes) vs Relational (B+ tree, fast reads). Relational wins (better read perf). Deploy SQLite per data node (local, file-based, isolated per node).

Tables 3-4: Object_mapping table

Updated persistence flow:

Figure 13: Updated data persistence flow

1. API sends object 4
2. Data node appends to /data/c
3. Insert record into object_mapping table
4. Return UUID

Durability #

Hardware failure & failure domains:

1. Annual disk failure rate: ~0.81%. 3 copies → 1-(0.0081³) ≈ 99.9999% reliability
2. Failure domains: node-level (server components), rack-level (shared switches/power), AZ-level (separate infrastructure)
3. Replicate data across AZs for extreme-case resilience

Figure 14: Multi-datacenter replication

Erasure coding:

Alternative to replication. (4+2) example: data split into 4 equal chunks (d1-d4), 2 parities (p1, p2) computed mathematically. Lose d3, d4 → reconstruct from d1, d2, p1, p2.

Figure 15: Erasure coding

(8+4): 8 data chunks + 4 parities across 12 failure domains. Can lose up to 4 nodes and reconstruct.

Figure 16: (8+4) erasure coding

Storage overhead: replication 3× → 200%. Erasure coding (8+4) → 50%.

Figure 17: Extra space comparison

Durability from 0.81% AFR: erasure coding → 11 nines.

Replication: latency-sensitive apps. Erasure coding: cost efficiency, archival. This design focuses on replication.

Correctness verification (checksums):

In-memory data corruption is common at scale. Append a checksum (MD5) to each object + file-level checksum when marked read-only.

Figures 18-20: Checksum generation, comparison, data node layout

Read flow: fetch data + checksum → compute → mismatched? → try other failure domains → reconstruct from 8 valid pieces.

Metadata data model #

Schema:

Figure 21: Database tables

Two tables: bucket (small, ~10GB for 1M users × 10 buckets × 1KB) and object.

1. Scale bucket table: a single server fits. Spread reads via replicas
2. Scale object table: shard by hash(bucket_name, object_name): most operations are URI-based

Three queries supported:

1. Find object ID by name
2. Insert/delete object by name
3. List objects in a bucket sharing a prefix

Listing objects in a bucket #

Flat structure, organized by prefixes. Path: s3://mybucket/abc/d/e/f/file.txt → bucket: mybucket, object: abc/d/e/f/file.txt, prefix: abc/d/e/f/.

Three uses:

1. aws s3 list-buckets: list all user's buckets
2. aws s3 ls s3://mybucket/abc/: list at the same prefix level (rolls up deeper prefixes)
3. aws s3 ls s3://mybucket/abc/ --recursive: all objects sharing a prefix

Single DB: SELECT * FROM object WHERE bucket_id = "123" AND object_name LIKE 'abc/%'

Sharded DB (distributed): query all shards → aggregate. Paging is complex: each shard returns different counts, offsets vary per shard, the cursor must track all offsets. Solution: denormalize listing data into a separate table sharded by bucket_id → isolates listing to a single DB. Acceptable trade-off (listing performance is rarely a priority).

Object versioning #

Figure 22: Object versioning

Upload flow for a versioned object: same as normal, but the metadata store inserts a new row (not overwrite) with the same bucket_id + object_name, new object_id (UUID) + object_version (TIMEUUID). Current version = largest TIMEUUID.

Figure 23: Versioned metadata

Deletion: all versions remain; insert a delete marker as a new version. GET on a delete marker → 404.

Figure 24: Delete with delete marker

Optimizing uploads of large files: Multipart upload #

Figure 25: Multipart upload

1. Initiate multipart upload → get uploadID
2. Split the file into parts (e.g. 1.6GB → 8 × 200MB). Upload each part with uploadID
3. Each part returns an ETag (MD5 checksum)
4. Complete multipart upload: send uploadID + part numbers + ETags
5. Data store reassembles the object (may take minutes for large files)

Old parts after reassembly → garbage collected.

Garbage collection #

Reclaims space from: lazy deletion (marked deleted), orphan data (half-uploaded/abandoned multipart), corrupted data (checksum failures).

Compaction: copy non-deleted objects from read-only files to a new file. Skip objects with delete_flag = true. Update the object_mapping table (file_name, start_offset). Wrap updates in a transaction.

Figure 26: Compaction

Wait until many read-only files accumulate to compact → avoid creating many small files.

Step 4 of 4: Wrap up #

What we designed:

1. Storage taxonomy → high-level design (data store + metadata store separation)
2. Data persistence (WAL-like merging, SQLite per node)
3. Durability (replication vs erasure coding, checksums)
4. Metadata sharding (hash of bucket+object name)
5. Listing (denormalized table)
6. Versioning (TIMEUUID + delete markers)
7. Multipart upload
8. Garbage collection (compaction)