LRU 缓存淘汰策略详解 - zxlrise/cache GitHub Wiki

1、LRU基础知识

1.1、LRU是什么

LRU 是由 Least Recently Used 的首字母组成，表示最近最少使用的含义，一般使用在对象淘汰算法上。 也是比较常见的一种淘汰算法。 其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高。

1.2、连续性

在计算机科学中，有一个指导准则：连续性准则。 时间连续性：对于信息的访问，最近被访问过，被再次访问的可能性会很高。缓存就是基于这个理念进行数据淘汰的。 空间连续性：对于磁盘信息的访问，将很有可能访问连续的空间信息。所以会有 page 预取来提升性能。

1.3、实现步骤

  1. 新数据插入到链表头部；
  2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
  3. 当链表满的时候，将链表尾部的数据丢弃。 其实比较简单，比起 FIFO 的队列，我们引入一个链表实现即可。

1.4、思考

如何判断是新数据？

  1. 新数据插入到链表头部；
  • 我们使用的是链表。判断新数据最简单的方法就是遍历是否存在，对于链表，这是一个 O(n) 的时间复杂度。其实性能还是比较差的。当然也可以考虑空间换时间，比如引入一个 set 之类的，不过这样对空间的压力会加倍。 什么是缓存命中？
  1. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
  • put(key,value) 的情况，就是新元素。如果已有这个元素，可以先删除，再加入，参考上面的处理。
  • get(key) 的情况，对于元素访问，删除已有的元素，将新元素放在头部。
  • remove(key) 移除一个元素，直接删除已有元素。
  • keySet() valueSet() entrySet() 这些属于无差别访问，我们不对队列做调整。 移除
  1. 当链表满的时候，将链表尾部的数据丢弃。
  • 链表满只有一种场景，那就是添加元素的时候，也就是执行 put(key, value) 的时候。直接删除对应的 key 即可。

2、Java代码实现

2.1、接口定义

和 FIFO 的接口保持一致，调用地方也不变。 为了后续 LRU/LFU 实现，新增 remove/update 两个方法。

public interface ICacheEvict<K, V> {

    /**
     * 驱除策略
     *
     * @param context 上下文
     * @since 0.0.2
     * @return 是否执行驱除
     */
    boolean evict(final ICacheEvictContext<K, V> context);

    /**
     * 更新 key 信息
     * @param key key
     * @since 0.0.11
     */
    void update(final K key);

    /**
     * 删除 key 信息
     * @param key key
     * @since 0.0.11
     */
    void remove(final K key);

}

2.2、LRU实现

直接基于 LinkedList 实现：

/**
 * 丢弃策略-LRU 最近最少使用
 * @author binbin.hou
 * @since 0.0.11
 */
public class CacheEvictLRU<K,V> implements ICacheEvict<K,V> {

    private static final Log log = LogFactory.getLog(CacheEvictLRU.class);

    /**
     * list 信息
     * @since 0.0.11
     */
    private final List<K> list = new LinkedList<>();

    @Override
    public boolean evict(ICacheEvictContext<K, V> context) {
        boolean result = false;
        final ICache<K,V> cache = context.cache();
        // 超过限制，移除队尾的元素
        if(cache.size() >= context.size()) {
            K evictKey = list.get(list.size()-1);
            // 移除对应的元素
            cache.remove(evictKey);
            result = true;
        }
        return result;
    }


    /**
     * 放入元素
     * （1）删除已经存在的
     * （2）新元素放到元素头部
     *
     * @param key 元素
     * @since 0.0.11
     */
    @Override
    public void update(final K key) {
        this.list.remove(key);
        this.list.add(0, key);
    }

    /**
     * 移除元素
     * @param key 元素
     * @since 0.0.11
     */
    @Override
    public void remove(final K key) {
        this.list.remove(key);
    }
}

实现比较简单，相对 FIFO 多了三个方法： update()：我们做一点简化，认为只要是访问，就是删除，然后插入到队首。 remove()：删除就是直接删除。

这三个方法是用来更新最近使用情况的。

2.3、注解属性

为了保证核心流程，我们基于注解实现。 添加属性：

/**
 * 是否执行驱除更新
 *
 * 主要用于 LRU/LFU 等驱除策略
 * @return 是否
 * @since 0.0.11
 */
boolean evict() default false;

2.4、注解使用

有哪些方法需要使用？

@Override
@CacheInterceptor(refresh = true, evict = true)
public boolean containsKey(Object key) {
    return map.containsKey(key);
}

@Override
@CacheInterceptor(evict = true)
@SuppressWarnings("unchecked")
public V get(Object key) {
    //1. 刷新所有过期信息
    K genericKey = (K) key;
    this.expire.refreshExpire(Collections.singletonList(genericKey));
    return map.get(key);
}

@Override
@CacheInterceptor(aof = true, evict = true)
public V put(K key, V value) {
    //...
}

@Override
@CacheInterceptor(aof = true, evict = true)
public V remove(Object key) {
    return map.remove(key);
}

2.4、注解驱除拦截器实现

执行顺序：放在方法之后更新，不然每次当前操作的 key 都会被放在最前面。

/**
 * 驱除策略拦截器
 * 
 * @author binbin.hou
 * @since 0.0.11
 */
public class CacheInterceptorEvict<K,V> implements ICacheInterceptor<K, V> {

    private static final Log log = LogFactory.getLog(CacheInterceptorEvict.class);

    @Override
    public void before(ICacheInterceptorContext<K,V> context) {
    }

    @Override
    @SuppressWarnings("all")
    public void after(ICacheInterceptorContext<K,V> context) {
        ICacheEvict<K,V> evict = context.cache().evict();

        Method method = context.method();
        final K key = (K) context.params()[0];
        if("remove".equals(method.getName())) {
            evict.remove(key);
        } else {
            evict.update(key);
        }
    }

}

2.5、测试

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .evict(CacheEvicts.<String, String>lru())
        .build();
cache.put("A", "hello");
cache.put("B", "world");
cache.put("C", "FIFO");

// 访问一次A
cache.get("A");
cache.put("D", "LRU");
Assert.assertEquals(3, cache.size());

System.out.println(cache.keySet());
  • 日志信息
[D, A, C]

通过 removeListener 日志也可以看到 B 被移除了：

[DEBUG] [2020-10-02 21:33:44.578] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: wor
⚠️ **GitHub.com Fallback** ⚠️