Redis的常用淘汰策略以及算法实现

java1234

共 11127字,需浏览 23分钟

 ·

2021-03-20 10:13

点击上方蓝色字体,选择“标星公众号”

优质文章,第一时间送达

  作者 |  MXC肖某某

来源 |  urlify.cn/UFZjyu

76套java从入门到精通实战课程分享

一、Redis的内存配置

1,Redis配置内存为多少合适?

默认:如果不设置最大内存大小或者设置最大内存大小为0,在64为操作系统下不限制内存大小,在32位操作系统下最多使用3GB内存。

极限情况:留出一倍内存。比如你的redis数据占用了8G内存,那么你还需要再预留8G空闲内存。也就是内存需求是16G。内存占用率低于50%是最安全的。

普通情况:正常情况下,在序列化周期内,不会更改所有数据,只会有部分数据更改,那么,预留出可能产生的更改部分的空间,就行。如果实在要说一个数据的话,一般推荐Redis设置内存为最大物理内存的75%都是安全的。


2,如何修改内存

a)配置文件修改

  redis.conf中

#设置为100M,单位是byte
maxmemory  104857600

b)命令行修改

config set maxmemory 104857600

3,查看最大内存

config get maxmemory
#或者使用
info memory

4,如果Redis的内存你打满了会怎么样?

  


二、Redis的内存淘汰策略

1,Redis 过期策略是:定期删除+惰性删除。

  所谓定期删除,指的是 Redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key,检查其是否过期,如果过期就删除。

  假设 Redis 里放了 10w 个 key,都设置了过期时间,你每隔几百毫秒,就检查 10w 个 key,那 Redis 基本上就死了,cpu 负载会很高的,消耗在你的检查过期 key 上了。注意,这里可不是每隔 100ms 就遍历所有的设置过期时间的 key,那样就是一场性能上的灾难。实际上 Redis 是每隔 100ms 随机抽取一些 key 来检查和删除的。

  惰性删除:数据到达过期时间,不做处理。等下次访问该数据时,如果未过期,返回数据;发现已过期,删除,返回不存在。

  但是实际上这还是有问题的,如果定期删除漏掉了很多过期 key,然后你也没及时去查,也就没走惰性删除,此时会怎么样?如果大量过期 key 堆积在内存里,导致 Redis 内存块耗尽了,咋整?实际上会走:内存淘汰机制。


2,内存淘汰机制

Redis内存淘汰机制有以下几个:

  • noeviction: 当内存不足以容纳新写入数据时,新写入操作会报错,这个一般没人用吧,实在是太恶心了。

  • allkeys-lru:当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的 key(这个是最常用的)。

  • allkeys-random:当内存不足以容纳新写入数据时,在键空间中,随机移除某个 key,这个一般没人用吧,为啥要随机,肯定是把最近最少使用的 key 给干掉啊。

  • volatile-lru:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,移除最近最少使用的 key(这个一般不太合适)。

  • volatile-random:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,随机移除某个 key。

  • volatile-ttl:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,有更早过期时间的 key 优先移除。

  • allkeys-lfu: 对所有key使用LFU算法进行删除。LFU:最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。

  • volatile-lfu: 对所有设置了过期时间的key使用LFU算法进行删除。


三、手写LRU算法

1,采用LinkedHashMap实现

public class Demo015_LRUCacheLinkedHashMap {

    private int capacity;
    private LinkedHashMap<Integer, Integer> linkedHashMap;

    public Demo015_LRUCacheLinkedHashMap(int capacity) {
        this.capacity = capacity;
        /**
         * 三个参数:capacity为容量,0.75位扩容因子,true为按照访问排序false为按照插入排序
         *   重写删除尾结点的方法,一旦发现当前linkhashmap的长度大于总容量就需要删除*/
        linkedHashMap = new LinkedHashMap<Integer, Integer>(capacity,0.75F,true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return super.size() > capacity;
            }
        };
    }

    public void put(int key, int value) {
        linkedHashMap.put(key, value);
    }

    public int get(int key) {
        Integer value = linkedHashMap.getOrDefault(key,-1);
        return value;
    }
}

2,自定义双向链表

  • 定义Node节点:key,val,next和prev

  • 定义DoubleLinkedNode管理Node结点组成头尾结点的双向链表

  • 定义hashmap存储每个结点

  • 插入时判断当前值是否已经存在hashmap中

    • 如果存在就更改当前值,删除双向链表中原来的这个值,添加新值到链表头结点并修改hashmap中当前值

    • 如果不存在当前值,判断当前容器是否满了,如果满了就删除链表尾部删除hashmap中数据。并添加新结点到链表头部和hashmap中

  • 获取时,直接从hashmap中获取。如果不存在直接返回-1,如果存在就删除链表尾部数据,更新链表头部数据为当前node

public class Demo015_LRUCache {

    class Node<K, V> {
        K key;
        V val;
        Node next;
        Node prev;

        public Node(){
            next = prev = null;
        }

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
            next = prev = null;
        }
    }

    class DoubleLinkedNode<K,V>{
        Node head;
        Node tail;

        public DoubleLinkedNode() {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }

        public void addHead(Node<K,V> node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        public void remove(Node<K,V> node) {
            if (node.prev == null || node.next==null) {
                return;
            }
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
        }

        public Node<K,V> getLast() {
            if (tail.prev == head) {
                return null;
            }
            return tail.prev;
        }
    }

    private int capacity;
    private HashMap<Integer, Node<Integer,Integer>> hashMap;
    private DoubleLinkedNode<Integer, Integer> doubleLinkedNode;

    public Demo015_LRUCache(int capacity) {
        this.capacity = capacity;
        hashMap = new HashMap<>();
        doubleLinkedNode = new DoubleLinkedNode<>();
    }

    public int get(int key) {
        Node<Integer,Integer> node = hashMap.get(key);
        if (node == null) {
            return -1;
        }
        doubleLinkedNode.remove(node);
        doubleLinkedNode.addHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node<Integer, Integer> node = hashMap.get(key);
        if (node == null) { //没有添加过
            if (hashMap.size() == capacity) { //达到最大值状态
                //删除最后结点
                Node<Integer, Integer> last = doubleLinkedNode.getLast();
                doubleLinkedNode.remove(last);
                hashMap.remove(last.key);
            }
            //添加头结点
            node = new Node<>(key, value);
            hashMap.put(key,node);
            doubleLinkedNode.addHead(node);
        }else {
            //如果添加过,删除双向链表的该节点,将其修改值之后添加到头节点
            doubleLinkedNode.remove(node);
            node.val = value;

            doubleLinkedNode.addHead(node);
            hashMap.put(key, node);
        }
    }
}





粉丝福利:Java从入门到入土学习路线图

👇👇👇

👆长按上方微信二维码 2 秒


感谢点赞支持下哈 

浏览 31
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报