文末本文转载自微信公众号《董泽润的技术笔记》，作者董泽润。转载本文请联系董泽润技术笔记公众号。所有IT从业者都接触过缓存，都必须了解其基本工作原理。业界流行一句话：缓存是万能的，有问题就擦。那么它的本质是什么？上图代表了从cpu到底层硬盘的不同级别，以及不同模块的运行速度。在上层多加一层缓存，可以解决下层速度慢的问题。这里的慢指的是两点：IO慢和cpu反复计算缓存的中间结果，但是缓存受限于成本。缓存大小一般是固定的，因此需要对数据进行淘汰，从而导致其他一系列问题：缓存一致性、击穿、雪崩、污染等，本文通过阅读redis源码，学习主流淘汰算法.如果leetcode146LRU[1]不需要，我想大家不会手写cache。简单的实现与工程实践相去甚远。realproductionreadycachelibrary非常测试细节Redis缓存淘汰配置一般情况下，redis不建议作为存储使用，只作为缓存使用，并设置了max-memory。当内存占用达到最大值时，redis-server会根据不同的配置开始删除key。Redis从4.0版本开始引入了LFU[2]，即LeastFrequentlyUsed。4.0之前默认使用LRU，即LeastRecentlyUsed。volatile-lru只对设置expire过期的key进行lru，而淘汰allkeys-lru，对所有key进行lru并淘汰volatile-lfu只对设置expire过期的key将lfu淘汰allkeys-lfu将对所有key使用lfu将被淘汰volatile-random只会对setexpireexpiredallkeys-random随机淘汰所有的keyvolatile-ttl会被淘汰ttl过期时间最小的keynoevictioneverything不要，如果此时内存已满时间，系统无法写入。默认策略是noeviction，即不驱逐。如果内存已满，系统将无法写入。建议设置为LFU。LRU优先淘汰最近不用的数据，无法应对冷数据。例如，短时间未访问的热键会被仅使用一次的冷数据冲走，不能反映真实的使用情况。LFU可以避免上述情况，但是简单的LFU实现无法应对突发流量，无法驱逐历史热键，所以redis的LFU实现类似于W-TinyLFU[3]，其中W表示windows，即，频率在一定时间窗口后减半。如果不减少，缓存就会变成历史数据的统计，而不是缓存，上面也提到了突发流量怎么处理？答案是给新访问的key一个初始频率值，这样就不能更新频率了，因为初始值为0。（如果数据集中有易失性*键）。如果没有唯一的东西，我们可以做*正在返回错误。*/if（server.maxmemory）{intretval=freeMemoryIfNeeded（）;if（（c->cmd->flags&REDIS_）&&retval==REDIS_ERR）{flagTransaction（c）;addReply（c,shared.oomerr);returnREDIS_OK;}}......}会在每次客户端命令处理时调用freeMemoryIfNeeded检查是否需要逐出某个key，当redis实际使用的内存达到上限时，它将开始被淘汰。然而，redis是相当棘手的。它不会为所有键创建一个lru队列，而是根据maxmemory_samples参数进行采样。系统默认为5个键。上面是一张很经典的图。当达到10键时，效果更接近理论。LRU算法，但是CPU消耗会变高，所以系统默认值就够用了。LFU实现robj*lookupKey(redisDb*db,robj*key,intflags){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){update;CLOK=LFUval(R)>l}el}}returnval;}else{returnNULL;}}当lookupKey访问到一个key时，LRU会被更新。从redis4.0开始，逐渐引入了LFU算法。由于复用了LRU域，只有24位*Wesplitthe24bitsintotwofields:**16bits8bits*+----------------+--------+*+Lastdecrtime|LOG_C|*+---------------+--------+低8位计数器用于计数频率，取值范围为0~255，但取对数后可以表示较大的访问频率，16位的ldt（LastDecrementTime）表示最后一次访问的分钟时间戳，用于衰减计数器值。如果计数器不衰减，则变成历史key访问次数的统计，而不是LFUunsignedlongLFUTimeElapsed(unsignedlongldt){unsignedlongnow=LFUGetTimeInMinutes();if(now>=ldt)returnnow-ldt;return65535-ldt+now;}请注意，仅使用ldt16位计数，最大值为65535，所以会有rewindLFU获取现有计数*counterofthescannedbobjectsifneeded.*/unsignedlongLFUDecrAndReturn(robj*o){unsignedlongldt=o->lru>>8;unsignedlongcounter=o->lru&255;unsignedlongnum_periods=server.lfu_decay_time?LFUTimeElapsed(ldt)/server.lfu_decay_time:0;if(num_periods)counter=(num_periods>counter)?0:counter-num_periods;returncounter;}num_periods表示计算的待衰减计数，lfu_decay_time表示衰减系数，默认值为1。如果lfu_decay_time大于1，衰减速度会变得很慢。最后返回的计数值是衰减后的，可能是0LFU计数更新和对数){if(counter==255)return255;doubler=(double)rand()/RAND_MAX;doublebaseval=counter-LFU_INIT_VAL;if(baseval<0)baseval=0;doublep=1.0/(baseval*server.lfu_log_factor+1);if(r
