Read for about 4 minutes

If you have ever used Redis, you probably know the expiration policy command. If you were asked to design an expiration key interface, what would you think?

When we use Redis, we usually set an expiration time, of course, there is no expiration time, that is, never expire.

When we set the expiration time, how redis determines whether it is expired or not, and what policy is used to delete it.

Redis sets the expiration time: expire key time(in seconds) – this is the most commonly used setex(String key, int seconds, String value) – String unique

With the exception of the string’s own methods that set the expiration time, all methods rely on the expire method to set the time

If no time is set, the cache will never expire

If you set an expiration time and then want the cache to never expire, use the Persist key

There are three expiration strategies:

Directory: (toc)

Time to delete

  1. Description: When setting the expiration time of a key, a timer is created for the key to delete the key when the expiration time comes

  2. Advantages: Ensure that the memory is released as soon as possible

  3. Disadvantages: If there are a lot of expired keys, deleting these keys will occupy a lot of CPU time. In the case of tight CPU time, the CPU cannot spend all the time to do important things, but also needs to spend time to delete these keys. If you create a timer for each key that is set to expire (there will be a large number of timers), the performance impact will be severe.

Lazy delete

  1. Description: The key is not deleted when it expires. Each time the key is obtained, the system checks whether the value is expired. If the value is expired, the system deletes it and returns NULL.
  2. Advantages: The delete operation only occurs when the key value is passed, and only the current key is deleted, so the CPU time is relatively small, and the deletion is already necessary (if not deleted, we will obtain the expired key).
  3. Disadvantages: Memory leaks can occur if a large number of keys are not fetched for a long time after the timeout period (useless garbage takes up a large amount of memory)

Periodically delete

  1. Description: Delete an expired key every once in a while
  2. Advantages: By limiting the duration and frequency of deletion operations, the deletion operation consumes less CPU time. – The disadvantages of scheduled deletion are addressed
  3. Disadvantages: In terms of memory friendly, not as good as “timed delete” (will cause a certain amount of memory, but not so much memory use lazy) in terms of CPU time friendly, not as good as “lazy delete” (will periodically compare and delete operations, CPU aspect is not as good as lazy, but better than timed)
  4. Difficulty: Reasonably set the execution duration of deletion operation (how long is the execution duration of each deletion) and the execution frequency (how long is the execution frequency of each deletion) (this depends on the server running condition). Too long execution time or too high execution frequency will put pressure on CPU. After each periodic deletion operation is performed, it is necessary to record which flag bit the traversal cycle reached, so that the next periodic time comes, the cycle will start from the last position
  5. Note: Memcached only uses lazy deletion, while Redis uses both lazy deletion and periodic deletion. This is another difference between the two. Setnx key2 value2: This method is similar to memcached’s add method in that if key2 already exists, it returns false and does nothing; If the set key2 does not exist, this method sets the cache key2-value2. If key2 is already in redis, setnx will return false if it is not deleted. If key2-value2 is not reset successfully, setnx will return false. So make sure you do an expiration check on key2 before setnx is executed.

Expiration strategy adopted by Redis

  • Lazy delete + delete regularly

Lazy deletion process:

  1. Before performing operations such as GET or setnx, check whether the key is expired.
  2. If the key expires, delete it and perform related operations.
  3. If no, directly perform the corresponding operation.
  4. Periodic deletion process (in simple terms, randomly delete less than or equal to a specified number of expired keys for each library of a specified number of libraries) :
  5. Iterate through each database (the number of “databases” specified in redis.conf, default is 16)
  6. Check the specified number of keys in the current library (default: 20 keys per library, note that the loop is executed 20 times, as described below)
  7. If no key in the current library is set to expire, the next library is traversed directly
  8. Obtain a random key with an expiration time and check whether the key expires. If the key expires, delete it
  9. Check whether the periodic deletion has reached the specified period. If so, exit the periodic deletion.

For periodic delets, there is a global variable current_db in the program to record the number of libraries to be traversed. Suppose there are 16 libraries, and we have traversed 10 of them on this periodic deletion, so the current_DB would be 11. The next periodic deletion would start on the 11th library. Assuming current_db is equal to 15, then the loop starts again at library 0 (where current_db==0).

conclusion

In practice, if we want to design our own expiration policy, it is critical to control the duration and frequency when using lazy deletion + periodic deletion, which needs to be adjusted according to server performance, concurrency, etc., so as to achieve the best.

Redis has four different commands that can be used to set the lifetime of the key (how long the key can exist) or the expiration time (when the key will be removed) :

The EXPIRE < key > < TTL > command is used to set the lifetime of key keys to TTL seconds.

The PEXPIRE < key > < TTL > command is used to set the lifetime of key keys to TTL milliseconds.

The EXPIREAT < key > < timestamp > command is used to set the expiration time of key to the timestamp specified in seconds.

The PEXPIREAT < key > < timestamp > command is used to set the expiration time of key to the timestamp specified in milliseconds.

Principle:

EXPIRE, PEXPIRE, and EXPIREAT are all implemented using the PEXPIREAT command, although there are many different units and different forms of setting commands: No matter which of the above four commands is executed by the client, the result of the transformation is the same as that of the PEXPIREAT command.

The Expires dictionary of the redisDb structure holds the expiration time of all the keys in the database. We call this dictionary an expired dictionary

The key of an expired dictionary is a pointer to a key object (that is, a database key) in the key space.

The value of the expired dictionary is an integer of type long, which holds the expiration time of the database key to which the key points — a UNIX timestamp with millisecond precision.

The following figure shows an example of a database with an expired dictionary, in which the key space holds all key-value pairs in the database, and the expired dictionary holds the expiration time of the database key.

For the sake of presentation, the Alphabet key object and book key object are repeated twice in the key space and out-of-date dictionary in the figure. In practice, the keys of the key space and the keys of the out-of-date dictionary point to the same key object, so no duplicate objects occur and no space is wasted.

The out-of-date dictionary in the figure holds two key-value pairs:

The key of the first key-value pair is the Alphabet key object with a value of 1385877600000, which means the expiration time of the database key Alphabet is 1385877600000 (zero hour on December 1, 2013).

The key of the second key-value pair is the book key object with a value of 1388556000000, which means the expiration time of the database key book is 1388556000000 (0:00, January 1, 2014). When a client executes the PEXPIREAT command (or three other commands that convert to PEXPIREAT commands) to set an expiration time for a database key, the server associates the given database key and expiration time in the database expiration dictionary.

After the server executes the following command

The out-of-date dictionary will add a new key-value pair, where the key is the Message key object and the value is 1391234400000 (0:00 on February 1, 2014), as shown:

The following is the pseudocode definition of the PEXPIREAT command

The PERSIST command can remove a key expiration time

The PERSIST command is the reverse of the PEXPIREAT command: the PERSIST command looks up the given key in the expiration dictionary and disassociates the key and value (expiration time) in the expiration dictionary.

Determination of expired keys

With the expiration dictionary, the program can check if a given key is expired by using the following steps:

  1. Check if the given key exists in the expired dictionary: if so, get the expiration time of the key.
  2. Check whether the current UNIX timestamp is greater than the expiration time of the key: if so, the key is expired; Otherwise, the key is not expired. This process can be described in pseudocode:

Github.com/Rodert/Java…