Introduction to LRU Cache

What is Cache?

Generally Definition The cache is way used to store frequently accessed data or instruction in a location for faster access by reducing the amount of expensive operators. it allows the processor to access data and instructions more quickly, which can greatly improve the performance of the system.

Special Example For example, the CPU cache is a small amount of fast memory that the CPU can access more quickly than the main memory. The CPU can access the cache faster than the main memory because the cache is located on the same chip as the CPU. The cache is used to store the data and instructions that the CPU is likely to use next.

Workflow of CPU Cache When the CPU needs to access data or instructions, it first checks the cache. If the data or instructions are in the cache, the CPU can access them quickly. If the data or instructions are not in the cache, the processor retrieves them from main memory and stores a copy in the cache for future use.

What is LRU Cache?

The LRU stand for “Least Recently Used”. It is a common cache replacement algorithm that is designed to automatically remove the least recently used items when it reaches its maximum capacity.

The idea behind LRU cache is to store the most recently used items in the cache, so that the program can access them quickly when needed. When the cache capacity is reached, the least recently used items are removed from the cache to make room for the new items. This ensures that the most recently used items are always available in the cache.

LRU Cache is useful in situations where there is limited space to store data and it is important to keep the most frequently used items quickly accessible. It is commonly used in web browsers, operating systems, and database systems to improve performance.

Interface Design

class LRUCache
{
public:
    LRUCache(int capacity);
    int get(const int &key);
    void put(const int &key, const int &value);
};

Data Structure

LRU Cache is often implemented by using a double linked list and a hash map.

The double linked list is used to store the key and value pair.
The hash map is used to store key and the iterator of the double linked list.

The head of the list is the most recently used item, and the tail of the list is the least recently used item.

When an item is accessed, it is moved to the head of the list.

When the cache reaches its capacity, the item at the tail of the list is removed from the cache.

C++ Implementation

// Using STL list and unordered_map
#include <list>
#include <random>
#include <iostream>
#include <unordered_map>

using namespace std;

class LRUCache
{
private:
    int capacity;                                           // capacity of the cache
    list<pair<int, int>> cache;                             // store the key and value pair
    unordered_map<int, list<pair<int, int>>::iterator> map; // store the key and the iterator of the list item

public:
    int MISS = 0;
    int HIT = 0;

    LRUCache(int capacity) : capacity(capacity) {}
    int get(const int &key)
    {
        // cout << "get " << key << endl;
        const auto it = map.find(key);
        // not found, return -1
        if (it == map.end())
        {
            MISS++;
            return -1;
        }
        // move the element to the front
        cache.splice(cache.begin(), cache, it->second);
        // return the value
        HIT++;
        return it->second->second;
    }
    void put(const int &key, const int &value)
    {
        const auto it = map.find(key);
        if (it != map.end())
        {
            // founded, update the value
            it->second->second = value;
            // move the element to the front
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // not found, insert the new element at the front
        // 1. check the capacity
        if (cache.size() == capacity)
        {
            // remove the last element
            const auto &last = cache.back();
            map.erase(last.first);
            cache.pop_back();
        }
        // 2. insert the new element at the front
        cache.emplace_front(key, value);
        map[key] = cache.begin();
    }

    void clear()
    {
        cache.clear();
        map.clear();
        HIT = 0;
        MISS = 0;
    }

    void print() const
    {
        for (const auto &p : cache)
        {
            cout << p.first << " " << p.second << endl;
        }
    }
};

int main()
{
    const int CAPACITY = 200;
    const int NUM = 1000;

    LRUCache cache(CAPACITY);

    // sequential access
    cout << "Sequential Access" << endl;
    cache.clear();
    for (int i = 0; i < NUM; ++i)
    {
        if (cache.get(i) == -1)
        {
            cache.put(i, i);
        }
    }
    cout << "HIT: " << cache.HIT << "\t\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;


    // sequential access with pre-fetch
    cout << "Sequential Access with Pre-Fetch" << endl;
    cache.clear();
    int size = 4; // pre-fetch size
    int key = 0;
    for (int i = 0; i < NUM; ++i)
    {
        if (cache.get(key) == -1)
        {
            for(int j = 0; j < size; ++j)
            {
                cache.put(key + j, key + j);
            }
        }
        key++;
        key = key % NUM;
    }

    cout << "HIT: " << cache.HIT << "\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    // random access
    cout << "Random Access" << endl;
    cache.clear();
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, NUM);
    for (int i = 0; i < NUM; ++i)
    {
        int key = dis(gen);
        if (cache.get(key) == -1)
        {
            cache.put(key,key);
        }
    }
    cout << "HIT: " << cache.HIT << "\tMISS: " << cache.MISS
            << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;


    // random access with pre-fetch
    cout << "Random Access with Pre-Fetch" << endl;
    cache.clear();
    size = 4; // pre-fetch size
    key = 0;
    for (int i = 0; i < NUM; ++i)
    {
        int key = dis(gen);
        if (cache.get(key) == -1)
        {
            for(int j = 0; j < size; ++j)
            {
                cache.put(key + j, key + j);
            }
        }
    }
    cout << "HIT: " << cache.HIT << "\tMISS: " << cache.MISS
         << "\t\tHit Rate: " << (double)cache.HIT / (cache.HIT + cache.MISS) << endl;

    return 0;

// Sequential Access
// HIT: 0          MISS: 1000              Hit Rate: 0
// Sequential Access with Pre-Fetch
// HIT: 750        MISS: 250               Hit Rate: 0.75
// Random Access
// HIT: 181        MISS: 819               Hit Rate: 0.181
// Random Access with Pre-Fetch
// HIT: 195        MISS: 805               Hit Rate: 0.195
}

Potential Issues

Pre-Fetch Failure The pre-fectch failure rasies when the pre-fetch data is never accessed until it is removed from the cache, which means the pre-fetching works was in vain, and it leads the potential hot data removed for storing the useless pre-fetch data. In the above example, the pre-fetching works only when the data is accessed sequentially.
Cache Pollution The cache pollution is a situation that the cache is polluted by the data that is not frequently accessed. In the above example, the cache is polluted by the random data. In that case, the cache is not effective for the frequently accessed data.

Solutions

1. Solution for Pre-Fetch Failure The pre-fetch failure can be solved by the following solutions:

Using sperate cache list for the pre-fetch data and the least recently used data.

For Example

Linux: active list and inactive list
MySQL Innodb: young list and old list.

Both of these two solutions have the same idea, which is to divide the data into cold data and hot data, and then use the LRU algorithm separately. Unlike the traditional LRU algorithm, all data are managed by only one LRU algorithm.

2. Solution for Cache Pollution The cache pollution can be solved by the following solutions:

Add a counter to the cache node, and then use the counter to determine the hot data and the cold data.
Add a timestamp to the cache node, and then use the timestamp to determine the hot data and the cold data.

For Example

Linux: Only when the counter is larger than a certain threshold, the data is moved to the active list from the inactive list.
MySQL Innodb: Only when the timestamp and counter are larger than a certain threshold, the item is moved to the young list from the old list.

The idea behind is increasing the threshold for data to be moved to the hot list, which means the cold data will be more difficult to move to the hot list. So, the hot data will be more likely keep in the hot list and prevent cache pollution.

Summary

In this article, we have introduced the LRU cache replacement policy and implemented it in C++. The LRU cache replacement policy is a very important cache replacement policy, and it is widely used in the real world.

However, the LRU cache replacement policy has some potential issues, and we have introduced the potential issues and potential solutions.

In the end, how to choose the cache replacement policy is a trade-off between the performance and the cost. Also, it really depends on the what kind of access pattern the application has.

There is no panacea.