Design an LRU Cache
What is Caching ?
Caching is an optimization technique that we can use in your applications to keep recent or often-used data in memory locations that are faster or computationally cheaper to access than their source.
Caching Strategies
As indicated a cache is a placeholder for recently access data in memory. This place-holder is finite hence we would need mechanisms to efficiently use this finite place holder in memory. These mechanisms are normally referred to as caching strategies in computer literature.
There are several different strategies that we can use. The strategies differ on how they evict items from the cache and keep it from growing past a predefined threshold.
Understanding LRU
In this article we will focus on LRU cache and understanding how a cache is implemented gives us a better sense of how system design concepts are implemented in the backend.
The Least Recently Used (LRU) cache is a popular caching strategy that discards the least recently used items first to make room for new elements when the cache is full. It organizes the items in order of their use, so that identifying items that have been used the least becomes easy.
LRU Design considerations
With that in mind lets proceed on designing an Least Recently Used (LRU) cache with the following capabilities:
- Cache needs to be initialized with a specified capacity.
- A
getmethod which returns the value of a specific key if exists otherwise-1. - A
putmethod that updates the value of a key if it exists or adds a new one. This also needs to take into account evicting items when cache is full.
The above cache also has to abide by the following constraints since we are designing a data structure that will help applications make efficient and fast access to data.
- Accessing any item should be
O(1). - Time required to get recently used element should be
O(1). - Time required to put any element should be
O(1). - Space required should be
O(n).
LRU Behaviour
Before we dive in with the implementation, lets look at the LRU behaviour with a simple example.
We start off with a simple array in memory (LRU cache) with 3 elements . Here 3 is the capacity of our LRU cache.
The top of the stack/array by default points to the Most Recently Used (MRU) element while the bottom of the stack points to the Least Recently Used (LRU) element.
Now lets add an element M1 into our cache. This is how our cache looks like after adding the first element.
Similarly lets add two more elements M2 and M3 respectively into our cache. This is how our cache looks like after adding the then.
As you can see everytime we add an element to our cache the element that gets added most recently becomes the MRU while the first element gradually becomes the LRU.
Now lets access the element M2 and see how our cache pointers change.
Since M2 was accessed, it now becomes the MRU and M3 is now pushed down the stack .
Now lets see what happens when we try to insert a new element M4 to our example cache.
At this point , since the cache is full, we need to discard the Least Recently Used (LRU) element from the cache. In this case M1 is the LRU element, and the remaining elements are then pushed down the stack.
Solution Design
To implement an LRU cache we make use of 2 data structures
- Doubly Linked List
- HashMap/Dictionary
The Doubly Linked List allows us to store element in specific order with least recently used element at bottom. The double links allow us to move any element to the top in constant time (unlike a normal list/array/slice).
However accessing an element would still take O(n) time . That's why we use a HashMap to store to map the elements to the nodes of the double linked list.
While doing an insert we insert the element in the head of the list and record it in the hashmap. If element is found, we move the node to the head of the list .
When the list is full we discard the tail and update the corresponding hashmap entry as well.
Implementation
With the above information in hand, lets attempt to try and implement the LRU Cache using python. We will be using OrderedDict which is a data type available from collections class of Python. This was implemented initially in Python and then written in C. Both implementations use a HashMap and a Double Linked List.
The get method above checks for existence of the key. If it does (cache hit) it moves the key to the end of the list, otherwise it returns -1 .
The put method adds/updates a key in the hashMap and then moves the key to the end of the list. In case the capacity is exceeded at this point , it removes an item from the top of the list which will always have the least recently used element .
Lets walk through a sample test case where the input is sample student codes.
Input
(34,"John")
(43,"Mary")
(23,"Jack")
(67,"Jill")
(54,"Peter")
Output after cache is populated with capacity 5 :-
OrderedDict({34: 'John', 43: 'Mary', 23: 'Jack', 67: 'Jill', 54: 'Peter'})
Most Recently Used (MRU) - (54,"Peter")
Least Recently Used (LRU) - (34,"John")
Output after key 23 is fetched (cache hit) :-
OrderedDict({34: 'John', 43: 'Mary', 67: 'Jill', 54: 'Peter', 23: 'Jack'})
Most Recently Used (MRU) - (23,"Jack")
Least Recently Used (LRU) - (34,"John")
Output after key 99 is fetched (cache miss) :-
OrderedDict({34: 'John', 43: 'Mary', 67: 'Jill', 54: 'Peter', 23: 'Jack'})
Most Recently Used (MRU) - (23,"Jack")
Least Recently Used (LRU) - (34,"John")
Output after key 77 is added :-
OrderedDict({43: 'Mary', 67: 'Jill', 54: 'Peter', 23: 'Jack', 77: 'Abby'})
Most Recently Used (MRU) - (77,"Abby")
Least Recently Used (LRU) - (43,"Mary")
The previous LRU item was discarded since cache capacity was reached
and now we have a new LRU item. The LRU cache can also be implemented without using OrderedDict . You can re-implement above in Python. However Ordered dict performance is better as its highly optimized since it can interface with C python as well.
References
