什么是 LRU 缓存算法？
什么是缓存 (Cache)？
缓存是一种用于存储经常访问的数据或指令的位置，以便通过减少大量昂贵的操作来加快访问速度。它允许处理器更快地访问数据和指令，从而大大提高系统的性能。
CPU Cache CPU 缓存是一种小容量的的高速内存，它通常集成在 CPU 芯片上，所以 CPU 可以更快地访问其存储的数据，其通常用于存储 CPU 下次可能使用到的数据和指令。
工作原理 当 CPU 需要访问数据或指令时，首先会检查其缓存。
如果数据或指令在缓存中，CPU 则快速访问它们。
如果数据或指令不在缓存中，处理器检查是否在内存中，并将数据副本存储在缓存中以供将来使用。
LRU 是什么？
LRU 是 “Least Recently Used” 的缩写。
LRU Cache 是一种常见的缓存替换算法，它的设计目的是在缓存容量满了时自动删除最近最少使用(最久时间前使用的)的项。
LRU 缓存的思想是将最近使用的项存储在缓存中，以便程序在需要时可以快速访问它们。
当缓存容量达到时，最近最少使用的项将从缓存中删除，以便为新项腾出空间。这确保了最近使用的项始终可用于缓存。
LRU 缓存在查询大量存储数据时非常有用的，它可以有效的保持最常使用的项目在缓存中，以便程序可以快速访问。通常用于 Web 浏览器，操作系统和数据库系统中，以提高性能。
接口设计
class LRUCache {
public:
LRUCache(int capacity);
int get(int key);
void put(int key, int value);
};
数据结构设计
LRU Cache 通常使用双向链表和哈希表来实现。
- 双向链表用于存储键值对。
- 哈希表用于存储键和双向链表的迭代器。
双向链表的头部是最近使用的项，尾部是最久时间前使用的项。
当访问一个项时，它将被移动到链表的头部。
当缓存达到其容量时，链表的尾部项将被删除。
C++ 实现
// 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
}
潜在问题
1.预读失败
预读失败的情况是，预读的数据从插入到缓存中直到被移除，都从未被访问。
这意味着预读是无效的，同时为了存储这些无用的预读数据，还会将潜在的热数据移除。
在上面的例子中，预读只在数据顺序访问时提高命中率。
2.缓存污染
缓存污染的情况是，缓存中的热数据被不经常访问的数据污染。
在上面的例子中，缓存区被大量随机访问的数据污染。
在这种情况下，缓存的命中率会大大降低。
解决方案
1.预读失败 下面的解决方法可以解决预读失败的问题：
- 使用分开的缓存列表来管理 预读数据 和 最近最少使用 的数据。
例如
- 在 Linux 系统中: 分别使用 active list 和 inactive list 来管理的缓存的数据。
- 在 MySQL Innodb 系统中: 分别使用容量大小不同的 young 区域 和 old 区域来管理缓存的数据.
上面两中解决方案的思想是将数据分为热数据和冷数据，然后分别使用 LRU 算法来管理。
2.缓存污染 下面的解决方法可以解决缓存污染的问题：
- 给 cache node 增加计数器，然后使用计数器来确定热数据和冷数据。
- 给 cache node 增加时间戳，然后使用时间戳来确定热数据和冷数据。
例如
- 在 Linux 系统中: 只有当计数器大于某个阈值时（通常是 2），才将数据从 inactive list 移动到 active list.
- 在 MySQL Innodb 系统中: 只有当时间戳和计数器大于某个阈值时，才将数据从 young list 移动到 old list.
上面两种解决方案的思想是增加阈值，使得冷数据更难被移动到热数据列表中。以此使得热数据更容易被保留在热数据列表中，从而避免缓存污染。
总结
在这篇文章中，我们介绍了 LRU 缓存替换算法，并且用 C++ 实现了它。
在嵌入式系统中，LRU 缓存替换算法是一种常见且常用的缓存替换算法。
同时他也是 LeetCode 上的一道题目，可以在 LeetCode - 146. LRU Cache 中找到。
但是，LRU 缓存替换算法也有一些潜在的问题，我们在文章中介绍了这些潜在的问题和解决方案。
最后，如何选择缓存替换算法是一个权衡性能和成本的问题。同时，它也取决于真实的应用场景。
没有万能的算法，只有适合的算法。
参考资料
Wikipedia - Cache replacement - LRU
最后修改于 2023-02-03
感谢您的支持 :D
