Local erasure codes for data storage

• US 9,600,365 B2
• Filed: 04/16/2013
• Issued: 03/21/2017
• Est. Priority Date: 04/16/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gopalan, Parikshit S, Fetterly, Dennis Craig, Huang, Cheng, Jenkins, Robert John Jr., Li, Jin, Yekhanin, Sergey
• Primary Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US13/863,912
• Publication Number:
  US 20140310571A1
• Time in Patent Office: 1,435 Days
• Field of Search: 714/801, 714799-800, 714/752, 714/746
• US Class Current: 1/1
• 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 a set of data symbols into a plurality of data groups so that each data group in the plurality of data groups includes a subset of the set of data symbols;

for each data group in the plurality of data groups;

generating a group parity symbol based on the subset of the set of data symbols included in the data group; and

including the group parity symbol in the data group;

storing the plurality of data groups across a first set of machines;

generating at least two global parity symbols, wherein each of the at least two global parity symbols is generated based on all the data symbols in the set of data symbols;

including the at least two global parity symbols in a global parity group;

storing the global parity group across a second set of machines that is different than the first set of machines; and

recovering from failures, wherein the failures comprise;

up to a first failure associated with any one symbol included in each data group of the plurality of data groups;

up to a number of additional failures associated with additional symbols of the plurality of data groups and the at least two global parity symbols in the global parity group, wherein the number of additional failures is up to a number of the at least two global parity symbols; and

wherein generating the at least two 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 plurality of data groups, r is a number of data symbols per data 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 co is a primitive element of the particular field.

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

3. The method of claim 1, wherein recovering from the failures comprises performing an exclusive-or of a group parity symbol of a particular data group against surviving data symbols of the particular data group to recover a failed data symbol of the particular data group.

4. The method of claim 1, 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 ω

_i 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, g is a number of the plurality of data groups, r is a number of data symbols per data 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 co is a primitive element of the particular field.

5. The method of claim 1, wherein generating the at least two global parity symbols comprises solving b equations with P=0, b−

1, wherein the b equations comprise;

Σ

_j=1^gΣ

_i=1^r(ω

_iλ

_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 plurality of data groups, r is a number of data symbols per data 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 a combination of a number of data symbols in the set of data symbols with a number of parity symbols in the group of parity symbols is greater than one more than a locality parameter.

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 set of data symbols into a plurality of data groups so that each data group in the plurality of data groups includes a subset of the set of data symbols;

for each data group in the plurality of data groups;

generate a group parity symbol based on the subset of the set of data symbols included in the data group; and

include the group parity symbol in the data group;

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

generate, as part of a global parity group, a number of first global parity symbols that is equal to a number of the columns, wherein each of the first global parity symbols is generated based on all the data symbols in the set of data symbols;

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

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

store the global parity group across a second plurality of machines that is different than the first plurality of machines; and

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 ω

_i 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 ω

_i 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.

8. The system of claim 7, wherein generating the group parity symbol comprises performing an exclusive-or of the subset of the set of data symbols included in 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:

the plurality of computer-executable components further comprises a recovery module to recover from failures;

the failures comprise no more than a failure of one data symbol in each of the plurality of data groups; and

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

11. The system of claim 7, wherein:

the plurality of computer-executable components further comprises a recovery module to recover from failures;

the failures comprise no more than a failure of one data symbol in each of the plurality of data groups; and

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

12. The system of claim 7, wherein:

the plurality of computer-executable components further comprises a recovery module to recover from failures;

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.

13. The system of claim 7, wherein the plurality of computer-executable components further comprises a recovery module to recover from failures, the recovery module solves 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.

14. The system of claim 7, wherein a combination of a number of data symbols in the set of data symbols with a number of parity symbols in the group of parity symbols is greater than one more than a locality parameter.

15. A system comprising:

one or more processors; and

memory storing computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising;

arranging a set of data symbols into a plurality of data groups so that each data group in the plurality of data groups includes a subset of the set of data symbols;

for each data group in the plurality of data groups;

generating a group parity symbol based on the subset of the set of data symbols included in the data group; and

including the group parity symbol in the data group;

storing the plurality of data groups across a first set of machines;

generating at least two global parity symbols, wherein each of the at least two global parity symbols is generated based on all the data symbols in the set of data symbols;

including the at least two global parity symbols in a global parity group;

storing the global parity group across a second set of machines that is different than the first set of machines; and

recovering from failures, wherein the failures comprise;

up to a first failure associated with any one symbol included in each data group of the plurality of data groups;

up to a number of additional failures associated with additional symbols of the plurality of data groups and the at least two global parity symbols, wherein the number of additional failures is up to a number of the at least two global parity symbols and;

wherein generating the at least two 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 plurality of data groups, r is a number of data symbols per data 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.

16. The system of claim 15, wherein for each data group in the plurality of data groups, the group parity symbol is based upon an exclusive-or of the subset of the set of data symbols included in the data group.

17. The system of claim 15, 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 ω

_i 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, Z_j is a group parity symbol, g is a number of the plurality of data groups, r is a number of data symbols per data 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.

18. The system of claim 15, wherein generating the at least two 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 plurality of data groups, r is a number of data symbols per data 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.

19. The system of claim 15, wherein recovering from the failures comprises performing an exclusive-or of a group parity symbol of a particular data group against surviving data symbols of the particular data group to recover a failed data symbol of the particular data group.

20. The system of claim 15, wherein a combination of a number of data symbols in the set of data symbols with a number of parity symbols is greater than one more than a locality parameter.