TECHNIQUES TO EFFICIENTLY COMPUTE ERASURE CODES HAVING POSITIVE AND NEGATIVE COEFFICIENT EXPONENTS TO PERMIT DATA RECOVERY FROM MORE THAN TWO FAILED STORAGE UNITS

• US 20150347231A1
• Filed: 06/02/2014
• Published: 12/03/2015
• Est. Priority Date: 06/02/2014
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Ozturk Erdinc, Vinodh Gopal
• Inventors: GOPAL, VINODH, OZTURK, ERDINC
• Granted Patent: US 9,594,634 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes

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⁻¹D 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.

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.

2. The apparatus of claim 1, wherein the first erasure code module is configured to compute, in the Galois field, a product of a data byte and a syndrome coefficient x⁻

1 as a right-shift of the data byte and selectively compensate a result of the right-shift based on a value of a least significant bit of the data byte.

3. The apparatus of claim 2, wherein the first erasure code module is further configured to selectively compensate the result of the right-shift with a constant derived from an irreducible polynomial associated with the Galois field.

4. The apparatus of claim 3, wherein the first erasure code module is further configured to compute the syndromes based on a 2⁸ Galois field, including to compute the product of the data byte and the coefficient x⁻

1 as an 8-bit right-shift of the data byte and selectively bit-wise XOR the result of the right-shift with a constant derived from an irreducible polynomial associated with the 2⁸ Galois field.

5. The apparatus of claim 4, wherein the first erasure code module is further configured to compute the syndromes based on an 8-bit Galois field polynomial 0x11D and selectively bit-wise XOR the result of the right-shift with hexadecimal value 8E.

6. The apparatus of claim 1, wherein the first erasure code module is configured to compute, in the Galois field, a product of a data byte and a coefficient x as a left-shift of the data byte and selectively compensate a result of the left-shift based on a value of a most significant bit of the data byte.

7. The apparatus of claim 6, wherein the first erasure code module is further configured to selectively compensate the result of the left-shift with a constant derived from an irreducible polynomial associated with the Galois field.

8. The apparatus of claim 7, wherein the first erasure code module is further configured to compute the syndromes based on a 2⁸ Galois field, including to compute the product of the data byte and the coefficient x as an 8-bit left-shift of the data byte and selectively bit-wise XOR the result of the left-shift with a constant derived from an irreducible polynomial associated with the 2⁸ Galois field.

9. The apparatus of claim 8, wherein the first erasure code module is further configured to compute the syndromes based on an 8-bit Galois field polynomial 0x11D and selectively bit-wise XOR the result of the left-shift with hexadecimal value 1D.

10. The apparatus of claim 1, wherein the first erasure code module is configured to compute syndromes for m greater than 2 with coefficient exponents that consist of integer values −

1, 0, and 1.

11. The apparatus of claim 1, wherein one of the k storage units includes a redundant array of l independent storage units, the apparatus further including:

a second erasure code module to compute n erasure code syndromes based on Reed Solomon (RS) operations in a Galois field and data distributed over the l storage units; and

a second data reconstruction module to reconstruct data of up to n of the l storage units based on the n syndromes and data stored in remaining ones of the l storage units, where l and n are positive integers and n is greater than 2.

12. The apparatus of claim 11, wherein the second erasure code module is configured to compute syndromes for n greater than 2 with coefficient exponents that consist of integer values −

1, 0, and 1.

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.

14. The computer readable medium of claim 13, further including instructions to cause the processor to:

compute, in the Galois field, a product of a data byte and a syndrome coefficient x<sup>−

1</sup> as a right-shift of the data byte; and

selectively compensate a result of the right-shift based on a value of a least significant bit of the data byte.

15. The computer readable medium of claim 14, further including instructions to cause the processor to selectively compensate the result of the right-shift with a constant derived from an irreducible polynomial associated with the Galois field.

16. The computer readable medium of claim 15, further including instructions to cause the processor to compute the syndromes based on a 2⁸ Galois field, including to:

compute the product of the data byte and the coefficient x<sup>−

1</sup> as an 8-bit right-shift of the data byte; and

selectively bit-wise XOR the result of the right-shift with a constant derived from an irreducible polynomial associated with the 2⁸ Galois field.

17. The computer readable medium of claim 16, further including instructions to cause the processor to compute the syndromes based on an 8-bit Galois field polynomial 0x11D, and selectively bit-wise XOR the result of the right-shift with hexadecimal value 8E.

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.

19. The method of claim 18, wherein the computing includes computing, in the Galois field, a product of a data byte and a syndrome coefficient x⁻

1 as a right-shift of the data byte, and selectively compensating a result of the right-shift based on a value of a least significant bit of the data byte.

20. The method of claim 19, wherein the selectively compensating includes selectively compensating the result of the right-shift with a constant derived from an irreducible polynomial associated with the Galois field.

21. The method of claim 20, wherein the computing further includes computing the syndromes based on an 8-bit Galois field polynomial 0x11D, and selectively bit-wise XORing the result of the right-shift with hexadecimal value 8E.

22. The method of claim 18, wherein the computing includes computing, in the Galois field, a product of a data byte and a coefficient x as a left-shift of the data byte, and selectively compensating a result of the left-shift based on a value of a most significant bit of the data byte.

23. The method of claim 22, wherein the selectively compensating includes selectively compensating the result of the left-shift with a constant derived from an irreducible polynomial associated with the Galois field.

24. The method of claim 23, wherein the computing further includes computing the syndromes based on an 8-bit Galois field polynomial 0x11D, and selectively bit-wise XORing the result of the left-shift with hexadecimal value 1D.

25. The method of claim 18, wherein the computing includes computing syndromes for m greater than 2 with coefficient exponents that consist of integer values −

1, 0, and 1.