过期策略

面试官：你了解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缓存

面试官：那你使用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();
    }

}

输出如下：