Redis deletion policy and eviction algorithm

This article has participated in 「 New people's creation ceremony 」 Activities , Start the road of nuggets creation together .

Redis Run in memory , The data is also stored in memory . Limited memory and unlimited data , Generally, the expiration time is added to the primary key , Prevent data from filling the memory , You need to use the deletion strategy and the eviction algorithm .

Deletion policy

Expired data ： Set the data of validity period , Expiry date ,Redis Not deleted immediately . Data deletion strategy is to process expired data , Control is expires Location .

There are three types of deletion policies , They are scheduled deletion 、 Lazy deletion and regular deletion . Balance memory and performance .

Delete regularly

Create a timer , When key Set expiration time , And when time arrives , There is a timer task to immediately delete the key . advantage ： To save memory , Expire delete , Quickly free up unnecessary memory . shortcoming ：CPU High pressure , No matter what CPU What is the load , All occupied CPU Delete operation , It will affect Redis Server response time and instruction throughput . summary ： Trade processor performance for memory space .

Lazy deletion

Data arrival expiration time , Don't deal with it , Delete... The next time you access the data . 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 ： High memory pressure , Data that has occupied memory for a long time . summary ： Trade memory space for processor performance .

Delete periodically

Redis When starting server initialization , Reading configuration server.hz Value , The default is 10. For each library expires Space ,expires[*]（ Each library has this interval ） Conduct a round of inspection , Every time you execute 250ms/server.hz Time , To perform a second server.hz Time .

For each expires[*] When testing , Random selection W individual key testing ,W Value = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP Property value .

If key Overtime , Delete key. If you delete in a round key The number is larger than W * 25%, Cycle the process . If you delete in a round key < W * 25%, Check the next exipires[*],0-15 loop .

Parameters current_db Used to record The method Which one to enter exipires[*] perform . Periodic polling Redis Time sensitive data in the library , Take the strategy of random selection , Use the proportion of expired data to control the frequency of deletion . summary ： Periodically spot check storage space .

Delete strategy comparison

Deletion policy	Memory footprint	CPU Resource utilization	The central idea
Delete regularly	To save memory , No occupation	Regardless of the time period CPU resources , High frequency	Performance for space
Lazy deletion	Heavy memory usage	Delayed execution ,CPUU High utilization	Space exchange performance
Delete periodically	Memory is cleaned up randomly on a regular basis	Spend... Of arc top per second CPU Resources maintain memory	Random sampling , Focus on spot check

The eviction algorithm

When the data enters Redis when , If the memory does not meet the minimum storage requirements for adding data ,Redis To temporarily delete some data and clean up the storage space for the current instruction . The strategy for cleaning up data becomes the eviction algorithm .

Eviction algorithm related configuration ：

maxmemory Maximum available memory , Default 0, unlimited . maxmemory-samples Select the number of data to be deleted each time . maxmemory-policy Configure the eviction algorithm .

After reaching the maximum memory , The strategy of expelling selected data , The selected data will not be scanned in the whole database .

The eviction algorithm ：

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

1. volatile-lru Recently, the least used data has been eliminated
2. volatile-lfu The data that has been used least recently is eliminated
3. volatile-ttl Obsolete data should be eliminated
4. volatile-random Choose any data to eliminate

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

1. allkeys-lru
2. allkeys-lfu
3. allkeys-random

Give up data

no-enviction： Exclusion data , May trigger OOM