The LRU Cache Data Structure
This whole LRU thing sounds great in theory. But now we have to grapple with another issue: how do we track which items were least recently used?
In the previous walk-through of LRU, we looked back at past requests to see which ones were made recently and which ones hadn’t been made in a while. Now, that would mean that we’d have to somehow save our past requests somewhere. But if we save all our requests, we defeat the entire purpose of an eviction policy, which is to free up memory! It doesn’t help to evict items from the cache if we end up saving the same items somewhere else. A better approach is to somehow indicate within the cache itself which items were recently requested and which weren’t.
There are several ways this can be done, but one clever tactic is to keep the cached items sorted in the order of how recently used they were. For example, if we have the cache [1, 6, 4, 5], and we then have a cache hit with a request for the 4, we take the 4 and move it to the front (that is, the left end) of the cache. The cache would then be sorted as [4, 1, 6, 5].
And if the next request was for the 5, which is also a cache hit, the cache would become [5, 4, 1, 6]. With this approach, the order of the items tells us how recently each item was used. That is, the item at the front of the list was used most recently, while the item at the back (that is, the right end) of the list is the LRU item.
Okay, so now we’re getting somewhere. The question now is what data structure to use to implement this strategy. At the beginning of this chapter, we used a hash table to serve as our cache, and this was a sensible choice at the time. After all, with a hash table, we can read, write, and even evict in O(1) time. However, as discussed in Volume 1, Chapter 8, hash tables cannot store values in sorted order. So, if we want to keep the cache values sorted by their recent use, a hash table comes up short.
An array, on the other hand, is great for keeping items sorted. But an array isn’t a perfect solution either. This is because reading from the cache can take up to O(N) time because we’ll have to perform a linear search on the array to find any value. That’s way too slow for a cache; we ideally want to be able to read from the cache instantaneously. It turns out that no single classic data structure makes for a great LRU cache.
However, if we combine two data structures together, we can create an LRU cache whose time complexity is O(1) for all operations. Prepare to be amazed.
Data Structure Dynamic Duo
As I mentioned, a hash table is not capable of keeping values in any sorted order. However, we could consider using an array in conjunction with a hash table to keep track of the cache order. That is, we can store data in a hash table so we can access the data quickly, but we can also store a copy of that data in an array so we can track how recently it was used. Yes, we consume extra space by storing the same data twice over, but perhaps it’s worth it. Let’s see.
To analyze the efficiency of using an array and a hash table together, let’s be absolutely clear on what operations we want our data structures to perform. At a high level, there are three major operations:
-
Reading from the cache. Upon each and every request for data, we check whether the data already exists in the cache before bothering to fetch the data from an external source.
-
Managing a cache miss. We have to evict data to make room for the new data.
-
Managing a cache hit. We potentially have to update the order of the cache to indicate that the requested item is the most recently used.
Let’s analyze how we’d perform these operations with a hash-table-and-array combo cache, starting with reading from the cache.
Read Efficiency
Again, we’ll be performing our reads from the hash table since such reads happen in constant time. In fact, we don’t need to touch the array at all when executing our reads. And so, here’s the performance of our read operation:
| Read |
|---|---|
Hash Table | O(1) |
Cache Miss Efficiency
As we’ve seen, each time we read from the cache, we’ll encounter either a cache miss or a cache hit. When we have a cache miss, we need to perform two cache operations. That is, we first evict the LRU item from the cache. Second, we insert the new data into the cache.
Now, here’s the thing. Because we’re modifying cache data, we need to update both of our data structures, namely, the array and the hash table. Specifically, we’ll have to insert and delete data from each data structure. Fortunately, inserting and deleting from a hash table are each O(1) operations, so they’ll run at breakneck speed. However, let’s see how fast the array operations are.
First, we evict the last item of the array from the cache since we’re sorting items so that the last element is the LRU item. Second, we insert the data we receive from the external source at the front of the cache. Being that the current request is, by definition, the most recent one, we put its data at the front to indicate that it is the most recently used item.
Here’s a visual of these two cache operations:
Evicting the last item from an array takes O(1) time, but inserting at the front of the array takes O(N) time because we have to shift all the remaining values rightward. (This idea is covered in Volume 1, Chapter 1.)
Let’s jot down the time complexity of all the cache operations we’ve looked at so far:
| Read | Insert | Evict |
|---|---|---|---|
Hash Table | O(1) | O(1) | O(1) |
Array |
| O(N) | O(1) |
Incidentally, the fact that we decided that the most-recently-used item goes in the front of the array is arbitrary; we could have set things up in reverse. That is, we could alternatively put the most-recently-used item at the end while keeping the LRU item at the front. However, this doesn’t help us in any way because although inserting at the end will now take O(1) time, evicting from the front will now take O(N) time. That is, when we delete an item from the front of an array, we then have to shift all the remaining values leftward.
Cache Hit Efficiency
The final operation we need to analyze is managing a cache hit. With a cache hit, we don’t need to update the hash table in any way since we’re not evicting anything, nor are we inserting any new data.
However, we do have to update the array. That is, we need to make sure that the data we just accessed gets moved to the front of the array to indicate that it’s the most-recently-used data. This data might currently be anywhere in the array. It could be somewhere in the middle, or at the front, or at the end. If it’s anywhere but the front, we need to pluck it from its current spot and move it to the front:
Here’s how this breaks down in terms of time complexity. First, we have to find the requested data within the array before we can move it. This search can take up to O(N) steps. Second, we have to move this item to the front of the array, causing the other elements to shift positions. If, for example, we move the last element to the front, this causes N-1 shifts, making this move another O(N) operation.
In our analysis going forward, we’ll keep these “Find” and “Move to Front” operations separate as shown in the following table:
| Find | Move to Front |
|---|---|---|
Array | O(N) | O(N) |
Each operation has the potential to take O(N) time.
Complete Efficiency Analysis
Okay, we’ve completed our efficiency analysis. Here’s the complete table of the speed of our proposed hash-table-and-array-combo cache:
| Read | Insert | Evict | Find | Move to Front |
|---|---|---|---|---|---|
Hash Table | O(1) | O(1) | O(1) |
|
|
Array |
| O(N) | O(1) | O(N) | O(N) |
It’s hard to say whether this is “good” or “bad” since we don’t have any other solutions currently on the table. However, if we want to improve upon this approach, we need to find ways to reduce the time of one or more of these operations.
Currently, the room for improvement lies within most of the array-based operations. As mentioned, one issue is that we’re inserting and deleting from both ends of the array, but an array can only act fast on one end; the other end takes O(N) time. Is there another data structure that maintains order but can also quickly insert and delete data on either end?
Linked Lists to the Rescue
As discussed in Volume 1, Chapter 14, a classic linked list allows us to insert and delete data from the list’s head in O(1) time. While this seems promising, recall that linked lists insert and delete data from the tail in O(N) time. Ultimately, a classic linked list won’t serve us better than an array since we’re looking for a way to insert and delete quickly from both ends of the cache.
However, a doubly linked list can insert and delete data from both ends in constant time. Again, this is because we track both the head and tail of the list at all times and can thereby access both ends instantaneously.
Here’s a simple depiction of a doubly linked list serving as a cache:
Again, we’ll continue to read from the hash table rather than the doubly linked list since reading from a hash table is just O(1). Reading from the doubly linked list would take up to O(N) since we’d have to perform a linear search to find anything.
Let’s now take a look at the doubly linked list’s operations and their efficiency.
Linked List Cache Miss
When we encounter a cache miss, we can evict the tail in a single step because doubly linked lists always track the tail. We can now also insert a new item at the head of the list in one step because linked lists also track the head.
In the following diagram, we insert item 1 at the head and also evict item 6. To evict the 6, we set the 2’s “next” link to None (rather than the 6) and declare the 2 to be the list’s tail going forward.
Linked List Cache Hit
When we chance upon a cache hit, we still have to spend N steps to find the item we’re looking for, but when we do, moving it to the front can be done in O(1) time. Specifically, we remove the desired node by having its two adjacent nodes link to each other, which effectively disconnects the desired node from the list:
We then take that node and make it the head of the list:
Linked List Advantages
It turns out that using a linked list instead of an array significantly boosts the speed of our cache! (From here on, I’ll sometimes refer to the doubly linked list as simply the “linked list.”)
Here’s a summary of the time complexity of our current linked-list solution:
| Read | Insert | Evict | Find | Move to Front |
|---|---|---|---|---|---|
Hash Table | O(1) | O(1) | O(1) |
|
|
Doubly Linked List |
| O(1) | O(1) | O(N) | O(1) |
All of our cache operations occur in constant time except for finding cache data in the linked list when we have a cache hit, which takes up to N steps. However, with a clever trick, we can even get the “Find” operation down to constant time.
Point to the Node
Following is a high-level visual of what our cache system currently looks like, using products and their prices as sample data:
As you can see, we store the data in duplicate: one set in the hash table, and the other inside the linked list. Note that we don’t need to store the prices themselves in the linked list; we just need the list to tell us the recency of when each product was requested.
In the diagram, we listed the hash keys in the same order as the linked list to make the visualization easier to grasp. However, keep in mind that hash tables have no inherent order; we’re relying solely on the linked list to keep the cache data sorted.
Currently, finding data in the linked list during a cache hit takes O(N) time. But with one small but arguably mind-blowing adjustment, we can get this “Find” operation to run in constant time. And that is, instead of storing the raw data inside the hash table, we store the nodes of the linked list in the hash table instead. In other words, the keys of the hash table remain the same, but the values will no longer be integers; the values will be the very nodes of the linked list:
What an interesting data structure! Although the nodes are contained as values within the hash table, there’s no reason why the nodes cannot still link to each other and thereby form a linked list. Note that for convenience, we’re now also placing the price data inside the nodes themselves.
As with our previous cache implementations, we still begin every request by reading the hash table to check whether the requested data is currently in the cache. But now, each time we have a cache hit, we don’t have to search the linked list for that data. Instead, the hash table itself points the way directly to the appropriate node of the linked list since the node is the actual value in the hash table. And once we have that node in hand, we’ll move it to the head of the linked list.
With this modification, our LRU cache achieves O(1) speed for all of its operations:
| Read | Insert | Evict | Find | Move to Front |
|---|---|---|---|---|---|
Hash Table | O(1) | O(1) | O(1) |
|
|
Doubly Linked List |
| O(1) | O(1) | O(1) | O(1) |
I’ll highlight more of the nitty-gritty details of each of these operations in the code walk-through that follows.
Code Implementation: LRU Cache
To code up our LRU cache, we’ll need a doubly linked list, so let’s take a look at a doubly linked list implementation. This implementation differs slightly from the one demonstrated in Volume 1, Chapter 14 since now we’re focusing on the functionality needed to serve our cache.
We’ll start by looking at the code for the nodes themselves:
| | class Node: |
| | |
| | def __init__(self, data): |
| | self.data = data |
| | self.next_node = None |
| | self.previous_node = None |
| | |
| | if isinstance(data, dict): |
| | self.product = data.get("key") |
| | self.price = data.get("data") |
This node is a double-ended node, having links to both the next_node and previous_node. Additionally, I’ve added some custom product and price attributes for the sake of our product price-searching app.
I’ve saved this code in a file called double_ended_node.py, and now import it into the implementation of the doubly linked list. Here’s the doubly linked list code:
| | import double_ended_node |
| | |
| | |
| | class DoublyLinkedList: |
| | |
| | def __init__(self, first_node=None, last_node=None): |
| | self.first_node = first_node |
| | self.last_node = last_node |
| | |
| | def append(self, data): |
| | new_node = double_ended_node.Node(data) |
| | |
| | if not self.first_node: |
| | self.first_node = new_node |
| | self.last_node = new_node |
| | else: |
| | new_node.previous_node = self.last_node |
| | self.last_node.next_node = new_node |
| | self.last_node = new_node |
| | |
| | return new_node |
| | |
| | def insert_head(self, data): |
| | new_node = double_ended_node.Node(data) |
| | |
| | if not self.first_node: |
| | self.first_node = new_node |
| | self.last_node = new_node |
| | else: |
| | new_node.next_node = self.first_node |
| | self.first_node.previous_node = new_node |
| | self.first_node = new_node |
| | |
| | return new_node |
| | |
| | def pop_head(self): |
| | popped_node = self.first_node |
| | self.first_node = self.first_node.next_node |
| | self.first_node.previous_node = None |
| | return popped_node |
| | |
| | def pop_tail(self): |
| | popped_node = self.last_node |
| | self.last_node = self.last_node.previous_node |
| | self.last_node.next_node = None |
| | return popped_node |
| | |
| | def move_to_head(self, node): |
| | if node == self.first_node: |
| | return |
| | |
| | if node.next_node: |
| | node.previous_node.next_node = node.next_node |
| | node.next_node.previous_node = node.previous_node |
| | else: # node is the tail |
| | node.previous_node.next_node = None |
| | self.last_node = node.previous_node |
| | |
| | node.next_node = self.first_node |
| | node.next_node.previous_node = node |
| | node.previous_node = None |
| | self.first_node = node |
The append and pop_head methods were already present in the Volume 1 implementation, but we’ve added a few new methods to ensure that the linked list can function as part of an LRU cache.
The insert_head method is similar to the append method, except that insert_head inserts a new node at the beginning of the list, whereas append inserts at the end of the list. Similarly, the pop_tail method is similar to pop_head, except that pop_tail removes and returns the list’s tail rather than its head.
The move_to_head method, which moves a given node to the head of the list, contains a number of steps and may feel a bit like performing a surgical operation. The following image highlights the various links we need to add and remove if the node we’re moving is currently somewhere in the middle of the list.
Say that we have a list in which the nodes are A, B, C, and D. If we want to move C to the front of the list, we make the following moves:
-
Change B’s next_node to point to D.
-
Change D’s previous_node to point to B.
-
Change C’s next_node to point to A.
-
Change A’s previous_node to point to C. (Previously, A was the head and so its previous_node pointed to None.)
-
Set C’s previous_node to None since C will be the head.
-
Mark C as the official head of the linked list.
At the end of the day, our list will appear like this:
With our linked list in place, we can now introduce our LruCache implementation:
| | import doubly_linked_list |
| | import time |
| | |
| | |
| | class LruCache: |
| | |
| | def __init__(self): |
| | self.hash_table = {} |
| | self.linked_list = doubly_linked_list.DoublyLinkedList() |
| | self.max_size = 4 |
| | |
| | def read(self, key): |
| | if key in self.hash_table: # Cache hit |
| | return self.freshen(key) |
| | else: # Cache miss |
| | return None |
| | |
| | def freshen(self, key): |
| | node = self.hash_table.get(key) |
| | self.linked_list.move_to_head(node) |
| | return node |
| | |
| | def cache(self, key, data): |
| | # If cache is full: |
| | if len(self.hash_table) >= self.max_size: |
| | self.evict() |
| | |
| | # Save new data in both linked list and hash table: |
| | new_node = self.linked_list.insert_head({"key": key, "data": data}) |
| | self.hash_table[key] = new_node |
| | |
| | def evict(self): |
| | # LRU eviction policy: |
| | evicted_node = self.linked_list.pop_tail() |
| | del self.hash_table[evicted_node.data["key"]] |
| | |
| | class PriceRequester: |
| | |
| | def __init__(self): |
| | self.cache = LruCache() |
| | |
| | def request_price_for(self, product): |
| | data = self.cache.read(product) |
| | if data: # Cache hit |
| | price = data.price |
| | else: # Cache miss |
| | price = self.search_web_for(product) |
| | self.cache.cache(product, price) |
| | |
| | return price |
| | |
| | def search_web_for(self, product): |
| | # Mock data: |
| | price = 1 |
| | # Mimic time it takes to search web: |
| | time.sleep(0.25) |
| | |
| | return price |
Two classes are at play here. The more important class is the LruCache, which serves as a generic LRU cache. But we’ve also included a PriceRequester class as an example of an application that uses the cache. While I recommend that you glance at the PriceRequester code, for now, we’re going to only walk through the LruCache class itself. Let’s take it from the top.
We’ve saved our doubly linked list code in a file called doubly_linked_list.py, so our code imports that module. We also import the time module to mock a web request within the PriceRequester code as we did earlier in the chapter.
Let’s take a look at the constructor of the LruCache:
| | def __init__(self): |
| | self.hash_table = {} |
| | self.linked_list = doubly_linked_list.DoublyLinkedList() |
| | self.max_size = 4 |
Here, we create the cache’s hash table and doubly linked list. We also set the maximum number of cache items to be 4, but this can easily be changed to any other number.
The read method attempts to find an item from the cache by looking up the item in the hash table:
| | def read(self, key): |
| | if key in self.hash_table: |
| | return self.freshen(key) |
| | else: |
| | return None |
Reading from the cache yields either a cache hit or a cache miss.
Upon a cache hit, we call the freshen method, whose details I’ll walk through shortly. The primary purpose of the freshen method is to move the item’s corresponding linked-list node to the front of the list to indicate that this item is the most recently used item.
If we have a cache miss, though, we return None to indicate that the item is not presently in the cache. This means that our app will have to find the data from an external source like the web, after which it can cache that data.
Next up, we have the freshen method, which moves a given node to the head of the linked list and ends by returning that node:
| | def freshen(self, key): |
| | node = self.hash_table.get(key) |
| | self.linked_list.move_to_head(node) |
| | return node |
The next method in this class is the cache method, which stores data inside the cache:
| | def cache(self, key, data): |
| | if len(self.hash_table) >= self.max_size: |
| | self.evict() |
| | |
| | new_node = self.linked_list.insert_head({"key": key, "data": data}) |
| | self.hash_table[key] = new_node |
Before caching any new data, the cache method first checks to see if the cache is already full. This is determined based on the max_size attribute defined in the class’s constructor. If the cache is full, we evict an item from the cache. (I’ll cover the evict method shortly.)
To cache new data, we first create a new node and place it at the head of the linked list to indicate that it’s the most recently used item. Then, we add the item’s key to the hash table and set the value to be the node we created for the linked list.
The final method, evict, removes data from the cache according to the LRU eviction policy:
| | def evict(self): |
| | evicted_node = self.linked_list.pop_tail() |
| | del self.hash_table[evicted_node.data["key"]] |
We need to evict the data from both the linked list and the hash table. Since the LRU node is the tail of the list, that’s the node we delete.
To remove the corresponding key from the hash table, we take a look at what item our deleted node contains and look for that item’s key in our hash table. We then delete that key-value pair from the hash table.
