This is the first day of my participation in Gwen Challenge

The article was first published on the official account: Mushrooms can’t sleep, welcome to have a look

preface

Redis stores key-value pairs. Keys are strings, and values have many types, such as String, list, hash, set, sorted set and so on. When setting key-value pairs we should also set the expiration time for them, via expire and pexpire commands; It can also be set using the setnx command. So, when the expiration time is set, how do you delete expired key-value pairs? To find out, let’s take a look at Redis’s expiration key deletion strategy. Before we talk about the delete strategy, it is important to know if a key is out of date. Here is a summary:

  1. Check if the key is in the expired dictionary, and if so, extract the expiration date for the key. (An expiration dictionary stores the expiration date of each key, where key is the key and value is the expiration date of type long.)
  2. After getting the expiration time, compare it to the current UNIX timestamp, if greater than, the key expires.

That’s how you can tell if a key is out of date. Next, how to delete a key when it expires.

Currently there are three deletion strategies:

  • Scheduled deletion: When setting the expiration time of a key, a timer is created to delete the key when the expiration time is reached.
  • Lazy delete: Lazy delete is not to delete when the expiration time is reached, but each time the key is obtained, it will determine whether the expiration, if the expiration, delete, and return empty; Return the key if it has not expired.
  • Periodically delete: Every once in a while, the keys in the database are checked and deleted if they expire. As to how much and when to delete, it is decided through specific procedures.

Each of these deletion strategies is described in detail below.

Time to delete

The scheduled deletion policy has the advantages of being memory-friendly. Because with timers, a key can be deleted as soon as it reaches its expiration date, freeing up memory. Disadvantages: CPU unfriendly. If there are a lot of expired keys, removing them can take up a significant amount of CPU time, and if CPU time is very tight, expending CPU time on deleting expired keys unrelated to the current task can have an impact on server response time and throughput. Therefore, it is not practical to delete expired keys through a timed deletion policy.

Lazy to delete

Advantages: Lazy delete policy is CPU time friendly. The program will only determine whether to delete the key when it is removed, and only the current key, other expired keys will not take CPU time to deal with. Disadvantages: Lazy delete policy is not memory friendly. If a large number of keys are not used all the time, they will not be deleted even if they expire and will occupy the memory. This can be thought of as a memory leak — a large amount of useless data remains in memory and will not be deleted.

Periodically delete

In contrast to timed deletion, which is CPU unfriendly, lazy deletion is memory unfriendly. Periodic deletions take a compromise approach:

  • The periodic deletion policy performs the deletion expiration key at intervals and limits the duration and frequency of the deletion operation to reduce the impact on the CPU time.
  • In addition, by periodically deleting expired keys, the memory waste caused by expired keys is effectively reduced.

But the duration and frequency of deletions are more difficult to define because:

  • If the frequency is too high or the duration is too long, it can take up a lot of CPU time.
  • If it is too short, it will waste memory.

So. If the periodic deletion policy is adopted, you need to define the duration and frequency based on specific service scenarios.

Redis actually uses a lazy delete + periodic delete strategy.

These two ways are a good use of CPU time and avoid memory waste. Let’s talk about lazy deletion and the implementation of periodic deletion.

Implementation of the lazy delete policy

The lazy delete policy is implemented by the expireIfNeeded function, which calls exipreIfNeeded to check input keys before all Redis commands that read or write to the database are executed.

  • If the key expires, it is removed and returns null.
  • If the key is not expired, no operation is performed.

Periodically remove policy implementations

The periodic deletion policy is implemented by the activeExpireCucle function. When it is called, it traverses each database in the server several times in a specified time, checks the expiration time of some keys randomly from the expires dictionary of the database, and deletes the expired keys.

  • Each time the function runs, a random number of database keys are checked and the expired keys are removed.
  • A global variable current_db records the progress of the current activeExpireCycle function check, and the next time the function executes, the previous progress will be processed. For example, if the current activeExpireCycle function runs to 10, current_db = 10; Then the next time the function executes, take the current_DB to 10 and continue.
  • Current_db = 0 when all database keys have been checked.

Processing of expired keys by AOF, RDB, and replication functions

Generate the RDB file

When a new RDB file is created by executing the SAVE command or the BGSAVE command, the program checks the keys in the database, and expired keys are not saved to the new RDB file. For example: Redis contains r1, R2, R3 three keys, and R1 has expired, then the program will only save R2 and R3 to the RDB file. Therefore, the expired key does not affect new RDB files.

Load the RDB file

When starting the Redis server, if the RDB function is enabled on the server, the server will load the RDB file.

  • If the server is running in primary mode, expired keys will be filtered out when loading the RDB file and will not be loaded into the Redis database.
  • If running in slave mode, the key is loaded into the database regardless of whether it is out of date. However, since the slave server is emptied during data synchronization between the master and slave servers, the expiration key generally does not affect the slave server either.

AOF file writes

When the server is in AOF mode, AOF does not care if a key is out of date but is not lazy or periodically deleted. If the key has been lazily or periodically deleted, AOF appends a DEL command to the end of the file to explicitly record that the key has been deleted.

AOF rewrite

When AOF is overwritten, expired keys are not loaded into the Redis database.

copy

When the server is in replication mode, the expiration key deletion from the secondary server is performed 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 slave server executes read commands sent by the client, it does not delete expired keys and continues normal operations.
  • The slave server removes the expired key only after receiving the DEL command from the master server.

Since the slave server will not delete the expired key actively, how to query the expired key of the slave server?

This is a very good question, and I did miss it when I wrote the article, so I’m going to explain it with a quote from the Redis website.

1. The slave server does not remove the expired key, it waits for the master to remove the expired key, and when the master expires (or is expelled due to the LRU algorithm), it generates a DEL command and sends it to all slave servers. 2. However, because this is the key expiration behavior of the master driver, the master cannot provide the DEL command in a timely manner. As a result, some key in the memory of the slave server has been logically expired. The slave uses its logical clock to report that keys are present only in read operations that do not violate the consistency of the data set (arriving from a new command from the host). In this way, you avoid returning an expired key from the node. In practice, an HTML page cache that is expanded from the node cache will avoid the problem of not expiring on time.

The last

Redis’ expired key deletion strategy is lazy deletion + periodic deletion, which can reasonably control CPU usage and reduce memory waste.

For more Java knowledge and brush problem sharing, you can come to the public account mushroom can’t sleep to see, we learn together.

The more active you are, the more active you will be. See you next time