Browse Prior Art Database

Cache with Automatic Working Set Size Determination

IP.com Disclosure Number: IPCOM000166628D
Original Publication Date: 2008-Jan-18
Included in the Prior Art Database: 2008-Jan-18
Document File: 2 page(s) / 27K

Publishing Venue

IBM

Abstract

This invention provides the design and implementation for a cache which is able to monitor its usage to accurately and dynamically determine the current size of its using application’s working set and adjust its capacity accordingly within a maximum upper bound determined by the using application. This results in improved performance of applications while reducing operational complexity.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Cache with Automatic Working Set Size Determination

Disclosed is a cache which is able to monitor its usage to accurately and dynamically determine the current size of its using application's working set and adjust its capacity accordingly within a maximum upper bound determined by the using application. The cache is implemented as a simple hash table of keyed entries. Each entry holds one item of data and some usage information about the item. This is a common software cache implementation design. The usage information maintained in the entry about its item includes:
an indication of its last retrieval, and
an indication of the time it was created

At any moment in time the cache has a working set size and a capacity which is somewhat more than the working set size. Whenever the number of items in the cache reaches its current capacity, then the items that have gone the longest without reference are evicted from the cache as necessary to get it back down to its working set. This is also a common cache implementation design. However, in this design when a cached item is evicted its containing entry is retained in the cache, but with a null value for the item. Such a retained entry is called an inactive entry. If an item is added to the cache and an inactive entry is found under the item's key, then the item is considered to be "re- added" to the cache. That is, if an item is evicted and then later another item is added that has the same key as the evicted item it is considered to be replacing an item that was evicted while still in use. Also note that if the entry selected for an item being added does not have a n...