您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis:缓存被我写满了,该怎么办?

时间:2021-02-01 15:23:23  来源:  作者:
Redis:缓存被我写满了,该怎么办?

 

介绍

Redis:缓存被我写满了,该怎么办?

 

redis是一个内存数据库,当Redis使用的内存超过物理内存的限制后,内存数据会和磁盘产生频繁的交换,交换会导致Redis性能急剧下降。所以在生产环境中我们通过配置参数maxmemoey来限制使用的内存大小。

当实际使用的内存超过maxmemoey后,Redis提供了如下几种可选策略。

noeviction:写请求返回错误

volatile-lru:使用lru算法删除设置了过期时间的键值对 volatile-lfu:使用lfu算法删除设置了过期时间的键值对 volatile-random:在设置了过期时间的键值对中随机进行删除 volatile-ttl:根据过期时间的先后进行删除,越早过期的越先被删除

allkeys-lru:在所有键值对中,使用lru算法进行删除 allkeys-lfu:在所有键值对中,使用lfu算法进行删除 allkeys-random:所有键值对中随机删除

我们来详细了解一下lru和lfu算法,这是2个常见的缓存淘汰算法。「因为计算机缓存的容量是有限的,所以我们要删除那些没用的数据,而这两种算法的区别就是判定没用的纬度不一样。」

LRU算法

「lru(Least recently used,最近最少使用)算法,即最近访问的数据,后续很大概率还会被访问到,即是有用的。而长时间未被访问的数据,应该被淘汰」

lru算法中数据会被放到一个链表中,链表的头节点为最近被访问的数据,链表的尾节点为长时间没有被访问的数据

Redis:缓存被我写满了,该怎么办?

 

「lru算法的核心实现就是哈希表加双向链表」。链表可以用来维护访问元素的顺序,而hash表可以帮我们在O(1)时间复杂度下访问到元素。

「至于为什么是双向链表呢」?主要是要删除元素,所以要获取前继节点。数据结构图示如下

Redis:缓存被我写满了,该怎么办?

 

使用双向链表+HashMap

双向链表节点定义如下

public class ListNode<K, V> {
    K key;
    V value;
    ListNode pre;
    ListNode next;

    public ListNode() {}

    public ListNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

封装双向链表的常用操作

public class DoubleList {

    private ListNode head;
    private ListNode tail;

    public DoubleList() {
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.pre = head;
    }

    public void remove(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void addLast(ListNode node) {
        node.pre = tail.pre;
        tail.pre = node;
        node.pre.next = node;
        node.next = tail;
    }

    public ListNode removeFirst() {
        if (head.next == tail) {
            return null;
        }
        ListNode first = head.next;
        remove(first);
        return first;
    }
}

封装一个缓存类,提供最基本的get和put方法。「需要注意,这两种基本的方法都涉及到对两种数据结构的修改」

public class MyLruCache<K, V> {

    private int capacity;
    private DoubleList doubleList;
    private Map<K, ListNode> map;

    public MyLruCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        doubleList = new DoubleList();
    }

    public V get(Object key) {
        ListNode<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        // 先删除该节点,再接到尾部
        doubleList.remove(node);
        doubleList.addLast(node);
        return node.value;
    }

    public void put(K key, V value) {
        // 直接调用这边的get方法,如果存在,它会在get内部被移动到尾巴,不用再移动一遍,直接修改值即可
        if ((get(key)) != null) {
            map.get(key).value = value;
            return;
        }

        // 如果超出容量,把头去掉
        if (map.size() == capacity) {
            ListNode listNode = doubleList.removeFirst();
            map.remove(listNode.key);
        }

        // 若不存在,new一个出来
        ListNode node = new ListNode(key, value);
        map.put(key, node);
        doubleList.addLast(node);
    }
}

这里我们的实现为最近访问的放在链表的尾节点,不经常访问的放在链表的头节点

测试一波,输出为链表的正序输出(代码为了简洁没有贴toString方法)

MyLruCache<String, String> myLruCache = new MyLruCache<>(3);
// {5 : 5}
myLruCache.put("5", "5");
// {5 : 5}{3 : 3}
myLruCache.put("3", "3");
// {5 : 5}{3 : 3}{4 : 4}
myLruCache.put("4", "4");
// {3 : 3}{4 : 4}{2 : 2}
myLruCache.put("2", "2");
// {4 : 4}{2 : 2}{3 : 3}
myLruCache.get("3");

「因为LinkedHashMap的底层实现就是哈希表加双向链表,所以你可以用LinkedHashMap替换HashMap和DoubleList来改写一下上面的类」

我来演示一下更骚的操作,只需要重写一个构造函数和removeEldestEntry方法即可。

使用LinkedHashMap实现LRU

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;


    public LruCache(int cacheSize) {
        /**
         * initialCapacity: 初始容量大小
         * loadFactor: 负载因子
         * accessOrder: false基于插入排序(默认),true基于访问排序
         */
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    /**
     * 当调用put或者putAll方法时会调用如下方法,是否删除最老的数据,默认为false
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

注意这个缓存并不是线程安全的,可以调用Collections.synchronizedMap方法返回线程安全的map

LruCache<String, String> lruCache = new LruCache(3);
Map<String, String> safeMap = Collections.synchronizedMap(lruCache);

Collections.synchronizedMap实现线程安全的方式很简单,只是返回一个代理类。代理类对Map接口的所有方法加锁

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

LFU算法

「LRU算法有一个问题,当一个长时间不被访问的key,偶尔被访问一下后,可能会造成一个比这个key访问更频繁的key被淘汰。」

即LRU算法对key的冷热程度的判断可能不准确。而LFU算法(Least Frequently Used,最不经常使用)则是按照访问频率来判断key的冷热程度的,每次删除的是一段时间内访问频率较低的数据,比LRU算法更准确。

使用3个hash表实现lfu算法

那么我们应该如何组织数据呢?

为了实现键值的对快速访问,用一个map来保存键值对

private HashMap<K, Integer> keyToFreq;

还需要用一个map来保存键的访问频率

private HashMap<K, Integer> keyToFreq;

「当然你也可以把值和访问频率封装到一个类中,用一个map来替代上述的2个map」

接下来就是最核心的部分,删除访问频率最低的数据。

  1. 为了能在O(1)时间复杂度内找到访问频率最低的数据,我们需要一个变量minFreq记录访问最低的频率
  2. 每个访问频率有可能对应多个键。当空间不够用时,我们要删除最早被访问的数据,所以需要如下数据结构,Map<频率, 有序集合>。每次内存不够用时,删除有序集合的第一个元素即可。并且这个有序集合要能快速删除某个key,因为某个key被访问后,需要从这个集合中删除,加入freq+1对应的集合中
  3. 有序集合很多,但是能满足快速删除某个key的只有set,但是set插入数据是无序的。「幸亏JAVA有LinkedHashSet这个类,链表和集合的结合体,链表不能快速删除元素,但是能保证插入顺序。集合内部元素无序,但是能快速删除元素,完美」

下面就是具体的实现。

public class LfuCache<K, V> {

    private HashMap<K, V> keyToVal;
    private HashMap<K, Integer> keyToFreq;
    private HashMap<Integer, LinkedHashSet<K>> freqTokeys;

    private int minFreq;
    private int capacity;

    public LfuCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqTokeys = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 0;
    }

    public V get(K key) {
        V v = keyToVal.get(key);
        if (v == null) {
            return null;
        }
        increaseFrey(key);
        return v;
    }

    public void put(K key, V value) {
        // get方法里面会增加频次
        if (get(key) != null) {
            // 重新设置值
            keyToVal.put(key, value);
            return;
        }

        // 超出容量,删除频率最低的key
        if (keyToVal.size() >= capacity) {
            removeMinFreqKey();
        }

        keyToVal.put(key, value);
        keyToFreq.put(key, 1);
        // key对应的value存在,返回存在的key
        // key对应的value不存在,添加key和value
        freqTokeys.putIfAbsent(1, new LinkedHashSet<>());
        freqTokeys.get(1).add(key);
        this.minFreq = 1;
    }

    // 删除出现频率最低的key
    private void removeMinFreqKey() {
        LinkedHashSet<K> keyList = freqTokeys.get(minFreq);
        K deleteKey = keyList.iterator().next();
        keyList.remove(deleteKey);
        if (keyList.isEmpty()) {
            // 这里删除元素后不需要重新设置minFreq
            // 因为put方法执行完会将minFreq设置为1
            freqTokeys.remove(keyList);
        }
        keyToVal.remove(deleteKey);
        keyToFreq.remove(deleteKey);
    }

    // 增加频率
    private void increaseFrey(K key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqTokeys.get(freq).remove(key);
        freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqTokeys.get(freq + 1).add(key);
        if (freqTokeys.get(freq).isEmpty()) {
            freqTokeys.remove(freq);
            // 最小频率的set为空,key被移动到minFreq+1对应的set了
            // 所以minFreq也要加1
            if (freq == this.minFreq) {
                this.minFreq++;
            }
        }
    }
}

测试一下

LfuCache<String, String> lfuCache = new LfuCache(2);
lfuCache.put("1", "1");
lfuCache.put("2", "2");
// 1
System.out.println(lfuCache.get("1"));
lfuCache.put("3", "3");
// 1的频率为2,2和3的频率为1,但2更早之前被访问,所以被清除
// 结果为null
System.out.println(lfuCache.get("2"));


Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Tags: Redis  点击:(16)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  Tags: Redis  点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  Tags: Redis  点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  Tags: Redis  点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: Redis  点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  Tags: Redis  点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: Redis  点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  Tags: Redis  点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  Tags: Redis  点击:(77)  评论:(0)  加入收藏
Nginx来限制访问控制的方法有多种,nginx主要有2个模块控制,但是那些不支持自定义,非常死,在大多数场景下并不实用。今天分享一个:利用openresty+lua+redis 实现封杀频繁恶意访问I...【详细内容】
2021-08-12  Tags: Redis  点击:(118)  评论:(0)  加入收藏
▌简易百科推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Java识堂    Tags:Redis   点击:(16)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  富集云科技有限公司    Tags:Redis   点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  弈秋的美好生活    Tags:redis   点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  川石信息    Tags:Redis   点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  JavaEdge    Tags:Redis   点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  faesuite    Tags:Redis   点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  语霖    Tags:Redis   点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  深夜敲代码    Tags:Redis   点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  小李说IT    Tags:Redis   点击:(77)  评论:(0)  加入收藏
当查询Redis中没有的数据时,该查询会下沉到数据库层,同时数据库层也没有该数据,当这种情况大量出现或被恶意攻击时,接口的访问全部透过Redis访问数据库,而数据库中也没有这些数据...【详细内容】
2021-07-30  随便t    Tags:缓存穿透   点击:(90)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条