缓存数据的淘汰之路（中）

作者：卢卡多多

2021 年 12 月 09 日
本文字数：3583 字
阅读完需：约 12 分钟

话说上期

数据又回来了，想起昨天被过期经理上了一课，虽然心里很是难过，但是毕竟知道人外有人，原来为了控制我们数据，制定了这么野性的过期键策略，听说后面的关更难了，但是还是要闯关一下了，不是还有那句话嘛，关关难过关关过

缓存淘汰策略

听说有个老头叫缓存淘汰策略，比过期键经理还有实力，好多难找的数据，都能被他找到，经过他这么一整，Redis 总统的管理起来就很容易了，为了可以更好的了解到接下来缓存淘汰策略，越战越勇的数据，背着自己的 value 心灵还是出发了，

一路经过了过期键经理的送别，游荡在半路上，遇见了一个老头，说你是来自过期键经理的数据吧，数据连忙惊讶，哇靠，这老头连我从哪里来的都知道，莫不是；

是的，我就是那个老头，说完就哈哈大笑起来。

什么时候会遇见这个老头呢？

缓存淘汰策略触发的条件：

当前缓存空间临界最大 memeory
当前需要业务改变，需要调整缓存策略
对于选中键值对，所有键值对做过滤时候

最直接的就是：比如就是当内存 maxmemory 不够用了，就会启用内存淘汰策略了；

老头手里有秘笈

专门治理缓存中的无量数据，

其中分为两个维度，四个方面---》八种结果；

维度

①过期键中筛选

②所以 key 中筛选

四个方面

LRU
LFU
RANDOM
TTL

八种缓存淘汰策略：

其中两个缩写：LRU: least recently used 最近最少使用(Least Recently Used)；最近最少使用算法 LFU: least frequently Used 置换算法(Least Frequently Used)最近频率算法

LRU 和最小 TTL 算法不是精确算法而是近似算法

首先呢，数据就先确定了有八种缓存淘汰策略，各有优势；

三大问题，就出现在数据脑海中

1.一般本地会用什么缓存淘汰策略呢？

2.如何修改缓存淘汰策略呢？

3.最近比较火缓存淘汰机制 LRU 思想是啥？

解析问题 1：

1.一般本地会用什么缓存淘汰策略呢？

如果是自己本地已经下载了 Redis，一般在配置文件 conf 中会找到，关于 memory-policy 的字段，其中配置的值为 noevcation 的，不会驱逐

表示对于缓存中的数据，不做淘汰，即是缓存内存奔溃；

解析问题 2：

2.如何修改缓存淘汰策略呢？

两种方式，一种是命令，一种是 conf 的方式：

命令方式：

config set maxmemory-policy allkeys-lru

复制代码

conf 文件

# maxmemory-policy noevication  不会驱逐，会导致redis奔溃maxmeory-policy allkeys-lru

复制代码

解析问题 3：

3.最近比较火缓存淘汰机制 LRU 思想是啥？

LRU: Least Recently Used 的缩写；即最近最少使用，的一种页面置换算法

本质上

此算法会过滤出最近最久未使用的数据予以淘汰

实例场景：

手机的后台任务，一个任务多次使用，会默认提示他的加载能力，特别少使用的会放在最左侧，直到内存发生空间紧张，优先使用 LRU;

此算法就是来源于力扣的算法， LRU 的缓存机制；

LRU 算法的思想：

所谓缓存：是读和写的操作，最好在 O(1)状态机制下，完成读与写的过程

特性要求：

必须要有顺序之分，因为根据排序，留存的时间区分
读写操作一次搞定，符合 O（1）的状态
如果缓存容量满了，删除不常用的数据，
每次访问要把最新的数据插入队头中去；
综上所述：

查找快，删除快，插入快，且还需要注意顺序的数据结构

就是哈希链表；

其中哈希：查找链表：插入和删除快，还要有顺序，双向链表

三个问题有了答案之后，数据感觉顿时对老头，心里的敬畏之情谊，

这老头对于 LRU 底层，多个缓存淘汰策略的制定，很有见解，果然姜换是老的辣

数据今天的旅途很是受益

卢卡寄语

通过对数据经过过期键，到缓存淘汰策略，一次次是将数据过滤，减少内存的损耗，

其中 LRU 算法思想在于多个场景技术中都用到过，比如手机的多任务，就是简单的 LRU 来做的，下期是卢卡带你手写 LRU 算法，期待数据又更好的表现。

LRU 算法

数据今天遇到一个大佬，人家都成为缓存老头的得意门生 LRU，数据在此之前早就听过它的大名，因为很多数据在过期之后，会让 LRU 大师兄去筛选出合适的数据，用来继续提供缓存服务，这里面就涉及了 LRU 大师兄的秘笈了

就是哈希链表，因为 LRU 大师兄，不仅查询数据 get(),set()数据也特别快，关键是可以很好的排序效果；

根据这三点，数据结构的木匠就给它打造了这个关于 hash -->保持顺序链表，将数据链接起来，查询和插入；

用 Java 中的数据结构写出 LRU 算法

Java 中对于链表有存在 hash 的，我们首先可以想到是 hashmap，但是我们这次要使用一个他的子类，

public class LinkedHashMap<K,V>  extends HashMap<K,V> implements Map<K,V>

复制代码

继承了 HashMap 的特性，查询快+插入快，底层是数组+红黑树

基于对于 LinkedHashMap,我们可以看一下关于类的注释：

手写 LRU 算法步骤

创建初始最大的容量
通过对构造器初始化，创建初始容器
删除操作，（必要的）


import java.util.LinkedHashMap;import java.util.Map;
/** * @author lucas * @create 2021-08-09 19:53 * @description LRU算法的基础实现 */public class LRUCacheDemo<k, v> extends LinkedHashMap<k, v> {
    /**     * 1.确定初始容量     * 2.初始化构造器的，容量capacity     * 3.删除操作     */    private int capacity;  //最大容量

    public LRUCacheDemo(int capacity) {        /**         *  @param  initialCapacity the initial capacity         * @param  loadFactor      the load factor         * @param  accessOrder     the ordering mode - <tt>true</tt> for         *         access-order, <tt>false</tt> for insertion-order 访问顺序         */        super(capacity, 0.75F, false);        this.capacity = capacity;    }
    //    默认的构造方法基于，负载因子和顺序//    public LRUCacheDemo(int initialCapacity, float loadFactor, boolean accessOrder, int capacity) {//        super(initialCapacity, loadFactor, accessOrder);//        this.capacity = capacity;//    }
    //删除操作    @Override    protected boolean removeEldestEntry(Map.Entry<k, v> eldest) {        return super.size() > capacity;    }

    public static void main(String[] args) {

        LRUCacheDemo lruCacheDemo = new LRUCacheDemo(3);
        lruCacheDemo.put(1, "a");        lruCacheDemo.put(2, "b");        lruCacheDemo.put(3, "c");
        System.out.println(lruCacheDemo.keySet());
        lruCacheDemo.put(4, "d");        System.out.println("增加第四个后，列表是"+lruCacheDemo.keySet());
        /**         * [1, 2, 3]         * 增加第四个后，列表是[2, 3, 4]         * 解析： 当前第四个进来之后，4这个值将最近最少使用的直接踢出去         */
        System.out.println("--------------------------------------------");        lruCacheDemo.put(3, "d");        System.out.println(lruCacheDemo.keySet());        lruCacheDemo.put(3, "d");        System.out.println(lruCacheDemo.keySet());        lruCacheDemo.put(3, "d");        System.out.println(lruCacheDemo.keySet());
        /***         * [2, 4, 3]         * [2, 4, 3]         * [2, 4, 3]         * 最近一直使用的，3的值最频繁，放在最右侧         */        System.out.println("--------------------------------------------");        lruCacheDemo.put(5, "d");        System.out.println(lruCacheDemo.keySet());
        /**         * [4, 3, 5]         * 5,进入之后，直接将最少使用的2挤出去         */
        /**  访问顺序（accessOrder）为ture         * [1, 2, 3]         * 增加第四个后，列表是[2, 3, 4]         * --------------------------------------------         * [2, 4, 3]         * [2, 4, 3]         * [2, 4, 3]         * --------------------------------------------         * [4, 3, 5]         */```js

复制代码

    /**访问顺序（accessOrder）为false     * [1, 2, 3]     * 增加第四个后，列表是[2, 3, 4]     * --------------------------------------------     * [2, 3, 4]     * [2, 3, 4]     * [2, 3, 4]     * --------------------------------------------     * [3, 4, 5]     */}

复制代码

}

利用 Java 的集合，可以实现 LRU 的功能；

本质上：如何在有限的容器中，转载多变的数据；

LRU：最近访问最少的元素挑选出来

其中对于构造器中，需要注意的点，对于 accessOrder-代表访问顺序

* 访问顺序accessOreder* - true for access-order,* -false for insertion-order

复制代码

卢卡寄语

数据通过对于 LRU 中 LINKhashMap 的实现，是基于 hash+双向链表的集合，熟悉了 LRU 基本的工作机制，以及对于多个数据进入固定容器，如何筛选的过程，下期我们会根据数据的表现，提升一个段位，对于让你纯手写，不借助现成的集合方式，实现一个 LRU 的算法；你会如何写呢，答案我们揭晓

发布于: 11 小时前阅读数: 9

原文链接:【http://xie.infoq.cn/article/31357d4c6adc4c12da7fd723d】。文章转载请联系作者。

卢卡多多

关注

努力寻找生活答案的旅途者 2020.04.12 加入

公众号：卢卡多多，欢迎一起交流学习

发布

暂无评论

创作场景

缓存数据的淘汰之路（中）

话说上期

缓存淘汰策略

什么时候会遇见这个老头呢？

老头手里有秘笈

维度

四个方面

1.一般本地会用什么缓存淘汰策略呢？

2.如何修改缓存淘汰策略呢？

3.最近比较火缓存淘汰机制 LRU 思想是啥？

解析问题 1：

解析问题 2：

解析问题 3：

本质上

实例场景：

LRU 算法的思想：

卢卡寄语

LRU 算法

用 Java 中的数据结构写出 LRU 算法

手写 LRU 算法步骤

本质上： 如何在有限的容器中，转载多变的数据；

卢卡寄语

卢卡多多

评论

本质上：如何在有限的容器中，转载多变的数据；