LRU (Least Recently Used)
算法思想
每次内存溢出时,把最长时间未被访问的数据置换出去。这种算法是完全从最近使用的时间角度去考虑的。
维护每个数据上一次被访问的 timestamp,每次移除 timestamp 最早的数据。
工作原理
我们需要实现 LRU
的 put 和 get 的 O(1) 复杂度操作 ——
需要的数据结构:list、unordered_map。
- list 链表使插入和删除操作的复杂度达到 O(1),list结点存储访问的数据。
- unordered_map 映射 key 到 list 结点,使查找的复杂度达到O(1)。
![image-20221120221005882](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20221120221005882.png)
执行过程:
- get 数据时从缓存中查找,若缓存(map)命中,则将数据从 list 中取出,并加入到 list 头部
- 若没有命中,则表明缓存穿透,后续需要从磁盘中获取要访问的数据加入缓存中
- 将数据加入缓存中时,若缓存满了,则淘汰 list 尾部的数据,然后在 list 头部加入新数据
存在的问题:
sequential flooding (顺序溢出) 造成缓存污染 —— 最近被访问的数据实际是最不可能需要的数据。
- 顺序读取所有数据,则缓存会被只读了一次之后再也不会读取的数据污染。即在某些特定的workload下,我们想移出的数据是那些最近被使用的,而不是最近最少被使用的。
代码实现
class LRUCache {
public:
LRUCache(int capacity) : cap(capacity), size(0) {}
int get(int key) {
if (map.find(key) == map.end()) return -1;
auto item = *map[key];
cache.erase(map[key]);
cache.push_front(item);
map[key] = cache.begin();
return item.second;
}
void put(int key, int value) {
if (map.find(key) == map.end()) {
if (size == cap) {
map.erase(cache.back().first);
cache.pop_back();
size--;
}
}
else {
cache.erase(map[key]);
size--;
}
cache.push_front({key, value});
map[key] = cache.begin();
size++;
}
private:
int cap;
int size;
list<pair<int, int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> map;
};
LRU-K
算法思想
LRU-K
中的 K 代表最近使用的次数,因此 LRU
可以认为是 LRU-1
。LRU-K
的主要目的是为了解决 LRU
算法仅访问一次就能替换造成的“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过 K 次”。
工作原理
相比 LRU
,LRU-K
需要多维护一个队列 (使用 list 实现),用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到 K 次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K
会淘汰第 K 次访问时间距当前时间最大的数据。
历史队列
:保存着每次访问的数据,当数据访问次数达到了k次,删除该数据并保存至缓存队列
;若尚未达到 K 次则继续保存,直至历史队列
也满了,那就根据一定的缓存策略 (FIFO、LRU、LFU) 进行淘汰。缓存队列
:保存已经访问 K 次的数据,当该队列满了之后,则淘汰最后一个数据,也就是第k次访问距离现在最久
的那个数据。
![image-20221120223204700](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20221120223204700.png)
执行过程:
- 数据第一次被访问,加入到访问历史队列;
- 若数据在访问历史列表里后没有达到 K 次访问,则按照一定规则(FIFO,LRU)淘汰;
- 当访问历史队列中的数据访问次数达到 K 次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;
- 缓存数据队列中被再次访问后,重新排序;
- 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第 K 次访问离现在最久”的数据。
LRU-K 具有 LRU 的优点,同时能够避免 LRU 的缺点。它的命中率要比 LRU 高,但因为要维护一个历史队列,因此内存消耗会比 LRU 多。
实际应用中 LRU-2 是综合各种因素后最优的选择,LRU-3 或者更大的 K 值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。
Two queues(2Q)
算法思想
该算法类似于 LRU-2
,不同点在于 2Q
将 LRU-2
算法中的访问历史队列(注意这不是缓存数据的)改为一个 FIFO
缓存队列,即:2Q
算法有两个缓存队列,一个是 FIFO
队列,一个是 LRU
队列。
工作原理
当数据第一次访问时,2Q算法将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据。
![image-20221120223844119](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20221120223844119.png)
- 新访问的数据插入到FIFO队列;
- 如果数据在FIFO队列中一直没有被再次访问,则最终按照FIFO规则淘汰;
- 如果数据在FIFO队列中被再次访问,则将数据移到LRU队列头部;
- 如果数据在LRU队列中再次被访问,则将数据移到LRU队列头部;
- LRU队列淘汰末尾的数据。
缺点跟LRU-K一致,其实2Q算法就是LRU-2,并且历史队列采用了FIFO的淘汰策略。
Muti Queue(MQ)
MQ
算法其实是 2Q
算法的一个扩展。
2Q
算法维护两个队列,而 MQ
算法根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级。
其核心思想是:优先缓存访问次数多的数据
。
举个例子
标签:缓存,队列,介绍,访问,算法,LRU,数据 From: https://www.cnblogs.com/angelia-wang/p/17189608.html