When you use Redis cache, you set an expiration time for the cached data to improve the cache hit ratio, and delete the cached data according to the expiration policy.
There are two types of cache expiration deletion policies for Redis: lazy deletion and periodic deletion.
In Redis, the key with the expiration time set will be stored in the expiration dictionary of Redis. When you perform a read or write operation on the key, it will first check whether the key exists in the expired dictionary, and if it exists, the expiration time of the key will be obtained and compared with the current time of the system
If the expiration time is greater than the current time, the key has not expired.
If the expiration time is less than or equal to the current time, the key is determined to have expired.
Out-of-date dictionaries
Expired dictionaries are stored in the RedisDB structure and are as follows:
typedef struct redisdb redisdb;Where:
The key of the expired dictionary points to a key in the Redis database.
The value of an expired dictionary is an integer of type long long, which is used to store the expiration time (timestamp, unit: milliseconds) corresponding to the key.
As shown in Fig
Lazy deletion processing logic, as shown in the image
Procedure: Perform read and write operations on the key to determine whether the key exists in an expired dictionary
If it does not exist, the read and write operations are performed normally.
If so, compare the key expiration time with the current time of the system to determine whether the key has expired
If the expiration time of the key is less than or equal to the current time (expired), the key is deleted.
If the key expires longer than the current time (not expired), the system performs read/write operations.
Periodically remove the processing logic, as shown in the image
Procedure: Redis randomly selects 20 keys from the expired dictionary at a frequency of 100 ms to check whether there are expired keys
If the key expires less than or equal to the current time, the key has expired.
If the key expiration time is greater than the current time, the key has not expired.
If there are expired keys, determine whether the number of expired keys exceeds 25% of the extracted number or whether the periodic deletion period exceeds 25 ms
If the execution period exceeds 25% or the execution duration exceeds 25 ms, 20 keys are randomly selected from the expired dictionary for checking, and the cycle continues until the number of expired keys does not exceed 25% or the execution duration does not exceed 25 ms.
If the execution duration does not exceed 25 ms, the expired key is deleted.
If no expired key exists, wait for 100 ms and continue to randomly select 20 keys from the expired dictionary for checking.
Note: Redis is regularly deleted on the main thread, and if a large number of keys expire at the same time, the read and write efficiency of Redis will be affected.
redis2.After version 8, it is possible to redis. by modifying the configuration fileThe hz parameter (the default value is 10, that is, 10 times per second) in conf to adjust the execution frequency of scheduled tasks that are deleted on a regular basis.
Parameter Hz: The value range of Hz is 1 500, the default value is 10, it is not recommended to exceed 100, increasing the value of Hz will occupy more CPU resources, only when the request delay is very low, you can consider increasing the value of Hz to 100.
The Redis expiration deletion policy adopts lazy deletion + periodic deletion as a trade-off between CPU resources and memory consumption
If lazy deletion is used, keys that have not been accessed will be stored in memory, resulting in a waste of memory resources.
If you only use periodic deletion, when a large number of keys expire at the same time, a large amount of CPU resources will be occupied, affecting the performance of read and write operations and system throughput.
The expiration deletion policy is an imprecise deletion policy, for those keys that have not been accessed for a long time and have been deleted regularly for many times, they will always be stored in memory, which may cause the memory of Redis to be exhausted.
In the configuration file redisconf, the maximum memory is set by the parameter maxmemory (the default is unlimited, and the value of this parameter is usually set to 3 4 of the physical memory).
When the Redis memory exceeds the maximum memory set by the maxmemory parameter, the memory elimination policy is triggered. The memory elimination policy is set by using the maxmemory-policy parameter, which is as follows:
volatile-lru: Keys with an expiration time set are eliminated based on the LRU algorithm (lru: least recently used, indicating that they have not been used for the longest time).
allkeys-lru: eliminates all keys (including keys with and without expiration time) based on the LRU algorithm (a common policy used in the environment).
volatile-lfu: Keys with an expiration time are eliminated based on the LFU algorithm (lfu: least frequently used).
allkeys-LFU: All keys are eliminated based on the LFU algorithm.
volatile-random: Keys with an expiration time set are eliminated based on the random elimination method.
allkeys-random: All keys are eliminated based on the random elimination method.
volatile-ttl: discards the key that is about to expire (minor ttl) for the key that has an expiration time set.
noeviction: does not eliminate any data, and returns an error when writing data to Redis when the memory space used exceeds the value set by the maxmemory parameter (default policy, generally not used).
It can be seen that except for the special noeviction and volatile-TTL strategies, the other six strategies can be divided into two categories:
A strategy that starts with volatile- is to weed out keys with an expiration time set according to a specific algorithm.
A strategy that starts with allkeys- is to weed out all keys based on a specific algorithm.
redis.Parameters related to the memory elimination policy in conf:
maxmemory: the upper limit of memory usage, the default value is 0, which indicates that the upper limit of memory usage is not limited.
maxmemory-policy: the memory elimination policy, the default policy is noeviction.
maxmemory-samples: the number of random samples, the default value is 5.
Memory Retirement Policy Selection:
If the data is idempotent (that is, some data is accessed more frequently and the rest are accessed less frequently), we recommend that you select the allkeys-lru or allkeys-lfu policies.
If the data is evenly distributed (i.e., all data have roughly equal access probabilities), we recommend that you select the allkeys-random policy.
If you need to set different TTLS to determine the order of data expiration, we recommend that you select the Volatile-TTL policy.
If some data needs to be stored for a long time and some data can be cleared, we recommend that you select the volatile-lru or volatile-random policies.
Note: Since setting the expiration time consumes additional memory, you can select the allkeys-lru policy to prevent Redis from consuming additional memory due to determining the expiration time of the key.
To view the memory retirement policy used by Redis, see config get maxmemory-policy.
Modify the memory elimination policy
config set maxmemory-policy Policy: takes effect immediately, restarts and reverts to default.
Modify the configuration file RedisThe parameter maxmemory-policy in conf Policy: The reboot takes effect.
redis - approximate LRU calculation execution process:
Randomly select n keys (n is set by the parameter maxmemory-samples, the default value is 5) to find the key that has not been accessed for the longest time (the time is determined by comparing the LRU attribute in RedisObject with the current time of the system) and delete the key.
If the system memory exceeds the memory usage limit again and still exceeds the memory usage limit, the preceding process continues.
Defects in the LRU algorithm
The LRU algorithm only focuses on the access time or order of the data, ignoring the value of the number of visits, and may eliminate hot data in the process of eliminating data.
As shown in Fig
In the figure, the timeline is from left to right, and data a b c is accessed several times in the same period of time. Data C is the most recently accessed data, and the heat of the data arranged according to the LRU algorithm is C>B>A, and the real heat of the data is B>A>C.
Why doesn't Redis just use the LRU algorithm?
If the LRU algorithm (based on hashmap + doubly linked list: an LRU algorithm will be shared later), additional memory needs to be consumed to store the prev and next pointers in the doubly linked list node, thereby reducing the storage space of REDIS.
Why is the default value of the maxmemory-samples parameter 5?
When the number of extractions is 5, the execution efficiency is very close to the standard LRU algorithm, although the number of extractions can be closer to the LRU algorithm when the number of extractions is set to 5, but it will consume more CPU resources, so the default value of the number of extractions is the result of the trade-off between the execution efficiency of the LRU algorithm and the consumption of CPU resources.
LFU (full name least frequently used) stands for the least frequently used recently, which is related to the number of key visits, and the core idea is that if a data is accessed frequently in the near future, the probability that it will be revisited in the future will be high, and the data accessed less frequently will have a high probability that it will not be used again in the future.
Note: The frequency of access to the LFU algorithm cannot be equated with the number of visits. As shown in Fig
In the figure, data A is accessed 5 times, and data B and C are accessed 4 times each
If the data popularity value is determined by the number of visits, the value is a>b=c.
If the accesses closer to the current time are more valuable considering timeliness, then the data popularity value is: c>b>a.
Therefore, the LFU algorithm generally has a time decay function to participate in the calculation of the heat value, taking into account the influence of access time.
LFU algorithm implementation
The implementation of the LFU algorithm does not use additional data structures, and reuses the LRU fields of the RedisObject data structure.
redisobject data structure:
typedef struct redisobject robj;Among them, there are differences in the way the LRU field is used in the LRU algorithm and the LFU algorithm
In the LRU algorithm, the LRU field is used to record the access timestamp of the key, so the key that has not been accessed for a long time can be compared with the current time based on the value recorded in the LRU field.
In the LFU algorithm, the LRU field is stored in two segments, with the highest 16-bit storage LDT (Last Decrement Time) and the lowest 8-bit storage Logistic Counter (LOGC).
The LRU field in the LFU algorithm, as shown in the figure:
ldt: the access timestamp of the key.
logc: used to record the access frequency of the key (i.e., the popularity value), the smaller the logc value, the lower the access frequency, the more likely it is to be eliminated, and the initial value of logc of the new key is 5 (the purpose is to prevent the new key from being eliminated immediately, and the number of visits to the new key is likely to be smaller than that of the old key that is not accessed).
LFU access frequency (logistic counter) algorithm implementation:
#define lfu_init_val 5/* logarithmically increment a counter. the greater is the current counter value * the less likely is that it gets really implemented. saturate it at 255. */uint8_t lfulogincr(uint8_t counter)Where:
If the counter is less than or equal to LFU init val, once the data is accessed and hit, the probability of the counter is close to 100% and increases by 1.
If the counter is greater than lfu init val, you need to calculate the difference between the two first, and then participate in the calculation of the increasing probability as part of the denominator.
As the counter value increases, the increasing probability gradually decays, and it is possible that several visits will not increase its value by 1.
When the counter value reaches 255, the value increment process is no longer performed.
In order to adapt to the characteristics of various business data, Redis introduces two tunable parameters in the implementation of the LFU algorithm:
lfu-decay-time: the time decay factor, measured in minutes, the default value is 1, the higher the value of this parameter, the slower the decay.
lfu-log-factor: increments the attenuation factor, the default value is 10, the higher the value of this parameter, the lower the increment probability.
Read Recommended] More exciting content, such as:
Redis series.
Data Structures & Algorithms.
NACOS series.
MySQL series.
JVM series.
Kafka series.
Concurrent programming series.
Please move to the personal homepage of [Nanqiu] for reference. The content is constantly being updated.
About the author] An old babe who loves technology and life, focuses on the field of J**A, and pays attention to [Nanqiu classmates] to take you to learn and grow together