author ： Kobayashi coding

Computer eight part essay website ：https://xiaolincoding.com

Hello everyone , I'm Xiao Lin .

Redis Of 「 Memory retirement strategy 」 and 「 Expiration deletion policy 」, Many friends are easily confused , Although these two mechanisms are used to delete , But the triggering conditions and strategies are different .

Let's talk about it today ,「 Memory retirement strategy 」 and 「 Expiration deletion policy 」.

Start ！

Expiration deletion policy

Redis Yes, yes key Set the expiration time , Therefore, there needs to be a corresponding mechanism to delete expired key value pairs , What does this work is the expired key deletion strategy .

How to set expiration time ？

First, yes key Command to set expiration time . Set up key There are totally 4 individual ：

  • expire <key> <n>： Set up key stay n Seconds after expired , such as expire key 100 Presentation settings key stay 100 Seconds after expired ;
  • pexpire <key> <n>： Set up key stay n Expired in milliseconds , such as pexpire key2 100000 Presentation settings key2 stay 100000 millisecond （100 second ） After expired .
  • expireat <key> <n>： Set up key At some time stamp （ Accurate to seconds ） Expires after , such as expireat key3 1655654400 Express key3 At the time stamp 1655654400 After expired （ Accurate to seconds ）;
  • pexpireat <key> <n>： Set up key At some time stamp （ Accurate to milliseconds ） Expires after , such as pexpireat key4 1655654400000 Express key4 At the time stamp 1655654400000 After expired （ Accurate to milliseconds ）

Of course , When setting the string , You can also do it at the same time key Set expiration time , share 3 Orders ：

  • set <key> <value> ex <n> ： When setting key value pairs , Also specify the expiration time （ Accurate to seconds ）;
  • set <key> <value> px <n> ： When setting key value pairs , Also specify the expiration time （ Accurate to milliseconds ）;
  • setex <key> <n> <valule> ： When setting key value pairs , Also specify the expiration time （ Accurate to seconds ）.

If you want to see something key The remaining survival time , have access to TTL <key> command .

#  When setting key value pairs , At the same time, specify the expiration time bit  60  second 
> setex key1 60 value1
OK

#  see  key1  How much time is left for expiration 
> ttl key1
(integer) 56
> ttl key1
(integer) 52

If you suddenly repent , Cancel key The expiration time of , You can use PERSIST <key> command .

#  Cancel  key1  The expiration time of 
> persist key1
(integer) 1

#  Use up  persist  After the command ,
#  Check it out  key1  The result of survival time is  -1, indicate  key1  Never expire  
> ttl key1 
(integer) -1

How to judge key It has expired ？

Whenever we talk about a key When the expiration time is set ,Redis Will put the key Take the expiration time and store it in a Out of date Dictionary （expires dict） in , in other words 「 Out of date Dictionary 」 Save all in the database key The expiration time of .

Expired dictionaries are stored in redisDb In structure , as follows ：

typedef struct redisDb {
    dict *dict;    /*  Database key space , Store all key value pairs  */
    dict *expires; /*  Key expiration time  */
    ....
} redisDb;

The data structure of the expired dictionary is as follows ：

  • The use of out of date Dictionaries key It's a pointer , Point to a key object ;
  • The use of out of date Dictionaries value It's a long long Type integer , This integer holds key The expiration time of ;

The data structure of the expired dictionary is shown in the following figure ：

A dictionary is actually a hash table , The biggest advantage of hash table is that we can use O(1) Time complexity to quickly find . When we look up a key when ,Redis First check that key Whether it exists in the expired dictionary ：

  • If not , Then the key value is read normally ;
  • If there is , Will get the key The expiration time of , Then compare with the current system time , If it is longer than the system time , Then it's not overdue , Otherwise, it is judged that key Has expired .

The expired key judgment process is shown in the following figure ：

What are the expiration delete policies ？

Say Redis Expire before deleting policy , Let me introduce to you first , Three common expiration deletion strategies ：

  • Delete regularly ;
  • Lazy deletion ;
  • Delete periodically ;

Next , Analyze their advantages and disadvantages respectively .

What is the scheduled deletion strategy ？

The way to delete the policy regularly is , Set up key The expiration time of , At the same time, create a scheduled event , When time arrives , Automatically executed by the event handler key Delete operation of .

Regularly delete the policy advantage ：

  • It's guaranteed to expire key Will be deleted as soon as possible , That is, the memory can be released as soon as possible . therefore , Scheduled deletion is the most memory friendly .

Regularly delete the policy shortcoming ：

  • It's overdue key In many cases , Delete expired key It may occupy a considerable part CPU Time , Not nervous in memory but CPU When time is tight , take CPU Time is used to delete expired keys irrelevant to the current task , It will undoubtedly affect the response time and throughput of the server . therefore , The timing deletion policy is very important for CPU unfriendly .

What about the lazy deletion strategy ？

The lazy deletion strategy is , Do not delete the expired key , Every time you access from the database key when , All detection key Is it overdue , If it expires, delete the key.

Lazy delete policy advantage ：

  • Because every time I visit , Will check key Is it overdue , So this strategy only uses very few system resources , therefore , Inert deletion policy pair CPU Time is the friendliest .

Lazy delete policy shortcoming ：

  • If one key It's overdue , And this key And still remain in the database , So as long as this expires key Has not been visited , The memory it occupies will not be released , Caused a certain waste of memory space . therefore , Lazy deletion strategy is not memory friendly .

What is the periodic deletion strategy ？

The practice of regularly deleting policies is , Every once in a while 「 Random 」 Take a certain number of... From the database key Inspection , And delete the expired key.

Delete the policy on a regular basis advantage ：

  • By limiting the length and frequency of deletion operations , To reduce the number of delete operations CPU Influence , At the same time, it can also delete some expired data to reduce the invalid space occupation of expired keys .

Delete the policy on a regular basis shortcoming ：

  • The effect of memory cleaning is not good , At the same time, no lazy delete uses less system resources .
  • It is difficult to determine how long and how often delete operations are performed . If it's done too often , The regular deletion policy becomes the same as the regular deletion policy , Yes CPU unfriendly ; If too little is done , That's the same as lazy deletion , Be overdue key The occupied memory will not be released in time .

Redis What is the expiration deletion policy ？

Previously, we introduced three expiration deletion strategies , Each one has its advantages and disadvantages , Using only one strategy cannot meet the actual needs .

therefore , Redis choice 「 Lazy deletion + Delete periodically 」 These two strategies are matched and used , In order to use reasonably CPU Strike a balance between time and avoiding memory waste .

Redis How to realize lazy deletion ？

Redis The lazy deletion strategy of is created by db.c In the document expireIfNeeded Function implementation , The code is as follows ：

int expireIfNeeded(redisDb *db, robj *key) {
    //  Judge  key  Is it overdue 
    if (!keyIsExpired(db,key)) return 0;
    ....
    /*  Delete expiration key  */
    ....
    //  If  server.lazyfree_lazy_expire  by  1  Indicates asynchronous deletion , On the contrary, delete synchronously ;
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

Redis When accessing or modifying key Before , Will be called expireIfNeeded Function to check it , Check key Is it overdue ：

  • If expired , Delete the key, As for choosing asynchronous deletion , Or choose to delete synchronously , according to lazyfree_lazy_expire Parameter configuration determines （Redis 4.0 The version starts with parameters ）, Then return null client ;
  • If it doesn't expire , Do nothing , Then return the normal key value pair to the client ;

The flow chart of inert deletion is as follows ：

Redis How to achieve regular deletion ？

Remember again , The practice of regularly deleting policies ： Every once in a while 「 Random 」 Take a certain number of... From the database key Inspection , And delete the expired key.

1、 How long is the inspection interval ？

stay Redis in , Default per second 10 Check the database once after expiration , This configuration is available through Redis Configuration file for redis.conf To configure , The configuration key is hz Its default value is hz 10.

Put special emphasis on , Each time you check the database, you don't traverse all of the out of date dictionaries key, Instead, a certain number of... Are randomly selected from the database key Do overdue checks .

2、 What is the number of random checks ？

I checked the source code , The implementation of periodic deletion is expire.c Under the document activeExpireCycle Function , The number of random checks is determined by ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP Defined , It is written dead in code , Values are 20.

in other words , During each round of random inspection of the database , They'll randomly choose 20 individual key Judge whether it is overdue .

Next , Tell me more about Redis The process of regular deletion ：

  1. Randomly select from the expired dictionary 20 individual key;
  2. Check this 20 individual key Is it overdue , And delete the expired key;
  3. If the current inspection has expired key The number of , exceed 5 individual （20/4）, That is to say 「 Has expired key The number of 」 Proportion 「 Random sampling key The number of 」 Greater than 25%, Then continue to repeat step 1; If it has expired key The proportion is less than 25%, Then stop deleting expired key, Then wait for the next round of inspection .

You can see , Periodic deletion is a circular process .

that Redis In order to ensure that periodic deletion will not cause excessive circulation , Causes thread to jam , For this reason, the time limit for regularly deleting circular processes is increased , Default will not exceed 25ms.

For regularly deleted processes , I wrote a pseudocode ：

do {
    // Expired quantity 
    expired = 0;
    // Number of random samples 
    num = 20;
    while (num--) {
        //1.  Randomly select from the expired dictionary  1  individual  key
        //2.  Judge that  key  Is it overdue , Delete if it has expired , At the same time  expired++
    }
    
    //  Exit after the time limit 
    if (timelimit_exit) return;

  /*  If the current inspection has expired  key  The number of , exceed  25%, Then continue random sampling , Otherwise, exit this round of inspection  */
} while (expired > 20/4); 

The process of regular deletion is as follows ：

Memory retirement strategy

Expiration deletion strategy mentioned above , Delete expired key, And when Redis The running memory of has exceeded Redis After setting the maximum memory , The memory elimination strategy will be used to delete the qualified key, To protect Redis Efficient operation .

How to set up Redis Maximum running memory ？

In profile redis.conf in , You can use the parameter maxmemory <bytes> To set the maximum running memory , Only in Redis The running memory of has reached the maximum running memory we set , Will trigger the memory elimination strategy . Operating systems with different digits ,maxmemory The default value of is different ：

  • stay 64 Bit operating system ,maxmemory The default value of is 0, Indicates that there is no memory size limit , Then no matter how much data the user stores to Redis in ,Redis It also does not check the available memory , until Redis The instance crashed due to insufficient memory and did nothing .
  • stay 32 Bit operating system ,maxmemory The default value of is 3G, because 32 The maximum number of bit machines can only support 4GB Of memory , The system itself needs certain memory resources to support the operation , therefore 32 The bit operating system limit is maximum 3 GB The available memory is very reasonable , In this way, it can avoid being caused by insufficient memory Redis Instance crash .

Redis What are the memory obsolescence strategies ？

Redis There are eight memory elimination strategies , These eight strategies can be roughly divided into 「 No data obsolescence 」 and 「 Data obsolescence 」 Two types of strategies .

1、 No data culling strategy

noeviction（Redis3.0 after , Default memory obsolescence policy ） ： It means that when the running memory exceeds the maximum set memory , Don't eliminate any data , Instead of providing services , Direct return error .

2、 Strategies for data elimination

in the light of 「 Data obsolescence 」 This kind of strategy , And then you can subdivide it into 「 Elimination in data with expiration time set 」 and 「 Elimination across all data ranges 」 These two strategies .

Elimination in data with expiration time set ：

  • volatile-random： Random elimination sets any key value of expiration time ;
  • volatile-ttl： Priority elimination of earlier expired key values .
  • volatile-lru（Redis3.0 Before , Default memory obsolescence policy ）： Eliminate all key values with expiration time set , The longest unused key value ;
  • volatile-lfu（Redis 4.0 New memory elimination strategy after ）： Eliminate all key values with expiration time set , Minimum key value used ;

Elimination across all data ranges ：

  • allkeys-random： Random elimination of any key value ;
  • allkeys-lru： Eliminate the oldest unused key value in the whole key value ;
  • allkeys-lfu（Redis 4.0 New memory elimination strategy after ）： Eliminate the least used key value in the whole key value .

How to view the current Redis Memory obsolescence strategy used ？

have access to config get maxmemory-policy command , To view the current Redis Memory obsolescence strategy , The order is as follows ：

127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"

It can be seen that , At present Redis It uses noeviction Type of memory elimination strategy , It is Redis 3.0 After that, the default memory elimination strategy , Indicates that when the running memory exceeds the maximum set memory , Don't eliminate any data , But the new operation will report an error .

How to modify Redis Memory retirement strategy ？

There are two ways to set the memory obsolescence policy ：

  • Mode one ： adopt “config set maxmemory-policy < Strategy >” Command settings . Its advantage is that it takes effect immediately after setting , No need to reboot Redis service , The disadvantage is restart Redis after , The settings will be invalid .
  • Mode two ： By modifying the Redis Configuration file modification , Set up “maxmemory-policy < Strategy >”, Its advantage is to restart Redis Post service configuration will not be lost , The disadvantage is that you have to restart Redis service , Settings can only take effect .

LRU Algorithm and LFU What's the difference between algorithms ？

LFU The memory elimination algorithm is Redis 4.0 Then add a memory elimination strategy , Then why add this algorithm ？ That must be to solve LRU The problem of algorithm .

Next , Just look at the difference between the two algorithms ？Redis How to implement these two algorithms ？

What is? LRU Algorithm ？

LRU The full name is Least Recently Used Translated into Recently at least use , Will choose to eliminate the least recently used data .

Tradition LRU The implementation of the algorithm is based on 「 Linked list 」 structure , The elements in the linked list are arranged from front to back in the order of operation , The key of the latest operation will be moved to the header , When memory obsolescence is required , Just delete the elements at the end of the linked list , Because the elements at the end of the list represent the elements that have not been used for the longest time .

Redis It is not implemented in this way LRU Algorithm , Because of the traditional LRU The algorithm has two problems ：

  • Need to use linked list to manage all cache data , It's going to cost extra space ;
  • When data is accessed , You need to move the data to the head end on the linked list , If there's a lot of data being accessed , Will bring a lot of linked list mobile operation , It's time consuming , And then it reduces Redis Cache performance .

Redis How to achieve LRU Algorithm ？

Redis It realizes a kind of The approximate LRU Algorithm , The purpose is to better save memory , its The way to achieve it is in Redis Add an additional field to the object structure of , The last access time used to record this data .

When Redis When performing memory obsolescence , Will use Random sampling to eliminate data , It's random 5 It's worth （ This value is configurable ）, then Eliminate the one that has not been used for the longest time .

Redis Realized LRU The advantages of the algorithm ：

  • There is no need to maintain a large linked list for all data , Save space ;
  • You don't have to move linked list items every time you access data , Improved cache performance ;

however LRU There's a problem with the algorithm , Can't solve cache pollution , For example, the application reads a large amount of data at one time , And these data will only be read this time , Then these data will remain Redis Cache for a long time , Cause cache pollution .

therefore , stay Redis 4.0 And then introduced LFU Algorithm to solve this problem .

What is? LFU Algorithm ？

LFU The full name is Least Frequently Used Translated into The least commonly used recently ,LFU The algorithm eliminates data according to the number of data accesses , Its core idea is “ If data has been accessed more than once , So the frequency of future visits will be higher ”.

therefore , LFU The algorithm will record the number of accesses to each data . When a data is accessed again , It will increase the number of accesses to the data . This solves the problem of being visited once in a while , Data is stored in the cache for a long time , Compared with LRU The algorithm is also more reasonable .

Redis How to achieve LFU Algorithm ？

LFU The algorithm is compared with LRU Implementation of algorithm , More records 「 Data access frequency 」 Information about .Redis The structure of the object is as follows ：

typedef struct redisObject {
    ...
      
    // 24 bits, Used to record the access information of the object 
    unsigned lru:24;  
    ...
} robj;

Redis In the object header lru Field , stay LRU Algorithm and LFU The use of the algorithm is not the same .

stay LRU In the algorithm, ,Redis The head of the object 24 bits Of lru Fields are used to record key Access timestamp for , So in LRU In mode ,Redis Can be based on... In the object header lru The value of the field record , To compare the last time key Long access time , So as to eliminate the longest unused key.

stay LFU In the algorithm, ,Redis The head of the object 24 bits Of lru Fields are divided into two segments to store , high 16bit Storage ldt(Last Decrement Time), low 8bit Storage logc(Logistic Counter).

  • ldt It's for recording key Access timestamp for ;
  • logc It's for recording key Frequency of visits , The smaller its value is, the lower its frequency of use , The easier it is to eliminate , Every new key Of logc The initial value is 5.

Be careful ,logc It's not just the number of visits , It's the frequency of visits （ Access frequency ）, because logc It will decay with time .

In every time key When interviewed , Will be right first logc Do an attenuation operation , The value of attenuation is related to the difference between before and after access time , If there is a big gap between the time of the last visit and the time of this visit , Then the greater the value of attenuation , In this way LFU The algorithm is based on Access frequency To eliminate data , Not just the number of visits . Access frequency needs to be considered key How long did your visit take place .key The longer the previous visit of is from the current time , So this key The frequency of access will be reduced accordingly , In this way, the probability of being eliminated will be greater .

Yes logc After the attenuation operation , Start to be right logc Add operation , Adding operations is not simple + 1, But according to the increase of probability , If logc The bigger key, its logc The harder it is to increase .

therefore ,Redis During a visit to key when , about logc It changes like this ：

  1. First, according to the current duration from the last visit , Come on logc To attenuate ;
  2. then , Then increase according to a certain probability logc Value

redis.conf Two configuration items are provided , Used to adjust LFU Algorithm to control logc Growth and decay of ：

  • lfu-decay-time Used to adjust logc Decay rate of , It's a number in minutes , The default value is 1,lfu-decay-time The bigger the value is. , The slower the attenuation ;
  • lfu-log-factor Used to adjust logc Growth rate of ,lfu-log-factor The bigger the value is. ,logc The slower the growth .

summary

Redis The expiration deletion strategy used is 「 Lazy deletion + Delete periodically 」, The deleted object is expired key.

The memory elimination strategy is to solve the problem of excessive memory , When Redis When the running memory of exceeds the maximum running memory , Will trigger the memory obsolescence policy ,Redis 4.0 After that, a total of 8 Memory elimination strategy , I'm also interested in this 8 Strategies for classification , as follows ：

End ！

Promise me , Don't get confused next time

series 《 The illustration Redis》 article

Data types ：

Persistent article ：

Cluster ：

Architecture ：

interviewer ：Redis What is the difference between expiration deletion strategy and memory obsolescence strategy ？ More articles about

  1. Redis Detailed explanation （ 11、 ... and ）------ Expiration deletion policy and memory obsolescence policy

    Before introducing this article , Let's look at the following questions first : ①. How to set up Redis Key expiration time ? ②. After setting the expiration time of a key , It's time , Is this key still available ? If not, does this key still occupy memory ? ③. How to set up R ...

  2. 【Redis】 Expiration key deletion strategy and memory elimination strategy

    Redis Expired key policy and memory obsolescence policy Catalog Redis Expired key policy and memory obsolescence policy Set up Redis Key expiration time Redis The determination of expiration time Expiration key deletion policy Delete regularly Lazy deletion Delete periodically Redis Expired delete policy ...

  3. redis Expiration strategy 、 Memory retirement strategy 、 Persistence mode 、 Master slave copy

    Link to the original text :https://blog.csdn.net/a745233700/article/details/85413179 One .Redis The expiration policy and memory obsolescence policy of :1. Expiration strategy : Delete periodically + Lazy deletion ...

  4. Redis The expiration policy and memory obsolescence policy of ( turn )

    Redis The expiration strategy of We all know ,Redis yes key-value database , We can set Redis Cached key The expiration time of .Redis The expiration strategy of is when Redis Cached key Out of date ,Redis How to deal with it . ...

  5. Redis The expiration policy and memory obsolescence policy of

    Redis The expiration strategy of : There are usually three kinds of ,Redis Both lazy expiration and periodic expiration policies are used in . Timed expiration : Each set expiration time of key All need to create a timer , It will be cleared immediately after the expiration time . This strategy can immediately clear expired data ...

  6. redis Key expiration and memory obsolescence strategies

    Key expiration time Set expiration time Redis You can set the expiration time for values stored in the database , As a cached database , This feature is very helpful . In our project token Or other login information , Especially SMS verification codes are time limited . According to tradition ...

  7. About redis A few small things ( Four )redis The expiration policy and memory elimination mechanism of

    1. Why data is out of date ? First , To understand redis It's used for data caching , Not for data storage ( Of course, it can also be used as a database ), So when does the data expire , The expired data is gone , There are two main cases of expiration , ① In setting up the cache data, we have formulated ...

  8. Redis Expiration deletion strategy and memory elimination mechanism in

    Redis in key The expiration delete policy for Preface Redis in key The expiration delete policy for 1. Delete regularly 2. Lazy deletion 3. Delete periodically Redis Expiration deletion policy in Whether the slave library will dirty read the expired key created by the master library Memory obsolescence mechanism ...

  9. Redis The expiration delete policy for ( And memory elimination mechanism )- turn

    Copyright notice : This paper is about CSDN Blogger 「 Othenus 」 The original article of , follow CC 4.0 BY-SA Copyright agreement , For reprint, please attach the original source link and this statement . Link to the original text :https://blog.csdn.net/qq_39944869/ ...

  10. redis The expiration policy and memory elimination mechanism of

    redis Regular deletion is used + Lazy delete strategy . Why not delete the policy regularly ? Delete regularly , Use a timer to monitor key, Automatically delete after expiration . Although memory is released in time , But it's very exhausting CPU resources . In the case of large concurrent requests ,CPU Time should be ...

Random recommendation

  1. [ turn ] of WorldWind1.4 Of worldwind.cs The solution of window designer opening error

    Solution for Designer error when opening WorldWind.cs in WW1.4.0 When I load the WW project in my Vi ...

  2. [FlyCapture2] Bumblebee XB3 Save Images to Three AVI Files (Left, Center and Right) The Bumblebee stereo camera saves the captured video to three different files on the left, middle and right

    PointGreyResearch Is the world's leading company dedicated to the development of advanced digital camera products .PointGrey Products involved in IEEE-1394 The camera . Stereo cameras and 360 Panoramic digital video camera . Two and three generations of Bumblebee stereo cameras ...

  3. Qt Wait for the prompt box （QMovie）

    sketch About gif I don't use much in actual projects , Because I feel a lot of flaws , Most of the time, the sawtooth is serious , Of course, it has a lot to do with the graph . About generating gif The method can provide a website preloaders, It can basically meet the needs . ...

  4. Shell Sort java

    Hill sort Hill sort is based on the following two properties of insertion sort : Insert sort is used to manipulate almost ordered data , Efficient , That is, the efficiency of linear sorting can be achieved .( Hill sort sorts some data first , It's equivalent to having been partially ordered ) ...

  5. ABP+AdminLTE+Bootstrap Table Authority management system section 11 --bootstrap table User management list

    This one starts bootstrap table, There are two ways to introduce projects , One is to download directly from the official website Address :http://bootstrap-table.wenzhixin.net.cn/ The other is Nuget introduce . then ...

  6. openssl Basic principle of certificate generation

    Excerpt from :http://blog.csdn.net/oldmtn/article/details/52208747 1. The basic principle A project of the company needs to carry out transaction data transmission , Because the bank has just started this project , the ...

  7. .Net Open source web crawler Abot Introduce （ turn ）

    Reprinted address :http://www.cnblogs.com/JustRun1983/p/abot-crawler.html .Net There are also many open source crawler tools in ,abot Is one of them .Abot It's an open source ...

  8. Baptize the soul , Practice python（50）-- Reptile — Basic knowledge

    Reptiles 1. What is a reptile Reptiles are one of the crawling species of insects , Good at crawling . ha-ha , Make fun of , In programming , Crawler is actually called web crawler , Web crawler , Also known as web spider , Network robot , stay FOAF Community Center , More often referred to as a web chaser ...

  9. bzoj-2038- Mo team

    2038: [2009 National Team ] Small Z Socks of (hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 15784  Solved: 7164[Sub ...

  10. C# Basic learning is StreamReader and StreamWriter

    StreamReader and StreamWriter To manipulate characters FileStream Manipulating bytes // Use StreamReader Read the file using (StreamReader sr=new Strea ...