Throughput optimization for redundancy coded data storage systems

• US 9,866,242 B1
• Filed: 06/17/2015
• Issued: 01/09/2018
• 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,688
• Time in Patent Office: 937 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/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/2942 wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• 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 optimizing throughput characteristics for data archives stored on data storage systems using redundancy coding techniques. 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 throughput requirements or time-to-retrieval limitations for retrieval requests associated with the archives stored and/or encoded therein. Implementing systems may monitor throughput 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,

storing a plurality of archives on a plurality of volumes by at least;

generating a set of shards representing the plurality of volumes, a minimum quorum quantity of the shards in the set being usable, by a 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 each shard of the set of shards on a respective storage device of a plurality of storage devices associated with the one or more computer systems; and

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 whether the determined respective storage device has sufficient throughput to service the request within a predetermined timeframe; and

if the determined storage device does not have sufficient throughput, retrieve the requested archives by at least;

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

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

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

3. The computer-implemented method of claim 1, wherein retrieving the requested archives further comprises retrieving the requested archives from the determined storage devices and the remainder of the storage devices by reconstituting the requested archives in a staging data store.

4. The computer-implemented method of claim 1, further comprising if a random access burden imposed by the request plus the current random access rate is equal to or less than the predetermined random access capability, retrieve the requested archives directly from the corresponding identity shard.

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;

retrieve original data of an archive stored as a set of redundancy coded shards that include at least an identity shard having at least a portion of the original data and an encoded shard representing an encoded form of the original data, by at least;

retrieving the original data from the identity shard; and

augmenting the retrieval of the requested original data by generating the requested original data from the encoded shard, such that a total retrieval throughput of the original data is greater than that of the retrieval throughput from the identity shard alone.

6. The system of claim 5, wherein each shard of the set of redundancy coded shards is stored on a respective volume of a set of volumes attached to the system.

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

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

9. The system of claim 5, wherein the services are further configured to generate, using a redundancy code, the set of shards such that a plurality of the shards in the set are usable, via the redundancy code, to generate the original data of the archive.

10. The system of claim 5, wherein the services are further configured to store each shard of the set of shards on a respective storage device of a plurality of storage devices associated with the at least one computing device.

11. The system of claim 5, wherein the services are further configured to augment the retrieval of the requested original data if the retrieval throughput from the identity shard alone is insufficient to service the request within a predetermined timeframe.

12. The system of claim 5, wherein the services are further configured to receive the archive from 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:

service requests for retrieving archives stored as a set of redundancy coded shards that include at least an identity shard having original data associated with the requests and an encoded shard output from processing the original data with a redundancy code, by at least;

retrieving the identity shard from a first storage device so as to retrieve the original data associated with the requests; and

if throughput from the first storage device is insufficient to service the requests within a predetermined timeframe, retrieving the encoded shard from a second storage device so as to augment the throughput by generating the requested original data from the encoded shard.

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, in response to storage requests, store the archives as the set of redundancy coded shards.

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 store the archives by processing the archives with the redundancy code to generate the set of redundancy coded 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 continuously evaluate incoming requests to determine, prior to service the requests, whether the throughput of the first storage device is sufficient to service the requests.

17. The non-transitory computer-readable storage medium of claim 13, wherein the first storage device and the second storage device have differing throughput capabilities.

18. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code includes at least one erasure code.

19. The non-transitory computer-readable storage medium of claim 13, wherein the first storage device is associated with a data storage facility of the computer system.

20. The non-transitory computer-readable storage medium of claim 13, wherein the second data storage device is associated with a data storage facility of the computer system.