Save expiration time

Redis can set an expiration date for each key, putting each key with an expiration date into a separate dictionary.

typedef struct redisDb { 
int id; // Redis has 16 databases by default.
long avg_ttl; // Average TTL (time to live) of stored database objects, used for statistics
dict *dict; // Store all key-values of the database
dict *expires; // Store the expiration time of the key
dict *blocking_keys;// BLPOP stores blocking keys and client objects
dict *ready_keys;// Block push response block the client stores the blocked key and the client object dict *watched_keys; // Store the key and client objects monitored by watch
} redisDb;
Copy the code

Dict is used to maintain all key-value pairs contained in a Redis database, and Expires is used to maintain keys in a Redis database with an expiration date (that is, a mapping of keys to expiration dates). Note that the expired time is expressed in milliseconds. For example, 2022-01-02 22:45:02 expired value is 1641134702000

When we use the expire command to set the expiration time of a key, Redis first looks up the dict dictionary table to see if the key exists. If so, it adds the key and expiration time to the Expires table.

When we insert data into the system using the setex command, Redis first adds keys and values to the dict dictionary table, and then keys and expires to the Expires dictionary table. Note that setex can only be used for strings.

Simply put, the key that sets the expiration date and the expiration date are all maintained in the expires dictionary table.

Setting expiration Time

The use of the expire

The expire command is used as follows: EXPIRE key TTL (in seconds)

127.0. 01.:6379> expire name 2 #2A second failure (integer)1 
127.0. 01.:6379> get name 
(nil) 
127.0. 01.:6379> set name zhangfei 
OK 
127.0. 01.:6379> TTL name # Always valid (integer) -1 
127.0. 01.:6379> expire name 30 #30A second failure (integer)1 
127.0. 01.:6379> < span style = "box-sizing: border-box! Important24A second failure (integer)24 
127.0. 01.:6379> TTL name # Invalid (integer) -2
Copy the code

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

The expire command is used to set the lifetime of a key to TTL seconds

The pexpire command is used to set the lifetime of a key to TTL milliseconds

The expireat command is used to set the expiration time of key to the timestamp specified in seconds

The pexpireat command is used to set the expiration time of key to the millisecond timestamp specified by timestamp

Note that the final implementation of expire, pexpire, and expireat is implemented through pexpireat, which means that whatever command the client executes, Redis will convert to pexpireat command execution. So the time stored in the Expires dictionary is when the key expires as a millisecond timestamp.

Expiry policies

If a key is expired, when is it deleted?

There are three expiration strategies

  • Scheduled deletion: When you set the expiration time of a key, create a timer to delete the key immediately when the expiration time of the key comes. (Create timer delete)
  • Lazy deletion: the expiration of a key is ignored, but each time a key is retrieved from the key space, the retrieved key is checked to see if it is expired, and if so, the key is deleted. If not, the key is returned. (Delete when using)
  • Periodically delete: Every once in a while, the program checks the database and deletes expired keys. Algorithms determine how many expired keys to delete and how many databases to check. (Scan and delete periodically)

Time to delete

  • advantages

1, the most friendly to memory: through the use of timer, you can ensure that expired keys will be deleted as soon as possible, to release the occupied memory

  • disadvantages

1. Least CPU-friendly: Deleting expired keys may occupy a considerable amount of CPU time and affect the response time and throughput of the server when there are many expired keys.

Lazy to delete

  • advantages

1, the most CPU-friendly: the expired key will only be checked when the key is taken out, that is, there is no need for the CPU to scan regularly, and there is no need to create a large number of timers.

  • disadvantages

1. Least memory friendly: If a key has expired but will not be accessed later, it will remain in the database. If you have too many of these keys, you can take up a lot of memory.

Periodically delete

Periodic deletion is a compromise between periodic deletion and lazy deletion as described above.

  • advantages

1. Delete periodically Perform the expiration key operation at intervals and limit the duration and frequency of the deletion operation to reduce the impact of the deletion operation on the CPU time.

2. By deleting expired keys, you can effectively reduce the memory waste caused by expired keys

  • Disadvantages It is difficult to determine the duration and frequency of deleting operations

1. If the deletion is performed too frequently or for a long time, the periodic deletion policy degenerates into a periodic deletion policy that consumes too much CPU execution time.

2. If the delete operation takes too little time or execution time is too short, the periodic deletion policy will waste memory like lazy deletion.

Redis expiration policy

Redis uses lazy deletion and periodic deletion: By matching these two strategies, the server can strike a good balance between using CPU time wisely and avoiding wasting memory space.

Implementation of the lazy delete policy

Db.c /expireIfNeeded all Redis commands that read or write to a database call the expireIfNeed function to check the input key before executing it:

  • If the key has expired, the expireIfNeeded function removes the key
  • If the key is not expired, the expireIfNeeded function does nothing

The following figure shows the procedure for invoking the expireIfNeeded function

And because every accessed key can be deleted, each command must be able to handle both the presence and absence of keys. The following figure shows the execution of the GET command

Periodically remove policy implementations

Expired key deletion policy on a regular basis by the redis. C/activeExpireCycle function implementation, whenever the redis server periodic operation redis. C/serverCron function executes, activeExpireCycle function is invoked, it within the prescribed time, Traverse each database in the server several times.

Redis defaults to 10 expiration scans per second. Instead of traversing all keys in an expired dictionary, expiration scans employ a simple greedy strategy, as follows.

(1) Randomly select 20 keys from the expired dictionary.

(2) Delete expired keys among the 20 keys.

(3) Repeat step (1) if more than a quarter of the keys are out of date. At the same time, in order to ensure that expired scanning will not occur excessive cycle, resulting in the deadlock of the process, the algorithm also increases the upper limit of scanning time, the default is not more than 25ms.

What would happen if all keys in a large Redis instance expired at the same time?

Consumption of CPU

Redis continues to scan the expired dictionary (loop multiple times) until the number of expired keys in the expired dictionary becomes sparse (loop number drops significantly).

The request is delayed or timed out

When a client request arrives, the server will wait at least 25ms for the request to be processed if the server just enters the expired scan state. If the client sets the timeout time to be shorter, such as 10ms, a large number of connections will be closed due to timeout, and many exceptions will occur on the business side

Therefore, it is important to pay attention to the expiration time. If a large number of keys expire, set the expiration time to a random range rather than all expire at the same time.

Reference:

Design and Implementation of Redis

Redis Deep Adventure