Non-parity in grid encoded data storage systems

• US 9,998,539 B1
• Filed: 07/01/2015
• Issued: 06/12/2018
• Est. Priority Date: 07/01/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brock, Adam Frederick, Donlan, Bryan James, Kirschner, James Caleb
• Primary Examiner(s): Whipple, Brian
• Application Number:
  US14/789,815
• Time in Patent Office: 1,077 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Techniques for encoding data storage systems using grid-encoded data storage systems with non-parity linear redundancy encoding schemes are described herein. A grid of shards with derived shards and data shards is generated that is indexed by a first index and a second index and is configured so that each shard is reproducible from other shards with the same first index and is also reproducible from other shards with the same second index. The grid of shards is further configured so that each data row of the grid of shards has at least two derived shards and at least twice as many data shards as derived shards.

Claims

1. A computer-implemented method, comprising:

generating a grid of shards, the grid of shards indexed by row and column, the grid of shards comprising a set of data shards and a set of derived shards, the set of derived shards comprising a set of horizontally-derived shards and a set of vertically-derived shards, wherein each shard of the grid of shards has a corresponding datacenter location, a corresponding row, and corresponding column and is configured such that;

the shard is reproducible from other shards associated with the row and reproducible from other shards associated with the column;

if the shard is a horizontally-derived shard of the set of horizontally-derived shards, the shard is derived based at least in part on a set of data shards having a same corresponding row as the horizontally-derived shard using a first linear redundancy code;

if the shard is a vertically-derived shard of the set of vertically-derived shards, the shard is derived based at least in part on a set of shards having a same corresponding column as the vertically-derived shard using a second linear redundancy code and the shard is derived based at least in part a set of vertically-derived shards having the same corresponding row as the vertically-derived shard using the first redundancy code;

each row of the grid of shards with one or more data shards includes a first number of horizontally-derived shards, the first number being at least two and a subset of the set of data shards with a second number of data shards, the second number being at least twice the first number; and

each row of the grid of shards with less than one data shard includes a subset of the set of vertically-derived shards with a third number of vertically-derived shards, the third number being equal to the first number plus the second number;

receiving a request to repair the grid of shards; and

as a result of receiving the request, at least;

selecting a set of shards to repair based at least in part on the request; and

repairing a shard of the set of shards to repair by at least;

selecting a first set of shards of the grid of shards, each shard of the first set of shards selected based at least in part on the row and column of the shard of the set of shards to repair; and

reproducing the shard of the set of shards to repair from a subset of the set of selected shards based at least in part on a first redundancy code and a second redundancy code.

2. The computer-implemented method of claim 1, wherein:

the first redundancy code is a linear redundancy code;

the shard is reproducible from other shards associated with the row using the first redundancy code;

the second redundancy code is a linear redundancy code; and

the shard is reproducible from other shards associated with the column using the second redundancy code.

3. The computer-implemented method of claim 1, wherein each corresponding datacenter includes at least two columns of the grid of shards.

4. The computer-implemented method of claim 1, wherein:

the first number is two; and

the first redundancy code is a Reed-Solomon code.

5. A system, comprising:

one or more processors; and

memory that stores computer-executable instructions that, as a result of execution by the one or more processors, cause the system to

generate a grid of shards, the grid of shards indexed at least by a first index and a second index, the grid of shards comprising a set of data shards and a set of derived shards, wherein;

each shard of the grid of shards has a corresponding first index and a corresponding second index, each shard configured such that the shard is reproducible from other shards associated with the first index and the shard is reproducible from other shards associated with the second index;

each data shard of the set of data shards has a corresponding data row of the grid of shards, each data row including a subset of the set of derived shards having at a number of derived shards that is at least two and a subset of the set of data shards having at a number of data shards least twice the number of derived shards, the subset of the set of data shards at least including the data shard; and

repair a shard in the grid of shards by at least reproducing the shard from a set of shards associated with the first index or the second index.

6. The system of claim 5, wherein:

the set of derived shards includes a set of vertically-derived shards; and

each vertically-derived shard of the set of vertically-derived shards has a corresponding derived row of the grid of shards, each derived row including a subset of the set of vertically-derived shards having a number of vertically-derived shards equal to a number of shards in each corresponding data row, the subset of the set of vertically-derived shards at least including the vertically-derived shard.

7. The system of claim 5, wherein each corresponding data row has two derived shards and four data shards.

8. The system of claim 5, wherein the second index is based at least in part on a datacenter location associated with the shard.

9. The system of claim 5, wherein the one or more services are further configured to at least:

update a first shard, the first shard having a respective first index and a respective second index;

update a first set of derived shards associated with the respective first index, the first set of derived shards associated with the respective first index having a second shard that is associated with a second index that differs from the respective second index;

update a second set of derived shards associated with the respective second index; and

update a third set of derived shards associated with the second index that differs from the respective second index.

10. The system of claim 5, wherein the one or more services are further configured to at least:

select the shard to repair from grid of shards;

select a set of other shards associated with the first index of the shard to repair; and

reproduce the shard to repair from a subset of the set of other shards associated with the first index using a first redundancy code.

11. The system of claim 5, wherein the one or more services are further configured to at least:

select the shard to repair from the grid of shards;

select a set of other shards associated with the second index of the shard to repair; and

reproduce the shard to repair from a subset of the set of other shards associated with the second index using a second redundancy code.

12. The system of claim 5, wherein each shard of the grid of shards has a corresponding storage device that is at least one of:

magnetic tape, magnetic disk, optical disk, memory resistor, flash memory, or computer memory.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of execution by one or more processors of a computer system, cause the computer system to at least:

generate a grid of shards, the grid of shards indexed by a first index and a second index, the grid of shards including a set of data shards and a set of derived shards, wherein;

each shard of the grid of shards has at least a corresponding first index and corresponding second index and is configured such that the shard is reproducible from other shards associated with the corresponding first index using a first redundancy code and the shard is reproducible from other shards associated with the corresponding second index using a second redundancy code;

each data shard of the set of data shards having a corresponding data row of the grid of shards, each data row including a first subset of the set of derived shards having first number of derived shards and a first subset of the set of data shards having a second number of data shards at least twice the first number of derived shards, the subset of the set of data shards at least including the data shard;

each vertically-derived shard of the set of derived shards having a corresponding derived row of the grid of shards, each derived row including a second subset of the set of derived shards having at least a third number of derived shards equal to a sum of the first number and the second number, the second subset of the set of derived shards at least including the derived shard; and

repair a shard in the grid of shards by at least reproducing the shard from a set of shards associated with the first index or the second index.

14. The non-transitory computer-readable storage medium of claim 13, wherein:

the first number of derived shards is one;

the second number of data shards is three; and

the first redundancy code is a parity redundancy code.

15. The non-transitory computer-readable storage medium of claim 13, wherein at least one of the corresponding first index or the corresponding second index is based at least in part on a geographical location of the shard.

16. The non-transitory computer-readable storage medium of claim 13, wherein:

the first number of derived shards is two;

the second number of data shards is four; and

the first redundancy code is a Reed-Solomon redundancy code.

17. The non-transitory computer-readable storage medium of claim 13, wherein the grid of shards forms a partitioned data set that includes a first set of shards of the grid of shards containing one or more portions of the data set and a second set of shards of the grid of shards generated by applying an erasure code to a subset of the first set of shards.

18. The non-transitory computer-readable storage medium of claim 17, wherein a subset of the partitioned data set is reproducible from a subset of the first set of shards and a subset of the second set of shards using the erasure code.

19. The non-transitory computer-readable storage medium of claim 13, wherein each shard of the grid of shards has a corresponding partitioning of the shards of the grid of shards such that the shard is reproducible from each of at least three partitions that do not contain the shard.

20. The non-transitory computer-readable storage medium of claim 13, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata including a first set of constants associated with the first redundancy code, a second set of constants associated with the second redundancy code, the first number, and the second number.