Prefetch algorithm for short sequences

• US 6,721,870 B1
• Filed: 06/12/2001
• Issued: 04/13/2004
• Est. Priority Date: 06/12/2001
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Yochai, Yechiel, More, Sachin, Arnan, Ron
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US09/879,431
• Time in Patent Office: 1,036 Days
• Field of Search: 711/113, 711/137, 711/112
• US Class Current: 711/204
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A prefetch process that generates prefetch tasks for short sequences that are no longer than n tracks in length. The value of n is selected as 8. The prefetch process maintains a history of short sequences, uses that history to predict an expected length of a current sequence and generates a short prefetch task based on that prediction. The historical short sequence data is stored in histograms, each histogram being associated with a different logical volume. The histograms store a cumulative count of sequence occurrences of a given sequence length for each sequence length in a range of 1 track to n tracks. The process applies a probability-based threshold to its prediction to control the aggressiveness of the prefetch task to be generated. The threshold is adjusted based on system activity level metrics, such as processor utilization and average memory access time.

Claims

1. A computer program product residing on a computer readable medium for prefetching data from a storage device, comprising instructions for causing a computer to:

maintain a history of sequences;

determine an amount of data to be prefetched from a storage device for a new I/O request using the history of sequences, the history of sequences comprising at least one histogram and the at least one histogram includes n count fields each for storing a count value for a corresponding sequence length in a range of 1 track to n tracks, the count value indicating a number of occurrences of sequences of the corresponding sequence length; and

the at least one histogram comprising a plurality of histograms and each histogram in the plurality of histograms is associated with a different logical volume.

2. A method of prefetching data from a storage device comprising:

maintaining a history of sequences;

determining an amount of data to be prefetched from a storage device for a new I/O request using the history of sequences, the history of sequences comprising at least one histogram and the at least one histogram includes n count fields each for storing a count value for a corresponding sequence length in a range of 1 track to n tracks, the count value indicating a number of occurrences of sequences of the corresponding sequence length; and

the at least one histogram comprising a plurality of histograms and each histogram in the plurality of histograms is associated with a different logical volume.

3. The method of claim 2, wherein n is equal to 8.

4. The method of claim 2, wherein maintaining comprises:

observing completion of a sequence of a given sequence length; and

incrementing the count value in any of the count fields for which the corresponding sequence length is less than or equal to the given sequence length.

5. A storage controller comprising:

a memory;

data structures stored in the memory, the data structures comprising a plurality of histograms to provide a history of sequences, each histogram in the plurality of histograms being associated with a different logical volume and including n count fields each for storing a count value for a corresponding sequence length in a range of 1 track to n tracks, the count value indicating a number of occurrences of sequences of the corresponding sequence length; and

a processor, coupled to the memory, operable to determine an amount of data to be prefetched from a logical volume for a new I/O request using the histogram associated with such logical volume.

6. The storage controller of claim 5, wherein the processor is operable to maintain the history of sequences by observing completion of a sequence of a given sequence length and incrementing the count value in any of the count fields for which the corresponding sequence length is less than or equal to the given sequence length.

7. The storage controller of claim 5, wherein, to determine the amount of data to be prefetched, the processor is operable to predict that a current sequence of a current sequence length will reach a next sequence length by computing a probability equal to a ratio of the count value for the corresponding sequence length that equals the next consecutive sequence length and count value for the corresponding sequence length that equals the current sequence length.

8. A method of prefetching data from a storage device comprising:

maintaining a history of sequences;

determining an amount of data to be prefetched from a storage device for a new I/O request using the history of sequences, the history of sequences comprising at least one histogram and the at least one histogram includes n count fields each for storing a count value for a corresponding sequence length in a range of 1 track to n tracks, the count value indicating a number of occurrences of sequences of the corresponding sequence length; and

predicting that a current sequence of a current sequence length will reach a next sequence length by computing a probability equal to a ratio of the count value for the corresponding sequence length that equals the next consecutive sequence length and count value for the corresponding sequence length that equals the current sequence length.

9. The method of claim 8, wherein maintaining comprises:

observing completion of a sequence of a given sequence length; and

incrementing the count value in any of the count fields for which the corresponding sequence length is less than or equal to the given sequence length.

10. The method of claim 8, wherein determining comprises:

applying a threshold to the prediction.

11. The method of claim 10, wherein determining further comprises:

establishing the threshold by setting to a configurable parameter.

12. The method of claim 10, wherein applying further comprises:

comparing the threshold to the prediction; and

determining if the probability is less than the threshold.

13. The method of claim 12, wherein determining further comprises:

repeating predicting and applying for each next sequence length until it is determined for such next sequence length that the probability is less than the threshold; and

returning a prefetch amount equal to such next sequence length minus the current sequence length when the results of the comparison indicate that the probability is less than the threshold.

14. The method of claim 12, wherein determining comprises:

adjusting the threshold based on system activity metrics.

15. The method of claim 14, wherein the system activity metrics include processor utilization.

16. The method of claim 15, wherein the system activity metrics include average memory access time.

17. The method of claim 16, wherein adjusting comprises:

setting the threshold to a predetermined maximum value if the process utilization exceeds a maximum allowed utilization level; and

otherwise, setting the threshold based on the average access time.

18. The method of claim 17, wherein setting the threshold based on the average access time comprises:

setting the threshold to a minimum threshold value if the average access time is less that a lower average access time threshold and setting the threshold to the maximum threshold if the average access time is greater than an upper average access time threshold;

otherwise, setting the threshold to a value computed using the minimum threshold, the maximum threshold and the average access time.