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

2次阅读

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

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

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

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

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

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

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

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

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

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

// 拜访一次 A
cache.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 自身就是对于 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");
// 拜访一次 A
cache.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");
// 拜访一次 A
cache.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

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

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

正文完

redis

发表至： redis

2020-10-04

0

关于redis:每个程序员都应该知道的-Redis-知识-String-底层原理

关于redis:如何用Redis实现分布式锁

618-Tech-Talk高并发场景下的数据访问速度如何保障

Redis-AOF一篇即懂

关于redis:redis学习

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

前言

LRU 基础知识

是什么

拓展浏览

简略的实现思路

基于数组

基于长度无限的双向链表

基于双向链表和哈希表

数据结构的抉择

代码实现

测试

基于 LinkedHashMap 实现

间接实现

简略革新

测试

小结

站内搜索