What is the LRU Cache Algorithm?
What is a Cache?
A cache is a location used to store frequently accessed data or instructions, speeding up access by reducing the number of expensive operations. It allows a processor to access data and instructions more quickly, thereby greatly improving system performance.
CPU Cache A CPU cache is a small, high-speed memory typically integrated on the CPU chip, allowing the CPU to access its stored data faster. It is commonly used to store data and instructions the CPU might need next.
How It Works When the CPU needs to access data or instructions, it first checks its cache.
If the data or instructions are in the cache, the CPU accesses them quickly.
If the data or instructions are not in the cache, the processor checks if they are in memory and stores a copy of the data in the cache for future use.
What is LRU?
LRU stands for "Least Recently Used."
An LRU Cache is a common cache replacement algorithm designed to automatically delete the least recently used (the one used the longest time ago) item when the cache capacity is full.
The idea behind an LRU cache is to store recently used items in the cache so that the program can access them quickly when needed.
When the cache reaches its capacity, the least recently used item is removed from the cache to make room for new items. This ensures that the most recently used items are always available in the cache.
LRU caches are very useful when querying large amounts of stored data. They effectively keep the most frequently used items in the cache for fast program access. They are commonly used in web browsers, operating systems, and database systems to improve performance.
Interface Design
class LRUCache {
public:
LRUCache(int capacity);
int get(int key);
void put(int key, int value);
};
Data Structure Design
An LRU Cache is typically implemented using a doubly linked list and a hash table.
- The doubly linked list stores the key-value pairs.
- The hash table stores the keys and iterators to the nodes in the doubly linked list.
The head of the doubly linked list is the most recently used item, and the tail 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.
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; list<pair<int, int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> map;
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 Problems
1. Prefetch Failure
Prefetch failure occurs when prefetched data is never accessed from the time it is inserted into the cache until it is evicted.
This means the prefetch is ineffective, and storing this useless prefetched data may also evict potentially hot data.
In the example above, prefetch only improves the hit rate for sequential data access.
2. Cache Pollution
Cache pollution occurs when hot data in the cache is contaminated by infrequently accessed data.
In the example above, the cache is polluted by a large amount of randomly accessed data.
In this case, the cache hit rate drops significantly.
Solutions
1. Prefetch Failure The following solutions can address the prefetch failure problem:
- Use separate cache lists to manage prefetched data and least recently used data.
For example
- In Linux systems: Use an active list and an inactive list to manage cached data.
- In MySQL Innodb systems: Use a young area and an old area with different capacities to manage cached data.
The idea behind both solutions is to separate data into hot and cold data, then manage each with the LRU algorithm.
2. Cache Pollution The following solutions can address the cache pollution problem:
- Add a counter to cache nodes, then use the counter to identify hot and cold data.
- Add a timestamp to cache nodes, then use the timestamp to identify hot and cold data.
For example
- In Linux systems: Only move data from the inactive list to the active list when the counter exceeds a certain threshold (usually 2).
- In MySQL Innodb systems: Only move data from the young list to the old list when the timestamp and counter exceed a certain threshold.
The idea behind both solutions is to introduce a threshold, making it harder for cold data to move into the hot data list. This makes it easier to retain hot data in the hot data list, thereby avoiding cache pollution.
Summary
In this article, we introduced the LRU cache replacement algorithm and implemented it in C++.
In embedded systems, the LRU cache replacement algorithm is a common and frequently used cache replacement algorithm.
It is also a problem on LeetCode, which can be found at LeetCode - 146. LRU Cache.
However, the LRU cache replacement algorithm also has some potential problems, which we introduced along with their solutions in this article.
Finally, choosing a cache replacement algorithm is a matter of balancing performance and cost. It also depends on the actual application scenario.
There is no one-size-fits-all algorithm, only the algorithm that fits.