Erasure coding: planning a Reed–Solomon virtual remote

Dev Discussions
1

I’m working on a Reed–Solomon–based erasure‑coding virtual remote for rclone and would like feedback on the design.

Motivation

Erasure coding splits data into (k) data shards and (m) parity shards; any (k) shards are enough to reconstruct the file, so you can lose up to (m) shards. Many storage systems (e.g. Backblaze B2, Ceph EC pools, Swift EC) use Reed–Solomon internally with layouts like 17+3 or 10+4 to get high durability with moderate overhead. In Go, github.com/klauspost/reedsolomon provides a fast, production‑grade implementation with systematic RS and streaming support over io.Reader/io.Writer.

There is already a PR for a simple RAID3‑style virtual remote: fixed 2+1 layout (two data shards plus one XOR parity shard) across three remotes, tolerating a single failure. It defines a self‑describing per‑shard header/footer so shards can be reconstructed even if the rclone config is lost, and it stores canonical hashes and last modification time inside each shard. This means the encoding does not depend on which backend features individual remotes support (hashes, mtimes, metadata), because that information is preserved in the shard payload itself.

Idea: sr Reed–Solomon remote

The plan is to generalize RAID3 into an sr virtual remote using Reed–Solomon:

  • For each file:
    • Split into (k) data shards.
    • Compute (m) parity shards, total (k+m).
    • Store each shard on a different underlying remote/object.
    • Read from any (k) available shards to reconstruct.

Configuration would follow the union style (one backend type, multiple instances with different params and upstreams): rclone

[sr-10-4]
type          = sr
data_shards   = 10
parity_shards = 4
upstreams     = remote1:bucket1 remote2:bucket2 ... remote14:bucket14
# placement_policy = spread | roundrobin | pinned (TBD)
# stripe_size      = 4M (TBD)

Different sr remotes can choose different (k,m) (e.g. 5+2, 8+3, 10+4).

Metadata and streaming

I plan to reuse and extend the RAID3 per‑shard metadata block so shards are self‑describing:

Core fields in the sr shard header/footer:

  • schemetype (rs-ec), schemeversion
  • objectid
  • dataparts (k), parityparts (m), partindex, stripesize
  • objectsize, padding
  • objecthashalgo / objecthash (canonical logical hash)
  • parthashalgo / parthash (per‑shard integrity)
  • objectmtime

Encoding would be streaming:

  • Choose a stripe size.
  • Loop: read stripe data into (k) buffers, call the RS encoder to generate (m) parity buffers, then write all (k+m) shard blocks to upstreams in parallel.
  • At EOF, finalize headers/footers with objectsize and padding.

The github.com/klauspost/reedsolomon API already supports this style.

Looking for feedback

Comments, design suggestions, and pointers to prior art are very welcome.

1 Like