Three deletion strategies and eviction algorithm of redis

---

Hello everyone , I'm cabbage . This article mainly explains Redis Three deletion strategies and expulsion Algorithm , If you get something after reading the article , You can support bloggers three times in a row ~, Hee hee .

---

One 、 Preface

• Before the article begins , Let me ask you a question first ： When we use instructions ：expire key second Give me a key Set expiration time , As soon as the expiration time arrives , This key Corresponding Expired data Is it really deleted by the server immediately ？ The answer is that it will not be deleted immediately . Knowing the answer , Take a look at Redis How to deal with expired data .

Two 、Redis Data features in

• Redis It's a memory level database , All data is stored in memory , The data in memory can be accessed by TTL Command gets its state , There are three states ：

Command result	state
XX	Time sensitive data
-1	Permanent data
-2	Expired data or Deleted data or Undefined data

3、 ... and 、 Time sensitive data storage structure

When we set the expired data with instructions , The address corresponding to the data will be placed in expires In the space , The storage method is hash , Stored value Is the expiration time .

Four 、、 Data deletion strategy

• Data deletion policy objectives ： In memory footprint and CPU Find a balance between occupation , Taking care of one thing and losing the other will result in the whole redis Performance degradation , Even cause server downtime or memory leakage

1、 Delete regularly

• Create a timer , When key Set an expiration time , And when the expiration time arrives , Delete the key immediately by the timer task
• advantage ： To save memory , Then delete , Free up unnecessary memory quickly
• shortcoming ：CPU Under great pressure , No matter what CPU How high is the load at this time , All occupied CPU, It will affect redis Server response time and instruction throughput

2、 Lazy deletion

• Data arrival expiration time , Don't deal with it . The next time you access the data , Would call expireIfNeeded() Function to determine whether the data is expired ：
  If not expired , Return the data
  Found expired , Delete , Return does not exist
• advantage ： save CPU performance , Delete when you find that you have to delete
• shortcoming ： There's a lot of memory pressure , Data that has occupied memory for a long time

3、 Delete periodically

Process analysis ：

• Redis When the server starts initialization , Reading configuration server.hz Value , The default is 10
• Then execute every second 10 Time serverCron() Method , This method is used to detect the server
• serverCron() Method will call databasesCron() Method , This method is used to traverse the database ,redis The default is 16 A database , Start with the first database
• databasesCron() Method will call activeExpireCycle() Method , This method will be applied to every expires[*] Test them one by one , Every time you execute 250ms/server.hz; To someone expires[*] When testing , Random selection W individual key testing
• If detected key Overtime , Delete key; If you delete in a round key The number of >W25%, Cycle the process ; If you delete in a round key The number of ≤W25%, Check the next expires[*],0-15 loop . among W Value =ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP Property value
• If activeExpireCycle() Execution time expired , Next time from current_db Keep going down
• Parameters current_db Used to record activeExpireCycle() Which one to enter expires[*] perform

• summary ： Periodic polling redis Time sensitive data in the library , Using random sampling strategy , Use the proportion of expired data to control the frequency of deletion
• Memory pressure is not great , Cold data that has occupied memory for a long time will be continuously cleaned up

5、 ... and 、 Delete strategy comparison

Delete regularly	To save memory , No occupation	Regardless of the time period CPU resources , High frequency	Time for space
Lazy deletion	Heavy memory usage	Delayed execution ,CPU High utilization	Change space for time
Delete periodically	Memory is cleaned up randomly on a regular basis	The cost per second is fixed CPU Resources maintain memory	Random sampling , Focus on spot check

6、 ... and 、 The eviction algorithm

1、 Concept introduction

When new data enters redis when , What if there's not enough memory ？Redis Using memory to store data , Before executing every command , Would call freeMemoryIfNeeded() Check if there is enough memory . If the memory does not meet the minimum storage requirements for newly added data ,redis To temporarily delete some data and clean up the storage space for the current instruction . The strategy for cleaning up data is called the eviction algorithm .

Be careful ： The process of evicting data is not 100% Can clean up enough available memory space , If not, repeat . After trying all the data , If the requirement of memory cleaning cannot be met , An error message will appear .

2、 Eight configurations

• Detect volatile data （ Data sets that may be out of date server.db[i].expires ）

volatile-lru	Select the least recently used data
volatile-lfu	Select the data that has been used least recently
volatile-ttl	Select the data that will be out of date
volatile-random	Choose any data to eliminate

• Check the whole database data （ All data sets server.db[i].dict ）

allkeys-lru	Select the least recently used data
allkeys-lfu	Select the data that has been used least recently
allkeys-random	Choose any data to eliminate

• Give up data

no-enviction	Exclusion data （redis4.0 Default policy in ）

---

Thank you for reading , Progress together , Hee hee ~