阅读 Redis 源码，学习缓存淘汰算法 W-TinyLFU

所有 IT 从业者都接触过缓存，一定了解基本工作原理，业界流行一句话：缓存就是万金油，哪里有问题哪里抹一下。那他的本质是什么呢?

上图代表从 cpu 到底层硬盘不同层次，不同模块的运行速度，上层多加一层 cache, 就能解决下层的速度慢的问题，这里的慢是指两点：IO 慢和 cpu 重复计算缓存中间结果

但是 cache 受限于成本，cache size 一般都是固定的，所以数据需要淘汰，由此引出一系列其它问题：缓存一致性、击穿、雪崩、污染等等，本文通过阅读 redis 源码，学习主流淘汰算法

如果不是 leetcode 146 LRU[1] 刷题需要，我想大家也不会手写 cache, 简单的实现和工程实践相距十万八千里，真正 production ready 的缓存库非常考验细节

Redis 缓存淘汰配置

一般 redis 不建义当成存储使用，只允许当作 cache, 并设置 max-memory, 当内存使用达到最大值时，redis-server 会根据不同配置开始删除 keys. Redis 从 4.0 版本引进了 LFU[2], 即 Least Frequently Used，4.0 以前默认使用 LRU 即 Least Recently Used

volatile-lru 只针对设置 expire 过期的 key 进行 lru 淘汰
allkeys-lru 对所有的 key 进行 lru 淘汰
volatile-lfu 只针对设置 expire 过期的 key 进行 lfu 淘汰
allkeys-lfu 对所有的 key 进行 lfu 淘汰
volatile-random 只针对设置 expire 过期的进行随机淘汰
allkeys-random 所有的 key 随机淘汰
volatile-ttl 淘汰 ttl 过期时间最小的 key
noeviction 什么都不做，如果此时内存已满，系统无法写入

默认策略是 noeviction, 也就是不驱逐，此时如果写满，系统无法写入，建义设置为 LFU 相关的。LRU 优先淘汰最近未被使用，无法应对冷数据，比如热 keys 短时间没有访问，就会被只使用一次的冷数据冲掉，无法反应真实的使用情况

LFU 能避免上述情况，但是朴素 LFU 实现无法应对突发流量，无法驱逐历史热 keys，所以 redis LFU 实现类似于 W-TinyLFU[3], 其中 W 是 windows 的意思，即一定时间窗口后对频率进行减半，如果不减的话，cache 就成了对历史数据的统计，而不是缓存

上面还提到突发流量如果应对呢?答案是给新访问的 key 一个初始频率值，不至于由于初始值为 0 无法更新频率

LRU 实现

intprocessCommand(redisClient*c){
......
/*Handlethemaxmemorydirective.
*
*Firstwetrytofreesomememoryifpossible(iftherearevolatile
*keysinthedataset).Iftherearenottheonlythingwecando
*isreturninganerror.*/
if(server.maxmemory){
intretval=freeMemoryIfNeeded();
if((c->cmd->flags&REDIS_CMD_DENYOOM)&&retval==REDIS_ERR){
flagTransaction(c);
addReply(c,shared.oomerr);
returnREDIS_OK;
}
}
......
}

在每次处理 client 命令时都会调用 freeMemoryIfNeeded 检查是否有必有驱逐某些 key, 当 redis 实际使用内存达到上限时开始淘汰。但是 redis 做的比较取巧，并没有对所有的 key 做 lru 队列，而是按照 maxmemory_samples 参数进行采样，系统默认是 5 个 key

阅读 Redis 源码，学习缓存淘汰算法 W-TinyLFU

上面是很经典的一个图，当到达 10 个 key 时效果更接近理论上的 LRU 算法，但是 cpu 消耗会变高，所以系统默认值就够了。

LFU 实现

robj*lookupKey(redisDb*db,robj*key,intflags){
dictEntry*de=dictFind(db->dict,key->ptr);
if(de){
robj*val=dictGetVal(de);
/*Updatetheaccesstimefortheageingalgorithm.
*Don'tdoitifwehaveasavingchild,asthiswilltrigger
*acopyonwritemadness.*/
if(!hasActiveChildProcess()&&!(flags&LOOKUP_NOTOUCH)){
if(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){
updateLFU(val);
}else{
val->lru=LRU_CLOCK();
}
}
returnval;
}else{
returnNULL;
}
}

当 lookupKey 访问某 key 时，会更新 LRU. 从 redis 4.0 开始逐渐引入了 LFU 算法，由于复用了 LRU 字段，所以只能使用 24 bits

*Wesplitthe24bitsintotwofields:
*
*16bits8bits
*+----------------+--------+
*+Lastdecrtime|LOG_C|
*+----------------+--------+

其中低 8 位 counter 用于计数频率，取值为从 0~255, 但是经过取对数的，所以可以表示很大的访问频率

高 16 位 ldt (Last Decrement Time)表示最后一次访问的 miniutes 时间戳, 用于衰减 counter 值，如果 counter 不衰减的话就变成了对历史 key 访问次数的统计了，而不是 LFU

unsignedlongLFUTimeElapsed(unsignedlongldt){
unsignedlongnow=LFUGetTimeInMinutes();
if(now>=ldt)returnnow-ldt;
return65535-ldt+now;
}

注意由于 ldt 只用了 16位计数，最大值 65535，所以会出现回卷 rewind

LFU 获取己有计数

*counterofthescannedobjectsifneeded.*/
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;
}