Shulou(Shulou.com)06/01 Report--

This article mainly introduces the example analysis of expired key deletion strategy and data eviction strategy in Redis, which is very detailed and has a certain reference value. Interested friends must read it!

As a high-performance memory NoSQL database, the capacity of Redis is limited by the maximum memory limit.

When using Redis in a real production environment, you may occasionally feel that Redis takes up more memory than you expected. In fact, in addition to the overhead of saving key-value pairs, the memory consumed by Redis also has some additional memory generated by the runtime, including:

Space occupied by expired Key

Progressive Rehash causes space that is not deleted in time

Redis manages data, including underlying data structure overhead, client information, read and write buffers, etc.

Extra overhead for master-slave replication and bgsave

Redis progressive Rehash, when the author introduced the expansion of Concurrenthashmap, made a brief introduction, click to view

The master-slave copy of Redis is introduced in detail in another blog post of the author. Click to view

Therefore, this article will mainly focus on the recycling of expired Key.

Delete policy for expired keys

If a key in Redis is expired, it is not deleted from memory immediately after the expiration time, but uses three different deletion strategies:

Delete now

Lazy deletion

Scheduled deletion

Among them, the second is passive deletion, the first and third are active deletion, and the first is more real-time.

1. Delete now

Immediate deletion means that when the expiration time of the key is set, a callback event is created, and when the expiration time is reached, the key deletion operation is automatically performed by the time processor.

Deleting immediately ensures the maximum freshness of the data in memory, because it ensures that expired keys will be deleted immediately after expiration, and the memory they occupy will be released. But deleting immediately is the least friendly to cpu. Because the delete operation will take up the time of cpu, if it happens that cpu is doing sorting and other calculations, it will put additional pressure on cpu.

And the current redis event processor handles time events-unordered linked list, the time complexity of finding a key is O (n), so it is not suitable to deal with a large number of time events.

two。 Lazy deletion

Lazy deletion means that after a key value expires, the key value will not be deleted immediately, but will not be detected to expire until the next time it is used. So the disadvantage of lazy deletion is obvious: a waste of memory.

For example, some data that is updated by point in time, such as log logs, may not be accessed for a long period of time after expiration, so so much memory is wasted to store log during that time.

3. Scheduled deletion

From the above analysis, immediate deletion will take up a lot of cpu in a short time, while lazy deletion will waste memory over a period of time, so regular deletion is a compromise.

Scheduled deletion means that delete operations are performed at regular intervals, and the impact of deletion operations on cpu is reduced by limiting the length and frequency of deletion operations. On the other hand, timing deletion also effectively reduces the memory waste caused by lazy deletion.

Expired Key cleanup algorithm

The mechanism of Redis expired Key cleaning limits the frequency and maximum time of cleaning. In order to achieve the best performance of long-term service, the expired Key is cleaned without affecting the normal service as far as possible.

Redis will periodically randomly test a batch of key with expiration time set and process them. Expired key tested will be deleted. The specific algorithm is as follows:

The Redis configuration item hz defines the execution cycle of serverCron tasks, which defaults to 10, that is, CPU executes 10 times per second when idle

The cleaning time of each expired key does not exceed 25% of the CPU time, that is, if hz=1, the maximum cleaning time is 250ms, and if hz=10, the maximum cleaning time is 25ms.

Traverse all db in turn while cleaning

20 key are randomly selected from db to determine whether they are out of date, and if they are expired, they are expelled.

If more than 5 key expires, repeat step 4, otherwise traverse the next db

In the cleaning process, if the 25%CPU time is reached, exit the cleaning process

This is a simple algorithm based on probability. The basic assumption is that the extracted samples can represent the entire key space, and redis continues to clean up expired data until the percentage of key that is about to expire is reduced to less than 25%.

Because the algorithm adopts the method of randomly fetching key to determine whether it is expired or not, it is almost impossible to clean up all the expired Key.

Increasing the hz parameter can increase the frequency of cleaning, and the expired key can be deleted in a more timely manner, but too high Hz will increase the consumption of CPU time.

Data eviction strategy

In redis, users are allowed to set the maximum memory size maxmemory (to be used with maxmemory-policy), and a setting of 0 means no limit (default configuration). This value needs to be set in the production environment, preferably no more than 60% of memory, 70% of memory. When the redis in-memory dataset is approaching maxmemory, redis will implement the data elimination strategy.

Redis provides six data elimination strategies. In the eviction algorithm, according to the eviction strategy set by the user, the key to be expelled is selected until the current memory is less than the maximum memory value.

The optional eviction strategies are as follows:

Volatile-lru: select the least used data to be eliminated from datasets with an expiration time set

Volatile-ttl: select expired data to be eliminated from datasets with an expiration time set

Volatile-random: arbitrarily select data elimination from datasets with an expiration time set

Allkeys-lru: select the least used data from the dataset to be eliminated

Allkeys-random: data elimination by randomly selecting data from the dataset

No-enviction (expulsion): prohibition of eviction data

The default policy in redis2.8 is volatile-lru

The default policy in redis3.2 and redis4.0 is no-eviction

If you use no-eviction, Redis will return an error message of OOM when there is insufficient memory

(error) OOM command not allowed when used memory > 'maxmemory'.

When there is no key in the cache that meets the cleanup criteria, the recycling policies volatile-lru, volatile-random and volatile-ttl will directly return an error like the policy noeviction.

It is important to choose the right recycling strategy, depending on the access mode of your application. Use the INFO command output to monitor the number of cache hits and misses to tune the configuration of Redis.

The general rules are as follows:

If you expect a user to request a power-law distribution (power-law distribution), that is, when you expect some subset elements to be accessed much more than others, you can use the allkeys-lru policy.

If access is expected to be cyclical, all keys are scanned continuously, or requests are expected to be evenly distributed (each element is accessed with the same probability), the allkeys-random policy can be used.

If you want redis to use the TTL values set by cached objects to determine which objects should be good cleanup candidates, you can use the volatile-ttl policy.

The above is all the contents of this article entitled "example Analysis of expired key deletion Policy and data ejection Policy in Redis". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.