Browse Prior Art Database

Method for LFU-LRU Cache Replacement Policy With Constant-Complexity

IP.com Disclosure Number: IPCOM000211159D
Publication Date: 2011-Sep-24

Publishing Venue

The IP.com Prior Art Database

Related Documents

Other References:
IPCOM000196714D - IP.COM IPCOM000199282D - IP.COM

Abstract

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.