You Can Lose a Third of Your Storage and Recover Every Byte

Start with a 400 MB file.

Cut it into four equal 100 MB pieces. Call them D0, D1, D2, and D3. Then calculate two more 100 MB pieces, P0 and P1, from the first four. Store all six pieces separately.

You now occupy 600 MB. Delete any two pieces. That is 200 MB, exactly one-third of what was stored. The original 400 MB file can still be recovered byte for byte.

That is the entire claim. The rest of this article explains why it is true, where it stops being true, and what the cleverness costs.

The idea without coding theory

The two extra pieces are not ordinary copies. Each is a different summary of all four data pieces.

Think of the original pieces as four unknown values. The stored system has six clues:

• four clues reveal an original value directly;
• two clues describe carefully chosen relationships among all four values.

You only need four independent clues to determine four unknowns. If any two of the six disappear, four clues remain. The recovery rules are designed so that every possible group of four is independent.

That last sentence does the heavy lifting. Two identical summaries would not help: they would repeat the same clue. The two recovery pieces must encode different information, and they must be chosen so no possible pair of losses leaves an unsolvable puzzle.

This is what a 4+2 erasure code means:

• 4 data pieces contain the original bytes;
• 2 parity pieces contain recovery information;
• any 4 valid pieces can recreate the data;
• losing 3 pieces is beyond the promise.

The technical name for each piece is a shard. One group of matching data and parity shards is a stripe.

Three examples make “any two” less abstract:

1. Both parity shards disappear. All four original data shards remain, so the file is read normally. The parity can be recalculated later.
2. One data shard and one parity shard disappear. Three original pieces and one recovery piece remain. The recovery piece contains enough information to rebuild the missing quarter.
3. Two data shards disappear. Two original pieces and both recovery pieces remain. Each recovery piece supplies a different relationship between the missing values. Together they determine both.

The third case is the important one. If P0 and P1 stored the same summary, they would provide the same relationship twice and the missing pair would remain ambiguous. Erasure coding constructs them differently so the remaining information is useful for every possible pair of losses, not only the easy ones.

The picture operates on equal-sized shards, but a real file can be any length. The final data shard is padded when necessary, and the original length is stored so recovery knows exactly where the file ends.

What “lose one-third” actually means

For the 400 MB example:

The missing 200 MB is one-third of the encoded stripe. It does not mean that any random third of the bytes on a disk can vanish. The losses must remove no more than two complete, correctly identified shards from the same valid stripe.

The survivors do not necessarily contain four readable quarters of the file. They may include parity. Recovery turns the four surviving clues back into the four original data shards and then joins them.

There are also two non-negotiable conditions:

1. The system must know which shards are missing or damaged.
2. The shards must be placed across genuinely independent failure domains.

If corruption silently presents itself as valid data, the decoder may trust a lie. If three shards share one machine, one machine failure can exceed the two-shard budget. The coding can be mathematically perfect while the storage system around it is wrong.

What this protects and what it does not

Erasure coding protects against a defined number of unavailable or rejected shards. It is not a general undo button.

• It is not compression. The encoded data is larger than the original.
• It is not encryption. Its goal is recovery, not secrecy.
• It is not a backup. Deleting or overwriting all six shards destroys the data consistently.
• It does not automatically detect corruption. Checksums or authentication must identify bad shards before decoding.
• It does not fix bad placement. Correlated failures can remove too many shards at once.

Backups, version history, integrity checks, access control, and geographic separation still have separate jobs.

Why not just make copies?

Copies are simpler. Three-way replication stores the whole file three times. Lose two well-placed copies and the third still works. Reads are direct and repair means copying bytes from a survivor.

The cost is capacity:

A full 4+2 stripe uses half as much raw capacity as three copies. The saving is real, but it is not free. Reads during failure need reconstruction, repairs pull data from several survivors, writes calculate parity, and placement becomes part of correctness.

Try the promise

Select any two shards below. Four survivors are enough. Select a third and the guarantee ends.

If that behavior makes sense, you already understand the purpose of erasure coding. Everything below is the machinery that makes “any four” true.

The machinery starts with one XOR parity shard

Start smaller: four data shards and one parity shard.

At every byte offset, XOR the four data bytes:

P = D0 XOR D1 XOR D2 XOR D3

XOR is its own inverse. If D2 disappears:

D2 = P XOR D0 XOR D1 XOR D3

Here is one byte position with actual values:

D0 = 0x57
D1 = 0x2a
D2 = 0xc1
D3 = 0x0f

P  = 0x57 XOR 0x2a XOR 0xc1 XOR 0x0f
   = 0xb3

D2 = 0xb3 XOR 0x57 XOR 0x2a XOR 0x0f
   = 0xc1

Repeat that operation independently at every byte offset and the entire missing shard returns. This is not a toy analogy; the same idea is used in single-parity storage systems.

One equation solves one unknown.

Lose two data shards and XOR parity leaves two unknowns inside one equation:

P XOR D0 XOR D3 = D1 XOR D2

There are many pairs of values with that XOR. The decoder cannot know which pair was original. Saving the same parity a second time does not help; two copies of one equation are still one independent equation.

A second loss needs a second equation

To recover two missing data shards, we need two independent equations. Conceptually:

P0 = a×D0 + b×D1 + c×D2 + d×D3
P1 = e×D0 + f×D1 + g×D2 + h×D3

When D1 and D2 vanish, move the known terms to the other side. Two equations remain for two unknowns. Solve them and both shards return.

The awkward detail is that our values are bytes. Normal integer arithmetic does not stay inside one byte, and “just take everything modulo 256” does not give every nonzero coefficient a multiplicative inverse. Matrix inversion needs those inverses.

Reed-Solomon moves the arithmetic into a finite field, usually GF(2^8) for byte-oriented storage. It contains exactly 256 values, so every result remains byte-shaped. Addition is XOR. Every nonzero element has a multiplicative inverse. Division and Gauss-Jordan elimination now work.

You can use the field operations without knowing how the field is constructed.

1 + x³ + x⁴

x⁸ + x⁴ + x³ + x² + 1   // 0x11d

func gfMul(a, b byte) byte {
    var product uint16
    left, right := uint16(a), uint16(b)

    for right != 0 {
        if right&1 != 0 {
            product ^= left
        }
        right >>= 1
        left <<= 1
        if left&0x100 != 0 {
            left ^= 0x11d
        }
    }
    return byte(product)
}

The matrix that makes six shards

Put the four data shards into a column vector. Encoding is one matrix multiplication:

encoded_shards = G × data_shards

G has six rows and four columns. We choose its first four rows as the identity matrix:

    [ 1 0 0 0 ]   -> D0
    [ 0 1 0 0 ]   -> D1
G = [ 0 0 1 0 ]   -> D2
    [ 0 0 0 1 ]   -> D3
    [ a b c d ]   -> P0
    [ e f g h ]   -> P1

This is systematic encoding. The first four outputs are the original data, unchanged. Healthy full reads can concatenate D0 through D3 without decoding.

The parity coefficients cannot be random decorative letters. We need every possible set of four rows from G to form an invertible 4×4 matrix. That is the property that makes any two shard erasures recoverable.

The companion program uses one fixed set of coefficients chosen to guarantee that every four-row survivor matrix can be inverted:

    [   1   0   0   0 ]
    [   0   1   0   0 ]
G = [   0   0   1   0 ]
    [   0   0   0   1 ]
    [  71 167 122 186 ]
    [ 167  71 186 122 ]

Those integers are field elements, not ordinary multipliers.

At one particular byte offset, the encoder takes four input bytes and performs the bottom two dot products:

P0[i] =  71×D0[i] XOR 167×D1[i] XOR 122×D2[i] XOR 186×D3[i]
P1[i] = 167×D0[i] XOR  71×D1[i] XOR 186×D2[i] XOR 122×D3[i]

Each multiplication uses the field operation from the optional section. Move to the next byte offset and use the same coefficients again. There is no cross-byte dependency in this block formulation, which is why implementations can divide large buffers into chunks, run vector instructions, and compute multiple parity outputs in parallel.

Real objects can be larger than one stripe. The storage system repeats this operation over the file and records which shards belong together.

Recovery is encoding backwards

Suppose D1 and P0 are missing. The survivors are D0, D2, D3, and P1.

Take the four rows of G that produced those survivors. Keep them in the same shard-index order:

G_survivors =
    [   1   0   0   0 ]   // D0
    [   0   0   1   0 ]   // D2
    [   0   0   0   1 ]   // D3
    [ 167  71 186 122 ]   // P1

By construction, this survivor matrix is invertible. Recover the original data:

data_shards = inverse(G_survivors) × surviving_shards

Then apply the original parity rows to regenerate any missing parity shard. Concatenate the four data shards and trim the zero padding using the stored original length.

Matrix inversion happens once per erasure pattern, not once per byte. The same inverse applies across every byte offset in the stripe.

The core of the Go reconstruction reads almost like the algorithm:

for row, shardIndex := range present {
    copy(survivorMatrix[row], generator[shardIndex])
    survivorShards[row] = shards[shardIndex]
}

decodeMatrix, err := invertMatrix(survivorMatrix)

for row := 0; row < dataShards; row++ {
    encodeRow(recovered[row], decodeMatrix[row], survivorShards)
}

The complete dependency-free implementation and tests are available on the companion code page.

Prove the title, exhaustively

A 4+2 stripe has 15 distinct pairs of shards that can disappear. Testing one friendly pair would prove very little, so the companion test removes each of the 15 pairs in turn, reconstructs the stripe, and compares every byte with the original. It also checks that every possible four-row survivor matrix is invertible and that a third missing shard fails cleanly.

The result:

verified all 15 two-shard loss patterns; every byte recovered

The limit is exact. Two missing shards leave four equations for four source shards. A third erasure leaves only three equations, so the original four shards can no longer be determined.

What the cleverness costs

Erasure coding buys capacity efficiency by spending work elsewhere:

• Healthy reads stay simple. Because the code is systematic, the system can read D0 through D3 directly.
• Degraded reads do more work. A missing data shard must be reconstructed from four survivors.
• Writes calculate parity. Small updates may need old data or parity before the affected fragments can be rewritten.
• Repairs fan out. Rebuilding one shard reads from several surviving locations instead of copying one replica.

Replication spends more capacity to keep these paths simple. Reed-Solomon saves capacity but makes failures and repairs more expensive. That is the trade: 1.5 TB instead of 3 TB in the opening comparison, in exchange for more CPU, network traffic, and coordination.

What the matrix cannot solve

The decoder can recover from two missing shards. It cannot decide whether those shards were placed sensibly. If three shards share one machine, one machine failure still defeats the code.

It also needs to know which inputs are bad. Silent corruption that looks valid can poison reconstruction, so real systems checksum each shard and reject damaged ones before decoding. Updates must keep data and parity consistent as well; mixing new data with old parity can produce convincing but incorrect bytes after a later failure.

The matrix provides the recovery guarantee. Placement, integrity checks, and careful updates keep its assumptions true.

That is erasure coding in one sentence: store extra equations instead of extra copies, then solve those equations when pieces disappear.