This blog is the fifth in the Redis series on Redis expiration key deletion strategy.

The first four articles in this series can be viewed by clicking on the following links:

Redis series (1) : Introduction to Redis and environment installation

Redis series (2) : Redis 5 data structures and common commands

Redis series 3: Redis persistence mechanism (RDB, AOF)

Redis series 4: Redis replication mechanism (master/slave replication)

Redis expiration key deletion strategy is also a common interview question. I was asked several times recently in an interview.

Memory resources are very valuable to Redis servers, and if some expired keys are not deleted, it can be a waste of resources.

So we need to consider the question: if a key is out of date, when will it be deleted?

1. Common deletion policies

The following three common deletion policies are used:

  1. Time to delete

    When setting the expiration time of a key, create a timer to delete the key immediately when the expiration time of the key comes.

  2. Lazy to delete

    Leave the expired key alone. Each time a key is retrieved from the key space, the key is checked to see if it is expired. If it is not, the key is deleted.

  3. Periodically delete

    Every once in a while, the program checks the database and deletes the expired keys, and the algorithm decides which database keys to delete.

Periodic deletion and periodical deletion are active deletion policies, and lazy deletion is passive deletion policy.

Let’s go through them all.

1.1 Periodic Deletion Policy

Periodic deletion Policy The periodic deletion policy ensures that expired keys are deleted as soon as possible and releases the memory occupied by expired keys.

Therefore, the advantages and disadvantages of a scheduled deletion policy are as follows:

  1. Pros: Very memory friendly
  2. Cons: Very CPU time unfriendly

For example, if there are a large number of command requests waiting to be processed by the server and the server is currently running out of memory, the response time and throughput of the server will suffer if the server spends a large amount of CPU time removing expired keys.

That is, if the server creates a large number of timers, the server’s performance in handling command requests will be reduced,

Therefore, Redis does not currently use a timed deletion strategy.

1.2 Lazy Deletion Policy

The lazy delete policy only performs expiration checks on keys when they are acquired and does not spend excessive CPU time deleting irrelevant expired keys.

Therefore, the advantages and disadvantages of the lazy delete strategy are as follows:

  1. Advantages: Very CPU time friendly
  2. Cons: Very memory unfriendly

For example, if the database has a lot of expired keys that are never accessed, these expired keys will continue to occupy valuable memory resources, resulting in a waste of resources.

1.3 Deleting a Policy Periodically

Periodic deletion policy is a compromise between periodic deletion policy and lazy deletion policy.

The periodic deletion policy deletes expired keys at intervals and limits the duration and frequency of the deletion operation to reduce the impact on CPU time. In addition, the periodic deletion of expired keys effectively reduces memory waste caused by expired keys.

2. Expiration key deletion policy used by Redis

The Redis server uses a lazy delete strategy and a periodic delete strategy.

2.1 Implementation of lazy deletion policy

The lazy deletion policy for expired keys is implemented by the expireIfNeeded function, which is called by all Redis commands that read or write to the database to check input keys before they are executed:

  • If the input key has expired, the input key is removed from the database
  • If the input key is not expired, no processing is done

The above description can be represented by the following flow chart:

2.2 Implementation of periodic deletion policy

The periodic deletion policy of expired keys is implemented by the activeExpireCycle function. The activeExpireCycle function will be called whenever the periodic operation serverCron function of Redis server is executed. It traverses each database in the server several times within a specified period of time. Check the expiration date of a random set of keys from the database’s Expires dictionary and delete the expired keys.

The general process of the activeExpireCycle function is as follows:

Function every time is running, from a certain number of database randomly take out a certain number of key inspection, and remove the expired keys, such as starting from 0 database check first, next time function, may be from the database to check 1, until completion of the 15 database check, starting from 0 database to check again, This ensures that every database is checked.

To highlight:

  1. When I was asked about the general process of deleting regularly in a recent interview, I answered as described above.
  2. Some interviewers may also ask, which keys are randomly deleted each time? The LRU algorithm (Least Recently Used) can be Used to describe the LRU algorithm.

3. RDB’s handling of expired keys

3.1 Generating an RDB File

When you run the SAVE command or BGSAVE command to create a new RDB file, the program checks the database keys, and expired keys are not saved to the newly created RDB file.

For example, if the database contains three keys k1, k2, and k3, and K2 is out of date, the program will only save K1 and k3 to the RDB file when creating a new RDB file, and k2 will be ignored.

3.2 Loading the RDB File

When starting the Redis server, if only RDB persistence is enabled on the server, the server will load the RDB file:

  • If the server is running in primary mode, when the RDB file is loaded, the program checks the saved keys in the file. Unexpired keys are loaded into the database, and expired keys are ignored.

  • If the server is running in slave mode, when the RDB file is loaded, all keys saved in the file, whether expired or not, are loaded into the database.

    Since the database on the slave server is emptied during data synchronization (full resynchronization), the expired key generally does not affect the slave server that loads the RDB file.

4. AOF’s treatment of expired keys

4.1 AOF file writing

If a key in the database has expired and AOF persistence is enabled on the server, the program appends a DEL command to the AOF file to explicitly record that the key has been deleted after lazy deletion or periodic deletion.

For example, if a client executes the GET message command to access an expired message key, the server will perform the following three actions:

  1. Delete the message key from the database
  2. Append aDEL messageCommand to AOF file
  3. To performGET messageThe client of the command returns an empty reply

4.2 AOF file rewrite

When an AOF file rewrite is performed, keys in the database are checked, and expired keys are not saved to the rewritten AOF file.

5. Processing of expired keys by the replication function

In the master-slave replication mode, the deletion of the expiration key on the secondary server is controlled by the primary server:

  • After removing an expired key, the master server explicitly sends a DEL command to all slave servers to tell slave servers to remove the expired key.
  • When the secondary server executes the read command sent by the client, it does not delete the key even if it finds that the key has expired, but returns the value of the key as usual.
  • The slave server does not remove the expired key until it receives the DEL command from the primary server.

6. Source code and reference

Redis Design and Implementation by Huang Jianhong