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

Preface

When Redis is used as a cache, memory consumption should be considered in some scenarios. Redis deletes expired keys to free up space. There are two strategies for deleting expired keys:

Lazy deletion: every time you get a key from the key space, check whether the obtained key expires, delete the key if it expires, and return the key if it does not expire. Delete regularly: every once in a while, the program checks the database and deletes the expired keys.

In addition, Redis can also turn on the LRU function to automatically eliminate some key-value pairs.

LRU algorithm

When we need to eliminate data from caching, we want to eliminate data that can no longer be used in the future and retain data that will be accessed frequently in the future, but the biggest problem is that caching does not predict the future. One solution is to predict through LRU: data that has recently been accessed frequently is more likely to be accessed in the future. The data in the cache generally has this access distribution: a part of the data has the vast majority of visits. When the access mode rarely changes, the last access time of each data can be recorded, and the data with the least idle time can be considered to be most likely to be accessed in the future.

For example, the following access mode: a visits every 5s, B visits every 2s, and C and D visit every 10s. | it represents the cut-off point for calculating idle time:

~ after a long period of time, please do not know what to do.

~ ~ Baking, Billing, Billing, Baking, Billing, Billing, Baking, Baking, Billing, Baking, Baking, Billing, Baking, Baking,

~ Cellular Centrum ~ |

~ D~D |

As you can see, LRU works well for A, B, and C, perfectly predicting the probability of being accessed in the future B > A > C, but predicting the least idle time for D.

However, on the whole, the LRU algorithm is already a good enough algorithm.

LRU configuration parameters

There are three LRU-related Redis configurations:

Maxmemory: when configuring Redis to store data, specify a limited amount of memory, such as 100m. When the memory consumed by the cache exceeds this value, data obsolescence will be triggered. When the data is configured to 0, there is no limit on the amount of data cached, that is, the LRU feature does not take effect. The default memory limit for a 64-bit system with a default value of 0732-bit is 3GBmaxmemory_policy: the elimination strategy after triggering data elimination maxmemory_samples: the accuracy of random sampling, that is, the number of key taken out immediately. The larger the value configuration, the closer to the real LRU algorithm, but the larger the value, the higher the corresponding consumption, which has a certain impact on performance, and the sample value defaults to 5.

Elimination strategy

There are several kinds of maxmemory_policy assignment in elimination strategy:

Noeviction: if the cached data exceeds the maxmemory limit, and the commands being executed by the client (most write instructions, with the exception of DEL and several instructions) will result in memory allocation Then return the error response allkeys-lru to the client: take LRU phase out volatile-lru for all keys: only for keys with expiration time set LRU phase out allkeys-random: randomly recycle all keys volatile-random: random recycle set expiration time key volatile-ttl: only eliminate keys with expiration time set-elimination survival time TTL (Time To Live) smaller keys

The three elimination strategies, volatile-lru, volatile-random and volatile-ttl, do not use full data and may not be able to phase out enough memory space. These three strategies are similar to noeviction in the absence of expired keys or keys that set the timeout property.

General rules of thumb:

Use allkeys-lru policy: you can choose this policy when you expect requests to conform to a power distribution (two-eight rule, etc.), such as when some subset elements are accessed more than others. Using allkeys-random: when continuously accessing all keys in a loop, or expecting an average distribution of requests (the probability of all elements being accessed is about the same) use volatile-ttl: to adopt this strategy, it is best to have differences in the TTL values of cache objects

Volatile-lru and volatile-random strategies are useful when you want to use a single Redis instance to achieve cache obsolescence and persist some frequently used key sets at the same time. Keys with no expiration time are persisted, and keys with expiration time are selected to participate in cache elimination. However, running two instances is generally a better way to solve this problem.

Setting the expiration time for a key also consumes memory, so using the allkeys-lru strategy saves more space because it allows you not to set the expiration time for the key.

Approximate LRU algorithm

We know that the LRU algorithm needs a two-way linked list to record the most recent access order of the data, but for the sake of memory saving, Redis's LRU algorithm is not a complete implementation. Instead of selecting the longest unaccessed keys for recycling, Redis tries to run an algorithm similar to LRU, sampling a small number of keys and then reclaiming the longest unaccessed keys. The accuracy of the algorithm can be adjusted by adjusting the number of samples maxmemory-samples for each collection.

According to the author of Redis, each Redis Object can squeeze out 24 bits of space, but 24 bits is not enough to store two pointers, and it is enough to store a low timestamp. Redis Object stores the unix time of new or updated objects in seconds, that is, it takes 194 days for LRU clock,24 bits data to overflow, and the cached data is updated very frequently, which is enough.

Redis's key space is placed in a hash table, and to select the longest unaccessed key from all the keys, another data structure is needed to store the source information, which is obviously not cost-effective. At first, Redis just randomly selected 3 key and then eliminated them. Later, the algorithm was improved to the strategy of N key, with a default of 5.

Redis3.0 then improves the performance of the algorithm by providing a pool of candidate key to be eliminated, with 16 key by default, sorted according to idle time. During the update, N key are randomly selected from the Redis key space, and their free time idle,key is calculated respectively. Idle,key will only enter pool when the pool is dissatisfied or when the idle time is greater than the minimum in the pool, and then select the key with the largest idle time from the pool to be eliminated.

The real LRU algorithm and the approximate LRU algorithm can be compared with the following images:

The light gray belt is the object that has been eliminated, the grey belt is the object that has not been eliminated, and the green belt is the newly added object. It can be seen that the effect of Redis 3.0is better than that of Redis 2.8when the maxmemory-samples value is 5. The approximate LRU algorithm using Redis 3.0 with 10 sample sizes is very close to the theoretical performance.

When the data access pattern is very close to the power distribution, that is, when most of the access is focused on partial keys, the LRU approximation algorithm will handle it well.

In the process of simulation experiment, we find that if we use the power distribution access mode, there is almost no difference between the real LRU algorithm and the approximate LRU algorithm.

LRU source code analysis

The keys and values in Redis are redisObject objects:

Typedef struct redisObject {unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; / * LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). * / int refcount; void * ptr;} robj

The low 24 bits lru of unsigned records the LRU time of redisObj.

When the Redis command accesses the cached data, the function lookupKey is called:

Robj * lookupKey (redisDb * db, robj * key, int flags) {dictEntry * de = dictFind (db- > dict,key- > ptr); if (de) {robj * val = dictGetVal (de); / * Update the access time for the ageing algorithm. * Don't do it if we have a saving child, as this will trigger * a copy on write madness. * / if (server.rdb_child_pid =-1 & & server.aof_child_pid = =-1 & &! (flags & LOOKUP_NOTOUCH)) {if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {updateLFU (val);} else {val- > lru = LRU_CLOCK ();} return val;} else {return NULL;}

When the policy is LRU (not LFU), this function updates the LRU value of the object and sets it to the LRU_CLOCK () value:

/ * Return the LRU clock, based on the clock resolution. This is a time * in a reduced-bits format that can be used to set and check the * object- > lru field of redisObject structures. * / unsigned int getLRUClock (void) {return (mstime () / LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;} / * This function is used to obtain the current LRU clock. * If the current resolution is lower than the frequency we refresh the * LRU clock (as it should be in production servers) we return the * precomputed value, otherwise we need to resort to a system call. * / unsigned int LRU_CLOCK (void) {unsigned int lruclock; if (1000/server.hz cmd- > flags & CMD_DENYOOM | | (c-> flags & CLIENT_MULTI & & c-> cmd- > proc! = execCommand)) {flagTransaction (c); addReply (c, shared.oomerr); return paid OK;}

Only the part that frees the memory space is listed. FreeMemoryIfNeededAndSafe is the function that frees memory:

Int freeMemoryIfNeeded (void) {/ * By default replicas should ignore maxmemory * and just be masters exact copies. * / if (server.masterhost & & server.repl_slave_ignore_maxmemory) return Cleavok; size_t mem_reported, mem_tofree, mem_freed; mstime_t latency, eviction_latency; long long delta; int slaves = listLength (server.slaves); / * When clients are paused the dataset should be static not just from the * POV of clients not being able to write, but also from the POV of * expires and evictions of keys not being performed. * / if (clientsArePaused ()) return Cleavok; if (getMaxmemoryState (& mem_reported,NULL,&mem_tofree,NULL) = = C_OK) return ClearOK; mem_freed = 0; if (server.maxmemory_policy = = MAXMEMORY_NO_EVICTION) goto cant_free; / * We need tofree memory, but policy forbids. * / latencyStartMonitor (latency); while (mem_freed)

< mem_tofree) { int j, k, i, keys_freed = 0; static unsigned int next_db = 0; sds bestkey = NULL; int bestdbid; redisDb *db; dict *dict; dictEntry *de; if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) || server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { struct evictionPoolEntry *pool = EvictionPoolLRU; while(bestkey == NULL) { unsigned long total_keys = 0, keys; /* We don't want to make local-db choices when expiring keys, * so to start populate the eviction pool sampling keys from * every DB. */ for (i = 0; i < server.dbnum; i++) { db = server.db+i; dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ? db->

Dict: db- > expires; if ((keys = dictSize (dict))! = 0) {evictionPoolPopulate (I, dict, db- > dict, pool); total_keys + = keys;}} if (! total_keys) break; / * No keys to evict. * / * Go backward from best to worst element to evict * / for (k = EVPOOL_SIZE-1; k > = 0; KMui -) {if (pool [k] .key = = NULL) continue; bestdbid = pool [k] .dbid; if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {de = dictFind (server.b [pool.dbid] .dict, pool [k] .key) } else {de = dictFind (server.db[ Pool [k] .dbid] .expires, Pool [k] .key);} / * Remove the entry from the pool. * / if (pool [k] .key! = pool [k] .cached) sdsfree (pool [k] .key); pool [k] .key = NULL; pool [k] .pole = 0; / * If the key exists, is our pick. Otherwise it is * a ghost and we need to try the next element. * / if (de) {bestkey = dictGetKey (de); break;} else {/ * Ghost... Iterate again. * /}} / * volatile-random and allkeys-random policy * / else if (server.maxmemory_policy = = MAXMEMORY_ALLKEYS_RANDOM | | server.maxmemory_policy = = MAXMEMORY_VOLATILE_RANDOM) {/ * When evicting a random key, we try to evict a key for * each DB, so we use the static 'next_db' variable to * incrementally visit all DBs. * / for (I = 0; I

< server.dbnum; i++) { j = (++next_db) % server.dbnum; db = server.db+j; dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ? db->

Dict: db- > expires; if (dictSize (dict)! = 0) {de = dictGetRandomKey (dict); bestkey = dictGetKey (de); bestdbid = j; break;}} / * Finally remove the selected key. * / if (bestkey) {db = server.db+bestdbid; robj * keyobj = createStringObject (bestkey,sdslen (bestkey)); propagateExpire (db,keyobj,server.lazyfree_lazy_eviction); / * We compute the amount of memory freed by db*Delete () 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. * / delta = (long long) zmalloc_used_memory (); latencyStartMonitor (eviction_latency); if (server.lazyfree_lazy_eviction) dbAsyncDelete (db,keyobj); else dbSyncDelete (db,keyobj); latencyEndMonitor (eviction_latency); latencyAddSampleIfNeeded ("eviction-del", eviction_latency); latencyRemoveNestedEvent (latency,eviction_latency); delta-= (long long) zmalloc_used_memory (); mem_freed + = delta; server.stat_evictedkeys++ NotifyKeyspaceEvent (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 (); / * Normally our stop condition is the ability to release * a fixed, pre-computed amount of memory. However when we * are deleting objects in another thread, it's better to * check, from time to time, if we already reached our target * memory, since the "mem_freed" amount is computed only * across the dbAsyncDelete () call, while the thread can * release the memory all the time. * / if (server.lazyfree_lazy_eviction & &! (keys_freed% 16) {if (getMaxmemoryState (NULL,NULL,NULL,NULL) = = C_OK) {/ * Let's satisfy our stop condition. * / mem_freed = mem_tofree;} if (! keys_freed) {latencyEndMonitor (latency); latencyAddSampleIfNeeded ("eviction-cycle", latency); goto cant_free; / * nothing to free... * /}} latencyEndMonitor (latency); latencyAddSampleIfNeeded ("eviction-cycle", latency); return Cruise OKscape cantonal free: / * We are here if we are not able to reclaim memory. There is only one * last thing we can try: check if the lazyfree thread has jobs in queue * and wait... * / while (bioPendingJobsOfType (BIO_LAZY_FREE)) {if (mem_reported-zmalloc_used_memory ()) + mem_freed) > = mem_tofree) break; usleep (1000);} return Clearer;} / * This is a wrapper for freeMemoryIfNeeded () that only really calls the * function if right now there are the conditions to do so safely: * *-There must be no script in timeout condition. *-Nor we are loading data right now. * * / int freeMemoryIfNeededAndSafe (void) {if (server.lua_timedout | | server.loading) return Cellular OK; return freeMemoryIfNeeded ();}

Several elimination strategies maxmemory_policy are implemented in this function.

When using LRU, you can see that starting from database 0 (default 16), select dict (all keys) or expires (keys with expiration time) of redisDb according to different policies. The pool,pool update policy for the candidate key pool is evictionPoolPopulate:

Void evictionPoolPopulate (int dbid, dict * sampledict, dict * keydict, struct evictionPoolEntry * pool) {int j, k, count; dictEntry * samples [server.maxmemory _ samples]; count = dictGetSomeKeys (sampledict,samples,server.maxmemory_samples); for (j = 0; j)

< count; j++) { unsigned long long idle; sds key; robj *o; dictEntry *de; de = samples[j]; key = dictGetKey(de); /* If the dictionary we are sampling from is not the main * dictionary (but the expires one) we need to lookup the key * again in the key dictionary to obtain the value object. */ if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) { if (sampledict != keydict) de = dictFind(keydict, key); o = dictGetVal(de); } /* Calculate the idle time according to the policy. This is called * idle just because the code initially handled LRU, but is in fact * just a score where an higher score means better candidate. */ if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) { idle = estimateObjectIdleTime(o); } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { /* When we use an LRU policy, we sort the keys by idle time * so that we expire keys starting from greater idle time. * However when the policy is an LFU one, we have a frequency * estimation, and we want to evict keys with lower frequency * first. So inside the pool we put objects using the inverted * frequency subtracting the actual frequency to the maximum * frequency of 255. */ idle = 255-LFUDecrAndReturn(o); } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { /* In this case the sooner the expire the better. */ idle = ULLONG_MAX - (long)dictGetVal(de); } else { serverPanic("Unknown eviction policy in evictionPoolPopulate()"); } /* Insert the element inside the pool. * First, find the first empty bucket or the first populated * bucket that has an idle time smaller than our idle time. */ k = 0; while (k < EVPOOL_SIZE && pool[k].key && pool[k].idle < idle) k++; if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) { /* Can't insert if the element is < the worst element we have * and there are no empty buckets. */ continue; } else if (k < EVPOOL_SIZE && pool[k].key == NULL) { /* Inserting into empty position. No setup needed before insert. */ } else { /* Inserting in the middle. Now k points to the first element * greater than the element to insert. */ if (pool[EVPOOL_SIZE-1].key == NULL) { /* Free space on the right? Insert at k shifting * all the elements from k to end to the right. */ /* Save SDS before overwriting. */ sds cached = pool[EVPOOL_SIZE-1].cached; memmove(pool+k+1,pool+k, sizeof(pool[0])*(EVPOOL_SIZE-k-1)); pool[k].cached = cached; } else { /* No free space on right? Insert at k-1 */ k--; /* Shift all elements on the left of k (included) to the * left, so we discard the element with smaller idle time. */ sds cached = pool[0].cached; /* Save SDS before overwriting. */ if (pool[0].key != pool[0].cached) sdsfree(pool[0].key); memmove(pool,pool+1,sizeof(pool[0])*k); pool[k].cached = cached; } } /* Try to reuse the cached SDS string allocated in the pool entry, * because allocating and deallocating this object is costly * (according to the profiler, not my fantasy. Remember: * premature optimizbla bla bla bla. */ int klen = sdslen(key); if (klen >

EVPOOL_CACHED_SDS_SIZE) {pool [k] .key = sdsdup (key);} else {pool (pool [k] .cached, key,klen+1); sdssetlen (pool [k] .cached, klen); pool [k] .key = pool [k] .cached;} pool [k] .pool [k] .dbid = dbid;}

Redis randomly selects the key of the number of maxmemory_samples, then calculates the idle time idle time of these key, and can enter the pool when the condition is met (which is greater than the idle time of some keys in pool). After the pool update, the keys with the most idle time in the pool are eliminated.

EstimateObjectIdleTime is used to calculate the idle time of the Redis object:

/ * Given an object returns the min number of milliseconds the object was never * requested, using an approximated LRU algorithm. * / unsigned long long estimateObjectIdleTime (robj * o) {unsigned long long lruclock = LRU_CLOCK (); if (lruclock > = o-> lru) {return (lruclock-o-> lru) * LRU_CLOCK_RESOLUTION;} else {return (lruclock + (LRU_CLOCK_MAX-o-> lru)) * LRU_CLOCK_RESOLUTION;}}

Idle time is basically the difference between the object's lru and the global LRU_CLOCK () multiplied by the precision LRU_CLOCK_RESOLUTION, converting seconds into milliseconds.

Reference link

Random notes on improving the Redis LRU algorithmUsing Redis as an LRU cache

Summary

The above is the whole content of this article. I hope the content of this article has a certain reference and learning value for everyone's study or work. Thank you for your support.

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.