Designing LRU Cache


2.4k words • 14 min read
system-design › lld
, , ,

Introduction

Can you design a cache and use the Least Recently Used policy for key eviction for a fixed size cache?

This question is pretty famous now a days for the interviewers. This was asked in the second round for the SDE 3 roles in one of the prominent travel companies of India. Though this was not the first question this was the last questions or precisely the alternative question for the BST question which I was struggling to solve.

Let’s try to design this cache step by step.

Caching

What is caching anyways?

Caching is an important pattern for various systems to improve latency. When we have a system that needs to respond as quickly as possible we deploy a layer of caching in such systems. Caching should be in memory to have the minimum latency possible. The data in the cache is always stored in the RAM.

You must be aware of REDIS as the most popular dedicated caching database.

Considerations

Designing cache requires us to add a few important constraints to the design. Let’s look explore them.

Fixed Size

When we plan to design cache, we need to limit the memory usages by assigning a fixed capacity to the cache. This helps us to restrict unlimited memory access and prevent OutOfMemory errors for the systems.

Eviction

Since the cache is limited, there’s a need to evict keys when the cache storage is full and new keys needs to be added. Proper eviction is important to maintain high cache hit rates and ensure that the most relevant data remains quickly accessible.

There are a few policies that are most commonly used:

  • Least Recently Used
  • Least Frequently Used
  • First In First Out
  • Time to Live (TTL Based)

We will cover the LRU policy and implement the same.

Constant Time Ops

The most important consideration for any caching system is ensuring that both storing new values and retrieving existing keys which are the operations can be done in constant time, regardless of the cache size. Constant time ensures high performance, especially in systems that handle large volumes of data or require real-time usages.

Implementation

Intuition

Before we directly jump to code let’s see the hints we already have:

  • Constant time
  • In-memory
  • Fixed Capacity

The above two things points out to the use of a HashTable. Hash table allows us average constant time get() and set(). The methods or the api for the cache will look like: 

1
void set(std::string key, int val)

The set() method will take a string key and an int value to store in the hash table.

1
int get(std::string key)

The get() method will take a string key and will return the int value stored against the key in the hash table. If the key is absent, we will return the negative INT_MAX value.

We will need a field to store the capacity of the cache. This will help us to check if the cache is already filled up when adding new keys.

Now let’s look at the initial class for the lru_cache. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <unordered_map>
#include <string>
#include <climits>


class lru_cache {
private: 
    size_t capacity;
    std::unordered_map<std::string, int> cache; 

public:
    lru_cache(size_t cap): capacity(cap) {}
};

In the code above, we have a field capacity to hold the limit of the cache. And we also have a hash table cache. Let’s also add the set and get methods as well.

Basic Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <unordered_map>
#include <string>
#include <climits>


class lru_cache {
private: 
    size_t capacity;
    std::unordered_map<std::string, int> cache; 

public:
    lru_cache(size_t cap): capacity(cap) {}

    int get(std::string key) {
        // find the key
        auto it = cache.find(key);

        // key is present 
        if (it != cache.end()) {
            return it->second;
        }

        // key is absent 
        return -INT_MAX;
    } 

    // allow adding keys in cache 
    void set(std::string key, int val) 
    {
        auto it = cache.find(key);

        if (it != cache.end()) {
            // key is already present
            // overwrite the keys 
            it->second = val;
        }
        // add new key 
        cache[key] = val;
    }
};

Until now we have a cache implementation that is using a HashTable. We are only setting and getting the value against that key.

Note: We have not still implemented the limit of the cache. Also right now we do not have any mechanism to understand that which key is the least frequently used.

Eviction Policy

Now when we will implement the fixed size cache we will need to check whether the cache is already full in the set call. if the cache is already full, and a new key is to be set we need to delete one of the existing keys to make space for the new incoming key.

Here’s where the eviction policies kick-in and help to decide which key to remove. For the Least Recently Used policy, we remove the key which is least used. And to recognize that we need another data structure which can keep track of the keys and help us identify the least recently used key.

Doubly Linked List

We will use a doubly linked list to track which keys are being used. When a key will be added, we will push the key to the front of the list. Also when a key is fetched, we will move it to the front from it’s current position.

Let’s examine the situations. 

1
2
3
DLL = [ ]
add (k1, v1), (k2, v2), (k3,v3)
DLL = [ k3 ] <-> [ k2 ] <-> [ k1 ]

Now if we try to get the key k2, we will move the key from second position to the front of the key. The list will become: 

1
2
get k2
DLL = [ k2 ] <-> [ k3 ] <-> [ k1 ]

The above demonstration of the list state tell us that we will need three operations from the list:

  • Insertion at the front: O(1)
  • Deletion from the back: O(1)
  • Deletion from the middle (when we have pointer to the node): O(1)

Since the time complexity for all the required operations are O(1) for a double linked list, the DLL is the best suited data structure for tracking the usages of the keys.

Final Implementation

Now we know that we will need to store the keys in the DLL, we need to update the class code to accommodate the list. Before that let’s also discuss on the point that how we can achieve the O(1) of deletion from middle of the DLL.

The deletion from DLL is O(1) only when we have the pointer to the node. To store the pointer to the node of the list (which holds the key), we need to tweak our HashTable as well. Our HashTable will not store the key and the pair of the value associated to the key and the pointer of the DLL node which holds the key for tracking. 

1
2
3
4
5
6
7
8
# The HashTable view 
[k1] -> (v1, &node1)
[k2] -> (v2, &node2)
[k3] -> (v3, &node3)
[k4] -> (v4, &node4)

# The DLL view 
DLL = [ k2 ] <-> [ k3 ] <-> [ k1 ] <-> [ k4 ]

Let’s re-implement the class with the new layout of the HashTable and the DLL for tracking the key usages. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <unordered_map>
#include<list>
#include <string>

class lru_cache 
{
private:
    size_t capacity;
    // cache will store string key - pair (int value, iterator of the key node from the list)
    std::unordered_map<
        std::string, 
        std::pair<
            int, std::list<std::string>::iterator
        >
    > cache;
    std::list<std::string> recently_used; 

public:
    lru_cache(size_t cap = 10) : capacity(cap) {}
}

The code may look bit uncommon but it is not difficult to understand. Let me cover a few basic things about the above C++11 code involving the std::unordered_map and std::list.

std::unordered_map

This is the new addition to the C++11 standard and it internally used a HashTable contrary to the HashMap which used the Red-Black tree and maintain order of the elements in increasing order.

The unordered_map does not maintain order. The find operation on the unordered_map returns an iterator. This iterator points to the pair which the hash table stores pair(K, V). A pair contains the first and second components which points to the key and the value respectively.

std::pair

C++ pair is a simple container holding two related values which are accessed using .first and .second. It is often used to return or store grouped data. Since we need to store the int value of the key and the iterator of the list (pointer to the node of the DLL), we are creating a pair like: 

1
std::pair<int, std::list<std::string>::iterator> val_pair;

We can ease the readability by defining a custom type like: 

1
2
3
4
using ListNodeAddr = std::list<std::string>::iterator;

// creating the pair now will look like: 
std::pair<int, ListNodeAddr> val_pair;

std::list

A C++ list is a doubly linked list container with fast O(1) insertion and deletion anywhere using iterators. We are using std:list to keep track of the recently used keys. When we will need to evict a key we can simply delete the last node of the list because it will be the least used key. We will also delete that key from the HashTable.

Get()

The get method will do two things.

  • Check if the key exists and return -INT_MAX if not found
  • If found, return the value and also move the key to the front of the list (used for monitoring the use of keys)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// minor update : use the string by constant reference to avoid copy 
int get(const std::string &key) 
{
    // check if key is present 
    auto it = cache.find(key);

    // key is not present
    if (it == cache.end()) return -INT_MAX;

    // delete the key from the list using the pointer (iterator)
    recently_used.erase(it->second.second);
    // add the key to front of the list as it was accessed
    recently_used.push_front(key);

    // update the iterator in the cache 
    it->second.second = recently_used.begin();

    // return the value 
    return it->second.first;
}

Set()

Generally what are the possibilities when we will try to add a new key? They key might not present, the key might be present or the cache is full. So our set method handles three cases:

  • Check if the key already present and overwrite the value
  • Check if the cache is not full, if full then evict the lru key
  • Add a new key

Note: The order is important! Let me explain.

Suppose we set the size of the cache to 3. And we will add these: (k1, v1), (k2, v2), (k3, v3), (k1, vx). Did you notice that at the end we are not adding new key but just the same key wil new value. If we are checking if cache if full instead of key already present then we will uselessly evict a key which is not required. (I did not cover this case in the interview 🤕).

Let’s look at the code. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
size_t set(const std::string &key, int val) 
{
    // if key is already present 
    auto it = cache.find(key);

    if (it != cache.end()) {
        // remove it from the list 
        recently_used.erase(it->second.second); 
        recently_used.push_front(key);
        cache[key] = {val, recently_used.begin()};

        return cache.size();
    }

    // check if cache is full
    if (cache.size() == capacity) {
        // evict the least recently used 
        // get the key 
        std::string lru_key = recently_used.back();

        // least recently used key is at the end of the list 
        recently_used.pop_back(); 
        // remove from the cache 
        cache.erase(lru_key);
    }


    recently_used.push_front(key);
    cache[key] = {val, recently_used.begin()};

    // return cache current size 
    return cache.size();
}

Full Code

Now that we have covered the implementation in parts and understood the reason for the implementations, let’s look at the full code. Here’s the final code for the lru_cache. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <unordered_map>
#include<list>
#include <string>

class lru_cache {
private:
    size_t capacity;
    // cache will store string key - pair (int value, iterator of the key node from the list)
    std::unordered_map<
        std::string, 
        std::pair<
            int, std::list<std::string>::iterator
        >
    > cache;
    std::list<std::string> recently_used; 

public:
    lru_cache(size_t cap = 10) : capacity(cap) {}

    int get(const std::string &key) 
    {
        // check if key is present 
        auto it = cache.find(key);

        // key is not present
        if (it == cache.end()) return -INT_MAX;

        // delete the key from the list using the pointer (iterator)
        recently_used.erase(it->second.second);
        // add the key to front of the list as it was accessed
        recently_used.push_front(key);

        // update the iterator in the cache 
        it->second.second = recently_used.begin();

        // return the value 
        return it->second.first;
    }

    size_t set(const std::string &key, int val) 
    {
        // if key is already present 
        auto it = cache.find(key);

        if (it != cache.end()) {
            // remove it from the list 
            recently_used.erase(it->second.second); 
            recently_used.push_front(key);
            cache[key] = {val, recently_used.begin()};

            return cache.size();
        }

        // check if cache is full
        if (cache.size() == capacity) {
            // evict the least recently used 
            // get the key 
            std::string lru_key = recently_used.back();

            // least recently used key is at the end of the list 
            recently_used.pop_back(); 
            // remove from the cache 
            cache.erase(lru_key);
        }


        recently_used.push_front(key);
        cache[key] = {val, recently_used.begin()};

        // return cache current size 
        return cache.size();
    }
};

Reflections

Now we have walked through the solution step by step I can reflect to my mistakes more clearly and for most of us they are the silly mistakes actually. For me for this question I made the following mistakes:

  • Choosing a Singly Linked List which made the removal from the middle a O(n) operation.
  • Not maintaining the order of the set method that I have already highlighted.

You can find the implementation on GitHub as well.

I hope you enjoyed this writing, I wish to share more such experiences, thank you for reading until the end.