Shulou(Shulou.com)06/01 Report--

If a key expires, when will it be deleted?

There are three possible answers to this question, each representing three different deletion strategies:

Timed Delete: Creates a timer at the same time as setting the key expiration time. Have the timer delete the key as soon as the key expires. Lazy Delete: Allow the key to expire, but each time a key is retrieved from the keyspace, check whether the retrieved key is expired, delete the key if it is expired, and return the key if it is not expired. Periodically delete: Every once in a while, the program checks the database to remove expired keys. How many expired keys to delete and how many databases to check is up to the algorithm.

Of these three policies, the first and third are active deletion policies, while the second is passive deletion policy.

preface

When using Redis, we can use EXPIRE or EXPIREAT command to set the expiration deletion time for key. The expires dictionary in the structure redisDb stores the expiration time of all keys. The key of this dictionary (dict) is a pointer to a key object in Redis. The value of the expiration dictionary is an integer that stores the expiration time.

/* Redis database representation. There are multiple databases identified * by integers from 0 (the default database) up to the max configured * database. The database number is the 'id' field in the structure. */typedef struct redisDb { dict *dict; /* The keyspace for this DB */ dict *expires; /* obsolete dictionary */ dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */ dict *ready_keys; /* Blocked keys that received a PUSH */ dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */ int id; /* Database ID */ long long avg_ttl; /* Average TTL, just for stats */} redisDb;

Set expiration time

Whether it is EXPIRE, EXPIREAT, or PEXPIRE, PEXPIREAT, the underlying implementation is the same. Find the key to set the expiration time in Redis key space, and add this entry (pointer to key, expiration time) to the expiration dictionary.

void setExpire(redisDb *db, robj *key, long long when) { dictEntry *kde, *de; /* Reuse the sds from the main dict in the expire dict */ kde = dictFind(db->dict,key->ptr); redisAssertWithInfo(NULL,key,kde != NULL); de = dictReplaceRaw(db->expires,dictGetKey(kde)); dictSetSignedIntegerVal(de,when);}

Expired Delete Policy

If a key expires, when will it be deleted? There are two types of expiration deletion policies in Redis: (1) lazy expiration deletion; and (2) periodic deletion. Let's look at it in detail.

inertness expiration deletion

Redis will find this key first when executing any read/write command. Lazy deletion will be placed as an entry point before finding the key. If the key expires, it will delete the key.

robj *lookupKeyRead(redisDb *db, robj *key) { robj *val; expireIfNeeded(db,key); //cut-in val = lookupKey(db,key); if (val == NULL) server.stat_keyspace_misses++; else server.stat_keyspace_hits++; return val;}

periodically delete

The periodic deletion of keys is performed in the periodic execution task of Redis (serverCron, executed every 100ms by default), and it is the master node where Redis occurs, because the slave node will synchronize to delete keys through the DEL command of the master node.

Traverse each db in turn (default configuration number is 16), for each db, randomly select 20 (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP) keys each time to judge whether they are expired. If less than 25% of the keys selected in one round are expired, terminate the process repeatedly. In addition, if a certain time limit is exceeded in the iteration process, terminate the process of deleting expired keys.

for (j = 0; j

< dbs_per_call; j++) { int expired; redisDb *db = server.db+(current_db % server.dbnum); /* Increment the DB now so we are sure if we run out of time * in the current DB we'll restart from the next. This allows to * distribute the time evenly across DBs. */ current_db++; /* Continue to expire if at the end of the cycle more than 25% * of the keys were expired. */ do { unsigned long num, slots; long long now, ttl_sum; int ttl_samples; /* 如果该db没有设置过期key，则继续看下个db*/ if ((num = dictSize(db->

expires)) == 0) { db->avg_ttl = 0; break; } slots = dictSlots(db->expires); now = mstime(); /* When there are less than 1% filled slots getting random * keys is expensive, so stop here waiting for better times... * The dictionary will be resized asap. */ if (num && slots > DICT_HT_INITIAL_SIZE && (num*100/slots

< 1)) break; /* The main collection cycle. Sample random keys among keys * with an expire set, checking for expired ones. */ expired = 0; ttl_sum = 0; ttl_samples = 0; if (num >

ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP) num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;// 20 while (num--) { dictEntry *de; long long ttl; if ((de = dictGetRandomKey(db->expires)) == NULL) break; ttl = dictGetSignedIntegerVal(de)-now; if (activeExpireCycleTryExpire(db,de,now)) expired++; if (ttl > 0) { /* We want the average TTL of keys yet not expired. */ ttl_sum += ttl; ttl_samples++; } } /* Update the average TTL stats for this database. */ if (ttl_samples) { long long avg_ttl = ttl_sum/ttl_samples; /* Do a simple running average with a few samples. * We just use the current estimate with a weight of 2% * and the previous estimate with a weight of 98%. */ if (db->avg_ttl == 0) db->avg_ttl = avg_ttl; db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50); } /* We can't block forever here even if there are many keys to * expire. So after a given amount of milliseconds return to the * caller waiting for the other active expire cycle. */ iteration++; if (iteration & 0xf) == 0) { /* Check once every 16 iterations */ long long elapsed = ustime()-start; latencyAddSampleIfNeeded("expire-cycle",elapsed/1000); if (elapsed > timelimit) timelimit_exit = 1; } //exit if (timelimit_exit) return; /* Stop deleting expired keys if less than 25% of keys in current db are expired */ } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER/4);}

summary

Lazy deletion: Determine whether the key expires before reading or writing

Delete periodically: sample key periodically to determine whether it expires

Well, the above is the whole content of this article, I hope the content of this article has a certain reference value for everyone's study or work, if you have questions, you can leave a message to exchange, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.