Explanation of the principle of Redis's expired key deletion strategy

This article brings you relevant knowledge about Redis. It mainly introduces the principle of Redis’ expired key deletion strategy. The Redis server actually uses two strategies: lazy deletion and regular deletion: By using these two deletion strategies together, the server can achieve a good balance between rational use of CPU time and avoiding wasted memory space. I hope it will be helpful to everyone.

Recommended learning: Redis video tutorial

The Redis server actually uses two strategies: lazy deletion and regular deletion: through cooperation Using these two deletion strategies, the server can achieve a good balance between rational use of CPU time and avoiding wasted memory space.

Lazy deletion

The lazy deletion strategy is the most friendly to CPU time: the program will only check the key for expiration when the key is taken out, which can ensure that the operation of deleting the expired key is only It will be done when it must be done, and the deletion target is limited to the currently processed key. This strategy will not spend any CPU time on deleting other irrelevant expired keys.

The disadvantage of the lazy deletion strategy is that it is the least friendly to memory: if a key has expired, and the key is still retained in the database, then as long as the expired key is not deleted, it will occupy The memory will not be released.

When using the lazy deletion strategy, if there are a lot of expired keys in the database, and these expired keys happen to not be accessed, then they may never be deleted (unless the user manually executes FLUSHDB ), we can even regard this situation as a memory leak - useless garbage data occupies a large amount of memory, but the server will not release them by itself. This is a problem for the Redis server whose running status is very dependent on memory. That's definitely not good news.

For example, for some time-related data, such as logs, after a certain point in time, access to them will be greatly reduced, or even no longer accessed. If such expired data A large number of keys are backlogged in the database. Users think that the server has automatically deleted them, but in fact these keys still exist, and the memory occupied by the keys has not been released. The consequences must be very serious.

Regular deletion

From the above discussion of lazy deletion, this deletion method has obvious flaws when used alone: ​​

Lazy Deleting wastes too much memory and risks memory leaks. The periodic deletion strategy is an integration and compromise of the first two strategies:

The periodic deletion strategy performs the deletion of expired keys at regular intervals and reduces deletion operations by limiting the duration and frequency of deletion operations. Impact on CPU time. In addition, by regularly deleting expired keys, the regular deletion strategy effectively reduces the memory waste caused by expired keys. The difficulty of the periodic deletion strategy is to determine the duration and frequency of the deletion operation:

If the deletion operation is performed too frequently, or the execution time is too long, the periodic deletion strategy will degenerate into a scheduled deletion strategy, so that it will Too much CPU time is spent deleting expired keys.

If the deletion operation is executed too little, or the execution time is too short, the regular deletion strategy will be the same as the lazy deletion strategy, resulting in a waste of memory. Therefore, if a regular deletion strategy is adopted, the server must reasonably set the execution duration and frequency of the deletion operation according to the situation.

Lazy deletion strategy

The lazy deletion strategy of expired keys is implemented by the db.c/expireIfNeeded function. All Redis commands that read and write the database will call the expireIfNeeded function to check the input keys before execution:

If the input key has expired, the expireIfNeeded function will delete the input key from the database.

If the input key has not expired, the expireIfNeeded function does not take action.

The expireIfNeeded function is like a filter, which can filter out expired input keys before the command is actually executed, thereby preventing the command from touching expired keys.

In addition, because each accessed key may be deleted by the expireIfNeeded function due to expiration, the implementation function of each command must be able to handle both the existence of the key and the absence of the key:

When the key exists, the command is executed according to the existence of the key.

When the key does not exist or the key is deleted by the expireIfNeeded function due to expiration, the command is executed as if the key does not exist.

Implementation of periodic deletion strategy

The periodic deletion strategy of expired keys is implemented by the redis.c/activeExpireCycle function. Whenever the Redis server periodic operation redis.c/serverCron function is executed, the activeExpireCycle function will When called, it traverses each database in the server multiple times within a specified time, randomly checks the expiration time of some keys from the expires dictionary of the database, and deletes the expired keys.

The entire process can be described in pseudo code as follows

The working mode of the activeExpireCycle function can be summarized as follows:

Every time the function runs, it takes out a certain number of random keys from a certain number of databases for inspection, and deletes the expired keys.

The global variable current_db will record the progress of the current activeExpireCycle function check, and the next time the activeExpireCycle function is called, the previous progress will be processed. For example, if the current activeExpireCycle function returns when traversing database No. 10, then the next time the activeExpireCycle function is executed, it will search for and delete expired keys starting from database No. 11.

As the activeExpireCycle function continues to execute, all databases in the server will be checked. At this time, the function resets the current_db variable to 0, and then starts a new round of checking work again.

When the server is running in replication mode, the deletion of expired keys from the slave server is controlled by the master server:

After the master server deletes an expired key, it will display Formally send a DEL command to all slave servers to tell the slave servers to delete the expired key.

When the slave server executes the read command sent by the client, even if it encounters an expired key, it will not delete the expired key, but continue to process the expired key like an unexpired key

The slave server will delete the expired key only after receiving the DEL command from the master server.

By controlling the master server to uniformly delete expired keys from the slave server, the consistency of the master-slave server data can be ensured. It is for this reason that when an expired key still exists in the database of the master server, The replica of this expired key in the slave server will also continue to exist. For example, there is a pair of master-slave servers, and their databases all store the same three keys message, xxx, and yyy, where message is the expired key, as shown in the figure.

If a client sends the command GET message to the slave server at this time, the slave server will find that the message key has expired, but the slave server will not delete the message key. Is to continue to return the value of the message key to the client, as if the message key has not expired

Assume that after this, a client sends the command GET message to the main server , then the master server will find that the key message has expired: the master server will delete the message key, return an empty reply to the client, and send the DEL message command to the slave server

slave server After receiving the DEL message command from the master server, the message key will also be deleted from the database. After that, the master and slave servers will no longer save the expired key message

Recommended learning: Redis video tutorial

The above is the detailed content of Explanation of the principle of Redis's expired key deletion strategy. For more information, please follow other related articles on the PHP Chinese website!