Full track read for adaptive pre-fetching of data

• US 7,899,996 B1
• Filed: 12/31/2007
• Issued: 03/01/2011
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Levin-Michael, Orit
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): BRADLEY, MATTHEW A
• Application Number:
  US12/006,127
• Time in Patent Office: 1,156 Days
• Field of Search: 711/137
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6024 History based prefetching

Abstract

Adaptively pre-fetching data includes collecting a first set of statistics based on a number of avoidable read-misses in which data exists that is prior to data being read, collecting a second set of statistics based on a number of avoidable read-misses in which data exists that follows data being read, and collecting a third set of statistics based on said first and second sets of statistics. On the basis of the second set of statistics, a pre-fetch technique is selected from a first technique that pre-fetches data following data being read and a second technique that pre-fetches data before and following the data being read. The first and third set of statistics may be used to determine when to pre-fetch data.

Claims

1. A method for adaptively pre-fetching data, comprising:

collecting a first set of statistics based on a number of avoidable read-misses in which data exists that is prior to data being read;

collecting a second set of statistics based on a number of avoidable read-misses in which data exists that follows data being read;

collecting a third set of statistics based on said first and second sets of statistics;

on the basis of said second set of statistics, selecting a pre-fetch technique from a first technique that pre-fetches data following data being read and a second technique that pre-fetches data before and following the data being read, wherein the selecting of the second technique reduces a number of instances where out of order reads result in avoidable read-misses, and wherein the avoidable read-misses are read-misses that could have been averted had a sector of data at a storage location been pre-fetched with other sectors of data at the storage location that were previously fetched;

upon detection of an avoidable read-miss and selecting the first technique, pre-fetching data following data being read based on comparison of a generated random number and the first set of statistics; and

upon detection of the avoidable read-miss and selecting the second technique, pre-fetching data before and following data being read based on a comparison of a generated random number and the third set of statistics.

2. The method of claim 1, wherein pre-fetching data before and following data being read includes fetching an entire track from a disk.

3. The method of claim 1, wherein pre-fetching data following data being read includes fetching data from the data being read to the end of a track on a disk.

4. The method of claim 1, wherein selecting a pre-fetch technique includes comparing the second set of statistics with a predefined value.

5. The method of claim 4, wherein the predefined value is a user settable parameter.

6. The method of claim 1, wherein, following selection of the first technique, data following data being read is pre-fetched if the generated random number is less than a value based on the first set of statistics and wherein, following selection of the second technique, data before and following data being read is pre-fetched if the generated random number is less than a value based on the third set of statistics.

7. The method of claim 6, wherein, upon selection of the first technique and the generated random number being greater than the value based on the first set of statistics, the values based on the sets of statistics are decremented.

8. The method of claim 6, wherein, upon selection of the second technique and the generated random number being greater than the value based on the third set of statistics, the values based on the sets of statistics are decremented.

9. Computer software, provided in a non-transitory computer-readable storage medium, that adaptively pre-fetches data, the software comprising:

executable code that collects a first set of statistics based on a number of avoidable read-misses in which data exists that is prior to data being read;

executable code that collects a second set of statistics based on a number of avoidable read-misses in which data exists that follows data being read;

executable code that collects a third set of statistics based on said first and second sets of statistics;

executable code that uses said second set of statistics to select a pre-fetch technique from a first technique that pre-fetches data following data being read and a second technique that pre-fetches data before and following the data being read, wherein the selecting of the second technique reduces a number of instances where out of order reads result in avoidable read-misses, and wherein the avoidable read-misses are read-misses that could have been averted had a sector of data at a storage location been pre-fetched with other sectors of data at the storage location that were previously fetched;

executable code that pre-fetches data following data being read based on comparison of a generated random number and the first set of statistics upon detection of an avoidable read-miss and selecting the first technique; and

executable code that pre-fetches data before and following data being read based on a comparison of a generated random number and the third set of statistics upon detection of the avoidable read-miss and selecting the second technique.

10. The computer software of claim 9, wherein pre-fetching data before and following data being read includes fetching an entire track from a disk.

11. The computer software of claim 9, wherein pre-fetching data following data being read includes fetching data from the data being read to the end of a track on a disk.

12. The computer software of claim 9, wherein selecting a pre-fetch technique includes comparing the second set of statistics with a predefined value.

13. The computer software of claim 12, wherein the predefined value is a user settable parameter.

14. The computer software of claim 9, wherein, following selection of the first technique, data following data being read is pre-fetched if the generated random number is less than a value based on the first set of statistics and wherein, following selection of the second technique, data before and following data being read is pre-fetched if the generated random number is less than a value based on the third set of statistics.

15. The computer software of claim 14, wherein, upon selection of the first technique and the generated random number being greater than the value based on the first set of statistics, the values based on the sets of statistics are decremented.

16. The computer software of claim 14, wherein, upon selection of the second technique and the generated random number being greater than the value based on the third set of statistics, the values based on the sets of statistics are decremented.

17. A storage device, comprising:

a plurality of directors;

a plurality of disk drives coupled to at least some of the directors;

a global memory, coupled to the directors, wherein at least one of the directors includes software that pre-fetches data from the disks into global memory, the software including executable code that collects a first set of statistics based on a number of avoidable read-misses in which data exists that is prior to data being read, executable code that collects a second set of statistics based on a number of avoidable read-misses in which data exists that follows data being read, executable code that collects a third set of statistics based on said first and second sets of statistics, executable code that uses said second set of statistics to select a pre-fetch technique from a first technique that pre-fetches data following data being read and a second technique that pre-fetches data before and following the data being read, wherein the selecting of the second technique reduces a number of instances where out of order reads result in avoidable read-misses, and wherein the avoidable read-misses are read-misses that could have been averted had a sector of data at a storage location been pre-fetched with other sectors of data at the storage location that were previously fetched, executable code that reads data following data being read based on comparison of a generated random number and the first set of statistics upon detection of an avoidable read-miss and selecting the first technique, and executable code that reads data before and following data being read based on a comparison of a generated random number and the third set of statistics upon detection of the avoidable read-miss and selecting the second technique.

18. The storage device of claim 17, wherein pre-fetching data before and following data being read includes fetching an entire track from a disk.

19. The storage device of claim 17, wherein pre-fetching data following data being read includes fetching data from the data being read to the end of a track on a disk.

20. The storage device of claim 17, wherein selecting a pre-fetch technique includes comparing the second set of statistics with a predefined value.

21. The storage device of claim 20, wherein the predefined value is a user settable parameter.

22. A method of determining when to pre-fetch a full track of data on a disk, comprising:

collecting statistics based on a number of avoidable read-misses in which data exists that is in the same track as data being read; and

upon detection of an avoidable read-miss, selecting and performing a pre-fetch technique for pre-fetching a full track of data based on comparison of a generated random number and the set of statistics, wherein the selecting of the pre-fetch technique reduces a number of instances where out of order reads result in avoidable read-misses, and wherein the avoidable read-misses are read-misses that could have been averted had a sector of data at a storage location been pre-fetched with other sectors of data at the storage location that were previously fetched.

23. The method of claim 22, wherein the statistics are based on tracking a number of avoidable read-misses in which data exists that follows data being read and a number of avoidable read-misses in which data exists that is prior to data being read.

24. Computer software, provided in a non-transitory computer-readable medium, that determines when to pre-fetch additional data from a disk, comprising:

executable code that provides for selection of one of the following modes;

a first mode for pre-fetch to end of track only, a second mode for pre-fetch entire track, a third mode where no pre-fetch is performed, and a fourth mode where pre-fetch to an end of track is performed upon second and subsequent read misses for a track, wherein the selecting of the second mode reduces a number of instances where out of order reads result in avoidable read-misses, and wherein the avoidable read-miss are read-misses that could have been averted had a sector of data at a storage location been pre-fetched with other sectors of data at the storage location that were previously fetched;

executable code that collects a first set of statistics based on a number of avoidable read-misses in which data exists that is prior to data being read;

executable code that collects a second set of statistics based on a number of avoidable read-misses in which data exists that follows data being read in response to selection of the second mode;

executable code that collects a third set of statistics based on said first and second sets of statistics in response to selection of the second mode;

executable code that pre-fetches data following data being read based on comparison of a generated random number and the first set of statistics upon detection of an avoidable read-miss and on selecting of the first mode; and

executable code that pre-fetches data before and following data being read based on a comparison of a generated random number and the third set of statistics upon detection of the avoidable read-miss and selecting the second mode.

25. Computer software, according to claim 24, wherein the second mode also includes pre-fetching to the end of track, the software further comprising:

executable code that, in response to selection of the second mode, uses said second set of statistics to select a pre-fetch technique from a first technique that pre-fetches data following data being read and a second technique that pre-fetches data before and following the data being read; and

executable code that pre-fetches data following data being read based on selection of the second mode and the first technique.