Rust implementation of Reed-Solomon erasure coding
This is a port of BackBlaze's Java implementation, Klaus Post's Go implementation, and Nicolas Trangez's Haskell implementation.
Version 1.X.X copies BackBlaze's implementation, and is less performant as there were fewer places where parallelism could be added.
Version 2.X.X copies Klaus Post's implementation, and will (hopefully) be using C source files from NicolasT's Haskell implementation.
See Notes and License section for details.
Add the following to your Cargo.toml
toml
[dependencies]
reed-solomon-erasure = "2.0"
and the following to your crate root
rust
extern crate reed_solomon_erasure;
```rust
extern crate reedsolomonerasure;
use reedsolomonerasure::*;
fn main () { let r = ReedSolomon::new(3, 2); // 3 data shards, 2 parity shards
let mut master_copy = shards!([0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, 10, 11],
[0, 0, 0, 0], // last 2 rows are parity shards
[0, 0, 0, 0]);
// Construct the parity shards
r.encode_shards(&mut master_copy).unwrap();
// Make a copy and transform it into option shards arrangement
// for feeding into decode_missing
let mut shards = shards_into_option_shards(master_copy.clone());
// We can remove up to 2 shards, which may be data or parity shards
shards[0] = None;
shards[4] = None;
// Try to reconstruct missing shards
r.reconstruct_shards(&mut shards).unwrap();
// Convert back to normal shard arrangement
let result = option_shards_into_shards(shards);
assert!(r.verify_shards(&result).unwrap());
assert_eq!(master_copy, result);
} ```
You can test performance under different configurations quickly(e.g. data parity shards ratio, parallel parameters) by cloning this repo : https://github.com/darrenldl/rse-benchmark
rse-benchmark contains a copy of this library(usually a fully functional dev version), so you only need to adjust main.rs
then do cargo run --release to start the benchmark.
Version 1.X.X, 2.X.X do not utilise SIMD, as stable Rust still does not support SIMD yet. For the time being, the library is written in pure Rust.
I am looking into using the assembly code from Klaus's project and/or the SIMD C files from Nicolas's project, but this will not be done very soon. Contact me if you'd like to help.
Machine : laptop with Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz (max 2.70GHz) 2 Cores 4 Threads
Version 2.X.X is roughly 4-5x faster than version 1.X.X for encoding, depending on threading etc, but is always faster than version 1.X.X.
Klaus Post's Go implementation is roughly 7-8x faster for encoding compared to version 2.X.X, depending on threading etc, but is always faster as it supports SIMD operations.
Below shows the result of one of the test configurations, other configurations show similar results(Klaus Post's is at least 7-8x faster for all operations).
|Configuration| Klaus Post's | 2.X.X | 1.X.X | |---|---|---|---| |10x2x1M|~7800MB/s|~1100MB/s|~250MB/s|
Contributions are welcome. Note that by submitting contributions, you agree that your work will be under the same license used by this project(MIT).
The 1.X.X implementation mostly copies BackBlaze's Java implementation.
The 2.X.X implementation mostly copies Klaus Post's Go implementation, and copies C files from Nicolas Trangez's Haskell implementation.
The test suite for both versions copies Klaus Post's Go implementation.
The tables and main functions of build.rs are translated from BackBlaze Java Implementation, and are under the same MIT License as used by the BackBlaze project
The source code copied directly from BackBlaze's project repo are under the MIT License as used by the project, the files are in BackBlaze_JavaReedSolomon
The tables and main functions of src/* are translated from Klaus Post's Go Implementation, and are under the same MIT License as used by Klaus Post's project
The source code copied directly from Klaus Post's project repo are under the MIT License as used by the project, the files are in KlausPost_reedsolomon
The C files for SIMD operations are copied(with none/minor modifications) from Nicolas Trangez's Haskell implementation, and are under the same MIT License as used by NicolasT's project
The source code copied directly from Nicolas Trangez's project repo are under the MIT License as used by the project, the files are in NicolasT_reedsolomon
All files are released under MIT License