Erasure code data protection and recovery computation system and method

Abstract

A system and method for performing erasure code data protection and recovery computations using simple arithmetic and data manipulation functions. Other embodiments set forth techniques for using the computation functions with a multiplicity of compact one-dimension table lookup operations. A set of assigned multi-threaded processor threads perform computations on data values in parallel to generate erasure code data protection information and to perform data recovery operations using available data and the data protection information. During normal operations, in one embodiment, threads may perform parallel computations using a small set of simple arithmetic operations and data manipulation functions. In other embodiments, the threads may also use a multiplicity of compact one-dimension lookup tables stored within the multi-threaded processor or otherwise accessible by the multi-threaded processor to perform the computations.

What is claimed is: 
     
       1. A system for storing data, the system comprising:
 a first processing circuit; 
 the first processing circuit being configured to send to a second processing circuit:
 a plurality of input Data Units; 
 a request specifying an erasure code operation to be performed, the erasure code operation being:
 a parity generation operation; or 
 a systematic data recovery operation; and 
 
 one or more constants to be used in performing the erasure code operation 
 
 wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to: 
 discover, at startup, an identification number of the first core and of a thread to be executed by the first core, and 
 perform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 
 
     
     
       2. The system of  claim 1 , wherein the one or more constants comprise:
 a powers table, listing, for each of a plurality of input values, a power of the input value in a Galois field; and 
 a logarithm table, listing, for each of the plurality of input values, a logarithm of the input value in the Galois field. 
 
     
     
       3. The system of  claim 2 , wherein each of the input Data Units is an n-bit number, n being a positive-integer power of 2, and the Galois field is GF( 2   n ). 
     
     
       4. The system of  claim 1 , wherein the one or more constants comprise an inverse array suitable for performing a systematic data recovery operation. 
     
     
       5. The system of  claim 4 , wherein the inverse array is a N×N array that when multiplied, in a Galois field, by a N×1 vector produces N recovered Data Units, N being a positive integer. 
     
     
       6. The system of  claim 1 , wherein the one or more constants comprise a multiplication table. 
     
     
       7. The system of  claim 6 , wherein the multiplication table lists, for each possible value of a first factor, a product of the first factor and a weight, the weight being one of a plurality of weights used to calculate a Q Erasure Code Data Unit as a weighted exclusive-or of Data Units in a slice. 
     
     
       8. A system for storing data, the system comprising:
 a first processing circuit; 
 the first processing circuit being configured to send to a second processing circuit:
 a plurality of input Data Units; 
 a request specifying an erasure code operation to be performed, the erasure code operation being:
 a parity generation operation; or 
 a systematic data recovery operation; and 
 
 a kernel, the kernel comprising machine code instructions that when executed by the second processing circuit cause the second processing circuit to perform the erasure code operation, 
 
 wherein the kernel includes instructions for performing a multiplication of a first factor and a second factor, without conditional operations, 
 wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to: 
 discover, at startup, an identification number of the first core and of a thread to be executed by the first core, and 
 perform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 
 
     
     
       9. The system of  claim 8 , wherein the instructions for performing the multiplication of the first factor and the second factor comprise a plurality of left-shift operations and a plurality of addition operations, each addition operation of the plurality of addition operations being a modulo 2 addition operation and corresponding to a corresponding bit of the second factor having a value of 1. 
     
     
       10. A system for storing data, the system comprising:
 a first processing circuit; and 
 a second processing circuit, 
 the first processing circuit being configured to send to the second processing circuit:
 a plurality of input Data Units; 
 a request specifying an erasure code operation to be performed, the erasure code operation being:
 a parity generation operation; or 
 a systematic data recovery operation; and 
 
 one or more constants to be used in performing the erasure code operation, 
 
 wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to: 
 discover, at startup, an identification number of the first core and of a thread to be executed by the first core, and 
 perform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 
 
     
     
       11. The system of  claim 10 , wherein the first processing circuit is a central processing unit and the second processing circuit is a graphics processing unit. 
     
     
       12. The system of  claim 10 , wherein the one or more constants comprise:
 a powers table, listing, for each of a plurality of input values, a power of the input value in a Galois field; and 
 a logarithm table, listing, for each of the plurality of input values, a logarithm of the input value in the Galois field. 
 
     
     
       13. The system of  claim 12 , wherein each of the input Data Units is an n-bit number, n being a positive-integer power of 2, and the Galois field is GF(2^n). 
     
     
       14. The system of  claim 10 , wherein the one or more constants comprise an inverse array suitable for performing a systematic data recovery operation. 
     
     
       15. The system of  claim 14 , wherein the inverse array is a N×N array that when multiplied, in a Galois field, by a N×1 vector produces N recovered Data Units, N being a positive integer. 
     
     
       16. The system of  claim 10 , wherein the one or more constants comprise a multiplication table. 
     
     
       17. The system of  claim 16 , wherein the multiplication table lists, for each possible value of a first factor, a product of the first factor and a weight, the weight being one of a plurality of weights used to calculate a Q Erasure Code Data Unit as a weighted exclusive-or of Data Units in a slice. 
     
     
       18. A method for storing or restoring data, the method comprising:
 sending, by a first processing circuit to a second processing circuit:
 a plurality of input Data Units; 
 a request specifying an erasure code operation to be performed, the erasure code operation being:
 a parity generation operation; or 
 a systematic data recovery operation; and 
 
 one or more constants to be used in performing the erasure code operation; and 
 
 performing, by the second processing circuit, the requested erasure code operation, 
 wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to: 
 discover, at startup, an identification number of the first core and of a thread to be executed by the first core, and 
 perform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 
 
     
     
       19. The method of  claim 18 , wherein the first processing circuit is a central processing unit and the second processing circuit is a graphics processing unit.