缓存淘汰机制LRU和LFU的区别

缓存淘汰机制LRU和LFU的区别

• 在高并发，高访问量的电商平台中，缓存是提升性能的的保障用户体验的关键；
• 然而，受限于物理内存，缓存空间总是有限的；
• 因此必须采用合适的淘汰（替换）策略，保证最有价值的数据能长时间驻留缓存。

LRU与LFU的基本原理

LRU（最少最近使用）

• 思路：优先淘汰最近一段时间最久没有被访问的数据；
• 实现：常用哈希表+双向链表；每当访问或者新增数据，即把该数据节点移到链表头部，淘汰是直接移除链表尾部；
• 优点：实现简单，适应访问热点快速变换的场景。

• 当我们连续插入DBCA时，此时内存以及满了；
• 那么当我们再插入一个M的时候，此时内存存放最久的数据D淘汰掉；
• 当我们从外部读取数据M的时候，此时M就会提到头部，这时候M就是最晚被淘汰掉的。

LFU（最不经常使用）

• 思路：优先淘汰一段时间内访问次数（频率）最低的数据；
• 实现：需要维护每个数据节点的访问频率，多用哈希表加"频率链表"组合。淘汰最低频率中的最旧节点。
• 优点：能够更好保持长期高频访问的数据，适合长期热门但访问分布分散的场景。

• 当我们插入ABC之后，其会以CBA的形式存储于双向链表中；
• 当我们再插入ABDE后，BA会到频率为2处，ED会到频率为1处；
• 当再次插入AMD，之后内存会满，如果此时我们再插入一个Q，会先淘汰频率为1处，最先插入的C。

实现方法和复杂性

电商场景下如何选择？

电商常见的数据访问模式：

• 秒杀，大促，首页推荐：短时间部分商品或页面极度火爆，热点变换块；
• 长期商品，个性化推荐：部分数据长期有较低频率访问。

选择建议：

• 若面向热点商品突变频繁场景（如秒杀，活动页）–优先选择LRU。因为持续被访问的热点商品会留在缓存前端，发生访问突变事能够快速适用变化，防止缓存穿透；
• 若需要保护"常青"商品或内容库（如个性化，长期售卖页面）–可选择LFU。能够留存虽然访问不集中的长期高配数据，防止配LRU “误杀”；
• 实际项目中采用分区或者多级缓存，针对不如业务分别设计缓存策略（如活动页LRU，推荐页LFU）。

结论

• LRU和LFU的根本区别：一个重"新近性"，一个重"访问频率"；
• 电商访问模式以热点突变为主，推荐优先使用LRU缓存机制；
• 综合业务需求时，可以混合使用LRU/LFU，或者采用2Q，LRU-K等改进型算法，结合流量特征和数据重要性灵活选型。

代码实现

LRU缓存（基于双向链表+哈希表）

/** * LRU缓存（基于双向链表+哈希表） */publicclassLRU<K,V>{privatefinalintcapacity;privatefinalMap<K,Node<K,V>>map;privatefinalNode<K,V>head,tail;staticclassNode<K,V>{Kkey;Vvalue;Node<K,V>prev,next;Node(){}Node(Kkey,Vvalue){this.key=key;this.value=value;}}publicLRU(intcapacity){this.capacity=capacity;this.map=newHashMap<>();head=newNode<>();tail=newNode<>();head.next=tail;tail.prev=head;}publicVget(Kkey){Node<K,V>node=map.get(key);if(node==null){returnnull;}moveToHead(node);returnnode.value;}publicvoidput(Kkey,Vvalue){Node<K,V>node=map.get(key);if(node==null){node=newNode<>(key,value);map.put(key,node);addToHead(node);if(map.size()>capacity){Node<K,V>tail=removeTail();map.remove(tail.key);}else{node.value=value;addToHead(node);}}}/** * 添加节点 * @param node */privatevoidaddToHead(Node<K,V>node){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}/** * 删除节点 * @param node */privatevoidremoveNode(Node<K,V>node){node.prev.next=node.next;node.next.prev=node.prev;}/** * 移动节点到头部 * @param node */privatevoidmoveToHead(Node<K,V>node){node.prev.next=node.next;node.next.prev=node.prev;addToHead(node);}/** * 删除尾部节点 * @return */privateNode<K,V>removeTail(){Node<K,V>node=tail.prev;node.prev.next=tail;tail.prev=node.prev;returnnode;}}

LFU缓存（基于HashMap+频率链表）

/** * LFU缓存（基于HashMap+频率链表） */publicclassLFU<K,V>{privateintcapacity;privateintminFreq;privatefinalMap<K,Node<K,V>>nodeMap;privatefinalMap<Integer,LinkedHashSet<Node<K,V>>>freqMap;staticclassNode<K,V>{Kkey;Vvalue;intfreq;Node(Kkey,Vvalue){this.key=key;this.value=value;this.freq=1;}}publicLFU(intcapacity){this.capacity=capacity;this.minFreq=0;this.nodeMap=newHashMap<>();this.freqMap=newHashMap<>();}publicVget(Kkey){Node<K,V>node=nodeMap.get(key);if(node==null)returnnull;increaseFreq(node);returnnode.value;}publicvoidput(Kkey,Vvalue){if(capacity<=0)return;if(nodeMap.containsKey(key)){Node<K,V>node=nodeMap.get(key);node.value=value;increaseFreq(node);return;}if(nodeMap.size()==capacity){// 淘汰访问频率最低且最久的节点LinkedHashSet<Node<K,V>>set=freqMap.get(minFreq);Node<K,V>toRemove=set.iterator().next();set.remove(toRemove);nodeMap.remove(toRemove.key);}Node<K,V>newNode=newNode<>(key,value);nodeMap.put(key,newNode);freqMap.computeIfAbsent(1,k->newLinkedHashSet<>()).add(newNode);minFreq=1;}privatevoidincreaseFreq(Node<K,V>node){intfreq=node.freq;LinkedHashSet<Node<K,V>>set=freqMap.get(freq);set.remove(node);if(freq==minFreq&&set.isEmpty()){minFreq++;}node.freq++;freqMap.computeIfAbsent(node.freq,k->newLinkedHashSet<>()).add(node);}}

测试案例

publicclassCacheTest{publicstaticvoidmain(String[]args){// 测试LRU缓存LRU<Integer,String>lruCache=newLRU<>(2);lruCache.put(1,"A");lruCache.put(2,"B");System.out.println(lruCache.get(1));// 输出: AlruCache.put(3,"C");System.out.println(lruCache.get(2));// 输出: null (2被淘汰)// 测试LFU缓存LFU<Integer,String>lfuCache=newLFU<>(2);lfuCache.put(1,"A");lfuCache.put(2,"B");System.out.println(lfuCache.get(1));// 输出: AlfuCache.put(3,"C");System.out.println(lfuCache.get(2));// 输出: null (2被淘汰，因1 频率高)}}