Redis数据淘汰算法 _Redis

众所周知，redis的所有数据都存储在内存中，但是内存是一种有限的资源，所以为了防止Redis无限制的使用内存，在启动Redis时可以通过配置项 maxmemory 来指定其最大能使用的内存容量。例如可以通过以下配置来设置Redis最大能使用 1G 内存：
maxmemory 1G当Redis使用的内存超过配置的 maxmemory 时，便会触发数据淘汰策略。Redis提供了多种数据淘汰的策略，如下：

volatile-lru: 最近最少使用算法，从设置了过期时间的键中选择空转时间最长的键值对清除掉
volatile-lfu: 最近最不经常使用算法，从设置了过期时间的键中选择某段时间之内使用频次最小的键值对清除掉
volatile-ttl: 从设置了过期时间的键中选择过期时间最早的键值对清除
volatile-random: 从设置了过期时间的键中，随机选择键进行清除
allkeys-lru: 最近最少使用算法，从所有的键中选择空转时间最长的键值对清除
allkeys-lfu: 最近最不经常使用算法，从所有的键中选择某段时间之内使用频次最少的键值对清除
allkeys-random: 所有的键中，随机选择键进行删除
noeviction: 不做任何的清理工作，在redis的内存超过限制之后，所有的写入操作都会返回错误；但是读操作都能正常的进行

可以在启动Redis时，通过配置项 maxmemory_policy 来指定要使用的数据淘汰策略。例如要使用 volatile-lru 策略可以通过以下配置来指定：
maxmemory_policy volatile-lruLRU算法LRU是 Least Recently Used 的缩写，即最近最少使用，很多缓存系统都使用此算法作为淘汰策略。
最简单的实现方式就是把所有缓存通过一个链表连接起来，新创建的缓存添加到链表的头部，如果有缓存被访问了，就把缓存移动到链表的头部。由于被访问的缓存会移动到链表的头部，所以没有被访问的缓存会随着时间的推移移动的链表的尾部，淘汰数据时只需要从链表的尾部开始即可。下图展示了这个过程：

文章插图

Redis的LRU算法Redis使用了结构体 robj 来存储缓存对象，而 robj 结构有个名为 lru 的字段，用于记录缓存对象最后被访问的时间，Redis就是以 lru 字段的值作为淘汰依据。robj 结构如下：
typedef struct redisObject { ... unsigned lru:24; ...} robj;当缓存对象被访问时，便会更新此字段的值。代码如下：
robj *lookupKey(redisDb *db, robj *key, int flags) { dictEntry *de = dictFind(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); /* Update the access time for the ageing algorithm. * Don't do it if we have a saving child, as this will trigger * a copy on write madness. */ if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) { if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { updateLFU(val); } else { val->lru = LRU_CLOCK(); // 更新lru字段的值 } } return val; } else { return NULL; }}lookupKey() 函数用于查找key对应的缓存对象，所以当缓存对象被访问时便会调用此函数。
Redis数据淘汰接下来我们分析一下当Redis内存使用超过配置的最大内存使用限制时的处理方式。
Redis在处理每一个命令时都会检查内存的使用是否超过了限制的最大值，处理命令是通过 processCommand() 函数进行的，检查内存使用情况的代码如下：
int processCommand(client *c) { ... if (server.maxmemory && !server.lua_timedout) { int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR; if (server.current_client == NULL) return C_ERR; if (out_of_memory && (c->cmd->flags & CMD_DENYOOM || (c->flags & CLIENT_MULTI && c->cmd->proc != execCommand))) { flagTransaction(c); addReply(c, shared.oomerr); return C_OK; } } ...}【Redis数据淘汰算法】检查内存的使用情况主要通过 freeMemoryIfNeededAndSafe() 函数进行，而 freeMemoryIfNeededAndSafe() 函数最终会调用 freeMemoryIfNeeded() 函数进行处理，由于 freeMemoryIfNeeded() 函数比较庞大，所以我们分段来进行分析：
int freeMemoryIfNeeded(void) { ... size_t mem_reported, mem_tofree, mem_freed; mstime_t latency, eviction_latency; long long delta; int slaves = listLength(server.slaves); ... if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK) return C_OK; mem_freed = 0; if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION) goto cant_free;freeMemoryIfNeeded() 函数首先会调用 getMaxmemoryState() 函数来获取Redis的内存使用情况，如果 getMaxmemoryState() 函数返回 C_OK，表示内存使用总量还没有超出限制，直接返回 C_OK 就可以了。如果 getMaxmemoryState() 函数不是返回 C_OK，表示内存使用总量已经超出限制，需要进行数据淘汰，需要淘汰数据的大小通过 mem_tofree 参数返回。