Redis的键过期策略、内存淘汰机制与LRU实现，这一篇给你安排了！

怼烎@ 2022-12-02 13:43 116阅读 0赞

## 过期策略 ##

> 面试官：你了解Redis的键过期策略吗？
> 
> 我：不了解
> 
> 面试官：（出门右拐，顺便把门口的垃圾带走）那让你来设计一个过期策略，你怎么去实现
> 
> 我：简单啊，给每个有过期时间的key绑定一个定时器就好了

### 定时器删除策略 ###

给每个有过期时间的key绑定一个定时器，时间一到，立马将该key从内存中删除。

优点：及时删除，有效解决了内存被过期key大量占用的问题。

缺点：大量占用CPU时间片，干不了正事，一直忙着删除过期key，解决不了大量占用cpu的问题。

> 面试官：既然定时器策略十分占用cpu，会导致redis查询缓慢，还有别的想法吗？
> 
> 我：反正最终的效果，只是用户获取不到过期的key，那只要在获取的时候，判断一下是否过期就行了。

### 惰性删除策略 ###

当key过期时间来临时，不作任何处理。只在获取该key时，判断是否过期，过期了则删除key，并且返回null；否则返回该key的值。

优点：不会大量占用CPU，Redis可以将大部分精力放在查询上。

缺点：如果用户一直不获取key，那么该过期的key就会一直存放在内存中，相当于内存泄漏。

> 面试官：惰性删除确实方便简单，但这十分浪费内存。还有别的想法吗？
> 
> 我：或者只起一个定时任务，定时扫描redis中所有有过期时间的key。

### 定期删除 ###

起一个全局的定时任务，定时扫描redis中所有有过期时间的key。但是为了保证不影响其他的业务，给这个定时任务设置执行时间与频率。

当这个定时任务的第一次执行到达了时间限制后，停止执行，下次执行的开始点就是上一次的终点。

当然Redis中存在大量的key，不可能扫描所有有过期时间的key，不然全部扫一遍的总耗时将十分漫长。

优点：在设置执行时间与频率后，不会影响其他业务。

缺点：如果扫描全部key，则依然存在内存泄漏的风险。如果每次扫描随机选取几个key，则会存在漏网之鱼。

--------------------

### Redis采用的过期策略 ###

Redis综合以上3种策略的优缺点，最终采取的策略是惰性删除+定期删除。

对于定期删除：redis每隔指定的时间，扫描即将要过期的key。值得注意的是，这里的扫描并不是扫描全部带有过期时间的key，更像是一种抽查。

首先循环每一个库，随机抽查其中带有过期时间的key，若过期的key占的比例超过某一个阈值，则继续抽查，一直到小于阈值的时候，才前往下一个库进行扫描。

redis默认的执行时间为25ms，超过这个时间后，只能等待下一次扫描继续处理剩余的任务。redis每隔100ms触发一次扫描任务。

下面使用java代码，简要描述一下定期删除的原理

package com.qcy.testRedis;
    
    import lombok.Data;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.stream.Collectors;
    
    /**
     * @author qcy
     * @create 2020/08/31 17:03:22
     */
    public class Main {
    
        /**
         * Redis库的总数
         */
        public static final int DB_SUM = 16;
        /**
         * 当前扫描的库的索引
         */
        public static int CURRENT_SCAN_DB_INDEX = 0;
        /**
         * 随机抽查的key的数量
         */
        public static final int RANDOM_KEY_SUM = 20;
        /**
         * 过期key占抽查总数的阈值
         */
        public static final int EXPIRE_TIME_THRESHOLD = RANDOM_KEY_SUM / 4;
    
        /**
         * 单次扫描的最大执行时间，单位ms
         */
        public static final int MAX_SCAN_TIME = 25;
    
        public static void main(String[] args) {
            //开始时间
            long startTime = System.currentTimeMillis();
    
            //如果全部扫描完，则开启新一轮
            if (CURRENT_SCAN_DB_INDEX == DB_SUM) {
                CURRENT_SCAN_DB_INDEX = 0;
            }
    
            for (int i = CURRENT_SCAN_DB_INDEX; i < DB_SUM; i++) {
                //main方法执行耗时最大为25ms,当然这用写是有问题的，这里只是做一个演示
                long currentTime = System.currentTimeMillis();
                if (currentTime - startTime >= MAX_SCAN_TIME) return;
            }
    
            //当前扫描的库
            RedisDB db = get(CURRENT_SCAN_DB_INDEX);
    
            while (true) {
                //获取有过期时间的key的总数
                int sum = db.getSumKeyWithExpireTime();
                if (sum == 0) {
                    break;
                }
    
                //默认随机找出20个
                List<RedisKey> keyList = db.getRandomKeyWithExpireTime();
                //找出其中已经过期的key,删除并且记录总数
                List<RedisKey> expireKeyList = keyList.stream().filter(RedisKey::isExpire).collect(Collectors.toList());
                long expireCount = expireKeyList.size();
                //删除key
                expireKeyList.forEach(k -> db.delete(k.getName()));
    
                //如果过期key的数量不大于随机的key总数的1/4，即小于5个后，则换一个库
                if (expireCount <= EXPIRE_TIME_THRESHOLD) {
                    break;
                }
            }
    
            CURRENT_SCAN_DB_INDEX++;
        }
    
    }

定期删除，难免会有漏网之鱼的存在。因此，最后一道防线则是利用惰性删除。

定期删除结合惰性删除，听起来确实很不错。但是，那些经历过定期删除仍然存活的过期key，倘若一直没有被查询过，就会一直存放在内存中，称为老赖。

清除这些老赖，就要谈到内存淘汰机制。

--------------------

## 内存淘汰机制 ##

主要有以下机制：

*  noeviction：         当内存不足时，写入操作会直接报错（这个确实很简单粗暴）
 *  allkeys-lru：         当内存不足时，删除最近最少使用的key
 *  allkeys-random： 当内存不足时，随机删除某些key
 *  allkeys-lfu:            当内存不足时，删除那些最近访问频率最低的key
 *  volatile-lru：         当内存不足时，删除最近最少使用的带有过期时间的key
 *  volatile-random： 当内存不足时，随机删除某些带有过期时间的key
 *  volatile-ttl：          当内存不足时，删除最快过期的key
 *  volatile-lfu:            当内存不足时，删除那些最近访问频率最低的带有过期时间的key

其中redis在4.0中引进的LFU策略，即淘汰最近访问频率较低的key，LFU比LRU更加精确地表示了key被关注的热度。如果有一个key刚被访问过了，LRU策略认为这个key最不可能删除的；而LFU策略需要追踪这一段时间内该key的访问频率，仅仅被访问一次，不足以让该key变得很热，在LFU策略下，还是很容易删除该key的。

查看redis默认的淘汰策略，可以使用以下命令：

config get maxmemory-policy

使用以下命令设置redis的淘汰策略为volatile-lfu：

config set maxmemory-policy volatile-lfu

--------------------

## 你说了这么多，来手写个LRU吧 ##

> 我：LinkedHashMap天然支持LRU，仅仅需要传入特定的参数就可以实现

详细的过程可以参考这篇文章[使用LinkedHashMap实现一个简易的LRU缓存][LinkedHashMap_LRU]

> 面试官：那你使用LinkedList与HashMap实现LRU
> 
> 我：你说什么，我没听见

使用LinkedList来保存key的顺序，使用HashMap来保存key对应的value。

仅仅只操作LinkedList头尾部的元素，因此时间复杂度为O(1)，由key在HashMap中获取value的时间复杂度也为O(1)。

package com.yang.testLRU;
    
    import java.util.HashMap;
    import java.util.LinkedList;
    
    public class Main {
    
        static class LRUCache {
            //维护位置的LinkedList,set()的时间复杂度O(n),但如果只操作头尾元素，则时间复杂度为O(1)
            private LinkedList<Integer> list;
            //维护键值的HashMap,get()的时间复杂度O(1)
            private HashMap<Integer, Integer> map;
            //缓存的容量
            private int capacity;
    
    
            public LRUCache(int capacity) {
                this.list = new LinkedList<>();
                this.map = new HashMap<>();
                this.capacity = capacity;
            }
    
            private Integer get(Integer key) {
                if (map.get(key) == null) {
                    //说明缓存中没有该key
                    return null;
                }
                //缓存中有该key,则先将该key在链表中删除，再移动到链表的尾部，从而保证头部是最近最久未使用的元素
                list.remove(key);
                list.offer(key);
                return map.get(key);
            }
    
            private void put(Integer key, Integer value) {
                if (map.get(key) != null) {
                    //说明缓存中有该key,先在链表中删除，再移动到尾部
                    list.remove(key);
                    list.offer(key);
                } else {
                    //说明缓存中没有该key,需要往缓存中插入
                    if (list.size() == capacity) {
                        //说明缓存已经满了
                        //删除链表头部元素
                        Integer head = list.poll();
                        //删除键值対
                        map.remove(head);
                    }
                    //此时缓存没满，或刚删除了头部元素
                    list.offer(key);
                }
                //插入map或刷新vaule
                map.put(key, value);
            }
    
            //输出链表元素
            private void print() {
                for (int i = list.size() - 1; i >= 0; i--) {
                    System.out.print(list.get(i) + " ");
                }
            }
    
        }
    
        public static void main(String[] args) {
            //假设内存容量只能存下4个数
            LRUCache cache = new LRUCache(4);
            cache.put(1, 1);
            cache.put(2, 2);
            cache.put(3, 3);
            cache.put(4, 4);
            cache.print();
            System.out.println();
    
            cache.get(1);
            cache.print();
            System.out.println();
    
            cache.put(5, 5);
            cache.print();
            System.out.println();
    
            cache.get(3);
            cache.print();
        }
    
    }

输出如下：

![20200831150610658.png][]

[LinkedHashMap_LRU]: https://blog.csdn.net/Apeopl/article/details/90137398
[20200831150610658.png]: /images/20221123/0939f4d202c949d09acf545acb1ddff8.png