Local Erasure Codes for Data Storage

• US 20140310571A1
• Filed: 04/16/2013
• Published: 10/16/2014
• Est. Priority Date: 04/16/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fetterly, Dennis Craig, Huang, Cheng, Li, Jin, Yekhanin, Sergey, Gopalan, Parikshit S., Jenkins, Robert John Jr.
• Granted Patent: US 9,600,365 B2
• Time in Patent Office: Days
• US Class Current: 714/764
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

In some examples, an erasure code can be implemented to provide for fault-tolerant storage of data. Maximally recoverable cloud codes, resilient cloud codes, and robust product codes are examples of different erasure codes that can be implemented to encode and store data. Implementing different erasure codes and different parameters within each erasure code can involve trade-offs between reliability, redundancy, and locality. In some examples, an erasure code can specify placement of the encoded data on machines that are organized into racks.

Claims

1. A method comprising:

arranging data symbols into data groups;

for each data group;

generating a group parity symbol; and

including the group parity symbol in the data group;

generating one or more global parity symbols, wherein the one or more global parity symbols are based on the data symbols; and

recovering from failures, wherein the failures comprise;

up to a first failure associated with a data symbol or group parity symbol of each data group; and

up to a number of additional failures associated with one or more of the data symbols, the group parity symbols, and the global parity symbols, wherein the number of additional failures is up to a number of the global parity symbols.

2. The method of claim 1, wherein for each group, the group parity symbol is based upon an exclusive-or of the data symbols of the group.

3. The method of claim 1, wherein generating one or more global parity symbols comprises solving b equations with P=0, b−

1, wherein the b equations comprise;

setting a first sum plus a second sum equal to zero, wherein;

the first sum comprises a sum from j=1 to g of;

a sum from i=1 to r of;

a product of ω

ⁱ and λ

_j, raised to a power of 2^P, and multiplied by X_i,j; and

the second sum comprises a sum from i=1 to b of;

a product of ω

ⁱ and λ

_g+1, raised to a power of 2^P, and multiplied by Y_i,

wherein X_i,j is a data symbol, Y_i is a global parity symbol, g is a number of the data groups, r is a number of data symbols per group, b is the number of global parity symbols, {λ

₁, . . . , λ

_g+1} is a collection of elements such that any b of them are linearly independent in a particular field, and ω

is a primitive element of the particular field.

4. The method of claim 1, wherein the failures comprise no more than a failure of one data symbol in each of the data groups;

and

wherein recovering from the failures comprises performing an exclusive-or of a group parity symbol of a group against surviving data symbols of the group to recover a failed data symbol of the group.

5. The method of claim 3, wherein the recovering from failures comprises solving b+g equations, wherein the b+g equations comprise:

g equations with j=1, . . . , g, that comprise;

setting a first sum equal to Z_j, wherein the first sum comprises a sum from i=1 to r of X_i,j; and

b equations, with P=0, . . . , b−

1, that comprise;

setting a first sum plus a second sum equal to zero, wherein;

the first sum comprises a sum from j=1 to g of;

a sum from i=1 to r of;

 

a product of ω

ⁱ and λ

_j, raised to a power of 2^P, and multiplied by X_i,j; and

the second sum comprises a sum from i=1 to b of;

a product of ω

ⁱ and λ

_g+1, raised to a power of 2^P, and multiplied by Yⁱ,

wherein X_i,j is a data symbol, Y_i is a global parity symbol, Z_j is a group parity symbol, g is a number of the data groups, r is a number of data symbols per group, b is the number of global parity symbols, {λ

₁, . . . , λ

_g+1} is a collection of elements such that any b of them are linearly independent in a particular field, and ω

is a primitive element of the particular field.

6. The method of claim 1, wherein generating one or more global parity symbols comprises solving b equations with P=0, . . . , b−

1, wherein the b equations comprise;

Σ

_j=1^gΣ

_i=1^r(ω

ⁱλ

_j)^2PX_i,j+Σ

_i=1^b(ω

ⁱλ

_g+1)^2PY_i=0,

wherein X_i,j is a data symbol, Y_i is a global parity symbol, g is a number of the data groups, r is a number of data symbols per group, b is the number of global parity symbols, {λ

₁, . . . , λ

_g+1} is a collection of elements such that any b of them are linearly independent in a particular field, and ω

is a primitive element of the particular field.

7. A system, comprising:

one or more processors;

a memory that includes a plurality of computer-executable components, the plurality of computer-executable components comprising an encoder module to;

arrange a first plurality of machines into a grid of rows and columns;

arrange a plurality of data symbols into data groups;

for each data group of the data groups;

generate a group parity symbol; and

include the group parity symbol in the data group;

store each of the data groups in a column of the first plurality of machines;

generate a number of first global parity symbols equal to a number of the columns to form a global parity group, wherein each first global parity symbol is based on each of the data symbols;

generate a second global parity symbol, wherein the second global parity symbol is a parity of the first global parity symbols; and

include the second global parity symbol in the global parity group.

8. The system of claim 7, wherein generating the group parity symbol comprises performing an exclusive-or of the data symbols of the data group.

9. The system of claim 7, wherein generating the second global parity symbol comprises performing an exclusive-or of the first global parity symbols.

10. The system of claim 7, wherein generating the first global parity symbols comprises solving r equations with P=0, . . . , r−

1, wherein the r equations comprise;

setting a first sum plus a second sum equal to zero, wherein;

the first sum comprises a sum from j=1 to g of;

a sum from i=1 to r of;

a product of ω

ⁱ and λ

_j, raised to a power of 2^P, and multiplied by X_i,j; and

the second sum comprises a sum from i=1 to r of;

a product of ω

ⁱ and λ

_g+1, raised to a power of 2^P, and multiplied by Y_i,

wherein X_i,j is a data symbol, Y_i is a global parity symbol, g is a number of the rows, r is a number of the columns, {λ

₁, . . . , λ

_g+1} is a collection of elements such that any g of them are linearly independent in a particular field, and ω

is a primitive element of the particular field.

11. The system of claim 7, wherein the recovery module recovers from failures, wherein the failures comprise no more than a failure of one data symbol in each of the data groups;

and

wherein recovering from the failures comprises performing a linear operation between a group parity symbol of a group and surviving data symbols of the group to recover a failed data symbol of the group.

12. The system of claim 7, wherein the recovery module recovers from failures, wherein the failures comprise no more than a failure of one data symbol in each of the data groups;

and

wherein recovering from the failures comprises performing an exclusive-or of a group parity symbol of a group against surviving data symbols of the group to recover a failed data symbol of the group.

13. The system of claim 7, wherein the recovery module recovers from failures, wherein the failures comprise a failure of one of the first global parity symbols;

and

recovering from the failures further comprises performing an exclusive-or of the second global parity symbol against surviving first global parity symbols of the global parity group to recover a failed first global parity symbol of the global parity group.

14. The system of claim 7, wherein the recovering from failures comprises solving g+r+1 equations, wherein the g+r+1 equations comprise:

g equations with j=1, . . . , g, that comprise;

setting a first sum equal to Z_j, wherein the first sum comprises a sum from i=1 to r of X_i,j;

a (g+1)th equation that comprises;

setting a first sum equal to Z_g+1, wherein the first sum comprises a sum from i=1 to r of Y_i; and

r equations, with P=0, . . . , r−

1, that comprise;

setting a first sum plus a second sum equal to zero, wherein;

the first sum comprises a sum from j=1 to g of;

a sum from i=1 to r of;

 

a product of ω

ⁱ and λ

_j, raised to a power of 2^P, and multiplied by X_i,j; and

the second sum comprises a sum from i=1 to r of;

a product of ω

ⁱ and λ

_g+1, raised to a power of 2^P, and multiplied by Y_i,

wherein X_i,j is a data symbol, Y_i is a global parity symbol, Z_j is a group parity symbol, Z_g+1 is the second global parity symbol, g is a number of the rows, r is a number of the columns, {λ

₁, . . . , λ

_g+1} is a collection of elements such that any g of them are linearly independent in a particular field, and ω

is a primitive element of the particular field.

15. A computer-readable medium storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

partitioning a stripe into data chunks to form data symbols;

separately encoding the stripe, the encoding comprising;

arranging the data symbols into a grid comprising a first number of rows and a second number of columns;

for each row of the grid, generating a row parity symbol using a code that is different than codes used to generate parity symbols for other rows of the grid, wherein the row parity symbol is based on data symbols of the row;

associating each row parity symbol with a corresponding row to form a row parity column of the grid that comprises each row parity symbol;

for each column of the grid, generating a column parity symbol based on data symbols of the column; and

associating each column parity symbol with a corresponding column to form a column parity row of the grid that comprises each column parity symbol.

16. The computer-readable medium of claim 15, further comprising computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising:

generating an additional one or more row parity symbols using a code that is different than codes used to generate parity symbols for other rows of the grid, wherein the one or more row parity symbols are based on data symbols of the row; and

associating each of the one or more row parity symbols with each corresponding row to form one or more additional row parity columns of the grid that comprise each of the one or more row parity symbols.

17. The computer-readable medium of claim 15, further comprising computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising correcting a failure pattern with a width of up to a number of row parity symbols per row plus one and a height of two, wherein the failure pattern does not involve the column parity row.

18. The computer-readable medium of claim 15, wherein each column parity is a simple exclusive-or of data symbols of a column corresponding to the column parity.

19. The computer-readable medium of claim 15, further comprising computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising storing coded symbols of the stripe to different failure domains.

20. The computer-readable medium of claim 15, wherein generating the row parity symbol comprises obtaining coefficients of the row parity symbol by solving A times R equations, with i from 1 to A and k from 1 to R, equations comprising:

setting a sum equal to zero, wherein;

the sum is from j=1 to B+2 of;

X_i,j divided by a sum of b_i,k and a_j,

wherein X_i,j is a data symbol, A is the number of rows, B is the number of rows, R is a number of parities per row, {a_j}<sub>i≦

j≦

B+R</sub> is a set of distinct elements on Galois Field F, {b_i,k}<sub>1≦

i≦

A,1≦

k≦

R</sub> is another set of distinct elements on the Galois Field F, and a_j and b_i,k are distinct so that no two elements are equal.