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

36次阅读

共计 4360 个字符，预计需要花费 11 分钟才能阅读完成。

前言

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

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

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

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

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

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

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

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

LRU 基础知识

拓展学习

Apache Commons LRUMAP 源码详解

Redis 当做 LRU MAP 应用

LRU 是什么

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

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

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

连续性

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

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

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

实现步骤

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

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

一点思考

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

如何判断是新数据？

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

咱们应用的是链表。

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

其实性能还是比拟差的。

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

什么是缓存命中

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

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

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

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

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

移除

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

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

间接删除对应的 key 即可。

java 代码实现

接口定义

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

}

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

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

那什么时候调用呢？

注解属性

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

增加属性：

/**
 * 是否执行驱除更新
 *
 * 次要用于 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
发表至： redis
2020-10-03
 0
关于redis:Redis核心技术3135
关于redis:Redis数据结构-字典
关于redis:redis-哨兵进阶
关于redis:ECX知识点