Erasure Coding For Dummies

​

Eric Olszewski

​

​

What is Erasure Coding?

Erasure Coding is a data protection scheme that shatters data into shards (fragments) that are encoded with parity (redundant data) and then stores those shards across multiple storage media and locations.

Why Does it Matter?

• You only need a subset of the shards to rehydrate data.
• You can replace failed components when convenient, without taking the system offline.
• The compromise of a shard of a file is much less worrisome than the compromise of the file, itself.

Decentralize everything!

Basics

Data

Nodes

Basics (cont’d)

Data

Nodes

Example 1

Data

Nodes

75

Example 1 (cont’d)

Data

Nodes

75

x+y=12

2x+2y=24

3x+3y=36

Reed-Solomon Codes (1960)

Example 2

Data

Nodes

ABDEFGHIJKLMNOP

DATA

DATA

DATA

DATA

PARITY

PARITY

Example 2 (cont’d)

Data

Generator Matrix

Data + Parity

X

=

Example 2 (cont’d)

Data

Nodes

ABDEFGHIJKLMNOP

ABCD

IJKL

EFGH

MNOP

51525349

55565725

Example 2 (cont’d)

X

=

Example 2 (cont’d)

X

=

Example 2 (cont’d)

X

=

Example 2 (cont’d)

X

=

Additional Resources

Special thanks to all the members of the open source community - we are nothing without them.

• Wikipedia
• A Note On Data Availability and Sharding (Vitalik)
• Erasure Coding Implementation (Vitalik)
• BackBlaze Reed-Solomon Encoding Implementation