Data retrieval optimization for redundancy coded data storage systems with static redundancy ratios

• US 9,838,042 B1
• Filed: 06/17/2015
• Issued: 12/05/2017
• Est. Priority Date: 06/17/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird
• Primary Examiner(s): Merant, Guerrier
• Application Number:
  US14/742,686
• Time in Patent Office: 902 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] 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 described and suggested herein include systems and methods for improving data performance characteristics for data archives stored on data storage systems using redundancy coding techniques, without necessitating expansion of the implementing data storage system. For example, redundancy coded shards, which may include identity shards that contain unencoded original data of archives, may be configured such that a variable number of the shards can be leveraged to meet performance requirements for retrieval requests associated with the archives stored and/or encoded therein. Multiple shards may be assigned to devices in an existing infrastructure to improve performance characteristics without changing redundancy code parameters. Implementing systems may monitor random access rates, capabilities, and burdens, so as to adaptively account for changes to some or all of the monitored parameters.

Claims

1. A computer-implemented method, comprising:

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

generating, from a plurality of received archives using a redundancy code, a set of shards representing the plurality of archives, a minimum quorum quantity of the shards in the set being usable, by the redundancy code, to generate original data of the archives, the set of shards including at least;

identity shards that contain the original data of the plurality of archives, and

encoded shards representing an encoded form of the original data; and

storing the set of shards on a set of storage devices, the set of storage devices having a quantity of storage devices that is associated with the minimum quorum quantity, such that a quantity of shards of the set of shards stored on the storage devices is an integer multiple of the quantity of storage devices, the integer multiple being two or greater;

in response to receiving a request for at least some of the stored plurality of archives, at least;

determining at least one of the respective storage devices on which a respective identity shard corresponding to the requested archives is stored;

determining performance characteristics for the determined storage device; and

if the determined performance characteristics are insufficient to complete retrieval of the respective identity shard within a timeframe determined for the retrieval, retrieve the requested archives by at least;

retrieving the requested archives from the determined storage devices having the corresponding identity shard; and

augmenting the retrieval of the requested archives by generating, using the redundancy code, original data corresponding to the requested archives from the shards stored on at least a portion of a remainder of the storage devices of the plurality of storage devices.

2. The computer-implemented method of claim 1, wherein each storage device of the plurality of storage devices is a physically separate data storage facility.

3. The computer-implemented method of claim 1, wherein the quantity of storage devices in the set of storage devices is associated with the minimum quorum quantity by being directly related to parameters of the redundancy code.

4. The computer-implemented method of claim 1, wherein the parameters include a quantity of shards of the set of shards to be stored so as to represent the archives.

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;

process received archives to generate two or more sets of shards representing the plurality of archives, a minimum quorum quantity of the shards across the two or more sets of shards being usable to generate unavailable shards in the any set of the two or more sets of shards, the two or more sets of shards including at least;

identity shards that contain the original data of the plurality of archives, and

encoded shards representing an encoded form of the original data; and

store each set of the two or more sets of shards across a set of storage devices, such that shards of at least two sets of the two or more sets are stored on each storage device of the set of storage devices;

in response to receiving a request for retrieval of the archives, at least;

retrieve the archives from a corresponding identity shard among the identity shards; and

augment the retrieval of the archives by generating the requested archives from at least a subset of the encoded shards and at least a subset of a remainder of the identity shards.

6. The system of claim 5, wherein each shard of the two or more sets of shards is stored on a respective volume of a set of volumes associated with the system.

7. The system of claim 6, wherein each respective volume of the set of volumes is associated with a respective storage device of the set of storage devices.

8. The system of claim 7, wherein each storage device of the set of storage devices is a data storage facility.

9. The system of claim 5, wherein the services are further configured to determine whether a storage device on which the corresponding identity shard is stored is capable of providing the archives within a timeframe determined for retrieving the archives.

10. The system of claim 9, wherein the services are further configured to augment the retrieval of the archives if determined that the storage device is incapable of providing the archives within the timeframe.

11. The system of claim 5, wherein the services are further configured to execute the retrieval of the archives from the corresponding identity shard and the augmentation of the retrieval by generating the archives in parallel with the retrieval.

12. The system of claim 5, wherein the services are further configured to provide the archive to a customer of the system via a programmatic interface.

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:

cause generation, by a redundancy code, of two or more sets of shards representing a plurality of archives to be stored by the computer system, a minimum quorum quantity of the shards across the two or more sets of shards being usable to generate unavailable shards in the any set of the two or more sets of shards, the two or more sets of shards including at least;

identity shards that contain the original data of the plurality of archives, and

encoded shards representing an encoded form of the original data; and

cause storage of each set of the two or more sets of shards across a set of storage devices associated with the computer system, such that shards of at least two sets of the two or more sets are stored on each storage device of the set of storage devices;

service requests for retrieving the archives, by at least;

determining whether the storage device associated with an identity shard corresponding to the requested archives is capable of accommodating the requests within a timeframe determined for the requests;

if the storage device is capable of accommodating the requests within the timeframe, then causing retrieval of the corresponding identity shard; and

if the storage device is not capable of accommodating the requests within the timeframe, then at least;

causing retrieval of at least a subset of a remainder of the shards; and

causing generation of the requested archives from the subset of the remainder of the shards.

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 receive the archives in connection with storage requests.

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

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 monitor performance characteristics of the set of storage devices to enable determinations of whether the requests will be accommodated within the timeframe.

17. The non-transitory computer-readable storage medium of claim 13, wherein at least some of the storage devices of the set of storage devices have different performance characteristics.

18. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code is an erasure code.

19. The non-transitory computer-readable storage medium of claim 13, wherein each storage device of the set of storage devices is a data storage facility.

20. The non-transitory computer-readable storage medium of claim 13, wherein the set of storage devices is under control of a data storage facility.