Architecture for implementing erasure coding

Patent metadata

Field	Value
Publication number	US-2016188407-A1
Application number	US-201414586628-A
Country	US
Kind code	A1
Filing date	Dec 30, 2014
Priority date	Dec 30, 2014
Publication date	Jun 30, 2016
Grant date	—

Abstract

Disclosed is an improved approach to implement erasure coding, which can address multiple storage unit failures in an efficient manner. The approach can effectively address multiple failures of storage units by implementing diagonal parity sets.

First claim

What is claimed is:

1 . A method, comprising:
identifying a plurality of storage units; determining a number of storage unit failures to be tolerated; computing one or more parity data that corresponds to the number of number of storage unit failures to be tolerated, wherein the one or more parity data comprises a row parity, first diagonal parity, and a second diagonal parity; and wherein the first diagonal parity and second diagonal parity are negative reciprocals of one another.

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 data within the plurality of storage units is organized as a matrix of rows and columns, and additional rows of data are added to the matrix.

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 set comprises a diagonal parity having a different slope from the second diagonal parity set.

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

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 set corresponds to multiple slopes.

11 . The method of claim 1 , wherein preset values are identified, and 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; identifying a line of data having one missing data; and computing the one missing data by considering the 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 data within the set of storage units is organized as a matrix of rows and columns, and additional rows of data are added to the matrix, and at least one value in the additional rows is used to compute the missing data.

15 . The method of claim 12 , wherein data within the set of storage units is organized as a matrix of rows and columns, and 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 computer readable medium, the 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; computing one or more parity data that corresponds to the number of number of storage unit failures to be tolerated, wherein the one or more parity data comprises a row parity, first diagonal parity, and a second diagonal parity; and wherein the first diagonal parity and second diagonal parity are negative reciprocals of one another.

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 data within the plurality of storage units is organized as a matrix of rows and columns, and additional rows of data are added to the matrix.

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 set comprises a diagonal parity having a different slope from the second diagonal parity set.

27 . The computer program product of claim 21 , wherein the one or more parity data comprises a row parity set.

28 . The computer program product of claim 21 , wherein each of the one or more parity data is computed independently of another parity set.

29 . The computer program product of claim 21 , wherein a parity set is re-computed in parallel with re-computation of another parity set upon a change to underlying data.

30 . The computer program product of claim 21 , wherein the first diagonal parity set corresponds to multiple slopes.

31 . The computer program product of claim 21 , wherein preset values are identified, and the preset values do not physically consume storage space in the plurality of storage units.

32 . A computer program product embodied on a computer readable medium, the 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 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; identifying a line of data having one missing data; and computing the one missing data by considering the parity data for the line in combination with known data in the line.

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

34 . The computer program product of claim 32 , wherein data within the set of storage units is organized as a matrix of rows and columns, and additional rows of data are added to the matrix, and at least one value in the additional rows is used to compute the missing data.

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