23 How Does Redis Eliminate Keys #
Hello, I’m your caching course teacher, Chen Bo. Welcome to Lesson 23 “Redis Eviction Policies”. In this lesson, we will mainly learn about the eviction principles, eviction methods, and 8 eviction policies of Redis.
Eviction Principles #
Let’s start by learning about the eviction principles of Redis.
In a running system, memory is always expensive and limited. When the total amount of data exceeds the available memory of Redis, in order to maximize access performance, Redis can only store the latest and hottest data.
When a key expires or when Redis occupies more memory than the threshold, Redis will eliminate the key, deleting expired or inactive keys and reclaiming the memory for new keys. The memory threshold of Redis is set through maxmemory, and the eviction policy after exceeding the memory threshold is set through maxmemory-policy. The specific eviction policies will be discussed in detail later. Redis eliminates keys in two scenarios: first, during the periodic execution of serverCron, it checks and eliminates keys; second, during command execution, it checks and eliminates keys.
In the first scenario, when Redis executes serverCron periodically, it checks the DB and cleans up expired keys. The cleanup process is as follows: First, it polls each DB and checks its expire dict, which is the dictionary with keys and their expiration time. From all the keys with expiration time, it randomly selects 20 sample keys and checks whether these keys have expired. If any of the 20 sample keys has expired, it gets deleted. If more than 5 out of the 20 samples have expired, meaning the expiration ratio is greater than 25%, it continues to randomly select another 20 sample keys from the DB’s expire dict for expiration cleanup. This process continues until the number of expired keys in the selected 20 sample keys is less than or equal to 5. Once this condition is met, the current DB is cleaned up, and then the next DB is polled.
During the execution of serverCron, if the fill rate of the expire dict in a certain DB is less than 1%, it stops sampling and checking that DB because the efficiency is too low. If the DB has too many expired keys and the cleanup process continues indefinitely, it would consume a large amount of the main thread’s time. Therefore, Redis also sets an expiration time. This expiration time is calculated based on the frequency of serverCron’s execution. In versions 5.0 and earlier, a slow loop eviction strategy is used by default, with a default expiration time of 25ms. If the cleanup takes longer than 25ms, it will stop. In version 6.0 (an unstable version), a fast loop strategy is used, with an expiration time of 1ms.
In the second scenario, when Redis executes a command request, it checks whether the current memory consumption exceeds the value of maxmemory. If it does, according to the eviction policy set, it will delete and evict keys.
Eviction Methods #
There are two eviction methods for keys in Redis: synchronous deletion and asynchronous deletion. During the periodic cleanup of expired keys by serverCron, if the delayed expiration configuration lazyfree-lazy-expire is set, it checks whether the value corresponding to the key is a compound type with multiple elements, such as a list, set, sorted set, or hash, and whether the number of elements in the value is greater than 64. If it is, it removes the key from the expire dict and main dict of the DB, and stores the value in the BIO task queue for asynchronous deletion by the BIO delayed delete thread. Otherwise, it directly deletes the key from the expire dict and the main dict of the DB, and reclaims the space occupied by the key and value. During command execution, if lazyfree-lazy-eviction is set, a similar detection method is used when evicting keys. For the four compound types with more than 64 elements, an asynchronous deletion is performed using the BIO thread. Otherwise, a synchronous deletion is used.
Eviction Policies #
Redis provides 8 eviction policies to manage keys and introduces an eviction pool based on samples to improve the accuracy of eviction and ensure that the least active keys are evicted while maintaining maximum performance. The eviction pool mainly works with LRU, LFU, and TTL memory management policies in the expire dict. The process is as follows: when Redis memory usage exceeds the threshold, N keys (default is 5) are randomly selected from either the main dict or the expire dict with expiration time. The idle value of each key is calculated and the keys are inserted into the evictionPool in ascending order of idle value. Then the key with the maximum idle value is selected for eviction.
When selecting an eviction policy, you can set the maximum memory using Redis’s maxmemory configuration and set the handling policy after exceeding the maximum memory using maxmemory_policy. If maxmemory is set to 0, it means there is no memory limitation and data can be continuously stored, which is suitable for storing small amounts of data as a storage solution. If the data volume is large, it is necessary to estimate the capacity of hot data and set an appropriate value to use Redis as a cache instead of a storage.
Redis provides 8 maxmemory_policy eviction policies to deal with the situation when memory exceeds the threshold.
The first eviction policy is noeviction, which is the default policy of Redis. When memory exceeds the threshold, Redis does not perform any cleanup and returns an error for all write operations, but handles read requests normally. The noeviction policy is suitable for business scenarios with a small amount of data, where critical data is stored in Redis and Redis is used as a database.
The second eviction policy is volatile-lru, which uses the Least Recently Used (LRU) algorithm to evict keys with expiration time. With this policy, Redis randomly selects N keys from the expire dict of redisDb, calculates the key’s idle time, inserts them into the evictionPool, and finally selects the key with the longest idle time for eviction. This policy is suitable for business scenarios where keys with expiration time need to be evicted and there is a distinction between hot and cold keys, so that the keys that have not been accessed for a long time can be evicted.
The third policy is volatile-lfu, which uses the Least Frequently Used (LFU) algorithm to evict keys with expiration time. With this policy, Redis randomly selects N keys from the expire dict of redisDb, calculates the relative usage frequency of keys based on their LRU values, and selects the key with the smallest usage frequency. To calculate the idle value for the LFU algorithm, Redis subtracts the relative usage frequency from 255, ensuring that the key with the maximum idle value has the smallest usage frequency. After calculating the idle values for N keys, they are inserted into the evictionPool, and finally the key with the maximum idle value, i.e., the key with the smallest usage frequency, is evicted. This policy is suitable for most business scenarios where keys have expiration time and there is a distinction between hot and cold keys.
The fourth policy is volatile-ttl, which selects the key with the earliest expiration time from keys with expiration time for eviction. With this policy, Redis also randomly selects N keys from the expire dict of redisDb, and calculates the idle value by subtracting the expiration time of the key from the maximum unsigned long value. After calculating the idle values for N keys, they are inserted into the evictionPool, and finally the key with the maximum idle value, i.e., the key that will expire soonest, is evicted. This policy is suitable for business scenarios where keys with expiration time need to be evicted and there is a distinction between hot and cold keys based on time.
The fifth policy is volatile-random, which randomly selects a key from keys with expiration time for eviction. With this policy, Redis selects a random key from the expire dict of redisDb and evicts it. If the keys that need to be evicted have expiration time and there is no obvious hotspot, and they are mainly accessed randomly, then this policy is suitable.
The sixth policy is allkey-lru, which uses the Least Recently Used (LRU) algorithm to evict all keys, not just keys with expiration time. This policy is similar to volatile-lru, where Redis selects the key with the longest time since last access from randomly chosen keys. The difference is that volatile-lru selects keys from the expire dict of redisDb, while allkey-lru selects keys from all keys. This policy is suitable for business scenarios where all keys need to be evicted and there is a distinction between hot and cold data.
The seventh policy is allkeys-lfu, which also uses the Least Frequently Used (LFU) algorithm to evict all keys. This policy is similar to volatile-lfu, where the key with the minimum access frequency is evicted from randomly chosen keys. The difference is that volatile-lfu selects keys from the expire dict, while allkeys-lfu selects keys from the main dict. This policy is suitable for scenarios where all keys need to be evicted, there is a distinction between hot and cold data, and the more frequently accessed data has a higher access frequency.
The last policy is allkeys-random, which randomly selects keys from all keys for eviction. It also selects a random key from the main dict and then deletes it. If all keys need to be evicted, and there is no obvious hotspot for key access, then this policy can be used.