LRU (Least Recently Used)
算法思想
每次内存溢出时，把最长时间未被访问的数据置换出去。这种算法是完全从最近使用的时间角度去考虑的。
维护每个数据上一次被访问的 timestamp，每次移除 timestamp 最早的数据。
工作原理
我们需要实现 LRU 的 put 和 get 的 O(1) 复杂度操作 ——
需要的数据结构：list、unordered_map。
- list 链表使插入和删除操作的复杂度达到 O(1)，list结点存储访问的数据。
- unordered_map 映射 key 到 list 结点，使查找的复杂度达到O(1)。
执行过程：
- 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次访问距离现在最久的那个数据。
执行过程：
- 数据第一次被访问，加入到访问历史队列；
- 若数据在访问历史列表里后没有达到 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队列里面，两个队列各自按照自己的方法淘汰数据。
- 新访问的数据插入到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