Request scheduling to mirrored heterogeneous storage arrays

[0001] The present invention generally relates to data storage arrangements, and more particularly to mirrored data storage arrangements.

[0002] The need for data storage has grown dramatically over the years, and the need has grown especially fast since the advent of public access to and business use of the Internet. Leading the drive for additional storage capacity are applications that use audio, video, and image data. Meeting the storage needs and satisfying the required quality of service of applications are major challenges faced by data centers. Example quality-of-service requirements include an expected response time and a minimum data transfer rate.

[0003] For a number of years disk arrays have been widely used for data storage. Disks are capable of storing a large quantity of data, and with configurations such as a RAID and data striping, the data stored in disk arrays are protected against hardware failure and a high rate of data transfer is achievable.

[0004] Different applications generate different types of storage access requests and generally access different data. A workload is the term used to refer to a set of related requests observed by a storage arrangement. A particular workload may be generated by one or more applications using the storage arrangement. The requests of a workload may be logically related, for example, requests from similar types of applications, or physically related, for example, requests that reference the same area of storage.

[0005] In some storage arrangements optimization is based on maximizing the overall performance of a particular disk array, irrespective of different quality-of-service requirements of the workloads. For example, specific configurations are established for a storage array and data are striped across multiple disks to achieve an overall data transfer rate. Data addressed by a workload that requires a high throughput or low response time may be striped over more disks than data addressed by a workload that requires lower throughput or a greater response time.

[0006] This approach, however, does not address the situation in which different workloads have different quality-of-service requirements. Storage arrays do not distinguish between different workloads that address the same data. Thus, all the workloads that address the same data will receive the same quality of service even though the workloads might have different quality of service requirements. Workloads demanding a lower quality of service may receive a quality of service that is better than necessary at the expense of workloads demanding a higher quality of service.

[0007] Another drawback is that quality-of-service requirements may change dynamically, and the changes may occur faster than the storage array can be reconfigured to address new requirements. Also, reconfiguration may temporarily degrade performance. Furthermore, the data access patterns of a workload may be unknown or poorly understood. Thus, suitably configuring the storage array prior to operation may not be feasible.

[0008] A system and method that address the aforementioned problems, as well as other related problems, are therefore desirable.

[0009] In various embodiments, the invention distributes storage requests that reference a replicated data set to heterogeneous storage arrays. A workload includes related storage requests that have a common quality-of-service requirement. The performance levels of the storage arrays are monitored in processing the storage requests. The performance levels of the storage arrays and quality-of-service requirements are used in distributing the storage requests between the storage arrays.

[0010] It will be appreciated that various other embodiments are set forth in the Detailed Description and claims which follow.

[0015] The various embodiments of the invention described herein distribute data access requests amongst heterogeneous storage arrays having copies of a replicated data set. The requests are distributed in a manner that considers not only the performance capabilities of the different storage arrays, but also the quality-of-service requirements of different workloads. In another aspect, the distribution is periodically adjusted according to observed performance of the storage arrays in processing requests from the different workloads.

[0016] FIG. 1 is a block diagram of a storage arrangement in which access to data is provided for multiple workloads, in accordance with an example embodiment of the invention. The storage arrangement includes multiple storage arrays 102–104, a storage cache 106, and a storage controller 108. Controller 108 provides access to the data in the storage arrays for clients 110, which are coupled to the controller via network 112. Access requests are distributed to the different storage arrays based on the performance capabilities of different storage arrays and the quality-of-service requirements of the different workloads

[0017] The storage arrays 102–104 are arrays of disks having a replicated a data set. In the example embodiment, the total bandwidth of the arrays is sufficient for the workloads that will access the replicated data set. In addition, the storage arrays are heterogeneous. That is, the physical characteristics or configuration of the arrays are different. For example, one array includes Solid State Disks (SSD) and the other array includes more conventional magnetic disks. Other characteristics that differentiate storage arrays include the data transfer rate and the numbers of disks in the array.

[0018] In another embodiment, the replicated data set is stored in more than two storage arrays. For example, the data set is replicated in storage arrays that are distributed over a network. The storage arrays may provide different performance levels relative to the controller 108 because of the different speeds of the intervening network links. Thus, the effective response times of storage arrays depend not only on the speed of the array itself but also on the connection between the array and the controller.

[0019] The storage arrangement also includes a cache 106. The cache includes memory for fast access to cached data, along with functionality for managing cache memory and writing updated cached data to the storage arrays. In an example embodiment, the cache 106 is integrated with controller 108, which generally manages network connections between the storage arrangement and the clients 110 generating the workloads. In an example embodiment, the logic of the workload distribution is implemented in the controller. The controller submits access requests to the different storage arrays based on the performance capabilities of different storage arrays and the quality-of-service requirements of the different workloads. In the example embodiment, this is accomplished by adjusting the probability by which requests are distributed to the different storage arrays. An example controller suitable for adaptation for purposes of the present invention is described in the patent/application entitled, “System and Method for Enforcing System Performance Guarantees,” by Wilkes, filed on Apr. 10, 2002, having application Ser. No. 10/135,412, the contents of which are incorporated herein by reference.

[0020] The clients 110 are coupled to the storage arrangement via network 112. The characteristics of the network will vary according to the application environment. For example, in various embodiments the network is a LAN, a WAN, an intranet, or the Internet. The clients represent applications that generate workloads having different quality-of-service requirements. The clients may be unrelated applications executing on one or more platforms. Alternatively, the clients may be related, but have different quality-of-service requirements.

[0021] Before discussing embodiments of the invention with reference to FIGS. 2 and 3, which illustrate example processes for processing requests and responses, the following discussion presents a higher-level view of one embodiment for distributing the requests to storage arrays having replicated data sets.

[0022] In an example embodiment of the invention, the quality-of-service requirement for a workload W is that the average response time for a read request needs to be less than R. The example embodiments of the invention are first described in terms of a replicated data set including two copies, one in a fast storage array and the other in a slower storage array. The example embodiments are then further described in more general terms for a replicated data set including n copies, where n>=2. The discussion of two copies is presented first because a replicated data set may be more commonly implemented with 2 copies versus more than 2 copies.

[0023] Each of the storage arrays with the replicated data set has a first-in-first-out (FIFO) queue. For each storage array, the controller distributes the incoming requests from workload W into the FIFO queue as a function of an associated probability; the probabilities associated with the storage arrays may vary as average response times change or quality-of-service requirements change.

[0024] The controller estimates actual response times for the faster storage array and slower storage array, Rf and Rs, respectively, for an initial read request within a workload. In various embodiments, the estimated response times may be fixed values for the storage arrays, based on analytical models, or based on response times for previous read requests from another workload sent to these devices. The response times along with the quality-of-service required response time R are used to compute the probability F associated with the faster storage array:

• • [0025] If (Rf>R) then
    • [0026] F=1;
  • [0027] otherwise, If (Rs<R) then,
    • [0028] F=1/2
  • [0029] otherwise
    • [0030] F=(Rs−R)/(Rs−RJ)

[0031] As each read request for workload W arrives, the probability of adding the request to the FIFO queue of the faster storage array is F. If the request is not added to the FIFO queue of the faster storage array, the request is added to the FIFO queue of the slower storage array. The slower storage array and the faster storage array each serves requests from its associated queue. However, if the FIFO queue of the faster array is empty, the faster array will serve requests in the FIFO queue of the slower array.

[0032] As time passes and the controller processes more requests, the average response times Rf and Rs are periodically adjusted. At the end of each period, Rf and Rs are adjusted and a new probability F is computed based on the new average response times. If the workload submits a change in the quality-of-service response time, the change is reflected in the new probability F, which is computed at the end of the period. In the period following adjustment of the average response times and probability, the new probability value is used to distribute requests between the faster and slower arrays.

[0033] The information generated in this manner may also be used for capacity planning purposes. For example, if Rf is larger than R for several periods then it may be that the bandwidth of the faster array is inadequate for the workloads assigned to it. In this scenario, the data storage configuration can be changed to meet the quality-of-service-requirements.

[0034] The following paragraphs describe an embodiment of the invention in which the number of copies of a replicated data set is n, where n is >=2. The storage arrays in which the copies of the replicated data set have different data transfer rates. However, the configuration is sufficient for the workloads accessing the replicated data set. As in the case of 2 copies, the controller divides the read requests between the n copies. The average response time of requests in a workload is controlled by changing the probabilities by which requests are distributed to the various copies.

[0035] F(1), F(2), . . . , F(n) represent the probabilities that requests from a workload W are sent to the copies 1,2, . . . ,n of the data set, respectively. It will be appreciated that F(1)+F(2)+ . . . +F(n)=1, and each probability is between 0 and 1. As each read request of workload W is received, the controller selects one of the n copies and adds the request to the associated FIFO queue; copy 1 is selected with probability F(1), copy 2 is selected with probability F(2) and so on. The controller also collects the response times of the requests sent to each copy and computes an average response time at the end of the period.

[0036] At the beginning of each period (after the first period), the probabilities F(1)−F(n) are adjusted as follows:

• • [0037] 1. Identify a “FAST_COPIES” set of copies of the data set having average response times less than or equal to R.
  • [0038] 2. Identify the remaining copies as a “SLOW_COPIES” set.
  • [0039] 3. Compute Rfast: the average of the response times of FAST_COPIES.
  • [0040] 4. Compute Rslow: the average of the response times of SLOW_COPIES.
  • [0041] 5. Compute F(1), F(2), . . . F(n):
    • [0042] If |FAST_COPIES| (the number of fast copies) is zero,
      • [0043] F(k)=1 for the copy with the shortest response time, zero for the others;
      • [0044] Otherwise, if |SLOW_COPIES| is zero,
        • [0045] F(k)=1/n for all the copies;
      • [0046] Otherwise, if copy k is a member of FAST_COPIES,
        • [0047] F(k)=(Rslow−R)/((Rslow−Rfast)|FAST_COPIES|);
      • [0048] Otherwise,
        • [0049] F(k)=(R−Rfast)/((Rslow−Rfast)|SLOW_COPIES|).

[0050] For the first period, the controller set the probabilities F(1)−F(n) as explained above for n=2. Also, as in the case of 2 copies, if the queue of one copy is empty, that copy may serve requests from the queue of any copy with a longer measured response time.

[0051] FIG. 2 is a flowchart of an example process for processing a storage access request. When the controller receives a request (step 202), it first determines whether the request is a quality of service specification for a workload (decision step 204). If so, the quality of service requirement is associated with the workload (step 206). In one embodiment, the requester identifier specified in a storage access requests is used for identifying a workload. It will be appreciated that, as explained above, there are different types of quality of service requirements and that type of quality-of-service requirement is implementation dependent. In an alternative embodiment, multiple types of quality-of-service requirements are established for each workload, and the controller distributes requests as a function of the multiple quality-of-service requirements.

[0052] If the request is for read access to specified data, the process selects a storage array to which to submit the request (step 208). The storage array is selected as a function of the quality-of-service requirements of the workloads and actual performance levels of the storage arrays. An example method for distributing the requests is the probabilistic function described above. In alternative embodiment, a model is used to predict the latency at each array and the fractions of requests sent to each are designed to meet the overall quality-of-service requirement. In another embodiment, the requests are distributed based on the queue lengths at each array, or alternatively, using a feedback-based controller such as a proportional integral-derivative control to adjust the fractions. The actual distribution may be probabilistic based on the fractions, or deterministic (for example, with two arrays and request fractions of ⅓:⅔, the first request out of every three is sent to the first array and the next two are sent to the second array.)

[0053] Because write requests are processed by writing to a cache and the cache accumulates write requests before flushing the data to the storage arrays, storage array performance is less an issue in processing write requests than for processing read requests. While write requests must be sent to all arrays, the writing can be performed when the arrays are lightly loaded and also when the cache is nearly full.

[0054] In order to track the actual performance level of a storage array, for example, the response time, a timestamp for the request is saved in association with the identity of the selected storage array, and the request is submitted to the selected storage array (step 210). During response processing, the actual performance levels are determined using the saved timestamps. The process then returns to receive and process another request (step 202).

[0055] FIG. 3 is a flowchart for processing the response to a storage access request. When the controller receives a response from a storage array (step 252), the requested data are returned to the client that made the request (step 254). The process then proceeds to accumulate information needed for determining the actual performance level of the storage array. The actual performance level in this example embodiment is the response time.

[0056] The timestamp that was saved when the request was submitted is retrieved (step 256), and the response time is determined using the saved timestamp and the time at which the response was received (step 258). As explained above, the example embodiment uses an average response time that is calculated over a selected period. For each storage array/workload pair, a total response time and a number of processed requests are accumulated during each period. Thus, a total response time, which is associated with the responding storage array and the workload of the request, is updated by adding the response time of the just-completed request (step 260). In addition, the number of requests processed by the storage array for the workload during the period is incremented.

[0057] At the end of each period (step 264), the accumulated information regarding the actual performance levels of the storage arrays and the response times experienced by the workloads is used to adjust the values used to distribute the requests. Specifically, the average response time for each of the storage arrays is computed using the associated number of request processed and the total response time (step 266). The new response levels are then applied to the function used to distribute the requests (step 268), as described above. The period timer is reset along with the response time totals and request counts (step 270) before returning to process another response.

[0058] The present invention is believed to be applicable to a variety of arrangements for scheduling storage access requests and has been found to be particularly applicable and beneficial in storage arrays having a replicated data set. Other aspects and embodiments of the present invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and illustrated embodiments be considered as examples only, with a true scope and spirit of the invention being indicated by the following claims.