Least Frequently Used (LFU) Cache - Design and Implementation

On how LFU works and how to implement an optimal solution.

What is LFU Cache?

The basic principle of LFU caching is to remove the least frequently used items first when the cache reaches its capacity limit. This means that the cache keeps track of the frequency with which each item is accessed, and when it needs to make space for a new item, it removes the item that has been accessed the least frequently.

LFU Cache Design

To implement a Least Frequently Used (LFU) cache solution we need to design a data structure that would support the following operations:

• LFUCache(int capacity) - initialises the object with the capacity of the data structure.

• int get(int key) - gets the value of the key if the key exists in the cache. Otherwise, returns -1.

• void put(int key, int value) - updates the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

The frequency for a key is incremented whenever a get or a put operation is called on the element.

Let’s run through an example to better understand how this would work:

1. Let’s say we have a cache with a capacity of 2 LFU(2) and we call put(1,1)
→ Our LFU will become {1,1,1} as we add the key 1 with value 1 which currently has a frequency of 1

2. Then we call put(2,2) → Our LFU will become {2,2,1},{1,1,1}. We added a new element with key 2 and value 2 which currently has a frequency of 1. Since elements with key 1 and 2 have the same frequency of 1, we add the most recently used element (the one with key 2) to the front of the list.

3. Then we call get(1). Our LFU will return 1 and the new LFU will be {1,1,2}, {2,2,1}. This is because we increase the frequency of element with key 2 to 2 (due to the read operation) and we move it to the front of the list because it has higher frequency than the other element.

4. Then we call put(3, 3). Our LFU will become {1,1,2}, {3,3,1}. A new element comes in but our cache is at full capacity so we need to remove an element. We remove from the end of the list (as this is where the element with the least frequency and least recency is stored), so {2,2,1} gets removed. We then add the new element with a frequency of 1, {3,3,1}.

5. We call get(2). We return -1 as the element no longer exists in the cache.

6. We call get(3). We return 3 and the LFU becomes {3,3,2}, {1,1,2}. We increase the frequency of 3 and move it before key 1 as even though they have the same frequency, key 3 has been accessed more recently.

7. We call put(4,4). The LFU becomes {3,3,2}, {4,4,1}. New element comes in, cache is full, we remove the last element with key 1 and add the new element with key 4.

8. We call get(1). We return -1 as element is no longer present in the cache.

9. We call get(3). We return 3 and our LFU becomes {3,3,3}, {4,4,1}. The read operation increases the frequency of element at key 3 to 3.

10. We call get(4). We return 4 and our LFU becomes {3,3,3}, {4,4,2}.

Possible Implementations

• Using a brute force approach, we could have an array with the size of the cache. Each element in the array would store the item along with its frequency and last access time. When we get an element, we’d have to iterate through the array to find our element and update the item with the incremented frequency value. This means getting an element would be on average O(n). To put an item when the cache is full, we’d have to look for an item to evict. So we’ll iterate through the whole array and look for the item with the least frequency and oldest access time. This would take O(n).

• Using a min-heap data structure would be an improvement - each node will hold the cached element along with its frequency. This makes it easy to remove an element when the cache is full as the least recently and frequently used element will be a the top. The problem comes when inserting or reading from the cache, as any operation will mean the min-heap will need to be rebalanced which will take O(logn).

Solution in constant time

To implement an LFU that uses constant time for pushing and getting items, we’re going to need 2 data structures: a key map and a frequency map.

• Key Map - stores the key of the item and the item node containing the key, value and frequency.

Code available on gist

• Frequency Map - stores the frequency as key and a doubly linked list of all the cached items having that frequency as value. The items in the doubly linked list are sorted by recency such that most recently accessed items will be at the head of the list and the least recently used at the tail. Due to the nature of the doubly linked list, removing, adding and updating a cached item will take O(1).

Code available on gist

Given those two data structures, the cache operations would have the following logic:

• get operation for an item X:

  • check that X is in our key map. If it doesn’t exist return -1. Otherwise get the frequency from the value node.

  • for the frequency we’ve obtained above, get the doubly linked list from the frequency map. Delete the node from the doubly linked list. Create a new node with the incremented frequency and added it to the frequency map at the head of the doubly linked list.

    
    Following the above instructions, the implementation for the get operation should look similar to this:

Code available on gist

• put operation for an item X:

  • if the item already exists in the cache, it returns the node and updates the frequency (hence, we call getNode which does all of these)

  • if the item doesn’t exist in the cache:

    • if the cache is full - we remove the least recently and frequency used item, which should be the tail of the doubly linked list value in the frequency map with the minimum frequency.

    • then we add the item at the head of the doubly linked list with has the frequency of 1

    
    Considering the above, the implementation for the put operation would look like:

Code available on gist

Putting everything together, the code should look like this.

Conclusion

In this article we had a look on how we would go about implementing an LFU.

To learn more about caching, have a look at the following articles:

• Mastering Cache Management: Eviction, Invalidation, and Optimal Data Access Strategies

Or stay tuned as in the upcoming articles, we'll dive deeper into:

• Types of Caches: Exploring different caching mechanisms like in-memory, distributed, and CDN caching.

• Deployment Strategies: Understanding how to integrate caching into your architecture.

• Metrics: How to monitor cache performance for optimal results.

• Implementation Solutions: Practical examples with popular caching tools and libraries.