Least profitability used caching scheme

• US 8,788,758 B1
• Filed: 01/12/2011
• Issued: 07/22/2014
• Est. Priority Date: 11/04/2008
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: de la Iglesia, Erik
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US13/005,463
• Time in Patent Office: 1,287 Days
• Field of Search: 711/136, 711/154, 711/156
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

A storage proxy loads cache lines with data from a storage device. Storage access requests are received from an initiator and directed to the storage device. The storage proxy provides the data from the cache lines in response to cache hits on the cache lines, and provides the data from the storage device in response to cache misses on the cache lines. Hit access times are identified for the cache lines in response to the cache hits and miss access times are identified for the storage device in response to cache misses. Data in the cache lines is updated with data from the storage device based on the hit access times and the miss access times associated with the cache lines.

Claims

1. An apparatus, comprising:

cache lines configured to store copies of data from a storage device; and

logic circuitry configured to derive hit access times and miss access times for the cache lines, wherein the hit access times are derived based on access times for the cache lines and the miss access times are derived based on access times for the storage device.

2. The apparatus of claim 1 wherein the logic circuitry is configured to replace the data in the cache lines with other data from the storage device according to the hit access times and miss access times.

3. The apparatus of claim 1 wherein the logic circuitry is configured to identify ratios between the hit access times and the miss access times associated with a cache line of the cache lines.

4. The apparatus of claim 3 wherein the logic circuitry is further configured to:

identify a high access time profitability cache line of the cache lines as having larger differences between the associated miss access times and associated hit access times and a low access time profitability cache line of the cache lines as having smaller differences between the associated miss access times and associated hit access times; and

replace the data in the low access time profitability cache lines before replacing the data in the high access time profitability cache lines.

5. The apparatus of claim 4 wherein the logic circuitry is further configured to:

receive a read request;

determine the data associated with the read request is located in the storage device and not located in the cache lines;

invalidate at least some of the low profitability access time cache lines in response to the cache lines being substantially full; and

replace the invalidated low profitability access time cache lines cache lines with the data in the storage device associated with the read request.

6. The apparatus of claim 1 wherein the logic circuitry is configured to identify address ranges associated with blocks of data, wherein at least some of the address ranges are associated with multiple cache lines and at least some of the hit access times and miss access times are associated with the address ranges.

7. The apparatus of claim 6 wherein the logic circuitry is configured to:

receive read requests;

identify read addresses in the read requests;

identify the address ranges containing the read addresses;

identify new hit access times for the identified address ranges when the read addresses are associated with data in the cache lines; and

identify new miss access times for the identified address ranges when the read addresses not associated with data in the cache lines.

8. The apparatus according to claim 7 wherein the logic circuitry is configured to average the new hit access times with the hit access times associated with the identified address ranges and average the new miss access times with the hit access times associated with the samo identified address ranges.

9. The apparatus of claim 6 wherein the logic circuitry is further configured to:

compare the hit access times with the miss access times associated with the address ranges;

identify access time profitability values for the address ranges based on the comparisons;

identify one of the address ranges having a lowest one of the access time profitability values; and

replacing the data in all of the cache lines associated with the identified one of the address ranges.

10. A method, comprising:

providing a cache memory;

providing a processor, configured to perform the steps of;

storing data from a storage device in cache lines;

receiving storage access requests;

identifying access times for servicing the storage access requests;

associating the access times with the cache lines;

deriving access time profitability values for the cache lines based on the associated access times; and

replacing data in the cache lines with data from the storage device based on the access time profitability values.

11. The method of claim 10 wherein the access times comprise hit access times for accessing the cache lines when the data associated with the storage access requests is located in the cache lines and miss access times for accessing the storage device when the data associated with the storage access requests is not located in the cache lines.

12. The method of claim 11 wherein deriving the access time profitability factors comprise deriving a ratio between the hit access times and miss access times associated with the same-cache lines.

13. The method of claim 10 further comprising:

receiving new storage access requests;

identifying new access times for the storage access requests;

associating the new access times with the cache lines;

updating the access time profitability values for the cache lines based on the new access times associated with the cache lines; and

replacing data in the cache lines with data from the storage device according to the updated access time profitability values.

14. The method of claim 13 wherein updating the access time profitability values comprises averaging the new access times with the access times associated with the cache lines.

15. The method of claim 10 wherein replacing the data in the cache lines comprises replacing the data in the cache lines with lower access time profitability values before replacing the data in the cache lines with higher access time profitability values.

16. The method of claim 10, further comprising:

identifying read count values for the cache lines;

identifying last read timestamp values for the cache lines; and

replacing data in the cache lines based on the read count values and/or the last read timestamp values for the cache lines.

17. The method of claim 10, comprising:

identify clusters of data having associated address ranges;

storing at least some of the clusters of data into multiple cache lines;

associating the access times with the clusters of data;

deriving the access time profitability values for the clusters of data; and

replacing the clusters of data in the cache lines based on the access time profitability values for the clusters of data.

18. The method of claim 17 further comprising:

identifying data access patterns for the storage access requests;

determining new address ranges for at least some of the clusters of data according to the data access patterns; and

identify new access times for the clusters of data with the new address ranges.

19. A storage proxy, comprising:

a cache resource including cache lines; and

a processor configured to;

load the cache lines with data from a storage device;

receive storage access requests from an initiator directed to the storage device;

provide the data from the cache lines in response to identifying cache line hits for the storage access requests;

provide the data from the storage device in response to identifying cache line misses for the storage access requests;

identify hit access times for the cache lines in response to the cache line hits;

identify miss access times for the storage device in response to the cache line misses; and

replace the data in the cache lines with other data from the storage devices based on the hit access times and the miss access times.

20. The storage proxy of claim 19 wherein the hit access times and miss access times are associated with the cache lines and the data in the cache lines is replaced according to comparisons between the hit access times and miss access times associated with the same cache lines.

21. The storage proxy of claim 19, wherein the cache lines include a miss access time counter and a hit access time counter.

22. The storage proxy of claim 19 further comprising a cluster map configured to identify address ranges for blocks of data.

23. The storage proxy of claim 22 wherein at least some of the miss access times and hit access times are associated with the address ranges.

24. The storage proxy of claim 23 wherein the processor is further configured to:

receive new storage access requests;

identify new hit access times for the cache lines in response to cache line hits for the new storage access requests;

combine the new hit access times with the hit access times previously identified for the same cache lines;

identify new miss access times for the storage device in response to cache line misses for the new storage access requests; and

combine the new miss access times with the miss access times associated with the cache lines.

25. The storage proxy of claim 23 wherein the processor is further configured to average the new hit access times with the hit access times previously identified for the same cache lines and average the new miss access times with the miss access times previously associated with the cache lines.