Redis memory elimination strategy

The common expired cleanup strategies are as follows:

  • Timed deletion: When setting the key expiration time, create a timer, and the timer will temporarily delete the key when the key expiration time comes.
  • Lazy deletion: Regardless of the expiration time of the key, only check whether the key expires every time the key is operated. Delete if expired, otherwise return result
  • Periodic deletion: Every once in a while, the program checks the database and deletes the expired keys. How many keys to delete and how much data to check are determined by the algorithm

Redis uses lazy deletion and periodic deletion, in which periodic deletion does not scan all keys every time. Assuming that one hundred thousand keys with expiration time are saved now, if you traverse all of them every time you clean up, the CPU consumption is too large, and it is very likely to become a Redis performance bottleneck.

Redis puts each key with an expiration time in a separate dictionary, and scans 10 times per second by default. The scan adopts a greedy idea:

  1. Randomly draw 20 keys from an expired dictionary
  2. Delete the expired keys among these 20 keys
  3. If the percentage of deleted keys exceeds 1/4, repeat the whole cycle

It can be analyzed from this that the key that sets the expiration time is not necessarily deleted after expiration. In order to prevent cleaning up even if the expiration time is set, the memory is still insufficient. Redis introduces a memory elimination strategy. When the redis memory space has been used up, corresponding actions are executed according to specific strategies. There are eight common memory elimination strategies as follows:

  1. noeviction: the default strategy, report an error, do not eliminate any Key
  2. allkeys-lru: Among all keys, some keys are eliminated through the LRU algorithm
  3. allkeys-lfu: Among all keys, some keys are eliminated through the LFU algorithm
  4. allkeys-random: Randomly eliminate some keys among all keys
  5. Volatile-lru: Among the keys with expiration time set, some keys are eliminated through the LRU algorithm
  6. Volatile-lfu: Among the keys with expiration time set, some keys are eliminated through the LFU algorithm
  7. Volatile-random: Among the keys with expiration time set, some keys are randomly eliminated
  8. volatile-ttl: Among the keys with expiration time set, select the key with a short TTL (time to live, remaining time) to be eliminated

The LRU (Least Recently Used) algorithm can clear the longest unused data, which is generally implemented through a queue. The implementation method is as follows:

  1. For adding operation, add Node node record data at the end of the LRU team before each addition
  2. For modification operations, modify the LRU queue Node node and move it to the end of the queue before each modification
  3. For query operations, find the corresponding Node node before each query and move it to the end of the queue
  4. For the delete operation, first delete the corresponding Node node from the LRU queue

Through the above operations and maintenance of the queue, it can be ensured that the head of the queue is always the least used element, and the tail of the queue is always the most recently used element. The least used element is processed by deleting the queue head and memory.

The Redis LRU algorithm has gone through two versions, which are generally based on the clock field:

struct redisServer {
	unsigned lruclock:LRU_BITS; 
typedef struct redisObject {
	/* key对象内部时钟 */
	unsigned lru:LRU_BITS;
} robj;

The clock has only 24 bits, and the unit is second. Each time you operate or query a Key, assign the current system clock to the Key object clock field, so that you can determine how long you haven’t operated on by the difference between the object clock field and the system clock field. The larger the difference, the longer you haven’t used it. . Under normal circumstances, the system clock is used to subtract the Key object clock to determine. The smaller the value, the more recently it has been used. Since the clock field has only 24 bits, there is a case where the value of the object clock field is greater than the value of the system clock field. In this case, add addition is used. The larger the field, the more recently used it is.

Early Redis adopted a random selection and elimination method: N keys are randomly selected each time, and the ones that have not been used for the longest time are eliminated. The implementation is particularly simple, but the efficiency is low. It needs to be recalculated each time. The results of the previous round are not used, and due to the random selection, the keys that may not be used for a long time are not eliminated.

Redis 3.0 optimizes the LRU algorithm and introduces the concept of buffer pool. Each time when traversing the extracted Key, the idle time of all Keys is stored in the buffer pool. The buffer pool adopts the idea of ​​maximum heap and saves the n keys with the largest current idle time, where n represents the size of the buffer pool, by default 16. After random extraction later, you only need to put the idle time of all Keys into the buffer pool. The buffer pool maintains the 16 Key objects with the largest idle time as usual, and eliminates the top element each time.

Although the LRU algorithm can eliminate the longest unused Key, there are still problems in some scenarios: Suppose that Key1 is accessed 100 times within an hour, and Key2 is accessed only once, but Key2 is used last. At this time, key1 will be used according to the LRU algorithm. Eliminated, however, we hope that key2 will be eliminated because it has a lower rating. In this scenario, Redis 4.0 introduces the LFU (Least frequently used) strategy, which can eliminate the least frequently used objects:

The LFU algorithm divides the clock field into two parts, changing from the original 24 bits to 16 bits to represent the clock, and 8 bits to represent the access frequency. The clock range that can be represented by 16 bits is very small. In order to expand the range, minutes are used here. 8-bit means that the maximum frequency can only reach 255. Here, the frequency value is updated in a non-linear way, but through a complex formula, which contains two new parameters:

lfu-log-factor:调整频率 count 增长速率,该值越大,增长越慢
lfu-decay-time:调整频率 count 减少速率

Source code of increasing frequency when accessing Key:

uint8_t LFULogIncr (uint8_t counter) {
	// 已经达到最大值不处理
	if (counter == 255) return 255;
	// 获取随机数
	double r = (double) rand() / RAND_MAX;
	// 当前频率减去初始频率
	double baseval = counter - LFU_INIT_VAL;
	if (baseval < 0) baseval = 0;
	double p = 1.0 / (baseval * server.lfu_log_factor + 1);
	if (r < p) counter++;
	return counter;

It can be seen from the code that the larger the previous count value and the larger the lfu_log_factor value, the smaller the calculated p and the lower the probability of growth. In order to prevent the newly created Key from being eliminated too much, the default frequency value is 5, and when the current frequency value is less than 5, 1 will be added for each visit

When it is really necessary to eliminate a key, calculate the frequency according to the following source code:

unsigned long LFUDecrAndReturn(robj *o) {
	// 通过高16位获取当前 key 的时间
    unsigned long ldt = o -> lru >> 8;
    // 通过低8位获取当前 count 值
    unsigned long counter = o -> lru & 255;
    // 计算要减去的量
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
// 计算时间差
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now - ldt;
    // 已经超过一个周期,16位 64435
    return 65535 - ldt + now;

It can be seen from the code that the larger the value of lfu_decay_time, the smaller the decrease, and the specific decrease is determined by the clock. In general, the result calculated by LFU is more accurate because it introduces the concept of frequency based on the clock