Erasure Coding: How HDFS Cuts Replication Cost from 200% to 50%

⏱️ Lectura: 12 min

Storing three complete copies of every file works, but it costs three times the disk space. Erasure coding achieves the same fault tolerance with a fraction of the space: it splits data into fragments, computes parity pieces using finite field math, and reconstructs whatever is missing without needing an identical copy stored elsewhere.

📑 En este artículo

1. TL;DR
2. What erasure coding is and why it matters
3. How erasure coding works under the hood
   1. The math in one paragraph
   2. Encoding and decoding
4. Practical examples with code
   1. Hello world with reedsolo
   2. Sharding a real file with simulated failures
5. How to get started
6. Real-world use cases
7. Common mistakes and best practices
8. Comparison with alternatives
9. Going deeper
   1. Why GF(256) instead of normal arithmetic
   2. Systematic vs non-systematic codes
10. Frequently Asked Questions
    1. Does erasure coding completely replace replication?
    2. How many fragments can I lose with an RS 6-3 scheme?
    3. Does erasure coding work the same for small files as for large files?
    4. What’s the difference between erasure coding and a simple CRC-style checksum?
    5. Do RAID 6 and HDFS erasure coding use the same algorithm?
11. References

Systems like HDFS, S3-style object storage, and RAID 6 arrays use this technique every day to survive failing disks without duplicating every byte. Understanding how it works under the hood, and coding it yourself, is simpler than it seems.

TL;DR

• You’ll understand why erasure coding replaces 3x replication with half or less of the disk space.
• You’ll code a Reed-Solomon encoder and decoder in Python using the reedsolo library.
• You’ll simulate the loss of entire fragments and reconstruct a file without any identical copy.
• You’ll learn to read a k+m notation like RS 6-3 and calculate how many failures it tolerates and what overhead it pays.
• You’ll learn when RAID 6 makes sense, when HDFS with erasure coding does, and when simple replication does.
• You’ll understand why QR codes, CDs, and erasure coding share the same Reed-Solomon math from 1960.

What erasure coding is and why it matters

The simplest way to tolerate failures is to keep copies: if a disk dies, you read another copy. That’s what HDFS does by default with its replication factor of 3, where each block lives on three different machines. It works, but the storage cost is 200% extra: for every terabyte of useful data, you store two additional terabytes just as backup.

Erasure coding attacks the same problem from a different angle. Instead of copying the entire piece of data, it splits it into k data fragments and computes m additional parity fragments, using finite field algebra: the same Galois fields that protect a scratched CD or a dirty QR code. The result is k+m total fragments, of which having any k is enough to reconstruct the complete original file.

That word “any” is the key: it doesn’t matter which m fragments are missing, or whether disks, nodes, or even entire racks fail. As long as k of the k+m fragments survive, reconstruction is mathematically possible. This is what separates erasure coding from a simple mirrored RAID disk: the protection doesn’t depend on which specific fragment is lost.

How erasure coding works under the hood

The math in one paragraph

Reed-Solomon, published by Irving Reed and Gustave Solomon in 1960 (see Wikipedia), treats each data fragment as a point on a polynomial over a finite field, typically GF(256) because it fits perfectly in a byte. With k points, you have enough to define a polynomial of degree k-1; the m parity fragments are that same polynomial evaluated at m additional points. Losing fragments is like erasing points from the graph: if k points still remain, the polynomial, and therefore the original data, can be reconstructed through interpolation.

Encoding and decoding

Encoding multiplies the k data fragments by a generator matrix (Vandermonde or Cauchy, both of which guarantee that any subset of rows is invertible) to produce the m parity fragments. Decoding does the reverse: using the fragments that survived, it builds a square submatrix, inverts it over the finite field, and multiplies to recover the lost fragments.

💡 Tip: before choosing k and m in production, first calculate how many simultaneous failures your real infrastructure can tolerate (disks per rack, racks per zone), and only then set m, not the other way around.

flowchart LR
 A["Original file"] --> B["Reed-Solomon encoder"]
 B --> C["Fragment D1"]
 B --> D["Fragment D2"]
 B --> E["Fragment D3"]
 B --> F["Parity P1"]
 B --> G["Parity P2"]
 subgraph Storage
 C
 D
 E
 F
 G
 end

Practical examples with code

Hello world with reedsolo

The reedsolo library implements Reed-Solomon in pure Python. Install it with pip install reedsolo and try the bare minimum: encode a string, corrupt a few bytes, and decode it.

from reedsolo import RSCodec

# 10 parity bytes added to the message
rsc = RSCodec(10)

mensaje = b"hello from programacion"
codificado = rsc.encode(mensaje)

# We simulate 3 damaged bytes, within the tolerated limit (10 // 2 = 5)
danado = bytearray(codificado)
danado[0] ^= 0xFF
danado[5] ^= 0xFF
danado[9] ^= 0xFF

recuperado, _, _ = rsc.decode(danado)
print(recuperado)  # b'hello from programacion'

RSCodec(10) adds 10 parity bytes, which allows correcting up to 5 corrupted bytes at unknown positions: each error first has to be located and then corrected, which is why the correction capacity is half the parity. The printed result is the original message intact.

Sharding a real file with simulated failures

The real use case doesn’t correct individual bytes: it splits a file into complete fragments across disks or nodes, and tolerates losing entire fragments. Using the same library, splitting into shards manually:

from reedsolo import RSCodec
import os

K, M = 6, 3  # 6 data fragments, 3 parity fragments (RS 6-3, same as HDFS)
rsc = RSCodec(M)

datos = os.urandom(1024 * 1024)  # sample 1 MB file
tam_fragmento = len(datos) // K
fragmentos = [datos[i*tam_fragmento:(i+1)*tam_fragmento] for i in range(K)]

# We encode byte by byte across the K fragments
# and keep only the last M parity bytes at each position
paridad = [rsc.encode(bytes([f[i] for f in fragmentos]))[-M:]
           for i in range(tam_fragmento)]

print(f"Data fragments: {K}, parity fragments: {M}")
print(f"Storage overhead: {M/K:.0%}")

With RS 6-3 the overhead is 3/6 = 50%, far below the 200% of storing three complete copies. That calculation, m/k, is the one to memorize before choosing a scheme.

How to get started

To experiment with erasure coding on your own machine without installing Hadoop or touching a cluster, three steps are enough:

1. Install the library: pip install reedsolo
2. Choose your k+m scheme based on how many simultaneous failures you want to tolerate. Rule of thumb: m equals the number of simultaneous failures to tolerate.
3. Run the sharding script above, then manually delete one or two fragments stored on disk and confirm that the decoder still reconstructs the original.

If you’d rather try it directly on a real distributed file system, HDFS has had erasure coding available as a policy since Hadoop 3.0. To confirm which policy runs on a directory:

hdfs ec -getPolicy -path /datos/produccion
hdfs ec -listPolicies

The first command shows whether that folder uses classic replication or an RS-6-3-1024k policy (Reed-Solomon 6+3 with 1 MB cells). The second lists all available policies in the cluster, documented in the official HDFS Erasure Coding guide.

Real-world use cases

Erasure coding isn’t an academic curiosity: it powers infrastructure used every day.

• HDFS: since Hadoop 3.0 it offers Reed-Solomon policies as an alternative to 3x replication, documented in the official guide. The default RS-6-3 policy pays 50% overhead versus the 200% of three copies.
• RAID 6: tolerates two broken disks at once by computing two independent parity blocks (P and Q) for each row of data, unlike RAID 5, which tolerates only one.
• S3-style object storage: object storage providers use variants of erasure coding across availability zones to maintain durability without tripling infrastructure cost.
• QR codes and barcodes: use Reed-Solomon to remain readable even when a corner of the code is broken, dirty, or covered.
• CDs and DVDs: the CIRC standard (Cross-Interleaved Reed-Solomon Coding) corrects physical scratches on the disc using the same math.
• Backblaze Vaults: the backup company explains in its technical blog how it uses Reed-Solomon to spread each file across dozens of servers and tolerate losing several disks without losing data.

Common mistakes and best practices

Erasure coding isn’t free or universal. These are the most common gotchas:

• CPU cost during reconstruction: rebuilding a lost fragment requires inverting a matrix and interpolating over GF(256), a computational cost that simple replication doesn’t have, since there it’s enough to just read the copy. In clusters with frequent disk failures, that cost adds up.
• Small files, high relative overhead: a file of a few KB split into 6 fragments leaves nearly empty fragments; the metadata overhead outweighs the space savings. That’s why HDFS applies erasure coding mainly to cold or rarely accessed data, and still uses 3x replication for hot data.
• Read latency during failures: reading a file with missing fragments requires rebuilding it before serving it, which adds latency compared to reading directly from a healthy replica.
• Not all m values are equal: an RS 10-4 scheme tolerates 4 failures, but if those 4 disks are in the same rack and the entire rack goes down, it doesn’t matter how much parity you have. The physical distribution of fragments matters as much as the math.

⚠️ Watch out: erasure coding protects against fragment loss, not against undetected silent corruption. Without per-fragment checksums, a corrupted byte that wasn’t marked as “lost” can slip into the reconstruction.

Comparison with alternatives

Scheme	Space overhead	Failures tolerated	When to use it
3x replication	200%	2 copies	Hot data, prioritizing read speed over cost
RAID 5	1 parity disk	1 disk	Small arrays where losing 2 disks at once is unlikely
RAID 6	2 parity disks	2 disks	Large arrays where reconstruction time is long
Erasure coding RS 6-3	50%	3 fragments	Cold or rarely accessed data in large-scale distributed storage

Going deeper

Why GF(256) instead of normal arithmetic

If common integer arithmetic were used, adding or multiplying fragments could overflow the range of a byte (0 to 255) and lose information. Galois fields GF(2⁸) solve this: every addition, subtraction, multiplication, and division between bytes results in another valid byte, with no overflow. It’s the same algebraic construction that AES uses for its S-box.

Systematic vs non-systematic codes

A code is “systematic” when the first k encoded fragments are literally the original unmodified data, and only the last m are computed parity. This is the approach used by HDFS and RAID: if nothing is missing, the data fragments are read directly, without decoding anything. Non-systematic codes mix data and parity across all fragments, useful in communication channels but rare in storage because they force decoding every time, even when it isn’t needed.

💭 Key takeaway: the same finite field math that reconstructs a file in HDFS is what makes a scratched CD still sound fine.

A historical fact that’s rarely mentioned: NASA space probes have been transmitting data encoded with Reed-Solomon since the 1970s to tolerate signal noise in deep space, the same family of codes that today protects hard drives in a data center.

sequenceDiagram
 participant Client
 participant Coordinator
 participant HealthyNode1
 participant HealthyNode2
 participant DownNode
 Client->>Coordinator: requests to read file
 Coordinator->>DownNode: requests fragment D4
 DownNode--xCoordinator: no response, disk broken
 Coordinator->>HealthyNode1: requests fragment D5
 Coordinator->>HealthyNode2: requests parity P1
 Coordinator->>Coordinator: reconstructs D4 through interpolation
 Coordinator-->>Client: returns complete file

flowchart TD
 A["1 TB of useful data"] --> B["3x replication"]
 A --> C["Erasure coding RS 6-3"]
 B --> D["3 TB on disk"]
 C --> E["1.5 TB on disk"]

📖 Summary on Telegram: View summary

Your next step: install pip install reedsolo, run this article’s sharding script, and manually delete one of the fragments stored on disk to confirm that reconstruction works before taking it to a real system.

Frequently Asked Questions

Does erasure coding completely replace replication?

Not always. Systems like HDFS combine both: 3x replication for frequently accessed hot data, and erasure coding for cold data where space savings matter more than read speed.

How many fragments can I lose with an RS 6-3 scheme?

Up to 3 of the 9 total fragments (6 data plus 3 parity), regardless of which ones. Losing a fourth fragment makes the file no longer recoverable with that scheme.

Does erasure coding work the same for small files as for large files?

Not equally well. With files of just a few kilobytes, the metadata overhead and fragmentation outweigh the space savings; that’s why in practice it’s mainly applied to data above a certain minimum size.

What’s the difference between erasure coding and a simple CRC-style checksum?

A CRC only detects that an error occurred; it doesn’t correct it or reconstruct lost data. Reed-Solomon can detect and correct errors, or directly reconstruct entire missing fragments, as long as enough fragments survive.

Do RAID 6 and HDFS erasure coding use the same algorithm?

Both are based on Reed-Solomon over Galois fields, but with different parameters: RAID 6 typically uses 2 fixed parity disks, while HDFS lets you choose the k+m scheme based on the configured policy.

References

• Reed-Solomon error correction (Wikipedia): history, math, and applications of the code published in 1960.
• HDFS Erasure Coding (Apache Hadoop): official guide to RS-6-3 policies and administration commands.
• reedsolo (GitHub): pure Python implementation used in this article’s code examples.
• Reed-Solomon (Backblaze Blog): technical explanation of how a backup provider applies erasure coding in production.
• RAID (Wikipedia): RAID levels, including RAID 6’s double parity.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Imagen destacada: Foto de Marc PEZIN en Unsplash