Locality-sensitive data retrieval for redundancy coded data storage systems

• US 10,311,020 B1
• Filed: 06/17/2015
• Issued: 06/04/2019
• 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): Bibbee, Jared M
• Application Number:
  US14/742,689
• Time in Patent Office: 1,448 Days
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067

Abstract

Techniques described and suggested herein include systems and methods for optimizing retrieval, based on localities associated with a requestor and that of various components of a data storage system, of 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 performance requirements or time-to-retrieval limitations for retrieval requests associated with the archives stored and/or encoded therein. Under some circumstances, implementing systems may monitor relative geographic locations, among other performance-related metrics, so as to retrieve data such that fewer hosting data storage facilities are used for a given retrieval.

Claims

1. A computer-implemented method, comprising:

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

generating a first set of shards representing the plurality of volumes, a minimum quorum quantity of the shards in the set being usable, by a first 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 a redundancy coded form of the original data;

generating a second set of shards for each set of the first set of shards, such that the second set of shards includes a respective shard of the first set of shards, and a second minimum quorum quantity of the second set of shards is usable, by a second redundancy code, to generate the respective shard of the first set of shards or any shard of the second set of shards;

storing each shard of the first set of shards in a respective data storage facility of a plurality of data storage facilities associated with the one or more computer systems, such that the original data of each archive of the plurality of archives is stored, in one or more of the identity shards, in no more than one data storage facility of a plurality of data facilities; and

storing each shard of the second set of shards, except for a respective shard also in the first set of shards, in one or more data storage devices associated with a respective data storage facility in which the respective shard of the first set of shards is stored; and

in response to receiving a request for an archive of the plurality of archives, at least;

determining the respective data storage facility of the plurality of data storage facilities on which the identity shard corresponding to the requested archive is stored;

determining at least a first geographic location associated with the request;

determining, based on at least a proximity between the first geographic location and a second geographic location associated with the respective data storage facility on which the identity shard is stored, whether the respective data storage facility has sufficient performance characteristics to service the request within a predetermined timeframe; and

if the determined data storage facility has sufficient performance characteristics, retrieving the requested archive from the determined respective data storage facility using the identity shard.

2. The computer-implemented method of claim 1, wherein each data storage facility of the plurality of data storage facilities is in a different geographic location.

3. The computer-implemented method of claim 1, further comprising if the determined data storage facility does not have sufficient performance characteristics to service the request within the predetermined timeframe, retrieve the requested archive by further generating the original data of the requested archive from other shards of the first set of shards stored in other data storage facilities.

4. The computer-implemented method of claim 1, further comprising if the determined data storage facility does not have sufficient performance characteristics to service the request within the predetermined timeframe, retrieve the requested archive by further generating the original data of the requested archive from at least other shards of the second set of shards stored in the respective data storage facility in which the identity shard is stored.

5. A system, comprising:

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

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 a redundancy coded form of the original data, retrieve the requested original data by at least;

determining, based at least on relative geographic locations of each of the redundancy coded shards, a random access memory burden on one or more devices storing the set of redundancy coded shards necessary to complete the retrieval within a predetermined timeframe;

retrieving the requested original data from the identity shard; and

if the determined random access memory burden exceeds a threshold value, increasing random access memory rate of the one or more devices associated with the retrieval by generating the requested original data from at least 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 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 of a set of data storage facilities, each data storage facility of the set having a different geographic location.

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

10. The system of claim 9, wherein the services generate a second set of shards for each shard of the set of shards, such that any of the shards in the second set may be generated from a minimum quorum quantity of other shards in the second set.

11. The system of claim 10, wherein the services augment the retrieval by generating the requested original data from the second set of shards.

20. The system of claim 5, wherein augmenting the retrieval of the original data comprises retrieving data from the identity shard in addition to generating the requested original data from at least the encoded shard.

12. 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:

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;

determining, based at least on a geographic location of the requestor associated with the requests and a geographic location of the identity shard, throughput burden on one or more devices storing the set of redundancy coded shards necessary to complete retrieval of the original data within a predetermined timeframe;

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

if the determined the throughput burden exceeds a threshold value, retrieving at least the encoded shard from a second storage device so as to increase throughput rate of the one or more devices associated with the retrieval of the requested original data by generating the requested original data from the encoded shard.

13. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of execution 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.

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 store the archives by processing the archives with the redundancy code to generate the set of redundancy coded shards.

15. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to determine if the performance characteristics are sufficient prior to retrieving the identity shard.

16. The non-transitory computer-readable storage medium of claim 12, wherein the first storage device and the second storage device are in different geographic locations.

17. The non-transitory computer-readable storage medium of claim 12, wherein the first storage device and the second storage device are co-located in a data storage facility.

18. The non-transitory computer-readable storage medium of claim 12, wherein the first storage device is a data storage facility of the computer system.

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