Inter-facility network traffic optimization for redundancy coded data storage systems

• US 9,825,652 B1
• Filed: 06/17/2015
• Issued: 11/21/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): Alphonse, Fritz
• Application Number:
  US14/742,683
• Time in Patent Office: 888 Days
• Field of Search: 714776, 714768, 714770, 714763, 714 42
• 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/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of 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 minimizing inter-facility data transfer during retrieval 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 throughput rates, capabilities, and burdens, so as to preferentially retrieve data such that the identity shards are favored and fewer hosting data storage facilities are used for a given retrieval.

Claims

1. A computer-implemented method, comprising:

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

processing a plurality of archives by at least;

generating a set of shards representing a plurality of volumes associated with the one or more computer systems, 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 the plurality of storage devices, 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 facility of a plurality of data facilities;

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

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

determining 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 only the determined respective data storage facility so as to avoid data transfer between the determined data storage facility and a remainder of the plurality of data storage facilities.

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, wherein retrieving the requested archive further comprises storing the retrieved archive in a staging data store accessible to a requestor of the retrieved archive.

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 other shards of the plurality of shards stored in other data storage facilities.

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 to retrieve original data of an archive, the original data having been 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 from the identity shard without accessing the encoded shard;

determine if a performance characteristic associated with the retrieval is sufficient to complete the retrieval, from the identity shard and without accessing the encoded shard, within a timeframe determined for fulfilling the request; and

if the performance characteristic is not sufficient, then augment 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.

9. The system of claim 5, wherein the services are further configured to generate, using an erasure code, the set of shards such that a plurality of the shards in the set are usable, via the erasure 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 separate data storage facility of a plurality of data storage facilities 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 in parallel with the retrieval.

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:

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

determining if performance characteristics associated with the identity shard are sufficient to complete retrieval of the original data within a timeframe determined for the retrieval;

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

if the performance characteristics are insufficient, retrieving at least the encoded shard from a second storage device so as to augment the retrieval of the requested original data 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 determine if the performance characteristics are sufficient prior to retrieving the identity shard.

17. The non-transitory computer-readable storage medium of claim 13, wherein the first storage device and the second storage device are in different physical facilities.

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

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to retrieve the stored archive further include instructions that cause the computer system to retrieve the stored archive in response to receiving a request to retrieve the stored archive.

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