本文从源码层面分析了redis的缓存淘汰机制，并在文章末尾描述使用Java实现的思路，以供参考。
相关配置
为了适配用作缓存的场景，redis支持缓存淘汰（eviction）并提供相应的了配置项：
maxmemory
设置内存使用上限，该值不能设置为小于1M的容量。
选项的默认值为0，此时系统会自行计算一个内存上限。
maxmemory-policy
熟悉redis的朋友都知道，每个数据库维护了两个字典：
db.dict：数据库中所有键值对，也被称作数据库的keyspacedb.expires：带有生命周期的key及其对应的TTL（存留时间），因此也被称作expireset当达到内存使用上限maxmemory时，可指定的清理缓存所使用的策略有：
noeviction当达到最大内存时直接返回错误，不覆盖或逐出任何数据allkeys-lfu淘汰整个keyspace中最不常用的(LFU)简(4.0或更高版本)allkeys-lru淘汰整个keyspace最近最少使用的(LRU)键allkeys-random淘汰整个keyspace中的随机键volatile-ttl淘汰expireset中TTL最短的键volatile-lfu淘汰expireset中最不常用的键(4.0或更高版本)volatile-lru淘汰expireset中最近最少使用的(LRU)键volatile-random淘汰expireset中的随机键当expireset为空时，volatile-*与noeviction行为一致。
maxmemory-samples
为了保证性能，redis中使用的LRU与LFU算法是一类近似实现。
简单来说就是：算法选择被淘汰记录时，不会遍历所有记录，而是以随机采样的方式选取部分记录进行淘汰。
maxmemory-samples选项控制该过程的采样数量，增大该值会增加CPU开销，但算法效果能更逼近实际的LRU与LFU。
lazyfree-lazy-eviction
清理缓存就是为了释放内存，但这一过程会阻塞主线程，影响其他命令的执行。
当删除某个巨型记录（比如：包含数百条记录的list）时，会引起性能问题，甚至导致系统假死。
延迟释放机制会将巨型记录的内存释放，交由其他线程异步处理，从而提高系统的性能。
开启该选项后，可能出现使用内存超过maxmemory上限的情况。
缓存淘汰机制
一个完整的缓存淘汰机制需要解决两个问题：
确定淘汰哪些记录——淘汰策略删除被淘汰的记录——删除策略淘汰策略
缓存能使用的内存是有限的，当空间不足时，应该优先淘汰那些将来不再被访问的数据，保留那些将来还会频繁访问的数据。因此淘汰算法会围绕时间局部性原理进行设计，即：如果一个数据正在被访问，那么在近期很可能会被再次访问。
为了适应缓存读多写少的特点，实际应用中会使用哈希表来实现缓存。当需要实现某种特定的缓存淘汰策略时，需要引入额外的簿记bookkeeping结构。
下面回顾3种最常见的缓存淘汰策略。
FIFO(先进先出)
越早进入缓存的数据，其不再被访问的可能性越大。
因此在淘汰缓存时，应选择在内存中停留时间最长的缓存记录。
使用队列即可实现该策略：
优点：实现简单，适合线性访问的场景
缺点：无法适应特定的访问热点，缓存的命中率差
簿记开销：时间O(1)，空间O(N)
LRU(最近最少使用)
一个缓存被访问后，近期再被访问的可能性很大。
可以记录每个缓存记录的最近访问时间，最近未被访问时间最长的数据会被首先淘汰。
使用链表即可实现该策略：
当更新LRU信息时，只需调整指针：
优点：实现简单，能适应访问热点
缺点：对偶发的访问敏感，影响命中率
簿记开销：时间O(1)，空间O(N)
LRU改进
原始的LRU算法缓存的是最近访问了1次的数据，因此不能很好地区分频繁和不频繁缓存引用。
这意味着，部分冷门的低频数据也可能进入到缓存，并将原本的热点记录挤出缓存。
为了减少偶发访问对缓存的影响，后续提出的LRU-K算法作出了如下改进：
在LRU簿记的基础上增加一个历史队列HistoryQueue
当记录访问次数小于K时，会记录在历史队列中（当历史队列满时，可以使用FIFO或LRU策略进行淘汰）当记录访问次数大于等于K时，会被从历史队列中移出，并记录到LRU缓存中K值越大，缓存命中率越高，但适应性差，需要经过大量访问才能将过期的热点记录淘汰掉。
综合各种因素后，实践中常用的是LRU-2算法：
优点：减少偶发访问对缓存命中率的影响
缺点：需要额外的簿记开销
簿记开销：时间O(1)，空间O(N+M)
LFU(最不经常使用)
一个缓存近期内访问频率越高，其再被访问的可能性越大。
可以记录每个缓存记录的最近一段时间的访问频率，访问频率低的数据会被首先淘汰。
实现LFU的一个简单方式，是在缓存记录设置一个记录访问次数的计数器，然后将其放入一个小顶堆：
为了保证数据的时效性，还要以一定的时间间隔对计数器进行衰减，保证过期的热点数据能够被及时淘汰：
删除策略
常见删除策略可以分为以下几种：
实时删除：每次增加新的记录时，立即查找可淘汰的记录，如果存在则将该记录从缓存中删除优点：实时性好，最节省内存空间缺点：查找淘汰记录会影响写入的效率，需要额外的簿记结构提高查找效率（比如LRU中的链表）惰性删除：在缓存中设置两个计数器，一个统计访问缓存的次数，一个统计可淘汰记录的数量每经过N次访问后或当前可淘汰记录数量大于M，则触发一次批量删除（M与N可调节）优点：对正常缓存操作影响小，批量删除减少维护开销缺点：实时性较差，偶发的删除操作会导致访问耗时波动异步删除：设置一个独立的定时器线程，每隔固定的时间触发一次批量删除优点：对正常缓存操作影透明，无额外性能开销缺点：需要增加维护线程，并且需要提前规划缓存的负载，以此决定如何在多个缓存实例上调度redis实现
redis中实现了LRU与LFU两种淘汰策略
为了节省空间，redis没有使用前面描述的簿记结构实现LRU或LFU，而是在robj中使用一个24bits的空间记录访问信息：
#defineLRU_BITS24typedefstructredisObject{...unsignedlru:LRU_BITS;/*LRU时间(相对与全局lru_clock的时间)或*LFU数据(8bits记录访问频率，16bits记录访问时间).*/}robj;每当记录被命中时，redis都会更新robj.lru作为后面淘汰算法运行的依据：
robj*lookupKey(redisDb*db,robj*key,intflags){//...//根据maxmemory_policy选择不同的更新策略if(server.maxmemory_policyMAXMEMORY_FLAG_LFU){updateLFU(val);}else{val-lru=LRU_CLOCK();}}LFU与LRU的更新关键在于updateLFU函数与LRU_CLOCK宏，下面分别进行分析。
更新LRU时间
当时使用LRU算法时，robj.lru记录的是最近一次访问的时间戳，可以据此找出长时间未被访问的记录。
为了减少系统调用，redis设置了一个全局的时钟server.lruclock并交由后台任务进行更新：
#defineLRU_CLOCK_MAX((1LRU_BITS)-1)/*Maxvalueofobj-lru*/#defineLRU_CLOCK_RESOLUTION/*以毫秒为单位的时钟精度*//***server.lruclock的更新频率为/server.hz*如果该频率高于LRU时钟精度，则直接用server.lruclock*避免调用getLRUClock()产生额外的开销*/#defineLRU_CLOCK()((/server.hz=LRU_CLOCK_RESOLUTION)?server.lruclock:getLRUClock())unsignedintgetLRUClock(void){return(mstime()/LRU_CLOCK_RESOLUTION)LRU_CLOCK_MAX;}计算LRU时间方法如下：
unsignedlonglongestimateObjectIdleTime(robj*o){unsignedlonglonglruclock=LRU_CLOCK();if(lruclock=o-lru){return(lruclock-o-lru)*LRU_CLOCK_RESOLUTION;}else{//处理LRU时间溢出的情况return(lruclock+(LRU_CLOCK_MAX-o-lru))*LRU_CLOCK_RESOLUTION;}}当LRU_CLOCK_RESOLUTION为ms时，robj.lru最长可记录的LRU时长为天0xFFFFFF//24。
更新LFU计数
当时使用LFU算法时，robj.lru被分为两部分：16bits记录最近一次访问时间，8bits用作计数器
voidupdateLFU(robj*val){unsignedlongcounter=LFUDecrAndReturn(val);//衰减计数counter=LFULogIncr(counter);//增加计数val-lru=(LFUGetTimeInMinutes()8)
counter;//更新时间}更新访问时间
前16bits用于保存最近一次被访问的时间：
/***获取UNIX分钟时间戳，且只保留最低16bits*用于表示最近一次衰减时间LDT(lastdecrementtime)*/unsignedlongLFUGetTimeInMinutes(void){return(server.unixtime/60);}增加访问计数
后8bits是一个对数计数器logarithmiccounter，里面保存的是访问次数的对数：
#defineLFU_INIT_VAL5//对数递增计数器，最大值为uint8_tLFULogIncr(uint8_tcounter){if(counter==)return;doubler=(double)rand()/RAND_MAX;doublebaseval=counter-LFU_INIT_VAL;if(baseval0)baseval=0;doublep=1.0/(baseval*server.lfu_log_factor+1);if(rp)counter++;returncounter;}当server.lfu_log_factor=10时，p=1/((counter-LFU_INIT_VAL)*server.lfu_log_factor+1)的增长函数如图所示：
使用函数rand()生成的介于0与1之间随机浮点数r符合均匀分布，随着counter的增大，其自增成功的概率迅速降低。
下列表格展示了counter在不同lfu_log_factor情况下，达到饱和（）所需的访问次数：
+--------+------------+------------+------------+------------+------------+
factor
hits
hits
Khits
1Mhits
10Mhits
+--------+------------+------------+------------+------------+------------+
0
+--------+------------+------------+------------+------------+------------+
1
18
49
+--------+------------+------------+------------+------------+------------+
10
10
18
+--------+------------+------------+------------+------------+------------+
8
11
49
+--------+------------+------------+------------+------------+------------+衰减访问计数
同样的，为了保证过期的热点数据能够被及时淘汰，redis使用如下衰减函数：
//计算距离上一次衰减的时间，单位为分钟unsignedlongLFUTimeElapsed(unsignedlongldt){unsignedlongnow=LFUGetTimeInMinutes();if(now=ldt)returnnow-ldt;return-ldt+now;}/***衰减函数，返回根据LDT时间戳衰减后的LFU计数*不更新计数器*/unsignedlongLFUDecrAndReturn(robj*o){unsignedlongldt=o-lru8;unsignedlongcounter=o-lru;/***衰减因子server.lfu_decay_time用于控制计数器的衰减速度*每过server.lfu_decay_time分钟访问计数减1*默认值为1*/unsignedlongnum_periods=server.lfu_decay_time?LFUTimeElapsed(ldt)/server.lfu_decay_time:0;if(num_periods)counter=(num_periodscounter)?0:counter-num_periods;returncounter;}16bits最多能保存的分钟数，换算成天数约为45天，因此LDT时间戳每隔45天就会重置一次。
执行删除
每当客户端执行命令产生新数据时，redis会检查内存使用是否超过maxmemory，如果超过则尝试根据maxmemory_policy淘汰数据：
//redis处理命令的主方法，在真正执行命令前，会有各种检查，包括对OOM情况下的处理:intprocessCommand(client*c){//...//设置了maxmemory时，如果有必要，尝试释放内存(evict)if(server.maxmemory!server.lua_timedout){intout_of_memory=(performEvictions()==EVICT_FAIL);//...//如果释放内存失败，并且当前将要执行的命令不允许OOM（一般是写入类命令）if(out_of_memoryreject_cmd_on_oom){rejectCommand(c,shared.oomerr);//向客户端返回OOMreturnC_OK;}}}实际执行删除的是performEvictions函数：
intperformEvictions(void){//循环，尝试释放足够大的内存while(mem_freed(longlong)mem_tofree){//...if(server.maxmemory_policy(MAXMEMORY_FLAG_LRU
MAXMEMORY_FLAG_LFU)
server.maxmemory_policy==MAXMEMORY_VOLATILE_TTL){/***redis使用的是近似LRU/LFU算法*在淘汰对象时不会遍历所有记录，而是对记录进行采样*EvictionPoolLRU被用于临时存储应该被优先淘汰的样本数据*/structevictionPoolEntry*pool=EvictionPoolLRU;//根据配置的maxmemory-policy，拿到一个可以释放掉的bestkeywhile(bestkey==NULL){unsignedlongtotal_keys=0,keys;//遍历所有的db实例for(i=0;iserver.dbnum;i++){db=server.db+i;dict=(server.maxmemory_policyMAXMEMORY_FLAG_ALLKEYS)?db-dict:db-expires;//根据policy选择采样的集合（keyspace或expireset）if((keys=dictSize(dict))!=0){//采样并填充poolevictionPoolPopulate(i,dict,db-dict,pool);total_keys+=keys;}}//遍历pool中的记录，释放内存for(k=EVPOOL_SIZE-1;k=0;k--){if(pool[k].key==NULL)continue;bestdbid=pool[k].dbid;if(server.maxmemory_policyMAXMEMORY_FLAG_ALLKEYS){de=dictFind(server.db[pool[k].dbid].dict,pool[k].key);}else{de=dictFind(server.db[pool[k].dbid].expires,pool[k].key);}//将记录从pool中剔除if(pool[k].key!=pool[k].cached)sdsfree(pool[k].key);pool[k].key=NULL;pool[k].idle=0;if(de){//提取该记录的keybestkey=dictGetKey(de);break;}else{/*Ghost...Iterateagain.*/}}}}//最终选中了一个bestkeyif(bestkey){//如果配置了lazyfree-lazy-eviction，尝试异步删除if(server.lazyfree_lazy_eviction)dbAsyncDelete(db,keyobj);elsedbSyncDelete(db,keyobj);//...}else{gotocant_free;/*nothingtofree...*/}}}负责采样的evictionPoolPopulate函数：
#defineEVPOOL_SIZE16#defineEVPOOL_CACHED_SDS_SIZEstructevictionPoolEntry{unsignedlonglongidle;/*LRU空闲时间/LFU频率倒数（优先淘汰该值较大的记录）*/sdskey;/*参与淘汰筛选的键*/sdscached;/*键名缓存*/intdbid;/*数据库ID*/};//evictionPool数组用于辅助eviction操作staticstructevictionPoolEntry*evictionPoolEntry;/***在给定的sampledict集合中进行采样*并将其中应该被淘汰的记录记录至evictionPool*/voidevictionPoolPopulate(intdbid,dict*sampledict,dict*keydict,structevictionPoolEntry*pool){intj,k,count;dictEntry*samples[server.maxmemory_samples];//从sampledict中随机获取maxmemory_samples个样本数据count=dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);//遍历样本数据for(j=0;jcount;j++){//根据maxmemory_policy计算样本空闲时间idleif(server.maxmemory_policyMAXMEMORY_FLAG_LRU){idle=estimateObjectIdleTime(o);}elseif(server.maxmemory_policyMAXMEMORY_FLAG_LFU){idle=-LFUDecrAndReturn(o);}else{//...}k=0;//根据idle定位样本在evictionPool中的索引（样本按照idle升序）while(kEVPOOL_SIZEpool[k].keypool[k].idleidle)k++;if(k==0pool[EVPOOL_SIZE-1].key!=NULL){//样本空闲时间不够长，不参与该轮evictioncontinue;}elseif(kEVPOOL_SIZEpool[k].key==NULL){//样本对应的位置为空，可以直接插入至该位置}else{//样本对应的位置已被占用，移动其他元素空出该位置}//...//将样本数据插入其对应的位置kintklen=sdslen(key);if(klenEVPOOL_CACHED_SDS_SIZE){pool[k].key=sdsdup(key);}else{//如果key长度不超过EVPOOL_CACHED_SDS_SIZE，则复用sds对象}pool[k].idle=idle;pool[k].dbid=dbid;}}Java实现
在了解以上知识后，尝试使用Java实现线程安全的淘汰策略。
确定簿记结构
在一个多线程安全的缓存中，很重要的一点是减少簿记：
一方面避免额外状态的维护开销另一方面可以减少系统处于不一致状态的边界情况因此参考redis使用计数器来记录访问模式：
/***缓存记录*/publicabstractclassCacheEntry{//CASUpdaterprivatestaticfinalAtomicLongFieldUpdaterCacheEntryTTL_UPDATER=AtomicLongFieldUpdater.newUpdater(CacheEntry.class,ttl);//缓存记录的剩余存活时间（无符号长整数）privatevolatilelongttl;protectedCacheEntry(longttl){this.ttl=ttl;}publiclongttl(){returnttl;}//支持并发更新TTLpublicbooleancasTTL(longold,longttl){returnTTL_UPDATER.