Estimating utilization of computing system resources

A technique for determining utilization of a computing system resource. A trace of requests in a computing system is collected. The trace is run while a time-basis of the requests of the trace is altered by issuing each request at a time that is based on timing of one or more prior requests. A first time-based statistic associated with collecting the trace is compared to a second time-based statistic associated with running the trace to determine the utilization.

FIELD OF THE INVENTION

The present invention relates to characterizing computing systems. More particularly, the present invention relates to the field of estimating utilization of a computing system and components thereof.

BACKGROUND OF THE INVENTION

Utilization is a measure of how well a computing system resource, such as a processor, memory device, storage system or communication infrastructure, is used. Measures of utilization are generally indicative of how much capacity of a resource is consumed by its workload and how much capacity is unused.

Knowledge of the level of resource utilization in computing systems is important for ensuring that applications are adequately serviced and that computing resources are deployed where they are most needed. If a resource is over-utilized, the system configuration may not support additional demands, such as additional users or an increased workload. As a result, users may experience performance degradation. To remedy this situation, the workload may be spread over additional or higher-capacity resources. Conversely, if only a small portion of a resource is being utilized, its unused capabilities may be wasted. To correct this, a lower-capacity resource may be substituted or a portion of the workload may be reassigned to the under-utilized resource.

One technique for estimating the utilization of a computing system resource involves the use of models. However, model construction can be time-consuming and there is no guarantee that utilization under any particular workload will be accurately predicted by the model. Other techniques involve monitoring activity of the resource under a workload. While this approach indicates the current workload of the resource, it has limited ability to predict how much capacity of the resource is unused. In addition, the required instrumentation can be difficult to implement.

Therefore, there is a need for improved techniques for estimating utilization of a computing system resource.

SUMMARY OF THE INVENTION

The present invention is a technique for determining utilization of a computing system resource. A trace of requests in a computing system is collected and stored. The trace includes at least a start time for each request represented in the trace. The trace is run by issuing and executing the requests of the trace while a time-basis of the requests of the trace is altered by issuing each request at a time that is based on timing of one or more prior requests. A first time-based statistic associated with collecting the trace is compared to a second time-based statistic associated with running the trace to determine the utilization.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

The invention is a technique for estimating utilization of a computing system and for estimating the utilization of components thereof. By obtaining an estimate of utilization, the computing system may be modified to improve the utilization. Thus, the present invention may be used to better ensure that the system is sufficiently provisioned for a workload without being over-provisioned. The invention may be used in connection with design of a new system, or for replacement, modification, or analysis of an existing system.

In one aspect, the computing system includes a data storage resource for which utilization is estimated. While the figures and discussion herein are directed primarily to aspects of the invention in which utilization is estimated for a data storage system and components thereof, it will be understood that utilization of any type of computing system or resource thereof may be estimated in accordance with aspects of the present invention.

FIG. 1illustrates an exemplary computing system100including a data storage resource102and one or more networked computing resources104. The computing resources104may each be implemented as a general-purpose computer system, workstation, terminal or other machine that hosts application programs. The computing resources104may communicate with the data storage system102via a network resource106(e.g., a storage area network or SAN). The computing resources104function as clients of the data storage system102. However, any of the resources104may function as a server, in which case, such a computing resource104may have its own clients.

The data storage system102may include a plurality of storage devices114. For example, the data storage system102may include any number and types of drives, such as hard drives (also referred to as disk drives), optical drives, and tape drives. In addition, a front-end controller108may be included to provide an interface between the network106and a cache memory110. The cache memory110may store frequently or recently accessed data. A back-end controller112may be included to provide an interface to the storage devices114. The storage devices114may be arranged in accordance with one or more RAID sets116. In this case, a single logical volume may be stored across the devices included in the set116.

Each computing resource104may include an operating system and one or more application programs. Exemplary applications include, but are not limited to, word-processing programs, database programs, e-mail programs, and backup programs. Certain application data may be stored at the resources104, and other application data (e.g., databases or backup files) might be stored on or across multiple of the data storage devices114in the data storage system102or even across multiple data storage systems.

Users of the computing system100communicate through the computing resources104. When a resource104performs an operation, it may send a request to the data storage system102to store information in the data storage system102or to retrieve information previously stored in the data storage system102. In response to a request to store information, the data storage system102receives the information and a location within the data storage system102to store the information (e.g., a Logical Unit Number and a SCSI block address) or a name for a location (e.g., a filename or file handle plus offset) from the computing resource104making the request and then stores the information. In response to a request to retrieve information, the data storage system102receives the location, or the name for the location, of the requested information in the data storage system102from the computing resource104. The data storage system102then retrieves the requested information and returns it to the computing resource104making the request.

More than one computing resource104may be executing an application at a given time, and, more than one computing resource104may be accessing or storing application data in the data storage system102at a given time.

FIG. 2illustrates a flow diagram of a method200for estimating utilization of a computing system resource in accordance with an aspect of the present invention. Program flow begins in a start state202and moves to a state204in which trace records are collected. For this purpose, activity (e.g., I/O activity, communication activity, CPU processing activity and so forth) in the system100may be monitored and recorded by one or more trace facilities. Each computing resource104may run an operating system (e.g., UNIX or WINDOWS NT) which controls a flow of data between the computing resources104and the data storage system102and collects traces. Other operating systems are also able to generate system traces or equivalents thereof. Rather than using an operating system to collect trace records, trace records may be generated by a hardware and/or software facility that intercepts communication activity.

A “trace” is a collection of activity records, such as network packets, disk I/O requests or file system requests. A trace facility instructs each computing resource104to gather the traces. Therefore, one or more computing resources104might be gathering traces at a given time. Traces may also be gathered by infrastructure of the network106(e.g., by one or more switches or routers) or by the data storage system102itself (e.g., by one or more disk arrays). The traces may be stored at the computing resources104, in the data storage system102, or in some other manner.

Each activity record includes a start time and a finish time. For a storage system, the start time may indicate the time when the request is sent to a storage resource, while the finish time may indicate the time when the requested data is returned (for a read request) or stored (for a write request). Each activity record may include additional information such as a create time (when an application issues the request to a kernel), an indication of the type of request (e.g, read or write), a start address (in the case of storage requests), a size and one or more identifiers, such as an identification of a device that originated the request, an identification of a device intended to act on the request, and/or a process identification.

As mentioned, trace records may be collected for a storage resource. For example, where utilization is to be determined for the storage system102as a whole, all of the trace records for activity in the storage system102may be collected. Alternatively, where utilization is to be determined for a portion of the storage system102, such as for a single storage device114, trace records may be collected only for activity directed to that device114.

Trace records may be collected for other types of resources. For example, traces may be collected that relate to activity of the central processing unit(s) of one or more of the computing resources104or that relate to network communication activity in the network106or in a network connecting computing resources104to other clients (not shown). For example, records of all communication in the network106may be collected. Alternatively, only records of communication activity that utilizes a selected portion of the network106, such as a single hub or link, may be collected.

FIG. 3Aillustrates an exemplary trace300A, including three request records shown with respect to time. Each of the three request records, labeled Req.1, Req.2and Req.3, has a start time, a finish time and a length. The length for a request is a difference between the finish time and the start time for the request. A first request, labeled Req.1, has a start time S1and a finish time F1. A second request, labeled Req.2has a start time S2and a finish time F2. A last request, labeled Req.3, has a start time S3and a finish time F3. It will be apparent that a particular trace may include a different number of records (e.g., tens, hundreds, thousands or more) having various start times, finish times and lengths.

Program flow then moves from the step204to a step206, in which the trace is run using an altered time basis. The time basis may be altered by reducing the time elapsed between requests such that the trace is time-compressed. Alternately, the trace may be time-expanded such that time elapsed between requests is expanded while running the trace. Thus, when originally collected, the trace reflects the actual workload on the system. However, when time-altered, the requests are run as an artificial workload.

One aspect of altering the time basis for the trace involves determining an average queue length for the original trace. The queue length generally indicates the number of requests started, but not yet finished, at any given time. This statistic may be a time-averaged or request-averaged. In the case of a time-averaged queue length, the sum of pending request times is computed and then divided by the length of the trace.

Using equation (1), the time-averaged queue length for the trace ofFIG. 3having three requests, Req.1, Req.2, and Req.3, and a length t1, may be computed as:

For a request-averaged queue length, the queue-length statistic is computed as a sum of requests pending at each start time, divided by the total number of requests n. Thus, the average-queue length may be given as:

For the trace ofFIG. 3, the request-averaged queue length may be computed as:

At start time S1, only Req.1is outstanding. At start time S2, Req.1and Req.2are outstanding, while at start time S3, only Req.3is outstanding. Thus, the numerator in equation (4) is four. There are a total of three requests in the trace300A. Accordingly, the divisor in equation (4) is three.

Alternately, the queue length statistic may be computed as a sum of requests pending at each finish time, divided by the total number of requests.

Then, when the trace is run, the requests are issued so as to maintain the average queue-length statistic (e.g., time averaged queue length, request-averaged queue length or other average queue length statistic) over the entire trace and to minimize or eliminate time between requests. Thus, the requests are issued as quickly as they can be processed, while maintaining the average number outstanding according to the average queue length statistic. The average number of outstanding requests may be maintained over the entire trace as an exponentially-weighted moving average, a simple mean, or other statistic.

FIG. 3Billustrates running the trace ofFIG. 3Aso as to maintain the request-averaged queue length and to minimize or eliminate time between requests. As shown inFIG. 3B, there is no time elapsed between requests. Assuming all of the requests were issued one after the other with no time between requests, this would result in a constant queue length of one. To increase the average queue length to 4/3, at least one of every three requests needs to be issued while another request is pending. Accordingly, the trace300B ofFIG. 3Bshows that Req.2is issued while Req.1is still pending.

The two above-described techniques maintain the average queue length over the entire trace. Thus, if the workload is bursty (e.g., having periods of relatively high activity separated by periods of relatively low activity), altering the time basis for running the trace (step206) will tend to eliminate this burstiness characteristic by issuing requests at a more uniform rate.

Thus, in another aspect, the trace is divided into multiple discrete intervals and an average queue length is determined for each of the multiple discrete intervals.FIG. 4illustrates a trace that has been divided into discrete intervals, Int.1, Int.2, Int.3. For each interval, an average queue length is determined. WhileFIG. 4shows only one or two requests per interval, it will be understood that many more requests may occur in each. The average queue length for each interval may be computed as a time-averaged statistic (e.g., using equation (1)) or as a request-averaged statistic (e.g., using equation (3)). The intervals may be of uniform or variable duration and may be approximately one, two or more orders of magnitude smaller than the total length of the trace. As an example, for a trace that has a length of one day, the intervals may be selected to have a length of one second. As another example, intervals of one minute may be selected for such a trace.

Thus, a series of average queue length values are formed including one value corresponding to each time interval. When the time-altered trace is run (step206), the corresponding average queue length is maintained for each interval. As a result, the time-altered trace is expected to better reflect the burstiness of the original trace. The intervals may be compressed, for example, by starting operations of a next interval as soon as all of the operations from a current interval are completed. Alternately, a next interval may be started prior to the end of the current interval. For example, the next interval may be started as soon as all of the operations, save a specified number of the operations, from the current interval are completed. The specified number may be one, two or more and is preferably selected to be close to the average queue length of the current or next interval so as to avoid having the queue length fall to an uncharacteristically low level during replay.

Certain requests may be pending at the divisions between intervals. This is shown inFIG. 4where the request Req.2starts during interval Int.1, but is not completed until sometime during the interval Int.2. When this occurs, the request is preferably treated as two requests of shorter duration, where each of the shorter requests occurs entirely within an interval, for computing the average queue lengths for each interval. Thus, as shown inFIG. 4, the request Req.2may be divided in two portions, labeled a and b. A first portion a has a start time S and a finish time Fa. Because the finish time Fa coincides with the boundary between the intervals, the portion a is entirely within the interval Int.1. Thus, the average queue length for the interval Int.1may be computed assuming it includes a request having a start time of S and a finish time of Fa. Similarly, a second portion b has a start time Sb and a finish time of F. Because the start time Sb coincides with the boundary between the intervals, the portion b is entirely within the interval Int.2. Thus, the average queue length for the interval Int.2may be computed assuming it includes a request having a start time of Sb and a finish time of F.

Alternately, the request may be treated as occurring entirely in either interval for purposes of computing the average queue length for the intervals.

In another aspect, the trace may be time-altered by forming a series of values, each of which indicates a number of requests outstanding. One value is formed at each start time of a request to indicate the number of requests outstanding at that start time. Thus, for the trace300A ofFIG. 3A, the series of values is 1, 2, 1, for each of the start times, S1, S2and S3, respectively. Note that this series corresponds to the values summed in the numerator of equation (3) for determining the request-averaged queue length. Then, when the trace is run (step206), the requests are issued in accordance with the series of values, without idle periods between issuing requests.

By following the series, 1, 2, 1, the resulting trace is similar to that ofFIG. 3B. More particularly, the first request Req.1is issued, this corresponds the first value in the series. Immediately thereafter, the next request Req.2may be issued since the second value in the series (i.e. 2) indicates that two requests are pending. Then, both Req.1and Req.2are completed before Req.3is issued, since the third value in the series (i.e. 1) indicates that one request is pending.

In another aspect of the invention, intervals between requests may be identified as being of different types of intervals and, then, the intervals may be selectively collapsed according to their type. For example,FIG. 5illustrates a trace500, including requests, Req.1through Req.8. A first type of interval has a beginning that coincides with a start time of a first request for the interval and an ending that coincides with a start time of a second request for the interval wherein the start time of the second request occurs later than the start time of the first request. Thus, an interval A1has a beginning that coincides with the start time S1of the request Req.1and an ending that coincides with the start time S2of the request Req.2. Similarly, an interval A2has a beginning that coincides with the start time S2of the request Req.2and an ending that coincides with the start time S3of the request Req.3. This sequence may continue in this manner for each interval between successive request start times such that an interval A7has a beginning that coincides with the start time S7of the request Req.7and ending that coincides with the start time for the request Req.8.

In addition, a second type of interval may be identified within the trace. Each interval of the second type has a beginning that coincides with a finish time of a first request for the interval and an ending that coincides with a start time of a second request for the interval. The start time of the second request occurs later than the start time of the first request. Thus, an interval B1has a beginning that coincides with the end time F3of the request Req.3and an ending that coincides with the start time S4of the request Req.4. Similarly, an interval B2has a beginning that coincides with the end time F6of the request Req.6and an ending that coincides with the start time of the request S7.

As shown inFIG. 5, intervals of the first and second type are identified only for selected requests of the trace. For example, inFIG. 5, each interval of the first type is identified for pairs of requests that have start times that occur closest in time. For example, the next start time after S1is S2. Thus, the interval A1extends between these adjacent start times. However, the intervals may alternately be defined as extending between start times that are separated by one or more intervening start times. For example, an interval may be identified as extending between the start times S1and S3, with one intervening start time (i.e. start time S2).

As shown inFIG. 5, intervals B1and B2of the second type are identified only for idle times between requests. Thus, as shown inFIG. 5, no requests are pending during the intervals B1and B2. It will be apparent, however, that this need not be the case. For example, intervals of the second type may be identified as a having beginnings that coincide with the end time of each nth request and endings that coincide with a next-closest start time, or a start time that is one or more start times away (i.e. there are one or more start times that occur during each interval of the second type). Thus, interval B3of the second type has a beginning that coincides with the end time F2of Req.2and an ending that coincides with the start time S5of Req.5. Note that portions of both request Req.3and request Req.4are pending during the interval B3since the interval B3begins before the finish time F3of Req.3and ends after the start time S4of Req.4. Similarly, another interval of the second type may be defined as having a beginning that coincides with the end time F4of request Req.4and an ending that coincides with the start time S8of request Req.8. Thus, portions of the requests Req.5, Req.6and request Req.7are pending during such an interval since it begins before the finish times F5and F6of Req.5and Req.6and ends after the start time S7of Req.7.

Then, once the intervals of the first and second types have been identified, altering the time-basis of the requests (step206) may include reducing (or expanding) the intervals based on type. For example, the intervals of the first type may be reduced to substantially zero while the intervals of the second type are substantially maintained. As another example, the intervals of the second type may be reduced to substantially zero while the intervals of the first type may be substantially maintained. As still another example, altering the time-basis of the requests of the trace may be accomplished by reducing (or expanding) the intervals of the first type by a predetermined proportion while substantially maintaining the intervals of the second type. As another example, intervals of the second type may be reduced (or expanded) by a predetermined proportion while the intervals of the first type may be substantially maintained.

Further, prior to identifying the intervals of the first and second types, the requests of the trace may be grouped according to selected processes of the computing system or according to one or more selected computing resources104of the computing system. A selected process may, for example, include only requests generated by a particular application program running on one of the computing resources (FIG. 1). For a trace, multiple different groups may be identified. Then, intervals of the first and second types may be identified only among requests of the same group. Thus, when the entire trace is run, the time basis for requests of each process is altered based only on the timing of the requests of that same group. This technique of grouping requests may also be in conjunction with the average queue length techniques described herein.

It will be apparent that for the techniques described herein for running a trace while altering its time basis, requests are issued at a time that is based on timing of one or more prior requests in the trace. Thus, much of the original character of the trace is retained though its time basis is altered. It will also be apparent that any means of determining a queue-length statistic from the original trace (e.g., computing a time-averaged or request averaged queue length, forming series of values, or using another statistical means) may be combined with any means of maintaining an appropriate number of outstanding requests while the trace replayed (e.g., by using a exponentially-weighted moving average or a simple mean, or by following the series of values or by using another statistical means).

Returning to the flow diagram ofFIG. 2, program flow then moves from the step206to a step208. In the step208, time-based statistics for collecting the trace (step204) and for replaying the trace (step206) are determined.

Assume that capacity of the computing system resource is unused during the period in which the trace was collected (step204). Then, when the trace is run (step206), at least some of this additional capacity is expected to be used to process the requests since they arrive at a faster rate. By using this additional capacity to process the same requests, it is expected that the total time required to run the trace will be shorter than the time during which the trace was collected. Conversely, assume that all or nearly all of the capacity of the computing system resource is used during the period in which the trace was collected (step204). Then, when the trace is run, it is unlikely that the requests will processed any faster than previously since there is little or no additional capacity to process them. Rather, they will generally be queued or the rate at which they are issued will be slowed until they can be processed. Under these circumstances, it is expected that the total time required to run the trace will not be substantially different than previously.

Thus, where the time basis of the trace is compressed (in step206), this second period of time is generally expected to be shorter than the time determined for collecting the trace (in step204), by an amount that is related to the utilization. Conversely, where the time basis of the trace is expanded (in step206), this second period of time is generally expected to be longer than the time determined for collecting the trace (in step204).

The length of a trace may be computed as a difference between the start time of the earliest record in the trace and the finish time of the last record in the trace. Thus, for the trace300A ofFIG. 3A, the length t1is the time elapsed between the start S1of request Req.1and the finish F3of request Req.3. In one aspect, the amount of time that the trace records are collected is selected prior to collecting the trace records. For example, it may be desired to collect trace records for a time period of, for example, one hour. It will be apparent however that another time period may be selected, such as a number of seconds, minutes, hours, days, and so forth. After selecting the time period, the records are collected for the selected time period (step204). If a request is outstanding (started, but not finished) at the end of the period, then the request may be excluded from, or included in, the trace. The length of the trace may then be computed as before, based on the requests in the trace, or may be computed as the selected interval for collection.

Then, in a step210, a first time-based statistic, corresponding to the collected trace, may be compared to a second time-based statistic, corresponding to the replay trace (e.g., by forming a ratio). This may be accomplished by computing a ratio of the length of replay trace and the length of the collected trace. This ratio is indicative of the utilization of the resource.

Alternately, rather than comparing the time during which the trace is collected to the time required to run the time-altered trace, a comparison may be made of a sum of request durations of the trace during collection to a sum of request duration when the time-altered trace is run. More particularly, in the step210rather than determine the length of the entire collected trace, the duration of each request may be determined and summed:
Sum of Durations(during collection)=Σ(F1collection−S1collection)  (5)
Then, rather than determine the entire time required to run the time-altered trace, the duration of each request may be determined and summed:
Sum of Durations(during replay)=(F1time—altered−S1time—altered)  (6)

A ratio of these sums may then be computed, for example:

where this ratio indicates utilization of the resource. Alternately, for each request, a ratio of the replay duration to the original duration of the trace may be computed. Then, these ratios may be summed and a mean computed as follows:

where n is the number of requests in the trace.

From the step210, program flow may terminate in a step212. It will be apparent that the steps ofFIG. 2need not all be performed in the order shown. For example, determining the time-based statistic for the collected trace may be performed prior to running the trace (step206), rather than during step210.

In another aspect of the invention, the time-altered trace may be run (in step206) on a system that is substantially different from a system from which the trace was collected (in step204). As before, the trace may be run on the second computing system while a time basis of requests of the trace is altered. The time-based statistic (e.g., the total length of the collected trace or the sum of request durations) for running the trace on the second computing system may then be determined.

Comparing the time-based statistic for running time-altered trace on the first system to the time-based statistic for running the time-altered trace on the second system, is thus indicative of the relative capabilities of the first and second computing systems. Also, comparing the time-based statistic determined for collecting the trace from the first system to the time-based statistic for running the time-altered trace on the second system may indicate utilization of the second system.