Precomputed redundancy code matrices for high-availability data storage

• US 9,495,249 B1
• Filed: 03/31/2015
• Issued: 11/15/2016
• Est. Priority Date: 03/31/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, Lazier, Colin Laird, Suver, Claire Elizabeth
• Primary Examiner(s): Butler, Sarai
• Application Number:
  US14/675,471
• Time in Patent Office: 595 Days
• Field of Search: 714/6.24
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

Techniques described and suggested herein include systems and methods for precomputing regeneration information for data archives (“archives”) that have been processed and stored using redundancy coding techniques. For example, regeneration information, such as redundancy code-related matrices (such as inverted matrices based on, e.g., a generator matrix for the selected redundancy code) corresponding to subsets of the shards, is computed for each subset and, in some embodiments, stored for use in the event that one or more shards becomes unavailable, e.g., so as to more efficiently and/or quickly regenerate a replacement shard.

Claims

1. A computer-implemented method, comprising:

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

determining, based on parameters of a redundancy code used to encode original data of an archive into a plurality of shards, at least one regeneration set, the regeneration set consisting of a subset of the plurality of shards and having a number of members equal to or greater than a minimum quorum of the plurality of shards necessary to regenerate the original data;

computing one or more matrices specific to the at least one regeneration set and corresponding to the redundancy code, the one or more matrices capable of being used with the corresponding subset of the plurality of shards to regenerate the original data;

storing the computed matrices;

at a time after detecting that one or more shards of the plurality of shards is unavailable, retrieving a matrix of the stored matrices that corresponds to a regeneration set that does not include the unavailable shards as members;

regenerating the original data using the retrieved matrix and the corresponding regeneration set; and

regenerating, using the redundancy code, a regenerated shard to replace the unavailable shard from the regenerated original data.

2. The computer-implemented method of claim 1, wherein the one or more matrices are computed by inverting at least a portion of a generator matrix used by the redundancy code, the portion corresponding to the regeneration set.

3. The computer-implemented method of claim 1, wherein the determination of the regeneration set, the computation of the matrices, and the storage of the computed matrices occurs in connection with initialization of an application that accesses the archive.

4. The computer-implemented method of claim 1, wherein the regenerated shard is identical to the unavailable shard it replaces.

5. The computer-implemented method of claim 1, wherein the matrix is retrieved at a time after detecting that an unavailable quantity of the plurality of shards plurality of shards is equal to or less than a predetermined level that is greater than a minimum quorum of available shards required to regenerate the original data.

6. 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 one or more regeneration sets from a plurality of shards, the plurality of shards having been generated by applying a redundancy code to original data of an archive, the regeneration sets including a subset of the plurality of shards capable of regenerating the original data;

compute information from the redundancy code and corresponding to the regeneration sets, the computed information being usable to regenerate a replacement shard for at least a subset of the shards in the plurality; and

at a time after detecting that one or more shards of the plurality of shards is unavailable, use the computed information to regenerate data associated with the unavailable shards.

7. The system of claim 6, wherein the one or more services are further configured to compute the information from the redundancy code by generating matrices from the redundancy code that correspond to a respective regeneration set.

8. The system of claim 7, wherein the one or more services are further configured to generate the matrices by inverting at least a portion of a generator matrix used by the redundancy code, the portion corresponding to the respective regeneration set.

9. The system of claim 6, wherein the redundancy code is an erasure code.

10. The system of claim 6, wherein the one or more services are further configured to store, in a data store in communication with the system, the computed information.

11. The system of claim 6, wherein the one or more services are further configured to determine the one or more regeneration sets and compute the information in connection with initialization of an application requesting the archive.

12. The system of claim 6, wherein the one or more services are further configured to determine the one or more regeneration sets and compute the information in connection with detecting a failure pattern associated with the plurality of shards.

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 one or more regeneration sets from a plurality of redundancy coded shards stored for an archive, each of the regeneration sets having a number of member shards equal to a quorum necessary to regenerate the archive;

compute information for each of the regeneration sets that is usable by the computer system to regenerate any of the plurality of redundancy coded shards using the member shards of a respective regeneration set; and

at a time after detecting that one or more shards of the plurality of shards is unavailable, use at least a subset of the computed information to generate data to replace the unavailable shards.

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 determine the one or more regeneration sets such that each shard of the plurality of shards is capable of being regenerated by a respective regeneration set to which it does not belong.

15. 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 compute the information for each of the regeneration sets based at least in part on one or more parameters of a redundancy code used to generate the shards from the archive.

16. The non-transitory computer-readable storage medium of claim 15, wherein the generated data to replace the unavailable shards includes at least one replacement shard.

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 store, in a data store associated with the computer system, the computed information for each of the regeneration sets.

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 one or more regeneration sets and compute the information for each of the regeneration sets prior to detecting that any shard of the plurality of shards is unavailable.

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 at least one replacement shard by generating original data of the archive.

20. The non-transitory computer-readable storage medium of claim 13, wherein the replacement shards are identical to the unavailable shards being replaced.