Multi-layered data redundancy coding techniques

• US 10,298,259 B1
• Filed: 06/16/2015
• Issued: 05/21/2019
• Est. Priority Date: 06/16/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): Blair, April Y
• Assistant Examiner(s): Hossain, Sazzad
• Application Number:
  US14/741,402
• Time in Patent Office: 1,435 Days
• 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: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2942 wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• 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/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

Techniques and methods for generating and implementing multiple layers of redundancy coded data are disclosed. For example, a redundancy coding scheme may include data elements that include data that is unencoded relative to the input, yet may still fully participate in providing redundancy to any data element in a given set. In a layered scheme, the input may include a bundle or group of encoded (or unencoded) data elements, thereby nesting two or more layers of redundancy coding. The specific amount of redundancy generated by such a scheme may be adjusted and adapted to failure characteristics of the entity on which the data elements are stored.

Claims

1. A computer-implemented method, comprising:

processing a plurality of requests to store archives on a data storage system having a set of volumes by at least;

applying a redundancy code to the archives to generate a plurality of shards, a subset of which include original data of the archives;

layering the plurality of shards into a plurality of groups such that;

a first group of the plurality of groups includes the subset of shards having the original data and at least one of the shards outside the subset of shards, and

a second group of the plurality of groups includes the first group and at least a subset of a remainder of the plurality of shards;

storing the first group of shards on a first subset of the set of volumes such that any member shard of the first group is regenerable, via the redundancy code, using a first quorum quantity of other shards in the first group, and

storing the second group of shards on a second subset of the set of volumes such that any member shard of the second group is regenerable, via the redundancy code, using a second quorum quantity of other shards in the second group; and

as a result of detecting that a particular shard stored on the first subset of the set of volumes is unavailable, regenerating the particular shard using the second subset of the set of volumes.

2. The computer-implemented method of claim 1, further comprising, in response to receiving information that one or more shards of the first group are unavailable, if an available quantity of available shards of the first group is equal to or greater than the first quorum quantity, regenerating an unavailable shard of the first group using only a plurality of remaining shards of the first group.

3. The computer-implemented method of claim 1, further comprising, in response to receiving information that one or more shards of the first group are unavailable, if an available quantity of available shards of the first group is less than the first quorum quantity, regenerating an unavailable shard of the first group using a plurality of remaining shards of the second group.

4. The computer-implemented method of claim 1, wherein storing the plurality of shard on the set of volumes further comprises storing each shard of the plurality of shards on a different volume of the set of volumes, wherein:

the members of the first group correspond to a first subset of the set of volumes,

the members of the second group correspond to a second subset of the set of volumes,

the first subset of volumes corresponds to a first entity having a first set of failure characteristics, and

the second subset of volumes corresponds to a second entity having a second set of failure characteristics.

5. A system, comprising:

at least one computing device that implements one or more services, wherein the one or more services;

apply at least one redundancy code to archives associated with storage requests to the one or more services, to generate a plurality of shards, a subset of which include original data of the archives;

group the plurality of shards into a first group and a second group, such that;

the first group includes the subset of shards having the original data and a first subset of a remainder of the plurality of shards, and

the second group includes a portion of the first group and a subset of a remainder of the plurality of shards not in the first group;

store the first group on a first set of volumes associated with the one or more services, such that any member of the first group is regenerable using a subset of a remainder of the first group,

store the second group on a second set of volumes associated with the one or more services, such that any member of the second group is regenerable using a subset of a remainder of the second group; and

as a result of detecting that a particular shard stored on the first set of volumes is unavailable, regenerate the particular shard using the second set of volumes.

6. The system of claim 5, wherein the one or more services further store each shard of the plurality of shards on a respective volume of a set of volumes associated with the system.

7. The system of claim 6, wherein each volume of the set of volumes is stored on a separate data storage device of a set of data storage devices.

8. The system of claim 7, wherein each data storage device of the set of data storage devices is of a uniform type.

9. The system of claim 5, wherein the one or more services further apply the at least one redundancy code to the archives by:

applying a first redundancy code to generate a first set of shards to be grouped into the first group; and

applying a second redundancy code to generate a second set of shards to be grouped into the second group.

10. The system of claim 5, wherein the one or more services further, in response to a request for the original data of the archives, retrieve the original data from the first group.

11. The system of claim 5, wherein the one or more services further, in response to receiving information that one or more shards of the first group are unavailable, attempt to regenerate the unavailable shards using only remaining shards of the first group.

12. The system of claim 11, wherein the one or more services further, if attempting to regenerate the unavailable shards using only remaining shards of the first group is unsuccessful, regenerate the unavailable shards using remaining shards of the second group.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of execution by one or more processors of a computer system, cause the computer system to:

as a result of receiving requests to store archives, generate a plurality of shards associated with the archives by applying at least one redundancy code to the archives, a subset of the plurality of shards including original data of the archives;

layer the plurality of shards into at least a first group and a second group, the first group including at least the subset of shards having the original data and a first subset of a remainder of the plurality of shards, the second group including the first group and at least a subset of a remainder of the plurality of shards not in the first group;

store the first group on a first set of volumes associated with the computer system, such that any shard of the first group is regenerable using only other shards in the first group;

store the second group on a second set of volumes associated with the computer system, such that any shard of the second group is regenerable using other shards in the second group; and

as a result of detecting that a particular shard stored on the first subset of the set of volumes is unavailable, regenerate the particular shard using the second subset of the set of volumes.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to associate the first group with a first set of data storage devices and the second group with a second set of data storage devices.

15. The non-transitory computer-readable storage medium of claim 14, wherein the first set of data storage devices and the second set of data storage devices are of the same type.

16. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to store each shard of the plurality of shards on a respective volume of a set of volumes associated with the computer system.

17. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to generate the plurality of shards in response to receiving one or more archives from a customer associated with the computer system.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to layer the plurality of shards into at least the first group and the second group so as to associate the first group with a first entity associated with the computer system having different failure characteristics than a second entity associated with the computer system.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to, in response to receiving information that one or more shards of the first group are unavailable, attempt to regenerate the unavailable shards using only remaining shards of the first group.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to, if attempting to regenerate the unavailable shards using only remaining shards of the first group is unsuccessful, regenerate the unavailable shards using remaining shards of the second group.