• 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:

  1. <A “Hitchhiker’s” Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data Centers>
  2. <A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes>

• 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 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

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

Base means no SIMD.

Need Data = Data size need read in reconstruction

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

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

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

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.

• Reed-Solomon
• XOR