Accelerated erasure coding for storage systems

• US 10,110,258 B2
• Filed: 09/30/2016
• Issued: 10/23/2018
• Est. Priority Date: 03/30/2016
• 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, Buinov, Konstantin, Zakharov, Kirill, Kurilov, Andrey
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US15/281,172
• Publication Number:
  US 20170288704A1
• Time in Patent Office: 753 Days
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon 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

Abstract

A method for generating coded fragments comprises receiving data to be encoded, splitting the data into a plurality of data fragments, identifying a first group of data fragments from among the plurality of data fragments using a coding matrix, summing the data fragments within the first group of data fragments to generate a first group sum, and using the first group sum to calculate at least a portion of two or more coded fragments.

Claims

1. A method comprising:

receiving data to be encoded;

splitting the data into a plurality of data fragments;

identifying a first group of data fragments from among the plurality of data fragments using a coding matrix;

summing the data fragments within the first group of data fragments to generate a first group sum; and

using the first group sum to calculate at least a portion of two or more coded fragments for erasure coding and storing the at least a portion of the two or more coded fragments in a data protection system configured to restore one or more lost ones of the data fragments.

2. The method of claim 1 wherein the coding matrix comprises a binary coding matrix, wherein identifying the first group of data fragments from among the plurality of data fragments comprises counting a number of 1'"'"'s within rows of the coding matrix.

3. The method of claim 2 wherein summing the data fragments within the first group of data fragments comprising XOR'"'"'ing the data fragments within the first group of data fragments.

4. The method of claim 2 further comprising:

updating two or more rows of the coding matrix to set 1'"'"'s to 0'"'"'s, wherein each of the two or more updated rows of the coding matrix is associated with a corresponding one of the two or more coded fragments.

5. The method of claim 4 further comprising:

identifying a second group of data fragments from among the plurality of data fragments using the updated coding matrix;

summing the data fragments within the second group of data fragments to generate a second group sum; and

using the second group sum to calculate at least a portion of two or more coded fragments.

6. The method of claim 1 wherein identifying the first group of data fragments comprises using a greedy algorithm.

7. The method of claim 6 wherein identifying a group of the data fragments using a greedy algorithm comprises:

generating two or more groups of data fragments each having the same number of data fragments;

for each of the two or more groups of data fragments, counting a number of coded fragments whose calculations include the sum of the data fragments within the group; and

identifying the first group of data fragments as the group of data fragments from among the two or more groups of data fragments having the highest count.

8. The method of claim 1 further comprising:

storing the plurality of data fragments and the two or more coded fragments across multiple nodes of a distributed storage system.

9. A system comprising:

one or more processors;

a volatile memory; and

a non-volatile memory storing computer program code that when executed on the processor causes execution across the one or more processors of a process operable to perform the operations of;

receiving data to be encoded;

splitting the data into a plurality of data fragments;

identifying a first group of data fragments from among the plurality of data fragments using a coding matrix;

summing the data fragments within the first group of data fragments to generate a first group sum; and

using the first group sum to calculate at least a portion of two or more coded fragments for erasure coding and storing the at least a portion of the two or more coded fragments in a data protection system configured to restore one or more lost ones of the data fragments.

10. The system of claim 9 wherein the coding matrix comprises a binary coding matrix, wherein the computer program code causes execution of a process operable to identify the first group of data fragments from among the plurality of data fragments by counting a number of 1'"'"'s within rows of the coding matrix.

11. The system of claim 10 wherein the computer program code causes execution of a process operable to sum the data fragments within the first group of data fragments by XOR'"'"'ing the data fragments within the first group of data fragments.

12. The system of claim 10 wherein the computer program code causes execution of a process further operable to:

update two or more rows of the coding matrix to set 1'"'"'s to 0'"'"'s, wherein each of the two or more updated rows of the coding matrix is associated with a corresponding one of the two or more coded fragments.

13. The system of claim 12 wherein the computer program code causes execution of a process further operable to:

identify a second group of data fragments from among the plurality of data fragments using the updated coding matrix;

sum the data fragments within the second group of data fragments to generate a second group sum; and

use the second group sum to calculate at least a portion of two or more coded fragments.

14. The system of claim 9 wherein the computer program code causes execution of a process operable to identify the first group of data fragments using a greedy algorithm.

15. The system of claim 14 wherein the computer program code causes execution of a process operable to identify a group of the data fragments using a greedy algorithm by:

generating two or more groups of data fragments each having the same number of data fragments;

for each of the two or more groups of data fragments, counting a number of coded fragments whose calculations include the sum of the data fragments within the group; and

identifying the first group of data fragments as the group of data fragments from among the two or more groups of data fragments having the highest count.

16. The system of claim 9 wherein the computer program code causes execution of a process further operable to:

store the plurality of data fragments and the two or more coded fragments across multiple nodes of a distributed storage system.

17. A computer program product tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to:

receive data to be encoded;

split the data into a plurality of data fragments;

identify a first group of data fragments from among the plurality of data fragments using a coding matrix;

sum the data fragments within the first group of data fragments to generate a first group sum; and

use the first group sum to calculate at least a portion of two or more coded fragments for erasure coding and storing the at least a portion of the two or more coded fragments in a data protection system configured to restore one or more lost ones of the data fragments.