LRU and LFU in Redis memory eviction

Redis supports several memory eviction policies to limit the memory usage amounts. Two of them are the LRU based and LFU based algorithms, I want to write some stuffs to express my insights (or the source code analysis? Whatever.) about them. You can look through the bundled redis.conf file to learn all memory eviction policies details. It’s just my random note so feel free to rectify my faults!

The LRU algorithm in Redis, is somewhat different from my intutive understanding. I have some Nginx modules development experiences, so I’m familiar with Nginx’s LRU use and implementation. Basically your node (object) should contain a field to mark its position in the LRU queue and whenever the node is accessed, it will be moved to the queue head, which means it was used recently. You might have guessed the eviction process: iterating objects from the tail of queue and free some of them. Frankly I think this pattern is good enough in most cases despite the queue is fat. The LRU implementation in Redis is totally different, each object only uses 24 bits (3 octets) to store the LRU clock, in contrast, the traditional LRU queue occupies at least 16 bytes(two pointers, next and prev). It’s space effective from this point of view, though 24 bits is narrow, it still can hold 194 days, and Redis handles overflow carefully. Each object’s LRU clock is updated when they are touched, to avoid too many system calls, the LRU clock was pre-computed with a settled frequency (1000/server.hz ). Basically we use this pre-computed value is enough as long as the LRU clock resolution isn’t precise overly.

robj *lookupKey(redisDb, robj *key, int flags) {
    ...

    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();
         }
    }
}

unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        lruclock = server.lruclock;
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

getLRUClock is trivial which just resorts the system call and return its least 24 significant bits.

So how Redis evicts keys to reduce the memory usage? Now you don’t have a global LRU queue to eliminate the least recent used keys easily. Redis uses a eviction pool (actually a linked list) and populates it by some random keys, this pool is monotonous, the first node in the pool has the least idle time, the last one has the maximum idle time. Coming key will be inserted at the suitable position according to the idle time. For now, the pool size is hardcoded by 16. After this step, Redis will pick a best key from the end of pool and delete this key. This process will be repeated until the memory usage is under the limitation.

The other way, LFU, is added to Redis newly, it traces each object’s access counter and evicts keys according the counter. You may think it’s naive and I just need to accumulate the counter whenever the object is touched, reducing the counter after a period. What’s amazing in Redis is that it just reuses the 24bits LRU clock space, so how can I maintain the counter and decay time (or the period) in just 3 octets? The way is neat and I have to admit that I cannot create this pattern, at least for now.

Redis splits the 24 bits into 2 parts, the most 16 significant bits are used to store its last decay time; the least 8 significant bits are the space of counter, but are you kidding me? What can I exercise this poor 8 bits? Well, the counter, actually is a logarithmic counter, you know 2^255 is large enough and enough and enough, it’s not hard to guess the algorithm is not precise so much but as we all know Redis is pragmatic, so as long as it works well, it’s worthwhile. The counter updating logic is also probabilistic:

uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

After glancing the above codes, you can easily see that the greater counter is, the smaller the probability to increse the counter. You can see the statistic in redis.conf to learn its performance.

The decay time, determining the period that counter need to be havled. This is imperative otherwise the counter will converge to 255 and never regress, this ofcourse will influence the memory eviction mechanics.

So which strategy should I use? You may need to ask yourself, what is my business? can I bear any data loss? If not, you even cannot use any memory eviction policy, the only choice is rejecting any write operations while memory exceeds the limitation. In contrast, if you are using Redis as data caching, memory policies have their use, LFU might be more concise, and if your Redis is new enough (>= 4.0), maybe you should try this! Or you can just use LRU, which is also good.