Reed-Solomon

Introduction:

Erasure Codes(based on Reed-Solomon Codes) engine in pure Go.

It's a kind of Systematic Codes, which means
the input data is embedded in the encoded output .

High Performance: dozens GiB/s per physics core.

High Reliability:

At least two companies are using this library in their storage system.
(More than dozens PB data)

Full test of galois field calculation and invertible matrices
(You can also find the mathematical proof in this repo).

Based on Klauspost ReedSolomon
& Intel ISA-L with some additional changes/optimizations.

It's the backend of XRS (Erasure Codes
which can save about 30% I/O in reconstruction process).

Specification

Math

Coding over in GF(2^8).

Primitive Polynomial: x^8 + x^4 + x^3 + x^2 + 1 (0x1d).

Cauchy Matrix is the generator matrix.

Any sub-matrix of encoding matrix is invertible (See the proof here).

Galois Field Tool: Generate primitive polynomial,
and it's log, exponent, multiply and inverse tables etc.

Inverse Matrices Tool: Calculate the number of inverse matrices
with specific data & parity number.

XP has written an excellent article (Here, in Chinese) about how
Erasure Codes works and the math behind it. It's a good start to read it.

Accelerate

SIMD: Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions

Reduce memory I/O: Write cache-friendly code. In the process of two matrices multiply, we will have to
read data times, and keep the temporary results, then write to memory. If we could put more data into
CPU's Cache but not read/write memory again and again, the performance should
improve a lot.

Cache inverse matrices: It'll save thousands ns, not much, but it's still meaningful
for small data.

...

Here (in Chinese) is an article about
how to write a fast Erasure Codes engine.
(Written by me years ago, need update, but the main ideas still work)

Performance

Performance depends mainly on:

CPU instruction extension.

Number of data/parity row vectors.

Platform:

goos: linux
goarch: amd64
pkg: github.com/templexxx/reedsolomon
cpu: 12th Gen Intel(R) Core(TM) i7-12700K

All test run on a single Core.

Encode:

I/O = (data + parity) * vector_size / cost

Data	Parity	Vector size	AVX2 I/O (MiB/S)	no SIMD I/O (MiB/S)
10	2	8KiB	35640.29	2226.84
10	2	1MiB	30136.69	2214.45
10	4	8KiB	19936.79	1294.25
10	4	1MiB	17845.68	1284.02
12	4	8KiB	19072.93	1229.14
12	4	1MiB	16851.19	1219.29

Reconstruct:

I/O = (data + reconstruct_data_num) * vector_size / cost

Data	Parity	Vector size	Reconstruct Data Num	AVX2 I/O (MiB/s)
10	4	8KiB	1	55775.91
10	4	8KiB	2	33037.90
10	4	8KiB	3	23917.16
10	4	8KiB	4	19363.26

Update:

I/O = (2 + parity_num + parity_num) * vector_size / cost

Data	Parity	Vector size	AVX2 I/O (MiB/S)
10	4	8KiB	55710.83

Replace:

I/O = (parity_num + parity_num + replace_data_num) * vector_size / cost

Data	Parity	Vector size	Replace Data Num	AVX2 I/O (MiB/S)
10	4	8KiB	1	116193.04
10	4	8KiB	2	65375.73
10	4	8KiB	3	48775.47
10	4	8KiB	4	40398.79
10	4	8KiB	5	35262.89
10	4	8KiB	6	31881.60

PS:

We must know the benchmark test is quite different with encoding/decoding in practice.
Because in benchmark test loops, the CPU Cache may help a lot.

Acknowledgements

Klauspost ReedSolomon: It's the
most commonly used Erasure Codes library in Go. Impressive performance, friendly API,
and it can support multi platforms(with fast Galois Field Arithmetic). Inspired me a lot.

Intel ISA-L: The ideas of Cauchy matrix and saving memory
I/O are from it.

templexxx/reedsolomon