Methods, apparatus and computer programs for scheduling storage requests

• US 7,565,484 B2
• Filed: 07/12/2007
• Issued: 07/21/2009
• Est. Priority Date: 06/23/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jain, Rohit, Verma, Akshat, Ghosal, Sugata
• Primary Examiner(s): Thai; Tuan V
• Assistant Examiner(s): Li; Zhuo H
• Application Number:
  US11/776,578
• Publication Number:
  US 20080016310A1
• Time in Patent Office: 740 Days
• Field of Search: 711/100, 711111-112, 711/113, 711/115, 711/4, 710/1, 710 5- 6, 710/36, 710/39, 710/40, 710/42
• US Class Current: 711/112
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0632 by initialisation or re-initialisation of storage systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Provided are methods, apparatus arid computer programs for scheduling storage input and/or output (I/O) requests. A method for scheduling storage access requests determines a request processing sequence calculated to maximize SLA-based revenues achievable from processing a number of requests. A storage controller includes a scheduler which implements a revenue-based scheduling function to determine a revenue-maximizing processing sequence, and then assigns storage access requests to locations in a queue corresponding to the determined sequence. In an on-line mode, the scheduler can adapt to additional received requests, evaluating the revenue function for the additional requests and modifying the schedule if required. The method may include analyzing a request stream to predict requests that are likely to be received in the near future, and taking account of the predicted requests when determining a processing schedule.

Claims

1. A computer-implemented method for scheduling storage access requests, said method comprising:

determining by a computer, by reference to Service Level Agreements (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests; and

ordering by said computer the plurality of storage access requests in a schedule corresponding to the determined revenue-maximizing sequence,

wherein said determining comprises evaluating a revenue function with reference to an estimated latency for each of the plurality of storage access requests, and

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests,

wherein the latency for each request is estimated using;

an estimate of seek time for moving a read/write head of a disk drive to a disk track corresponding to a data location of a respective storage access request, wherein the seek time is estimated from characteristics of a respective disk drive, a current read/write head position, and a required read/write head position for performing a requested storage access operation;

an estimated data transfer time determined according to a data size of each request and the disk drive characteristics; and

an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of the read/write head.

2. The method of claim 1, wherein said latency of a particular storage access request is dependent on a location of a previous serviced storage access request.

3. The method of claim 1, wherein said determining comprises:

for each of a set of candidate processing sequences, evaluating a latency-dependent revenue function to determine a latency-dependent loss of revenue for each request as compared with a maximum achievable revenue; and

identifying a sequence within the set of candidate processing sequences having a minimum accumulated loss of revenue for the plurality of requests.

4. The method of claim 1, further comprising:

in response to receipt of additional storage access requests, repeating said determining and ordering steps.

5. The method of claim 1, further comprising:

analyzing a stream of data access requests and comparing with known request stream characteristics to predict future request;

wherein said determining includes determining a position in the sequence for the predicted future requests.

6. The method of claim 1, further comprising:

analyzing parameters of received data access requests to select a suitable latency-dependent revenue function from a plurality of revenue functions.

7. The method of claim 1, wherein said determining comprises determining a revenue-maximizing sequence subject to a condition that all received requests to access data on a particular disk track X are arranged consecutively in the sequence to ensure that requests to access data on a same disk track X are served consecutively before moving a read/write head to another track.

8. The method of claim 1, wherein said determining comprises determining a revenue-maximizing sequence subject to a condition that, when a read/write head moves from a first track X_i and a second track X_k during processing of the sequence of data access requests, all received requests to access data on an intervening track X_j are processed before requests to access data on the second track X_k, for i<

j<

k and i>

j>

k.

9. A storage access controller comprising:

computer-readable storage media storing instructions to control a scheduler to determine, by reference to Service Level Agreements (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests and for ordering the plurality of storage access requests in a scheduled sequence corresponding to the determined revenue-maximizing sequence,

wherein said scheduler is further adapted to evaluate a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

10. The storage controller of claim 9, further comprising:

a predictor for analyzing a stream of data access requests and comparing with known request stream characteristics to predict future requests;

wherein the scheduler is adapted to determine a revenue-maximizing processing sequence that includes a position in the sequence for the predicted future requests.

11. The storage controller of claim 9, further comprising:

a classifier for analyzing parameters of received data access requests to select a suitable latency-dependent revenue function from a plurality of revenue functions.

12. A scheduler for a storage access controller, comprising:

computer-readable storage media storing instructions for determining, by reference to Service Level Agreements (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests; and

means for ordering the plurality of storage access requests in a schedule corresponding to the determined revenue-maximizing sequence,

wherein said instructions further evaluates a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

13. A data processing apparatus comprising:

a data processing unit;

a data storage unit; and

a storage access controller adapted to determine, by reference to Service Level Agreements (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests and for ordering the plurality of storage access requests in a scheduled sequence corresponding to the determined revenue-maximizing sequence,

wherein said storage access controller is further adapted to evaluate a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

14. A computer program storage medium readable by computer, tangibly embodying a program of instructions executable by the computer to perform a method of scheduling storage access requests, the method comprising:

determining, by reference to Service Level Agreements (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests; and

ordering the plurality of storage access requests in a schedule corresponding to the determined revenue-maximizing sequence,

wherein said determining comprises evaluating a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

15. A method for operating a storage service, said method comprising:

maintaining a data store within a set of network-accessible data storage units;

receiving storage access requests for access to the data store;

scheduling received storage access requests by determining, by reference to Service Level Agreement (SLA)-based revenues achievable for processing storage access requests, a revenue-maximizing processing sequence for a plurality of storage access requests, and ordering the plurality of storage access requests in a schedule corresponding to the determined revenue-maximizing sequence,

wherein said determining comprises evaluating a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

16. A method for scheduling storage access requests, said method comprising:

determining, by reference to Service Level Agreements (SLA)-based reward parameters, a reward-function-maximizing processing sequence for a plurality of storage access requests; and

ordering the plurality of storage access requests in a schedule corresponding to the determined reward-function-maximizing sequence,

wherein said determining comprises evaluating a revenue function with reference to an estimated latency for each of the plurality of storage access requests,

wherein said revenue function is dependent only on said estimated latency and a non-unity weight associated with said storage access requests such that said revenue function is non-increasing with an increase in latency of said storage access requests, and

wherein the latency is estimated using an estimated rotational delay for rotating a disk sector, required by the storage access request, into a position required for operation of a read/write head based on characteristics of a respective disk drive.

17. The method of claim 16, wherein the reward parameters include measurable customer satisfaction parameters.

18. The method of claim 17, wherein the Service Level Agreements (SLA)-based reward parameters include reward parameters for a plurality of reward functions and said determining comprises evaluating the plurality of reward functions and aggregating reward values for the plurality of reward functions.

19. The method of claim 18, wherein the plurality of reward functions include a latency-dependent revenue function and an aggregate latency function and said determining comprises determining a processing sequence to maximize revenues within the constraints of an acceptable aggregate latency.