Object Storage System Design Template (S3-Like, Erasure Coding)

System Design: [Object storage service name]

Reference design for an S3-compatible object (blob) store: a strongly consistent metadata service, data placement across failure domains, packing of small objects into large volumes, replication for new data and erasure coding for data that has cooled, durability arithmetic, repair and deletion. It draws on the published Haystack (OSDI 2010) and f4 (OSDI 2014) papers and on the public Amazon S3 documentation for API behaviour. It follows the structure of the System Design Document template, adds a 45-minute interview path, access-pattern and failure-mode tables and a cited "How real systems do it" box, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; values marked Example are assumptions, not benchmarks.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Product teams store user uploads, backups and analytics files on a network file system that holds 3 copies of everything. It costs three times the logical bytes, listing a directory with millions of files takes minutes, and two disk-shelf failures in one rack last year made 4 TB unavailable for a day. The company needs an internal object store with an S3-compatible API, lower storage overhead and a stated durability target.]

1.2 Proposed solution

[Example: A regional service across three availability zones (AZs). Stateless front ends speak the S3 REST API. A metadata service, sharded by bucket and key range on consensus-replicated groups, maps each object version to its data location and gives strong read-after-write consistency. New objects are written as three replicas, one per AZ, into large append-only volumes; small objects are packed many to a volume so a read costs one disk seek. After 30 days without change, volumes are converted to a Reed-Solomon RS(9,6) code with five fragments per AZ, which survives the loss of a whole AZ plus one more disk at 1.67 times the logical size. Background scrubbers verify checksums and a repair service rebuilds lost fragments.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

Use this order when the document serves an interview or a short design review. The written sections below are the long form of each step.

Start the default deep dive with the naive answer, three full copies, and work out its cost (150 PB raw for 50 PB of data). Then introduce a Reed-Solomon code, show why the fragments must be spread so one AZ holds no more fragments than the code can lose, and only then compute durability.

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

Name these explicitly so reviewers and interviewers do not pull the design toward them.

• [Example: a POSIX file system interface or in-place partial updates of objects]
• [Example: content delivery to end users (a CDN sits in front)]
• [Example: tabular or vector bucket types and query in place]
• [Example: cross-region strong consistency (replication is asynchronous)]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Bandwidth

Three replicas on write mean 3.75 GB/s of disk writes at peak, and the later conversion to RS(9,6) writes another $1.25 \times 15/9 \approx 2.08$ GB/s on average when it catches up with peak intake. At the average PUT rate the gross intake is about 1.3 PB a month before deletes. Consequence: reads, not writes, size the network; the front end tier is sized on 200 Gbit/s egress and a cache absorbs the hottest objects.

3.3 Raw capacity

Consequence: erasure coding saves about 63 PB of raw disk against three replicas, which pays for the extra CPU and repair traffic many times over.

3.4 Metadata

At 2 TB per metadata shard that is 50 shards, each a three-member consensus group. Every GET needs one metadata lookup (100 000/s at peak) unless the front end caches the location of immutable versions. Consequence: metadata does not fit in memory on one machine and must be range-partitioned from day one.

3.5 Disk operations

• Average GET load per drive: $100\,000 / 5\,417 \approx 18$ reads/s, well below the roughly 100 random reads a second an HDD sustains, but only if a GET costs one seek (7.2).
• Objects per drive: $2 \times 10^{11} / 5\,417 \approx 3.7 \times 10^{7}$. With a 32-byte in-memory index entry per object that is 1.2 GB of index per drive, about 28 GB per 24-drive server. Consequence: the storage-node index fits in memory, so no disk read is spent on finding the object.

3.6 Summary

4. API design

4.1 Interfaces

For reference, the public Amazon S3 documentation (checked October 2026) lists multipart parts of 5 MiB to 5 GiB, at most 10 000 parts and a maximum object size of 48.8 TiB; choose your own limits and publish them, and check the provider page if you need exact compatibility.

4.2 Multipart flow

Parts become visible only when the completion commits the version in one metadata transaction, so readers never see half an object. Incomplete uploads expire by lifecycle rule (Example: 7 days) and their parts are garbage-collected.

4.3 Error example

A conditional create that loses the race gets 412 and must not retry the same create; the client reads the existing version instead.

HTTP/1.1 412 Precondition Failed
Content-Type: application/problem+json

{"type": "https://storage.example.com/problems/precondition-failed", "title": "Object already exists", "status": 412, "detail": "If-None-Match: * was set and the key reports/2026/q3.parquet already has a current version.", "instance": "/analytics/reports/2026/q3.parquet"}

5. Data model

5.1 Entities

A volume is an append-only container (Example: 100 GB). While open it is written as three replicas; once sealed and cold it is encoded as nine data and six parity fragments. Objects point at volumes, not disks, so moving or re-encoding a volume never touches object metadata.

5.2 Storage choices

5.3 Access patterns

Sequential key names (timestamps as prefixes) concentrate writes on the last range. The metadata service splits a range when its write rate stays above a threshold, and documentation tells clients that prefixes spread load.

6. High-level design

7. Detailed design

The deep dives in this section, each with options, choice and reason:

7.1 Metadata service and consistency

• Keys are ordered by (bucket, key) and split into ranges. Each range is a consensus group of three members in three AZs; a write commits when two members accept it.
• A PUT writes the data first, then commits the version in metadata. Only the commit makes the object visible, so a crash between the two leaves orphan data for garbage collection, never a visible broken object.
• Reads of the latest version go to the range leader (or to a follower with a read lease), so a GET after a successful PUT always sees it. LIST scans the same ordered ranges, so it also sees new keys at once.
• Two concurrent PUTs to the same key both succeed; the later commit becomes the latest version. If-Match and If-None-Match let clients avoid lost updates. There are no transactions across keys.
• Bucket configuration (policies, lifecycle, versioning state) is cached in front ends and is eventually consistent for a short interval; document it.

7.2 Packing small objects into volumes

A file per object costs inodes, directory lookups and extra seeks. Instead, each storage node appends objects ("needles") to a large volume file and keeps an in-memory map from object ID to offset and length. A GET is then one metadata lookup (often cached) plus one disk read. Each needle carries a header with its ID, size and checksum, so the in-memory index can be rebuilt by scanning the volume, and a periodic index checkpoint keeps restarts fast. Objects larger than Example: 16 MiB skip packing: they are split into 8 MiB extents and erasure-coded directly, because a large object gains nothing from replication-first writes.

7.3 Redundancy and durability

Placement. For RS(9,6) the 15 fragments of a volume go to 15 different servers in 15 different racks, five per AZ. Losing an AZ removes five fragments; nine of the remaining ten are enough to read, so data stays available and one more failure is still tolerated.

Durability model. With independent drive failures, the probability that one drive holding a fragment fails during a repair window of $T$ hours is

A stripe of $n$ fragments that tolerates $n-k$ losses is lost when more than $n-k$ fragments fail within the same window:

Read this table with care. The model assumes independent failures and a fixed repair window; real losses come from correlated events the model ignores: a power or cooling failure in a rack, a bad firmware batch, a bug in the encoder, an operator deleting the wrong volume. The design therefore spreads fragments across racks and AZs, mixes drive batches, verifies every encoded volume by decoding it before the replicas are dropped, and keeps versioning and retention locks as the defence against logical deletion. The extra margin of RS(9,6) also matters while an AZ is down: with five fragments already gone, a remaining stripe is lost only if two of the other ten fail in a window, about $1.35 \times 10^{-7}$ per 24-hour window, which is why AZ outages trigger priority repair.

Repair speed. Rebuilding a 20 TB drive (16 TB used) onto one spare at 150 MB/s takes about 29.6 hours; spreading the rebuild across 100 drives at 50 MB/s each takes about 0.9 hours. Distributed repair is what keeps $T$ small. Rebuilding one RS(9,6) fragment reads nine fragments, so repair traffic is nine times the lost bytes and must be throttled against client traffic.

7.4 Write and read paths

The front end acknowledges only after all three replicas have synced and the metadata commit succeeded. If one replica fails, the front end writes the object to a different open volume rather than accepting two copies. A GET reads one replica (nearest AZ first) or, for coded volumes, the one data fragment that holds the object; it falls back to a decode from any nine fragments when that fragment is missing, and verifies the checksum before returning bytes.

7.5 Scrubbing and silent corruption

Every fragment is read and checksummed at least once every Example: 30 days. A mismatch marks the fragment bad and queues a repair from the other fragments. Front ends verify checksums on every read as well, so a corrupt fragment is never served even before the scrubber finds it.

7.6 Deletion, versioning and space reclamation

• A DELETE in a versioned bucket adds a delete marker; older versions stay until lifecycle rules expire them. Retention locks block deletion and overwrite until a date, including for administrators in compliance mode.
• In replicated volumes, deleted needles are marked in the index and the volume is compacted by copying live needles to a new volume.
• In coded volumes, each object is encrypted with its own data key stored in metadata. Deleting the key makes the bytes unreadable at once (crypto-shredding). Space is reclaimed later by rewriting volumes whose live share has fallen below Example: 60%.

7.7 How real systems do it

How real systems do it (paraphrased, not copied). The Haystack paper (Beaver, Kumar, Li, Sobel and Vajgel, OSDI 2010) describes the photo store of a large social network that, at the time, served over a million images a second at peak. The authors found that a network file system spent disk operations on file metadata, so Haystack packs photos into large volume files (about 100 GB each) and keeps a compact in-memory map from photo to offset, using on average about 10 bytes of memory per photo, so a read needs at most one disk operation. The f4 paper (Muralidhar and co-authors, OSDI 2014) adds a warm tier: once data is older and read less, volumes move from Haystack's replicated layout (effective replication 3.6, three copies on RAID-6) to Reed-Solomon(10,4) inside a cell, with blocks of a stripe on different racks, and an XOR of two volumes in a third region for disaster tolerance, which brings the effective replication factor to 2.1. f4 handles deletes by removing a per-object encryption key. This design keeps the same ideas: packed volumes (7.2), hot then cold redundancy (7.3) and key deletion (7.6). Read the originals in 12.3.

8. Scalability and performance

Latency budget for a GET of a 200 KB object (target p99 100 ms to first byte):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Teams copy data in with checksums verified on both sides and keep the old file system read-only for 60 days. The encoder starts with verification only (encode, decode, compare, keep replicas) for 30 days before any replica is dropped. Rollback of the encoder means keeping replicas, which costs capacity but no data.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on common industry practice for object storage, the published Haystack (OSDI 2010) and f4 (OSDI 2014) papers and the public Amazon S3 documentation cited in 12.3, used only as a behaviour reference. The papers are paraphrased in 7.7 only; no text, figures or code were copied. The durability figures come from the simple independent-failure model in 7.3 and are illustrative, not a guarantee; all capacity numbers are examples computed from the stated assumptions. Original text written for this collection. Template licence: MIT.