Generalized Reed Solomon Codes for Erasure Correction in SDDS
Scalable Distributed Data Structures (SDDS) need scalable availability. This can be provided through replication, which is storage intensive, or through the use of Erasure Correcting Codes (ECC) to provide redundancy, which is more complicated. The authors calculate availability under both strategies and show that redundancy through use of an ECC implies significantly less overhead. They introduce a generalized Reed Solomon code as an ECC that uses ordinary parity (XOR) for the first level of redundancy, and adapts to the scaling up and down of an SDDS file. They derive the relevant properties of the ECC directly and discuss its adaptation to the changing needs of a SDDS.