Spring breeze to ah who, butterflies suddenly full of grass

preface

Redis is most commonly used for caching, and one of the reasons why Redis is so fast is that it stores data at the nanosecond speed of memory, which greatly improves the performance of application services. (From the user’s point of view, this thing is fast.)

However, every technology has its limitations. For example, memory space in a computer is much smaller than disk space, and memory is more expensive than disk space. So if we put all the data in memory, obviously it is a high cost, very low price thing.

So it’s more about letting Redis store hot data, and statistically speaking, in most business scenarios, according to the 80-20 rule, 20% of data contributes to close to or more than 80% of visits and frequency (there are always some exceptions, of course).

However, there is only so much memory space, and with the increasing amount of business cache data, it is inevitable that the limited memory space will be accidentally filled up.

How does Redis solve the problem of full cache?

Let’s start with Java. If you use Java, you know that Java runs on the JVM, and one of the great things about the JVM is that you don’t have to worry about memory collection as much as you do C or C++ students. Redis also has its own memory reclamation mechanism, but it is “simple” compared to the JVM, because the Redis memory reclamation mechanism has two main strategies.

Redis memory reclamation mechanism policy

Redis deletes an expired key policy

Lazy delete:

As the name implies, lazy delete does not actively do anything. Instead, when a client reads a key with a timeout set, it will delete it if it has exceeded the expiration time. However, the obvious problem is that when expired keys are not accessed and deleted in time, the memory will not be freed in time.

Periodic deletion:

Timed deletion actually starts a timed task in Redis, and retrieves keys by default timed number of runs per second, key expiration rate and speed mode.

In addition to deleting expired key policy is certainly not enough, so we further filter data elimination strategy through algorithm.

Redis elimination strategy

But no matter the previous delete expired key policy, or the purpose of the elimination policy itself is to prevent memory overflow. Redis elimination strategy provides 8 elimination strategies. Redis4.0 implements 6 elimination strategies, and since 4.0 two more strategies have been added, so Redis has 8 elimination strategies.

It can be divided into two categories:

  • Noeviction is a design designed to exclude data.

  • There are seven strategies for weeding out data.

Here we focus on seven strategies for weeding out data, which can again be grouped into two categories:

Will be eliminated in all data: ALLkeys-LRU, AllKeys-random, allKeys-LFU

Volatile – lRU, volatile-random, volatile- TTL, volatile- LFU will be eliminated in setting expiration data

Guys, I put the mind map I stayed up all night.

Redis elimination strategy in detail

By default, noeviction is designed as a default policy when Redis memory exceeds maxMemory and will not weed out any data. Write requests after the Redis cache is full are not processed and will return an error.

Allkeys-lru, ALLKeys-Random and ALLKeys-LFU were followed. They filter out data that is set to expire, so the range of data they filter is set to expire. When data expires, even if the cache is not full, it will be weeded out and deleted.

Volatile – TTL: deletes the key whose expiration time is closest according to its TTL. The key whose expiration time is earlier is deleted first.

Volatile -random: Random. Expired keys are deleted at random.

Volatile – LRU: In the case of keys with expiration time, the LRU algorithm is used to filter out the elimination key.

Volatile – lFU: The LFU algorithm is used to filter out out keys for which expiration time is set.

The elimination data range of allkeys-LRU, Allkeys-Random and allKeys-LFU prefixes with ALL includes allkey values. The elimination data range is allkey values, which means that the elimination will be carried out no matter whether the expiration time is set.

Allkeys-random: randomly weed out data from allkeys.

Allkeys-lru: filters data using the lru algorithm in allkeys.

Allkeys-lfu: filters data across allkeys using the lfu algorithm.

Both TTL and RANDOM algorithm rules are relatively simple, while the main LRU and LFU algorithms are not complicated, let’s have a look.

LRU (Least Recently Used)

LRU (Least Recently Used) filters the Least frequently Used data, removes the Least frequently Used data, and keeps the most Recently Used data in the cache.

How to filter can be seen in the following example, assuming that in a limited space, the most recently accessed will be moved to the top, and the most recently inaccessible will be moved to the end, namely the LRU end. When the space is used up and there is new data, the end key of the LRU end will be replaced and eliminated.

The LRU algorithm is very user experience. “If data has been accessed recently, the probability of being accessed again is very high.”

So if you want to implement the LRU algorithm, naturally you need to have the data structure to support it, in this case you can use a linked list, with a linked list to store all the cached data. The problem with using only linked lists, however, is that when faced with a large amount of data, the movement of linked lists can also become cumbersome and time-consuming, which affects Redis performance.

Redis will not miss this opportunity to optimize, so Redis is working on the LRU algorithm. So start by recording the timestamp of the last time each piece of data was accessed. Later, when Redis is ready to eliminate data, N data are randomly selected for the first time, and then taken as a candidate set. Finally, the LRU field carried by these N data is compared, and the smallest one will be eliminated from the cache.

Redis provides a configuration parameter for Maxmemory-samples that allows Redis to select data as candidate datasets.

When faced with elimination data, Redis needs to select the data, and then it will enter the elimination candidate set created for the first time.

The selection criteria are: the lRU attribute value of the data entering the candidate set must be less than the minimum LRU value in the candidate set.

When new data is entered into the candidate dataset, Redis will exclude the data with the smallest LRU field value from the candidate dataset if the number of data in the candidate dataset reaches maxmemory-samples.

You see, the Redis cache can improve its performance by eliminating the need to maintain a large and growing linked list for increasing data, eliminating the cost of moving the list every time data is accessed.

LFU (Least Frequently Used)

LFU (Least Frequently Used) is the Least Frequently Used recently. LFU cache strategy is very similar to LRU, which is correct, because LFU is a cache strategy optimized on the basis of LRU.

LFU differs from LRU in that LFU divides LRU’s original 24bit LRU field into Idt value and counter value. Where Idt is the first 16bit of the lru field represents the access timestamp. The counter value is the last 8 bits of the LRU field, which is the number of accesses.

LFU algorithm uses two ways: increasing access frequency and decreasing access frequency.

Increasing access frequency

It is incremented by counter, but the maximum it can represent is only 255, so a better counting method is used. Whenever data is accessed, the counter value is multiplied by lFU_log_factor and then multiplied by 1, and the reciprocal is obtained to obtain the p value; Then the ratio of p value to random number r between 0 and 1. When p value is greater than r value, the counter will increase by 1.

1/(baseval * lfu_log_factor + 1)

A table provided by the official website of Redis, when lFU_log_factor is set to different values, different times of access, the counter value changes.

As can be seen from the table, the value of lFU_log_factor is 1, and when the number of accesses is 100K, the value of counter reaches 255, and there is no way to distinguish the number of accesses. When lFU_log_factor is set to 100, the number of visits is 10M, and the value of counter reaches 255. At this point, different data with the number of visits less than 10M can be distinguished by the value of counter.

Access frequency attenuation

When Redis implements the LFU strategy, in addition to increasing access frequency, it also designs a attenuation mechanism. As can be seen from the above, counter keeps increasing until it reaches the top 255, and pure increasing cannot reflect the heat of a key. Therefore, if the key is not accessed for a period of time, counter also needs to decrease accordingly.

Decaying rate The decaying rate of counter is controlled by the lfu-decay-time configuration item, with a default value of 1 indicating that counter is decayed by N if there is no access for N minutes.

conclusion

The memory reclamation strategy of Redis has two aspects: deleting expired keys and eliminating keys. However, both the deletion and elimination strategies are aimed at controlling and preventing memory overflow. In terms of elimination strategies, Redis4.0 implements 6 elimination strategies, and since 4.0 two more strategies have been added, so there are 8 elimination strategies in Redis. LRU and LFU algorithm strategies are the most important. LFU is a strategy based on LRU, but LFU is not used to replace LRU; The former LRU strategy focuses on data timeliness, while the latter LFU focuses on access frequency.

This, my friends, is the end.

I am a fierce and agile seed, afraid of what infinite truth, into an inch, have into an inch of joy. Thanks for your attention, likes, favorites and comments. See you next time!

The article continues to update, you can search wechat “a fierce and agile seed” to read the first time.