DYNAMIC OPTIMIZATION OF CACHE MEMORY

• US 20080294846A1
• Filed: 08/05/2008
• Published: 11/27/2008
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Endo, Yasuhiro, Bali, Naveen, Patel, Naresh
• Granted Patent: US 8,176,251 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

The present invention includes dynamically analyzing look-up requests from a cache look-up algorithm to look-up data block tags corresponding to blocks of data previously inserted into a cache memory, to determine a cache related parameter. After analysis of a specific look-up request, a block of data corresponding to the tag looked up by the look-up request may be accessed from the cache memory or from a mass storage device.

Claims

1. A method comprising:

dynamically analyzing a look-up request from a cache look-up algorithm to look-up a data block tag corresponding to a block of data previously inserted into a cache memory to determine a cache related parameter;

accessing a block of data corresponding to the tag from a mass storage device; and

dynamically modifying the cache look-up algorithm based on the cache related parameter,

wherein the cache memory comprises a virtual cache memory having a plurality of virtual cache memory portions, blocks of data evicted from a first portion are inserted into a second portion.

2. The method of claim 1, wherein the tag corresponds to a block of data evicted from the cache memory, written over in the cache memory, or no longer stored in the cache memory.

3. The method of claim 1, wherein the tag corresponds to a block of data stored in the cache memory.

4. The method of claim 1, wherein the cache memory comprises one of a buffer cache memory, a victim cache memory, and a virtual cache memory.

5. The method of claim 1, wherein the cache memory comprises a virtual cache memory and the blocks and tags are inserted into the virtual cache memory, and the blocks are not stored in the virtual cache memory.

6. The method of claim 1, wherein dynamically analyzing further comprises:

updating a plurality of counters associated with the tag when a look-up request for the tag is received;

dynamically updating a plurality of statistics derived from the counters when the counters are updated; and

further comprising;

caching, in the cache memory, a copy of the block of data accessed after updating the plurality of statistics.

7. The method of claim 1, further comprising dynamically analyzing and accessing a plurality of tags corresponding to a plurality of blocks of data previously inserted into the cache memory, wherein each tag uniquely identifies a block.

8. The method of claim 1, wherein dynamically analyzing includes determining a hit/miss ratio comprising a ratio of a number of successful look-up requests, and a number of unsuccessful look-up requests.

9. The method of claim 1, where dynamically analyzing includes counting a number of the tags correspond to a metadata block of data, and counting a number of the tags correspond to a normal data block of data.

10. The method of claim 1, wherein the cache memory is a virtual cache memory having a total data storage size, and dynamically analyzing comprises determining a percentage of the total data storage size defined by a sum of data sizes of blocks corresponding to the tags.

11. The method of claim 7, wherein dynamically analyzing comprises counting a number of look-up requests for each tag over a period of time.

12. The method of claim 1, wherein dynamically analyzing comprises determining a working set size comprising a percentage of the number of tags looked up at least once by the operating system.

13. The method of claim 1, wherein the cache related parameter comprises an optimal cache data storage size of the cache memory to store the blocks of data, or an optimal cache data eviction algorithm to evict blocks of data previously inserted into the cache memory from the cache memory.

14. The method of claim 13, wherein an optimal cache data storage size of the cache memory is identified by a cache data storage size of one of the first portion, and a combination of the first portion and the second portion.

15. A method comprising:

dynamically analyzing a look-up request from a cache look-up algorithm to look-up a data block tag corresponding to a block of data previously inserted into a cache memory to determine a cache related parameter;

accessing a block of data corresponding to the tag from a mass storage device; and

dynamically modifying the cache look-up algorithm based on the cache related parameter,

wherein the cache memory comprises a virtual cache memory having a plurality of virtual cache memory portions, blocks of data evicted from a first portion are inserted into a second portion; and

wherein said dynamically analyzing comprises analyzing look-up requests to look-up a first data block tag corresponding to a first blocks of data previously inserted into the first portion, and analyzing a look-up request to look-up a second data block tag corresponding to a second block of data previously inserted into the first and second portions.

16. The method of claim 15, wherein the tag corresponds to a block of data evicted from the cache memory, written over in the cache memory, or no longer stored in the cache memory.

17. The method of claim 15, wherein the cache memory comprises a virtual cache memory and the blocks and tags are inserted into the virtual cache memory, and the blocks are not stored in the virtual cache memory.

18. The method of claim 15, wherein dynamically analyzing further comprises:

updating a plurality of counters associated with the tag when a look-up request for the tag is received;

dynamically updating a plurality of statistics derived from the counters when the counters are updated; and

further comprising;

caching, in the cache memory, a copy of the block of data accessed after updating the plurality of statistics.

19. The method of claim 15, further comprising dynamically analyzing and accessing a plurality of tags corresponding to a plurality of blocks of data previously inserted into the cache memory, wherein each tag uniquely identifies a block.

20. The method of claim 19, wherein dynamically analyzing comprises counting a number of look-up requests for each tag over a period of time.

21. The method of claim 15, wherein the cache related parameter comprises an optimal cache data storage size of the cache memory to store the blocks of data, or an optimal cache data eviction algorithm to evict blocks of data previously inserted into the cache memory from the cache memory.

22. The method of claim 21, wherein an optimal cache data storage size of the cache memory is identified by a cache data storage size of one of the first portion, and a combination of the first portion and the second portion.