A Reed-Solomon Code for Disk Storage, and Efficient Recovery Computations for Erasure-Coded Disk Storage

Abstract

Reed-Solomon erasure codes provide efficient simple techniques for redundantly encoding information so that the failure of a few disks in a disk array doesn’t compromise the availability of data. This paper presents a technique for constructing a code that can correct up to three errors with a simple, regular encoding, which admits very efficient matrix inversions. It also presents new techniques for efficiently computing the sums of streams of data elements in a finite field, such as is needed in recovering data after a disk failure.