Grid encoded data storage systems for efficient data repair

• US 10,162,704 B1
• Filed: 07/01/2015
• Issued: 12/25/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: Kirschner, James Caleb, Donlan, Bryan James, Lazier, Colin Laird, Franklin, Paul David
• Primary Examiner(s): Lamarre, Guy
• Application Number:
  US14/789,783
• Time in Patent Office: 1,273 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Techniques for encoding data storage systems using grid encoded data storage systems are described herein. Data to be stored in a data storage system is obtained and the 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. Each of the shards has at least a first index corresponding to one dimension of the grid and a second index corresponding to a second dimension of the grid. Loss of a plurality of data shards can be repaired because each shard is reproducible from one or more shards with a first index that is associated with the first index of the shard and is also reproducible from one or more shards with a second index that is associated with the second index of the shard.

Claims

1. A computer-implemented method, comprising:

storing, on a plurality of storage devices, a grid of shards indexed by a first index and a second index, wherein individual shards of the grid of shards are each reproducible from first shards associated with a respective value of the first index and reproducible from second shards associated with a respective value of the second index, the first shards different from the second shards;

detecting that a shard of the grid of shards is to be replaced, the shard being associated with a first index value of the first index and a second index value of the second index; and

replacing the shard by at least;

updating the shard with new data to result in an updated shard;

storing the updated shard on a storage device of the plurality of storage devices, the storage device associated with the first index value and the second index value;

updating a plurality of shards in the grid of shards, the plurality of shards associated with the second index value, to result in an updated plurality of shards; and

storing, on a subset of the plurality of storage devices associated with the second index value the updated plurality of shards.

2. The computer-implemented method of claim 1, wherein each shard in the grid of shards is reproducible from a first set of shards using a first linear redundancy code and from a second set of shards using a second linear redundancy code different from the first linear redundancy code.

3. The computer-implemented method of claim 1, wherein each shard in the grid of shards is reproducible from a first set of shards using a Reed Solomon redundancy code and from a second set of shards using a parity redundancy code.

4. The computer-implemented method of claim 1, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata at least including a first set of constants associated with a first redundancy code and a second set of constants associated with a second redundancy code different from the first redundancy code.

5. The computer-implemented method of claim 1, wherein the new data is generated from other shards of the grid of shards, the other shards associated with the first index value.

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

obtain data;

use the obtained data to generate a grid of shards such that;

the grid of shards is indexed by at least a first index and a second index; and

the grid of shards comprises a set of data shards and a set of derived shards, each shard of the grid of shards having a corresponding value of a first index and corresponding value of a second index and being configured such that the shard is reproducible from a plurality of shards associated with the first value and each shard of the grid of shards is reproducible from a plurality of other shards associated with the second value, the plurality of shards associated with the first value being different from the plurality of shards associated with the second value;

store, on a plurality of storage devices respectively associated with the first index and the second index, shards of the grid of shards; and

as a result of detecting that a first shard of the grid of shards is to be updated with new data, the first shard having a respective first index value of the first index and a respective second index value of the second index;

update the first shard with the new data, thereby generating an updated first shard; and

update, based on the updated first shard, a first set of derived shards of the grid of shards and a second set of derived shards of the grid of shards, the first set of derived shards being associated with the first index value, the second set of derived shards being associated with the second index value, thereby respectively generating an updated first set of derived shards and an updated second set of derived shards.

7. The system of claim 6, wherein the one or more services further update, based at least in part on the updated first set of derived shards and the updated second set of derived shards, other shards of the grid of shards.

8. The system of claim 6, wherein the one or more services further, as a result of receiving a request to retrieve data from a data shard of the grid, at least:

if an integrity of a first shard is sufficient to fulfill the request to retrieve the data from the first shard, fulfill the request using the first shard; and

if the integrity of the first shard is insufficient to fulfill the request, at least;

reproduce the first shard from other shards to result in a reproduced first shard; and

fulfill the request using the reproduced first shard.

9. The system of claim 6, wherein the one or more services further:

select a set of shards associated with a first index value of the first index; and

reproduce a data shard from a subset of the set of shards associated with the first index value.

10. The system of claim 9, wherein the one or more services further:

select a set of shards associated with a second index value of the second index; and

reproduce the data shard from a subset of the set of other shards associated with the second index value.

11. The system of claim 6, wherein each shard of the grid of shards is stored on a respective storage device in a storage location associated with the plurality of storage devices, the storage location selected based at least in part on the corresponding second index value of the shard.

12. The system of claim 11, wherein the respective storage device is at least one of:

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

13. The system of claim 12, wherein the respective storage device is selected based at least in part on a number of changes to the shard per unit time.

14. The system of claim 6, wherein the grid of shards forms a partitioned data set that includes one or more shards containing one or more portions of the data set and one or more shards generated by applying an erasure code to the one or more shards containing the one or more portions of the data set.

15. 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:

receive a request to update a shard of a grid of shards, the grid of shards indexed by a first index and a second index, wherein each shard of the grid of shards has at least a corresponding value of a first index and corresponding value from a second index and is configured such that the shard is reproducible from first shards associated with the corresponding first index value and the shard is reproducible from second shards associated with the corresponding second index value, the first shards being different from the second shards; and

as a result of receiving the request;

update a first shard of the grid, the first shard having a corresponding first index value of the first index and a corresponding second index value of the second index;

update a first set of derived shards associated with the corresponding first index value to result in an updated first set of derived shards, the first set of derived shards associated with the corresponding first index having a second shard that is associated with a third index value of the second index that differs from the corresponding second index value;

update a second set of derived shards associated with the corresponding second index value to result in an updated second set of derived shards; and

store, at respective locations of one or more data storage devices associated with the computer system, the updated first set of derived shards and the updated second set of derived shards.

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

17. The non-transitory computer-readable storage medium of claim 15, wherein:

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

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

the first redundancy code is different than the second redundancy code.

18. The non-transitory computer-readable storage medium of claim 15, 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.

19. The non-transitory computer-readable storage medium of claim 18, 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.

20. The non-transitory computer-readable storage medium of claim 15, 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.