Data block frequency map dependent caching

• US 8,271,736 B2
• Filed: 02/07/2008
• Issued: 09/18/2012
• Est. Priority Date: 02/07/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Karan, Thakur, Tarun
• Primary Examiner(s): Song, Jasmine
• Assistant Examiner(s): BERNARD, DANIEL J
• Application Number:
  US12/027,983
• Publication Number:
  US 20090204765A1
• Time in Patent Office: 1,685 Days
• Field of Search: None
• 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 a data de-duplication mechanism with 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 data block in a dataset;

creating a set of de-duplicated data blocks in the cache memory with the data de-duplication mechanism;

ordering the set of de-duplicated data blocks in the cache memory according to the corresponding frequency count for each of the de-duplicated data blocks;

ordering de-duplicated data blocks having a same frequency count in the cache memory into a least recently used order according to an average value of a cache residence term for each de-duplicated data block;

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

evicting the data block from the cache memory when the frequency count for the data block is greater than zero; and

evicting all data blocks having a same frequency count that is less than or equal to the frequency count of other data blocks from the cache memory, with data blocks having a same frequency count evicted in the least recently used order according to an average value of a cache residence term, before evicting any data block with a higher frequency count.

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. A device for increasing cache memory performance and utilization, comprising:

a cache memory;

a data de-duplication engine in data communication with said cache memory;

a data block frequency map for receiving a frequency count for a data block from said data de-duplication engine; and

an eviction controller in data communication with said cache memory and adapted to receive frequency counts from said data frequency map and further adapted to select a next data block to be deleted from said cache memory from among a group of data blocks having a same frequency count and arranged within said group in a least recently used order according to an average value of a cache residence term for each data block,

wherein, said data block frequency map provides weights that are directly proportional to a corresponding frequency count of a block in a dataset, a data block having a nonzero frequency count is deletable, said weights are used to influence a caching algorithm controlling said page prefetching and eviction process, and, during operation, all data blocks that have a lesser frequency count in said dataset are evicted in said least recently used order according to said average value of said cache residence term before any others with higher frequencies, even though such may not have been a first block for page eviction decided by said caching algorithm.

4. The device of claim 3, 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.

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

6. 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 comprising a frequency of duplicate data objects; and

a least recently used (LRU) cache manager for arranging data objects into groups in said cache memory, each of said groups comprising data objects having a same value of said frequency, and data objects in each of said groups ordered into a least recently used order according to an average value of a cache residence term for each data object, and for evicting data objects from said cache memory from a group of data objects having a lowest frequency greater than zero indicated by a corresponding value in said data object frequency map, and for evicting data objects in each of said groups in a least recently used order according to an average value of a cache residence term for each data object.

7. The cache memory system of claim 6, further comprising:

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

8. The cache memory system of claim 6, further comprising:

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

9. The cache memory system of claim 6, 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.

10. The cache memory system of claim 6, wherein caching memory depends on a data block frequency map for page prefetching, and a 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.

11. A computer program product, comprising:

a non-transitory computer-readable medium;

means, provided on the computer-readable medium, for forming a table comprising a frequency of duplicate data objects in a cache memory;

means, provided on the computer-readable medium, for ordering the data objects in the cache memory according to their corresponding frequencies from the table;

means, provided on the computer-readable medium, for forming groups of data objects, each group comprising data objects with a same frequency, and within each group, ordering the data objects in a least recently used order according to an average value of a cache residence term for each data object;

means, provided on the computer-readable medium, for evicting from the cache memory a data object selected from a group of data objects having a least value of frequency, and from among the group of data objects comprising a least value of frequency, for evicting the least recently used data object according to the average value of the cache residence term for each data object; and

means, provided on the computer-readable medium, for evicting all data objects from a group of data objects having a least value of frequency before ejecting a data object from a group of data objects having a higher value of frequency.