Back to results
US 7,899,996 B1Granted
Full track read for adaptive pre-fetching of data
AssigneeEMC Corporation
InventorOrit Levin-Michael
Life of this patent
Estimating the term…
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.
Claims25
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.
4 more elements
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.
4 more elements
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.
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.
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.
5 more elements
Dependencies are inferred from the claim text.