Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1, the introduction of

Redis is a key-value database based on memory storage. As we know, although the memory is fast, the space is small. When the physical memory reaches the upper limit, the system will run very slowly. However, swap belongs to hard disk storage, and the speed is far less than memory, especially for Redis, a service with very high QPS, this situation cannot be accepted. (Note that if the swap is also full, the system will experience an error!)

For Linux, you can use free -m to check the swap size :\

So how to prevent this from happening at Redis is very important.

2. Maxmemory configuration

Redis provides a maxMemory configuration to address this problem. This configuration can specify the maximum data SET of Redis memory, usually in the Redis. Conf file, or can be configured at run time using the CONFIG SET command. Diagram of configuration items in the redis. Conf file: \

By default, the maxmemory configuration item is not enabled. The 64-bit OS has no memory limit by default, and the 32-bit OS has 3GB implicit memory by default. If the maxmemory value is 0, the memory is not limited.

Therefore, when we do the cache architecture, we should make the appropriate maxMemory configuration according to the hardware resources + business requirements.

3. What if the memory reaches maxmemory

It is clear that maxmemory is configured, and Redis cannot stop working when maxmemory reaches its maximum. How does Redis handle this problem? This is the focus of this article. Redis provides the Maxmemory-policy elimination strategy (this article only covers LRU, not LFU, and LFU will be covered in the next article), which deletes the key that meets the condition and sends out the old and brings in the new. Maxmemory-policy:

  • Noeviction: Error returned when memory limit is reached and client tries to execute commands that may cause more memory to be used, simple read operations are still allowed, but no new data can be written, del requests are allowed.
  • Allkeys-lru: filters out allkeys using the Least Recently Used lru algorithm
  • Allkeys-random: selects allkeys at random
  • Volatile – lRU: The Least Recently Used (lRU) algorithm is Used to eliminate all keys with expiration times. This ensures that data that does not have expiration times and needs to be persisted will not be selected for elimination
  • Volatile -random: Random elimination from all keys with expiration dates
  • Volatile – TTL: Compares the TTL of the remaining expiration time of all keys. The smaller the TTL, the earlier it is eliminated

Volatile lFU /allkeys-lfu is not the same as volatile lfu.

Random Random elimination deletes some keys randomly to release memory space. If the TTL expiration time is small, you can compare the TTL size and delete keys with small TTL values to release memory space. So how is LRU implemented? How does Redis know which key has been used recently and which key has not been used recently?

4. Implementation of LRU algorithm

We use a Java container to implement a simple LRU algorithm. We use ConcurrentHashMap to store the mapping of key-value results and ConcurrentLinkedDeque to maintain the access order of keys. LRU implementation code:

package com.lizba.redis.lru; import java.util.Arrays; import java.util.List; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedDeque; LRU / * * * < p > * * < / p > simple implementation * * @ Author: Liziba * @ the Date: 2021/9/17 23:47 */ public class SimpleLru {/** Data cache */ private ConcurrentHashMap<String, Object> cacheData; Private ConcurrentLinkedDeque<String> sequence; private ConcurrentLinkedDeque<String> sequence; /** Private int capacity; public SimpleLru(int capacity) { this.capacity = capacity; cacheData = new ConcurrentHashMap(capacity); sequence = new ConcurrentLinkedDeque(); } /** * setValue ** @param key * @param value * @return */ public Object setValue(String key, Object value) {// Check whether LRU is required to eliminate this.maxMemoryHandle(); If (sequence.contains(key)) {sequence.remove(); } sequence.addFirst(key); cacheData.put(key, value); return value; } /** * reaches the maximum memory, Discard the least recently used key */ private void maxMemoryHandle() {while (sequence.size() >= capacity) {String lruKey = sequence.removeLast(); cacheData.remove(lruKey); System.out.println("key: "+ lruKey +" ); Public List<String> getAll() {return array.asList (sequence.toarray (new String[]) {})); }}Copy the code

Test code:

package com.lizba.redis.lru; / * * * < p > the least recently used * * test < / p > * * @ Author: Liziba * @ the Date: 2021/9/18 0:00 */ public class TestSimpleLru { public static void main(String[] args) { SimpleLru lru = new SimpleLru(8); for (int i = 0; i < 10; i++) { lru.setValue(i+"", i); } System.out.println(lru.getAll()); }}Copy the code

Test result: \

image.png

As can be seen from the above test results, the first key0 and key1 are eliminated, and the last key added is also the latest key stored in the head of the sequence. Through this scheme, LRU algorithm can be implemented very simply; But the disadvantage is also very obvious, the scheme needs to use additional data structure to save the key access order, which will increase the memory consumption of Redis, itself used to optimize the memory scheme, but to consume a lot of memory, obviously not.

5. Approximate LRU of Redis

In this case, Redis uses an approximate LRU algorithm, which is not completely accurate in eliminating the most recently used keys, but the overall accuracy can also be guaranteed. The approximate LRU algorithm is very simple. In the key object of Redis, 24bit is added to store the system time stamp of the last access. When the client sends the key write request to the Redis server, the memory reaches maxMemory, and the lazy deletion is triggered. The Redis service selects five keys that meet the criteria by random sampling (allkees-lru is randomly sampled from allkeys, volatile lru is randomly sampled from allkeys with expiration dates) and compares them with the most recent access timestamp recorded in the key object. Discard the oldest key of the five; If the memory is still low, continue to repeat this step.

Note that 5 is the default Redis random sample value size, which can be configured with maxmemory_samples in Redis. Conf: \

image.png

For the random LRU algorithm mentioned above, Redis officially provides a data graph of test accuracy:

  • The top layer of light gray represents the eliminated key. Figure 1 is the schematic diagram of the eliminated standard LRU algorithm
  • The dark gray layer in the middle represents old keys that have not been eliminated
  • The lightest green at the bottom indicates the most recently accessed key

At the time of Redis 3.0 Maxmemory_samples being set to 10, the Redis approximation LRU algorithm was very close to the real LRU algorithm, But it is clear that setting maxmemory_samples to 10 is more CPU time consuming than setting maxmemory_samples to 5, because the calculation time increases with each larger sample. The LRU algorithm of Redis3.0 is more accurate than that of Redis2.8, because Redis3.0 adds a elimination pool of the same size as maxmemory_samples. Each time keys are eliminated, they are first compared with those waiting to be eliminated in the elimination pool, and the oldest keys are finally eliminated. It’s basically all the keys that are selected and eliminated and then you compare them and eliminate the oldest one.

6. There are problems

LRU algorithm seems to be relatively easy to use, but there are also unreasonable places. For example, two keys A and B were added to Redis at the same time one hour before elimination. A was accessed 1000 times in the first 49 minutes, but was not accessed in the last 11 minutes. B was accessed only once in the 59th minute of the hour; At this point, if the LRU algorithm is used, if both A and B are selected by Redis sampling, A will be eliminated. Obviously, this is unreasonable. In view of this situation, Redis 4.0 added LFU algorithm, which is more reasonable than LRU. I will study the elimination algorithm together in the following. Please pay attention to my column if necessary.