LFU Eviction Scheme with O(1) time complexity.
Caches are almost everywhere in the systems we use, speeding up the performance of these systems under the hood. And these caches can implement different eviction schemes such as MRU(Most Recently Used), MFU(Most Frequently Used), LRU(Least Frequently Used), LFU(Least Frequently Used), and each of them has its time and place. Although LRU is the most used one because it affords a time complexity of O(1) for all operations(insert, lookup, delete).
But in many situations, LFU can be a better alternative, say for cases where the size of the cache is small yet the cache keeps getting a continuous stream of one entity repeatedly, followed by other hits of other entities briefly. Here the caches that implement LRU will ignore the potential need for the entity that has more continuous hits. But since LFU is O(logn), an LRU is preferred. But this article is not about making a case for LFU, but rather talks about how we can implement LFU eviction in O(1) time.
Operations supported by LFU:
The main operations that a cache must support are -
- Set (insert) an item into the cache
- Retrieve (lookup) an item from the cache
- Evict (remove) an item from the cache
The following are the time complexities for an LFU for the above operations -
- Insert — O(logn)
- Lookup — O(logn)
- Delete — O(logn)
The time complexity of the LFU cache hinges on the data structures it uses for the caches — Binomial heap and Hash table. Since all operations on a collision-free hash table are of constant time, the time complexity depends mainly on the heap. Hence the following implementation suggests the use of Doubly Linked Lists.
Proposed Algorithm:
Here the use of two doubly linked lists is proposed. One is to maintain a list of frequencies of the entities, and the other to maintain the list of entities corresponding to a frequency. Hash table also used for retrieving the entities with a key.
In the above illustration, each block with a number represents a frequency, and each frequency node has its own list of entities having that same access frequency, called node list.
The following is the pesudo-code for creating an LFU. It starts with an empty hash map and an empty frequency list. Whenever an element is added, an entry is created in the hashmap which points to the new element with its key. Hence the no of elements in the lists and the no of entries in the hashmap are the same.
Then a new node is added to the frequency list with value — 1. This new element will now be set to point to the frequency node 1. The run time complexity of this is O(1).
If the element is accessed again, it sees if the next frequency node exists, and if does checks if it differs by 1. If so, it will be changed to point to the next node, else a new node is created in between with the relevant frequency number, and the element will be made to point to it. This again is a complexity of O(1), that is of access.
For deletion, any element from the least frequency node is chosen and deleted, and if all the elements from a node are deleted, then the frequency node also is deleted. Hence deletion time is also of order O(1).
Hence a runtime complexity of O(1) is achieved overall.
This article is based on this paper by Shah, Mitra, and Matani. Thanks for reading.
