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 :
- Key expiration policy To prevent memory saturation .
- 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 :
- Randomly select from the set of expired keys 20 Key
- Delete the expired key
- 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 :
- 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 .
- 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 :
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 |
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).