Random access optimization for redundancy coded data storage systems

• US 9,853,662 B1
• Filed: 06/17/2015
• Issued: 12/26/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, Brock, Adam Frederick, Franklin, Paul David
• Primary Examiner(s): Merant, Guerrier
• Application Number:
  US14/742,684
• Time in Patent Office: 923 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/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: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• 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 random access 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 random access requirements for retrieval requests associated with the archives stored and/or encoded therein. 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,

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, each respective storage device having a predetermined random access capability for data stored thereon;

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 a current random access rate for the determined storage device; and

if a random access burden imposed by the request plus the current random access rate is above the predetermined random access capability, retrieving the requested archives by at least;

retrieving the requested archives from the determined storage devices having the corresponding identity shard, such that the predetermined random access capability is not exceeded; 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 the random access burden imposed by the request plus the current random access rate is equal to or less than the predetermined random access capability, retrieving 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;

in response to receiving a request for 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, at least;

determine whether the identity shard is capable of accommodating a random access burden associated with the request;

if the identity shard is capable of accommodating the random access burden, then service the request by retrieving the requested original data from the identity shard; and

if the identity shard is not capable of accommodating the random access burden, then service the request by at least;

retrieving the requested 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.

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 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 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 a 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 minimum quorum quantity 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 execute the retrieval of the requested original data from the identity shard and the augmentation of the retrieval by generating the requested original data from the encoded data in parallel.

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;

assessing a random access burden associated with the requests;

determining whether a first storage device associated with the identity shard is capable of accommodating the random access burden;

if the first storage device is capable of accommodating the random access burden, then service the request by retrieving the requested original data from the identity shard; and

if the first storage device is not capable of accommodating the random access burden, then retrieving the requested original data by at least;

retrieving the encoded shard from a second storage device capable of accommodating at least a portion of the random access burden; and

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 original data associated with 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 monitor a current random access rate of a storage device associated with at least the first storage device.

17. The non-transitory computer-readable storage medium of claim 13, wherein the first storage device and the second storage device have differing random access 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 the first storage device is a data storage facility.

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