Techniques to efficiently compute erasure codes having positive and negative coefficient exponents to permit data recovery from more than two failed storage units

摘要

Erasure code syndrome computation based on Reed Solomon (RS) operations in a Galois field to permit reconstruction of data of more than 2 failed storage units. Syndrome computation may be performed with coefficient exponents that consist of −1, 0, and 1. A product xD of a syndrome is computed as a left-shift of data byte D, and selective compensation based on the most significant bit of D. A product x−1D of a syndrome is computed as a right-shift of data byte D, and selective compensation based on the most significant bit of D. Compensation may include bit-wise XORing shift results with a constant derived from an irreducible polynomial associated with the Galois field. A set of erasure code syndromes may be computed for each of multiple nested arrays of independent storage units. Data reconstruction includes solving coefficients of the syndromes as a Vandermonde matrix.

主权项

1. An apparatus, comprising, a processor and memory configured to:
compute m erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and data distributed over k storage units, wherein at least one of the m erasure code syndromes includes a coefficient of exponent negative one (x−1) and a coefficient of exponent positive one (x), including to compute, in the Galois field, one or more of,
a product of a data byte and the coefficient x−1 as a right-shift of the data byte, anda product of the data byte and the coefficient x as a left-shift of the data byte; and reconstruct data of up to m of the k storage units based on the m erasure code syndromes and data stored in remaining ones of the k storage units, where k and m are positive integers, wherein m is greater than 2, and wherein k is greater than m.