Erasure Coding: How to Save Disk Space Without Giving Up Redundancy

If you operate a storage system, keeping a single copy of your data is obviously not enough. Disks fail, servers fail, racks fail, and sometimes whole availability zones fail, so some form of redundancy is required if you want the data to survive hardware failures.

The simplest way to achieve that is replication, a common industry choice is 3-way replication. If you have 1 TB of data and keep three copies, you consume 3 TB of physical storage, thus needing 3x the disk space... And, sadly, disks are expensive these days. This is easy to understand, easy to implement, and gives you a straightforward recovery model: if one copy disappears, read another one and create a replacement in another server so you restore full redundancy.

The downside is obvious: it is expensive. For every byte of useful data, you are storing three bytes on disk.

Erasure coding gives us a different way to buy redundancy.

Instead of copying the data, add enough information to rebuild it

Imagine that we split your data into six chunks:

D1 D2 D3 D4 D5 D6

We then calculate three additional chunks (more on this calculation later):

P1 P2 P3

and store all nine:

D1 D2 D3 D4 D5 D6 P1 P2 P3

This is usually described as a 6+3 erasure code. The first six chunks contain the original data, while the other three contain additional information calculated from it.

At this point, you can see the basic trade-off: we can tolerate several missing chunks while using around 1.5× the raw capacity instead of the 3× required by three-way replication.

You do not need all nine chunks to read all the data. With this 6+3 Reed-Solomon scheme, any six chunks are enough, which means we can lose any three chunks and still reconstruct the original object.

If each shard lives on a different server, the stripe can survive the loss of any three of those servers. A three-way replicated object, by comparison, becomes unavailable once all three machines holding its replicas are lost.

For example:

D1 D2 -- D4 -- D6 P1 -- P3

Three chunks are missing, but six survive, so the original data is still recoverable.

This is the main idea behind erasure coding: instead of storing several complete copies of the same thing, you store the original data plus enough extra mathematical information to reconstruct whatever goes missing.

Where does the space saving come from?

Suppose we want to store 600 TB of useful data.

With three-way replication we need:

600 TB × 3 = 1,800 TB

With a 6+3 erasure code we need:

600 TB × 9/6 = 900 TB

So we have gone from 1,800 TB of physical storage to 900 TB while still retaining the ability to survive multiple failures.

Another way to express it is that three-way replication has a 3× storage cost, while 6+3 erasure coding has a 1.5× storage cost. At small scale that may simply be a nice saving. At petabyte or exabyte scale, it becomes a very large amount of hardware, power, rack space, and money.

What is actually inside P1, P2 and P3?

This is where Reed-Solomon coding comes in.

A simplified way to think about Reed-Solomon is that every parity chunk contains a different mathematical relationship between the original data chunks.

Take a much smaller example with three data values:

D1
D2
D3

We could generate two parity values that look conceptually like this:

P1 = D1 + D2 + D3
P2 = D1 + 2×D2 + 4×D3

Now imagine that D2 and D3 disappear. We still know D1, P1 and P2, so after subtracting the contribution of D1 we are left with something equivalent to:

D2 + D3 = something
2×D2 + 4×D3 = something else

We have two unknown values and two independent equations, which means we can solve for both missing values.

That is the useful intuition behind Reed-Solomon. Real implementations use finite-field arithmetic rather than normal integer arithmetic, but from a storage-system point of view the important idea is simply that each parity shard gives us another independent equation involving the original data.

If one chunk disappears, we need enough information to solve for one unknown. If two disappear, we need two independent equations. If three disappear, we need three. A 6+3 scheme gives us enough redundancy to recover from any three missing chunks.

What if the parity chunks are the ones that fail?

Nothing particularly interesting happens.

If all three parity chunks disappear:

D1 D2 D3 D4 D5 D6 -- -- --

We still have all the original data, so reads can continue normally. The system only needs to regenerate the missing parity later to restore its expected level of redundancy.

The important point is that the parity chunks are not special backup copies. A 6+3 code can tolerate the loss of any three chunks, whether those are three data chunks, three parity chunks, or some mixture of the two. As long as six of the nine remain, the data can be recovered.

Why not just XOR everything?

A much simpler parity scheme would be:

P = D1 XOR D2 XOR D3

This is similar to the parity used by RAID-5. If D2 disappears, we can reconstruct it easily:

D2 = P XOR D1 XOR D3

The problem appears when two chunks disappear. If both D2 and D3 are gone, we have two unknown values but only one parity equation. There simply is not enough information to determine what both original values were.

Reed-Solomon gets around this by generating several different, independent parity equations. That extra information is what allows it to recover several missing chunks at the same time.

The storage saving is not free: Trade-offs.

Erasure coding saves a lot of disk space, but it pushes some of the cost into other parts of the system.

With replication, repairing a lost copy is relatively simple: read a healthy replica and write another copy somewhere else.

With erasure coding, repairing a missing shard may require reading several surviving shards from different disks or machines, decoding them, reconstructing the missing data, and then writing the replacement shard. That consumes CPU, disk bandwidth, network bandwidth, and coordination between storage nodes.

Degraded reads can become more expensive for the same reason. If the exact shard you need is unavailable, the system may have to fetch several other shards and reconstruct the missing one before it can satisfy the read.

So the trade-off is not really "replication versus free disk space." It is closer to this:

Replication
-----------
More storage
Simple reads
Simple repair

Erasure coding
--------------
Less storage
More computation
More expensive repair
More coordination

Whether that trade-off makes sense depends on the workload, the hardware, and the scale of the system. The right redundancy strategy depends on the workload, hardware and failure model

Small writes are another trade-off

Erasure coding also makes writes more complicated, especially small updates.

With three-way replication, changing a small piece of data is conceptually simple: write the new data to the replicas.

With erasure coding, the parity chunks depend on the contents of the data chunks. If part of D2 changes, the corresponding parity information in P1, P2, and P3 may also need to change.

One common approach is called read-modify-write. The system reads the old data and parity, calculates how the update changes the parity, and then writes both the updated data and updated parity back out.

Conceptually:

read old D2
read old parity
        ↓
apply update
        ↓
recalculate affected parity
        ↓
write new D2
write new parity

For large sequential writes this may not be a big problem, because the system can encode an entire new stripe at once. For small random writes, however, the amount of extra I/O and coordination can become significant.

This is one reason many storage systems do not use the same redundancy scheme for every workload. Replication may be preferable for hot, frequently updated data, while erasure coding becomes much more attractive for large objects, colder data, or workloads where capacity efficiency matters more than write latency.

Degraded reads: the data is still there, but reads get more expensive

One of the useful properties of erasure coding is that losing a shard does not immediately make the data unavailable.

Suppose we have our usual 6+3 stripe:

D1 D2 D3 D4 D5 D6 P1 P2 P3

and D3 becomes unavailable:

D1 D2 -- D4 D5 D6 P1 P2 P3

If a client wants data that lives entirely in D1, nothing particularly interesting happens. The system can simply read D1 as normal.

The interesting case is when the client asks for data from D3.

With replication, the storage system would normally read another replica. With erasure coding there may be no second copy of D3, so the system has to reconstruct it from the surviving shards.

Conceptually, instead of:

read D3

the request becomes something closer to:

read D1
read D2
read D4
read D5
read D6
read one parity shard
        ↓
decode
        ↓
reconstruct D3
        ↓
return requested data

The exact number of shards required depends on the erasure code and implementation, but the important point is that one missing read can turn into several reads from several machines, plus network traffic and decoding work.

That is a degraded read.

The data is still available, but serving it is more expensive.

Why degraded reads hurt

The obvious cost is additional I/O. A request that normally required one disk read may now require data from several disks or servers. Those fragments then have to travel over the network and be decoded before the original request can complete.

That introduces several kinds of amplification at once:

normal read
    ↓
1 shard read

degraded read
    ↓
multiple shard reads
network fan-out
decoding CPU
extra memory
more coordination

There is also a latency problem. A normal read may depend on one storage node responding quickly. A reconstructed read depends on several nodes, so the request can become sensitive to the slowest of them.

This is particularly unpleasant in distributed systems because latency distributions have long tails. If you need six responses instead of one, you have more opportunities for one of those responses to be slow.

The system can try to compensate by issuing extra reads or choosing the fastest available set of shards, but that creates even more traffic.

So although erasure coding has preserved availability, the workload can now be running in a noticeably worse state.

So why not just stay degraded?

Because redundancy is a consumable resource.

With a healthy 6+3 stripe we can lose three shards:

6 data + 3 parity
3 failures tolerated

After losing one shard, we only have two failures of safety left:

8 surviving shards
2 more can disappear

Lose another before repairing:

7 surviving shards
1 failure left

Lose a third:

6 surviving shards
no redundancy left

At that point the data is still readable, but one more shard failure makes the stripe unrecoverable.

This is why repair matters even when clients can still successfully read the data. The system is not just repairing performance; it is restoring its failure budget.

A useful way to think about it is that every missing shard moves the stripe closer to the edge:

9 shards  → healthy
8 shards  → degraded
7 shards  → more degraded
6 shards  → readable, but no failures left
5 shards  → data lost

For a 6+3 code, six surviving shards are enough to reconstruct the object, but that does not mean operating permanently with six shards is acceptable.

Repair also stops repeated reconstruction

There is another practical reason to repair quickly.

Imagine D3 is missing and clients keep requesting data from it. Without repair, the system may reconstruct that data over and over again:

request 1 → reconstruct D3
request 2 → reconstruct D3
request 3 → reconstruct D3
request 4 → reconstruct D3

That is wasteful.

Once the system reconstructs D3 and writes it to a new machine, subsequent reads go back to:

request → read D3

So repair removes the extra CPU, network and disk cost from future reads as well as restoring redundancy.

Some systems may temporarily cache reconstructed data or perform reconstruction lazily, but eventually the missing shard needs to be restored if the system wants to return to its intended durability and performance characteristics.

Repair itself creates load

There is an awkward part, though: the thing that fixes degraded operation also consumes resources.

To rebuild D3, the system might have to read six surviving shards, move that data across the network, decode the missing shard and write it to another machine.

If one disk fails, that may affect thousands or millions of stripes. Suddenly the storage system wants to perform a huge number of reconstructions at once.

That creates what is often called a repair storm:

hardware failure
      ↓
many missing shards
      ↓
many reconstruction reads
      ↓
heavy disk + network + CPU load
      ↓
foreground requests become slower

If repair is too slow, the system remains exposed to additional failures for longer. If repair is too aggressive, it can consume so much I/O and network bandwidth that normal customer traffic suffers.

This creates another trade-off: repair quickly enough to restore durability, but not so aggressively that the repair process becomes an outage of its own.

Large storage systems therefore tend to prioritise repair work. A stripe that has lost two shards may be repaired before one that has lost only one, because it is closer to becoming unrecoverable. Systems may also throttle reconstruction traffic, spread it across machines, or delay lower-priority repairs when the cluster is under heavy load.

So when a shard disappears, erasure coding has done its job: the data is still there. But the system is now spending more resources to serve it and has less protection against the next failure.

That is why degraded operation is something you tolerate temporarily, not a state you want to stay in.

Bit rot: when the disk gives you the wrong data

So far we have assumed that failures are obvious: a disk dies, a server disappears, or a shard becomes unavailable. There is another, nastier failure mode where the storage device happily returns data, but the data is no longer the same as what you originally wrote.

This is usually referred to as bit rot or, more generally, silent data corruption.

A sector might be damaged, firmware might return incorrect data, memory corruption might occur somewhere in the I/O path, or a bug might simply write the wrong bytes. From the point of view of the application, this is potentially worse than a failed disk because nothing necessarily tells you that anything went wrong.

In a system with hundreds of thousands of servers, this, and many other supposedly rare failures, becomes a Tuesday.

Imagine our usual stripe:

D1 D2 D3 D4 D5 D6 P1 P2 P3

D3 still exists and the server hosting it is perfectly healthy, but one part of the shard has silently changed:

D1 D2 D3* D4 D5 D6 P1 P2 P3
      ^
   corrupted

Erasure coding can help us recover the correct data, but there is an important catch: we first need to know that D3 is wrong.

That is why storage systems normally combine erasure coding with checksums or other integrity metadata. When a shard is written, the system calculates a checksum for it. When the shard is read later, it calculates the checksum again and compares the result.

Conceptually:

write D3
   ↓
checksum(D3) = ABC123
   ↓
store D3 + checksum

Later:

read D3
   ↓
checksum(D3) = F91E20
   ↓
expected ABC123
   ↓
corruption detected

Once the system knows that D3 cannot be trusted, it can treat it much like a missing shard. Instead of returning the corrupt data, it can reconstruct the correct version from the remaining shards:

D1 D2 D3* D4 D5 D6 P1 P2 P3
        ↓
    ignore D3
        ↓
read enough healthy shards
        ↓
reconstruct D3
        ↓
verify checksum
        ↓
replace corrupted copy

This is an important distinction. Erasure coding provides the redundancy needed to correct corruption; checksums tell us which data needs correcting. Without some independent integrity check, the system may have no reliable way to distinguish a valid shard from a corrupted one.

Scrubbing: finding corruption before somebody reads it

There is another problem with silent corruption: some data may not be read for months or years.

If corruption is only discovered when an application happens to request the object, you might find it very late, perhaps after other shards in the same stripe have also failed.

Storage systems therefore commonly perform scrubbing, where data is periodically read and its integrity checked even when no client has requested it.

A scrub might discover:

D1 ✓
D2 ✓
D3 ✗
D4 ✓
D5 ✓
D6 ✓
P1 ✓
P2 ✓
P3 ✓

The system can then reconstruct D3 while the stripe still has plenty of redundancy, rather than waiting until the corruption becomes part of a more serious failure.

This is another reason repair matters even when everything appears to be working. Redundancy is useful only if the copies or shards you are relying on are actually healthy.

There is a slightly uncomfortable consequence here: having nine shards does not necessarily mean you have nine good shards. If corruption can remain undetected for long periods, your real redundancy may be lower than your metadata suggests.

Checksums, background scrubbing and erasure coding therefore complement each other:

Checksums
    ↓
detect corruption

Scrubbing
    ↓
find it early

Erasure coding
    ↓
reconstruct the correct data

Repair
    ↓
restore full redundancy

This also changes how we think about disk failures. A completely dead disk is inconvenient, but at least the failure is obvious. Silent corruption is dangerous precisely because the system may continue operating normally while one of the pieces it expects to rely on is already bad.

Placement: deciding where the chunks actually live

So far we have treated the nine chunks in our 6+3 stripe as if they simply existed somewhere in the storage system:

D1 D2 D3 D4 D5 D6 P1 P2 P3

But where we place those chunks is just as important as how we calculate them.

A 6+3 code does not mean “survives three server failures” by itself. It means “survives three missing shards.” Placement is what turns that mathematical guarantee into a server, rack, or zone failure guarantee.

The obvious rule is that putting two chunks from the same stripe on the same disk would be a bad idea. If that disk fails, we lose two chunks at once. Putting all nine chunks on different disks but inside the same server is not much better, because a server failure would still take the entire stripe with it.

So a storage system normally spreads the chunks across failure domains. A simplified layout might look like this:

Rack A          Rack B          Rack C

Server A1       Server B1       Server C1
   D1              D3              D5

Server A2       Server B2       Server C2
   D2              D4              D6

Server A3       Server B3       Server C3
   P1              P2              P3

Now a single disk or server failure only removes one chunk. We can also lose an entire rack and still have six chunks left, which is exactly the minimum required by our 6+3 code.

This illustrates an important distinction: erasure coding defines how many failures we can tolerate, while placement determines which real-world failures translate into lost chunks.

A placement algorithm then needs to understand the topology of the storage system. Disks belong to servers, servers belong to racks, racks may belong to clusters or availability zones, and failures at those levels are not independent. A failed power distribution unit might take out half a rack. A top-of-rack switch failure can make every server in a rack unreachable at the same time. An availability-zone outage can remove thousands of machines at once.

Randomly choosing nine disks without considering any of this can produce a mathematically valid erasure-coded stripe with terrible real-world durability.

Spreading versus locality

The obvious response is to spread every shard as far apart as possible, but that introduces another trade-off.

Suppose the nine chunks are distributed across three availability zones. That gives excellent protection against a zone failure, but now normal writes may require sending data across zones, and reconstruction may need to pull several shards over relatively expensive and slower network links.

At the other extreme, keeping all nine chunks in the same rack gives excellent locality and cheap networking, but very poor protection against rack-level failures.

Placement is therefore an optimization problem between durability, availability, network cost, latency and repair behaviour.

A system might choose something like:

3 racks
3 chunks per rack
never two chunks on the same server

or perhaps:

3 availability zones
3 chunks per zone
each chunk on a different server

The exact policy depends on what failures the system is designed to survive.

There is no universally correct layout.

Placement also matters during repair

Things become more interesting when something actually fails.

Suppose D3 disappears:

D1 D2 -- D4 D5 D6 P1 P2 P3

The storage system can reconstruct it from six surviving chunks, but it also needs to decide where the new D3 should be placed.

Simply choosing the first machine with free disk space can gradually destroy the original placement guarantees. After enough failures and repairs, you might accidentally end up with several chunks from the same stripe in the same rack or failure domain.

So repair is not just:

reconstruct missing chunk
write it somewhere

It is closer to:

identify missing chunk
        ↓
select surviving chunks
        ↓
reconstruct it
        ↓
find a destination that preserves placement constraints
        ↓
write the replacement

The placement policy therefore needs to apply both when the data is initially written and every time the system repairs or rebalances it.

Correlated failures are the real enemy

When talking about redundancy, it is tempting to think only in terms of individual disk failures. Large storage systems are usually more concerned about correlated failures.

Disks in the same server share a power supply, motherboard and network connection. Servers in the same rack share switches and power infrastructure. Machines from the same hardware batch may fail in similar ways. A software bug can take down thousands of otherwise independent machines at once.

This means that "nine chunks on nine disks" tells us surprisingly little about durability unless we also know where those disks are and what they share.

For example, this:

9 chunks
9 disks
1 server

has terrible fault isolation.

This:

9 chunks
9 servers
1 rack

is better, but one rack failure can still remove everything.

And this:

9 chunks
9 servers
3 racks

may allow the system to survive an entire rack failure, depending on how the shards are distributed.

The goal of placement is to make sure that failures which are likely to happen together do not consume more erasure-code tolerance than expected.

Repair traffic also depends on placement

Placement affects performance as well as durability.

If a missing shard can be reconstructed from six machines in the same rack, most of the repair traffic stays on the rack network. If those six shards live in different racks or availability zones, the same repair may consume much more expensive network capacity.

This becomes particularly important during large failures. Losing one disk is easy. Losing an entire server may trigger hundreds or thousands of reconstructions at once. Losing a rack can trigger an enormous amount of repair traffic exactly when the network is already dealing with a failure.

A good storage system therefore has to think not only about where the data is placed, but also about what the system will look like while it is degraded.

That can mean throttling repairs, prioritising stripes that are closest to losing data, spreading reconstruction work across the fleet, or temporarily accepting reduced redundancy rather than saturating the network and making the outage worse.

This is one of the places where erasure coding becomes significantly more complicated than replication. The mathematics tells us that the data is recoverable. The distributed system still has to recover it without falling over in the process.

The useful mental model

The simplest distinction is this:

Replication survives failures by storing complete duplicate copies of the data. Erasure coding survives failures by storing enough mathematical information to recreate the data that disappeared.

That is why erasure coding is so attractive in large storage systems. Instead of paying a 3× capacity cost for three-way replication, a scheme such as 6+3 can reduce that to 1.5× while still tolerating multiple failures.

You save a substantial amount of storage, but in exchange you accept more complex reads, repairs, placement and recovery logic. At small scale, replication is often the easier choice. At petabyte or exabyte scale, however, the capacity savings become very difficult to ignore.