redis学习笔记（三）redis数据淘汰策略

ゝ一纸荒年。 2022-07-13 00:07 202阅读 0赞

> 本文讲的是 当redis设定了最大内存之后，缓存中的数据集大小超过了一定比例，实施的淘汰策略，不是删除过期键的策略，虽然两者非常相似。

# redis系列文章目录 #

*  [Redis 利用Hash存储节约内存][Redis _Hash]
 *  [使用spring-data-redis实现incr自增][spring-data-redis_incr]
 *  [Redis学习笔记（九）redis实现时时直播列表缓存,支持分页\[热点数据存储\]][Redis_redis]
 *  [Redis学习笔记（八）redis之lua脚本学习][Redis_redis_lua]
 *  [Redis学习笔记（七）jedis超时重试机制注意事项][Redis_jedis]
 *  [Redis学习笔记（六）redis实现分布式锁][Redis_redis 1]
 *  [Redis学习笔记（五）jedis(JedisCluster)操作Redis集群 redis-cluster][Redis_jedis_JedisCluster_Redis_ redis-cluster]
 *  [redis学习笔记（四）缓存与数据库一致性问题][redis]
 *  [redis学习笔记（三）数据淘汰策略][redis 1]
 *  [redis学习笔记（二）JedisCluster + redis 3.2.5集群][redis_JedisCluster _ redis 3.2.5]
 *  [redis学习笔记（一）redis3.2.5集群安装与测试][redis_redis3.2.5]

# 概述 #

在 redis 中，允许用户设置最大使用内存大小通过配置`redis.conf`中的`maxmemory`这个值来开启内存淘汰功能，在内存限定的情况下是很有用的。  
设置最大内存大小可以保证redis对外提供稳健服务。

redis 内存数据集大小上升到一定大小的时候，就会施行数据淘汰策略。redis 提供 6种数据淘汰策略通过`maxmemory-policy`设置策略：

1.  volatile-lru：从已设置过期时间的数据集（server.db\[i\].expires）中挑选最近最少使用的数据淘汰
2.  volatile-ttl：从已设置过期时间的数据集（server.db\[i\].expires）中挑选将要过期的数据淘汰
3.  volatile-random：从已设置过期时间的数据集（server.db\[i\].expires）中任意选择数据淘汰
4.  allkeys-lru：从数据集（server.db\[i\].dict）中挑选最近最少使用的数据淘汰
5.  allkeys-random：从数据集（server.db\[i\].dict）中任意选择数据淘汰
6.  no-enviction（驱逐）：禁止驱逐数据

redis 确定驱逐某个键值对后，会删除这个数据并将这个数据变更消息发布到本地（AOF 持久化）和从机（主从连接）

## LRU 数据淘汰机制 ##

在服务器配置中保存了 lru 计数器 server.lrulock，会定时（redis 定时程序 serverCorn()）更新，server.lrulock 的值是根据 server.unixtime 计算出来的。

另外，从 struct redisObject 中可以发现，每一个 redis 对象都会设置相应的 lru。可以想象的是，每一次访问数据的时候，会更新 redisObject.lru。

LRU 数据淘汰机制是这样的：在数据集中随机挑选几个键值对，取出其中 lru 最大的键值对淘汰。所以，你会发现，redis 并不是保证取得所有数据集中最近最少使用（LRU）的键值对，而只是随机挑选的几个键值对中的。

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td> <code>// redisServer 保存了 lru 计数器</code> <code>struct redisServer { </code> <code>...</code> <code>unsigned lruclock:22; /* Clock incrementing every minute, for LRU */</code> <code>...</code> <code>};</code> <code>&nbsp;</code> <code>// 每一个 redis 对象都保存了 lru</code> <code>#define REDIS_LRU_CLOCK_MAX ((1&lt;&lt;21)-1) /* Max value of obj-&gt;lru */</code> <code>#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */</code> <code>typedef struct redisObject { </code> <code>// 刚刚好 32 bits</code> <code>&nbsp;</code> <code>// 对象的类型，字符串/列表/集合/哈希表</code> <code>unsigned type:4;</code> <code>// 未使用的两个位</code> <code>unsigned notused:2; /* Not used */</code> <code>// 编码的方式，redis 为了节省空间，提供多种方式来保存一个数据</code> <code>// 譬如：“123456789” 会被存储为整数 123456789</code> <code>unsigned encoding:4;</code> <code>unsigned lru:22; /* lru time (relative to server.lruclock) */</code> <code>&nbsp;</code> <code>// 引用数</code> <code>int refcount;</code> <code>&nbsp;</code> <code>// 数据指针</code> <code>void *ptr;</code> <code>} robj;</code> <code>&nbsp;</code> <code>// redis 定时执行程序。联想：linux cron</code> <code>int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { </code> <code>......</code> <code>/* We have just 22 bits per object for LRU information.</code> <code>* So we use an (eventually wrapping) LRU clock with 10 seconds resolution.</code> <code>* 2^22 bits with 10 seconds resolution is more or less 1.5 years.</code> <code>*</code> <code>* Note that even if this will wrap after 1.5 years it's not a problem,</code> <code>* everything will still work but just some object will appear younger</code> <code>* to Redis. But for this to happen a given object should never be touched</code> <code>* for 1.5 years.</code> <code>*</code> <code>* Note that you can change the resolution altering the</code> <code>* REDIS_LRU_CLOCK_RESOLUTION define.</code> <code>*/</code> <code>updateLRUClock();</code> <code>......</code> <code>}</code> <code>&nbsp;</code> <code>// 更新服务器的 lru 计数器</code> <code>void updateLRUClock(void) { </code> <code>server.lruclock = (server.unixtime/REDIS_LRU_CLOCK_RESOLUTION) &amp;</code> <code>REDIS_LRU_CLOCK_MAX;</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

## TTL 数据淘汰机制 ##

redis 数据集数据结构中保存了键值对过期时间的表，即 redisDb.expires。和 LRU 数据淘汰机制类似，TTL 数据淘汰机制是这样的：从过期时间的表中随机挑选几个键值对，取出其中 ttl 最大的键值对淘汰。同样你会发现，redis 并不是保证取得所有过期时间的表中最快过期的键值对，而只是随机挑选的几个键值对中的。

总结

redis 每服务客户端执行一个命令的时候，会检测使用的内存是否超额。如果超额，即进行数据淘汰。

`// 执行命令`

`int processCommand(redisClient *c) {`

`......`

`// 内存超额`

`/* Handle the maxmemory directive.`

`*`

`* First we try to free some memory if possible (if there are volatile`

`* keys in the dataset). If there are not the only thing we can do`

`* is returning an error. */`

`if (server.maxmemory) {`

`int retval = freeMemoryIfNeeded();`

`if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {`

`flagTransaction(c);`

`addReply(c, shared.oomerr);`

`return REDIS_OK;`

`}`

`......`

`}`

` `

`// 如果需要，是否一些内存`

`int freeMemoryIfNeeded(void) {`

`size_t mem_used, mem_tofree, mem_freed;`

`int slaves = listLength(server.slaves);`

` `

`// redis 从机回复空间和 AOF 内存大小不计算入 redis 内存大小`

`/* Remove the size of slaves output buffers and AOF buffer from the`

`* count of used memory. */`

`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;`

`}`

`// server.aof_buf && server.aof_rewrite_buf_blocks`

`if (server.aof_state != REDIS_AOF_OFF) {`

`mem_used -= sdslen(server.aof_buf);`

`mem_used -= aofRewriteBufferSize();`

`}`

` `

`// 内存是否超过设置大小`

`/* Check if we are over the memory limit. */`

`if (mem_used <= server.maxmemory) return REDIS_OK;`

` `

`// redis 中可以设置内存超额策略`

`if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)`

`return REDIS_ERR; /* We need to free memory, but policy forbids. */`

` `

`/* Compute how much memory we need to free. */`

`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; /* just to prevent warning */`

`sds bestkey = NULL;`

`struct dictEntry *de;`

`redisDb *db = server.db+j;`

`dict *dict;`

` `

`// 不同的策略，选择的数据集不一样`

`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;`

` `

`// 随机淘汰随机策略：随机挑选`

`/* volatile-random and allkeys-random policy */`

`if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||`

`server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)`

`{`

`de = dictGetRandomKey(dict);`

`bestkey = dictGetKey(de);`

`}`

` `

`// LRU 策略：挑选最近最少使用的数据`

`/* volatile-lru and allkeys-lru policy */`

`else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||`

`server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)`

`{`

`// server.maxmemory_samples 为随机挑选键值对次数`

`// 随机挑选 server.maxmemory_samples个键值对，驱逐最近最少使用的数据`

`for (k = 0; k < server.maxmemory_samples; k++) {`

`sds thiskey;`

`long thisval;`

`robj *o;`

` `

`// 随机挑选键值对`

`de = dictGetRandomKey(dict);`

` `

`// 获取键`

`thiskey = dictGetKey(de);`

` `

`/* When policy is volatile-lru we need an additional 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);`

`o = dictGetVal(de);`

` `

`// 计算数据的空闲时间`

`thisval = estimateObjectIdleTime(o);`

` `

`// 当前键值空闲时间更长，则记录`

`/* Higher idle time is better candidate for deletion */`

`if (bestkey == NULL || thisval > bestval) {`

`bestkey = thiskey;`

`bestval = thisval;`

`}`

` `

`// TTL 策略：挑选将要过期的数据`

`/* volatile-ttl */`

`else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {`

`// server.maxmemory_samples 为随机挑选键值对次数`

`// 随机挑选 server.maxmemory_samples个键值对，驱逐最快要过期的数据`

`for (k = 0; k < server.maxmemory_samples; k++) {`

`sds thiskey;`

`long thisval;`

` `

`de = dictGetRandomKey(dict);`

`thiskey = dictGetKey(de);`

`thisval = (long) dictGetVal(de);`

` `

`/* Expire sooner (minor expire unix timestamp) is better`

`* candidate for deletion */`

`if (bestkey == NULL || thisval < bestval) {`

`bestkey = thiskey;`

`bestval = thisval;`

`}`

` `

`// 删除选定的键值对`

`/* Finally remove the selected key. */`

`if (bestkey) {`

`long long delta;`

` `

`robj *keyobj = createStringObject(bestkey,sdslen(bestkey));`

` `

`// 发布数据更新消息，主要是 AOF 持久化和从机`

`propagateExpire(db,keyobj);`

` `

`// 注意， propagateExpire() 可能会导致内存的分配， propagateExpire()`

`提前执行就是因为 redis 只计算 dbDelete() 释放的内存大小。倘若同时计算 dbDelete() 释放的内存`

`和 propagateExpire() 分配空间的大小，与此同时假设分配空间大于释放空间，就有可能永远退不出这个循环。`

`// 下面的代码会同时计算 dbDelete() 释放的内存和 propagateExpire() 分配空间的大小：`

`// propagateExpire(db,keyobj);`

`// delta = (long long) zmalloc_used_memory();`

`// dbDelete(db,keyobj);`

`// delta -= (long long) zmalloc_used_memory();`

`// mem_freed += delta;`

`/`

` `

`/* 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++;`

` `

`// 将数据的删除通知所有的订阅客户端`

`notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",`

`keyobj, db->id);`

`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();`

`}`

` `

`// 未能释放空间，且此时 redis 使用的内存大小依旧超额，失败返回`

`if (!keys_freed) return REDIS_ERR; /* nothing to free... */`

`}`

`return REDIS_OK;`

`}`

## 适用场景 ##

下面看看几种策略的适用场景：

*  allkeys-lru： 如果我们的应用对缓存的访问符合幂律分布（也就是存在相对热点数据），或者我们不太清楚我们应用的缓存访问分布状况，我们可以选择allkeys-lru策略。
 *  allkeys-random： 如果我们的应用对于缓存key的访问概率相等，则可以使用这个策略。
 *  volatile-ttl： 这种策略使得我们可以向Redis提示哪些key更适合被eviction。

另外，volatile-lru策略和volatile-random策略适合我们将一个Redis实例既应用于缓存和又应用于持久化存储的时候，然而我们也可以通过使用两个Redis实例来达到相同的效果，值得一提的是将key设置过期时间实际上会消耗更多的内存，因此我们建议使用allkeys-lru策略从而更有效率的使用内存。

[Redis _Hash]: http://blog.csdn.net/liubenlong007/article/details/53816561
[spring-data-redis_incr]: http://blog.csdn.net/liubenlong007/article/details/77817742
[Redis_redis]: http://blog.csdn.net/liubenlong007/article/details/53838737
[Redis_redis_lua]: http://blog.csdn.net/liubenlong007/article/details/53816087
[Redis_jedis]: http://blog.csdn.net/liubenlong007/article/details/53815968
[Redis_redis 1]: http://blog.csdn.net/liubenlong007/article/details/53782934
[Redis_jedis_JedisCluster_Redis_ redis-cluster]: http://blog.csdn.net/liubenlong007/article/details/53766734
[redis]: http://blog.csdn.net/liubenlong007/article/details/53690312
[redis 1]: http://blog.csdn.net/liubenlong007/article/details/53690103
[redis_JedisCluster _ redis 3.2.5]: http://blog.csdn.net/liubenlong007/article/details/53689306
[redis_redis3.2.5]: http://blog.csdn.net/liubenlong007/article/details/53471459