Using temporal access patterns for determining prefetch suitability

• US 8,775,741 B1
• Filed: 01/08/2010
• Issued: 07/08/2014
• Est. Priority Date: 01/13/2009
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: de la Iglesia, Erik
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US12/684,387
• Time in Patent Office: 1,642 Days
• Field of Search: 711/137, 711/173, 711/204, 711/E12.057, 711/167, 711/169, 711/213
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0615 Address space extension
• 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/6024 History based prefetching

Abstract

A storage control system includes a prefetch controller that identifies memory regions for prefetching according to temporal memory access patterns. The memory access patterns identify a number of sequential memory accesses within different time ranges and a highest number of memory accesses to the different memory regions within a predetermine time period.

Claims

1. A system, comprising:

a cache memory; and

a control circuit configured to;

monitor storage operations to a storage device;

identify regions accessed within the storage device;

identify time durations between sequential accesses to the same regions of the storage device;

prefetch data from the regions of the storage device based on the time durations between sequential accesses to the same regions of the storage device; and

store the prefetched data in the cache memory,

wherein a first set of counters track the number of accesses to each of the different regions within a given time window and a second set of counters track a maximum number of accesses to each of the different regions for the given time window.

2. The system of claim 1 wherein the data is prefetched from the storage device into a tiering media and the tiering media comprises memory components that have faster access times than the storage device.

3. The system of claim 2 wherein the tiering media comprises flash memory or Random Access Memory (RAM) integrated circuits and the storage device comprises a disk array.

4. The system of claim 2 wherein the tiering media resides within a storage system.

5. The system of claim 4 wherein the tiering media is distributed among, or shared, with one or more clients connected to the storage system through a network interface.

6. The system of claim 1 wherein the control circuit is configured to monitor storage access patterns to the storage device and dynamically partition storage address areas into the regions according to the storage access patterns.

7. A system, comprising:

a control circuit configured to;

monitor storage operations to a storage device;

identify regions accessed within the storage device;

identify times between sequential accesses to the same regions;

prefetch data from the regions of the storage device based on the times between sequential accesses to the same regions; and

track the times between sequential accesses to the same regions for different time ranges.

8. A system, comprising:

a control circuit configured to;

monitor storage operations to a storage device;

associate storage address areas within the storage device with different regions;

track a number of storage operations to each of the different regions within a given time window;

assign timestamps to the storage operations and determine a number of accesses to each of the different regions within the given time window by incrementing or decrementing a set of counters according to a comparison of the timestamps with a configurable time window value; and

prefetch data from the storage device in response to the storage operations based on the number of accesses to each of the different regions.

9. A system, comprising:

a logic circuitry configured to;

monitor storage operations to a storage device;

associate storage address areas within the storage device with different regions;

track storage accesses to the different regions during a given time window;

track a maximum number of storage accesses to the different regions for the given time window; and

identify an average size of the storage accesses for each of the different regions and prefetch an amount of data from the different regions according to the average size of the storage accesses for the different regions and the maximum number of accesses to the different regions for the given time window.

10. A system, comprising:

a control circuit configured to;

monitor storage operations to a storage device;

associate storage address areas within the storage device with different regions;

track storage accesses to the different regions during a given time window; and

prefetch data from the storage device based on the storage accesses tracked to the different regions, wherein;

a first set of counters track the number of accesses to each of the different regions within a given time window,

a second set of counters track a maximum number of accesses to each of the different regions for the given time window, and

a third set of counters track a number of back to back storage operations that occur within different time intervals for each of the different regions.

11. The system of claim 10 wherein the control circuit assigns timestamps to the storage operations and tracks the number of back to back storage operations that occur within the different time intervals in the different regions by incrementing the third set of counters according to a comparison of the timestamps assigned to the back to back storage operations for the same regions.

12. The system of claim 11 further comprising a First In-First Out (FIFO) circuit that buffers the time stamps, and buffers an identifier of the regions associated with the storage operations, on a first in-first out basis during the given time window.

13. A method, comprising:

identifying time values for accesses to different regions of a storage device;

identifying a time difference between a first one of the time values for an earlier one of the accesses to one of the different regions and a second one of the time values for a later one of the accesses to one of the different regions of the storage device;

incrementing a count number for one of the different regions associated with the later one of the accesses;

decrementing a count number for one of the different regions associated with the earlier one of the accesses when the time difference is outside of a threshold value;

identifying a maximum value for the count number associated each of the different regions; and

prefetching data from the different regions based on the maximum value for the count number associated with each of the different regions.

14. A method, comprising:

identifying access patterns for different regions of a storage device;

identifying different time ranges between sequential storage accesses in same regions of the storage device;

identifying a first number for the sequential storage accesses to each of the different regions that are within a given time range;

identifying a second number for all of the other sequential storage accesses to each of the different regions that are outside of the given time range;

identifying a maximum number of storage accesses for each of the different regions that are within a given time window;

identifying ratios for each of the different regions between the first number and the maximum number; and

identifying the different regions suitable for prefetching when the ratios for the regions are greater or equal to the second number for the regions.

15. A method, comprising:

identifying access patterns for different regions of a storage device;

determining a length of prefetching for the different regions by multiplying a maximum number of read operations to each of the different regions within a given time window by an average read size for each of the different regions; and

prefetching data from the different regions of the storage device that are determined to be suitable for prefetching based on the length of prefetching for the different regions.

16. A method, comprising:

identifying, by a computing device, a number of memory accesses within a predetermined time period;

identifying, by the computing device, times between sequential memory accesses;

classifying, by the computing device, the times between the sequential memory accesses into different time ranges; and

prefetching, by the computing device, contents of the memory according to the number of memory accesses, the times identified between the sequential memory accesses, and patterns between the times in the different time ranges.

17. The method of claim 16 further comprising:

identifying a highest number of memory accesses for the predetermined time period; and

prefetching contents of the memory according to the identified highest number of memory accesses and the patterns between the times in the different time ranges.

18. The method of claim 17 further comprising:

inserting operation identifiers into a First In-First Out (FIFO) circuit associated with the memory accesses, the identifiers identifying different memory regions where the memory accesses are directed and including timestamps identifying when the memory accesses were received;

removing the operation identifiers from the FIFO that reside in the FIFO beyond the predetermined time period;

identifying a maximum number of operation identifiers for each of the different memory regions that reside in the FIFO at the same time; and

using the maximum number of operation identifiers to determine which of the associated memory regions to conduct prefetching.