Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced

Not a filesystem, and that is the point

Object storage looks like a filesystem and deliberately is not one. The differences are the design:

• Flat namespace. A bucket holds objects keyed by a string. There are no real directories — photos/2026/cat.jpg is one key that happens to contain slashes, which is why "renaming a folder" means rewriting every key under it.
• Immutable objects. You replace an object; you do not seek into it and modify bytes. This single constraint is what makes cheap replication, erasure coding and versioning possible — there is no in-place update to coordinate.
• No hierarchy locking, no partial writes. Which is exactly why it scales to trillions of objects and why it is unsuitable as a database.

Scope

• PUT, GET, DELETE, LIST on objects within buckets.
• Objects from a few KB to several TB.
• 11 nines of durability as the headline requirement — losing data is the unforgivable failure.
• Versioning, multipart upload, and storage tiering.

The architectural split that makes it work

Separate metadata from data:

• The metadata store maps bucket + key (+ version) to a list of chunk locations, plus size, checksum, content type and timestamps. It is small, strongly consistent, and queried on every request.
• The data store holds immutable chunks on many machines. It is enormous and needs no transactional semantics.

These have completely different requirements — one needs consistency and indexing, the other needs throughput and cheap bulk capacity — and splitting them lets each be built correctly. It also explains why LIST is the awkward operation: it is a metadata range scan over a flat keyspace, which is why listing a bucket with a billion objects is paginated and comparatively slow while GET is fast.

Durability: replication versus erasure coding

Replication stores N full copies. Simple, fast to repair (copy a surviving replica), and fast to read (any copy serves the request). At 3×, you pay 200% overhead and survive 2 simultaneous losses.

Erasure coding splits an object into k data chunks and computes m parity chunks, such that any k of the k+m chunks reconstruct the object. With Reed–Solomon(6,3): 6 data + 3 parity = 9 chunks at 1.5× overhead, surviving 3 losses. Compare directly: erasure coding gives better fault tolerance for half the storage.

Which raises the obvious question — why replicate anything? Three real costs:

• Repair amplification. Losing one 1 MB chunk requires reading 6 chunks from 6 machines and recomputing. Replication reads 6 MB from one machine. At fleet scale, disks fail constantly, so repair traffic is continuous background load, and erasure coding multiplies it.
• Read latency. A small object read must contact k machines and wait for the slowest, so tail latency is governed by the worst of six rather than the best of three.
• Small-object waste. Splitting a 4 KB object into six chunks produces tiny fragments; per-chunk metadata and minimum block sizes can exceed the data itself.

Hence the rule: erasure-code the cold, large bulk; replicate the hot, small and latency-critical. Most production systems do both and move objects between schemes as access patterns reveal themselves.

Failure domains are what turn the arithmetic into real durability. Chunks must be placed so that no single correlated failure — a rack, a power circuit, an availability zone — takes out more than m chunks. Nine chunks spread across nine racks survives a rack loss; nine chunks that happen to land in one rack survives nothing, while reporting the same replication factor. Durability is a property of placement, not of the coding scheme.

Multipart upload, and why it exists

Uploading a 5 TB object as one HTTP request is untenable: a failure at 99% loses everything, one connection caps throughput, and no proxy tolerates the duration. Multipart upload fixes it in three phases:

1. Initiate — the client asks to start an upload and receives an upload ID.
2. Upload parts — parts are uploaded independently, in parallel, in any order, each returning an ETag. A failed part is retried alone.
3. Complete — the client sends the list of part numbers and ETags; the service assembles them and then makes the object visible.

The critical property is that the object becomes visible atomically at completion — readers never observe a half-uploaded object. Note the operational consequence: an abandoned multipart upload leaves parts consuming storage that no object references and no LIST reveals. Every real deployment needs a lifecycle rule to abort incomplete uploads, and forgetting it is a classic silent cost leak.

Integrity: checksums all the way down

At sufficient scale, disks return wrong data rather than errors — bit rot, firmware bugs, torn writes. So every chunk carries a checksum, verified on read and periodically by a background scrubber that walks stored data looking for corruption and repairs from parity or replicas. Without scrubbing, corruption is discovered only when someone reads the object, which for archival data could be years — by which time the redundancy protecting it may also have degraded.

End to end, the client can send a checksum with the upload so the service verifies the bytes it received match what was sent, catching corruption in transit. (S3's ETag is a related but distinct thing — for single-part uploads it is the MD5 of the object, but for multipart uploads it is a hash of the part hashes plus a part count, so it is not the MD5 of the whole object and cannot be compared as one. That mismatch surprises people writing verification scripts.)

Versioning and deletion

With versioning enabled, a PUT to an existing key creates a new version rather than overwriting, and each version is independently addressable. Because objects are immutable, this is nearly free — you add a metadata row pointing at new chunks and keep the old rows.

Deletion is the subtle part. A DELETE on a versioned object writes a delete marker: a tombstone that becomes the current version, so GET returns 404 while the prior versions still exist and can be restored. Two consequences worth knowing: deletion increases metadata, and deleting data does not free space until a lifecycle policy expires the old versions. A bucket whose storage bill keeps rising while the application "deletes" aggressively is almost always this.

Space is reclaimed asynchronously by a garbage collector that finds chunks no live version references, and by compaction that merges the surviving small objects out of mostly-dead storage regions into fresh ones — the same mechanic as LSM-tree compaction, and for the same reason: reclaiming space in an append-only store means rewriting what is still alive.

Which scheme, when

Decision	Option	Choose when	Cost / breaks when
Durability	Erasure coding (6,3)	Large, cold, bulk data — the majority by bytes	Small objects, latency-sensitive reads, repair-heavy fleets
Durability	3× replication	Small, hot, latency-critical objects	Bulk storage — you pay 2× the disk for less fault tolerance
Upload	Multipart	Anything above ~100 MB	Tiny objects — pure overhead; needs abort lifecycle rules
Upload	Single PUT	Small objects	Large objects — no resume, one connection, timeouts
Consistency	Strong read-after-write	Modern expectation; pipelines depend on it	Requires a consistent metadata store — the harder component
Consistency	Eventual for overwrites	Legacy designs, geo-replicated reads	Read-after-write workflows silently read stale objects
Metadata	Sharded KV by bucket+key	Scales to trillions of objects	LIST across shards needs a merge; prefix scans get hot

The consistency row deserves a note: object storage historically offered eventual consistency for overwrites, and plenty of designs still assume it. Strong read-after-write is now the norm, and it is worth being explicit about which you are designing, because a data pipeline that writes then immediately reads is correct under one model and intermittently broken under the other — with failures that only appear under load.

Pitfalls

• Erasure coding small objects. Fragment overhead can exceed the data; batch small objects together first.
• Chunk placement ignoring failure domains. Nominal 3-loss tolerance, actual 0 if all chunks share a rack.
• No scrubber. Silent corruption found on read, years later, possibly alongside degraded redundancy.
• Forgetting to abort incomplete multipart uploads. Invisible storage that bills forever.
• Treating ETag as the object's MD5 for multipart uploads — it is not, and integrity checks built on that assumption fail confusingly.
• Assuming DELETE frees space with versioning enabled. It adds a delete marker; a lifecycle policy is what reclaims.
• Sequential key prefixes (timestamps at the start of the key) creating a metadata hot shard, because all writes land in one range.
• Using it as a database. No partial updates, no locking, slow LIST — the flat immutable model is a poor fit for mutable records.

Cost model — what dominates the bill

Object storage is the one system here where raw capacity really is the dominant cost — which is precisely why the erasure-coding decision is worth so much money.

Rough BOTE for 100 PB of logical data. At 3× replication you provision 300 PB; with RS(6,3) you provision 150 PB for better fault tolerance. At even $10/TB-month for dense disk, that difference is 150,000 TB × $10 = $1.5 million/month saved. No other decision on this page is worth a fraction of that, and it is why every large object store erasure-codes its bulk tier.

Then the operational costs that surprise people. Repair traffic is continuous: with hundreds of thousands of disks, some fail every day, and each erasure-coded repair reads k chunks across the network. That background rebuild bandwidth must be provisioned, and it competes with user traffic — which is why repair is rate-limited and why a large correlated failure produces a long rebuild queue. Metadata is small per object but enormous in aggregate: a trillion objects at ~1 KB of metadata each is 1 PB of strongly-consistent, indexed, low-latency storage — far more expensive per byte than the bulk tier, and often the harder scaling problem.

Dominant line items: bulk capacity (× the redundancy overhead); then metadata store capacity and IOPS; then egress, which for a public service is typically the largest revenue-relevant line; then repair bandwidth.

Levers: erasure-code everything that tolerates it (by far the biggest); lifecycle-tier cold objects to cheaper media and expire old versions; abort incomplete multipart uploads; and compact small objects so per-object metadata and minimum-block waste do not dominate for the many-tiny-files workload.

Operability: the fingerprints of a sick object store

Storage growing while application-reported data volume is flat has three usual causes and they are distinguishable: orphaned multipart parts (check incomplete-upload age), retained old versions plus delete markers (check version counts per key), and garbage collection falling behind (check unreferenced-chunk backlog). All three bill you for data nobody can read.

Read tail latency degrading while median holds is the erasure-coding signature — a read waits for k chunks, so one slow disk anywhere in the placement group hurts the tail; the fix is hedged requests or reconstructing from parity rather than waiting. Repair queue length growing after a rack failure is expected, but if it does not drain you are rate-limited below your failure rate, which means durability is degrading over time rather than recovering.

The two genuinely dangerous ones: scrubber-detected corruption rate rising, which can indicate a bad firmware batch or a failing hardware generation and is the earliest warning you will get before correlated data loss; and chunk placement skew, where a rebalance or a topology change has quietly co-located chunks of the same object in one failure domain. The second is invisible in every capacity dashboard and is exactly the condition under which a routine rack failure becomes a data-loss incident, so it deserves an explicit audit rather than trust.

Watch also for a hot metadata shard from sequential key prefixes, and LIST latency climbing as a bucket grows, which is inherent to range-scanning a flat keyspace and is a signal to redesign key layout rather than to add capacity. Signals worth having: incomplete-upload count and age, versions and delete markers per key, GC backlog, per-object chunk-placement failure-domain audit, scrub corruption rate by hardware batch, repair queue depth and drain rate, and read latency percentiles split by storage scheme.

---

Authored for this guide to cover the S3-like object storage design (Alex Xu Vol. 2, ch. 24 — not present in the Vol. 1 PDF); replication-versus-erasure-coding diagram hand-authored as SVG. Complements this guide's Distributed File System topic, "Checksums and ETags", and "Cloud Storage Data Movement" pages.

I just read a lesson on **Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced** (System Design) and want to truly understand it. Explain Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Designing an S3-like Object Storage — Erasure Coding, Multipart & Versioning, Traced** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.