1. Field of the Invention
The invention relates to benchmark tests of computer storage disks. More particularly, the invention concerns defining a random miss list, and producing a desired hit ratio in a benchmark test using the miss list.
2. Description of the Related Art
Benchmark performance tests are frequently used to evaluate the performance of computer disk storage products such as, for example, disk drives. Generally, benchmark tests are used to test response time, which is how quickly input/output (I/O) completion occurs when reading or writing, and throughput, which is the number of I/O operations that a drive can process per second. In order to reflect data base accesses in a credible way with these benchmarks, multiple processes must generate I/O concurrently to a shared set of files on the system.
One or more disks and a cache, which is a high speed memory associated with the disk(s), together make up a disk storage system. A hit occurs when the data that is the object of an I/O operation is present in the cache. Conversely, a miss occurs when the data that is the object of an I/O operation is not present in the cache. The hit ratio is the number of hits divided by the total number of I/O operations. Similarly, the miss ratio is the number of misses divided by the total number of I/O operations. Typically, a range of hit ratios must be tested, often including specific anticipated hit-ratios. The I/O operations are typically reads and writes. Because the sum of the hit ratio and the miss ratio equals one, the hit ratio can be determined if the miss ratio is known, and the miss ratio can be determined if the hit ratio is known. A dial-in hit ratio is a hit ratio that can be specified by the user. When data that is the object of an I/O operation is not present in the cache (a miss), typically the data will be loaded into the cache, which is referred to as a stage operation. Commonly, a track of data is loaded in the cache as the result of a stage operation.
A prior art method for producing a desired hit ratio in a benchmark test is illustrated by the tasks 100 of the flowchart in FIGS. 1A and 1B. This method has a dial-in hit ratio. In task 105, the disk area to be tested is divided into N tracks. The disk area to be tested can include one or more entire disk drives and/or portions of one or more disk drives. Preferably, the disk area to be tested is one or more entire disk drive(s). Typically, the disk area to be tested will be drive(s) of a computer on which the benchmark test is run. Preferably, the disk drive is a magnetic disk drive (commonly referred to as a "hard drive"). Alternatively, this method could be used to test other data storage media, for example, optical data storage disks, or magneto-optical data storage disks. This method for producing a desired hit ratio in a benchmark can generally be run on any type of computer system having sufficient computing power to drive the particular I/O system being used.
A track is defined as the largest unit of transfer from disk to cache. Tracks are defined such that a request for data on one track does not enable a hit to occur on any other track. The exact definition of a track is flexible, and need not be related to physical tracks. For example, some or all of the tracks can be logical tracks rather than physical tracks.
Cache misses are obtained or produced as needed by making requests to the tracks identified in a miss list. A single miss list can be used to obtain cache misses for successive benchmark tests, which can also be referred to as experiments. In order to be able to produce misses with a desired frequency, a list of tracks for the miss list is defined (which can also be referred to as being generated). The miss list is defined implicitly, without requiring an array or other memory structure to enumerate the elements of the list. The tracks in the miss list are used for the I/O operations in the benchmark test(s). The miss list consists of L of the available tracks organized in a pseudo-random order. In task 110 in FIG. 1, a miss list of L tracks is defined, with L.ltoreq.N, wherein N represents a number of tracks the disk area to be tested is divided into and with L being larger than the largest number of track images that can be stored in disk cache, which is designated S. L must be larger than the largest number of track images that can be stored in disk cache in order to ensure that elements of the miss list will be cycled out of the cache before possibly being used again, to ensure that a miss will occur if an element is used again. Randomness of the addresses of the tracks chosen for the miss list is desirable because it enhances the reliability of the results of the benchmark test because it spreads the misses randomly throughout the disk area being tested.
A miss will occur the first time a track on the miss list is accessed in an I/O operation. A hit will occur subsequent times that a track on the miss list is accessed in an I/O operation, unless the track is used again after cycling through the entire miss list, or after cycling through enough of the miss list to cause that track to be cycled out of the cache. Thus, the user can select the hit ratio by specifying the probability that a new track on the miss list will be used for an I/O operation.
As shown in task 115, prior to conducting the first I/O operation of the first benchmark test to be run with a particular miss list, it must be ensured that the cache corresponding with the disk area to be tested does not contain the address of any of the tracks in or on the miss list. This prevents the occurrence of inadvertent hits, and is accomplished by clearing the contents of the cache, or by writing into the cache any data pattern that does not load the addresses of any of the tracks in the miss list in any of the address fields of the cache. If necessary, the cache can be powered down to clear the contents of the cache. When using a single miss list for more than one benchmark test, it is not necessary to clear the cache between benchmark tests or to write a data pattern described above into the cache between benchmark tests, even if different hit ratios are used in the benchmark tests.
The tracks in the miss list are referred to as m(i), for i=0, 1, . . . L-1. In task 120, the tracks in the miss list are subdivided into groups, with each group having G tracks. G is chosen such that: EQU (safety factor one)(maximum misses in any single benchmark run).ltoreq.GP .ltoreq.L; (1)
where P is the number of concurrent processes. Safety factor one is included to ensure that no process generates more than G misses in a single experiment. In the prior art, it is known to use a value of 1.5 for safety factor one. The maximum misses in any single benchmark run is estimated as: EQU (test interval)(physical disks)(miss ratio)/(fastest disk service time);
where the test interval is the period of time of running the benchmark for collecting data, and where the fastest disk service time is the shortest possible time in which data can be retrieved from the disk.
In task 125, a different group of G tracks from the miss list is assigned to each one of a plurality of concurrent processes. For example, in the first benchmark test (also referred to as an experiment), process zero is assigned the tracks: EQU m(i),i=0,1, . . . , G-1;
and process one is assigned the tracks: EQU m(i), i=G,G+1, . . . , 2G-1.
This pattern continues until the final process is assigned the tracks: EQU m(i), i=(P-1)G, (P-1)G+1, . . . , ((P-1)G+G-1=PG-1).
Assignment of tracks in subsequent experiments continues where the previous assignments leave off, until all of the elements of the miss list have been exhausted. The pattern of assignments then continues by rotating back to the beginning of the miss list. For example, ifi=PG=L-1 represents the last element of the list, then in the second experiment of the example above the tracks assigned to process zero would be: EQU m(i),i=PG, 0, 1, . . . G-2.
Thus, each combination of a specific process running in a specific benchmark experiment is assigned one group of G tracks from the miss list.
If desired, the number of concurrent processes can be changed between benchmark runs. Either or both of the quantities P and G can be changed, and such a change need not be planned in advance (the new values can be based upon information gathered in previous runs). However, the new values of P and G must continue to satisfy equation (1) above.
In task 130, a pointer for each process is initialized. The pointer for each process is initialized to point to the first track in the corresponding group of G tracks. The value of i for each group of G tracks assigned to a process acts as the pointer for that group of tracks.
The method of FIG. 1A continues at circle B in FIG. 1B. At this point the benchmark test is commenced by starting the running of all of the processes. Each process then independently cycles through tasks 135, 140, and 145. In task 135, an I/O operation is performed. The I/O operation is performed on the track pointed to by the pointer for the process. After a process completes task 135, in task 140 it is decided whether to cause the process to perform an additional I/O operation. For each process, it will always be decided to perform an additional I/O operation, until the end of the test interval is reached, after which no additional I/O operations will be performed by any processes. Thus, a plurality of I/O operations are performed for each process. Each I/O operation is performed on the track m(i) pointed to by the pointer for the process at the time of the I/O operation. If in task 140 it is decided to perform an additional I/O operation, then task 145 is performed. If the end of the test interval has been reached, then in task 140 it will be decided not to perform an additional I/O operation, and task 150 will then be performed.
In task 145, a random choice is made whether to change the position of the pointer within the group of G tracks corresponding with the process. The position of a pointer is changed by incrementing the pointer. This choice is made, and the pointer is incremented or not incremented as a result of the choice, prior to each I/O operation after the first I/O operation for the process. The probability of incrementing the pointer is set equal to the desired miss ratio. To increment a pointer, if i currently points to the last element of the miss list, then i is incremented by resetting it to zero, otherwise, i is incremented by adding one to its current value.
Each I/O operation may also be referred to as an I/O request. For each process, a request will be a cache miss if and only if the position of the pointer was changed after the immediately preceding I/O request for that process. This ensures that the process generates an I/O pattern with the specified hit ratio. The I/O operations can be all reads, all writes, or any combination of reads and writes. Thus, this method can be used to control the hit ratios for reads and/or writes. When using writes, it is assumed that a write miss causes a stage (a write to cache of the missed track).
For each process, after task 145 is completed, tasks 135 and 140 are performed again. If, in task 140, it is decided not to perform an additional I/O operation, then task 150 is performed.
In task 150, it is decided whether to perform an additional experiment (also referred to as an additional test). If it is decided to perform an additional experiment, then the method is continued at circle A in FIG. 1A, otherwise the method is ended.
The desired miss ratio for the first experiment may also be referred to as a first desired miss ratio, and, if a second experiment is performed, the desired miss ratio for the second experiment is referred to as a second desired miss ratio. In the second experiment, initializing a pointer for each process is referred to as reinitializing a pointer for each process, even if a new process or new processes are used in the second experiment. Performing one or more additional experiments permits dividing device tests into a succession of individual benchmark experiments, (also referred to as runs) in order to test disk performance at various specific hit ratios. It is not necessary to define a new miss list when changing hit ratios. Thus, one or more benchmark tests, having the same or different hit ratios, may be conducted using a single miss list.
A method known in the prior art for defining a miss list is shown by the tasks 200 of the flowchart in FIG. 2. In task 205, L is set equal to N, wherein L is the number of tracks in the miss list and N represents a number of tracks the disk area to be tested is divided into. In task 210, a variable j is set equal to [cL], where the square brackets represent the greatest integer function (which can also be described as taking the integer part of the value). c is an empirically determined constant, with 0&lt;c &lt;1. The value of c is chosen to maximize the randomness of the resulting track selection. c=367/1361 is a preferred value of c.
After j is calculated, a variable k (for k=j, j+1, . . . ) is tested to determine whether k is relatively prime to L. For the first such k (the smallest such k), a variable D is set equal to k. These tasks are summarized in task 215. As shown in task 220, after D is ascertained, the tracks m(i) of the miss list (for integers i, for 0&lt;i&lt;L) are calculated as follows: m(i)=iD(mod L).
Despite the usefulness of the method described above, better, more reliable results could be produced if a more random miss list could be generated, because greater randomness in the addresses of the tracks in the miss list would result in misses being spread more randomly throughout the disk area being tested. Accordingly, there is a need for a method for producing a more random miss list for use in a benchmark test.
USPTO Backgrounds
USPTO Backgrounds