Redis作为一个成熟的数据存储中间件,它提供了完善的数据管理功能,比如之前我们提到过的数据过期和今天我们要讲的数据淘汰(evict)策略。在开始介绍Redis数据淘汰策略前,我先抛出几个问题,帮助大
Redis作为一个成熟的数据存储中间件,它提供了完善的数据管理功能,比如之前我们提到过的数据过期和今天我们要讲的数据淘汰(evict)策略。在开始介绍Redis数据淘汰策略前,我先抛出几个问题,帮助大家更深刻理解Redis的数据淘汰策略。
- 何为数据淘汰,Redis有了数据过期策略为什么还要有数据淘汰策略?
- 淘汰哪些数据,有什么样的数据选取标准?
- Redis的数据淘汰策略是如何实现的?
何为Evict
我先来回答第一个问题,Redis中数据淘汰实际上是指的在内存空间不足时,清理掉某些数据以节省内存空间。 虽然Redis已经有了过期的策略,它可以清理掉有效期外的数据。但想象下这个场景,如果过期的数据被清理之后存储空间还是不够怎么办?是不是还可以再删除掉一部分数据? 在缓存这种场景下 这个问题的答案是可以,因为这个数据即便在Redis中找不到,也可以从被缓存的数据源中找到。所以在某些特定的业务场景下,我们是可以丢弃掉Redis中部分旧数据来给新数据腾出空间。
如何Evict
第二个问题,既然我们需要有淘汰的机制,你们在具体执行时要选哪些数据淘汰掉?具体策略有很多种,但思路只有一个,那就是总价值最大化。我们生在一个不公平的世界里,同样数据也是,那么多数据里必然不是所有数据的价值都是一样的。所以我们在淘汰数据时只需要选择那些低价值的淘汰即可。
所以问题又来了,哪些数据是低价值的?这里不得不提到一个贯穿计算机学科的原理局部性原理,这里可以明确告诉你,局部性原理在缓存场景有这样两种现象,1. 最新的数据下次被访问的概率越高。 2. 被访问次数越多的数据下次被访问的概率越高。 这里我们可以简单认为被访问的概率越高价值越大。基于上述两种现象,我们可以指定出两种策略 1. 淘汰掉最早未被访问的数据。2. 淘汰掉访被访问频次最低的数据,这两种策略分别有个洋气的英文名LRU(Least Recently Used)和LFU(Least Frequently Used)。
Redis中的Evict策略
除了LRU和LFU之外,还可以随机淘汰。这就是将数据一视同仁,随机选取一部分淘汰。实际上Redis实现了以上3中策略,你使用时可以根据具体的数据配置某个淘汰策略。除了上述三种策略外,Redis还为由过期时间的数据提供了按TTL淘汰的策略,其实就是淘汰剩余TTL中最小的数据。另外需要注意的是Redis的淘汰策略可以配置在全局或者是有过期时间的数据上,所以Redis共计以下8中配置策略。
配置项 | 具体含义 |
---|
MAXMEMORY_VOLATILE_LRU | 仅在有过期时间的数据上执行LRU |
MAXMEMORY_VOLATILE_LFU | 仅在有过期时间的数据上执行LFU |
MAXMEMORY_VOLATILE_TTL | 在有过期时间的数据上按TTL长度淘汰 |
MAXMEMORY_VOLATILE_RANDOM | 仅在有过期时间的数据上随机淘汰 |
MAXMEMORY_ALLKEYS_LRU | 在全局数据上执行LRU |
MAXMEMORY_ALLKEYS_LFU | 在全局数据上执行LFU |
MAXMEMORY_ALLKEYS_RANDOM | 在全局数据上随机淘汰 |
MAXMEMORY_NO_EVICTION | 不淘汰数,当内存空间满时插入数据会报错 |
源码剖析
接下来我们就从源码来看下Redis是如何实现以上几种策略的,MAXMEMORY_VOLATILE_和MAXMEMORY_ALLKEYS_策略实现是一样的,只是作用在不同的dict上而已。另外Random的策略也比较简单,这里就不再详解了,我们重点看下LRU和LFU。
LRU具体实现
LRU的本质是淘汰最久没被访问的数据,有种实现方式是用链表的方式实现,如果数据被访问了就把它移到链表头部,那么链尾一定是最久未访问的数据,但是单链表的查询时间复杂度是O(n),所以一般会用hash表来加快查询数据,比如Java中LinkedHashMap就是这么实现的。但Redis并没有采用这种策略,Redis就是单纯记录了每个Key最近一次的访问时间戳,通过时间戳排序的方式来选找出最早的数据,当然如果把所有的数据都排序一遍,未免也太慢了,所以Redis是每次选一批数据,然后从这批数据执行淘汰策略。这样的好处就是性能高,坏处就是不一定是全局最优,只是达到局部最优。
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr; } robj;
LRU信息如何存的? 在之前介绍redisObject的文章中 我们已提到过了,在redisObject中有个24位的lru字段,这24位保存了数据访问的时间戳(秒),当然24位无法保存完整的unix时间戳,不到200天就会有一个轮回,当然这已经足够了。
robj *lookupKey(redisDb *db, robj *key, int flags) { dictEntry *de = dictFind(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){ if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { updateLFU(val); } else { val->lru = LRU_CLOCK(); // 这里更新LRU时间戳 } } return val; } else { return NULL; }}
LFU具体实现
lru
这个字段也会被lfu用到,所以你在上面lookupkey中可以看到在使用lfu策略是也会更新lru
。Redis中lfu的出现稍晚一些,是在Redis 4.0才被引入的,所以这里复用了lru字段。 lru的实现思路只有一种,就是记录下key被访问的次数。但实现lru有个问题需要考虑到,虽然LFU是按访问频次来淘汰数据,但在Redis中随时可能有新数据就来,本身老数据可能有更多次的访问,新数据当前被访问次数少,并不意味着未来被访问的次数会少,如果不考虑到这点,新数据可能一就来就会被淘汰掉,这显然是不合理的。
Redis为了解决上述问题,将24位被分成了两部分,高16位的时间戳(分钟级),低8位的计数器。每个新数据计数器初始有一定值,这样才能保证它能走出新手村,然后计数值会随着时间推移衰减,这样可以保证老的但当前不常用的数据才有机会被淘汰掉,我们来看下具体实现代码。
LFU计数器增长
计数器只有8个二进制位,充其量数到255,怎么会够? 当然Redis使用的不是精确计数,而是近似计数。具体实现就是counter概率性增长,counter的值越大增长速度越慢,具体增长逻辑如下:
/* 更新lfu的counter,counter并不是一个准确的数值,而是概率增长,counter的数值越大其增长速度越慢 * 只能反映出某个时间窗口的热度,无法反映出具体访问次数 */uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; double r = (double)rand()/RAND_MAX; double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL为5 if (baseval < 0) baseval = 0; double p = 1.0/(baseval*server.lfu_log_factor+1); // server.lfu_log_factor可配置,默认是10 if (r < p) counter++; return counter;}
从代码逻辑中可以看出,counter的值越大,增长速度会越慢,所以lfu_log_factor配置较大的情况下,即便是8位有可以存储很大的访问量。下图是不同lfu_log_factor在不同访问频次下的增长情况,图片来自Redis4.0之基于LFU的热点key发现机制。
原标题:Redis源码剖析之内存淘汰策略(Evict)
关键词:Java,Redis
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。