Redis stores key-value pairs, where the keys are strings and the values are of various types, such as string, list, hash, set, sorted set, and so on. When setting a key-value pair, we should also set the expiration time for it, which can be set by expire and pexpire commands, or by setnx command. So, after setting the expiration time, how exactly do you delete the expired key-value pairs? To find out, let’s take a look at Redis’ expired key deletion policy. Redis

Before we talk about the deletion policy, let’s take a look at how to determine if a key is expired.

  1. Check if the key is in the expiration dictionary, if it exists, then retrieve the expiration time of the key. (The expiration dictionary stores the expiration time of each key, where key is the key and value is the expiration time of long type)
  2. After getting the expiration time, compare it with the current UNIX timestamp, and if it is greater, the key expires.

This is how to determine if a key is expired. Next, let’s talk about how to delete a key when it has expired.

For now there are three deletion strategies.

  • Timed deletion: Create a timer when setting the expiration time of a key, and delete the key through the timer when the key expiration time is reached 。
  • Inert deletion: Inert deletion is not when the expiration time is reached to delete, but each time the key is obtained, it will determine whether it is expired, if expired then delete and return empty; not expired, it returns the key value 。
  • Periodic deletion: Every once in a while, the keys in the database are checked and deleted if they are expired. As for how much to delete and when to delete, it is decided by specific procedures 。

Each of the deletion strategies is described in detail below.

Timed deletion

Timed delete policy The advantage is: memory friendly. Because with the timer, when a key reaches its expiration time it is immediately deleted, freeing up memory directly. Disadvantage: It is not CPU friendly. If there are many expired keys, deleting them will take up a significant amount of CPU time, and if CPU time is very tight, spending CPU time on deleting expired keys that are not related to the current task will affect the server’s response time and throughput. Therefore, it is not practical to delete the expired keys by a scheduled deletion policy.

Inert deletion

Advantages of the inert delete strategy: CPU time friendly. The program will only determine if a key is deleted when it is removed, and it will only work on the current key; other expired keys will not take CPU time to process. Disadvantages of inert deletion strategy: Not memory friendly. If there are a large number of keys that have not been used, they will not be deleted even if they are expired and will keep occupying memory. This can be interpreted as a memory leak - a large amount of useless data keeps occupying memory and will not be deleted.

Periodic deletion

Compared to timed deletion which is CPU unfriendly, inert deletion is memory unfriendly. Periodic deletion uses a compromise approach.

  • The periodic delete policy performs the delete expired key operation at regular intervals and reduces the impact of the delete operation on CPU time by limiting the length and frequency of the delete operation execution.
  • And, by periodically deleting expired keys, the memory waste caused by expired keys is effectively reduced.

However, the duration and frequency of deletion are more difficult to define because.

  • If the frequency is too high or the duration is too long, then it will take up a lot of CPU time.
  • If it is too short, memory will be wasted again.

Therefore. If a periodic deletion policy is used, the duration and frequency need to be defined by specific business scenarios.

Redis actually uses an inert delete + periodic delete strategy

These two approaches make good use of CPU time and avoid memory wastage. Next, we will talk about the implementation of inert deletion and periodic deletion.

Implementation of inert deletion policy

The inert deletion policy is implemented by the expireIfNeeded function. All Redis commands that read or write to the database call the exipreIfNeeded function to check the input keys before they are executed.

  • If the key is expired, it will delete the key and return null.
  • If the key is not expired, the operation is not done.

Implementation of periodic deletion policy

The periodic deletion policy is implemented by the activeExpireCucle function, which, when called, it iterates through each database in the server several times within a specified time period, checks the expiration time of a random portion of keys from the database’s expires dictionary, and removes the expired keys from it.

  • Each time the function runs, it takes a random number of keys from a certain number of database keys and checks them and removes the expired keys from them.

  • There is a global variable current_db that records the progress of the current activeExpireCycle function check, and the next time the function is executed, the progress of the previous one is processed. For example, if the current activeExpireCycle function reaches 10, speak current_db = 10; then the next time the function executes, it takes the 10 from current_db and continues executing.

  • When all database keys have been checked, current_db = 0.

Handling of expired keys by AOF, RDB and replication functions

Generate RDB files

When you execute SAVE command or BGSAVE command to create a new RDB file, the program will check the keys in the database, and the expired keys will not be saved to the new RDB file. For example, if redis contains r1, r2 and r3 keys, and r1 has expired, then the program will only save r2 and r3 to the RDB file. Therefore, the expired keys will not have any effect on the new RDB file.

Load RDB file

When starting the redis server, if the server has the RDB feature enabled, then the server will load the RDB file

  • If the server is running in master server mode, then when loading the RDB file, expired keys will be filtered out and will not be loaded into the redis database.
  • If running in slave server mode, then the keys are loaded into the database regardless of whether they are expired or not. But, since the slave server is cleared when the master and slave servers synchronize data, expired keys will generally have no effect on the slave server either.

AOF file writing

When the server is in AOF mode, if a key is expired but not deleted inertly or periodically, then AOF ignores it. If it is deleted inertly or periodically, AOF will append a DEL command to the end of the file to log that the key has been deleted.

AOF Rewrite

When AOF is rewritten, expired keys are not loaded into the redis database.

Reproduction

When the server is in replication mode, the expired key deletion actions for the slave servers are performed by the master server.

  • After the master server deletes an expired key, it displays a DEL command sent to all slave servers to tell them to delete the expired key.
  • When executing the read command sent by the client from the server, even if it encounters an expired key, it does not delete it, but continues its normal operation.
  • The slave server will delete the expired key only after receiving a DEL command from the master server.

Some people ask: Since the slave server doesn’t actively delete expired keys, what if I query the slave server for expired keys?

This is a very good question, and I did leave this point behind when I wrote the article, so I will quote from the Redis official website to explain this issue

How Redis replication deals with expires on keys

Redis expires allow keys to have a limited time to live (TTL). Such a feature depends on the ability of an instance to count the time, however Redis replicas correctly replicate keys with expires, even when such keys are altered using Lua scripts.

To implement such a feature Redis cannot rely on the ability of the master and replica to have synchronized clocks, since this is a problem that cannot be solved and would result in race conditions and diverging data sets, so Redis uses three main techniques in order to make the replication of expired keys able to work:

  1. Replicas don’t expire keys, instead they wait for masters to expire the keys. When a master expires a key (or evict it because of LRU), it synthesizes a DEL command which is transmitted to all the replicas.
  2. However because of master-driven expire, sometimes replicas may still have in memory keys that are already logically expired, since the master was not able to provide the DEL command in time. In order to deal with that the replica uses its logical clock in order to report that a key does not exist only for read operations that don’t violate the consistency of the data set (as new commands from the master will arrive). In this way replicas avoid reporting logically expired keys are still existing. In practical terms, an HTML fragments cache that uses replicas to scale will avoid returning items that are already older than the desired time to live.
  3. During Lua scripts executions no key expiries are performed. As a Lua script runs, conceptually the time in the master is frozen, so that a given key will either exist or not for all the time the script runs. This prevents keys expiring in the middle of a script, and is needed in order to send the same script to the replica in a way that is guaranteed to have the same effects in the data set.

Once a replica is promoted to a master it will start to expire keys independently, and will not require any help from its old master.

Finally

Redis’ expired key deletion policy is inert delete + periodic delete, which also allows for reasonable control of CPU usage and reduces memory waste.

Reference https://juejin.cn/post/6970680853584150565