Architecture for implementing erasure coding

Patent metadata

Field	Value
Publication number	US-9672106-B2
Application number	US-201414586628-A
Country	US
Kind code	B2
Filing date	Dec 30, 2014
Priority date	Dec 30, 2014
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

A method for implementing erasure coding, including identifying a plurality of storage units, determining a number of storage unit failures to be tolerated, organizing data within the plurality of storage units as a matrix of rows and columns for computing one or more parity data, configuring the matrix to include one or more additional rows having preset values, computing the one or more parity data from the matrix that corresponds to the number of storage unit failures to be tolerated, wherein the one or more parity data comprises a row parity, a first diagonal parity, and a second diagonal parity, wherein the one or more additional rows having the preset values are used to compute the first diagonal parity and the second diagonal parity; and wherein the first diagonal parity comprises a different slope from the second diagonal parity.

First claim

What is claimed is:

1. A computer implemented method, comprising:
identifying a plurality of storage units;
determining a number of storage unit failures to be tolerated;
configuring a matrix having rows and columns, wherein a first set of columns corresponds to the plurality of storage units and a second set of columns having an amount of columns corresponding to the number of storage unit failures to be tolerated, the second set of columns comprising one or more parity data, wherein a first set of rows corresponds to data from respective storage units and a second set of rows comprising one or more additional rows having preset values, the one or more additional rows corresponding to the number of storage unit failures to be tolerated minus one;
computing the one or more parity data to populate the second set of columns of the matrix, wherein the one or more parity data comprises a row parity, a first diagonal parity, and a second diagonal parity, wherein the first diagonal parity and the second diagonal parity are computed from the preset values in the one or more additional rows; and
wherein the first diagonal parity comprises a different slope from the second diagonal parity.

2. The method of claim 1 , wherein the first diagonal parity set comprises an ascending diagonal parity and the second diagonal parity set comprises a descending diagonal parity.

3. The method of claim 1 , wherein the one or more additional rows added to the matrix provide enough known values such that lines missing a single block of data can be identified for allowing a recovery of the single block of data via the one or more parity data.

4. The method of claim 1 , wherein the storage units comprise software-based storage.

5. The method of claim 4 , where the storage unit corresponds to a file or extent group.

6. The method of claim 1 , wherein the first diagonal parity and second diagonal parity are negative reciprocals of one another.

7. The method of claim 1 , wherein the one or more additional rows are determined based at least in part on a multiple of an absolute value of the slope of the first diagonal parity.

8. The method of claim 1 , wherein each of the one or more parity data is computed independently of another parity set.

9. The method of claim 1 , wherein a parity set is re-computed in parallel with re-computation of another parity set upon a change to underlying data.

10. The method of claim 1 , wherein the first diagonal parity corresponds to multiple slopes.

11. The method of claim 1 , wherein the preset values for the one or more additional rows are zeros, and wherein the preset values do not physically consume storage space in the plurality of storage units.

12. A method to recover data, comprising:
identifying a set of storage units having a failure, wherein the set of storage units corresponds to a set of one or more parity data that had been computed and wherein the set of one or more parity data comprises a first diagonal parity set and a second diagonal parity set, and wherein data within the set of storage units are organized as a matrix having rows and columns with one or more additional rows having preset values, wherein an amount of the one or more additional rows added to the matrix corresponds to a number of storage unit failures to be tolerated minus one;
identifying a line of data having a single missing data, wherein the single missing data within the line of data is identifiable based at least in part on the amount of the one or more additional rows having preset values being added to the matrix when computing the one or more parity data comprising diagonal parity data; and
computing the single missing data by considering a parity data from the one or more parity data for the line in combination with known data in the line.

13. The method of claim 12 , wherein the first diagonal parity set comprises an ascending diagonal parity and the second diagonal parity set comprises a descending diagonal parity.

14. The method of claim 12 , wherein the amount of the one or more additional rows added to the matrix provides enough known values such that lines missing a single data can be identified for allowing a recovery of the single data via the one or more parity data.

15. The method of claim 12 , wherein a row in the matrix is recovered by first recovering with the first diagonal parity set, followed by using the second diagonal parity set, and then followed by using a row parity set.

16. The method of claim 12 , wherein the storage units comprise software-based storage.

17. The method of claim 12 , wherein the first diagonal parity set comprises a diagonal parity having a different slope from the second diagonal parity set.

18. The method of claim 12 , wherein the set of one or more parity data comprises a row parity set.

19. The method of claim 12 , wherein recovery is performed in parallel by concurrently performing recovery on data from a top row having missing data and on data from a bottom row having missing data.

20. The method of claim 12 , wherein recovery is performed in parallel by concurrently processing multiple stripes of data that each has only a single missing data.

21. A computer program product embodied on a non-transitory computer readable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for performing a process, comprising:
identifying a plurality of storage units;
determining a number of storage unit failures to be tolerated;
configuring a matrix having rows and columns, wherein a first set of columns corresponds to the plurality of storage units and a second set of columns having an amount of columns corresponding to the number of storage unit failures to be tolerated, the second set of columns comprising one or more parity data, wherein a first set of rows corresponds to data from respective storage units and a second set of rows comprising one or more additional rows having preset values, the one or more additional rows corresponding to the number of storage unit failures to be tolerated minus one;
computing the one or more parity data to populate the second set of columns of the matrix, wherein the one or more parity data comprises a row parity, a first diagonal parity, and a second diagonal parity, wherein the first diagonal parity and the second diagonal parity are computed from the preset values in the one or more additional rows; and
wherein the first diagonal parity comprises a different slope from the second diagonal parity.

22. The computer program product of claim 21 , wherein the first diagonal parity set comprises an ascending diagonal parity and the second diagonal parity set comprises a descending diagonal parity.

23. The computer program product of claim 21 , wherein the one or more additional rows added to the matrix provide enough known values such that lines missing a single block of data can be identified for allowing a recovery of the single block of data via the one or more parity data.

24. The computer program product of claim 21 , wherein the storage units comprise software-based storage.

25. The computer program product of claim 24 , where the storage unit corresponds to a file or extent group.

26. The computer program product of claim 21 , wherein the first diagonal parity and second diagonal parity are negative recip

Assignees

• Nutanix Inc

Inventors

• Bronnikov Dmitri
• Gill Binny Sher

Classifications

• G06F11/1076 Primary

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