Redis缓存淘汰算法——LRU、LFU

快来打我* 2022-08-31 12:22 254阅读 0赞

[个人博客][Link 1]欢迎访问

> 总结不易，如果对你有帮助，请点赞关注支持一下  
> 微信搜索程序dunk，关注公众号，获取博客源码、数据结构与算法笔记（超级全）、大厂面试、笔试题

## Redis过期键的删除策略 ##

对于过期键一般的三种删除策略

*  定时删除：在设置键的过期时间的同时，创建一个定时器（timer），让定时器在键的过期时间来临时，立即执行对键的删除操作
 *  惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，那就返回该键
 *  定期删除：每过一段时间，程序就对数据库进行一次检查，删除里面的过期键。至于删除多少过期的键，以及检查多少个数据库，则由算法决定

三种策略优缺点

*  定时删除策略
    
     *  对内存是最友好的：通过使用定时器，定时删除策略可以保证过期键会尽可能快地被删除，并释放过期键所占的内存；
     *  但另一方面，定时删除策略的缺点是，它对CPU是最不友好的：在过期键比较多的情况下，将CPU时间用在删除和当前任务无关的过期键上，无疑对服务器的响应时间和吞吐量造成影响
 *  惰性删除策略
    
     *  惰性删除策略对CPU时间来说是友好的：程序只会在取出键时才对键进行过期检查是，这可以保证删除过期键的操作只会在非做不可的情况下进行
     *  惰性删除的缺点：它对内存是最不友好的：如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，他所占用的内存就不会被释放掉
 *  定时删除占用太多的CPU时间，影响服务器的响应时间和吞吐量；惰性删除浪费太多的内存，有内存泄漏的危险。定期删除策略是前两种策略的一种整合折中
    
     *  定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响
     *  通过定期删除过期键，定期删除策略有效地减少了因为过期键带来的内存浪费
     *  定期删除策略的难点是确定删除操作的执行时长和频率

问题来了：定期没删，也没查询，该怎么办？

## 内存淘汰机制 ##

*  noeviction:返回错误当内存限制达到并且客户端尝试执行会让更多内存被使用的命令（大部分的写入指令，但DEL和几个例外）
 *  allkeys-lru: 尝试回收最少使用的键（LRU），使得新添加的数据有空间存放。
 *  volatile-lru: 尝试回收最少使用的键（LRU），但仅限于在过期集合的键,使得新添加的数据有空间存放。
 *  allkeys-random: 回收随机的键使得新添加的数据有空间存放。
 *  volatile-random: 回收随机的键使得新添加的数据有空间存放，但仅限于在过期集合的键。
 *  volatile-ttl: 回收在过期集合的键，并且优先回收存活时间（TTL）较短的键,使得新添加的数据有空间存放。

如果没有键满足回收的前提条件的话，策略**volatile-lru**, **volatile-random**以及**volatile-ttl**就和noeviction 差不多了。

## [LRU][](最近最少使用算法) ##

/** * @author ：zsy * @date ：Created 2021/7/25 12:41 * @description：https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=190&&tqId=35214&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking */
    public class NC93设计LRU缓存结构 { 
        @Test
        public void test() { 
        }
    
    
        public class Solution { 
            /** * lru design * @param operators int整型二维数组 the ops * @param k int整型 the k * @return int整型一维数组 */
            public int[] LRU (int[][] operators, int k) { 
                // write code here
                LRUCache lruCache = new LRUCache(k);
                ArrayList<Integer> res = new ArrayList<>();
                for (int[] operator : operators) { 
                    if (operator[0] == 1) { 
                        lruCache.put(operator[1], operator[2]);
                    } else { 
                        res.add(lruCache.get(operator[1]));
                    }
                }
                int[] ans = new int[res.size()];
                for (int i = 0; i < res.size(); i++) { 
                    ans[i] = res.get(i);
                }
                return ans;
            }
    
            class LRUCache { 
                int capacity;
                Map<Integer, Node> map;
                DoubleList list;
    
                public LRUCache (int cap) { 
                    this.capacity = cap;
                    this.map = new HashMap<>();
                    this.list = new DoubleList();
                }
    
                /** * 添加缓存 * 如果map中包含当前key，则修改当前的val值，并将节点添加到链表头部 * 否则 * 如果双端链表的长度小于cap，直接添加到链表头部 * 否则，移除链表最后一个节点，添加到链表头部，删除map中的映射 * 最后，添加到map中 * @param key * @param val */
                public void put(int key, int val) { 
                    Node cur = new Node(key, val);
                    if(map.containsKey(key)) { 
                        list.remove(map.get(key));
                        list.addFirst(cur);
                    } else { 
                        if(list.size == capacity) { 
                            Node node = list.removeLast();
                            map.remove(node.key);
                        }
                        list.addFirst(cur);
                    }
                    map.put(key, cur);
                }
    
                /** * 如果map中不包含key，返回-1 * 否则，获取当前节点，删除当前节点（map、list），将节点添加到list头部 * @param key * @return */
                public int get(int key) { 
                    if(!map.containsKey(key)) return -1;
                    Node target = map.get(key);
                    list.remove(target);
                    list.addFirst(target);
                    return target.val;
                }
            }
    
            class Node { 
                int key, val;
                Node next, pre;
    
                public Node(int key, int val) { 
                    this.key = key;
                    this.val = val;
                }
    
                @Override
                public String toString() { 
                    return "Node{" +
                            "key=" + key +
                            ", val=" + val +
                            '}';
                }
            }
    
            class DoubleList { 
                Node head;
                Node tail;
                int size;
    
                public DoubleList() { 
                    head = new Node(-1, -1);
                    tail = new Node(-1, -1);
                    head.next = tail;
                    tail.pre = head;
                    size = 0;
                }
    
                public void addFirst(Node node) { 
                    node.next = head.next;
                    head.next = node;
                    node.next.pre = node;
                    node.pre = head;
                    size++;
                }
    
    
                public Node remove(Node node) { 
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                    size--;
                    return node;
                }
    
                public Node removeLast() { 
                    Node target = tail.pre;
                    tail.pre.pre.next = tail;
                    tail.pre = tail.pre.pre;
                    size--;
                    return target;
                }
    
                public void list() { 
                    Node temp = head.next;
                    while(temp != tail) { 
                        System.out.println(temp);
                        temp = temp.next;
                    }
                }
    
            }
        }
    }

找一个数据结构实现下Java版本的LRU还是比较容易的，知道啥原理就好了

使用LinkedHashMap版的LRU算法

/** * @author ：zsy * @date ：Created 2021/5/14 11:23 * @description：使用LinkedHashMap构建LRU页面置换算法 */
    public class LRULinkedHashMap { 
    
        public static void main(String[] args) { 
            LRUCache<Integer, Integer> lruCache = new LRUCache<>(3);
            lruCache.put(1,2);
            lruCache.put(2,2);
            lruCache.put(3,2);
            lruCache.get(2);
            //必须这样测试
            //否则会报ConcurrentModificationException异常
            Iterator<Map.Entry<Integer, Integer>> it = lruCache.entrySet().iterator();
            while(it.hasNext()) { 
                Map.Entry entry = it.next();
                System.out.println(entry.getKey() + " " + entry.getValue());
            }
            lruCache.put(4,3);
            lruCache.get(2);
            lruCache.put(4,5);
            it = lruCache.entrySet().iterator();
            while(it.hasNext()) { 
                Map.Entry entry = it.next();
                System.out.println(entry.getKey() + " " + entry.getValue());
            }
        }
    
        static class LRUCache<K, V> extends LinkedHashMap<K, V> { 
            private final int CACHE_SIZE;
    
            public LRUCache(int cacheSize) { 
                //true表示让hashmap按照访问顺序，最新访问的放在头部，最老访问的放在尾部
                super((int)Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true);
                this.CACHE_SIZE = cacheSize;
            }
    
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 
                //当map中数量大于指定缓存数量，就删除最老的数据
                return size() > CACHE_SIZE;
            }
        }
    
    }

## LFU(最不经常使用算法) ##

*  set(key, value)：将记录(key, value)插入该结构
 *  get(key)：返回key对应的value值

但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；

如果调用次数最少的key有多个，上次调用发生最早的key被删除

/** * @author ：zsy * @date ：Created 2021/7/25 13:31 * @description：https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1?tpId=190&&tqId=35215&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking */
    public class NC94LFU缓存结构设计 { 
        @Test
        public void test() { 
            Solution solution = new Solution();
        }
    
        public class Solution { 
            /** * lfu design * @param operators int整型二维数组 ops * @param k int整型 the k * @return int整型一维数组 */
            public int[] LFU (int[][] operators, int k) { 
                // write code here
                LFUCache lfuCache = new LFUCache(k);
                ArrayList<Integer> res = new ArrayList<>();
                for (int[] operator : operators) { 
                    if (operator[0] == 1) { 
                        lfuCache.put(operator[1], operator[2]);
                    } else { 
                        res.add(lfuCache.get(operator[1]));
                    }
                }
                int[] ans = new int[res.size()];
                for (int i = 0; i < res.size(); i++) { 
                    ans[i] = res.get(i);
                }
                return ans;
            }
    
            class LFUCache { 
                //容量
                int capacity;
                //map
                Map<Integer, Node> map;
                //双向链表
                DoubleList list;
    
                public LFUCache(int capacity) { 
                    this.capacity = capacity;
                    map = new HashMap<>();
                    list = new DoubleList();
                }
    
                /** * 1、已经存在key * -覆盖val，frequency++ * -删除链表中的节点，重新加入 * 2、不存在 * -达到了最大容量 * 删除链表第一个元素，执行插入操作 * -未达到 * 直接插入节点 * @param key * @param val */
                public void put(int key, int val) { 
                    if (map.containsKey(key)) { 
                        Node node = map.get(key);
                        list.remove(node);
                        node.val = val;
                        node.frequency++;
                        map.put(key, node);
                        list.add(node);
                    } else { 
                        Node cur = new Node(key, val, 1);
                        if (list.size >= capacity) { 
                            Node node = list.removeFirst();
                            map.remove(node.key);
                        }
                        list.add(cur);
                        map.put(key, cur);
                    }
                }
    
                /** * 获取val，frequency++，链表重新赋值 * @param key * @return */
                public int get(int key) { 
                    if (!map.containsKey(key)) return -1;
                    Node node = map.get(key);
                    list.remove(node);
                    node.frequency++;
                    list.add(node);
                    return node.val;
                }
            }
    
            //双向链表
            class DoubleList { 
                //头尾指针
                Node head, tail;
                //节点数量
                int size;
    
                public DoubleList() { 
                    this.head = new Node(-1, -1, -1);
                    this.tail = new Node(-1, -1, Integer.MAX_VALUE);
                    head.next = tail;
                    tail.pre = head;
                    size = 0;
                }
    
                /** * 删除节点 * @param node * @return */
                private Node remove(Node node) { 
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                    size--;
                    return node;
                }
    
                /** * 添加节点，并且维护链表顺序 * -频次升序 * -相同频次，按操作时间早->晚排序（方便删除） * @param node */
                private void add(Node node) { 
                    Node temp = head;
                    while (node.frequency >= temp.next.frequency) { 
                        temp = temp.next;
                    }
                    node.next = temp.next;
                    temp.next.pre = node;
                    temp.next = node;
                    node.pre = temp;
                    size++;
                }
    
                /** * 删除第一个节点，即调用次数最少，且调用发生最早 * @return */
                private Node removeFirst() { 
                    Node tar = head.next;
                    head.next = tar.next;
                    tar.next.pre = head;
                    size--;
                    return tar;
                }
    
                /** * 展示列表，测试使用 */
                private void list() { 
                    Node temp = head.next;
                    while (temp != null && temp != tail) { 
                        System.out.println(temp);
                        temp = temp.next;
                    }
                }
            }
    
            //Node存放K-V值和当前节点操作的频次
            class Node { 
                private int key, val, frequency;
                Node pre, next;
    
                public Node(int key, int val, int frequency) { 
                    this.key = key;
                    this.val = val;
                    this.frequency = frequency;
                }
            }
        }
    }

[Link 1]: http://www.dunkcode.cn
[LRU]: https://blog.csdn.net/qq_35190492/article/details/103041932?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162055059816780366543961%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=162055059816780366543961&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v2~rank_v29-3-103041932.nonecase&utm_term=Redis