FAILURE-DECOUPLED VOLUME-LEVEL REDUNDANCY CODING TECHNIQUES

• US 20170024281A1
• Filed: 09/30/2016
• Published: 01/26/2017
• 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
• Granted Patent: US 9,697,080 B2
• Time in Patent Office: Days
• 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,

selecting a first predetermined pattern and a second predetermined pattern for a set of volumes such that, when respectively applied to a first subset of a plurality of volumes and a second subset of the plurality of volumes, decorrelates a failure of the first subset of the plurality of volumes from the failure of the second subset of the plurality of volumes;

processing incoming archives so as to make a determination of which of the first predetermined pattern and the second predetermined pattern to apply, based at least in part on an attribute of the incoming archives;

applying a redundancy code to the archives to generate redundancy coded archives; and

storing the redundancy coded archives on one of the first subset of the plurality of volumes or the second subset of the plurality of volumes according to the determination.

2. The computer-implemented method of claim 1, further comprising responding to requests to retrieve a subset of the redundancy coded archives by at least:

retrieving the redundancy coded archives from one of the first subset of the plurality of volumes or the second subset of the plurality of volumes according to the determination; and

regenerating original data associated with the redundancy coded archives.

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 that implements one or more services, wherein the one or more services;

receive a request to store an archive;

determine, based at least in part on an attribute associated with the request, a storage pattern for a set of volumes that, when applied to the set of volumes, decorrelates a failure of the set of volumes from a different failure;

apply a redundancy code to the archive to generate a redundancy coded archive; and

store the redundancy coded archive on the set of volumes according to the storage pattern.

6. The system of claim 5, wherein shards of the redundancy coded archive are stored such that original data of the archive is entirely stored within a single volume of the set of volumes.

7. The system of claim 5, wherein the one or more services further stores the redundancy coded archives such that original data of the archives is stored to a subset of the set 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 set of volumes corresponds to one storage device of a plurality of storage devices associated with the one or more services.

10. The system of claim 5, wherein the attribute is an identity associated with a requestor for the request.

11. The system of claim 5, wherein the attribute includes one or more abstractions defined in the request.

12. The system of claim 5, wherein the one or more services further stores additional archives such that a fixed quantity of data in the additional archives is committed according to the storage pattern prior to committing at least a portion of a remainder of the data according to a different storage pattern.

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:

determine, from a request to store an archive, an attribute associated with the request;

generate, based at least in part on the attribute, a storage pattern for a set of volumes of the computer system that, when applied to the set of volumes, decorrelates a failure of the set of volumes from a different failure;

generate a redundancy coded form of the archive to generate one or more shards; and

write the one or more shards to the set of volumes according to the storage pattern.

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 storage pattern by evenly dividing members of the set of volumes between the storage pattern and a different storage pattern.

15. The non-transitory computer-readable storage medium of claim 13, wherein the attribute is associated with a customer entity associated with the archives.

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 generate the storage pattern pseudorandomly in connection with the attribute.

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, write the one or more shards such that each shard of the one or more shards is written to a different volume of the set of volumes.

18. The non-transitory computer-readable storage medium of claim 13, wherein the different failure is a failure of a different set of volumes associated with a system that hosts the set of volumes.

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, write the one or more shards such that an identity shard of the one or more shards, the identity shard storing original data of the archive, is written to a single volume of the set of volumes.

20. The non-transitory computer-readable storage medium of claim 13, wherein the attribute is associated with contents of the archive.