reed-solomon
Fast, reliable Reed-Solomon erasure coding as a native addon for Node.js, licensed under the MIT License.
For an introduction to erasure coding, see this post by Brian Beach on the Backblaze blog.
Installation
npm install @ronomon/reed-solomon
Performance
The native addon executes asynchronously in Node's threadpool without blocking the event loop:
CPU | Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz
CORES | 8
THREADS | 1
------------------------------------------------------------------
DATA | PARITY | SHARD SIZE | LATENCY | THROUGHPUT
------------------------------------------------------------------
1 | 1 | 4096 | 0.202ms | 20.29 MB/s
1 | 1 | 65536 | 0.038ms | 1720.57 MB/s
1 | 1 | 262144 | 0.048ms | 5435.80 MB/s
------------------------------------------------------------------
1 | 2 | 4096 | 0.020ms | 199.95 MB/s
1 | 2 | 65536 | 0.025ms | 2606.39 MB/s
1 | 2 | 262144 | 0.081ms | 3249.66 MB/s
------------------------------------------------------------------
1 | 3 | 4096 | 0.023ms | 177.43 MB/s
1 | 3 | 65536 | 0.033ms | 2004.03 MB/s
1 | 3 | 262144 | 0.108ms | 2428.02 MB/s
------------------------------------------------------------------
1 | 4 | 4096 | 0.027ms | 149.38 MB/s
1 | 4 | 65536 | 0.041ms | 1611.52 MB/s
1 | 4 | 262144 | 0.134ms | 1952.67 MB/s
------------------------------------------------------------------
2 | 1 | 4096 | 0.041ms | 197.48 MB/s
2 | 1 | 65536 | 0.057ms | 2285.90 MB/s
2 | 1 | 262144 | 0.114ms | 4611.48 MB/s
------------------------------------------------------------------
2 | 2 | 4096 | 0.049ms | 166.09 MB/s
2 | 2 | 65536 | 0.075ms | 1736.75 MB/s
2 | 2 | 262144 | 0.203ms | 2579.89 MB/s
------------------------------------------------------------------
2 | 3 | 4096 | 0.064ms | 128.74 MB/s
2 | 3 | 65536 | 0.093ms | 1414.32 MB/s
2 | 3 | 262144 | 0.316ms | 1659.31 MB/s
------------------------------------------------------------------
2 | 4 | 4096 | 0.060ms | 135.47 MB/s
2 | 4 | 65536 | 0.111ms | 1182.68 MB/s
2 | 4 | 262144 | 0.430ms | 1220.38 MB/s
------------------------------------------------------------------
3 | 1 | 4096 | 0.065ms | 189.66 MB/s
3 | 1 | 65536 | 0.076ms | 2602.82 MB/s
3 | 1 | 262144 | 0.182ms | 4329.66 MB/s
------------------------------------------------------------------
3 | 2 | 4096 | 0.059ms | 209.24 MB/s
3 | 2 | 65536 | 0.095ms | 2073.39 MB/s
3 | 2 | 262144 | 0.322ms | 2441.14 MB/s
------------------------------------------------------------------
3 | 3 | 4096 | 0.060ms | 204.08 MB/s
3 | 3 | 65536 | 0.119ms | 1649.52 MB/s
3 | 3 | 262144 | 0.473ms | 1663.10 MB/s
------------------------------------------------------------------
3 | 4 | 4096 | 0.076ms | 162.42 MB/s
3 | 4 | 65536 | 0.227ms | 867.70 MB/s
3 | 4 | 262144 | 0.618ms | 1273.22 MB/s
------------------------------------------------------------------
4 | 1 | 4096 | 0.060ms | 273.79 MB/s
4 | 1 | 65536 | 0.087ms | 3023.48 MB/s
4 | 1 | 262144 | 0.228ms | 4596.09 MB/s
------------------------------------------------------------------
4 | 2 | 4096 | 0.056ms | 294.79 MB/s
4 | 2 | 65536 | 0.111ms | 2362.53 MB/s
4 | 2 | 262144 | 0.407ms | 2577.41 MB/s
------------------------------------------------------------------
4 | 3 | 4096 | 0.056ms | 294.13 MB/s
4 | 3 | 65536 | 0.146ms | 1797.57 MB/s
4 | 3 | 262144 | 0.623ms | 1681.80 MB/s
------------------------------------------------------------------
4 | 4 | 4096 | 0.066ms | 248.58 MB/s
4 | 4 | 65536 | 0.187ms | 1401.34 MB/s
4 | 4 | 262144 | 0.857ms | 1222.92 MB/s
------------------------------------------------------------------
5 | 1 | 4096 | 0.067ms | 305.98 MB/s
5 | 1 | 65536 | 0.150ms | 2177.36 MB/s
5 | 1 | 262144 | 0.311ms | 4208.79 MB/s
------------------------------------------------------------------
5 | 2 | 4096 | 0.050ms | 407.33 MB/s
5 | 2 | 65536 | 0.115ms | 2859.69 MB/s
5 | 2 | 262144 | 0.500ms | 2621.67 MB/s
------------------------------------------------------------------
5 | 3 | 4096 | 0.067ms | 304.29 MB/s
5 | 3 | 65536 | 0.204ms | 1609.13 MB/s
5 | 3 | 262144 | 0.772ms | 1698.20 MB/s
------------------------------------------------------------------
5 | 4 | 4096 | 0.074ms | 276.14 MB/s
5 | 4 | 65536 | 0.257ms | 1274.51 MB/s
5 | 4 | 262144 | 1.071ms | 1223.68 MB/s
------------------------------------------------------------------
6 | 1 | 4096 | 0.068ms | 361.53 MB/s
6 | 1 | 65536 | 0.105ms | 3755.04 MB/s
6 | 1 | 262144 | 0.354ms | 4439.00 MB/s
------------------------------------------------------------------
6 | 2 | 4096 | 0.060ms | 409.94 MB/s
6 | 2 | 65536 | 0.135ms | 2907.23 MB/s
6 | 2 | 262144 | 0.590ms | 2664.83 MB/s
------------------------------------------------------------------
6 | 3 | 4096 | 0.064ms | 384.48 MB/s
6 | 3 | 65536 | 0.237ms | 1662.03 MB/s
6 | 3 | 262144 | 0.961ms | 1637.34 MB/s
------------------------------------------------------------------
6 | 4 | 4096 | 0.076ms | 323.20 MB/s
6 | 4 | 65536 | 0.306ms | 1286.81 MB/s
6 | 4 | 262144 | 1.269ms | 1239.15 MB/s
------------------------------------------------------------------
7 | 1 | 4096 | 0.055ms | 518.41 MB/s
7 | 1 | 65536 | 0.123ms | 3720.08 MB/s
7 | 1 | 262144 | 0.401ms | 4574.62 MB/s
------------------------------------------------------------------
7 | 2 | 4096 | 0.055ms | 523.62 MB/s
7 | 2 | 65536 | 0.172ms | 2665.10 MB/s
7 | 2 | 262144 | 0.693ms | 2648.54 MB/s
------------------------------------------------------------------
7 | 3 | 4096 | 0.068ms | 422.02 MB/s
7 | 3 | 65536 | 0.266ms | 1727.26 MB/s
7 | 3 | 262144 | 1.100ms | 1668.10 MB/s
------------------------------------------------------------------
7 | 4 | 4096 | 0.081ms | 352.39 MB/s
7 | 4 | 65536 | 0.354ms | 1295.14 MB/s
7 | 4 | 262144 | 1.501ms | 1222.15 MB/s
------------------------------------------------------------------
8 | 1 | 4096 | 0.046ms | 710.37 MB/s
8 | 1 | 65536 | 0.104ms | 5024.44 MB/s
8 | 1 | 262144 | 0.357ms | 5867.80 MB/s
------------------------------------------------------------------
8 | 2 | 4096 | 0.025ms | 1286.85 MB/s
8 | 2 | 65536 | 0.130ms | 4019.83 MB/s
8 | 2 | 262144 | 0.504ms | 4159.09 MB/s
------------------------------------------------------------------
8 | 3 | 4096 | 0.040ms | 819.81 MB/s
8 | 3 | 65536 | 0.183ms | 2857.84 MB/s
8 | 3 | 262144 | 0.683ms | 3072.52 MB/s
------------------------------------------------------------------
8 | 4 | 4096 | 0.031ms | 1049.90 MB/s
8 | 4 | 65536 | 0.238ms | 2199.69 MB/s
8 | 4 | 262144 | 0.983ms | 2133.64 MB/s
------------------------------------------------------------------
9 | 1 | 4096 | 0.035ms | 1045.72 MB/s
9 | 1 | 65536 | 0.085ms | 6926.25 MB/s
9 | 1 | 262144 | 0.370ms | 6376.90 MB/s
------------------------------------------------------------------
9 | 2 | 4096 | 0.038ms | 982.72 MB/s
9 | 2 | 65536 | 0.147ms | 4005.27 MB/s
9 | 2 | 262144 | 0.577ms | 4088.25 MB/s
------------------------------------------------------------------
9 | 3 | 4096 | 0.041ms | 893.76 MB/s
9 | 3 | 65536 | 0.224ms | 2629.15 MB/s
9 | 3 | 262144 | 0.869ms | 2715.82 MB/s
------------------------------------------------------------------
9 | 4 | 4096 | 0.043ms | 866.49 MB/s
9 | 4 | 65536 | 0.331ms | 1779.40 MB/s
9 | 4 | 262144 | 1.281ms | 1842.45 MB/s
------------------------------------------------------------------
10 | 1 | 4096 | 0.027ms | 1508.91 MB/s
10 | 1 | 65536 | 0.097ms | 6757.32 MB/s
10 | 1 | 262144 | 0.421ms | 6233.25 MB/s
------------------------------------------------------------------
10 | 2 | 4096 | 0.033ms | 1250.72 MB/s
10 | 2 | 65536 | 0.167ms | 3925.31 MB/s
10 | 2 | 262144 | 0.654ms | 4011.25 MB/s
------------------------------------------------------------------
10 | 3 | 4096 | 0.040ms | 1025.30 MB/s
10 | 3 | 65536 | 0.242ms | 2703.63 MB/s
10 | 3 | 262144 | 1.047ms | 2504.04 MB/s
------------------------------------------------------------------
10 | 4 | 4096 | 0.050ms | 824.13 MB/s
10 | 4 | 65536 | 0.358ms | 1829.99 MB/s
10 | 4 | 262144 | 1.393ms | 1881.64 MB/s
------------------------------------------------------------------
11 | 1 | 4096 | 0.029ms | 1565.69 MB/s
11 | 1 | 65536 | 0.107ms | 6725.60 MB/s
11 | 1 | 262144 | 0.433ms | 6661.48 MB/s
------------------------------------------------------------------
11 | 2 | 4096 | 0.041ms | 1108.18 MB/s
11 | 2 | 65536 | 0.194ms | 3721.06 MB/s
11 | 2 | 262144 | 0.685ms | 4207.69 MB/s
------------------------------------------------------------------
11 | 3 | 4096 | 0.035ms | 1280.41 MB/s
11 | 3 | 65536 | 0.265ms | 2718.35 MB/s
11 | 3 | 262144 | 1.144ms | 2520.31 MB/s
------------------------------------------------------------------
11 | 4 | 4096 | 0.051ms | 880.45 MB/s
11 | 4 | 65536 | 0.417ms | 1727.85 MB/s
11 | 4 | 262144 | 1.600ms | 1802.67 MB/s
------------------------------------------------------------------
12 | 1 | 4096 | 0.042ms | 1168.18 MB/s
12 | 1 | 65536 | 0.121ms | 6489.28 MB/s
12 | 1 | 262144 | 0.442ms | 7124.52 MB/s
------------------------------------------------------------------
12 | 2 | 4096 | 0.029ms | 1696.64 MB/s
12 | 2 | 65536 | 0.188ms | 4185.55 MB/s
12 | 2 | 262144 | 0.832ms | 3782.82 MB/s
------------------------------------------------------------------
12 | 3 | 4096 | 0.059ms | 839.80 MB/s
12 | 3 | 65536 | 0.323ms | 2434.45 MB/s
12 | 3 | 262144 | 1.314ms | 2393.83 MB/s
------------------------------------------------------------------
12 | 4 | 4096 | 0.066ms | 740.71 MB/s
12 | 4 | 65536 | 0.445ms | 1767.18 MB/s
12 | 4 | 262144 | 1.739ms | 1808.54 MB/s
------------------------------------------------------------------
13 | 1 | 4096 | 0.029ms | 1832.60 MB/s
13 | 1 | 65536 | 0.117ms | 7284.64 MB/s
13 | 1 | 262144 | 0.519ms | 6566.15 MB/s
------------------------------------------------------------------
13 | 2 | 4096 | 0.035ms | 1523.66 MB/s
13 | 2 | 65536 | 0.242ms | 3514.81 MB/s
13 | 2 | 262144 | 0.964ms | 3534.83 MB/s
------------------------------------------------------------------
13 | 3 | 4096 | 0.045ms | 1187.89 MB/s
13 | 3 | 65536 | 0.354ms | 2406.95 MB/s
13 | 3 | 262144 | 1.457ms | 2339.49 MB/s
------------------------------------------------------------------
13 | 4 | 4096 | 0.082ms | 648.33 MB/s
13 | 4 | 65536 | 0.642ms | 1327.69 MB/s
13 | 4 | 262144 | 2.542ms | 1340.53 MB/s
------------------------------------------------------------------
14 | 1 | 4096 | 0.028ms | 2030.67 MB/s
14 | 1 | 65536 | 0.122ms | 7500.05 MB/s
14 | 1 | 262144 | 0.564ms | 6504.95 MB/s
------------------------------------------------------------------
14 | 2 | 4096 | 0.039ms | 1471.78 MB/s
14 | 2 | 65536 | 0.286ms | 3204.86 MB/s
14 | 2 | 262144 | 1.078ms | 3404.64 MB/s
------------------------------------------------------------------
14 | 3 | 4096 | 0.065ms | 888.39 MB/s
14 | 3 | 65536 | 0.519ms | 1766.39 MB/s
14 | 3 | 262144 | 2.019ms | 1817.82 MB/s
------------------------------------------------------------------
14 | 4 | 4096 | 0.090ms | 634.96 MB/s
14 | 4 | 65536 | 0.713ms | 1286.64 MB/s
14 | 4 | 262144 | 2.817ms | 1302.66 MB/s
------------------------------------------------------------------
15 | 1 | 4096 | 0.032ms | 1907.47 MB/s
15 | 1 | 65536 | 0.140ms | 7040.96 MB/s
15 | 1 | 262144 | 0.618ms | 6365.28 MB/s
------------------------------------------------------------------
15 | 2 | 4096 | 0.047ms | 1315.35 MB/s
15 | 2 | 65536 | 0.304ms | 3234.42 MB/s
15 | 2 | 262144 | 1.130ms | 3481.12 MB/s
------------------------------------------------------------------
15 | 3 | 4096 | 0.085ms | 726.10 MB/s
15 | 3 | 65536 | 0.593ms | 1657.45 MB/s
15 | 3 | 262144 | 2.148ms | 1830.25 MB/s
------------------------------------------------------------------
15 | 4 | 4096 | 0.120ms | 513.61 MB/s
15 | 4 | 65536 | 0.738ms | 1332.41 MB/s
15 | 4 | 262144 | 3.033ms | 1296.38 MB/s
------------------------------------------------------------------
16 | 1 | 4096 | 0.044ms | 1488.75 MB/s
16 | 1 | 65536 | 0.134ms | 7848.64 MB/s
16 | 1 | 262144 | 0.592ms | 7081.85 MB/s
------------------------------------------------------------------
16 | 2 | 4096 | 0.043ms | 1512.59 MB/s
16 | 2 | 65536 | 0.295ms | 3558.64 MB/s
16 | 2 | 262144 | 1.184ms | 3542.97 MB/s
------------------------------------------------------------------
16 | 3 | 4096 | 0.090ms | 732.23 MB/s
16 | 3 | 65536 | 0.634ms | 1653.17 MB/s
16 | 3 | 262144 | 2.428ms | 1727.20 MB/s
------------------------------------------------------------------
16 | 4 | 4096 | 0.115ms | 571.62 MB/s
16 | 4 | 65536 | 0.852ms | 1230.77 MB/s
16 | 4 | 262144 | 3.396ms | 1234.95 MB/s
------------------------------------------------------------------
17 | 1 | 4096 | 0.033ms | 2102.59 MB/s
17 | 1 | 65536 | 0.172ms | 6482.07 MB/s
17 | 1 | 262144 | 0.587ms | 7590.47 MB/s
------------------------------------------------------------------
17 | 2 | 4096 | 0.040ms | 1741.43 MB/s
17 | 2 | 65536 | 0.316ms | 3528.31 MB/s
17 | 2 | 262144 | 1.334ms | 3341.86 MB/s
------------------------------------------------------------------
17 | 3 | 4096 | 0.081ms | 854.85 MB/s
17 | 3 | 65536 | 0.642ms | 1735.37 MB/s
17 | 3 | 262144 | 2.657ms | 1677.29 MB/s
------------------------------------------------------------------
17 | 4 | 4096 | 0.118ms | 590.97 MB/s
17 | 4 | 65536 | 0.881ms | 1264.46 MB/s
17 | 4 | 262144 | 3.677ms | 1211.94 MB/s
------------------------------------------------------------------
18 | 1 | 4096 | 0.045ms | 1621.06 MB/s
18 | 1 | 65536 | 0.161ms | 7337.85 MB/s
18 | 1 | 262144 | 0.694ms | 6802.32 MB/s
------------------------------------------------------------------
18 | 2 | 4096 | 0.061ms | 1217.39 MB/s
18 | 2 | 65536 | 0.356ms | 3316.56 MB/s
18 | 2 | 262144 | 1.457ms | 3239.25 MB/s
------------------------------------------------------------------
18 | 3 | 4096 | 0.083ms | 885.94 MB/s
18 | 3 | 65536 | 0.689ms | 1711.45 MB/s
18 | 3 | 262144 | 2.853ms | 1653.91 MB/s
------------------------------------------------------------------
18 | 4 | 4096 | 0.110ms | 672.03 MB/s
18 | 4 | 65536 | 0.905ms | 1303.68 MB/s
18 | 4 | 262144 | 3.965ms | 1189.92 MB/s
------------------------------------------------------------------
19 | 1 | 4096 | 0.037ms | 2075.31 MB/s
19 | 1 | 65536 | 0.217ms | 5737.11 MB/s
19 | 1 | 262144 | 0.769ms | 6477.97 MB/s
------------------------------------------------------------------
19 | 2 | 4096 | 0.061ms | 1283.72 MB/s
19 | 2 | 65536 | 0.375ms | 3324.22 MB/s
19 | 2 | 262144 | 1.532ms | 3250.41 MB/s
------------------------------------------------------------------
19 | 3 | 4096 | 0.107ms | 727.70 MB/s
19 | 3 | 65536 | 0.734ms | 1696.71 MB/s
19 | 3 | 262144 | 2.993ms | 1664.30 MB/s
------------------------------------------------------------------
19 | 4 | 4096 | 0.131ms | 595.96 MB/s
19 | 4 | 65536 | 0.981ms | 1269.12 MB/s
19 | 4 | 262144 | 4.167ms | 1195.18 MB/s
------------------------------------------------------------------
20 | 1 | 4096 | 0.052ms | 1560.67 MB/s
20 | 1 | 65536 | 0.202ms | 6493.22 MB/s
20 | 1 | 262144 | 0.801ms | 6545.79 MB/s
------------------------------------------------------------------
20 | 2 | 4096 | 0.054ms | 1506.94 MB/s
20 | 2 | 65536 | 0.407ms | 3218.66 MB/s
20 | 2 | 262144 | 1.635ms | 3205.88 MB/s
------------------------------------------------------------------
20 | 3 | 4096 | 0.105ms | 776.62 MB/s
20 | 3 | 65536 | 0.758ms | 1728.85 MB/s
20 | 3 | 262144 | 3.167ms | 1655.57 MB/s
------------------------------------------------------------------
20 | 4 | 4096 | 0.123ms | 666.05 MB/s
20 | 4 | 65536 | 1.078ms | 1215.52 MB/s
20 | 4 | 262144 | 4.415ms | 1187.52 MB/s
------------------------------------------------------------------
Usage
Adjust threadpool size and control concurrency
Please see the crypto-async module for advice on adjusting threadpool size and controlling concurrency.
Encoding Parity Shards
var ReedSolomon = require('@ronomon/reed-solomon');
// Specify the number of data shards (<= ReedSolomon.MAX_K):
var k = 6;
// Specify the number of parity shards (<= ReedSolomon.MAX_M):
var m = 3; // Protect against the loss of any 3 data or parity shards.
// Create an encoding context (can be cached and re-used concurrently):
var context = ReedSolomon.create(k, m);
// Specify the size of each shard in bytes (must be a multiple of 8 bytes):
var shardSize = 65536;
// Allocate the data buffer containing all data shards:
var buffer = Buffer.alloc(shardSize * k);
// Specify the offset into the data buffer at which data shards begin:
// This allows you to include a header.
var bufferOffset = 0;
// Specify the size after this offset of all data shards:
// This allows you to include a footer.
var bufferSize = shardSize * k;
// Allocate the parity buffer containing all parity shards:
var parity = Buffer.alloc(shardSize * m);
// Specify the offset into the parity buffer at which parity shards begin:
// This allows you to include a header.
var parityOffset = 0;
// Specify the size after this offset of all parity shards:
// This allows you to include a footer.
var paritySize = shardSize * m;
// Specify the sources, present in buffer or parity (as bit flags):
// We are encoding parity shards, so we mark all data shards as sources.
var sources = 0;
for (var i = 0; i < k; i++) sources |= (1 << i);
// Specify the targets, missing in buffer or parity, which should be encoded:
// We are encoding parity shards, so we mark all parity shards as targets:
var targets = 0;
for (var i = k; i < k + m; i++) targets |= (1 << i);
// Encode all parity shards:
ReedSolomon.encode(
context,
sources,
targets,
buffer,
bufferOffset,
bufferSize,
parity,
parityOffset,
paritySize,
function(error) {
if (error) throw error;
// Parity shards now contain parity data.
}
);Encoding Corrupted Shards
// Corrupt first data shard:
buffer[bufferOffset + (shardSize * 0)] = 255;
// Corrupt first parity shard:
parity[parityOffset + (shardSize * 0)] = 255;
// We still have enough parity to corrupt one more shard.
// Specify the targets, missing in buffer or parity, which should be encoded:
var targets = 0;
targets |= (1 << 0); // Data shard at index 0 needs to be encoded.
targets |= (1 << k); // Parity shard at index 6 (k + 0) needs to be encoded.
// Specify the sources, present in buffer or parity:
// We need at least k sources.
// For this example, we assume that a shard is a source if it is not a target.
// An optimization is available here:
// If a shard is not a source or target, it might not be encoded.
// The shard may be encoded if needed to encode other shards, but otherwise not.
var sources = 0;
for (var i = 0; i < k + m; i++) {
if (targets & (1 << i)) continue;
sources |= (1 << i);
}
// Encode the corrupted data and parity shards:
ReedSolomon.encode(
context,
sources,
targets,
buffer,
bufferOffset,
bufferSize,
parity,
parityOffset,
paritySize,
function(error) {
if (error) throw error;
// Data shard at index 0 has been repaired.
// Parity shard at index 6 has been repaired.
}
);Tests
reed-solomon ships with extensive tests, including a long-running fuzz test.
node test.js
Benchmark
node benchmark.js