How to design S3 object storage
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- The write path and durability
- Storing billions of small objects
- Replication or erasure coding
- Metadata sharding and listing
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
An object store keeps blobs of any size under a bucket and a key, hands back a version id on each write, and lists keys by prefix. At 100 PB of new data a year, with disks dying at 0.81% a year, the answer turns on two separations: metadata kept apart from the bytes so each side scales on its own, and the bytes copied to several failure domains before the client hears success, with erasure coding added later so that durability stays affordable.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
How much data arrives, and how big are the objects? | The volume decides how many data nodes you run and whether cost is a design goal; the size mix decides whether small objects need a special layout on disk. | About 100 PB of new data a year. Roughly 20% of objects are under 1 MB, 60% are 1 to 64 MB and 20% are over 64 MB, which works out to about 0.68 billion objects stored once the disks are 40% full. |
What durability and availability do we promise? | Durability sets how many copies or parity pieces each object needs and how fast a lost disk must be rebuilt; availability sets how much downtime a failover may cost. | 6 nines of durability (99.9999%) and 4 nines of availability (99.99%). Disks fail at about 0.81% a year, so losing disks is routine and losing bytes is not allowed. |
After a PUT succeeds, must a GET return the new object right away? | It decides when the success reply goes back: after the bytes are safe on all the copies, or after the first copy, with the rest caught up in the background. | Yes. A reader who asks after the success reply sees the new version, so the reply is sent after the copies are written and the metadata row is committed. |
Do we keep every old version of an object, and can a GET ask for one? | Versioning turns each write into a new row rather than an overwrite, and it changes what a delete means. | Yes. Each write gets a version id, a GET without one returns the latest, and a delete adds a marker rather than erasing older versions. |
How do people list objects: by prefix, in key order, in pages? | Listing is the one query that does not look up a single key, so it decides how the metadata rows may be sharded. | By prefix within one bucket, in key order, a page at a time with a cursor for the next page. A bucket may hold billions of keys. |
How large can one object be, and must an upload survive a dropped connection? | A multi-gigabyte upload over one request fails on any hiccup; parts uploaded independently can be retried one at a time. | Very large, so a multipart flow is in scope: start an upload, send parts in any order, then complete it. |
Is this one region, and how much does storage cost matter? | Cross-region replication is a separate design, and a cost target is what pushes the answer from plain copies toward erasure coding. | One region; cross-region copies are out of scope. Cost matters: be ready to cut the storage bill without giving up durability. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
100 PB of new data a year | Capacity grows by adding data nodes, so a routing layer and a placement service have to decide where each object lands, and nothing else may need to know. Metadata has to stay small per object, about 1 KB, so the whole index stays near 0.68 TB and lives apart from the bytes. |
6 nines of durability (99.9999%) | An object sits on several disks in separate failure domains before the client is told it worked. Each copy carries a checksum, a scrubber reads data nobody asked for, and a lost disk is rebuilt from the other copies or pieces soon after it dies. |
4 nines of availability (99.99%) | About 52 minutes of downtime a year, so failover is automatic. The placement service runs as a consensus group that keeps working with a minority of its machines down, and the API and routing tiers hold no state, so any instance can take any request. |
Low storage cost without losing durability | Three whole copies cost 200% overhead, so the design keeps copies for hot data and moves the rest to 8+4 erasure coding at 50% overhead. Small objects are packed into large files so disk blocks and inodes are not wasted on them. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Chance of losing an object kept as two or three copies | 0.81% a year is 0.0081. Three disks all dying within the year before repair: 0.0081^3 ≈ 5.3 × 10^-7, so about 99.99995% of objects survive, about 6 nines. Two disks: 0.0081^2 ≈ 6.6 × 10^-5, about 4 nines. Under 8+4 coding an object is lost when 5 of its 12 pieces die: 792 ways to pick 5 pieces × 0.0081^5 ≈ 2.8 × 10^-8, about 7 nines if lost pieces were left unrepaired for the whole year; the chapter's figure for 8+4 is about 11 nines. Failures are assumed independent throughout. 0.81% also means about one disk in 123 dies each year. | Three copies clear 6 nines; two copies land near 4 nines | How many copies the durability target needs, and why cutting to two is not a savings. |
Disk bought per year of new data | Three copies: 3 × 100 PB = 300 PB, a 200% overhead. Two copies: 200 PB. 8+4 erasure coding: 12 pieces ÷ 8 data pieces = 1.5, so 100 PB × 12 ÷ 8 = 150 PB, a 50% overhead. | 300 PB with three copies, 150 PB with 8+4 coding, per 100 PB written | The storage bill, and the cost curveball: coding halves it while durability goes up. |
Small objects arriving each year | 20% of about 1.7 billion objects a year ≈ 340 million under 1 MB; 20% of the 0.68 billion stored now ≈ 136 million. | About 340 million small objects a year | The inodes a one-file-per-object layout would burn each year. |
Objects per packed data file | Assume a 4 GB data file, the 'few GB' in the design. 4 GB ÷ 0.5 MB median small object ≈ 8,000 objects per file; 340 million ÷ 8,000 ≈ 42,500 files a year. | About 8,000 objects per file, tens of thousands of files a year instead of hundreds of millions | Why packing removes the inode problem on a data node. |
Piece size under 8+4 coding | 32 MB median object ÷ 8 = 4 MB a piece; 200 MB ÷ 8 = 25 MB; 0.5 MB ÷ 8 ≈ 64 KB. | 4 MB a piece for a typical object; tiny pieces for small objects | What each node reads on a GET, and why small objects should be packed into a large file before that file is coded. |
Downtime 4 nines allows | 0.01% × 525,600 minutes a year ≈ 52.6 minutes. | About 52 minutes a year | Why failover of the placement service and the metadata store must be automatic. |
Metadata growth | About 1.7 billion new objects a year × 1 KB a row ≈ 1.7 TB a year, on top of about 0.68 TB stored now. | About 1.7 TB of metadata a year | Metadata fits a handful of servers; sharding it is about request load and hot buckets, not space. |
Disk seeks the read load needs | About 1,000 reads a second ÷ 100 to 150 random seeks a disk ≈ 7 to 10 disks' worth of seeks if each GET costs one seek. If a GET first walks a directory and an inode, say three seeks, that is 20 to 30 disks' worth. | A handful of disks' seeks at one seek per read, about three times that if each read walks the filesystem first | Why the object map on a data node has to answer from memory or one local lookup, with one positioned read for the bytes. |
Core entities
| Entity | What it holds |
|---|---|
Bucket | A named container owned by one account; few per account, so the whole table is small. |
Object metadata | One row per version of a key: which bytes it points at and how to serve them. |
Object data | The bytes themselves, addressed by object id and spread over a replication group or a set of coded pieces. |
Object mapping on a data node | A node's private index from object id to where the bytes sit inside its large data files. |
Multipart upload | An in-progress large upload: which parts have arrived and where their bytes are. |
The API
| Endpoint | Notes |
|---|---|
| Creates a bucket for the caller IAM identifies. Names are unique across the service, so this is one insert with a unique constraint, and a taken name is rejected. |
| Streams the bytes through the API service to the data store, then writes the metadata row. The reply goes back after the copies are written and the row is committed, so a GET that follows sees this version. Metadata headers land in the row, not with the bytes. |
| Without a version id, returns the latest version; if the latest row is a delete marker, 404 Not Found. The API reads the row, asks routing for the bytes by object id, verifies the checksum and streams them back. |
| Keys under the prefix in key order, one page at a time. The cursor is an opaque token that encodes where the page ended, so a client that stops and resumes picks up where it left off. Objects added or removed while it pages may or may not appear, since no snapshot is taken. How this runs across shards is the metadata deep dive. |
| Starts an upload and returns an id. Parts are sent independently, in any order and in parallel, each stored like a small object; the complete call lists the parts in order and the API writes one metadata row that points at them. A failed part is retried on its own. An upload that is not completed keeps its parts until the client aborts it or a cleanup rule the operator configures removes them. |
The high-level design
Step 1 of 4
Metadata apart from the bytes
Start with the split the whole design rests on. A client's request reaches a stateless API service through a load balancer. The API checks the caller with IAM, streams the object's bytes through a routing service to a data node, and then writes a small metadata row (bucket, key, version id, object id) to a metadata store. Metadata and data live in different systems because they have different shapes: a row is about 1 KB and is queried by key, prefix and version, while an object averages about 59 MB and is read as one stream. Listing and versioning are questions for the rows; the data nodes just store and return bytes by object id.
What breaks first
The deep dives
The write path and durability. A client PUTs an object and receives a success reply. What has to be true on disk and in the metadata store before that reply goes out, what does a reader see if a disk dies a minute later, and what happens to writes when the service that decides placement goes down?
Storing billions of small objects. A fifth of objects are under 1 MB. How does a data node lay them out on disk, how does a GET go from an object id to the bytes, and how does the node notice a flipped bit?
A concept that helps here: Log-structured storage: packing small objects into large files
A concept that helps here: Database indexesA concept that helps here: Blob storage and presigned uploadsReplication or erasure coding. Keeping three whole copies of each year's 100 PB is a large disk bill. How would you cut it without dropping below 6 nines, and what do reads and repairs cost afterward?
Metadata sharding and listing. One bucket holds billions of objects and a client lists everything under a prefix. Which part of the metadata store strains first, what is the shard key, and how does a paged listing run from the first page to the next?
Concepts this guide uses
- Replication and read replicas
- Leader election and failover
- Consistency models
- Log-structured storage: packing small objects into large files
- Database indexes
- Blob storage and presigned uploads
- Erasure coding and replication
- Sharding and partition keys
- Hot keys and hot partitions
Sources
- Alex Xu, System Design Interview volume 2, chapter 25: notes by Preslav Mihaylov
- Amazon S3 User Guide: Uploading and copying objects using multipart upload
- Amazon S3 API Reference: ListObjectsV2
- Amazon S3 User Guide: Data protection in Amazon S3
- The Raft Consensus Algorithm
- Meta Engineering: Needle in a haystack: efficient storage of billions of photos
- Wikipedia: Erasure code
- SQLite: Appropriate Uses For SQLite
- Wikipedia: inode