When we meet an attractive interviewer in a job interview, we think the interview will be easier and we will be able to show off our skills. But here’s the thing: when a beautiful interviewer hears you’ve used Redis, it raises a question.

👩 Interviewer: Q1, do you know the Redis command that sets the expiration time of a key?

👧 you: you don’t hesitate to blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah

🎈 This time you want to ask so simple? But is it really that simple? The interviewer pauses, then asks.

👩 Interviewer: Q2, how does Redis implement the expiration date? And how do you tell if the key is out of date? 👧 you :(at this time think this is still difficult to do with me), and then bala bala talk, Redis database server in the redisDb data structure and expiration time determination

(🎈 you are thinking again should not ask it, change the topic of Redis, then you are wrong)

👩 interviewer :(looks up at you with a smile) Q3, what about the deletion strategy of expired keys and the deletion strategy and implementation of Redis expired keys? 🤦️ you: Then you answer is not so fluent, sometimes the mind is blocked.

(🎈 this is you may be a little bit confused, or only know some expired key delete strategy, but specific how to achieve do not know ah, you think the interviewer’s questions so over?)

👩 interviewer: Q4, how do you deal with expired keys (such as AOF and RDB) in other links? 🤦 🤦 : you…

(🎈 this is more embarrassing, know not complete, may not know, originally wanted to perform well, but also thought the interview is relatively simple, did not expect to experience these)

To avoid this awkward situation, jot down the following information so you can impress an attractive interviewer.

1. Redis Expire Key foundation

Redis database uses the redisDb data structure in the database server, which is as follows:

typedef struct redisDb { dict *dict; /* Key space key space */ dict *expires; /* Expired 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;Copy the code

Among them,

  • Key space (key spaceDict dictionaries are used to hold all key-value pairs in a database
  • Expired dictionary (expires): Saves the expiration time of all keys in the databaseUNIXThe timestamp represents, and the value islong longThe integer

1.1 Setting the Expiration Time Command

  • EXPIRE \

    \< TTL > : the EXPIRE

    command is used to set the expiration time of the key to TTL seconds later

  • The PEXPIRE \

    \< TTL > : command is used to set the expiration time of the key to TTL milliseconds later
  • The EXPIREAT \

    \

    : command is used to set the expiration time of the key to the timestamp in seconds specified by timrestamp

  • PEXPIREAT \

    \

    : The PEXPIREAT \

    \

    command is used to set the expiration time of the key to the milliseconds timestamp specified by timrestamp



Set expiration time:

redis> set Ccww   5 2 0  
ok  
redis> expire Ccww 5  
ok  
Copy the code

Use redisDb structure to store data graph representation:

1.2 Preservation and determination of expiration time

The expiration key can be determined by the expiration dictionary. The steps are as follows:

  1. Checks if the given key exists in the expired dictionary, and if so, retrieves the expiration time of the key
  2. Determines 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.

2. Delete the expiration key

2.1 Three Different Deletion strategies

  1. Scheduled deletion: When the expiration time of a key is set, a scheduled task is created. When the expiration time of a key reaches, the key is deleted immediately
  2. Lazy deletion: a key is allowed to expire, but each time a key is retrieved from the key space, the retrieved key is checked for expiration, if expired, the key is deleted, and if not, the key is returned
  3. Periodically delete: Every once in a while, the program checks the database and removes expired keys. The algorithm decides how many expired keys to delete and how many databases to check.

2.2 Advantages and disadvantages of the three deletion strategies

2.2.1 Scheduled Deletion

  • Advantages: Memory friendly, a timed deletion policy ensures that expired keys are deleted as quickly as possible and free up memory occupied during the country
  • Disadvantages: Not friendly to CPU time. Deleting expired keys occupies a large part of CPU time when there are too many expired keys. Deleting expired keys irrelevant to the current task when the memory is not tight but THE CPU time is tight affects the response time and throughput of the server

2.2.2 Lazy Deletion

  • Advantages: CPU time friendly, expired keys are checked and deleted each time a key is retrieved from the key space, deletion targets are also limited to currently processed keys, and this policy does not spend any CPU time on unrelated deletion tasks.
  • Disadvantages: not memory friendly, expired keys may not be deleted, resulting in occupied memory will not be released. Memory leaks can even occur when there are many expired keys that are not accessed, which can cause them to remain in memory forever, causing memory leaks.

2.2.4 Delete files periodically

Due to the fact that scheduled deletion takes up too much CPU time, affects the response time and throughput of the server, and lazy deletion wastes too much memory and has the risk of memory leakage, a periodic deletion strategy that integrates and compromises these two strategies emerges.

  1. The periodic deletion policy performs the deletion expiration key at intervals and limits the duration and frequency of the deletion operation to reduce the impact on the CPU time.
  2. The timed deletion strategy effectively reduces memory waste due to expired keys.

The difficulty of the periodic deletion policy is to determine the duration and frequency of the deletion operation:

Delete operations are performed too frequently. If the execution time is too long, the periodic deletion policy degenerates into a periodic deletion policy and consumes too much CPU time to delete expired keys. On the contrary, the lazy deletion strategy is the same as the waste of memory. Therefore, to use the periodic deletion policy, set the execution duration and frequency of the deletion operation based on the server conditions.

3. Expiry key deletion policy of Redis

Redis server is used together with lazy deletion and periodic deletion. Through the combination of these two strategies, the server can strike a balance between rational use of CPU time and waste of memory space.

3.1 Implementation of lazy deletion policy

Redis finds this key before any read or write command is executed, and lazy deletion is used as a pointcut before looking for the key, and if the key is out of date, it is removed.

robj *lookupKeyRead(redisDb *db, robj *key) { robj *val; expireIfNeeded(db,key); // pointcut val = lookupKey(db,key); if (val == NULL) server.stat_keyspace_misses++; else server.stat_keyspace_hits++; return val; }Copy the code

throughexpireIfNeededThe function checks whether the input key is deleted

Int expireIfNeeded(redisDb *db, robj *key) {/* Expire time */ mstime_t when = getExpire(db,key); mstime_t now; /* If (when < 0) return 0; /* No expire for this key */ /* Server loading */ if (server.loading) return 0; /* Obtain the current time according to certain rules */ now = server.lua_caller? server.lua_time_start : mstime(); If we think the key is expired at this time. * */ if (server.masterhost! = NULL) return now > when; If (now <= when) return 0; /* delete key */ server.stat_expiredKeys ++; propagateExpire(db,key,server.lazyfree_lazy_expire); notifyKeyspaceEvent(NOTIFY_EXPIRED, "expired",key,db->id); return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) : dbSyncDelete(db,key); }Copy the code

3.2 Implementation of the periodic deletion policy

The key is periodically deleted in the Redis periodic execution task (serverCron, every 100ms by default), and is the master node where the Redis occurs, because the slave node is synchronized with the DEL command on the master node to delete the key.

for (j = 0; j < dbs_per_call; j++) { int expired; redisDb *db = server.db+(current_db % server.dbnum); current_db++; */ do {unsigned long num, slots; long long now, ttl_sum; int ttl_samples; /* If ((num = dictSize(db->expires)) == 0) {db->avg_ttl = 0; break; } slots = dictSlots(db->expires); now = mstime(); /* If (num && slots > DICT_HT_INITIAL_SIZE && (num*100/slots < 1)) break; 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; If (db->avg_ttl == 0) db->avg_ttl = avg_ttl; db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50); } 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; } /* If (timelimit_exit) return; /* Stop deleting expired keys */} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4); /* Stop deleting expired keys */} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4) }Copy the code

For each DB, 20 (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP) keys are randomly selected for each db. If less than 25% of the selected keys are expired, the loop terminates repeatedly. In addition, the expiration deletion process is terminated if a certain time limit is exceeded during iteration.

4. Processing of expired keys by AOF, RDB and replication functions

4.1 RDB

The RDB file generation program checks the keys in the database. Expired keys are not saved to the newly created RDB file

Load the RDB file

  1. The primary service loads the RDB file, checks the keys saved in the file and loads the unexpired keys ignoring the expired keys
  2. Loading the RDB file from the server loads all the keys (expired and unexpired) stored in the file, but synchronizing data from the primary server also clears the secondary database.

4.2 AOF

  • AOF file writing: When an expired key is deleted, a DEL command is added to the AOF file to explicitly record that the key was deleted.
  • AOF overwriting: Expired keys are not saved to the overwritten AOF file

4.3 copy

When the server is running in replication mode, the expiration key deletion action of the secondary server is controlled by the primary server. This benefit is mainly to maintain data consistency between the primary and secondary servers:

  1. After removing an expired key, the master server explicitly sends a DEL command to all slave servers to tell slave servers to remove the expired key
  2. When the slave server executes the read command sent by the client, it does not delete the expiration key even if it encounters the expiration key.
  3. The secondary server is deleted only after receiving the primary server DEL command.

Is everyone still ok? If you like, move your hands to show 💗, point a concern!! Thanks for your support!

Welcome to pay attention to the public number [Ccww technology blog], original technical articles launched at the first time