A faster Reed-Solomon library for Rust and why we wrote our own

Reed-Solomon erasure coding is what keeps user data durable on Sia. Spread data across enough independent hosts and a file outlives any that drop offline or slow down. That redundancy costs far less than full replication for the same durability, and since you only need a subset of shards, the client can read from whichever hosts answer first and skip the stragglers. None of this is novel in the storage space: Amazon S3, MinIO, Backblaze, Ceph, and others use erasure coding for the same basic reason.

For most of Sia's life, erasure coding was the server's job while your devices just sent and fetched files, a centralized wrapper over a decentralized network. With Sia's new architecture, the middleman is gone. Clients interact directly with storage providers. Now the client SDKs have to fetch, encrypt, erasure code, and fan out data themselves. They also have to hide that complexity from developers and run wherever users need them. That, unfortunately, includes a browser tab.

That left us with an interesting problem... How fast can Reed-Solomon run in a browser?

We needed an implementation that was fast on x86, ARM, and WebAssembly, and produced the exact same parity bytes as the data already on the network. There is one Rust crate that produces the same parity bytes and compiles to WebAssembly: reed_solomon_erasure. Without SIMD acceleration, its browser performance was not fast enough.

So we decided to write a new one. That became sia_reed_solomon: Reed-Solomon erasure coding over GF(2^8), SIMD-accelerated (even in browsers), MIT licensed, and wire-compatible with the data already stored on Sia.

sia_reed_solomon is another Rust port of Klaus Post's reedsolomon, the Go original. Sia has used it in production for eleven years. It's the standard for erasure coding in Go and a common target of ports for other languages due to its performance.

The benchmarks

Setup: 10 data shards + 20 parity, 4 MiB shards, AWS *.4xlarge spot runners (16 vCPU each). The shard layout is Sia's default. It keeps a file recoverable when untrusted hosts drop offline without overpaying for redundancy, and 4 MiB shards reflect the network's minimum chunk size. SIMD is the default build. "Scalar" is the --no-default-features --features parallel build, no SIMD but still multithreaded. The backend is picked at runtime. AVX2 and GFNI run on x86_64, NEON on aarch64, scalar everywhere else.

Throughput comes from Criterion (Rust) and go test -bench (Go), each timing only the operation, not shard setup or the random fill.

Reconstruct throughput is reported per data slab (data_shards × shard_size), which makes it comparable to download throughput. It also means `reconstruct -1 data lost` looks very high, since only one shard is rebuilt while the rate is normalized to the full slab.

Throughput across backends

Against the field

Klaus's Go is the baseline. It isn't a Rust crate we could pull into the SDK, but it's the high bar we measure against. reed_solomon_erasure (built with simd-accel) is the one actual Rust alternative for our usecase.

On c5.4xlarge (AVX2):

On c7i.4xlarge (GFNI):

On c7g.4xlarge (NEON):

On native targets we're 6x to over 25x faster than reed_solomon_erasure in these benches.

Klaus's package still wins encode on every machine, and wins outright on NEON. His kernels are generated assembly; we use Rust SIMD intrinsics. But on x86 backends, we beat it on reconstruction, and even on heavy reconstructions we stay ahead (8.2 vs 6.2 GiB/s on GFNI). Reconstruct is the download path: every time a client reads data and a shard is missing, it has to rebuild the original from parity.

The Rust benches and the Go bench harness are both in the repo under comparisons/ if you want to reproduce any of this.

Where the speed comes from

Erasure coding is mostly one operation repeated: multiply a shard by a constant in GF(2^8) and XOR it into an accumulator. Addition in the field is a plain XOR, and every byte is independent of the next, so the same work runs across a whole shard with nothing to coordinate between bytes. Scalar code walks a shard one byte at a time while SIMD processes 16 or 32 bytes per instruction.

That multiply is normally a 256-entry table lookup. The split-table method breaks each byte into two 4-bit nibbles, turning it into two 16-entry lookups XORed together. A 16-entry lookup is exactly what a SIMD shuffle does, 16 lanes in one instruction with the table in a register. So the multiply collapses to two shuffles and an XOR. GFNI skips it: GF2P8AFFINEQB applies the constant's 8x8 GF(2) matrix to each byte in one instruction, no tables.

WASM-SIMD

That's great, but wasn't the point to be faster in a browser?

Luckily, WASM-SIMD is supported in all browser targets we support. It adds a portable 128-bit vector type and a set of lane-wise instructions over it, including the byte shuffle (u8x16_swizzle) split-table depends on. The browser's engine lowers these to native SIMD instructions so the bytecode reaches the CPU's vector unit. With that, the browser runs the same shuffle-based multiply as the native SIMD backends: 16 bytes per instruction with the lookups in registers rather than one byte and a dependent load per step.

As far as we know, no other Rust Reed-Solomon crate has a WASM-SIMD backend. It's a niche target, but important for our SDKs.

That's roughly 8x faster on encode. The reconstruct gap depends on how much is missing: with one shard gone it's under 2x, but in the worst case, all 10 data shards need to be rebuilt, reed_solomon_erasure is over 5x slower.

In the browser, the library runs on the user's hardware with no bigger machine to offload to. On upload, the client encrypts, encodes, then sends the shards to hosts. The first two are CPU-bound, and the send is network-bound, so the faster those finish, the sooner each chunk hits the wire. Download is the same in reverse, fetching shards over the network, then reconstructing and decrypting. SIMD keeps encode and reconstruct from becoming the bottleneck.

Get it

It's on crates.io, docs are on docs.rs, source is on GitHub, MIT licensed.

1use sia_reed_solomon::ReedSolomon;
2
3let rs = ReedSolomon::new(10, 20)?; // 10 data + 20 parity
4rs.encode(&mut shards)?;
5assert!(rs.verify(&shards)?);
6
7let mut shards: Vec<Option<Vec<u8>>> = shards.into_iter().map(Some).collect();
8shards[3] = None;
9rs.reconstruct(&mut shards)?;

If you're building anything that needs fast, browser-capable erasure coding in Rust, give it a try.