常用缓存算法——LRU

Posted on In ,

LRU算法

Least recently used（LRU）一种常用的缓存算法,通过首先丢弃最近最少使用的记录。LRU算法需要跟踪何时使用了什么，并确保算法始终丢弃最近最少使用的记录。
LRU算法及其实现-以LinkedHashMap为例：

LRU 使用LinkedHashMap代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.github.ordiy.map;

import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 经典的LRU 算法
 *  热点数据缓存
 * @Author:ordiy
 */
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
    private int cacheSize;

    public LRUCache( int cacheSize) {
        super(cacheSize,(float)0.75,true);
        this.cacheSize = cacheSize;
    }
     @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
       // System.out.println(eldest);
        return size() > cacheSize;
    }
}
  • 测试代码
@Test
public void testKey(){
    LRUCache<String,Integer> cache =  new LRUCache<>(5);
    //初始化数据
    for (int i = 0; i < 5; i++) {
        cache.put("key"+i,i);
    }
    // 模拟最近使用
    String key = "key3";
    cache.get(key);
    System.out.println("after get-->:"+ key);
    printMap(cache);

    //put data and remove Eldest Entry
    cache.put("key10",10);
    System.out.println("after put data and remove Eldest Entry");
    printMap(cache);
}
  • 输出结果
after get-->:key3
cache order:
key0=0 hashCode: 3288497 , key1=1 hashCode: 3288499 , key2=2 hashCode: 3288497 , key4=4 hashCode: 3288497 , key3=3 hashCode: 3288503 ,
3288497
after put data and remove Eldest Entry
cache order:
key1=1 hashCode: 3288499 , key2=2 hashCode: 3288497 , key4=4 hashCode: 3288497 , key3=3 hashCode: 3288503 , key10=10 hashCode: 101943476 ,
  • 过程解析
    images

使用LinkedHashMap的记录数据顺序、accessOrder、removeEldestEntry特性实现了一个简单的LRU。在分布式场景下，需要使用类似redis,pika等软件进行实现。
注意 因为LinkedHashMap并非线程安全的，多线程场景需要使用Collections.synchronizedMap进行包装
**分布式场景可以用 Redis 等组件实现 **

总结

LRU缓存有其局限性，在类似于双11这样的场景，流量/活跃用户突然大增时会出现缓存击穿问题。

参考:

https://juejin.im/post/5a4b433b6fb9a0451705916f
LinkedHashMap 源码详细分
oracle doc LinkedHashMap
Java集合类 LinkedHashMap