Scheduled or gradual redundancy encoding schemes for data storage

• US 8,806,296 B1
• Filed: 06/27/2012
• Issued: 08/12/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,200
• Time in Patent Office: 776 Days
• Field of Search: 714/763, 711/112, 711/161
• US Class Current: 714/763
• CPC Class Codes: G06F 11/085 using codes with inherent redundancy, e.g. n-out-of-m codes
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
• CPC Class Codes: H03M 13/293 with erasure setting

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,

determining, based at least in part on an analysis of at least one of a profile of a customer among a plurality of customers using the one or more computer systems and storing data on a storage system, age of the data, a pattern of access to the data, or one or more operational characteristics of the storage system, a schedule for a scheduled erasure coding scheme that applies one or more erasure codes to the data at one or more scheduled intervals according to the schedule;

determining, for each subset of the stored data and based at least in part on an access frequency of the subset of stored data, the one or more erasure codes to be applied to the stored data for at least one of the scheduled intervals; and

applying the determined erasure codes to the associated subset of data at the associated scheduled intervals.

2. The computer-implemented method of claim 1, wherein the scheduled erasure coding scheme applies erasure codes that successively decrease a stretch factor of the data over time, the stretch factor based at least in part on a ratio of a size of objects stored for a given subset of the stored data to a minimum size of the stored objects required to reconstitute the given subset of stored data.

3. The computer-implemented method of claim 1, wherein the analysis is performed on information provided through a programmatic interface that is exposed to the plurality of customers.

4. The computer-implemented method of claim 1, wherein the access frequency is provided by the customer associated with the subset of stored data.

5. The computer-implemented method of claim 1, wherein the determination of the scheduled erasure coding scheme is in response to a request, via a programmatic interface exposed to the plurality of customer, by the customer associated with the stored data.

6. The computer-implemented method of claim 1, wherein the determination of the scheduled erasure coding scheme is initiated by the one or more computer systems and independently of input from any of the plurality of customers.

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

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

determining, based at least in part on an analysis of one or more storage characteristics associated with data stored on a storage system, a redundancy encoding scheme that encodes the data with one or more error-correcting codes according to a schedule; and

causing the error-correcting codes of the forward error correction scheme to be applied to the data in accordance with the schedule.

8. The computer-implemented method of claim 7, wherein the storage characteristics include at least one of a profile of a customer using the one or more computer systems and storing data on a storage system, age of the data, a pattern of access to the data, or one or more operational characteristics of the storage system.

9. The computer-implemented method of claim 7, wherein causing the error-correcting codes to be applied to the data includes causing at least a subset of the data to be re-encoded a plurality of times in accordance with the schedule, each re-encoding using different erasure codes.

10. The computer-implemented method of claim 9, wherein causing the error-correcting codes to be applied to the data includes causing at least a subset of the data to be re-encoded a plurality of times in accordance with the schedule to progressively decrease a stretch factor of the data over time.

11. The computer-implemented method of claim 7, wherein the operational characteristics of the storage system include a level of correlation of failure frequencies between one or more hardware components of the storage system.

12. The computer-implemented method of claim 7, wherein the analysis of the storage characteristics includes generation of a statistical model of expected access frequency of the data over time.

13. A data storage 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;

determine, by analyzing one or more storage parameters corresponding to data stored on the system, a storage optimization plan that is effective to encode the data using one or more error correction codes according to a schedule; and

cause the storage optimization plan to be implemented by causing the data to be encoded according to the schedule.

14. The data storage system of claim 13, wherein the storage parameters include at least one of a profile of a customer using and storing data on the data storage system, age of the data, a pattern of access to the data, or one or more operational characteristics of the data storage system.

15. The data storage system of claim 13, wherein the storage optimization plan is scheduled to encode all stored data of a specified age at a specified interval.

16. The data storage system of claim 13, wherein the error correction codes include erasure codes.

17. The data storage system of claim 13, wherein the instructions cause the data storage system to further provide a programmatic interface to users of the data storage system that enables the users to at least:

request storage of the data on the data storage system;

request retrieval of the stored data;

specify the data storage parameters;

initiate the determination of the storage optimization plan; and

initiate the implementation of the storage optimization plan.

18. The data storage system of claim 13, further comprising a plurality of substantially similar data storage devices on which the data is stored, and wherein the storage optimization plan is effective to stratify the stored data into disparate layers of at least one of durability or performance by encoding subsets of the stored data according to the schedule.

19. One or more 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:

generate a redundancy encoding schedule that includes one or more error correcting codes that, when applied to data stored upon the media according to the schedule, satisfies one or more storage requirements relating to the stored data; and

cause at least a subset of the data to be encoded in accordance with the generated redundancy encoding schedule.

20. The computer-readable storage media of claim 19, wherein:

the data stored in volumes are accessible by customers of the computing resource provider, the volumes being abstracted from the media; and

the one or more error correcting codes are uniformly applied to all data within each volume according to the schedule.

21. The computer-readable storage media of claim 19, wherein the error-correcting codes are applied to the data prior to the storage of the data upon the media.

22. The computer-readable storage media of claim 19, wherein the error-correcting codes are applied to the data previously stored upon the media.

23. The computer-readable storage media of claim 19, wherein:

the storage requirements include a maximum level of input/output operations per time period per unit of the stored data that increases over time; and

the redundancy encoding schedule is generated to re-encode the data using a series of the one or more error correcting codes that satisfies the increasing maximum level of input/output operations per time period per unit of the stored data.

24. The computer-readable storage media of claim 23, wherein the instructions cause the computer system to further determine the maximum level of input/output operations per time period per unit of the stored data based at least on an age of the stored data.