LRU Cache
Last updated
Last updated
Sun-Li BeatteayFollowJan 4 · 8 min readLRU cache (Image Credit: https://corvostore.github.io/#LRU)
Note: All the code in this article can be found on GitHub.
When I was interviewing for my first software engineering job, I was asked about least recently used (LRU) caches a number of times. I was asked to both code them and to describe how they’re used in larger systems. And if you’ve done your fair share of coding interviews, it’s likely you have, too.
From an interviewer's perspective, caching makes for a versatile topic. It can be used to gauge someone’s low-level understanding of data structures and algorithms. It can also be turned around to challenge one’s high-level comprehension of distributed systems.
For job candidates, however, it can be a jarring experience — especially if you’ve never used them in a professional setting. That was the case for me. The first time I was asked about LRU caches, my mind went blank. I’d heard of them, sure. But in all my studying of binary trees and heaps, I hadn’t bothered to learn what goes into them. And live in front of an interviewer isn’t the ideal setting to try to work it out.
While I didn’t do too well in that interview, that doesn’t have to be your fate. In this article, I’m going to teach you the what and how of LRU caches. By the end, you will know how to implement your own cache in less than 100 lines of code without any third-party libraries — all within ten minutes.
So let’s get going — time is ticking.
Caches are a type of data storage device that typically stores data in memory for fast retrieval. They are generally implemented as a key-value store, meaning you store and access the data via an identifying key of some sort.
The RAM on your computer is an example of a cache. The operating system stores data in RAM for faster access than the hard drive, and it uses the address of the memory cell as the key.Operating system caches (Image Credit: https://www.sciencedirect.com)
LRU caches are a specific type of cache with a unique feature. When an LRU cache runs out of space and needs to remove data, it will evict the key-value pair that was least recently fetched from the cache.
Popular open source examples of LRU caches are Redis and Memcached.
For tech businesses that provide an API or user interface, performance and availability are crucial. Think about the last time you visited a slow website. Did you stay and wait for it to load, or did you leave and visit another site? Most likely the latter. Slow or under-performing websites can result in millions in lost revenue.
Unfortunately, many of the same systems that rely on high uptime also have to store mountains of data. This is often the case for social media and e-commerce sites. These sites store their data in a database of some sort, be it SQL or NoSQL. While this is standard practice, the problem comes when you need to fetch that data. Querying databases, especially when they contain a lot of data, can be quite slow.
Enter the cache.
The next time an interviewer asks you how to optimize an API endpoint or workflow that requires fetching the same data over and over, caching is a good place to start.
However, knowing how caches work and how to use them is easy. Knowing how to build one yourself is the hard part. And that’s exactly what we’ll be focusing on.
For the purposes of this article, I will be using Python to implement the LRU cache. It’s succinct, easy to read, and a lot of people know it. However, if Python isn’t your thing or you’re curious about how to implement it in other languages, you can check out my examples repository.
Before we start building our cache, we have to understand what the requirements are. The first will be the API. Which methods do we need to implement?
While production quality caches are feature rich, we’ll keep it simple. You’ll only need to create two methods:
get(key)
set(key, value)
But that isn’t all. The LRU cache itself has a number of requirements:
When the max size of the cache is reached, remove the least recently used key.
Whenever a key is fetched or updated, it becomes the most recently used.
Both get and set operations must complete in O(1) time complexity (meaning that no matter how large the cache is, it takes the same amount of time to complete).
When fetching a key that doesn’t exist, return a null value.
The first question that we need to answer is, which data structure should back our LRU cache? After all, a cache is not a data structure itself.
Since the cache uses get and set and needs to operate in O(1) time, you might’ve thought of a hash map or dictionary. That would indeed fulfill some requirements. But what about removing the LRU key? A dictionary doesn’t allow us to know which is the oldest key.
We could use a time stamp as part of the dictionary value and update it whenever the key is fetched. This would tell us which key-value pair is the oldest. The problem is, we would need to loop through all the dictionary entries to check which is the oldest — breaking our O(1) requirement.
So what’s the answer?
This is where I should let you in on a secret. We’re actually going to need two data structures: one for fetching the values (dictionary/hash map) and one for keeping the items sorted by frequency of use.
So what should the second data structure be? If you thought of an array, you’re getting close.
We can use an array to keep the items sorted. And each key in the dictionary can reference the index of a value in the array. Whenever a key is fetched, we can move that value to the front of the array, pushing the rest of the items back, and update the index in the dictionary.
But we are close. We just need a data structure with the same sorting benefits of an array that can also get, set, and delete data in O(1) time. And the data structure that fits all of those requirements is a doubly linked list (DLL).
Now that we know the data structure makeup of our LRU cache, we can start building it!
Looking at this code, you may assume that we’re done. But there’s a catch. Did you notice the DoublyLinkedList on Line 6? Python doesn’t come with a DoublyLinkedList in the standard library.
In fact, the majority of programming languages don’t come equipped with a DLL. And since live coding challenges rarely let you use third-party libraries, we will have to implement it ourselves.
While linked lists usually come with many convenience methods, we only need to implement a small subset of them:
move_front(node)
unshift(value)
remove_tail
Whenever a key is fetched from our cache, we will need to make that key the most recently used. This involves moving that key to the front of the DLL.
The unshift method for a DLL works very similarly to an array where we insert a value at the front or head of the list. Our LRU cache will use this method whenever set(key, value) is called.
When we combine our LRU cache and DLL, this is what we get:
And just like that, 10 minutes later, we’ve created a basic LRU cache in less than 100 lines of code. For extra practice, you can try adding the ability to delete a key, creating simple unit tests to prove it works, or creating it in a different language.
As I mentioned before, if Python isn’t your thing, don’t worry. I have more examples for JavaScript, Ruby, and Go. I’m also open to pull requests for other languages.
Since caches keep data in memory, they are much more performant than traditional databases. And for social media sites, where 20% of the most popular content drives 80% of the traffic, caching can dramatically decrease the load on the databases.SQL vs. cache speed comparison (Image Credit: https://dzone.com/articles/redis-vs-mysql-benchmarks)
With these requirements in mind, we can get to work.Photo by ConvertKit on Unsplash
However, there’s still a small issue. Under the hood, arrays are a continuous row of data cells. If we need to move values to the front of the array and push the rest down, that operation will get slower as the array increases in size. In other words, inserting items at the beginning of an array takes O(N) time.Image Credit: Author
A doubly linked list is the same as a linked list, except each node in the list has an additional reference to the previous node as well as the next node.Image Credit: https://medium.com/flawless-app-stories/doubly-linked-lists-swift-4-ae3cf8a5b975
Each key in the dictionary will reference a node in our linked list. This way, we’ll be able to easily fetch data, as well as update and delete it.Image Credit: https://corvostore.github.io/#LRU
When it comes to crafting a DLL, the most important aspect is the design. There are many different types of linked lists with different tradeoffs, but for our use cases, we’ll be making a circular DLL. This will give us quick access to the head and tail, which is important for an LRU cache.Circular doubly linked list w/ root node (Image Credit: Author)
Implementing move_front can be a bit confusing as it involves both removing a node from the list and inserting it in a different location. We do this by changing and swapping the next and prev on a number of surrounding nodes.Move Front animation (Image Credit: Author)
Luckily for us, unshift shares a lot of logic with move_front. If we update move_front slightly, we can use it to implement unshift.Unshift animation (Image Credit: https://visualgo.net)
If our cache reaches its max size, we will need to remove the least recently used key. This involves removing the tail of our DLL. Similar to unshift, remove_tail shares some common logic with move_front. While we can’t reuse move_front for remove_tail, we can abstract some of the common logic.Remove Tail animation (Image Credit: https://visualgo.net)
