Redis's key expiration strategy and memory elimination strategy

Rocky_chi 2020-11-09 00:08:21
redis key expiration strategy memory


Redis

Redis It's high performance, memory based NoSQL database . Because memory is a valuable resource , You can't use it without restrictions , therefore Redis Provides :

  1. Key expiration policy To prevent memory saturation .
  2. Memory retirement strategy To make the memory saturated and continue to provide external services .

Memory expiration policy

expire command

Redis Provides expire Command to give a key (key) Set expiration time :

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

similar setex command , You can also set the expiration time for the target key , But it's actually equivalent to set and expire Atomic operation of two commands . expire It only works on Redis The key , So there's no way to list perhaps set Set the expiration time for the element in . Call delete on a key (delete) Or rewrite (override) Such as del,set,getset after , Will clear the expiration time on the key ; call persist The command also clears the expiration time on the key ; The operation of modifying the key content is as follows incr,hset, Does not affect the expiration time of the key .

Key expiration principle

Redis There are two ways Keys expire : Passive way (passive way) And the active way (active way).

Passive delete

When a key with an expiration time set is accessed , If it's found to be out of date ,Redis Will directly delete it and return a null value .

Active delete

Passive deletion is an inert deletion mechanism , It doesn't take a lot of time to delete keys , To ensure the Redis A high performance . But if the key is never accessed , Will cause a memory leak . therefore Redis Provides a proactive deletion strategy :Redis Will regularly ( By default, every second 10 Time ) In the set of keys with expiration time set (expire set) in , Select a random number of keys , Judge to delete . The specific steps are as follows :

  1. Randomly select from the set of expired keys 20 Key
  2. Delete the expired key
  3. If the percentage of expired keys exceeds 25%, Then repeat the steps 1

The above steps will be in Redis Each (16 individual ) It's all executed in the database , And each execution is limited to a certain amount of time , Prevent taking up too much time to affect Redis Processing performance . It's a probability based compromise , It can prevent scanning too many expired keys Redis Throughput , At the same time, it also ensures that the expired key will not take up too much space .

Recovery and synchronization of expired data

Redis The expiration policy of is only executed in the master node , When a key expires , The master node will go to its replica node (replicas) Send a del command , This removes the data on the replica node , To ensure data consistency , meanwhile , I will go to aof Write a del command . stay Redis from aof In the process of recovery in the file , If a key is found to be out of date , It will be deleted directly . Allied , It's generating rdb When you file , If you find an expired key , The key will not be written to the snapshot file .

Be careful , The expiration time of a key is machine based unix Time stamp Of , So we must ensure the stability of machine time . For example, set the expiration time of a key to 1 Minutes later , At the same time, turn the machine time up 1 minute , Then the key will immediately be considered expired .

Redis The source code of the expiration policy is in here .

Memory retirement strategy

Even if a Key expiration policy , We will inevitably run out of memory ( Memory used is greater than the specified maxmemory). In order to make Redis Can continue to work ( Add data ), It triggers it Memory retirement strategy , To clear part of the existing data .

Redis4.0 Previous memory elimination strategy

Memory elimination strategy can be used maxmemory-policy To specify the , stay Redis4.0 The following methods have been provided before :

  • noeviction: Don't eliminate memory , When there is Redis Receive new write in On command , Direct return error ( Inquiry and del Except for orders )
  • allkeys-lru: On all the keys , application LRU(less recently used) Strategy , That is to eliminate the least recently used keys
  • volatile-lru: On the key with the expiration time set , application LRU Strategy , If the expired keyset is empty , And noeviction The strategy is the same
  • allkeys-random: Random elimination of some keys
  • volatile-random: Random elimination of keys with expiration time set , If the expired keyset is empty , And noeviction The strategy is the same
  • volatile-ttl: Set the expiration time of the key , Try to eliminate TTL Smaller keys , That is, try to eliminate the expired keys , If the expired keyset is empty , And noeviction The strategy is the same

When the client sends a new insert command ,Redis By checking, it is found that the current memory consumption exceeds maxmemory, It will call the set memory elimination strategy to free up some memory space , Used to execute new commands .

LRU Algorithm

The precise LRU The algorithm will consume more memory , therefore Redis An approximation is used LRU Algorithm : Sampling from a set , And eliminate the oldest data in the sample . Can pass maxmemory-samples( Default 5) Adjust the sample size to control LRU The accuracy of the algorithm .

Here is Redis in Object The definition of :

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

among lru It's used to record keys LRU Time field . The algorithm is to compare the value of this field to eliminate the old data in the sample .

The following pictures are from Redis Official website , It's theory LRU,Redis2.8 LRU 5samples,Redis3.0 LRU 5samples and Redis3.0 LRU 10samples A contrast to , You can see Redis3.0 LRU 10samples It's close to the theoretical accuracy . LRU Comparison

LFU Strategy

If there's a key, it's rarely accessed , But it happened to be recently interviewed , according to LRU Strategy , It's not going to be cleared . therefore LRU It doesn't exactly describe the hot and cold of the bond . So , from 4.0 Version start ,Redis Provides a new algorithm :LFU(Least Frequently Used). In this mode ,Redis Will record the access frequency of the key , The lower the frequency of access , The more likely it is to be cleared .

LFU It can also be targeted at allkeys and volatile

  • volatile-lfu: On the key with the expiration time set , application LFU Strategy .
  • allkeys-lfu: On all the keys , application LRU Strategy , If the expired keyset is empty , And noeviction The strategy is the same .

LFU The algorithm uses a counter (probabilistic counter), Used to record the frequency at which keys are accessed : When the key is accessed , The counter will go up ; At regular intervals , The counter is decremented . Actually, this counter , Still stored in redisObject Of lru Field , It records The last time the counter was decremented and The value of the counter Two messages . You can think of , There are two dimensions that can affect counters :

  1. The period of the counter decrement : Periodic decrement can ensure the timeliness of the counter , And the guarantee value will not exceed the maximum length in the short term .
  2. The speed at which the counter goes up : in fact Redis Only to Access count Provides 8 position ( Range 0-255) Storage space , Therefore, it is necessary to control the increasing speed of the counter to play the role of each bit .

Correspondingly ,Redis These two dimensions provide lfu-log-factor( The default value is 10) and lfu-decay-time( The default value is 1) Two parameters to adjust the accuracy of the algorithm . The default value is based on experimental results , namely : about 100 Ten thousand times After the request , The counter is at its maximum ; every other 1 minute , The counter is decremented once .lfu-decay-time Well understood. . about lfu-log-factor, You can refer to the following table :

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

I've already introduced , The range of the counter is 0-255 Between (8bit Storage ), As you can see from the table , As the number of visits increases , The counter will grow slower ; When lfu-log-factor The smaller the value of , The faster the counter reaches its maximum 255. therefore , In fact, this parameter is used to control High frequency of visits And Low access frequency In this case, the accuracy of the algorithm is .

summary

As in memory database , Memory resources for Redis It's very valuable .Redis Adopted Access delete And Delete periodically There are two ways to deal with expiration (expired) data ; When the application memory reaches maxmemory when ,Redis Memory obsolescence policy will be enabled , There are two most commonly used algorithms : Recently at least use (LRU) And the lowest frequency of visits (LFU).

Reference resources

how redis expires keys
Using Redis as an LRU cache

版权声明
本文为[Rocky_chi]所创,转载请带上原文链接,感谢

  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课程百度云