As an important mechanism for periodically cleaning up invalid data, primary key invalidation exists in most caching systems, and Reids are no exception. Among the commands provided by Redis, EXPIRE, EXPIREAT, PEXPIRE, PEXPIREAT, SETEX and PSETEX can be used to set the expiration time of a key-value pair. A key-value pair, once associated with an expiration date, is automatically deleted after expiration (or becomes inaccessible more accurately). The concept of primary key invalidation is easy to understand, but how does it work in Redis? Recently, this blogger has had several questions about the primary key failure mechanism in Redis, and has conducted a careful exploration of it according to these questions. Now the summary is as follows for you to see.
Aside from calling PERSIST, are there any other circumstances in which the expiration time of a primary key can be undone? The answer is yes. First, when a primary key is deleted with the DEL command, the expiration time is automatically reversed. Second, when a primary key with an expiration date is overwritten by an update, the expiration date of that primary key will also be revoked. SET, MSET, or GETSET may cause the primary key to be overwritten by the update, while INCR, DECR, LPUSH, HSET, etc., are the values corresponding to the update. This type of operation does not touch the expiration time of the primary key. In addition, there is a special command called RENAME. When we RENAME a primary key, the expiration time of the previous association is automatically passed to the new primary key. However, if a primary key is overwritten by RENAME (for example, if the primary key Hello is overwritten by the RENAME world Hello command), the expiration time of the overwritten primary key is automatically revoked, and the new primary key retains the characteristics of the original primary key.
How is primary key invalidation implemented in Redis, that is, how is invalid primary key deleted? In fact, There are two methods for Redis to delete invalid primary keys: 1) Passive way: Delete invalid primary keys if they are found to be invalid when they are accessed; 2) Active way: periodically delete some invalid primary keys from the primary keys whose expiration time is set. We’ll explore the implementation of these two methods in code, but before we do that, let’s take a look at how Redis manages and maintains primary keys (note: all the source code in this blog post is from RedIS-2.6.12).
The first section of code gives the structure definition of the database in Redis. Except for ID, the structure definition is all Pointers to the dictionary. We only look at dict and Expires. The former is used to maintain all key-value pairs contained in a Redis database (dict[Key]: Value) The latter is used to maintain a primary key in a Redis database with an expiration date set (the structure can be understood as expires[key]:timeout, which is a mapping of the primary key and expiration time). When we use SETEX and PSETEX to insert data into the system, Redis first adds keys and values to the dict dictionary table, and then keys and expires to the Expires dictionary table. When we use EXPIRE, EXPIREAT, PEXPIRE, and PEXPIREAT commands to set the expiration time of a primary key, Redis first looks up the dict dictionary table to see if the primary key exists, and if so, adds the primary key and expiration time to the Expires table. Simply put, a primary key with an expiration date and an expiration date are all maintained in the expires dictionary table.
Code snippet 1:
typedef struct redisDb {
dict *dict;
dict *expires;
dict *blocking_keys;
dict *ready_keys;
dict *watched_keys;
int id;
} redisDb;
With an overview of how Redis maintains stale primary keys, let’s take a look at how Redis passively removes stale primary keys. A function called expireIfNeeded is called in any function that accesses data. That is, Redis calls it when implementing GET, MGET, HGET, LRANGE, and other commands that involve reading data. Its purpose is to check that data is invalid before reading it, and delete it if it is. The expireIfNeeded function is described in section 2, and its implementation is not repeated here. Another function called in the expireIfNeeded function, propagateExpire, is used to broadcast invalid primary keys to two destinations before they are officially deleted: One is to send an AOF file to record the deletion of the invalid primary Key in the standard command format of DEL Key. The other is all slaves sent to the current Redis server. The operation of deleting invalid primary keys is also told to delete their own invalid primary keys in the standard command format of DEL Key. From this we can see that all Redis servers running as slaves do not need to use negative methods to remove invalid primary keys, they only need to obey the Master!
Code snippet 2:
int expireIfNeeded(redisDb *db, robj *key) {
Gets the expiration time of the primary key
long long when = getExpire(db,key);
If the expiration time is negative, it indicates that the expiration time is not set for the primary key (the default expiration time is -1) and 0 is returned
if (when < 0) return 0;
If the Redis server is loading data from the RDB file, return 0 instead of deleting invalid primary keys
if (server.loading) return 0;
If the current Redis server is running as a Slave, then the deletion of invalid primary keys is not performed, because Slave
Deletion of invalid primary keys is controlled by the Master, but the deletion time of the invalid primary key is compared with the current time
To tell the caller if the specified primary key has been invalidated
if (server.masterhost ! = NULL) {
return mstime() > when;
}
If none of the preceding conditions is met, the expiration time of the primary key is compared with the current time. If the specified primary key is found
Return 0 if it’s not invalidated
if (mstime() <= when) return 0;
If it is found that the primary key is indeed invalid, the statistics on the invalid primary key are updated first, and then the primary key is lost
The primary key is deleted from the database
server.stat_expiredkeys++;
propagateExpire(db,key);
return dbDelete(db,key);
}
Code snippet 3:
void propagateExpire(redisDb *db, robj *key) {
robj *argv[2];
Shared. del is a common Redis object that is initialized when the Redis server is started, namely the del command
argv[0] = shared.del;
argv[1] = key;
incrRefCount(argv[0]);
incrRefCount(argv[1]);
Check if THE Redis server has AOF enabled, and if so, log a DEL for the failed primary key
if (server.aof_state ! = REDIS_AOF_OFF)
feedAppendOnlyFile(server.delCommand,db->id,argv,2);
Check if Redis server owns slaves, if so send DEL invalid primary key to all slaves, here it is
The expireIfNeeded function does not need to actively remove the cause of invalid primary keys when it discovers that it is a Slave
Just follow the command sent by the Master
if (listLength(server.slaves))
replicationFeedSlaves(server.slaves,db->id,argv,2);
decrRefCount(argv[0]);
decrRefCount(argv[1]);
}
The expireIfNeeded function is used to remove invalid primary keys in a negative way. However, this is not enough because Redis will never know that invalid primary keys are invalid if they are not accessed again. They will never be deleted, which will result in wasted memory space. Therefore, Redis has also prepared an aggressive deletion method that uses Redis timing events to interrupt at regular intervals to complete certain operations, including checking for and removing invalid primary keys. The time event callback we are talking about here is serverCron, which is created when the Redis server starts. The number of times per second is specified by the macro definition REDIS_DEFAULT_HZ, which is 10 times per second by default. Code section 4 shows the program code at the time the event is created, in the initServer function of the redis.c file. ServerCron not only checks for and removes invalid primary keys, but also updates statistics, controls client connection timeouts, BGSAVE and AOF triggers, etc. Here we focus on the implementation of the deletion of invalid primary keys, namely activeExpireCycle.
Code snippet 4:
if( aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL) == AE_ERR) {
redisPanic(“create time event failed”);
exit(1);
}
Code section 5 gives the implementation and detailed description of the function activeExpireCycle. Its main implementation principle is to iterate through the Expires dictionary table of each database in Redis server. Try sampling REDIS_EXPIRELOOKUPS_PER_CRON (default value: 10) randomly to check whether they are invalid and delete the invalid primary keys. If the number of invalid primary keys accounts for more than 25% of the sample number, Redis will assume that there are still a lot of failed primary keys in the current database, so it will continue with the next round of random sampling and deletion until the percentage drops below 25% before it stops processing the current database and moves on to the next database. Note that the activeExpireCycle function does not attempt to process all the databases in Redis at once, but at most REDIS_DBCRON_DBS_PER_CALL (the default is 16), In addition, the activeExpireCycle function also has a limited processing time. It does not run as long as it wants to. All of this has one purpose: to avoid excessive CPU usage for invalid primary key deletion. In code section 5, all the codes of activeExpireCycle are described in detail to learn how to implement the function.
Code snippet 5:
void activeExpireCycle(void) {
Because each call to the activeExpireCycle function does not check all Redis databases at once, you need to record it
The number of the last Redis database processed by each function call, so that the next call to the activeExpireCycle function is made
You can also continue processing from this database, which is why current_DB is declared static, while the other
The timelimit_exit variable is used to record whether the execution time of the last call to the activeExpireCycle function was reached
We are running out of time, so we need to declare static as well
static unsigned int current_db = 0;
static int timelimit_exit = 0;
unsigned int j, iteration = 0;
The number of Redis databases processed by invoking the activeExpireCycle function each time is REDIS_DBCRON_DBS_PER_CALL
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
long long start = ustime(), timelimit;
If the number of databases in the current Redis server is less than REDIS_DBCRON_DBS_PER_CALL, all databases are processed.
If the execution time of the activeExpireCycle function last time reaches the upper limit, many invalid primary keys are used
Will choose to process all databases
if (dbs_per_call > server.dbnum || timelimit_exit)
dbs_per_call = server.dbnum;
The longest time (in microseconds) to execute the activeExpireCycle function, where REDIS_EXPIRELOOKUPS_TIME_PERC
Specifies the percentage of CPU time that can be allocated to the activeExpireCycle function. The default value is 25, server.hz
Is the number of activeExpireCycle calls in one second, so the calculation formula should be more clearly written like this, namely
(1000000 * (REDIS_EXPIRELOOKUPS_TIME_PERC / 100)) / server.hz
timelimit = 1000000*REDIS_EXPIRELOOKUPS_TIME_PERC/server.hz/100;
timelimit_exit = 0;
if (timelimit <= 0) timelimit = 1;
Traversal processes invalid data in each Redis database
for (j = 0; j < dbs_per_call; j++) {
int expired;
redisDb *db = server.db+(current_db % server.dbnum);
Incrementing current_DB immediately ensures that even this time, you won’t be able to delete all the current times within the time limit
The next call to activeExpireCycle will start processing the invalid primary key from the next database.
This ensures that every database has a chance to be processed
current_db++;
Start processing invalid primary keys in the current database
do {
unsigned long num, slots;
long long now;
If the expires dictionary table size is 0, the database does not have a primary key that sets the expiration date
A database
if ((num = dictSize(db->expires)) == 0) break;
slots = dictSlots(db->expires);
now = mstime();
If the Expires dictionary table is not empty, but its fill rate is less than 1%, the cost of randomly selecting a primary key for checking
It’s going to be high, so I’m going to check the next database
if (num && slots > DICT_HT_INITIAL_SIZE &&
(num*100/slots < 1)) break;
expired = 0;
If the expires dictionary table does not have enough entries to sample, all keys are selected as samples
if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
num = REDIS_EXPIRELOOKUPS_PER_CRON;
while (num–) {
dictEntry *de;
long long t;
Randomly obtain a primary key with an expiration time and check whether it has expired
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
t = dictGetSignedIntegerVal(de);
if (now > t) {
The primary key is invalid and deleted
sds key = dictGetKey(de);
robj *keyobj = createStringObject(key,sdslen(key));
Also broadcast the invalidation of the primary key before deleting it
propagateExpire(db,keyobj);
dbDelete(db,keyobj);
decrRefCount(keyobj);
expired++;
server.stat_expiredkeys++;
}
}
Add one to iteration after each sample deletion. Check whether the execution time is correct after every 16 sample deletions
The time limit is reached. If the time limit is reached, the system records that the time limit is reached and exits
iteration++;
if ((iteration & 0xf) == 0 &&
(ustime()-start) > timelimit)
{
timelimit_exit = 1;
return;
}
If the percentage of failed primary keys in the sample is greater than 25%, the sampling deletion process continues
} while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4);
}
}
How does Memcached delete invalid primary keys from Redis? First, Memcached also takes a passive approach when deleting a stale primary key, meaning that Memcached does not monitor the stale primary key internally, but only checks if it is stale when it is accessed via Get. Second, the main difference between Memcached and Redis in primary key invalidation is that Memcached does not actually delete the failed primary key as Redis does. Instead, Memcached simply retakes the space used by the failed primary key. This way, when new data is written to the system, Memcached will preferentially use the stale primary key space. If the stale primary key runs out of space, Memcached can also use the LRU mechanism to reclaim space that has not been accessed for a long time, so Memcached does not require the periodic deletion that occurs in Redis. This is due to the memory management mechanism Memcached uses. In addition, Redis can also set maxmemory-policy to determine whether to use LRU to reclaim memory in OOM (thanks @jonathan_dai)Xenojoshua.com/2013/07/red…A correction of the original text in
)!
Will the primary key failure mechanism of Redis affect system performance? From the above introduction to the primary key invalidation mechanism of Redis, we know that although Redis will periodically check the primary key whose expiration time is set and delete the primary key that has expired, However, by limiting the number of databases processed at a time, the number of times the activeExpireCycle function can be executed in one second, the CPU time allocated to the activeExpireCycle function, and the percentage of failed primary keys that can continue to be deleted, Redis has greatly reduced the impact of primary key failure mechanism on the overall performance of the system. However, if a large number of primary key failures occur simultaneously in a short time in practical application, the response capability of the system will still be reduced, so this situation should undoubtedly be avoided.
Redis. IO/Commands /ex… & redis. IO/switchable viewer/newest… &
www.cppblog.com/richbirdand… &
www.cnblogs.com/tangtianfly…