Repairing Reed-Solomon Codes

We study the performance of Reed-Solomon (RS) codes for the exact repair problem in distributed storage. Our main result is that, in some parameter regimes, Reed-Solomon codes are optimal regenerating codes, among maximum distance separable (MDS) codes with linear repair schemes. Moreover, we give a characterization of MDS codes with linear repair schemes, which holds in any parameter regime, and which can be used to give non-trivial repair schemes for RS codes in other settings. More precisely, we show that for k-dimensional RS codes whose evaluation points are a finite field of size n, there are exact repair schemes with bandwidth (n-1) log((n-1)/(n-k)) bits, and that this is optimal for any MDS code with a linear repair scheme. In contrast, the naive (commonly implemented) repair algorithm for this RS code has bandwidth k log(n) bits. When the entire field is used as evaluation points, the number of nodes n is much larger than the number of bits per node (which is O(log(n))), and so this result holds only when the degree of sub-packetization is small. However, our method applies in any parameter regime, and to illustrate this for high levels of sub-packetization, we give an improved repair scheme for a specific (14,10)-RS code used in the facebook hadoop analytics cluster.