Failure mode-sensitive layered redundancy coding techniques

• US 10,270,476 B1
• Filed: 06/16/2015
• Issued: 04/23/2019
• Est. Priority Date: 06/16/2015
• Status: Expired due to Fees

• 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,407
• Time in Patent Office: 1,407 Days
• 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/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/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

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:

analyzing one or more failure characteristics of one or more data storage layers, the data storage layers each comprising one or more data storage devices of a computer system;

determining, based on the analyzed failure characteristics, one or more parameters for a redundancy code to be applied to archives intended to be stored on the one or more data storage layers;

configuring the redundancy code with the one or more parameters;

processing the archives with the configured redundancy code so as to;

generate a plurality of shards, an identity subset of which includes identity shards that contain original data of the archives; and

group the shards according to the one or more parameters into one or more groups of shards that are each configured for the failure characteristics of a respective data storage layer of the one or more data storage layers on which a respective group is to be stored; and

storing each group of the one or more groups of shards on the respective data storage layer such that the one or more failure characteristics of the respective data storage layer are reduced for the archives represented by the plurality of shards relative to other data stored on the respective data storage layer.

2. The computer-implemented method of claim 1, further comprising adjusting contents of one or more of the groups in response to receiving information that the failure characteristics of one or more respective data storage layer has changed.

3. The computer-implemented method of claim 2, wherein the contents of the one or more groups are adjusted by adding additional shards to the one or more groups.

4. The computer-implemented method of claim 1, wherein the groups are configured so as to enable a respective data storage layer to regenerate one or more shards of a group using only remaining shards of the group.

5. A system, comprising:

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

determine, based on failure characteristics of a data storage layer, the data storage layer comprising one or more data storage devices of the system, a redundancy level for a group of redundancy coded shards stored on the data storage layer;

configure the group with the determined redundancy level by at least applying a redundancy code to a subset of the shards in the group;

store the group on the data storage layer such that the failure characteristics of the data storage layer are reduced, relative to other data outside of the group, for data represented by the group; and

in response to receiving information that a quantity of shards in the group is unavailable, regenerate the unavailable shards using a remainder of shards in the group.

6. The system of claim 5, wherein the failure characteristics include a failure rate of the data storage layer.

7. The system of claim 5, wherein the one or more services further determine the redundancy level by at least analyzing the data storage layer to determine the failure characteristics.

8. The system of claim 7, wherein the one or more services further analyze the data storage layer by using Markov chain analysis.

9. The system of claim 5, wherein the one or more services further monitor the failure characteristics of the data storage layer.

10. The system of claim 9, wherein the one or more services further adjust the redundancy level in response to determining that the failure characteristics have changed.

11. The system of claim 9, wherein the one or more services further monitor the failure characteristics by monitoring device health information associated with the data storage layer.

12. The system of claim 9, wherein the one or more services further monitor the failure characteristics by monitoring a data reliability history associated with the data storage layer.

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:

analyze failure characteristics of data storage layers associated with the computer system, the data storage layers each comprising one or more data storage devices of the computer system;

determine redundancy levels for the data storage layers based on the analyzed failure characteristics;

process groups of redundancy coded shards associated with the data storage layers to configure the groups to conform with the determined redundancy levels;

store the groups on the respective data storage layers such that the failure characteristics of the respective data storage layers are reduced for data represented by the at least one of the groups relative to other data represented outside of the at least one of the groups; and

in response to receiving information that shards in the groups are unavailable, regenerate the unavailable shards using a remainder of shards in a respective 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 process the groups of redundancy coded shards by modifying the contents of the groups.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to modify the contents of the groups by adding or removing one or more encoded shards from the groups.

16. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to modify the contents of the groups by replacing identity shards with encoded shards.

17. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to modify the contents of the groups by replacing encoded shards with identity shards.

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 store the groups of redundancy coded shards on respective data storage layers.

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 monitor the failure characteristics of the data storage layers.

20. 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 adjust the determined redundancy levels based on the monitored failure characteristics.