Scheduling of reconstructive I/O read operations in a storage environment

• US 8,589,625 B2
• Filed: 09/15/2010
• Issued: 11/19/2013
• Est. Priority Date: 09/15/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hayes, John, Hong, Bo, Wang, Feng, Miller, Ethan, Harmer, Craig
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US12/882,872
• Publication Number:
  US 20120066449A1
• Time in Patent Office: 1,161 Days
• Field of Search: 711/114, 711/163, 714/47.1
• US Class Current: 711/114
• 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/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• 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/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system and method for effectively scheduling read and write operations among a plurality of solid-state storage devices. A computer system comprises client computers and data storage arrays coupled to one another via a network. A data storage array utilizes solid-state drives and Flash memory cells for data storage. A storage controller within a data storage array comprises an I/O scheduler. The storage controller is configured to receive a read request targeted to the data storage medium, and identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request. In response to either detecting or predicting the first storage device will exhibit variable performance, the controller is configured to generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device.

Claims

1. A computer system comprising:

a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

and a data storage controller coupled to the data storage medium;

wherein the data storage controller is configured to;

receive a read request targeted to the data storage medium;

identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

wherein the storage controller is further configured to schedule relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time; and

wherein in response to detecting a rate of requests being received exceeds a given threshold, the storage controller is configured to schedule relatively long latency operations such that more than N devices within a RAID group is permitted to be busy at any given time.

2. The computer system as recited in claim 1, wherein the storage controller is configured to generate said reconstruct read request based at least in part on a recent history of I/O requests.

3. The computer system as recited in claim 1, wherein the reconstruct read request includes at least two read requests targeted to at least two devices of the plurality of storage devices, and wherein the storage controller is configured to schedule the at least two read requests such that they complete at approximately a same time.

4. The computer system as recited in claim 1, wherein in response to detecting the rate of requests has fallen below a threshold, the storage controller is configured to schedule relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time.

5. A method for use in a computing system, the method comprising:

receiving a read request targeted to a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

identifying at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generating a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

scheduling relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time; and

wherein in response to detecting a rate of requests being received exceeds a given threshold, scheduling relatively long latency operations such that more than N devices within a RAID group is permitted to be busy at any given time.

6. The method as recited in claim 5, further comprising generating said reconstruct read request based at least in part on a recent history of I/O requests.

7. The method as recited in claim 5, wherein the reconstruct read request includes at least two read requests targeted to at least two devices of the plurality of storage devices, and wherein the method further comprises scheduling the at least two read requests such that they complete at approximately a same time.

8. The method as recited in claim 5, wherein reconstruct reads are not possible while more than N devices within the RAID group are busy.

9. The method as recited in claim 5, wherein in response to detecting the rate of requests has fallen below a threshold, the method further comprises scheduling relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time.

10. The method as recited in claim 5, wherein the read request has a given priority, and wherein the method further comprises scheduling both of the at least two read requests with a same priority as the given priority.

11. The method as recited in claim 5, wherein the read request has a given priority, and wherein the method further comprises scheduling each of the at least two read requests to have a different priority from one another.

12. A non-transitory computer readable storage medium comprising program instructions, wherein when executed by a processing device, the program instructions are operable to:

receive a read request targeted to a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

schedule relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time; and

wherein in response to detecting a rate of requests being received exceeds a given threshold, schedule relatively long latency operations such that more than N devices within a RAID group is permitted to be busy at any given time.

13. A computer system comprising:

a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

and a data storage controller coupled to the data storage medium;

wherein the data storage controller is configured to;

receive a read request targeted to the data storage medium;

identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

wherein the reconstruct read request includes at least two read requests targeted to at least two devices of the plurality of storage devices, and wherein the storage controller is configured to schedule the at least two read requests such that they complete at approximately a same time; and

wherein each of the plurality of storage devices includes a queue for storing pending operations, and wherein the storage controller is configured to schedule the at least two read requests such that they complete at approximately a same time by storing each of the at least two read requests at approximately a same queue depth in a queue of a corresponding storage device, or a queue depth with a predicted approximately equal completion time.

14. The computer system as recited in claim 13, wherein the storage controller is further configured to schedule relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time.

15. The computer system as recited in claim 14, wherein said long latency operations include one or more of a cache flush operation, a trim operation, and an erase block operation, hibernation, a write, or a large read.

16. The computer system as recited in claim 13, wherein the read request has a given priority, and wherein the storage controller is configured to schedule both of the at least two read requests with a same priority as the given priority.

17. The computer system as recited in claim 13, wherein the read request has a given priority, and wherein the storage controller is configured to schedule each of the at least two read requests to have a different priority from one another.

18. The computer system as recited in claim 17, wherein the storage controller is configured to determine a priority with which to schedule each of the at least two read requests based upon a state of a device to which a read of the at least two read requests is directed.

19. The computer system as recited in claim 18, wherein said state includes one or more of a queue occupancy level of a corresponding device, and an average response latency of a corresponding device.

20. The computer system as recited in claim 13, wherein the storage controller is further configured to partition a received request into multiple requests, and insert a reconstruct read request between the multiple requests.

21. A method for use in a computing system, the method comprising:

receiving a read request targeted to a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

identifying at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generating a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

wherein the reconstruct read request includes at least two read requests targeted to at least two devices of the plurality of storage devices, and wherein the method further comprises scheduling the at least two read requests such that they complete at approximately a same time; and

wherein each of the plurality of storage devices includes a queue for storing pending operations, and wherein the method further comprises scheduling the at least two read requests such that they complete at approximately a same time by storing each of the at least two read requests at approximately a same queue depth in a queue of a corresponding storage device, or a queue depth with a predicted approximately equal completion time.

22. The method as recited in claim 21, further comprising scheduling relatively long latency operations such that no more than N devices of the plurality of devices in the RAID group is performing a scheduled long latency operation at any given time.

23. The method as recited in claim 22, wherein said long latency operations include one or more of a cache flush operation, a trim operation, and an erase block operation, hibernation, a write, or a large read.

24. A non-transitory computer readable storage medium comprising program instructions, wherein when executed by a processing device, the program instructions are operable to:

receive a read request targeted to a data storage medium comprising a plurality of storage devices configured to store data in at least one RAID group;

identify at least a first storage device of the plurality of storage devices which contains data targeted by the read request; and

generate a reconstruct read request configured to obtain the data from one or more devices of the plurality of storage devices other than the first storage device, in response to either detecting or predicting the first storage device will exhibit variable performance, wherein the variable performance comprises at least one of a relatively high response latency or relatively low throughput;

wherein the reconstruct read request includes at least two read requests targeted to at least two devices of the plurality of storage devices, and wherein the program instructions are further executable to schedule the at least two read requests such that they complete at approximately a same time; and

wherein each of the plurality of storage devices includes a queue for storing pending operations, and wherein the program instructions are further executable to schedule the at least two read requests such that they complete at approximately a same time by storing each of the at least two read requests at approximately a same queue depth in a queue of a corresponding storage device, or a queue depth with a predicted approximately equal completion time.