Accelerated Galois field coding for storage systems

1. A method for use with a distributed storage system having a plurality of storage nodes each having locally attached storage devices, the method comprising:

retrieving a single-element multiplication matrix for a Galois field (GF);

generating, by the distributed storage system, a multi-element multiplication matrix for the GF using the single-element multiplication matrix;

receiving, at the distributed storage system, a request to store data;

erasure-coding the data to produce a plurality of data fragments and a plurality of coded fragments, the erasure-coding being performed by at least one processor in the distributed storage system based on the multi-element multiplication matrix, the erasure-coding being performed by using one or more XOR-based addition operations;

storing the plurality of data fragments within local storage devices of at least two of the plurality of storage nodes; and

storing the plurality of coded fragments within local storage devices of at least two of the plurality of storage nodes.

2. The method of claim 1 wherein the Galois field includes 2 4 elements and the single-element multiplication matrix is a 16×16 matrix.

3. The method of claim 2 wherein the multi-element multiplication matrix is a 16×256 matrix.

4. The method of claim 1 , wherein erasure-coding the data includes:

dividing the data into the plurality of data fragments arranged as a column vector;

retrieving a coding matrix having elements in the Galois field; and

calculating the dot product of ones of the data fragments and rows of the coding matrix using the multi-element multiplication matrix to generate the plurality of coded fragments.

5. The method of claim 1 further comprising storing the multi-element multiplication matrix to non-volatile memory.

6. The method according to claim 1 , further including generating the multi-element multiplication matrix for the GF using the single-element multiplication matrix prior to encoding data.

7. A storage system, comprising:

a plurality of storage nodes each having locally attached storage devices; and

a processor configured to:

retrieve a single-element multiplication matrix for a Galois field (GF);

generate a multi-element multiplication matrix for the GF using the single-element multiplication matrix;

receive a request to store data;

erasure-code the data to produce a plurality of data fragments and a plurality of coded fragments, the erasure coding being performed by using the multi-element multiplication matrix, the erasure coding being performed by using one or more XOR-based addition operations;

store the plurality of data fragments within local storage devices of at least two of the plurality of storage nodes; and

store the plurality of coded fragments within local storage devices of at least two of the plurality of storage nodes.

8. The storage system of claim 7 wherein the Galois field includes 2 4 elements and the single-element multiplication matrix is a 16×16 matrix.

9. The storage system of claim 8 wherein the multi-element multiplication matrix is a 16×256 matrix.

10. The storage system of claim 7 wherein erasure-coding the data includes

divide the data into the plurality of data fragments arranged as a column vector;

retrieve a coding matrix having elements in the Galois field; and

calculate the dot product of ones of the data fragments and rows of the coding matrix using the multi-element multiplication matrix to generate plurality of coded fragments.

11. The storage system of claim 7 further comprising a non-volatile memory, wherein the processor is further configured to store the multi-element multiplication matrix to the non-volatile memory.

12. The storage system according to claim 7 , wherein the multi-element multiplication matrix for the GF is generated using the single-element multiplication matrix prior to encoding data.