Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1, the introduction of

An obvious drawback of LRU is that it cannot correctly represent the heat of a Key. If a Key is never accessed, but only accessed by a user shortly before memory flushing occurs, this is considered a hot Key in the LRU algorithm. For example, both keyA and keyB are set to Redis at the same time. Before memory flushing occurs, keyA is frequently accessed, while keyB is only accessed once. However, this access time is closer to the memory flushing trigger time than any other access time of keyA. If both keyA and keyB are selected by Redis, keyA is preferred. I don’t think anyone wants keyA to be obsolete, so is there a better memory elimination mechanism? Of course there is. That’s LFU. \

LFU(Least Frequently Used) is an elimination algorithm introduced in Redis 4.0. It eliminates keys by comparing their access frequency, and the most Frequently Used is Frequently Used.

Differences between LRU and LFU:

  • LRU -> Recently Used, based on the time of the last visit
  • LFU -> Frequently Used, compared by key access frequency

Since Redis4.0 two LFU modes have been added to the MaxMemory_policy elimination policy (LRU see my last article) :

  • Volatile – LFU: LFU is used to eliminate keys with expiration time
  • Allkeys-lfu: adopts the lfu elimination algorithm for allkeys

2. Implementation method

The minimum space footprint for Redis to allocate a string is 19 bytes, 16 bytes (object header) +3 bytes (SDS base field). Redis memory elimination algorithm LRU/LFU is implemented by LRU in the object header. Redis object header memory structure:

typedef struct redisObject { unsigned type:4; // 4 bits object type (zset, set, hash, etc.) unsigned Encoding :4; Unsigned lRU :24; // The storage mode of the 4 bits object (ziplist, intset, etc.) // 24bits Record object access information int refcount; // 4 bytes reference count void * PTR; // 8 bytes (64-bit OS), pointing to the object's specific storage address/object body}Copy the code

The LRU field in the Redis object header is used differently in LRU mode than in LFU mode.

2.1 LRU implementation

In LRU mode, the LRU field stores the clock server. Lrulock of Redis when the key is accessed. When a key is accessed, Redis updates the value of the LRU field in the key’s object header. Therefore, in LRU mode, Redis can compare the last access time of the key based on the value recorded in the LRU field in the object header.

To demonstrate a simple Redis-LRU algorithm in Java code:

  • Redis object head
package com.lizba.redis.lru; / * * * < p > head * * Redis object < / p > * * @ Author: Liziba * @ the Date: 2021/9/22 22:40 */ public class RedisHead {/** private Long lru; /** private Object body; public RedisHead setLru(Long lru) { this.lru = lru; return this; } public RedisHead setBody(Object body) { this.body = body; return this; } public Long getLru() { return lru; } public Object getBody() { return body; }}Copy the code
  • Redis LRU implementation code
package com.lizba.redis.lru; import java.util.Comparator; import java.util.List; import java.util.concurrent.ConcurrentHashMap; import java.util.stream.Collectors; /** * <p> ** @author: Liziba * @date: 2021/9/22 22:36 */ public class RedisLruDemo {/** * private ConcurrentHashMap<String, RedisHead> cache; /** * Private int initialCapacity; public RedisLruDemo(int initialCapacity) { this.initialCapacity = initialCapacity; this.cache = new ConcurrentHashMap<>(initialCapacity); ; } /** * LRU ** @param key * @param body */ public void set(String key, Object body) {synchronized (redislrudemo.class) {if (! cache.containsKey(key) && cache.size() >= initialCapacity) { this.flushLruKey(); } } RedisHead obj = this.getRedisHead().setBody(body).setLru(System.currentTimeMillis()); cache.put(key, obj); LRU ** @param key * @return */ public Object get(String key) {RedisHead result = null; if (cache.containsKey(key)) { result = cache.get(key); result.setLru(System.currentTimeMillis()); } return result; Private void flushLruKey() {List<String> sortData = cache.keyset ().stream() .sorted(Comparator.comparing(key -> cache.get(key).getLru())) .collect(Collectors.toList()); String removeKey = sortData.get(0); System.out.println(" discard -> "+ "lru:" + "cache.get(removeKey).getlru () +" body: "+ cache.get(removeKey).getbody ()); cache.remove(removeKey); if (cache.size() >= initialCapacity) { this.flushLruKey(); } return; Public List<RedisHead> getAll() {return cache.keyset ().stream().map(key ->); cache.get(key)).collect(Collectors.toList()); } private RedisHead getRedisHead() { return new RedisHead(); }}Copy the code
  • The test code
package com.lizba.redis.lru; import java.util.Random; import java.util.concurrent.TimeUnit; / test LRU * * * * < p > * < / p > * * @ Author: Liziba * @ the Date: 2021/9/22 22:51 */ public class TestRedisLruDemo { public static void main(String[] args) throws InterruptedException { RedisLruDemo demo = new RedisLruDemo(10); For (int I = 0; int I = 0; i < 10; i++) { demo.set(i + "", i); } for (int I = 0; i < 20; i++) { int nextInt = new Random().nextInt(10); TimeUnit.SECONDS.sleep(1); demo.get(nextInt + ""); } for (int I = 10; i < 15; i++) { demo.set(i + "", i); } System.out.println("-------------------------------------------"); ForEach (redisHead -> system.out.println (" rest -> "+ "lru:" + redishead.getlru () + "body: " + redisHead.getBody())); }}Copy the code
  • The test results

2.2 LFU Implementation Mode

In LFU mode, the 24bit LRU field of the Redis object header is split into two segments for storage. The higher 16bit stores Last Decrement Time (LDT) and the lower 8bit stores LogC (Logistic Counter). \


​

2.2.1 LDT (Last Decrement Time)

The high 16bit is used to record the time of the last decrement of the counter. Since there are only 8 bits, the storage is Unix minute timestamp 2^16. The 16 bits can represent the maximum value of 65535 (655/24/60 ≈45.5), and about 45.5 days will be returned (retracting refers to the value after the module is reset from 0).

Last Decrement Time calculation algorithm

/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) For the LFU implementation. */ // server. Unixtime is Redis. Unsigned Long LFUGetTimeInMinutes(void) {return (server.unixtime/60) & 65535; } /* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */ unsigned long LFUTimeElapsed(unsigned Long LDT) {// Get the current LFU time unsigned long now = LFUGetTimeInMinutes(); // If (now >= LDT) return now-ldt; Return 65535- LDT +now; return 65535- LDT +now; return 65535- LDT +now; }Copy the code

2.2.2 logc (Logistic Counter)

The lower 8 bits are used to record the number of Rediskey accesses. The maximum number of Rediskey accesses is 255. The logC value for each new key is 5 (LFU_INITI_VAL). This ensures that new values are not selected first; Logc is updated every time the key is accessed; In addition, logC decays over time.

2.2.3 LogC Algorithm Adjustment

Redis.conf provides two configuration items to adjust the LFU algorithm to control the growth and decay of Logistic Counter. \

  • Lfu-log-factor is used to adjust the growth rate of Logistic Counter. The larger the value of Lfu-log-factor is, the slower the growth rate of Logistic Counter is.

Redis Logistic Counter growth source code:

/* Logarithmically increment a counter. The greater is the current counter value * the less likely is that it gets */ uint8_t LFULogIncr(uint8_t counter) {// Logistic counter Max is 255 if (counter) == 255) return 255; R double r = (double)rand()/RAND_MAX; // counter minus LFU_INIT_VAL (LFU_INIT_VAL is the initial Logistic counter value for each key, defaults to 5) double baseval = counter -lfu_init_val; If (baseval < 0) baseval = 0; if (baseval < 0) baseval = 0; // lfu-log-factor is used here // It can be seen that if lfu_log_factor is larger, p is smaller // the probability of r < p is smaller, Double p = 1.0/(baseval*server.lfu_log_factor+1); if (r < p) counter++; return counter; }Copy the code

The following is the change data of Logistic Counter of key with the increase of access times under different values of lfu-log-factor provided by the official website: \

  • Lfu-decay-time is used to adjust the decay rate of Logistic Counter. It is a value in minutes and the default value is 1. The larger the value of lfu-decay-time is, the slower the decay is.

Redis Logistic Counter attenuation source code:

/* If the object decrement time is reached decrement the LFU counter but * do not update LFU fields of the object, we update the access time * and counter in an explicit way when the object is really accessed. * And we will times halve  the counter according to the times of * elapsed time than server.lfu_decay_time. * Return the object frequency counter.  * * This function is used in order to scan the dataset for the best object * to fit: as we check for the candidate, we incrementally decrement the * counter of the scanned objects if needed. */ unsigned long LFUDecrAndReturn(robj *o) { Unsigned long LDT = o->lru >> 8; Logc unsigned long counter = o-> 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; }Copy the code

2.2.4 LFU optimization

LFU and LRU have one thing in common. When the memory reaches max_memory, the key selection is randomly grasped. Therefore, Redis designs an elimination pool to make this randomness more accurate. Redis 3.0 optimizes this one (from Redis. IO) : \

3. Use of LFU

3.1 Configuration File Enable the LFU elimination algorithm

Conf file and set maxmemory-policy volatile-lfu/allkeys-lfu\

Restart Redis and the connected client will view configuration information \ for maxmemory_policy through the info command

Get the Logistic Counter value \ of the LFU of the object via the object freq key