Method providing for the flexible prefetching of data from a data storage system

• US 5,765,213 A
• Filed: 12/08/1995
• Issued: 06/09/1998
• Est. Priority Date: 12/08/1995
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Ofer, Erez
• Primary Examiner(s): Downs, Robert W.
• Assistant Examiner(s): Verbrugge, Kevin
• Application Number:
  US08/569,803
• Time in Patent Office: 914 Days
• Field of Search: 395/414, 395/421.03, 395/464, 395/383
• US Class Current: 711/213
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A method of prefetching data from the storage media of a data storage system, in which the data is stored on, and read from, the storage media in individually-accessible data storage portions, such as tracks of a hard disk. A number of immediately past-read data storage portions are used to predict a storage portion or portions that will likely be requested in the future. The unique identifiers of those previously-read data storage portions are determined, and a prediction coefficient is calculated for each unique identifier. The prediction coefficient is then multiplied by the unique identifier, and the results are summed to determine the unique identifier of a data portion to be prefetched.

Claims

1. A method of prefetching data from storage media of a data storage system, in which data is stored on, and read from, the storage media in individually-accessible data storage portions, each said data storage portion having a unique identifier, the method including the steps of:

designating a number of previously - read data storage portions as the data storage portions upon which a data storage portion prefetch prediction will be based;

determining the unique identifiers of each of the designated data storage portions;

calculating a prediction coefficient for each determined unique identifier;

predicting the unique identifier of at least one data storage portion, by multiplying the unique identifier of each of the designated data storage portions by the prediction coefficient for each determined unique identifier and summing the results for all the unique identifiers to determine the unique identifier for the at least one data storage portion; and

prefetching from the storage media the at least one data storage portion having the predicted unique identifier.

2. The data prefetch method of claim 1 in which the step of designating a number of previously-read data storage portions includes selecting a plurality of consecutive, immediately past-read data storage portions as the designated data storage portions.

3. The data prefetch method of claim 2 in which the step of predicting the unique identifier of each of at least one data storage portion includes ascertaining the unique identifiers of a number of separate data storage portions.

4. The data prefetch method of claim 3 in which the step of prefetching the at least one data storage portion includes prefetching the number of separate data storage portions having the unique identifiers which have been resolved.

5. The data prefetch method of claim 4 wherein the data storage system includes a cache memory, the method further including the step of placing the number of separate data storage portions in the cache memory.

6. The data prefetch method of claim 5 in which the step of prefetching the at least one data storage portion further includes reading the number of data storage portions from the storage media in a particular order.

7. The data prefetch method of claim 6 in which the step of placing the number of separate data storage portions in the cache memory includes ordering the number of separate data storage portions in the cache memory in the same particular order in which the number of separate data storage portions were read from the storage media.

8. The data prefetch method of claim 3 in which the step of selecting a plurality of consecutive, immediately past-read data storage portions as the designated data storage portions includes selecting n immediately past-read data storage portions.

9. The data prefetch method of claim 8 in which the step of ascertaining the unique identifier of a number of separate data storage portions includes ascertaining the unique identifiers of n separate data storage portions.

10. A method of prefetching data from storage media in a data storage system, in which the data is stored on, and read from, the storage media in individually-accessible data storage portions, each having a unique identifier, the method including the steps of:

selecting a number of previously-read data storage portions;

labeling the data storage portions, with the label k, in the order in which the data storage portions were read, from k=1 to k=p;

determining the unique identifier, S(n-k),of each of the p data storage portions;

calculating a prediction coefficient a_k for each of the p data storage portions; and

predicting the unique identifier, S(n), of the next data storage portion to be read, according to the formula;

##EQU6##