关于redis:java-从零开始手写-redis七LRU-缓存淘汰策略详解

java 从零手写实现 redis（一）如何实现固定大小的缓存？

java 从零手写实现 redis（三）redis expire 过期原理

java 从零手写实现 redis（三）内存数据如何重启不失落？

java 从零手写实现 redis（四）增加监听器

java 从零手写实现 redis（五）过期策略的另一种实现思路

java 从零手写实现 redis（六）AOF 长久化原理详解及实现

咱们后面简略实现了 redis 的几个个性，java 从零手写实现 redis（一）如何实现固定大小的缓存？中实现了先进先出的驱除策略。

然而理论工作实际中，个别举荐应用 LRU/LFU 的驱除策略。

Apache Commons LRUMAP 源码详解

Redis 当做 LRU MAP 应用

LRU 是由 Least Recently Used 的首字母组成，示意最近起码应用的含意，个别应用在对象淘汰算法上。

也是比拟常见的一种淘汰算法。

其核心思想是 如果数据最近被拜访过，那么未来被拜访的几率也更高。

在计算机科学中，有一个领导准则：连续性准则。

工夫连续性：对于信息的拜访，最近被拜访过，被再次拜访的可能性会很高。缓存就是基于这个理念进行数据淘汰的。

空间连续性：对于磁盘信息的拜访，将很有可能拜访间断的空间信息。所以会有 page 预取来晋升性能。

新数据插入到链表头部；
每当缓存命中（即缓存数据被拜访），则将数据移到链表头部；
当链表满的时候，将链表尾部的数据抛弃。

其实比较简单，比起 FIFO 的队列，咱们引入一个链表实现即可。

咱们针对下面的 3 句话，逐句考虑一下，看看有没有值得优化点或者一些坑。

（1）新数据插入到链表头部；

咱们应用的是链表。

判断新数据最简略的办法就是遍历是否存在，对于链表，这是一个 O(n) 的工夫复杂度。

其实性能还是比拟差的。

当然也能够思考空间换工夫，比方引入一个 set 之类的，不过这样对空间的压力会加倍。

（2）每当缓存命中（即缓存数据被拜访），则将数据移到链表头部；

put(key,value) 的状况，就是新元素。如果已有这个元素，能够先删除，再退出，参考下面的解决。

get(key) 的状况，对于元素拜访，删除已有的元素，将新元素放在头部。

remove(key) 移除一个元素，间接删除已有元素。

keySet() valueSet() entrySet() 这些属于无差别拜访，咱们不对队列做调整。

（3）当链表满的时候，将链表尾部的数据抛弃。

链表满只有一种场景，那就是增加元素的时候，也就是执行 put(key, value) 的时候。

间接删除对应的 key 即可。

和 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);

}

间接基于 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()：删除就是间接删除。

这三个办法是用来更新最近应用状况的。

那什么时候调用呢？

为了保障外围流程，咱们基于注解实现。

增加属性：

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

有哪些办法须要应用？

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

执行程序：放在办法之后更新，不然每次以后操作的 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);
        }
    }

}

咱们只对 remove 办法做下特判，其余办法都应用 update 更新信息。

参数间接取第一个参数。

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: world, type: evict

redis LRU 淘汰策略，实际上并不是真正的 LRU。

LRU 有一个比拟大的问题，就是每次 O(n) 去查找，这个在 keys 数量特地多的时候，还是很慢的。

如果 redis 这么设计必定慢的要死了。

集体的了解是能够用空间换取工夫，比方增加一个 Map<String, Integer> 存储在 list 中的 keys 和下标，O(1) 的速度去查找，然而空间复杂度翻倍了。

不过这个就义还是值得的。这种后续对立做下优化，将各种优化点对立思考，这样能够兼顾全局，也便于前期对立调整。

下一节咱们将一起来实现以下改进版的 LRU。

Redis 做的事件，就是将看起来的简略的事件，做到一种极致，这一点值得每一个开源软件学习。

文中次要讲述了思路，实现局部因为篇幅限度，没有全副贴出来。

开源地址：https://github.com/houbb/cache

感觉本文对你有帮忙的话，欢送点赞评论珍藏关注一波~

你的激励，是我最大的能源~

关于redis:java-从零开始手写-redis七LRU-缓存淘汰策略详解

前言

LRU 基础知识

拓展学习

LRU 是什么

连续性

实现步骤

一点思考

如何判断是新数据？

什么是缓存命中

移除

java 代码实现

接口定义

LRU 实现

注解属性

注解应用

注解驱除拦截器实现

测试

小结