DATA BLOCK FREQUENCY MAP DEPENDENT CACHING

• US 20090204765A1
• Filed: 02/07/2008
• Published: 08/13/2009
• Est. Priority Date: 02/07/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thakur, Tarun, Gupta, Karan
• Granted Patent: US 8,271,736 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• 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
• CPC Class Codes: G06F 12/127 using additional replacement algorithms

Abstract

A method for increasing the performance and utilization of cache memory by combining the data block frequency map generated by data de-duplication mechanism and page prefetching and eviction algorithms like Least Recently Used (LRU) policy. The data block frequency map provides weight directly proportional to the frequency count of the block in the dataset. This weight is used to influence the caching algorithms like LRU. Data blocks that have lesser frequency count in the dataset are evicted before those with higher frequencies, even though they may not have been the topmost blocks for page eviction by caching algorithms. The method effectively combines the weight of the block in the frequency map and its eviction status by caching algorithms like LRU to get an improved performance and utilization of the cache memory.

Claims

1. A method for increasing cache memory performance and utilization, comprising:

combining a data block frequency map generated by data de-duplication mechanism and a page prefetching and eviction process;

using said data block frequency map to provide weights that are directly proportional to a corresponding frequency count of a block in a dataset; and

influencing a caching algorithm controlling said page prefetching and eviction process with said weights;

wherein, any data blocks that have a lesser frequency count in said dataset are evicted before any others with higher frequencies, even though such may not have been a first block for page eviction decided by said caching algorithm.

2. The method of claim 1, wherein cache memory performance and utilization are substantially improved by including said weight of blocks in the frequency map and its eviction status with said caching algorithm.

3. The method of claim 1, wherein said caching algorithm embodies a least recently used (LRU) policy.

12. The cache memory system of claim 1 further comprising:

a data frequency index map device for storing and providing access to said data object frequency map.

4. A method for caching memory that depends in part on a data block frequency map generated by data de-duplication for page prefetching, and its page eviction policy, wherein data items that have lesser frequencies of use are evicted before those with higher frequencies even though they may not have been the least recently used.

5. The method of claim 4, further comprising:

using single instance storage for data de-duplication that incidentally provides an data block frequency index map, and such that when a request comes in for a page not already in cache, a least recently used algorithm uses said block frequency index map as an index to select data objects for eviction with lesser frequencies.

6. A device for increasing cache memory performance and utilization, comprising:

a data block frequency map generated by data de-duplication mechanism combined with a page prefetching and eviction process;

wherein, said data block frequency map provides weights that are directly proportional to a corresponding frequency count of a block in a dataset;

wherein, said weights are used to influence a caching algorithm controlling said page prefetching and eviction process;

wherein, during operation, any data blocks that have a lesser frequency count in said dataset are evicted before any others with higher frequencies, even though such may not have been a first block for page eviction decided by said caching algorithm.

7. The device of claim 6, wherein cache memory performiance and utilization are substantially improved by including said weight of blocks in the frequency map and its eviction Status with said caching algorithm.

8. The method of claim 6, wherein said caching algorithm embodies a least recently used (LRU) policy.

9. A cache memory that includes a data block frequency map generated by data de-duplication for page prefetching, and its page eviction policy, wherein data items with lesser frequencies of use are evicted during operation before any with higher frequencies and not strictly have been a least recently used.

10. The cache memory of claim 9, further comprising:

a single instance storage for data de-duplication that incidentally provides an data block frequency index map, and such that when a request comes in for a page not already in cache, a least recently used algorithm uses a block frequency index map as an index to select data objects for eviction with lesser frequencies.

11. A cache memory system, comprising:

a data de-duplicator for eliminating duplicate data objects in a cache memory and for building a data object frequency map; and

an LRU cache manager for evicting data objects from said cache memory that have a lowest duplication frequency indicated by a corresponding value in said data object frequency map, and that have been the least recently used data object.

13. The cache memory system of claim 11, further comprising:

an LRU device which implements a least recently used algorithm and which tracks cache access hits and misses.

14. The cache memory system of claim 11, further comprising:

a data frequency index map device for storing and providing access to said data object frequency map;

an LRU device which implements a least recently used algorithm and which tracks cache access hits and misses; and

an eviction device connected to be able to read said data object frequency map, and read the LRU device, and providing for a selection of which data objects to evict from said cache memory.

15. The cache memory system of claim 11, wherein caching memory depends on a data block frequency map for page prefetching, and its page eviction policy, and data items that have lesser frequencies of use are evicted before those with higher frequencies, even though they may not have been the least recently used.

16. A cache memory control device, wherein caching memory depends on a data block frequency map for page prefetching, and its page eviction policy, and data items that have lesser frequencies of use are evicted before those with higher frequencies, even though they may not have been the least recently used, and a single instance storage for data de-duplication incidentally provides an object frequency index map, such that when a request comes in for a page not already in cache, a least recently used algorithm uses the object frequency index map as an index to select any data objects for eviction with lesser frequencies.