This article has participated in the third “topic writing” track of the Denver Creators Training Camp. For details, check out: Digg Project | Creators Training Camp third is ongoing, “write” to make a personal impact.

Redis (Remote Dictionary Server) is an open source, network-enabled, memory-based and persistent logging, key-value database written in ANSI C language, and provides multiple language APIS. It has the following characteristics:

  • Memory – based operation with high performance characteristics
  • Support distributed, theoretically can be infinite expansion
  • Key-value storage structure, efficient query
  • Provides a variety of development language API, easy to integrate with existing business systems.

Generally used in business systems as distributed cache, centralized Session storage, distributed lock and other application scenarios.

To ensure high performance, both local and distributed caches use memory to store data. Due to the cost and memory limitation, when the stored data exceeds the cache capacity, the cached data needs to be deleted. The general elimination strategies include FIFO to eliminate the earliest data, LRU to eliminate the least recently used data, and LFU to eliminate the most recently used data.

Redis cache flush policy triggered

We don’t allow swap behavior in redis in production. Redis provides the configuration parameter maxMemory to specify the maximum memory that can be used.

The following configurations are valid:

Maxmemory 1000KB maxmemory 100MB maxmemory 1GB maxmemory 0 # indicates that there is no limitCopy the code

The redis.conf configuration file is as follows

Eight Redis cache strategies

  1. Volatile – lRU deletes the least frequently used data for which the timeout is set.
  2. Allkeys -lru queries allkeys for the least frequently used data to delete, which is the most widely used strategy;
  1. Volatile -random Randomly deletes data that has been timed out;
  2. Allkeys-random queries allkeys and deletes them randomly.
  1. Volatile – TTL queries all the data with the specified timeout period, sorts the data immediately, and deletes the data that is about to expire.
  2. Noeviction (default) if set to this property, no deletion will be performed, error will be returned if memory is out;
  1. Volatile – lFU expels the least frequently used key from all keys with expired time;
  2. Allkeys-lfu removes the least frequently used key from allkeys;

Redis LRU and LFU algorithm

LRU algorithm

The Redis LRU algorithm is not an exact implementation. This means that Redis is unable to select the best candidate for expulsion, the one with the most visits in the past. Instead, it tries to run an approximation of the LRU algorithm by sampling a small number of keys and then expelling the best of the sampled keys (with the earliest access time).

However, since Redis 3.0, the algorithm has been improved and some good candidates can be selected for expulsion. This improves the performance of the algorithm and enables it to more closely resemble the behavior of a real LRU algorithm.

The important thing about the Redis LRU algorithm is that you can adjust the accuracy of the algorithm by changing the number of samples to check each expulsion. This parameter is controlled by the following configuration instructions:

maxmemory-samples 5
Copy the code

Redis doesn’t use a real LRU implementation because it requires more memory. However, for applications that use Redis, the approximations are virtually equivalent. Below is a comparison of the LRU approximation used by Redis with the real LRU.



The test that generated the diagram above populates the Redis server with a given number of keys. Access the key from first to last, so the first key is the best candidate for expulsion using the LRU algorithm. Later, 50% of the key was added to force the expulsion of half of the old key.

You can see three kinds of points in the diagram, forming three different bands.

  • The light gray zone is the object of expulsion.
  • Gray bands are objects that have not been expelled.
  • The green band is the added object.

In a theoretical LRU implementation, we would expect the first half to expire in the old key. The Redis LRU algorithm will only expire the old key in probability.

The LRU is simply a model for predicting the likelihood that a given key will be accessed in the future. Also, if your data access pattern is very power-law like, most of the access will be in key sets that the LRU approximation algorithm can handle well.

Disadvantages: A large number of cold data may be accessed within a certain period of time, resulting in a large number of hot data

LFU algorithm

Starting with Redis 4.0, a new least-used expulsion mode is available. This pattern may be better in some cases (providing better hit/miss ratio) because using LFU Redis attempts to track the frequency of access to items, so rarely used items are expelled, while frequently used items have a higher chance of staying in memory.

If you assume that in the LRU, items that have recently been accessed but are virtually never requested will not expire, the risk is to expel keys that have a higher chance of being requested in the future. LFU does not have this problem and should generally be better adapted to different access modes.

To configure the LFU mode, use the following policies:

  • Volatile – lFU uses approximate LFU expulsion on keys that have expired sets.
  • Allkeys-lfu uses approximate LFU to expel any key.

LFU is similar to LRU: it uses a probability counter, called a Morris counter, so that only a few bits of each object are used to estimate the frequency of object access, combined with the decay period so that the counter decreases over time: At some point, we no longer want to treat keys as frequently accessed keys, even if they used to be, so that algorithms can adapt to shifts in access patterns.

This information is sampled similarly to what happens in LRU (as described in the previous section of this document) in order to select candidates for expulsion.

However, unlike LRU, LFU has certain tunable parameters: for example, how quickly should it be ranked down if frequent items are no longer accessed? You can also adjust the Morris counter range to better adapt the algorithm to a particular use case.

By default Redis 4.0 is configured as:

  • Saturate the counter at about one million requests.
  • The counter is attenuated every minute.

These should be reasonable values and experimentally tested, but users may want to use these configuration Settings to select the best values.

Instructions on how to adjust these parameters can be found in redis.conf in the sample file for the source distribution, but simply put, they are:

lfu-log-factor 10 
lfu-decay-time 1
Copy the code

The decay time is obvious, which is the number of minutes the counter should decay when sampled and found to be older than this value. A special value of 0 means that the counter is always attenuated with each scan and is rarely useful.

The counter log factor changes how many hits are required to saturate the frequency counter, which is exactly in the 0-255 range. The higher the coefficient, the more accesses are required to reach the maximum. According to the following table, the lower the coefficient, the better the resolution of the low-access counter:

+--------+------------+------------+------------+------------+------------+ | factor | 100 hits | 1000 hits | 100K hits | 1M hits | 10M hits | +--------+------------+------------+------------+------------+------------+ | 0 | 104 | 255 | 255 255 | 255 | | + -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- + | 1 18 49 | | 255 | | 255 | 255 | + -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + 10 10 18 | | | | 142 | | 255 | 255 + + -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- - + -- -- -- -- -- -- -- -- -- -- -- -- + | 100 | 8 11 49 | | 143 | | 255 | +--------+------------+------------+------------+------------+------------+Copy the code

Weed out the data that has been accessed least frequently in the recent period and use the number as a reference.

Disadvantages:

1. Recently added data are often easy to be excluded, because the number of initial methods is relatively small.

2. If the frequency-time metric is 1 hour, hotspot data with an average access frequency of 1000 per hour of a day may be excluded from data with an average access frequency of 1001 over a 2-hour period. There may be some threshold data.

Suggestions for setting cache policies

Suggestion: After understanding the Redis obsolescence policy, you should proactively set/update the expire time of the key to eliminate old data that is not active, which is helpful to improve the query performance

Refer to the content

  • redis.io
  • Redis. IO/switchable viewer/lru -…