Determining pre-fetching per storage unit on a storage system

1. For a data storage system including a cache and one or more physical storage devices, wherein data for a plurality of logical storage units is stored on the one or more physical storage devices, a method comprising:

receiving a first read request to read a first page of a first of the plurality of logical storage units;

for a first group of one or more most recent read requests for the first logical storage unit, the first group including the first read request and one or more most recent read requests for the logical storage unit prior to the first read request, each of the one or more most recent read requests specifying a respective second page of the first logical storage unit, determining a value of a proximity metric indicative of a collective sequential proximity of the first page and the one or more second pages within the first logical storage unit;

determining whether to pre-fetch one or more next sequential pages to the first page of the first logical storage unit based on the value of the proximity metric;

fetching the first page from the one or more physical storage device into the cache; and

prefetching the one or more next sequential pages from the one or more physical storage devices into the cache only if it is determined to prefetch the one or more next sequential pages,

wherein a predefined look-ahead value defines a number of next pages to pre-fetch for the first logical storage unit for a pre-fetch operation,

wherein the proximity metric is based at least in part on a predefined look-ahead threshold value corresponding to the predefined look-ahead value, and

wherein the predefined look-ahead threshold value affects a probability of performing a pre-fetch operation.

2. The method of claim 1 , wherein determining whether to pre-fetch the one or more next sequential pages of the first logical storage unit includes:

comparing the proximity metric to a predefined proximity threshold; and

determining to pre-fetch the one or more next sequential pages if the proximity metric is greater than or equal to the predefined proximity threshold.

3. The method of claim 1 ,

wherein determining the proximity metric includes:

sorting the first group into a first sequence according to a sequential order of the first page and the one or more second pages with the first logical storage unit; and

calculating the proximity metric value based at least in part on the sorted first group.

4. The method of claim 1 , wherein the predefined look-ahead threshold value is defined to be the predefined look-ahead value.

5. The method of claim 1 , further comprising:

maintaining a data structure including one or more entries, each entry corresponding to a respective one of the plurality of logical storage units, and each entry specifying a group of most recent read requests for the respective logical storage unit corresponding to the entry,

wherein determining the proximity metric includes accessing the data structure.

6. The method of claim 5 , wherein each entry of the data structure includes one or more page fields specifying a respective value for a page of one of the one or more most recent read requests of the logical storage unit represented by the entry, up to a predefined maximum number of page field values, and

wherein the method further comprises:

in response to receiving the first read request, determining that a first entry of the one or more entries of the data structure already includes the predefined maximum number of page field values;

removing one or more oldest page field values from the first entry; and

adding a page field value representing the first page.

7. The method of claim 3 , wherein determining the proximity metric further includes, for each pair of successive read requests in the first sequence:

determining a page difference, if any, between the respective pages of the pair, and

if there is a page difference between the respective pages:

adding one to a page difference count;

determining whether an amount of the page difference is the same or less than the predefined look-ahead threshold value; and

if the amount of the page difference is the same or less than the predefined look- ahead threshold value, adding one to a pre-fetch hit count,

wherein the proximity metric value is calculated as the pre-fetch hit count divided by the page difference count.

8. A data storage system comprising:

a cache;

a plurality of logical storage units;

one or more physical storage devices on which data for the logical storage units is stored;

one or more processors; and

a memory comprising code stored thereon that, when executed, performs a method comprising:

receiving a first read request to read a first page of a first of the plurality of logical storage units;

for a first group of one or more most recent read requests for the first logical storage unit, the first group including the first read request and one or more most recent read requests for the logical storage unit prior to the first read request, each of the one or more most recent read requests specifying a respective second page of the first logical storage unit, determining a value of a proximity metric indicative of a collective sequential proximity of the first page and the one or more second pages;

determining whether to pre-fetch one or more next sequential pages to the first page of the first logical storage unit based on the value of the proximity metric;

fetching the first page from the one or more physical storage device into the cache; and

prefetching the one or more next sequential pages from the one or more physical storage devices into the cache only if it is determined to prefetch the one or more next sequential pages,

wherein a predefined look-ahead value defines a number of next pages to pre-fetch for the first logical storage unit for a pre-fetch operation,

wherein the proximity metric is based at least in part on a predefined look-ahead threshold value corresponding to the predefined look-ahead value, and

wherein the predefined look-ahead threshold value affects a probability of performing a pre-fetch operation.

9. The data storage system of claim 8 , wherein determining whether to pre-fetch the one or more next sequential pages of the first logical storage unit includes:

comparing the proximity metric to a predefined proximity threshold; and

determining to pre-fetch the one or more next sequential pages if the proximity metric is greater than or equal to the predefined proximity threshold.

10. The data storage system of claim 8 ,

wherein determining the proximity metric includes:

sorting the first group into a first sequence according to a sequential order of the first page and the one or more second pages with the first logical storage unit; and

calculating the proximity metric value based at least in part on the sorted first group.

11. The data storage system of claim 8 , wherein the predefined look-ahead threshold value is defined to be the predefined look-ahead value.

12. The data storage system of claim 8 , the method further comprising:

maintaining a data structure including one or more entries, each entry corresponding to a respective one of the plurality of logical storage units, and each entry specifying a group of most recent read requests for the respective logical storage unit corresponding to the entry,

wherein determining the proximity metric includes accessing the data structure.

13. The data storage system of claim 12 , wherein each entry of the data structure includes one or more page fields specifying a respective value for a page of one of the one or more most recent read requests of the logical storage unit represented by the entry, up to a predefined maximum number of page field values, and

wherein the method further comprises:

in response to receiving the first read request, determining that a first entry of the one or more entries of the data structure already includes the predefined maximum number of page field values;

removing one or more oldest page field values from the first entry; and

adding a page field value representing the first page.

14. The system of claim 10 , wherein determining the proximity metric further includes, for each pair of successive read requests in the first sequence:

determining a page difference, if any, between the respective pages of the pair, and if there is a page difference between the respective pages:

adding one to a page difference count;

determining whether an amount of the page difference is the same or less than the predefined look-ahead threshold value; and

if the amount of the page difference is the same or less than the predefined look- ahead threshold value, adding one to a pre-fetch hit count,

wherein the proximity metric value is calculated as the pre-fetch hit count divided by the page difference count.

15. One or more computer-readable media having software stored thereon for a storage system including a cache, a plurality of logical storage units and one or more physical storage devices on which data for the logical storage units is stored, the software comprising:

executable code that receives a first read request to read a first page of a first of the plurality of logical storage units;

executable code that, for a first group of one or more most recent read requests for the first logical storage unit, the first group including the first read request and one or more most recent read requests for the logical storage unit prior to the first read request, each of the one or more most recent read requests specifying a respective second page of the first logical storage unit, determines a value of a proximity metric indicative of a collective sequential proximity of the first page and the one or more second pages;

executable code that determines whether to pre-fetch one or more next sequential pages to the first page of the first logical storage unit based on the value of the proximity metric;

executable code that fetches the first page from the one or more physical storage devices into the cache; and

executable code that prefetches the one or more next sequential pages from the one or more physical storage into the cache only if it is determined to prefetch the one or more next sequential pages,

wherein a predefined look-ahead value defines a number of next pages to pre-fetch for the first logical storage unit for a pre-fetch operation, wherein the proximity metric is based at least in part on a predefined look-ahead threshold value corresponding to the predefined look-ahead value, and

wherein the predefined look-ahead threshold value affects a probability of performing a pre-fetch operation.

16. The one or more computer-readable media of claim 15 , wherein the executable code that determines whether to pre-fetch the one or more next sequential pages of the first logical storage unit includes:

executable code that compares the proximity metric to a predefined proximity threshold; and

executable code that determines to pre-fetch the one or more next sequential pages if the proximity metric is greater than or equal to the predefined proximity threshold.

17. The one or more computer-readable media of claim 15 ,

wherein executable code that determines the proximity metric includes:

executable code that sorts the first group into a first sequence according to a sequential order of the first page and the one or more second pages with the first logical storage unit;

executable code that, for each pair of successive read requests in the first sequence:

determines a page difference, if any, between the respective pages of the pair, and

if the amount of the page difference is the same or less than the look-ahead value, adds one to a pre-fetch hit count; and

executable code that calculates the proximity metric value based at least in part on the sorted first group as the pre fetch hit count divided by the page difference count.

18. The one or more computer-readable media of claim 15 , wherein the predefined look-ahead threshold value is defined to be the predefined look-ahead value.

19. The one or more computer-readable media of claim 15 , the software further comprising:

executable code that maintains a data structure including one or more entries, each entry corresponding to a respective one of the plurality of logical storage units, and each entry specifying a group of most recent read requests for the respective logical storage unit corresponding to the entry,

wherein determining the proximity metric includes accessing the data structure.

20. The one or more computer-readable media of claim 19 , wherein each entry of the data structure includes one or more page fields specifying a respective value for a page of one of the one or more most recent read requests of the logical storage unit represented by the entry, up to a predefined maximum number of page field values, and

wherein the software further comprises:

executable code that, in response to receiving the first read request, determines that a first entry of the one or more entries of the data structure already includes the predefined maximum number of page field values;

executable code that removes one or more oldest page field values from the first entry; and

executable code that adds a page field value representing the first page.