详解Redis 缓存删除机制(源码解析)
删除的范围
- 过期的key
- 在内存满了的情况下,如果继续执行set 等命令,且所有key都没有过期,那么会按照缓存淘汰策略选中的key
过期删除
redis中设置了过期时间的key会单独存储一份
typedefstructredisDb{ dict*dict;//所有的键值对 dict*expires;//设置了过期时间的键值对 //... }redisDb;
设置有效期
Redis中有4个命令可以给key设置过期时间,分别是expire pexpire expireat pexpireat
设置相对时间
expire
//src/expire.c /*EXPIREkeyseconds*/ voidexpireCommand(client*c){ expireGenericCommand(c,mstime(),UNIT_SECONDS); }
pexpire
//src/expire.c /*PEXPIREkeymilliseconds*/ voidpexpireCommand(client*c){ expireGenericCommand(c,mstime(),UNIT_MILLISECONDS); }
设置绝对时间
expireat
//src/expire.c /*EXPIREATkeytime*/ voidexpireatCommand(client*c){ expireGenericCommand(c,0,UNIT_SECONDS); }
pexpireat
//src/expire.c /*PEXPIREATkeyms_time*/ voidpexpireatCommand(client*c){ expireGenericCommand(c,0,UNIT_MILLISECONDS); }
以上4种方法最终都会调用下面的通用函数expireGenericCommand :
//src/expire.c voidexpireGenericCommand(client*c,longlongbasetime,intunit){ robj*key=c->argv[1],*param=c->argv[2]; //获取数据对象 longlongwhen; if(getLongLongFromObjectOrReply(c,param,&when,NULL)!=C_OK) return; //将时间转化成以ms为单位 if(unit==UNIT_SECONDS)when*=1000; when+=basetime; //在master节点上,如果设置的过期时间小于当前时间,那么将命令转化成DEL指令 if(when<=mstime()&&!server.loading&&!server.masterhost){ robj*aux; intdeleted=server.lazyfree_lazy_expire?dbAsyncDelete(c->db,key): dbSyncDelete(c->db,key); //... //将删除命令同步给slave和AOF //... }else{ //设置过期时间 setExpire(c,c->db,key,when); //... //构造返回值和发布对象更新消息 //... return; } }
设置过期时间的操作由setExpire 执行,他将dictEntry 的unionv 中的s64 设为过期时间
//src/db.c voidsetExpire(client*c,redisDb*db,robj*key,longlongwhen){ dictEntry*kde,*de; //找出db->dict中对应的存储对象,这里的查询和用get查询数据是逻辑一样,通过hashFunc(key)&sizemask //找到bucket后在链表中遍历 kde=dictFind(db->dict,key->ptr); //找出db->expires中对应的存储对象,如果没有则新建一个 de=dictAddOrFind(db->expires,dictGetKey(kde)); // dictSetSignedIntegerVal(de,when); //... } #definedictSetSignedIntegerVal(entry,_val_)\ do{(entry)->v.s64=_val_;}while(0)
db->expires 中存储的 dictEntry 表示的是过期key和过期时间,存储过期时间的v 是一个union ,可见在redis中不同使用场景或不同编码下v 的意义不同
typedefstructdictEntry{ void*key; union{ void*val; uint64_tu64; int64_ts64; doubled; }v; structdictEntry*next; }dictEntry;
查询过期时间
ttlkey返回key剩余过期秒数。
//src/expire.c /*TTLkey*/ voidttlCommand(client*c){ ttlGenericCommand(c,0); }
pttlkey返回key剩余过期的毫秒数。
//src/expire.c /*PTTLkey*/ voidpttlCommand(client*c){ ttlGenericCommand(c,1); }
以上2种查看方式最终都会调用下面的通用函数ttlGenericCommand :
//src/expire.c /*ImplementsTTLandPTTL*/ voidttlGenericCommand(client*c,intoutput_ms){ //... //key不存在时报错 //... //获取过期时间,如果没有过期时间则 expire=getExpire(c->db,c->argv[1]); if(expire!=-1){ ttl=expire-mstime(); if(ttl<0)ttl=0; } if(ttl==-1){ addReplyLongLong(c,-1); }else{ //根据指定的单位返回结果,以秒为单位时向上取整 addReplyLongLong(c,output_ms?ttl:((ttl+500)/1000)); } }
获取过期时间的操作由getExpire 执行,在db->expires 中查询到对象后,获取unionv 中的成员s64
//src/expire.c //返回过期时间的绝对时间 longlonggetExpire(redisDb*db,robj*key){ dictEntry*de; //查询对象 if(dictSize(db->expires)==0|| //如果返回为NULL表示没有设置过期时间,向上返回-1 (de=dictFind(db->expires,key->ptr))==NULL)return-1; //获取v.s64 returndictGetSignedIntegerVal(de); } #definedictGetSignedIntegerVal(he)((he)->v.s64)
过期策略
Redis综合使用惰性删除和定期扫描实现
惰性删除
每次访问时会调用expireIfNeeded 判断key是否过期,如果过期就删除该键,否则返回键对应的值。单独使用这种策略可能会浪费很多内存。
//src/db.c intexpireIfNeeded(redisDb*db,robj*key){ mstime_twhen=getExpire(db,key); mstime_tnow; //没有设置过期时间,直接返回 if(when<0)return0; //从硬盘中加载数据时不执行过期操作 if(server.loading)return0; //参考GitHubIssue#1525 //对于master,在执行LuaScript的过程中,可能会用某个key是否存在当作判断条件 //为了避免一个脚本中前后条件不一致,将当前时间强制设为脚本开始时间 now=server.lua_caller?server.lua_time_start:mstime(); //对于slave,返回此时key是否已过期,但不执行后续删除操作 if(server.masterhost!=NULL)returnnow>when; //key未过期 if(now<=when)return0; //统计过期key的个数 server.stat_expiredkeys++; //向所有的slave和AOF文件写入一条DEL指令 propagateExpire(db,key,server.lazyfree_lazy_expire); //向keyspacechannel中发布一条key过期的消息 notifyKeyspaceEvent(NOTIFY_EXPIRED, "expired",key,db->id); //根据配置决定是同步删除还是异步删除(仅删除引用,由后台线程执行物理删除) returnserver.lazyfree_lazy_expire?dbAsyncDelete(db,key): dbSyncDelete(db,key); }
特殊处理
在master节点执行Lua脚本时
参考GitHubIssue#1525,对于master,在执行LuaScript的过程中,可能会用某个key是否存在当作判断条件。为了避免一个脚本中前后条件不一致,将当前时间强制设为脚本开始时间。
例如多次执行如下Lua脚本/tmp/myscript.lua 出现的结果可能不一致
--/tmp/myscript.lua ifredis.call("exists",KEYS[1])==1 then redis.call("incr","mycounter") end ifredis.call("exists",KEYS[1])==1 then returnredis.call("incr","mycounter") end
具体复现操作可以参考下面的bash 脚本:
while[1] do redis-clisetxfoopx100>/dev/null sleep0.092 redis-cli--eval/tmp/myscript.luax>/dev/null sleep0.1 redis-cligetmycounter redis-cli-p6380getmycounter done
对于slave节点
在slave节点上,key的删除操作由master发来的DEL 执行,因此这里只返回是否过期的结果给客户端,而不执行删除操作
正在从RDB和AOF读取数据时跳过这个步骤
定期扫描
系统每隔一段时间就定期扫描一次,发现过期的键就进行删除。单独使用这种策略可能出现键已经过期但没有删除的情况
Redis默认每100ms执行一次(通过hz 参数配置,执行周期为1s/hz)过期扫描。由于redisDb中设置了过期时间的key会单独存储,所以不会出现扫描所有key的情况
具体步骤由activeExpireCycle 函数执行
activeExpireCycle、incrementallyRehash等后台操作都是由databasesCron触发的
voidactiveExpireCycle(inttype){ //... //依次遍历各个db for(j=0;jACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP) num=ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP; //从设置了过期时间的key中随机抽取20个 while(num--){ dictEntry*de; longlongttl; //随机挑选dict中的一个key if((de=dictGetRandomKey(db->expires))==NULL)break; ttl=dictGetSignedIntegerVal(de)-now; //执行删除,具体删除操作和惰性删除中类似 if(activeExpireCycleTryExpire(db,de,now))expired++; //... } //... //更新统计数据等操作 //... //如果每次删除的key超过了样本数的25%,说明过期键占的比例较高,需要再重复执行依次 }while(expired>ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4); } //... }
随机抽样由dictGetRandomKey 执行
//src/dict.c /*Returnarandomentryfromthehashtable.Usefulto *implementrandomizedalgorithms*/ dictEntry*dictGetRandomKey(dict*d) { dictEntry*he,*orighe; unsignedlongh; intlistlen,listele; //没有数据,返回为NULL,外层函数接收到NULL后会中断过期操作的执行 if(dictSize(d)==0)returnNULL; //根据rehashidx参数判断是否正在执行rehash,如果正在执行, //则先执行rehash中的一个步骤 if(dictIsRehashing(d))_dictRehashStep(d); if(dictIsRehashing(d)){ do{ //正在执行rehash,所以两个ht中的对象都要考虑 // //由于正在执行rehash,所以可以肯定ht[0]中下标小于等于rehashidx的bucket //肯定没有数据,所以只从ht[0]中大于rehashidx的bucket和ht[1]中抽取 h=d->rehashidx+(random()%(d->ht[0].size+ d->ht[1].size- d->rehashidx)); he=(h>=d->ht[0].size)?d->ht[1].table[h-d->ht[0].size]: d->ht[0].table[h]; //取到空bucket时重试 }while(he==NULL); }else{ do{ //参考写入ht时计算下标的规则hashFunc(key)&sizemake //这里random()&sizemask是随机取一个下标 h=random()&d->ht[0].sizemask; he=d->ht[0].table[h]; //取到空bucket时重试 }while(he==NULL); } //到这一步he是ht[n]中某个bucket中完整的链表 //所以还要从这个链表中随机取一个对象 //遍历计算整个链表的长度 listlen=0; orighe=he; while(he){ he=he->next; listlen++; } //随机取链表中某个对象的下标 listele=random()%listlen; he=orighe; //重新遍历链表获取指定下标的对象 while(listele--)he=he->next; returnhe; }
缓存淘汰
配置最大内存限制
在redis.conf中配置
redisserver启动时加载配置文件和命令行参数中的maxmemory,存入Server对象的maxmemory字段
main 中在redisserver启动时执行初始化等操作,其中会执行加载配置文件的loadServerConfig 函数
//src/server.c intmain(intargc,char**argv){ //.. //加载配置 loadServerConfig(configfile,options); //.. //警告过小的配置 if(server.maxmemory>0&&server.maxmemory<1024*1024){ serverLog(LL_WARNING,"WARNING:Youspecifiedamaxmemoryvaluethatislessthan1MB(currentvalueis%llubytes).Areyousurethisiswhatyoureallywant?",server.maxmemory); } }
loadServerConfig 中将配置文件、stdin、命令行参数加载到config字符串中,然后调用loadServerConfigFromString
//src/config.c voidloadServerConfig(char*filename,char*options){ sdsconfig=sdsempty(); charbuf[CONFIG_MAX_LINE+1]; //加载配置文件 if(filename){ FILE*fp; //启动命令为./redis-server-则从stdin中读取,需要用触发EOF if(filename[0]=='-'&&filename[1]=='\0'){ fp=stdin; }else{ //第一个参数不是-,则尝试打开这个参数指定的文件 if((fp=fopen(filename,"r"))==NULL){ serverLog(LL_WARNING, "Fatalerror,can'topenconfigfile'%s'",filename); exit(1); } } //将配置文件中的每一行追加到config中 while(fgets(buf,CONFIG_MAX_LINE+1,fp)!=NULL) config=sdscat(config,buf); if(fp!=stdin)fclose(fp); } //添加其他选项,例如./redis-server--port8080后面的参数,直接加到config中 if(options){ config=sdscat(config,"\n"); config=sdscat(config,options); } loadServerConfigFromString(config); sdsfree(config); }
loadServerConfigFromString 从上一步中的config 字符串中逐行读取配置,并写入server 对象
//src/config.c voidloadServerConfigFromString(char*config){ //... //按行读取配置文件 lines=sdssplitlen(config,strlen(config),"\n",1,&totlines); for(i=0;i1024 server.maxmemory=memtoll(argv[1],NULL); } } }
使用CONFIGSET命令配置
RedisServer接收到客户端的CONFIGSET命令后调用configSetCommand函数
服务端接收到命令时将命令和参数存入RedisServer的argc和argv
argc:4 argv:0123 configsetmaxmemory10mb
动态配置maxmemory后会立即尝试触发内存回收,而修改其他内存相关配置(例如:maxmemory_policy)时不会触发
if(0){ //... }config_set_memory_field("maxmemory",server.maxmemory){ //配置不为0,表示之前限制过内存 if(server.maxmemory){ if(server.maxmemory32位机器的内存限制
对于64位机器,将maxmemory设置为0表示不限制内存,但由于32位寻址空间最多只有4GB,所以默认内存限制设为3GB,缓存淘汰策略设为noeviction
//src/server.c //... if(server.arch_bits==32&&server.maxmemory==0){ serverLog(LL_WARNING,"Warning:32bitinstancedetectedbutnomemorylimitset.Setting3GBmaxmemorylimitwith'noeviction'policynow."); server.maxmemory=3072LL*(1024*1024);/*3GB*/ server.maxmemory_policy=MAXMEMORY_NO_EVICTION; }淘汰策略
淘汰策略使用CONFIGSETmaxmemory-policy 配置
默认:
- **noeviction:**内存满了后对于set 等命令直接返回错误
针对所有key:
- allkeys-lru:在所有key的范围内使用LRU算法执行删除,如果内存仍然不够,则报错
- **allkeys-lfu:**在所有key的范围内使用LRU算法执行删除,如果内存仍然不够,则报错
- **allkeys-random:**在所有key的范围内随机执行删除,如果内存仍然不够,则报错
针对设置了过期时间的key:
- **volatile-lru:**在设置了过期时间的key中使用LRU算法执行删除,如果内存仍然不够,则报错
- **volatile-lfu:**在设置了过期时间的key中使用LRU算法执行删除,如果内存仍然不够,则报错
- **volatile-random:**在设置了过期时间的key中随机执行删除,如果内存仍然不够,则报错
- **volatile-ttl:**删除即将过期的key,如果内存仍然不够,则报错
Redis在执行淘汰之前会计算部分对象的idle 值,使用不同淘汰策略时计算idle 值的方法也不同,idle 值越大表示这个值越需要优先删除。
下面主要介绍LRU和LFU中idle 值的计算方法
LRU淘汰策略
抽样删除,样本数量通过CONFIGSETmaxmemory-samples100 控制,对应RedisObject中的maxmemory_samples 参数,抽样数量越多和传统的LRU算法越接近
优化策略
为了避免传统的LRU算法通常使用hashmap+链表实现带来的开销,Redis进行了如下优化:
RedisObject结构中设置了一个lru字段,用来记录数据的访问时间戳,而不是每次调整对象在链表中的位置
typedefstructredisObject{ //对象类型 unsignedtype:4; //对象编码 unsignedencoding:4; //LRU算法和LFU算法公用lru这个字段 // //LRU_BITS默认为24,因此最大只能存储194天的时间戳, //创建对象时会写入这个字段,访问对象时会更新这个字段, //超过之后再从0开始计算 unsignedlru:LRU_BITS; intrefcount; void*ptr; }robj;使用抽样数组代替链表,后续在候选集合中根据lru字段值的大小进行筛选,避免了链表带来的开销。候选集合中的对象用evictionPoolEntry 表示
structevictionPoolEntry{ unsignedlonglongidle;//用于淘汰排序,在不同算法中意义不同 sdskey;//键的名字 //... };计算方法
全局对象lru_clock 记录了当前的unix时间戳,由serverCron 调用 updateCachedTime 默认每100ms更新一次。更新频率与hz 参数有关,1s/hz 即为更新间隔时间。
LRU_CLOCK_RESOLUTION 的值为1000,因此使用LRU_CLOCK 函数获取lru_clock 时,如果每秒更新频率在1次以上,会使用全局变量中缓存的lrulcock
unsignedintLRU_CLOCK(void){ unsignedintlruclock; if(1000/server.hz<=LRU_CLOCK_RESOLUTION){ atomicGet(server.lruclock,lruclock); }else{ lruclock=getLRUClock(); } returnlruclock; }如果更新频率不到每秒1次,则会用函数getLRUClock 实时计算lruclock
unsignedintgetLRUClock(void){ //mstime()获取unix时间戳,单位时毫秒 //除以LRU_CLOCK_RESOLUTION(值为1000),将时间戳转化为秒 return(mstime()/LRU_CLOCK_RESOLUTION)&LRU_CLOCK_MAX; }其中LRU_CLOCK_MAX 表示lru_clock 最大的可能值,这个值与redisObject中lru 最大的可能值一样,定义如下:
#defineLRU_CLOCK_MAX((1<所以最终比较时lru_clock 和robj.lru 的值都在[0,LRU_CLOCK_MAX]的范围内。
从逻辑上讲,当前时间戳应该永远大于上次访问的时间戳 ,因此正常的计算规则应该是lru_clock-robj.lru 。
但是由于lru_clock 和robj.lru 是当前时间戳取模后的值,所以可能出现lru_clock 小于robj.lru 的情况,所以这种情况下计算规则应该改为lru_clock+194天-robj.lru
但是对于lru_clock 和robj.lru 间隔超过194天的情况仍然无法判断,所以更能存在删除不准确的情况。
将上述的逻辑组合起来就是LRU算法下获取idle 值的函数:
//src/evict.c //以秒为精度计算对象距离上一次访问的间隔时间,然后转化成毫秒返回 unsignedlonglongestimateObjectIdleTime(robj*o){ unsignedlonglonglruclock=LRU_CLOCK(); if(lruclock>=o->lru){ return(lruclock-o->lru)*LRU_CLOCK_RESOLUTION; }else{ return(lruclock+(LRU_CLOCK_MAX-o->lru))* LRU_CLOCK_RESOLUTION; } }在Redis3.0中,当取样数量设为10时,已经和传统的LRU算法效果很接近了
LFU淘汰策略
LFU算法复用robj.lru 字段,将这个24bit的字段拆分成了两部分:
- ldt(lastdecrementtime,单位:分钟):lru字段的前16bit,表示数据的访问时间戳,最多只能存储45天。
- counter值:lru字段的后8bit,表示数据的访问频率
递增策略
counter能表示的最大值是255,因此counter与访问次数不能是线性关系,这里采用的计算步骤如下:
- 随机取0到1之间的随机数r
- 比较r与1/((counter-LFU_INIT_VAL)*lfu_log_factor+1)的大小,其中LFU_INIT_VAL是常量,默认为5,lfu_log_factor是可配置参数,默认为10
- 如果r小则counter增加1,否则counter不变
实现代码如下:
uint8_tLFULogIncr(uint8_tcounter){ //counter值已经到达了255,不能再增加,直接返回 if(counter==255)return255; doubler=(double)rand()/RAND_MAX; doublebaseval=counter-LFU_INIT_VAL;//LFU_INIT_VAL值为5 if(baseval<0)baseval=0; doublep=1.0/(baseval*server.lfu_log_factor+1); if(r
访问次数与counter值之间大概是对数关系,counter值越大,增速越低
//https://redis.io/topics/lru-cache +--------+------------+------------+------------+------------+------------+ |factor|100hits|1000hits|100Khits|1Mhits|10Mhits| +--------+------------+------------+------------+------------+------------+ |0|104|255|255|255|255| +--------+------------+------------+------------+------------+------------+ |1|18|49|255|255|255| +--------+------------+------------+------------+------------+------------+ |10|10|18|142|255|255| +--------+------------+------------+------------+------------+------------+ |100|8|11|49|143|255| +--------+------------+------------+------------+------------+------------+衰减策略
除了访问对象时counter需要增加,对于一段时间内没有访问的对象还要相应地减少counter值,递减的速率由lfu-decay-time 参数控制。
counter衰减步骤如下:取当前时间戳(单位:分钟)的低16位记为now ,计算与ldt 的差值。这里与LRU算法中计算lru_clock 和robj.lru 时可能出现一样的问题,由于ldt最多只能表示45天,所以如果距离对象上次访问超过45天,则无法准确计算访问的时间间隔
unsignedlongLFUDecrAndReturn(robj*o){ //取高16位 unsignedlongldt=o->lru>>8; //取低8位 unsignedlongcounter=o->lru&255; //如果lfu_decay_time为0,则步修改counter,否则将counter减少LFUTimeElapsed(ldt)/lfu_decay_time unsignedlongnum_periods=server.lfu_decay_time?LFUTimeElapsed(ldt)/server.lfu_decay_time:0; if(num_periods) //保证counter的最小值位0 counter=(num_periods>counter)?0:counter-num_periods; returncounter; } //计算距离上次访问的间隔时间 unsignedlongLFUTimeElapsed(unsignedlongldt){ //取当前时间戳(单位:分钟) unsignedlongnow=LFUGetTimeInMinutes(); //计算时间差 if(now>=ldt)returnnow-ldt; return65535-ldt+now; } //获取当前时间戳,以分钟为单位,取低8位 unsignedlongLFUGetTimeInMinutes(void){ return(server.unixtime/60)&65535; }如果lfu_decay_time为0,则步修改counter,否则将counter减少LFUTimeElapsed(ldt)/lfu_decay_time
例如,在lfu_decay_time为1的情况下,如果有N分钟没有访问这个对象,那么counter值减N
每次访问一个对象时都会调用updateLFU更新counter的值:
voidupdateLFU(robj*val){ unsignedlongcounter=LFUDecrAndReturn(val); counter=LFULogIncr(counter); val->lru=(LFUGetTimeInMinutes()<<8)|counter; }执行淘汰
当Redis需要淘汰一批数据时,会调用evictionPoolPopulate 获取一批待删除对象,根据设置的淘汰范围的不同,会决定传递给evictionPoolPopulate 的sampledict 参数是存有全部数据的db->dict 还是只有设置了过期时间的数据的db->expires
voidevictionPoolPopulate(intdbid,dict*sampledict,dict*keydict,structevictionPoolEntry*pool){ intj,k,count; dictEntry*samples[server.maxmemory_samples]; //随机获取server.maxmemory_samples个对象,写入samples中 count=dictGetSomeKeys(sampledict,samples,server.maxmemory_samples); //遍历每个对象 for(j=0;jdict(还可能是db->expires),并且不是按volatile-ttl淘汰 //那么还要将对象转化成数据字典中对应的对象,然后取其值 if(server.maxmemory_policy!=MAXMEMORY_VOLATILE_TTL){ if(sampledict!=keydict)de=dictFind(keydict,key); //#definedictGetVal(he)((he)->v.val) //这里还是利用union的特性,如果是db->dict中的元素,返回的是键的值 //如果是db->expires中的元素,返回的是过期时间 o=dictGetVal(de); } //按各算法计算idle分值,idle越大的越应该被先淘汰 // //如果使用LRU淘汰算法,则计算对象的空闲时间 if(server.maxmemory_policy&MAXMEMORY_FLAG_LRU){ idle=estimateObjectIdleTime(o); //使用LFU淘汰算法, }elseif(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){ idle=255-LFUDecrAndReturn(o); //使用volatile-ttl算法,用ULLONG_MAX减去过期时间作为分值 }elseif(server.maxmemory_policy==MAXMEMORY_VOLATILE_TTL){ idle=ULLONG_MAX-(long)dictGetVal(de); }else{ serverPanic("UnknownevictionpolicyinevictionPoolPopulate()"); } k=0; //与原pool中的idle值进行比较,找出应该比当前对象先淘汰出去的对象 while(k 完成上述操作后,pool中剩下的就是新筛选出来的最需要淘汰的对象了。
在freeMemoryIfNeeded 中会调用evictionPoolPopulate 来筛选需要淘汰的对象,每次删除一个,直到释放了足够的内存。如果始终无法达到内存需求,则会报错。
到此这篇关于Redis缓存删除机制(源码解析)的文章就介绍到这了,更多相关Redis缓存删除内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。