常用缓存算法——LRU

Posted on Edited on In , Disqus:

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;
    }
}

  • 测试代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    @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);
    }

  • 输出结果

    1
    2
    3
    4
    5
    6
    7
    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