Throughput-sensitive redundancy encoding schemes for data storage

• US 8,850,288 B1
• Filed: 06/27/2012
• Issued: 09/30/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., Patiejunas, Kestutis
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US13/535,306
• Time in Patent Office: 825 Days
• Field of Search: 714/746, 714/752, 714/758, 714/763, 714/800
• US Class Current: 714/763
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• 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/353 Adaptation to the channel
• 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:

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

receiving information that includes at least;

a transaction rate requirement for data stored on a storage system;

a durability requirement for the data, the durability requirement including at least a maximum level of data loss per unit of time; and

one or more operational characteristics of the storage system;

determining, based at least in part on the transaction rate requirement, the durability requirement, and the one or more operational characteristics, an erasure coding scheme to be applied to the data;

at a time after the erasure coding scheme is determined, modifying the erasure coding scheme applied to the data in response to a change in at least one of the transaction rate requirement, the durability requirement, or the one or more operational characteristics; and

applying the modified erasure coding scheme to the data.

2. The computer-implemented method of claim 1, wherein the storage system includes a plurality of networked datacenters across which the data is distributed.

3. The computer-implemented method of claim 1, wherein the erasure coding scheme, when applied to the data, changes, independently of the operational characteristics of the storage system, at least one of a transaction rate or durability associated with the data.

4. The computer-implemented method of claim 1, wherein the required transaction rate is a required maximum number of input/output operations per time period per unit of the stored data.

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

the stored data is a data object; and

the transaction rate requirement is derived by the one or more computer systems from at least a size of the data object and the operational characteristics of the storage system; and

the operational characteristics of the storage system include one or more performance characteristics of devices in the storage system.

6. The computer-implemented method of claim 1, wherein the transaction rate requirement is specified via a programmatic interface exposed to users of the one or more computer systems.

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

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

receiving information about one or more access-related characteristics required for data stored on a storage system;

determining, based at least in part on the received information, a redundancy coding scheme to be applied to the data; and

at a time after the redundancy encoding scheme is determined, modifying the redundancy encoding scheme to be applied to the data in response to receiving information regarding a change of at least one of the access-related characteristics.

8. The computer-implemented method of claim 7, wherein the access-related characteristics include at least one of:

a transaction rate requirement for the stored data;

a durability requirement for the data, the durability requirement including at least a maximum level of data loss per unit of time;

or

one or more operational characteristics of the storage system.

9. The computer-implemented method of claim 7, further comprising determining, by the one or more computer systems and based at least in part on analyzing the stored data, the access-related characteristics.

10. The computer-implemented method of claim 7, wherein the access-related characteristics are determined by the one or more computer systems, based at least in part on analyzing a history of one or more data storage patterns of a user associated with the stored data.

11. The computer-implemented method of claim 7, wherein the access-related characteristics are determined by querying a user associated with the stored data.

12. The computer-implemented method of claim 7, wherein:

the redundancy encoding scheme includes the application of at least one erasure code upon at least a subset of the data prior to storage; and

modifying the forward error correction scheme includes applying, on at least the stored data, an updated erasure code that, when applied to the data, is responsive to the changed access-related characteristics.

13. A data storage management system, comprising:

one or more processors; and

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

detect changes to one or more access-related requirements for data stored according to an error correction encoding scheme; and

at a time after detecting a change to at least a subset of the one or more access-related requirements, modifying the error correction encoding such that the stored data conforms with the changed access-related requirements.

14. The data storage management system of claim 13, wherein the data is stored across a subset of a plurality of datacenters connected to the data storage management system.

15. The data storage management system of claim 13, wherein:

the stored data is a first dataset among a plurality of stored data sets;

the error correction encoding is a first encoding among a plurality of encodings, at least some of which are applied to at least some of the plurality of data sets; and

the first encoding is determined and updated for the first data set independently from the encodings applied to the remaining data sets.

16. The data storage management system of claim 15, further comprising a plurality of storage devices that are substantially similar, and wherein at least some of the stored data sets have differing access characteristics as a result of the applied encodings associated with the stored data sets.

17. The data storage management system of claim 13, wherein the one or more access-related requirements include at least one of:

a transaction rate requirement for the stored data;

a durability requirement for the data, the durability requirement including at least a maximum level of data loss per unit of time;

or

one or more operational characteristics of the storage system.

18. The data storage system of claim 13, wherein:

the stored data comprises a plurality of stored data objects; and

at least one of the one or more access-related requirements is dependent on object sizes of at least a portion of the stored data objects.

19. 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:

causing an error correction scheme that satisfies one or more storage requirements relating to be applied to data stored upon the media, wherein the one or more storage requirements are requirements of the computing resource provider; and

in response to information that at least one storage requirement has changed;

updating the error correction scheme to satisfy the changed storage requirement; and

causing the updated error correction scheme to be applied to the stored data.

20. The storage media of claim 19, wherein the error correction scheme includes at least one erasure code to be applied to at least a portion of the stored data.

21. The storage media of claim 19, wherein the instructions cause the computer system to further query a user of the computing resource provider for the information.

22. The storage media of claim 19, wherein the one or more storage requirements include a maximum stretch factor, the stretch factor being a ratio of a quantity of objects stored for a given subset of the stored data to a minimum number of the stored objects required to reconstitute the given subset of stored data.

23. The storage media of claim 19, wherein the instructions cause the computer system to further provide a programmatic interface to users of the computing resource provider that enables the users to at least:

request storage of data upon the storage media;

request retrieval of the stored data;

specify the storage requirements; and

change the storage requirement.