Redis过期策略和内存淘汰机制

0.前言

既然Redis是内存缓存，那由于内存容量有限，不可能像文件DB那样把数据仍进去就完事了。
并且Redis里存放的多是热点数据，所以需要适时对过期的key进行清理，来释放空间；但是，在清理过后，仍然有可能还是存在大量的“废弃”key，这时候就需要内存淘汰机制来强制清理了。

过期时间

Redis支持为key设置一个生存时间TTL，在经过指定的时间后，Server会自动删除TTL=0的key。

redis> SET key value
OK
redis> EXPIRE key 5
(integer) 1
redis> GET key  // 5秒之内
"value"
redis> GET key  // 5秒之后
(nil)

SETEX命令可以在设置一个字符串键的同时为键设置过期时间，这个命令是一个类型限定的命令（只能用于字符串键）。
同时Redis提供了统一的设置过期时间命令：EXPIRE，PEXPIRE为一个key设置秒，毫秒级别的TTL

可能的过期策略

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

定期删除是定时+惰性的折中。

1.Redis过期策略

Redis提供了以下两种过期策略：
定期删除+惰性删除

定期删除

Redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。

优缺点

优点：

• 通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响
• 减少内存浪费

缺点：

• 有的key可能扫描不到

为毛随机抽取？
如果全部抽取，则需要扫描所有的key，判断TTL，开销太大！
有何不足？
随机抽取，可能导致大量的过期key没有被抽取到！

惰性删除

获取 key 的时候，如果此时 key 已经过期，就删除，不会返回任何东西。

优缺点

优点：

• 对CPU时间来说是最友好的：程序只会在取出键时才对键进行过期检查，这可以保证删除过期键的操作只会在非做不可的情况下进行，并且删除的目标仅限于当前处理的键，这个策略不会在删除其他无关的过期键上花费任何CPU时间。

缺点：

• 它对内存是最不友好的：如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，它所占用的内存就不会释放
• 内存泄漏：如果数据库中有非常多的过期键，而这些过期键又恰好没有被访问到的话，那么它们也许永远也不会被删除（除非用户手动执行FLUSHDB）

2.内存淘汰算法

定期删除+惰性删除就一定OK？

如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时会怎么样？如果大量过期 key 堆积在内存里，导致 Redis 内存块耗尽了，咋整？
答案是：内存淘汰机制。

几种淘汰算法

• noeviction: 当内存不足以容纳新写入数据时，新写入操作会报错
• allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）
• allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个 key
• volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的 key（这个一般不太合适）
• volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个 key。
• volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的 key 优先移除

配置

redis.conf里配置maxmemory，表示使用最大的内存。
64位机器上，默认是0，表示没有内存限制；32位机器上，默认是3GB

手撕一个LRU/LFU？

LinkedHashMap

最简单的，使用LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer> {
	private int capacity;
	
	public LRUCache(int capacity) {
		super(capacity, 0.75f, true);
		this.capacity = capacity;
	}
	
	public int get(int key) {
		return super.getOrDefault(key, -1);
	}
	
	public void put(int key, int value) {
		super.put(key, value);
	}
	@Override
	protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
		return size() > capacity; 
	}
}

手撕双链表

缓存淘汰算法LRU/LFU实现