Redis design and Implementation (II) | database (deletion strategy & expiration elimination strategy)

database

1. Database in server

• structure

struct redisServer {
    
    //  An array holds all the databases of the server 
    redisDb *db; 
    //  Number of databases on the server 
    int dbnum;                     
    //  Record the database being used by the client 
	redisDb *db; 
}

1.1 Switch database

• summary

redis Both the server and the client in the server maintain 16 A database , The default is 0 Number , Can pass select（ The bottom layer is through modification redisClient.db Pointer to modify ） To change the database point of the client

1.2 Database key space

• summary

Redis It's a key-value pair (key-value pair) database server , Each database in the server consists of a redis.h/redisDb Structural representation , among ,redisDb Structural dict The dictionary holds all key value pairs in the database , We call this dictionary key space (key space ):

• The key of the key space is also the key of the database , Each key is a string object .
• The value of the key space is the value of the database , Each value can be a string object 、 List objects 、 Hash table object 、 Any of a collection object and an ordered collection object Redis object .

typedef struct redisDb {
    
	// ...
	// Database key space , Save all key value pairs in the database 
	dict *dict;
	// Save the integer representation number of the database 
	redisDb *id;
	// The expiration time of the save key 
	redisDb *expires;
}redisDb;

• Example

redis>SET message "hello world"
OK
redis> RPUSH alphabet "a" "b" "c"
(integer) 3
redis> HSET book name "Redis in Action"
(integer) 1
redis> HSET book author "Josiah L.Carlson"
(integer) 1
redis>HSET book publisher "Manning"
(integer) 1

Procedure for finding keys （）

• summary

There is no need to add, delete or change , It's simple , Just find the location and perform the corresponding operation , We said earlier redis The whole data is based on k-v Is stored in the form of , that redisDb Dictionary in structure Dict The bottom layer is the hash table ,Dict Address to hash table , As we said before , Hash table is divided into 0 Number and 1 Number ;0 Number is used to store elements ,1 Number is rehash When using

lookup （ Addressing ） The process ：

1. First judge 0 Hash table No ,1 Whether the hash table is empty , If 0 If No. is empty, it will directly return null.
2. Judge 0 No. is in progress rehash, If in the rehashing Stage , that 2 All tables may exist key. If it's going on rehash, Will call once _dictRehashStep Method ,_dictRehashStep For database dictionary 、 And hash key dictionary for passive rehash.
3. To calculate hash value , According to the current dictionary and key value , To calculate the hash value .
4. Calculate the index , According to the current dictionary and hash value , To calculate the key The index .
5. According to the index value , Find the corresponding linked list , Traverse the link to find key Matching data .
6. When ht[0] After searching , Again rehash Judge , If not rehashing, And end it , Otherwise, yes ht[1] repeat 3 4 5 step .（ If in the rehashing Stage , be ht[1] It may also exist key, At this time, you need to ht[1] Repeat on 345 step , If not rehash Stage , be ht[1] If it is empty, there is no need to judge ）

1.4 Set the key's lifetime or expiration time

• Set the expiration time of the key

expire and expireat It's all about setting the expiration time , One more setex command , This is to set a string key and set the expiration time for the key ,setex String keys only

• Get the expiration time of the key

TTL and PTTL Command can get the remaining expiration time of a key , These remaining expiration times are saved in redisDB Of expires Dictionaries （ Out of date Dictionary ） in

Expired key determination ：

• Through out of date dictionaries , The program can use the following steps to check whether a given key has expired

Check whether the given key exists in the expired Dictionary ; If there is , So get the expiration time of the key

• Check current UNIX Whether the time stamp is greater than the expiration time of the key

• If yes , Then the key has expired
• No. , Key not expired

• Summarize four commands for setting expiration time

• EXPIRE<key> <ttl>： The command is used to key key The lifetime of is set to ttl second .
• PEXPIRE<key> <ttl>： The command is used to key key The lifetime of is set to ttl millisecond .
• EXPIREAT<key> <timestamp>： The command is used to key key The expiration time for is set to timestamp The time stamp of the specified number of seconds .
• PEXPIREAT<key> <timestamp>： The command is used to key key The expiration time for is set to timestamp The specified number of milliseconds .

• summary

Although there are many different units and different forms of setting commands , But actually EXPIRE、PEXPIRE、EXPIREAT All three commands use PEXPIREAT Command to achieve ： No matter which of the above four commands is executed by the client , After the conversion , The final execution effect is the same as the execution PEXPIREAT command .

• Remove expiration time

persist command

• Expired keys under two persistence policies

• about ROB The generation and loading of files ignore the expiration key, that is, they are not affected by the expiration key , But the process is a little different , For example, for ROB When loading files , If it is loaded into the slave server, all keys will be loaded , However, when synchronizing to the primary server, the expiration key will be filtered out
• about AOF File writing and rewriting are the same as filtering out expired keys

• Copy

When the master and slave servers are replicating , Whether the expiration key is deleted or not is entirely up to the master server , After the primary server queries, it is checked that this key is an expired key to be deleted DEL command , This command synchronizes to the slave server and deletes the corresponding key from the server , Because of this mechanism , When the master server and the slave server have the same expiration key and the reconstruction is not queried and checked on the master server DEL when , When you query the expired key from the server, you will return the corresponding value It's worth it , But if you visit the primary server first, you will return null, And delete the key of the master-slave server

• Database notification

• Key space notification ： Pay attention to what commands are executed on this key
• Key time notification ： Notice what key is executing a command

1.5 Expiration deletion policy & Redis Expired policies used

Expiration deletion policy

• Three deletion strategies for expired keys , The first and third are active deletion strategies , The second is passive deletion

• Delete regularly ： While setting the key expiration time , Create a timer (timer), Let the timer when the key expires , Delete the key immediately .
• Lazy deletion ： Let the key expire , But every time you get a key from the key space , Check whether the obtained key is expired , If it's overdue , Delete the key ; If it doesn't expire , Just go back to the key .
• Delete periodically ： Every once in a while , Program on the database for a check , Delete the expiration key inside . As for how many expiration keys to delete , And how many databases to check , It's up to the algorithm .

• Delete regularly

advantage ： Timing is very memory friendly ,

shortcoming ：

• But for CPU Will increase resource consumption , When there are a large number of expired keys, it is necessary to establish a timer to record the deletion , that CPU Will take a long time to process , When there are many connections to handle CPU Resources should be placed on processing connections rather than deleting expired keys ,
• And the creation timer needs redis Middleware to assist implementation , This is a linked list, and the timer needs to On Complexity , That's why I picked up sesame seeds and lost watermelon **

• Lazy deletion

advantage ： This pair CPU It's friendly , You can check the expiration time after getting the key , This can ensure that the operation of deleting the expired key will only be carried out when it has to be done , And the target of deletion is limited to the currently processed key , This policy does not spend any time deleting other unrelated expired keys CPU Time

shortcoming ： But not memory friendly , Because a key that has expired will still be saved in the database , As long as this key is not deleted, it will remain in memory , When enough expired keys are not deleted, it can be regarded as a memory leak , The server will not take the initiative to release . So especially for log journal , When it exceeds a certain time, it will be automatically deleted

• Delete periodically

For the complementarity of the above two strategies , But we need to find a balance between time and frequency , Otherwise, there will be serious consequences

• Periodically delete the policy and delete the expired key every once in a while , And by limiting the duration and frequency of deletion operation, the deletion operation pair can be reduced CPU The effect of time
• By removing the expired key on a regular basis , The periodic deletion strategy effectively reduces the memory waste caused by expired keys

Redis Expired policies used

• Redis Expired policies used

Redis Use lazy delete and periodic delete fits , The server can allocate resources reasonably

Implementation of lazy delete strategy ：

The lazy deletion policy for expired keys is determined by expireIfNeeded Function implementation , All read and write databases Redis Commands call... Before execution expireIfNeeded Function to check the input key （ This function is like a AOP Prior notice of , Delete expired keys before actually executing the command ）

• If the input key has expired , that expireIfNeeded Function deletes the input key from the database
• If the input key has not expired , that expireIfNeeded The function does not act

Periodically delete the implementation of the policy ：

The periodic deletion policy of expired keys is determined by activeExpireCycle Function implementation , whenever Redis The periodic operation of the server serverCron Function execution time ,activeExpireCycle The function will be called , It's within the prescribed time , Traverse the databases in the server several times , From the database expires Randomly check the expiration time of some keys in the dictionary , And delete the expiration key

• The running steps of the function ：

• Every time the function runs , Take a certain number of random keys from a certain number of databases for inspection , And delete the expiration key
• Global variables current_db Will record the current activeExpireCycle Function to check the progress , And next time activeExpireCycle When a function is called , Then process the last progress . for instance , If at present activeExpireCycle The function is traversing 10 Database number returned , So next time activeExpireCycle Function execution time , Will be taken from 11 No. database starts to find and delete expired keys
• With activeExpireCycle The continuous execution of functions , All databases in the server will be checked , Then the function will current_db The variable is reset to 0, Then start a new round of inspection again

1.6 Redis Expiration elimination strategy

• summary

With the expiration time, there may still be a large number of key Can't be cleaned up OOM, So in order to solve this problem ,Redis To build the 8 Expiration elimination strategy in , To complement expired deletion

• The classification is as follows

1. volatile-lru（least recently used）： From the set of data for which the expiration time has been set （server.db[i].expires） Choose the least recent to make ⽤ The data is eliminated .
2. allkeys-lru（least recently used）： When memory is not ⾜ To accommodate newly written ⼊ Data time , In key space , Remove the most recent to make ⽤ Of key（ This is the most common ⽤ Of ）.
   3. volatile-lfu（least frequently used）： From the set of data for which the expiration time has been set (server.db[i].expires) Choose the least often to make ⽤ The data is eliminated .
3. allkeys-lfu（least frequently used）： When memory is not ⾜ To accommodate newly written ⼊ Data time , In key space , Remove the least frequently made ⽤ Of key.
4. volatile-random： From the set of data for which the expiration time has been set （server.db[i].expires） In the arbitrary selection of data elimination .
5. allkeys-random： From the data set （server.db[i].dict） In the arbitrary selection of data elimination .
6. volatile-ttl（time to live）： From the set of data for which the expiration time has been set （server.db[i].expires） To select the data to be expired .
7. no-eviction： Forbid ⽌ Expulsion data , That is, when memory is not ⾜ To accommodate newly written ⼊ Data time , New writing ⼊ The operation will report an error .（ The default configuration , But you shouldn't use this ）.

LRU The implementation of the ：

Redis One was maintained internally 24 Bit clock , Each object also maintains a clock , Every time you use an object , The clock will become the timestamp of the current system , When it needs to be done LRU When , For example, select the clock to eliminate the object with the longest current system time .

LFU The implementation of the ：

take 24 The bit clock is divided into two parts , front 16 Bits represent time , after 8 Bits represent the number of times used , If used many times before , It has not been used recently. It will decay according to time , in addition , To prevent a key Just joined and deleted , So I'll be interested in the new key Assign an initial value 5.