How AWS S3 Uses Erasure Coding to Protect Your Data

When a file is uploaded to an Amazon S3 bucket, it is automatically stored across multiple Availability Zones, S3 is engineered to deliver 11 nines of durability (99.999999999%), which often leads beginners to assume that AWS simply stores three full copies of the same object — one in each Availability Zone.

However, S3 does not rely on naïve replication. Storing raw copies is inefficient, increases storage costs, and still exposes risk: if all three replicas were ever corrupted or lost at the same time, the object would be unrecoverable.

Instead, AWS uses far more advanced techniques — specifically erasure coding and Reed–Solomon encoding — to distribute data and parity fragments across Availability Zones. This approach drastically reduces redundancy while still ensuring that even if entire AZs or multiple fragments fail, S3 can automatically reconstruct the object without any data loss.

What is Erasure Coding?

Erasure Coding is a data-protection technique in which data is divided into multiple fragments and supplemented with additional parity fragments. Even if several of these fragments are lost or corrupted, the original data can still be reconstructed mathematically.

How Does Erasure Coding Work?

When a file is uploaded, S3 breaks it into smaller pieces and generates extra parity pieces using mathematical algorithms (often Reed–Solomon codes). These pieces are then distributed across multiple Availability Zones.

For example, consider uploading a 100 MB object:

1. Data is split into smaller blocks
S3 may divide the file into 10 data blocks, each containing a portion of the original file

2. Parity blocks are generated
It then computes 4 additional parity blocks using erasure-coding math.

3. Blocks are distributed across Availability Zones
All 14 blocks (10 data + 4 parity) are stored across multiple storage nodes in three or more AZs.

To understand the idea behind erasure coding, let’s start with a very basic example using small numbers.

Suppose we want to store two pieces of data

D1 = 10;
D2 = 20;

If we store only these two values and one of them is lost, the data becomes unrecoverable.
To avoid this, we introduce a parity value.

We compute a simple parity using:

P = D1 + D2
P = 10 + 20 = 30

Assume second disk value is lost to recover the lost data

P = D1 + D2

D2 = P - D1

Now substitute the known values:

D2 = 30 - 10 = 20

The missing data is fully reconstructed.

Erasure Coding Example (3 Data Chunks → 2 Parity Chunks)

To illustrate how real erasure-coding systems work (similar to those used in cloud storage), let’s walk through a simplified Reed–Solomon–style example

We start with three data values (data chunks):

D1 = 5 
D2 = 7
D3 = 9

Reed–Solomon encoding treats these values as points on a polynomial.
For simplicity, imagine we evaluate this polynomial at five points:

F(1), F(2), F(3) → Data chunks

F(4), F(5) → Parity chunks

For demonstration, suppose the polynomial is:

F(x) = x² + 3x + 1

I have taken a polynomial with degree 3 since i used 3 chunks usually it should be ( k — 1 )

Evaluate F(x) at x = 1 to 5:

| x | F(x) | Purpose  |
| - | ---- | -------- |
| 1 | 5    | Data 1   |
| 2 | 11   | Data 2   |
| 3 | 19   | Data 3   |
| 4 | 29   | Parity 1 |
| 5 | 41   | Parity 2 |

Simulate a Failure

Assume two chunks are lost:

F(2) = 11
F(4) = 29

Remaining chunks:

F(1) = 5 
F(3) = 19
F(5) = 41

A polynomial of degree 2 can be reconstructed from any 3 points, so recovery is still possible.Rebuild the Original Polynomial

We know:

F(x) = ax² + bx + c

Using the three known points:

From F(1) = 5

a + b + c = 5          ...(1)

From F(3) = 19

9a + 3b + c = 19       ...(2)

From F(5) = 41

25a + 5b + c = 41      ...(3)

Solve the equations

(2) − (1):

8a + 2b = 14
4a + b = 7              ...(4)

(3) − (1):

24a + 4b = 36
6a + b = 9              ...(5)

(5) − (4):

2a = 2
a = 1

Substitute a = 1 into (4):

4(1) + b = 7
b = 3

Substitute a = 1, b = 3 into (1):

1 + 3 + c = 5
c = 1

Recover the Missing Chunks

Now evaluate the missing values:

Recover F(2) and Recover F(4):

F(x) = ax² + bx + c

now substitute the x and the values a, b, c

F(2) = 4 + 6 + 1 = 11
F(4) = 16 + 12 + 1 = 29

Both lost chunks are reconstructed exactly.

Now Let’s Jump to the real calculation on how the files are stored across multiple location

Consider uploading a 4 MB file to cloud storage.

4 MB = 4,194,304 bytes

The storage system divides each object internally into fixed-size stripes of 64 KB (this is just an example; the actual size may vary).

size = 64 KB = 65,536 byte

1. Calculate the total stripes

4,194,304 bytes(4Mb) ÷ 65,536 bytes(64Kb) = 64 stripes

So the object is split into 64 stripes.

2. Erasure Coding Inside Each Stripe

Each stripe is then erasure-coded independently, In this example, the system uses a 6 data + 3 parity scheme

Get Vignesh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

6 data blocks ,3 parity blocks ,Total = 9 blocks per stripe

The usable data per stripe is evenly divided across the 6 data blocks:

65,536 bytes ÷ 6 ≈ 10,922 bytes per data block(approximately)

(Any remaining bytes are handled internally via padding).

Stripes layout

┌────────────── Stripe 0 (64 KB) ──────────────┐
│                                              │
│ D0 │ D1 │ D2 │ D3 │ D4 │ D5 │  P0 │  P1 │ P2 │
│≈10k│≈10k│≈10k│≈10k│≈10k│≈10k│  parity blocks │
└──────────────────────────────────────────────┘

┌────────────── Stripe 63(64 KB) ──────────────┐
│                                              │
│ D0 │ D1 │ D2 │ D3 │ D4 │ D5 │  P0 │  P1 │ P2 │
│≈10k│≈10k│≈10k│≈10k│≈10k│≈10k│  parity blocks │
└──────────────────────────────────────────────┘

D0–D5 → Data blocks (split from the stripe payload) P0–P2 → Parity blocks (computed mathematically)

how parity are generate the parity are generated (Real math)

S3 uses the Reed–Solomon Ersure coding and Vendermonde Matrix

3. Reed — solomon erasure coding included Galois Field GF (2⁸) which does ⊕ for normal addition and multiplication in table based format

let dive deep into how the parity is generated

let’s take stripe 0 in this example ,which has 6 data shards and 3 parity block each shard has data from 0 to 10921

┌────────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ j      │ D0  │ D1  │ D2  │ D3  │ D4  │ D5  │
├────────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 0      │  a  │  b  │  c  │  d  │  e  │  f  │
│ 1      │  g  │  h  │  i  │  j  │  k  │  l  │
│ 2      │  m  │  n  │  o  │  p  │  q  │  r  │
│ ...    │ ... │ ... │ ... │ ... │ ... │ ... │
│ j      │ x0  │ x1  │ x2  │ x3  │ x4  │ x5  │
└────────┴─────┴─────┴─────┴─────┴─────┴─────┘

assume it like a table ( the values in the table are placeholders values ) and for each row the parity is created it will be having 3 parity blocks

with the help of the vendermonde matrix ( it has distinct element it help use the achieve the recovery of lost data )

4. parity calculations

Let j=10 The value D[0] for 10 is 0x10 also the same for the other below defined values

D0 = 0x01 - 1
D1 = 0x02 - 2
D2 = 0x03 - 3
D3 = 0x04 - 4
D4 = 0x05 - 5
D5 = 0x06 - 6 

to build the matrix choose 6 distinct values should be in the range GF (2ˆ8)

α = [1, 2, 3, 4, 5, 6]

so the matrix will be looking like

P0 = [1, 1, 1, 1, 1, 1]
P1 = [1, 2, 3, 4, 5, 6]
P2 = [1, 4, 9, 16, 25, 36]

the parity rows are obtained by substituting in the α in the above formula

[ P0 ]   [ 1  1  1   1   1   1 ]   [ D0 ]
[ P1 ] = [ 1  2  3   4   5   6 ] × [ D1 ]
[ P2 ]   [ 1  4  9  16  25  36 ]   [ D2 ]
                                   [ D3 ]
                                   [ D4 ]
                                   [ D5 ]

the above are the parity rows and the matrix formed from thr parity rows

let make it simple by using the formula to calcluate the parity rows one by one

P0[j] = 1·D0[j] ⊕ 1·D1[j] ⊕ 1·D2[j] ⊕ 1·D3[j] ⊕ 1·D4[j] ⊕ 1·D5[j]

P1[j] = 1·D0[j] ⊕ 2·D1[j] ⊕ 3·D2[j] ⊕ 4·D3[j] ⊕ 5·D4[j] ⊕ 6·D5[j]

P2[j] = 1·D0[j] ⊕ 4·D1[j] ⊕ 9·D2[j] ⊕ 16·D3[j] ⊕ 25·D4[j] ⊕ 36·D5[j]

Addition (⊕) = bitwise XOR , Multiplication = polynomial multiplication modulo the irreducible polynomial

multiplication ()

P0 (simple XOR)

P0 = 01 ⊕ 02 ⊕ 03 ⊕ 04 ⊕ 05 ⊕ 06
   = 07

convert the decimal to binary and perform the XOR operation

P1 (weighted)

1·01 = 01
2·02 = 04
3·03 = 06 ⊕ 03 = 05
4·04 = 10
5·05 = 14 ⊕ 05 = 11
6·06 = (4·06) ⊕ (2·06) = 18 ⊕ 0C = 14

let me explain how the multiplication takes place

 (3.03) is splitted into (2.03) ⊕ (1.03) 
 (2.03) - 3 multiplied 2 (i.e) which is leftshift << 1 (by 1 bit)
  3 << 1 = 00000110 (6)

now we got the answer for (2.03) = 00000110 

00000110 = (2.03)
       ⊕
00000011 = (1.03)
--------
00000101 = 5 
--------

the same calculation applies for all the above weighted P1

P1 = 01 ⊕ 04 ⊕ 05 ⊕ 10 ⊕ 11 ⊕ 14
   = 15

P2 (squared coefficients)

1·01  = 01
4·02  = 08
9·03  = (8·03) ⊕ 03 = 18 ⊕ 03 = 1B
16·04 = 40
25·05 = 16·05 ⊕ (8·05 ) ⊕ (1·05) = 41
36·06 = (32·06) ⊕ (4·06) = C0 ⊕ 18 = D8

P2 = 01 ⊕ 08 ⊕ 1B ⊕ 40 ⊕ 41⊕ D8
   = CB

what S3 will store in one stripe is these 9 shards are stored across 3 AZs.

D0 = 01
D1 = 02
D2 = 03
D3 = 04
D4 = 05
D5 = 06
P0 = 07
P1 = 15
P2 = CF

5.data recovery of the lost nodes

Lost shards:

D1, D4, P1

Survivors (6 shards):

D0, D2, D3, D5, P0, P2

This is worst-case: mixed data + parity loss

from p0

Unknowns :D1, D4
Known equations:

D1 ⊕ D4 = P0 ⊕ (D0 ⊕ D2 ⊕ D3 ⊕ D5)
        = 07 ⊕ (01 ⊕ 03 ⊕ 04 ⊕ 06)
        = 07 ⊕ 00
        = 07

D1 ⊕ D4 = 07 --equation 1

from p2

P2 = 1*D0 ⊕ 4*D1 ⊕ 9*D2 ⊕ 16*D3 ⊕ 25*D4 ⊕ 36*D5

Unknown data: D1, D4
known equation: 4*D1 ⊕ 25*D4 = P2 ⊕ (1*D0 ⊕ 9*D2 ⊕ 16*D3 ⊕ 36*D5)

(1.01) = 1

(4·02) = 08

(9.03) = (8.03) ⊕ 03 
       = 1B 

16·04 = (2^4). 04
        16₁₆ = 0x10 = 00010000₂ 
        04₁₆ = 0x04 = 00000100₂
         so we need 4 times left shift 
         00000100 << 4 = 01000000₂ 
      = 40₁₆

25·05 = 16·05 ⊕ (8·05 ) ⊕ (1·05)
      = 41

36·06 = (32·06) ⊕ (4·06)
        (32·06) = (2^5).06
          so we need 5 times left shift
          06 << 5 = 11000000₂ 

        (4·06) = (2^2).06  
          so we need 2 times left shift  
          06 << 2 = 00011000₂
      = D8 

(1*D0 ⊕ 9*D2 ⊕ 16*D3 ⊕ 36*D5) = 82 

(1*D0 ⊕ 9*D2 ⊕ 16*D3 ⊕ 36*D5) = 82 and P2 =CF by substitution

now the equation becomes,
4·D1 ⊕ 25·D4 = CF ⊕ 82

4·D1 ⊕ 25·D4 = 4D -- equation 2 

The both equations are :

D1 ⊕ D4 = 07 — equation 1
4·D1 ⊕ 25·D4 = 4D — equation 2

from the above equation D1 = D4 ⊕ 07 

   4·(D4 ⊕ 07) ⊕ 25·D4 = 4D

   (4·D4) ⊕ (4·07) ⊕ (25·D4) = 4D

07 = 00000111
 4 = 00000100

(4·07) = 07 << 2 
       = 00011100
       = 1C

(4 ⊕ 25).D4 ⊕ 1C = 4D

(4 ⊕ 25).D4 = 1C ⊕ 4D 


  04 = 00000100
  25 = 00010101
  ⊕   
     = 00010001 = 11 (hex) 

  4D ⊕ 1C = 51

  11.D4 = 51 

The final equation is 11.D4 = 51

now the inverse multiplication occurs

basically in GF (2⁸) a . a-¹= 01

11 · 11⁻¹ = 01   (in GF(2⁸))

We multiply both sides by 11⁻¹:

D4 = 51 · 11⁻¹ 

what is the value for the 11⁻¹ ( inverse )

11 (hex) → binary → polynomial

0x11 = 00010001₂
     = x⁴ + 1

11⁻¹ = 94

The inverse values are pre calculate and kept in the tables for fast lookups

D4 = 51 . 94 , D4 = 05

substitute in the equation D1 ⊕ D4 = 07

D1 = 07 ⊕ 05

we have calculated the D1= 02 and D4 =05 from the remaining shards

The missing parity P1 will be generated with the shards