关于redis 超过最大内存限制，触发淘汰策略说明

Love The Way You Lie 2021-10-09 09:18 194阅读 0赞

# 内存清理策略
    # volatile-lru -> 对所有设置了过期时间的key使用lru算法进行删除
    # allkeys-lru -> 对所有key使用lru算法进行删除
    # volatile-lfu -> 对所有设置了过期时间的key使用lfu算法进行删除
    # allkeys-lfu -> 对所有key使用lfu算法进行删除
    # volatile-random -> 对所有设置了过期时间的key使用随机算法进行删除
    # allkeys-random -> 对所有key使用随机算法进行删除
    # volatile-ttl -> 删除马上要过期的key
    # noeviction -> 永不过期，不会删除任何key

默认：6.0.8版本淘汰策略是：noeviction，只要没有被动过期，就不会主动过期，这是默认的淘汰策略。

1.一般不建议使用随机：random，因为不怎么科学删除；如果存在热点key被清除了，那么缓存击穿、穿透，就会有问题；

2.那么什么是LRU算法、LFU算法呢？

讲故事说明：

如果说一个老奶奶，有三个儿子；然后大儿子，在最近一年内都没有回来过，那么就可以认为这个儿子不合格，那么就可以认为这个大儿子，在接下来的日子也是不会回来的，就断绝母子关系了，这就是LRU算法，在最近的一段时间内一直都没有被访问到这个KEY；那么就会认为这个KEY在之后也不会被访问到了，那么就会被淘汰；

那么二儿子，在最近一年内就回来过一次，那么就可以认为这个二儿子，在接下来的日子也是不会回来的，就断绝母子关系了，这就是LFU算法，在最近的一段时间内很少访问到这个KEY；那么就会认为这个KEY在之后也不会被访问到了，那么就会被淘汰；

（举例不是很形象，但是是那么个意思）

那么举其他例子呢？就好比，我们的手机的进程内存，要知道，我们的手机内存是优先的，会经常碰到一个问题就是，杀进程。假设我们的手机内存是8G，那也会有上限；

那么这个使用就会有过期淘汰进程了。

关于这个LRU算法，那么我们就需要设计一个算法来讨论一下：

链表 + Hash;

链表是控制优先级顺序，Hash控制是快速定位到具体的内容

1.巧妙使用LinkedHashMap实现（jdk支持api）

public class LruDemo extends LinkedHashMap {
    
        private final int capacity;
    
        /**
         * 构造
         *
         * @param capacity    最大容量
         * @param accessOrder 排序规则：true=最近热点数据  false=首次进入规则
         */
        public LruDemo(int capacity, boolean accessOrder) {
            super(capacity, 0.75F, accessOrder);
            this.capacity = capacity;
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return super.size() > capacity;
        }
    }

那么测试

public static void main(String[] args) {
            LruDemo lruDemo = new LruDemo(3, true);
    
            lruDemo.put("1", "1");
            lruDemo.put("2", "1");
            lruDemo.put("3", "1");
            System.out.println(lruDemo.keySet());
    
            lruDemo.put("2", "1");
            System.out.println(lruDemo.keySet());
    
            lruDemo.put("5", "1");
            System.out.println(lruDemo.keySet());
    
            lruDemo.put("2", "1");
            System.out.println(lruDemo.keySet());
            lruDemo.put("2", "1");
            System.out.println(lruDemo.keySet());
            lruDemo.put("2", "1");
            System.out.println(lruDemo.keySet());
    
    
            lruDemo.put("6", "1");
            System.out.println(lruDemo.keySet());
    
        }

结果如下：

![20201213144502655.png][]

看看实现源码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjIzNjg4_size_16_color_FFFFFF_t_70][]

翻译一下：

一个特殊的\{@link \#LinkedHashMap（int，float，boolean）构造函数\}是提供以创建链接的哈希图，其迭代顺序为顺序上次访问其条目的时间，从最近到最近（<i>访问顺序</i>）。这种地图非常适合建立LRU缓存。

官方文档都说明了LRU的实现原理，那么想知道LRU算法如何实现，那么就看看LinkedHashMap结构把。

2.手动构造 双向链表 + HASH散列 O（1）

其中Map用于定位，linked为双向链表，维护出队，入头位；

public class LruDemo2 {
    
        private int cacheSize;
    
        private Map<Integer, Node<Integer, Integer>> map;
    
        private DoubleLinkedList<Integer, Integer> linked;
    
        static class Node<K, V> {
    
            private K key;
            private V value;
    
            private Node<K, V> prev;
            private Node<K, V> next;
    
            public Node() {
                this.key = null;
                this.value = null;
                this.prev = this.next = null;
            }
    
            public Node(K key, V value) {
                this.key = key;
                this.value = value;
                this.prev = this.next = null;
            }
        }
    
        static class DoubleLinkedList<K, V> {
            /**
             * 这个两个节点为虚拟节点，无实际意义
             */
            private Node<K, V> head;
            private Node<K, V> tail;
    
            public DoubleLinkedList() {
                this.head = new Node<>();
                this.tail = new Node<>();
    
                //构造头节点的 后驱现在 是 尾节点
                this.head.next = tail;
                //构造尾节点点的 前置现在 是 头节点
                 this.tail.prev = head;
    
            }
    
            /**
             * 新增节点
             *
             * @param node
             */
            public void addNode(Node<K, V> node) {
                //将当前节点的后驱指向头结点的后驱
                node.next = this.head.next;
                //将节点的前驱指向头结点
                node.prev = this.head;
    
                //当前头结点的后驱的前驱指向为当前节点
                this.head.next.prev = node;
                //当前头结点的后驱指向当前节点
                this.head.next = node;
    
                // 双向绑定
            }
    
            /**
             * 删除节点
             *
             * @param node
             */
            public void removeNode(Node<K, V> node) {
                //将当前节点的前驱的后驱指向当前节点的后驱
                node.prev.next = node.next;
                //将当前节点的后驱的前驱指向当前节点的前驱
                node.next.prev = node.prev;
    
                //将当前节点前后脱离
                node.prev = null;
                node.next = null;
            }
    
            /**
             * 获取最后一个节点
             *
             * @return
             */
            public Node<K, V> getLastNode() {
                return this.tail.prev;
            }
    
        }
    
        public LruDemo2(int cacheSize) {
            this.cacheSize = cacheSize;
            this.map = new HashMap<>(cacheSize);
            this.linked = new DoubleLinkedList<>();
        }
    
        /**
         * 获取节点
         *
         * @param key
         * @return
         */
        public int getKey(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node<Integer, Integer> node = map.get(key);
    
            //将该节点活跃前置
            this.linked.removeNode(node);
            this.linked.addNode(node);
            return node.value;
        }
    
        /**
         * 新增节点
         *
         * @param key
         * @param value
         */
        public void put(int key, int value) {
            //判断之前是否存在
            Node<Integer, Integer> node;
            if (this.map.containsKey(key)) {
                node = this.map.get(key);
                this.linked.removeNode(node);
            } else {
                //校验当前链表长度
                if (this.map.size() == this.cacheSize) {
                    Node<Integer, Integer> lastNode = this.linked.getLastNode();
                    this.linked.removeNode(lastNode);
                    this.map.remove(lastNode.key);
                }
    
                node = new Node<>(key, value);
                this.map.put(key, node);
            }
            this.linked.addNode(node);
        }
    }

执行算法

public class LruDemo2 {
        public static void main(String[] args) {
            LruDemo2 lruDemo = new LruDemo2(3);
    
            lruDemo.put(1, 1);
            lruDemo.put(2, 1);
            lruDemo.put(3, 1);
            System.out.println(lruDemo.map.keySet());
    
            lruDemo.put(2, 1);
            System.out.println(lruDemo.map.keySet());
    
            lruDemo.put(5, 1);
            System.out.println(lruDemo.map.keySet());
    
    
    
            lruDemo.put(6, 1);
            System.out.println(lruDemo.map.keySet());
    
        }
    
    }

结果

![20201213155652964.png][]

总结：LRU算法，是一种 活跃淘汰算法，按照链表实现，可以使用Hash快速查找、通过双向链表绑定，进行活跃前置，不活跃则解除可达性引用，被GC；那么我们上述没有实现get，最近使用前置，但是算法中已经实现了。原理是一样的，当该key被使用，那么我们将该node先解绑、再重新绑定前置；LRU算法，就是一种最近未使用淘汰算法；

LFU算法就是一种最近不怎么使用的淘汰算法；

两者区别为：LRU针对时间角度进行淘汰（最新数据）；LFU为针对使用频率进行淘汰（热点数据）；

各有千秋，针对业务的不同，那么我们将使用不同的淘汰算法（笔者使用的是 “对设置过过期时间的KEY进行 热点数据 淘汰算法”）

[20201213144502655.png]: /images/20211009/35649a6669984774aeda296d36e2f7ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjIzNjg4_size_16_color_FFFFFF_t_70]: /images/20211009/d6cb327b4b3741f5a7eafc8364058de8.png
[20201213155652964.png]: /images/20211009/47342b1debbb496982feac12170d8343.png