Skip to content

Latest commit

 

History

History
476 lines (448 loc) · 25.4 KB

README.md

File metadata and controls

476 lines (448 loc) · 25.4 KB

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