大家好，欢迎来到IT知识分享网。

过期策略

面试官：你了解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++;
    }

}

IT知识分享网

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

定期删除结合惰性删除，听起来确实很不错。但是，那些经历过定期删除仍然存活的过期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默认的淘汰策略，可以使用以下命令：

IT知识分享网config get maxmemory-policy

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

config set maxmemory-policy volatile-lfu

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

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

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

面试官：那你使用LinkedList与HashMap实现LRU

我：你说什么，我没听见

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

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

IT知识分享网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();
    }

}

输出如下：