Reed–Solomon codes (storage)
Reed-Solomon codes are maximum-distance-separable codes over finite-field symbols, used to recover missing data and, with suitable decoders, correct errors.
An RS(n, k) code has n - k check symbols and minimum distance n - k + 1. Any k distinct, intact symbols from the same codeword determine the payload. With a suitable errors-and-erasures decoder, E unknown symbol errors and S known erasures are correctable when 2E + S <= n - k. An erasure-only storage API does not locate silent corruption automatically. [6] [7]
Systematic layout and full generator rank alone do not prove any-k recovery. The corrected Vandermonde construction transforms the complete matrix using column operations. Its GF(16) example is reproduced with all 81,920 payload/survivor round trips; a separate row-mixing control loses recovery for two of 20 survivor sets. [9] [10]
Storage profiles also specify a plugin, technique, field parameters and placement. RAID 6 describes double-parity protection, not one unique codec. Defaults are release-specific: Reef profile documentation lists jerasure, while the development ISA documentation lists isa. Inspect the deployed profile before assuming either. [1] [2] [3]
Relations
- related
- Erasure coding, RAID 6, Parity RAID, RAID 5, LDPC (NAND ECC), Bit error rate, Object storage, Optical archival storage, Blu-ray data archive, Locally repairable code, Maximum distance separable code, Systematic code, Symbol erasure, Error-and-erasure decoding
Advantages
- Maximum distance separable: n − k redundancy symbols tolerate n − k known erasures, the best possible for that redundancy
- Symbol-oriented correction handles burst errors and whole-device losses well
- Configurable k and m let designers trade raw-space overhead against the number of tolerated failures
Limitations
- Encoding and decoding use finite-field arithmetic, so the codes cost more compute than simple XOR parity
- Recovering a lost symbol requires the surviving symbols of the same codeword, so repair involves reading from many devices
- Repair must validate helper integrity and fragment identity; solving an invertible system is not a corruption detector.
- The actual matrix construction and supported parameter range must justify any-k recovery.
Citations
- Erasure code profiles (Ceph documentation, Reef)
- ISA erasure code plugin (Ceph documentation)
- Jerasure erasure code plugin (Ceph documentation)
- Plank and Ding, SPE 35(2), 189-194 (2005), DOI 10.1002/spe.631. Journal metadata.
- RFC 5510 (2009), sections 3.1 and 8.1-8.4: finite fields, systematic encoding and the erasure-channel contract.
- Forney, MIT 6.451 (2005), section 6.5.3: bounded-distance errors-and-erasures correction.
- Plank and Ding. UT-CS-03-504 (24 April 2003), section 3, Table 1 and worked GF(16) example, pages 2-4. Full six-page report reviewed.
- Hesela: GF(16) reconstruction and row-mixing negative control, with executable tests.
Further reading
- Intel ISA-L erasure_code.h, gf_gen_rs_matrix contract; commit 8fa1e72fee7338fcfbf829b00f2f407631bd2dba.
- Hesela: exact GF(7) errors-and-erasures examples and false-identification negative control.
Sources & caveats
- The complete 24 April 2003 technical report was reviewed and its example reconstructed. The 2005 journal record supplies publication metadata, not the numerical reproduction. [9] [4]
- GF(16) arithmetic uses XOR and the polynomial x^4 + x + 1; it is not integer arithmetic modulo 16. The row-mixing control is an explanatory calculation, not a production failure rate. [10]