I saw an interview question before: What are the expiration strategies of Redis? What are the memory flushing mechanisms? Write the LRU code implementation by hand? The author combined with the problems encountered in the work of learning analysis, I hope to read this article can be helpful to everyone.
Start with an indescribable glitch
Description: A timer task depends on the generated interface list data, sometimes, sometimes not.
Suspected Redis deletion policy expired
The troubleshooting process is long. Because the timer is manually executed, the set data does not report an error, but the set data does not take effect after the timer is executed.
Set did not report an error, but when the set was checked again, there was no data, began to suspect Redis expired deletion policy (to be precise, it should be Redis memory reclamation mechanism of data elimination policy triggered by the memory limit to eliminate data). , resulting in the new data added to Redis being discarded. Finally, it was found that the fault was caused by configuration error, which led to data writing in the wrong place, not the memory reclamation mechanism of Redis.
After this failure, if we encounter similar problems next time, how can we effectively prove the correctness of Redis memory reclamation after suspecting it? How can you quickly prove a guess right or wrong? And when is it reasonable to suspect memory reclamation? The next time you encounter a similar problem, you can locate the cause of the problem more quickly and accurately. In addition, the principle of Redis memory reclamation mechanism also needs to be mastered to understand what it is and why.
I spent some time looking up information to study the memory reclamation mechanism of Redis, and read the implementation code of memory reclamation, and share the memory reclamation mechanism of Redis with you through the code combined with the theory.
Why is memory reclamation needed?
-
In Redis, the set command can specify the expiration time of a key. When the expiration time is reached, the key will become invalid.
-
2, Redis is based on memory operation, all data is stored in memory, the memory of a machine is limited and very precious.
Based on the above two points, in order to ensure that Redis can continue to provide reliable services, Redis needs a mechanism to clear the infrequently used, invalid and redundant data. The data after failure needs to be cleared in time, which requires memory reclamation.
Redis memory reclamation mechanism
Redis memory reclamation is mainly divided into two parts: expired deletion strategy and memory elimination strategy.
Expired Deletion Policy
Delete keys that reached the expiration date.
1. Delete periodically
A timer is created for each key that has an expiration date and is immediately deleted once the expiration date is reached. This policy can immediately clear expired data and is more memory friendly. However, the disadvantage is that it consumes a large amount of CPU resources to process expired data, which affects Redis throughput and response time.
2. Lazy deletion
When a key is accessed, the system checks whether the key is expired. If the key expires, it is deleted. This strategy maximizes CPU savings, but is very memory unfriendly. At the extreme end of the spectrum, a large number of expired keys may not be accessed again and therefore will not be cleared, resulting in a large amount of memory usage.
In computer science, lazy deletion refers to a method of deleting elements from a hash table (also called a hash table). In this method, deletion only refers to the deletion of an element, not the entire deletion. Deleted sites are treated as empty elements when inserted and occupied when searched.
3. Delete regularly
Every once in a while, scan the expired key dictionary in Redis and remove some expired keys. This strategy is a compromise of the former two. It can also adjust the interval of periodic scan and the time limit of each scan to achieve the optimal balance of CPU and memory resources in different situations.
In Redis, both periodic deletion and lazy deletion are used.
Principle of the expiration deletion policy
In order not to sound confused, before introducing the principle of expiration deletion strategy, I will introduce you to some Redis basics that you may need.
RedisDb structure definition
As we know, Redis is a key-value database, for each Redis database, Redis uses a redisDb structure to save, its structure is as follows:
typedef struct redisDb { dict *dict; /* The database's key space, which holds all key value pairs in the database */ dict *expires; /* Save all expired keys */ 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 */ int id; /* database ID field, representing different databases */ long long avg_ttl; /* Average TTL, just for stats */ } redisDb;Copy the codeFor each Redis database, a dictionary data structure is used to hold each key/value pair. Dict shows the following structure:
The above is the core data structure used in the implementation of expiration policy. Program = data structure + algorithm, now that we’ve introduced the data structure, let’s move on to what the algorithm looks like.
Expires attribute
The second property redisDb defines is Expires, which is also a dictionary of types. Redis adds all expired key-value pairs to Expires and then periodically deletes them to clean up the expires value. Examples of expires scenarios are:
1, set specifies the expire time
If a key is set with an expiration time specified, Redis adds the key directly to the Expires dictionary and sets the expiration time to that dictionary element.
Invoke the expire command
Explicitly specifies the expiration time of a key
3. Restore or modify data
Restore the file or change the key from the Redis persistence file. If the key in the data already has an expiration date, add that key to the Expires dictionary
All of these actions save expired keys to Expires. Redis periodically cleans expired keys from the Expires dictionary.
The time when Redis cleans expired keys
1, When Redis is started, it will register two kinds of events, one is the time event, the other is the file event. Time events are events that Redis processes during background operations, such as client timeout and deletion of expired keys. File events are processing requests.
In the case of a time event, the redis registered callback function is serverCron, and in the case of a scheduled task callback, the databasesCron is called to clean up some of the expired keys. (This is an implementation of periodic deletion.)
Int serverCron(struct aeEventLoop *eventLoop, long long ID, void *clientData) {... /* Handle background operations on Redis databases. */ databasesCron(); . }Copy the code2. Each time a key is accessed, the expireIfNeeded function is called to determine whether the key is expired. If so, the key is cleared. (This is an implementation of lazy deletion.)
robj *lookupKeyRead(redisDb *db, robj *key) { robj *val; expireIfNeeded(db,key); val = lookupKey(db,key); . return val; }Copy the code3. Proactively clear some expired keys during the execution of the event cycle. (This is also an implementation of lazy deletion.)
void aeMain(aeEventLoop *eventLoop) {
eventLoop->stop = 0;
while (!eventLoop->stop) {
if (eventLoop->beforesleep != NULL)
eventLoop->beforesleep(eventLoop);
aeProcessEvents(eventLoop, AE_ALL_EVENTS);
}
}
void beforeSleep(struct aeEventLoop *eventLoop) {
...
/* Run a fast expire cycle (the called function will return
- ASAP if a fast cycle is not needed). */
if (server.active_expire_enabled && server.masterhost == NULL)
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_FAST);
...
}
Copy the codeImplementation of expiration policies
As we know, Redis runs in a single thread, so it should not take too much time and CPU to clean up keys. It is necessary to clean expired keys without affecting normal services as much as possible. The algorithm of overdue clearing is as follows:
1. Server. Hz Indicates the serverCron task execution period. The default interval is 10, that is, the serverCron task execution period is 10 times per second when the CPU is idle. Timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100; For example, if hz=1, the maximum cleaning time is 250ms, and if hz=10, the maximum cleaning time is 25ms. 3. In quick cleanup mode (in the beforeSleep function call), the maximum cleanup time is 1ms. 4. Iterate through all DB's in turn. 5. Select 20 keys randomly from the db expiration list to determine whether the keys are expired. If the keys are expired, clear them. If more than five keys have expired, repeat Step 5. Otherwise, continue to process the next DB. 7.Copy the codeAs can be seen from the implemented algorithm, this is a simple algorithm based on probability and random extraction, so it is impossible to delete all expired keys. By increasing the Hz parameter, the cleaning frequency can be improved, and expired keys can be deleted in a more timely manner, but too high Hz will increase the CONSUMPTION of CPU time.
Remove the key
Prior to Redis4.0, the delete instruction was del, which freed the object’s memory directly. In most cases, this instruction was very fast without any sense of delay. However, if the deleted key is a very large object, such as a hash containing tens of millions of elements, then the deletion will cause a single-thread stall and Redis will respond slowly. In order to solve this problem, the unlink instruction was introduced in the 4.0 version of Redis. the unlink instruction can “lazily” handle the deletion operation, throwing the deletion operation to the background thread, which can asynchronously reclaim the memory.
In practice, after determining that the key needs to expire, the actual process of deleting the key is to broadcast the EXPIRE event to the slave library and AOF files, and then decide whether to delete it immediately or asynchronously, depending on the redis configuration.
If the deletion is immediate, Redis will immediately free up the memory space occupied by the key and value, otherwise, Redis will free up the space needed for delayed deletion in another BIO thread.
summary
In general, Redis’s expires deletion strategy is to register the serverCron function at startup, and each time clock cycle, some keys in the Expires dictionary will be extracted for cleaning, so as to achieve periodic deletion. In addition, beforeSleep calls the activeExpireCycle function every time a Redis access event arrives to clean up part of the key in 1ms. This is the implementation of lazy deletion.
Redis is a combination of regular delete and inert deleted, basically can be a very good deal with expired data cleaning, but in fact I still have a question, if is the key date is more, regularly delete missed part of and there is no check in time, which has not gone inert to delete, so there will be a lot of accumulation is the key date in memory, lead to Redis memory exhaustion, What happens when you run out of memory and a new key arrives? Is it outright abandonment or something else? Is there a way to accept more keys?
Memory flushing strategy
Redis’s memory flushing strategy means that when the memory reaches the maxmemory limit, it uses some algorithm to decide which data to clean up to ensure the storage of new data.
Redis memory flushing mechanism
- Noeviction: New write operations will bug when memory is insufficient to accommodate new write data.
- Allkeys-lru: When memory is insufficient to hold new data written to the key space (
server.db[i].dict), remove the least recently used key (this is the most commonly used key). - Allkeys-random: When memory is insufficient to hold new data written to the key space (
server.db[i].dict), randomly remove a key. - Volatile -lru: When memory is insufficient to accommodate new writes, the key space (
server.db[i].expires), remove the least recently used key. - Volatile -random: When memory is insufficient to accommodate new writes, the key space (
server.db[i].expires), randomly remove a key. - Volatile – TTL: When memory is insufficient to accommodate new writes, the key space (
server.db[i].expires), keys with an earlier expiration date are removed first.
In the configuration file, you can configure which elimination mechanism to use through maxmemory-policy.
When will the cull take place?
Redis determines each time a command is processed (processCommand calls freeMemoryIfNeeded) whether the current Redis memory limit is reached, and if so, the corresponding algorithm is used to process the keys that need to be removed. The pseudocode is as follows:
int processCommand(client *c) { ... if (server.maxmemory) { int retval = freeMemoryIfNeeded(); }... }Copy the codeLRU implementation principle
The LRU algorithm (Latest Recently Used) is most commonly Used by Redis by default when weeding out keys. Redis stores the last access time of the key by saving the LRU attribute in each redisObject, and directly reads the LRU attribute of the key when implementing the LRU algorithm.
In the concrete implementation, Redis traverses each DB, randomly selects a batch of sample keys from each DB, default is 3 keys, and then deletes the least recently used key from the 3 keys. The pseudo-code is as follows:
keys = getSomeKeys(dict, sample)
key = findSmallestIdle(keys)
remove(key)
Copy the codeThe number 3 is the maxmeory-samples field in the configuration file, and it is also possible to set the sample size. If you set it to 10, it will work better, but it will also consume more CPU resources.
Above is the principle of Redis memory reclamation mechanism introduction, after understanding the above principle introduction, back to the beginning of the problem, in doubt when the Redis memory reclamation mechanism can determine whether the fault is caused by the Redis memory reclamation mechanism?
Go back to the origin of the problem
How do I prove that the failure was caused by the memory reclamation mechanism?
According to the previous analysis, if a set does not report an error, but does not take effect, there are only two cases:
- 1. The expiration time is too short, for example, 1s?
- Memory is out of maximum limit and noeviction or Allkeys-Random is configured.
Therefore, in this case, first check whether the expiration time is added to the set, and whether the expiration time is reasonable. If the expiration time is short, then check whether the design is reasonable.
If the expiration time is ok, you need to check the memory usage of Redis, check the configuration file of Redis, or use the info command in Redis to check the status of Redis, and the maxMemory property to check the maximum memory value. If the value is 0, there is no limit. In this case, usED_memory is compared with Redis maximum memory to check the memory usage.
If the current memory usage is high, you need to check if there is any Max memory configured, if there is any Max memory configured, you need to check if the key setup is not successful due to memory reclamation, and the memory flushing algorithm is noeviction or Allkeys-random, if it is, It can be confirmed that the memory reclamation mechanism of Redis is the cause. If the memory does not exceed the limit or the memory flushing algorithm is not the same as the preceding two, you need to check whether the key has expired and use TTL to check the lifetime of the key. If the set fails, the TTL should be updated immediately. If the set fails, you should check whether the operation code is correct.
conclusion
Redis has two ways to reclaim memory, one is to reclaim expired keys, and the other is to release memory when the maximum memory of Redis is exceeded.
For the first case, Redis will do this at:
1. During each access, check whether the key expiration time reaches. If so, delete the key
The default value is 10 times per second. The cleaning time of expired keys does not exceed 25% of the CPU time. That is, if hz=1, the cleaning time is 250ms at most, and if hz=10, the cleaning time is 25ms at most.
In the second case, Redis will determine whether the current redis reaches the maximum memory limit every time the redis command is processed. If the maximum memory limit is reached, the corresponding algorithm is used to process the key to be deleted.
After reading this article, can you answer the interview question at the beginning of the article?
thinking
We know that Redis is single-threaded. Single-threaded Redis also contains so many tasks for each thread that processes commands: processing commands, cleaning up expired keys, handling memory reclamation, etc. Why can it be so fast? What are the optimizations in there? Stay tuned to explore this question later.
Original article, writing is limited, talent and learning shallow, if the article is not straight, hope to inform.
If this article was helpful to you, please click “like”, thanks ^_^
More exciting content, please pay attention to the individual public number.
