Layered redundancy encoding schemes for data storage

• US 8,869,001 B1
• Filed: 06/27/2012
• Issued: 10/21/2014
• Est. Priority Date: 06/27/2012
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin L.
• Primary Examiner(s): TRIMMINGS, JOHN P
• Application Number:
  US13/535,294
• Time in Patent Office: 846 Days
• Field of Search: 714/763, 714/769, 714/755, 711/115, 711/112, 711/161
• US Class Current: 714/755
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/293 with erasure setting
• 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

Abstract

Techniques for optimizing data storage are disclosed herein. In particular, methods and systems for implementing redundancy encoding schemes with data storage systems are described. The redundancy encoding schemes may be scheduled according to system and data characteristics. The schemes may span multiple tiers or layers of a storage system. The schemes may be generated, for example, in accordance with a transaction rate requirement, a data durability requirement or in the context of the age of the stored data. The schemes may be designed to rectify entropy-related effects upon data storage. The schemes may include one or more erasure codes or erasure coding schemes. Additionally, methods and systems for improving and/or accounting for failure correlation of various components of the storage system, including that of storage devices such as hard disk drives, are described.

Claims

1. A computer-implemented method for optimizing data storage comprising:

applying, by one or more computer systems, a primary erasure coding scheme to data stored on a storage system comprising a plurality of hardware layers, at least one of which is a physical storage layer that comprises a plurality of hardware storage devices upon which at least a subset of the data is stored, and each of the remaining hardware layers of the plurality of hardware layers comprising a plurality of devices of one type, the one type selected from the group consisting of datacenters, storage servers, hardware storage devices, and storage device zones, thereby generating primary encoded data, the primary redundancy encoding including one or more erasure codes;

determining, based at least in part on analyzing the correlated failure modes of at least the physical storage layer, a secondary erasure coding scheme for the physical storage layer; and

applying the secondary erasure coding scheme to the subset of the data stored upon the one or more hardware storage devices of the physical storage layer, wherein the secondary redundancy encoding includes one or more erasure codes that alter a stretch factor of the primary encoded data.

2. The computer-implemented method of claim 1, wherein the plurality of hardware storage devices include hard disk drives that have been adapted to internally minimize correlation of hardware failure types.

3. The computer-implemented method of claim 2, wherein the correlation of hardware failure types is internally minimized by limiting remapping of data written to a zone of writable media of the hard disk drive to the same zone.

4. The computer-implemented method of claim 1, wherein the plurality of hardware layers are arranged in a layer hierarchy that corresponds with a device hierarchy of the storage system.

5. The computer-implemented method of claim 1, wherein:

at least one layer among the plurality of hardware layers comprises a plurality of datacenters; and

at least one second layer among the plurality of hardware layers comprises at least one server room within one datacenter among the plurality of datacenters.

6. The computer-implemented method of claim 1, wherein the secondary erasure coding scheme is continuously updated as the correlated failure modes of the physical storage layer change over time.

7. A computer-implemented method for optimizing data storage comprising:

applying, by one or more computer systems, a primary redundancy encoding scheme to data stored across a plurality of system layers of a storage system, thereby generating primary encoded data, the primary redundancy encoding including one or more erasure codes;

determining, based at least in part on analyzing one or more storage characteristics of at least a subset of the system layers, at least one secondary redundancy encoding scheme; and

applying the secondary redundancy encoding scheme to data stored on the subset of system layers for which the storage characteristics are analyzed, wherein the secondary redundancy encoding scheme includes one or more erasure codes that alter a stretch factor of the primary encoded data.

8. The computer-implemented method of claim 7, wherein the system layers include at least one hardware storage layer comprising a plurality of hardware storage devices.

9. The computer-implemented method of claim 7, wherein the primary redundancy coding scheme contains one or more primary erasure codes that are applied to all data stored across the storage system.

10. The computer-implemented method of claim 9, wherein the secondary redundancy encoding scheme contains one or more secondary erasure codes that are applied to the data stored upon the subset of system layers in addition to the one or more primary erasure codes.

11. The computer-implemented method of claim 7, further comprising at a time after determining the secondary redundancy encoding scheme, applying the secondary error correction coding scheme to the stored data to replace the application of the redundancy encoding scheme.

12. The computer-implemented method of claim 7, wherein the one or more storage characteristics include at least a rate of failures per unit of time of the subset of system layers.

13. A data storage system, comprising:

a plurality of storage layers;

one or more processors; and

memory, including instructions executable by the one or more processors to cause the computer system to at least;

apply a primary redundancy encoding to data stored across at least a subset of the plurality of storage layers, thereby generating primary encoded data, the primary redundancy encoding including one or more erasure codes;

determine a secondary redundancy encoding from an analysis of reliability information for at least the subset of storage layers upon which the primary encoded data is stored; and

apply the secondary redundancy encoding to the primary encoded data, wherein the secondary redundancy encoding includes one or more erasure codes that, when applied to the stored data, alter a stretch factor of the primary encoded data.

14. The data storage system of claim 13, wherein the secondary redundancy encoding, when applied, improves at least one of a stretch factor of the primary encoded data, a durability level of the primary encoded data, or a recovery time for regenerating the primary encoded data.

15. The data storage system of claim 13, wherein the subset of storage layers comprises a data volume that is accessible to a user of the data storage system.

16. The data storage system of claim 13, wherein the reliability information is provided by a user of the data storage system.

17. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computing resource provider'"'"'s computer system, cause the computer system to at least:

cause a primary encoding, using a primary error correction coding scheme, of data stored upon a storage subsystem of the computer system, the storage subsystem including a plurality of storage layers, thereby generating primary encoded data, the primary redundancy encoding including one or more erasure codes;

analyze one or more failure modes of at least a subset of the plurality of storage layers to determine at least one secondary error correction coding scheme to be applied to at least a subset of the plurality of storage layers; and

cause the determined secondary error correction coding scheme to be applied to the associated subset of storage layers, wherein the secondary error correction coding scheme includes one or more erasure codes that, when applied to the associated subset of storage layers, alter a stretch factor of the primary encoded data.

18. The non-transitory computer-readable storage media of claim 17, wherein the instructions cause the computer system to further provide a programmatic interface that enables customers of the computing resource provider to at least request storage and retrieval of the data upon the storage subsystem.

19. The non-transitory computer-readable storage media of claim 17, wherein the subset of the plurality of storage layers includes hardware data storage devices.

20. The non-transitory computer-readable storage media of claim 17, wherein the secondary error correction coding scheme contains a coding hierarchy of erasure codes that each correspond to a storage layer of the plurality of storage layers, the plurality of storage layers being arranged into a layer hierarchy that corresponds with the coding hierarchy.

21. The non-transitory computer-readable storage media of claim 17, wherein the storage subsystem comprises a plurality of data centers that further comprise a plurality of hardware data storage devices.

22. The non-transitory computer-readable storage media of claim 21, wherein the plurality of data centers comprise a first storage layer among the plurality of storage layers, and the plurality of hardware data storage devices comprise a second storage layer among the plurality of storage layers.