【大厂面试02期】Redis过期key是怎么样清理的？

PS:本文已收录到1.1K Star数开源学习指南——《大厂面试指北》，如果想要了解更多大厂面试相关的内容及获取《大厂面试指北》离线PDF版，请扫描下方二维码码关注公众号“大厂面试”，谢谢大家了！项目地址：http://notfound9.github.io/interviewGuide/#/docs/BATInterview

《大厂面试指北》项目截图：

image

获取《大厂面试指北》离线PDF版，请扫描下方二维码关注公众号“大厂面试”

image

【大厂面试02期】Redis过期key是怎么样清理的？

在Redis中，对于过期key的清理主要有惰性清除，定时清理，内存不够时清理三种方法，下面我们就来具体看看这三种清理方法。

(1)惰性清除

在访问key时，如果发现key已经过期，那么会将key删除。

(2)定时清理

Redis配置项hz定义了serverCron任务的执行周期，默认每次清理时间为25ms，每次清理会依次遍历所有DB，从db随机取出20个key，如果过期就删除，如果其中有5个key过期，那么就继续对这个db进行清理，否则开始清理下一个db。

(3)内存不够时清理

当执行写入命令时，如果发现内存不够，那么就会按照配置的淘汰策略清理内存，淘汰策略一般有6种，Redis4.0版本后又增加了2种，主要由分为三类

第一类不处理，等报错(默认的配置)
- noeviction，发现内存不够时，不删除key，执行写入命令时直接返回错误信息。（Redis默认的配置就是noeviction）
第二类从所有结果集中的key中挑选，进行淘汰
- allkeys-random 就是从所有的key中随机挑选key，进行淘汰
- allkeys-lru 就是从所有的key中挑选最近使用时间距离现在最远的key，进行淘汰
- allkeys-lfu 就是从所有的key中挑选使用频率最低的key，进行淘汰。（这是Redis 4.0版本后新增的策略）
第三类从设置了过期时间的key中挑选，进行淘汰

这种就是从设置了expires过期时间的结果集中选出一部分key淘汰，挑选的算法有：
- volatile-random 从设置了过期时间的结果集中随机挑选key删除。
- volatile-lru 从设置了过期时间的结果集中挑选上次使用时间距离现在最久的key开始删除
- volatile-ttl 从设置了过期时间的结果集中挑选可存活时间最短的key开始删除(也就是从哪些快要过期的key中先删除)
- volatile-lfu 从过期时间的结果集中选择使用频率最低的key开始删除（这是Redis 4.0版本后新增的策略）

LRU算法

LRU算法的设计原则是如果一个数据近期没有被访问到，那么之后一段时间都不会被访问到。所以当元素个数达到限制的值时，优先移除距离上次使用时间最久的元素。

可以使用双向链表Node+HashMap<String, Node>来实现，每次访问元素后，将元素移动到链表头部，当元素满了时，将链表尾部的元素移除，HashMap主要用于根据key获得Node以及添加时判断节点是否已存在和删除时快速找到节点。

PS:使用单向链表能不能实现呢，也可以，单向链表的节点虽然获取不到pre节点的信息，但是可以将下一个节点的key和value设置在当前节点上，然后把当前节点的next指针指向下下个节点，这样相当于把下一个节点删除了

//双向链表
    public static class ListNode {
        String key;//这里存储key便于元素满时，删除尾节点时可以快速从HashMap删除键值对
        Integer value;
        ListNode pre = null;
        ListNode next = null;
        ListNode(String key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    ListNode head;
    ListNode last;
    int limit=4;
    
    HashMap<String, ListNode> hashMap = new HashMap<String, ListNode>();

    public void add(String key, Integer val) {
        ListNode existNode = hashMap.get(key);
        if (existNode!=null) {
            //从链表中删除这个元素
            ListNode pre = existNode.pre;
            ListNode next = existNode.next;
            if (pre!=null) {
               pre.next = next;
            }
            if (next!=null) {
               next.pre = pre;
            }
            //更新尾节点
            if (last==existNode) {
                last = existNode.pre;
            }
            //移动到最前面
            head.pre = existNode;
            existNode.next = head;
            head = existNode;
            //更新值
            existNode.value = val;
        } else {
            //达到限制，先删除尾节点
            if (hashMap.size() == limit) {
                ListNode deleteNode = last;
                hashMap.remove(deleteNode.key);
              //正是因为需要删除，所以才需要每个ListNode保存key
                last = deleteNode.pre;
                deleteNode.pre = null;
                last.next = null;
            }
            ListNode node = new ListNode(key,val);
            hashMap.put(key,node);
            if (head==null) {
                head = node;
                last = node;
            } else {
                //插入头结点
                node.next = head;
                head.pre = node;
                head = node;
            }
        }

    }

    public ListNode get(String key) {
        return hashMap.get(key);
    }

    public void remove(String key) {
        ListNode deleteNode = hashMap.get(key);
        ListNode preNode = deleteNode.pre;
        ListNode nextNode = deleteNode.next;
        if (preNode!=null) {
            preNode.next = nextNode;
        }
        if (nextNode!=null) {
            nextNode.pre = preNode;
        }
        if (head==deleteNode) {
            head = nextNode;
        }
        if (last == deleteNode) {
            last = preNode;
        }
        hashMap.remove(key);
    }

LFU算法

LFU算法的设计原则时，如果一个数据在最近一段时间被访问的时次数越多，那么之后被访问的概率会越大，基本实现是每个数据都有一个引用计数，每次数据被访问后，引用计数加1，需要淘汰数据时，淘汰引用计数最小的数据。在Redis的实现中，每次key被访问后，引用计数是加一个介于0到1之间的数p，并且访问越频繁p值越大，而且在一定的时间间隔内，
如果key没有被访问，引用计数会减少。

最后

大家有什么想法，可以一起讨论！