Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

Redis

Redis It's high performance, memory based NoSQL database . Because memory is a valuable resource , You can't use it without restrictions , therefore Redis Provides ：

1. Key expiration policy To prevent memory saturation .
2. Memory retirement strategy To make the memory saturated and continue to provide external services .

Memory expiration policy

expire command

Redis Provides expire Command to give a key (key) Set expiration time ：

redis> SET foo "bar"
"OK"
redis> EXPIRE foo 10
(integer) 1
redis> TTL foo
(integer) 10

similar setex command , You can also set the expiration time for the target key , But it's actually equivalent to set and expire Atomic operation of two commands . expire It only works on Redis The key , So there's no way to list perhaps set Set the expiration time for the element in . Call delete on a key (delete) Or rewrite (override) Such as del,set,getset after , Will clear the expiration time on the key ; call persist The command also clears the expiration time on the key ; The operation of modifying the key content is as follows incr,hset, Does not affect the expiration time of the key .

Key expiration principle

Redis There are two ways Keys expire ： Passive way (passive way) And the active way (active way).

Passive delete

When a key with an expiration time set is accessed , If it's found to be out of date ,Redis Will directly delete it and return a null value .

Active delete

Passive deletion is an inert deletion mechanism , It doesn't take a lot of time to delete keys , To ensure the Redis A high performance . But if the key is never accessed , Will cause a memory leak . therefore Redis Provides a proactive deletion strategy ：Redis Will regularly ( By default, every second 10 Time ) In the set of keys with expiration time set (expire set) in , Select a random number of keys , Judge to delete . The specific steps are as follows ：

1. Randomly select from the set of expired keys 20 Key
2. Delete the expired key
3. If the percentage of expired keys exceeds 25%, Then repeat the steps 1

The above steps will be in Redis Each (16 individual ) It's all executed in the database , And each execution is limited to a certain amount of time , Prevent taking up too much time to affect Redis Processing performance . It's a probability based compromise , It can prevent scanning too many expired keys Redis Throughput , At the same time, it also ensures that the expired key will not take up too much space .

Recovery and synchronization of expired data

Redis The expiration policy of is only executed in the master node , When a key expires , The master node will go to its replica node (replicas) Send a del command , This removes the data on the replica node , To ensure data consistency , meanwhile , I will go to aof Write a del command . stay Redis from aof In the process of recovery in the file , If a key is found to be out of date , It will be deleted directly . Allied , It's generating rdb When you file , If you find an expired key , The key will not be written to the snapshot file .

Be careful , The expiration time of a key is machine based unix Time stamp Of , So we must ensure the stability of machine time . For example, set the expiration time of a key to 1 Minutes later , At the same time, turn the machine time up 1 minute , Then the key will immediately be considered expired .

Redis The source code of the expiration policy is in here .

Memory retirement strategy

Even if a Key expiration policy , We will inevitably run out of memory ( Memory used is greater than the specified maxmemory). In order to make Redis Can continue to work ( Add data ), It triggers it Memory retirement strategy , To clear part of the existing data .

Redis4.0 Previous memory elimination strategy

Memory elimination strategy can be used maxmemory-policy To specify the , stay Redis4.0 The following methods have been provided before ：

• noeviction: Don't eliminate memory , When there is Redis Receive new write in On command , Direct return error ( Inquiry and del Except for orders )
• allkeys-lru: On all the keys , application LRU(less recently used) Strategy , That is to eliminate the least recently used keys
• volatile-lru: On the key with the expiration time set , application LRU Strategy , If the expired keyset is empty , And noeviction The strategy is the same
• allkeys-random: Random elimination of some keys
• volatile-random: Random elimination of keys with expiration time set , If the expired keyset is empty , And noeviction The strategy is the same
• volatile-ttl: Set the expiration time of the key , Try to eliminate TTL Smaller keys , That is, try to eliminate the expired keys , If the expired keyset is empty , And noeviction The strategy is the same

When the client sends a new insert command ,Redis By checking, it is found that the current memory consumption exceeds maxmemory, It will call the set memory elimination strategy to free up some memory space , Used to execute new commands .

LRU Algorithm

The precise LRU The algorithm will consume more memory , therefore Redis An approximation is used LRU Algorithm ： Sampling from a set , And eliminate the oldest data in the sample . Can pass maxmemory-samples( Default 5) Adjust the sample size to control LRU The accuracy of the algorithm .

Here is Redis in Object The definition of ：

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;

among lru It's used to record keys LRU Time field . The algorithm is to compare the value of this field to eliminate the old data in the sample .

The following pictures are from Redis Official website , It's theory LRU,Redis2.8 LRU 5samples,Redis3.0 LRU 5samples and Redis3.0 LRU 10samples A contrast to , You can see Redis3.0 LRU 10samples It's close to the theoretical accuracy .

LFU Strategy

If there's a key, it's rarely accessed , But it happened to be recently interviewed , according to LRU Strategy , It's not going to be cleared . therefore LRU It doesn't exactly describe the hot and cold of the bond . So , from 4.0 Version start ,Redis Provides a new algorithm ：LFU(Least Frequently Used). In this mode ,Redis Will record the access frequency of the key , The lower the frequency of access , The more likely it is to be cleared .

LFU It can also be targeted at allkeys and volatile：

• volatile-lfu: On the key with the expiration time set , application LFU Strategy .
• allkeys-lfu: On all the keys , application LRU Strategy , If the expired keyset is empty , And noeviction The strategy is the same .

LFU The algorithm uses a counter (probabilistic counter), Used to record the frequency at which keys are accessed ： When the key is accessed , The counter will go up ; At regular intervals , The counter is decremented . Actually, this counter , Still stored in redisObject Of lru Field , It records The last time the counter was decremented and The value of the counter Two messages . You can think of , There are two dimensions that can affect counters ：

1. The period of the counter decrement ： Periodic decrement can ensure the timeliness of the counter , And the guarantee value will not exceed the maximum length in the short term .
2. The speed at which the counter goes up ： in fact Redis Only to Access count Provides 8 position ( Range 0-255) Storage space , Therefore, it is necessary to control the increasing speed of the counter to play the role of each bit .

Correspondingly ,Redis These two dimensions provide lfu-log-factor( The default value is 10) and lfu-decay-time( The default value is 1) Two parameters to adjust the accuracy of the algorithm . The default value is based on experimental results , namely ： about 100 Ten thousand times After the request , The counter is at its maximum ; every other 1 minute , The counter is decremented once .lfu-decay-time Well understood. . about lfu-log-factor, You can refer to the following table ：

I've already introduced , The range of the counter is 0-255 Between (8bit Storage ), As you can see from the table , As the number of visits increases , The counter will grow slower ; When lfu-log-factor The smaller the value of , The faster the counter reaches its maximum 255. therefore , In fact, this parameter is used to control High frequency of visits And Low access frequency In this case, the accuracy of the algorithm is .

summary

As in memory database , Memory resources for Redis It's very valuable .Redis Adopted Access delete And Delete periodically There are two ways to deal with expiration (expired) data ; When the application memory reaches maxmemory when ,Redis Memory obsolescence policy will be enabled , There are two most commonly used algorithms ： Recently at least use (LRU) And the lowest frequency of visits (LFU).

Reference resources

how redis expires keys
Using Redis as an LRU cache