23 Memory Reclamation Mechanism and Algorithms

23 Memory Reclamation Mechanism and Algorithms #

Before we begin this article, we need to understand that in Redis, expiration policy and memory eviction policy are two completely different concepts, but many people confuse them.

Firstly, Redis expiration policy refers to the strategy Redis uses to delete expired key-value pairs. Redis memory eviction mechanism refers to the strategy Redis adopts to delete key-value pairs that meet certain conditions when the running memory of Redis exceeds the maximum memory set.

We have discussed the expiration policy in detail in the previous articles. In this article, we will focus on Redis memory eviction mechanism.

Redis Maximum Running Memory #

The memory eviction mechanism is triggered only when the running memory of Redis reaches a certain threshold, which is the maximum running memory set by us. This value can be found in the Redis configuration file, with the configuration item being maxmemory.

The execution process of memory eviction is shown in the following diagram:

img

Querying the Maximum Running Memory #

We can use the config get maxmemory command to view the set maximum running memory. The command is as follows:

127.0.0.1:6379> config get maxmemory
1) "maxmemory"
2) "0"

We find that this value is actually 0, which is the default value for a 64-bit operating system. When maxmemory is 0, it means that there is no memory size restriction.

Tip: The default maximum memory value for a 32-bit operating system is 3GB.

Memory Eviction Policies #

Viewing Redis Memory Eviction Policy #

We can use the config get maxmemory-policy command to view the current memory eviction policy of Redis. The command is as follows:

127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"

It can be seen that Redis uses the noeviction type of memory eviction mechanism, which means that when the running memory exceeds the maximum memory setting, no data will be evicted, but new operations will return an error.

Classification of Memory Eviction Policies #

In earlier versions of Redis, there are 6 types of eviction policies:

  1. noeviction: No data is evicted. When there is not enough memory, new operations will return an error. This is the default memory eviction policy of Redis.
  2. allkeys-lru: Evict the least recently used key-value pair in the entire key-value store.
  3. allkeys-random: Evict any key-value pair randomly.
  4. volatile-lru: Evict the least recently used key-value pair among all key-value pairs with expiration time set.
  5. volatile-random: Evict any key-value pair with expiration time set randomly.
  6. volatile-ttl: Evict the key-value pair that will expire sooner.

In Redis version 4.0, two more eviction policies are added:

  1. volatile-lfu: Evict the least frequently used key-value pair among all key-value pairs with expiration time set.
  2. allkeys-lfu: Evict the least frequently used key-value pair in the entire key-value store. 其中 allkeys-xxx represents eliminating data from all key-value pairs, while volatile-xxx represents eliminating data from key-value pairs with expiration keys.

Updating Redis Memory Eviction Policies #

There are two methods to set memory eviction policies, each with its own advantages and disadvantages that need to be weighed by the user.

  • Method 1: Set the policy with the command “config set maxmemory-policy ”. The advantage is that it takes effect immediately without requiring a Redis service restart, but the disadvantage is that the setting will be lost after a Redis restart.
  • Method 2: Modify the Redis configuration file and set “maxmemory-policy ”. The advantage is that the configuration will not be lost after a Redis service restart, but the disadvantage is that a Redis service restart is required for the setting to take effect.

Memory Eviction Algorithms #

From the classification of memory eviction policies, we can see that besides random deletion and no deletion, there are mainly two eviction algorithms: LRU algorithm and LFU algorithm.

LRU Algorithm #

LRU, which stands for Least Recently Used, is a commonly used page replacement algorithm that evicts the least recently used page.

1. LRU Algorithm Implementation

The LRU algorithm requires a linked list structure, where the elements in the list are arranged in the order of their operations, and the most recently operated key is moved to the head of the list. When memory eviction is needed, simply delete the element at the tail of the list.

2. LRU Approximation Algorithm

Redis uses an approximate LRU algorithm to better save memory. This is achieved by adding an additional field to the existing data structure to record the last accessed time of this key-value pair. During memory eviction in Redis, it randomly samples 5 values (this value is configurable) and evicts the least recently used one.

3. Shortcomings of the LRU Algorithm

The LRU algorithm has a shortcoming. For example, if a key-value pair that has not been used for a long time is accessed once recently, it will not be evicted, even if it is the least frequently used cache. Therefore, the LFU algorithm was introduced in Redis 4.0. Let’s take a look at it.

LFU Algorithm #

LFU, which stands for Least Frequently Used, evicts data based on the total number of accesses. The core idea of LFU is “if data has been accessed many times in the past, it will be accessed with a higher frequency in the future.”

LFU solves the problem of data not being evicted after being accessed only once, and it is more reasonable compared to the LRU algorithm.

In Redis, the LFU information is recorded in the object header, as shown in the source code below:

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

In Redis, LFU storage consists of two parts: 16 bits of ldt (last decrement time) and 8 bits of logc (logistic counter).

  1. logc stores the access frequency, where the minimum value that can be represented by 8 bits is 255. A smaller value indicates a lower frequency of use and is easier to evict.
  2. ldt stores the last update time of logc.

Summary #

Through this article, we have learned that Redis memory eviction policies are completely different from expiration policies. Memory eviction policies address the problem of Redis exceeding its memory capacity. They determine whether to evict data by comparing it with maxmemory and use the maxmemory-policy parameter to determine which eviction strategy to use. Starting from Redis 4.0, there are 8 eviction strategies available. The default strategy is noeviction, which means no key-value pairs will be evicted when memory usage exceeds the limit, but new operations will result in an error.