What happens to Redis when memory runs out

Preface

As a server, the memory is not unlimited, so there will always be memory exhaustion. Then when the memory of the Redis server is exhausted, if the request command continues to be executed, what will Redis do?

Memory reclamation

When using Redis services, in many cases, certain key-value pairs will only be valid for a certain period of time. In order to prevent this type of data from occupying memory all the time, we can set the validity period for the key-value pairs. In Redis, four independent commands can be used to set the expiration time for a key:

expire key ttl: Set the expiration time of the key value to ttl seconds .

pexpire key ttl: Set the expiration time of the key value to ttl milliseconds .

expireat key timestamp: Set the expiration time of the key value to the specified timestamp seconds .

pexpireat key timestamp: Set the expiration time of the key value to the specified timestamp milliseconds .

PS: No matter which command is used, the bottom layer of Redis is finally implemented using the pexpireat command. In addition, commands such as set can also set the key and add the expiration time at the same time, so that the atomicity of the setting and expiration time can be guaranteed.

After setting the validity period, you can use the ttl and pttl commands to query the remaining expiration time (if the expiration time is not set, the following two commands return -1, if an illegal expiration time is set, both return -2):

ttl key returns the remaining expiration seconds of the key.

pttl key returns the number of milliseconds remaining for the key to expire.

Expiration strategy

If you delete an expired key, we generally have three strategies:

Timed deletion: Set a timer for each key, once the expiration time is up, delete the key. This strategy is very memory friendly, but not CPU friendly, because each timer will take up a certain amount of CPU resources.

Lazy deletion: No matter whether the key is expired or not, it will not be deleted actively. It will be judged whether it is expired every time the key is obtained. If it expires, the key will be deleted, otherwise the value corresponding to the key will be returned. This strategy is not memory friendly and may waste a lot of memory.

Regular scan: The system scans regularly at regular intervals, and deletes expired keys. This strategy is relatively a compromise between the above two strategies. It should be noted that this regular frequency should be controlled in accordance with the actual situation. The use of this strategy has a drawback that keys that have expired may also be returned.

In Redis, the choice is the combined use of strategy 2 and strategy 3. However, the regular scan of Redis will only scan the keys with the expiration time set, because the key with the expiration time set in Redis will be stored separately, so there will be no scanning of all keys:

typedefstructredisDb{

dict *dict;//All key-value pairs

dict *expires;//Key-value pairs with expiration time set

dict *blocking_keys;//Blocked keys, such as when the client executes blocking instructions such as BLPOP

dict *watched_keys;//WATCHED keys

intid;//Database ID

//... other attributes omitted

} redisDb;

8 elimination strategies

If all the keys in Redis have not expired and the memory is full at this time, what will Redis do when the client continues to execute commands such as set? Redis provides different elimination strategies to deal with this scenario.

First, Redis provides a parameter maxmemory to configure the maximum memory usage of Redis:

maxmemory

Or it can be dynamically modified by the command config set maxmemory 1GB.

If this parameter is not set, then Redis uses up to 3GB of memory in a 32-bit operating system, but there is no limit in a 64-bit operating system.

Redis provides 8 elimination strategies, which can be configured through the parameter maxmemory-policy:

Elimination strategy description

Volatile-lru deletes keys with an expiration time according to the LRU algorithm until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

allkeys-lru deletes all keys according to the LRU algorithm until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

Volatile-lfu deletes keys with an expiration time according to the LFU algorithm until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

allkeys-lfu deletes all keys according to the LFU algorithm until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

Volatile-random randomly deletes keys with an expiration time until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

allkeys-random randomly deletes all keys until free space is available. If there is no key object that can be deleted, and the memory is still not enough, an error will be reported

Volatile-ttl deletes the data that will expire recently according to the ttl attribute of the key-value object. If not, report an error directly

Noeviction default strategy, do not do any processing, directly report an error

PS: The elimination strategy can also be dynamically configured by directly using the command config set maxmemory-policy <policy>.

LRU algorithm

The full name of LRU is: Least Recently Used. That is: the longest time it has not been used recently. This is mainly for use time.

Redis's improved LRU algorithm

In Redis, the traditional LRU algorithm is not used, because the traditional LRU algorithm has two problems:

Need extra space for storage.

There may be some key values ​​that are used very frequently, but have not been used recently, and thus are deleted by the LRU algorithm.

In order to avoid the above two problems, Redis has modified the traditional LRU algorithm and deleted it through sampling .

The configuration file provides an attribute maxmemory_samples 5, the default value is 5, which means that 5 key values ​​are randomly selected, and then these 5 key values ​​are deleted according to the LRU algorithm, so it is obvious that the larger the key value, the more accurate the deletion high.

For the sampling LRU algorithm and the traditional LRU algorithm, there is a comparison chart on the Redis official website:

The light gray band is the deleted object.

The gray bands are objects that have not been deleted.

Green is the added object.

The first picture in the upper left corner represents the traditional LRU algorithm. You can see that when the number of samples reaches 10 (upper right corner), it is very close to the traditional LRU algorithm.

How Redis manages heat data

When we talked about string objects earlier, we mentioned that there is a lru attribute in the redisObject object:

typedefstructredisObject(unsignedtype: 4;//Object type (4 bits = 0.5 bytes) unsigned encoding: 4; // Encoding (4 bits = 0.5 bytes) unsignedlru: LRU_BITS; // Record the last time the object was accessed by the application ( 24 bits = 3 bytes) intrefcount;//reference count. When it is equal to 0, it means that it can be garbage collected (32 bits = 4 bytes) void*ptr;//Point to the actual underlying data storage structure, such as: SDS, etc. (8 bytes)} robj;

The lru attribute is written when the object is created, and updated when the object is accessed. Normal people's thinking is that the final decision whether to delete a certain key is definitely to subtract lru from the current timestamp, and the one with the largest difference will be deleted first. But this is not done in Redis. Redis maintains a global attribute lru_clock, which is updated by a global function serverCron executed every 100 milliseconds, and records the current unix timestamp.

The final decision to delete the data is obtained by subtracting the lru attribute of the object from lru_clock. So why does Redis do this? Wouldn't it be more accurate to take the global time directly?

This is because doing so can avoid directly fetching global attributes every time the lru attribute of the object is updated, instead of calling system functions to obtain system time, thereby improving efficiency (Redis has many such detailed considerations to improve performance. It can be said that the performance is optimized to the extreme as much as possible).

But there is another problem here. We see that the lru attribute in the redisObject object is only 24 bits, and the 24 bits can only store the 194-day timestamp size. Once it exceeds 194 days, the calculation will start from 0 again, so this time It may happen that the lru attribute in the redisObject object is greater than the global lru_clock attribute.

Because of this, the calculation needs to be divided into two situations:

When global lruclock>lru, use lruclock-lru to get free time.

When global lruclock

It should be noted that this calculation method does not guarantee that the longest idle time can be deleted from the sampled data. This is because there are very few cases where it has not been used for more than 194 days. Once again, the calculation will only go wrong when the lruclock continues to exceed the lru attribute in the second round.

For example, the lru recorded by object A is 1 day, and the second round of lruclock has reached 10 days. At this time, the calculation result is only 10-1=9 days, which should actually be 194+10-1=203 days. But this kind of situation can be said to happen rarely, so this processing method may be deleted inaccurately, but this algorithm itself is an approximate algorithm, so it will not have much impact.

LFU algorithm

The full name of LFU is: Least Frequently Used. That is: the least frequently used recently, this is mainly for the frequency of use. This attribute is also recorded in the lru attribute in redisObject.

When we use the LFU recycling strategy, the upper 16 bits of the lru attribute are used to record the access time (last decrement time: ldt, in minutes), and the lower 8 bits are used to record the access frequency (logistic counter: logc), referred to as counter.

Increasing frequency of visits

Each key of the LFU counter has only 8 bits, and the maximum value it can represent is 255, so Redis uses a probability-based logarithm to increase the counter. r

Given an old access frequency, when a key is accessed, the counter is incremented as follows:

Extract the random number R between 0 and 1.

counter- the initial value (default is 5), get a basic difference value, if the difference value is less than 0, then directly take 0, for the convenience of calculation, this difference value is recorded as baseval.

The formula for calculating the probability P is: 1/(baseval * lfu_log_factor + 1).

If R <P, the frequency is incremented (counter++).

The lfu_log_factor in the formula is called the logarithmic factor, and the default is 10, which can be controlled by parameters:

lfu_log_factor 10

The following figure shows the relationship between the logarithmic factor lfu_log_factor and the growth of the frequency counter:

It can be seen that when the logarithmic factor lfu_log_factor is 100, about 10M (10 million) visits will increase the visit counter to 255, and the default 10 can also support 1M (1 million) visits to reach 255. The upper limit, which is sufficient to meet the demand in most scenarios.

Decreasing frequency of visits

If the access frequency counter just keeps increasing, it will all reach 255 sooner or later, which means that the counter keeps increasing and cannot fully reflect the popularity of a key, so when a key is not accessed for a period of time, the counter needs to be reduced accordingly.

The counter reduction speed is controlled by the parameter lfu-decay-time, the default is 1, and the unit is minute. The default value of 1 means: if there is no access within N minutes, the counter will be decremented by N.

lfu-decay-time 1

The specific algorithm is as follows:

Get the current timestamp, convert it to minutes and take the lower 16 bits (for the convenience of subsequent calculations, this value is recorded as now).

Take out the high 16 bits of the lru attribute in the object (in order to facilitate subsequent calculations, this value is recorded as ldt).

When lru>now, the default is one cycle (16 bits, maximum 65535), then take the difference 65535-ldt+now: when lru<=now, take the difference now-ldt (in order to facilitate subsequent calculations, this The difference is recorded as idle_time).

Take out the value of lfu_decay_time in the configuration file, and then calculate: idle_time / lfu_decay_time (for the convenience of subsequent calculations, this value is recorded as num_periods).

Finally, reduce the counter: counter-num_periods.

It looks so complicated. In fact, the calculation formula is just one sentence: Take out the current timestamp and compare the lru attribute in the object to calculate how long it has not been accessed. For example, the calculated result is that it has not been accessed for 100 minutes, and then remove it. The configuration parameter lfu_decay_time, if this configuration defaults to 1, which means 100/1=100, it means that there is no access in 100 minutes, so the counter is reduced by 100.

to sum up

This article mainly introduces the processing strategy of Redis expired keys, as well as the 8 elimination strategies of Redis when the server memory is not enough, and finally introduces the two main elimination algorithms in Redis, LRU and LFU.