Incremental media size extension for grid encoded data storage systems

• US 9,904,589 B1
• Filed: 07/01/2015
• Issued: 02/27/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): Kudirka, Joseph
• Application Number:
  US14/789,778
• Time in Patent Office: 972 Days
• Field of Search: 714 62, 714800, 714801, 714804
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/064 Management of blocks
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/1148 Structural properties of the code parity-check or generator matrix
• 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

Abstract

Techniques for incrementally increasing media size in data storage systems using grid encoded data storage techniques are described herein. A grid of shards is created where each shard of the grid of shards has a first index, a second index and each shard also has an associated storage device configured with a storage capacity that is large enough to store the largest set of data on a shard. Upon determining to replace the storage devices of the grid with storage devices that have a different storage capacity, the storage devices can be incrementally replaced within the grid by first padding each shard of the grid of shards with a set of data values, replacing a data shard storage device with a device of the different storage capacity, and replacing a set of derived shard storage devices with devices of the different storage capacity.

Claims

1. A computer-implemented method, comprising:

under the control of one or more computer systems configured with executable instructions,

generating a grid of shards, the grid of shards forming a partitioned data set, the grid of shards being 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;

the partitioned data set 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;

each shard of the grid of shards has 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 associated with the row; and

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 associated with the column;

each shard of the grid of shards having a corresponding first data size; and

each shard of the grid of shards has a corresponding storage device of a set of storage devices that stores the shard, each storage device of the set of storage devices having a first storage capacity sufficient for a maximum corresponding first data size of the grid of shards;

determining a second data size for the shards of the grid of shards;

padding each shard of the grid of shards with a corresponding number of zero values, the corresponding number of zero values determined based at least in part on subtracting the corresponding first data size from the second data size;

replacing a first storage device of the set of storage devices that stores a first data shard of the grid of shards with a first replacement storage device that stores the first data shard, the first replacement storage device having a second storage capacity sufficient for the second data size, the first data shard having a corresponding first row and first column;

replacing a first subset of the set of storage devices with a first set of replacement storage devices having a storage capacity sufficient for the second data size, each replacement storage device of the first set of replacement storage devices configured to store a corresponding derived shard of a first set of derived shards associated with the first row, the first set of derived shards associated with the first row having a shard that is associated with a second column;

replacing a second subset of the set of storage devices with a second set of replacement storage devices having a storage capacity sufficient for the second data size, each replacement storage device of the second set of replacement storage devices configured to store a corresponding derived shard of a second set of derived shards associated with the first column; and

replacing a third subset of the set of storage devices with a third set of replacement storage devices having a storage capacity sufficient for the second data size, each replacement storage device of the third set of replacement storage devices configured to store a corresponding derived shard of a third set of derived shards associated with the second column.

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

each storage device of the set of storage devices is a magnetic tape drive;

each storage device of the second set of replacement storage devices is a disk drive; and

each storage device of the third set of replacement storage devices is a disk drive.

3. The computer-implemented method of claim 1, wherein one or more of the storage devices of the set of storage devices is a logical storage device that includes a plurality of physical storage devices, each logical storage device addressable as a single storage device.

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

each derived shard of the first set of derived shards is derived based at least in part on a parity redundancy code;

each derived shard of the second set of derived shards is derived based at least in part on a Reed-Solomon redundancy code; and

each derived shard of the third set of derived shards is derived based at least in part on 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 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, a corresponding second index, and a corresponding storage device having a first storage capacity sufficient to store a first maximum data amount corresponding to a first shard size associated with the grid of shards and configured to store the shard, 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;

determine a second maximum data amount corresponding to a second shard size associated with the grid of shards;

pad each shard of the grid of shards with an amount of data that is based at least in part on a difference between the first storage capacity and a second storage capacity, the second storage capacity sufficient to store the second maximum data amount, the amount of data including a set of data values; and

if a selected storage device corresponding to a first shard of the grid of shards is replaced with a replacement storage device having a storage capacity sufficient for the second storage capacity, replace a first set of storage devices with a second set of storage devices having a storage capacity sufficient for the second storage capacity, the storage devices in the first set of storage devices selected based at least in part on the first index of the first shard and based at least in part on the second index of the first shard.

6. The system of claim 5, wherein the second maximum data amount is greater than the first maximum data amount.

7. The system of claim 5, wherein the first set of storage devices includes:

a first subset of the set of storage devices corresponding to a first set of derived shards associated with the first index of the first shard, the first set of derived shards associated with the first index of the shard having a second shard with a respective second index;

a second subset of the set of storage devices corresponding to a second set of derived shards associated with the second index of the first shard; and

a third subset of the set of storage devices corresponding to a third set of derived shards associated with the respective second index of the second shard.

8. The system of claim 7, wherein:

each derived shard of the first set of derived shards is derived based at least in part on a first redundancy code;

each derived shard of the second set of derived shards is derived based at least in part on a second redundancy code; and

each derived shard of the third set of derived shards is derived based at least in part on the second redundancy code.

9. The system of claim 8, wherein:

the first redundancy code is at least one of;

a parity code, a Reed-Solomon code, a repetition code, a cyclic code, a Hamming code, a Reed-Muller code, a Goppa code, a BCH code, a Golay code, or an expander code; and

the second redundancy code is at least one of;

a parity code, a Reed-Solomon code, a repetition code, a cyclic code, a Hamming code, a Reed-Muller code, a Goppa code, a BCH code, a Golay code, or an expander code.

10. The system of claim 8, wherein the set of data values is a set of zero values of a first finite field associated with the first redundancy code that are zero values of a second finite field associated with the second redundancy code.

11. The system of claim 5, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata at least including the first maximum data amount and the second maximum data amount.

12. The system of claim 5, wherein the corresponding second index of each shard of the grid of shards is based at least in part on a datacenter location of the corresponding storage device.

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:

use 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, a corresponding second index, and a corresponding storage device, the grid of shards configured such that each shard of the grid of shards is reproducible from other shards associated with the first index and each shard of the grid of shards is reproducible from other shards associated with the second index, each corresponding storage device having a first storage capacity sufficient to store a first maximum data amount corresponding to a first shard size associated with the grid of shards,

determine a second maximum data amount corresponding to a second shard size associated with the grid of shards and pad each shard with an amount of data that is based at least in part on a difference between the first maximum data amount and the second maximum data amount, the amount of data including a set of data values;

replace a first storage device configured to store a first shard with a first replacement storage device configured to store the first shard, the first shard having a corresponding first index and a corresponding second index; and

replace each storage device of a set of storage devices with a corresponding replacement storage device, each storage device of the set of storage devices corresponding to a derived shard in a set of derived shards, the set of derived shards including;

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

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

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

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

determine a first storage capacity of the first storage device;

determine a second storage capacity of the first replacement storage device;

replace the first storage device with the replacement storage device if the second storage capacity is greater than the first storage capacity; and

move a set of data from the first storage device to the replacement storage device.

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

determine a first media type of the first storage device;

determine a second media type of the first replacement storage device; and

replace the first storage device with the replacement storage device if the second media type differs from the first media type.

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

the first media type is at least one of;

magnetic tape, magnetic disk, optical disk, flash memory, memory resistor, or computer memory; and

the second media type is at least one of;

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

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

each derived shard of the first subset of derived shards is derived based at least in part on a first linear redundancy code;

each derived shard of the second subset of derived shards is derived based at least in part on a second linear redundancy code; and

each derived shard of the third subset of derived shards is derived based at least in part on the second linear redundancy code.

18. The non-transitory computer-readable storage medium of claim 17, wherein each data value of the set of data values is at least one of:

a first zero value of a first finite field associated with the first linear redundancy code or a second zero value of a second finite field associated with the second linear redundancy code.

19. 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 at least including the first maximum data amount, the second maximum data amount, and the first storage capacity of the corresponding storage device.

20. The non-transitory computer-readable storage medium of claim 13, wherein the replacement storage device is configured to read from a storage medium associated with the first storage device.