Redis memory key – value is based on the database, the size of the memory is limited, if the memory is full, Redis will do, in addition, we can through the expire set the expiration date of the key, so the key is expired, Redis collection mechanism is how?

Memory reclamation policy

Maximum memory configuration

Redis Based on the Redis. Conf configuration file in the directory, you can set the memory size used by Redis

Set the maximum memory usage to 100MB
maxmemory 100mb
Copy the code

Tips: If this is set to 0, 64-bit operating systems default to no memory limit, while 32-bit operating systems implicitly limit to 3GB

Redis also has two commands for maximum memory

Config get maxMemory 1) "maxmemory" 2) "0" // Set maxmemory 100MBCopy the code

Eviction Policies

Redis has several strategies to handle this situation when the maximum memory limit for configuration files is reached:

If you do not know the LRU algorithm, you can refer to this article LRU algorithm

  • Noeviction: Write requests will no longer be served, errors will be returned (except DEL requests and some special requests)

  • Allkeys-lru: uses the lru algorithm to weed out allkeys

  • Volatile – LRU: Uses the LRU algorithm to flush out expired keys

  • Allkeys-random: randomly weed out data from allkeys

  • Volatile -random: Randomly weed out keys with expiration dates

  • Volatile – TTL: The key whose expiration time is set is discarded according to its expiration time. The earlier the key expires, the earlier the key is discarded

Like Noeviction, error returns when no key can be eliminated when using volatile- LRU, volatile- Random, volatile- TTL policiesCopy the code

Redis supports command modification of expulsion policies

Noeviction config get maxmemory-policy 1 noeviction config get maxmemory-policy 1"maxmemory-policy"
 2)  "noeviction"// Change the memory expulsion policy configset maxmemory-policy allkeys-lru
Copy the code

Similarly, you can specify an expulsion policy in a configuration file

maxmemory-policy allkeys-lru
Copy the code

How does an eviction strategy work

  1. When Redis receives a command to add data
  2. Redis checks memory usage to see if the maximum memory limit is exceeded
  3. If so, the memory expulsion policy is executed, and then the command is executed.

Tips: If a command uses a lot of memory, it may exceed the maximum memory limit

LRU algorithm implemented in Redis

Redis implements an approximate LRU algorithm, which is not quite the same as the conventional LRU algorithm. The approximate LRU algorithm weeded out data by random sampling, randomly producing 5 (default) keys at a time, and weeding out the least recently used keys from the data.

In order to realize the approximate LRU algorithm, Redis adds an extra 24bit field to each key, which is used to store the last access time of the key.

Tips: You can modify the number of samples by setting the value maxmemory-samples parameter

Redis 3.0 optimizes this approximation algorithm

The new algorithm maintains a candidate pool (size 16). The data in the pool is sorted according to the access time. The first randomly selected key is added to the pool, and the subsequent randomly selected key is added to the pool only when the access time is shorter than the minimum time in the pool. When the pool is full, if new keys need to be added, the pool with the highest last access time (most recently accessed) is removed.

When you need to flush, you need to flush out the key that has not been accessed for the longest time from the pool.

Comparison of old and new algorithms

The image below is a comparison of the old and new algorithms according to the official Redis documentation:

  • Light grey is the data that is eliminated
  • Gray is old data that hasn’t been eliminated
  • Green is the new data

It can be seen that the effect of 3.0 is significantly better than that of 2.8, and the larger the sample number, the closer it is to the standard LRU algorithm

Why doesn’t Redis use a real LRU

The reason is simple, the theoretical LRU requires you to use more memory (each key also needs to store the address of the previous key), but as you can see from the above figure, the approximate LRU algorithm used by Redis 3.0 is almost equivalent to the theoretical LRU algorithm.

New eviction strategy -LFU

LFU algorithm is a new elimination strategy added in Redis4.0. Its full name is Least Frequently Used, and its core idea is that key is eliminated according to the frequency of recent visits. Those that are seldom visited are eliminated first, and those that are Frequently visited are retained.

The LFU algorithm can better represent the heat of a key being accessed. If you are using the LRU algorithm, a key that has not been accessed for a long time, but only once in a while, is considered hot data and will not be eliminated, while some keys that are likely to be accessed in the future will be eliminated. This is not the case with the LFU algorithm, because using a key once does not make it hot data.

The realization mainly depends on two parameters calculator and decay period, the calculator value range is 0-255, the higher the number of visits, the higher the corresponding value, decay period means that every certain time, the calculator will be reduced. There are two parameters

// The larger the factor, the more times the frequency counter needs to be decayed lfu-log-factor 10 // Every minute the calculator decays by 1, 0 means that the counter is always decayed lfu-decay-time by 1Copy the code

LFU has two strategies:

  • Volatile – LFU: The LFU algorithm is used to eliminate the key whose expiration time is set
  • Allkeys-lfu: uses the lfu algorithm to eliminate data in allkeys

Key failure mechanism

Redis has two Key failure mechanisms: passive way and active way.

Passive way

When a client attempts to access a key and finds that the key is invalid, it deletes the key and informs the client that the key is invalid.

Active way

Of course, having a passive approach is not enough, because there may be expired keys that are never accessed again.

So how do you delete those keys, do you periodically walk through the library? Of course not, it’s too performance intensive when there’s a lot of data.

Redis proactively deletes invalid keys by randomly selecting some keys for verification. If the keys are invalid, they will be deleted and eliminated.

Specific measures

Redis performs the following operations 10 times per second:

  1. Randomly selected from a set of keys with an expiration date20A key.
  2. Delete all expired keys
  3. If the expired key exceeds25%To perform Step 1 again.

Reference:

This article refers to the official Redis documents Lru-cache and EXPIRE

Mining user lotus leaf Redis memory elimination strategy article