Layered redundancy coding for encoded parity data

• US 10,270,475 B1
• Filed: 06/16/2015
• Issued: 04/23/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,403
• Time in Patent Office: 1,407 Days
• 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 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• 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/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

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 archives to be stored on a set of volumes by at least;

applying a first redundancy code to the archives to generate a plurality of shards, a first subset of which include original data of the archives, a second subset of which include encoded shards, such that at least a predetermined first quorum quantity of the plurality of shards is usable to regenerate any shard of the plurality of shards; and

layering the plurality of shards into a plurality of groups such that a first group of the plurality of groups includes the first subset of shards, and a second group of the plurality of groups includes the second subset of shards;

processing the second group with a second redundancy code so as to generate a third group including the second group and parity shards for the encoded shards in the second group, the parity shards being usable for regenerating any shards in the first group and the second group; and

storing the third group on a computer system so as to enable the computer system to regenerate any stored shard of the second group using only shards in the third group, if a quantity of shards in the third group available for access by the computer system is equal to or greater than a predetermined second quorum quantity for the third group.

2. The computer-implemented method of claim 1, wherein the predetermined second quorum quantity is equal to a quantity of the second subset of shards.

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

4. The computer-implemented method of claim 1,

further comprising determining a quantity of the parity shards to generate based on one or more failure characteristics of one or more entities on which the third group is stored.

5. A system, comprising:

memory storing instructions that, as a result of being executed by one or more processors of the system, cause the system to;

apply a redundancy code to archives to generate a plurality of shards, a first subset of which includes original data of the archives, a second subset of which include encoded shards;

group the plurality of shards such that a first encoded group includes only shards from the second subset;

process the first encoded group to generate a second encoded group including the first encoded group and additional encoded shards based at least in part on the first encoded group; and

store the second encoded group so as to enable the at least one computing device to regenerate any shard of the first encoded group using only shards in the second encoded group.

6. The system of claim 5, wherein the instructions further cause the system to process the first encoded group such that any of the shards in the second encoded group are capable of being interchangeably used to regenerate shards of the first subset.

7. The system of claim 5, wherein the instructions further cause the system to process the first encoded group by generating, using a second redundancy code, the additional encoded shards.

8. The system of claim 5, wherein the instructions further cause the system to associate each shard of the plurality of shards with a volume of a set of volumes associated with the system.

9. The system of claim 8, wherein each volume of the set of volumes is stored on a separate data storage device of a set of data storage devices associated with the system.

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

11. The system of claim 5, wherein the instructions further cause the system to receive information that one or more encoded shards of the first encoded group are unavailable, using only the encoded shards remaining in the second encoded group to regenerate the unavailable encoded shards.

12. The system of claim 5, wherein the instructions further cause the system to determine a quantity of the additional encoded shards to be added by analyzing failure characteristics of one or more entities to be associated with the plurality of shards.

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 at least:

process archives to generate, using a redundancy code, a plurality of shards, a first subset of which includes original data of the archives, a second subset of which include encoded shards;

apportion the plurality of shards into a plurality of groups, including at least a first encoded group that includes only shards from the second subset;

generate a second encoded group including the first encoded group and additional encoded shards by applying a second redundancy code to the first encoded group; and

store the second encoded group so as to enable the computer system to regenerate any shard of the first encoded group using only shards in the second encoded group.

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 augment the encoded group with the additional encoded shards such that the additional encoded shards are capable of being used to regenerate the original data of the archives.

15. 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 apportion the plurality of shards such that the plurality of groups includes an identity group that includes the first subset of the plurality of shards.

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 generate the second encoded group by processing the encoded shards with a second redundancy code to generate the additional encoded shards.

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, at a time after receiving information that one or more encoded shards of the second encoded group are unavailable, if a quantity of available encoded shards in the second encoded group is equal to or greater than a predetermined level, regenerate the unavailable shards using only encoded shards in the second encoded group.

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 determine a quantity of the additional encoded shards by analyzing one or more failure characteristics of one or more data storage devices on which the second encoded group is to be stored.

19. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code is an erasure code.

20. The non-transitory computer-readable storage medium of claim 19, wherein the shards of the first subset are associated with one or more identity rows of a generator matrix used by the erasure code.