Shulou(Shulou.com)05/31 Report--

In this article Xiaobian for you to introduce in detail "Redis's LRU cache elimination algorithm how to achieve", the content is detailed, the steps are clear, the details are handled properly, I hope this "Redis's LRU cache elimination algorithm how to achieve" article can help you solve doubts, following the editor's ideas slowly in depth, together to learn new knowledge.

1 the implementation principle of standard LRU

LRU, recently least used (Least Recently Used,LRU), classic caching algorithm.

LRU uses a linked list to maintain the access of each data in the cache, and adjusts the position of the data in the linked list according to the real-time access of the data, and then indicates whether the data has been recently accessed or has not been accessed for some time through the location of the data in the linked list.

LRU sets the head and tail of the chain to MRU and LRU, respectively:

MRU,Most Recently Used abbreviation, indicating that the data has just been accessed

LRU side, where data is the least recently accessed data

LRU can be divided into the following situations:

Case1: when new data is inserted, LRU inserts the data into the head of the chain and moves the data from the head of the original list and the data after it to the tail by one bit.

Case2: when data has just been accessed, LRU moves the data from its current position in the linked list to the head of the link. Move other data from the head of the linked list to its current position by one bit to the tail.

Case3: when the length of the linked list cannot hold more data, and new data is inserted, LRU removes the data at the end of the linked list, which is equivalent to eliminating the data from the cache.

Case2 diagram: the length of the linked list is 5, and the data stored from the head to the tail of the linked list are 5, 3, 3, 9, 10, and 8, respectively. Assuming that data 9 is accessed once, 9 is moved to the head of the linked list, and data 5 and 33 are moved one bit toward the end of the linked list.

Therefore, if you strictly follow the LRU implementation, it is assumed that Redis saves a lot of data and needs to be implemented in the code:

Maintain a linked list of all the data that can be held when using maximum memory for Redis

Additional memory space is required to hold the linked list

Whenever new data is inserted or existing data is accessed again, multiple linked list operations need to be performed

In the process of accessing data, Redis is affected by the cost of data movement and linked list operations.

This eventually leads to a decline in Redis access performance.

Therefore, whether it is to save memory or to maintain high performance of Redis, Redis is not implemented strictly according to the basic principles of LRU, but provides an approximate LRU algorithm implementation.

Implementation of approximate LRU algorithm for 2 Redis

How does Redis's memory obsolescence mechanism enable the approximate LRU algorithm? The following configuration parameters in redis.conf:

Maxmemory, which sets the maximum amount of memory that can be used by Redis server. Once the actual amount of memory used by server exceeds this threshold, server will perform memory elimination according to the maxmemory-policy configuration policy.

Maxmemory-policy, set Redis server memory elimination strategy, including approximate LRU, LFU, elimination by TTL value, random phase-out, etc.

Therefore, once the maxmemory option is set and maxmemory-policy is configured as allkeys-lru or volatile-lru, approximate LRU is enabled. Both allkeys-lru and volatile-lru use approximate LRU phase-out data. The difference is:

Allkeys-lru is to filter the data that will be eliminated among all KV pairs.

Volatile-lru filters data that will be eliminated in KV pairs with TTL set.

How does Redis implement the approximate LRU algorithm?

Calculation of global LRU clock value

How to calculate the global LRU clock value to judge the timeliness of data access

Initialization and update of key value to LRU clock value

Which functions initialize and update the LRU clock value corresponding to each key-value pair

The actual execution of approximate LRU algorithm

How to implement the approximate LRU algorithm, that is, when to trigger data elimination, and the implementation of the actual elimination mechanism

2.1 calculation of global LRU clock value

The approximate LRU algorithm still needs to distinguish the access timeliness of different data, that is, Redis needs to know the last access time of the data. Therefore, there is a LRU clock: the timestamp of each access to the data is recorded.

Redis uses a redisObject structure to hold a pointer to V for the V in each KV pair. In addition to recording the pointer to the value, redisObject also uses 24 bits to store LRU clock information, corresponding to lru member variables. In this way, each KV pair records its last accessed timestamp in the lru variable.

The redisObject definition contains the definition of the lru member variable:

How is the LRU clock value of each KV pair calculated? Redis Server uses an instance-level global LRU clock, and the LRU time of each KV pair is set according to the global LRU clock.

The global LRU clock is saved in the member variable lruclock of the Redis global variable server

When Redis Server is started and initServerConfig is called to initialize the parameters, getLRUClock is called to set the value of lruclock:

Therefore, it should be noted that * * if the interval between two accesses of a data is less than 1s, then the timestamp of the two accesses is the same! * * because the LRU clock accuracy is 1s, it cannot distinguish between different timestamps with an interval of less than 1 second!

The getLRUClock function divides the UNIX timestamp obtained by LRU_CLOCK_RESOLUTION to get the UNIX timestamp calculated in terms of LRU clock precision, that is, the current LRU clock value.

GetLRUClock calculates the LRU clock value and the macro definition LRU_CLOCK_MAX (the maximum value that a LRU clock can represent).

So by default, the global LRU clock value is the UNIX timestamp calculated with a precision of 1s, and is initialized in initServerConfig.

How is the global LRU clock value updated while Redis Server is running? It is related to the serverCron corresponding to the time events that Redis Server runs periodically in the event-driven framework.

ServerCron, as a callback function of time events, is executed periodically. Its frequency value is determined by the hz configuration item of redis.conf. The default value is 10, that is, the serverCron function runs once per 100ms (1s/10 = 100ms). In serverCron, the global LRU clock value will be updated periodically by calling getLRUClock according to the execution frequency of this function:

In this way, each KV pair can obtain the latest access timestamp from the global LRU clock.

For each KV pair, in which functions does its corresponding redisObject.lru be initialized and updated?

2.2 initialization and update of key value to LRU clock value

For a KV pair, the LRU clock value is initially initialized when the KV pair is created. This initialization operation is called in the createObject function, which is called when Redis wants to create a KV pair.

In addition to allocating memory space to redisObject, createObject initializes the setting of redisObject.lru based on the maxmemory_policy configuration.

If maxmemory_policy=LFU, the value of the lru variable is initialized to the calculated value of the LFU algorithm

Maxmemory_policy ≠ LFU, then createObject calls LRU_CLOCK to set the LRU value, that is, the LRU clock value corresponding to the KV pair.

LRU_CLOCK returns the current global LRU clock value. Because once a KV pair is created, it is equivalent to having a visit, and its corresponding LRU clock value indicates its access timestamp:

When will the LRU clock value of that KV pair be updated again?

As long as a KV pair is accessed, its LRU clock value will be updated! When a KV pair is accessed, the access operation will eventually call lookupKey.

LookupKey looks for the KV pair to access from the global hash table. If the KV pair exists, lookupKey updates the LRU clock value of the key-value pair, that is, its access timestamp, according to the configuration value of the maxmemory_policy.

When maxmemory_policy is not configured as a LFU policy, the lookupKey function calls the LRU_CLOCK function to get the current global LRU clock value and assign it to the lru variable in the redisObject structure of the key-value pair

In this way, once each KV pair is accessed, the latest access timestamp can be obtained. But you may wonder: how did these access timestamps end up being used to approximate LRU algorithms for data elimination?

2.3 actual implementation of approximate LRU algorithm

Redis implements approximate LRU to reduce the overhead of memory resources and operation time.

2.3.1 when will the algorithm execution be triggered?

The main logic of approximate LRU is performEvictions.

PerformEvictions is called by evictionTimeProc, and the evictionTimeProc function is called by processCommand.

When processCommand,Redis processes each command, it calls:

Then, isSafeToPerformEvictions will again determine whether to continue with performEvictions based on the following conditions:

Once performEvictions is called and maxmemory-policy is set to allkeys-lru or volatile-lru, the approximate LRU is triggered to execute.

2.3.2 approximate the specific implementation process of LRU

Execution can be divided into the following steps:

2.3.2.1 determine current memory usage

Call getMaxmemoryState to evaluate the current memory usage and determine whether the current Redis Server memory usage exceeds the maxmemory configuration value.

If the maxmemory is not exceeded, the return ClearOKPerformance performance Evictions will also be returned directly.

When getMaxmemoryState evaluates the current memory usage, if it finds that the used memory exceeds maxmemory, it calculates the amount of memory that needs to be freed. The size of this free memory = the amount of memory used-maxmemory.

However, the amount of memory used does not include the size of the replication buffer for master-slave replication, which is calculated by getMaxmemoryState by calling freeMemoryGetNotCountedMemory.

If the current amount of memory used by Server exceeds the upper limit of maxmemory, performEvictions will perform a while cycle to eliminate data and release memory.

To eliminate the data, Redis defines the array EvictionPoolLRU, stores the candidate KV pairs to be eliminated, the element type is evictionPoolEntry structure, and stores the idle time idle, corresponding K and other information of the KV pairs to be eliminated:

In this way, when Redis Server performs initSever initialization, it will call evictionPoolAlloc to allocate memory space for the EvictionPoolLRU array, the size of which is determined by EVPOOL_SIZE, and 16 candidate KV pairs can be saved by default.

PerformEvictions updates the collection of candidate KV pairs to be eliminated, that is, the EvictionPoolLRU array, in the process of looping through the elimination data.

2.3.2.2 Update the collection of candidate KV pairs to be eliminated

PerformEvictions calls evictionPoolPopulate, which first calls dictGetSomeKeys to randomly get a certain number of Ks from the hash table to be sampled:

The hash table sampled by dictGetSomeKeys, determined by the maxmemory_policy configuration item:

If maxmemory_policy=allkeys_lru, the hash table to be sampled is the global hash table of Redis Server, that is, sampling in all KV pairs

Otherwise, the hash table to be sampled is the hash table that holds the K with TTL set.

The number of Ks sampled by dictGetSomeKeys is determined by the configuration item maxmemory-samples. Default is 5:

Therefore, dictGetSomeKeys returns a collection of sampled KV pairs. EvictionPoolPopulate executes a loop based on the number of KV pairs count actually sampled: call estimateObjectIdleTime to calculate the idle time of each KV pair in the sampling set:

Next, evictionPoolPopulate traverses the collection of candidate KV pairs to be eliminated, the EvictionPoolLRU array, and tries to insert each sampled KV pair into the EvictionPoolLRU array, depending on one of the following conditions:

Can find an empty space in the array that has not yet been inserted into the KV pair

The idle time of a KV pair can be found in the array < the idle time of the sampled KV pair

Once established, evictionPoolPopulate can insert sampled KV pairs into the EvictionPoolLRU array. After all the sampled key-value pairs have been processed, the evictionPoolPopulate function completes the update of the set of eliminated candidate key-value pairs.

Next, performEvictions begins to select the KV pair that will eventually be eliminated.

2.3.2.3 Select the eliminated KV pair and delete

Because evictionPoolPopulate has updated the EvictionPoolLRU array, and the K in the array is sorted according to the idle time from small to large. So, performEvictions iterates through the EvictionPoolLRU array once, starting with the last K of the array, and if the selected K is not empty, it will be used as the final eliminated K.

The process executes logic:

Once the obsolete KPerformEvictions is selected, synchronous deletion or asynchronous deletion will be performed according to the lazy deletion configuration of Redis server:

At this point, performEvictions eliminated a K. If there is not enough memory space released at this time, that is, if the space to be released is not reached, performEvictions will also repeat the process of updating the collection of candidate KV pairs to be eliminated and selecting the final elimination K until the size requirement of the space to be released is met.

PerformEvictions process:

The approximate LRU algorithm does not use a time-consuming and space-consuming linked list, but uses a fixed size of the data set to be eliminated, each time randomly select some K to join the data set to be eliminated.

Finally, delete the K with the longest idle time according to the length of idle time of K in the collection to be eliminated.

After reading this, the article "how to implement Redis's LRU cache elimination algorithm" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself to understand it. If you want to know more about related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.