Shulou(Shulou.com)06/01 Report--

This article will explain in detail the case of LRU algorithm in Redis. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

LRU algorithm of Redis

The idea behind the LRU algorithm is ubiquitous in computer science, and it is very similar to the "locality principle" of programs. In a production environment, although there are Redis memory usage alerts, it is beneficial to understand the cache usage strategy of Redis. The following is the policy for the use of Redis in the production environment: the maximum available memory is limited to 4GB and the allkeys-lru deletion policy is adopted. The so-called deletion strategy: when the redis usage has reached the maximum memory, such as 4GB, if a new Key is added to the redis at this time, then Redis will select a Key to delete. So how to choose the right Key to delete?

CONFIG GET maxmemory

"maxmemory"4294967296"

CONFIG GET maxmemory-policy

"maxmemory-policy"allkeys-lru"

In the official document Using Redis as an LRU cache description, several deletion strategies are provided, such as allkeys-lru, volatile-lru, and so on. In my opinion, there are three factors to consider when choosing: random, the time Key was recently visited, and the expiration time of Key (TTL)

For example: allkeys-lru, "count all" Key history visits, and remove the "oldest" Key. Note: I put quotation marks here, in fact, in the specific implementation of redis, it is very expensive to count the recent visit time of all Key. Think about it. How do you do that?

Evict keys by trying to remove the less recently used (LRU) keys first, in order to make space for the new data added.

Another example: allkeys-random, which randomly selects a Key and removes it.

Evict keys randomly in order to make space for the new data added.

Another example: volatile-lru, which removes only those Key that use the expire command to set the expiration time, according to the LRU algorithm.

Evict keys by trying to remove the less recently used (LRU) keys first, but only among keys that have an expire set, in order to make space for the new data added.

Another example: volatile-ttl, which removes only those Key that use the expire command to set the expiration time, and the shorter the survival time of the Key (the smaller the TTL KEY), the priority is to remove it.

Evict keys with an expire set, and try to evict keys with a shorter time to live (TTL) first, in order to make space for the new data added.

The Key that the volatile policy (eviction methods) acts on is the Key that sets the expiration time. In the redisDb structure, a key named expires dictionary (dict) is defined to hold all the key that have the expiration time set with the expire command, where the key of the expires dictionary points to a key in the redis database key space (redisServer--- > redisDb--- > redisObject), and the value of the expires dictionary is the expiration time of that key (integer of type long).

Additional mention: the redis database key space refers to a pointer named "dict" and type hash dictionary defined in the structure redisDb, which is used to hold every key object in the redis DB and the corresponding value object.

Since there are so many strategies, which one should I use? This involves the access pattern of Key in Redis (access-pattern). Access-pattern is related to code business logic. For example, Key that conforms to certain characteristics is often accessed, while other Key is not used very much. If all Key can be accessed equally by our application, then its access mode obeys uniform distribution; in most cases, the access mode obeys power exponential distribution (power-law distribution), and the access mode of Key may also change over time, so we need an appropriate deletion strategy to catch (capture) a variety of situations. Under the power exponential distribution, LRU is a good strategy:

While caches can't predict the future, they can reason in the following way: keys that are likely to be requested again are keys that were recently requested often. Since usually access patterns don't change very suddenly, this is an effective strategy.

Implementation of LRU Strategy in Redis

The most intuitive idea: LRU, record the last visit time of each key (such as unix timestamp), the smallest Key of unix timestamp, which has not been used recently, remove this Key. If you look at it, you can do it with a HashMap. Yes, but first you need to store each Key and its timestamp. Second, compare timestamp to get the minimum value. It's too expensive to be realistic.

The second method: from another point of view, do not record the specific access time point (unix timestamp), but record the smaller the idle time:idle time, which means that it was recently accessed.

The LRU algorithm evicts the Least Recently Used key, which means the one with the greatest idle time.

For example, the four Key,An A, B, C and D visit every 5 seconds, B visits every 2 seconds, and C and D visit every 10 seconds. (a tilde stands for 1s), as can be seen from the above picture: a's free time is 2sMagi B's idle time is 1sMagi C's idle time is 5sMagne D has just been visited, so idle time is 0s

Here, all the Key lists are linked with a two-way linked list (linkedlist). If a Key is accessed, move the Key to the header of the linked list, and when you want to remove the Key, remove it directly from the footer.

It is simple to implement because all we need to do is to track the last time a given key was accessed, or sometimes this is not even needed: we may just have all the objects we want to evict linked in a linked list.

But in redis, it is not implemented in this way, it thinks that LinkedList takes up too much space. Redis does not implement KV database directly based on string, linked list, dictionary and other data structures, but creates an object system Redis Object on these data structures. A field of type unsigned of length 24bit is defined in the redisObject structure to store the last time the object was accessed by the command program:

By modifying a bit the Redis Object structure I was able to make 24 bits of space. There was no room for linking the objects in a linked list (fat pointers!)

After all, there is no need for a completely accurate LRU algorithm, and even if a recently visited Key is removed, the impact is not significant.

To add another data structure to take this metadata was not an option, however since LRU is itself an approximation of what we want to achieve, what about approximating LRU itself?

Originally, Redis was implemented as follows:

Select three Key at random and remove the Key with the largest idle time. Later, change 3 to a configurable parameter, which defaults to N=5:maxmemory-samples 5

When there is to evict a key, select 3 random keys, and evict the one with the highest idle time

It's that simple, unbelievably simple, and very effective. But it still has its drawbacks: every time it is randomly selected, it does not make use of historical information. When removing (evict) one Key in each round, randomly select a Key from N, remove the largest Key; of idle time, and then randomly select a Key... from N in the next round. Have you ever thought that I actually knew about the idle time of N Key in the last round of removing Key, so can I take advantage of some of the information I knew in the next round of removing Key?

However if you think at this algorithm across its executions, you can see how we are trashing a lot of interesting data. Maybe when sampling the N keys, we encounter a lot of good candidates, but we then just evict the best, and start from scratch again the next cycle.

Start from scratch is so stupid. So Redis made another improvement: using buffer pool (pooling)

When you remove Key in each round, you get the idle time of N Key, and if its idle time is larger than the idle time of Key in pool, add it to pool. In this way, the Key removed each time is not only the largest of the N randomly selected Key, but also the largest idle time in the pool, and: the Key in the pool is screened through several rounds of comparison, and its idle time is larger than the idle time of the randomly obtained Key. It can be understood that the Key in the pool retains "historical experience information".

Basically when the N keys sampling was performed, it was used to populate a larger pool of keys (just 16 keys by default). This pool has the keys sorted by idle time, so new keys only enter the pool when they have an idle time greater than one key in the pool or when there is empty space in the pool.

Using "pool", a global scheduling problem is transformed into a local comparison problem. (although sorting is essentially a comparison, embarrassing). To know the largest key of idle time, the exact LRU needs to sort the idle time of the global key, and then you can find the largest key of idle time. But an approximate idea can be adopted, that is, random sampling (samping) several key, these key represent the global key, put the key obtained by samping into the pool, and update the pool after each sampling, so that the key with the largest idle time of the randomly selected key is always saved in the pool. When you need evict key, take out the largest key of idle time directly from pool and evict it. This kind of thinking is worth learning from.

At this point, the LRU-based removal strategy has been analyzed. There is also a removal strategy based on LFU (access frequency) in Redis, which will be discussed later.

LRU implementation in JAVA

LinkedHashMap in JDK implements the LRU algorithm, using the following construction method, and accessOrder represents the "least recently used" metric. For example, accessOrder=true, when the java.util.LinkedHashMap#get element is executed, it indicates that the element has recently been accessed.

/ * * Constructs an empty LinkedHashMap instance with the * specified initial capacity, load factor and ordering mode. * * @ param initialCapacity the initial capacity * @ param loadFactor the load factor * @ param accessOrder the ordering mode-true for * access-order, false for insertion-order * @ throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive * / public LinkedHashMap (int initialCapacity, float loadFactor Boolean accessOrder) {super (initialCapacity, loadFactor) This.accessOrder = accessOrder;}

Rewrite the java.util.LinkedHashMap#removeEldestEntry method.

The {@ link # removeEldestEntry (Map.Entry)} method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

To ensure thread safety, wrap the LinkedHashMap object with Collections.synchronizedMap:

Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map.

The implementation is as follows: (org.elasticsearch.transport.TransportService)

Final Map timeoutInfoHandlers = Collections.synchronizedMap (new LinkedHashMap (100,.75F, true) {@ Override protected boolean removeEldestEntry (Map.Entry eldest) {return size () > 100;}})

When the capacity exceeds 100, start implementing the LRU policy: evict the least recently unused TimeoutInfoHolder objects.

The case of LRU algorithm in Redis is shared here. I hope the above content can be helpful to everyone and learn more knowledge. If you think the article is good, you can share it for more people to see.

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.