What happens to Redis when memory runs out?

As a server, memory is not infinite, so there will always be a case of running out of memory, so when the Redis server runs out of memory, if you continue to execute the request command, what will Redis do?

Set validity period

When using the Redis service, in many cases certain key-value pairs will only be valid for a certain period of time. To prevent this type of data from holding up memory, we can set a key-value pair expiration date. Redis allows you to set the expiration time of a key with four separate commands:

• Expire key TTL: Sets the expiration time of the key value to TTL seconds.
• Pexpire key TTL: Sets the expiration time of the key value to TTL milliseconds.
• Expireat key timestamp: Sets the expiration time of the key value to the specified timestamp seconds.
• Pexpireat key timestamp: Sets the expiration time of the key value to the specified number of timestamp milliseconds.

PS: No matter which command is used, the bottom layer of Redis is finally implemented with the pexpireat command. In addition, the set command can also set the expiration time along with the key, which ensures the atomicity of the set value and expiration time.

After the validity period is set, you can run the TTL and PTTL commands to query the remaining expiration time. If the expiration time is not set, -1 is returned. If an invalid expiration time is set, -2 is returned.

• TTL Key Indicates the remaining expiration seconds of the key.
• PTTL key Returns the remaining number of milliseconds for the key to expire.

Expiry policies

When deleting an expired key, we generally have three strategies:

• Scheduled deletion: Set a timer for each key and delete the key once the expiration time is up. This strategy is memory-friendly, but cpu-unfriendly, because each timer consumes a certain amount of CPU resources.
• Lazy deletion: No matter whether the key is expired or not, it is not deleted actively. It is determined whether the key is expired each time it is retrieved. If the key is expired, it is deleted; otherwise, the value corresponding to the key is returned. This strategy is not memory friendly and can waste a lot of memory.
• Periodical scan: The system periodically scans for expired keys and deletes them. This strategy is a compromise between the above two strategies. It should be noted that the regular frequency should be controlled according to the actual situation. One drawback of using this strategy is that expired keys may also be returned.

In Redis, it chooses the combined use of strategy 2 and strategy 3. Redis periodically scans only the keys with expiration date set. Because Redis stores the keys with expiration date separately, it does not scan all keys:

typedef struct redisDb { dict *dict; // All key values are dict *expires; // Dict *blocking_keys with an expiration date; Dict *watched_keys; // Dict *watched_keys; // Dict *watched_keys; //WATCHED keys int id; //Database ID //... Other attributes are omitted} redisDb;Copy the code

Eight elimination strategies

If all keys in Redis are not expired and memory is full, what will Redis do if the client continues to execute commands such as set? Redis offers different elimination strategies to handle this scenario.

First, Redis provides a parameter maxMemory to configure the maximum amount of memory Redis can use:

maxmemory <bytes>
Copy the code

Alternatively, you can run the config set maxmemory 1GB command to dynamically change the memory.

If this parameter is not set, Redis uses a maximum of 3GB of memory on 32-bit operating systems and no limit on 64-bit operating systems.

Redis provides eight types of elimination policies, which can be configured with the maxmemory-policy parameter:

PS: You can also run the config set maxmemory-policy < policy > command to dynamically configure an elimination policy.

LRU algorithm

LRU: Least Recently Used. That is, it has not been used for the longest time. This is mainly about time of use.

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

• Extra space is required 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 reformed the traditional LRU algorithm and deleted it through sampling.

The configuration file provides an attribute, Maxmemory_samples 5, which defaults to 5, to randomly extract five keys and then delete them using the LRU algorithm, so it’s clear that the larger the key, the more accurate the deletion will be.

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

• Light gray bands are deleted objects.
• The gray bands are objects that have not been deleted.
• Green is the added object.

The first image on the upper left represents the traditional LRU algorithm. As you can see, when the sample number reaches 10 (upper right), it is very close to the traditional LRU algorithm.

RedisObject has an LRU property:

typedef struct redisObject { unsigned type:4; // Object type (4 bits =0.5 bytes) Unsigned Encoding :4; // Encode (4 bits =0.5 bytes) unsigned LRU :LRU_BITS; // Record the last time the object was accessed by the application (24 bits =3 bytes) int refcount; // Reference count. Void * PTR; void * PTR; // Point to the underlying actual data storage structure, such as SDS, etc. (8 bytes)} robj;Copy the code

The LRU attribute is written when the object is created and updated when the object is accessed. The normal thinking is that the final decision to delete a key is always to subtract the LRU from the current timestamp, and the largest difference will be deleted first. However, this is not done in Redis. The global attribute lru_clock is maintained in Redis. This attribute is updated every 100 milliseconds by a global function serverCron, which records the current Unix timestamp.

The final decision to delete data is obtained by subtracting the object’s LRU attribute from the lRU_clock. So why is Redis doing this? Wouldn’t it be more accurate to just take the global time?

This is because it avoids the need to directly fetch the global attribute every time the lRU attribute of the object is updated, instead of calling the system function to obtain the system time, thus improving efficiency (Redis has a lot of such details to improve performance, which can be said to optimize the performance as much as possible).

The lRU attribute in the redisObject is only 24 bits, which can only store 194 days of timestamp size. After 194 days, the value is reset from 0. It is possible that the LRU attribute in the redisObject is greater than the global LRU_clock attribute.

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

• When global LRUClock > LRU, the free time is obtained using lRUClock-lru.
• When global LRUClock < LRU, the idle time is obtained using lRUClock_max (194 days) -lRU + lRUClock.

It should be noted that this calculation method does not guarantee that the data with the longest idle time can be deleted from the sampled data. This is because it is rare for the first 194 days not to be used, and again only if the LRUClock continues to exceed the LRU attribute in round 2 does the calculation go wrong.

For example, the LRU recorded by object A is 1 day, but the second round of LRUClock has reached 10 days, so the calculation result is only 10-1=9 days, actually 194+10-1=203 days. But this kind of situation can be said to happen less, so this kind of processing method is possible to delete inaccurate situation, but itself this algorithm is an approximate algorithm, so it will not have too much impact.

LFU algorithm

LFU full name: most Frequently Used. That is: the least frequency of recent use, this is mainly aimed at the frequency of use. This property is also recorded in the LRU property of the redisObject.

When we adopted the LFU reclamation strategy, the high 16 bits of the LRU attribute were used to record the visit time (Last Decrement Time: LDT, in minutes) and the low 8 bits were used to record the visit frequency (Logistic Counter: logC), or counter for short.

Increasing access frequency

The LFU counter has only 8 bits per key, and the maximum it can represent is 255, so Redis uses a probability-based logarithm to increment counter. r

Given an old access frequency, counter increments as a key is accessed in the following way:

• Extract random number R between 0 and 1.
• Counter – initial value (default is 5), resulting in a base difference. If the difference is less than 0, it takes 0 directly. For ease of calculation, this difference is called baseval.
• Probability P is calculated by 1/(Baseval * lFU_log_factor + 1).
• If R < P, the frequency increases (counter++).
• The lfu_log_factor in the formula is called the logarithmic factor. The default value is 10, which can be controlled by parameters:

lfu_log_factor 10
Copy the code

The graph below shows the relationship between the logarithmic factor LFU_log_factor and the increase of frequency counter:As you can see, when the logarithmic factor lFU_log_factor is 100, it takes about 10M (10 million) visits to increase access counter to 255, The default 10 can also support up to 1M (1 million) visits to counter to reach the 255 limit, which is sufficient for most scenarios.

The access frequency decreases

If the visit frequency of counter is only increasing, it will all reach 255 sooner or later. In other words, increasing counter cannot fully reflect the heat of a key. Therefore, when a key is not accessed for a period of time, counter also needs to decrease accordingly.

The decaying rate of counter is controlled by the lfu-decay-time parameter, which defaults to 1 in minutes. The default value of 1 means that if there is no access for N minutes, counter is reduced by N.

lfu-decay-time 1
Copy the code

The specific algorithm is as follows:

• Gets the current timestamp and converts it to the lower 16 bits after the minute (this value is denoted as now for subsequent calculations).
• Extract the high 16 bits in the LRU attribute inside the object (this value is denoted as LDT for subsequent calculations).
• When LRU > now, one cycle (16 bits, maximum 65535) has passed by default. Then, the difference value is 65535- LDT +now: When LRU <= now, the difference value is now- LDT (for convenience of subsequent calculation, the difference value is idLE_time).
• Take the value of LFU_DECay_time from the configuration file and calculate IDle_time/lFU_decay_time (num_periods for subsequent calculations).
• Finally reduce counter: counter – num_periods.

It seems so complicated, but the formula is simply: Compare the current timestamp with the lRU attribute of the object and calculate how long it is currently inaccessible. For example, the result is 100 minutes, and then remove the configuration parameter lFU_decay_time. If this configuration is 1 by default, 100/1=100, It means no access for 100 minutes, so counter goes down by 100.

conclusion

This paper mainly introduces the Redis expired key processing strategy, and when the server memory is not enough Redis eight kinds of elimination strategy, and finally introduces two main elimination algorithm in Redis LRU and LFU.

Source: cnblogs.com/lonely-wolf/p/14403264.html