In the last article, some basic LRU algorithms and optimization strategies were shared. This article will continue the theme and share the use and optimization of LRU algorithm in Redis.

Redis memory reclamation strategy

Before introducing Redis’ LRU usage, we need to take a look at Redis’ memory reclamation strategy.

As a high performance memory KV database, Redis is bound to need a mechanism to control the memory occupation of Redis and avoid memory overflow. The configuration related to the memory limit is the maxMemory parameter, which can be dynamically adjusted to dynamically limit the memory usage of Redis.

Redis memory reclamation strategy has two aspects:

  • Delete expiration key
  • Recovery strategy

Delete expiration key

Redis removes expired keys in two ways:

  1. Lazy to delete

    If a key has an expiration time, an expiration time stamp is appended to the key. When the client accesses the key, the expiration time stamp is first checked. If the key value has expired, null is returned and the key is deleted. Using lazy deletion avoids maintaining a linked list of expiration times, but there is a memory leak problem if an expired key is never accessed.

  2. Deleting a Scheduled Task

    In order to avoid memory leaks in the inert delete, Redis will launch a regular task, the default is 10 s running time, the timing task will randomly pick up some key and delete from the database which expired keys, if it is found that more than 25% of all key has expired, the repeat once the timing task, until the random scanning into a number of key, The percentage of expired key values is less than 25%.

Recovery strategy

When the memory usage of Redis exceeds the configured value, the Redis expels old data according to certain rules. Redis can configure six reclaiming policies:

  1. Noeviction: Rejects all write operations and returns Error, will not affect read operations.
  2. Allkeys-lru: performs the lru algorithm on allkeys.
  3. Volatile – LRU: Performs the LRU algorithm on all keys that have an expiration time.
  4. Allkeys-random: randomly ejects allkeys.
  5. Volatile -random: Randomly expel keys with expiration time.
  6. Volatile – TTL: expels the data that is to expire the fastest.

You can select an appropriate expulsion policy according to the data access mode of the specific application and the cache hit ratio calculated with the INFO command.

We can see that there are two expulsion strategies related to LRU, and Redis has optimized the LRU algorithm.

Approximate LRU algorithm

The principle of

Redis uses a sample-based approximate LRU algorithm instead of the normal LRU algorithm to avoid the high resource consumption of the normal LRU algorithm, while programs like Redis do not need to expel the exact longest unreachable key.

Brief description: Redis randomly samples a small number of key values, selects the key that has not been accessed for the longest time, and then weeds it out.

The maxmemory-samples parameter can be used to configure the number of keys for each sample. Generally, this value is set to 5. When this value is set to 10, it is close to the recovery result of ordinary LRU algorithms, but it also brings corresponding resource consumption. The Redis website has the following test results:

  • Light gray: data to be reclaimed
  • Dark grey: data that has not been collected
  • Green: The latest data is inserted

The top left corner is the result of a normal LRU collection, which is only inserted and accessed once, so old data is discarded in a first-come-first-served order. Since Redis3.0 added a expulsion pool, you can see that Redis3.0 is better than the 2.8 version. Moreover, it can be seen that increasing the number of samples can also improve the recovery effect.

implementation

1. The LRU clock

Redis has a global LRU clock, LRUClock, which records the LRU time since the service started and is updated every 100ms. When a client creates or accesses a key value, the LRU clock of the key value itself is updated against this global clock.

This means that each key value has an access time record.

2. Execute a reclamation policy

Before inserting data, the system checks whether there is sufficient capacity. If not, a reclamation policy is executed to expel old data. Here we specify the collection strategy associated with LRU.

3. The expulsion of pool

The structure of an Entry in an expulsion pool is shown below:

#define REDIS_EVICTION_POOL_SIZE 16
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time. */
    sds key;                    /* Key name. */
};
Copy the code

Where idle is the idle time and key is the key value, the idle time is calculated according to the ABOVE LRU clock. An expulsion pool is an array consisting of 16 entries in the order of idle entries.

When you need to insert a key into the expulsion pool, you first need to populate the expulsion pool, randomly select several key values from the database according to the configured sampling parameters, and then perform the following operations in sequence.

This key is then compared in the expulsion pool to find the key with a large idle time:

  • If no such key is found and there is no empty space in the expulsion pool, it means that the inserted key is the key with the least idle time, so it is not necessary to join the expulsion pool, so it is skipped.
  • If such a key is found and the expulsion pool is empty, the Entry is inserted directly before the existing key, and the previous Entry shifts.
  • If such a key is found and there is no space in the expulsion pool, it is inserted after the key with the least idle time is removed from the expulsion pool.

Then comes the logic to actually delete the key:

In the eviction pool, delete from the key with the longest idle time until there is enough data space.

For those of you who are interested, check out the Redis source code for the freeMemoryIfNeeded() method and the evictionPoolPopulate() method.

The source address

conclusion

This paper introduces the memory reclamation strategy of Redis and the principle and implementation of Redis approximate LRU algorithm. From the optimization of THE LRU algorithm by Redis, we can find that a good design is not about how accurate it should be. Sometimes we can balance accuracy and performance to meet the function we really want to achieve.