Determining data redundancy in grid encoded data storage systems

• US 10,394,762 B1
• Filed: 07/01/2015
• Issued: 08/27/2019
• Est. Priority Date: 07/01/2015
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Kirschner, James Caleb, Donlan, Bryan James, Lazier, Colin Laird
• Primary Examiner(s): Phillips, III, Albert M
• Application Number:
  US14/789,837
• Time in Patent Office: 1,518 Days
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/17 Details of further file system functions
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• 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 in grid encoded data storage systems are described herein. Data is stored in a grid of shards using grid encoding techniques that store the data in a combination of data shards and derived shards. Because the data is redundantly encoded in the grid of shards, a plurality of distinct copies of the data are reproducible from the grid of shards where each distinct copy is reproducible from a non-overlapping set of shards of the grid of shards.

Claims

1. A computer-implemented method, comprising:

generating a grid of shards, the grid of shards indexed by row and column and 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, the grid of shards based at least in part on a first redundancy coding scheme and a second redundancy coding scheme, the first redundancy coding scheme and the second redundancy coding scheme based at least in part on a minimum number of partitions associated with a set of data items stored in the grid of shards such that;

each shard of the grid of shards has a corresponding first row and corresponding first column and is configured such that;

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

if the shard is a horizontally-derived shard of the set of horizontally-derived shards, the shard is reproducible based at least in part on a set of data shards associated with the first row using the first redundancy coding scheme; and

if the shard is a vertically-derived shard of the set of vertically-derived shards, the shard is reproducible based at least in part on a set of shards associated with the first column using the second redundancy coding scheme; and

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, the partitioning including;

a first partition that contains a plurality of shards of the grid of shards with a row equal to the first row and a column different from the first column;

a second partition that contains a plurality of shards of the grid of shards with a column equal to the first column and a row different than the first row; and

a third partition that contains a plurality of shards of the grid of shards with a row different than the first row and a column different than the first column.

2. The computer-implemented method of claim 1, wherein at least two partitions of the partitioning are in different datacenter locations of a set of datacenter locations.

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

the first redundancy coding scheme is based at least in part on a parity redundancy code; and

the second redundancy coding scheme is based at least in part on a Reed-Solomon redundancy code.

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

the shard is reproducible from the plurality of shards of the first partition using the first redundancy encoding scheme;

the shard is reproducible from the plurality of shards of the second partition using the second redundancy encoding scheme; and

the shard is reproducible from the plurality of shards of the third partition using the first redundancy encoding scheme and the second redundancy encoding scheme.

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

the partitioning further includes one or more additional partitions, each of the one or more additional partitions not including the shard, not including the plurality of shards of the first partition, not including the plurality of shards of the second partition, not including the plurality of shards of the third partition; and

the shard is reproducible from the plurality of shards of each of the one or more additional partitions using at least one of;

the first redundancy encoding scheme or the second redundancy encoding scheme.

6. A system, comprising at least one computing device that implements one or more services, wherein the one or more services:

generate a grid of shards, the grid of shards;

being indexed at least by a first index and a second index;

comprising a set of data shards and a set of derived shards, each shard of the grid of shards;

having a corresponding first index and a corresponding second index;

being reproducible from other shards associated with the first index of the shard; and

being reproducible from other shards associated with the second index of the shard;

store the grid of shards; and

reproduce a particular shard of the stored grid of shards from a plurality of shards of the stored grid of shards each including a first index different than the first index of the particular shard and a second index different than the second index of the particular shard.

7. The system of claim 6, wherein:

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

the shard is reproducible from other shards associated with the second index using a second redundancy code; and

the shard is reproducible from the plurality of shards using the first redundancy code and the second redundancy code.

8. The system of claim 7, wherein each shard of the grid of shards has a corresponding partitioning the partitioning including at least three partitions that do not contain the shard, the partitioning including:

a first partition that contains the other shards associated with the first index of the shard, the other shards having a second index different from the second index of the shard;

a second partition that contains the other shards associated with the second index of the shard, the other shards having a first index different than the first index of the shard; and

a third partition that contains a plurality of shards of the grid of shards with a first index different than the first index of the shard and a second index different than the second index of the shard.

9. The system of claim 7, wherein:

the first redundancy code is selected based at least in part on a minimum number of partitions associated with a set of data items stored in the grid of shards; and

the second redundancy code is selected based at least in part on the minimum number of partitions.

10. The system of claim 7, wherein the first redundancy code is a parity redundancy code and the second redundancy code is a Reed-Solomon redundancy code.

11. The system of claim 7, wherein the one or more services are further configured to repair an unavailable shard by at least:

select a first set of shards based at least in part on the first index of the unavailable shard; and

generate a replacement shard for the unavailable shard from a subset of the set of shards using the first redundancy code.

12. The system of claim 7, wherein the one or more services are further configured to repair an unavailable shard by at least:

select a set of shards based at least in part on the second index of the unavailable shard; and

generate a replacement shard for the unavailable shard from a subset of the set of shards using the first redundancy code.

13. The system of claim 6, wherein a number of derived shards of the grid of shards is determined based at least in part on a minimum number of partitions associated with a set of data items stored in the grid of shards.

14. A computer-implemented method, comprising:

generating a grid of shards, the grid of shards indexed by at least 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 and is 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; and

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;

storing the grid of shards; and

reproducing a particular shard of the stored grid of shards from a partition of the at least three partitions that do not contain the shard.

15. The computer-implemented method of claim 14, wherein the corresponding partitioning includes:

a first partition that contains a plurality of shards of the grid of shards with a first index equal to the corresponding first index of the shard and a second index different from the corresponding second index of the shard;

a second partition that contains a plurality of shards of the grid of shards with a second index equal to the corresponding second index of the shard and a first index different than the corresponding first index of the shard; and

a third partition that contains a plurality of shards of the grid of shards with a first index different than the corresponding first index of the shard and a second index different than the corresponding second index of the shard.

16. The computer-implemented method of claim 15, wherein:

the shard is reproducible from the plurality of shards of the first partition using a first redundancy code;

the shard is reproducible from the plurality of shards of the second partition using a second redundancy code; and

the shard is reproducible from the plurality of shards of the third partition using the first redundancy code and the second redundancy code.

17. The computer-implemented method of claim 16, further comprising determining a minimum number of derived shards of the grid of shards, the minimum number determined based at least in part on a minimum number of partitions in the partitioning.

18. The computer-implemented method of claim 17, wherein:

the first redundancy code is selected based at least in part on the minimum number of partitions in the partitioning; and

the second redundancy code is selected based at least in part on the minimum number of partitions in the partitioning.

19. A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed 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 at least 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 and is 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; and

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;

store the grid of shards; and

reproduce a particular shard of the stored grid of shards based at least in part on the other shards associated with the first index.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

as a result of receiving a request to store data in the grid of shards, at least;

update a first shard associated with the request, the first shard having a corresponding first index and a corresponding second index;

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

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

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

21. The non-transitory computer-readable storage medium of claim 19, wherein the corresponding partitioning includes:

a first partition that contains a plurality of shards of the grid of shards with a first index equal to the corresponding first index of the shard and a second index different from the corresponding second index of the shard;

a second partition that contains a plurality of shards of the grid of shards with a second index equal to the corresponding second index of the shard and a first index different than the corresponding first index of the shard; and

a third partition that contains a plurality of shards of the grid of shards with a first index different than the corresponding first index of the shard and a second index different than the corresponding second index of the shard.

22. The non-transitory computer-readable storage medium of claim 21, wherein:

the shard is reproducible from the plurality of shards of the first partition using a first redundancy code;

the shard is reproducible from the plurality of shards of the second partition using a second redundancy code; and

the shard is reproducible from the plurality of shards of the third partition using the first redundancy code and the second redundancy code.

23. The non-transitory computer-readable storage medium of claim 22, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata at least including a set of constants associated with at least one of the first redundancy code or the second redundancy code.

24. The non-transitory computer-readable storage medium of claim 19, wherein the corresponding partitioning is based at least in part on a set of requirements received from a user of the computer system.

25. The non-transitory computer-readable storage medium of claim 19, wherein the corresponding partitioning is based at least in part on a set of requirements received from a third-party to the computer system.