ALLOCATING DATA BASED ON HARDWARE FAULTS

• US 20170300396A1
• Filed: 06/30/2017
• Published: 10/19/2017
• Est. Priority Date: 05/15/2013
• Status: Abandoned Application

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird
• Application Number:
  US15/639,458
• Publication Number:
  US 20170300396A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: G06F 2211/1004 Adaptive RAID, i.e. RAID system adapts to changing circumstances, e.g. RAID1 becomes RAID5 as disks fill up
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• 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: G11B 19/041 Detection or prevention of read or write errors
• CPC Class Codes: G11B 33/08 Insulation or absorption of undesired vibrations or sounds

Abstract

A data storage service receives a request to store data into a data storage system that consists of many physical data storage locations, each location having various physical characteristics. The data storage service determines a proper location for the data based on data placement rules applied to the physical data storage locations such that a set of proper locations is identified. The data storage service can place the data according to data placement rules.

Claims

1. A computer-implemented method, comprising:

storing a set of data fragments among a plurality of physical storage devices distributed among a plurality of physical data storage locations;

in response to a request to retrieve a data object that was used to generate the set of data fragments, determining a manner of retrieving the data object based at least in part on a current activity state of storage devices storing the set of data fragments and involving reading fewer than all of the set of data fragments; and

causing retrieval of the data object in accordance with the determined manner.

2. The computer-implemented method of claim 1, further comprising applying a redundancy encoding scheme to a data object to generate the set of data fragments, the set of data fragments configured such that a proper subset of the set of data fragments is usable to construct the data object.

3. The computer-implemented method of claim 1, further comprising updating a set of data placement rules based on at least one hardware failure at a data storage system that includes at least one of the plurality of physical data storage locations to generate an updated set of data placement rules, the updated set of data placement rules defining criteria for selecting separate storage locations for the data fragments to mitigate a risk of data loss of the set of data fragments when hardware failure occurs at one or more selected storage locations.

4. The computer-implemented method of claim 1, wherein storing the plurality of data fragments is based at least in part on a placement for plurality of data fragments that is based at least in part on an updated set of data placement rules applied to physical characteristics of at least a subset of a plurality of physical data storage devices, the placement indicating a plurality of locations from the plurality of physical data storage devices that satisfy the updated set of data placement rules.

5. The computer-implemented method of claim 4, wherein determining the placement comprises determining a location for a first data fragment based on the updated set of data placement rules, and iteratively determining a location for remaining data fragments of the plurality of data fragments based on the set of updated data placement rules and based on a determined location for each previously located data fragment.

6. The computer-implemented method of claim 4, wherein the set of data placement rules are configured to satisfy one or more conditions for physical location heterogeneity when the set of data placement rules are satisfied.

7. The computer-implemented method of claim 4, wherein the placement for the data fragments is determined by selecting the placement from a plurality of placements predetermined to satisfy the updated data placement rules prior to receiving a data object for storage.

8. The computer-implemented method of claim 1, further comprising receiving a data object to be stored in a data storage system, the data storage system comprising the plurality of physical data storage locations, each location of the plurality of physical data storage locations having a plurality of physical characteristics.

9. A computer-implemented method comprising:

receiving a request to retrieve a data object;

selecting a physical storage device based at least in part on a current activity state of the physical storage device, the physical storage device storing a fragment of the data object;

reconstructing the data object based at least in part on the fragment and a set of other fragments, the set of other fragments stored among a set of other physical storage devices; and

providing a response to the request based at least in part on the data object.

10. The computer-implemented method of claim 9, further comprising causing the fragments to be stored according to a determined placement including delaying storage of each data fragment until storage devices adjacent to a selected storage location are idle.

11. The computer-implemented method of claim 9, further comprising generating the fragments using a redundancy encoding scheme.

12. The computer-implemented method of claim 9, wherein the fragments are stored based at least in part on an updated set of data placement rules, and wherein the updated set of data placement rules is updated based on at least one hardware failure at a data storage system that includes the set of physical storage devices and defining criteria for selecting separate locations for data fragments to mitigate a risk of data loss of the data fragments when hardware failure occurs at one or more selected locations.

13. The computer-implemented method of claim 9, wherein a collective size of the fragments is greater than a size of received data used to generate the fragments and each of the fragments has an individual size less than the size of the received data.

14. A system, comprising:

memory including instructions that, when executed by one or more processors, cause the system to;

store a set of fragments of data among a plurality of physical storage devices distributed among a plurality of physical locations based at least in part on an updated set of data placement rules;

in response to a request to retrieve the data, determining a manner of retrieving the data based at least in part on a current activity state of storage devices storing the data fragments and involving reading fewer than all of the data fragments; and

cause retrieval of the data in accordance with the determined manner.

15. The system of claim 14, wherein storing the set fragments of data comprises:

determining a location for a first data fragment based on the updated set of data placement rules, and

determining a location for remaining data fragments of the set of data fragments based on the updated set of data placement rules and based on a determined location for each previously located data fragment.

16. The system of claim 14, wherein the set of fragments of data are configured such that a proper subset of the fragments is usable to construct a set of data for recovery.

17. The system of claim 14, wherein the updated set of data placement rules are updated based on at least one hardware failure at one or more of the physical locations and defining criteria for selecting separate locations for the set of fragments of data to mitigate a risk of data loss of the set of data fragments when hardware failure occurs at one or more of the selected locations.

18. The system of claim 14, wherein the system operates in support of a data storage service provided by a computing resource service provider to a plurality of customers;

and

the fragments of data contain data of a customer of the computing resource service provider for storage in the system.

19. The system of claim 14, wherein:

the fragments of data are generated by applying a redundancy encoding engine to data; and

the fragments individually contain an amount of data that is less than a size of the data but collectively contain an amount of data that is greater than the size of the data.

20. The system of claim 14, wherein the fragments are stored based at least in part on physical characteristics of the plurality of physical storage devices, the physical characteristics include one or more physical characteristics selected from a group consisting of:

a location within a multiple storage device unit and a location within a data storage rack.