Redis的键过期策略及内存淘汰策略简介

Rocky_chi 2020-11-09 00:08:21
redis Nosql github rdb Persist


Redis

Redis是高性能的基于内存的NoSQL数据库。因为内存是比较宝贵的资源,无法无限制使用,所以Redis提供了:

  1. 键过期策略来防止内存饱和。
  2. 内存淘汰策略来使得内存饱和之后继续对外提供服务。

内存过期策略

expire命令

Redis提供了expire命令来给一个键(key)设置过期时间:

redis> SET foo "bar"
"OK"
redis> EXPIRE foo 10
(integer) 1
redis> TTL foo
(integer) 10

类似setex命令,也可以对目标键设置过期时间,但它其实相当于setexpire两个命令的原子操作。 expire只能作用于Redis中的键,所以无法对list或者set中的元素设置过期时间。对某个键调用删除(delete)或者重写(override)的命令如del,set,getset之后,会清除键上的过期时间;调用persist命令也会清除键上的过期时间;而修改键内容的操作如incr,hset,则不会对键的过期时间产生影响。

键的过期原理

Redis键有两种过期方式:被动方式(passive way)和主动方式(active way)。

被动删除

当某个设置了过期时间的键被访问时,如果发现它已经过期,Redis会直接将其删除并返回一个空值。

主动删除

被动删除是一种惰性删除机制,它不会花很多时间在键的删除上,保证了Redis的高性能。但是如果键一直不被访问,将导致内存泄漏。所以Redis提供了主动删除的策略:Redis会定期地(默认每秒钟10次)在设置了过期时间的键的集合(expire set)中,随机选择一部分键,判断删除。具体步骤如下:

  1. 在过期键集合中随机选择20个键
  2. 将其中已经过期的键删除
  3. 如果其中过期的键占比超过25%,则重复步骤1

以上步骤会在Redis的每个(16个)数据库中都执行一遍,并且每次执行都会限制在一定时间之内,防止占用过多时间影响Redis处理性能。 这是一种基于概率的折中方案,既可以防止扫描过多的过期键影响Redis的吞吐量,同时也保证了过期键不会占用太多的空间。

过期数据的恢复及同步

Redis的过期策略只在主节点中执行,当某个键过期时,主节点会往其副本节点(replicas)发送一个del命令,由此删除副本节点上的数据,从而保证数据的一致性,同时,也会往aof文件中写入一个del命令。 在Redisaof文件中恢复的过程中,如果发现某个键已过期,会直接将之删除。类似的,在生成rdb文件时,如果发现过期键,该键将不会被写入快照文件。

注意,键的过期时间是基于机器的unix时间戳的,所以必须要保证机器时间的稳定性。比如将某个键的过期时间设置为1分钟之后,同时将机器时间调快1分钟,那么这个键将立马被认为是过期的。

Redis过期策略的源码在这里

内存淘汰策略

即使有了键过期策略,我们还是会不可避免地遇到内存不够的情况(已使用内存大于指定的maxmemory)。为了使Redis能继续工作(添加数据),它会触发内存淘汰策略,来清除部分已存在的数据。

Redis4.0之前的内存淘汰策略

内存淘汰策略可以用maxmemory-policy来指定,在Redis4.0之前提供了以下方式:

  • noeviction: 不淘汰内存,当有Redis收到新的写入命令时,直接返回错误(查询以及del等命令除外)
  • allkeys-lru: 在所有的键上,应用LRU(less recently used)策略,即淘汰最近最少使用的键
  • volatile-lru: 在设置了过期时间的键上,应用LRU策略,如果过期键集为空,则和noeviction策略一样
  • allkeys-random: 随机淘汰一部分键
  • volatile-random: 随机淘汰设置了过期时间的键,如果过期键集为空,则和noeviction策略一样
  • volatile-ttl: 在设置了过期时间的键集中,尽量淘汰TTL较小的键,即尽量淘汰即将过期的键,如果过期键集为空,则和noeviction策略一样

当客户端发送一条新的插入命令时,Redis通过检查发现当前内存占用超过了maxmemory,它将调用设置好的内存淘汰策略以腾出一部分内存空间,用来执行新的命令。

LRU算法

精确的LRU算法将耗费较多的内存,所以Redis采用了一种近似的LRU算法:从集合中进行采样,并淘汰样本中最老的数据。可以通过maxmemory-samples(默认5)调整抽样的样本数量来控制LRU算法的精度。

下面是RedisObject的定义:

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;

其中lru就是用来记录键的LRU时间的字段。算法就是对比这个字段的值来淘汰样本中老的数据的。

以下图片来自Redis官网,是理论LRURedis2.8 LRU 5samplesRedis3.0 LRU 5samplesRedis3.0 LRU 10samples的一个对比,可以看到Redis3.0 LRU 10samples已经很接近理论精度了。 LRU Comparison

LFU策略

如果有一个键很少会被访问,但是恰巧最近被访问了,根据LRU策略,它是不会被清除的。所以LRU并不能非常确切地描述键的冷热。为此,从4.0版本开始,Redis提供了一种新的算法:LFU(Least Frequently Used)。在这种模式下,Redis会记录键的访问频率,访问频率越低,越有可能被清除。

LFU同样可以分别针对allkeysvolatile

  • volatile-lfu: 在设置了过期时间的键上,应用LFU策略.
  • allkeys-lfu: 在所有键上,应用LRU策略,如果过期键集为空,则和noeviction策略一样.

LFU算法利用了一个计数器(probabilistic counter),用来记录键被访问的频率:当键被访问,计数器会递增;每隔一定的周期,计数器会递减。其实这个计数器,依然存储在redisObjectlru字段中,它记录了最近一次计数器递减的时间计数器的值两个信息。可以想到,有两个维度可以影响到计数器:

  1. 计数器递减的周期:周期性递减可以保证计数器的时效性,并且保证值短期内不会无限制增长超过最大长度。
  2. 计数器递增的速度:事实上Redis只给访问计数提供了8位(范围0-255)的存储空间,所以必须要控制计数器的递增速度来发挥每一位的效用。

对应地,Redis为这两个维度分别提供了lfu-log-factor(默认值10)和lfu-decay-time(默认值1)两个参数来调整算法的精度。默认值是基于实验的结果,即:约100万次请求之后,计数器达到最大值;每隔1分钟,计数器递减一次。lfu-decay-time很好理解。对于lfu-log-factor,可以参照下表:

factor 100 hits 1000 hits 100K hits 1M hits 10M hits
0 104 255 255 255 255
1 18 49 255 255 255
10 10 18 142 255 255
100 8 11 49 143 255

前面已经介绍过,计数器的范围是0-255之间(8bit存储),从表中可以看到,随着访问次数变大,计数器增长会变慢;当lfu-log-factor的值设的越小,计数器越快达到最大值255。所以,其实这个参数是用来控制高访问频率低访问频率情况下算法的精度的。

总结

作为内存数据库,内存资源对于Redis来说是很宝贵的。Redis采用了访问删除定期删除两种方式来处理过期(expired)数据;当应用内存达到maxmemory时,Redis会启用内存淘汰策略,最常用的有两种算法:最近最少使用(LRU)和最低频率访问(LFU)。

参考

how redis expires keys
Using Redis as an LRU cache

版权声明
本文为[Rocky_chi]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/2411391/blog/4708293

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云