Rebundling grid encoded data storage systems

• US 9,959,167 B1
• Filed: 07/01/2015
• Issued: 05/01/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: Donlan, Bryan James, Lazier, Colin Laird
• Primary Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US14/789,825
• Time in Patent Office: 1,035 Days
• 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/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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 rebundling grid encoded data storage systems are described herein. A new grid of shards is created based in part on shards from a first grid of shards. The second grid of shards contains data shards, including one or more data shards from the first grid of shards, and derived shards that are indexed by row and column and is configured so that shards in the second grid are reproducible from shards in the same row using a first redundancy code and are also reproducible from shards in the same column using a second redundancy code. The derived shards of the second grid of shards are then derived from other shards in the second grid of shards using the first redundancy code and the second redundancy code.

Claims

1. A computer-implemented method, comprising:

generating a first grid of shards, the first grid of shards indexed by row and column, the first grid of shards comprising a first set of data shards and a first set of derived shards, the first set of derived shards comprising a first set of horizontally-derived shards and a first set of vertically-derived shards, wherein each shard of the first 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 corresponding to the shard of the first grid of shards using a first redundancy code and reproducible from other shards associated with the column corresponding to the shard of the first grid of shards using a second redundancy code;

generating a second grid of shards, the second grid of shards indexed by row and column, the second grid of shards comprising a second set of data shards and a second set of derived shards, the second set of data shards including at least twice as many data shards as the first set of data shards, the second set of data shards including the first set of data shards, the second set of derived shards comprising a second set of horizontally-derived shards and a second set of vertically-derived shards, wherein each shard of the second 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 corresponding to the shard of the second grid of shards using a third redundancy code and reproducible from other shards associated with the column corresponding to the shard of the second grid of shards using the second redundancy code;

deriving a horizontally-derived shard in the second grid of shards by at least;

selecting a first set of shards of the second grid of shards based at least in part on having the same corresponding row as the horizontally-derived shard; and

reproducing the horizontally-derived shard from a subset of the first set of shards based at least in part on the third redundancy code;

deriving a vertically-derived shard in the second grid of shards by at least;

selecting a second set of shards of the second grid of shards based at least in part on having the same corresponding column as the vertically-derived shard; and

reproducing the vertically-derived shard from a subset of the second set of shards based at least in part on the first redundancy code; and

storing, on one or more storage devices corresponding to datacenter locations of the second grid of shards, the second grid of shards.

2. The computer-implemented method of claim 1,

wherein each corresponding datacenter location of the second grid of shards has at least two corresponding columns of the second grid of shards.

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

the first redundancy code is a parity redundancy code; and

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

4. The computer-implemented method of claim 1, wherein the third redundancy code is a Reed-Solomon redundancy code.

5. A system, comprising at least one computing device configured to implement one or more services, wherein the one or more services are configured to:

generate a second grid of shards based at least in part on a first grid of shards, the second grid of shards being stored one or more storage devices across a plurality of datacenter locations and indexed at least by row and column, the second grid of shards comprising a set of data shards and a set of derived shards, the set of data shards at least including one or more data shards from the first grid of shards, each shard of the second grid of shards having a corresponding row, a corresponding column, and a corresponding datacenter location, each shard of the second grid of shards configured such that the shard is reproducible from other shards associated with the row using a first redundancy code and the shard is reproducible from other shards associated with the column using a second redundancy code;

update a first subset of the set of derived shards based at least in part on applying the first redundancy code to one or more shards of the second grid of shards, the one or more shards selected based at least in part on having the same corresponding row; and

update a second subset of the set of derived shards based at least in part on applying the second redundancy code to one or more shards of the second grid of shards, the one or more shards selected based at least in part on having the same corresponding column.

6. The system of claim 5, wherein:

each shard of the first grid of shards has a corresponding row; and

each shard of the first grid of shards is configured such that the shard is reproducible from other shards of the first grid of shards associated with the row using the first redundancy code.

7. The system of claim 5, wherein the set of derived shards includes one or more horizontally-derived shards from the first grid of shards, the one or more horizontally-derived shards derived based at least in part on the first redundancy code.

8. The system of claim 5, wherein the set of derived shards includes one or more vertically-derived shards from the first grid of shards, the one or more vertically-derived shards derived based at least in part on the second redundancy code.

9. The system of claim 5, wherein:

each row of the second grid of shards with at least one data shard includes two horizontally-derived shards and four data shards; and

each row of the second grid of shards without data shards includes six vertically-derived shards.

10. The system of claim 5, wherein:

each row of the second grid of shards with at least one data shard includes one horizontally-derived shard and three data shards; and

each row of the second grid of shards without data shards includes four vertically-derived shards.

11. The system of claim 10, wherein the first redundancy code is a parity redundancy code.

12. The system of claim 5, wherein:

the first redundancy code is a Reed-Solomon redundancy code; and

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

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

using a first 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, the first grid of shards indexed by row and column, wherein each shard of the first grid of shards has at least a corresponding row, a corresponding column, and a corresponding datacenter location, each shard of the first grid of shards configured such that each shard of the grid of shards is reproducible from other shards associated with the corresponding row using a first redundancy code and each shard of the first grid of shards is reproducible from other shards associated with the corresponding column using a second redundancy code,

generate a second grid of shards based at least in part on the first grid of shards by causing the computer system to at least;

add, for each shard of the first grid of shards, a corresponding pair of shards to the second grid of shards, each pair of shards having a first shard and a second shard, such that;

the first shard of the pair of shards has a same corresponding row as the shard, a same corresponding column as the shard, and a same corresponding datacenter location as the shard;

the second shard of the pair of shards has the same corresponding row as the shard and the same datacenter location as the shard; and

if the shard is a data shard, the first shard of the pair of shards is based at least in part on the shard;

derive a first set of derived shards of the second grid of shards such that each shard of the second grid of shards is reproducible from other shards of the second grid of shards associated with the corresponding row of the shard using a third redundancy code; and

derive a second set of derived shards of the second grid of shards such that each shard of the second grid of shards is reproducible from other shards of the second grid of shards associated with the corresponding column of the shard using the second redundancy code; and

store the second grid of shards on one or more storage devices corresponding to the datacenter locations.

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

select a shard of the second grid of shards to repair;

select a set of other shards from the second grid of shards associated with the row of the shard; and

reproduce the shard from a subset of the set of other shards associated with the row using the third redundancy code.

15. The non-transitory computer-readable storage medium of claim 13, wherein the third redundancy code is a Reed-Solomon redundancy code.

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

select a shard of the second grid of shards to repair;

select a set of other shards of the second grid of shards associated with the column of the shard; and

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

17. The non-transitory computer-readable storage medium of claim 13, wherein each shard of the second 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.

18. The non-transitory computer-readable storage medium of claim 17, wherein the first shard of the pair of shards has the same corresponding storage device as the shard.

19. The non-transitory computer-readable storage medium of claim 13, wherein, if the shard is a horizontally-derived shard, the first shard of the pair of shards is a horizontally-derived shard based at least in part on the shard and the second shard of the pair of shards is a horizontally-derived shard.

20. The non-transitory computer-readable storage medium of claim 13, wherein, if the shard is a vertically-derived shard, the first shard of the pair of shards is a vertically-derived shard based at least in part on the shard and the second shard of the pair of shards is a vertically-derived shard.