Accelerated Galois field coding for storage systems

Patent metadata

Field	Value
Publication number	US-10291265-B2
Application number	US-201615193409-A
Country	US
Kind code	B2
Filing date	Jun 27, 2016
Priority date	Dec 25, 2015
Publication date	May 14, 2019
Grant date	May 14, 2019

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.

First claim

What is claimed is:

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.

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Trusov Maxim
• Danilov Mikhail
• Tchoub Ivan
• Karpenkov Sergey
• Koyushev Sergey

Classifications

• H03M13/154 Primary

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title

• H03M13/151

  using error location or error correction polynomials · CPC title

• H03M13/6516 Primary

  Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/2909

  Product codes · CPC title