About the implementation of redis Key elimination strategy
- 2020-05-27 07:32:56
- OfStack
1 the maximum memory deletion policy in the configuration file
In the redis configuration file, you can set the maximum memory usage for redis, and when redis reaches its maximum memory usage (how do you know when it has reached its maximum?). , redis will select the key to be deleted according to the policy in the configuration file, and delete the values of key-value. If according to the configured policy, there is no key that conforms to the policy, that is to say, the memory is no longer able to accommodate the new key-value, but at this time, key cannot be deleted, then a write error will occur if it is written at this time.
1.1 setting of maximum memory parameters
If the maxmemory parameter is set to 0, there are two cases:
* on 64-bit systems, there is no limit.
* on a 32-bit system, it is 3G. According to the official redis documentation, the maximum memory of a 32-bit system is 4G, with 1G reserved for the system. And the policy is automatically set to noeviction.
That is to say, on a 32-bit system, if maxmemory is set to 0, it defaults to 3G. When it reaches 3G and writes to reidis, it will report an error.
1.2 several strategies for removing key when the maximum memory is reached
* volatile-lru -
>
remove the key with an expire set using an LRU algorithm
Select according to the LRU algorithm (not used recently at least), and delete the key that has the expire time set.
* allkeys-lru -
>
remove any key accordingly to the LRU algorithm
According to the LRU algorithm, delete any key. Whether or not this key has an expire time set.
* volatile-random -
>
remove a random key with an expire set
Randomly delete 1 key with expire time set.
* allkeys-random -
>
remove a random key, any key
Randomly delete any 1 key, regardless of whether the key has expire time set or not.
* volatile-ttl -
>
remove the key with the nearest expire time (minor TTL)
Delete key with the most recent termination time value (TTL).
* noeviction -
>
don't expire at all, just return an error on write operations
If no termination time is set, 1 error is returned.
1.3 configure the maximum memory policy
The default policy for these commands is: volatile-lru
# At the date of writing this commands are: set setnx setex append
# incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
# sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
# zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
# getset mset msetnx exec sort
#
# The default is:
# maxmemory-policy volatile-lru
1.4 configure the number of test samples to delete key
maxmemory-samples
Since both the LRU and minimum TTL algorithms are not exact algorithms. So you can choose how many samples you want to test. For example, by default redis will check for three key and select one of the three key that has not been used recently. Of course you can change the value of the number of samples you check.
To modify this value, you can set the parameters in the configuration file:
maxmemory-samples 3
2 implementation
The implementation of these deletion strategies is done in the function freeMemoryIfNeeded(void). Here's how each strategy is implemented.
2.1 when to delete key-value
When will maxmemory-policy policy be set, when will key be deleted?
In fact, when the maxmemory parameter is set, the corresponding key value will be deleted according to maxmemory-policy when processing each command.
The code is as follows:
// This function is called for each command that processes the client
int processCommand(redisClient *c) {
... ...
/* Handle the maxmemory directive.
*
* First we try to free some memory if possible (if there are volatile
* keys in the dataset). If there are not the only thing we can do
* is returning an error. */
// The above meaning is: if there can be deleted key And the release of the 1 Some memory, if not present, is returned to the client 1 A mistake.
if (server.maxmemory) { // if maxmemory Don't for 0 , then the following function is called to release it 1 some key
int retval = freeMemoryIfNeeded(); // Delete according to configuration policy key
if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) { // If there is an error, the processing command is terminated and the error is returned to the client
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
... ...
}
Practice 1: if the maxmemory variable is not set, maxmemory-policy will not work.
Practice 2: if the maxmemory variable is not set, the release policy will not be invoked when the command is processed, which will speed up the processing of the command.
2.2 delete the overall process of key
When the maximum memory is reached, the old key needs to be deleted according to the policy. All the deletion operations and the implementation of the deletion policy are implemented in the function freeMemoryIfNeeded().
Before executing the delete policy, select db and look for key.
The general steps are as follows:
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
mstime_t latency;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = zmalloc_used_memory();
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) {
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */
// Check if the current system exceeds the memory limit
if (mem_used <= server.maxmemory) return REDIS_OK;
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR; /* We need to free memory, but policy forbids. */
/* Compute how much memory we need to free. */
mem_tofree = mem_used - server.maxmemory;
mem_freed = 0;
latencyStartMonitor(latency);
while (mem_freed < mem_tofree) {
int j, k, keys_freed = 0;
// traverse 16 A database
for (j = 0; j < server.dbnum; j++) {
long bestval = 0; /* just to prevent warning */
sds bestkey = NULL;
struct dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
// Notice here, if ALLKEYS_xx The policy is directly in the corresponding library structure dict Look for key .
// If you are ALLKEYS_xx Strategy, which means maybe volatile-xxx The library structure of the operation will be set to expires Structure.
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
// If you set up
dict = server.db[j].dict;
} else {
dict = server.db[j].expires;
}
// If the size of the database is 0 , indicating no key Exist, continue next 1 Looking in a database
if (dictSize(dict) == 0) continue;
... ...
}2.2 implementation of volatile-lru mechanism and allkeys-lru
2.2.1 LRU mechanism in redis
As for the LRU mechanism, redis's official documentation explains it as follows:
Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
However since Redis 3.0 (that is currently in beta) the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.
What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:
maxmemory-samples 5
The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.
redis's LRU algorithm is not really LRU. It is implemented in another way. This means that redis does not always select the best key to delete. The reason for not using the true LRU algorithm is that it may consume more memory. The algorithm is about the same as the real LRU algorithm.
redis is to select the best key to delete from a small part of key. The number of key in this part can be specified, and the parameter maxmemory-samples can be set in the configuration file.
2.2.2 implementation of LRU mechanism
The freeMemoryIfNeeded() function first calculates the difference between the maximum free memory and the memory currently in use. If this is not enough, the old key-value is released.
If the LRU policy is used, the following code will be used to select the optimal deletion of key, and then the deletion operation will be carried out:
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
mstime_t latency;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = zmalloc_used_memory(); // Calculate the amount of memory currently in use, to exclude slave and AOF The use of buffer The size of the
if (slaves) { // traverse slaves Linked lists, minus slave The amount of memory used
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) { // Minus the AOF Memory size used
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */ // Check to see if the set memory limit has been reached
if (mem_used <= server.maxmemory) return REDIS_OK;
// Unfreed memory
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR; /* We need to free memory, but policy forbids. */
/* Compute how much memory we need to free. */ // Calculate the amount of memory to be released
mem_tofree = mem_used - server.maxmemory;
mem_freed = 0;
latencyStartMonitor(latency);
while (mem_freed < mem_tofree) { // The amount of memory that has been freed is less than the amount to be freed
int j, k, keys_freed = 0;
for (j = 0; j < server.dbnum; j++) { // Traverse all databases to free up memory
long bestval = 0; /* just to prevent warning */
sds bestkey = NULL;
struct dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
// this 1 Step to select out the value of the database dict
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{ // if maxmemory-policy The value is LRU or RANDOM , directly in the main database for elimination
dict = server.db[j].dict;
} else { // Other policies where the termination time has been set key Eliminate in the middle.
dict = server.db[j].expires;
}
if (dictSize(dict) == 0) continue; // There is no data skipping in the current database
/* volatile-random and allkeys-random policy */ // if RANDOM In the strategy 1 a
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
de = dictGetRandomKey(dict);
bestkey = dictGetKey(de);
}
/* volatile-lru and allkeys-lru policy */// If the delete policy is LRU In the strategy 1 a
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
// According to the configuration file maxmemory_samples The value of the decision to make a few selections to delete key From these key You pick it out.
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
// Randomly selected from the library 1 a key-value structure (dictEntry type ) The nodes of the
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de); // // Get from this node key String address of
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
// If the maximum memory deletion policy is volatile-lru Is required from db Look for thiskey .
// if VOLATILE-xx Policy, then the storage structure of the currently operating library is expires , at this point need from dict Found in the key
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
// To obtain key de the value value
o = dictGetVal(de);
// Look at the key The rest of your life
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
// Each time from the traversal of a few Key selected lru One of the longest key .
// So how do you update key the lru Value? Every time I look for the key It will be updated when key the lru Value, which is the timestamp of the system.
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
/* volatile-ttl */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
thisval = (long) dictGetVal(de);
/* Expire sooner (minor expire unix timestamp) is better
* candidate for deletion */
if (bestkey == NULL || thisval < bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
... ...
// So if I go here, I'm going to delete the optimal key It's been selected. Now enter the delete phase.
// Whatever the strategy, as long as the best is chosen key , the following deletion process will be executed.
/* Finally remove the selected key. */
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj);
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can't account for
* that otherwise we would never exit the loop.
*
* AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// To remove the bestkey The corresponding key-value Value. Notice that you have to follow both dict Delete from, and also from expires Removed.
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
keyobj, db->id);
decrRefCount(keyobj);
keys_freed++;
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
if (slaves) flushSlavesOutputBuffers();
}
}
if (!keys_freed) {
latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return REDIS_ERR; /* nothing to free... */
}
}
latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return REDIS_OK;
}