Accelerated erasure coding for storage systems

Patent metadata

Field	Value
Publication number	US-2017288704-A1
Application number	US-201615281172-A
Country	US
Kind code	A1
Filing date	Sep 30, 2016
Priority date	Mar 30, 2016
Publication date	Oct 5, 2017
Grant date	—

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.

First claim

What is claimed is:

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.

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.

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.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Trusov Maxim
• Danilov Mikhail
• Buinov Konstantin
• Zakharov Kirill
• Kurilov Andrey

Classifications

• H03M13/611

  Specific encoding aspects, e.g. encoding by means of decoding · CPC title

• H03M13/2909 Primary

  Product codes · CPC title

• H03M13/373 Primary

  with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title

• G06F11/1012

  using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence) · CPC title