Difference between redis' memory obsolescence strategy and expiration deletion strategy

Catalog

Preface

Expiration deletion policy

How to set expiration time ？

How to judge key It has expired ？

What are the expiration delete policies ？

Redis What is the expiration deletion policy ？

Memory retirement strategy

How to set up Redis Maximum running memory ？

Redis What are the memory obsolescence strategies ？

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

summary

Preface

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 .

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 」.

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 value1OK# 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 an expiration 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 .

Advantages of scheduled deletion strategy ： 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 .

Disadvantages of the scheduled deletion strategy ： 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.

Advantages of lazy deletion strategy ： 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 .

Disadvantages of lazy deletion strategy ： 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.

Advantages of regularly deleting policies ： 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 .

Disadvantages of regularly deleting policies ：

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 To the customer service end ;

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 Scheduled deletion process of ：

Randomly select from the expired dictionary 20 individual key;

Check this 20 individual key Is it overdue , And delete the expired key;

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 , Scheduled 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 upper limit of time for regularly deleting circular processes is increased , Default will not exceed 25ms.

For the process of scheduled deletion , 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 scheduled 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-policy1) "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 Least recently used , 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 an approximation LRU Algorithm , The purpose is to better save memory , It is implemented 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 hasn't 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 as 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 eliminates the data according to the access frequency , 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 , The addition operation is not simple and direct  + 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 ：

First, according to the current duration from the last visit , Come on logc To attenuate ;

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 ：

This is about Redis The article on the difference between memory elimination strategy and expiration deletion strategy is introduced here , More about Redis For the contents of memory elimination strategy and expiration deletion strategy, please search the previous articles of software development network or continue to browse the relevant articles below. I hope you will support software development network more in the future ！