Accelerated Galois field coding for storage systems

• US 10,291,265 B2
• Filed: 06/27/2016
• Issued: 05/14/2019
• Est. Priority Date: 12/25/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Trusov, Maxim, Danilov, Mikhail, Tchoub, Ivan, Karpenkov, Sergey, Koyushev, Sergey
• Primary Examiner(s): Abraham, Esaw T
• Application Number:
  US15/193,409
• Publication Number:
  US 20170187398A1
• Time in Patent Office: 1,051 Days
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/2909 Product codes
• 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
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

A technique to accelerate Galois Field (GF) arithmetic. The technique, which does not rely on any specific processor instruction set, can be used to accelerate erasure coding within storage systems.

Claims

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⁴ 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⁴ 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.