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

This article mainly explains "what is Redis-LFU". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is Redis-LFU".

LFU is an elimination strategy used in redis, of course, the implementation of redis is very clever, its full name is Least Frequently Used, that is, it is eliminated with less use. It is more accurate than LRU (you can learn it by yourself, and later articles will supplement it). By reading the redis-related source code (version:6.2), we find that the robj * lookupKey (redisDb * db, robj * key, int flags) function is called every time you operate db. This function is implemented in this way.

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 (! hasActiveChildProcess () & &! (flags & LOOKUP_NOTOUCH)) {if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {updateLFU (val);} else {val- > lru = LRU_CLOCK ();}} return val;} else {return NULL;}}

When the key is found in the dictionary & when it does not open a child thread to do the saving operation & with the maximum memory strategy & MAXMEMORY_FLAG_LFU, it will updateLFU. Let's see how the updateLFU function is implemented. Let's start with the code:

Void updateLFU (robj * val) {unsigned long counter = LFUDecrAndReturn (val); counter = LFULogIncr (counter); val- > lru = (LFUGetTimeInMinutes () lru & 255; unsigned long num_periods = server.lfu_decay_time? LFUTimeElapsed (ldt) / server.lfu_decay_time: 0; if (num_periods) counter = (num_periods > counter)? 0: counter-num_periods; return counter;}

The first line in the method

Unsigned long ldt = o-> lru > > 8

This is to calculate the time of the last visit, and some people here may ask why you moved 8bit to the right because the 8 bits on the right are counter and have to be moved out in order to get time. If you can't figure it out if you can't move left and right now, review and review.

Line 2

Unsigned long counter = o-> lru & 255

This will figure out that counter,&255 just turns the previous 16bit into zero. In the same way, if you don't understand & now, please review.

Line 3

Unsigned long num_periods = server. Lfu_decay_time? LFUTimeElapsed (ldt) / server. Lfu_decay_time: 0

Its function is to calculate the decreasing num,lfu_decay_time represents the lfu decline factor, and the function of LFUTimeElaspsed is to calculate the difference between the current now and the last visit, that is, how long it has not been accessed. Then / decrement factor, figure out how much you need to decrement counter.

Last

If (num_periods)

Counter = (num_periods > counter)? 0: counter-num_periods

Return counter

Figure out the counter.

2.counter first do decrement, and then do increment, on the code, specific explanation, just look at my comments

Void updateLFU (robj * val) {unsigned long counter = LFUDecrAndReturn (val); / / decreasing operation counter = LFULogIncr (counter); / / increasing operation val- > lru = (LFUGetTimeInMinutes () encoding = OBJ_ENCODING_RAW; o-> ptr = ptr; o-> refcount = 1; / * Set the LRU to the current lruclock (minutes resolution), or * alternatively the LFU counter. * / if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {/ / when the maximum memory policy and LFU are set, go LFU o-> lru = (LFUGetTimeInMinutes ())

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.