![LRU 及 LFU 算法]()
算法实现
LRU
LRU 是一种基于“最近最少使用”原则的缓存淘汰策略。其核心思想是，如果一个数据项在最近被频繁使用，那么它就更有可能在未来被再次访问。反之，较少被访问的数据项应该被优先淘汰。以146. LRU 缓存为例，实现LRU算法：
其实，LRU的思想很简单，我们需要能快速拿到最久未使用的节点，那么就可以借助顺序的数据结构去实现，最近访问的在前面，最久访问的在后面，替换的时候替换掉最后面的就可以了。
但问题在于中间对某个key访问的话，他就会变成最近访问的，需要把他移动到最前面，如果用List的话复杂度比较高，很容易就想到用链表，而且为了快速的插入和删除应该使用双向列表更为合适。
同时为了能快速地拿到头结点和尾节点，可以设置虚拟头尾节点简化操作。
然后想一下我们还需要建立key和value的映射来实现O(1)时间内的get，这里用的肯定就是HashMap了。
那么如何建立这两种数据结构的映射呢？可以选用很巧妙的方法，HashMap的value是链表的节点，将实际的value存到链表节点中。
class LRUCache {
class ListNode{
ListNode pre;
ListNode next;
int value;
int key;
public ListNode(){}
public ListNode(int key, int value){
this.value = value;
this.key = key;
}
}
int capacity;
ListNode virtualHead;
ListNode virtualTail;
Map<Integer,ListNode> cache = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
virtualHead = new ListNode();
virtualTail = new ListNode();
virtualHead.next = virtualTail;
virtualTail.pre = virtualHead;
}
public int get(int key) {
ListNode node = cache.getOrDefault(key, null);
if(node != null){
moveToHead(node);
return node.value;
}
else{
return -1;
}
}
public void put(int key, int value) {
ListNode node = cache.getOrDefault(key, null);
if(node != null){
moveToHead(node);
node.value = value;
}
else{
if(capacity == 0){
removeLastNode();
}else{
--capacity;
}
ListNode newNode = new ListNode(key,value);
insertNode(newNode);
cache.put(key,newNode);
}
}
public void removeLastNode(){
ListNode lastNode = virtualTail.pre;
lastNode.pre.next = virtualTail;
virtualTail.pre = lastNode.pre;
cache.remove(lastNode.key);
}
public void insertNode(ListNode node){
virtualHead.next.pre = node;
node.next = virtualHead.next;
virtualHead.next = node;
node.pre = virtualHead;
}
public void moveToHead(ListNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
this.insertNode(node);
}
}
|
其实Java中已经有类似的数据结构存在，就是LinkedHashMap，它默认就会按照插入的顺序排序，因此也可以借助这种数据结构实现：
class LRUCache {
private int capacity;
private Map<Integer, Integer> cache;
public LRUCache(int capacity) {
this.cache = new LinkedHashMap<>();
this.capacity = capacity;
}
public int get(int key) {
if(this.cache.containsKey(key)){
int temp = this.cache.get(key);
this.cache.remove(key);
this.cache.put(key, temp);
return temp;
}
else{
return -1;
}
}
public void put(int key, int value) {
if(this.cache.containsKey(key)){
int temp = this.cache.get(key);
this.cache.remove(key);
this.cache.put(key, value);
}
else{
if(this.capacity > 0){
this.cache.put(key, value);
this.capacity--;
}else{
int oldKey = this.cache.keySet().iterator().next();
this.cache.remove(oldKey);
this.cache.put(key, value);
}
}
}
}
|
LFU
LFU 是一种基于“最少使用”原则的缓存淘汰策略。其核心思想是，如果某个数据项被访问的次数较少，那么它应该被优先淘汰，而不是最近没被访问的数据。
实现这种算法相比LRU就复杂的多，这里参考了labuladong 的算法笔记中的解法，使用了三个HashMap建立三种映射关系：
Map<Integer, Integer> key2Value ：key 和 value 映射Map<Integer, Integer> key2Freq ：key 和访问频率映射 Map<Integer, LinkedHashSet<Integer>> freq2Keys ： 访问频率和该访问频率的所有 key 的映射，LinkedHashSet保证了访问顺序为插入顺序（这保证了题目中：在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键的要求）
通过三种映射关系，我们就可以实现通过key获得和更新其访问频率，再加上一个变量（minFreq）用于记录最小访问频率，就可以实现获取和移除需要被替换的key。具体代码如下：
class LFUCache {
private Map<Integer, Integer> key2Value;
private Map<Integer, Integer> key2Freq;
private Map<Integer, LinkedHashSet<Integer>> freq2Keys;
private int capacity;
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFreq = 0;
this.key2Value = new HashMap<>();
this.key2Freq = new HashMap<>();
this.freq2Keys = new HashMap<>();
}
public int get(int key) {
if(key2Value.containsKey(key)){
addFreq(key);
return key2Value.get(key);
}else{
return -1;
}
}
public void put(int key, int value) {
if(key2Value.containsKey(key)){
key2Value.put(key, value);
addFreq(key);
}else{
if(capacity == 0){
removeMinFreKey();
}else{
capacity -= 1;
}
minFreq = 1;
key2Freq.put(key, 1);
key2Value.put(key, value);
freq2Keys.putIfAbsent(1, new LinkedHashSet<Integer>());
freq2Keys.get(1).add(key);
}
}
public void removeMinFreKey(){
LinkedHashSet<Integer> temp = freq2Keys.get(minFreq);
int minFreKey = temp.iterator().next();
temp.remove(minFreKey);
if(temp.isEmpty()){
freq2Keys.remove(minFreq);
}
key2Freq.remove(minFreKey);
key2Value.remove(minFreKey);
}
public void addFreq(int key){
int oldFreq = key2Freq.get(key);
key2Freq.put(key, oldFreq + 1);
LinkedHashSet<Integer> temp = freq2Keys.get(oldFreq);
temp.remove(key);
if(temp.isEmpty()){
freq2Keys.remove(oldFreq);
if(oldFreq == minFreq){
minFreq++;
}
}
freq2Keys.putIfAbsent(oldFreq + 1, new LinkedHashSet<Integer>());
freq2Keys.get(oldFreq + 1).add(key);
}
}
|
对比
| 算法 |
优点 |
缺点 |
| LRU |
实现简单
适用于具有时间局部性特点的场景 |
访问频率高的数据因暂时未被访问就被置换出去
存在缓存污染问题 |
| LFU |
可以解决缓存污染和错误置换问题
某些场景下缓存命中率可能更高 |
实现复杂
需要更多的内存和计算开销 |
Redis 中的 LRU 和 LFU
在 Redis的内存淘汰策略中(当 Redis 的运行内存已经超过 Redis 设置的最大内存之后，则会使用内存淘汰策略删除符合条件的 key，以此来保障 Redis 高效的运行), 就提供了LRU和LFU算法，但是并没有采用上面提到的这种算法，因为Redis作为内存型数据库，其内存比较紧张，这种方式带来了额外的空间开销，而且频繁的链表操作也会降低性能。Redis采用的其实都是近似算法，具体如下：
Redis中的LRU算法：
Redis 实现的是一种近似 LRU 算法，目的是为了更好的节约内存，它的实现方式是在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间。
当 Redis 进行内存淘汰时，会使用随机采样的方式来淘汰数据，它是随机取 5 个值（此值可配置），然后淘汰最久没有使用的那个。
然而该算法存在缓存污染问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间（需要比他早的数据都被移除或者更新，这些数据才会被清理），造成缓存污染。
Redis中的LFU算法
LFU算法中记录了每个key的两个信息：
- 上次访问的时间戳
- 访问频率（不是单纯的访问频次），会随着时间推移而衰减
具体来说分成两步，其中衰减速度和增长速度都是可配置的：
- 衰减：在每次 key 被访问时，会先对 logc 做一个衰减操作，衰减的值跟前后访问时间的差距有关系，如果上一次访问的时间与这一次访问的时间差距很大，那么衰减的值就越大，
- 增加：增加操作并不是单纯的 + 1，而是根据概率增加，如果 logc 越大的 key，它的 logc 就越难再增加。
存储结构，LRU算法和LFU算法共用了对象头中的同一个字段：
![1731509732330.png]()
在 LRU 算法中，Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳，因此在 LRU 模式下，Redis可以根据对象头中的 lru 字段记录的值，来比较最后一次 key 的访问时间长，从而淘汰最久未被使用的 key。
在 LFU 算法中，Redis对象头的 24 bits 的 lru 字段被分成两段来存储，高 16bit 存储 ldt(Last Decrement Time)，低 8bit 存储 logc(Logistic Counter)。
此外之前在使用Verilog设计龙芯CPU时也涉及到了Cache替换策略，可以使用矩阵法来实现LRU，可参考用FPGA实现最近最少使用(LRU)算法
参考：
