METHODS, APPARATUS AND COMPUTER PROGRAMS FOR SCHEDULING STROAGE REQUESTS

• US 20080016310A1
• Filed: 07/12/2007
• Published: 01/17/2008
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Akshat Verma, Rohit Jain, Sugata Ghosal
• Original Assignee: Akshat Verma, Rohit Jain, Sugata Ghosal
• Inventors: Verma, Akshat, Jain, Rohit, Ghosal, Sugata
• Granted Patent: US 7,565,484 B2
• Time in Patent Office: Days
• US Class Current: 711/167
• 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 analysing 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 method for scheduling storage access requests, said 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, 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.

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

4. The method of claim 3, wherein the latency for each request is estimated by combining the estimate of seek time with an estimated data transfer time, the data transfer time being determined according to a data size of each request and the disk drive characteristics.

5. The method of claim 4, wherein the latency for each request is estimated by combining the estimate of seek time and data transfer time with an estimated rotational delay for rotating a disk sector, required by the data access request, into a position required for operation of the read/write head.

6. 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.

7. The method of claim 1, further comprising:

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

8. 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.

9. 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.

10. 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.

11. 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.

12. A storage access controller comprising:

a scheduler 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 scheduler is further adapted to evaluate 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.

13. The storage controller of claim 12, 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.

14. The storage controller of claim 12, 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.

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

program code 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 program code further evaluates 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.

16. 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, 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.

17. A program storage device 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, 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.

18. 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, 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.

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

20. The method of claim 19, wherein the reward parameters include measurable customer satisfaction parameters.

21. The method of claim 20, 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.

22. The method of claim 21, 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.