TECHNIQUES TO EFFICIENTLY COMPUTE ERASURE CODES HAVING POSITIVE AND NEGATIVE COEFFICIENT EXPONENTS TO PERMIT DATA RECOVERY FROM MORE THAN TWO FAILED STORAGE UNITS
First Claim
1. An apparatus to reconstruct data distributed over multiple storage units, comprising:
- a first erasure code module to compute m erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and the data distributed over k storage units; and
a first data reconstruction module to reconstruct data of up to m of the k storage units based on the m syndromes and data stored in remaining ones of the k storage units, where k and m are positive integers, and wherein m is greater than 2.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
-
Citations
25 Claims
-
1. An apparatus to reconstruct data distributed over multiple storage units, comprising:
-
a first erasure code module to compute m erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and the data distributed over k storage units; and a first data reconstruction module to reconstruct data of up to m of the k storage units based on the m syndromes and data stored in remaining ones of the k storage units, where k and m are positive integers, and wherein m is greater than 2. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A non-transitory computer readable medium encoded with a computer program, including instructions to cause a processor to reconstruct data distributed over multiple storage units, including to:
-
compute m erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and the data distributed over k storage units; and reconstruct data of up to m of the k storage units based on the m syndromes and data stored in remaining ones of the k storage units, where k and m are positive integers and m is greater than 2. - View Dependent Claims (14, 15, 16, 17)
-
-
18. A method of reconstructing data distributed over multiple storage units, comprising:
-
computing m erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and data distributed over k storage units; and reconstructing data of up to m of the k storage units based on the erasure code syndromes and data stored in remaining ones of the k storage units, where k and m are positive integers, and wherein m is greater than 2. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
-
Specification