X-Reed-Solomon

Introduction:

Fast and efficient data reconstruction Erasure Code engine in pure Go.

Systematic Codes with MDS property.

More than 10GB/s per physics core.

Saving about 30% I/O in reconstruction.

Has been used for a distributed storage system with more than 10PB data.

Based on papers:

<A “Hitchhiker’s” Guide to Fast and Efﬁcient Data Reconstruction in Erasure-coded Data Centers>

<A Piggybacking Design Framework for Read-and Download-efﬁcient Distributed Storage Codes>

Getting Started

Make sure you have read the papers.

XRS splits row vector into two equal parts.

e.g. 10+4:

+---------+
| a1 | b1 |
+---------+
| a2 | b2 |
+---------+
| a3 | b3 |
+---------+
    ...
+---------+
| a10| b10|
+---------+
| a11| b11|
+---------+
| a12| b12|
+---------+
| a13| b13|
+---------+

So it's important to choose a fit size for reading/write disks efficiently.

APIs are almost as same as normal Reed-Solomon Erasure Codes.

Performance

Performance depends mainly on:

CPU instruction extension.

Number of data/parity row vectors.

Platform:

MacBook Pro 15-inch, 2017 (Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz)

All test run on a single Core.

RS means Reed-Solomon Codes(for comparing), the RS lib is here

Encode:

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

Base means no SIMD.

Data	Parity	Vector size	RS I/O (MB/S)	XRS I/O (MB/S)
12	4	4KB	12658.00	10895.15
12	4	1MB	8989.67	7530.84
12	4	8MB	8509.06	6579.53

Reconstruct:

Need Data = Data size need read in reconstruction

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

Data	Parity	Vector size	Reconstruct Data Num	RS Need Data	XRS Need Data	RS Cost	XRS Cost	RS I/O (MB/S)	XRS I/O (MB/S)
12	4	4KB	1	48KB	34KB	2140 ns/op	3567 ns/op	24885.17	10334.99
12	4	4KB	2	48KB	48KB	3395 ns/op	5940 ns/op	16890.41	9654.17
12	4	4KB	3	48KB	48KB	4746 ns/op	7525 ns/op	12945.61	8164.76
12	4	4KB	4	48KB	48KB	5958 ns/op	8851 ns/op	10999.75	7404.41

Update:

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

Data	Parity	Vector size	RS I/O (MB/S)	XRS I/O (MB/S)
12	4	4KB	32739.22	26312.14

Replace:

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

Data	Parity	Vector size	Replace Data Num	RS I/O (MB/S)	XRS I/O (MB/S)
12	4	4KB	1	63908.06	44082.57
12	4	4KB	2	39966.65	26554.30
12	4	4KB	3	30007.81	19583.16
12	4	4KB	4	25138.38	16636.82
12	4	4KB	5	21261.91	14301.15
12	4	4KB	6	19833.14	13121.98
12	4	4KB	7	18395.47	12028.10
12	4	4KB	8	17364.02	11300.55

PS:

And 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.

FengMingquan-sjtu/xrs