Failure-decoupled volume-level redundancy coding techniques

• US 9,459,959 B1
• Filed: 03/30/2015
• Issued: 10/04/2016
• Est. Priority Date: 03/30/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Donlan, Bryan James, Suver, Claire Elizabeth
• Primary Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US14/673,796
• Time in Patent Office: 554 Days
• Field of Search: 714/766, 714/763, 714/767, 714/799, 714/800, 714/6.2, 714/6.24, 714/6.1
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1072 in multilevel memories
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers

Abstract

Techniques described and suggested herein include systems and methods for storing, indexing, and retrieving original data of data archives on data storage systems using redundancy coding techniques. For example, redundancy codes, such as erasure codes, may be applied to archives (such as those received from a customer of a computing resource service provider) so as allow the storage of original data of the individual archives available on a minimum of volumes, such as those of a data storage system, while retaining availability, durability, and other guarantees imparted by the application of the redundancy code. Sparse indexing techniques may be implemented so as to reduce the footprint of indexes used to locate the original data, once stored. The volumes may be apportioned into failure-decorrelated subsets, and archives stored thereto may be apportioned to such subsets.

Claims

1. A computer-implemented method, comprising:

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

determining at least two failure-decorrelated subsets of a set of volumes such that;

each failure-decorrelated subset is capable of storing redundancy coded archives; and

failure of a first portion of one or more of the failure-decorrelated subsets, the first portion having at least one common member with a second portion of the one or more of the failure-decorrelated subsets that includes at least one member that does not exist in the first portion, does not affect data integrity of redundancy coded archives stored on at least the second portion of the one or more failure-decorrelated subsets;

processing archives to be stored on the set of volumes so as to determine, based on one or more characteristics of the archives, which of the failure-decorrelated subsets to commit the archives;

storing the processed archives on a first subset of volumes of the determined failure-decorrelated subset, the first subset of volumes having a number of members corresponding to a quorum quantity of a redundancy code to be applied to the processed archives;

applying the redundancy code to the processed archives to generate encoded shards; and

storing the encoded shards on a second subset of volumes of the determined failure-decorrelated subset, the second subset being outside the first subset.

2. The computer-implemented method of claim 1, further comprising responding to requests for at least a subset of the archives by retrieving the subset from the first subset of volumes.

3. The computer-implemented method of claim 1, further comprising, if a volume of the first subset of volumes is unavailable, using at least one of the encoded shards to regenerate the unavailable volume.

4. The computer-implemented method of claim 1, wherein the redundancy code is an erasure code that includes an identity matrix.

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;

determine, from a set of volumes, at least two failure-decorrelated subsets of the set of volumes, each of the failure-decorrelated subsets capable of storing data such that a failure of other failure-decorrelated subsets affects only data stored on a portion thereof;

process incoming archives so as to determine which of the failure-decorrelated subsets to commit the archives;

apply a redundancy code to the archives; and

store the redundancy coded archives to the determined failure-decorrelated subset of volumes.

6. The system of claim 5, wherein the shards are stored such that the original data of a respective archive of the archives is entirely stored within a single volume of the determined failure-decorrelated subset of volumes.

7. The system of claim 5, wherein the one or more services is further configured to store the redundancy coded archives such that original data of the archives is stored to a subset of the determined failure-decorrelated subset of volumes.

8. The system of claim 5, wherein the one or more services includes an archival storage service provided by the system.

9. The system of claim 5, wherein each volume of the plurality of volumes corresponds to one storage device of a plurality of storage devices.

10. The system of claim 5, wherein the one or more services are further configured to determine which of the failure-decorrelated subsets to commit the archives by associating a first attribute of the archives with a second attribute of the failure-decorrelated subsets.

11. The system of claim 10, wherein the one or more services are further configured to determine each of the failure-decorrelated subsets from the set of volumes by randomly selecting a quantity of members of the set of volumes that corresponds to a quantity of members required by the redundancy code.

12. The system of claim 5, wherein the one or more services are further configured to process the incoming archives such that a fixed quantity of data in the incoming archives is committed to a given failure-decorrelated subset prior to writing to other of the failure-decorrelated subsets.

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:

generate a plurality of failure-decorrelated subsets of a set of volumes, each failure-decorrelated subset of the plurality;

including at least one volume of the set of volumes that differs from any of the members of at least one of the other failure-decorrelated subsets; and

having a number of members that is less than a number of members of the set of volumes;

in response to receiving archives to be stored on the set of volumes, selecting, based on one or more attributes of a subset of the archives, at least one of the failure-decorrelated subsets on which to store the archives; and

storing the archives on the selected failure-decorrelated subsets.

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 generate the plurality of failure-decorrelated subsets by evenly dividing members of the set of volumes between the plurality of failure-decorrelated subsets.

15. The non-transitory computer-readable storage medium of claim 13, wherein the one or more attributes of the subset of the archives includes a value associated with a customer entity to which the archives belong.

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 store the subset of the archives by:

storing original data of the subset of the archives to a subset of volumes of the selected failure-decorrelated subsets;

applying a redundancy code to the subset of the archives to generate encoded shards; and

storing the encoded shards to volumes outside the subset of volumes of the selected failure-decorrelated subsets.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions further comprise instructions that, when executed by the one or more processors, store the archives such that a fixed quantity of data in the archives is committed to a given failure-decorrelated subset prior to writing to other failure-decorrelated subsets.

18. 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 store the archives such that a first subset of the archives is stored on a different failure-decorrelated subset than a second subset of the archives that differs from the first subset of the archives.

19. 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 generate the plurality of failure-decorrelated subsets by apportioning an equal number of volumes of the set of volumes to each of the failure-decorrelated subsets.

20. The non-transitory computer-readable storage medium of claim 19, wherein the apportioned number of volumes for each of the failure-decorrelated subsets is associated with a number of symbols generated by a redundancy code applied to the archives in response to receiving the archives.