VOLUME-LEVEL REDUNDANCY CODING TECHNIQUES FOR SEQUENTIAL TRANSFER OPTIMIZED STORAGE DEVICES

• US 20160179824A1
• Filed: 12/19/2014
• Published: 06/23/2016
• Est. Priority Date: 12/19/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Suver, Claire Elizabeth, Donlan, Bryan James, Franklin, Paul David
• Granted Patent: US 9,959,274 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

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.

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 to be stored on a plurality of volumes so as to;

sort the plurality of archives according to at least one criterion shared by the plurality of archives; and

determine which archives of the sorted plurality of archives will be stored on each volume of the plurality of volumes;

generating indexes for the plurality of volumes, each index of the indexes reflecting the a subset of the sorted plurality of archives to be stored on a respective volume of the plurality of volumes;

store the sorted plurality of archives and the generated indexes on a subset of the plurality of volumes, thereby generating a plurality of shards;

applying a redundancy code to the sorted plurality of archives and the generated indexes to generate encoded shards; and

storing the encoded shards on corresponding volumes outside the subset of the plurality of volumes.

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

3. The computer-implemented method of claim 1, further comprising, if a shard among the plurality of shards is detected as unavailable, using at least one of the encoded shards with a subset of the plurality of shards to regenerate the unavailable shard.

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;

sort a plurality of archives in a predetermined order for storage, in the predetermined order, on a plurality of volumes;

process the plurality of archives with a redundancy code so as to generate a plurality of shards, a subset of which includes original data of the plurality of archives; and

store the shards on the plurality of volumes such that a subset of the plurality of volumes includes the original data.

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

7. The system of claim 5, wherein the shards are stored such that the original data of a respective archive of the plurality of archives is stored within a maximum of two volumes of the subset of the plurality 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 generate indexes for the plurality of volumes, each index of the indexes reflecting a subset of the sorted plurality of archives to be stored on a respective volume of the plurality of volumes.

11. The system of claim 10, wherein the one or more services are further configured to:

process the indexes with the redundancy code so as to include each index of the indexes in a respective shard; and

store the shards such that each volume of the plurality of volumes includes a respective index of the processed indexes.

12. The system of claim 5, wherein the one or more services are further configured to, if a shard among the subset of the plurality of shards is detected as unavailable, using a second subset of the plurality of shards to regenerate the unavailable shard using the redundancy code.

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 an order for a plurality of archives in which the plurality of archives is to be stored on a plurality of volumes;

generate a plurality of shards, each shard of the plurality of shards corresponding to a volume of the plurality of volumes, by applying a redundancy code to at least the plurality of archives such that;

a subset of the plurality of shards contains original data of the plurality of archives, and

the subset of the plurality of shards is stored on the plurality of volumes such that the plurality of archives is represented in the determined order within the subset of the plurality of shards; and

storing the plurality of shards on corresponding volumes of the plurality of volumes.

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 indexes for the plurality of volumes, each index of the indexes reflecting a subset of plurality of archives to be stored on a respective volume of the plurality of volumes in the determined order.

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 generate the plurality of shards by further applying the redundancy code to the indexes so as to include a respective index in each shard of the plurality of 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 the order for the plurality of archives by grouping subsets of the plurality of archives having common ownership by one or more customers of the computer system.

17. 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 the order for the plurality of archives by sequentially sorting the plurality of archives by a plurality of attributes.

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 determine the order for the plurality of archives by sorting the plurality of archives by the time each archive of the plurality of archives was received by the computer system.

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, if a shard among the plurality of shards is detected as unavailable, regenerate the unavailable shard using at least a subset of the remaining shards of the plurality of shards.

20. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code is an erasure code that, when applied to the plurality of archives, generates the subset of the plurality of shards such that the subset corresponds with an identity matrix containing the original data.