服务器之家

服务器之家 > 正文

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

时间:2021-11-08 22:58     来源/作者:董泽润的技术笔记

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

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

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

上图代表从 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 实现

  1. intprocessCommand(redisClient*c){
  2. ......
  3. /*Handlethemaxmemorydirective.
  4. *
  5. *Firstwetrytofreesomememoryifpossible(iftherearevolatile
  6. *keysinthedataset).Iftherearenottheonlythingwecando
  7. *isreturninganerror.*/
  8. if(server.maxmemory){
  9. intretval=freeMemoryIfNeeded();
  10. if((c->cmd->flags&REDIS_CMD_DENYOOM)&&retval==REDIS_ERR){
  11. flagTransaction(c);
  12. addReply(c,shared.oomerr);
  13. returnREDIS_OK;
  14. }
  15. }
  16. ......
  17. }

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

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

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

LFU 实现

  1. robj*lookupKey(redisDb*db,robj*key,intflags){
  2. dictEntry*de=dictFind(db->dict,key->ptr);
  3. if(de){
  4. robj*val=dictGetVal(de);
  5. /*Updatetheaccesstimefortheageingalgorithm.
  6. *Don'tdoitifwehaveasavingchild,asthiswilltrigger
  7. *acopyonwritemadness.*/
  8. if(!hasActiveChildProcess()&&!(flags&LOOKUP_NOTOUCH)){
  9. if(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){
  10. updateLFU(val);
  11. }else{
  12. val->lru=LRU_CLOCK();
  13. }
  14. }
  15. returnval;
  16. }else{
  17. returnNULL;
  18. }
  19. }

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

  1. *Wesplitthe24bitsintotwofields:
  2. *
  3. *16bits8bits
  4. *+----------------+--------+
  5. *+Lastdecrtime|LOG_C|
  6. *+----------------+--------+

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

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

  1. unsignedlongLFUTimeElapsed(unsignedlongldt){
  2. unsignedlongnow=LFUGetTimeInMinutes();
  3. if(now>=ldt)returnnow-ldt;
  4. return65535-ldt+now;
  5. }

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

LFU 获取己有计数

  1. *counterofthescannedobjectsifneeded.*/
  2. unsignedlongLFUDecrAndReturn(robj*o){
  3. unsignedlongldt=o->lru>>8;
  4. unsignedlongcounter=o->lru&255;
  5. unsignedlongnum_periods=server.lfu_decay_time?LFUTimeElapsed(ldt)/server.lfu_decay_time:0;
  6. if(num_periods)
  7. counter=(num_periods>counter)?0:counter-num_periods;
  8. returncounter;
  9. }

num_periods 代表计算出来的待衰减计数,lfu_decay_time 代表衰减系数,默认值是 1,如果 lfu_decay_time 大于 1 衰减速率会变得很慢

最后返回的计数值为衰减之后的,也有可能是 0

LFU 计数更新并取对数

  1. /*Logarithmicallyincrementacounter.Thegreateristhecurrentcountervalue
  2. *thelesslikelyisthatitgetsreallyimplemented.Saturateitat255.*/
  3. uint8_tLFULogIncr(uint8_tcounter){
  4. if(counter==255)return255;
  5. doubler=(double)rand()/RAND_MAX;
  6. doublebaseval=counter-LFU_INIT_VAL;
  7. if(baseval<0)baseval=0;
  8. doublep=1.0/(baseval*server.lfu_log_factor+1);
  9. if(r
  10. returncounter;
  11. }

计数超过 255, 就不用算了,直接返回即可。LFU_INIT_VAL 是初始值,默认是 5

如果减去初始值后 baseval 小于 0 了,说明快过期了,就更倾向于递增 counter 值

  1. doublep=1.0/(baseval*server.lfu_log_factor+1);

这个概率算法中 lfu_log_factor 是对数底,默认是 10, 当 counter 值较小时自增的概率较大,如果 counter 较大,倾向于不做任何操作

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

counter 值从 0~255 可以表示很大的访问频率,足够用了

  1. #+--------+------------+------------+------------+------------+------------+
  2. #|factor|100hits|1000hits|100Khits|1Mhits|10Mhits|
  3. #+--------+------------+------------+------------+------------+------------+
  4. #|0|104|255|255|255|255|
  5. #+--------+------------+------------+------------+------------+------------+
  6. #|1|18|49|255|255|255|
  7. #+--------+------------+------------+------------+------------+------------+
  8. #|10|10|18|142|255|255|
  9. #+--------+------------+------------+------------+------------+------------+
  10. #|100|8|11|49|143|255|
  11. #+--------+------------+------------+------------+------------+------------+

基于这个特性,我们就可以用 redis-cli --hotkeys 命令,来查看系统中的最近一段时间的热 key, 非常实用。老版本中是没这个功能的,需要人工统计

  1. $redis-cli--hotkeys
  2. #Scanningtheentirekeyspacetofindhotkeysaswellas
  3. #averagesizesperkeytype.Youcanuse-i0.1tosleep0.1sec
  4. #per100SCANcommands(notusuallyneeded).
  5. ......
  6. [47.62%]Hotkey'key17'foundsofarwithcounter6
  7. [57.14%]Hotkey'key43'foundsofarwithcounter7
  8. [57.14%]Hotkey'key14'foundsofarwithcounter6
  9. [85.71%]Hotkey'key42'foundsofarwithcounter7
  10. [85.71%]Hotkey'key45'foundsofarwithcounter8
  11. [95.24%]Hotkey'key50'foundsofarwithcounter7
  12. --------summary-------
  13. Sampled105keysinthekeyspace!
  14. hotkeyfoundwithcounter:7keyname:key40
  15. hotkeyfoundwithcounter:7keyname:key42
  16. hotkeyfoundwithcounter:7keyname:key50

谈谈缓存的指标

前面提到的是 redis LFU 实现,这是集中式的缓存,我们还有很多进程的本地缓存。如何评价一个缓存实现的好坏,有好多指标,细节更重要

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

吞吐量:常说的 QPS, 对标 bucket 实现的 hashmap 复杂度是 O(1), 缓存复杂度要高一些,还有锁竞争要处理,总之缓存库实现的效率要高

缓存命中率:光有吞吐量还不够,缓存命中率也非常关键,命中率越高说明引入缓存作用越大

高级特性:缓存指标统计,如何应对缓存击穿等等

原文链接:https://mp.weixin.qq.com/s/xU401KzBSWbgj7fokRA41A

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部