Flexible data storage device mapping for data storage systems

• US 10,324,790 B1
• Filed: 12/17/2015
• Issued: 06/18/2019
• Est. Priority Date: 12/17/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Donlan, Bryan James, Lazier, Colin Laird
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): Gandhi, Dipakkumar B
• Application Number:
  US14/973,716
• Time in Patent Office: 1,279 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/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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

A logical storage layer for shared storage systems interposes between address ranges of the shards and the storage devices on which the shards are stored. The shards may be logically addressed using a plurality of addressable zones, to which the storage devices are independently mapped. Data requests related to a given piece of data associated with a shard may involve multiple storage devices, and vice versa.

Claims

1. A computer-implemented method, comprising:

generating, from a data set, a first set of shards defined by a redundancy encoding scheme, each shard of the first set of shards having a corresponding size that corresponds to a smallest available capacity of any storage device among a set of storage devices capable of storing the first set of shards;

mapping each shard of the first set of shards to a logical storage layer such that each shard corresponds to a plurality of addressable zones allocated by the logical storage layer, each addressable zone corresponding to an address range of the shard;

mapping each storage device of the set of storage devices to at least one addressable zone of the plurality of addressable zones independently of the mapping of the first set of shards to the logical storage layer;

storing the first set of shards on the set of storage devices in accordance with the plurality of addressable zones to which the set of storage devices are mapped; and

in response to information indicating failure of a storage device mapped to a respective subset of the plurality of addressable zones, repairing, using the redundancy encoding scheme, at least one corresponding address range of at least one corresponding shard for each addressable zone of the respective subset of the plurality of addressable zones.

2. The computer-implemented method of claim 1, wherein the redundancy encoding scheme generates the first set of shards as a bundle-encoded set of shards.

3. The computer-implemented method of claim 1, wherein the redundancy encoding scheme generates the first set of shards as a grid-encoded set of shards.

4. The computer-implemented method of claim 1, wherein the storage devices of the set of storage devices have the same available capacity.

5. A system, comprising:

at least one computing device that implements one or more services, wherein the one or more services at least;

generate a set of redundancy coded shards by processing a set of data with a redundancy code;

map the set of redundancy coded shards to a logical storage layer such that each shard of the set corresponds to a plurality of addressable zones allocated by the logical storage layer, each addressable zone corresponding to an address range of the shard;

associate a set of storage devices to the logical storage layer so as to associate one or more addressable zones of the plurality of addressable zones to each storage device of the set of storage devices;

store the set of redundancy coded shards on the set of storage devices in accordance with the one or more addressable zones associated with each storage device of the set of storage devices; and

service requests related to a portion of the set of data by manipulating one or more respective storage devices of the set of storage devices associated with a respective addressable zone associated with the portion of the set of data.

6. The system of claim 5, wherein the one or more services are further configured to generate the set of redundancy coded shards by processing the set of data using the redundancy code.

7. The system of claim 6, wherein the redundancy code is Reed-Solomon.

8. The system of claim 6, wherein the redundancy code is a linear erasure code.

9. The system of claim 6, wherein the one or more services are further configured to generate the set of redundancy coded shards such that each shard of the set of redundancy coded shards is not larger than a lowest available capacity of any storage device in the set of storage devices.

10. The system of claim 5, wherein the set of redundancy coded shards is a bundle of bundle-encoded shards.

11. The system of claim 5, wherein the set of redundancy coded shards is a grid of grid-encoded shards.

12. The system of claim 5, wherein:

each shard of the set of redundancy coded shards is associated with an equal number of addressable zones of the plurality of addressable zones; and

the equal number of addressable zones is a plural subset of the plurality of addressable zones.

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:

process data for storage on a set of storage devices, thereby generating processed data, by at least;

generating a set of redundancy coded shards from the data by applying a redundancy encoding scheme to the data; and

apportioning the set of redundancy coded shards to a logical storage layer such that each shard of the set corresponds to a plurality of addressable zones of the logical storage layer;

store the processed data on a set of storage devices via the logical storage layer so as to associate one or more addressable zones of the plurality of addressable zones to each storage device of the set of storage devices; and

service requests related to a portion of the processed data by manipulating one or more respective storage devices of the set of storage devices associated with a respective addressable zone associated with the portion of the set of data.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to generate the set of redundancy coded shards as a grid of grid-encoded shards.

15. The non-transitory computer-readable storage medium of claim 14, wherein the grid of grid-encoded shards is indexed by row and column, the grid of grid-encoded shards comprising a set of data shards and a set of derived shards, wherein each shard of the grid of grid-encoded shards has a corresponding row, a corresponding column, and a corresponding subset of the one or more addressable zones associated with the shard, each shard of the grid of grid-encoded shards configured such that the shard is reproducible from other shards associated with the row and the shard is reproducible from other shards associated with the column.

16. The non-transitory computer-readable storage medium of claim 15, wherein the grid of grid-encoded shards includes at least:

a first linear redundancy code, the first linear redundancy code selected such that each shard of the grid of grid-encoded shards is reproducible from other shards associated with the row using the first linear redundancy code; and

a second linear redundancy code, the second linear redundancy code selected such that each shard of the grid of grid-encoded shards is reproducible from other shards associated with the column using the second linear redundancy code.

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

the first linear 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 linear 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.

18. The non-transitory computer-readable storage medium of claim 16, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to:

select a shard to repair;

select a set of other shards associated with the row; and

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

19. The non-transitory computer-readable storage medium of claim 16, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to:

select a shard to repair;

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

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

20. The non-transitory computer-readable storage medium of claim 13, wherein the set of redundancy coded shards is a bundle of bundle-encoded shards.