Method for LFU-LRU Cache Replacement Policy With Constant-Complexity
Publication Date: 2011-Sep-24
The IP.com Prior Art Database
IPCOM000196714D: IP.COM [+2]
We introduce a method for high performance caching using an LFU-LRU (least-frequently-and-least-recently-used) combined replacement policy. The cache itself is implemented as an array. The frequency tracking is implemented using frequency sets, and the recency tracking is implemented with set-relative recency lists, both of which are doubly-linked lists. Each cache element furthermore has references to its associated frequency set and to its associated recency element. These are updated accordingly each time a cache operation is performed, such that the least-frequently-used (LFU) items are always in the LFU set, and the LFU-LRU cache item is always the least-recently-used (LRU) item in the set-relative recency list of the LFU set. Thus, cache item replacement/eviction can always be done in O(1) time. Retrieve and insertion operations are also performed in constant time with this method.
The main purpose of a memory cache is to make data available to consumers of that data more quickly than would be possible if the data were retrieved from its original location in the backing store. Several factors contribute to the performance of a cache -first, the speed of key lookup in the directory to get the address of the required data within the cache. Second is the speed of retrieval of data from the cache - this is accomplished by the use of fast memory such as RAM. Third is the efficiency with which the attributes that are used as the basis for replacement are kept up-to-date. These attributes are referred to herein as the “replacement metadata”, which consists of recency replacement metadata and frequency replacement metadata.
The LFU-LRU cache replacement method presented here satisfies a number of criteria:
· It implements a LFU-LRU combined replacement policy. This is chiefly a method for implementation of LFU. When a LFU cache element is chosen as a candidate for eviction, recency is also used as a criterion for selection of the cache element.
· The size of the cache is configurable at run-time. It can also handle arbitrarily large cache sizes without adversely affecting cache performance.
· All common cache operations are accomplished in constant time. The worst case complexity for cache operations is O(1). (Note: the worst-case complexity for lookup of a key in the directory is dependent on how the directory is implemented; e.g. if the directory is implemented as a hash table, then the average lookup operation complexity is O(1)).
Figure 1 shows the overall layout of the cache’s main components.
The directory, also referred to as a “map”, implements the lookup from cache entry key to cache array entry (either the cache array entry index or a pointer to the cache array entry). Each directory entry consists of a key-value pair, where the key consists of a single cache entry key, and the value is the index of the associated cache entry that contains the data. In an alternate implementation, the directory entry value is a pointer to the associated cache entry, rather than an index. The directory exists to accomplish fast lookup of cache entries. The directory can be implemented using any of several types of data structure, as long as it has O(1) average-case lookup time. For instance, the directory can be implemented using an array (allowing O(1) worst-case lookup time), or as a hash-table, or as a balanced binary tree.
The size of the directory is not dependent on the size of the cache, but it must be equal to or greater than the cache size. The decoupling of the directory size from the cache size allows for an unlimited in size key set when the directory is implemented as an array (it is limited only by available memory for storing the directory array). This decoupling also allows the directory to be tuned for perf...