关于redis:从零开始手写-redis八朴素-LRU-淘汰算法性能优化

前言

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

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

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

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

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

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

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

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

LRU 基础知识

是什么

LRU算法全称是最近起码应用算法（Least Recently Use），宽泛的利用于缓存机制中。

当缓存应用的空间达到下限后，就须要从已有的数据中淘汰一部分以维持缓存的可用性，而淘汰数据的抉择就是通过LRU算法实现的。

LRU算法的根本思维是基于局部性原理的工夫局部性：

如果一个信息项正在被拜访，那么在近期它很可能还会被再次拜访。

拓展浏览

Apache Commons LRUMAP 源码详解

Redis 当做 LRU MAP 应用

java 从零开始手写 redis（七）redis LRU 驱除策略详解及实现

简略的实现思路

基于数组

计划：为每一个数据附加一个额定的属性——工夫戳，当每一次拜访数据时，更新该数据的工夫戳至以后工夫。

当数据空间已满后，则扫描整个数组，淘汰工夫戳最小的数据。

有余：保护工夫戳须要消耗额定的空间，淘汰数据时须要扫描整个数组。

这个工夫复杂度太差，空间复杂度也不好。

基于长度无限的双向链表

计划：拜访一个数据时，当数据不在链表中，则将数据插入至链表头部，如果在链表中，则将该数据移至链表头部。当数据空间已满后，则淘汰链表最开端的数据。

有余：插入数据或取数据时，须要扫描整个链表。

这个就是咱们上一节实现的形式，毛病还是很显著，每次确认元素是否存在，都要耗费 O(n) 的工夫复杂度去查问。

基于双向链表和哈希表

计划：为了改良下面须要扫描链表的缺点，配合哈希表，将数据和链表中的节点造成映射，将插入操作和读取操作的工夫复杂度从O(N)降至O(1)

毛病：这个使咱们上一节提到的优化思路，不过还是有毛病的，那就是空间复杂度翻倍。

数据结构的抉择

（1）基于数组的实现

这里不倡议抉择 array 或者 ArrayList，因为读取的工夫复杂度为 O(1)，然而更新绝对是比较慢的，尽管 jdk 应用的是 System.arrayCopy。

（2）基于链表的实现

如果咱们抉择链表，HashMap 中还是不能简略的存储 key, 和对应的下标。

因为链表的遍历，实际上还是 O(n) 的，双向链表实践上能够优化一半，然而这并不是咱们想要的 O(1) 成果。

（3）基于双向列表

双向链表咱们放弃不变。

Map 中 key 对应的值咱们放双向链表的节点信息。

那实现形式就变成了实现一个双向链表。

代码实现

节点定义

/** * 双向链表节点 * @author binbin.hou * @since 0.0.12 * @param <K> key * @param <V> value */public class DoubleListNode<K,V> {    /**     * 键     * @since 0.0.12     */    private K key;    /**     * 值     * @since 0.0.12     */    private V value;    /**     * 前一个节点     * @since 0.0.12     */    private DoubleListNode<K,V> pre;    /**     * 后一个节点     * @since 0.0.12     */    private DoubleListNode<K,V> next;    //fluent get & set}

外围代码实现

咱们放弃和原来的接口不变，实现如下：

public class CacheEvictLruDoubleListMap<K,V> extends AbstractCacheEvict<K,V> {    private static final Log log = LogFactory.getLog(CacheEvictLruDoubleListMap.class);    /**     * 头结点     * @since 0.0.12     */    private DoubleListNode<K,V> head;    /**     * 尾巴结点     * @since 0.0.12     */    private DoubleListNode<K,V> tail;    /**     * map 信息     *     * key: 元素信息     * value: 元素在 list 中对应的节点信息     * @since 0.0.12     */    private Map<K, DoubleListNode<K,V>> indexMap;    public CacheEvictLruDoubleListMap() {        this.indexMap = new HashMap<>();        this.head = new DoubleListNode<>();        this.tail = new DoubleListNode<>();        this.head.next(this.tail);        this.tail.pre(this.head);    }    @Override    protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {        ICacheEntry<K, V> result = null;        final ICache<K,V> cache = context.cache();        // 超过限度，移除队尾的元素        if(cache.size() >= context.size()) {            // 获取尾巴节点的前一个元素            DoubleListNode<K,V> tailPre = this.tail.pre();            if(tailPre == this.head) {                log.error("以后列表为空，无奈进行删除");                throw new CacheRuntimeException("不可删除头结点!");            }            K evictKey = tailPre.key();            V evictValue = cache.remove(evictKey);            result = new CacheEntry<>(evictKey, evictValue);        }        return result;    }    /**     * 放入元素     *     * （1）删除曾经存在的     * （2）新元素放到元素头部     *     * @param key 元素     * @since 0.0.12     */    @Override    public void update(final K key) {        //1. 执行删除        this.remove(key);        //2. 新元素插入到头部        //head<->next        //变成：head<->new<->next        DoubleListNode<K,V> newNode = new DoubleListNode<>();        newNode.key(key);        DoubleListNode<K,V> next = this.head.next();        this.head.next(newNode);        newNode.pre(this.head);        next.pre(newNode);        newNode.next(next);        //2.2 插入到 map 中        indexMap.put(key, newNode);    }    /**     * 移除元素     *     * 1. 获取 map 中的元素     * 2. 不存在间接返回，存在执行以下步骤：     * 2.1 删除双向链表中的元素     * 2.2 删除 map 中的元素     *     * @param key 元素     * @since 0.0.12     */    @Override    public void remove(final K key) {        DoubleListNode<K,V> node = indexMap.get(key);        if(ObjectUtil.isNull(node)) {            return;        }        // 删除 list node        // A<->B<->C        // 删除 B，须要变成： A<->C        DoubleListNode<K,V> pre = node.pre();        DoubleListNode<K,V> next = node.next();        pre.next(next);        next.pre(pre);        // 删除 map 中对应信息        this.indexMap.remove(key);    }}

实现起来不难，就是一个繁难版本的双向列表。

只是获取节点的时候，借助了一下 map，让工夫复杂度升高为 O(1)。

测试

咱们验证一下本人的实现：

ICache<String, String> cache = CacheBs.<String,String>newInstance()        .size(3)        .evict(CacheEvicts.<String, String>lruDoubleListMap())        .build();cache.put("A", "hello");cache.put("B", "world");cache.put("C", "FIFO");// 拜访一次Acache.get("A");cache.put("D", "LRU");Assert.assertEquals(3, cache.size());System.out.println(cache.keySet());

日志

[DEBUG] [2020-10-03 09:37:41.007] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict[D, A, C]

因为咱们拜访过一次 A，所以 B 曾经变成起码被拜访的元素。

基于 LinkedHashMap 实现

实际上，LinkedHashMap 自身就是对于 list 和 hashMap 的一种联合的数据结构，咱们能够间接应用 jdk 中 LinkedHashMap 去实现。

间接实现

public class LRUCache extends LinkedHashMap {    private int capacity;    public LRUCache(int capacity) {        // 留神这里将LinkedHashMap的accessOrder设为true        super(16, 0.75f, true);        this.capacity = capacity;    }    @Override    protected boolean removeEldestEntry(Map.Entry eldest) {        return super.size() >= capacity;    }}

默认LinkedHashMap并不会淘汰数据，所以咱们重写了它的removeEldestEntry()办法，当数据数量达到预设下限后，淘汰数据，accessOrder设为true意为依照拜访的程序排序。

整个实现的代码量并不大，次要都是利用LinkedHashMap的个性。

简略革新

咱们对这个办法简略革新下，让其适应咱们定义的接口。

ICache<String, String> cache = CacheBs.<String,String>newInstance()        .size(3)        .evict(CacheEvicts.<String, String>lruLinkedHashMap())        .build();cache.put("A", "hello");cache.put("B", "world");cache.put("C", "FIFO");// 拜访一次Acache.get("A");cache.put("D", "LRU");Assert.assertEquals(3, cache.size());System.out.println(cache.keySet());

测试

代码

ICache<String, String> cache = CacheBs.<String,String>newInstance()        .size(3)        .evict(CacheEvicts.<String, String>lruLinkedHashMap())        .build();cache.put("A", "hello");cache.put("B", "world");cache.put("C", "FIFO");// 拜访一次Acache.get("A");cache.put("D", "LRU");Assert.assertEquals(3, cache.size());System.out.println(cache.keySet());

日志

[DEBUG] [2020-10-03 10:20:57.842] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict[D, A, C]

小结

上一节中提到的数组 O(n) 遍历的问题，本节曾经根本解决了。

但其实这种算法仍然存在肯定的问题，比方当偶发性的批量操作时，会导致热点数据被非热点数据挤出缓存，下一节咱们一起学习如何进一步改良 LRU 算法。

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

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

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

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