Redis淘汰删除策略
原创
Redis数据库作为缓存系统使用通常只保留部分的热点数据。当热点数据超过Redis设置的内存总大小时就需要删除陈旧的数据，为键空间设计一套高效的过期策略将使得应用程序的内存需求更可控。本文介绍Redis的键淘汰策略以及在Redis内部是如何实现的。
Redis6种淘汰Key策略
Redis中通过maxmemory参数来设定内存的使用上限，当Redis使用内存达到设定的最大值的时候，会根据配置文件中的策略选取要删除的key来删除，从而给新的键值留出空间；
目前Redis提供了6种的淘汰策略（默认的是noeviction）：
- noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
- allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。
- allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
- volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。这里特别注意的一点：当redis内存耗尽时，Redis会开始删除那些设置了过期时间的键，即使该键仍然有剩余时间。
- volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
- volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。
其中Redis的LRU算法，其中有几点需要注意的地方。首先，Redis的LRU算法时不准确的。因为Redis并不会自动选择真正最少使用的键或者最早访问的键，而是默认会选择5个键的样本，并驱逐当中最少使用的那个。如果需要增加LRU的精确性，我们可以通过更改redis.conf文件中的maxmemory-samples指令，或者再运行时通过config set maxmemory-samples命令进行设置，增大该值可以提升RedisLRU的准确性，效果更接近真实的LRU，但是副作用时消耗更多的cpu资源。
如何查看当前redis实例的key淘汰策略：
CONFIG GET maxmemory-policy
Redis的过期键删除策略
常见过期键的删除策略总结
上面介绍了redis的6种Key淘汰策略。如果一个Key满足淘汰条件需要删除 ，那么它是在什么时候会被删除的呢? 通常有三种不同的方式：
1、定时删除：在设置Key的过期的同时，创建一个定时器(timer)，让定时器在键的过期来临时，立即执行对键的删除操作。
- 优点：对内存时最友好的，通过使用定时器，定时删除策略可以保证过期键会尽可能的被快速删除，并释放过期键所占用的内存。
- 缺点：在过期键比较多的情况下，删除过期键中一行为可能会占用相当一部分cpu时间，将cpu时间用在删除和当前任务无关的过期键上，无疑是对服务器的响应时间和吞吐量造成影响。因此，要让服务器创建大量的定时器从而实现定时删除策略，从cpu资源利用上讲并不现实。
2、惰性删除:放任键过期不管，但是每次从键空间获取键时，都检查获得的键时否过期，如果过期的话，就删除该键;若谷没有过期，就返回该键。
- 优点：cpu友好，程序只会在取出键时才对键的过期时间进行检查，这保证了删除过期键的操作只会在非作不可的情况下进行，并且删除的目标只限于当前处理的键，因此该策略不会再删除其他无关的过期键上浪费cpu资源。
- 缺点：内存不友好。在使用惰性删除是，如果数据库中有非常多的过期键，而这些过期键又恰好没有被访问到的话，那么他们永远也不会被删除，导致无用的拉起数据占用着内存，有内存泄漏的问题。
3、定期删除:每隔一段时间，程序就对数据库进行一次检查，删除里面过期键。至于需要删除多少过期键，以及需要检查多少个键，则有算法决定。 定期删除策略时以上两种策略的整合和折中：
- a.定期删除策略每隔一段时间执行一次删除过期操作，并通过限制删除执行的时长和频率来减少删除操作对cpu时间的影响
- b.通过定期删除过期键，定期删除策略有效地减少了因为过期键带来的内存浪费。
Redis过期键删除的实现
Redis通过配合使用定期删除和惰性删除量种策略，合理使用cpu时间和避免浪费内存空间之间取得了平衡。这里对Redis服务器中定期删除和惰性删除的具体实现进行说明。
用于存储过期Key的底层数据结构
redis底层数据结构是由dict以及expires两个字典构成，通过下一张图可以非常清晰了解到redis中带过期时间的key-value的存储结构，可以更加深刻认识到redis的内存管理机制。
- 过期字典的键是一个指针，这个指针指向键空间中的某个键对象
- 过期字典的值是一个long long 类型的整数，这个整数保存了键所指向的数据库键的过期时间---一个毫秒精度的unix时间戳
typedef struct redisDB {
// ...
// 过期字典，保存着键的过期时间
dict* expires;
// ...
}
惰性策略的实现
过期键的惰性策略有db.c/expireIfNeeded函数实现，所有读写数据库的Redis命令在执行之前都会调用expireIfNeeded
函数进行Key的检查，如果输入键已经过期，那么该函数将会删除Key，否则什么也不做。具体代码如下：
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
// 计算占用内存大小时，并不计算slave output buffer和aof buffer，
// 因此maxmemory应该比实际内存小，为这两个buffer留足空间。
mem_used = zmalloc_used_memory();
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.appendonly) {
mem_used -= sdslen(server.aofbuf);
mem_used -= sdslen(server.bgrewritebuf);
}
// 判断已经使用内存是否超过最大使用内存，如果没有超过就返回REDIS_OK，
if (mem_used <= server.maxmemory) return REDIS_OK;
// 当超过了最大使用内存时，就要判断此时redis到底采用何种内存释放策略，根据不同的策略，采取不同的清除算法。
// 首先判断是否是为no-enviction策略，如果是，则返回REDIS_ERR,然后redis就不再接受任何写命令了。
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR;
// 计算需要清理内存大小
mem_tofree = mem_used - server.maxmemory;
mem_freed = 0;
while (mem_freed < mem_tofree) {
int j, k, keys_freed = 0;
for (j = 0; j < server.dbnum; j++) {
long bestval = 0;
sds bestkey = NULL;
struct dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
// 1、从哪个字典中剔除数据
// 判断淘汰策略是基于所有的键还是只是基于设置了过期时间的键，
// 如果是针对所有的键，就从server.db[j].dict中取数据，
// 如果是针对设置了过期时间的键，就从server.db[j].expires（记录过期时间）中取数据。
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
dict = server.db[j].dict;
} else {
dict = server.db[j].expires;
}
if (dictSize(dict) == 0) continue;
// 2、从是否为随机策略
// 是不是random策略，包括volatile-random 和allkeys-random，这两种策略是最简单的，就是在上面的数据集中随便去一个键，然后删掉。
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
de = dictGetRandomKey(dict);// 从方法名猜出是随机获取一个dictEntry
bestkey = dictGetEntryKey(de);// 得到删除的key
}
// 3、判断是否为lru算法
// 是lru策略还是ttl策略，如果是lru策略就采用lru近似算法
// 为了减少运算量,redis的lru算法和expire淘汰算法一样，都是非最优解，
// lru算法是在相应的dict中，选择maxmemory_samples(默认设置是3)份key，挑选其中lru的，进行淘汰
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
de = dictGetRandomKey(dict);
thiskey = dictGetEntryKey(de);
/* When policy is volatile-lru we need an additonal lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey); //因为dict->expires维护的数据结构里并没有记录该key的最后访问时间
o = dictGetEntryVal(de);
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
// 找到那个最合适删除的key
// 类似排序，循环后找到最近最少使用，将其删除
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
// 如果是ttl策略。
// 取maxmemory_samples个键，比较过期时间，
// 从这些键中找到最快过期的那个键，并将其删除
else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
de = dictGetRandomKey(dict);
thiskey = dictGetEntryKey(de);
thisval = (long) dictGetEntryVal(de);
/* Expire sooner (minor expire unix timestamp) is better candidate for deletion */
if (bestkey == NULL || thisval < bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
// 根据不同策略挑选了即将删除的key之后，进行删除
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
// 发布数据更新消息，主要是AOF 持久化和从机
propagateExpire(db,keyobj); //将del命令扩散给slaves
// 注意， propagateExpire() 可能会导致内存的分配，
// propagateExpire() 提前执行就是因为redis 只计算
// dbDelete() 释放的内存大小。倘若同时计算dbDelete()
// 释放的内存和propagateExpire() 分配空间的大小，与此
// 同时假设分配空间大于释放空间，就有可能永远退不出这个循环。
// 下面的代码会同时计算dbDelete() 释放的内存和propagateExpire() 分配空间的大小
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can't account for
* that otherwise we would never exit the loop.
*
* AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// 只计算dbDelete() 释放内存的大小
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
decrRefCount(keyobj);
keys_freed++;
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
// 将从机回复空间中的数据及时发送给从机
if (slaves) flushSlavesOutputBuffers();
}
}//在所有的db中遍历一遍，然后判断删除的key释放的空间是否足够，未能释放空间，且此时redis 使用的内存大小依旧超额，失败返回
if (!keys_freed) return REDIS_ERR; /* nothing to free... */
}
return REDIS_OK;
}从源码分析中可以看到redis在使用内存中超过设定的阈值时是如何将清理key-value进行内管管理，其中涉及到redis的存储结构。
总结出的具体流程见图1
例如图2的GET命令的执行过程中，命令需要判断键是否存在以及键时否过期，然后根据判断来执行合适的操作。
定期删除策略的实现
过期键的定期删除策略由redis.c/activeExpireCycle函数实现，每当Redis的服务器周期性操作redis.c/serverCron函数执行时，activeExpireCycle函数就会被调用，它在规定的时间内，分多次遍历服务器的各个数据库，从数据库的expires字典中随机检查一部分的过期键，并删除其中的过期键。
伪代码描述如下：
#默认每次检查的数据库数量
DEFAULT_DB_NUMBERS = 16
#默认每个数据库检查的键数量
DEFAULT_KEY_NUMBERS = 20
#全局变量，记录检查进度
current_db = 0
def activeExpireCycle():
#初始化要检查的数据库数量
#如果服务器的数据库数量比DEFAULT_DB_NUMBERS小，那么以服务器的数据库数量为准
if server.dbnum < DEFAULT_DB_NUMBERS:
db_numbers = server.dbnum
else:
db_numbers = DEFAULT_DB_NUMBERS
for _ in range(db_numbers):
#获取当前要处理的数据库
if current_db == server.dbnum:
current_db = 0
redisDb = server.db[current_db]
current += 1
#检查数据库的j键，一次轮询最多检查DEFAULT_KEY_NUMBERS的键
for j in range(DEFAULT_KEY_NUMBERS):
#如果当前数据库没有一个带过期时间的key，那么跳过该数据库
if redisDb.expires.size() == 0:
break
#随机取一个过期时间的键
key_with_ttl = redis.expires.get_random_key()
#检查是否过期，如果过期就删除它
if is_expired(key_with_ttl):
delete_key(key_with_ttl)
#已经到达时间上限，停止继续处理余下的检测
if reach_time_limit():
return
对于定期删除策的工作模式可以总结如下：
- 函数每次运行时，都从一定数量的数据库中取出一定数量的随机键进行检查，并删除其中过期键。
- 全局变量 current_db会记录当前activeExpireCycle函数检查的进度，并在下一次activeExpireCycle函数调用时，接着上次的进度进行处理。比如，如果当前activeExpireCycle函数遍历10号数据库返回了，那么下次activeExpireCycle函数执行时，将从11号数据库开始查找并删除过期键。
- 随着activeExpireCycle函数的不断执行，服务器中的所有数据库都会被检查一遍，这时函数将current_db重新置0，然后再开始新一轮的检查。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。