Distributed data storage with reduced storage overhead using reduced-dependency erasure codes

• US 10,146,618 B2
• Filed: 01/04/2016
• Issued: 12/04/2018
• Est. Priority Date: 01/04/2016
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Pamies-Juarez, Lluis, Guyot, Cyril, Mateescu, Robert Eugeniu
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US14/987,244
• Publication Number:
  US 20170192848A1
• Time in Patent Office: 1,065 Days
• Field of Search: 714755, 714752, 714799, 714786, 714801
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/036 Heuristic code construction methods, i.e. code construction or code search based on using trial-and-error
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• 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/2792 Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• 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
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A system that implements a near-optimal, reduced-dependency erasure code construction to redundantly distribute computer data across multiple storage nodes includes a memory that stores machine instructions and a processor that executes the machine instructions to group storage segments into discrete groups, each of which corresponds to an individual storage node. The processor further executes the machine instructions to represent regeneration constraints and associate the constraints with storage segments in multiple storage nodes. The processor also executes the machine instructions to generate a parity check matrix based on the regeneration constraints, the associations and the storage segments. The processor additionally executes the machine instructions to construct a generator matrix based on the parity check matrix.

Claims

1. A device for redundantly storing computer data, comprising:

a non-transitory memory that stores machine instructions; and

a processor coupled to the non-transitory memory that executes the machine instructions to;

generate a first set of representations of a plurality of storage segments;

generate a second set of representations of a plurality of regeneration constraints, wherein each of the regeneration constraints is configured such that when data is lost each of the regeneration constraints regenerates a portion of the plurality of storage segments so that the lost data is recovered, and each of the regeneration constraints regenerates and recovers a lost portion of the plurality of storage segments;

group the first set of representations into a plurality of discrete groups;

create a plurality of associations correlating each of the second set of representations with one of the first set of representations in each discrete group of a subset of the plurality of discrete groups;

generate a parity check matrix based on the first set of representations, the second set of representations, and the plurality of associations; and

construct a generator matrix based on the parity check matrix, each of the plurality of discrete groups corresponding to a respective storage node of a plurality of storage nodes, and the plurality of associations randomly distributed among the plurality of discrete groups.

2. The device of claim 1, wherein the processor further executes the machine instructions to:

determine a first number and a second number;

divide an amount of storage data into a plurality of data segments equal to the first number; and

apportion a plurality of redundant segments equal to the second number, the plurality of storage segments including the plurality of data segments and the plurality of redundant segments, and a ratio of the first number to a sum of the first and second numbers corresponding to an encoding rate.

3. The device of claim 2, wherein the processor further executes the machine instructions to:

construct a bipartite graph and generate the parity check matrix based on the graph,

wherein the first set of representations includes a first plurality of vertices representing the plurality of data segments and the plurality of redundant segments, the second set of representations includes a second plurality of vertices representing the plurality of regeneration constraints, and the plurality of associations includes a plurality of edges connecting each of the first plurality of vertices with a respective vertex of the second plurality of vertices, the plurality of edges approximately equally distributed among the first vertices, the first plurality of vertices and the second plurality of vertices forming two disjoint sets of vertices, and the first plurality of vertices grouped into approximately equally-sized subsets corresponding to each of the plurality of discrete groups.

4. The device of claim 1, wherein each of the plurality of associations corresponding to a respective regeneration constraint of the plurality of regeneration constraints associates the respective regeneration constraint to a respective storage node of the plurality of storage nodes.

5. The device of claim 1, wherein each of the plurality of associations corresponds to a respective data segment of the plurality of data segments or to a respective redundant segment of the plurality of redundant segments.

6. The device of claim 1, wherein each of the plurality of regeneration constraints corresponds to ten or fewer of the plurality of associations.

7. The device of claim 1, wherein executing the machine instructions to construct the generator matrix further comprises constructing an inner generator matrix based on the parity check matrix, and constructing an outer generator matrix based on the inner generator matrix and the first number of data segments, wherein the generator matrix is the matrix product of the inner generator matrix and outer generator matrix.

8. A method for redundantly storing computer data, comprising:

generating a first set of representations, each of the first set of representations corresponding to a respective storage segment of a plurality of storage segments;

grouping the first set of representations into a plurality of discrete groups, each of the plurality of discrete groups corresponding to a respective storage node of a plurality of storage nodes;

generating a second set of representations, each of the second set of representations corresponding to a respective regeneration constraint of a plurality of regeneration constraints, wherein each of the regeneration constraints is configured such that when data is lost each of the regeneration constraints regenerates a portion of the plurality of storage segments so that the lost data is recovered, and each of the regeneration constraints regenerates and recovers a lost portion of the plurality of storage segments;

creating a plurality of associations that correlate each respective regeneration constraint with one respective storage segment corresponding to each discrete group of a subset of the plurality of discrete groups, the plurality of associations substantially equally randomly distributed among the plurality of discrete groups;

generating a parity check matrix based on the first set of representations, the second set of representations, and the plurality of associations; and

constructing a generator matrix at least in part based on the parity check matrix.

9. The method of claim 8, further comprising:

dividing an amount of storage data into a first number of data segments; and

apportioning a second number of redundant segments, the plurality of storage segments including the first number of data segments and the second number of redundant segments.

10. The method of claim 9, further comprising:

determining the first number; and

determining the second number, wherein a ratio of the first number to a sum of the first number and the second number corresponds to an encoding rate.

11. The method of claim 9, wherein constructing the generator matrix further comprises:

constructing an inner generator matrix based on the parity check matrix; and

constructing an outer generator matrix based on the inner generator matrix and the first number of data segments, wherein the generator matrix is the matrix product of the inner generator matrix and outer generator matrix.

12. The method of claim 11, wherein constructing the outer generator matrix further comprises designing the outer generator matrix with a first dimension equal to an opposite dimension of the inner generator matrix, and a second dimension equal to a minimum rank corresponding to a submatrix based on a combination of column sets associated with the inner generator matrix, each column set including a third number of columns equal to a fourth number of storage segments in each of the plurality of discrete groups.

13. The method of claim 12, wherein constructing the outer generator matrix further comprises interleaving a matrix column including a redundant parity value with an identity matrix having a third dimension equal to the number of first data segments.

14. The method of claim 9, further comprising determining a third number of discrete groups of the plurality of discrete groups in the subset, wherein the third number corresponds to a degree associated with each respective regeneration constraint.

15. The method of claim 8, further comprising:

constructing a bipartite graph wherein the first set of representations includes a first plurality of vertices representing the first number of data segments and the second number of redundant segments, the second set of representations includes a second plurality of vertices representing the plurality of regeneration constraints, and the plurality of associations includes a plurality of edges connecting each of the first plurality of vertices with a respective vertex of the second plurality of vertices, the plurality of edges approximately equally distributed among the first vertices, the first plurality of vertices and the second plurality of vertices forming two disjoint sets of vertices, and the first plurality of vertices grouped into approximately equally-sized subsets corresponding to each discrete group of the plurality of discrete groups; and

generating the parity check matrix based on the bipartite graph.

16. The method of claim 8, wherein each of the plurality of associations corresponds to a respective data segment of the first number of data segments or to a respective redundant segment of the second number of redundant segments.

17. The method of claim 8, wherein each of the plurality of associations corresponding to each respective regeneration constraint of the plurality of regeneration constraints correlates the respective regeneration constraint to a respective storage node of the plurality of storage nodes.

18. The method of claim 8, wherein the plurality of storage nodes includes at least five and not greater than twenty-five storage nodes, and the plurality of storage segments includes at least fifty and not greater than two thousand five hundred storage segments.

19. A computer program product for redundantly storing computer data, comprising:

a non-transitory, computer-readable storage medium encoded with instructions, which when executed by a processor, cause the processor to perform;

dividing an amount of storage data into a first number of data segments;

apportioning a second number of redundant segments, a plurality of storage segments including the first number of data segments and the second number of redundant segments;

generating a first set of representations corresponding to the plurality of storage segments;

grouping the first set of representations into a plurality of discrete groups corresponding to a plurality of storage nodes;

generating a second set of representations corresponding to a plurality of regeneration constraints, wherein each of the regeneration constraints is configured such that when data is lost each of the regeneration constraints regenerates a portion of the plurality of storage segments so that the lost data is recovered, and each of the regeneration constraints regenerates and recovers a lost portion of the plurality of storage segments;

creating a plurality of associations that correlate each of the plurality of regeneration constraints with one of the plurality of storage segments corresponding to each discrete group of a subset of the plurality of discrete groups, the plurality of associations substantially equally randomly distributed among the plurality of discrete groups;

generating a parity check matrix based on the first set of representations, the second set of representations, and the plurality of associations; and

constructing a generator matrix at least in part based on the parity check matrix.

20. The computer program product of claim 19, further comprising instructions, which when executed by the processor, cause the processor to perform:

constructing a bipartite graph wherein the first set of representations includes a first plurality of vertices representing the first number of data segments and the second number of redundant segments, the second set of representations includes a second plurality of vertices representing the plurality of regeneration constraints, and the plurality of associations includes a plurality of edges connecting each of the first plurality of vertices with one of the second plurality of vertices, the plurality of edges approximately equally distributed among the first plurality of vertices, the first plurality of vertices and the second plurality of vertices forming two disjoint sets of vertices, and the first plurality of vertices grouped into approximately equally-sized subsets corresponding to each of the plurality of discrete groups; and

generating the parity check matrix based on the bipartite graph.