Design an object storage service

I would split the system in two. A metadata index keeps one small row per object, sorted by bucket and key and sharded by key range, each shard replicated by consensus. At 20 billion objects that is about 4 TB, or 200 GB in each of 20 shards, and listing by prefix is a seek and a scan in one shard. The data lives on storage nodes as erasure-coded chunks, 6 data plus 3 parity, which costs 1.5 times the space and tolerates 3 lost chunks.

Objects hash into 100,000 placement groups. A small cluster map says which nine nodes on nine racks hold a group, so a disk failure changes the map and no metadata. A put writes the chunks first, then commits the metadata row, so a visible object always has durable data and the leader answers reads, which gives read-after-write. With 3,000 disks, about 60 fail each year, so a health monitor queues repairs, the worst groups first.

Rebuilding a disk takes about 5.6 hours, and shortening that window helps durability most. Checksums and scrubbing catch silent corruption. Large objects go up as parallel parts and become visible with one commit.

These numbers are assumptions for the exercise, not facts about a real system:

• The service holds 20 billion objects with a mean size of 2 MB, which is 40 PB. A metadata row takes 200 bytes.
• Data is stored with a 6 data plus 3 parity code, so any 6 of 9 chunks rebuild an object. Disks hold 20 TB and a disk fails 2% of years.
• The cluster can rebuild lost data at 1 GB/s without hurting normal traffic. Metadata is split into 20 shards.

The arithmetic:

Raw storage

40 PB × 9 ÷ 6 = 60 PB with the code; 40 PB × 3 = 120 PB with 3 copies

60 PB, half the space of three copies

Disks and failures

60 PB ÷ 20 TB = 3,000 disks; × 2% a year

about 60 failures a year, roughly one a week

Metadata index

20B × 200 bytes = 4 TB; ÷ 20 shards; 100,000 requests/s ÷ 20

200 GB and about 5,000 lookups/s per shard

Repair of one lost disk

20 TB to rebuild ÷ 1 GB/s = 20,000 s; reads are 6 × 20 TB = 120 TB

about 5.6 hours, and 120 TB of reads

Chance of losing an object, if failures were independent

p = 2% × 5.6 h ÷ 8,760 h ≈ 1.3 in 100,000 per disk per window. A 9-chunk group dies if 4 fail: 126 × p^4, over 1,564 windows a year

≈ 5 in 10^15 a year, against ≈ 3 in 10^12 for 3 copies. Real risk is correlated failures

The two have different shapes. Metadata is tiny rows that need ordered lookups, prefix scans and strong consistency. Data is huge, unchanging blobs that need disk throughput. Keeping them apart lets us put metadata on fast flash in a replicated, sorted store, and data on cheap, large disks.

The metadata index is sorted by bucket and key, and it is split by key range, not by hash. A hash spreads load evenly, but a listing by prefix would then have to ask every shard and merge. With ranges, a prefix usually sits in one shard. The price is hot ranges, such as keys that begin with a timestamp, so shards split when they grow past a size or load limit. At 20 billion rows of 200 bytes, that is 4 TB in 20 shards.

Data placement uses indirection. Recording nine nodes on every row would be big and would need rewriting whenever a disk fails. Instead, hash the object id into one of 100,000 placement groups. A small cluster map says which nine nodes hold each group. The map is a few megabytes, every gateway keeps a copy, and it changes only when disks fail or are added. A failure changes the map for the groups on that disk, and no metadata row changes.

The numbers fit: 60 PB ÷ 100,000 groups is 600 GB a group, or about 67 GB per node. A disk then belongs to 100,000 × 9 ÷ 3,000 = 300 groups, and 300 × 67 GB gives its 20 TB. Those 300 groups have their partners spread across the cluster, so a repair is read from many disks at once.

Write order. Write the chunks first and commit the metadata last. A crash in between leaves orphan chunks that no row points to. A garbage collector removes chunks without a row once they are a day old. Readers can never see a half-written object, because they always go through the row.

Very small objects do badly with a 6-way split, since each chunk would be a few hundred bytes. Pack small objects into larger blobs, or keep three copies of them.

Three copies. Simple. A read goes to any one node, and repair is a plain copy. It tolerates the loss of 2 copies, and it costs 3 times the space: 120 PB for our 40 PB.

Erasure coding, 6 data plus 3 parity. Cut the object into 6 data chunks, and compute 3 parity chunks with an error-correcting code. Any 6 of the 9 chunks rebuild the whole object, so any 3 losses are survivable. It costs 9 ÷ 6 = 1.5 times the space, 60 PB. The prices are real. A read needs 6 nodes and not 1, so ask for 7 and use the first 6 to arrive, which protects tail latency. A write needs the encoding work and 9 writes. Repair needs reading 6 chunks to rebuild 1, so rebuilding a 20 TB disk reads 120 TB.

Durability arithmetic. At 1 GB/s, a rebuild takes about 5.6 hours. In that window, a disk fails with probability p ≈ 1.3 in 100,000. A 9-chunk group is lost only if 4 chunks fail inside the same window, which is about 126 × p^4. Over the 1,564 windows in a year, that is about 5 in 10^15 per object. Three copies need all 3 to fail, about p^3 per window, or 3 in 10^12 a year. So the code is both smaller and safer, in this model.

The model assumes failures are independent, and they are not. A rack loses power, a batch of disks has the same firmware bug, or an operator makes a mistake. So place the 9 chunks on 9 different racks, ideally across 3 zones, and test the repair path often.

The window is the lever. Loss needs 4 failures inside one window, and each window is shorter and more frequent when repair is faster, so halving the repair time cuts the yearly risk about 8 times. Repair the groups with the most missing chunks first. Wait 10 minutes before declaring a disk dead, so a reboot does not trigger a 120 TB read.

Disks also rot silently. Store a checksum with every chunk, check it on each read, and run a slow background scrub that reads every chunk. A bad chunk is treated as lost and rebuilt.

Multipart upload. The client asks to start an upload and gets an upload id. It then sends parts, each with a number, in parallel and with independent retries. Each part is stored as chunks like any object, with a checksum. When the client calls complete with the list of parts, the service commits one metadata row that lists the parts in order, and that single write makes the object appear. An abort, or an upload left for a week, has its parts deleted. If a limit is 10,000 parts, a 5 TB object needs parts of at least 500 MB. A range read finds which parts and chunks hold the requested bytes.

Listing. A list call has a bucket, a prefix, a delimiter such as a slash, a start point and a page size. Because the index is sorted, the shard seeks to the prefix and scans forward. With a delimiter, when it reaches a key like photos/2024/a.jpg under the prefix photos/, it returns the common prefix photos/2024/ once and then seeks past every key that starts with it. This is how a bucket looks like folders without ever storing folders. The next page is a token holding the last key returned, not an offset, so pages stay correct while keys are added.

Read-after-write. Each metadata shard is a small group of replicas using a consensus protocol. A commit returns after a majority has written the row. Reads and lists for that shard are answered by the leader, or by a follower that has first checked that it has applied everything the leader has committed. So any request made after a put returns will see the row. Because the chunks were written first, a visible row always points to readable data.

Overwrites. An overwrite writes a new object with a new id and then switches the row to point at it in one atomic write. A reader gets the whole old object or the whole new one, since both are immutable. The old chunks are removed later by garbage collection.

A put that must not replace an existing key is a conditional insert on the same row. If we allowed stale reads from any follower, reads would scale further but could miss a new object, so say that choice out loud.